A Dynamic Programming Algorithm for Grid-Based Formation Planning of Multiple Vehicles

A common operation in multirobot systems is to generate a motion plan for multiple robots such that the robots can move in formation to achieve some desired effects. For example, in autonomous parking lots, a group of vehicles can be asked to move to another location when they block another vehicle that needs to leave the parking lot. In this paper, we present a novel grid-based planning approach for motion planning that minimizes the makespan of moving multiple vehicles from one location to another in a safe manner. Unlike most existing multirobot planning algorithms, our algorithm uses dynamic programming to compute a nearly-optimal motion plan for a large group of vehicles in polynomial time with the help of a given set of intermediate vehicle patterns. Our experimental results show that our algorithm is much faster than an exact algorithm but does not increase the minimum makespans tremendously.

Authors

• Tsz-Chiu Au

Keywords

• Heuristic algorithms
• Planning
• Dynamic programming
• Multi-robot systems
• Intelligent robots
• Multiple Vehicles
• Planning Of Vehicles
• Path Planning
• Multi-agent Systems
• Exact Algorithm
• Planning Algorithm
• Intermediate Pattern
• Local Information
• Urban Planning
• Undirected
• Grid Cells
• Exhaustive Search
• Autonomous Vehicles
• Vertices
• Formation Control
• Directed Acyclic Graph
• Final Configuration
• EU Energy
• Minimum Delay
• Depth-first
• Set Of Vehicles
• Bilevel Optimization
• Complete Algorithm
• Reserve System
• Control Rules
• Motion Primitives
• Simple Cycle
• Directed Graph