Centralized and Distributed Approaches for Restoring the Weak Controllability of Multi-Agent Interdependent STNUs

1 Introduction and RelatedWork

In multi-agent temporal planning problems, agents must first collaboratively construct individual plans through task allocation and planning techniques, possibly involving negotiation, and then check and coordinate the temporal executability of their plans. In this paper, we focus exclusively on the latter stage and on the specific case where the task owner controls task durations. At the same time, other compliant agents may depend on those durations and may learn them only just before or during execution. Let us consider an example from the healthcare domain: the radiology department waits for a patient's surgery, performed by the emergency department, to finish. The duration of the surgery is therefore uncertain for the former, since it is set by the latter and may be communicated only in accordance with the surgery department's policy. Such compliant agents must check the executability of their plans, but may also try to repair a non-executable plan by negotiating shared constraints.

Simple Temporal Networks (STNs) [Dechter et al., 1991] are a well-known framework for managing temporal duration and checking temporal consistency of plans. They have been extended to STNs with Uncertainty (STNU) [Vidal and Fargier, 1999] to represent uncertain (contingent) durations, redefining consistency as controllability: an STNU is controllable if a strategy exists for executing the plan, whatever the values taken by the contingent durations. Three levels of controllability exist, depending on when the contingents' durations will be known: just before execution (Weak), during execution (Dynamic), or never (Strong).

Extensions to multi-agent settings were first addressed in Multi-agent STNU (MaSTNU [Casanova et al., 2016]) or Disjunctive TNU [Bhargava and Williams, 2019] (MaDTNU) models that consider common exogenous uncertainty, i.e., contingent constraints still come from Nature and affect all agents equally. Some approaches propose decoupling algorithms for Dynamic Controllability that ensure each agent is controllable [Casanova et al., 2016] [Zhang and Williams, 2021]. Another centralized approach with common exogenous contingent constraints introduces the concept of a contract to represent interdependent activities across agents [Lubas and Eder, 2023]. These contracts are similar to classical inter-agent constraints and are compiled into a single STNU to verify Dynamic Controllability. Overall, these models enforce central controllability checking, which is wellsuited to multi-agent planning problems in which a common task is divided among different participants.

More recently, the Multi-Agent Interdependent STNUs (MISTNU) model introduced a semantically distinct notion of contract, corresponding to a shared constraint being controllable for one agent but contingent for others [Sumic et al., 2024b]. It distinguishes between exogenous and interagent contingencies, preserving privacy, and defining clear execution and observation semantics at various controllability levels. That model fits semi-decentralized multi-agent planning, where each agent plans its own course of action while coordinating through mutual commitments. The authors define the distributed controllability-checking problem for MISTNUs and propose a centralized repair method to restore controllability when needed, by negotiating contract durations using Satisfiability Modulo Theories (SMT) [Barrett and Tinelli, 2018].

Meanwhile, new algorithms have emerged for detecting the causes of Weak and Dynamic uncontrollability of STNUs in the form of inconsistent negative cycles [Sumic and Vidal, 2024; Hunsberger and Posenato, 2022]. In this paper, we show that such "informed" algorithms can improve the current "blind" centralized repair by specifically targeting those cycles. Our first contribution is to translate negative cycles into linear constraints, focusing on the Weak Controllability repair problem, and to develop a centralized linearprogramming approach. Experiments show that, although the number of negative cycles is theoretically exponential, they can be repaired efficiently.

Our second contribution proposes a distributed approach to the same problem, still leveraging the linear constraints that encode the negative cycles. The problem is addressed from a Distributed Constraint Reasoning perspective [Yokoo et al., 1998] and modeled as a Distributed Constraint Optimization Problem [Modi et al., 2005] that can be solved by any distributed method. We notably assess the performance of optimal algorithms ADOPT, AFB, DPOP, and SyncBB. In such approaches, agents implement a coordination protocol to reach an agreement over the contract bounds.

The paper provides the necessary background on STNUs and MISTNUs in Section 2, then presents our contributions in Sections 3 to 4, assessing them through comprehensive experiments in Section 5, and concludes with a few prospects.

2 Background

2.1 Single Agent Temporal Models

