The DOI matches its Crossref record; 98 of the 98 references it cites were found in a registry or an index.
Gross motion planning—a survey
Open accessAbstract
Motion planning is one of the most important areas of robotics research. The complexity of the motion-planning problem has hindered the development of practical algorithms. This paper surveys the work on gross-motion planning, including motion planners for point robots, rigid robots, and manipulators in stationary, time-varying, constrained, and movable-object environments. The general issues in motion planning are explained. Recent approaches and their performances are briefly described, and possible future research directions are discussed.
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
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
Introduction to automata theory, languages and computation
(1981) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(81)90068-9 · Cited by 10,699
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
Latombe, J.-C. (1991) · Springer eBooks · doi:10.1007/978-1-4615-4022-9 · Cited by 6,396
Voronoi diagrams—a survey of a fundamental geometric data structure
Aurenhammer, F. (1991) · ACM Computing Surveys · doi:10.1145/116873.116880 · Cited by 4,340
Computational Geometry--An Introduction.
Atallah, M. J., Preparata, F. P., & Shamos, M. I. (1986) · Mathematics of Computation · doi:10.2307/2008200 · Cited by 4,238
Proceedings. 1985 IEEE International Conference on Robotics and Automation
(1985) · doi:10.1109/robot.1985 · Cited by 3,673
Dubins, L. E. (1957) · American Journal of Mathematics · doi:10.2307/2372560 · Cited by 3,045
Impedance Control: An Approach to Manipulation
Hogan, N. (1984) · 1984 American Control Conference · doi:10.23919/acc.1984.4788393 · Cited by 2,929
2009 International Joint Conference on Artificial Intelligence
(2009) · doi:10.1109/jcai15434.2009 · Cited by 2,800
An 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
2013 IEEE International Conference on Robotics and Automation
(2013) · doi:10.1109/icra19839.2013 · Cited by 2,025
Real-Time Obstacle Avoidance for Manipulators and Mobile Robots
Khatib, O. (1986) · Autonomous Robot Vehicles · doi:10.1007/978-1-4613-8997-2_29 · Cited by 1,569
A fast procedure for computing the distance between complex objects in three-dimensional space
Gilbert, E. G., Johnson, D. W., & Keerthi, S. S. (1988) · IEEE Journal on Robotics and Automation · doi:10.1109/56.2083 · Cited by 1,513
The complexity of robot motion planning
Canny, J. (1988) · Medical Entomology and Zoology · Cited by 1,375
Time-Optimal Control of Robotic Manipulators Along Specified Paths
Bobrow, J. E., Dubowsky, S., & Gibson, J. S. (1985) · The International Journal of Robotics Research · doi:10.1177/027836498500400301 · Cited by 1,315
Shamos, M. I., & Hoey, D. (1975) · 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) · doi:10.1109/sfcs.1975.8 · Cited by 1,057
Proceedings. 1988 IEEE International Conference on Robotics and Automation
(1988) · doi:10.1109/robot.1988 · Cited by 984
Schwartz, J. T., & Sharir, M. (1983) · Advances in Applied Mathematics · doi:10.1016/0196-8858(83)90014-3 · Cited by 801
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
Mitchell, J. S. B., Mount, D. M., & Papadimitriou, C. H. (1987) · SIAM Journal on Computing · doi:10.1137/0216045 · Cited by 720
A potential field approach to path planning
Hwang, Y. K., & Ahuja, N. (1992) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.127236 · Cited by 684
Self-citationA 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
Solving the find-path problem by good representation of free space
Brooks, R. A. (1983) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1983.6313112 · Cited by 601
Position referencing and consistent world modeling for mobile robots
Chatila, R., & Laumond, J. (2005) · Proceedings. 1985 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1985.1087373 · Cited by 567
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
New lower bound techniques for robot motion planning problems
Canny, J., & Reif, J. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.42 · Cited by 538
Hopcroft, J. E., Schwartz, J. T., & Sharir, M. (1984) · The International Journal of Robotics Research · doi:10.1177/027836498400300405 · Cited by 528
A 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
Schwartz, J. T., & Sharir, M. (1983) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.3160360305 · Cited by 454
Impedance Control: An Approach to Manipulation: Part III—Applications
Hogan, N. (1985) · Journal of Dynamic Systems, Measurement, and Control · doi:10.1115/1.3140701 · Cited by 452
Multiresolution path planning for mobile robots
Kambhampati, S., & Davis, L. (1986) · IEEE Journal on Robotics and Automation · doi:10.1109/jra.1986.1087051 · Cited by 442
A “retraction” method for planning the motion of a disc
Ó'Dúnlaing, C., & Yap, C. K. (1985) · Journal of Algorithms · doi:10.1016/0196-6774(85)90021-5 · Cited by 404
Global path planning using artificial potential fields
Warren, C. W. (2003) · Proceedings, 1989 International Conference on Robotics and Automation · doi:10.1109/robot.1989.100007 · Cited by 370
Distance functions and their application to robot path planning in the presence of obstacles
Gilbert, E., & Johnson, D. (1985) · IEEE Journal on Robotics and Automation · doi:10.1109/jra.1985.1087003 · Cited by 367
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
On Shortest Paths in Polyhedral Spaces
Sharir, M., & Schorr, A. (1986) · SIAM Journal on Computing · doi:10.1137/0215014 · 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
Shortest paths on a polyhedron
Chen, J., & Han, Y. (1990) · Proceedings of the sixth annual symposium on Computational geometry - SCG '90 · doi:10.1145/98524.98601 · Cited by 301
Constructing the visibility graph for n-line segments in O(n2) time
Welzl, E. (1985) · Information Processing Letters · doi:10.1016/0020-0190(85)90044-4 · Cited by 298
The weighted region problem: finding shortest paths through a weighted planar subdivision
Mitchell, J. S. B., & Papadimitriou, C. H. (1991) · Journal of the ACM · doi:10.1145/102782.102784 · Cited by 295
AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments
Yap, C. K. (1987) · Discrete & Computational Geometry · doi:10.1007/bf02187890 · Cited by 294
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
Efficient computation of continuous skeletons
Kirkpatrick, D. G. (1979) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1979.15 · Cited by 262
Integrated path planning and dynamic steering control for autonomous vehicles
Krogh, B., & Thorpe, C. (1986) · Proceedings. 1986 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1986.1087444 · Cited by 259
Schwartz, J. T., & Sharir, M. (1983) · The International Journal of Robotics Research · doi:10.1177/027836498300200304 · Cited by 248
A Monte-Carlo algorithm for path planning with many degrees of freedom
Barraquand, J., & Latombe, J.-C. (2002) · Proceedings., IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1990.126256 · Cited by 247
A linear algorithm for computing the visibility polygon from a point
ElGindy, H. A., & Avis, D. (1981) · Journal of Algorithms · doi:10.1016/0196-6774(81)90019-5 · Cited by 244
Superquadric artificial potentials for obstacle avoidance and approach
Khosla, P., & Volpe, R. (2003) · Proceedings. 1988 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1988.12323 · Cited by 237
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
Planning Smooth Paths for Mobile Robots
Jacobs, P., & Canny, J. (1993) · Nonholonomic Motion Planning · doi:10.1007/978-1-4615-3176-0_8 · Cited by 220
Real-time robot motion planning using rasterizing computer graphics hardware
Lengyel, J., Reichert, M., Donald, B. R., & Greenberg, D. P. (1990) · Proceedings of the 17th annual conference on Computer graphics and interactive techniques · doi:10.1145/97879.97915 · Cited by 215
Discrete and Computational Geometry
Aronov, B. S., Goodman, E., & Pollack, R. (2003) · Algorithms and combinatorics · doi:10.1007/978-3-642-55566-4 · Cited by 209
Computing the distance between general convex objects in three-dimensional space
Gilbert, E. G., & Foo, C.-P. (1990) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.88117 · Cited by 201
Path Relaxation: Path Planning for a Mobile Robot
Thorpe, C., & Matthies, L. (1984) · OCEANS 1984 · doi:10.1109/oceans.1984.1152243 · Cited by 185
On the complexity of kinodynamic planning
Canny, J., Donald, B., Reif, J., & Xavier, P. (1988) · [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1988.21947 · Cited by 184
Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition
Collins, G. E. (1998) · Texts & monographs in symbolic computation/Texts and monographs in symbolic computation · doi:10.1007/978-3-7091-9459-1_4 · Cited by 168
[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science
(1988) · doi:10.1109/sfcs.1988 · Cited by 167
Task-level planning of pick-and-place robot motions
Lozano-Perez, T., Jones, J. L., Mazer, E., & O'Donnell, P. A. (1989) · Computer · doi:10.1109/2.16222 · Cited by 161
Handey: A robot system that recognizes, plans, and manipulates
Lozano‐Pérez, T., Jones, J. L., Mazer, E., O'Donnell, P. A., Grimson, W. E. L., Tournassoud, P., & Lanusse, A. (2005) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1987.1087847 · Cited by 160
Kondo, K. (1991) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.88136 · Cited by 157
Motion planning in the presence of movable obstacles
Wilfong, G. (1988) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/73393.73422 · Cited by 149
A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles
Avnaïm, F., Boissonnat, J. D., & Faverjon, B. (1989) · Lecture notes in computer science · doi:10.1007/3-540-51683-2_25 · Cited by 149
Proceedings of the 4th international symposium on Robotics Research
Bolles, R. C., & Roth, B. (1988) · Cited by 137
Proximity and reachability in the plane.
Lee, D.-T. (1978) · Defense Technical Information Center (DTIC) · Cited by 132
Robot planning and control via potential functions
Koditschek, D. E. (1989) · ScholarlyCommons (University of Pennsylvania) · Cited by 130
On the general motion-planning problem with two degrees of freedom
Guibas, L. J., Sharir, M., & Sifrony, S. (1989) · Discrete & Computational Geometry · doi:10.1007/bf02187744 · Cited by 115
Fast, three-dimensional, collision-free motion planning
Herman, M. (1986) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1986.1087622 · Cited by 105
High speed robot control and obstacle avoidance using dynamic potential functions
Newman, W. S., & Hogan, N. (2005) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1987.1088046 · Cited by 105
Motion planning with inertial constraints
Ó'Dúnlaing, C. (1987) · Algorithmica · doi:10.1007/bf01840370 · Cited by 95
Fortune, S., & Wilfong, G. (1988) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/62212.62256 · Cited by 94
Motion Planning with Six Degrees of Freedom
Donald, B. R. (1984) · Defense Technical Information Center (DTIC) · Cited by 92
A framework of knowledge-based assembly planning
Huang, Y. F., & Lee, C. S. G. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1991.131647 · Cited by 87
SANDROS: a motion planner with performance proportional to task difficulty
Chen, P. C., & Hwang, Y. K. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1992.220112 · Cited by 85
Self-citationEffect of kinematics on motion planning for planar robot arms moving amidst unknown obstacles
Lumelsky, V. (1987) · IEEE Journal on Robotics and Automation · doi:10.1109/jra.1987.1087094 · Cited by 84
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
Some Heuristics for the Navigation of a Robot
Chattergy, R. (1985) · The International Journal of Robotics Research · doi:10.1177/027836498500400105 · Cited by 82
Motion Planning for an Autonomous Vehicle
Wilfong, G. (1990) · Springer eBooks · doi:10.1007/978-1-4613-8997-2_28 · Cited by 81
Global time optimal motions of robotic manipulators in the presence of obstacles
Shiller, Z., & Dubowsky, S. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1988.12076 · Cited by 78
SPAR: a planner that satisfies operational and geometric goals in uncertain environments
Hutchinson, S., & Kak, A. C. (1990) · doi:10.1609/aimag.v11i1.823 · Cited by 77
Exact robot navigation using cost functions: the case of distinct spherical boundaries in E/sup n/
Rimon, E., & Koditschek, D. E. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1988.12325 · Cited by 77
Canny, J., & Donald, B. R. (1987) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/41958.41974 · Cited by 76
Real-Time Pathfinding in Multirobot Systems Including Obstacle Avoidance
Freund, Ε., & Hoyer, H. (1988) · The International Journal of Robotics Research · doi:10.1177/027836498800700104 · Cited by 73
An opportunistic global path planner
Canny, J., & Lin, M. C. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1990.126229 · Cited by 67
On the Movement of Robot Arms in 2-Dimensional Bounded Regions
Hopcroft, J. E., Joseph, D., & Whitesides, S. H. (1985) · SIAM Journal on Computing · doi:10.1137/0214025 · Cited by 67
Parallel robot motion planning
Lozano‐Pérez, T., & O'Donnell, P. A. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1991.131722 · Cited by 64
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 55
Sensor interpretation and task-directed planning using perceptual equivalence classes
Donald, B. R., & Jennings, J. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1991.131977 · Cited by 52
Shortest paths on polyhedral surfaces
O’Rourke, J., Suri, S., & Booth, H. (2005) · Springer eBooks · doi:10.1007/bfb0024013 · Cited by 45
Planning Strategic Paths Through Variable Terrain Data
Mitchell, J. S. B., & Keirsey, D. M. (1984) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.943182 · Cited by 44
Time-minimal paths among moving obstacles
Fujimura, K., & Samet, H. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1989.100129 · Cited by 37
Motion planning for robot arm manipulators with proximity sensing
Cheung, E. B., & Lumelsky, V. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1988.12147 · Cited by 35
Path planning among moving obstacles using spatial indexing
Fujimura, K., & Samet, H. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1988.12305 · Cited by 33
Automatic obstacle avoidance at high speeds via reflex control
Newman, W. S. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1989.100128 · Cited by 28
Kedem, K., & Sharir, M. (1988) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/73393.73427 · Cited by 23
Robotic manipulators and the geometry of real semialgebraic sets
Tannenbaum, A., & Yomdin, Y. (1987) · IEEE Journal on Robotics and Automation · doi:10.1109/jra.1987.1087105 · Cited by 22
(1990)
Cited by
A Review of Motion Planning Techniques for Automated Vehicles
Gonzalez, D., Perez, J., Milanes, V., & Nashashibi, F. (2016) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2015.2498841 · Cited by 1,670
Vision for mobile robot navigation: a survey
Desouza, G. N., & Kak, A. C. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.982903 · Cited by 1,357
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
A Survey of Motion Planning Algorithms from the Perspective of Autonomous UAV Guidance
Goerzen, C., Kong, Z., & Mettler, B. (2010) · Journal of Intelligent and Robotic Systems · doi:10.1007/s10846-009-9383-1 · Cited by 779
Obstacle avoidance in a dynamic environment: a collision cone approach
Chakravarthy, A., & Ghose, D. (1998) · IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans · doi:10.1109/3468.709600 · Cited by 556
Metadata
- Authors
- Hwang, Y. K., & Ahuja, N.
- Venue
- ACM Computing Surveys
- Published
- 1992-09
- Volume
- 24
- Issue
- 3
- Pages
- 219-291
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2051626883
- Cited by
- 826
- References
- 98
- FWCI
- 22.13
- Type
- journal article
- Language
- en
- Open access
- bronze
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.