Managing Communication Costs under Temporal Uncertainty

1 Introduction

In multi-agent temporal plans, individual agents are uncertain about the behavior of other agents and must communicate to resolve that ambiguity. While these agents might have the capability to promptly deliver updates, there may be reasons why delivering immediate updates is expensive. For example, an autonomous underwater vehicle may have the equipment on-board to immediately transfer information to any other agent, but sending it may use precious battery power needed for the rest of its mission. It may make sense to use a slower and less expensive means of communicating about its actions or to omit relaying information altogether.

In this paper, we consider the problem of how to construct a minimum-cost communication protocol that still guarantees the feasibility of the original plan. This protocol is chosen subject to a supplied cost function which characterizes how expensive it is to communicate at certain moments in time. To verify whether any particular communication protocol is feasible, we can evaluate the protocol in the context of a temporal network using delay controllability [Bhargava et al., 2018], but there does not yet exist an efficient way to generate a protocol with low cost. Our paper focuses on this problem and offers two main contributions.

First, we demonstrate how to efficiently prune the available search space by providing an algorithm for deriving delay controllability conflicts. We augment existing delay controllability detection algorithms to output a conflict whenever a temporal plan is uncontrollable due to overly delayed communication. Adding this capability is essential, as it makes our search over an otherwise continuous and unbounded space tractable through the use of conflict-directed search [Williams and Ragno, 2007]. Our work on delay controllability conflict extraction matches the best-known O(n3 ) runtime of dynamic controllability conflict extraction techniques [Bhargava et al., 2017].

Second, we explore three different variants of conflictdirected search, two sub-optimal and one optimal, analyzing their performance and guarantees. We show that for certain networks the sub-optimal algorithms can provide at best a polynomial approximation of the true optimal cost, but that in practice they provide a reasonable approximation while executing much faster than optimal search.

It is also possible to interpret this problem as a temporal plan relaxation problem where delays associated with observation of uncertain events undergo relaxation. Under such a view, it is natural to ask whether it is possible to combine delay relaxation with temporal constraint relaxation techniques [Fang et al., 2014; Yu et al., 2014; Cui et al., 2015]. While we believe it is straightforward to unify the two concepts and their corresponding algorithms, such work is outside the scope of this paper.

2 Background

Simple Temporal Networks with Uncertainty (STNU) provide a way to reason about events that are outside an agent's control through the encoding of uncertainty [Vidal and Fargier, 1999]. In STNUs, events whose times can be assigned by the acting agent are called activated timepoints and events whose time values cannot be assigned are called received timepoints. Temporal constraints restrict the amount of time that can elapse between two events (e.g. event Amust happen no more than 20 minutes after event B) and are also split into those that must be satisfied by the acting agent, free constraints, and those that are guaranteed to be satisfied by some assignment of value to a received timepoint, contingent

Edge Generation Rules

constraints. All contingent constraints relate some activated timepoint to some received timepoint that follows it, and there is exactly one contingent constraint per received timepoint.

To determine whether there exists a guarantee that we can satisfy all constraints of an STNU, we examine its controllability. In this paper we focus in particular on delay controllability [Bhargava et al., 2018]. Delay controllability considers whether a just-in-time assignment of values to timepoints exists if for every received timepoint xe, the agent learns about the true time of the received timepoint after γ(xe) additional time has passed, where γ is the associated delay function. Delay controllability of an STNU can be computed efficiently in worst-case O(n3 ) time [Bhargava et al., 2018]. Delay controllability allows us to model disjointed communication that is often representative of multi-agent plan execution; if an external agent is delayed in communicating the results of some action, then for that particular action we assign γ(xe) = t.

When analyzing STNUs and their controllability, we often find it easier to consider their labeled distance graph representation [Morris, 2006; 2014]. Each timepoint of the original STNU corresponds to a node in the graph, and for each temporal constraint of the form l ≤ xB - xA ≤ u (or A [l,u] --→ B), we add two edges, A u-→ B and B -l -→ A. For each contingent link of the form A [l,u] ==⇒ C, we also add two additional labeled edges of the form A c:l -→ C and C C:-u ---→ A. These labeled edges represent conditional constraints; the lower-case labeled constraint applies when A =⇒ C takes on its lowest value and the upper-case labeled constraint applies when A =⇒ C takes on its largest value.

