pathplanning

Path planning is the process of determining a feasible route for an agent to move from a starting state to a designated goal state while avoiding collisions and, in many cases, optimizing an objective such as distance or energy. It is a foundational problem in robotics, autonomous vehicles, unmanned aerial systems, and animation, and it applies to both physical robots and virtual agents. Planning may consider the agent's kinematic and dynamic constraints and the geometry of the environment.

In formal terms, planning is often posed in a configuration space, or C-space, where each point represents a complete state of the agent. Obstacles map to forbidden regions, and the planner seeks a collision-free trajectory or path through free space. The output is typically a path parameterized by time or arc length and may be required to satisfy constraints such as nonholonomic motion, bounds on velocity and acceleration, or energy limits.

Algorithms fall into several families. Graph-based planners, such as Dijkstra’s algorithm and A*, operate on discretized representations of the space. Sampling-based planners, including PRM and RRT (and its variants like RRT*), handle high-dimensional or complex spaces. Optimization-based methods, such as CHOMP and TrajOpt, formulate path selection as the minimization of a cost function. Local planning approaches (for dynamic environments) provide rapid replanning, with methods like D*, D* Lite and others.

Applications range from autonomous navigation for ground and aerial robots to character animation and logistics routing. Common challenges include dynamic or uncertain environments, nonholonomic constraints, sensor noise, and the need for real-time replanning. Performance is assessed by path quality (length, clearance, smoothness), safety, and computational efficiency.

See also: motion planning, sampling-based motion planning, kinodynamic planning.