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...

Full description

Saved in:
Bibliographic Details
Main Author: Au, Tsz-Chiu
Format: Conference Proceeding
Language:English
Subjects:
Dynamic programming
Heuristic algorithms
Intelligent robots
Multi-robot systems
Planning
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2153-0866
DOI:10.1109/IROS55552.2023.10341481