⋆ Dynamic Scope-Based Dijkstra’s Algorithm Petr Hlinˇeny´ and Ondrej Moriˇs Faculty of Informatics, Masaryk University Botanicka´ 68a, 602 00 Brno, Czech Republic [email protected], [email protected] 2 1 0 2 Abstract. Webriefly report on the current state of a new dynamical- n gorithmfortherouteplanningproblembasedonaconceptofscope(the a static variant presented at ESA’11, [16]). We first motivate dynamiza- J tion oftheconceptofscopeadmissibility,andthenwebrieflydescribea 0 modificationofthescope-awarequeryalgorithm of[16]todynamicroad 1 networks. Finally, we outline ourfuture work on this concept. ] S 1 Introduction D . s The single pair shortest path problem in real-world road networks, also known c [ as route planning, has many important everyday applications. There are two most significant variants of the problem – static and dynamic route planning. 1 In the static variant, a road network is fixed during the computation of v 0 optimal routes (query). Static route planning received a lot of attention during 0 the last decades. On the other hand, in the dynamic variant a road network is 0 subject to change in time – some new roads are built, some other are closed, 2 traffic jams or car accidents happen, some routes must be avoided due to turn . 1 angle limits, and so on. Clearly, the latter is a more realistic scenario. Actually, 0 even time-dependent cost functions can be modeled in dynamic route planning 2 to some extent. 1 : Classicalalgorithmssuchas Dijkstra’s [1]or A* [3] andtheir dynamic adap- v tions[2]arenotwellsuitable neitherforstatic norfordynamicvariantsbecause i X of huge road networks size. Thus, a feasible solution lies in computing suitable r auxiliary data of the road network (preprocessing) in order to improve both a time and space complexity of subsequent queries. This technique led to several very interesting static approaches in the last decade, see extensive surveys, for instance, in [13,14]. Some of these algorithms such as highway-hierarchies [10], ALT [9] or, for example, geometric containers [8] were proved to work fine also in the dynamic scenario [7,6,11,12]. Recently, in order to fill a gap between a variety of exact route planning approaches,wehavepublished [16]a differentnovelapproachaimedat“reason- able”routes.Itisbasedonaconceptofscope,whosecoreideacanbeinformally outlinedasfollows:Theedgesofaroadnetworkareassociatedwithascopemap ⋆ Research supported by the Czech Science Foundation, grants P202/11/0196 and Eurocores GIG/11/E023. such that an edge e assigned scope s is admissible on a route R if, before or e after reaching e, such R travels distance less than a value associated with s on e edges with scope higher than s . The desired effect is that low-level roads are e fine near the start or target positions, while only roads of the highest scope are admissible in the long middle sections of distant routing queries. Overall, this nicelycorrespondswithhumanthinkingofintuitiveroutes,andallowsforavery space-efficient preprocessing,too. New Contribution. In the dynamic scenario, however, a static scope map may badly fail. Imagine, for instance, a closure of a motorway tunnel which can be bypassed only on low-level mountain roads. Then a detour would not be scope admissible in the aforementioned sense, and so a dynamic adjustement of this definition is needed. We present such an adjusted definition here, along with a modification of Dijkstra’s algorithmfor scope admissible routes in this dynamic scenario. Our algorithm is exact, and its time complexity grows only slightly over ordinary Dijkstra if few negative changes are introduced in the network. 2 Preliminaries A directed graph G is a pair of a finite set V(G) of vertices and a finite multi- set E(G) ⊆ V(G)×V(G) of edges. A walk P ⊆ G is an alternating sequence (u0,e1,u1,...,ek,uk) of vertices and edges of G such that ei = (ui−1,ui) for i=1,...,k. The weight of a walk P ⊆G w.r.t. a weighting w:E(G)7→R of G isdefinedas|P| =w(e )+w(e )+···+w(e )whereP =(u ,e ,...,e ,u ).An w 1 2 k 0 1 k k optimal walk between two vertices achieves the minimum weight over all walks. A road network is referred to as a pair (G,w) where G is a directed graph (such that the junctions are represented by V(G) and the roads by E(G)), and w (cost function) is given as a non-negative edge weighting w : E(G) 7→R+. In 0 the dynamic scenario, w is simply replaced with w∗ (differing from w only on few edges, say). If e is removed then let w∗(e)=∞. Drivenbyreal-worldmotivation,wefocusonnegative(increasedweight,even to ∞) changes in w. We thus now for simplicity omit the possibility of adding newedgestoG,thoughweunderstanditmaybe usefulwhen,e.g.,adesignated detour locally changes the road network. 3 Scope and Scope Admissibility A simplified versionofthe scope concept is briefly introducedhere.We strongly recommend reading [16] for more detailed treatment and, due to lack of space, omit most details here. Definition 3.1 ([16]). Let (G,w) be a road network. A scope mapping is de- fined as S :E(G) 7→N ∪{∞} such that 0,∞∈Im(S). Elements of the image 0 Im(S) are called scopelevels. Each scope level i∈Im(S) is assigned a constant value of scope νS ∈R ∪{∞} such that 0=νS <νS <···<νS =∞. i 0 0 1 ∞ In practice there are only a few scope levels (say, 5). The desired effect, as formalized next, is in admitting low-level roads only near the start or target positions until higher level roads become widely available. Definition 3.2 ([16]). Let (G,w) be a road network and x ∈ V(G). An edge e = (u,v) ∈ E(G) is x-admissible in G for a scope mapping S if, and only if, there exists a walk P ⊆G−e from x to u such that 1. each edge of P is x-admissible in G−e for S, 2. P is optimal subject to (1), and 3. for ℓ=S(e), Pf∈E(P),S(f)>ℓ w(f) ≤ νℓS. Definition 3.3 ([16]). Let (G,w) be a road network and S a scope mapping. For a walk P = (s = u ,e ,...e ,u ) in G; P is s-admissible in G for S if 0 1 k k every e ∈E(P) is s-admissible in G for S. i Static S-Dijkstra’s Algorithm. Aforementioned seemingly complicated defini- tions can be smoothly integrated into (the bidirectional variants of) Dijkstra’s orA*algorithms,simplykeepingtrackoftheextremes-admissibility(ort-adm. in reverse dir.) condition: – For every accessed vertex v and each scope level ℓ ∈ Im(S), the algorithm keeps, as σℓ[v], the best achieved value of the sum Pf∈E(P),S(f)>ℓ w(f). – The s-admissibility of edges e starting in v then depends just on σS(e)[v]≤ νS , and only s-admissible edges are relaxed further. S(e) Theorem 3.4 ([16]). S-Dijkstra’s algorithm (uni-directional), for a road net- work (G,w), a scope mapping S, and a start vertex s∈V(G), computes an op- timal s-admissible walk from s to every v ∈V(G) in time O(cid:0)|E(G)|·|Im(S)|+ |V(G)|·log|V(G)|(cid:1). The most important computational aspect of scope lies in the fact that only the edges of unbounded scope level ∞ matter for global preprocessing (an idea relatedto better knownreach [5]). Informally,the query algorithmof [16] works instages:Intheopeningcellular phase,theroadnetworkislocallysearched(uni- directional S-Dijkstra) from both start and target vertices until only edges of unbounded scope are admissible. Then a small preprocessed “boundary graph” is searched by another algorithm (e.g. hub-based labeling [15]) in the boundary phase. Finally, in the closing cellular phase, the scope-unbounded long middle section of the route is “unrolled” in the whole network. We remark that the boundary graph will remain static even in the dynamic scenario (due to expensive preprocessing), and dynamic changes will be mainly dealt with in the closing cellular phase. Yet we have to pay attention to scope admissibility since it is the key to much improved preprocessing [16] to the boundary graph. It is therefore essential to “dynamize” our definition and S- Dijkstra’s algorithm for that purpose. 4 S-Dijkstra’s Algorithm – Dynamization In the rest, due to limited space, we only briefly sketch the uni-directional Dy- namic S-Dijkstra’s Algorithm used locally in the opening cellular phase (while the admissibility definition is implicitly embedded in it). This procedure can be routinely turned into bidirectional and then used to resolvedynamic changes in cells during the closing cellular phase. We first remark on the “only negative change” assumption of our approach (Sec. 2). This well corresponds with a real-world situation in which just “bad things happenon the road”,and the driverthus usually has to find anavailable detour, instead of looking for unlikely road improvements. Therefore, we are contentifourqueryalgorithmfindsthatanoptimalrouteoftheoriginalnetwork (wrt. w) is admissible, though not perfectly optimal,1 in the changed network (w∗). However, when things go worse with w∗, then our algorithm will always find an optimal dynamic-scope admissible detour in the changed network. Main Informal Idea. Imagine a driverapproachinga roadrestrictionor closure. Whatwouldshedo?Intuitively,thebestsolutionisforhertoslipofftheoriginal route (even ahead of the restriction), and re-allow the use of low-level (i.e., inadmissible in the ordinary setting) roads nearby the restriction. Of course, she still wants to minimize detour costs and drive reasonably in terms of such adjusted scope admissibility. Triple Search. Dynamic changes in our S-Dijkstra’s algorithm, starting from s, are resolved by a detour procedure executed whenever an s-admissible changed edge e=(u,v), i.e. with w(e)<w∗(e), is going to be relaxed.For simplification we assume that there is only one such changed edge e in the whole network. The detour procedure is analogical to ordinary Dijkstra, except that to its single (called live) search it adds two other auxiliary searches called dead and detour. Their roles are as follows: – Live (theoriginal)–runningasinstaticS-Dijkstra,relaxesonlys-admissible edges while using dynamic w∗. Let Q denote its queue of discoveredver- live tices, d its temporary distance estimates, and σ its scope condition live live vector. – Dead – started from the end v of e as if w(e) was not changed. So, initially, Q ={v}andd =d exceptd [v]=d [u]+w(e).Thepurpose dead dead live dead live of Q is to later identify which alternative walks are actualdetours for e. dead – Detour - the core new search started from u. Upon reaching e, it resets σ [u] to 0 on all scope levels ≤ S(e). Then it fills Q with u and detour detour vertices x on the access route from s to u such that a reverse search from u to x does not exhaust σ yet. Note that σ is normally updated detour detour with this reverse search. However, d [x] = d [x] for those added x ∈ detour live Q . detour 1 Note that a designated detour of a road construction may perhaps turn out faster than another previously optimal route. detour(u-admissible) s e dead x u v live(s-admissible) Fig.1.Anillustration ofourdetourprocedure.Uponreachingdynamicallychangede suchthatw∗(e)>w(e);theoriginallivesearchcontinueswrt.w∗ fromalreadyreached vertices except v (solid lines), and two new searches are started – the detour search from u and some of its predecesors (in dashed lines) and the dead search continueing after v wrt. w (dotted area). Thesearchthencontinuesconcurrentlywithallthethreequeues(so,starting turnswilllikelybetakenbyQ ).Everyrelaxationfromoneofthequeuesis detour done as in the static S-Dijkstra’s algorithm, i.e., updating also the appropriate σ• vector. Rules which relate together the three searches are outlined below. Live or Dead. Ourdriver’sdesireistogetbacktoheroriginalrouterepresented by the dead search. This happens when the dead search meets either with the livesearch(no needto bypassthe problematicedgee)orwiththe detour search (a detour is found). For more details (see also Fig. 1), imagine a vertex y ∈ V(G) being relaxed from one of the three queues. – Suppose y is relaxedfrom Q . If d [y]≥d [y] ord [y]≥d [y], live dead live detour live then y is removed from Q or Q , respectively. dead detour – Suppose y is relaxed from Q . If d [y] ≤ d [y] < d [y], then detour dead detour live y is moved from Q (implic. with all its descendants) into Q setting detour live new distance estimate d [y]:=d [y]. live detour – Suppose y is relaxed from Q . If d [y] ≤ d [y] < d [y], then dead detour dead live again, y is moved into Q with new distance estimate d [y]. live detour Notice that whenever Q or Q becomes empty, the other one may also dead detour be removed and the algorithm then continues as original S-Dijkstra. Altogether, the above described Dynamic S-Dijkstra’s Algorithm adds at mostaconstantmultiplicativefactortothecomplexityofstaticS-Dijkstra,and weproposethatusuallythis increaseis onlybyanadditivefactor(the deadand detour searches restricted to a neighbourhood of e). Borrowing Scope in Detour. There is one more specific aspect of the aforemen- tioneddetoursearch.Wenotonlywanttoresetσ [u]uponreachingchanged detour e in the forward direction, but we intend to do the same for σ [v] “back- detour wards”.Informally,wewouldliketoallowlow-levelroadsnotonlytoslipoffthe original route, but also to return to it from a detour. However, this cannot be done simply in a backward search, and so we instead “borrow” a needed scope value for σ . detour Precisely, the detour search is allowed to relax even non-s-admissible edges, keeping track of the limited scope value debt (on each level). This debt must then be repaid “from v” when the detour search meets the dead search (if it is notrepaidinfull, thenthis searchbranchsubsequentlydies).Again,due tolack of space, we omit further details. Multiple Changes. The previous dynamic algorithmmay be extended to handle multiple changededges in w∗, too,as we very briefly outline now.We introduce multiple dead and detour searches, each labeled by a set of all changed edges that affected it. In this view, the original live search is actually the dead search with the empty label. All these concurrent searches are related together by a complex set of rules depending on their label sets (such as, finishing an L-labeled detour of an edge e moves it to the search labeled by L\{e }; etc). We summarize: 1 1 Theorem 4.1. Dynamic S-Dijkstra’s algorithm (uni-directional), for a road network (G,w) dynamically changed to (G,w∗), a scope mapping S, and a start vertex s ∈ V(G), computes a dynamically s-admissible walk from s to every v ∈V(G). This computed walk is optimal in (G,w∗), or in (G,w).2 Ifc denotes thenumberofedges esuchthat w(e)<w∗(e),then thealgorithm runs in time at most O(cid:0)2c·(|E(G)|·|Im(S)|+|V(G)|·log|V(G)|)(cid:1). Even though the factor 2c may look horrible, we believe the actual effect on time complexity is marginal in real-world scenarios with not-so-many dynamic changes (due to typical “locality” of detours). A thorough experimental evalua- tion of the complexity of our algorithm is the subject of ongoing research. 5 Discussion We have outlined the current state of our work on dynamization of the scope- baserouteplanningtechnique[16]forbothunexpectedandpredictable(tosome extend) road network changes. Our approach is aimed at a proper relaxationof scope admissibility when a driver approaches changed road segment, by locally re-allowingnearbyroadsoflowerscopelevel.Atthesametimeweclaimthatthe computed detour minimizes costs and still remains reasonable in terms of scope admissibility. However, formalized algorithm, its complexity analysis, rigorous proof of correctness and most details are omitted due to lack of space. 2 This slick formulation is to handle the (unlikely in practice) situation when the changed network actually contains a shorter route from s to v which may not be found. In a summary, we have shown that a scope-based route planning approach withcellularpreprocessing[16]canbeusednotonlyinstaticbutalsoindynamic road networks. Our immediate future work in this direction will include the following points; – precise definition of dynamic scope admissibility, – adding new edges and positive dynamic changes, – incorporating so called maneuvers, and – experimentally evaluating this dynamic algorithm on real-worldmap data. References 1. EEdsgerDijkstra. Anoteontwoproblemsinconnectionwithgraphs. Numerische Mathematik, 1:269–271, 1959. 2. Kenneth L Cooke and Eric Halsey. The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications, 14(3):493 – 498, 1966. 3. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. Correction to “a formal basis for the heuristic determination of minimum cost paths”. SIGART Bull., 1(37):28–29, 1972. 4. ValerieKing.Fullydynamicalgorithmsformaintainingall-pairsshortestpathsand transitive closure in digraphs. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, pages 81–, Washington, DC, USA, 1999. IEEE Computer Society. 5. Ron Gutman. Reach-based routing: A new approach to shortest path algorithms optimizedforroadnetworks. InProceedings6thWorkshoponAlgorithmEngineer- ing and Experiments (ALENEX), pages 100–111, 2004. 6. DorotheaWagner,ThomasWillhalm,andChristosD.Zaroliagis.Dynamicshortest pathscontainers. Electr. Notes Theor. Comput. Sci.,92:65–84, 2004. 7. Ingrid C. M. Flinsenberg. Route planning algorithms for car navigation. PhD thesis, Technische Universiteit Eindhoven,2004. 8. DorotheaWagner,ThomasWillhalm,andChristosZaroliagis. Geometriccontain- ers for efficient shortest-path computation. J. Exp. Algorithmics, 10, December 2005. 9. AndrewV.GoldbergandChrisHarrelson.Computingtheshortestpath:A*search meets graph theory. In In Proc. 16th ACM-SIAM Symposium on Discrete Algo- rithms, pages 156–165, 2005. 10. PeterSandersandDominikSchultes. Engineeringhighwayhierarchies. InESA’06: Proceedingsofthe14thconferenceonAnnualEuropeanSymposium,pages804–816, London,UK, 2006. Springer-Verlag. 11. DanielDellingandDorotheaWagner. Landmark-basedroutingindynamicgraphs. In Proceedings of the 6th international conference on Experimental algorithms, WEA’07, pages 52–65, Berlin, Heidelberg, 2007. Springer-Verlag. 12. DominikSchultesandPeterSanders. Dynamichighway-noderouting. InWEA’07: Proceedings of the 6th international conference on Experimental algorithms, pages 66–79, Berlin, Heidelberg, 2007. Springer-Verlag. 13. Dominik Schultes. Route Planning in Road Networks. PhD thesis, Karlsruhe University,Karlsruhe, Germany, 2008. 14. Daniel Delling. Engineering and Augmenting Route Planning Algorithms. PhD thesis, Karlsruhe University,Karlsruhe, Germany,2009. 15. Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. A hub-based labeling algorithm for shortest paths in road networks. In Proceedings of the 10th international conference on Experimental algorithms, SEA’11, pages 230–241, Berlin, Heidelberg, 2011. Springer-Verlag. 16. Petr Hlinˇeny´ and Ondrej Moriˇs. Scope-Based Route Planning. In ESA’11: Pro- ceedings of the 19th conference on Annual European Symposium, pages 445–456, Berlin Heidelberg, 2011. Springer-Verlag. arXiv:1101.3182 (preprint). 17. Petr Hlinˇeny´ and Ondrej Moriˇs. Generalized Maneuvers in Route Planning. In MEMICS’11: 7th International Doctoral Workshop, Berlin Heidelberg, 2012. Springer-Verlag. (to appear), arXiv:1107.0798 (preprint).