## Planning AlgorithmsPlanning algorithms are impacting technical disciplines and industries around the world, including robotics, computer-aided design, manufacturing, computer graphics, aerospace applications, drug design, and protein folding. This coherent and comprehensive book unifies material from several sources, including robotics, control theory, artificial intelligence, and algorithms. The treatment is centered on robot motion planning, but integrates material on planning in discrete spaces. A major part of the book is devoted to planning under uncertainty, including decision theory, Markov decision processes, and information spaces, which are the 'configuration spaces' of all sensor-based planning problems. The last part of the book delves into planning under differential constraints that arise when automating the motions of virtually any mechanical system. This text and reference is intended for students, engineers, and researchers in robotics, artificial intelligence, and control theory as well as computer graphics, algorithms, and computational biology. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

3 | |

4 | |

14 | |

16 | |

20 | |

23 | |

24 | |

22 Searching for feasible plans | 27 |

91 Preliminary concepts | 361 |

92 A game against nature | 368 |

93 Twoplayer zerosum games | 378 |

94 Nonzerosum games | 386 |

95 Decision theory under scrutiny | 393 |

Sequential Decision Theory | 408 |

102 Algorithms for computing feedback plans | 419 |

103 Infinitehorizon problems | 430 |

23 Discrete optimal planning | 36 |

24 Using logic to formulate discrete planning | 48 |

25 Logicbased planning methods | 53 |

Motion Planning | 63 |

Geometric Representations and Transformations | 66 |

32 Rigidbody transformations | 76 |

33 Transforming kinematic chains of bodies | 83 |

34 Transforming kinematic trees | 93 |

35 Nonrigid transformations | 99 |

The Configuration Space | 105 |

42 Defining the configuration space | 120 |

43 Configuration space obstacles | 129 |

44 Closed kinematic chains | 139 |

SamplingBased Motion Planning | 153 |

51 Distance and volume in Cspace | 154 |

52 Sampling theory | 161 |

53 Collision detection | 173 |

54 Incremental sampling and searching | 180 |

55 Rapidly exploring dense trees | 189 |

56 Roadmap methods for multiple queries | 196 |

Combinatorial Motion Planning | 206 |

62 Polygonal obstacle regions | 208 |

63 Cell decompositions | 218 |

64 Computational algebraic geometry | 232 |

65 Complexity of motion planning | 247 |

Extensions of Basic Motion Planning | 257 |

72 Multiple robots | 263 |

73 Mixing discrete and continuous spaces | 270 |

74 Planning for closed kinematic chains | 279 |

75 Folding problems in robotics and biology | 287 |

76 Coverage planning | 292 |

77 Optimal motion planning | 295 |

Feedback Motion Planning | 304 |

82 Discrete state spaces | 306 |

83 Vector fields and integral curves | 314 |

84 Complete methods for continuous spaces | 328 |

85 Samplingbased methods for continuous spaces | 340 |

DecisionTheoretic Planning | 357 |

Basic Decision Theory | 360 |

104 Reinforcement learning | 435 |

105 Sequential game theory | 442 |

106 Continuous state spaces | 455 |

Sensors and Information Spaces | 462 |

111 Discrete state spaces | 463 |

112 Derived information spaces | 472 |

113 Examples for discrete state spaces | 480 |

114 Continuous state spaces | 487 |

115 Examples for continuous state spaces | 494 |

116 Computing probabilistic information states | 507 |

117 Information spaces in game theory | 512 |

Planning Under Sensing Uncertainty | 522 |

121 General methods | 523 |

122 Localization | 528 |

123 Environment uncertainty and mapping | 540 |

124 Visibilitybased pursuitevasion | 564 |

125 Manipulation planning with sensing uncertainty | 570 |

Planning Under Differential Constraints | 587 |

Differential Models | 590 |

132 Phase space representation of dynamical systems | 606 |

133 Basic NewtonEuler mechanics | 615 |

134 Advanced mechanics concepts | 630 |

135 Multiple decision makers | 645 |

SamplingBased Planning Under Differential Constraints | 651 |

141 Introduction | 652 |

142 Reachability and completeness | 660 |

143 Samplingbased motion planning revisited | 670 |

144 Incremental sampling and searching methods | 678 |

145 Feedback planning under differential constraints | 693 |

146 Decoupled planning approaches | 696 |

147 Gradientbased trajectory optimization | 707 |

System Theory and Analytical Techniques | 712 |

152 Continuoustime dynamic programming | 720 |

153 Optimal paths for some wheeled vehicles | 728 |

154 Nonholonomic system theory | 736 |

155 Steering methods for nonholonomic systems | 753 |

Bibliography | 767 |

811 | |

### Common terms and phrases

action space action trajectory algebraic applied assumed backprojection boundary C-space cell decomposition Cfree Chapter collision computed Conference on Robotics configuration space considered constructed coordinate cost functional curve defined denote derived determine differential constraints Dijkstra's algorithm dimension discrete dynamic programming edge environment example exists expressed feedback plan finite Formulation given goal graph grid homeomorphic I-space initial integration Lie bracket linear manifold matrix methods metric motion planning motion planning problem Nash equilibria navigation function nondeterministic nondeterministic I-state nonholonomic obstacle region obtained open set parameters phase space planning algorithms players polygonal polynomials possible probabilistic Proceedings IEEE pursuit-evasion quaternions randomized reachable resulting roadmap Robotics & Automation rotation saddle point samples sampling-based Section sequence sequential game shown in Figure solution solve stage strategy subset Suppose topological topological space transformations transition equation tree uncertainty value iteration variables vector field velocity vertex vertices yields

### Popular passages

Page 789 - K. Kant and SW Zucker. Toward efficient trajectory planning: The path-velocity decomposition.