Motion Planning: A Journey of Robots, Molecules, Digital Actors, and Other Artifacts
The DOI matches its Crossref record; 45 of the 45 references it cites were found in a registry or an index.
Abstract
During the past three decades, motion planning has emerged as a crucial and productive research area in robotics. In the mid-1980s, the most advanced planners were barely able to compute collision-free paths for objects crawling in planar workspaces. Today, planners efficiently deal with robots with many degrees of freedom in complex environments. Techniques also exist to generate quasioptimal trajectories, coordinate multiple robots, deal with dynamic and kinematic constraints, and handle dynamic environments. This paper describes some of these achievements, presents new problems that have recently emerged, discusses applications likely to motivate future research, and finally gives expectations for the coming years. It stresses the fact that nonrobotics applications (e.g., graphic animation, surgical planning, computational biology) are growing in importance and are likely to shape future motion-planning research more than robotics itself.
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
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 1×
“Two popular approaches were introduced in the 1980s: approximate cell decomposition, where the free space is represented by a collection of simple cells (Brooks and Lozano-Pérez 1983), and potential field (Khatib 1986).”
BackgroundLatombe, J.-C. (1991) · Springer eBooks · doi:10.1007/978-1-4615-4022-9 · Cited by 6,396
Self-citationProbabilistic 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 · cited 2×
“To avoid pathological cases caused by the deterministic potential field, another type of randomized planner was later developed (Kavraki et al. 1996), which consists of sampling the configuration space at random and connecting the samples in free space by “local” paths (typically straight paths), thus creating a proba…”
Self-citationAn algorithm for planning collision-free paths among polyhedral obstacles
Lozano-Pérez, T., & Wesley, M. A. (1979) · Communications of the ACM · doi:10.1145/359156.359164 · Cited by 2,304
Spatial Planning: A Configuration Space Approach
Lozano-Perez (1983) · IEEE Transactions on Computers · doi:10.1109/tc.1983.1676196 · Cited by 2,113
The complexity of robot motion planning
Canny, J. (1988) · Medical Entomology and Zoology · Cited by 1,375
Robot Motion Planning: A Distributed Representation Approach
Barraquand, J., & Latombe, J.-C. (1991) · The International Journal of Robotics Research · doi:10.1177/027836499101000604 · Cited by 995
Self-citationAutomatic Synthesis of Fine-Motion Strategies for Robots
Lozano-Pérez, T., Mason, M. T., & Taylor, R. H. (1984) · The International Journal of Robotics Research · doi:10.1177/027836498400300101 · Cited by 898
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
Randomized kinodynamic planning
LaValle, S. M., & Kuffner, J. J. (2003) · Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No.99CH36288C) · doi:10.1109/robot.1999.770022 · Cited by 673
Video Rewrite: driving visual speech with audio
Bregler, C., Covell, M., & Slaney, M. (1997) · Proceedings of the 24th annual conference on Computer graphics and interactive techniques - SIGGRAPH '97 · doi:10.1145/258734.258880 · Cited by 669
A motion planner for nonholonomic mobile robots
Laumond, J.-P., Jacobs, P. E., Taix, M., & Murray, R. M. (1994) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.326564 · Cited by 583
A Mobile Automaton: An Application of Artificial Intelligence Techniques
Nilsson, N. J. (1969) · doi:10.21236/ada459660 · Cited by 552
Path planning in expansive configuration spaces
Hsu, D., Latombe, J.-C., & Motwani, R. (2002) · Proceedings of International Conference on Robotics and Automation · doi:10.1109/robot.1997.619371 · Cited by 552
Self-citationA fast algorithm for incremental distance calculation
Lin, M. C., & Canny, J. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1991.131723 · Cited by 475
An exploration of sensorless manipulation
Erdmann, M. A., & Mason, M. T. (1988) · IEEE Journal on Robotics and Automation · doi:10.1109/56.800 · Cited by 463
Orienting polygonal parts without sensors
Goldberg, K. Y. (1993) · Algorithmica · doi:10.1007/bf01891840 · Cited by 437
Efficient distance computation between non-convex objects
Quinlan, S. (2002) · Proceedings of the 1994 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1994.351059 · Cited by 391
AUTOPASS: An Automatic Programming System for Computer Controlled Mechanical Assembly
Lieberman, L. I., & Wesley, M. A. (1977) · IBM Journal of Research and Development · doi:10.1147/rd.214.0321 · Cited by 326
On Finding Narrow Passages with Probabilistic Roadmap Planners
(1998) · Robotics: The Algorithmic Perspective · doi:10.1201/9781439863886-18 · Cited by 307
Toward realistic soft-tissue modeling in medical simulation
Delingette, H. (1998) · Proceedings of the IEEE · doi:10.1109/5.662876 · Cited by 303
Barraquand, J., & Latombe, J. C. (1993) · Algorithmica · doi:10.1007/bf01891837 · Cited by 293
Self-citationGeometric reasoning about mechanical assembly
Wilson, R. H., & Latombe, J.-C. (1994) · Artificial Intelligence · doi:10.1016/0004-3702(94)90048-5 · Cited by 292
Self-citationPlanning motions with intentions
Koga, Y., Kondo, K., Kuffner, J., & Latombe, J.-C. (1994) · Proceedings of the 21st annual conference on Computer graphics and interactive techniques - SIGGRAPH '94 · doi:10.1145/192161.192266 · Cited by 269
Self-citationOn 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-citationChoosing good distance metrics and local planners for probabilistic roadmap methods
Amato, N. M., Bayazit, O. B., Dale, L. K., Jones, C., & Vallejo, D. (2002) · Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat. No.98CH36146) · doi:10.1109/robot.1998.677043 · Cited by 184
Coordinated motion planning for multiple car-like robots using probabilistic roadmaps
Svestka, P., & Overmars, M. H. (2002) · Proceedings of 1995 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1995.525508 · Cited by 165
Two manipulation planning algorithms
Alami, R., Laumond, J., & Siméon, T. (1994) · HAL · Cited by 137
Assembly maintainability study with motion planning
Chang, H. T., & Li, T. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1995.525415 · Cited by 130
On multi-arm manipulation planning
Koga, Y., & Latombe, J.-C. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1994.351231 · Cited by 129
Self-citationPractical Motion Planning in Robotics: Current Approaches and Future Directions
Gupta, K. K., & del Pobil, A. P. (1998) · John Wiley & Sons, Inc. eBooks · Cited by 122
The Design of a Mechanical Assembly System
Lozano‐Pérez, T. (1976) · Defense Technical Information Center (DTIC) · Cited by 114
A motion planning approach to flexible ligand binding.
Singh, A. P., Latombe, J.-C., & Brutlag, D. L. (1999) · PubMed · Cited by 107
Self-citationRandomized query processing in robot path planning
Kavraki, L. E., Latombe, J., Motwani, R., & Raghavan, P. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225159 · Cited by 104
Self-citationPlanning the motions of a mobile robot in a sensory uncertainty field
Takeda, H., Facchinetti, C., & Latombe, J.-C. (1994) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.329009 · Cited by 99
Self-citationMotion planning with uncertainty: a landmark approach
Lazanas, A., & Latombe, J. (1995) · Artificial Intelligence · doi:10.1016/0004-3702(94)00079-g · Cited by 96
Self-citationPart orientation with one or two stable equilibria using programmable force fields
Böhringer, K. F., Donald, B. R., Kavraki, L. E., & Lamiraux, F. (2000) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.843172 · Cited by 82
Algorithms for Robotic Motion and Manipulation
Laumond, J., & Overmars, M. H. (1997) · A K Peters/CRC Press eBooks · doi:10.1201/9781439864524 · Cited by 76
Placing a robot manipulator amid obstacles for optimized execution
Hsu, D., Latcombe, J.-C., & Sorkin, S. (2003) · IEEE International Symposium on Assembly and Task Planning (ISATP) · doi:10.1109/isatp.1999.782972 · Cited by 71
Video Rewrite: Driving Visual Speech with Audio
Bregler, C., Covell, M., & Slaney, M. (2023) · Seminal Graphics Papers: Pushing the Boundaries, Volume 2 · doi:10.1145/3596711.3596787 · Cited by 67 · cited 2×
“A system like the one described in [9] solves the problem more e ciently by associating pnonemes to video captured motions and applying morphing techniques to combine these”
MethodMotion planning for a rigid body using random networks on the medial axis of the free space
Wilmarth, S. A., Amato, N. M., & Stiller, P. F. (1999) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/304893.304967 · Cited by 58
Partitioning and Handling Massive Models for Interactive Collision Detection
Wilson, A., Larsen, E., Manocha, D., & Lin, M. C. (1999) · Computer Graphics Forum · doi:10.1111/1467-8659.00352 · Cited by 50
Elastic strips: A framework for integrated planning and execution
Brock, O., & Khatib, O. (2008) · Springer eBooks · doi:10.1007/bfb0119411 · Cited by 48
Constraint-based interactive assembly planning
Jones, R. E., Wilson, R. H., & Calton, T. L. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1997.614251 · Cited by 30
Cited by
Sampling-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
Anytime Motion Planning using the RRT*
Karaman, S., Walter, M. R., Perez, A., Frazzoli, E., & Teller, S. (2011) · 2011 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2011.5980479 · Cited by 881
Bohlin, R., & Kavraki, L. E. (2000) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844107 · Cited by 856
Real-Time Motion Planning for Agile Autonomous Vehicles
Frazzoli, E., Dahleh, M. A., & Feron, E. (2002) · Journal of Guidance, Control, and Dynamics · doi:10.2514/2.4856 · Cited by 830
Sampling-Based Robot Motion Planning: A Review
Elbanhawi, M., & Simic, M. (2014) · IEEE Access · doi:10.1109/access.2014.2302442 · Cited by 786
Metadata
- Authors
- Latombe, J.-C.
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 1999-11
- Volume
- 18
- Issue
- 11
- Pages
- 1119-1128
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W2037907469
- Cited by
- 264
- References
- 45
- FWCI
- 10.27
- 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.