motion planning
In plain wordsWorking 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.
The task of computing a continuous robot motion, feasible and ideally optimal, that carries the robot from a start configuration to a goal without collisions while honoring constraints such as joint limits, dynamics and smoothness. It is usually posed in the robot's 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'., where the robot becomes a point and obstacles become forbidden regions. Exact algorithms exist but scale badly: the general problem is PSPACE-hard, with cost growing exponentially in the robot's degrees of freedomdegrees of freedom, n.: The number of independent ways something can move. A robot arm with six motorized joints has six; a free-floating object can slide three ways and turn three ways.. Practical families are grid and lattice search with 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. and its variants; artificial potential fields, which are fast but can trap the robot in local minima; sampling-based planners such as probabilistic roadmapsprobabilistic 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. and rapidly exploring random treesrapidly 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., which handle many-jointed arms and are probabilistically complete; and 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.. Kinodynamic planning also respects velocity and acceleration limits. A typical pipeline plans a geometric path, then smooths and time-parameterizes it for a controller. Learned policies increasingly replace explicit planning in manipulation but are harder to certify as collision-free.
Motion planning for the seven-joint arm takes about 40 milliseconds with a sampling-based planner.
Origin
Formalized from the late 1970s: Tomás Lozano-Pérez and Michael Wesley's 1979 collision-free path algorithm, Lozano-Pérez's configuration-space approach (1983), John Reif's 1979 proof that the generalized 'mover's problem' is PSPACE-hard, Jacob Schwartz and Micha Sharir's 'piano movers' papers (1983) and Oussama Khatib's potential fields (1986). Jean-Claude Latombe's textbook Robot Motion Planning (1991) consolidated the field.
Usage note
Overlaps with path planningpath planning, n.: Finding 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., which some reserve for the geometric route, often of a mobile robot, while motion planning adds timing, dynamics and many-jointed bodies. Distinct from 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. in symbolic AI, which sequences discrete actions rather than continuous motions.
Related
- path planningpath planning, n.: Finding 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.
- 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'.
- 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.
- 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.
- 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.
- 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.
- inverse kinematicsinverse kinematics, n.: Working backward from where you want a robot's hand to be to the joint angles that will put it there, like working out how to bend your arm to touch your nose.
- 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.
Sources
- Latombe, J.-C. (1991). Robot Motion Planning. Kluwer Academic.
- LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press.
Mentioned in
roboticsrobotics, n.: The science and engineering of building robots and making them work: designing their bodies, sensors and motors, and writing the software that lets them see, plan and move safely., 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., degrees of freedomdegrees of freedom, n.: The number of independent ways something can move. A robot arm with six motorized joints has six; a free-floating object can slide three ways and turn three ways., inverse kinematicsinverse kinematics, n.: Working backward from where you want a robot's hand to be to the joint angles that will put it there, like working out how to bend your arm to touch your nose., manipulationmanipulation, n.: A robot's use of arms, hands or grippers to change the world around it: picking things up, moving, pushing, opening, assembling or using tools., path planningpath planning, n.: Finding 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., Robot Operating SystemRobot Operating System, prop. n.: Free, widely used software that serves as the plumbing of many robots, letting separate programs for sensors, planning and motors pass messages to each other, with a large library of ready-made tools., 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'., forward kinematicsforward kinematics, n.: The math that works out where a robot's hand or tool ends up, given the angles of all its joints, by chaining together the movement each joint adds., 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., 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.