Robotic Online Path Planning on Point Cloud
The DOI matches its Crossref record; 56 of the 56 references it cites were found in a registry or an index.
Abstract
This paper deals with the path-planning problem for mobile wheeled- or tracked-robot which drive in 2.5-D environments, where the traversable surface is usually considered as a 2-D-manifold embedded in a 3-D ambient space. Specially, we aim at solving the 2.5-D navigation problem using raw point cloud as input. The proposed method is independent of traditional surface parametrization or reconstruction methods, such as a meshing process, which generally has high-computational complexity. Instead, we utilize the output of 3-D tensor voting framework on the raw point clouds. The computation of tensor voting is accelerated by optimized implementation on graphics computation unit. Based on the tensor voting results, a novel local Riemannian metric is defined using the saliency components, which helps the modeling of the latent traversable surface. Using the proposed metric, we prove that the geodesic in the 3-D tensor space leads to rational path-planning results by experiments. Compared to traditional methods, the results reveal the advantages of the proposed method in terms of smoothing the robot maneuver while considering the minimum travel distance.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 29,065
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
Marching cubes: A high resolution 3D surface construction algorithm
Lorensen, W. E., & Cline, H. E. (1987) · Proceedings of the 14th annual conference on Computer graphics and interactive techniques · doi:10.1145/37401.37422 · Cited by 10,104 · cited 1×
“, meshed surface [17], [18] or tree-based structures [11], which were inspired from topological segmentation of 2-D”
BackgroundMarching cubes: A high resolution 3D surface construction algorithm
Lorensen, W. E., & Cline, H. E. (1987) · ACM SIGGRAPH Computer Graphics · doi:10.1145/37402.37422 · Cited by 8,647
3D is here: Point Cloud Library (PCL)
Rusu, R. B., & Cousins, S. (2011) · 2011 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2011.5980567 · Cited by 4,885 · cited 1×
“In recent years, the fast development of 3-D mapping techniques [11], [12] and sensors [13] enables the modeling of the multiterrain environment [14] for practical applications [15], [16].”
BackgroundParallel Tracking and Mapping for Small AR Workspaces
Klein, G., & Murray, D. (2007) · 2007 6th IEEE and ACM International Symposium on Mixed and Augmented Reality · doi:10.1109/ismar.2007.4538852 · Cited by 4,346 · cited 1×
“Nowadays, computer vision usually worked as the primary method to get the pose estimation [34], [35].”
MethodRRT-connect: An efficient approach to single-query path planning
Kuffner, J. J., & LaValle, S. M. (2000) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844730 · Cited by 3,555
The Geometry of Algorithms with Orthogonality Constraints
Edelman, A., Arias, T. A., & Smith, S. T. (1998) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479895290954 · Cited by 2,685 · cited 1×
“The tensor split algorithm is using orthogonality constraints proposed in [68].”
MethodSimultaneous localization and mapping (SLAM): part II
Bailey, T., & Durrant-Whyte, H. (2006) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2006.1678144 · Cited by 2,554 · cited 1×
“It is originated from the widely applied representations derived by mature 2-D SLAM techniques [6], such as filteringbased methods [7], [8] or pose-graph-based methods [9].”
MethodEisenhart, L. P. (1950) · Princeton University Press eBooks · doi:10.1515/9781400884216 · Cited by 2,506
Using occupancy grids for mobile robot perception and navigation
Elfes, A. (1989) · Computer · doi:10.1109/2.30720 · Cited by 2,213 · cited 1×
“It is originated from the widely applied representations derived by mature 2-D SLAM techniques [6], such as filteringbased methods [7], [8] or pose-graph-based methods [9].”
MethodFastSLAM: a factored solution to the simultaneous localization and mapping problem
Montemerlo, M., Thrun, S., Koller, D., & Wegbreit, B. (2002) · doi:10.5555/777092.777184 · Cited by 2,012 · cited 1×
“It is originated from the widely applied representations derived by mature 2-D SLAM techniques [6], such as filteringbased methods [7], [8] or pose-graph-based methods [9].”
MethodThe Isomap Algorithm and Topological Stability
Balasubramanian, M., & Schwartz, E. L. (2002) · Science · doi:10.1126/science.295.5552.7a · Cited by 839 · cited 2×
“To this end, we adopt the k-nearest-neighbor (k-NN) concept which is mostly applied in manifold learning methods such as Isomap [75].”
MethodRGB-D Mapping: Using Depth Cameras for Dense 3D Modeling of Indoor Environments
Henry, P., Krainin, M., Herbst, E., Ren, X., & Fox, D. (2014) · Springer Tracts in Advanced Robotics · doi:10.1007/978-3-642-28572-1_33 · Cited by 809 · cited 1×
“In recent years, the fast development of 3-D mapping techniques [11], [12] and sensors [13] enables the modeling of the multiterrain environment [14] for practical applications [15], [16].”
BackgroundComputing geodesics and minimal surfaces via graph cuts
Boykov, & Kolmogorov (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238310 · Cited by 555 · cited 1×
“Inspired by the 2-D metric introduced in [67] and [73], with symmetric positive-definite tensors, we propose the following Riemannian metric:”
MethodThe Office Marathon: Robust navigation in an indoor office environment
Marder-Eppstein, E., Berger, E., Foote, T., Gerkey, B., & Konolige, K. (2010) · 2010 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2010.5509725 · Cited by 517 · cited 1×
“Path planning on 2-D developable plane has been a solved problem, since several open-source libraries were available to the community [39].”
BackgroundChitta, S., Sucan, I., & Cousins, S. (2012) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2011.2181749 · Cited by 466
6D SLAM—3D mapping outdoor environments
Nüchter, A., Lingemann, K., Hertzberg, J., & Surmann, H. (2007) · Journal of Field Robotics · doi:10.1002/rob.20209 · Cited by 450 · cited 1×
“In recent years, the fast development of 3-D mapping techniques [11], [12] and sensors [13] enables the modeling of the multiterrain environment [14] for practical applications [15], [16].”
BackgroundPath Planning for Autonomous Underwater Vehicles
Petres, C., Pailhas, Y., Patron, P., Petillot, Y., Evans, J., & Lane, D. (2007) · IEEE Transactions on Robotics · doi:10.1109/tro.2007.895057 · Cited by 433 · cited 1×
“underwater [45] robots have also been studied, leading to stochastic approaches that cope with the increased complexity in space like rapidly random trees [46] and neural network-based planning [23].”
BackgroundA Computational Framework for Segmentation and Grouping
(2000) · Elsevier eBooks · doi:10.1016/b978-0-444-50353-4.x5000-8 · Cited by 414 · cited 3×
“Tensor voting [22] is a computational framework used for structural extraction based on saliency of basic geometrical elements.”
BackgroundMethodInfluentialEfficient Sparse Pose Adjustment for 2D mapping
Konolige, K., Grisetti, G., Kümmerle, R., Burgard, W., Limketkai, B., & Vincent, R. (2010) · 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems · doi:10.1109/iros.2010.5649043 · Cited by 395 · cited 1×
“D SLAM techniques [6], such as filtering-based methods [7], [8] or pose-graph-based methods [9].”
MethodAutonomous driving in urban environments: approaches, lessons and challenges
Campbell, M., Egerstedt, M., How, J. P., & Murray, R. M. (2010) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2010.0110 · Cited by 353 · cited 1×
“Several researchers have tried to adopt similar algorithms also apply in outdoor scenarios like autonomous cars, where the problem mostly lies in perception and the latent driving rules [40].”
BackgroundGeometric Methods and Applications
Gallier, J. H. (2011) · Texts in applied mathematics · doi:10.1007/978-1-4419-9961-0 · Cited by 345
Bortoff, S. A. (2000) · Proceedings of the 2000 American Control Conference. ACC (IEEE Cat. No.00CH36334) · doi:10.1109/acc.2000.878915 · Cited by 338 · cited 1×
“approaches [32], [33] to generate path in a full 3-D space, regarding different kinematic constraints.”
BackgroundComparison of surface normal estimation methods for range sensing applications
Klasing, K., Althoff, D., Wollherr, D., et al. (2009) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2009.5152493 · Cited by 308 · cited 1×
“Reference [56] is a recent report report on different criteria for surface normal estimation of 3-D range data.”
BackgroundReal-Time Plane Segmentation Using RGB-D Cameras
Holz, D., Holzer, S., Rusu, R. B., & Behnke, S. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-32060-6_26 · Cited by 277 · cited 1×
“These normal estimation results often lead to clustering or segmentation of point cloud, such as by an initial segmentation in normal space, then refines in distance space [51].”
BackgroundAutonomous UAV path planning and estimation
Tisdale, J., Kim, Z., & Hedrick, J. (2009) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2009.932529 · Cited by 275 · cited 1×
“On the other hand, 3-D path planning for aerial [44] or”
BackgroundChallenging data sets for point cloud registration algorithms
Pomerleau, F., Liu, M., Colas, F., & Siegwart, R. (2012) · The International Journal of Robotics Research · doi:10.1177/0278364912458814 · Cited by 263 · cited 1×
“As a sample of use case, we utilize one of the dataset introduced by [78] for the test on real data.”
MethodSelf-citationFinding shortest paths on surfaces using level sets propagation
Kimmel, R., Amir, A., & Bruckstein, A. M. (1995) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.387512 · Cited by 231 · cited 1×
“An efficient method based on contour propagation was proposed in [63].”
MethodReal-time 3d SLAM with wide-angle vision
Davison, A. J., Cid, Y. G., & Kita, N. (2004) · IFAC Proceedings Volumes · doi:10.1016/s1474-6670(17)32089-x · Cited by 174 · cited 1×
“Nowadays, computer vision usually worked as the primary method to get the pose estimation [34], [35].”
MethodMoving Groups of Microparticles Into Array With a Robot–Tweezers Manipulation System
Chen, H., & Sun, D. B. (2012) · IEEE Transactions on Robotics · doi:10.1109/tro.2012.2196309 · Cited by 148 · cited 1×
“THE DEVELOPMENT of robotics is always inspired by human experience and activities [1].”
BackgroundA fast path planning by path graph optimization
Hwang, J. Y., Kim, J. S., Lim, S. S., & Park, K. H. (2003) · IEEE Transactions on Systems Man and Cybernetics - Part A Systems and Humans · doi:10.1109/tsmca.2003.812599 · Cited by 142 · cited 2×
“, meshed surface [17], [18] or tree-based structures [11], which were inspired from topological segmentation of 2-D”
BackgroundAn efficient dynamic system for real-time robot-path planning
Willms, A. R., & Yang, S. X. (2006) · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · doi:10.1109/tsmcb.2005.862724 · Cited by 141
Inference of segmented color and texture description by tensor voting
Jia, J., & Tang, C. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.10 · Cited by 121 · cited 1×
“It has been applied to applications such as segmentation [57], [58].”
MethodExperience in System Design for Human-Robot Teaming in Urban Search and Rescue
Kruijff, G.-J., Janíček, M., Keshavdas, S., Larochelle, B., Zender, H., Smets, N. J. J. M., Mioch, T., Neerincx, M. A., van Diggelen, J., Colas, F., et al. (2013) · Springer tracts in advanced robotics · doi:10.1007/978-3-642-40686-7_8 · Cited by 113 · cited 1×
“D mapping techniques [11], [12] and sensors [13] enables the modeling of the multiterrain environment [14] for practical applications [15], [16].”
BackgroundSelf-citationTensor Voting: A Perceptual Organization Approach to Computer Vision and Machine Learning
Mordohai, P., & Medioni, G. (2006) · Synthesis lectures on image, video, and multimedia processing · doi:10.2200/s00049ed1v01y200609ivm008 · Cited by 108
3D path planning and execution for search and rescue ground robots
Colas, F., Mahesh, S., Pomerleau, F., Liu, M., & Siegwart, R. (2013) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2013.6696431 · Cited by 105 · cited 4×
“However, even with online optimization [10], the dense voting process is generally computationally very expensive, since it requires regeneration of the tensor field at each sampled position.”
BackgroundMethodInfluentialSelf-citationTreatment Planning and Image Guidance for Radiofrequency Ablation of Large Tumors
Ren, H., Campos-Náñez, E., Yaniv, Z. R., Banovac, F., Abeledo, H. G., Hata, N., & Cleary, K. (2013) · IEEE Journal of Biomedical and Health Informatics · doi:10.1109/jbhi.2013.2287202 · Cited by 78 · cited 1×
“coverage optimization [29], [30], and space constraints [31].”
BackgroundVisual Homing From Scale With an Uncalibrated Omnidirectional Camera
Liu, M., Pradalier, C., & Siegwart, R. (2013) · IEEE Transactions on Robotics · doi:10.1109/tro.2013.2272251 · Cited by 75 · cited 1×
“lies on a developable surface [3], [4].”
Self-citationRobust estimation of adaptive tensors of curvature by tensor voting
Tong, W.-S., & Tang, C. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.62 · Cited by 66 · cited 1×
“The readers are referred to [80] for curvature estimation by TVF.”
BackgroundDistance Functions and Geodesics on Submanifolds of $\R^d$ and Point Clouds
Mémoli, F., & Sapiro, G. (2005) · SIAM Journal on Applied Mathematics · doi:10.1137/s003613990342877x · Cited by 64 · cited 1×
“Mémoli and Sapiro [65] explained the intrinsic properties for geodesic on point clouds, considering manifold sampling and noise.”
BackgroundLiu, M., & Siegwart, R. (2013) · IEEE Transactions on Robotics · doi:10.1109/tro.2013.2272250 · Cited by 63 · cited 1×
“D environments [19]–[21].”
Self-citationA Path-Planning Algorithm Using Vector Potential Functions in Triangular Regions
Pamosoaji, A. K., & Hong, K. (2013) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmca.2012.2221457 · Cited by 56 · cited 1×
“Derived from that, such a concept is usually extended to robotic planning for navigation, using various cost or potential functions [2] depending on selected criteria or applications.”
BackgroundTarget-Motion Prediction for Robotic Search and Rescue in Wilderness Environments
Macwan, A., Nejat, G., & Benhabib, B. (2011) · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · doi:10.1109/tsmcb.2011.2132716 · Cited by 49 · cited 1×
“In recent years, the fast development of 3-D mapping techniques [11], [12] and sensors [13] enables the modeling of the multiterrain environment [14] for practical applications [15], [16].”
BackgroundNormal estimation for pointcloud using GPU based sparse tensor voting
Liu, M., Pomerleau, F., Colas, F., & Siegwart, R. (2012) · IEEE International Conference on Robotics and Biomimetics (ROBIO) · doi:10.1109/robio.2012.6490949 · Cited by 38
Self-citationOccupancy Mapping and Surface Reconstruction Using Local Gaussian Processes With Kinect Sensors
Kim, S., & Kim, J. (2013) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2013.2272592 · Cited by 37 · cited 1×
“5) Trajectory is planned on raw point cloud without the preprocessing such as mesh reconstruction [18], [25].”
BackgroundIncremental topological segmentation for semi-structured environments using discretized GVG
Liu, M., Colas, F., Oth, L., & Siegwart, R. (2014) · Autonomous Robots · doi:10.1007/s10514-014-9398-8 · Cited by 36 · cited 2×
“Additionally, when a dense representation is available, applications such as structure analysis [26] and segmentation [20] could be handily treated.”
MethodSelf-citationRobot Navigation in Multi-terrain Outdoor Environments
Pereira, G. A. S., Pimenta, L. C. A., Fonseca, A. R., Corrêa, L. D. Q., Mesquita, R. C., Chaimowicz, L., de Almeida, D. S. C., & Campos, M. F. M. (2009) · The International Journal of Robotics Research · doi:10.1177/0278364908097578 · Cited by 33
Tensor-voting-based navigation for robotic inspection of 3D surfaces using lidar point clouds
Stumm, E. S., Breitenmoser, A., Pomerleau, F., Pradalier, C., & Siegwart, R. (2012) · The International Journal of Robotics Research · doi:10.1177/0278364912461537 · Cited by 32 · cited 1×
“Preliminary work using TVF for planning has been proposed using an iterative algorithm over the dense voting grids [61], where the generated path adapts to smooth local curvature due to the nonholonomic motion constraints.”
MethodChoi, J., Choi, M., Nam, S. Y., & Chung, W. K. (2011) · Autonomous Robots · doi:10.1007/s10514-011-9223-6 · Cited by 29 · cited 1×
“D environments [19]–[21].”
A 3-D-Point-Cloud System for Human-Pose Estimation
Chan, K.-C., Koh, C., & Lee, C. S. G. (2014) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2014.2329266 · Cited by 27 · cited 1×
“Therefore, it is widely used for point cloud analysis [47], [48].”
MethodThe role of homing in visual topological navigation
Liu, M., Pradalier, C., Pomerleau, F., & Siegwart, R. (2012) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2012.6385640 · Cited by 27 · cited 1×
“lies on a developable surface [3], [4].”
Self-citationA parallel point cloud clustering algorithm for subset segmentation and outlier detection
Teutsch, C., Trostmann, E., & Berndt, D. (2011) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.888654 · Cited by 18 · cited 1×
“[52] presented a clustering algorithm for subset segmentation, which targets at segmentation of point clouds without plane-assumption.”
6D SLAM3D mapping outdoor environments
NüchterAndreas, LingemannKai, HertzbergJoachim, & SurmannHartmut (2007) · Journal of Field Robotics · doi:10.5555/1291068.1291071 · Cited by 17
Approximating Geodesics on Point Set Surfaces
Ruggeri, M. R., Darom, T., Saupe, D., & Kiryati, N. (2006) · Cited by 16
Graph cuts using a Riemannian metric induced by tensor voting
Koo, H. I., & Cho, N. I. (2009) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2009.5459195 · Cited by 8 · cited 2×
“Inspired by the 2-D metric introduced in [67] and [73], with symmetric positive-definite tensors, we propose the following Riemannian metric:”
BackgroundMethod
Cited by
A deep-network solution towards model-less obstacle avoidance
Tai, L., Li, S., & Liu, M. (2016) · 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2016.7759428 · Cited by 207
“A series of tasks, such as visual localization[19], visual homing [20], [21], exploration and path-following[22], could be achieved.”
BackgroundSelf-citationEl Ghazouali, S., Mhirit, Y., Oukhrid, A., Michelucci, U., & Nouira, H. (2024) · Sensors · doi:10.3390/s24092889 · Cited by 24
Metadata
- Authors
- Liu, M.
- Venue
- IEEE Transactions on Cybernetics
- Published
- 2016-05
- Volume
- 46
- Issue
- 5
- Pages
- 1217-1228
- ISSN
- 2168-2267 (ISSN-L)
- 2168-2275
- OpenAlex
- W2341115255
- Cited by
- 160
- References
- 56
- FWCI
- 9.53
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.