We present alternative approaches to routing and scheduling in Answer Set Programming (ASP), and explore them in the context of Multi-agent Path Finding. The idea is to capture the flow of time in terms of partial orders rather than time steps attached to actions and fluents. This also abolishes the need for fixed upper bounds on the length of plans. The trade-of for this avoidance is that (parts of) temporal trajectories must be acyclic, since multiple occurrences of the same action or fluent cannot be distinguished anymore. While this approach provides an interesting alternative for modeling routing, it is without alternative for scheduling since fine-grained timings cannot be represented in ASP in a feasible way. This is diferent for partial orders that can be eficiently handled by external means such as acyclicity and diference constraints. We formally elaborate upon this idea and present several resulting ASP encodings. Finally, we demonstrate their efectiveness via an empirical analysis.
The ease of Answer Set Programming (ASP [1]) to express reachability has made it a prime candidate for addressing various routing problems, like multi-agent path finding [ 2], phylogenetic inference [3], wire routing [4], etc. This lightness vanishes, however, once routing is combined with scheduling for expressing deadlines and durations since fine-grained timings cannot be feasibly represented in ASP. This is because ASP [5], just like CP [6] and SAT [7], usually account for time by indexing action and fluent variables with time steps, a technique tracing back to situation calculus [8] and temporal logic [9]. Each time step results in a copy of the problem description. Hence, the finer the granularity of time, the more copies are produced. Although this is usually a linear increase, it eventually leads to a decrease in performance.
We rather capture flows of time by means of partial orders on actions and/or fluents, similar to partial-order planning [10]. In fact, the avoidance of time steps also eliminates the need for upper bounds on temporal trajectories, that is, horizons or makespans. The trade-of for this is that (parts of) temporal trajectories must be acyclic, since multiple occurrences of the same action or fluent cannot be distinguished without indexing. Moreover, to cease the influence of the granularity of time on the solving process, the idea is to outsource the treatment of partial orders by using hybrid ASP, more precisely, acyclicity and diference constraints. Intuitively, these constraints are used for ordering actions in view of collision evasion. As a matter of fact, we have already applied this technique in several industrial-scale applications involving routing and scheduling, namely, train scheduling [11], system design [12], and warehouse robotics [13]. However, the intricacy of these applications obscured a clear view on the underlying encoding techniques and their formal foundations, which we present in what follows. To simplify this, we apply it to Multi-Agent Path Finding (MAPF [14]), a simple yet highly relevant AI problem.
We begin with some preliminaries from graph theory [15]. We consider graphs (, ) where is a finite set of vertices and ⊆ × is a set of edges. A walk in a graph (, ) is a sequence ()=0 of vertices ∈ for 0 ≤ ≤ such that (, +1) ∈ for all 0 ≤ < . We use () = to refer to the vertex at index 0 ≤ ≤ of walk and | | = to refer to the length of the walk. A walk in a graph (, ) leads from ∈ to ∈ if (0) = and () = . The vertex set of a walk is ( ) = { () | 0 ≤ ≤ | |}; we write ∈ for ∈ ( ). The index set of a walk in a graph (, ) for a vertex ∈ is () = { | = (), 0 ≤ ≤ | |}. A path is a walk in which all vertices (and therefore also all edges) are distinct. A cycle is a walk in which only the first and last vertices are equal. Note that a cycle with just one vertex is also a path. A stroll in a graph (, ) is a walk in the reflexively closed graph (, ∪{(, ) | ∈ }). That is, a stroll is obtained from a walk in (, ) by repeating some or none of its vertices (to mimic waiting). A stroll is path-like, if () = [min (), max ()] for all ∈ . Informally, a stroll is path-like, if dropping all repeated vertices results in a path.
We use the above to define the MAPF problem. In what follows, we consider simple graphs (, ) where ⊆ × is irreflexive. A MAPF problem is a triple (, , ) where (, ) is a simple graph and is a finite set of agents. Each agent ∈ has a start vertex ∈ and a goal vertex ∈ . We stipulate that all start and all goal vertices are disjoint. That is, for all , ∈ , we require that ̸= implies ̸= and ̸= . The start and goal vertex of an agent may coincide, that is, we may have = for ∈ . An agent can either wait at its current vertex or move to a neighboring one. Hence, we use strolls to capture the movement of agents. A plan of length for a MAPF problem (, , ) is a family { }∈ of strolls of length in (, ) leading from to for all ∈ . A plan for a MAPF problem is path-based if all its strolls are path-like. We use as a shortcut for whenever it is clear from context that agent is associated with stroll . A plan { }∈ of length for a MAPF problem (, , ) is 1. vertex conflict-free if () ̸= () for all , ∈ such that ̸= and 0 ≤ ≤ , 2. swap conflict-free if ( + 1) ̸= () or () ̸= ( + 1) for all , ∈ such that ̸= and 0 ≤ < , and 3. follow conflict-free if ( + 1) ̸= () for all , ∈ such that ̸= and 0 ≤ < . A vertex conflict occurs if two agents occupy the same vertex at some point. A swap conflict occurs if two agents traverse the same edge in opposite directions at some point. A follow conflict occurs if an agent enters a vertex another agent just left. The absence of follow conflicts implies the absence of swap conflicts.
Finally, we rely on a basic acquaintance with ASP, and refer the interested reader for details to the literature [16]; the input language of clingo is described in the Potassco User Guide [17].
Consider the MAPF problem (, , ) in Figure 1, delineating in blue and red the movements = {, | 0 ≤ ≤ 1, 0 ≤ ≤ 3} = 0,2 = {(,, ,) ∈ 32 | | − | + | − | = 1} = 1,3 = {, } = 1,0
= 0,0
1
of agents and all of which traverse vertices 0,1 and 1,1 on the following strolls:
4 = (0,2, 0,1, 1,1, 1,2, 1,3)
5 = (0,2, 0,1, 1,1, 1,2, 1,3, 1,3)
4 = (1,0, 1,1, 0,1, 0,0, 0,0)
5 = (1,0, 1,0, 1,0, 1,1, 0,1, 0,0)
6 = (0,2, 0,1, 1,1, 1,2, 1,3, 1,3, 1,3)
6 = (1,0, 1,0, 1,0, 1,0, 1,1, 0,1, 0,0)
(
1 1 1
1
Next, we characterize plans for MAPF problems in terms of orders on agent positions. 3
1 1
An event set ℰ for a MAPF problem (, , ) is a set of events of form @ where ∈ and
∈ . For illustration, consider the events corresponding to the positions of agents and in
Figures 2 and 3 (see also the plans in (
An ordered event set (ℰ , ≺ ) for a MAPF problem (, , ) is path-based if
(
In fact, the ordered event set (ℰ∪ℰ, ≺ ∪≺ ) comprises two conflicts because @0,1, @0,1 as well as @1,1, @1,1 belong to ℰ ∪ ℰ but are unrelated by ≺ ∪ ≺ . The adjacency of 0,1 and 1,1 allows us to resolve this by adding @1,2 ≺ @1,1 (since this implies @1,1 ≺ @0,1). That is, the ordered event set
(ℰ ∪ ℰ, (≺ ∪ ≺ ∪ {@1,2 ≺ @1,1})* ) for the MAPF problem from Figure 1 is (path-based and) conflict-free.
The next definition establishes a general relation between path-based ordered event sets. In other words, two ordered event sets are compatible, if they resolve all conflicts among agents in the same way.
We consider the ordered event set in (
compatible if
Two ordered event sets (ℰ , ≺ 1) and (ℰ , ≺ 2) for a MAPF program (, , ) are We call such an event set a minimal conflict-free path-based ordered event set.
The ordered event set in (
Proposition 2. We have an onto relationship between plans and ordered event sets for MAPF problems: a) for each conflict-free path-based plan, there exists exactly one minimal conflict-free pathbased ordered event set, and b) for each minimal conflict-free path-based ordered event set, there exists at least one conflictfree path-based plan.
This onto relationship underlines the role of conflict-free path-based ordered event sets as an
abstraction of conflict-free path-based plans; the essence lies in the order of events, no matter
the continuance in a position. For example, the conflict-free path-based plan { 6, 6 } from (
Let us now detail the constructions underlying Proposition 2.a) and 2.b).
Given a conflict-free path-based plan { }∈ for a MAPF problem (, , ), the corresponding minimal conflict-free path-based ordered event set is the smallest ordered event set ({@ () | ∈ , 0 ≤ ≤ | |}, ≺ ) satisfying the following conditions: 1. @ () ≺ @ ( + 1) for all 0 < ≤ with () ̸= ( + 1), and 2. @ ( + 1) ≺ @ () for all , ∈ and 0 ≤ < ≤ with ̸= and () = () ̸= ( + 1).
Observe that the ordered event set in (
Given a conflict-free path-based ordered event set ( , ℰ ≺ ) for a MAPF problem (, , ), a conflict-free path-based plan { }∈ is constructed as follows. First of all, we define a sequence of mappings from events to time steps: for each ∈ ℰ and > 0, define 1. 0( ) = 0 2. ( ) = max{ − 1( )} ∪ { − 1( ′) + 1 | ′ ∈ ℰ , ′· ≺ } Consider a fixed point = of this construction satisfying = +1 for some ≥ 0. Intuitively, gives the earliest arrival time of each agent at its traversed locations. With it, we define for each agent ∈ its stroll = ()=0 as follows: 1. = max{ ( ) | ∈ ℰ } 2. = for all @· ≺ @ and all (@) ≤ < (@) 3. = for @ = max≺ ℰ and all (@) ≤ ≤ The resulting plan { }∈ is conflict-free and path-based. Note that there is no shorter plan corresponding to the order since agents move as early as possible.
Consider the construction of arrival time mappings in Table 1 for the ordered event set in (
We represent a MAPF problem (, , ) as a set of facts Γ(, , ) consisting of an atom vertex() for each vertex ∈ , an atom edge(,) for each edge (, ) ∈ , and atoms agent(), start(,), and goal(,) for each agent ∈ . We assume that a suitable syntactic representation is chosen for values of italic variables; this representation is set in typewriter in the source code.
We represent plans by predicates move/3 or move/4, depending on whether we use explicit time points or not. In both cases, the first argument identifies an agent, and the second and third an edge. A path or stroll ()=0 of an agent is then represented by atoms of form move(,− 1,) or move(,− 1,,) with − 1 ̸= for 0 < ≤ , respectively. We use the variant with time points in the next section and drop them in Section 3.4.
We first present a basic encoding for MAPF following the traditional approach in Answer Set Planning [5], which relies on time steps.
The encoding in Listing 1 computes conflict-free plans { }∈ of length for MAPF problems (, , ). The parameter allows for preventing follow conflicts when set to fc. We use a choice rule in Line 1 to generate move candidates. For each time point 1 ≤ ≤ and each agent ∈ , we choose at most one move(,,,) for an edge (, ) ∈ . The selected moves indicate agents exiting vertex at time point − 1 and arriving at vertex at time point . In Lines 3, 4, and 5, we generate candidates for strolls from the start positions of agents ∈ and moves selected in Line 1. Line 3 ensures that (0) = encoded by at(,0,0). In the following line, we derive agent positions at(,,) from move(,,,) establishing () = . The last line in the block encodes that an agent stays at its position if it has not been moved. That is, if we have ( − 1) = and the agent is not moved at time point , we obtain () = captured by at(,,). Note the use of _ in the negative literal. This can be seen as a shortcut for not move(A,U,T) together with the rule move(A,U,T) :- move(A,U,V,T) projecting out variable V; the _ must not be interpreted as an anonymous variable here. At this point, the vertices in the stroll candidates are not necessarily connected by edges nor do Listing 1 Encoding to find bounded length plans for MAPF 1 { move(A,U,V,T): edge(U,V) } <= 1 :- agent(A), T=1... 3 at(A,U,0) :- start(A,U). 4 at(A,V,T) :- move(A,_,V,T), T=1... 5 at(A,U,T) :- at(A,U,T-1), not move(A,U,_,T), T=1... 7 :- move(A,U,_,T), not at(A,U,T-1).
8 :- goal(A,U), not at(A,U,). 10 :- { at(A,U,T) } > 1, vertex(U), T=0... 11 :- move(_,U,V,T), move(_,V,U,T). 12 :- at(A,U,T), at(B,U,T+1), A!=B, =fc. 14 :- { at(A,U,T) } != 1, agent(A), T=1... they lead to goal vertices . The next two integrity constraints in Lines 7 and 8 ensure that the candidates are indeed strolls. Connectedness is ensured by the first integrity constraint. We discard candidates whenever the agent is not at the source vertex of a move. For each true atom move(,,,), we require ( − 1) = by discarding solutions where not at(,, − 1) is true. At this point, the stroll candidates are indeed strolls. The only missing piece is to require that they lead to goal vertices. This is addressed by the second integrity constraint ensuring that () = . For now, we have a plan { }∈ that is not necessarily conflict-free. In Lines 10, 11, and 12, we ensure that the plan is free of vertex, swap, and follow conflicts, respectively. The first integrity constraint discards plans in which two agents occupy the same vertex at the same time. The next integrity constraint ensures that there are no swap conflicts. Here, we deviate slightly from the definition of swap conflicts. Observe that a swap conflict can only occur if two agents travel between two vertices in opposing directions at the same time point. Thus, we discard solutions with opposing moves. We treat follow conflicts in Line 12 following the definition. Finally, we add a redundant check in Line 14 asserting that any agent must be at exactly one position. This check is meant to improve solving performance.
Proposition 3 (Soundness). Given a MAPF problem (, , ), let be the union of Γ(, , ) and the program in Listing 1 for some ∈ N0 (and = fc).
If is an answer set of , then {( | at(,,) ∈ )=0}∈ is a vertex, swap, (and follow) conflict-free plan for (, , ).
Proposition 4 (Completeness). Given a MAPF problem (, , ), let be the union of Γ(, , ) and the program in Listing 1 for some ∈ N0 (and = fc).
If { }∈ is a vertex, swap (and follow) conflict-free plan for (, , ), then Γ(, , ) ∪ {at(, (),) | ∈ , 0 ≤ ≤ }∪{move(, ( − 1), (),) | 0 < ≤ , (− 1) ̸= ()} is an answer set of .
We now present a solution to MAPF reflecting event orderings; it consists of Listing 2, 3, and 4. Listing 2 Encoding to find candidate paths for MAPF problems 1 { move(A,U,V): edge(U,V) } <= 1 :- agent(A), vertex(V). 2 { move(A,U,V): edge(U,V) } <= 1 :- agent(A), vertex(U). 3 :- move(A,U,_), not start(A,U), not move(A,_,U). 4 :- move(A,_,U), not goal(A,U), not move(A,U,_). 6 :- start(A,U), move(A,_,U). 7 :- goal(A,U), move(A,U,_). 8 :- start(A,U), not goal(A,U), not move(A,U,_). 9 :- goal(A,U), not start(A,U), not move(A,_,U).
The first encoding in Listing 2 selects atoms move(,,) for agents ∈ and edges (, ) ∈ for a MAPF problem (, , ). Given a stable model of Listing 2, the selected moves for each agent form a subgraph (, ) of (, ) such that 1. = {(, ) | move(,,) ∈ }, 2. = {, } ∪ {, | (, ) ∈ }, 3. deg− () = deg+() = 1 for all move(,,) ∈ , 4. deg− () = 1 if ̸= and deg+() = 1 if ̸= for all move(,,) ∈ , 5. deg− () = deg+() = 0, and 6. deg− () = deg+() = 1 if ̸= .
Any vertex on a path diferent from the start vertex must have an in degree ( deg− ) of one in (, ); any vertex on a path diferent from the goal vertex must have an out degree ( deg+) of one in (, ); the start and goal vertices must be the start and end of the path. Hence, the subgraph for an agent consists of exactly one path leading from to and zero or more separate cycles with a length greater than or equal to two.
To see this, let us go over the rules and see how they afect the in and out degrees of vertices. The rules in Lines 1 and 2 generate atoms move(,,) for agents ∈ such that (, ) ∈ . Furthermore, they ensure that deg− () ≤ 1 and deg+() ≤ 1 for all move(,,). We also get deg− () ≥ 1 and deg+() ≥ 1 for all move(,,). Thus, at this point, we have deg− () = deg+() = 1 for all move(,,). Lines 3 and 4 ensure that deg− () = 1 if ̸= and deg+() = 1 if ̸= for all move(,,). Note that this uses deg− () ≤ 1 and deg+() ≤ 1 ensured in Lines 1 and 2. Lines 6 and 7 ensure that deg− () = deg+() = 0. Lines 8 and 9 ensure that deg− () = deg+() = 1 if ̸= . Note that this uses deg− () ≤ 1 and deg+() ≤ 1 ensured in Lines 1 and 2.
The second encoding in Listing 3 selects atoms resolve(,,) in accord with Definition 2. When such an atom is derived, agent has to depart from vertex before agent arrives at . The rule in Line 4 chooses which of two agents moving to the same vertex has to move first. Listing 3 Encoding to find candidate event orders for MAPF problems 1 resolve(A,B,U) :- start(A,U), move(B,_,U), A!=B. 2 resolve(A,B,U) :- goal(B,U), move(A,_,U), A!=B. 3 { resolve(A,B,U); 4 resolve(B,A,U) } >= 1 :- move(A,_,U), move(B,_,U), A<B. 6 :- resolve(A,B,U), resolve(B,A,U).
The encoding assumes that ̸= and ̸= for all , ∈ with ̸= . Thus, a conflict at a start and goal vertex can only arise if another agent moves to such a vertex. The rules in Lines 1 and 2 select the right resolution order at these vertices: agents at their start vertex as well as agents passing through the goal position of another agent have to move first. At this point, there is at least one resolve atom for each case in Definition 2. The integrity constraint in Line 6 ensures that there is exactly one. Note that there is exactly one true move(,,) for each true resolve(,,). This is obvious for atoms derived by the rule in Line 4. Assume that resolve(,,) is derived by the rule in Line 1. Then there are two cases. If = , a conflicting atom would be derived in Line 2. If ̸= , there must be a move for agent . The same argument can be made for resolve atoms derived by the rule in Line 2.
Finally, the encoding in Listing 4 ensures that the move and resolve atoms from Listings 2 and 3 form a conflict-free path-based ordered event set. The edge directive in Line 1 specifies Listing 4 Encoding to find conflict-free ordered event sets for MAPF 1 #edge ((A,U),(A,V)) : move(A,U,V).
2 #edge ((A,V),(B,U)) : resolve(A,B,U), move(A,U,V). a graph containing edges given by the move atoms. We can interpret the tuples (, ) in the edge right after the #edge keyword as events @. Thus for each true move(,,) an edge (@, @) is added to the graph. The solver discards all solutions where this graph contains a cycle. Remember that the encoding in Listing 2 admits graphs with paths and cycles for agents. Thus, at this point, we have ensured that the moves form a path-based ordered event set. The edge directive in Line 2 further extends the above graph. In accord with Definition 2, we add edge (@, @) for each atom resolve(,,) where @· ≺ @ is captured by move(,,). We have seen above that there is exactly one such move. Thus, if the resulting graph is acyclic, then there is a corresponding conflict-free path-based ordered event set.
Next, we define how to obtain orders from answers sets of the above programs. Definition 4. Let (, , ) be a MAPF problem and be an answer set of Γ(, , ) and the programs in Listings 2, 3, and 4.
The ordered event set (ℰ, ≺ ) corresponding to is the smallest ordered event set such that a) ℰ = {@, @ | move(,,) ∈ } ∪ {@ | resolve(,,) ∈ }
Proposition 5 (Soundness). Let (, , ) be a MAPF problem and be the union of Γ(, , ) and the programs in Listings 2, 3, and 4.
If is an answer set of , then the ordered event set (ℰ , ≺ ) corresponding to is a minimal conflict-free path-based ordered event set for (, , ).
Together with Proposition 2.b), this implies the existence of a corresponding path-based plan, which can be constructed as described at the end of Section 3.1.
Definition 5. Let (, , ) be a MAPF problem and (ℰ , ≺ ) be a minimal conflict-free path-based ordered event set for (, , ).
We define the set of atoms corresponding to (ℰ , ≺ ) as the smallest set such that a) Γ(, , ) ⊆ , Proposition 6 (Completeness). Let (, , ) be a MAPF problem and be the union of Γ(, , ) and the programs in Listings 2, 3, and 4.
If (ℰ , ≺ ) is a minimal conflict-free path-based ordered event set for (, , ), then the set of atoms corresponding to (ℰ , ≺ ) is an answer set of .
This and Proposition 2.a) implies that each path-based plan of a MAPF problem has a corresponding stable model of the MAPF encodings.
To evaluate our encoding variants, we built an ASP-based benchmark generator for diferent types of grid-based MAPF problems,1 viz. random and room configurations. The instances are created by choosing subgraphs of a square grid graph (, ) with = { | 1 ≤ , ≤ } and = {( , ) ∈ × | | − | + | − | = 1} for some > 0. The generated graphs are undirected and connected. Agents’ start and goal vertices are picked randomly. For room instances, the grid is evenly divided into rooms separated by walls of width one; neighboring rooms are connected by choosing up to one random vertex as a door. For random ones, a certain percentage of the vertices of the square grid graph is chosen.
Instances are built via the following parameters: 10 ≤ ≤ 40 for the size of the underlying square grid graph, between 5 and 30 agents, square rooms of size 1 to 5, and vertices are chosen with a 50% probability for the random instances. In total, we consider 105 instances 1https://github.com/krr-up/mapf-instance-generator
Random instances with path-based plans vsc-free vsfc-free
Room instances with path-based plans vsc-free vsfc-free 104 103 102 101 100 0 20 order AC 40 60 0 order ASP
20 order DC 40 60 vanilla 0 (56 random, 38 room) with at least one conflict-free path-based plan. We ran all instances on a compute cluster with Intel Xeon E5-2650v4@2.9GHz CPUs with 64GB of memory running Debian Linux 10.2 We used a timeout of 3h and limited the memory to 16GB per instance.
We consider the vanilla encoding (vanilla) in Listing 1 and the event ordering encoding (order AC) described in Section 3.4. Furthermore, we use a variant of the latter replacing the acyclicity constraints in Listing 4 with diference constraints ( order DC) and clingo[dl] as solver: 1 &diff{(A,U)+1}<=(A,V) :- move(A,U,V).
2 &diff{(A,V)+1}<=(B,U) :- resolve(A,B,U), move(A,U,V).
Finally, we use a plain ASP encoding (order ASP) to check if the generated order is acyclic. Without going into details, we mention that this check results in groundings of cubic size in the number of possible events.
We try to find both conflict-free ( vsfc-free) and vertex and swap conflict-free plans ( vsc-free). In the second setting, this means setting the mode to fc for the vanilla encoding. For the DC encoding, this means changing the diference constraint in Line 1 above to use +0 instead of +1 and an additional integrity constraint to discard swap conflicts. Note that the integrity constraint does not increase the asymptotic size complexity of the grounding. For the ASP and AC encodings, the second setting involves a more complicated construction, which we do not detail here. Note that even for the AC encodings, this involves a lot more overhead comparable to that of the order ASP setting.
We formulate the following hypotheses for evaluating the generated benchmark on the configurations described above. The vanilla encoding should perform well for small plan lengths (H1). The order ASP configuration is not applicable in practice because of the too large grounding (H2). The order AC configuration works well for path-based plans in the vsfc-free setting even with large plan lengths (H3) but does not work well in the vsc-free setting (H4). The order DC configuration works well for path-based plans with large plan lengths independent of the conflict handling ( H5).
The plots in Figure 4 present cactus plots showing the time (x-axis) to solve an instance (y2https://www.cs.uni-potsdam.de/bs/research/labs.html#hardware axis); run times are sorted in ascending order for each curve matching one of the configurations discussed above. Note that we fix the plan length for the vanilla encoding in the vsc-free setting to the optimal length such that an instance is satisfiable. Since we did not have this information available for vsfc-free (and it is hard to compute), we added 20% to the plan length.
We begin with evaluating the vsc-free setting. In line with H1, we observe that the vanilla encoding performs well noting that agents can move to their goal vertices rather directly. Agreeing with H5, order DC performs well too. On room instances it is better than vanilla, which we attribute to the longer plan length necessary to avoid obstacles. As stipulated in H2 and H4, the order ASP and order AC configurations do not work at all.
In the vsfc-free setting, we evaluate the random and room instances separately. We begin with the random instances. Note that order DC performs almost the same as in the vsc-free setting. However, the vanilla configuration becomes much slower if plans have to be follow conflict-free. While this is partly associated with larger plan lengths, we cannot fully explain this behavior. Finally, we confirm H3, noting that order AC performs well here. However, despite the less expressive AC constraints, it performs does not perform as well as order DC. This is due to clingo[dl] implementing stronger propagation enabled using option --propagate=full. The room instances are much harder in the vsfc-free setting. Not just vanilla but also the event order based configurations are slowed down. We attribute this to short plan length due to H1 and large overhead due to many reachable vertices for the event order settings.
Although our focus has been on routing, the addition of scheduling boils down to replacing the acyclicity constraints in Listing 4 by diference constraints taking durations into account. Assuming that the edge predicate has a third duration argument, we use the following rules: 1 &diff{(A,U)+D}<=(A,V) :- move(A,U,V), edge(U,V,D).
2 &diff{(A,V)+D}<=(B,U) :- resolve(A,B,U), move(A,U,V), edge(U,V,D). Without entering details, the above should sufice to indicate that our approach generalizes to combined routing and scheduling in a seamless way (as detailed in the upcoming full version of our paper). As mentioned, we have already successfully applied this technique in industrial applications involving routing and scheduling [11, 12, 13]. This paper aims at providing an introduction to the underlying encoding techniques and their formal foundations.
Our approach builds on the characterization of plans in terms of partially ordered event sets. This is similar to partial order planning, where a partial order is maintained among actions [10]. In MAPF, a related idea was implemented using activity constraints from constraint-based scheduling [18]. Also, simple temporal networks were used to add schedules to pre-computed plans [19]. Similarly, in robotics, action dependency graphs were used to avoid online collisions by adding temporal dependencies to existing plans [20]. Finally, it is worth mentioning that it was recently shown that whenever each agent has a predefined path, the problem of deciding if there is a MAPF solution (without any bounds on any cost function) is NP-Hard [21]. Acknowledgments. This work was funded by DFG grant SCHA 550/15. [15] E. Bender, S. Williamson, Lists, Decisions and Graphs, University of California, San Diego, 2010. [16] V. Lifschitz, Answer set planning, in: D. de Schreye (Ed.), Proceedings of the International
Conference on Logic Programming (ICLP’99), MIT Press, 1999, pp. 23–37. [17] M. Gebser, R. Kaminski, B. Kaufmann, M. Lindauer, M. Ostrowski, J. Romero, T. Schaub, S. Thiele, Potassco User Guide, 2 ed., University of Potsdam, 2015. URL: http:// potassco.org. [18] R. Barták, J. Svancara, M. Vlk, A scheduling-based approach to multi-agent path finding with weighted and capacitated arcs, in: E. André, S. Koenig, M. Dastani, G. Sukthankar (Eds.), Proceedings of the Seventeenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS’18), IFAAMAS, 2018, pp. 748–756. [19] W. Hönig, T. Kumar, L. Cohen, H. Ma, H. Xu, N. Ayanian, S. Koenig, Multi-agent path ifnding with kinematic constraints, in: A. Coles, A. Coles, S. Edelkamp, D. Magazzeni, S. Sanner (Eds.), Proceedings of the Twenty-sixth International Conference on Automated Planning and Scheduling (ICAPS’16), AAAI Press, 2016, pp. 477–485. [20] A. Berndt, N. van Duijkeren, L. Palmieri, T. Keviczky, A feedback scheme to reorder a multi-agent execution schedule by persistently optimizing a switchable action dependency graph, CoRR abs/2010.05254 (2020). URL: https://arxiv.org/abs/2010.05254. doi:10.48550/arXiv.2010.05254. [21] M. Abrahamsen, T. Geft, D. Halperin, B. Ugav, Coordination of multiple robots along given paths with bounded junction complexity, CoRR abs/2303.00745 (2023). URL: https: //doi.org/10.48550/arXiv.2303.00745. doi:10.48550/arXiv.2303.00745.