Approximate Heuristic Search for Semi-Decentralized Systems

1 Introduction

Many real-world multiagent systems must operate rapidly in challenging environments characterized by communication uncertainty. For example, drones jointly navigating subterranean cave systems may communicate only upon establishing line-of-sight (Fig. 1), while medical aircraft coordinating patient movement in tactical environments may be subject to adversarial jamming. Effective coordination in these scenarios requires agents to balance autonomous decisionmaking with the ability to synchronize beliefs when possible. The Decentralized Partially Observable Markov Decision Process (Dec-POMDP) provides a rigorous formalism for distributed multiagent planning [Becker et al., 2004; Bernstein et al., 2002; Amato et al., 2013]. While the standard Dec-POMDP formulation captures implicit communication, it does not model the explicit communication dynamics of many deployed systems, where information exchange is probabilistic and constrained by range, latency, or cost.

To overcome this gap, recent research has extended the Dec-POMDP to incorporate explicit communication costs [Goldman and Zilberstein, 2008], delays [Oliehoek and Spaan, 2012; Oliehoek, 2013], or intermittency [Zhang et al., 2024]. In this work, we focus on semi-decentralized systems characterized by intermittent connectivity (formally modeled as "sojourn" or semi-Markov information sharing). In this paradigm, agents operate independently for variable durations before re-synchronizing their histories based on specific triggers. While this offers a realistic model for systems that drift in and out of connectivity, it presents a formidable computational challenge: the planning algorithmmust reason over a joint belief space that stochastically expands and collapses, rendering exact solution methods intractable for nontrivial horizons. We assume the model dynamics, to include communication, are known a priori and therefore primarily concerned with planning rather than learning.

Existing approaches commonly trade scalability for optimality. Exact algorithms like Recursive Small-Step Semi-Decentralized A* (RS-SDA*) provide theoretical guarantees but struggle to scale beyond small benchmarks due to double-exponential complexity. Conversely, scalable approximations like Approximate RS-MAA* [Koops et al., 2024] are limited to fully decentralized execution and cannot efficiently exploit periods of connectivity. We therefore introduce Approximate RS-SDA*, an approximate heuristic search algorithm for semi-decentralized systems. Our approach interleaves offline planning with online search, effectively "collapsing" the joint belief state during communication windows. We also apply a progress-based pruning metric that accounts for probability mass across both centralized and decentralized policy components and various heuristic relaxation techniques.

Contributions

• We introduce Approximate RS-SDA*, a heuristic search algorithm that scales to large semi-decentralized problems by interleaving offline planning with online search, pruning the priority queue, and relaxing heuristics.
• We validate that Approximate RS-SDA* regularly finds near optimal solutions in less than 1% of the time required by exact solvers on standard benchmarks and both deterministic and stochastic labyrinth problems, and conduct ablation studies.
• We demonstrate real-world feasibility by executing unmanned multiagent path planning under line-of-sight communication constraints in two high-fidelity, threedimensional DARPA Subterranean Challenge simulation environments.

Ultimately, we present a scalable algorithmic framework for multiagent control in probabilistic communication environments, bridging the gap between theoretical semidecentralized models and deployable autonomous systems.

2 Preliminaries

We formulate the problem as a semi-decentralized partially observable Markov decision process (SDec-POMDP) [AlHusseini et al., 2026]. The SDec-POMDP is a model for cooperative multiagent systems subject to probabilistic communication constraints, unifying the standard Dec-POMDP and MPOMDP frameworks into a single formalism.

2.1 SDec-POMDPs

The semi-decentralized partially observable Markov decision process (SDec-POMDP) is a stochastic, semi-decentralized multiagent model for sequential decision-making under partial observability and probabilistic communication characterized by tuple ⟨I, S, ¯ A, ¯O, T,O,R, F⟩, where:

• I is a finite set of k agents,
• S is a finite set of states,
• ¯ A = ×iAi is a finite set of joint actions,
• ¯O = ×iOi is a finite set of joint observations, and
• T : S × ¯ A × S → [0, 1] is a state transition function where T(s′ | s, ¯a) is the probability of transitioning into state s′ given joint action ¯a being performed in state s,
• O : ¯O×S × ¯ A → [0, 1] is a joint-observation function where O(¯ o′ | s′ , ¯a) specifies the probability of attaining joint-observation ¯ o′ when joint action ¯a results in state s′ ,
• R : S × ¯ A → R is a reward function such that R(s, ¯a) is the immediate reward for performing joint action ¯a in state s, and
• F(· | s, ¯a) is the communication sojourn distribution. Each agent has a nonnegative sojourn communication time τi ∈ R≥0 denoting the time until it returns to an information-sharing state, conditioned on the current state s and joint action a.

2.2 Intermittent Connectivity Dynamics

The defining feature of the SDec-POMDP is the explicit modeling of intermittent connectivity via the sojourn random variable τ. Each agent in the system toggles stochastically between two information regimes:

Communication Epochs (τ = 0): An agent enters a communicating state when its sojourn time resolves to zero. This may involve communication with a global blackboard [Erman et al., 1980; Craig, 1988], or alternatively, with one of potentially many communicating subsets of agents. During a communication epoch, agents share histories and take joint actions. If τi = 0, ∀i ∈ I, we collapse the distributed set of individual agent beliefs into a single shared joint belief.

Decentralized Epochs (τ > 0): An agent operates in a decentralized state when its sojourn time is greater than zero. The agent relies on local action observation history at timestep t, hi,t = (ai,0, oi,1, . . . , ai,t-1, oi,t), possibly supplemented by prior information exchange with other agents, and acts per some decentralized policy.

This structure generalizes standard models: an SDecPOMDP with fixed τi = 0, ∀i ∈ I reduces to an MPOMDP, while τi →∞, ∀i ∈ I reduces to a Dec-POMDP.

2.3 Objective

The SDec-POMDP objective is to maximize expected reward by finding a policy encoding a favorable communication structure. Selector functions (f, g, h) govern how memories, actions, and observations inform both agent memories ¯m and "blackboard" memory mc. We seek an optimal blackboard policy πc and local agent policies ¯π that maximize the value function, where b0 is the initial belief:

Recursive expansion V πc,¯a (mc, ¯m, s) sums the immediate reward and the discounted future value across all probabilistic outcomes of communication and state transitions. This formulation relies on policy probability function ψ(¯a | mc, ¯m), which selects joint actions by toggling between the centralized blackboard policy and local agent policies depending on ¯ τ . The evolution of the system's information state is governed by the memory update functions ηc(m′c ) and η(m′i ), which determine the next memory states for the blackboard and individual agents, respectively. These update functions are conditioned on selector functions (f, g, h) that act as gates-either propagating observations and actions to the shared blackboard when the communication sojourn time τ = 0, or restricting them to local histories when τ > 0.

3 AlgorithmDesign

Approximate RS-SDA* extends exact-optimal RS-SDA* through three approximation techniques: interleaved offline planning and online search via softmax-weighted voting, stage-wise progress pruning, and tail value heuristic approximation through recursive depth limits. We also consider and implement a computationally lightweight lossy clustering strategy that groups agent histories based on observation windows of size k.

3.1 Communication and Belief Splitting

RS-SDA* partitions the posterior belief b at each stage σ into decentralized bdec and centralized bcen components. By doing so, RS-SDA* decouples the portion of the policy that leads to a communication epoch from the expensive historydependent decentralized search tree. The centralized probability mass is instead conditioned on the resulting joint belief.

Define a generalized trigger function Φ as the evaluation of communication sojourn distribution F within the complete transition context C = (s, ¯a, s′ , ¯ o′ , b′ ). Extending the communication model to C allows Φ to support any semidecentralized scenario. Communication may be conditioned on:

• States: Φ(C) = I(s′ ∈ Ssync)
• Actions: Φ(C) = I(¯a ∈ Async)
• Observations: Φ(C) = I(¯ o′ ∈ Osync)
• Beliefs: Φ(C) = I(H(b¯a¯ o′ ) > ϵ)

or some complex combination thereof, where H(b) is the entropy of belief b compared against some threshold ϵ. This allows RS-SDA* to support communication conditioned

on state-based triggers (spatial zones), action-based triggers (communication events), observation-based triggers (environment signals), and belief-based triggers (uncertainty thresholds) all within a single solver architecture.

Further define decentralized mass fraction ω as a function of the Bayesian posterior belief b¯a¯ o :

