path planning
In plain wordsFinding a route for a robot or vehicle from a start to a goal that avoids obstacles, usually the shortest or safest one, much as a navigation app finds a route on a map.
The task of computing a collision-free geometric route between a start and a goal, usually for a mobile robotmobile robot, n.: A robot that travels around by itself — on wheels, tracks, legs, propellers or thrusters — such as a robot vacuum, warehouse cart, delivery robot or planetary rover., vehicle or dronedrone, n.: An aircraft that carries no one aboard to fly it: a person steers it from the ground, or its own software does. Small camera-carrying quadcopters are the most familiar kind., optimizing length, time, energy, clearance or risk. Unlike motion planningmotion planning, n.: Working out how a robot should move from where it is to where it needs to be, without hitting anything and within the limits of what its body can do. in the broad sense, path planning often ignores timing and detailed dynamics, which a later trajectory-generation step adds. Common methods are graph search over a grid, occupancy gridoccupancy grid, n.: A robot's map of the world drawn as a grid of small squares or cubes, each marked with the chance that something solid is there, so the robot knows where it can safely go. or road network with Dijkstra's algorithm or A*A* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first.; incremental replanners such as D* Lite, which update routes efficiently as new obstacles are sensed; sampling-based planners; and lattice planners or hybrid A*, which respect a car's turning radius. Navigation software usually splits the work between a global planner, which finds a route across the whole map, and a local planner, which follows that route while dodging moving obstacles over the next few seconds. In video games the same problem is called pathfinding.
The global path planner sends the robot down the east corridor; the local planner handles the people.
Origin
Its foundations are Edsger Dijkstra's shortest-path algorithm (1959) and A* search, developed by Peter Hart, Nils Nilsson and Bertram Raphael for SRI's ShakeyShakey the robot, prop. n.: A wheeled robot built at a California research institute between 1966 and 1972 that could look around, make a plan and carry it out: the first mobile robot to work out its own steps toward a goal. (1968). Anthony Stentz's D* (1994) introduced efficient replanning for robots in partly unknown terrain, and hybrid A* guided Stanford's car in the 2007 DARPA Urban Challenge.
Related
- motion planningmotion planning, n.: Working out how a robot should move from where it is to where it needs to be, without hitting anything and within the limits of what its body can do.
- A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first.
- occupancy gridoccupancy grid, n.: A robot's map of the world drawn as a grid of small squares or cubes, each marked with the chance that something solid is there, so the robot knows where it can safely go.
- mobile robotmobile robot, n.: A robot that travels around by itself — on wheels, tracks, legs, propellers or thrusters — such as a robot vacuum, warehouse cart, delivery robot or planetary rover.
- simultaneous localization and mappingsimultaneous localization and mapping, n.: How a robot, drone or headset builds a map of an unfamiliar place while at the same time working out where it is on that map, using its cameras or laser scanners.
- trajectory optimizationtrajectory optimization, n.: Calculating the best way for a robot to move over time, choosing exact positions, speeds and forces moment by moment so the motion is smooth, fast or energy-efficient and avoids obstacles.
- motion planningmotion planning, n.: Working out how a robot should move from where it is to where it needs to be, without hitting anything and within the limits of what its body can do.
Sources
- Hart, P. E., Nilsson, N. J. & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4(2), 100–107.
- Stentz, A. (1994). Optimal and efficient path planning for partially-known environments. Proc. IEEE ICRA 1994.
Mentioned in
A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first., automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes., Dijkstra's algorithmDijkstra's algorithm, n.: A classic method for finding the shortest routes from one starting point to every other point on a map or network, by always settling the nearest not-yet-settled point next., mobile robotmobile robot, n.: A robot that travels around by itself — on wheels, tracks, legs, propellers or thrusters — such as a robot vacuum, warehouse cart, delivery robot or planetary rover., motion planningmotion planning, n.: Working out how a robot should move from where it is to where it needs to be, without hitting anything and within the limits of what its body can do., configuration spaceconfiguration space, n.: An imaginary space in which a robot's whole body position is a single point, which turns 'move this many-jointed robot without hitting things' into 'find a path for a dot'., occupancy gridoccupancy grid, n.: A robot's map of the world drawn as a grid of small squares or cubes, each marked with the chance that something solid is there, so the robot knows where it can safely go., probabilistic roadmapprobabilistic roadmap, n.: A planning method that scatters many random safe robot poses through a space and links nearby ones into a road network, so routes can later be looked up quickly, as on a map., rapidly exploring random treerapidly exploring random tree, n.: A planning method that grows a branching tree of random moves outward from the robot's starting position, spreading quickly into open space until a branch reaches the goal.