Roadmap-based motion planning in dynamic environments

In this paper a new method is presented for motion planning in dynamic environments, that is, finding a trajectory for a robot in a scene consisting of both static and dynamic, moving obstacles. We propose a practical algorithm based on a roadmap that is created for the static part of the scene. On this roadmap an approximate time-optimal trajectory from a start to a goal configuration is computed, such that the robot does not collide with any moving obstacle. The trajectory is found by performing a search for a shortest path on an implicit grid in state-time space. The approach is applicable to any robot type in configuration spaces with any dimension, and the motions of the dynamic obstacles are unconstrained, as long as they are known beforehand. The approach has been implemented for a free-flying robot in a three-dimensional workspace and experiments show that the method achieves interactive performance in complex environments.

Authors

• Jur van den Berg
• Mark H. Overmars

Keywords

• Motion planning
• Orbital robotics
• Layout
• Robots
• Trajectory
• Virtual environment
• Design automation
• Path planning
• Roentgenium
• Road accidents
• Dynamic Environment
• Shortest Path
• Configuration Space
• Dynamic Obstacles
• Degrees Of Freedom
• Amount Of Time
• Rest Of The Paper
• Unit Time
• Start Time
• Unit Length
• Reachable
• Tree Branches
• Arc Length
• Collision Detection
• Dijkstra’s Algorithm
• Destination Node
• Preprocessing Phase
• Static Obstacles
• Robot Configuration
• Start Node
• Local Trajectory
• Global Trajectory
• Priority Queue
• Top Element
• Branch Points
• Investigation Of Interactions
• Time Step