By inferring additional constraints using these edges, it is possible to assess whether an STNU is delay controllable with respect to a delay function γ (see rules reproduced from [Bhargava et al., 2018] in Table 1).

Using these rules, assessing delay controllability reduces to finding a semi-reducible negative cycle in the STNU's labeled distance graph. A semi-reducible negative cycle is a negative cycle that, after applying a series of reductions, has no lower-case edges. Finding a semi-reducible negative cycle serves as a certificate that the STNU is not delay control- Input: Labeled distance graph, G = 〈V, E〉; delay function γ

Output: Whether the STNU derived from the distance graph is delay controllable and if not, the edges embodying the conflict

Initialization:

• 1 negNodes ← the set of all vertices with incoming negative edges;
• 2 novel ← []; list of newly added edges;

3 preds ← {}; mapping of function call to predecessors; DELAYCONTROLLABLE?:

• 4 for v ∈ negNodes do

5

6

cycleFree?, edges ←DELAYDIJKSTRA(G, γ, v,

preds, novel, [v], negNodes);

if !cycleFree? then

• 7 return false, EXTRACTCONFLICTS(edges, novel, preds)
• 8 return true, ∅

Algorithm 1: Delay Controllability algorithm that reports conflicts

lable with respect to a particular delay function γ. Efficiently finding and extracting these semi-reducible negative cycles will be an important building block as we consider how to find minimum-cost communication strategies that still let us achieve our goals.

2.1 Modeling Communication Costs

We now define the communication cost minimization problem. For a given STNU, S, we wish to provide a delay function γ that minimizes the total communication cost C(γ) subject to the constraint that S is delay controllable with respect to γ. We assume that the cost function C is component-wise monotonically decreasing. That is to say, given two delay functions γ1 and γ2, such that for all received timepoints xe, γ1(xe) ≤ γ2(xe), we have that C(γ1) ≥ C(γ2).

This approach matches our intuitions for how to assign costs to communication patterns; we would never pay more to learn about an event at a later time. From a delay controllability perspective, we know that decreasing the communication delay for any given timepoint preserves controllability. Therefore, if there were a shorter delay with lower cost, we would always prefer to use that shorter delay.

2.2 Modeling Uncertain Communication and Risk

Our choice of allowable cost functions gives us significant leeway in modeling problems. Of particular note is the ability to model uncertainty in communication and to determine whether the system is controllable with some probability. This mirrors previous work that assesses the controllability of over-constrained temporal problems subject to some risk bound [Wang and Williams, 2015; Yu et al., 2015].

Imagine that instead of picking an exact delay when communication happens, an agent provides a probability distribution over when the communication will happen. To get a controllability guarantee, it suffices to ask whether the model STNU is controllable when every communication event happens at the maximum of the allowable range. However, this approach puts undue importance on the tails of these distributions. Instead a better question to ask is whether we can get some probabilistic guarantee of success (e.g. 98% of the time we can satisfy all constraints given this probability distribution).

Using our cost function framework, it is relatively straightforward to model this kind of problem. If we let d be a function mapping received timepoints to proposed bounds on their delay, we can use a cost function C(γ) = 1 -

then our probability of success then becomes 1 - C(γ).

It is worth noting that this approach does not assume independence between timepoints. So long as there is a function that faithfully represents the distribution, we can determine whether our problem satisfies the provided risk bounds.

3 Conflict Extraction

Searching for an optimal-cost communication protocol can be expensive since the search space is continuous and unbounded. Rather than using uninformed search, we can learn how to fix low-cost communication strategies that are uncontrollable to guide our search towards an optimal result. To do so, we rely on conflicts, which serve as certificates explaining why our original network is uncontrollable.

3.1 Finding Conflicts

