{'fraction_non_alphanumeric': 0.04118591538777491, 'fraction_numerical': 0.01448788320077667, 'mean_word_length': 3.955041628122109, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multiagent Simple Temporal Problem: The Arc-Consistency Approach

The Simple Temporal Problem (STP) is a fundamental temporal reasoning problem and has recently been extended to the Multiagent Simple Temporal Problem (MaSTP). In this paper we present a novel approach that is based on enforcing arc-consistency (AC) on the input (multiagent) simple temporal network. We show that the AC-based approach is sufficient for solving both the STP and MaSTP and provide efficient algorithms for them. As our AC-based approach does not impose new constraints between agents, it does not violate the privacy of the agents and is superior to the state-of-the-art approach to MaSTP. Empirical evaluations on diverse benchmark datasets also show that our AC-based algorithms for STP and MaSTP are significantly more efficient than existing approaches.


Introduction
The Simple Temporal Problem (STP) (Dechter, Meiri, and Pearl 1991) is arguably the most well-known quantitative temporal representation framework in AI. The STP considers time points as the variables and represents temporal information by a set of unary or binary constraints, each specifying an interval on the real line. Since its introduction in 1991, the STP has become an essential sub-problem in planning or scheduling problem (Barták, Morris, and Venable 2014).
While the STP is initially introduced for a single scheduling agent and is solved by centralized algorithms, many realworld applications involve multiple agents who interact with each other to find a solution like the following example: Example 1. When Alice is looking for a position at company X, she might need to arrange an interview appointment with X. Suppose that her colleague Bob is also applying for the position and Alice and Bob are both applying for another position at company Y . To represent and solve such an interview scheduling problem, we need a multiagent framework (see Figure 1 for an illustration). However, as D PPC is based on the P 3 C algorithm (Planken, de Weerdt, and van der Krogt 2008), which triangulates the input constraint graph, it has the drawback of creating new constraints between agents that are possibly not directly connected. In Figure 1, D PPC triangulates the inner cycle by adding at least one new constraint either between X and Y or between Alice and Bob. Neither of these new constraints are desirable, as they introduce constraints between two previously not directly connected agents and thus present a threat to the privacy of the relevant agents.
As the recent technological advancements have allowed for solving larger problems that are highly interwoven and dependent on each other, efficiency and privacy have become critical requirements. To address this challenge, we propose a new approach to solve the MaSTP, which is based on arc-consistency.
A constraint R between two variables x, y is called arcconsistent (AC), if for every value d x from the domain of x there is a value d y in the domain of y such that (d x , d y ) ∈ R. While AC is an important tool for solving finite (multiagent) constraint satisfaction problems (CSPs) (Montanari 1974;Baudot and Deville 1997;Nguyen and Deville 1998;Hamadi 2002) at first glance it is not clear how it can be applied to solving CSPs with real domains such as the STP, because either the existing AC algorithms are fine-grained and work with each single element of a domain to enforce AC, which is impossible for real domains, or they are coarsegrained, but cannot guarantee their termination, as real domains can be infinitely refined when constraints are propagated. 1 Our contributions in this paper are as follows.
• We provide the first AC-based approach for solving STP and analyze its computational complexity (Section 3). • We provide the first AC-based approach for solving multiagent STP, which preserves the privacy of the agents, and analyze its computational complexity (Section 4). • We experimentally show that both our centralized and distributed algorithms outperform their existing counterparts for solving STP (Section 5).
The next section gives a formal introduction to STP.

The Simple Temporal Problem
This section briefly introduces the STP. Details can be found in (Dechter, Meiri, and Pearl 1991).
The simple temporal problem (STP) is a constraint satisfaction problem where each constraint is a set of linear inequalities of the form where a vw , b vw are constants and v, w are variables defined on a continuous domain representing time points. The constraint in (1) is abbreviated as where I v could be a singleton or empty. Assume that o is a special auxiliary variable that represents the fixed zero temporal point. Then the domain I v can also be regarded as a constraint from o to v and Algebraic operations on STP constraints are defined as follows. The intersection of two STP constraints defined on variables v, w yields a new constraint over v, w that represents the conjunction of the constraints. It is defined as The composition of an STP constraint I vu over variables v, u and another STP constraint I uw over u, w yields a new STP constraint over v, w that is inferred from the other two constraints and is defined as Remark 1. For STP constraints, the composition and intersection are associative and, as noted in (Dechter, Meiri, and Pearl 1991), composition distributes over non-empty intersection for intervals, i.e., I ⊗ (J ∩ K) = (I ⊗ J) ∩ (I ⊗ K) for any three intervals I, J, K such that J ∩ K = ∅.
Definition 1. An instance of STP is called a simple temporal network (STN) and is a tuple V, D, C , where V is a finite set of variables, D = {I v | v ∈ V } is a set of intervals, and C is a set of STP constraints defined on V .
We assume that all variables in V appear in C and at most one constraint exists between any pair of variables v and w. Moreover, if I vw = [a, b] is the constraint in C from v to w, we always assume that the constraint I wv = I −1 vw = [−b, −a] is also in C. As previously mentioned, the domain I v of each variable v can be regarded as either a unary constraint, or a binary constraint I ov = I v , where o is a fixed variable representing the zero time point.
An STN naturally induces a graph in the following sense. Definition 2. The constraint graph G N = (V, E) of an STN N = V, D, C is an undirected graph, where the set E of edges consists of constrained unordered pairs of variables in C, i.e., Let G N = (V, E) be the constraint graph of an STN N . We can use a labelled directed graph to illustrate N , where for any undirected edge {v, w} ∈ E there is exactly one directed edge (v, w) that is labelled with the corresponding interval [a vw , b vw ].
A path π from v to w in G N is a sequence of variables u 0 , u 1 , ..., u k such that v = u 0 , w = u k , and {u s , u s+1 } is an edge in E for each s = 0, . . . , k − 1 (k is called the length of π). We write π for the composition of all these I us,us+1 , i.e., If v = w, then we call π a cycle at v. For a cycle π, let [a, b] = π. We call π a negative cycle if b < 0. Definition 3. A solution of an STN N = V, D, C is an assignment, that assigns to each variable v ∈ V a time point from I v ∈ D such that all constraints in C are satisfied. N is said to be consistent if N has a solution. Two STNs are said to be equivalent if they have the same solution set. Definition 4 (Minimality). Let N = V, D, C be a consistent STN and let v and w be variables in V . A constraint I vw from v to w is said to be minimal if every assignment that assigns time points from domains I v and I w to v and w, respectively, and satisfies I vw can be extended to a solution of N . A domain I v of v ∈ V is said to be minimal if every assignment of a time point from I v to v can be extended to a solution of N . We say N is minimal if every constraint in C as well as every domain in D is minimal (note that, since we regard domains as constraints between the zero time point o and variables, we also require the domains to be minimal).

Solving the STP with Arc-Consistency
In this section we show that enforcing arc-consistency is sufficient to solve the STP. Definition 5. Let N = V, D, C be an STN. Suppose v and w are two variables in V , I v and I w are, respectively, their domains, and I vw is a constraint in C from v to w.
We say that I vw is arc-consistent (AC) (relative to I v and We say that N is AC if both I vw and I wv are AC for every constraint Lemma 1. Let N = V, D, C be an STN and v, w ∈ V two variables that are constrained by I vw in C. Then I vw is arc-consistent relative to I v and I w iff I v ⊆ I w ⊗ I wv .
Proof. It suffices to show that which proves Eq. (3).
Proof. This follows directly from Lemma 1 and that I vw is AC relative to I v and I w .
The following result directly follows from Lemma 2. Corollary 3. Let N = V, D, C be an arc-consistent STN. Let π be a path in N from w to v. Then I v ⊆ I w ⊗ π.
Lemma 4. Let N = V, D, C be an arc-consistent STN and v, w variables in V . If N is consistent, then I v ⊆ I w ⊗ I m wv , where I m wv is the minimal constraint from w to v. Proof. Since N is consistent, I m wv is nonempty. Recall that I m wv is the intersection of the compositions along all paths in N from w to v (cf. (Dechter, Meiri, and Pearl 1991, §3)) and composition distributes over non-empty intersection for intervals. The result follows directly from Corollary 3.
Lemma 5 ( (Shostak 1981)). Suppose N = V, D, C is an STN. Then N is inconsistent if and only if there exists a negative cycle. Lemma 6. Given a consistent STN N = V, D, C with n = |V |, for any path π of length ≥ n there is a path π of length < n such that π ⊆ π.
Proof. Since the length of π is ≥ n, π must have a cycle at a variable v. As the cycle is not negative, removing the cycle and leaving only v in the path results in a path π with π ⊆ π. Repeating this procedure until there is no cycle gives the desired result. Lemma 7. Let N = V, D, C be an STN and N its ACclosure. Then N is consistent iff N has no empty domain.
Proof. We prove N is inconsistent iff N has an empty domain. As N and N are equivalent, if N has an empty domain, then N is inconsistent. Now suppose N is inconsistent. Then by Lemma 5, there exists a negative cycle π in N at some w such that where π k is the concatenation of k copies of path π. Because Theorem 8. Let N = V, D, C be a consistent STN and N its AC-closure. Then all domains in N are minimal.
Proof. If the constraint graph G N is connected, i.e., for any two variables v, w, there is a path in G N that connects v to w, then we may replace the constraint from v to w with the nonempty minimal constraint I m vw (or add I m vw , if there was no constraint between v and w). We write the refined STN as N * . For any two variables v, w, by Lemma 4, I v is contained in I w ⊗ I m wv and I w is contained in I v ⊗ I m vw . This shows that N * is the same as the minimal STN of N , and thus, establishes the minimality of each I v .
In case the constraint graph is disconnected, we consider the restriction of N to its connected components instead. The same result applies.
Two special solutions can be constructed if N is arcconsistent and has no empty domain. Proposition 9. Let N = V, D, C be an arc-consistent Proof. Let N = V, D , C be the minimal STN of N . By Theorem 8, we have D = D and N is equivalent to N . The above claim follows as the assignments (Dechter 2003, Corollary 3.2)).
Theorem 10. Enforcing AC is sufficient to solve STP.
Proof. Let N be an STN and N its AC-closure. If N has an empty domain, then N has no solution by Lemma 7. If N does not have an empty domain, then we can use Proposition 9 to find a solution.
Remark 2. (i) As solving an STN is equivalent to solving a system of linear inequalities, the solution set of an STN is a convex polyhedron. Thus any convex combination of the two solutions A and B is again a solution of the STN. (ii) Enforcing AC can in essence find all solutions of an STN: Suppose Algorithm 1: ACSTP Input : An STN N = V, D, C and its constraint graph G = (V, E), where |V | = n. Output: An equivalent network that is AC, or "inconsistent".
if #Q = n then return N 11 return "inconsistent" N is arc-consistent and has no empty domain. We pick an arbitrary variable v that has not been instantiated yet, then assign any value from D v to v, and enforce AC on the resulting network. We repeat this process until all variables are instantiated. (iii) Proposition 9 can also be obtained by first showing that STP constraints are both max/min-closed, and then using the result in (Jeavons and Cooper 1995, Thm 4.2), which states that the AC-closure of a constraint network over max/min-closed constraints have the maximal and the minimal values of the domains as two solutions. As a consequence of this, Theorem 8 can also be obtained, because the solution set of an STN is convex (cf. Remark 2 (i)).

A Centralized AC Algorithm for the STP
In this section we propose an AC algorithm, called ACSTP, to solve STNs. The algorithm is presented as Algorithm 1.
Theorem 11. Given an input STN N , Algorithm 1 returns "inconsistent" if N is inconsistent. Otherwise, it returns the AC-closure of N .
Proof. We first note that intersection and composition of constraints do not change the solution set of the input STN N . This has two implications: First, if a domain I v becomes empty during the process of the algorithm, then the solution set of N is empty and N is inconsistent. Second, if the algorithm terminates and its output N is AC, then N is the AC-closure of N . Consequently, it suffices to show that if the algorithm terminates and returns N , then N is AC. We first consider the case, where the algorithm returns N in line 10 at the kth iteration of the for-loop (lines 2-10) for some 1 ≤ k ≤ n. We show that N is AC. Let I k v be the domain of v obtained after the kth iteration of the forloop. Due to lines 6 and 8, we have for all {v, w} ∈ E that I k v ⊆ I k−1 v ∩ (I k−1 w ⊗ I wv ) and I k−1 w = I k w . Thus we have for {v, w} ∈ E that I k v ⊆ I k w ⊗ I wv , which is by Lemma 1 equivalent to saying that I vw is AC w.r.t. domains I k v and I k w . Hence, the output N is AC. Now suppose that the algorithm exited in line 11 returning "inconsistent". Thus, at the nth iteration of the for-loop we have #Q < n in line 10. We prove that N is inconsistent by contradiction. Assume that N is consistent. For any v ∈ V and any k ≥ 1, we write Π k v for the set of paths from o (the auxiliary variable denoting the zero time point) to v with length ≤ k in the constraint graph of N . We claim for any k ≥ 1. Then, with I m v being the minimal domain of v, we have because I m v is the intersection of the compositions along all paths in N from o to v (cf. (Dechter, Meiri, and Pearl 1991, §3)), where it suffices to only build compositions along paths of length ≤ n by Lemma 6. Thus I n v = I n−1 v = I m v for all v ∈ V , which is a contradiction to our assumption that at the nth iteration of the for-loop we have #Q < n in line 10.
We now prove (5) by using induction on k. First, for k = 1, since Π 1 v contains only one path of length 1 (i.e., the edge {o, v}), we have (5) is true for k − 2 for all w ∈ V . Then by line 6 and our induction hypothesis we have which proves (5).

Solving the MaSTP with Arc-Consistency
In this section we extend ACSTP to a distributed algorithm DisACSTP to solve multiagent simple temporal networks (MaSTNs).

Definition 6. (Boerkoel and Durfee 2013) A multiagent simple temporal network (MaSTN) is a tuple
is an STN belonging to agent i and we require that V i ∩ V j = ∅ for any two different agents i, j = 1, . . . , p. • C X is a set of external constraints, where each constraint is over two variables belonging to two different agents.
Constraint graphs for MaSTNs can be defined analogously as that for STNs, where we use E X for the set of edges corresponding to constraints in C X . See Figure 1 for an illustration. In Figure 1, the edges in E X are represented as red lines.
Definition 7. Suppose M = P, C X is an MaSTN. Let I vw ∈ C X with v ∈ V i , w ∈ V j be an external constraint. We say that I vw is an external constraint of agent i, and write C X i for the set of external constraints of agent i. We call v and w a shared and an external variable of agent i, respectively. We write V X i for the set of external variables of agent i. In Figure 1, the vertices for shared variables are represented as red circles.
DisACSTP is presented in Algorithm 2. In DisACSTP each agent i gets as input its portion N i of the input MaSTN M and the set C X i of its external constraints, and runs its own algorithm. Similar to ACSTP, DisACSTP updates the domains of N i at each iteration of the for-loop and maintains a queue Q i to record the information about the unchanged domains. When a domain becomes empty during the updates, then the agent can terminate the algorithm and conclude that the input MaSTN M is inconsistent. There are however aspects in DisACSTP that are different from ACSTP, which stem from the fact that in MaSTP an agent cannot have the global knowledge of the states of other agents' processes without sharing certain information with other agents. These aspects are the following: 1. The total number n of the variables in the input MaSTN is initially not known to individual agents. This, however, can easily be determined using an echo algorithm (Chang 1982). We can therefore regard n as given as an input to DisACSTP.
2. As the agents may run their processes at different paces, at each iteration of the for-loop (lines 2-34), they synchronize the domains of their external variables (lines 3-4).
Otherwise, some agents might use stale external domains and make wrong conclusions.

When a domain becomes empty while running
DisACSTP, an agent broadcasts (lines 9-11) this information to other agents so that they can terminate their algorithms as soon as possible. Receive the domains of the external variables from the neighbors.

11
return "inconsistent" 4. If the queue Q i of an agent i is full (i.e., it contains all of the agent's variables in V i ) after an iteration of the forloop, then the agent shares this information with all other agents in M so as to jointly determine whether the queues of all agents are full and the network is arc-consistent (lines 15-16 and 21-30).
5. If the queue Q of an agent is not full after an iteration of the for-loop, then the agent broadcasts this information to all other agents, so that they can move to the next iteration of the for-loop as soon as possible.
All the preceding aspects are subject to communication of certain information between agents. DisACSTP coordinates this communication while (i) preserving the privacy of each agent and (ii) reducing the duration of any idle state of an individual agent. Concretely: • Each agent shares information only with the agents who are connected through an external constraint. We call them the neighbors of the agent. This neighborhoodrelationship among the agents induces a graph that we call henceforth the agent graph.
• Each agent shares with its neighbors only the domains of its shared variables. No other information is shared (such as its network structure, constraints, private variables and their domains) and only the neighbors w.r.t. the agent graph can share the information. This property is a critical advantage over D PPC (Boerkoel and Durfee 2013), as D PPC often creates new external constraints during the process and reveal more private information of the agents than necessary.
• Each agent uses a broadcasting mechanism to share global properties of the input MaSTN, i.e., an agent first sends a message (e.g., "inconsistent") to its neighbors, then the neighbors forward the message to their neighbors and so on, until all agents receive the message. To reduce the number of messages, duplicates are ignored by the agents. An agent i broadcasts the following messages: "arcconsistent", "inconsistent" and "Q i is not full", where the last message is indirectly broadcasted by agent i skipping lines 14-34 and moving to the next iteration of the forloop and then sending its shared domains to its neighbors. This initiates a chain reaction among the idle neighbors of agent i who have not moved to the next iteration yet, as they quit the idle states (lines 19-20) and move to the next iteration of the for-loop and then send also their shared domains to their idle neighbors (lines 3-4).
• There is a dedicated agent who checks at each iteration of its for-loop (given its queue is full) whether the queues of all other agents are full at the same iteration. This dedicated agent is determined by building a minimal spanning tree (e.g., by using an echo algorithm (Chang 1982)) T (M) of the agent graph. The agent who is the root (henceforth the root agent) of this tree becomes then the dedicated agent. The root agent sends an inquiry to its children to check whether the queues of all its descendants are full (lines 15-16). The inquiry is then successively forwarded by the descendants whose queues are full. We have to distinguish here between two cases: (1) If all descendants' queues are full, then the inquiry reaches all the leaf agents and returns back as feedbacks (lines 22-23) until the root agent receives all the feedbacks (lines 25-30) and broadcasts "arc-consistency".
(2) If a descendant's queue is not full, then the descendant moves on to the next iteration of the for-loop and initiates a chain reaction among other agents by sending the domains of its shared variables to its neighbors (cf. the second paragraph of the third bullet point).
Due to the properties so far considered, DisACSTP is guaranteed to simulate the behavior of ACSTP while allowing concurrent domain update operations. Theorem 13. Let M = P, C X be an MaSTN. Let N max be a network with e max = max e i + e X

Evaluation
In this section we experimentally compare our algorithms against the state-of-the-art algorithms for solving STNs. For centralized algorithms, we compare our ACSTP algorithm against Planken, de Weerdt, and van der Krogt's P 3 C algorithm (2008); for distributed algorithms, we compare our DisACSTP algorithm against Boerkoel and Durfee's D PPC algorithm (2013). All experiments for distributed algorithms used an asynchronous simulator in which agents are simulated by processes which communicate only through message passing and default communication latency is assumed to be zero. Our experiments were implemented in Python 3.6 and carried out on a computer with an Intel Core i5 processor with a 2.9 GHz frequency per CPU, 8 GB memory 2 .
As measures for comaring performances we use the number of constraint checks and the number of non-concurrent constraint checks (NCCCs) performed by the centralized algorithms and the distributed algorithms, respectively. Given an STN N = V, D, C , a constraint check is performed when we compute relation r ← I vw ∩(I vu ⊗I uw ) and check if r = I vw or r ⊆ I vw .
ACSTP vs. P 3 C Datasets We selected instances from the benchmark datasets of STNs used in (Planken, de Weerdt, and van der Krogt 2012) for evaluations. We considered the scale-free graphs (Scale-free-1) with 1000 vertices and density parameter varying from 2 to 50. We also considered the scalefree graphs (Scale-free-2) with varying vertex count. The scale-free density parameter for this selection is 5. Beside these artificially constructed graphs, we also considered graphs that are based on the road network of New York City (New York). This dataset contains 170 graphs on 108-3906 vertices, 113-6422 edges.

Results
The results are presented in Figure 2, where base-10 log scales are used for the y-axes. For the scale-free graphs we observe that ACSTP is 100-1000 times faster than P 3 C. The dataset New York only contains very sparse networks (each network's density is less than 1%), thus both algorithms could easily solve these networks. However, we still observe that ACSTP is about 5-12 times faster than P 3 C.

DisACSTP vs. D PPC
Datasets We selected instances from the benchmark datasets of MaSTNs used in (Boerkoel and Durfee 2013) for evaluations. The first dataset BDH was randomly generated using the multiagent adaptation of Hunsberger's (2002) random STN generator. Each MaSTN has N agents each with start time points and end time points for 10 activities, which are subject to various local constraints. In addition, each MaSTN has X external contraints. We evaluated the algorithms by varying the number of agents (N ∈ {2, 4, 8, 12, 16}, X = 50 × (N − 1)) and the total number of external constraints (N = 16, X ∈ {100, 200, 400, 800}). The second dataset WS is derived from a multiagent factory scheduling domain (Wilcox and Shah 2012), where N agents are working together to complete T tasks in a man-ufacturing environment. We evaluated algorithms by varying the number of agents (N ∈ {2, 4, 8, 12, 16}, T = 20 × N ) and the total number of tasks (N = 16, T ∈ {80, 160, 240, 320, 400, 480}).

Results
The results are presented in Figure 3, where base-10 log scales are again used for the y-axes. For the DBH random networks (Figure 3a) we observe that DisACSTP is 5-30 times faster than D PPC. For the WS scheduling networks (Figure 3b) DisACSTP is 2-10 times faster than D PPC. For both datasets we observe that, with increasing x-values, the y-values (i.e., NCCCs) for DisACSTP grow slower than those for D PPC.

Conclusion
In this paper we presented a novel AC-based approach for solving the STP and the MaSTP. We have shown that arcconsistency is sufficient for solving an STN. Considering that STNs are defined over infinite domains, this result is rather surprising. Our empirical evaluations showed that the AC-based algorithms are significantly more efficient than their PC-based counterparts. This is mainly due to the fact that PC-based algorithms add many redundant constraints in the process of triangulation. More importantly, since our AC-based approach does not impose new constraints between agents that are previously not directly connected, it respects as much privacy of these agents as possible. We should note here that even though our distributed algo-rithm DisACSTP showed remarkable performance, it can be further fine-tuned by using different termination detection mechanisms (cf. (Mattern 1987) and (Raynal 2013, Ch. 14)).
It would be interesting to see how the result in this paper can be used for solving the general disjunctive temporal problems (Stergiou and Koubarakis 2000). Potential extensions of our paper also include adapting our AC algorithms to incremental algorithms for the STP (Planken, de Weerdt, and Yorke-Smith 2010), dynamic situations (Morris, Muscettola, and Vidal 2001) and uncertainty (Venable and Yorke-Smith 2005).