Path Planning Algorithms — Family Index

Tier 3 zoo of path / motion planning algorithms beyond the Tier 1 sampler (A*, RRT, PRM, lattice). Every entry cites originator + year. SI primary; planning state in metres / radians; time in seconds.

1. At a glance

Five major algorithmic families plus a reactive layer:

• Graph / grid search — Dijkstra (1959), A*(1968), weighted/bounded-A*, IDA*, JPS (2011), Theta* (2010), D*(1994) and D*-Lite (2002), LPA*(2001-04), ARA* (2003), AD*. Deterministic, optimal-on-graph.
• Sampling-based — PRM (1996), PRM*(2011), RRT (1998), RRT-Connect (2000), RRT* (2011), Informed RRT*(2014), BIT* (2015), FMT*(2015), SST (2016), AIT*/EIT* (2020-22). Probabilistically complete; some asymptotically optimal.
• Optimization-based — CHOMP (2009), STOMP (2011), TrajOpt (2013-14), GPMP/GPMP2 (2016-18), ITOMP. Local minimum but smooth and fast; warm-startable.
• State lattice + motion primitives — Pivtoraiko/Kelly/Knepper (2007-09). Precomputed feasible primitives; standard for Ackermann + planetary rovers.
• Decomposition — exact cell (trapezoidal, Boustrophedon — Choset 2000), approximate (quadtree / occupancy-grid), visibility graph, Voronoi/GVG (Choset).
• Special vehicles — Dubins (1957), Reeds-Shepp (1990), Hybrid A* (Dolgov/Thrun 2008).

Reactive layer (used on top of a global path): DWA (Fox/Burgard/Thrun 1997), TEB (Roesmann 2012), MPPI (Williams 2017), VFH/VFH+ (Borenstein/Koren 1991, Ulrich 2000), Pure Pursuit, Stanley.

2. Grid + graph search

• Dijkstra (1959) — Edsger W. Dijkstra. Uniform-cost search; radial wavefront from start; admissible + optimal on non-negative edge graphs. O((V+E) log V) with a binary heap.
• A (1968)* — Hart, Nilsson, Raphael. Best-first with f(n) = g(n) + h(n). Admissible h (never overestimates) → optimal; consistent h → no re-expansion. Standard heuristics on grids: Manhattan (4-connect), Euclidean, Octile (8-connect), Chebyshev.
• Weighted A* — f = g + w·h, w > 1. Bounded suboptimal (cost ≤ w·optimal), much faster.
• Bounded-suboptimal A family* — Optimistic, EES, DPS (Thayer + Ruml). Inflate strategically rather than uniformly.
• IDA — Iterative-Deepening A** (Korf 1985). DFS bounded by f-threshold; O(b·d) memory; used when A*‘s OPEN list blows up.
• JPS — Jump Point Search (Harabor + Grastien 2011) — Uniform-cost grid pruning that recursively jumps along straight + diagonal “natural” + “forced” neighbors. 10×–40× faster than A* on open maps. Adopted in StarCraft modding, Total War, and pathfinding-benchmark grids.
• JPS+ (Harabor 2014) — Precomputed jump-distance per direction per cell; near-zero-branching online expansion.
• JPS-3D / JPS-2(N) — Extensions to 3D grids and arbitrary connectivity.
• Theta (Daniel, Nash, Koenig, Felner 2010)**— Any-angle A: parent set to grandparent when line-of-sight holds. Produces taut shortest paths on grid without 45° staircase artefacts. Variants: Lazy Theta*, Angle-Propagation Theta*.
• D — Dynamic A (Stentz 1994)** — Replans incrementally when edge costs change (sensed obstacles). Used on the Mars rover stack and DARPA Grand Challenge. Replanning cost proportional to change, not full graph.
• D-Lite (Koenig + Likhachev 2002)**— Same incremental behaviour as D but built on LPA*; simpler code, dominant choice in modern rover/AGV deployments.
• LPA — Lifelong Planning A (Koenig + Likhachev 2001-04)** — Incremental search reusing previous g-values when start + graph change.
• ARA — Anytime Repairing A (Likhachev, Gordon, Thrun 2003)** — Returns suboptimal solution fast (high w), then progressively tightens w toward 1 reusing previous OPEN/CLOSED. Anytime contract.
• AD — Anytime Dynamic A (Likhachev et al. 2005)** — ARA*+ D*-Lite: anytime + replanning. CMU rover and DARPA Urban Challenge stack.
• MHA — Multi-Heuristic A (Aine et al. 2014)** — Multiple inadmissible heuristics with one anchor admissible heuristic; bounded suboptimal.
• R (Likhachev + Stentz 2008)**— Randomized A for high-dim search. Subgoal generation reduces effective branching factor for high-dim arms.
• Focal-list search (A*ε, Pearl + Kim 1982) — Expand from a focal list of states within ε of f_min instead of strict min; trades subopt bound for tie-breaking flexibility.
• Anytime Window A (Aine, Chakrabarti, Kumar 2007)* — Replans only inside a sliding window around the robot — good fit for partial reconfig of long paths.
• PEA, RBFS* — Partial expansion / recursive best-first variants; obscure but used for memory-bounded planning on grids > 10^7 nodes.

Implementation note: in modern robotics stacks the grid-search workhorses ship in the SBPL library (Maxim Likhachev, CMU) — Search-Based Planning Library — which is the reference codebase for ARA*, AD*, ANA*, MHA*, R*, and lattice search. Nav2 wraps an SBPL-style A* / Hybrid-A* as Smac Planner.

3. Sampling-based planners