A Simple Temporal Network (STN) is a tuple ⟨V,E⟩, where V is a set of real-value variables called timepoints {v1, . . . , vn}, and E is a set of temporal constraints between timepoints called requirements [Dechter et al., 1991]. Specifically, each requirement ek ∈ E is of the form vj -vi ∈ [l, u], with vi, vj ∈ V, l ∈ R ∪ {-∞}, and u ∈ R ∪ {+∞}; l and u represent the minimal and maximal possible temporal distance between vi and vj. A requirement is represented as an edge vi [l, u] vj. A reference timepoint vz is generally included in V as a fixed temporal anchor assumed to be the first executed timepoint of the network, i.e., vz will take a value such that each implicit constraint vz ≤ vi for each vi ∈ V is satisfied.

An STN is satisfiable if a timepoint assignment (schedule) exists that satisfies all the constraints. We say that a controller executes an STN when it schedules its timepoints.

An STN with Uncertainty (STNU) is an extension of STNs in which one distinguishes a subset of constraints whose values (duration) are decided by external entities (i.e., Nature) and the controller can only observe them [Vidal and Fargier, 1999]. An STNU X = ⟨V,E,C⟩ is a tuple where V is now divided into controllable (Vc) and uncontrollable (Vu) timepoints. C is a set of (uncontrollable) contingent links ck each of the form vj - vi ∈ [l, u], where vi ∈ Vc, vj ∈ Vu, and

0 < l ≤ u. The value (duration) ωk = vj - vi is set by an external entity before or during the execution. Once vi is executed, the value of vj is vi + ωk. Any ck is depicted as vi [l, u] vj . A schedule for an STNU is a mapping δ : V → R from timepoints to real values.

Definition 1 (Situation, Projection and Solution). Given an STNU X = ⟨V,E,C⟩, the situations of X are the set of tuples Ω defined as the Cartesian product of contingent domains: Ω = ×ck∈C [lk, uk]. Each situation ω = {ω1, . . . , ωn} ∈ Ω represents one possible complete set of values for the durations of the contingent links of X.

A projection X ω = (V, E ∪ C ω ) of X is an STN, where C ω replaces each contingent link ck with the rigid requirement induced by ωk. A solution of X ω is a schedule δω satisfying all the constraints.

Intuitively, a projection replaces each contingent link with a rigid requirement, i.e., a constraint reduced to a singleton.

In STNUs, consistency needs to be redefined: a network is now said to be controllable if there exists a schedule that satisfies all requirement constraints in any possible projection.

Three levels of controllability exist: Strong Controllability (SC) assumes that a single common schedule δ satisfies all constraints in all situations, which is relevant when the durations of external events cannot be observed (conformant planning). Weak Controllability (WC) assumes there is one consistent schedule for each situation, which is relevant when all contingent durations will be known just before execution (oracle). Dynamic Controllability (DC) assumes the schedule values assignment depends on past observations only, regardless of the contingent durations still to be observed. In this paper, we only recall the formal definition of WC, which is our focus.

Definition 2 (Decision and Observation). ∀vi ∈ Vc, dec(vi) is the instant at which δ(vi) is decided by the controller. ∀ωk ∈ C, obs(ωk) is the instant at which ωk is observed by the controller.

Definition 3 (Weak Controllability (WC)). An STNU X is weakly controllable iff ∀ω ∈ Ω, ∃δω, which is a solution of Xω. Execution semantics: ∀ωk ∈ ω, obs(ωk) = vz, and the decision policy is free: ∀vi ∈ Vc, dec(vi) ≤ vi.

DC and WC checking rely on algorithms to check if there are negative cycles in the distance graph of STNUs [Hunsberger and Posenato, 2022; Sumic et al., 2024a]. The distance graph of an STNU is a graph XD = ⟨V, E⟩ where a requirement constraint in E is represented through two edges vi u vj and vj -l vi in E. A contingent link in C is represented through four edges: two as above, a lower-case (LC) edge vi j:l vj, and an upper-case (UC) edge vj J:-u vi. The LC vi j:l vj (resp. UC vj J:-u vi ) represents the uncontrollable possibility that the duration vj - vi might take its minimum value l (resp. maximum value u).

