GLocal: A Hybrid Approach to the Multi-Agent Mission Re-Planning Problem

• Main Authors: Frasheri, Mirgita, Miloradovic, Branko, Esterle, Lukas, Papadopoulos, Alessandro V.
• Format: Conference Proceeding
• Language: English
• Subjects: Autonomous Agents; Centralized Planning; Computer architecture; Costs; Decentralized Planning; Dynamic scheduling; Limiting; Multi-Agent Systems; Planning; Resource management; Task analysis
• ISSN: 2472-8322
• DOI: 10.1109/SSCI52147.2023.10371893

Multi-agent systems can be prone to failures during the execution of a mission, depending on different circumstances, such as the harshness of the environment they are deployed in. As a result, initially devised plans for completing a mission may no longer be feasible, and a re-planning process needs to take place to re-allocate any pending tasks. There are two main approaches to solve the re-planning problem (i) global re-planning techniques using a centralized planner that will redo the task allocation with the updated world state and (ii) decentralized approaches that will focus on the local plan reparation, i.e., the re-allocation of those tasks initially assigned to the failed robots, better suited to a dynamic environment and less computationally expensive. In this paper, we propose a hybrid approach, named GLocal, that combines both strategies to exploit the benefits of both, while limiting their respective drawbacks. GLocal was compared to a planner-only, and an agent-only approach, under different conditions. We show that GLocal produces shorter mission make-spans as the number of tasks and failed agents increases, while also balancing the tradeoff between the number of messages exchanged and the number of requests to the planner.