A Semi-Decentralized Approach to Multiagent Control

Mahdi Al-Husseini; Mykel J. Kochenderfer; Kyle H. Wray

cs.AIMar 12, 2026

A Semi-Decentralized Approach to Multiagent Control

Authors: Mahdi Al-Husseini, Mykel J. Kochenderfer, Kyle H. Wray

Organizations: Stanford University Stanford, United States · Northeastern University Boston, United States

Abstract

We introduce an expressive framework and algorithms for the semi-decentralized control of cooperative agents in environments with communication uncertainty. Whereas semi-Markov control admits a distribution over time for agent actions, semi-Markov communication, or what we refer to as semi-decentralization, gives a distribution over time for what actions and observations agents can store in their histories. We extend semi-decentralization to the partially observable Markov decision process (POMDP). The resulting SDec-POMDP unifies decentralized and multiagent POMDPs and several existing explicit communication mechanisms. We present recursive small-step semi-decentralized A* (RS-SDA*), an exact algorithm for generating optimal SDec-POMDP policies. RS-SDA* is evaluated on semi-decentralized versions of several standard benchmarks and a maritime medical evacuation scenario. This paper provides a well-defined theoretical foundation for exploring many classes of multiagent communication problems through the lens of semi-decentralization.

Figures & tables

Figure 1. A semi-decentralized multiagent evacuation scenario with probabilistic restrictions on communication. Aircraft and watercraft must coordinate under communication constraints to move patients from aid stations to hospitals.

Figure 2. The SDec-POMDP dynamic decision network, with the policy infrastructure on the left and model on the right. The green backdrop contains the blackboard with memory $M_{c}$ generated from the histories of communicating agents. The gray backdrop with plate notation includes the individual agent memories $M_{i}$ . $Z$ selector nodes are selectively toggled by $\bar{\tau}$ to facilitate memory propagation $\eta$ , represented by dashed lines. Policy $\psi$ edges are represented by dotted lines. The SDec-POMDP framework is flexible and can be easily modified to capture the structural and informational characteristics of different problem domains.

	RS-MAA*		RS-SDA*		Classical MAA*
	(RS-SDA* lower bound)		upper bound
	levels	nodes/stage	levels	nodes/stage	levels	nodes/stage
$t$	$n\|O_{\star}\|^{t}$	$n\|\mathcal{O}_{\star}\|^{t}\|A_{\star}\|$	$\|\mathcal{O}_{\star}\|^{tn}$	$\|\mathcal{O}_{\star}\|^{tn}\|A_{\star}\|^{n}$	1	$\|A_{\star}\|^{n\|\mathcal{O}_{\star}\|^{t}}$
0	2	6	1	9	1	9
1	4	12	4	36	1	81
2	8	24	16	144	1	6,561

Table 1. SDec-Tiger levels and nodes by stage for RS-MAA*, RS-SDA*, and MAA*.

|A_{\star}|=3

|O_{\star}|=2

, and

n=2

Figure 3. Illustrating RS-SDA* applied to SDec-Tiger using mixed component policies through stage $\sigma=2$ .

Figure 4. MaritimeMEDEVAC environment representation and centralized/decentralized/semi-decentralized optimal policy values for horizons one through eight.

SDec-Tiger
	lower bound		our approach		upper bound
	decentralized		semi-decentralized		centralized
	RS-MAA*		RS-SDA*		RS-SDA*
$h$	value	time	value	time	value	time
8	12.21726	1	27.21518	<1	47.71696	<1
9	15.57244	6	30.90457	<1	53.47353	<1

Table 2. RS-SDA* offline planning performance on semi-decentralized benchmarks and MaritimeMEDEVAC . TO denotes timeout (

>

1200s) and MO denotes memout (

>

16GB).

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

$\bar{a}$	$OL$	$OR$	$L$
$OL$	(-50, 20)	(-100, -100)	(-101, 9)
$OR$	(-100, -100)	(20, -50)	(9, -101)
$L$	(-101, 9)	(9, -101)	(-2, -2)

Appendix

Table 3. SDec-Tiger Rewards (

TL

TR

)

Figure 5. Illustration of four of nine possible joint actions for SDec-Tiger . Agents communicate their observation histories with some probability when they listen to the same door (in green).

Figure 6. Illustration of two of nine joint actions in SDec-FireFighting ( $n_{h}=3,n_{f}=4$ ). Agents communicate when they suppress the same house, shown in green.

Figure 7. Illustration of the SDec-BoxPushing environment. Agents communicate when they are both in the green square.

