Decentralized multi-robot allocation of tasks with temporal and precedence constraints. (17th November 2017)

• Record Type: Journal Article
• Authors: Nunes, Ernesto; McIntire, Mitchell; Gini, Maria
• Is Part Of: Advanced robotics. Volume 31:Number 22(2017)
• Page Start: 1193
• Page End: 1207
• Publication Date: 2017-11-17
• Subjects: Task allocation -- temporal constraints -- precedence constraints; Robotics -- Periodicals; Robotics -- Japan -- Periodicals; Robotics; Japan; Periodicals; 629.89205
• DOI: 10.1080/01691864.2017.1396922
• Languages: English
• ISSNs: 0169-1864

Abstract

Abstract: We present an auction-based method for a team of robots to allocate and execute tasks that have temporal and precedence constraints. Temporal constraints are expressed as time windows, within which a task must be executed. The robots use our priority-based iterated sequential single-item auction algorithm to allocate tasks among themselves and keep track of their individual schedules. A key innovation is in decoupling precedence constraints from temporal constraints and dealing with them separately. We demonstrate the performance of the allocation method and show how it can be extended to handle failures and delays during task execution. We leverage the power of simulation as a tool to analyze the robustness of schedules. Data collected during simulations are used to compute well-known indexes that measure the risk of delay and failure in the robots' schedules. We demonstrate the effectiveness of our method in simulation and with real robot experiments. Graphical Abstract: