Many multi-agent planning problems have agents that move independently but pay for each other's choices. A road crew's work on one section does not change another crew's progress, yet both crews are fined if they close roads in the same district at the same time. Planners for these "transition-independent" problems (models where each agent's next state depends only on its own state and action) must still search a joint space that grows exponentially with the number of agents. They prune that space with optimistic bounds on the team's value. We propose computing those bounds the way optimal classical planners combine heuristics. First, solve many small models, each covering a pair of agents. Then split the fines and each agent's own costs among these models so the pieces never add up to more than the true cost. Finally, let each model greedily keep only the share of cost it actually needs and pass the rest on to the next model.
This is saturated cost partitioning moved from state abstractions to agent groups. In classical planning, the order in which components claim costs decides almost everything about bound quality. We therefore treat that order sensitivity as the central object of study rather than an implementation detail. The question is whether the order effect that dominates single-agent planning also appears, and can be controlled, when the components are overlapping groups of agents that share both local costs and interaction fines. If it does, the payoff is tighter admissible bounds for exact multi-agent search at a fraction of the cost of solving a linear program at every node.
Core Claim
Transition independence makes the projection of a multi-agent problem onto any subset of agents an exact smaller Markov decision process. The dynamics are not coarsened at all. Any looseness in a bound built from such projections therefore comes entirely from how costs are divided among them. That property turns multi-agent planning into a clean testbed for order sensitivity. Our claim is that order-aware saturated partitioning over agent-pair projections gives substantially tighter admissible bounds than the alternatives on coordination-heavy instances. The comparison points are uniform splitting of fines, the bounds used by current exact solvers, and random orders. The key ingredient is a value-per-cost ordering of agent groups adapted from classical planning.
A structural observation forces the use of pairs rather than single agents. A fine that is charged only when two agents act simultaneously cannot be charged to either agent alone. Any cost placed on agent $i$'s "maintain district X" action would also apply when nobody else is there, so admissibility forces each single agent's share of the fine to zero. The smallest components that can see an interaction are the groups of agents it involves. Each agent belongs to several such groups, so its own maintenance costs must also be divided among overlapping groups. That overlap is exactly where greedy order matters: the first pair containing agent $i$ can absorb all of $i$'s costs and starve the rest.
Relation to Prior Work
The mechanism comes from saturated cost partitioning in classical planning. That work orders a set of admissible heuristics, lets each one keep the minimum cost function that preserves its estimate, and passes the leftover costs down the sequence Diverse and Additive Cartesian Abstraction Heuristics. Later work supplies both the motivation and the tools. Seipp, Keller and Helmert prove that for a fixed set of abstractions the order alone can move the combined estimate between near zero and a perfect bound. They also show that a diverse portfolio of about 81 orders beats 200 random ones Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning. Seipp's value-per-cost greedy ordering, which ranks a component by its heuristic value divided by one plus the positive cost it consumes, reaches 1,048 solved IPC tasks against 1,008 for SymBA* Better Orders for Saturated Cost Partitioning in Optimal Classical Planning. Online order generation removes an offline phase that often exceeds 1,000 seconds Online Saturated Cost Partitioning for Classical Planning. Transition-level and subset saturation refine where costs are kept Subset-Saturated Transition Cost Partitioning. All of this work is single-agent and deterministic, and its components are abstractions that coarsen the dynamics. Our components are exact agent-group projections of a stochastic model, and the saturation step has to be redefined for expected costs.
On the multi-agent side, CoRe from Scharpff and colleagues factors the returns of transition-independent multi-agent MDPs into conditional return graphs. It uses bounds derived from those graphs to prune joint actions in branch-and-bound, and it dynamically decouples agents once their interactions end (Solving Transition-Independent Multi-Agent MDPs with Sparse Interactions; Solving Multi-agent MDPs Optimally with Conditional Return Graphs). CoRe is the solver we plug into and the strongest competitor. Its bounds never divide shared fines among agent subproblems, and the authors note that the graphs blow up when interactions are dense. Dense interaction is precisely the regime where a partitioned bound should help most. Dibangoye, Amato and Doniec show that transition and observation independence make local Markov policies sufficient and use heuristic search over occupancy states Scaling Up Decentralized MDPs Through Heuristic Search. Their result supplies the admissibility argument we reuse, though their heuristic is not built by partitioning.
The closest existing work on ordering is Agrawal, Varakantham and Yeoh's Offline-Online method. It precomputes random agent selection orders for greedy submodular team formation and picks among them at runtime Decentralized Planning for Non-dedicated Agent Teams with Submodular Rewards in Uncertain Environments, building on the greedy guarantees of Decentralized Planning in Stochastic Environments with Submodular Rewards. That work orders agents for approximate policy selection by random sampling. We order agent groups for admissible bound construction under a shared cost pool, using a guided ratio. Finally, Nair and colleagues warn that transition independence fails under physical coupling Networked Distributed POMDPs: A Synthesis of Distributed Constraint Optimization and POMDPs. This constrains our scope: under coupling, projections become approximations rather than exact models, and the clean attribution of looseness to cost splitting no longer holds.
Research Program
Write the team problem as costs to minimize, with fines as positive costs. Let $G_1,\dots,G_m$ be the agent groups: all pairs that share an interaction, plus singletons for agents with no interactions. The projection onto group $G_k$ is the MDP over the local states of its members plus the time step. Because transitions are independent, its dynamics are exact. Its cost function $c_k$ is defined on group states and actions.
Admissibility follows from a short argument. Any joint policy induces, for each group, a valid (possibly randomized and history-dependent) policy in that group's projection. Therefore, if the group cost functions satisfy $\sum_k c_k(\text{projection}_k(s,a)) \le c(s,a)$ for every joint state $s$ and joint action $a$, the sum of the groups' optimal expected costs never exceeds the optimal joint expected cost. We will write out this argument formally. It is the part a reviewer will check first.
Saturation for a stochastic projection keeps only the cost needed to preserve the group's optimal values $V_k$:
$$\hat c_k(x,a) = V_k(x) - \sum_{x'} P_k(x' \mid x,a)\, V_k(x'),$$
where $x$ is a group state, $a$ a group action, and $P_k$ the projected transition model. This is the smallest cost function under which $V_k$ still satisfies the Bellman inequalities. The leftover, $c - \hat c_k$, pulled back to joint transitions by taking the minimum over preimages, is passed to the next group. Saturated values can be negative. Handling negative costs is an open problem even in classical planning, so we will compare two options: clipping at zero, and allowing negative shares with a separate admissibility check.
On top of this, we build four ordering schemes. The first is random order. The second is a static value-per-cost order computed once. The third is a dynamic value-per-cost order that re-solves after each group claims its share. The fourth is a diversified portfolio that keeps an order only if it improves the bound on at least one sampled joint state, with the final bound being the maximum over the portfolio.
We also test an online variant in which CoRe's search supplies the sample states for diversification. This mirrors the interval strategy of online classical planning and avoids a fixed offline phase.
Baselines
The naive reference point is the bound that ignores interaction fines entirely: each agent's own optimal local cost, summed. It is admissible and cheap, and every other method must beat it. A second naive point is uniform partitioning, which splits each fine equally among the groups that see it and splits each agent's local costs equally among the groups containing it. This isolates whether saturation and ordering add anything beyond simply using pair projections.
The strongest existing method is CoRe with its own bounds from conditional return graphs Solving Multi-agent MDPs Optimally with Conditional Return Graphs. It is the strongest because it is the only solver in the file that solves Maintenance Planning Problem instances optimally at 10 agents. The file reports that it cut joint action evaluations by about one order of magnitude against dynamic programming and by several orders against SPUDD. SPUDD failed on 63.9% of certain test sets. The file reports no coverage count or bound-gap figure for CoRe on the Maintenance Planning Problem that we could adopt as a numeric target. For a fair comparison, we keep CoRe's search code, dynamic decoupling and tie-breaking fixed and swap only the bound. We give every configuration the same per-instance time and memory limit, and the time spent building the bound counts against that limit. Beating CoRe means evaluating fewer joint actions and solving more instances within the limit on the coordination-heavy and multi-agent subsets. Because CoRe is exact, we will also take the tighter of the two bounds and report whether that combination beats both.
The optimality reference is optimal cost partitioning over the same pair projections. We can pose it as one linear program over per-group occupancy measures and cost shares, and solve it at the initial state. It tells us how much of the partitioning gap each greedy order closes.
The ablations isolate the key ingredient in two ways. The first is the four ordering schemes on identical projection sets. The second is saturated partitioning over singletons versus pairs, which confirms the structural claim that single-agent projections cannot see fines.
Why not just…?
Why not just solve the optimal partitioning linear program? In classical planning, optimal cost partitioning solved only 531 tasks in 24 hours, while diversified saturation solved 966 in 30 minutes Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning. Multi-agent instances are different, though. With at most ten agents and small local models, a per-state program may be affordable, and this is a real threat. We will settle it directly by measuring the linear program's per-node time inside CoRe and its end-to-end solved count against diversified saturation. If the program wins at these scales, we report that and treat the greedy orders as useful only where the program is out of reach, on longer horizons and the scaling subset.
Why not just split fines uniformly among the involved agents? Uniform splitting avoids ordering altogether. When groups are symmetric, it may be nearly as good as saturation. It wastes budget when one pair's projection cannot use its share, for example because that pair's agents are rarely in the same district, and saturated partitioning exists precisely to reclaim such waste. The uniform baseline above measures this directly. If uniform matches saturated partitioning on most subsets, order sensitivity is not a practical concern in this domain, and we will say so.
Why not just sample random orders, as Offline-Online does? Random orders are the method of Decentralized Planning for Non-dedicated Agent Teams with Submodular Rewards in Uncertain Environments. In classical planning, guided greedy orders clearly beat random starts Better Orders for Saturated Cost Partitioning in Optimal Classical Planning. We measure the number of random orders needed to match the value-per-cost portfolio.
Why not just rely on CoRe's existing bounds? CoRe's bounds do not account for how a fine is shared across groups, and its graphs grow large under dense interaction. The swap-only comparison on the coordination-heavy subset tests whether that matters.
Proposed Experiments
The primary benchmark is the Maintenance Planning Problem suite used by CoRe. The random two-agent horizon sweep measures bound tightness against known optima. The 1,000 coordination-heavy instances form the dense regime. The 1,200 general instances with two to four agents measure overall solved counts. The pyramid instances test scaling to ten agents. As a secondary check with different interaction structure, we use the transition-independent meeting-in-a-grid and recycling robot domains from Scaling Up Decentralized MDPs Through Heuristic Search. The metrics are the initial-state bound as a fraction of the optimal cost, joint actions evaluated, wall-clock time including bound construction, and instances solved within the limit.
The first decisive check concerns order spread. On identical pair-projection sets, we compute the ratio of the best to the worst bound over sampled orders. If that spread is small on the coordination-heavy instances, the order sensitivity that dominates classical planning does not transfer. The contribution then reduces to "pair projections with uniform splitting", and we will report it that way. The second check is whether value-per-cost ordering closes most of the gap between random orders and the optimal linear program at the initial state. The third is whether the tighter bound turns into fewer joint action evaluations and more solved instances inside CoRe once construction time is counted. A final stress test adds sparse physical coupling (shared corridor cells) to the grid domains. It measures how quickly the method degrades once projections stop being exact, which marks the edge of where transition independence carries the method.
References
- Diverse and Additive Cartesian Abstraction Heuristics
- Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning
- Better Orders for Saturated Cost Partitioning in Optimal Classical Planning
- Online Saturated Cost Partitioning for Classical Planning
- Subset-Saturated Transition Cost Partitioning
- Solving Transition-Independent Multi-Agent MDPs with Sparse Interactions
- Solving Multi-agent MDPs Optimally with Conditional Return Graphs
- Scaling Up Decentralized MDPs Through Heuristic Search
- Decentralized Planning for Non-dedicated Agent Teams with Submodular Rewards in Uncertain Environments
- Decentralized Planning in Stochastic Environments with Submodular Rewards
- Networked Distributed POMDPs: A Synthesis of Distributed Constraint Optimization and POMDPs