HiTi graph model of topographical road maps in navigation systems
- 23 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In navigation systems, a primary task is to compute the minimum cost route from the current location to the destination. One of the major problems for navigation systems is that a significant amount of computation time is required to find a minimum cost path when the topographical road map is large. Since navigation systems are real time systems, it is critical that the path be computed while satisfying a time constraint. We propose a new graph model named HiTi (hierarchical multi graph model), for efficiently computing an optimal minimum cost path. Based on HiTi graph model, we propose a new single pair minimum cost path algorithm. We empirically show that our proposed algorithm performs far better than the traditional A* algorithm. Further, we empirically analyze our algorithm by varying both edge cost distribution and hierarchical level number of HiTi graphs.Keywords
This publication has 12 references indexed in Scilit:
- The efficient computation of strong partial transitive-closuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient evaluation of traversal recursive queries using connectivity indexPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Path computation algorithms for advanced traveller information system (ATIS)Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Integrating case-based reasoning, knowledge-based approach and Dijkstra algorithm for route findingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Algorithms for searching massive graphsIEEE Transactions on Knowledge and Data Engineering, 1994
- Transitive closure algorithms based on graph traversalACM Transactions on Database Systems, 1993
- Level graphs and approximate shortest path algorithmsNetworks, 1992
- Efficient algorithms for the instantiated transitive closure queriesIEEE Transactions on Software Engineering, 1991
- On the optimality of A∗Artificial Intelligence, 1977
- A note on two problems in connexion with graphsNumerische Mathematik, 1959