Synthesis of Communication Policies for Multi-Agent Systems Robust to Communication Restrictions

1 Introduction

In cooperative multi-agent systems (MAS), individual agents are required to collaborate to achieve a joint task. One way to achieve this collaboration is to provide a centralized joint policy that the agents must adhere to. Typically, such policies need to correlate the actions of different agents. As a result, their successful execution requires communication between the agents to exchange, for example, local state information, and to coordinate their actions. However, in many real-world settings, agents have to operate in environments where communication could be restricted due to physical limitations, such as limited bandwidth or signal interference. As such restrictions can severely impact the coordination between agents and, hence, their performance, it is imperative that communication restrictions be considered in the design of joint policies for MAS. This requires devising policies that prescribe how the limited resources available for communication should be allocated.

In this paper, we focus on cooperative MAS with joint reach-avoid objectives (which require the agents to reach some target set of joint states while avoiding some unsafe states), possibly operating under communication restrictions on the number of agents allowed to communicate. We consider the setting where communicating agents exchange full current state information and jointly select actions. This requires policies that determine which subset of agents should communicate at the current state of system execution, which we term communication policies. Clearly, communication policies cannot depend on the full information about agents' local states, as this would defeat their purpose. In this work, we assume that communication policies can use some public information about the agents' states, which, in practice, could be very limited or even non-existent. A typical example is a system in which agents know the coarse regions in which other agents are located but not their precise locations. The rationale is that this public information is significantly less costly to communicate and changes less frequently.

We study the problem of synthesizing communication policies, together with joint policies that govern the agents' actions, which we call action policies. The challenge is that these two policies should be synthesized in tandem since the joint action policy should be adapted to the communication policy, requiring as little communication as possible beyond that allowed by the communication policy. To address this challenge, we introduce a cost function that, intuitively, measures the information exchange between agents required by the action policy that goes beyond what is allowed by the communication policy. We show that this cost function can be used in an upper bound on the performance loss when the action policy is executed under restricted communication and following the communication policy. Based on this bound, we propose a method for synthesizing pairs of action and communication policies that minimizes an overapproximation of the cost function and achieves optimal reach-avoid probability under unrestricted communication. 1

Related work. Decision-theoretic models for MAS [Rizk et al., 2018] such as decentralized MDPs (Dec-MDPs) and decentralized partially observable MDPs (DecPOMDPs) [Goldman and Zilberstein, 2004] and their respective policy synthesis problems have been extensively studied. A key characteristic of these models is that agents cannot communicate. In contrast, in our setting, agents are allowed to communicate and exchange information about their independent local states and transitions, but this communication must be minimized relative to a communication policy.

1 An extended version of this paper is available at: https://arxiv. org/abs/2505.13311

A number of MAS models exist where communication is allowed but used sparsely to simplify the policy synthesis task. These include [Guestrin et al., 2001], where a coordination graph representing the dependencies between the agents is given, and [Melo and Veloso, 2011], where the decentralized model is equipped with information about the states in which the agents need to interact. Other methods [Wu et al., 2011] use online planning to use communication dynamically on demand. These approaches enable the synthesis of optimal policies that conform to given communication structures or minimize communication. On the other hand, our method synthesizes optimal action policies equipped with communication policies that make them robust to communication restrictions.

The closest to our work is [Karabag et al., 2022], which proposes a technique for constructing joint policies for cooperative MAS that are robust to temporary or permanent loss of communication. In contrast, the policies we compute must be robust to communication restrictions, and thus benefit from associated communication policies. Thus, while [Karabag et al., 2022] can use total correlation to synthesize policies minimizing dependency between the agents, we need to develop a cost function whose values depend on the sought communication policy. Similarly to [Karabag et al., 2022], our cost function uses information-theoretic measures, but the challenge is to account for the unknown communication policy.

2 Preliminaries

In this section, we review some definitions and concepts.

For n ∈ N, we define [n] := {1, . . . , n}. We denote the set of discrete probability distributions over a set X with ∆(X).

Markov decision processes (MDPs) provide a framework for modeling and analysis of sequential decision processes.

Definition 1. A Markov decision process (MDP) is a tuple M = (S, A, P, sinit ) where S is a finite set of states, A is a finite set of actions, P : S×A→∆(S) is a partial transition probability function, and sinit ∈ S is an initial state.