• PRM — Probabilistic Roadmap (Kavraki, Svestka, Latombe, Overmars 1996) — Multi-query: sample N collision-free configs offline, connect k-nearest with local planner, build roadmap; online query connects start + goal then graph-searches. Ideal for static environments queried many times.
• PRM (Karaman + Frazzoli 2011)* — k = k_PRM·log n connectivity radius → asymptotic optimality.
• sPRM / Lazy PRM (Bohlin + Kavraki 2000) — Defer collision checks until on the candidate path.
• RRT — Rapidly-exploring Random Tree (Steven LaValle 1998, LaValle + Kuffner 2001) — Single-query: incrementally grow tree biased toward unexplored space by sampling + extending toward sample. Probabilistically complete, not optimal.
• RRT-Connect / RRT-Bidirectional (Kuffner + LaValle 2000) — Two trees from start and goal grown alternately, attempted joins. Dramatic speedup on narrow-passage problems.
• RRT (Karaman + Frazzoli 2011)* — Adds rewiring within radius γ(log n / n)^(1/d): asymptotically optimal. The reference modern RRT variant.
• Informed RRT (Gammell, Srinivasa, Barfoot 2014)* — After first solution, samples only inside heuristic prolate hyperspheroid (ellipsoid containing all paths better than c_best). Dramatically faster convergence.
• BIT — Batch Informed Trees (Gammell, Srinivasa, Barfoot 2015)**— Heuristic search on an implicit random geometric graph; processes samples in batches with A-like edge-queue ordering. State of the art for cost-minimisation in continuous spaces.
• FMT — Fast Marching Tree (Janson, Schmerling, Clark, Pavone 2015)* — Forward dynamic-programming on disk-graph samples; offline, asymptotically optimal.
• SST — Stable Sparse RRT (Li, Littlefield, Bekris 2016) — Kinodynamic, asymptotically near-optimal under dynamics, with pruning for sparseness.
• AIT + EIT (Strub + Gammell 2020-22)** — Adaptively Informed / Effort-Informed Trees: lazy bidirectional heuristic refinement on the samples. Faster than BIT*.
• Kinodynamic RRT (LaValle + Kuffner 2001) — Forward-integrates a control input from each node; respects dynamics directly.
• CC-RRT — Chance-Constrained RRT (Luders, Karaman, How 2013) — Probabilistic safety constraints under Gaussian uncertainty.
• KPIECE (Şucan + Kavraki 2009) — Discretization-aware tree; handles complex dynamics + high-dim arm well; default OMPL solver for many problems.
• EST — Expansive Space Tree (Hsu, Latombe, Motwani 1997) — Sampling biased toward boundary of explored region.
• SBL — Single-query Bidirectional Lazy (Sánchez + Latombe 2003) — Lazy collision checking + bidirectional sampling.
• STRIDE (Gipson + Moll + Kavraki 2013) — GNAT-tree spatial decomposition for efficient nearest-neighbour queries on manifolds.
• LBKPIECE — Lazy Bidirectional KPIECE — Lazy collision checking version of KPIECE; common OMPL choice for high-DoF.
• TRRT — Transition-based RRT (Jaillet, Cortés, Siméon 2010) — Cost-space sampling that climbs toward low-cost regions via Metropolis acceptance — useful when “cost” is non-binary (terrain, comfort).
• PDST — Path-Directed Subdivision Tree (Ladd + Kavraki 2005) — Maintains a partition over reached states + a tree of paths through them. Strong for kinodynamic.
• VF-RRT — Vector Field RRT (Ko, Kim, Kavraki 2014) — Biases sampling along a guidance vector field; very effective when a coarse desired flow is known (e.g., currents, attractor field).
• SyCLoP — Synergistic Combination of Layers of Planning (Plaku, Kavraki, Vardi 2010) — Discrete planner over workspace decomposition guides a sampling-based planner; good for very long horizons.

A note on probabilistic completeness vs asymptotic optimality: RRT and PRM are probabilistically complete (probability of finding a solution → 1 as samples → ∞), but the returned cost is arbitrary. RRT*, PRM*, BIT*, FMT* etc. are asymptotically optimal — cost → optimal almost surely. In real-time deployments people usually accept the first feasible solution, hence RRT-Connect’s dominance.

4. Optimization-based planners

Used either standalone for a smooth trajectory given a homotopy class, or as a post-processing smoother after a sampling planner.