Definition 4 (Inconsistent Cycle). Given a distance graph XD, a cycle ϱ = (vi, αij , vj , . . . , vk, αkm, vm) is a sequence of timepoints and edge values s.t vi ≡ vm and where each αkk′ is the (unlabeled or LC or UC) value of the considered edge connecting vk to vk′ . We denote by α(ϱ) the length of a cycle, i.e., the sum of the values of the edges composing the path, ignoring possible labels. A cycle ϱ is negative/ inconsistent iff α(ϱ) < 0. We denote by M = {ϱ1, . . . , ϱn} the set of all inconsistent cycles of an STNU.

2.2 Multi-Agent Interdependent STNU

STNUs have been extended to a multi-agent context, considering that the duration of a link that is controllable for one agent may be observed as contingent by other agents [Sumic et al., 2024b]. Such shared and duplicated constraints are controllable for the agent that makes the decision, but are contingent for an agent that depends on such decisions. To express such semantics, the authors first define a contract p as a label that is associated with a range of durations that can be assigned to distinct binary constraints in different STNUs.

Definition 5 (cSTNU). A Contracting STNU (cSTNU) is an STNU extended with links being labeled by contracts. A cSTNU is a tuple S = ⟨V, R, W, E, C, O⟩ such that:

• V is defined as in STNUs.
• R and W are sets of owned (W) and observed (R) contracts, such that R ∩ W = ∅.
• E is the set of local requirement constraints, which are not related to contracts.
• C is a set of labeled contingent links of the form vi p vj where p ∈ R, corresponding to the observed contracts.
• O is a set of owned contract links of the form either vi p vj or vi p vj, where p ∈W.

In other words, C is now related to observed contracts, which are necessarily contingent. While constraints corresponding to owned contracts are now in O, they will retain the same status, either as a requirement or a contingent link. At checking time, they will be considered as contingent since the interval of possible values is a commitment between a writer and the readers, that even the owner is not supposed to shrink while others check their controllability with respect to them: then requirements are in E and contingents in C∪O; while at execution time they may be considered as controllable so that the owner can modify the bounds or set an effective value: then requirements are in E ∪ O and contingents in C.

Although the model can still support exogenous nonrepairable contingent constraints, in this paper, we assume that all contracts have an owner, i.e., each constraint in C is issued by another agent that has the same contract in its own set O.

Alongside cSTNUs, they define a new multi-agent model called Multi-agent Interdependent STNU composed of a set of agents, each with its cSTNU, and a reification function B that, given a contract p, returns the range [lp, up] of possible durations for p. For any cSTNU S, we call reification of S the application of B to its contracts, replacing all labels with the interval delimited by B, i.e., [lp, up], returning an STNU.

Definition 6 (MISTNU). A MISTNU is a tuple G = ⟨A, Σ, B⟩ such that:

• A is a set of agents {a1, a2, . . . , an};
• Σ is a set of cSTNUs Sa = ⟨Va,Ra,Wa,Ea,Ca,Oa⟩, one for each a ∈ A, such that
• ∀a ∈ A, Pa = Ra ∪ Wa is the set of contracts of agent a, and vz ∈ Va is the mutual reference timepoint for the sake of synchronization.
• for every pair of agents a, b ∈ A, Wa ∩Wb = ∅
• B: P → R2 is the global reification function for all the contracts P = ⋃a∈A Pa.

Example 1. Consider a radiologist (agent a), a nurse (agent b), and a doctor (agent c). The radiologist performs an X-ray on the first patient, represented by contract p, whose duration is observed by the nurse and the doctor to be contingent: the nurse waits for the X-ray before escorting the patient, while the doctor can analyze the results only after its completion. The nurse then escorts the current patient and brings a second patient to the radiologist, represented by contract q, which is owned by the nurse but observed by the radiologist. Finally, contract r represents the second X-ray, along with the following dependencies involving the nurse and the radiologist. After this second X-ray, the radiologist must clean and inspect the equipment within the required time window. Figure 1 illustrates the corresponding MISTNU, including contract ranges, deadline constraints, and additional local constraints.

