This research essay and literature review investigates some of the gateways to path finding in static and dynamic networks that are listed in present research literature. A selected set of different approaches are highlighted and set in a broader context, illustrating the various aspects of path finding in static and dynamic networks. It is shown that the A* algorithm is the dominant algorithm for solving fastest path problems. A further attempt is made to draw attention to the advances that have been made in path finding in the field of robotics, in order to establish a lateral relation that can form the basis of further exploration and fruitful merger of the two research fields.
Introduction
Euler’s famous “Königsberg bridge” question, dating back as far as 1736, is often seen as the starting point of modern path finding – was it possible to find a path through the city crossing each of its seven bridges once and only once and then returning to the origin? His methods formed the basis of what is now known as graph theory, and which in turn paved the way for path finding algorithms.
The author’s interest in this subject stems from his lifelong experiences in long–distance road travelling, where successful route planning prior to travelling and en-route is essential to finding the optimal path from origin to destination. “Optimal” can take up many forms, such as shortest time, shortest distance, or least total cost, the latter being of major concern in some parts the author’s home country, where travelling by car may mean many costly ferry crossings and expensive toll roads in order to get from one’s departure to one’s arrival.
Semantically one can distinguish between path finding in a fixed static network, with set costs for traversing the network, and path finding in a dynamic network, where the cost of traversing the network varies over the time of traversing.
Because path finding is applicable to many kinds of networks, such as roads, utilities, water, electricity, telecommunications and computer networks alike, the total number of algorithms that have been developed over the years is immense. The aim of this essay is to compromise a selected cross-section of approaches towards path finding and the related fields of research, such as transportation GIS, network analysis, operations research, artificial intelligence and robotics, to mention just a few examples where path finding theories are employed.
It is this author’s deliberate intention to use a wide approach to show the different research gateways that lead towards path finding in dynamic networks. This is done in order to find a common denominator that will allow a unifying approach. Using a fitting network analysis metaphor, this can be described as “breadth first search”.
Intelligent Transportation Systems
In the recent decades road transportation systems have undergone considerable increase in complexity and congestion proclivity. This then has given rise to the field of ITS, Intelligent Transport Systems, with the goal to apply and merge advanced technology to make transportation more safe and efficient, with less congestion, pollution and environmental impact. In working towards this goal, ITS can take many different forms.
Vehicle location and navigation systems are one of these forms and have come along with the emerging field of transport telematics. Transport telematics implies the large-scale integration and implementation of telecommunication and informatics technology in the field of transportation, penetrating all areas and modes of transport, the vehicles, the infrastructure, the organisation and management of transport.
Zhao (1997) distinguishes between route planning and route guidance as two key elements in vehicle location and navigation systems as part of ITS. Route planning is the process that helps vehicle drivers plan a route prior to driving a specific part of his or her journey. Route guidance is the real-time process of guiding the driver along the route generated by a route planner.
Huang et al. (1995) discriminates route guidance even further, distinguishing between centralised and decentralised route guidance. In the former, vehicles conduct their own path finding using on-board computers and static road maps in CD-ROMs, and applying heuristic search algorithms. Centralised route guidance relies on traffic management centres (TMC) to answer path queries submitted by vehicles linked to it. In this case, Huang et al. (1995) describe a central server holding a materialised view of all shortest paths at that given time, accessed by lookup requests from the vehicles equipped with this system. Although not explicitly stated, it can be assumed that this also is the case in the Advanced Traveller Information System (ATIS) detailed by Shekar and Fetterer (1996a) or the ADVANCE project portrayed by both Revels (1998) and Zhao (1997). Boyce et al. (1997) provide a detailed evaluation study of the ADVANCE project for further reference.
Shortest Path Algorithms
The analysis of transportation networks is one of many application areas in which the computation of shortest paths is one of the most fundamental problems. These have been the subject of extensive research for many years: Deo (1984), Cherkassky et al. (1993), Zhan et al. (1996 and 1997).
A network consists of arcs, or links, and nodes. The fastest path is calculated as a function associated with the cost of travelling the link. Even though the different research literature tends to group the types of shortest paths problems slightly different, one can discern, in general, between paths that are calculated as one-to-one, one-to-some, one-to-all, all-to-one, or all-to-all shortest paths. In software packages solving static network shortest path problems the software usually aggregates a once-off all-to-all calculation for all nodes, from which subsequent routes then are derived.
Clearly, this approach is not feasible for dynamic networks, where the travel cost is time-dependent or randomly varying. However, the majority of published research on shortest paths algorithms has dealt with static networks that have fixed topology and fixed costs. A few early attempts on dynamic approaches, referenced by Chabini (1997), are Cooke and Halsey (1966) and Dreyfus (1979). Given the computational restraints in the capacity of past computer systems this is not surprising. Not more than a decade ago, Van Eck (1990) reports several hours as an average time for a computer to churn through an all-to-all calculation on a 250-nodes small-scale static network, and several days on a 16.000-nodes large-scale network.
One way of dealing with dynamic networks is splitting continuous time into discrete time intervals with fixed travel costs, as noted by Chabini (1997). Thus, understanding shortest path algorithms in static networks becomes fundamental to working with dynamic networks.
Shortest paths in static networks
Several algorithms and data structures for algorithms have been put forward since the classic shortest path algorithm by Dijkstra (1959). In its modified version, this algorithm computes a one-to-all path in all directions from the origin node and terminates when the destination has been reached. Deonardo and Fox (1979) introduce a new data structure of reaching, pruning and buckets.
The original Dijkstra algorithm explores an unnecessary large search area, which led to the development of heuristic searches, among them the A* algorithm, that searches in the direction of the destination node. This avoids considering directions with non- favourable results and reduces computation time.
A significant improvement is seen in the bi-directional search, computing a path from both origin and destination, and ideally meeting at the middle. In relation to this search technique, it should be remarked that Jacob et al. (1998) discard bi-directional algorithms as impractical in their computational study of routing algorithms for realistic transportation networks. Firstly, as not extendable to general path problems and secondly, as having a run-time notably longer than A*.
Zhan and Noon (1996) undertake a comprehensive study of shortest path algorithms on 21 real road networks from different 10 different states in the U.S., with networks ranging from 1600/500 to 93000/264000 nodes/arcs. In this study, Dijkstra-based algorithms, however differing in data structure, outperform other algorithms in one-to-one or one-to-all fastest path problems.
In summary, the A* algorithm, along with Dijkstra-based algorithms, are preferred in most of the literature researched by the author the author. It is in fact noteworthy that the Dijkstra algorithm has prevailed to the present date, proving its universal validity.
Shortest paths in dynamic networks
It is a result of the recent advances in computer and communications technology, together with the developments in ITS, that have flared a renewed interest in dynamic networks. This interest in the concept of dynamic management of transportation has also brought forward a set of algorithms that are particularly aimed at optimising the run-time of computations on large-scale networks.
Chabini (1998) lists the following types of dynamic shortest path problems depending on (a) fastest versus minimum cost (or shortest) path problems; (b) discrete versus continuous reperentation of time; (c) first-in-first-out (FIFO) networks versus non-FIFO networks, in which a vehicle departing at a later time than a previous vehicle can arrive at the destination before the pervious vehicle; (d) waiting is allowed at nodes versus waiting is not allowed; (e) questions asked: one-to-all for a given departure time or all departure times, and all-to-one for all departure times; and (f) integer versus real valued link travel costs.
Fu and Rilett (1996) investigate what they call the dynamic and stochastic shortest path problem by modelling link travel times as a continuous-time stochastic process. The aim of their research was to estimate travel time for a particular path over a given time period. They deviate from the mainstream appraisal of the A* algorithm and advocate the k-shortest path. The reason for this is that standard shortest path algorithms may fail to find the minimum expected paths, particularly when dealing with non-linear optimisation, as is the case in developing travel time estimation models. However, in lieu of real data, their research is based on a hypothetical change pattern in travel time.
Building on the research from path finding algorithms in static networks, Chabini (1997) remarks that a time-space expansion representation can be used in dynamic networks, applying discrete time intervals with fixed costs. Hence, depending on how time is treated, dynamic shortest path problems can be subdivided into two types: discrete and continuous. In the discrete case, if using 15-second time intervals, a full 24-hour implementation would involve calculations on 5760 time discretisations, multiplied with the number of nodes and links. Chabini (1997) makes a distinct separation between fastest time paths, in which the cost of a link is the travel time of that link, and minimum cost paths, in which link costs can be of a general form. The difference between these two is nonetheless not explored until Chabini (1998).
Chabini (1997) identifies two key questions in dynamic path finding: (1) what are the fastest paths from one origin to all destinations departing at a given time, and (2) what are the fastest paths from all nodes to one destination for all departure times. He sees the latter as the most significant in relation to ITS, which is true, if one assumes that ITS aims at finding the best path for multiple vehicles with the same destination. In Chabini (1998) the focus extends slightly, now three questions are put forward: (1) one-to-all fastest path at a given time interval, (2) all-to-one fastest path for all departure times and (3) all-to-one minmum cost path for all departure time intervals.
Chabini (1997, 1998) places emphasis on the all-to-one minimum cost path as the key algorithm with relation to ITS, the reason being that only a limited set of all network nodes are destination nodes in realistic road networks, while there is a considerably larger number of nodes that will be origin nodes. (Moving vehicles tend more to converge to the same goal than to spread in all directions)
Horn (1999) continues along the research trails of Chabini (1997) and Fu and Rilett (1996), but uses a less detailed articulation of travel dynamics, reflecting as he puts it, the recognition that information about network conditions in most parts of the world are most likely to be sparse and that merely estimates of average speed on individual network links are available in most cases. With the presumption that these estimates allow for variation in speed, congestion and delays at nodes, he studies a number of Dijkstra variant algorithms that address these particular conditions. Most important, he propounds an algorithm that calculates an approximation of shortest time path travel duration (path travel time), independent of the particular navigation between nodes. For an experienced vehicle driver, estimated travel time may be more important than the exact route that is to follow. This is a noteworthy addition to the fastest path algorithms in dynamic networks.
Related research: robotics
Taking into account Chabini (1998), who noted that the literature on dynamic shortest path problems seems to be quite limited, the author of this paper investigated an intriguing sidetrack, namely path finding within the field of robotics. Robots, or autonomous or remotely operated vehicles, must perform in both known and unknown environments. Finding a path through uncertain terrain is similar to path finding in dynamic networks.
Haigh et al. (1994, 1995, 1997) uses case-based reasoning and the accumulation and reuse of previously traversed routes as main entry point to optimal path finding. Here, the A* algorithm in combination with analogical reasoning is seen as the most robust framework for route planning that can adapt to incomplete information and changing conditions (Haigh et al., 1997). Other heuristic searches (i.e. hill-climbing) are discarded as prone to failure in unexpected situations.
Stentz (1994, 1995) takes the A* algorithm further, by modifying it into what he calls D* (Dynamic A*). His works focus on moving a robot equipped with an innate map through a field of unknown obstacles, and revising the map and re-planning the route as obstacles are encountered.
With reference to ITS and dynamic path finding, the “unknown obstacles” in Stentz’ work can be circumscribed as the arbitrary or time-dependent changing of link costs, thus providing a link for transferral of knowledge between these research fields.
Discussion
It is noteworthy that the heuristic A* algorithm dominates the research literature for static networks.
Almost all comparison studies involving the A* algorithm conclude with this algorithm’s superiority over other approaches. Dijkstra-based algorithms, with various enhancements in their data structure in the form of heaps, buckets and queues, are also well represented.
Research has also proven that dynamic network fastest path problems can be reduced to static fastest path problems if continuously varying link travel times are expanded for a time interval or given an estimated value. The A* and Dijkstra algorithms are applicable in both static and dynamic networks.
Finding fastest paths in dynamic networks as part of ITS and in the route re-planning module as part of robotics appear to have seemingly diverging approaches. In the former the emphasis is on assembling and conveying as much real and updated information as possible. The latter starts off with some, but not necessary all information. Here, by applying analogy, user-dependent preferences and experiences can be incorporated into route planning or guidance systems.
Particularly in the case of Advanced Traveller Information Systems, there will be a considerable amount of repetitive day-to-day travelling and commuting. The experience and knowledge of these traffic patterns ought to be fed back into the system and used as a knowledge database, providing a basis for analogical reasoning, which is fundamental to Haigh’s papers.
The author believes that establishing a lateral relation between robotics and ITS can form the basis of further exploration and fruitful merger of the two research fields.
Future outlook
This essay attempted to investigate some of the approaches to path finding in static and dynamic networks that are listed in present research literature. A selected set of different approaches were highlighted and set in a broader context, illustrating the various aspects of path finding in time-dependent dynamic environments.
The author is fully aware that not all relevant research has been covered, but believes that the approach provided in this paper can provide a starting point for transferral of knowledge and research between ITS and robotics. Interestingly enough, relevant research literature exploring this specific topic has not been found to date. Consequently, this possible link between ITS and robotics suggests a promising area for future research.
In such, this paper is meant as a potential framework for the development of a lateral methodology in conjunction with the author’s MSc Thesis.
Acknowledgements
The investigation for this research essay has not been an easy task. The University of Leicester is not renown for it’s advances in Transportation and Operations Research, and thus, most of the much literature had to be obtained by making use of the total limited number of inter-library loans, by accessing online publications, searching via internet databases, posting in mailing lists and user groups, by visiting other libraries in person and via personal communication with the various authors of the papers referenced in this essay. This has been a frustrating and time-consuming process, and the investigation has not been as full and elaborate as the author himself had hoped for initially. Nevertheless it has been a rewarding and learning process, sparking the motivation for his prospective future work. The author wishes to express his sincere gratitude and appreciation to all those who in large or small contributed to the successful completion of this paper.
References
Boyce, D. E. et al (1997) Dynamic route choice model of large-scale traffic network, Journal of Transportation Engineering, vol. 123, no. 4, pp. 276-282
Burrough, P.A. and McDonell, R.A. (1998) Principles of Geographic Information Systems, Ch.7, pp.180-181
Chabini, I. (1998) Discrete dynamic shortest path problems in transportation applications, Transportation Research Record 1645
Chabini, I. (1997) A new algorithm for shortest paths in discrete dynamic networks, as presented at 8th IFAC/IFIP/IFORS Symposium on transportation systems, Tech Univ Crete, Greece, 16-18 June 1997
Cherkassky, B., Goldberg, A. and Radzik, T. (1993) Shortest paths algorithms: theory and experimental evaluation, Technical Report 93-1480, Department of Computer Science, Stanford University, 1993.
Chou, Y. H. (1997) Exploring Spatial Analysis in Geographic Information Systems, Ch.7, pp. 215-264
Cooke, K.L. and Hasley E. (1966) The shortest route through a network with time-dependent intermodal transit times, Journal of Mathematical Analysis and Applications, vol. 14, pp. 493-498
Deo, N. and Pang, C.-Y. (1984) Shortest path algorithms: taxonomy and annotation, Networks, vol. 14, pp. 275-323
Deonardo, E. and Fox, B. L. (1979) Shortest-route methods: 1. Reaching. Pruning and buckets, Operations Research, vol. 27, pp. 161-196
Dijkstra, E. W. (1959), A note on two problems in Connection with graphs, Numerische Mathematik, vol. 1, 1959, pp. 269-271
Dolan, A. and Aldous, J. (1993) Introduction to Networks and Algorithms, Ch. 7, Ch. 8, Ch 18
Dreyfus, S.E (1969) An appraisal of some shortest path algorithms, Operations Research, vol. 17, pp. 395-412
Fu, L. and Rilett, L.R.(1996) Expected shortest paths in dynamic and stochastic traffic networks, Transportation Research, Part B: Methodological, vol. 32, no. 7, pp. 499-516
Haigh, K. Z. , Shewchuk,J.R. and Veloso, M. (1994) Route planning and learning from execution. Working notes from the AAAI Fall Symposium “Planning and Learning: On to Real Applications”, AAAI Press, November, 1994, pp. 58 – 64.http://www.ri.cmu.edu/pubs/pub_2922.html
Haigh, K. Z. and Veloso, M. (1995) Route planning by analogy
Case-Based Reasoning Research and Development, Proceedings of ICCBR-95, Springer-Verlag, October, 1995, pp. 169 – 180 http://www.ri.cmu.edu/pubs/pub_2921.html
Haigh, K. Z. , Shewchuk,J.R. and Veloso, M. (1997) Exploiting Domain Geometry in Analogical Route PlanningJournal of Experimental and Theoretical Artificial Intelligence, No. 9, September, 1997, pp. 509 – 541http://www.ri.cmu.edu/pubs/pub_2921.html
Horn, M. E. T. (1999) Efficient modeling of travel in networks with time-varying link speeds, CSIRO Mathematical and Information Sciences Technical Report CMIS 99/97 http://www.cmis.csiro.au/Mark.Horn/
Huang, Y.-W. Jing, N., Rundensteiner, E. (1996) Path view algorithm for transportation networks: The dynamic reordering approach, ITS RCE Center, Technical Report, June 1995 ftp://ftp.eecs.umich.edu/people/rundenst/papers/r-95-14.ps
Jacob, R., Marathe, M. V. and Nagel, K. (1998) A computational study of routing algorithms for realistic transportation networks, 2nd Workshop on Algorithmic Engineering (WAE’98), Saarbrücken, Germanz, August 19-21 1998, received via personal communication
Jones, C. (1998) Geographical Information Systems and Computer Cartography, Ch. 13, pp. 225-230
Liu, B. et al. (1994) Integrating case-based reasoning, knowledge-based approach and Dijkstra algorithm for route finding. Proceedings of the Tenth Conference on Artificial Intelligence for Applications, pp. 149-55
Openshaw, S. and C. (1997) Artificial intelligence in geography, Ch. 6, pp. 55-72, John Wiley and Sons
Revlels, B.M. (1998) The ADVANCE Project – A Dynamic Route Guidance Case Study http://www.people.virginia.edu/~bmr8n/ITSPaper/advance.htm
Shekhar, S., Fetterer, A. and Liu, D.-R. (1996) Genesis: An approach to data dissemination in Advanced Traveler Information Systems, Bulletin of the Technical Committee on Data Engineering, September 1996, vol. 19, no. 3, pp.
Shekhar, S. and Fetterer, A. (1996) Path computation in Advanced Traveler Information Systems, Proceedings of the 6th Annual Meeting and Exposition of the Intelligent Transportation Society of America, Houston, Texas, August 15-18, 1996
Stentz, A. (1994) The D* Algorithm for real-time planning of optimal traverses, Tech Report CMU-RI-TR-94-37, Robotics Institute, Carnegie Mellon University, October 1994 http://www.ri.cmu.edu/pubs/pub_356.html
Stentz, A. (1995) The Focussed D* Algorithm for real-time planning of optimal traverses, Proceedings of the International Joint Conference on Artificial Intelligence, August, 1995. http://www.ri.cmu.edu/pubs/pub_1213.html
Stentz, A. (1993) Optimal and efficient path planning for unknown and dynamic environments,Tech Report CMU-RI-TR-93-20, Robotics Institute, Carnegie Mellon University, August 1993 http://www.ri.cmu.edu/pubs/pub_310.html
Van Eck, J. R. and De Jong, T. (1990), Adapting datastructures and algorithms for faster transport network computations, Proceedings of the 4th int. symposium on spatial data handling, vol.1, pp. 295-304
Zhan, F. B. (1997) Three fastest shortest path algorithms on real road networks: Data structures and procedures, Journal of Geographic Information and Decision Analysis, vol.1, no.1, pp. 69-82 http://publish.uwo.ca/~jmalczew/gida_1/Zhan/Zhan.htm
Zhan, F. B. and Noon, C. E. (1996) Shortest Path Algorithms: An Evaluation using Real Road Transportation Science vol. 32, no. 1, pp. 65-73
Zhao, Y. (1997) Vehicle Location and Navigation Systems, Ch. 5 – 6, Ch. 10 – 12, Artech House Inc, Norwood, MA http://birch.dlut.edu.cn/~yzhao/
Related
- husdal.com: Shortest path finding: a comparison
