Heterogeneous Multirobot Coordination with Spatial and Temporal Constraints - Robotics Institute Carnegie Mellon University

Heterogeneous Multirobot Coordination with Spatial and Temporal Constraints

Conference Paper, Proceedings of 20th National Conference on Artificial Intelligence (AAAI '05), pp. 1292 - 1297, June, 2005

Abstract

Existing approaches to multirobot coordination separate scheduling and task allocation, but finding the optimal schedule with joint tasks and spatial constraints requires robots to simultaneously solve the scheduling, task allocation, and path planning problems. We present a formal description of the multirobot joint task allocation problem with heterogeneous capabilities and spatial constraints and an instantiation of the problem for the search and rescue domain. We introduce a novel declarative framework for modeling the problem as a mixed integer linear programming (MILP) problem and present a centralized anytime algorithm with error bounds. We demonstrate that our algorithm can outperform standard MILP solving techniques, greedy heuristics, and a market based approach which separates scheduling and task allocation.

Notes
Thanks too to iLog Corporation for their generous support

BibTeX

@conference{Koes-2005-9205,
author = {Mary Koes and Illah Nourbakhsh and Katia Sycara},
title = {Heterogeneous Multirobot Coordination with Spatial and Temporal Constraints},
booktitle = {Proceedings of 20th National Conference on Artificial Intelligence (AAAI '05)},
year = {2005},
month = {June},
pages = {1292 - 1297},
publisher = {AAAI Press},
keywords = {Multirobot coordination, Integer Linear Programming},
}