Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning
Kyle Brown, Oriana Peltzer, Martin A. Sehr, Mac Schwager, Mykel J. Kochenderfer
Abstract
We study the problem of sequential task assignment and collision-free routing for large teams of robots in applications with inter-task precedence constraints (e.g., task A and task B must both be completed before task C may begin). Such problems commonly occur in assembly planning for robotic manufacturing applications, in which sub-assemblies must be completed before they can be combined to form the final product. We propose a hierarchical algorithm for computing makespan-optimal solutions to the problem. The algorithm is evaluated on a set of randomly generated problem instances where robots must transport objects between stations in a "factory" grid world environment. In addition, we demonstrate in high-fidelity simulation that the output of our algorithm can be used to generate collision-free trajectories for non-holonomic differential-drive robots.
BibTeX
@inproceedings{icra2020_optimalsequentia,
title = {Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning},
author = {Kyle Brown and Oriana Peltzer and Martin A. Sehr and Mac Schwager and Mykel J. Kochenderfer},
booktitle = {ICRA 2020},
year = {2020}
}