Although the model could be fully decentralized, the contract bounds are defined by B, which serves as a common, blackboard-like external and public structure [Botti et al., 1995], making MISTNU a semi-decentralized model in which only information about the shared contracts is public.

The MISTNU model is useful for assessing the controllability of each agent in a distributed manner, depending on when the contract duration is shared. We tackle the case of WC, where such communication happens before execution and has proven highly relevant in applications [Sumic and Vidal, 2024] when, e.g., some resource availability is not known in advance by an agent but will be set together with related task durations at the start of the day, which is, for instance, often met in healthcare services.

Execution semantics. In the WC setting, a situation is a complete assignment of durations to the contracts reified as contingent links. This assignment is fixed before execution and communicated to all agents at the initial reference timepoint vz. Thus, situations are not generated by agents' scheduling decisions: all agents react to the same global situation. The MISTNUWC condition, therefore, checks whether, for every possible global assignment of contract durations, each reified local STNU admits a feasible schedule.

Definition 7 (MISTNUWC). The Weak Controllability of a MISTNU G = ⟨A,Σ, B⟩ is defined as ∀Sa ∈ Σ, S G a is WC, where S G a is the reification of Sa to an STNU using B.

When the MISTNU is not controllable, i.e., at least one cSTNU is not controllable, the MISTNU may be repaired by shrinking the contracts' bounds as defined as follows for WC:

Definition 8 (Weak Repair). Given a MISTNU G = (A, Σ, B) such that, for some a ∈ A, S G a is not WC, theWeak Repair Problem consists in finding a new reification function B′ for a MISTNU G ′ = (A,Σ, B′ ) such that:

• ∀p ∈ P, if B(p) = [lp, up] and B′ (p) = [l′p , u′p ], then lp ≤ l′p ≤ u′p ≤ up.
• G ′ is WC, i.e., ∀a ∈ A, S G′ a is WC.

In [Sumic et al., 2024b], the authors used a standard exponential WC checking method [Vidal and Fargier, 1999] and, when it fails, proposed a centralized SMT-based repair algorithm that encodes all the projections of each agent network and searches for the minimal reduction of the contracts that satisfy these projections. The MISTNU in Figure 1 with function B is not WC, and we show that each agent STNU contains a negative cycle, as depicted in Figure 2. The function B′ in Figure 1 provides new bounds that make the MISTNU WC.

A recent work proves that checking WC of MISTNU is coNP-complete, while its (centralized) optimal repair problem has been determined to be in ΣP2 [Maris et al., 2025].

2.3 Distributed Constraint Optimization

The Distributed Constraint Reasoning (DCR) framework enables formal modeling of coordination and decision-making among multiple agents, each controlling variables, to collectively satisfy or optimize constraints defined over these variables. We are interested in the latter one, called Distributed Constraint Optimization Problems (DCOPs), to find optimal solutions, which is known to be NP-hard [Modi et al., 2005].

Definition 9 (DCOP [Modi et al., 2005]). A Distributed Constraint Optimization Problem (DCOP) is formally represented by a tuple ⟨A, X , D, F, µ⟩:

• A = {a1, . . . , a|A|} is a set of agents;
• X = {x1, . . . , xn} is a set of discrete variables;
• D = {d(x1), . . . , d(xn)} is a set of finite domains, such that variable xi takes values in d(xi) = {vi1 , . . . , vik };
• F = {f1, . . . , fm} is a set of soft constraints, where fi is a function that defines a cost ∈ R ∪ {∞} for each combination of values to the variables in its scope;
• µ: X →A is a function that assigns the control of each variable to an agent.

A solution to a DCOP is a complete assignment σ that minimizes a global objective function F(σ) that aggregates the individual costs fi's: σ∗ = argminσ F(σ). The sum is generally used as an aggregation function: σ∗ = argminσ ∑fi∈F fi.

In a DCOP algorithm, each agent assigns values to its variables and communicates with peers to achieve a complete assignment, assuming that messages between agents may be delayed but are never lost. DCOP models can capture hard constraints by using infinite costs.

3 CentralizedWeak Repair