For simplicity we sometimes write P(s, a, s′ ) instead of P(s, a)(s′ ), for s, s′ ∈ S and a ∈ A. We denote with A(s) := {s ∈ S | ∃s′ ∈ S. P(s, a, s′ ) > 0} the set of actions enabled in s ∈ S. We assume that A(s) ̸= ∅ for every s ∈ S.

A path in an MDP M is a finite or infinite sequence τ = s0a1s1 . . . st-1atst, . . . of alternating states and actions such that P(st, at+1, st+1) > 0 for all t ∈ N.

A policy for an MDP M = (S,A, P, sinit) is a function π : (S · A)∗ · S → ∆(A), that maps each finite path ending in a state to a probability distribution over actions and is such that if π(s0a1 . . . st)(a) > 0, then a ∈ A(st). A policy is called positional, if its decisions depend solely on the current state. Formally, we can represent a positional policy π as a function π : S → ∆(A). For simplicity, we write π(τ, a) and π(s, a) instead of π(τ)(a) and π(s)(a), respectively.

Definition 2. A Markov chain is a triple C = (S, P, sinit) where S is the set of states, P : S → ∆(S) is the transition probability function, and sinit ∈ S is the initial state.

Given an MDP M, a policy π for M induces an (potentially infinite-state) Markov chain. We denote this Markov chain with Mπ, which is defined as Mπ = ((S ·A)∗ ·S, PMπ , sinit ), where for every τ = s0a1 . . . st-1atst ∈ (S · A)∗ · S, a ∈ A and s ∈ S we have that PMπ (τ, τ · a · s) = π(τ, a) · P(st, a, s). For a positional policy π for an MDP M, the induced Markov chain has a finite set of states. Formally, Mπ = (S, PMπ , sinit ), where for every s ∈ S and s′ ∈ S we have PMπ (s, s′ ) = ∑a∈A(s) π(s, a) · P (s, a, s′ ).

A Markov chain C = (S, P, sinit) can be seen as a sequence of discrete stochastic variables (St, t ∈ N), which generates a stationary process S where P(St = s) is the probability of the chain visiting state s ∈ S at time t. The occupancy measure of a state s is νs := ∑∞t=0 P(St = s).

Given a policy π for an MDP M = (S,A, P, sinit), we denote with νs,a the occupancy measure of the state-action pair (s, a), i.e., the expected number of times that action a is taken at state s, defined as νs,a := ∑∞t=0 P(St = s, At = a). By definition, we have that νs,a = ∑∞t=0 P(St = s,At = a) = ∑∞t=0 P(St = s) · P(At = a | St = s) = π(s, a) · νs.

Entropy of Stochastic Processes

The entropy is a measure of uncertainty about the outcome of a random variable [Shannon and Weaver, 1949].

Definition 3. For a discrete random variable X, its support V defines a countable sample space from which X takes a value v ∈ V according to a probability mass function (pmf) p(v) := P(X = v). The entropy of X is defined as H(X) := - ∑v∈V p(v) log p(v). By convention, 0 log 0 = 0.

The entropy is always non-negative. It vanishes for a deterministic X (i.e., if X is completely determined).

Let (X1,X2) be a pair of random variables with joint pmf p(v1, v2) and support V1 × V2. The joint entropy of (X1,X2) is defined by H(X1,X2) := - ∑v1∈V1 ∑v2∈V2 p(v1, v2) log p(v1, v2).

The conditional entropy of a random variable X1 given X2 is defined as H(X1|X2) := - ∑v1∈V1 ∑v2∈V2 p(v1, v2) log p(v1 | v2).

The joint and conditional entropy definitions extend to the collection of n random variables [Cover and Thomas, 2006].

The entropy of a Markov chain C = (S, P, sinit) is defined as the joint entropy over all random variables St for t ∈ N. That is, H(C) := H(S0, S1, S2, . . .) = ∑∞t=0 H(St | St-1 . . . S0). The entropy of a Markov chain is in general infinite. The entropy of a Markov chain is finite if and only if it is absorbing [Biondi et al., 2014]. In this paper, we restrict our analysis to absorbing Markov chains.

[Biondi et al., 2014] showed that the entropy of a Markov chain can be characterized in terms of the occupancy measure of the states and their so-called local entropy. The local entropy L(s) of a state s in a Markov chain is the entropy of the probability distribution over the next states defined by P, formally, L(s) := H(St+1 | St = s) =

- ∑s′∈S P(s, s′ ) logP(s, s′ ). Then, as shown in [Biondi et al., 2014], the entropy H(C) can be expressed as H(C) = ∑s∈S L(s) · νs, where νs is the occupancy measure of s.

Multi-Agent Markov Decision Processes

Multi-agent Markov decision processes (MMDPs) describe sequential decision-making tasks in which multiple agents select actions in order to collaboratively maximize a given common reward-based optimization criterion. A joint policy prescribes actions for all agents. During the execution of such a policy, all agents have access to the joint state of the system.

Definition 4. Formally, a Multi-agent Markov decision process (MMDP) is a tuple M = (N, S, A, P, sinit ) where:

• N is the number of agents;
• S = S 1 ×S 2 × . . . ×S N is a finite set of global states;
• A = A1 ×A2 ×. . .×AN is a finite set of joint actions;
• P : S ×A → ∆(S) is the joint transition probability function such that for every s = ⟨s1 , . . . , sN ⟩ ∈ S, a = ⟨a1 , . . . , aN ⟩ ∈ A and u = ⟨u1 , . . . , uN ⟩ ∈ S it holds that P(s, a)(u) := ∏Ni=1 P i (si , ai )(ui ), where S i , Ai and P i : S i ×Ai →∆(S i ) are the local states, actions and transition probability function of agent i ∈ [N];
• sinit = ⟨s1init , . . . , sNinit ⟩ ∈ S is the initial state.

We identify agents with the elements of the set [N]. Each agent i ∈ [N] is modeled by an MDP M i = (S i ,Ai , P i , siinit ). Note that the transition probability functions P i of the agents are independent and the joint transition probability function in Definition 4 is defined as their product. We denote with i the set [N] \ {i} of agents other than i.

All agents have access to a centralized view and operate in the environment by executing a positional joint policy πact : S → ∆(A). We denote with Πpos act (M) := S → ∆(A) the set of positional joint policies for an MMDPM.

In this paper, we consider MMDPs with joint reachavoid objectives. Such an objective is defined as a pair (Starget , Savoid ) of sets of states such that Starget ∩Savoid = ∅. It requires that the agents maximize the probability of reaching a joint state in Starget , while avoiding Savoid .

Given a joint policy πact for an MMDP M with a reach-avoid objective (Starget , Savoid), we denote with PMπact ((¬Savoid)UStarget ) the probability of reaching Starget while avoiding Savoid in the Markov Chain Mπact .

Given a reach-avoid objective in an MMDP M, the optimal joint policy synthesis problem requires finding a policy π∗ such that PMπ∗ ((¬Savoid)UStarget ) = supπ PMπ ((¬Savoid)UStarget ). The optimal policy that maximizes the reach-avoid probability is denoted as π∗ , and the optimal value is denoted as v∗ (M, Starget , Savoid ).

Since a joint policy in an MMDP has access to the full state, it is essentially a policy in the product MDP. Thus, for reach-avoid objectives, it suffices to consider positional joint policies. An optimal joint policy πact for the reach-avoid objective (Starget , Savoid) in the MMDP M can be computed using standard techniques by solving a linear program.

3 ProblemFormulation

Implementing joint policies in environments with uncertainty requires effective coordination among the agents. Achieving this coordination often depends on establishing robust communication. However, agents may face limitations in their communication capabilities, including restrictions on the type and amount of information they can share. Additionally, at certain time steps, the environment might limit the number of agents allowed to communicate. Let us consider an example.

Example 1. Figure 1 depicts a simple robot navigation problem where three robots must coordinate to reach their respective targets while avoiding collision. The target locations of robots R1, R2, and R3 are labeled with T1, T2, and T3, respectively. Each of R1 and R2 has two potential target locations. Once each of the robots has reached one of their targets, the team's task is complete.

To maximize the probability of reaching their targets while avoiding collision, the robots must communicate, exchanging information about their current locations and actions. What communication is necessary depends on the executed joint policy and the resulting execution paths. For example, if R1 and R2 decide to swap their locations to reach their respective targets at the top of the grid, communication between these two agents is essential to avoid collisions, while R3 can navigate to its target independently, disregarding the positions of the other robots. On the other hand, if one of R1 or R2 decides to reach its target at the bottom of the grid, communication between this robot and R3 will be needed. Finally, if both R1 and R2 decide to reach their targets at the bottom of the grid, then all three robots must communicate.

