Motion Planning in Dynamic Environments, Softcover reprint of the original 1st ed. 1991
Coll. Computer Science Workbench

Computer Science Workbench is a monograph series which will provide you with an in-depth working knowledge of current developments in computer technology. Every volume in this series will deal with a topic of importance in computer science and elaborate on how you yourself can build systems related to the main theme. You will be able to develop a variety of systems, including computer software tools, computer graphics, computer animation, database management systems, and computer-aided design and manufacturing systems. Computer Science Workbench represents an important new contribution in the field of practical computer technology. TOSIYASU L. KUNII To my parents Kenjiro and Nori Fujimura Preface Motion planning is an area in robotics that has received much attention recently. Much of the past research focuses on static environments - various methods have been developed and their characteristics have been well investigated. Although it is essential for autonomous intelligent robots to be able to navigate within dynamic worlds, the problem of motion planning in dynamic domains is relatively little understood compared with static problems.

1 Introduction.- 1.1 Dynamic environments.- 1.2 Statement of the problem.- 1.3 Scope of the monograph.- 2 Background.- 2.1 Stationary obstacles.- 2.1.1 Configuration spaces.- 2.1.2 Shortest path problems.- 2.1.3 General problems.- 2.2 Dynamic obstacles.- 2.2.1 Hardness results.- 2.2.2 Space-time formulations.- 2.2.3 Divide-and-conquere fomulations.- 2.2.4 Collision avoidance with moving obstacles.- 2.2.5 Collision detection among moving objects.- 2.3 Summary.- 3 Time-Minimal Motion: Basics.- 3.1 Introduction.- 3.2 Accessibility graphs.- 3.3 Planning and motion.- 3.4 Time-minimal motion theorem.- 3.5 Analysis.- 3.6 Discussions.- 3.7 Summary.- 4 Time-Minimal Motion: Applications.- 4.1 Concave obstacles.- 4.2 Convex obstacles.- 4.2.1 Polygonal obstacles.- 4.2.2 Circular obstacles.- 4.3 Start point and destination point.- 4.3.1 Fast moving destination point.- 4.3.2 Piecewise linear motion of the destination point.- 4.3.3 Piecewise continuous motion of the destination point.- 4.3.4 Disjoint start points.- 4.3.5 Starting from a line segment.- 4.4 Piecewise linear motion of the obstacles.- 4.4.1 Extension.- 4.4.2 Optimality.- 4.4.3 Complexity.- 4.4.4 Comparison with other approaches.- 4.4.5 Repeated motion.- 4.5 Nonlinear motion of the obstacles.- 4.5.1 Accelerating obstacles.- 4.5.2 Rotating obstacles.- 4.6 Splitting and merging obstacles.- 4.6.1 Splits and merges.- 4.6.2 Subgoals.- 4.6.3 Algorithm.- 4.6.4 Analysis.- 4.6.5 Moving obstacles with uncertain velocities.- 4.7 Heuristics in dynamic domains.- 4.8 Unexpected obstacles.- 4.9 Summary.- 5 Time-Minimal Motion: Generalizations.- 5.1 Transient obstacles.- 5.1.1 Statement of the problem.- 5.1.2 Disappearing obstacles.- 5.1.3 Appearing obstacles.- 5.1.4 Propagation of the wavefront.- 5.1.5 Algorithm and analysis.- 5.2 Moving obstacles in three dimensions.- 5.2.1 Properties of shortest paths.- 5.2.2 Properties of time-minimal motions.- 5.3 Summary.- 6 Constrained Motion.- 6.1 Constraints on the motion of the robot.- 6.2 Space representation.- 6.3 Path search.- 6.4 Simulation results.- 6.5 Summary.- 7 Multiple Mobile Agents.- 7.1 Distributed approaches.- 7.2 Mobile agents.- 7.3 Simulation results.- 7.4 Summary.- 8 Conclusions.- 8.1 Summary.- 8.2 Open problems.- References.