In this section, we propose a centralized algorithm for the Weak Repair Problem that improves on the approach of [Sumic et al., 2024b]. The previous method encodes all projections of the agents' networks and searches for a repair using SMT. Here, instead, we first use an informed WCchecking algorithm [Sumic and Vidal, 2024], which returns the causes of non-controllability as inconsistent cycles. We then encode only those cycles as linear constraints and solve the resulting linear-programming problem. We assume that a central agent can read the public contract bounds and impose a new reification function.

3.1 Weak Repair Through Inconsistent Cycles

The STNU Weak Repair Problem can be solved by reducing the bounds of contingent links [Sumic et al., 2024a]. We prove that this can be obtained by considering only the contingent links present in inconsistent cycles of the non-WC network.

Theorem 1 (STNU inconsistent cycles repair). Let X = ⟨V, E, C⟩ be a non-WC STNU, and let M = {ϱ1, . . . , ϱn} be its set of inconsistent cycles involving contingent links. Repairing a non-WC STNU is equivalent to finding new contingent bounds (if any) for each cycle ϱk ∈ M such that ϱ′k with new contingent bounds becomes consistent without creating any new inconsistent cycle.

Proof. Let X = ⟨V,E,C⟩ be a non-WC STNU, and let M= {ϱ1, . . . , ϱn} be its set of inconsistent cycles. Since all relevant constraints must be satisfied in all possible situations, an inconsistent cycle indicates a situation in which the network is not executable. Shrinking contingent bounds removes possible situations and can only increase lower-bound contributions or decrease upper-bound contributions in the distance graph; hence, it cannot create new inconsistent cycles.

Thus, if all ϱk ∈ M are repaired, no inconsistent cycles remain. Hence, the newly formed STNU X ′ = ⟨V,E,C ′ ⟩, with C ′ = {i [l′ , u′ ] j | i [l, u] j ∈ C} and l ≤ l′ ≤ u′ ≤ u, satisfies Definition 3, since every projection X ′ω , with ω ∈ Ω′ , admits a solution δω [Sumic et al., 2024a; Hunsberger and Posenato, 2022].

Conversely, assume that even reducing contingent links to singletons, i.e., l′ = u′ , is not enough to remove an inconsistent cycle. Then at least one projection X ′ω , with ω ∈ Ω′ , does not satisfy Definition 3; hence, X ′ is not WC.

Following Theorem 1, we extend it for MISTNUs by repairing the inconsistent cycles of each non-WC cSTNU.

Corollary 1 (Weak repair through inconsistent cycles). Given a non-WC MISTNU G = ⟨A,Σ, B⟩, its Weak Repair Problem can be solved by considering the inconsistent cycles of all reified agent STNUs. More precisely, for every ϱk ∈ ⋃a∈A Ma, where Ma is the set of inconsistent cycles of S G a , one must find new contract bounds, if any, that make ϱk consistent as in Theorem 1.

3.2 A Linear Encoding of Inconsistent Cycles

In this section, we show how to "solve" a set of inconsistent cycles by solving a linear programming (LP) problem. First of all, we show how to encode an inconsistent cycle ϱ in the distance graph S G a of an agent a as a linear inequality to solve. Therefore, let us assume that ϱ = (vi, αij, vj, . . . , vk, αkm, vm) is an inconsistent cycle with length α(ϱ) = ∑ij αij , where value labels are discarded, and that it contains at least one edge whose labeled value αkk′ is equal to k′ :lp or K′ :-up, where lp/up is the current lower/ upper bound associated with a contract p.

For each contract lower/upper bound lp/up present in ϱ, we define a rational variable lp /up . Then, in ∑ij αij, we replace each αk,k′ = lp/up by the linear expression lp - lp/up - up and remove any other unlabeled value. Then, the summation becomes a linear expression of the introduced variable. We call such an expression Υϱ . More formally,

The inconsistent cycle is repaired by assigning values to the variables lp and up such that the linear inequality Υϱ ≥ |α(ϱ)| and the bounds lp ≤ lp ≤ up ≤ up are satisfied.

For example, the inconsistent cycle of agent a in Figure 2 is encoded as (lp - 5) + (lq - 10) + (lr - 10) ≥ 5, and a possible solution is lp = 10, lq = 10, and lr = 10.

Now, it is possible to define how to solve the inconsistent cycles of an STNU and, in general, of an MISTNU. Given any STNU S G a and the set of its inconsistent cycles Ma, to repair each inconsistent cycle ϱk ∈ Ma, it is sufficient to solve the linear programming problem defined by the set of linear constraints.

To solve the Weak Repair Problem of an MISTNU, we must encode all the agents' inconsistent cycles using a common set of variables for the contract bounds. We denote by Ψ the set of constraints associated with the contracts' variables, and by Υwc the set of encodings of all the inconsistent cycles. More formally,

Algorithm 1: cycles repair procedure

Input: A MISTNU G = ⟨A, Σ, B⟩

Output: B if G is WC, a new reification B′ if G is not WC

but repairable, ∅ otherwise.

all cycles = []

foreach cSTNU Sa ∈ Σ do

cycles = check WC(S G a ) all cycles = all cycles ∪ cycles

if all cycles == ∅ then return B

//G is WC

elseB′ = encode cycles(all cycles) //Use eq. (1) and solve it

by eq. (5)

if B′ == ∅ then return ∅

else return B′

//G is not reparable

Consequently, the Weak Repair Problem has a solution iff Υwc admits one. Among all possible solutions to the LP problem Υwc, we are interested in finding a solution that minimizes the modification of the current function B. More formally, we solve the Weak Repair Problem by solving the following minimization linear programming problem:

Our methodology is summarized in Algorithm 1. Given a MISTNU G, we extract all inconsistent cycles from each reified agent STNU S G a using the approach in [Sumic and Vidal, 2024]. If no inconsistent cycle is found, G is WC. Otherwise, each inconsistent cycle is encoded using Equation (1), and the resulting system is solved using Equation (5). If no solution exists, G is deemed non-repairable.

4 DistributedWeak Repair Solving

In this section, we map the Weak Repair Problem for MISTNUs to a DCOP, which we call WRP-DCOP. As shown in Section 3, inconsistent cycles can be expressed as linear constraints over contract bounds. In the distributed setting, each agent locally checks the WC of its reified STNU and, if it is not WC, shares only the contract-bound information needed to negotiate a repair. These shared bounds define the DCOP variables, while the linear encodings of the inconsistent cycles define the DCOP constraints. Soft constraints can then be added to minimize the sum of bound adjustments, as in Equation (5).

4.1 TheWeak Repair Problem as a DCOP

Given a non-WC MISTNU G = (A, Σ, B), we build the corresponding DCOP ⟨A,X,D,F, µ⟩ as follows. The DCOP agents are the MISTNU agents, i.e., A = A. For each contract p ∈ ⋃a∈A Pa with B(p) = [lp, up], we introduce two DCOP variables, lp and up , representing the repaired lower and upper bounds of p. Since DCOP variables have finite domains, we discretize the interval [lp, up] according to the application's temporal granularity. Thus, d(lp ) = d(up ) = {lp, . . . , up}. This discretization is exact whenever time values are represented as integers in the chosen time unit. Therefore, X = ⋃p∈⋃a∈A Pa {lp , up }, D = {d(x) | x ∈ X}.

Next, we determine F by adding a cost function to the set of linear constraints defined in the Weak Repair problem to use the objective function F(σ) introduced in Definition 9. We consider two types of hard constraints: those induced by inconsistent cycles, and those enforcing the consistency of the repaired bounds of each contract, i.e., lp ≤ up .

Hard constraints are modeled through infinite costs: each hard constraint has cost 0 when it is satisfied and cost +∞ otherwise. For example, the inconsistent cycle of agent a in Figure 2 induces the cost function f i cycle = 0 if (lp -5)+(lq - 10) + (lr - 10) ≥ 5, and f i cycle = +∞ otherwise. Similarly, for each contract p, we add a bound-consistency cost function f p bounds = 0 if lp ≤ up , and f p bounds = +∞ otherwise.

The mapping µ assigns both variables lp and up to the agent that owns contract p. Formally, if p ∈ Wa, then µ(lp ) = µ(up ) = a.