Consider the scenario where the communication is constrained, and at any given time at most two robots are allowed to communicate. In order to be robust to this restriction, the joint policy should minimize the need for communication between all three robots at the same time, and should be equipped with a communication policy that prescribes which pair of robots should communicate at a given time.

We study the cooperative execution of a joint policy under specific conditions. Consider a scenario where agents can, without restriction, share some public information, such as, for example, their current region. Additionally, they can share precise state and local information, but there is a limitation on the number of agents permitted to do this at any given time.

We now extend the policy execution in this scenario, which we refer to as 'restricted communication', and present our problem formulation. We formalize our problem as a Markov game with one and a half players: the multi-agent system, and the stochastic environment. The objective of the system is to reach the set of target states while avoiding the "avoid" states. The game is played in a sequence of rounds, starting at an initial state. At each step, public information is freely exchanged between all agents, and based on this information the agents collaboratively select a subset of agents for further information exchange, which includes the sharing of agents' local states. Communication is established within this subset, with the selected agents sharing information and making collective decisions. Conversely, the remaining agents cannot communicate and share local state information. Consequently, the remaining agents must act independently and make decisions solely based on locally available information and estimates of other agents' states. After all agents execute the respective policies to select actions, the process transitions to the next state according to the probabilistic transition relation.

Definition 5. We formulate the team's decision problem as a cooperative Markov game represented as a tuple ̂ M = (M, O1 , . . . , ON , L1 , . . . LN , K) where

• for each i ∈ [N], Oi andLi are finite sets of respectively publicly observable and local states of agent i;
• M = (N, S,A, P, sinit) is an MMDP such that S i = Oi ×Li for each agent i ∈ [N];
• K ∈ {0, 1, . . . ,N} is the number of agents allowed to communicate at each point in time.

In the above definition, we consider MMDPs of a special form where the states of each agent are factored into a public part Oi that can be observed by all the other agents and local part Li that cannot be directly observed by the other agents. In order for agent i's local state information to become known to another agent, agent i must communicate that information to that agent. We consider a setting where there can be a disruption in the communication, resulting in the restriction that only K out of the N agents are allowed to communicate. When K = N we are in the full-communication case where any joint policy can be executed due to the unrestricted communication between the agents. In the other extreme, when K = 0 no communication is allowed. When communication is restricted, that is, K < N, we assume that agents rely on the notion of imaginary play introduced in [Karabag et al., 2022] in order to estimate the current local states of other agents. Furthermore, when 0 < K < N, agents need to agree at each step of the execution on a subset of at most K agents that will communicate, that is, exchange state information, at this step. This is done by choosing the so-called communication actions prescribed by a communication policy. The communication policy is a joint policy that is guaranteed to be implementable because it relies only on the public part of the agents' states, which can be always shared by all agents.

In Definition 5, the number K of agents allowed to exchange information when communication is restricted is fixed. Our results can be extended to the case when K changes dynamically in the course of the execution.

We define the set of communication actions consisting of the sets of agents of size exactly K, that is Acomm := {c ⊆ [N] | |c|= K}. While we could allow communication actions selecting sets with fewer than K agents, such actions are dominated by those with maximal allowed cardinality.

For c ∈ Acomm, the set of remaining agents is c := [N]\c. We denote by O := O1 × . . . ×ON the set of joint public states. A communication policy is a function of the form πcomm : O+ → ∆(Acomm). We let Πcomm(O,K) be the class of all communication policies for given O and K. We denote with Πpos comm(O,K) := O → ∆(Acomm) the set of positional communication policies for ̂ M.

The agents operate in the environment by executing a pair of joint policies π = (πcomm, πact) where πcomm ∈ Πcomm and πact ∈ Πact. We refer to πact as an action policy and to πcomm as a communication policy. Each agent maintains a local imaginary copy of the current local states of the other agents. At each decision step, all agents first share the public parts of their states. The agents execute jointly the policy πcomm to select a subset c of K agents that will communicate with each other at the current step. The subset of agents eligible for communication shares the local part of their states with each other, and each agent updates their local imaginary copy based on the received information. Thus, the agents in c have accurate knowledge of each other's current local state, while this can be inaccurate for the rest of the agents. Subsequently, the agents in c jointly execute the action policy πact to determine a joint action. Each of the other agents executes πact independently. Its state gets updated accordingly, and the local imaginary copies of the states of the agents in i are sampled from the respective distributions. After that, the system proceeds to the next decision step. This continues until a state in Starget ∪ Savoid is reached. At each step, the agents selected for communication operate in a centralized manner.

