Real-world robots often operate in settings where objective priorities depend on the underlying context of operation. When the underlying context is unknown a priori, multiple robots may have to coordinate to gather informative observations to infer the context, since acting based on an incorrect context can lead to misaligned and unsafe behavior. Once the underlying true context is inferred, the robots optimize their task-specific objectives in the preference order induced by the context. We formalize this problem as a Multi-Robot Context-Uncertain Stochastic Shortest Path (MR-CUSSP), which captures context-relevant information at landmark states through joint observations. Our two-stage solution approach is composed of (1) CIMOP (Coordinated Inference for Multi-Objective Planning), which computes plans that guide robots toward informative landmarks to efficiently infer the true context, and (2) LCBS (Lexicographic Conflict-Based Search) for collision-free multi-robot path planning with lexicographic objective preferences induced by the context. We evaluate the algorithms using three simulated domains and demonstrate practical applicability using five mobile robots in the salp domain setup.
A most-likely-outcome determinization first yields a discrete graph representation of the stochastic domain. CIMOP prioritizes visiting landmark states that minimize belief entropy and assigns robots accordingly, updating the shared belief from joint observations at landmarks. Once the context is inferred (\(c_g\)), the induced lexicographic ordering \(\Theta(c_g)\) and a heuristic drive task planning. LCBS uses lexicographic \(A^*\) to compute preference-aligned paths, detects conflicts in the joint plan, and iteratively adds constraints via binary branching until a conflict-free solution is found.
Belief entropy for 5 and 35 robots, cumulative entropy under increasing redundant landmarks, and planning time with growing team size. CIMOP infers the context faster and scales far better than ARVI and SAIA across all domains. All results are averaged over five instances with randomized starting locations.
Success rate on 15 instances (five from each domain) as the planning-time budget tightens from 120 to 5 seconds, with five robots and three objectives. LCBS holds 100% success at every budget, while BB-MO-CBS-\(k\), MO-CBS, and Scalarized CBS degrade as time shrinks.
We validate the full two-stage approach on five mobile robots in the salp domain using the Robotarium testbed. Robots adapt their formations to satisfy observation requirements at landmarks, collapse the shared belief in real time, and then execute preference-aligned plans under the inferred context.
(1) Start with a uniform belief over three contexts. (2) Form a chain to observe the cave landmark and update the belief. (3) Four robots form a ring to observe the crevice landmark and collapse the belief. (4) Robots independently plan under the inferred context \(c_2\), prioritizing minimizing coral damage over energy and time to goal.
CIMOP + LCBS (Ours) completes both stages in under 6 seconds, while other combinations require 40 to 120 seconds, enabling real-time execution on physical robots.
@inproceedings{rustagi2026mrcussp,
title = {Multi-Robot Coordination for Planning under Context Uncertainty},
author = {Rustagi, Pulkit and Wray, Kyle Hollins and Saisubramanian, Sandhya},
booktitle = {Proceedings of the thirty-ninth IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
year = {2026}
}