In the case of delay controllability, we know that the presence of a semi-reducible cycle in our STNU is such a certificate, and we present a way to extract those conflicts and a technique for trying to resolve them. Our conflict-extraction algorithm builds on top of the original delay controllability algorithm [Bhargava et al., 2018] through the maintenance of some additional state.

The original delay controllability algorithm (Algorithm 1) works by invoking a variant of Dijkstra's algorithm from each negative weight edge. The calls to Dijkstra's algorithm are responsible for finding the shortest semi-reducible paths from each node to all others in the graph. The subroutine is recursively invoked any time another negative edge is found, and when an infinite recursion is detected, we know that we have found a cycle composed of several semi-reducible negative paths. More detail on the correctness of the algorithm can be found in [Bhargava et al., 2018].

To efficiently extract delay controllability conflicts, we augment this algorithm to have it return the set of edges from the original graph composing the detected conflict. Lines 1924 of Algorithm 2 are where we assemble the edges that compose the semi-reducible negative cycle. Whenever a recursive call to DELAYDIJKSTRA returns false, we know that at some point in the call stack, we discovered a semi-reducible negative cycle. However, the entire chain of edges is not necessarily part of the cycle. We use the third return value of DELAYDIJKSTRA to specify one node that is known to be part of the cycle. At line 23, we augment the list of edges that compose the negative cycle, and at line 24, we signal that we have fully specified a semi-reducible negative cycle because we have returned to a node we have already visited.

Input: Labeled distance graph G = 〈V, E〉, delay function γ, start node s, list of predecessor edges preds, list of new edges, callStack, and negNodes

Output: Whether the current walk is cycle-free, and the edges composing a semi-reducible negative cycle

• Initialization: 1 Q←PriorityQueue(); 2 labelDist ← []; shortest distances for labeled path; 3 unlabDist ← []; shortest distances for unlabeled path; 4 labelDist[s] ← 〈0, ∅〉; 5 unlabDist[s] ← 〈0, ∅〉; 6 for e ∈ s.incomingEdges() if e.weight < 0 and !e.lowerCase() do 7 Q.add(〈e.from, e.label〉, e.weight); 8 (e.label == ∅ ? unlabDist : labelDist)[e.from] ← 〈e.weight, e〉

DelayDijkstra:

