Multi-Robot Coordination for Planning under Context Uncertainty

1. Problem Definition

The paper addresses the challenge of Multi-Robot Planning under Context Uncertainty. In real-world scenarios, robots often operate in environments where the priority ordering of objectives (e.g., speed vs. safety vs. energy) depends on an underlying context (e.g., strong currents, coral zones, human traffic) that is unknown a priori.

• The Core Challenge: Acting based on an incorrect context leads to misaligned or unsafe behavior. However, inferring the true context often requires joint sensing (coordinated robot configurations) at specific landmark states, rather than independent observations.
• Formalization: The authors formalize this as the Multi-Robot Context-Uncertain Stochastic Shortest Path (MR-CUSSP) problem.
  • State Space: $X = S \times P$, where $S$ is the joint physical state and $P$ is the set of possible contexts.
  • Observations: Information is only available at specific landmarks ($L$) when robots form specific configurations (e.g., a ring or chain). These observations are "belief-collapsing," meaning they can uniquely identify the true context.
  • Objective: Robots must first coordinate to visit landmarks to infer the true context ($c_g$), and then execute a collision-free path that optimizes a lexicographic ordering of objectives induced by that context.

2. Methodology

The authors propose a two-stage solution approach that separates the challenges of information gathering and task execution.

Stage 1: Coordinated Context Inference (CIMOP)

Algorithm: CIMOP (Coordinated Inference for Multi-Objective Planning).

• Goal: Compute joint plans to visit landmark states in an order that minimizes belief entropy (uncertainty) as quickly as possible.
• Mechanism:
  1. Entropy Calculation: Calculates the reduction in belief entropy ($H(b)$) achievable by visiting a specific landmark with a specific number of robots.
  2. Robot Assignment: Iteratively assigns the nearest available robots to the landmark offering the highest entropy reduction.
  3. Planning: Uses a standard Conflict-Based Search (CBS) planner with determinization to generate collision-free paths for groups of robots to reach their assigned landmarks.
  4. Belief Update: Upon reaching a landmark and making joint observations, the shared belief is updated. If the belief collapses (entropy = 0), the true context is identified.

Stage 2: Lexicographic Task Planning (LCBS)

Algorithm: LCBS (Lexicographic Conflict-Based Search).

• Goal: Compute collision-free paths for all robots that strictly adhere to the lexicographic preference ordering ($\Theta$) induced by the inferred context.
• Mechanism:
  • Low-Level Search: Uses Lexicographic A* (LA*) to find the optimal path for an individual robot. Unlike standard A*, LA* compares cost vectors using lexicographic ordering ($<_{lex}$) rather than scalar sums, ensuring strict priority adherence.
  • High-Level Search: Extends the Conflict-Based Search (CBS) framework. It maintains a constraint tree where nodes represent joint plans.
    • If a conflict (vertex or edge collision) is detected, the algorithm splits the node, adding constraints to force one of the conflicting robots to replan.
    • The search prioritizes nodes with the lexicographically smallest joint cost vector, ensuring the final solution is optimal under the specific context-induced preferences.

Determinization

To handle the stochastic nature of the environment efficiently, the authors use Most-Likely Outcome Determinization. This converts the stochastic domain into a discrete graph where edges represent the most probable transitions, allowing the use of efficient graph-based planners (CIMOP and LCBS) with replanning capabilities if unexpected outcomes occur.

3. Key Contributions

1. MR-CUSSP Framework: A novel formalization of multi-robot planning where objective preferences are latent and dependent on a context that can only be inferred via joint observations.
2. CIMOP Algorithm: A planning algorithm specifically designed to coordinate robots to visit landmarks that maximize information gain (entropy reduction) for context inference.
3. LCBS Algorithm: A novel extension of Conflict-Based Search that integrates Lexicographic A* at the low level. This allows for the direct optimization of strict priority orderings without needing to scalarize objectives or compute full Pareto frontiers.
4. Two-Stage Architecture: A decoupled approach that separates the "information gathering" phase from the "task execution" phase, enabling scalability and computational efficiency.

4. Experimental Results

The authors evaluated their approach in three simulated domains and a hardware deployment:

• Domains:
  1. Salp (Underwater): Robots infer flow/coral zones to prioritize ecological safety vs. speed.
  2. Warehouse: Robots infer traffic congestion levels to prioritize throughput vs. human safety.
  3. Forest Firefighting: Robots infer wind/smoke conditions to prioritize energy vs. speed.
• Baselines: Compared against ARVI/SAIA (for inference) and BB-MO-CBS, Scalarized CBS, and MO-CBS (for planning).
• Key Findings:
  • Faster Inference: CIMOP reduced belief entropy significantly faster than baselines (e.g., reaching zero entropy in 20 steps vs. 60–80 for baselines in the Salp domain).
  • Scalability: CIMOP scaled well to 35 robots, planning in under 2 minutes, whereas baselines took 40–80 minutes.
  • Planning Efficiency: LCBS maintained 100% success rate even with tight time budgets (5 seconds), while Pareto-based baselines failed significantly as time decreased.
  • Hardware Validation: Using 5 physical robots (GTernal), the full pipeline (CIMOP + LCBS) completed in under 6 seconds, compared to 40–120 seconds for baseline combinations.

5. Significance

This work is significant because it bridges the gap between active information gathering and multi-objective planning in multi-robot systems.

• Realism: It addresses the realistic constraint that critical environmental data often requires coordinated sensing, which existing independent-sensing models fail to capture.
• Safety & Alignment: By explicitly modeling context-dependent preferences, the system ensures robots do not optimize for the wrong objective (e.g., prioritizing speed in a fragile coral zone), thereby preventing unsafe or inefficient behaviors.
• Computational Tractability: By avoiding the computation of full Pareto frontiers and using lexicographic ordering directly, the approach offers a scalable solution for real-time deployment on physical robot teams.