Tiered auctions for multi-agent coordination in domains with precedence constraints

Edward Jones, M Bernardine Dias, and Anthony (Tony) Stentz
Proceedings of the 26th Army Science Conference, December, 2008.


Download
  • Adobe portable document format (pdf) (629KB)
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
Many applications require teams of robots to cooperatively execute complex tasks. Among these domains are some that require robots to interact closely at particular times and locations to accomplish some task components, but otherwise allow the team members to act independently. Successful execution in such domains often requires agent interactions that must adhere to constraints of precedence. Precedence requirements can occur when agents' plans call for certain pre-conditions to be met at particular times and places. In this work we focus on precedence-constrained emergency response. In this domain a group of fire trucks agents attempt to navigate through a city in order to extinguish a set of fires that have occurred in the wake of a large-scale disaster. Another effect of the disaster is that debris have blocked roads in the city, making roads impassable for the fire trucks. Debris can be cleared by bulldozer robots, which are also operating in the environment. To maximize fire fighting performance fire trucks and bulldozers must determine when and where debris clearance interactions should occur and who should be involved. Our proposed method for coordination in domains with precedence-constrained interactions is a market-based approach to planning, allocating, and scheduling that uses a novel tiered auction framework. The tiered auction framework allows agents to solicit the assistance of other agents in determining their suitability for a task; in this framework agents hold sub-auctions to decide what interactions may best address application constraints. For the emergency response domain we propose a tiered auction method that uses single-task fire truck assignment at the top tier and multi-task bulldozer assignment at the second auction tier so that fire trucks can find maximally efficient routes to fires. We show that the tiered auction approach improves over a standard single-tier market-based approach in a simulated emergency-response domain.

Keywords
multi-robot coordination, market-based approaches

Notes

Text Reference
Edward Jones, M Bernardine Dias, and Anthony (Tony) Stentz, "Tiered auctions for multi-agent coordination in domains with precedence constraints," Proceedings of the 26th Army Science Conference, December, 2008.

BibTeX Reference
@inproceedings{Jones_2008_6233,
   author = "Edward Jones and M Bernardine Dias and Anthony (Tony) Stentz",
   title = "Tiered auctions for multi-agent coordination in domains with precedence constraints",
   booktitle = "Proceedings of the 26th Army Science Conference",
   month = "December",
   year = "2008",
}