At this stage, WRP-DCOP models the satisfaction version of the Weak Repair, using only hard constraints. A DCOP solver searches for an assignment minimizing F(σ). In this satisfaction version, a solution with cost 0 satisfies all hard constraints and therefore corresponds to a valid repair. If every assignment has cost +∞, then at least one hard constraint is violated in every possible assignment, and no repair exists.

4.2 Minimizing Contract Reductions

To model a WRP-DCOP that minimizes bound reductions, as in Equation (5), we add soft unary cost functions. For each contract p, the cost associated with increasing the lower bound is lp -lp, while the cost associated with decreasing the upper bound is up-up . Thus, among all assignments satisfying the hard constraints, the solver selects one that minimizes the total bound adjustment. A finite-cost solution is a valid repair; if all assignments have cost +∞, no repair exists.

Example 2. In the following, we model the example of the Weak Repair Problem of Figure 1 using the inconsistent cycles of Figure 2 as a WRP-DCOP:

• A = {a, b, c};
• X = {lp , up , lq , uq , lr , ur };
• D = {d(x) | x ∈ X}, where d(li ) = d(ui ) = {li, . . . , ui} for each i ∈ {p, q, r};
• F = {f 1 cycle = 0 if (lp - 5) + (lq - 10) + (lr - 10) ≥ 5 else +∞, f 2 cycle = 0 if (10 - up ) + (15 - uq ) + (20 - ur ) ≥ 15 else +∞, f 3 cycle = 0 if (lp - 5) ≥ 1 else +∞, f p bounds = 0 if lp ≤ up else +∞, f q bounds = 0 if lq ≤ uq else +∞, f r bounds = 0 if lr ≤ ur else +∞, f lp reduc : (lp - lp), f up reduc : (up - up ), f lq reduc : (lq - lq), f uq reduc : (uq -uq ), f lr reduc : (lr - lr), f ur reduc : (ur -ur )};
• µ = {lp ↦→ a, up ↦→ a, lq ↦→ b, uq ↦→ b, lr ↦→ a, ur ↦→ a}.

Note that agent c controls no contract in this example and therefore owns no DCOP variable.

5 Experimental Evaluation

Here, we empirically evaluate the proposed centralized and distributed repair approaches. For the centralized approach, we compare our linear encoding with the previous SMT encoding of [Sumic et al., 2024b]. For the distributed approach, we evaluate both the satisfaction version of WRP-DCOP and the optimization version that minimizes the number of bound adjustments. The complexity of our methods depends on two components: the WC checking routine and the repair procedure. WC checking is theoretically exponential [Sumic and Vidal, 2024], and the number of inconsistent cycles returned by the checker may also be exponential. Accordingly, our experimental study has two objectives: (i) assess the practical cost of checking WC on MISTNUs, which requires checking each agent's reified STNU; and (ii) evaluate the scalability of the centralized and distributed repair methods despite the potentially exponential number of inconsistent cycles.

5.1 Environment and Benchmark

We conducted our experiments on a 20-core Intel ® Xeon ® CPU E5-2660 at 2.6 GHz, with 64 GB RAM, running Ubuntu 18. We implemented our centralized method using the pySMT framework [Gario and Micheli, 2015], with Z3 [De Moura and Bjørner, 2008] as the backend solver for linear real arithmetic. For the distributed approach, we used FRODO [L´eaut´e et al., 2009], a Java library providing complete DCOP algorithms.

The benchmark [Sumic et al., 2024b] consists of 350 nonWC but repairable MISTNUs. Each instance involves four agents, and all agent networks in the same instance have the same number of timepoints. The benchmark is organized into seven groups of 50 instances, with network sizes in (20, 30, 50, 80, 100, 150, 200) timepoints per agent network. For each size, the number of owned contracts per agent is fixed at 1-7. Since an activity duration is modeled as a constraint between two timepoints (start and end), a network of size 50 can represent a plan with around 20 activities plus additional deadlines.

5.2 CentralizedMethod Evaluation

Figure 3 reports the average execution time as a function of the network size. We separate the time required to identify inconsistent cycles, namely WC checking, from the time required to repair them using our linear encoding. The figure also reports the average execution time of the SMT repair algorithm of [Sumic et al., 2024b]. With a time limit of one hour, the SMT encoding repaired instances up to size 30, whereas our centralized method repaired instances up to size 100 and timed out on sizes 150 and 200.

