Robot planning for multi-robot fleets is a complex optimization challenge, complicated by uncertainties in the environment and action costs (e.g., movement affected by weather or terrain). Since exact optimization is NP-hard and requires real-time solutions, heuristics like A* and Monte-Carlo Tree Search (MCTS) are widely used. However, most prior work ignores uncertainty in action costs.
Inspired by Mixed-Criticality (MC)—originally for real-time task scheduling with uncertain execution times, we adapt MC to robot planning. We generalize it beyond time constraints to model arbitrary resource uncertainties. Our approach starts with a single-robot MCTS solution, chosen for its efficiency and online replanning capabilities. We then extend it to multi-robot systems, using a leader to coordinate smaller groups, ensuring unique objective allocation and synchronized replanning.
Experiments show our MC-based method outperforms traditional MCTS: it achieves more objectives in normal conditions, guarantees critical ones in adverse environments, reduces oversizing, and improves resilience to robot loss.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne