Path planning is the computational problem of finding a route from one location to another while avoiding obstacles, and it underpins nearly every autonomous system you encounter, from warehouse robots to self-driving cars to the routing engine on your phone. The field has grown from simple shortest-path searches on grid maps into a sprawling ecosystem of algorithms tailored to different physical constraints, numbers of agents, and levels of uncertainty. What makes path planning interesting is that no single algorithm wins everywhere; the right choice depends heavily on what is moving, what it knows about its surroundings, and how fast it needs to decide.
Grid Maps and the Algorithms That Search Them
The earliest practical approaches to path planning carved the environment into a grid of cells, each marked as free, occupied, or partially blocked. A robot’s world became a checkerboard, and finding a path meant searching that checkerboard for a connected chain of free cells leading from start to goal. Two algorithms from computer science became workhorses for this: Dijkstra’s algorithm, which fans out in all directions guaranteeing the shortest path, and A*, which adds a heuristic estimate of remaining distance so it can focus its search toward the goal and finish faster. Both are still in heavy use today, often as components inside larger systems.
1Applied and Computational Engineering. The evolution and current frontiers of path planning algorithms for mobile robots: A comprehensive reviewGrid-based search has a clear limitation: as the environment gets larger or as you add more dimensions (think of a robotic arm that can bend at six joints, giving it six dimensions of freedom), the number of cells explodes. Searching a six-dimensional grid cell by cell becomes computationally brutal. That scaling problem drove the development of a fundamentally different family of planners.
Sampling-Based Methods for High-Dimensional Spaces
Instead of discretizing the entire environment into a grid, sampling-based planners explore the space by tossing random points into it and connecting them if a collision-free path exists between them. The most widely known of these is the Rapidly-exploring Random Tree (RRT), which grows a tree of reachable configurations outward from the start until a branch reaches the goal. RRT is fast and works well in spaces with many dimensions, but the paths it produces tend to be jagged and far from optimal.
An extension called RRT* addressed that shortcoming. RRT* adds two operations after each new point is sampled: it checks whether rerouting through a nearby node would shorten the path to the new point, and it checks whether any existing nodes would benefit from rerouting through the new point. These operations let the tree continually improve itself. Given enough iterations, RRT* is guaranteed to converge to the optimal path. The tradeoff is speed: convergence can be slow, and a lot of computation gets spent refining the tree in regions that ultimately do not matter.2Engineering Applications of Artificial Intelligence. More Quickly-RRT*: Improved Quick Rapidly-exploring Random Tree Star algorithm based on optimized sampling point with better initial solution and convergence rate Researchers have proposed dozens of variants that bias the sampling, prune unneeded branches, or seed the tree with a rough initial solution to speed things along.
Layering Global and Local Plans
In practice, many robotic systems do not rely on a single planner. They use a hierarchical architecture: a global planner computes a coarse route across a map of known obstacles, and a local planner handles the moment-to-moment decisions needed to follow that route while dodging anything unexpected.
One approach combines an ant-colony-optimization algorithm for the global layer with the Dynamic Window Approach (DWA) for the local layer. The global path is computed first on a grid map, then key turning points along that path are fed to DWA as intermediate waypoints. DWA evaluates a set of candidate velocities the robot could execute in the next time step, scoring each one on how well it tracks the global heading, avoids nearby obstacles, and respects the robot’s speed limits. The result is a system that can follow an efficient overall route while swerving around a person who steps into the aisle or a box that was not on the original map.3Scientific Reports. Global and local path planning of robots combining ACO and dynamic window algorithm
This two-layer pattern shows up across the field, not just in ground robots. Autonomous vehicles, for instance, use a route-level planner to decide which lanes to be in and when to change, and then a local planner to generate smooth, safe trajectories that respect vehicle dynamics. One framework designed for self-driving cars constructs a “corridor” of drivable space in a curved coordinate system and then solves an optimization problem within that corridor to produce a smooth path around obstacles.4arXiv. Frenet Corridor Planner: An Optimal Local Path Planning Framework for Autonomous Driving
When Dozens of Agents Share the Space
Planning for one robot is hard enough. Planning for dozens of robots moving simultaneously through the same environment, without any of them colliding, is a different class of problem entirely. This is known as multi-agent path finding, and it comes up in Amazon-style warehouse fulfillment, airport taxiway management, and video-game AI.
The brute-force approach is to treat all agents as a single composite entity whose state includes every agent’s position. You then search for a path through that combined state space. The problem is that the state space grows exponentially with the number of agents, so the search becomes impractical for more than a handful.
Conflict-Based Search (CBS) takes a different tack. It works on two levels. At the lower level, each agent plans its own shortest path independently, as if no other agents exist. At the higher level, CBS checks whether any of those individual paths conflict. When two agents would occupy the same cell at the same time, CBS branches: in one branch, agent A is forbidden from being in that cell at that time; in the other, agent B is forbidden. Each branch re-plans the affected agent’s path under the new constraint. This process repeats, building a tree of conflict resolutions, until a set of paths is found with no collisions. Because each low-level search involves only one agent, CBS often examines far fewer states than a global A* search over the joint state space. Experiments have shown speedups of up to a full order of magnitude over previous approaches.5Proceedings of the AAAI Conference on Artificial Intelligence. Conflict-Based Search For Optimal Multi-Agent Path Finding
CBS has since been extended in several directions. A generalized version called Meta-Agent CBS allows small groups of agents to be merged and planned jointly when their conflicts are too entangled for the basic two-level scheme to resolve efficiently.6Artificial Intelligence. Conflict-based search for optimal multi-agent pathfinding Another line of work adds heuristics to the high-level search, estimating how much future conflict resolution will cost. Adding those heuristics has sped up CBS by up to a factor of five on benchmark problems.7Proceedings of the International Conference on Automated Planning and Scheduling. Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding
Machine Learning for Navigation
Classical planners require an explicit model of the environment and a well-defined cost function. Deep reinforcement learning flips the problem: instead of coding rules for how to navigate, you let an agent learn a navigation policy by trial and error in a simulated world. The agent receives a reward for reaching the goal and a penalty for hitting obstacles, and over millions of episodes it develops a mapping from sensor readings to movement commands.
The appeal is flexibility, especially in environments that change unpredictably. A trained policy can react to moving obstacles it has never seen before, because it has learned general strategies rather than memorized specific maps. Simulation experiments with mobile robots in dynamic environments have confirmed that deep reinforcement learning can achieve higher success rates than several classical baselines, and the learned policies tend to be more stable when the environment shifts.8Journal of Circuits, Systems and Computers. Mobile Robot Path Planning Method Based on Deep Reinforcement Learning Algorithm
The downsides are real, though. Training is computationally expensive. The learned policy is a black box, which makes it hard to guarantee that the robot will never do something unsafe. And performance can degrade sharply when the real world differs from the training simulation in ways the engineer did not anticipate. For these reasons, learned planners are most commonly used today as one component inside a larger system, not as the sole decision-maker.
Safety Guarantees and Control Barriers
When a robot operates near people or expensive equipment, “usually avoids collisions” is not good enough. The system needs formal guarantees that it will not crash into anything, even while replanning on the fly in a changing environment.
One promising approach uses control barrier functions (CBFs), which are mathematical constraints that define a safe region around the robot and force the controller to keep the robot inside that region at every time step. A recent framework combines model predictive control with CBFs derived from grid-based obstacle maps. Rather than requiring pre-computed equations for every obstacle shape, the method generates convex safety zones directly from the grid, making it applicable to irregular and nonconvex obstacles. In tests with a wheeled robot navigating tight, dynamically changing spaces, the approach outperformed established CBF benchmarks in computing speed, path quality, and its ability to always find a feasible trajectory.9arXiv. Safety-Critical Planning and Control for Dynamic Obstacle Avoidance Using Control Barrier Functions
Safety-critical planning is especially important for autonomous vehicles operating at highway speeds, where the margin for error is measured in fractions of a second. It is also a major concern in surgical robotics and drone flights over populated areas. As autonomous systems move into higher-stakes environments, the demand for provable safety properties is only increasing.
Coverage Planning Instead of Point-to-Point
Not every path planning problem is about getting from A to B. Sometimes the goal is to visit every part of an area: mowing a lawn, inspecting a solar farm, vacuuming a floor. This variant is called coverage path planning, and it introduces a different set of challenges. The planner must ensure complete coverage while minimizing overlap and total travel distance.
A typical pipeline for an autonomous lawnmower, for example, starts with the user drawing a boundary on an aerial map. The system converts those boundaries into coordinates, decomposes the area into simpler sub-regions, generates back-and-forth mowing paths within each sub-region, and then converts the whole plan into GPS waypoints the mower can follow.10arXiv. End-to-End Framework for Robot Lawnmower Coverage Path Planning using Cellular Decomposition The decomposition step is where the algorithmic work happens: irregular yard shapes with garden beds and trees must be split into rectangles or trapezoids that can each be covered with simple sweeping motions. Getting the decomposition wrong means the mower either misses patches or wastes time doubling back.
Coverage planning also shows up in search-and-rescue operations, agricultural spraying, undersea surveying, and any scenario where thoroughness matters more than speed.
Navigating Around People
A delivery robot rolling through a busy office building faces a problem that no purely geometric planner handles well: people have expectations about how things should move around them. Cutting between two people having a conversation is geometrically feasible but socially rude. Approaching someone from behind at high speed feels threatening even if the robot would stop in time. Social navigation research tries to encode these unwritten rules into the planner’s cost function.
One approach learns a value function that captures the social cost of different positions relative to people and their activities, then feeds that learned cost into a traditional heuristic search planner as an extra heuristic. Early work in this area has focused on specific scenarios like joining a queue, where the socially acceptable behavior is to approach from a particular direction and wait at a particular distance.11arXiv. Learning Social Heuristics for Human-Aware Path Planning The challenge is that social norms vary across cultures, contexts, and individuals, making a universal social cost function elusive.
Environmental Forces You Cannot Ignore
For ground robots on a flat floor, the environment is mostly about obstacles. For drones and underwater vehicles, the medium they move through is itself a factor. Wind, currents, and turbulence can push a vehicle off course, drain its battery, or make certain paths physically impassable.
Path planners for drones in complex terrain now incorporate real-time wind field predictions. One system uses a sampling-based planner that models the aircraft’s dynamics under nonuniform wind conditions, iteratively computing feasible trajectories using curved path segments that account for the vehicle’s minimum turning radius.12arXiv. Towards Fully Environment-Aware UAVs: Real-Time Path Planning with Online 3D Wind Field Prediction in Complex Terrain Without this kind of adaptation, a drone following a nominally shortest path through a mountain valley might find itself fighting a headwind that doubles its energy consumption, when a slightly longer path with a tailwind would have been far more efficient.
Similar issues arise in ocean robotics, where currents can be stronger than the vehicle’s top speed in some regions, and in space mission planning, where gravitational fields from multiple bodies create a constantly shifting landscape of energy costs.
Planning Under Uncertainty
Most classical planners assume the robot knows where it is and has an accurate map. In practice, both assumptions are frequently wrong. Sensors are noisy, maps are incomplete, and obstacles appear without warning. Planning under this kind of uncertainty requires a fundamentally different mathematical foundation.
The formal framework for decision-making when the state is only partially observable involves maintaining a probability distribution over where the robot might be, rather than a single point estimate. As the robot moves and takes sensor readings, it updates that distribution. The planner then chooses actions that are good across the range of plausible states, not just the most likely one. For multiple robots working together under uncertainty, the problem becomes even harder because each robot’s information is different, and communication between them may be limited or delayed.13Robotics. Decision-Making for Path Planning of Mobile Robots Under Uncertainty: A Review of Belief-Space Planning Simplifications
These methods are computationally expensive, which has led to a range of practical simplifications. Some systems plan over a simplified belief state that only tracks the robot’s position uncertainty, ignoring everything else. Others use robust optimization that plans for the worst case within a bounded uncertainty set. Still others embed probabilistic reasoning into standard graph-search algorithms, augmenting the graph with information about how much the robot expects to learn at each node. The state of the art is a patchwork of approximations, each trading off between computational cost and how faithfully it represents the robot’s actual uncertainty.
Scaling Up with Hardware
As path planning problems grow, whether because the environment is larger, the number of agents is higher, or the physical model is more detailed, the computational demands can outstrip what a standard processor can deliver in real time. Two hardware trends are pushing the boundary.
The first is GPU acceleration. Graphics processors are built for massive parallelism, and many path planning operations, like evaluating thousands of candidate trajectories simultaneously or running population-based optimization, map naturally onto GPU architectures. A recent framework for agricultural drone routing uses GPU-accelerated quantum-annealing-inspired optimization, and its core advantage is that computation time stays manageable even as the number of waypoints grows.14arXiv. GPU-Accelerated Quantum Annealing-Inspired UAV Path Planning for Smart Agriculture The “quantum-annealing-inspired” part means the algorithm mimics the energy-minimization behavior of quantum systems without requiring actual quantum hardware; the GPU is doing the heavy lifting.
The second trend is actual quantum computing, which remains largely experimental for path planning but holds theoretical promise for combinatorial problems like the traveling salesman variants that appear in multi-stop routing. Practical quantum advantage for real-world planning problems has not been demonstrated yet, and current quantum machines are noisy and small. But the theoretical speedups are large enough that several research groups are actively building hybrid classical-quantum planning pipelines in anticipation of better hardware.
What Biological Navigation Can Teach Planners
Animals solve path planning problems every day, and often with far less computation than any algorithm we have built. Migratory birds navigate thousands of kilometers using magnetic fields and celestial cues. Desert ants track their position using a mechanism called path integration: they continuously estimate their displacement from the nest by integrating their own movement, essentially running dead reckoning in their neural circuits.
Research suggests that path integration plays a more widespread role in animal navigation than previously appreciated, contributing not just to moment-to-moment positioning but to the learning of cognitive maps that represent the spatial relationships between landmarks over large scales.15PubMed Central. Map and compass navigation: the mechanism and ontogeny of animal maps This has practical relevance for robotics. Bio-inspired navigation systems that mimic path integration have been used in robots to maintain a rough sense of position when GPS is unavailable, such as inside buildings or underground. The broader lesson from biology is that navigation does not require perfect information or exhaustive search. Animals combine multiple imperfect cues, tolerate substantial error, and refine their internal maps incrementally. That philosophy aligns well with the direction modern robot planning is heading: away from the assumption of perfect knowledge and toward robust performance under messy, incomplete information.
Interestingly, the neural circuits involved in mammalian spatial navigation, particularly the grid cells and place cells discovered in the hippocampal region, have inspired a class of neural network architectures for robot localization. These networks learn spatial representations that share structural properties with biological grid cells, suggesting that evolution stumbled onto computational principles that are genuinely useful for the navigation problem regardless of whether the navigator is made of neurons or silicon.