Robot Motion Planning: A Distributed Representation Approach
The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Abstract
We propose a new approach to robot path planning that consists of building and searching a graph connecting the local minima of a potential function defined over the robot's configuration space. A planner based on this approach has been implemented. This planner is consider ably faster than previous path planners and solves prob lems for robots with many more degrees of freedom (DOFs). The power of the planner derives both from the "good" properties of the potential function and from the efficiency of the techniques used to escape the local min ima of this function. The most powerful of these tech niques is a Monte Carlo technique that escapes local min ima by executing Brownian motions. The overall approach is made possible by the systematic use of distributed rep resentations (bitmaps) for the robot's work space and configuration space. We have experimented with the plan ner using several computer-simulated robots, including rigid objects with 3 DOFs (in 2D work space) and 6 DOFs (in 3D work space) and manipulator arms with 8, 10, and 31 DOFs (in 2D and 3D work spaces). Some of the most significant experiments are reported in this article.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“RRT is faster than PRM and both are probabilistically complete [257], which means a path that satisfies the given conditions will be guaranteed to be found with enough runtime.”
From A Survey of Autonomous Driving: Common Practices and Emerging Technologies (2020) · cites this paper as [257]
Citations
Cites
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949
Probability, Random Variables, and Stochastic Processes.
Abrahams, J., & Papoulis, A. (1984) · Journal of the American Statistical Association · doi:10.2307/2288754 · Cited by 16,226
Probability, Random Variables, and Stochastic Processes
Miller, I. (1966) · Technometrics · doi:10.1080/00401706.1966.10490365 · Cited by 8,452
Image analysis and mathematical morphology
(1982) · Computer Graphics and Image Processing · doi:10.1016/0146-664x(82)90078-8 · Cited by 8,151
Real-Time Obstacle Avoidance for Manipulators and Mobile Robots
Khatib, O. (1986) · The International Journal of Robotics Research · doi:10.1177/027836498600500106 · Cited by 7,894 · cited 2×
“For example, a widely used heuristics consists of guiding the robot along the negated gradient of an artificial potential field (Khatib 1986).”
Latombe, J.-C. (1991) · Springer eBooks · doi:10.1007/978-1-4615-4022-9 · Cited by 6,396
Self-citationImage Analysis and Mathematical Morphology.
Diggle, P. J., & Serra, J. (1983) · Biometrics · doi:10.2307/2531038 · Cited by 3,894
Principles of Artificial Intelligence
Nilsson, N. J. (1982) · doi:10.1007/978-3-662-09438-9 · Cited by 3,457
Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
Černý, V. (1985) · Journal of Optimization Theory and Applications · doi:10.1007/bf00940812 · Cited by 3,436
Data Structures and Algorithms
(2003) · Series on software engineering and knowledge engineering · doi:10.1142/9789812791245 · Cited by 2,117
Spatial Planning: A Configuration Space Approach
Lozano-Perez (1983) · IEEE Transactions on Computers · doi:10.1109/tc.1983.1676196 · Cited by 2,113
Data Structures and Algorithms
Wirth, N. (1984) · Scientific American · doi:10.1038/scientificamerican0984-60 · Cited by 1,418
The complexity of robot motion planning
Canny, J. (1988) · Medical Entomology and Zoology · Cited by 1,375
Schwartz, J. T., & Sharir, M. (1983) · Advances in Applied Mathematics · doi:10.1016/0196-8858(83)90014-3 · Cited by 801
Complexity of the mover's problem and generalizations
Reif, J. H. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.10 · Cited by 765
Toward Efficient Trajectory Planning: The Path-Velocity Decomposition
Kant, K., & Zucker, S. W. (1986) · The International Journal of Robotics Research · doi:10.1177/027836498600500304 · Cited by 753
Principles of artificial intelligence
Schliferstein, A. (1981) · Proceedings of the IEEE · doi:10.1109/proc.1981.12145 · Cited by 644
A simple motion-planning algorithm for general robot manipulators
Lozano-Perez, T. (1987) · IEEE Journal on Robotics and Automation · doi:10.1109/jra.1987.1087095 · Cited by 618
A subdivision algorithm in configuration space for findpath with rotation
Brooks, R. A., & Lozano-Perez, T. (1985) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1985.6313352 · Cited by 550
Schwartz, J. T., & Sharir, M. (1983) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.3160360305 · Cited by 454
Exact robot navigation by means of potential functions: Some topological considerations
Koditschek, D. (2005) · Proceedings. 1987 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1987.1088038 · Cited by 345
Diffusions for Global Optimization
Geman, S., & Hwang, C.-R. (1986) · SIAM Journal on Control and Optimization · doi:10.1137/0324060 · Cited by 313
Generalization of Voronoi Diagrams in the Plane
Lee, D. T., & Drysdale, III (1981) · SIAM Journal on Computing · doi:10.1137/0210006 · Cited by 312
A local based approach for path planning of manipulators with a high number of degrees of freedom
Faverjon, B., & Tournassoud, P. (2005) · Proceedings. 1987 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1987.1087982 · Cited by 281
Schwartz, J. T., & Sharir, M. (1983) · The International Journal of Robotics Research · doi:10.1177/027836498300200304 · Cited by 248
Planning, geometry, and complexity of robot motion
Schwartz, J. T., Sharir, M., & Hopcroft, J. E. (1986) · Cited by 244
Stochastic stereo matching over scale
Barnard, S. T. (1989) · International Journal of Computer Vision · doi:10.1007/bf00054836 · Cited by 242
VLSI Placement and Global Routing Using Simulated Annealing
Sechen, C. (1988) · The Kluwer International Series in Engineering and Computer Science · doi:10.1007/978-1-4613-1697-8 · Cited by 236
Deadlock-free and collision-free coordination of two robot manipulators
O'Donnell, P. A., & Lozano-Perez, T. (1989) · Proceedings, 1989 International Conference on Robotics and Automation · doi:10.1109/robot.1989.100033 · Cited by 227
Obstacle avoidance using an octree in the configuration space of a manipulator
Faverjon, B. (2005) · Proceedings. 1984 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1984.1087218 · Cited by 211
On nonholonomic mobile robots and optimal maneuvering
Barraquand, J., & Latombe, J.-C. (2003) · Proceedings. IEEE International Symposium on Intelligent Control 1989 · doi:10.1109/isic.1989.238696 · Cited by 198
Self-citationNew heuristic algorithms for efficient hierarchical path planning
Zhu, D. J., & Latombe, J.-C. (1991) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.68066 · Cited by 191
Self-citationRetraction: A new approach to motion-planning
Ó'Dúnlaing, C., Sharir, M., & Yap, C. K. (1983) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800061.808750 · Cited by 171
A survey of motion planning and related geometric algorithms
Schwartz, J. T., & Sharir, M. (1988) · Artificial Intelligence · doi:10.1016/0004-3702(88)90053-7 · Cited by 157
Strategies for Solving Collision-free Trajectories Problems for Mobile and Manipulator Robots
Gouzènes, L. (1984) · The International Journal of Robotics Research · doi:10.1177/027836498400300403 · Cited by 151
Small Random perturbation of dynamical systems with reflecting boundary
Anderson, R. F., & Orey, S. (1976) · Nagoya Mathematical Journal · doi:10.1017/s0027763000017232 · Cited by 126
Motion Planning with Six Degrees of Freedom
Donald, B. R. (1984) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 94
Erdmann, M. A., & Lozano‐Pérez, T. (1986) · Defense Technical Information Center (DTIC) · doi:10.21236/ada196213 · Cited by 92
Robot motion planning with many degrees of freedom and dynamic constraints
Barraquand, J., Langlois, B., & Latombe, J. (1991) · International Symposium on Robotics · Cited by 88
Self-citationThe construction of analytic diffeomorphisms for exact robot navigation on star worlds
Rimon, E., & Koditschek, D. E. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1989.99962 · Cited by 85
A geometrical approach to planning manipulation tasks. The case of discrete placements and grasps
Alami, R., Siméon, T., & Laumond, J. (1990) · HAL · Cited by 82
Motion Planning with Six Degrees of Freedom. Revision
Donald, B. R. (1984) · Defense Technical Information Center (DTIC) · doi:10.21236/ada181538 · Cited by 74
Object level programming of industrial robots
Faverjon, B. (1986) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1986.1087412 · Cited by 60
Controllability of Mobile Robots with Kinematic Constraints.
Barraquand, J., & Latombe, J. (1990) · Defense Technical Information Center (DTIC) · doi:10.21236/ada326998 · Cited by 23
Self-citationAlgorithmic issues of sensor-based robot motion planning
Lumelsky, V. (1987) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.1987.272799 · Cited by 20
Research works printed but not linked: 16
- Barnard, S.T., 1988, Computer Vision, 2
- Barraquand, J., 1988, Markovian random fields in computer vision: Applications to seismic data understanding
- Barraquand, J., Proc. of the 4th IEEE Int. Symp. on Intelligent Control
- Barraquand, J., 1989, Robot Motion Planning: A Distributed Representation Approach. Report no. STAN-CS-89-1257
- Brooks, R.A., Proc. of the 8th Int. Joint Conf. on Artificial Intelligence
- Faverjon, B., Proc. of the IEEE Int. Conf. on Robotics and Automation
- Faverjon, B., Proc. of the IEEE Int. Conf. on Robotics and Automation
- Faverjon, B., Proc. of the IEEE Int. Conf. on Automation and Robotics
- Koditschek, D.E., Proc. of the IEEE Int. Conf. on Robotics and Automation
- Laugier, C., 1985, Int. Conf. on Advanced Robotics.
- Lumelsky, V., Proc. of the 26th IEEE Conf. on Decision and Control
- Métivier, C., 1990, Run-time statistical analysis of a robot motion planning algorithm. Internal technical note. Robotics Laboratory, Dept. of Computer Science
- O'Donnell, P.A., Proc. of the IEEE Int. Conf. on Robotics and Automation
- Ó'Dúnlaing, C., Proc. of the 15th ACM Symp. on the Theory of Computing
- Reif, J.H., 1979, Science, 421
- Rimon, E., Proc. of the IEEE Int. Conf. on Robotics and Automation
Cited by
Probabilistic roadmaps for path planning in high-dimensional configuration spaces
Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.508439 · Cited by 6,343
“For example, for planar articulated robots with many dofs, the customized implementation of Section V is much more consistent than the Randomized Path Planner (RPP) of [ 6 ].”
InfluentialSelf-citationSampling-based algorithms for optimal motion planning
Karaman, S., & Frazzoli, E. (2011) · The International Journal of Robotics Research · doi:10.1177/0278364911406761 · Cited by 5,275
Randomized Kinodynamic Planning
LaValle, S. M., & Kuffner, J. J. (2001) · The International Journal of Robotics Research · doi:10.1177/02783640122067453 · Cited by 3,254
A Survey of Autonomous Driving: Common Practices and Emerging Technologies
Yurtsever, E., Lambert, J., Carballo, A., & Takeda, K. (2020) · IEEE Access · doi:10.1109/access.2020.2983149 · Cited by 1,889
“Randomized Potential Planner (RPP) [252] is one of the earliest SBP approaches, where random walks are generated for escaping local minimums.”
BackgroundMethodNumerical potential field techniques for robot path planning
Barraquand, J., Langlois, B., & Latombe, J.-C. (1992) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/21.148426 · Cited by 889
Self-citation
Metadata
- Authors
- Barraquand, J., & Latombe, J.-C.
- Affiliations
- Stanford University (US)
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 1991-12
- Volume
- 10
- Issue
- 6
- Pages
- 628-649
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W1978301848
- Cited by
- 995
- References
- 46
- Citations by year
- 2026: 7 · 2025: 11 · 2024: 17 · 2023: 9 · 2022: 18 · 2021: 32 · 2020: 28 · 2019: 23 · 2018: 23 · 2017: 19 · 2016: 37 · 2015: 21 · 2014: 24 · 2013: 24 · 2012: 20
- FWCI
- 37.68
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- journals.sagepub.com/page/policies/text-and-data-mining-license (tdm)
- Locations
- The International Journal of Robotics Research (publishedVersion)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Robotic Path Planning Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Keywords
- robot path planning, motion planning, distributed representations, bitmaps, potential function, local minima, Monte Carlo methods, Brownian motion, configuration space, high-degree-of-freedom robots, robot manipulators
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.