What Is Motion Planning?

Motion planning is the computational problem of finding a sequence of configurations or actions that moves a robot or autonomous agent from an initial state to a goal state while satisfying geometric, kinematic, and dynamic constraints. A configuration specifies the full state of the system, such as the joint angles of a robotic arm or the position and heading of a ground vehicle, and the space of all possible configurations is called the configuration space (C-space). Motion planning algorithms search this space for a feasible or optimal path while avoiding collisions with obstacles, respecting actuator limits, and in some formulations minimizing a cost such as travel time or energy expenditure.

The discipline draws on computational geometry, control theory, and combinatorial optimization, and it has been central to robotics since the foundational work on the piano mover's problem in the early 1980s.

Configuration Space and Geometric Planning

The configuration space formulation, introduced by Lozano-Perez, transforms motion planning into a point navigation problem: the robot is abstracted to a point and obstacles are expanded by the robot's geometry, creating C-obstacles in configuration space that the path must avoid. Roadmap methods, including the Probabilistic Roadmap (PRM) algorithm, sample configurations randomly, check each for collision, and connect nearby valid configurations with local planners to build a graph of the free configuration space. Query time amounts to graph search between the start and goal nodes. PRM methods handle high-dimensional configuration spaces efficiently but require a precomputed roadmap, which limits their use in dynamic environments where obstacles move. An overview of motion planning for robots from MIT's open textbooks on robotics describes how C-space decomposition methods and their variants trade precomputation cost against query speed.

Sampling-Based Tree Methods

Rapidly-exploring Random Trees (RRT), introduced by LaValle and Kuffner in 1998, build a tree incrementally by sampling the configuration space at random and extending the tree toward each sample from its nearest node. Unlike PRM, RRT is single-query and does not require a full roadmap, making it applicable in dynamic environments. The algorithm explores the free space broadly and quickly, with each random sample biasing the tree toward unexplored regions. RRT* extends RRT with a rewiring step that reconnects nodes through lower-cost parents as the tree grows, and the cost-optimal path converges to the true optimum as the number of samples approaches infinity. Research on sampling-based planners for robotics published on arXiv reviews the current state of RRT variants, kinodynamic planners, and asymptotically optimal methods across articulated arms, aerial vehicles, and legged robots.

Navigation and Robot Control Integration

Motion planning for mobile robots must interface with a navigation stack that includes localization, mapping, and low-level control. A global planner computes a route through a map of known obstacles; a local planner then adapts the commanded trajectory in real time to account for detected obstacles not represented in the global map, using dynamic window or velocity obstacle approaches. For legged locomotion, the contact sequence and foot placement are part of the planning problem, coupling the geometric path with whole-body dynamics. Robot control and motion planning resources from the University of Illinois Robotics Systems group describe how hierarchical architectures decompose the full planning and control problem across abstraction levels, from task-space goal specification down to joint torque commands. The CMU Robotics Institute lecture notes on RRT planning provide a formal treatment of tree-based search in continuous configuration spaces.

Applications

Motion planning has applications in a range of fields, including:

• Industrial robot arm coordination in assembly and welding cells
• Autonomous vehicle path planning in structured and unstructured environments
• Surgical robot guidance for minimally invasive procedures
• Unmanned aerial vehicle route planning and deconfliction
• Space rover terrain traversal and sample acquisition