Execution under Restricted Communication

The evolution of the system given a pair of communication and action policies can be formalized as follows. Given ̂ M = (M,O1 , . . . ,ON ,L1 , . . . LN ,K) with M = (N, S,A, P, sinit), a pair of positional joint policies π = (πcomm, πact) ∈ Πpos comm(O,K) × Πpos act (M) induces a Markov chain ̂ Mπ = ( ̂ S, ̂ P, ̂ sinit ) defined as follows.

• The set of states is ̂ S = ̂ S 1 × . . . × ̂ S N , where for each agent i ∈ [N] we have ̂ S i := S i × ∏j∈i Lj .

∏i∈c pi,a,c · ∏j∈c pj,aj,c where the quantities q, and pi,a,c, and pj,aj,c are defined below. We pick the smallest imin ∈ c and define the element lk c ∈ Lk for k ∈ [N], where lk c = lk 1 if k ∈ c and lk c = limin,k 1 otherwise.

Then, we define

For U ⊆ S, we define ̂ U ⊆ ̂ S as ̂ U = {⟨⟨si ,mi ⟩⟩i∈[N] ∈ ̂ S | ⟨si ⟩i∈[N] ∈ U}. We thus lift Starget and Savoid to ̂ Starget and ̂ Savoid. For a pair π = (πcomm, πact) ∈ Πpos comm(O, K)×Πpos act (M) of communication and action policies, P̂ Mπ ((¬ ̂ Savoid )U ̂ Starget ) is the probability of reaching Starget while avoiding Savoid , executing πcomm and πact.

Our goal is to compute a pair (π∗ comm, π∗ act ) of positional communication and action policies such that π∗ act is optimal for M under unrestricted communication, and among all pairs with optimal action policies, π∗ is optimal for ̂ M.

Problem 1. Given a cooperative Markov game ̂ M = (M = (N, S,A, P, sinit),O1 , . . . ,ON ,L1 , . . . LN ,K) as in Definition 5 and a reach-avoid objective (Starget , Savoid) for M, find a pair of positional policies π∗ = (π∗ comm, π∗ act ) ∈ Πpos comm(O,K) × Πpos act (M) such that PMπ∗act ((¬Savoid)UStarget ) = v∗ (M, Starget , Savoid) and for every π = (πcomm, πact) ∈ Πpos comm(O,K) × Πpos act (M) for which we have PMπact ((¬Savoid )UStarget ) = v∗ (M, Starget , Savoid), it also holds that

We restrict Problem 1 to positional communication and action policies. By considering a cooperative Markov game where |O|= 1 but different sets of agents need to communicate over time, it is easy to see that communication policies with memory are strictly more powerful. However, for the sake of efficient synthesis, we focus on positional policies.

4 Policy Synthesis

For the rest of this section, we fix a cooperative Markov game ̂ M = (M,O1 , . . . ,ON ,L1 , . . . LN ,K) with M = (N, S,A, P, sinit) as in Definition 5, and a reach-avoid objective (Starget , Savoid). Our goal is to compute a joint action policy that is both optimal and robust to communication restrictions. To this end, we introduce a cost function based on entropy for information sharing among agents. We first present this cost function, followed by our approach for computing a pair of action and communication policies.

4.1 Cost Function for Information Sharing Relative to a Communication Policy

Recall that we denote O := O1 × . . .ON and L := L1 × . . . LN . For each communication action c ∈ Acomm, we define Oc := ∏i∈c Oi and Lc := ∏i∈c Li .

Let π = (πcomm, πact) ∈ Πpos comm(O, K) × Πpos act (M) be a pair of positional joint communication and action policies.

The cost function D(πcomm,πact) which we define, measures the information exchange between agents required by the action policy that goes beyond what is allowed by the communication policy. It considers all agents i and all possible coalitions c of K agents. With each, it associates a value Gi (πcomm, πact) or Gc (πcomm, πact), respectively. These are sums of entropy over time, with additional conditioning on the global observations O and weighted by the probability that at the respective time step the process is "relevant".

where