• CHOMP — Covariant Hamiltonian Optimization for Motion Planning (Ratliff, Zucker, Bagnell, Srinivasa 2009) — Gradient descent on functional F = smoothness + obstacle (signed-distance) cost; covariant update (Riemannian metric on trajectory space). Smooth + fast but local-minimum prone.
• STOMP — Stochastic Trajectory Optimization for Motion Planning (Kalakrishnan, Chitta, Theodorou, Pastor, Schaal 2011) — Sample N noisy trajectory perturbations, weight by cost (REPS-like update). Handles non-differentiable costs; widely shipped in MoveIt.
• TrajOpt (Schulman, Ho, Lee, Awwal, Bradlow, Pan, Patil, Goldberg, Abbeel 2013-14) — Sequential Quadratic Programming on signed-distance + dynamic constraints with continuous-time collision checking (swept-volume). Benchmarks: faster + more reliable than CHOMP/STOMP on standard motion-planning sets; baseline for many follow-ups.
• GPMP / GPMP2 — Gaussian-Process Motion Planning (Mukadam, Yan, Boots 2016; Dong, Mukadam, Dellaert, Boots 2018) — GP prior over trajectory; factor-graph inference (GTSAM) for MAP planning. Sparse + incremental.
• ITOMP — Interactive Time-Optimal Motion Planning (Park, Pan, Manocha 2012) — Real-time replan with dynamic obstacle predictions.
• OptiMotion + Bouquet — OMPL geometric-then-optimize wrappers; PRM*/RRT* → CHOMP / TrajOpt smoothing.
• GPU-Voxels + cuRobo (NVIDIA 2023) — Parallel collision + cuRobo trajectory optimization; sub-millisecond arm plans on Jetson/Workstation GPUs.
• CIO — Contact-Invariant Optimization (Mordatch, Todorov, Popović 2012) — Joint optimization over trajectory + contact schedule with soft contact constraints; foundation of many humanoid/manipulation trajectory optimisers.
• DDP / iLQR — Differential Dynamic Programming (Mayne 1966) / Iterative LQR (Todorov + Li 2005) — Newton’s method on the value function along a trajectory; backbone of many MPC trajectory optimisers for legged robots and manipulators.
• Direct collocation / multiple shooting — Generic transcriptions used by CasADi / Drake to turn trajectory optimization into an NLP solved by IPOPT / SNOPT. Particularly common for humanoid + quadruped whole-body planning.
• MIQP / MICP trajectory optimization (Deits + Tedrake 2014) — Mixed-integer quadratic programs to choose convex regions (“IRIS regions”) + a polynomial within each; gives globally optimal trajectories through free space.

Trade-off: optimisation planners produce smooth trajectories ready for execution but are local — they need either a homotopy-class seed (from RRT-Connect, hand-drawn waypoints, or last cycle) or a global search shell.

5. State lattices + motion primitives

Pivtoraiko + Kelly + Knepper 2007-2009. Offline: enumerate dynamically feasible short motion primitives from a discrete state (x, y, θ, κ) lattice; cost each. Online: graph-search (A*, ARA*, AD*) over primitives → output a sequence that is feasible by construction. Differential constraints handled at design time, not in the search.

Used in:

• DARPA Urban Challenge (CMU’s Boss, 2007).
• Mars Curiosity + Perseverance ground-planning (with traversability cost map).
• Many AGV + warehouse fleets for non-holonomic vehicles.

Tradeoff: completeness limited by primitive set; resolution-complete on the lattice.

Variants:

• Search-based lattice planner (SBPL) — Likhachev’s reference implementation; ships with ARA*, AD*, ANA*.
• Smac Lattice Planner (Macenski + Open Navigation 2022) — ROS 2 Nav2 lattice planner derived from SBPL; integrates with costmap + behaviour-tree replans.
• Adaptive lattices — Different primitive resolutions in different parts of state space (Knepper + Mason 2009).
• Online primitive generation — When a fixed lattice is too coarse near obstacles, generate just-in-time motion primitives by sampling around the discrete neighbour set.

6. Cell decomposition

• Exact cell decomposition — Trapezoidal sweep (Latombe 1991); polygonal exact. Planning reduces to graph search over cells.
• Boustrophedon cellular decomposition (Choset 2000) — Critical-event decomposition for coverage planning (lawn-mowing pattern). Foundation for autonomous mowers, vacuums, sweepers, aerial surveys.
• Approximate cell decomposition — Quadtree / octree; occupancy-grid. Practical default — every Nav2 / move_base costmap is this.
• Visibility graph — Nodes = obstacle vertices; edges = mutually visible pairs; shortest path is piecewise linear (Lozano-Pérez + Wesley 1979). Provably optimal in 2D for polygonal obstacles. Doesn’t scale to 3D or many obstacles.
• Generalized Voronoi Graph (GVG) — Howie Choset 1996-2000 — Topological skeleton equidistant from obstacles; safe corridors; used for exploration + topological SLAM. Closely tied to medial-axis transform.

7. Geometric algorithms for special vehicles

• Dubins (Lester Dubins 1957) — Shortest C¹ path for a forward-only car-like vehicle with minimum turning radius R between two oriented poses. Always one of six primitives: LSL, RSR, LSR, RSL, LRL, RLR (L=left arc, S=straight, R=right arc). Closed-form.
• Reeds-Shepp (Reeds + Shepp 1990) — Generalization allowing reverse motion. 48 (originally 48; reducible to 46) primitive sequence types; closed-form table lookup. Standard for autonomous parking + truck backing.
• Hybrid A (Dolgov, Thrun, Montemerlo, Diebel 2008)**— Stanford “Junior” DARPA Urban Challenge planner. A in continuous (x, y, θ) with discretized grid for closed-list. Two heuristics: 2D non-holonomic-without-obstacles (Reeds-Shepp distance), and 2D holonomic-with-obstacles (Dijkstra on inflated grid). At each expansion, attempts a Reeds-Shepp analytic shot to goal; if collision-free, plan completes. The de-facto standard for tight-maneuver auto parking + AGV docking. Implementations: ROS hybrid_a_star, Apollo, Autoware.

8. Reactive / local planners (run on top of a global path)