Recall that the belief over successor states s′ is updated using the set of agent histories ¯h of actions taken and observations received:

where η is a normalizing constant equal to Pr(¯ o′ | b, ¯a)-1 , and Pr(¯ o′ | b, ¯a) = ∑ s′∈S O(¯ o′ | s′ , ¯a) ∑ s∈S T(s′ | s, ¯a)b(s). Belief

b¯a¯ o′ is then generated by applying the belief update equation ∀s′ ∈ S. b¯a¯ o′ is partitioned into decentralized posterior b¯a¯ o′ dec and centralized b¯a¯ o′ cen :

We then apply a modified version of the RS-SDA* Bellman equation:

3.2 Interleaved Offline Planning and Online Search

To scale beyond the small horizons of exact solvers, we interleave offline policy generation with online search, a technique typically applied in receding horizon control for POMDPs [Paquet, 2005; Ross et al., 2008]. Approximate RS-SDA* expands the policy tree to some stage σ, executes a selected partial policy φ up to a communication epoch, and then re-plans from the resulting posterior belief b′ . This interleaving, visualized in Figure 2, mitigates the double-exponential branching factor of Dec-POMDPs and enables aggressive pruning during the offline phase. As will be demonstrated, interleaving performs remarkably well in problems with stochastic observation models such as SDEC-TIGER and NOISY LABYRINTH.

We employ an early-commitment mechanism to avoid exhaustive search when the planner identifies a strong consensus for centralization. We periodically inspect the top-k nodes of the priority queue, computed component-wise over each stage. A centralization score vector ¯ S is found by taking the Softmax-weighted average of the binary centralization RS-SDA* (Interleaved Offline Planning Online Search)

vectors ¯ vφ of these k nodes, weighted by their heuristic values V (φ) and a temperature parameter τtemp:

If score Sσ exceeds a confidence threshold δ, we discard all partial policies in the queue that would result in decentralization at stage σ. This collapses the search space onto the consensus. The search continues only until the leading policy is fully expanded up to the consensus stage σ, at which point it is executed online. This ensures that the planner commits to certain communication events without wasting further computational budget on unlikely decentralized alternatives.

3.3 Progress-Based Pruning with Centralization

The solver allocates computational resources efficiently across the belief space by implementing a stage-wise progress constraint inspired by Koops et al. [2024] and adapted for semi-decentralized settings. The centralized policy component is treated as an additional agent and the stage-wise budget L is therefore split across n+1 groups. This helps ensure that search allocates resources proportionally between resolving centralized triggers and specifying decentralized agent actions. The progress of a partial policy prog(φ) follows:

where κ is the number of groups fully specified in the current stage σ(φ), g is the group being expanded, c is the number of g's clusters that have already been assigned an action, p is the cumulative probability mass of c, and |C σ(φ) g | is the total number of clusters associated with g. Critically, prog(φ) guarantees that a fully specified policy will be found within h · L expansions, so long as L ≥ (n + 1)max(|C|).

3.4 Heuristic Approximation

Whereas exact optimal search algorithms like RS-SDA* and RS-MAA* benefit from tight, admissible heuristics to enable pruning, approximate methods benefit from computationally efficient guidance that rapidly steers the search towards promising regions of policy space. The objective is to find high-quality policies for long horizons quickly. To do so, we adapt tail value approximation for semi-decentralized execution. This technique splits the planning horizon into a solved "head" and an approximated "tail", the latter estimating value using relaxed heuristics like QMDP or POMDP. The depth of the head is represented by hyperparameter r. We partition this approximation into separate calculations for the centralized and decentralized policy components, weighted by the probability mass ω in each partition. Because QMDP assumes full state observability, it aligns closely with the information available to the centralized partition, rendering the heuristic tight while remaining computationally inexpensive.

4 Experiments

We evaluate Approximate RS-SDA* against RS-MAA*, Approximate RS-MAA*, and RS-SDA*. Collectively, these search techniques comprise the current state-of-the-art for decentralized and semi-decentralized multiagent planning. RSMAA* is the decentralized lower bound and RS-SDA* with all states and joint-actions centralized is the centralized upper bound for subsequent experiments. This section considers three semi-decentralized benchmarks from the literature, including both state and action-triggered synchronization. We also present an ablation on combinations of L, r, interleaving, and heuristic across six labyrinth problems shown in Figure 3, with and without stochastic observation dynamics.