Note that if K = 0, that is, Acomm = {∅}, then πcomm is a constant function and no communication between any agents is allowed. In such case, D(πcomm,πact) is the total correlation from [Karabag et al., 2022]. When K > 0, only the correlation between agents that are outside of what is allowed by πcomm contributes to the value of D(πcomm,πact). If D(πcomm,πact) is 0, this means that all dependencies between the agents in πact are covered by the respective agents being allowed by πcomm to communicate at the necessary points in time.

The cost function D(πcomm,πact) has a key property, namely it allows us to provide an upper bound on the performance loss under restricted communication. This is established in the next theorem. Complete proofs are provided in the extended version of this paper [Soudijani and Dimitrova, 2025].

Theorem 1. For any cooperative Markov game ̂ M with MMDP M, reach-avoid objective (Starget , Savoid ), and π = (πcomm, πact) ∈ Πpos comm(O, K) × Πpos act (M), it holds that

Due to the form of D(πcomm,πact), in our method for computing a pair of communication and action policies, described in the rest of the section, we will use a proxy function.

4.2 Policy Synthesis

Our approach proceeds in two steps.

Optimistic Optimal Value for Reach-Avoid Probability

As we require the action policy to be optimal under unrestricted communication, in the first step, we compute the optimal value v∗ (M, Starget , Savoid ) for the reach-avoid probability assuming unrestricted communication.

Minimizing the Cost of Communication

In the second step, we use the value v∗ (M, Starget , Savoid) as a threshold in the computation of a pair (πcomm, πact) of policies. This threshold constrains the action policy πact to be optimal under unrestricted communication. Additionally, we formulate an objective function based on the cost function D(πcomm,πact). To this end, we provide a proxy to D(πcomm,πact), expressed in terms of occupancy measures. The term ∑∞t=1 H (AtSt|S0A1S1 . . . At-1St-1) can be expressed in terms of occupancy measure using existing results [Biondi et al., 2014]. For the other two terms in D(πcomm,πact), we provide upper bounds.

Consider a pair of joint policies π = (πcomm, πact) and the Markov chain Mπact induced from the MMDP M. This Markov chain generates a stationary process X, which is the joint path of the agents. The entropy H (X) of X has a closed form expression in terms of νs,a.

Proposition 1. The entropy of the joint state-action process until reaching the target can be expressed in terms of the state-action occupancy measure νs,a as

The path of a single agent i or a group of agents c follows a hidden Markov model where X is the underlying process and Xi , or Xc , respectively, is the observed process. Therefore, the terms Gi (πcomm, πact) and Gc (πcomm, πact) do not have closed-form expressions based on occupancy measures. Instead, we employ stationary processes which induce the same occupancy measures, and derive expressions that are upper bounds for Gi (πcomm, πact) and Gc (πcomm, πact).

For each agent i ∈ [N] and each set of agents c ∈ Acomm, we consider the stationary process that induces the same occupancy measures νo,li ,ai and νo,lc ,ac, respectively, as the joint policy. We establish the following proposition.

Proposition 2. Let

Combining Proposition 1 and Proposition 2, we obtain an upper bound ¯D(πcomm,πact) on D(πcomm,πact) based on occupancy measures. That is, we have D(πcomm,πact) ≤ ¯D(πcomm,πact) for

Cost optimization problem. Using the function ¯D defined in eq. (1), we formulate bellow, in (2), the optimization problem with decision variables xo,l,a and xo,c, representing the occupancy measures for each joint public state-local state-action triplet (o, l, a) and for each joint public statecommunication action pair (o, c), respectively. Through appropriate marginalization, xo,li ,ai and xo,lc ,ac represent the public state-local state-action occupancy measures for individual agents and groups of agents, respectively. For synthesis, we assume that the occupancy measure is finite for all states s ∈ S \ (Savoid ∪ Starget). We add absorbing sink-states and corresponding actions to ̂ M, denoted with (oα, lα) = ((o1α, l1α), . . . , (onα, lnα)) and aα = (a1α, . . . , anα), respectively. These states represent the end of the game concerning the reach-avoid objective, that is, for all (o, l) ∈ (Starget ∪ Savoid ) we have P ((o, l), aα)((oα, lα)) = 1.

We consider the optimization problem (2) with the objective (2a) and constraints (2b) - (2h) given below. The value v∗ computed in the first step is used to constrain from below the reach-avoid probability of the action policy. Additionally, the value of the function ¯D must be minimized.

The constraints (2b) - (2g) are presented below.