• DWA — Dynamic Window Approach (Fox, Burgard, Thrun 1997) — Sample velocity pairs (v, ω) inside the dynamic window (reachable in Δt under accel limits). Score each by goal heading + clearance + velocity; pick max. Real-time, kinematic-feasible. Default ROS 1 local planner.
• TEB — Timed Elastic Band (Roesmann, Hess, Feiten, Bengel, Bertram 2012-14) — Deform a discrete-time pose+timestamp sequence to a local minimum of a weighted-sum cost (path length, time, obstacle distance, dynamic limits, non-holonomic constraints). Multi-trajectory homotopy class exploration to avoid local minima. Standard ROS Nav2 controller alongside DWB.
• MPPI — Model Predictive Path Integral (Williams, Wagener, Drews, Theodorou, Rehg, Boots 2017-18) — Sampling-based MPC: forward-roll thousands of noisy control sequences per cycle on a GPU; weight by exponentiated cost; update mean. Handles arbitrary cost. Auto-Rally (Georgia Tech) drift racing, NVIDIA Isaac Drive, autonomous racing. ROS 2 Nav2 has nav2_mppi_controller.
• VFH — Vector Field Histogram (Borenstein + Koren 1991) — Build polar histogram of obstacles; pick valley closest to goal direction. Predecessors of DWA.
• VFH+ (Ulrich + Borenstein 1998) — Adds robot dimensions + smoothing.
• VFH (Ulrich + Borenstein 2000)**— VFH+ + A lookahead.
• Pure Pursuit (Coulter 1992) — Geometric path follower: aim at a lookahead point on the path; circle through current pose to lookahead defines steering. Standard for AGV.
• Stanley controller (Hoffmann, Tomlin, Montemerlo, Thrun 2007) — Stanford “Stanley” DARPA Grand Challenge follower: cross-track-error + heading-error feedback. Used by Apollo + Autoware for high-speed tracking.
• Regulated Pure Pursuit (Macenski 2022) — Modern ROS 2 Nav2 default: adapts lookahead to speed + scenario.

9. Multi-robot / decentralized

• CBS — Conflict-Based Search (Sharon, Stern, Felner, Sturtevant 2015) — Optimal multi-agent path finding (MAPF). Low-level: A* per agent. High-level: binary tree splitting on detected conflicts (constraint expansion). State of the art for optimal MAPF.
• ECBS — Enhanced CBS (Barer et al. 2014) — Bounded suboptimal CBS.
• EECBS — Explicit Estimation CBS (Li et al. 2021) — Stronger heuristics, faster bounded suboptimal MAPF.
• MAPF-LNS / LNS2 (Li et al. 2021-22) — Large-neighbourhood-search local repair; scales to 1000+ agents.
• PBS — Priority-Based Search, PP — Prioritized Planning — Faster but incomplete.
• ORCA / RVO — (Reciprocal) Velocity Obstacles (van den Berg, Lin, Manocha 2008-11) — Each agent picks a velocity in the half-plane that mutually guarantees collision avoidance; no communication required. Smooth swarm flow; default crowd-sim + drone-swarm primitive.
• NH-ORCA / HRVO — Non-holonomic + hybrid-reciprocal extensions.
• CADRL / GA3C-CADRL (Chen, Liu, Kreiss, How 2017) — Deep-RL multi-agent collision avoidance.
• ALAN — Action-Local Anytime planner + Token-passing (Ma + Koenig 2017) — Lifelong MAPF with continuous tasks, used in Amazon-style warehouses.
• MAPF-POST / CCBS — Continuous-time CBS (Andreychuk et al. 2019) — Plans in continuous time rather than discretized timesteps.
• Distributed MPC swarm (Saska et al. 2017, Honig et al. 2018) — Each agent solves local MPC over neighbour trajectories communicated each cycle.
• GLAS — Global-to-Local Autonomy Synthesis (Riviere, Hönig, Yue, Chung 2020) — Learned decentralized policy from a centralized planner’s data.

10. Learning-based planning

• NavRL + NavRL-Mob + ION — PPO + LSTM goal-conditioned policies in NVIDIA Isaac / Omniverse training pipelines; sim-to-real for mobile robots.
• Imitation of A heuristics*— Neural cost-to-go (CNN/transformer) predicts h(n); used to accelerate A* / weighted Aon grids (e.g., Neural A, Yonetani et al. 2021).
• MPNet (Qureshi, Yip 2019-21) — Encoder-decoder generates intermediate waypoints in C-space; orders-of-magnitude faster than RRT* on its training distribution.
• VINs — Value Iteration Networks (Tamar et al. 2016) — Differentiable VI module as a planning prior.
• Diffusion policy planners (Chi, Feng, Du, Burchfiel, Tedrake, Song 2023; follow-ups 2024-25) — Conditional diffusion over action trajectories; strong manipulation results, increasingly used as a planning-with-execution prior.
• Differentiable simulation — Brax, MuJoCo MJX, Warp; back-prop through dynamics for trajectory optimization with learned dynamics models.
• DRL navigation policies + safety filter — End-to-end policy with control-barrier-function / MPC safety fallback (NavRL, GoalNav, DD-PPO Habitat).
• GNN motion planners (Khan et al. 2020-22) — GNN over a sampled graph to predict edges to expand.
• PRM-RL (Faust, Oslund, Ramirez, Francis, Tapia, Fiser, Davidson 2018) — Combine PRM for long-horizon with a local RL policy for short-horizon execution; Google research.
• Decision-Transformer / Goal-conditioned BC — Offline-RL framing of nav: condition action transformer on goal + history; works when demonstrations are abundant.
• MCTS-based planning (AlphaGo lineage, Silver et al. 2017-18) — Used in robotics for non-prehensile manipulation, long-horizon TAMP search.
• PlaNet / Dreamer (Hafner et al. 2019-23) — World-model latent rollouts for planning; intersects with model-based RL.
• CMP — Cognitive Mapping and Planning (Gupta et al. 2017) — End-to-end mapping + value iteration on egocentric features.

Caveat: as of 2026, learned planners are mostly research and niche commercial deployments. Production stacks for safety-critical robotics (auto, surgical, industrial) almost always use a classical planner as the spine with learning at perception + behaviour layers only. Diffusion policies are the closest to crossing over into production manipulation.

