Overview of Part II: Motion Planning

Planning in Continuous Spaces

Part II makes the transition from discrete to continuous state spaces. Two alter- native titles are appropriate for this part: 1) motion planning, or 2) planning in continuous state spaces. Chapters 3–8 are based on research from the field of mo- tion planning, which has been building since the 1970s; therefore, the name motion planning is widely known to refer to the collection of models and algorithms that will be covered. On the other hand, it is convenient to also think of Part II as planning in continuous spaces because this is the primary distinction with respect to most other forms of planning.

In addition, motion planning will frequently refer to motions of a robot in a 2D or 3D world that contains obstacles. The robot could model an actual robot, or any other collection of moving bodies, such as humans or flexible molecules. A motion plan involves determining what motions are appropriate for the robot so that it reaches a goal state without colliding into obstacles. Recall the examples from Section 1.2.

Many issues that arose in Chapter 2 appear once again in motion planning.

Two themes that may help to see the connection are as follows.

1. Implicit representations

A familiar theme from Chapter 2 is that planning algorithms must deal with im- plicit representations of the state space. In motion planning, this will become even more important because the state space is uncountably infinite. Furthermore, a complicated transformation exists between the world in which the models are de- fined and the space in which the planning occurs. Chapter 3 covers ways to model motion planning problems, which includes defining 2D and 3D geometric models and transforming them. Chapter 4 introduces the state space that arises for these problems. Following motion planning literature [657, 588], we will refer to this state space as the configuration space. The dimension of the configuration space corresponds to the number of degrees of freedom of the robot. Using the configura- tion space, motion planning will be viewed as a kind of search in a high-dimensional configuration space that contains implicitly represented obstacles. One additional complication is that configuration spaces have unusual topological structure that must be correctly characterized to ensure correct operation of planning algorithms. A motion plan will then be defined as a continuous path in the configuration space.

1. Continuous → discrete

A central theme throughout motion planning is to transform the continuous model into a discrete one. Due to this transformation, many algorithms from Chapter 2 are embedded in motion planning algorithms. There are two alternatives to

80

achieving this transformation, which are covered in Chapters 5 and 6, respec- tively. Chapter 6 covers combinatorial motion planning, which means that from the input model the algorithms build a discrete representation that exactly rep- resents the original problem. This leads to complete planning approaches, which are guaranteed to find a solution when it exists, or correctly report failure if one does not exist. Chapter 5 covers sampling-based motion planning, which refers to algorithms that use collision detection methods to sample the configuration space and conduct discrete searches that utilize these samples. In this case, complete- ness is sacrificed, but it is often replaced with a weaker notion, such as resolution completeness or probabilistic completeness. It is important to study both Chapters 5 and 6 because each methodology has its strengths and weaknesses. Combi- natorial methods can solve virtually any motion planning problem, and in some restricted cases, very elegant solutions may be efficiently constructed in practice. However, for the majority of “industrial-grade” motion planning problems, the running times and implementation difficulties of these algorithms make them un- appealing. Sampling-based algorithms have fulfilled much of this need in recent years by solving challenging problems in several settings, such as automobile as- sembly, humanoid robot planning, and conformational analysis in drug design. Although the completeness guarantees are weaker, the efficiency and ease of im- plementation of these methods have bolstered interest in applying motion planning algorithms to a wide variety of applications.

Two additional chapters appear in Part II. Chapter 7 covers several exten- sions of the basic motion planning problem from the earlier chapters. These extensions include avoiding moving obstacles, multiple robot coordination, ma- nipulation planning, and planning with closed kinematic chains. Algorithms that solve these problems build on the principles of earlier chapters, but each extension involves new challenges.

Chapter 8 is a transitional chapter that involves many elements of motion planning but is additionally concerned with gracefully recovering from unexpected deviations during execution. Although uncertainty in predicting the future is not explicitly modeled until Part III, Chapter 8 redefines the notion of a plan to be a function over state space, as opposed to being a path through it. The function gives the appropriate actions to take during exection, regardless of what configuration is entered. This allows the true configuration to drift away from the commanded configuration. In Part III such uncertainties will be explicitly modeled, but this comes at greater modeling and computational costs. It is worthwhile to develop effective ways to avoid this.