Setup. All experiments were conducted on an AMD Ryzen 9 9900X3D 12-Core Processor (4400 MHz), with timeout occurring at 20 minutes. Approximate RS-SDA* is implemented in Python 3, and code is available at https://github.com/mahdial-husseini/RSSDA to support reproducibility. We compare directly against the RS-MAA* implementation provided by Koops et al. [2024].

Semi-Decentralized Benchmarks. We evaluate RS-SDA* on three SDec-POMDP benchmarks: SDEC-TIGER, SDECMARS, and MARITIMEMEDEVAC [Al-Husseini et al., 2026]. SDEC-TIGER uses action-based communication triggers and has stochastic observation dynamics; interleaved results are therefore presented in Table 1 as average values with standard errors across 1000 trials. SDEC-MARS and MARITIMEMEDEVAC use state-based communication triggers. Labyrinths. We also test using LABYRINTH, a two-agent graph search problem, and NOISY LABYRINTH, a more challenging variant with stochastic observations. In LABYRINTH, agents execute a search and return mission: they navigate a graph to locate a hidden target node selected uniformly from the environment and then return to the start node with the target information. The agents receive a step cost of -1 and a terminal reward of +100 if either returns to the start node having found the target. Agents can only share information and take joint actions when within line-of-sight. NOISY LABYRINTH is a high-stakes perception and drilling problem. Agents are equipped with noisy sensors that return binary observations correlated with the target's presence at the current node. The action space is augmented with a terminal DRILL action. Agents must locate the hidden target using uncertain sensor data and commit to drilling. A correct drill yields +100, while drilling at a non-target location incurs a catastrophic penalty of -200. Both problems are tested using the six generated labyrinth structures in Figure 3 and the 3D DARPA Subterranean Challenge cave sites Tunnels and Chamber in Figure 4.

Hyperparameters. We consider four hyperparameters associated with our approximation techniques: stage-wise iteration limit L, recursion limit r, sliding window length k, choice of heuristic, and whether to apply interleaved offline planning and online search. This is annotated in Tables 1 and 2 using [r][heuristic choice][k], [L], [TI1]. Not all problems benefit from sliding window clustering, and [k] and [TI1] may be left blank.

Results. Experiments on SDec-POMDP benchmarks demonstrate that Approximate RS-SDA* overcomes the scalability limitations of exact algorithms while retaining solution quality. In SDEC-MARS for h = 100, our solver returns a value of 288.86 in just 30 seconds, closely matching the centralized upper bound of 288.97. By contrast, the fully decentralized Approximate RS-MAA* baseline requires 89 seconds to find a significantly lower value of 234.06, illustrating the inherent value of exploiting intermittent communication opportunities. In SDEC-TIGER, Approximate RS-SDA* with interleaved offline planning and online search returns values that average close to the semi-decentralized exact optimal expected reward; however, each Approximate RS-SDA* run for h = 20 takes 0.01 s, whereas the exact optimal expected reward calculation requires 400 times that.

We further validate scalability on six graph-based labyrinth topologies, where we observe distinct performance trade-offs between the "Fast", "Accurate", and "Interleaved" algorithm variants. In deterministic environments, the "Fast" variant (using QMDP) is often sufficient, finding near-optimal solutions in under one second (e.g., matching the optimal 96.75 in EXTCROSS9). However, complex topologies such as MESH10 for h = 5 require the "Accurate" variant to escape local optima, improving values from 74.44 to 85.67 with only a marginal increase in computation time. In the challenging Noisy Labyrinth variants, where offline planning with either heuristic consistently times out due to high branching factors, the "Interleaved" variant proves valuable. By deferring longterm decisions until after online short-term partial policy execution, interleaving successfully achieves high-quality results (e.g., 68.05±16.06 in NOISY LADDER10 for h = 8) whereas both "Fast" and "Accurate" offline baselines time out.

5 Demonstration

We use the Prospector simulator [Ward et al., 2025a] to simulate caves from the DARPA Subterranean Challenge dataset, which features real world data from the Louisville Mega Cavern, a former limestone mine in Kentucky. Prospector remeshes the 3D data provided by DARPA, and provides sim-

