RI | Publications | Heterogeneous Multirobot Coordination with Spatial and Temporal Constraints

Text only version of this site

Heterogeneous Multirobot Coordination with Spatial and Temporal Constraints
M. Koes, I. Nourbakhsh, and K. Sycara
Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI), AAAI Press, June, 2005, pp. 1292-1297.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Download [Help]

Adobe portable document format (pdf) [424 KB]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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

Sponsor: NSF
Grant ID: IIS-0205526

Associated center: CIMDS
Associated lab/group: Intelligent Software Agents
Associated project: Urban Search and Rescue

Number of pages: 6

Note: Thanks too to iLog Corporation for their generous support

Text Reference

M. Koes, I. Nourbakhsh, and K. Sycara, "Heterogeneous Multirobot Coordination with Spatial and Temporal Constraints," Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI), AAAI Press, June, 2005, pp. 1292-1297.

BibTeX Reference

@inproceedings{Koes_2005_5138,
   author = "Mary Koes and Illah Nourbakhsh and Katia Sycara",
   title = "Heterogeneous Multirobot Coordination with Spatial and Temporal Constraints",
   booktitle = "Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI)",
   month = "June",
   year = "2005",
   pages = "1292-1297",
   publisher = "AAAI Press",
   note = "Thanks too to iLog Corporation for their generous support"
}