11. 3D + manipulator-arm specific

High-dim configuration-space planning (6–7 DoF arm, 2–3 m reach):

• OMPL solvers used in practice: RRT-Connect (default for many MoveIt pipelines), RRT*, BIT*, FMT*, EST, KPIECE, SBL, STRIDE, LBKPIECE, BiTRRT.
• MoveIt 2 pipelines (Open Robotics + PickNik) — OMPL + Pilz industrial trajectory generator (deterministic LIN/PTP/CIRC for industrial robots, no probabilistic sampling) + CHOMP/STOMP smoothing + TrajOpt option.
• cuRobo (NVIDIA 2023) — GPU-parallel collision check + L-BFGS trajectory optimization for arms; sub-millisecond plans common.
• CBiRRT (Berenson 2009) — Constrained Bidirectional RRT on task-space manifolds (e.g., holding a glass upright).
• TrajOpt + signed-distance fields — Standard for high-DoF arm + base + multi-arm coordinated planning.

11b. Common heuristics + cost terms

Tied to most planners is a per-edge or per-state cost function. Practical robotic stacks blend:

• Path length / euclidean — baseline.
• Time — straightforward when speed is bounded.
• Energy / control effort — quadratic in torque or current.
• Smoothness / jerk — finite differences along the trajectory; key for arm + drone comfort.
• Clearance — signed distance to obstacles; either as constraint (TrajOpt) or soft cost (CHOMP).
• Traversability — terrain slope, roughness, friction (rover, off-road, quadruped).
• Visibility / observability — favouring paths the perception stack can localise against.
• Social cost — pedestrian comfort distance (Hall’s proxemics), used in service-robot nav.
• Risk / uncertainty — chance constraints, conditional value-at-risk over predicted obstacle trajectories.
• Lane + traffic-rule — for on-road autonomy; sticks to lane centre, respects signed lane semantics.

Tier 3 lesson: the cost function dictates the path more than the algorithm choice. Two A*‘s with different cost terms produce wildly different behaviour; same for two RRT*‘s. Spend time tuning costs before swapping planners.

12. Libraries / frameworks

• OMPL — Open Motion Planning Library (KavrakiLab, Rice University) — The canonical sampling-planner library. C++ with Python bindings. Used by MoveIt + many academic pipelines. Implements 30+ planners.
• MoveIt 2 (Open Robotics + PickNik) — ROS 2 motion planning framework: OMPL + Pilz + CHOMP/STOMP/TrajOpt; planning-scene; servo; cartesian-paths.
• ROS 2 Nav2 (Macenski et al., Open Navigation 2020+) — Successor to ROS 1 move_base. Behaviour-Tree based; pluggable planners (Smac A*/ Smac Hybrid-A* / NavFn / Theta*) + controllers (DWB, TEB, MPPI, RPP). Costmap 2D.
• CasADi + IPOPT — Symbolic + auto-diff for NLP-based motion planning; very common for MPC on quadrotors + manipulators.
• Drake + MathematicalProgram (Russ Tedrake, MIT) — Convex / NLP / MIQP formulations of MP and control; trajectory optimization with kinematic trees.
• Aikido (Personal Robotics Lab, CMU) — Trajectory + constraint manifold + RViz integration.
• TrajOptLib + TrajOptROS (Levi Armstrong, Southwest Research Institute) — Industrial-grade TrajOpt fork; used by ROS-Industrial.
• mp_baselines (CMU) — Reference implementations of CHOMP, STOMP, GPMP, TrajOpt.
• MPNet, DiffSE3, Neural-A* — Learning-based planning research codebases.
• Apollo (Baidu) — Open self-driving stack with EM-planner + Hybrid A* + Lattice planner.
• Autoware (Tier IV + Autoware Foundation) — Open self-driving stack with Freespace planner (Hybrid A*) + Lane-Driving planner.
• TOPP-RA (Hauser + Pham 2018) — Time-Optimal Path Parametrization by Reachability Analysis; turns a geometric path into a time-optimal trajectory respecting torque + velocity limits. Standard tool for finishing geometric planner output.
• Ruckig (Pfister 2021) — Real-time online jerk-limited trajectory generation; widely used for industrial-arm + servo control.
• Pinocchio + HPP (Carpentier, Mansard et al., LAAS-CNRS) — Rigid-body dynamics + planning framework — humanoid + manipulation work at Toyota Research, NAVER LABS, Boston Dynamics AI Institute.
• OCS2 (ETH Zurich) — Optimal control toolbox for legged + manipulation MPC; used in ANYmal stack.
• Crocoddyl (LAAS-CNRS 2020) — Multi-contact DDP optimization library for legged robots.
• TOWR (Winkler et al. 2018) — Trajectory optimization for walking robots; symbolic NLP via Ifopt.
• MoveIt Task Constructor (Görner, PickNik) — Higher-level pipeline combining sub-tasks (approach, grasp, transit, place) each planned with the underlying solver.
• PythonRobotics (AtsushiSakai) — Pedagogical reference implementations of nearly every planner above; widely used to learn the algorithms.

13. Comparison table