Constraints (2b), (2c) and (2d) capture the definitions of the expressions ¯ Gi (πcomm, πact), ¯ Gc (πcomm, πact) and H (X) from Proposition 2 and Proposition 1 respectively. Formally,

Similarly, constraints (2e) encode the respective definitions from Proposition 2. Formally, we have

Constraint (2f) lower-bounds the reach-avoid probability for the sought action policy, and constraint (2g) enforces the usual flow constraint for occupancy measures:

Finally, constraints (2h) express the relationship between the occupancy measures xo,l,a and xo,c via the occupancy measure of o ∈ O.

Policies from an optimal solution. Let (x∗o,l,a , x∗o,c ) be an optimal solution to the optimization problem (2). We define the pair (π∗ comm, π∗ act ) of policies by

The next theorem states that (π∗ comm, π∗ act ) has the desired properties, namely π∗ act ensures v∗ under unrestricted communication, and (π∗ comm, π∗ act ) minimizes the value of ¯D.

Theorem 2. Let ̂ M be a cooperative Markov game with MMDP M, (Starget , Savoid) be a reach-avoid objective, and (π∗ comm, π∗ act ) be the pair of policies defined by (3) for an optimal solution to (2a). Then, we have PMπ∗act ((¬Savoid)UStarget ) = supπ PMπ ((¬Savoid)UStarget ). Furthermore, for every pair (π′comm, π′act ) ∈ Πpos comm(O, K) × Πpos act (M) of positional joint communication and action policies, if the policy π′act is optimal, that is, if PMπ′act ((¬Savoid)UStarget ) = supπ PMπ ((¬Savoid)UStarget ), then for function ¯D defined in eq. (1) we have ¯D(π∗ comm,π∗ act ) ≤ ¯D(π′comm,π′act ).

5 Experimental Evaluation

We evaluated our approach on four multi-robot navigation scenarios. In each scenario, we consider a MAS with three agents and K = 2. We used the formalization in Section 4 to synthesize for each problem a pair of communication and action policies. All experiments were performed on a Macbook Pro with an Apple M2 chip and 32GB memory. The two optimization problems are solved using GLPK [Makhorin, 2000] and SNOPT [Gill et al., 2018], respectively. The detailed setup and results of all scenarios are included in [Soudijani and Dimitrova, 2025].

With this evaluation we aim to demonstrate the following.

1. Our method synthesizes policies with zero communication cost (which means they fully conform to the communication restrictions) when such policies exist.
2. Our method is capable of synthesizing policies that adhere to communication restriction while incurring zero communication cost-an outcome that cannot be achieved through approaches based solely on minimizing total correlation as an objective function.
3. Our method can synthesize communication policies that adapt dynamically to the current state of public information so that the set of communicating agents changes.
4. There is a trade-off between performance (the reachavoid probability) and the value of our cost function.

Next, we describe the four scenarios and the respective results. Further details can be found in the extended version of this paper [Soudijani and Dimitrova, 2025].

Scenario #1 with Navigation Tasks

We consider the environment in Figure 1. The task of the robots, initialized as marked in the figure, is to navigate to one of their target cells, labeled T1, T2, and T3, respectively, avoiding collision. At any given time, only two robots can communicate and share precise locations. Which ones communicate is decided based on public information, which is the current regions of the robots. The regions, labeled o = 0, o = 1, and o = 2 are shown in Figure 2a. The possible actions are moving in one of the four cardinal directions or remaining in place. Moves succeed with probability 0.9 and fail, resulting in remaining in the current cell, with probability 0.1. The remain action and impossible actions stay in place.

Result. The method proposed in Section 4 generates a pair of policies where the action policy is optimal under unrestricted communication, with reach-avoid probability 0.99. The synthesized communication policy results in cost zero. It assigns probability 1 to robots R1 and R2 communicating. The synthesized action policy matches that, unlike other possible action policies with reach-avoid probability 0.99. Thus, our method identifies a suitable action policy that can be equipped with a communication policy achieving cost zero.

Scenario #2 with a Swarm Intersection

The goal of this scenario is to compare our method with the approach based on minimizing the total correlation. In the scenario depicted in Figure 2b, three robots are required to navigate to their respective target locations while avoiding collisions. The publicly available information corresponding to each region is illustrated in Figure 2c. Again, only two out of three agents can communicate their precise location without an extra communication cost.