Table 1 provides additional information on solved instances, including the average number of inconsistent cycles and their average arity. These results illustrate the exponential increase in the number of cycles requiring repair.

Overall, the centralized linear encoding outperforms the SMT encoding in efficiency and scalability. Although inconsistent cycles can be exponential in number, repairing one cycle often repairs others involving the same contracts. For instance, in Figure 2, fixing contract p to [10, 10] repairs the inconsistent cycles of agents a and c. Thus, WC checking is the main computational bottleneck and the primary target for scalability improvements.

5.3 Study of the Distributed Approach

We evaluate the distributed approach on the same benchmark instances used for the centralized evaluation, encoded as WRP-DCOP instances as described in Section 4. We consider four complete DCOP algorithms: SyncBB, a synchronous distributed branch-and-bound algorithm [Hirayama and Yokoo, 1997]; DPOP, a synchronous inference-based algorithm over a DFS pseudo-tree [Petcu and Faltings, 2005]; ADOPT, an asynchronous memory-bounded best-first search algorithm [Modi et al., 2005]; and AFB, an asynchronous search algorithm related to SyncBB [Gershman et al., 2006].

We first compare the four algorithms on the satisfaction version of WRP-DCOP, without optimization, to assess the feasibility of repair-based search. With a 5-minute limit per instance, Table 2 reports solved instances and average runtimes, with standard deviations shown after ±, over the 250 instances of sizes 20-100. SyncBB and AFB solve all instances; ADOPT solves fewer; and DPOP solves only 55/250, likely due to high-arity constraints.

Next, we evaluate AFB and SyncBB on the optimization version of WRP-DCOP, minimizing total bound adjustments. With a 1-hour limit per instance, Table 3 shows that AFB solves more instances and is faster than SyncBB, likely due to concurrent constraint checks. However, neither algorithm returns optimal solutions within the time limit for instances of sizes 80 and 100.

For instances where AFB and SyncBB did not return an optimal solution within the time limit, we compared the feasible solutions from the satisfaction experiment with the corresponding optimal costs computed by the centralized method. Solution quality is reported as 100 · C ⋆ /C, where C ⋆ is the optimal repair cost and C is the cost of the feasible solution; higher values are better. As shown in Table 3, both algorithms produced identical quality values, with particularly high-quality feasible repairs for instances of sizes 80 and 100.

Overall, the scalability of the distributed approach is mainly limited by the underlying DCOP algorithms when optimality is required. However, feasible, non-optimal repairs provide a practical trade-off: they can be obtained within a few seconds and achieve reasonably high solution quality. For sizes 80 and 100, feasible distributed repairs still reach 82%- 90% of the centralized optimum.

6 Conclusions

This paper addressed the Weak Repair Problem for non-WC MISTNUs through a cycle-based perspective. Starting from WC-checking algorithms that identify inconsistent cycles, we provided a linear encoding of those cycles and used it to derive two repair methods: a centralized linear-programming approach that computes optimal repairs, and a distributed formulation, WRP-DCOP, that preserves privacy while enabling inter-agent coordination.

The empirical results support the practical relevance of this framework. The centralized method is more efficient and scalable than the previous SMT encoding, repairing instances up to size 100 within the time limit (while SMT stops at size 30). In the distributed setting, complete DCOP solvers are effective for finding feasible repairs, and, when optimality is difficult to guarantee on larger instances, they still return solutions with good quality. Overall, these results indicate that repairing through inconsistent cycles is a promising alternative to blind repair.

The main limitation highlighted by our study is not repair itself, but WC checking, which remains the main computational bottleneck. Future work will therefore focus on: (i) tailored WRP-DCOP algorithms and better ordering heuristics; (ii) incomplete distributed methods that trade optimality for scalability; and (iii) extending the same cycle-based repair principle to Dynamic Controllability via iterative detect-andrepair schemes. Improving cycle-detection methods to return richer sets of relevant cycles appears particularly promising for scaling both centralized and distributed repair.