Algorithm	Space	Optimal?	Replans / dynamic?	Typical use	Exemplar lib
Dijkstra	grid / graph	yes	no	Baseline	networkx
A*	grid / graph	yes (admissible h)	no	Global path	OMPL, Nav2 NavFn
Weighted A*	grid / graph	bounded subopt	no	Speed > optimality	SBPL
IDA*	tree-like	yes	no	Memory-bounded	textbook
JPS / JPS+	uniform grid	yes	no	Game AI, large maps	JPS+ in Smac
Theta*	grid (any-angle)	near-shortest	no	Smooth grid paths	Smac Theta*
D*/ D*-Lite	grid	yes	yes (incremental)	Mars rover, AGV	SBPL D*-Lite
LPA*	graph	yes	yes (incremental)	Building block	SBPL
ARA*	graph	anytime → opt	no	Time-pressured plan	SBPL
AD*	graph	anytime → opt	yes	DARPA Urban Challenge	SBPL
MHA*	graph	bounded subopt	no	High-DoF arms	SBPL
PRM / PRM*	continuous	PRM*: yes asym.	no	Static multi-query	OMPL
RRT	continuous	no	no	Single-query base	OMPL
RRT-Connect	continuous	no	no	Fast feasible arm	OMPL (MoveIt default)
RRT*	continuous	asymptotic	no	Optimal arm/AGV	OMPL
Informed RRT*	continuous	asymptotic	no	Faster convergence	OMPL
BIT*	continuous	asymptotic	no	SoTA continuous-opt	OMPL
AIT*/ EIT*	continuous	asymptotic	no	Faster BIT*	OMPL
FMT*	continuous	asymptotic	no	Offline	OMPL
SST	kinodynamic	near-asymptotic	no	Dynamics	OMPL
KPIECE	continuous + dyn	no	no	High-dim	OMPL
Kinodyn RRT	dynamics	no	no	Quadrotor short	custom
CC-RRT	uncertain dyn	no	no	Risk-bounded	research
CHOMP	continuous (smooth)	local	no	Arm smoothing	mp_baselines
STOMP	continuous (smooth)	local stoch.	no	Non-diff costs	MoveIt
TrajOpt	continuous (smooth)	local	no	Arm + mobile	TrajOptLib
GPMP2	continuous (smooth)	local MAP	no	Incremental arm	GPMP2
State lattice	discrete primitives	resolution opt	no (with AD*)	Ackermann, rover	SBPL
Boustrophedon	2D cells	optimal coverage	no	Lawn/sweep	custom
Visibility graph	2D polygons	yes	no	Theoretical 2D	research
GVG / Voronoi	2D / 3D	safe	no	Exploration	Choset libs
Dubins	(x,y,θ), no reverse	yes geom.	no	Fixed-wing UAV	dubins-py
Reeds-Shepp	(x,y,θ) + reverse	yes geom.	no	Parking, truck	OMPL
Hybrid A*	(x,y,θ) continuous	local	yes (replan)	Auto parking, AGV	Smac H-A*
DWA / DWB	velocity (v,ω)	local	yes	Mobile local	Nav2 DWB
TEB	(x,y,θ,t)	local	yes	ROS local plan	teb_local_planner
MPPI	trajectories	local sampled MPC	yes	Racing, drones	nav2_mppi
VFH+	velocity	local	yes	Cheap reactive	research
Pure Pursuit / Stanley	follow given path	n/a	yes	Path follower	Nav2 RPP, Autoware

14. Selection heuristics

• 2D household / vacuum / mobile-base global → A* (4/8-connect) on inflated occupancy grid, plus JPS+ for big maps.
• 2D dynamic / changing costs (sensed obstacles, mining, agriculture) → D*-Lite on rolling grid + ARA* anytime layer.
• On-road autonomous driving → Lattice planner or Hybrid A* (for parking / unstructured) → spline / quintic polynomial smoothing → Frenet-frame local planner with MPC controller.
• AGV in warehouse with dynamic obstacles → A*/ Smac Hybrid-A* global + TEB or MPPI local + ORCA / EECBS fleet-level coordination.
• Manipulator 6-7 DoF arm, free space → RRT-Connect (fast feasibility) or BIT* (optimality) via OMPL inside MoveIt 2; post-smooth with TrajOpt or STOMP.
• Manipulator on constrained task (hold cup upright, weld seam) → CBiRRT or TrajOpt with equality constraints.
• Autonomous parking, narrow maneuvering → Hybrid A* with Reeds-Shepp analytic-shot.
• Quadruped foothold sequencer → state lattice over discrete foothold options + MPC inner loop for body / swing-leg trajectory (BigDog, ANYmal, Spot stack).
• Aerial drone short-horizon obstacle avoidance → MPPI or TEB on sliding window; sometimes Kinodynamic RRT for replans.
• Fixed-wing UAV waypoint following → Dubins paths chained between waypoints; lookahead-based path follower.
• Multi-AGV fleet (10-1000 robots) → CBS / ECBS / EECBS planner + ORCA at execution time; LNS2 if 1000+ agents.
• End-to-end mobile robot navigation → DRL policy (NavRL / DD-PPO) + classical collision-avoidance fallback (DWA / TEB) as safety filter.
• Rough-terrain rover → D*-Lite or AD* on traversability cost map with custom slope/roughness terms.
• Surgical needle steering → RRT-Connect with bevel-tip needle motion model; Reeds-Shepp-like non-holonomic primitives.
• Coverage planning (mowing, sweeping, surveying, painting) → Boustrophedon decomposition + within-cell zig-zag.
• Exploration of unknown → Frontier-based + GVG (Voronoi) + RRT-based info-theoretic gain.
• Underwater / AUV → State-lattice with currents in cost; D*-Lite for replanning.
• Humanoid whole-body → Footstep planner (ARA* over discrete footstep primitives) + whole-body trajectory optimization (DDP / iLQR / TOWR) + MPC.
• Mobile manipulator (base + arm) → Decoupled (plan base then arm) is brittle; coupled BIT* / TrajOpt in the full (base, arm) C-space is becoming standard; cuRobo accelerates this on GPU.
• Forklift / OTR truck reversing → Reeds-Shepp primitives + Hybrid A* with extended trailer kinematics.
• Marine surface vessel → A*/ Hybrid A* with COLREGS compliance cost + MPC inner loop honoring rudder dynamics.
• Construction / earth-moving → Coverage planner (Boustrophedon) over the working volume, plus task-and-motion planning to sequence multiple operations.

