Multi-robot Graph Traversal with Support Coordination under Stochastically Moving Adversaries

Manshi Limbu; Xuan Wang; Gregory J. Stein; Daigo Shishika; Xuesu Xiao

cs.MAMar 16, 2026

Multi-robot Graph Traversal with Support Coordination under Stochastically Moving Adversaries

Authors: Manshi Limbu, Xuan Wang, Gregory J. Stein, Daigo Shishika, Xuesu Xiao

Organizations: George Mason University

Abstract

Cooperative multi-robot missions require team of robots to traverse environments where adversaries or hazards with stochastic dynamics induce time-varying traversal risk. While support coordination--where robots assist teammates in traversing risky regions--can significantly reduce mission costs, its effectiveness depends on the team's ability to anticipate future risk. We formulate support-based multi-robot graph traversal problem with stochastically moving adversaries, where future risky regions become uncertain as adversaries move through the environment. When adversaries remain stationary, our formulation reduces to the static risky-edge setting. To address the stochastic case, we model individual adversaries as first-order Markov stay-move processes over graph edges and propagate their occupancy distributions over a finite planning horizon to obtain time-indexed edge-risk forecasts. These forecasts inform the support candidate selection and joint robot path planning. Experimental results show that forecast-informed support decisions consistently lower expected team cost relative to evaluated baselines in stochastic motion settings.

Figures & tables

Fig. 1 : From stationary to stochastic adversaries in multi-robot graph traversal. Stationary adversaries result in static edge risks (left), whereas adversaries with stochastic stay–move dynamics induce time-varying, dynamic edge risks (right), motivating anticipatory support coordination.

Fig. 2 : Forecast-aware cooperative planning pipeline. The graph (left) has adversaries with stochastic dynamics $\theta$ . Their occupancy distributions are propagated forward in time to obtain edge-risk forecasts $\rho_{uv}(t)$ (red, middle). These forecasts guide support candidate selection, producing support-edge mappings $\Gamma_{uv}$ (green, middle). The resulting temporal graph (right) enables joint planning to minimize forecast-based expected team cost.

Fig. 3 : Expected team cost ( $J_{\exp}$ ) across adversary stay probabilities $\{0.2,0.5,0.8,1.0\}$ , graph sizes ( $|V|\in\{5,10,15,20\}$ ), and robot–adversary configurations $\{2\times 4,3\times 4,4\times 4\}$ . Rows show configurations and columns show graph sizes.

Fig. 4 : Illustrative example on a 5-node graph (stay = 0.8) comparing No Support and the Forecast-aware method.

Ag	Adv	stay = 0.2			stay = 0.5			stay = 0.8
Ag	Adv	$J_{\exp}$	$J_{\text{real}}$	$\Delta$	$J_{\exp}$	$J_{\text{real}}$	$\Delta$	$J_{\exp}$	$J_{\text{real}}$	$\Delta$
2	2	6.63	6.52	-0.11	6.41	6.16	-0.25	5.65	5.34	-0.31
2	4	8.18	8.06	-0.12	8.06	7.93	-0.13	7.09	6.62	-0.47
2	6	9.48	9.30	-0.18	9.21	9.03	-0.18	7.88	7.40	-0.48
2	8	10.77	10.71	-0.06	10.69	10.52	-0.17	9.43	8.56	-0.87
3	2	9.61	9.30	-0.31	9.36	9.12	-0.24	8.74	8.52	-0.22

TABLE I : Cost calibration of expected vs. realized team cost (

J_{\text{exp}}

J_{\text{real}}

) across stay probabilities

(stay=\{0.2,0.5,0.8\})

, robots

(Ag=\{2,3,4\})

, and adversaries

(Adv=\{2,4,6,8\})

on a 10-node graph (

r=1.6

k=2

, and

s=1

). Each

J_{\mathrm{real}}

averages 2,500 realizations (500 MC trials for each of five random seeds)

Fig. 5 : Comparison of node-scoring factors across stay probabilities $(stay=\{0.2,0.5,0.8,1.0\})$ for DSDG and SSSG scenarios with $2\times 4$ and $3\times 4$ robot-adversary configurations on a 10-node graph ( $r=1.6$ , $k=2$ , $s=1$ ).

Explore similar work

Multi-Robot Multi-Goal Motion Planning with Stochastic Skills
Oct 6, 2026William Schnyder, Valentin N. Hartmann, Stelian CorosMulti-Robot Motion Planning Multi-Agent Planning
Computational Robotics Lab (CRL), ETH Zürich
Stochastic Multi-Objective Kinodynamic Planning Against Adversaries
Jul 21, 2026Thomas Marshall Vielmetti, Daniel Cherenson, Dimitra PanagouGeometric Planning Planning
Multi-Robot Coordination for Planning under Context Uncertainty
Mar 14, 2026Pulkit Rustagi, Kyle Hollins Wray, Sandhya SaisubramanianMulti-Robot Systems Multi-Robot Motion Planning
Collaborative Robotics and Intelligent Systems (CoRIS) Institute, Oregon State University, Corvallis, OR 97331, USA · Khoury College of Computer Sciences, Northeastern University, Boston, MA 02115, USA

Oct 6, 2026, cs.ROJ/K move · Enter open · S save

Multi-Robot Multi-Goal Motion Planning with Stochastic Skills

William Schnyder, Valentin N. Hartmann, Stelian Coros

Computational Robotics Lab (CRL), ETH Zürich

Multi-Robot Motion Planning Multi-Agent Planning

Open paper AskPDF arXiv

As robots are increasingly deployed in groups and share workspaces to execute real-world tasks, planning their concurrent motions around complex manipulation skills becomes essential. These skills involve continuous physical execution and may exhibit stochastic behavior, resulting in variable execution times and uncertain continuous trajectories. Existing planners either limit execution to single-robot scenarios, rely on open-loop paths, or use post-hoc scheduling that prevents dynamic coordination. In this paper, we address this gap by integrating stochastic skills into sampling-based multi-robot planning by formulating the problem as a Markov Decision Process (MDP) over a multi-modal composite roadmap. For stochastic skills, solving the MDP yields a reactive policy that allows controllable robots to dynamically adapt their motions in response to other robots' execution of manipulation skills. By resolving skill uncertainty directly at planning time, this approach avoids the pessimism of conservative baselines and unlocks robust, dynamic multi-robot coordination. Code for the planners is available at https://www.vhartmann.com/stochastic-skills.

Abstract

Explore similar work

Multi-Robot Multi-Goal Motion Planning with Stochastic Skills

Stochastic Multi-Objective Kinodynamic Planning Against Adversaries

Multi-Robot Coordination for Planning under Context Uncertainty