View Chapter

Chapter 7 — Motion Planning

Lydia E. Kavraki and Steven M. LaValle

This chapter first provides a formulation of the geometric path planning problem in Sect. 7.2 and then introduces sampling-based planning in Sect. 7.3. Sampling-based planners are general techniques applicable to a wide set of problems and have been successful in dealing with hard planning instances. For specific, often simpler, planning instances, alternative approaches exist and are presented in Sect. 7.4. These approaches provide theoretical guarantees and for simple planning instances they outperform samplingbased planners. Section 7.5 considers problems that involve differential constraints, while Sect. 7.6 overviews several other extensions of the basic problem formulation and proposed solutions. Finally, Sect. 7.8 addresses some important andmore advanced topics related to motion planning.

Powder transfer task using demonstration-guided motion planning

Author  Ron Alterovitz

Video ID : 17

In unstructured environments such as people's homes, robots executing a task might need to avoid obstacles while satisfying the task's motion constraints. In this video, a robot completes a powder transfer task using demonstration-guided motion planning, an approach that combines an asymptotically-optimal sampling-based motion planner with a learned cost metric which encodes the task constraints.

Simulation of a large crowd

Author  Dinesh Manocha

Video ID : 21

Motion-planning methods can be used to simulate a large crowd which is a system with a very high degree of freedom. This video illustrates an approach that uses an optimization method to compute a biomechanically energy-efficient, collision-free trajectory for each agent. Many phenomena arise such as lane formation.

Motion planning in multi-robot scenario.

Author  Jamie Snape, Jur van den Berg, Stephen J. Guy, Dinesh Manocha

Video ID : 22

Motion planning can be used for multiple robot scenarios. In this video, each iRobot Roomba senses its surroundings and acts independently without central coordination or communication with other robots. This approach uses the current position and the velocity of other robots to predict their future trajectories in order to avoid collisions.

Alpha puzzle

Author  Mark Moll

Video ID : 23

The alpha puzzle problem is a common benchmark scenario for motion planning. The puzzle consists of two intertwined twisted tubes. The objective is to separate the tubes, where one tube is considered a stationary obstacle and the other tube is the moving object (robot). Solving the problem is challenging because it contains a narrow passage in the configuration space. This plan was generated by a sampling-based motion planner implemented in the Open Motion Planning Library (OMPL).

Kinodynamic motion planning for a car-like robot

Author  Caleb Voss

Video ID : 24

In this video, the objective of the car is to reach a goal location by jumping over a ramp and pushing a block out of the way. This problem requires kinodynamic motion planning for a car-like robot using a physics simulator. This video was generated using the software tools OMPL, Blender, and MORSE.