9 if s ∈ callStack[1 : end] then 10 return false, ∅, s; 11 preds[s] ← 〈labelDist, unlabelDist〉; 12 while Q.size() > 0 do 13 v, label, weight ← Q.pop(); 14 if weight ≥ 0 then 15 G.add(〈v, s, weight〉); 16 novel.add(〈v, s, weight〉); 17 continue; 18 if v ∈ negNodes then 19 newStack ← [v].concat(callStack); 20 result, edges, end ← DELAYDIJKSTRA(G, γ, v, preds, novel, newStack, negNodes); 21 if !result then 22 if end ̸= ∅ then 23 edges.add(EXTRACTEDGEPATH(s, v, labelDist, unlabelDist)); 24 end ← (end == s) ? ∅ : end; 25 return false, edges, end; 26 for e ∈ v.incomingEdges() where e.weight ≥ 0 and (!e.isLowerCase() or e.label ̸= label) do 27 w ← e.weight + weight; 28 l ← (label ̸= ∅ and w > -γ(label) ? ∅ : label; 29 dist ← l ̸= ∅ ? labelDist : unlabDist; 30 if Q.addOrDecKey(〈e.from, l〉, w) then 31 dist[e.f rom] ← 〈w, e〉; 32 lower ← s.incomingLowerEdge(); 33 if lower ̸= null and e.weight < γ(lower.label) and Q.addOrDecKey(〈lower.f rom, l〉, w + lower.weight) then 34 dist[lower.f rom] ← 〈w + lower.weight, e〉; 35 negNodes.remove(s); 36 return true, ∅, ∅;

The introduction of additional processing to extract conflicts does not damage the algorithm's O(n3 ) runtime, as maintaining the additional data structures only incurs a constant overhead. Each call to EXTRACTEDGEPATH adds at most n edges to our list, and EXTRACTEDGEPATH is called at most once per call to DELAYDIJKSTRA. Because DELAYDIJKSTRA is called at most once per node, it adds an additional overhead of O(n2 ), which is dominated by the normal runtime of the algorithm.

Finally, the call to EXTRACTCONFLICTS in line 7 of Algorithm 1 takes the list of edges composing the cycle and replaces any newly added edges with the original edges that were used to derive them. The resulting output is our conflict.

3.2 Resolving Conflicts

Now that we have a way of extracting conflicts when our STNU is uncontrollable, we need a way to resolve them. Given a semi-reducible negative cycle, there are two ways to eliminate it: make the cycle non-negative or make it nonsemi-reducible. Since our communication protocol has no impact on the length of edges in the STNU's labeled distance graph representation, modifying our communication protocol will not affect the weight of the cycle. As a result, we must instead focus our attention on how to modify γ to eliminate semi-reducibility.

Only two of the reduction rules involve γ: the lower-case reduction rule and the cross-case reduction rule, and we explain how to change γ to resolve delay controllability conflicts and how this guarantees that iterative resolutions will eventually lead us to a valid solution.

Theorem 1. If an STNU is controllable when γ = 0 (or in other words, is dynamically controllable), then if the STNU has a controllability conflict for any particular choice of γ, we can always adjust γ to eliminate a lower-case or crosscase reduction.

Proof. A semi-reducible negative cycle is one where we can apply edge reductions to eliminate lower-case edges. In particular, the lower-case and cross-case reduction rules are the rules directly responsible for eliminating those edges.

For every lower-case edge from our conflict's semireducible negative cycle, we use the following approach for invalidating the reduction. From a lower-case edge with label b, we find the shortest subpath of the cycle that immediately follows the lower-case edge such that its total weight is less than γ(B). We know such a subpath exists because all lowercase edges have non-negative weight, the total weight of the cycle is negative, and γ(B) ≥ 0. If the weight of the subpath is non-negative, we adjust our γ(B) to be equal to its weight.

If we cannot adjust any value of γ because all of the successive subpaths are negative, then we have a contradiction. This same semi-reducible negative cycle would still be present when γ = 0, and the original STNU would not be dynamically controllable.

4 Minimum-Cost Communication

With an efficient way to extract delay controllability conflicts, we can now focus on identifying low-cost and ultimately minimum-cost values of γ which yield delay controllable networks. In this section, we present three solutions that are based on a form of conflict-directed search. The first two have no optimality guarantees but are fast in practice, and the

Input: Labeled distance graph, G = 〈V, E〉 for STNU;

Output: A valid communication protocol γ or ∅ if one does not exist;

GREEDYCOMMCOST:

• 1 if !DELAYCONTROLLABLE?(G, γ( ) = 0) then
• 2 return ∅;
• 3 candidate ← γ( ) =∞;
• 4 controllable, conflict ←DELAYCONTROLLABLE?(G, candidate);
• 5 while !controllable do
• 6 candidate ←
• candidate.pickResolution(conf lict);
• 7 controllable, conf lict ←

DELAYCONTROLLABLE?(G, candidate);

• 8 return candidate;

Algorithm 3: Algorithm that performs different variants of greedy search to find a communication protocol for an input STNU that is delay controllable.

third is a conflict-directed best-first search that is guaranteed to yield an optimal value of γ.

4.1 Conflict-Directed Search

Our initial approach at finding a feasible communication protocol (Algorithm 3) uses conflicts to iteratively refine its choice of delay function γ. Before we proceed with a potentially costly search process, we first check at line 1 to see whether the original STNU is dynamically controllable (or whether it is delay controllable with respect to γ = 0). Since decreasing observation delays always preserves controllability, we know that if the STNU is not dynamically controllable, we have no chance of finding a suitable delay function and can safely skip the search process.

Once we have a guarantee that there does exist some value of γ which makes the STNU delay controllable, we can begin our search. Each conflict returned from the delay controllability check (lines 4, 7) represents a disjunction of modifications we could make to our delay function to eliminate this particular conflict.

Our first two approaches, blind search and lowest-costresolution search (LCRS) employ different conflict resolution strategies to find an approach that works and are represented by different implementations of the pickResolution function at line 6. Rather than keeping track of all possible branches, we choose a single disjunct to resolve and continue checking for delay controllability. In the case of blind search, we nondeterministically commit to any of the possible conflict resolutions, and in the case of LCRS, we commit to the conflict resolution with lowest possible cost. In expectation, blind search is quicker to pick a conflict resolution, but LCRS may find solutions that are overall lower in cost. While neither approach is optimal, both approaches are guaranteed to eventually find a satisfying delay function γ that yields a controllable STNU since they will eventually resolve all conflicts.

4.2 Conflict-Directed Best-First Search

While blind search and LCRS are appealingly simple, that they are not guaranteed to be optimal is cause for concern. We are unable to provide guarantees that our search procedures are within a constant factor approximation of optimal, and in extreme instances, these search processes can yield results that are polynomially worse than optimal.

Theorem 2. Blind search and LCRS are not guaranteed to yield results within a constant factor of optimal.

Proof. Consider the STNU in Figure 1, which we call a k-contrived STNU, and imagine that we want to find a minimum-cost delay function γ making it controllable. For simplicity, assume that our cost function is C(γ) = ∑xe 1 1+γ(xe) . When called on this STNU, DELAYCONTROL-

LABLE? identifies a semi-reducible negative cycle that includes A =⇒ B and Ci =⇒ Di for all 0 ≤ i < k. The corresponding resolution to that conflict requires that either γ(B) = 0 or for some 0 ≤ i < k, γ(Di) = 1.

With a blind approach, we pick random disjuncts to satisfy until the STNU is controllable. However, each choice to relax γ(Di) makes no overall progress towards the controllability of the STNU. Only when γ(B) = 0 does the STNU become controllable. In expectation, k2 relaxations happen before blind search relaxes γ(B). Since each relaxation of γ(Di) to 1 incurs a cost of 12 and relaxing γ(B) to 0 incurs a cost of 1, in expectation blind search incurs a cost of 1 + k4 .

With LCRS, the results are even worse. LCRS always elects to resolve the conflict by letting some γ(Di) = 1 since this incurs a cost of 12 whereas letting γ(B) = 0 incurs a cost of 1. As such, LCRS updates γ(Di) for all k such contingent links before updating γ(B), meaning it incurs a cost of 1 + k2 , whereas the optimal approach has a cost of just 1.

Input: Labeled distance graph, G = 〈V, E〉 for STNU, and a

cost function C;

Output: A communication protocol γ that is of minimal cost or ∅ if one does not exist;

Initialization:

1 queue ← [] // queue of candidate γ functions; MINCOMMCOST:

• 2 if !DELAYCONTROLLABLE?(G, γ( ) = 0) then
• 3 return ∅;
• 4 queue.append(γ( ) =∞);
• 5 γ ← queue.pop();
• 6 controllable, conflict ←DELAYCONTROLLABLE?(G, γ);
• 7 while !controllable do
• 8 queue.add(γ.allResolvedConf licts(conf lict));
• 9 queue.sortBy(C);
• 10 γ ← queue.pop();

11

controllable, conf lict ←

DELAYCONTROLLABLE?(G, γ);

12 return γ;

Algorithm 4: Algorithm that computes minimum-cost communication protocol for an STNU.

These results motivate our interest in developing an optimal algorithm.

Our optimal algorithm for finding a minimal communication cost (Algorithm 4) is a form of conflict-directed bestfirst search (CDBFS) [Williams and Ragno, 2007] and works as follows. Like with the greedy algorithm, we immediately check if the STNU is controllable with respect to γ = 0 or whether it is dynamically controllable (lines 2-3).

Once we know that a solution can be found, we now have to find the lowest-cost solution. Since we know that our cost function C is component-wise monotonically decreasing, we start with the lowest cost communication pattern possible, γ =∞, and add it to our queue.

Every time we try a communication protocol that is too limiting and get back a conflict, we use the conflict to generate a set of delay functions to try later. For the value of γ we last checked, we derive modifications that each satisfy one of the provided disjuncts. We always choose the lowest cost value that satisfies the disjunct, which occurs when the delay for a received timepoint is exactly equal to the conflict's upper bound. By Theorem 1, we know that we will eventually reach a solution and because we are using best-first search, we know it will be optimal.

5 Experimental Results

The search algorithms we have presented differ in key ways. Blind search and LCRS have much lower overhead but have no guarantees of optimality. In contrast, CDBFS is guaranteed to output an optimal communication protocol but can be quite slow in practice. In this section, we present our empirical analysis as a way to better characterize exactly how different these approaches are and when it might be preferable to use one over the other. All tests were run on a machine with an Intel i7 processor and 39GB of RAM.

We start by examining the performance on k-contrived STNUs. We performed 50 trials each with parameters k = 10, 20, 30, 40, 50, and for all experiments, we assumed a cost function of C(γ) = ∑xe 1 1+γ(xe) . As expected, LCRS always

outputted a solution with cost 1 + k2 , blind search outputted a cost that converged in expectation to 1 + k4 , and CDBFS always outputted a unit cost solution.

As we scale problem size, the difference between the suboptimal approaches and CDBFS starts to grow (Figure 2). For each problem size, CDBFS has a significantly slower runtime than the suboptimal searches (p << 0.01) with no significant difference found between blind search and LCRS.

While there is a clear trade-off between the approaches, the data we have presented so far is for one specific type of graph. To validate that these trends hold more generally, we ran our experiments for randomly generated STNUs as well. Our random STNUs were composed of k independent contingent links which each had a lower bound of 0 and an integer upper bound that was uniformly chosen between 1 and 4. For each pair of endpoints between distinct contingent links, we added a requirement link between the two with probability 1 4k . Each requirement link also had a lower bound of 0 and an integer upper bound chosen uniformly between 1 and 4. For our analysis, we ensured that our 50 trials were selected from the set of random STNUs that were dynamically controllable but not delay controllable. In instances where the STNU is either not dynamically controllable or is already delay controllable, the algorithms behave identically.

Our experiments demonstrate that the differences we saw in runtime between the optimal and suboptimal approaches persist (Figure 3). At problem sizes of k = 30, 40, 50, CDBFS is significantly slower than both suboptimal searches (p < 0.05). We also start to see a difference between blind search and LCRS. At k = 30, 40, 50, LCRS is also significantly faster than blind search (p << 0.01).

When we turn our attention to cost, however, we see that on random graphs, we see a strong improvement in our results (Figure 4). Across all problem sizes, we see that while blind search is on average within 35% of optimal, remarkably, LCRS is on average within 1.5% of optimal. Given the massive difference in speed and the close approximation of optimal results, this provides strong support for the use of LCRS in low-cost communication protocol generation.

Figure 4: The quality of the solutions when run on random graphs. Quality is given by the optimal cost divided by the cost of the returned solution. A score of 1.0 represents the optimal solution.

6 Conclusion

In this paper, we introduced the problem of producing a low-cost communication protocol that makes a temporal plan feasible in the face of uncontrollable actions. To produce such a protocol, we provided an efficient means of extracting delay controllability conflicts and used those conflicts as a means of guiding our search through a continuous state space. The three algorithms we presented, blind search, LCRS, and CDBFS, have very different properties with the first two being significantly faster with the last one guaranteeing optimality. While we provide theoretical results demonstrating that the suboptimal searches can be polynomially worse than CDBFS, in practice we expect that LCRS provides highly competitive results with significant improvements in speed.

Our current efforts demonstrate an effective way to plan communication, but our approach makes the strong assumption that communication is reliable and that plans are immutable. In practice, however, communication is likely to have some probability success and as execution happens, plans can be changed to account for unexpected events. These areas of focus are both important when considering communication in the context of planning and are promising subjects for future areas of research.

Acknowledgments

This research was funded in part by the Toyota Research Institute under grant number LP-C000765-SR.