Prioritized motion planning for multiple robots

In this paper we address the problem of motion planning for multiple robots. We introduce a prioritized method, based on a powerful method for motion planning in dynamic environments, recently developed by the authors. Our approach is generically applicable: there is no limitation on the number of degrees of freedom of each of the robots, and robots of various types - for instance free-flying robots and articulated robots - can be used simultaneously. Results show that high-quality paths can be produced in less than a second of computation time, even in confined environments involving many robots. We examine three issues in particular in this paper: the assignment of priorities to the robots, the performance of prioritized planning versus coordinated planning, and the influence of the extent by which the robot motions are constrained on the performance of the method. Results are reported in terms of both running time and the quality of the paths produced.

Authors

• Jur van den Berg
• Mark H. Overmars

Keywords

• Motion planning
• Robot kinematics
• Orbital robotics
• Robot motion
• Trajectory
• Drones
• Path Planning
• Running Time
• Dynamic Environment
• Extent Of Influence
• Planning Of Robots
• Heuristic
• Shortest Path
• Arrival Time
• Optimization Criteria
• Configuration Space
• Optimal Path
• Sum Of Time
• Latest Time
• Dijkstra’s Algorithm
• Path In Space
• Static Obstacles
• Dynamic Obstacles
• Coordinate Approach
• Increase In Path Length
• multiple robots
• prioritized