Forecast-Aware Cooperative Planning on Temporal Graphs under Stochastic Adversarial Risk

1. Problem Statement

The paper addresses the challenge of cooperative multi-robot traversal in environments where traversal risks are not static but evolve over time due to stochastic adversarial dynamics (e.g., patrolling enemies or shifting hazards).

• Core Challenge: In dynamic environments, a "myopic" planner that only reacts to current risk levels fails to optimize team performance. It may deploy support resources too early, too late, or in locations that are no longer risky, leading to unnecessary detours and increased mission costs.
• The Gap: Existing frameworks (like TCGRE) assume static risk landscapes or deterministic adversary movements. They lack mechanisms to anticipate how risk propagates over time.
• Objective: To minimize the expected total team cost (traversal time + penalties for encountering adversaries) by coordinating robot paths and support actions (teammates temporarily pausing to cover risky edges) based on forecasted future risks.

2. Methodology

The authors propose a Forecast-Aware Cooperative Planning framework that integrates three distinct stages:

A. Adversary Dynamics Modeling

• Stochastic Model: Adversaries are modeled as moving along graph edges according to a first-order Markov stay-move process.
• Transition Probabilities: An adversary on edge $e$ either stays with probability $\theta_{stay}$ or moves to an adjacent edge $e'$ with probability $\theta_{move}$.
• Risk Propagation: The system propagates these transition probabilities forward in time to generate time-indexed edge-risk forecasts ($\rho_{uv}(t)$). This represents the probability that at least one adversary occupies edge $(u, v)$ at time $t$.

B. Forecast-Aware Support Allocation

Instead of fixing support positions based on initial risk, the method dynamically allocates support nodes based on predicted future risks.

• Candidate Selection: Identifies edges expected to become risky within the planning horizon ($T$).
• Scoring Function: For each candidate support node, a score is calculated to balance two factors:
  1. Path Overlap ($\hat{P}$): How many robot paths traverse the node (ensuring support is placed on high-traffic corridors).
  2. Risk Potential ($\hat{R}$): The cumulative forecasted risk of the edge the node can cover, weighted by spatial proximity.
  • Formula: $Score(x) = \alpha \hat{P}(x) (1 + \beta \hat{R}(x))$
• Allocation: The top-scoring nodes are assigned as support positions for specific risky edges.

C. Joint Path Planning

• Temporal Graph: The problem is formulated on a temporal graph where edge costs are time-dependent.
• Cost Function: The traversal cost for an edge includes a base cost plus a penalty if an adversary is present, unless support is active.
  • $Cost = r_a + r_p \cdot \rho_{uv}(t) \cdot (1 - \gamma^S_{uv}(t))$
  • Where $\gamma^S$ indicates if support is active.
• Solver: The team uses a Lazy A* algorithm. It defers risk evaluation until an edge is expanded during the search, using the expected risk forecasts to guide the heuristic. This ensures computational efficiency while maintaining optimality under the expected cost model.

3. Key Contributions

1. Problem Formulation: Defined cooperative multi-robot traversal on temporal graphs under stochastic adversarial risk, where costs evolve dynamically based on Markovian adversary movements.
2. Forecast-Aware Mechanism: Introduced a novel support allocation strategy that leverages risk forecasting to proactively assign support nodes to edges that will become risky, rather than just those that are currently risky.
3. Performance Validation: Demonstrated that the approach consistently reduces expected team costs compared to non-anticipatory baselines (Random, TCGRE, No Support) and approaches the performance of an "Oracle" planner (which knows the exact future adversary path).

4. Experimental Results

The authors evaluated the framework on randomly generated graphs (5 to 20 nodes) with varying numbers of robots (2–4) and adversaries (fixed at 4, with varying stay probabilities).

• Cost Reduction: The Forecast-Aware method consistently achieved the lowest expected team cost across all graph sizes and adversary mobility settings (stay probabilities 0.2 to 0.8).
• Comparison with Baselines:
  • vs. TCGRE (Static): TCGRE failed to adapt to changing risks, leading to higher costs. Forecast-Aware outperformed it by allocating support to edges that became risky later in the horizon.
  • vs. Random: Random allocation worked well only on very small graphs where the search space was limited. On larger graphs, Forecast-Aware significantly outperformed random selection by aligning support with traffic and risk.
  • vs. Oracle: The method approached the performance of an Oracle planner (which has perfect knowledge of future adversary positions), proving the efficacy of the forecasting model.
• Computational Efficiency: The method terminated within the 90-second timeout for all scenarios, whereas "No Support" baselines often failed to find feasible paths in larger, high-risk settings due to exhaustive search requirements.
• Ablation Studies:
  • Cost Calibration: The expected cost ($J_{exp}$) closely matched the realized cost ($J_{real}$) from Monte Carlo simulations, validating the accuracy of the risk forecast model.
  • Scoring Factors: Combining Risk Forecasts with Path Overlap (the default strategy) yielded the best results, proving that anticipating where robots will go is just as critical as knowing where the risk is.

5. Significance and Conclusion

This work bridges the gap between static multi-robot planning and dynamic, adversarial environments. By shifting from reactive to proactive planning, the framework allows robot teams to navigate high-risk zones more efficiently without excessive waiting or detours.

• Practical Impact: The approach is highly relevant for real-world applications like search-and-rescue in disaster zones with shifting hazards, convoy protection against patrolling threats, and warehouse logistics with dynamic obstacles.
• Future Work: The authors note current limitations regarding the need for known adversary dynamics and centralized planning. Future directions include integrating online learning to estimate adversary models in real-time and extending the framework to decentralized coordination.

In summary, the paper establishes that anticipating temporal risk evolution is a critical factor in reducing mission costs for cooperative robot teams, and provides a robust mathematical framework to achieve this.