Path Planning

Finding, without collisions, a sequence of positions or poses to pass through from a start to a goal.

Path planning is the problem of computing a collision-free geometric route through an environment given a start and a goal; it is often used interchangeably with ‘motion planning,’ and is also called the ‘piano mover's problem.’ Strictly, a path only describes which configurations (combinations of position and orientation) are visited in sequence, with no notion of time; adding a velocity and acceleration at each moment turns a path into a trajectory, a step called trajectory planning or time parameterization. Common algorithms fall into three families: grid search (A*, Dijkstra), suited to 2D map navigation; sampling-based methods (PRM, RRT), suited to high-dimensional configuration spaces such as robot arms; and artificial potential fields, simple but prone to getting stuck in local minima. Mobile robots typically run a global path planner first, then a local planner that avoids obstacles as it goes.

ExampleA mobile robot searches a grid map with A* for a route from its charging dock to the front door that avoids furniture, then hands that jagged path to trajectory planning and the chassis controller for execution.

Also called

Path Search, Pathfinding, Piano Mover's Problem

Related

Motion Planning · Trajectory Planning · A* Search · Rapidly-exploring Random Tree · Probabilistic Roadmap · Configuration Space (C-Space)

Sources

Wikipedia: Motion planning
Lynch & Park, Modern Robotics（§9.1 path 与 trajectory 的定义；第 10 章 Motion Planning） (Chinese)