(a) Tunnels traversability graph. (b) Tunnels coordination graph.

(d) Chamber coordination graph.

Figure 4: Fifteen node two-dimensional traversability and coordination graphs for two DARPA Subterranean Challenge cave sites: Tunnels and Chamber. The traversability graph has an edge between two nodes if they are spatial neighbors, and the coordination graph has an edge between two nodes if they have a line-of-sight connection.

ulations of other real-world caves using data gathered from caving expeditions.

The simulator provides a voxelized representation of these cave systems, manually marked waypoints of interest (Figure 4), accelerated collision and line-of-sight checking, and both 2D and 3D simulation modes. It also provides a low level Model Predictive Path Integral (MPPI) quadrotor controller [Ward et al., 2025b] based on a 12 degree of freedom quadrotor dynamics model [Sabatino, 2015] which is implemented in JAX [Bradbury et al., 2018] for fast, parallelized simulation.

Figure 5: Two-agent exploration of two cave systems using the Prospector simulator, featuring POV and top down views for each agent (right group), alongside an overhead view of the cave (left). Full videos are available as supplemental material.

Each quadrotor's state consists of its position, Euler angles (roll, pitch, yaw), linear velocity, and body-frame angular rates, while control inputs correspond to the angular velocities of the four rotors. The simulation time step is set to ∆t = 0.1 s. An MPPI controller [Williams et al., 2017] controls the vehicle, which samples 2048 control sequences per timestep over a horizon of 32 steps. A low temperature parameter (λ = 0.05) biases samples toward high-reward trajectories, while uniform control noise σ = 1.0 encourages exploration.

A waypoint-following reward is employed to guide each quadrotor along the node sequence computed by the algorithm described in Section 3, combining a distance-to-goal term, a control-effort regularizer, and a collision penalty:

where pt is the quadrotor's position, p⋆ ∈ R3 is the next waypoint's position, Ts is the number of states in the rollout, and wd = 1.0 is the distance weight.

where ut ∈ R4 is the control input (rotor angular velocities), Ta is the number of actions in the rollout, and wu = 0.1 is the control-effort weight.

where Coll(p, ragent) is true if the agent at position p intersects the environment within radius ragent, I[·] ∈ {0, 1} is an indicator function, and ccol = 106 is a collision penalty.

The total waypoint cost is J = Jdist +Jctrl +Jcol, and the reward is defined as the negative cost

All experiments are conducted with two agents operating simultaneously. We first consider the Tunnels environment (Figure 5a), corresponding to DARPA SubT Section 6. The policy achieves a 100% success rate over 10 randomized trials, with the quadrotors maintaining an average flight speed of 0.731 m s-1 . The entire map (31 × 59 × 4 meter extents, and an internal volume of 536 cubic meters) is explored in 20.01 seconds.

We next evaluate performance in the Chambers environment (Figure 5b), corresponding to DARPA SubT Section 5. The policy achieves a 100% success rate over 10 randomized trials, with the quadrotors maintaining an average flight speed of 0.775 m s-1 . The entire map (41 × 62 × 11 meter extents, and an internal volume of 11, 492 cubic meters) is explored in 26.10 seconds.

Overall, Approximate RS-SDA* prevents failures (collisions) whilst efficiently exploring these challenging 3D cave environments, demonstrating its efficacy as a semidecentralized planning policy in a search-and-rescue context.

6 Conclusion

We present Approximate RS-SDA*, a scalable heuristic search algorithm that supports semi-decentralized problems. The results confirm that our solver finds near-optimal solutions orders of magnitude faster than exact solvers for many types of problems. The practical impact is evidenced by our demonstrations in high-fidelity DARPA Subterranean Challenge simulations, where the high-level algorithm helped efficiently navigate complex, communication-restricted cave sites. While promising, the current framework relies on predefined communication models and has not yet been evaluated on larger teams where the combinatorial belief space expands further. Future work will address these scalability constraints by considering coordination graphs for systems with three or more agents, exploring learning-based approaches for unknown or non-stationary communication dynamics, implementing learned heuristics, and investigating the theoretical interplay between sojourn communication and the sojourn control characteristic of semi-Markov decision processes.