Multi-agent Path Planning and Network Flow Jingjin Yu Steven M. LaValle Abstract—Thispaperconnectsmulti-agentpathplanningon In this paper, we explore and exploit the connection graphs (roadmaps) to network flow problems, showing that between multi-agent path planning on collision-free unit- the former can be reduced to the latter, therefore enabling distance graphs (or CUGs, see Section II for the definition) the application of combinatorial network flow algorithms, as andnetworkflow.Webeginbyshowingthatmulti-agentpath well as general linear program techniques, to multi-agent path planningproblems on graphs. Exploiting this connection, planning on CUGs is closely related to a class of problems 3 we show that when the goals are permutation invariant, the called dynamic network flow or network flow over time. We 1 0 problem always has a feasible solution path set with a longest then focus on the permutation invariant multi-agent path 2 finish time of no more than n+V 1 steps, in which n is planning problem on CUGs (by permutation invariant, we − the number of agents and V is the number of vertices of the mean that goals are not pre-assigned to agents. Instead, we n underlyinggraph.Wethengiveacompletealgorithmthatfinds a such a solution in O(nVE) time, with E being the number of only require that each goal is reached by a unique agent), J edges of the graph. Taking a further step, we study time and establishing that such problems always have solutions. To 7 distanceoptimalityofthefeasiblesolutions,showthattheyhave solvetheproblemalgorithmically,anadaptedmaximumflow apairwiseParetooptimalstructure,andagainprovideefficient algorithm is provided which plans collision free paths for ] algorithms for optimizing two of these practical objectives. S all agents with worst time complexity O(nVE), in which D I. INTRODUCTION n is the number of agents, V is the number of vertices of the CUG and E is the number of edges of the CUG. . s Consider the problem illustrated in Fig. 1, which inspired Moreover, we guarantee that the last agent takes time no c the authors to pursue this research. As an exercise (26-1 [ more than n+V 1 to reach its goal, assuming that agents in [7]), the escape problem is to determine, given m n2 − ≤ travel at unit speed. Next, we construct efficient algorithms 4 evadersplacedonmdifferentpointsofann ngrid,whether v × forobtainingtemporallyand spatially optimalsolutions. For there are m vertex disjoint paths from these m locations to 7 example,ouralgorithmforshortestoveralltime has running m different points on the boundary of the grid. Intended as 1 time O(nVElogV). We also show that these temporal and 7 ademonstrationofapplicationsofmaximumflowalgorithms spatial objectives cannot be optimized simultaneously (i.e., 5 (Ch. 26 of [7]), it undoubtedly mimics multi-agent1 path they have a Pareto optimalstructure). Portionsof the Pareto . planning problems on graphs. Intrigued by the elegant net- 4 optimal structure collapse as we move to the permutation- 0 workflowbasedsolutiontotheescapeproblem,wewonder: invariant multi-agent path planning problem on CUGs with 2 How tightly are these two classes of problems intertwined goal-replacement. 1 and how we may take advantage of the relationship? As a universal subroutine in multi-agent systems, : v collision-free path planning for multiple agents finds appli- i X cationsintasksspanningassembly[18],[33],evacuation[4], [39],formationcontrol[2],[38],[41],[43],[45],localization r a [14],objecttransportation[31],[40],searchandrescue[21], and so on. Given its importance, path planning for multi- agentsystems hasremainedas a subjectof intense studyfor manydecades.Duetothevastsizeoftheavailableliterature, (a) (b) weonlymentionamostrelatedsubsetoftheresearchinthis fieldandreferthereadersto[5],[26],[28]andthereferences Fig.1. Examplesoftheescapeproblemona6 6grid.Theblackdiscsare × therein for a more comprehensive review of the subject. theinitialevaderlocations.Thegoalistoplandisjointpathsfortheevaders toreachdifferentvertices ontheboundaryofthegrid.a)An instancewith When all agents are treated as a single agent with a high solutiongivenastheboldedges.b)Aninstance withoutasolution. dimensional configuration space, the problem can be solved using cylindrical algebraic decomposition [6] or Canny’s This paper is a preliminary extended version of [?]. This work was roadmap algorithm [3], in theory. Such coupled approaches supported in part by NSF grants 0904501 (IIS Robotics) and 1035345 (Cyberphysical Systems), DARPA SToMP grant HR0011-05-1-0008, and sufferfromthecurseofdimensionality;evenwhensampling MURI/ONRgrantN00014-09-1-1052. basedmethods[23],[27]areused,instancesinvolvingonlya JingjinYuiswiththeDepartmentofElectrical andComputer Engineer- small numberof agents can be computationallychallenging. ing, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA. E-mail: [email protected]. Steven M. LaValle is with the Department of This difficulty prompts the study of methods that seek to Computer Science, University of Illinois at Urbana-Champaign, Urbana, explore local features whenever possible to avoid working IL61801USA.E-mail:[email protected]. with too many agents at a time. Among these, decoupled 1Weuseagentinsteadofrobotsincethemethodappliestoscenariossuch asevacuation planning. planningisthemostpopular,whichgenerallyperformscoor- dinationofrobotmotionafterdecidingapathforeachrobot The rest of the paper is organized as follows. In Section [17], [22], [34], [37], [42], [49]. In contrast, priority based II, we define three multi-agent path planning problems on methods force an order on agents to significantly reduce CUGs. Section III starts with a quick review of network the search space [10], [47]. Some more recent works using flow problems and then proceeds to show the reduction decoupling heuristics include applying optimal decoupling from multi-agent path planning on CUGs to network flow. techniques to exploit problem instances with low degrees Concentratingoureffortsonthepermutationinvariantmulti- of coupling [48], using push-and-swap primitives to avoid agent path planning problem, Section IV begins with a key unnecessary explorationof search space [30], and heuristics construction that allows us to tightly bound the time steps aimedatperformanceguarantees(completenessislost)[50]. required for a time-expanded network to have a feasible Our algorithmic efforts in this paper focus on the per- solution, which in turn enables efficient algorithms. Section mutation invariant multi-agent path planning problem on V takes a further step and studies solution optimality on CUGs. Such formulations, in both discrete and continuous threenaturalobjectives,showingtheobjectiveshaveaPareto forms,areextensivelystudiedasformationcontrolproblems optimal structure. Section VI providesa quick discussion of [2], [38], [41], [43], [45], among others. On research that thegoal-replacementcase,introducesafourthobjective,and appearsmostly related to this aspect of ourpaper,a discrete showsthatthethreetemporalobjectiveslosethepartialorder grid abstraction model for formation control was studied in structure. We conclude in Section VII. [32]. To plan the paths, a three-step process was used in II. MULTI-AGENTPATH PLANNINGPROBLEMS ON [32]: 1) Target assignment, 2) Path allocation, 3) Trajectory COLLISION-FREE UNIT-DISTANCEGRAPHS scheduling. Although it was shown that the process always terminates, no characterization of solution complexity was Let G=(V,E) be a connected, undirected, simple graph offered. In contrast, we provide very efficient algorithms (i.e., no multi-edges), in which V = vi is its vertex set { } that solve a strictly more general class of problems with and E = (vi,vj) is its edge set. Let A= a1,...,an be a { } { } optimality assurance. On the continuous side, a novel for- set of agents with initial and goal locations on G given by mationspaceapproachwasemployedto representthe entire the injective maps xI :A V and xG:A V, respectively. → → formationof robotteams with a single polynomialof which Note that A is essentially an index set; xI(A) and xG(A) are therootscorrespondtotheunassignedconfigurationsforthe the set of initial and goal locations, respectively.We require robots in the formation [24]. that xI(A) and xG(A) be disjoint. For convenience, we let We delay the literature review on network flow, from n= A and use V,E to denote the cardinality of the sets | | which we devise our time expansion construction for multi- V,E, respectively, since the meaning is usually clear from agent path planning,to Section III. The basic idea of apply- the context. Let s be a bijection3 that acts on xG, a feasible ingtimeexpansiontoroboticsproblemisfarfromnew[10], path for a single agent ai is a map pi :Z+ V with the [36]. To the best of our knowledge, however, the research following properties4: 1. pi(0)=xI(ai). 2. Fo→r each i, there presented here is an original attempt at proposing a general exists a smallest kmin Z+ such that pi(kmin)=(s xG)(ai) timeexpansiontechnique,connectingittonetworkflow,and forsomefixeds .That∈is,theendpointofthepath p◦iissome makingfulluseofthebenefitsthatcomewiththisapproach. goal vertex.3. For any k kmin, pi(k) (s xG)(ai). 4. For ≥ ≡ ◦ We also note that our exact and complete algorithms all any 0 k<kmin, (pi(k),pi(k+1)) E or pi(k)=pi(k+1). ≤ ∈ come with low constants in their respective worst case time Intuitively,think of the domain of the paths as discrete time complexitybecause they are derivedfrom well studied fully steps. We say that two paths pi,pj are in collision if there combinatorial algorithms2. Our simulation result, which we existsk Z+ suchthat pi(k)=pj(k)(meet)or(pi(k),pi(k+ ∈ omit due to the length limit, confirms this assertion. 1))=(pj(k+1),pj(k)) (head-on). If p(k)= p(k+1), the There are three main contributions. First, we formally agentstays at vertex p(k) duringthe time interval [k,k+1] . establish the link between multi-agent path planning on As mentioned,in this paper,we work with a specific type graphs and network flow, showing how multi-agent path ofgraphcalledthecollision-freeunit-distancegraph(CUG): planning can be reduced to network flow problems, thereby A CUG is a connected, undirected graph G satisfying the enabling the potential application of powerful tools from following:1. Every edge is of unit length;2. Given any two combinatorial optimization to path planning for multiple distinctedges(u1,v1)and(u2,v2)ofGwithu1=u2,v1=v2, 6 6 agentsinaprincipledway.Second,fortheplanningproblem twodiscshapes(orsphericalfor3Dormore)agentsofradius in which agents do not have pre-specified goals, we give less than √2/4 traveling at unit speed through these edges fast and complete algorithms for finding collision free path (starting simultaneously at u1,u2, respectively) will never sets that deliver every agent to a different goal. Third, we collide. A radius of √2/4 is the largest possible for two study time and distance optimality of the feasible solutions adjacent agents to travel along an “L” shaped path. One can to the aforementioned problem, show that they have a easily verify that any graph with unit edge length and no pairwiseParetooptimalstructure,andagainprovideefficient acute angles between adjacent edges is a CUG. Hence, a algorithms for optimizing two of these practical objectives. connected 2D grid with holes is a CUG. Since subgraphs 2Afullycombinatorialalgorithmisanalgorithmthatonlyadds,subtracts, 3s isintroduced tounifytheproblem formulations; itsusewillbecome andcomparesvalues;nomultiplication anddivisionoperationsareallowed clearshortly.Fornow,thereadermaythinkofitsimplyastheidentitymap. (i.e.,ordered groupoperations versusordered fieldoperations) [16]. 4Inthispaper, weletZ+:=N 0 . ∪{ } of 2D grids are easy to draw and visualize, we generally Problem3modelstheprobleminwhichmultipleidentical use subgraphs of 2D grids when we create examples in this or indistinguishable agents need to be deployed for serving paper. With the above setup, the multi-agent path planning requests at different locations. This problem always has a on CUGs problem is defined as follows. solution:We simplyplanandexecuteonepathata timeand use more “remote” goal vertices earlier to avoid possible Problem 1 (Multi-agent Path Planning on CUGs) Given blocking of later paths; a proof of the existence of such a 4-tuple (G,A,x ,x ) in which G is a CUG, find a set of a choice of paths is given in Section IV. Going one step I G paths P= p ,...,p such that p’s are feasible paths for further and allowing multiple agents to reach the same goal 1 n i respective a{gents a’s}with s being the identity map and no (at different time steps), we get the permutation invariant i two paths p,p are in collision. multi-agent path planning on CUGs with goal replacement i j problem. We require the graph to be a CUG so that it is suitable for multi-agentpath planning. We formalize the rationale in Problem 4 (PermutationInvariantMulti-agentPathPlan- the following lemma. ning on CUGs with Goal Replacement) Given a 4-tuple (G,A,x ,x ) in which G is a CUG, find a set of paths P= I G cOobllsiesirovnat(iaosna2paLrettialpis,oplujtiboen ttowPoropbaltehms 1t)h.aTtheanretwnootdisinc a{gpe1n,.ts..a,ip’ns}fosrucahntahrabtitpria’rsya(rbeuftefiaxsiebdl)espaathnsdfnoor rtwesopepcatitvhes shapedagents5ofradiuslessthan√2/4,startingatthesame pi,pj are in collision except at vertices of xG(A). timeandmovingalongtheserespectivepathswithunitspeed, Thisproblemprovidesarealisticmodelforscenariossuch will never collide. as evacuation of a building due to fire hazard;the set x (A) G PROOF. Without loss of generality, assume the two representsthe exitsto safety:Afteran agentreachesan exit, agents (say, a and a ) started moving at time t = 0 the agent can be removed from the system and the exit i j along p and p , respectively. Between any time becomes available again shortly after. Since G is connected i j steps k and k +1, k 0, agents a and a travels and goals can be reused, a feasible solution to Problem 4 i j along edge (p(k),p(k≥+ 1)) and (p (k),p (k + 1)), can be easily obtainedby sendingall agentsto a single goal i i j j respectively. Since p and p are not in collision, we vertex sequentially. i j always have p(k) = p (k), p(k+1) = p (k+1), and i 6 j i 6 j III. MULTI-AGENTPATH PLANNING ONCUGS AND (p(k),p(k+1))=(p (k+1),p (k)). By the definition of i i 6 j j NETWORKFLOW CUG, two disc shaped agents of radius less than √2/4 A. Network Flow traveling on these edges at unit speed will never collide between time interval [k,k+1]. Since k is arbitrary, the two In this subsection we give a brief review of network flow agents will never collide. (cid:3) problems and algorithms pertinent to our problems. For surveys on network flow, see [1], [13]. We start with the Observation2showsthatasolutiontoProblem1provides classic static network flow problems. a path set for disc agents with radius √2/4 in A to reach their respective goals without a collision. It is easy to see Static Network Flow. A network N =(G,u,c,S) consists thatnotallinstancesofthisproblemaresolvable.Moreover, ofadirectedgraphG=(V,E)withu,c:E Z+ asthemaps → the decision version of Problem 1 (i.e., is there a solution defining the capacities and costs on edges, respectively, and that takes the agents to goals within K time steps) is NP- S V as the set of sources and sinks. We let S=S+ S , − ⊂ ∪ complete6. If we remove the assumption that all agents with S+ denotingthe set of sources and S denotingthe set − must reach their respective goals and allow permutation of sink vertices. For a vertex v V, let d +(v) (resp. d (v)) − ∈ invariantpaths (i.e., as long as each goalgets occupiedby a denote the set of edges of G going to (resp. leaving) v. A uniqueagentintheend),Problem1becomesthepermutation feasible (static) S+,S -flow on this network N is a map − invariant multi-agent path planning on CUGs problem. f :E Z+ that satisfies edge capacity constraints, → e E, f(e) u(e), (1) Problem 3 (PermutationInvariantMulti-agentPathPlan- ∀ ∈ ≤ ningonCUGs)Givena4-tuple(G,A,x ,x )inwhichGisa the flow conservation constraints at non terminal vertices, I G CUG, find a set of paths P= p ,...,p such that p’s are 1 n i feasiblepathsforrespectiveag{entsai’sfo}ranarbitrary(but ∀v∈V\S, X f(e) − X f(e)=0, (2) fixed)permutations andnotwopaths pi,pj areincollision. e∈d +(v) e∈d −(v) and the flow conservation constraints at terminal vertices, 5Orspherical agents with radius less than √2/4, for dimensions higher than2. X( X f(e) X f(e))= − 6The lengthy proof is out of scope for the current paper. For curious v S+ e d (v) e d +(v) readers, the NP-hardness proof is similar to that from [44]; the NP ∈ ∈ − ∈ (3) membershipproof,whichisnontrivial, leads tofastheuristics forsolving X( X f(e) X f(e)). − Problem1. v S e d +(v) e d (v) ∈ − ∈ ∈ − The quantity on either side of (3) is called the value of the Discrete time and continuoustime. In a discrete time model, flow. flows enter and exit from vertices at integer time steps The classic (single-commodity) maximum flow problem t = 0,1,...,T. For a given edge e = (u,v) E, we may asks the question that given a network N , what is the view the cost c(e) as the time that is requir∈ed to pass an maximum value of flow that can be pushed through the amount of flow (not exceeding the capacity) from the tail network (i.e., seeking to maximize F)? The minimum cost u to the head v of the edge e. Therefore, we may interpret maximum flow problem further requires the flow to have a (static) flow network N as a dynamic one without any minimum total cost among all maximum flows. That is, we change of notations. In the closely related continuous time want to find the flow among all maximum flows such that model, which we do not use in this paper, a flow rate is the quantity assignedtoeachedge,designatinghowfastaunitofflowcan Xc(e) f(e) (4) pass throughthe edge. The constraints imposed in the static · networkflowmodelgenerallyapplytodynamicnetworkflow e E ∈ models, except that dynamic network flow further requires is minimized. Given integer inputs, integer maximum flow that at any time, the flow passing through any edge cannot always exists, and many polynomial time algorithms exist exceed the edge capacity. for finding such a solution [9], [15]. The minimum cost maximum flow problem is equivalent to the minimum cost circulation problem, which is also solvable in polynomial x s+ time [46]. 2 2 x WhenadditionalstructureisputonS,additionalquestions s + 1 s- arise. If we limit the supply (demand) of the source (sink) y vertices, we obtain a type of the flow problem called the 0 y 1 s- transshipment problem. To formalize this, let d:V Z be 0 1 2 3 4 → the supplies on the vertices of G. Given a vertex v V, a (a) (b) ∈ positived(v)suggeststhatthevertexhaspositivesupply(v ∈ S+) and a negative one suggests that the vertex has positive Fig. 2. a) The (static) flow network with source s+ and sink s . The − demand(v S ).Forallotherverticesv,d(v)=0.Thebasic numbers on the edges are the costs/time delay for passing through these ∈ − edges. We may assume that the capacities are all unit capacities. b) The versionofthetransshipmentproblemasksforafeasibleflow time-expanded network with 5 copies ofthe original vertices (T =4). All through the network that also respects the supply/demand edges have unit capacity. There is a forward edge between two vertices u requirements andvattimestepst andt′,respectively (e.g.xatt=0andyatt′=1),if one of the following is true: 1. e=(u,v) is an edge of the static network ∀v∈S+, eXd (v)f(e) −eXd +(v)f(e)=d(v), wawrihetihcthhce(heas)av=meuet′nv−itertctoe(sxthtseo).fbTltahhceekgsetraedtegincesen,dewgtwehsiocarhkreraeantlasdiontc′ta−hleletcd=ohs1otsld(atohsveecr(gere)ed’esgn)e;se2ds.ignuec,sve, ∈ − ∈ (5) travelingthroughagreenedgeisthesameastheagentnotactuallymoving. v S−, X f(e) X f(e)=d(v). ∀ ∈ − e d +(v) e d (v) ∈ ∈ − Given a dynamic flow network, a question similar to the Thetransshipmentproblembecomestheevacuationproblem single-commodity maximum flow problem is the following: when S =1 and the demand of the single sink vertex Starting at t =0, what is the maximum units of flow the − | | is equal to the total supply of the source vertices. The can reach the sinks on or before time t =T? It turns out transshipment problem and the evacuation problem, as that this problem can be solved using static flow algorithms special cases of the maximum flow problem, can be such as Edmonds-Karp [9] over a time-expanded network. solved with maximum flow algorithms mentioned above. For example, given the dynamic flow network in Fig. 2(a), If we instead require that vertices of S+,S are paired up its time-expanded network with T =4 is given in Fig. 2(b). − as (s ,s ),...,(s ,s ) and that commodity of type i can To computea flow overthe time expandednetwork,we first 1 ′1 k ′k be injected only into s and taken out at s, we get the add a super source and connect it using outgoing edges to i ′i multi-commodity flow problem. Optimality questions as all copies of source vertices at t =0, and add a super sink these from the single-commodity case can be asked here as and connect all copies of sink vertices for all t to it using well. Unlike in the single commodity case, finding integer outgoing edges (the super source, super sink, and additional maximum flow for multi-commodity problems is NP-hard edges are not shown in Fig. 2(b)). in general and MAX SNP-hard (NP-hard to approximate below a certain multiple of optimal flow value) even for Lemma 5 For a sufficiently large T, a flow for a dynamic some simple restrictions [8]. flow network N is feasible if and only if the corresponding static flow on the time-expanded network of N is feasible. Dynamic Network Flow. If we consider that flowing com- modities through edges takes some time to complete, the A proof of Lemma 5 can be found in [12]. Note that problem becomes a dynamic network flow problem, which determining a minimally sufficient T required by Lemma sometimes is also called network flow over time. There are 5, which directly affects the running time of the result- twocommonvariationsofthedynamicnetworkflowmodel: ing algorithm, is non-trivial. The standard maximum flow algorithms have time complexity depending polynomially edge, and zero cost to the other four edges. To finish the on T and are therefore pseudopolynomial in general. For construction of Fig. 3(c), for each vertex v G, we add ∈ a special class of problems, the quickest transshipment one edge between every two successive copies (i.e., we add problem, of which the goal is finding the quickest feasible the edges (v(0),v(1)),(v(1),v(1)),...,(v(T),v(T))). These ′ ′ flow for a transshipment problem over a dynamic network, correspond to the green and blue edges in Fig. 3(c). For all strongly polynomial time algorithm7 exists [19]. However, green edges, we assign them unit capacity and cost; for all the algorithm requires calling subroutines (for example, blue edges, we assign them unit capacity and zero cost. submodularfunctionoptimizationroutines)thatare not fully The graph Fig. 3(c) is the main piece of G, which is ′ combinatorial algorithms and also has with large constant mostlydonewith the exceptionofthe setS. We maysimply terms when it comes to asymptotic time complexity. As we letS+= u(0):u s+ andS = v(T) :v s .That { ∈{ i }} − { ′ ∈{ −i }} will see, our problems can be solved using polynomialtime is, S+ contains the first copies of the initial locations and fullycombinatorialalgorithms,duetotheirspecialstructures. S the last copies of the goal locations. The network N = − ′ (G,u,c,S+ S )isnowcomplete;wehavereducedProblem ′ − B. Equivalence Between Multi-agent Path Planning on ∪ 1 to an integermaximummulti-commodityflow problemon CUGs and Maximum Network Flow N with each agent from A as a single type of commodity. ′ In this subsection, we establish a reduction from the problems of our interest to multi-commodity network flow. Theorem 6 Given an instance of Problem 1 with input For illustration purpose, we use the simple graph G in parameters (G,A,x ,x ), there is a bijection between its I G Fig. 3(a), with initial locations s+ ,i=1,2 and goal lo- solutions(with maximum numberof time steps up to T) and { i } (cGat,io{nas1,{as2−i}},x,Ii=:a1i,7→2.sA+in,xiGns:taanic7→e os−if)P.roTbolebme a1bilsegtoiveanppblyy tvhaeluientnegoenrmthaextiimmuem-exmpualntid-ecdomnemtwodoirtkyNflow′ csoonlusttirouncsteodffflroomw maximum flow algorithms, we construct from G a time- (G,A,x ,x ) with T time steps. I G expanded directed graph G, part of which is shown in Fig. ′ 3(c). We construct Fig. 3(c) as follows. PROOF. (Injectivity)Assume that P= p ,...,p is a solution to 1 n { } s 2- s 1- u(t )0 u(t+1) s 2- s 1- ttahn=atin0ps,t.a(.tn.),cTec,oorwfreePspromobnaldreksmttoh1e.aFcovorepryeteaxochfopfpii(Gta))ndaantedvtiempryie(tt)si′tme(perestctaeilpnl i thetime-expandedgraphG.Connectingtheseverticesof G s +1 s +1 sequentially(thereisonlyo′newaytodothis)yieldsoneunit′ s +2 v(t )0 v(t+1) s +20 1 10 2 soifnflkovwertfiicoensiNn S′+(,aSfter,wcohninchecitsintgrivtoiaal)p.pIrtoipsrsiatrtaeigsohutfrocrewaanrdd − (a) (b) (c) to see that if two paths p,p are not in collision, then the i j corresponding flows f,f on N are vertex disjoint paths i j ′ Fig.3. a)AsimpleCUGG.b)Agadgetforsplitting anundirected edge and therefore do not violate any flow constraint. Since any throughtimesteps.c)Partofthetime-expanded network(T=2). two paths in P are not in collision, the corresponding set of Sincewecannotcreateaninfinitetime-expandednetwork, flows f1,...,fn is feasible and maximal on N ′. { } we need to specify the required number of time steps. For (Surjectivity) Assume that f1,...,fn is a integer now assume that this number is some sufficiently large maximum multi-commodity flow{on the ne}twork N ′ with T (that is, if a flow with value F is achievable with an fi =1. First we establish that any pair of flows fi,fj are | | arbitrarily long time expansion, then F is also achievable vertex disjoint. To see this, we note that fi,fj (both are unit with only T time steps). After fixing T, we create 2T + flows) cannot share the same source or sink vertices due 1 copies of vertices from G, with indices 0,1,1′,..., as to the unit capacity structure of N ′ enforced by the blue shown in Fig. 3(c). For each vertex v G, we denote edges. If fi,fj share some non-sink vertex v at time step thesecopiesv(0)=v(0),v(1),v(1),v(2),..∈.,v(T).Foreach t>0, bothflowsthenmustpassthroughthe sameblueedge ′ ′ ′ edge (u,v) G and time steps t,t+1, 0 t <T, we then (see Fig. 3(b)) with v being either the head or tail vertex, add the gad∈get shown in Fig. 3(b) betwe≤en u(t),v(t) and which is not possible. Thus, fi,fj are vertex disjoint on ′ ′ u(t+1),v(t+1) (arrows from the gadget are omitted from N ′. We can readily converteach flow fi to a corresponding Fig. 3(c) since they are too small to draw). This gadget path pi (after deleting extra source vertex, sink vertices, ensures that two agents cannot travel in opposite directions vertices in the middle of the gadgets, and tail vertices of on an edge in the same time step. For the gadget, we assign blue edges) with the guarantee that no pi,pj will collide unit capacity to all edges, unit cost to the horizontalmiddle due to “meet”. By construction of N ′, the gadget we used ensures that “head-on” collision is also not possible. The 7An algorithm is a strongly polynomial algorithm if: 1. The number set p1,...,pn is then a solution to Problem 1. (cid:3) { } of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance, and 2. The Sinceintegermaximummulti-commodityflowisNP-hard, spaceusedbythealgorithm isboundedbyapolynomial inthesizeofthe input[16]. the above construction does not directly offer an efficient solution to Problem 1. Nevertheless, with backtracking, it Property 9 Eachpathq isashortestpathbetweenhead(q) i i is not hard to design complete algorithms that search the and tail(q) on G. i time-expanded network N for a feasible solution. Our ′ preliminary analysis shows that when the problem instance Property 10 The total length of the path set Q is minimal. isnotparticularlyhard(i.e.,whentherearenotmanynarrow passagesinthecombinedconfigurationspace),asolutioncan Property 11 If we orient the edges of every path qi Q ∈ be found relatively quickly. We plan to study this problem fromhead(qi)totail(qi),notwopathsshareacommonedge in more detail in future work. Alternatively, we may readily oriented in different directions. obtainanintegerlinearprogrammingproblemfrom N and ′ Properties8and9aremerelyrestrictionstohavetheinitial apply heuristics such as branch and bound method [25], and goal vertices paired up using shortest paths. Property for which many heavily optimized numerical packages are 10 requires the total length of these paths to be minimal. readilyavailable.MovingtoProblem3,allowinganarbitrary Property11, whichis impliedbyProperty10, lendsto show permutation s to act on x means that we may treat all G that the paths can be oriented to form a directed acyclic agents as a single type of commodity. Theorem 6 gives us graph. the following corollary. Lemma 12 There exists aset ofpathsQ= q ,...,q that 1 n Corollary 7 Given an instance of Problem 3 with input { } satisfies Properties 8-11. parameters (G,A,x ,x ), there is a bijection between its I G solutions(with maximum numberof time steps up to T) and PROOF. the integer maximum flow solutions of flow value n on the The first property is trivial to satisfy: Given an arbitrary time-expanded network N ′ constructed from (G,A,xI,xG) instance of Problem 3, an arbitrary pairing of vertices, one with T time steps. from x (A) and one from x (A), will meet the requirement. I G Since G is connected, for each pair of vertices of the At this point, Problem 3 can be solved in polynomial form (s+,s ) with s+ x (A) and s x (A), there is a time using the algorithm for the quickest transshipment i −i i ∈ I −i ∈ G path between them with finite distance. Picking an arbitrary problemwithlinearprogrammingsubroutinesforoptimizing shortestpathq betweens+,s onG(theremaybemultiples submodular functions. In the next section, we show that i i −i of these; for example when G is a grid graph) for 1 i n we can do better by bounding the required time steps for ≤ ≤ satisfies the second property. The third requirement can be findingafeasiblesolutiontoProblem3andthenapplymore satisfied by checking all possible path sets satisfying the standard combinatorial algorithms for network flow. first two requirements and select one with the smallest total distance. IV. EFFICIENTCOMBINATORIALALGORITHMS FOR PERMUTATIONINVARIANTMULTI-AGENTPATH PLANNING ONCUGS s+ i !+ !{ s{ i i i If we choose to apply combinatorial network flow algo- u v rithms over the time-expanded network to find solutions to !{ !+ s+ j s{ j j Problem 3, the first priority is to determine the required j numberof time steps necessary to find a solution;otherwise we cannot declare that the algorithm is complete. We now Fig. 4. Two opposite running paths, qi =s+i w i+uvw i−s−i and qj = providea tight bound on T. Let (G,A,xI,xG) be an instance s+jw +j vuw −j s−j (black paths), have total length at least 2 longer than that of Problem 3. We first prove some intermediate results ofq′i=s+i w i+w −j s−j andq′j=s+jw +j w i−s−i (greenpaths). on path sets over G. To distinguish these paths from the solution path set, denote them as Q = q ,...,q . For With Properties 8-10 satisfied, we claim that Property 1 n { } convenience,head(q), tail(q), and len(q) denote the start 11 is automatic. Suppose the statement is false and assume i i i vertex, end vertex, and length of qi, respectively. With a that two oriented paths qi,qj run in different directions slight abuse of notation,V(),E() denote the vertex set and on some common edge (u,v). We may write the paths edge set of the input param·eter, ·which can be either a path, as q = s+w +uvw s and q = s+w +vuw s , in which i i i i− −i j j j −j −j qi, or a set of paths, such as Q. An intersection between w i+ is the path of qi connecting s+i to u (see Fig. 4). twopathsisa maximalconsecutivesequenceofverticesand w ,w +,w are interpreted similarly. Then, the paths i− j −j edges common to the two paths. A standalone goal vertex q = s+w +w s and q = s+w +w s have total length ′i i i −j −j ′j j j i− −i cisonatavienritnegx vv.∈TxoG(sAta)rtsuocffh, twheatwthaenrteaispaatshinsgelteQpatwhitqh∈thQe etoqtuaalldinisgtalnecne(qais)s+umlepnt(iqonj).−W2e,cwohnicclhudceonthtraatdnicotstwthoeosrhioerntteesdt following properties: paths can have edges oriented in opposite directions. (cid:3) Property 8 Forall1 i n,head(qi) xI(A)andtail(qi) Above proof technique can be generalized to show that ≤ ≤ ∈ ∈ xG(A). For any two paths qi,qj, head(qi)=head(qj) and the oriented paths cannot form any directed cycles. 6 tail(q)=tail(q ). i j 6 Theorem 13 A path set Q that satisfies Properties 8-10 PROOF. induces a directed acyclic graph (DAG) structure on E(Q). By Theorem 13, the paths in Q induces a directed acyclic graph on E(Q). This implies that at least one vertex PROOF. from x (A) must be a standalone goal vertex; otherwise G Since Property11 is impliedby Properties8-10, all edges every goal must be on another path and the directed path ofE(Q)haveauniqueorientation.Therefore,thepathset Q containing the goals must close to form a directed cycle induces a directed graph structure over E(Q). This implies because there are only a finite number of goals. (cid:3) thatthestatementofthetheoremcanonlybefalseifthereis adirectedcycleintheinduceddirectedgraph.Sinceasingle The existence of a standalone goal vertex allows the path from Q, being a shortest path, cannot form a directed construction of a path set which decomposes into paths cycle itself, at least two or more paths, say q1,...,qk, are that can be sequentially scheduled without colliding into need to form a directed cycle. Without loss of generality, each other. We characterize such a path set as one with an we assume these k paths are all needed to form a cycle additional property. (removing any q, 1 i k will leave no directed cycles i ≤ ≤ by q ,...,q q). That is, for each 1 i k, the directed { 1 k}\ i ≤ ≤ Lemma 15 There exists a path set Q satisfying Properties cycle, say C, has at least one edge that belongs only to 8-11 and the following additional property: q (an illustration is given in Fig. 5). We show that we i can update these paths, without violating Properties 8-10, Property 16 Let Q := q,...,q . For any 1 i n, to obtain a path in the end that intersects itself, which i i n { } ≤ ≤ restricting to Q, among all possible paths connecting an contradicts Property 10. i initial location (of Q) to a standalone goal location (of Q) i i using oriented edges from E(Q), q is one shortest such. q i i 2 q0 PROOF. 2 q0 We begin with a Q = q ,...,q satisfying Properties 1 1 n { } q 8-10 and constructa Q = q ,...,q satisfying the desired 1 ′ { ′1 ′n} property while preserving Properties 8-10. By Corollary q k 14, there are one or more standalone goal vertices. Among all possible paths connecting some initial and standalone Fig. 5. A hypothetical (directed) cycle in a path set. We can switch the goals using oriented edges from E(Q), we pick one among thheeadtsotaalndlentagitlhs.oNfoqw1,wq2e tcoangeretmthoevegrqeenanpdatshtsillqh′1a,vqe′2 twheithsoaumtecdhiarnegcitnedg the shortest. This is q′1. Note it is likely that q′1 ∈/ Q, cycle. Performing the same procedure (e′2ssentially an inductive argument) in which case we may assume head(q′1) = head(qi) and eventually yields apaththatcontains adirected cycle. q We may write q as w uw vw , in which uw v is the j 1 1 2 3 2 maximal segment of q1 that belongs to the cycle C; w 1,w 3 q qk maybeempty.SomeotherpathintersectingCmustintersect i q q j i uw v at v (by the maximality of uw v) and have a segment 2 2 belonging to C starting at vertex v; let q be such a path. (a) (b) 2 Since q contributes some unique edges to C, there are 2 Fig.6. Possiblecasesforrearrangingpathswithoutaffectingtotallength. some edges of q in C that follow v but do not belong 2 a)q isthelowergreenpath.b) q isthemiddlegreenpath. to uw v. We can then write q =w vw ww , in which w ′1 ′1 2 2 4 5 6 is the last vertex of q belonging to C. Note that uw v 2 2 tail(q ) = tail(q ) for some q,q Q. There are two and w v may have edges that overlap. We can rearrange ′1 j i j ∈ 4 possibilities: Either E(q ) E(q) E(q ) or q contains q ,q into q = w uw vw ww and q = w vw . Clearly, ′1 ⊂ i ∪ j ′1 1 2 ′1 1 2 5 6 ′2 4 3 edges from some other paths. For the first case (Fig. 6(a)), len(q )+len(q )=len(q )+len(q ); that is, the new path 1 2 ′1 ′2 rearranging the paths as shown in green does not change set again satisfies Properties 8-10. We have shown that a total path length. I.e., Properties 8-10 still hold. For the path set q ,...,q with a directed cycle can be rearranged to yield{a p1ath sekt}such that q ,q ,...,q again contains second case, we may assume that E(q′1)\(E(qi)∪E(qj)) { ′1 3 k} belong to some other paths qk (applying similar reasoning the same directed cycle. Applying the same reasoning used in the first case, we can always get such a q via k recursively shows that we can obtain a shortest path that switchingheadsandtailsofpathswithoutchangingthetotal intersects itself, which is not possible. (cid:3) path length). The switching shown in Fig. 6(b) gives us q ′1 without changing total path length. After updating Q (now Theorem 13 implies the following. contains q as an element), we apply the same procedureto ′1 Q q and so on; the end result is a path set satisfying all Corollary 14 ApathsetQthatsatisfiesProperties8-10has de\s{ire′1d}properties. (cid:3) a standalone goal vertex. If we schedule agents using a path set Q satisfying caneffectivelyremoveq fromtheset q ,...,q andapply 1 1 k { } properties 8-16, there can never be cases where two agents induction hypothesis to q ,...,q to see that p ,...,p 2 k 2 k { } { } block each other, as a direct consequence of Lemma 12. contains no pairs that will collide. Adding p back proves 1 There is still the possibility that one agent blocks another. the inductive case. The following theorem shows that such blocking can be Since len(q) ℓ and no schedule delays a path by more i ≤ minimized. than n 1time steps, T =n+ℓ 1is sufficientforschedule the pat−h set Q. − (cid:3) Theorem 17 Given an instance of Problem 3 with input parameters (G,A,xI,xG) and let ℓ be the largest pairwise Sinceℓ cannotbe largerthanV, thenumberofverticesof distancebetweenamemberofx (A)andamemberofx (A), G, the following corollary is immediate. I G ℓ= max dist(u,v). (6) Corollary 18 For every instance of Problem 3, a feasible ∀u∈xI(A),v∈xG(A) solution exists. Atime-expandednetworkN withT =n+ℓ 1isnecessary ′ − and sufficient for a feasible solution to Problem 3 to exist. In particular, the construction in the proof of Lemma 12 yields a complete (albeit not necessarily efficient) algorithm PROOF. for Problem 3. In addition to confirming that any maximum (Necessity) We constructan instance of Problem 3 shown flow algorithm over the time expanded network N with ′ in Fig. 7. The graph G is two stars with centers connected T = n+ℓ 1 is a also complete algorithm, Theorem 17 by a single path; the red vertices form xI(A) and the blue enables us−to show that such algorithms are efficient. A ones xG(A). It is clear that all red vertices are of distance combinatorial algorithm is an algorithm that only adds, ℓ to all blue vertices. Given this graph G, only one agent subtracts, and compares values; no multiplications and divi- can go from a red vertex to the adjacent black vertex at a sions are allowed (i.e., ordered group operationsversus field single time step. As such, it takes at least n time steps for operations).Analgorithmisastronglypolynomialalgorithm the last agent at a red vertex to go to the neighboringblack if: 1. The number of operations in the arithmetic model of vertex. After that, it takes the last agent ℓ 1 steps to reach computation is bounded by a polynomial in the number of − a blue vertex. Therefore, a total of T =n+ℓ 1 time steps integers in the input instance, and 2. The space used by the − is necessary. algorithmisboundedbyapolynomialinthesizeoftheinput [16]. s- 1 Theorem 19 Problem 3 is solvable using a combinatorial s+ s -n algorithm in strongly polynomial time. 1 PROOF. s+ Since ℓ is the length of some shortest path on a n connected graph G, ℓ = V 1 in the worst case. − Hence, in the worst case, T = n+V 2. Following − Fig. 7. An instance of Problem 3 for demonstrating necessity claim of the construction algorithm given in Section III, the Theorem17. time-expanded network N has an underlying directed ′ graph G with O(T) copies of the undirected graph (Sufficiency) Lemma 15 guarantees the existence of a ′ G (the gadget and extra edges only introduce a small path set satisfying Properties 8-16; we work with such a constant). The graph G then has O(V(n+V 2)) vertices path set Q and schedule it to get a path set P in the time- ′ − and O(E(n+V 2)) edges. Denoting the running time expanded network. The schedule is fairly simple: At each − of an maximum flow algorithm as MF(n,n ,n ) in t=i 1,1 i n, we letagenta movealongq. The claim v e i i − ≤ ≤ which n,n ,n are the number of agents, vertices, and is that no collision will occur withing the scheduled path v e edges, respectively, Problem 3 can be solved in time set P, which we prove via induction. For the base case, a 1 O(MF(n,V(n+V 2),E(n+V 2))) O(MF(n,V2,VE)) starts at head(q1) at t =0. By Property 16, no other initial − − ∼ (there cannot be more agents than vertices), which is locationscanbeclosertotail(q )thanhead(q ).Sinceother 1 1 strongly polynomial since many polynomial time maximum pathsstart later,theycannotgetinthe way of q ’s schedule, 1 flow algorithms exist. (cid:3) which we denote p . Therefore, p cannot collide with any 1 1 other scheduled paths before it reaches its goal. Using the Ford-Fulkerson algorithm [11], the time com- For the inductive case, assume that q ,...,q can be 1 k 1 scheduledtoget p ,...,p without{collision.−We}needto plexity is O(nVE). In practice, even better running times 1 k 1 wshiothwouthtacto{llqi1si,o..n{..,qWk}e cuasne−bteh}escphreodpuelretdytothagtetta{ipl(1q,..).,ipsk}a aOr(eV)poasnsdiblℓe. IOf(VG21).isThae ptilmanearcogmrpaplehx,itywethehnavbeecoEme∼s 1 ∼ 1 1 standalone goal vertex, which means that no other q,i=1 O(MF(n,V(n+V2 2),V(n+V2 2))) O(MF(n,V(n+ i 6 1 1 − − ∼ will ever pass tail(q1). That is, p1 cannot collide with any V2),V(n+V2))). Since in our case n<V, Ford-Fulkerson otherpathonorafterthetimeitreachesitsgoal,tail(q1).We gives us the running time O(nV(n+V12))=O(n2V+nV32). V. OPTIMALSOLUTIONS Since the total time it takes for paths other than pk to finish In this section, we present optimal solutions for the is at least Pni=1len(pi)−len(pk), the time it takes for any permutation invariant multi-agent path planning problem. path pk P to finish cannot be longer than ∈ After introducing several temporal and spatial objectives n n n(n 1) of practical importance, we apply techniques from network Xlen(qi)+ − (Xlen(pi) len(pk)) 2 − − flow to obtain optimal solutions for two of these objectives. i=1 i=1 (9) (n 1)(n 2) Sincetheseobjectivesaredifferentfromthebasicversion of − − +V. Problem3, we provideupdatedboundson T, the numberof ≤ 2 timesstepssufficientfora solutionto exist. Lastly,we show (cid:3) that these objectives possess a Pareto optimal structure and they cannot be optimized simultaneously. Unfortunately, existing results on network flow do not seem to translate into a polynomial time algorithm for A. Optimizing over the Feasible Solutions optimizing Objective 20. The second objective, minimizing Having found feasible solutions to Problem 3, we turn the time thatits lastgoalisreached,providesa lowerbound the focus to the optimality of these solutions for practical on the time that is required to reach all goals. Solutions purposes. As mentioned in Section II, we intend to use the optimizing this objective are useful in providing worst ser- formulation as a model for scenarios such as multi-robot vicing time estimate or guarantee. Solutions to the quickest servicing. For many applications, time optimality is a top transshipment problem [19] yield optimal solutions to this priority.Optimizingoverthe feasible solutionsto Problem3 objective.However,wecanavoidusingsubmodularfunction (that is, we require that all goals are reached), there are two optimization routines if we have a polynomial bound on T, natural criteria for measuring time optimality: whichis providedin the followingcorollaryofTheorem17. Objective 20 Minimizingtheaveragetimeittakesallagents to reach their goals. Corollary 23 Thereexists anoptimalsolutionforObjective Objective 21 Minimizing the time it takesfor the lastagent 21 in a time-expanded network with T =n+ℓ 1. − to reach its goal. To see that Corollary 23 is true, note that T =n+ℓ 1 In terms of agents (robots or people) serving requests, is sufficient forfinding a feasible solution, which must h−ave Objective 20 seeks to minimize the average time before a completion time as large as that of a solution to Objective request gets served, which is arguably the most efficient 21. With the bound on T, running logT rounds (via binary approach. The time steps sufficient for an optimal solution search) of maximum flow over time-expandednetwork with to exist for this objective is (n 1)(n 2)/2+V. different time horizon then gives us an optimal solution − − to Objective 21. The running time is then bounded by Theorem 22 There exists an optimal solution for Objective O(MF(n,V2,VE)logV), which is strongly polynomial. In 20 in a time-expanded network with T =(n 1)(n 2)/2+ − − particular, with Ford-Fulkerson, the running time becomes V. O(nVElogV). PROOF. Let P= p1,...,pn be an solution path set with After time optimality, another very useful solution prop- { } minimum total arrivaltime. The total completion time for P erty to optimize is the total distance traveled by the agents, cannot be less than n len(p), since that is the shortest i.e., spatial optimality: Pi=1 i possibledistancetotravel(moretimemaybeneededsincea robotmaystayidleatanintermediatevertex).Ifweleaveany Objective 24 Minimizing the total distance traveled by the path p out,the totalarrivaltimeit takesforallother p’sto agents on G. k i finishcannotbelessthan n len(p) len(p ).Forany p , Pi=1 i − k k Because we work with a CUG, if an agent a actually len(p ) V 1, because interchangeabilityof robots means i k ≤ − moves along path p between time steps t and t+1, p(t) that it is never necessary for any robot to revisit a vertex. i i must be different from p(t+1). These correspond to the On the other hand, if we start with a shortest unscheduled i black edges in the time-expanded network (see Fig. 3(b)). path set Q= q ,...,q and schedule them according to 1 n { } Thus, to optimize this objective, we can find the shortest Schedule ??, the total finish time cannot be more than total distance traveled by all agents via setting the cost of n n n(n 1) X(len(qi)+i 1)=Xlen(qi)+ − . (7) the holdover edge (green edges in Fig. 3(b)) to zero and − 2 then running minimum cost maximum flow algorithm over i=1 i=1 the time-expanded network. The method is again strongly This provides an upper bound on the minimum total arrival polynomial, with complexity O(V2ElogV), due to the fol- time.By theminimalityofpathsetQ,we have(thefactthat lowing corollary. V 1 len(p ) 0 is used) k − − ≥ n n Xlen(pi) len(pk)+V 1 Xlen(qi). (8) Corollary 25 Thereexists anoptimalsolutionforObjective − − ≥ 24 in a time-expanded network with T =n+ℓ 1. i=1 i=1 − PROOF. Using the scheduling method for establishing form, we may write these results as (6.25,14)and (6.5,12). the sufficiency condition of Theorem 17 on a path set Q Clearly, Objectives 20 and 24 are incompatible. satisfying Properties 8-16 yields the bound. (cid:3) Finally,forObjectives21and24,we mayreusethegraph from Fig. 8(a). It is not hard to check that the vectors we obtain forthis case should be (2,8) and (3,6), which shows B. Pareto Optimality Between the Objectives that the objectives are incompatible. (cid:3) Fromthediscussionintheprevioussubsection,weobserve that each of the three objectives is of practical importance. At this point, one might be tempted to seek solutions that VI. PERMUTATIONINVARIANT MULTI-AGENTPATH optimize multiples of these objectives simultaneously. We PLANNINGPROBLEM ONCUGS WITHGOAL showthatthisisnotpossibleforeachpairoftheseobjectives. REPLACEMENT Inthefollowingtheorem,wesaythattwoobjectivesarecom- After a thorough discussion of Problem 3, we shift our patible if and only if they can be optimized simultaneously. attentiontoProblem4,whichallowsmultipleagentstoreach Otherwise, we say the objectives are incompatible. the same goal. An algorithm for finding a feasible solution to this problem is a trivial modification to the algorithm Theorem 26 Over the feasible solutions to Problem 3, Ob- for solving Problem 3: During the construction of the time- jectives 20-24 are pairwise incompatible. expandednetwork N , instead of letting the edges (v,v )’s ′ ′ ′′ for a goal vertex v have unit capacity, we let them have PROOF. infinite capacities, which allows the reuse of a goal vertex For each pair of objectives from the three objectives, we ofGatmultipletimesteps.AnidenticalversionofCorollary provide an instance of Problem 3, with which we demon- 7 can be stated and proved with the same proof. Similarly, strate the existence of Pareto optimal solutions. Theorem 17 continues to apply. That is, a feasible solution First we look at Objectives 20 and 21. For this pair we to Problem 4 can be found in strongly polynomial time. use G from Fig. 8(a) and for the rest of this proof, the red Given feasible solutions to Problem 4, we may again ask verticesaretheinitiallocationsandtheblueverticesthegoal optimality questions about these solutions. Objectives 20- locations. The optimal solution for Objective 20 is for the 24 from Section V still make sense here. Since Problem 3 agents to take the solid paths connecting the sources and and 4 are quite similar, it is not surprising (as readers can sinks, which has a value of 3+1+1+1 = 3. These paths yield easilyverify)thatthesametechniquesusedtooptimizethese 4 2 a value of 3 for Objective 21 since the longest path has a objectivesforProblem3stillapply.ForProblem4,however, length 3. We may write these two values as a vector (3,3). anotherobjectiveontimeoptimalityisalsousefulinpractice. 2 IfweoptimizeforObjective21,thenthedashedpathsgivea value2andthesepathsyieldanaveragetimeof 2+2+2+2=2. 4 In vector form, this is (2,2). Hence, Objectives 20 and 21 Objective 27 Maximizing the number of agents arriving at are incompatible. each time stept=0,1,...,T, with smallert’s havinghigher priorities. Inthedomainofnetworkflow,Objective27isoftencalled earliest arrival flows. It is applicable to time critical scenar- ios, such as evacuations due to emergencies (fire, diseases, etc.),inwhichtheenvironmentmaybecomehazardousatany given time and render further evacuation efforts impossible. (a) (b) We did not include this objective in earlier discussions Fig.8. Flownetworks usedintheproofofTheorem26. on optimality since the objective is locally greedy and an optimal solution may not be a feasible solution to Problem To show that Objectives 20 and 24 are incompatible, we 3. Onesimple exampleis illustratedin Fig. 9(a). Because of use the graph from Fig. 8(b), which can be embeddable in the local greedy selection, s+ gets paired up with s , which 2 −1 a three dimensional grid (a 2D version can be constructed makesgoals unreachableundertheformulationofProblem −1 as well, but that will require more vertices and edges). For 3. Also, in case where all goals are reached, Objective Objective 20, the optimalsolutionis letting the agenton the 27 may cause later goals to be reached in arbitrarily long rightmostredvertextakethepathgivenbythedashededges time and after traveling arbitrary far. Fig. 9(b) provides an andlettingtherestoftheagentsmovethroughthegreenedge example.Here,localgreedyselectionforcess+ tobepaired i+1 successively, which will in turn require some agents to wait up with s for 1 i n 1, which in turn forces s+ to be alittle.Thisgivesanaveragetimeof 3+4+5+5=6.25.These paired up−i with s≤. T≤hus−, one agent must go throu1gh the 4 −n pathsyieldatotaltraveldistanceof3+3+3+5=14.Ifwe upper (dashed) path, which can be made arbitrarily long. optimizeoverObjective24,thenallagentsshouldgothrough However, when goal replacement is allowed, since each thegreenedge.Thisgivesanaveragetimeof 3+4+5+6=6.5 goal can be used arbitrarily many times, problem instances 4 and a total travel distance of 3+3+3+3=12. In vector such as these from Fig. 9 are no longer problematic. This