The work closest to ours is [Karabag et al., 2022], which employs total correlation to measure dependencies between agents and to synthesize an (action) policy that is robust to communication loss. However, [Karabag et al., 2022] does not consider communication policies since robustness is w.r.t. complete loss of communication, not to partial limitation of the communication. Thus, there is a baseline for comparison only for the action policies synthesized by our approach (which are optimal), namely the policies computed using total correlation in the objective function. Minimizing total correlation cannot yield action policies that satisfy communication restrictions, whereas our method can do so, and also generates a matching communication policy.

Result. In scenario #2, our approach finds a pair of action and communication policies that satisfy the reach-avoid property with probability 1 and ensure communication cost 0. Thus, it finds policies that satisfy the communication restriction. In contrast, the action policy generated using total correlation violates the communication restriction at time t = 2 when it requires coordination among three agents. Here, the minimum total correlation is 0.591, while the total correlation of the policy computed by our method is 0.693, and thus it will not be computed by minimizing total correlation.

Scenario #3 with a Hallway

In this scenario, we consider the environment in Figure 2d. The public information regions, labeled o = 0, o = 1, and o = 2, are depicted in Figure 2e. In this scenario, coordination among certain robots is critical at certain time steps to avoid collisions. As before, only two of the robots are allowed to communicate at any given time.

Result. The synthesized action policy achieves a reachavoid probability of 1, and the communication policy ensures zero communication cost by selecting the appropriate set of robots to communicate in different public information states.

Scenario #4 with High Uncertainty

The robots in the environment shown in Figure 2f must navigate to their respective target cells while avoiding collisions. The public information regions here correspond to the rows, as shown in Figure 2g. The actions are the same as in Scenario #1. Here, however, the move actions lead to the desired cell with probability 0.9, and the remaining 0.1 probability is redistributed across the current cell and all other neighboring cells. For impossible move actions, the full transition probability 1.0 is redistributed among the current cell and all valid neighboring cells. As in previous scenarios, when communication is restricted, only two of three agents can communicate. In this scenario, a crowded intersection necessitates communication among all agents to avoid collisions.

Result. Here, the optimal reach-avoid probability under full communication is 0.958. No pair of action and communication policies exists that achieves this probability with zero communication cost. If, however, we lower the threshold and only ask for a policy that guarantees 0.92 reach-avoid probability under unrestricted communication, then our method synthesizes one with zero cost.

Performance

Our evaluation is focused on evaluating the quality of our approach on a range of relatively small but interesting problem instances, as well as its principle feasibility. Although our method requires solving large nonlinear optimization problems to synthesize a pair of policies, the running time remains reasonable for the considered benchmarks. The runtimes range from a few minutes for Environment #3 (with 528 constraints and 62,581 variables) to one hour for Environment #4 (with 531 constraints and 62,956 variables) and Environment #2 (with 1,332 constraints and 163,081 variables), and up to three hours for Environment #1 (with 1,344 constraints and 164,581 variables). Clearly, the performance depends on the number of agents and the sparsity of the transition probability matrices. In the future, we plan to conduct larger-scale experiments and develop techniques for further improving performance.

6 Discussions and FutureWork

Limitations and extensions. One limitation of the model we study in this paper is that the number K of agents always allowed to communicate is fixed. We can incorporate a dynamically changing K as part of the state, making the model and cost function more complex. Another limitation is the restriction to positional policies, which allows us to formulate the problem via occupancy measures. In the future we will consider extensions with bounded memory communication policies. Another challenge is the scalability, in particular with growing number of agents, which we plan to address by developing methods that iteratively improve the policies for subsets of agents. Additionally, we assume that the model, including public information is given. While in many cases identifying public information is natural (regions, fixed capabilities), exploring relations to agents' observations and approaches to deriving such information is an interesting direction.

Richer communication models. The focus of our work is to establish a rigorous theoretical foundation and provide novel insights and methodology. Our main aim is to provide the necessary basis for further theoretical exploration and practical applications. Moving forward, we plan to study extensions with richer communication restrictions (such as dynamic changes in communication availability) and explore ways to make the approach robust to implementation aspects such as delayed or noisy communication.

Identifying public information. The granularity of the public information affects the number of decision variables (for the communication policy) and hence the performance of policy synthesis. More (i.e., finer) public information leads to higher computation times. The choice of public information depends on the application and available communication bandwidth. In many cases, this is natural, such as coarser geographic regions or agents' capabilities. Developing techniques for identifying public information is one interesting direction for future work.