RESCUE: Multi-Robot Planning Under Resource Uncertainty and Objective Criticality

Franco Cordeiro, Samuel Tardieu, Laurent PautetECRTS 2025 · DOI

TL;DR

This paper introduces RESCUE, a novel multi-robot planning framework that tackles the challenges of uncertain resource costs and varying objective criticality. By integrating mixed-criticality principles and distributed synchronization, RESCUE significantly improves mission robustness, resilience against robot failures, and overall efficiency compared to existing methods.

What Problem Does This Paper Address?

Autonomous multi-robot systems, like drone fleets performing active perception missions, face complex planning challenges. These missions often require robots to cooperate to achieve objectives such as collecting sensor data. While multi-robot systems offer advantages in speed and robustness, environmental factors (wind, terrain) introduce significant uncertainty in resource costs, particularly battery consumption. Furthermore, mission objectives themselves have varying levels of criticality; some are essential for mission success (high-critical), while others contribute to optimization (low-critical). Existing planning heuristics struggle to simultaneously address these issues, especially in dynamic environments requiring replanning and when dealing with potential robot failures. The paper aims to bridge this gap by developing a planning approach that can effectively manage resource uncertainty and objective criticality in a distributed multi-robot setting.

Methods

RESCUE builds upon existing techniques like Task Allocation Monte Carlo Tree Search (TA-MCTS) and Mixed-Criticality Monte Carlo Tree Search ((MC)2TS). Its core contributions include:

  • Comprehensive Model: A unified model that integrates criticality, uncertainty, and robustness for robot fleets.
  • Partitioned and Hierarchical Planning: RESCUE decomposes the problem by first dispatching objectives to groups of robots (TA-MCTS-like) and then having each robot independently schedule and execute its assigned objectives using a single-robot mixed-criticality approach ((MC)2TS-like).
  • Local Mode Change: Inspired by (MC)2TS, robots can switch between an optimistic (LO-mode) and a pessimistic (HI-mode) execution strategy based on resource consumption. This mode change is local to the robot, enhancing robustness.
  • Distributed Synchronization and Replanning: A lightweight, distributed synchronization mechanism allows robots to trigger replanning when they complete their tasks. This enables dynamic adaptation to changing conditions and efficient resource redistribution.
  • IDLE Objective: A novel "IDLE" objective is introduced to keep robots active and available for reassignment, preventing the loss of valuable resources when they have no immediate tasks.
  • Objective Spreading Factor ($\alpha$): A parameter that penalizes unbalanced objective allocations, specifically designed to mitigate the impact of robot failures by promoting a more even distribution of critical tasks.

Datasets

Not discussed in the paper. The experiments were conducted using simulated scenarios.

Key Insights and Ideas

  • Mixed-Criticality for Multi-Robots is Crucial: Applying mixed-criticality concepts, traditionally used for single-processor real-time systems, to multi-robot planning is essential for handling uncertain costs and prioritizing critical objectives.
  • Local Mode Changes Enhance Robustness: Allowing individual robots to switch criticality modes locally, rather than system-wide, prevents minor resource overruns from cascading into mission-wide disruptions.
  • The "IDLE" Objective is a Smart Resource Management Tactic: Keeping robots available even when they have completed their assigned tasks is vital for fleet resilience, allowing them to pick up tasks discarded by other robots in HI-mode or in case of failures.
  • Objective Spreading Mitigates Fault Impact: Penalizing unbalanced objective distribution (using the $\alpha$ factor) significantly improves resilience when a robot fails, ensuring that the loss of one robot doesn't disproportionately affect mission completion.

Key Results

  • Robustness: RESCUE reduced system oversizing and completed up to 40% more objectives compared to a pessimistic TA-MCTS approach in favorable environments.
  • Resilience: In scenarios with a faulty robot, RESCUE reduced the impact of the failure by up to 14% compared to a non-mixed-criticality approach. It also demonstrated improved safety by ensuring HI-actions were more reliably executed.
  • Efficiency: A fleet of 5 robots achieved a performance gain of up to 2.31x compared to a single robot performing the same objectives.
  • Adaptability: Frequent replanning, enabled by the distributed synchronization, allowed the fleet to adapt to changing environments and exchange objectives more effectively.

Limitations and Future Work

  • Limited Criticality Levels: The current RESCUE implementation supports only two criticality levels (high and low). Future work aims to extend this to more levels, aligning with existing avionics safety standards (e.g., DO-178C).
  • Hard Deadlines: The current framework focuses on mission-wide deadlines. Future work will enforce hard deadlines for individual objectives.
  • Communication Assumptions: The approach assumes reliable, time-bounded communication. While it tolerates intermittent issues, permanent communication loss is treated as a fault.
  • Coordinator Faults: The system assumes the coordinator is fault-free, which might not always be realistic in real-world deployments.

Summary updated

BibTeX
@inproceedings{cordeiro2025rescue,
  author = {Franco Cordeiro and Samuel Tardieu and Laurent Pautet},
  title = {{RESCUE: Multi-Robot Planning Under Resource Uncertainty and Objective Criticality}},
  booktitle = {ECRTS},
  year = {2025},
  doi = {10.4230/lipics.ecrts.2025.5},
}
Figure