{ "id": "ep98t6kt5e", "slug": "path-planning-algorithm", "title": "Path-planning algorithm", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.algorithms" }, { "id": "technology.computing.ai.graph_network_algorithms", "label": "Graph and network algorithms", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.graph_network_algorithms" }, { "id": "technology.computing.ai.graph_network_algorithms.shortest_path_algorithms", "label": "Shortest paths", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.graph_network_algorithms.shortest_path_algorithms" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Non-geographic · 1946 to 2000: Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms" } ] }, { "id": "geo.nongeo.t2001.technology.computing.ai.algorithms", "label": "Non-geographic · 2001 to 2020: Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.algorithms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t2001", "label": "Non-geographic · 2001 to 2020", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001" }, { "id": "geo.nongeo.t2001.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology" }, { "id": "geo.nongeo.t2001.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing" }, { "id": "geo.nongeo.t2001.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai" }, { "id": "geo.nongeo.t2001.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t2001.technology.computing.ai.algorithms" } ] } ], "excerpt": "A path-planning algorithm computes a collision-free route for a robot or agent from a start to a goal position. Main approaches include graph search such as A, sampling-based planners such as RRT, and potential fields.", "snippet": "A path-planning algorithm computes a collision-free route for a robot or agent from a start to a goal position. Main approaches include graph search such as A, sampling-based planners such as RRT, and potential fields.", "node": "technology.computing.ai.graph_network_algorithms.shortest_path_algorithms", "markdown": "# Path-planning algorithm\n\nA path-planning algorithm computes a collision-free route for a robot or agent from a start position to a goal position. In the standard formulation the output is a continuous path \\( \\tau: [0,1] \\rightarrow C_{\\mathrm{free}} \\) with \\( \\tau(0) = q_I \\) and \\( \\tau(1) = q_G \\), where \\( C_{\\mathrm{free}} \\) is the set of configurations at which the robot overlaps no obstacle.[1](https://lavalle.pl/papers/Lav11b.pdf) Recent neural planners output a distribution over next-step joint motions from which paths are rolled out.[2](https://doi.org/10.48550/arxiv.2409.05864) Two main schools exist: combinatorial planning, which constructs discrete complete structures in configuration space (the set of all possible positions of a robot's parts), and [sampling-based planning](https://www.edgepedia.org/sampling-based-planning), which uses collision detection to probe and incrementally search configuration space; sampling-based approaches are the most common choice for industrial-grade problems.[1](https://lavalle.pl/papers/Lav11b.pdf)\n\n| Key fact | Value | Source |\n|---|---|---|\n| Output of the basic problem | Continuous path \\( \\tau: [0,1] \\rightarrow C_{\\mathrm{free}} \\) from \\( q_I \\) to \\( q_G \\) | [1](https://lavalle.pl/papers/Lav11b.pdf) |\n| A* evaluation function | \\( f(n) = g(n) + h(n) \\); admissible \\( h \\) never overestimates cost-to-go | [3](https://underactuated.csail.mit.edu/planning.html) • [4](https://doi.org/10.1109/tssc.1968.300136) |\n| Guarantees of sampling-based planners | Probabilistically complete; RRT* additionally asymptotically optimal | [5](https://ar5iv.labs.arxiv.org/html/1105.1186) • [6](https://ttic.edu/ripl/assets/publications/karaman11.pdf) |\n| Computational hardness | PSPACE-hard even for multiple translating axis-aligned rectangles in \\( \\mathbb{R}^2 \\) | [7](https://www.clear.rice.edu/comp450/papers/chapter_kav_lav.pdf) |\n| Dominant runtime cost | Collision checking, up to 90% of execution time | [8](https://eng.libretexts.org/Bookshelves/Mechanical_Engineering/Introduction_to_Autonomous_Robots_%28Correll%29/04%3A_Path_Planning/4.03%3A_Sampling-based_Path_Planning) |\n| Replanning speedup | D* Lite up to two orders of magnitude faster than replanning from scratch with A* | [9](https://www.cs.cmu.edu/%7emaxim/files/hsplanguide_icaps05ws.pdf) |\n\n## How it works\n\n**Graph search** plans on a discrete graph. A* orders expansion by \\( f(n) = g(n) + h(n) \\), where \\( g(n) \\) is the lowest cost found so far from the start and \\( h(n) \\) estimates the remaining cost to a goal.[4](https://doi.org/10.1109/tssc.1968.300136) A heuristic is admissible if it never over-estimates cost-to-go; with an admissible heuristic A* is complete and optimal, and [Dijkstra's algorithm](https://www.edgepedia.org/dijkstras-algorithm) is the special case with \\( h(n) = 0 \\).[3](https://underactuated.csail.mit.edu/planning.html) • [10](https://cw.fel.cvut.cz/b201/_media/courses/b4m36uir/lectures/b4m36uir-lec03-handout-2x2.pdf) A* returns an optimal path on the discrete graph it searches, but that graph path may only approximate the continuous-space optimum up to grid resolution, and runtime grows exponentially with state-space dimension.[5](https://ar5iv.labs.arxiv.org/html/1105.1186)\n\n**Sampling-based planning** avoids explicit obstacle representation by probing \\( C_{\\mathrm{free}} \\) through a collision-checking module. These planners are probabilistically complete, meaning the probability of finding an existing solution tends to one, but basic RRT converges to a suboptimal solution with probability one.[5](https://ar5iv.labs.arxiv.org/html/1105.1186) Karaman and Frazzoli proved this zero probability of convergence to the optimum and proposed RRT*, which converges almost surely to an optimal solution while retaining probabilistic completeness.[6](https://ttic.edu/ripl/assets/publications/karaman11.pdf)\n\n**Potential fields** build a differentiable function \\( U(q) \\) with an attractive component toward the goal and a repulsive component away from obstacles, then apply gradient descent. Because gradient descent reaches only a local minimum, this does not guarantee a solution.[7](https://www.clear.rice.edu/comp450/papers/chapter_kav_lav.pdf)\n\n## How it is done\n\nThe practitioner first defines the configuration space and computes \\( C_{\\mathrm{free}} = \\{ q \\in C \\mid A(q) \\cap O = \\emptyset \\} \\), then chooses a planner family.[1](https://lavalle.pl/papers/Lav11b.pdf) For A*, the open list is a priority queue and the closed list is a hash set; the most costly operations are closed-list insert and lookup and extracting the minimal-\\( f \\) element.[10](https://cw.fel.cvut.cz/b201/_media/courses/b4m36uir/lectures/b4m36uir-lec03-handout-2x2.pdf) The loop removes the minimal-\\( \\hat{f}(n) \\) node, generates successors, and updates \\( g(n') = g(n) + c(n, n') \\) when it improves the cost.[11](https://www.aorthey.com/assets/lectures/motion-planning/03_lecture.pdf)\n\nFor PRM, a preprocessing phase samples roughly 1000 random collision-free configurations and connects nearby ones into a roadmap; the query phase then connects start and goal and searches with A*.[12](https://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/PRM/prmbasic_01.pdf) • [3](https://underactuated.csail.mit.edu/planning.html) Single-query planners such as RRT follow a template of initializing a search graph, selecting a vertex, running a local planner that produces a collision-checked segment, inserting the edge, and checking for a solution.[13](https://msl.cs.uiuc.edu/~lavalle/planning/node219.html) The RRT samples \\( q_{\\mathrm{rand}} \\) in all of \\( C \\), not only \\( C_{\\mathrm{free}} \\), and extends the nearest tree point toward it.[1](https://lavalle.pl/papers/Lav11b.pdf) Because collision checking consumes up to 90% of runtime, lazy collision evaluation first finds a candidate path and checks its segments afterward.[8](https://eng.libretexts.org/Bookshelves/Mechanical_Engineering/Introduction_to_Autonomous_Robots_%28Correll%29/04%3A_Path_Planning/4.03%3A_Sampling-based_Path_Planning) Jagged final paths are smoothed by replacing segments with straight lines in \\( C_{\\mathrm{free}} \\).[1](https://lavalle.pl/papers/Lav11b.pdf)\n\n## Origin\n\nA* was presented by Peter Hart, Nils Nilsson, and Bertram Raphael in 1968 in IEEE Transactions on Systems Science and [Cybernetics](https://www.edgepedia.org/cybernetics).[4](https://doi.org/10.1109/tssc.1968.300136) The RRT was introduced by Steven LaValle in 1998.[14](https://lavalle.pl/papers/Lav02.pdf) RRT*, PRM*, and RRG were presented by Sertac Karaman and Emilio Frazzoli in 2011 in The International Journal of Robotics Research.[15](https://doi.org/10.1177/0278364911406761) The D* algorithm was introduced by Anthony Stentz in 1994 for real-time replanning of optimal traverses through graphs with changing arc costs.[16](https://publications.ri.cmu.edu/storage/publications/pub_files/pub3/stentz_anthony__tony__1994_2/stentz_anthony__tony__1994_2.pdf) D* Lite is credited to Sven Koenig and Maxim Likhachev in 2002.[10](https://cw.fel.cvut.cz/b201/_media/courses/b4m36uir/lectures/b4m36uir-lec03-handout-2x2.pdf) • [17](http://www.cs.toronto.edu/~jabaier/publications/HernandezBA14.pdf) Theta* was presented by Kenny Daniel and colleagues in 2007.[10](https://cw.fel.cvut.cz/b201/_media/courses/b4m36uir/lectures/b4m36uir-lec03-handout-2x2.pdf) Informed RRT* was presented by Jonathan Gammell, Siddhartha Srinivasa, and Timothy Barfoot in 2014 on arXiv.[18](https://doi.org/10.48550/arxiv.1404.2334) BIT* was presented by the same three authors in 2014 on arXiv.[19](https://personalrobotics.cs.washington.edu/publications/gammell2015bitstar.pdf) FMT* was presented by Lucas Janson and colleagues in 2015 in The International Journal of Robotics Research.[20](https://doi.org/10.1177/0278364915577958) CHOMP was presented by Matt Zucker and colleagues in 2013 in The International Journal of Robotics Research.[21](https://ietresearch.onlinelibrary.wiley.com/doi/10.1049/iet-csr.2018.0003) MI-RRT* was presented by Marco Faroni, Nicola Pedrocchi, and Manuel Beschi in 2024 in [Autonomous Robots](https://www.edgepedia.org/autonomous-robots).[22](https://doi.org/10.1007/s10514-024-10157-5) Neural MP was presented by Murtaza Dalal and colleagues in 2024 on arXiv.[2](https://doi.org/10.48550/arxiv.2409.05864)\n\n## Variants\n\n**Informed RRT*** retains RRT*'s probabilistic completeness and asymptotic optimality but, after a first solution is found, samples directly the prolate hyperspheroid subset of states that could improve it, improving convergence rate and final solution quality.[23](https://robotic-esp.com/papers/gammell_iros14) • [18](https://doi.org/10.48550/arxiv.1404.2334) **BIT*** unifies graph-based and sampling-based planning by searching a series of increasingly dense implicit random geometric graphs in order of potential solution quality.[24](https://robotic-esp.com/papers/gammell_ijrr20) • [19](https://personalrobotics.cs.washington.edu/publications/gammell2015bitstar.pdf) FMT* itself is a fast-marching sampling-based method for optimal planning in many dimensions.[20](https://doi.org/10.1177/0278364915577958)\n\n**D* Lite** searches from goal to start, maintains per-node \\( g \\) and \\( rhs \\) estimates (with \\( rhs(s) = 0 \\) at the goal and the one-step lookahead minimum over successors otherwise), and repairs only affected costs when arc costs change; AD* combines this incremental replanning with ARA*'s anytime, decreasing-inflation search.[10](https://cw.fel.cvut.cz/b201/_media/courses/b4m36uir/lectures/b4m36uir-lec03-handout-2x2.pdf) • [9](https://www.cs.cmu.edu/%7emaxim/files/hsplanguide_icaps05ws.pdf) **Theta*** extends A* to any-angle paths on grids using a LineOfSight check.[10](https://cw.fel.cvut.cz/b201/_media/courses/b4m36uir/lectures/b4m36uir-lec03-handout-2x2.pdf) **MI-RRT*** mixes admissible informed sampling with local sampling near the current solution, reducing planning time by up to 34% versus Informed RRT* in reported experiments.[22](https://doi.org/10.1007/s10514-024-10157-5)\n\n## Applications\n\nPRM has been applied to robots with 3 to 16 degrees of freedom in known static environments, finding paths for 10-DOF robots in a fraction of a second after preprocessing of a few dozen seconds.[25](https://www.kavrakilab.org/publications/kavraki-latombe1998probabilistic-roadmaps-for.pdf) Informed RRT* was evaluated on HERB, a 14-DOF mobile manipulation platform.[26](https://www.robots.ox.ac.uk/~mobile/Papers/2018TRO_gammell.pdf) D*-family replanners have flown on a [Mars rover](https://www.edgepedia.org/mars-rover) and run in the [DARPA Urban Challenge](https://www.edgepedia.org/darpa-urban-challenge).[17](http://www.cs.toronto.edu/~jabaier/publications/HernandezBA14.pdf) • [10](https://cw.fel.cvut.cz/b201/_media/courses/b4m36uir/lectures/b4m36uir-lec03-handout-2x2.pdf) In published comparisons, RRT is fastest among PRM, RRT, and Voronoi-diagram roadmap methods and suits time-critical mobile robots and UAVs, though with the worst path-obstacle safety distance.[27](https://www.cambridge.org/core/journals/robotica/article/comparative-analysis-of-popular-mobile-robot-roadmap-pathplanning-methods/95651415E38A60AA4BB71C90F31D576F) BIT* consistently outperforms RRT*, Informed RRT*, and FMT* on random-world and HERB manipulation problems.[19](https://personalrobotics.cs.washington.edu/publications/gammell2015bitstar.pdf)\n\n## Limitations and alternatives\n\nEach family fails in characteristic ways. Potential fields trap robots in local minima, oscillate near obstacles, and were designed for static environments.[28](https://www.nature.com/articles/s41598-025-96614-2) Narrow passages are bottlenecks with near-zero measure, so sampling-based planners rarely sample them; in one empirical study all six anytime planners tested were unreliable on 5D-and-above problems with narrow passages, and grid search degrades drastically as dimension grows.[29](https://www.annualreviews.org/content/journals/10.1146/annurev-control-061623-094742) • [30](https://motion.cs.illinois.edu/papers/IROS2014-OptimalBenchmarking.pdf) Sampling-based planners are also highly sensitive to implementation details such as step size, biasing percentage, and k-nearest parameters.[31](https://ieeexplore.ieee.org/document/6722915) For changing arc costs, D* repairs only the affected path portion and is far more efficient than brute-force replanning, with speedup factors of nearly 300 for large environments.[16](https://publications.ri.cmu.edu/storage/publications/pub_files/pub3/stentz_anthony__tony__1994_2/stentz_anthony__tony__1994_2.pdf)\n\n**Trajectory optimization** is the nearest alternative family. CHOMP optimizes a trajectory using a precomputed potential field from signed distance to obstacles, but can be trapped in local optima with non-convex obstacles, making the initial guess important; optimization-based methods (CHOMP, TrajOpt, KOMO, GPMP) usually find only locally optimal solutions and lack completeness or optimality guarantees.[21](https://ietresearch.onlinelibrary.wiley.com/doi/10.1049/iet-csr.2018.0003) • [29](https://www.annualreviews.org/content/journals/10.1146/annurev-control-061623-094742) In one comparison of six anytime planners, the most consistent performer was a hybrid of sampling-based planning and trajectory optimization.[30](https://motion.cs.illinois.edu/papers/IROS2014-OptimalBenchmarking.pdf)\n\n**Learning-based planners** have expanded since 2023. Neural MP trains a generalist planner on procedurally generated scenes and reports real-world success-rate improvements of 23% over sampling-based methods across 64 tasks.[2](https://doi.org/10.48550/arxiv.2409.05864)\n\n## References\n\n1. [Motion Planning: The Essentials (LaValle)](https://lavalle.pl/papers/Lav11b.pdf)\n2. [Dalal, Murtaza and colleagues (2024). Neural MP: A Generalist Neural Motion Planner. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.2409.05864)\n3. [Ch. 12 - Sampling-based motion planning (Underactuated Robotics, MIT)](https://underactuated.csail.mit.edu/planning.html)\n4. [Peter Hart, Nils Nilsson, Bertram Raphael (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics.](https://doi.org/10.1109/tssc.1968.300136)\n5. [Sampling-based Algorithms for Optimal Motion Planning (arXiv:1105.1186)](https://ar5iv.labs.arxiv.org/html/1105.1186)\n6. [Anytime Motion Planning using the RRT*](https://ttic.edu/ripl/assets/publications/karaman11.pdf)\n7. [Motion Planning chapter (Kavraki & LaValle)](https://www.clear.rice.edu/comp450/papers/chapter_kav_lav.pdf)\n8. [4.03: Sampling based Path Planning (eng.libretexts.org)](https://eng.libretexts.org/Bookshelves/Mechanical_Engineering/Introduction_to_Autonomous_Robots_%28Correll%29/04%3A_Path_Planning/4.03%3A_Sampling-based_Path_Planning)\n9. [A Guide to Heuristic-based Path Planning (Likhachev et al., ICAPS-05 workshop)](https://www.cs.cmu.edu/%7emaxim/files/hsplanguide_icaps05ws.pdf)\n10. [B4M36UIR Lecture 03: Path Planning (Faigl, CTU Prague)](https://cw.fel.cvut.cz/b201/_media/courses/b4m36uir/lectures/b4m36uir-lec03-handout-2x2.pdf)\n11. [Motion Planning Lecture 3 - Graph-based Planning: Representations, A*, Admissible heuristics](https://www.aorthey.com/assets/lectures/motion-planning/03_lecture.pdf)\n12. [Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces (IEEE Trans. Robotics and Automation, 1996)](https://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/PRM/prmbasic_01.pdf)\n13. [Planning Algorithms, Section 5.4.1 The General Framework (LaValle)](https://msl.cs.uiuc.edu/~lavalle/planning/node219.html)\n14. [From Dynamic Programming to RRTs: Algorithmic Design of Feasible Trajectories (LaValle, 2002)](https://lavalle.pl/papers/Lav02.pdf)\n15. [Sertac Karaman, Emilio Frazzoli (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research.](https://doi.org/10.1177/0278364911406761)\n16. [The D* Algorithm for Real-Time Planning of Optimal Traverses (Stentz, 1994)](https://publications.ri.cmu.edu/storage/publications/pub_files/pub3/stentz_anthony__tony__1994_2/stentz_anthony__tony__1994_2.pdf)\n17. [Making A* Run Faster than D*-Lite for Path-Planning in Partially Known Terrain (Hernández & Baier, AAAI 2014)](http://www.cs.toronto.edu/~jabaier/publications/HernandezBA14.pdf)\n18. [Gammell, Jonathan D., Srinivasa, Siddhartha S., Barfoot, Timothy D. (2014). Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1404.2334)\n19. [BIT*: Batch Informed Trees for Optimal Sampling-based Planning (ICRA 2015)](https://personalrobotics.cs.washington.edu/publications/gammell2015bitstar.pdf)\n20. [Lucas Janson and colleagues (2015). Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions. The International Journal of Robotics Research.](https://doi.org/10.1177/0278364915577958)\n21. [Survey of optimal motion planning (IET Cyber-Systems and Robotics)](https://ietresearch.onlinelibrary.wiley.com/doi/10.1049/iet-csr.2018.0003)\n22. [Marco Faroni, Nicola Pedrocchi, Manuel Beschi (2024). Adaptive hybrid local–global sampling for fast informed sampling-based optimal path planning. Autonomous Robots.](https://doi.org/10.1007/s10514-024-10157-5)\n23. [Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic (IROS 2014)](https://robotic-esp.com/papers/gammell_iros14)\n24. [Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search (IJRR 2020)](https://robotic-esp.com/papers/gammell_ijrr20)\n25. [Practical Motion Planning in Robotics (Kavraki & Latombe, Wiley, 1998)](https://www.kavrakilab.org/publications/kavraki-latombe1998probabilistic-roadmaps-for.pdf)\n26. [Informed Sampling for Asymptotically Optimal Path Planning (consolidated TRO 2018 version)](https://www.robots.ox.ac.uk/~mobile/Papers/2018TRO_gammell.pdf)\n27. [Comparative analysis of popular mobile robot roadmap path-planning methods (Robotica)](https://www.cambridge.org/core/journals/robotica/article/comparative-analysis-of-popular-mobile-robot-roadmap-pathplanning-methods/95651415E38A60AA4BB71C90F31D576F)\n28. [Simulation-based review of classical, heuristic, and metaheuristic path planning algorithms | Scientific Reports](https://www.nature.com/articles/s41598-025-96614-2)\n29. [Sampling-Based Motion Planning: A Comparative Review (Annual Reviews)](https://www.annualreviews.org/content/journals/10.1146/annurev-control-061623-094742)\n30. [An Empirical Study of Optimal Motion Planning (IROS 2014)](https://motion.cs.illinois.edu/papers/IROS2014-OptimalBenchmarking.pdf)\n31. [Sampling-Based Robot Motion Planning: A Review (IEEE Access)](https://ieeexplore.ieee.org/document/6722915)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Graph and network algorithms › Shortest paths*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/PRM/prmbasic_01.pdf", "https://msl.cs.uiuc.edu/~lavalle/planning/node219.html", "http://www.cs.toronto.edu/~jabaier/publications/HernandezBA14.pdf" ], "url": "https://www.edgepedia.org/path-planning-algorithm", "markdown_url": "https://www.edgepedia.org/path-planning-algorithm.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Path-planning algorithm\", Edgepedia (EdgeChat), https://www.edgepedia.org/path-planning-algorithm. Edgepedia Community License 1.0.", "credit_md": "\"[Path-planning algorithm](https://www.edgepedia.org/path-planning-algorithm)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/path-planning-algorithm](https://www.edgepedia.org/path-planning-algorithm). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Path-planning algorithm\", Edgepedia (EdgeChat), https://www.edgepedia.org/path-planning-algorithm. Edgepedia Community License 1.0.", "speakable": "A path-planning algorithm computes a collision-free route for a robot or agent from a start to a goal position." }