15. Cross-references

• path-planning — Tier 1 entry node.
• trajectory-generation — Time parameterization, splines, polynomials.
• mpc-for-robots — Receding-horizon control closely tied to MPPI + TEB.
• control-algorithms — Lower-level trackers (Pure Pursuit, Stanley, LQR, MPC).
• slam-algorithms — Map sources consumed by planners.
• mobile-base-wheeled — Ackermann / differential / omni kinematics that constrain primitives.
• manipulator-design + manipulator-topologies — Where arm-specific planners live.

16. Citations

• Steven M. LaValle, Planning Algorithms, Cambridge University Press, 2006. Free online: lavalle.pl/planning. The canonical reference.
• Howie Choset, Kevin Lynch, Seth Hutchinson, George Kantor, Wolfram Burgard, Lydia Kavraki, Sebastian Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations, MIT Press, 2005.
• Hart, Nilsson, Raphael 1968. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” IEEE Trans. SSC.
• Dijkstra 1959. “A note on two problems in connexion with graphs.” Numerische Mathematik.
• Harabor + Grastien 2011. “Online Graph Pruning for Pathfinding on Grid Maps.” AAAI.
• Daniel, Nash, Koenig, Felner 2010. “Theta*: Any-Angle Path Planning on Grids.” JAIR.
• Stentz 1994. “Optimal and Efficient Path Planning for Partially-Known Environments.” ICRA.
• Koenig + Likhachev 2002. “D* Lite.” AAAI.
• Likhachev, Gordon, Thrun 2003. “ARA*: Anytime A* with Provable Bounds on Sub-Optimality.” NeurIPS.
• Kavraki, Svestka, Latombe, Overmars 1996. “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces.” IEEE T-RA.
• LaValle 1998. “Rapidly-Exploring Random Trees: A New Tool for Path Planning.” TR 98-11, Iowa State.
• Kuffner + LaValle 2000. “RRT-Connect: An Efficient Approach to Single-Query Path Planning.” ICRA.
• Karaman + Frazzoli 2011. “Sampling-based Algorithms for Optimal Motion Planning.” IJRR.
• Gammell, Srinivasa, Barfoot 2014. “Informed RRT*.” IROS.
• Gammell, Srinivasa, Barfoot 2015. “Batch Informed Trees (BIT*).” ICRA.
• Janson, Schmerling, Clark, Pavone 2015. “Fast Marching Tree.” IJRR.
• Li, Littlefield, Bekris 2016. “Asymptotically Optimal Sampling-Based Kinodynamic Planning.” IJRR.
• Strub + Gammell 2020. “Adaptively Informed Trees (AIT*).” ICRA.
• Strub + Gammell 2022. “Effort-Informed Trees (EIT*).” T-RO.
• Ratliff, Zucker, Bagnell, Srinivasa 2009. “CHOMP: Gradient Optimization Techniques for Efficient Motion Planning.” ICRA.
• Kalakrishnan, Chitta, Theodorou, Pastor, Schaal 2011. “STOMP: Stochastic Trajectory Optimization for Motion Planning.” ICRA.
• Schulman, Duan, Ho, Lee, Awwal, Bradlow, Pan, Patil, Goldberg, Abbeel 2014. “Motion Planning with Sequential Convex Optimization and Convex Collision Checking.” IJRR. (TrajOpt.)
• Mukadam, Dong, Yan, Dellaert, Boots 2018. “Continuous-time Gaussian Process Motion Planning via Probabilistic Inference.” IJRR. (GPMP2.)
• Pivtoraiko, Knepper, Kelly 2009. “Differentially Constrained Mobile Robot Motion Planning in State Lattices.” J. Field Robotics.
• Choset 2000. “Coverage of Known Spaces: The Boustrophedon Cellular Decomposition.” Autonomous Robots.
• Choset + Burdick 2000. “Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph.” IJRR.
• Dubins 1957. “On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents.” Amer. J. Math.
• Reeds + Shepp 1990. “Optimal Paths for a Car that Goes Both Forwards and Backwards.” Pacific J. Math.
• Dolgov, Thrun, Montemerlo, Diebel 2008. “Practical Search Techniques in Path Planning for Autonomous Driving.” AAAI Workshop; Stanford “Junior.”
• Fox, Burgard, Thrun 1997. “The Dynamic Window Approach to Collision Avoidance.” IEEE Robotics & Automation Magazine.
• Roesmann, Hess, Feiten, Bengel, Bertram 2012-15. “Trajectory Modification Considering Dynamic Constraints of Autonomous Robots.” ROBOTIK; “Integrated Online Trajectory Planning and Optimization in Distinctive Topologies.” Robotics and Autonomous Systems.
• Williams, Wagener, Goldfain, Drews, Rehg, Theodorou, Boots 2017-18. “Information-Theoretic Model Predictive Control: Theory and Applications to Autonomous Driving.” T-RO. (MPPI.)
• Borenstein + Koren 1991. “The Vector Field Histogram — Fast Obstacle Avoidance for Mobile Robots.” IEEE T-RA.
• Ulrich + Borenstein 1998, 2000. “VFH+”, “VFH*.” ICRA.
• Hoffmann, Tomlin, Montemerlo, Thrun 2007. “Autonomous Automobile Trajectory Tracking for Off-Road Driving.” ACC. (Stanley.)
• Sharon, Stern, Felner, Sturtevant 2015. “Conflict-Based Search for Optimal Multi-Agent Pathfinding.” Artif. Intell.
• van den Berg, Guy, Lin, Manocha 2011. “Reciprocal n-Body Collision Avoidance (ORCA).” Robotics Research.
• Yonetani, Taniai, Barekatain, Ishii, Schroers 2021. “Path Planning Using Neural A* Search.” ICML.
• Qureshi + Yip 2019. “Motion Planning Networks (MPNet).” IEEE T-RO.
• Chi, Feng, Du, Burchfiel, Tedrake, Song 2023. “Diffusion Policy: Visuomotor Policy Learning via Action Diffusion.” RSS.
• Şucan, Moll, Kavraki 2012. “The Open Motion Planning Library.” IEEE Robotics & Automation Magazine. (OMPL.)
• Macenski, Martín, White, Clavero 2020. “The Marathon 2: A Navigation System.” IROS. (Nav2.)
• Pearl + Kim 1982. “Studies in Semi-Admissible Heuristics.” IEEE T-PAMI.
• Aine, Chakrabarti, Kumar 2007. “AWA* — A Window Constrained Anytime Heuristic Search Algorithm.” IJCAI.
• Korf 1985. “Depth-First Iterative-Deepening: An Optimal Admissible Tree Search.” Artif. Intell.
• Likhachev + Stentz 2008. “R* Search.” AAAI.
• Aine, Swaminathan, Narayanan, Hwang, Likhachev 2014. “Multi-Heuristic A*.” Artif. Intell.
• Bohlin + Kavraki 2000. “Path Planning Using Lazy PRM.” ICRA.
• Hsu, Latombe, Motwani 1997. “Path Planning in Expansive Configuration Spaces.” Int. J. Comp. Geom. Appl.
• Sánchez + Latombe 2003. “A Single-Query Bi-Directional Probabilistic Roadmap Planner with Lazy Collision Checking.” Robotics Research.
• Şucan + Kavraki 2009. “KPIECE: A Discretization-Based Motion Planner.” IROS.
• Gipson, Moll, Kavraki 2013. “Resolution Independent Density Estimation for Motion Planning in High-Dimensional Spaces.” ICRA. (STRIDE.)
• Ladd + Kavraki 2005. “Motion Planning in the Presence of Drift, Underactuation and Discrete System Changes.” RSS. (PDST.)
• Jaillet, Cortés, Siméon 2010. “Sampling-Based Path Planning on Configuration-Space Costmaps.” IEEE T-RO. (T-RRT.)
• Plaku, Kavraki, Vardi 2010. “Motion Planning with Dynamics by a Synergistic Combination of Layers of Planning.” IEEE T-RO. (SyCLoP.)
• Berenson, Srinivasa, Ferguson, Kuffner 2009. “Manipulation Planning on Constraint Manifolds.” ICRA. (CBiRRT.)
• Mordatch, Todorov, Popović 2012. “Discovery of Complex Behaviors through Contact-Invariant Optimization.” SIGGRAPH.
• Todorov + Li 2005. “A Generalized Iterative LQG Method for Locally-Optimal Feedback Control of Constrained Nonlinear Stochastic Systems.” ACC.
• Mayne 1966. “A Second-Order Gradient Method of Optimizing Non-Linear Discrete-Time Systems.” Int. J. Control. (Original DDP.)
• Deits + Tedrake 2014. “Computing Large Convex Regions of Obstacle-Free Space through Semidefinite Programming.” WAFR. (IRIS.)
• Pivtoraiko + Kelly 2005. “Generating Near Minimal Spanning Control Sets for Constrained Motion Planning in Discrete State Spaces.” IROS.
• Knepper + Mason 2009. “Empirical Sampling of Path Sets for Local Area Motion Planning.” ISER.
• Borrelli, Bemporad, Morari 2017. Predictive Control for Linear and Hybrid Systems. Cambridge. (MPC reference.)
• Hauser + Pham 2018. “Parabolic Time-Optimal Path Parametrization.” (TOPP-RA.)
• Honig, Preiss, Kumar, Sukhatme, Ayanian 2018. “Trajectory Planning for Quadrotor Swarms.” IEEE T-RO.
• Saska, Vakula, Preucil 2014. “Swarms of Micro Aerial Vehicles Stabilized under a Visual Relative Localization.” ICRA.
• Faust, Oslund, Ramirez, Francis, Tapia, Fiser, Davidson 2018. “PRM-RL: Long-Range Robotic Navigation Tasks by Combining Reinforcement Learning and Sampling-Based Planning.” ICRA.
• Gupta, Davidson, Levine, Sukthankar, Malik 2017. “Cognitive Mapping and Planning for Visual Navigation.” CVPR. (CMP.)
• Hafner, Pasukonis, Ba, Lillicrap 2023. “Mastering Diverse Domains through World Models.” (DreamerV3.)
• Andreychuk, Yakovlev, Atzmon, Stern 2019. “Multi-Agent Pathfinding with Continuous Time.” IJCAI. (CCBS.)
• Li, Ruml, Koenig 2021. “EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding.” AAAI.
• Riviere, Hönig, Yue, Chung 2020. “GLAS: Global-to-Local Safe Autonomy Synthesis for Multi-Robot Motion Planning with End-to-End Learning.” RA-L.