Motion Planning in Dynamic Environments

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.