Panel of Figure 8 — Figure 8. Illustration of the SDec-Mars environment. Agents in (a), the survey site beacon scenario, can communicate when co-located or adjacent to the same not yet surveyed survey site. Agents in (b), the right band rendezvous scenario, communicate alongside the right side of the grid when at least one site remains incomplete. Agents in (c), the drill site beacon scenario, can communicate when co-located or adjacent to the same not yet drilled drill site.

Figure 9. Illustration of the MaritimeMEDEVAC environment. Agents communicate when they are positioned adjacent to patient pickup and drop-off sites.

Multi-Agent Control

Multi-agent control coordinates interacting autonomous agents to achieve shared goals while respecting safety, communication, and resource constraints.

See all 108 papers

Semi-Decentralized Multi-Spacecraft Collision Avoidance under Communication Constraints
Jul 29, 2026Grace Ra Kim, Mahdi Al-Husseini, Duncan Eddy +1Collision Avoidance Partially Observable Markov Decision Processes
PhD Candidate, Aeronautics and Astronautics, Stanford University, 496 Lomita Mall, Stanford, CA 94305 · Post-Doctoral Researcher, Aeronautics and Astronautics, Stanford University, 496 Lomita Mall, Stanford, CA 94305 · Professor, Aeronautics and Astronautics, Stanford University, 496 Lomita Mall, Stanford, CA 94305
Fully Decentralized and Safety-Aware Multi-Agent Reinforcement Learning for Control on Networks
Sep 28, 2026Theodore Rogalski, Shirantha WelikalaMulti-Agent Control Decentralized MARL
Electrical & Computer Engineering Department Stevens Institute of Technology Hoboken, USA
Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs
Sep 8, 2026Xiangwu Wang, Chengwei Cao, Hongyuan TangMulti-Agent System Optimization Multi-Agent Coordination
University of Hong Kong · University of California, San Diego · Carnegie Mellon University

Jul 29, 2026J/K move · Enter open · S save

Semi-Decentralized Multi-Spacecraft Collision Avoidance under Communication Constraints

Grace Ra Kim, Mahdi Al-Husseini, Duncan Eddy, Mykel J. Kochenderfer

PhD Candidate, Aeronautics and Astronautics, Stanford University, 496 Lomita Mall, Stanford, CA 94305 · Post-Doctoral Researcher, Aeronautics and Astronautics, Stanford University, 496 Lomita Mall, Stanford, CA 94305 · Professor, Aeronautics and Astronautics, Stanford University, 496 Lomita Mall, Stanford, CA 94305

Collision Avoidance Partially Observable Markov Decision Processes Multi-Agent Planning Multi-Agent Communication

Open paper AskPDF arXiv

Current spacecraft collision-avoidance operations rely on intermittent ground-station contacts, requiring operators to plan with delayed and asynchronously updated information. Consequently, maneuvers must be planned with only intermittent information sharing between operators, raising the question of how much coordination is needed to achieve collision-avoidance performance comparable to centralized planning. Although decision-theoretic approaches such as partially observable Markov decision processes (POMDPs) capture the sequential and uncertain nature of collision avoidance, existing multiagent extensions typically assume either continuous information sharing or communication models that do not reflect operational ground-station constraints. To explicitly model this intermittent information availability, we formulate the spacecraft-to-spacecraft collision avoidance problem as a semi-decentralized POMDP (SDec-POMDP), where we govern information propagation directly by realistic ground-station visibility windows. Joint maneuver policies are computed using approximate Recursive Small-Step Semi-Decentralized A* (RS-SDA*), following the state-of-the-art A*-based lineage for decentralized multiagent planning. Across a representative suite of conjunction scenarios, semi-decentralized planning recovers near-centralized maneuver quality while requiring 28.5% fewer synchronization events than continuous coordination. Comparisons with representative rule-based operator heuristics further show that communication-aware planning more consistently achieves the desired operational miss-distance band while minimizing unnecessary trajectory deviation. Together, these results establish a practical planning framework for autonomous collision avoidance under realistic intermittent communication, bridging the gap between idealized centralized coordination and fully decentralized planning execution.

Abstract

Multi-Agent Control

Explore similar work

Semi-Decentralized Multi-Spacecraft Collision Avoidance under Communication Constraints

Fully Decentralized and Safety-Aware Multi-Agent Reinforcement Learning for Control on Networks

Reachability-Certified Subteam Decomposition for Locally Interacting Multi-Agent MDPs