D-ITAGS: A Dynamic Interleaved Approach to Resilient Task Allocation, Scheduling, and Motion Planning
- 6 January 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 8 (2) , 1037-1044
Abstract
Complex, multi-task missions require the coordination of heterogeneous robots at multiple inter-connected levels, such as coalition formation, scheduling, and motion planning. This challenge is exacerbated by dynamic changes, such as sensor and actuator failures, communication loss, and unexpected delays. We introduce Dynamic Iterative Task Allocation Graph Search (D-ITAGS) to simultaneously address coalition formation, scheduling, and motion planning in dynamic settings involving heterogeneous teams. D-ITAGS achieves resilience via two key characteristics: i) interleaved execution, and ii) targeted repair. Interleaved execution enables an effective search for solutions at each layer while avoiding incompatibility with other layers. Targeted repair identifies and repairs parts of the existing solution impacted by a given disruption, while conserving the rest. In addition to algorithmic contributions, we derive accurate bounds on schedule suboptimality and provide insights into the inherent trade-off between time and resource optimality in these settings. Our experiments reveal that i) D-ITAGS is significantly faster than recomputation from scratch in dynamic settings, with little to no loss in solution quality, and ii) the theoretical bounds on optimality gap consistently hold in practice.Keywords
All Related Versions
Funding Information
- Army Research Laboratory (W911NF-17-2-0181, W911NF-20-2-0036)
This publication has 27 references indexed in Scilit:
- A taxonomy for task allocation problems with temporal and ordering constraintsRobotics and Autonomous Systems, 2017
- Multi-Robot Coalitions Formation with Deadlines: Complexity Analysis and SolutionsPLOS ONE, 2017
- Heterogeneous Multi-Robot System for Mapping Environmental Variables of GreenhousesSensors, 2016
- A novel distributed scheduling algorithm for time-critical multi-agent systems2015
- A Heuristic Distributed Task Allocation Method for Multivehicle Multitask Problems and Its Application to Search and Rescue ScenarioIEEE Transactions on Cybernetics, 2015
- A distributed multi-agent production planning and scheduling framework for mobile robotsComputers & Industrial Engineering, 2013
- The Open Motion Planning LibraryIEEE Robotics & Automation Magazine, 2012
- Analysis of Dynamic Task Allocation in Multi-Robot SystemsThe International Journal of Robotics Research, 2006
- A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot SystemsThe International Journal of Robotics Research, 2004
- RoboCup Rescue: search and rescue in large-scale disasters as a domain for autonomous agents research2003