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

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.