Hierarchical path computation approach for large graphs
Authors:
- 15 July 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Aerospace and Electronic Systems
- Vol. 44 (2) , 427-440
Abstract
Time is a critical factor in several path planning problems such as flood emergency rescue operations, escape planning from fires and chemical warfare agents dispersed in large buildings, evacuation from urban areas during natural disasters such as earthquakes, and military personnel movement. We propose a hierarchical path planning algorithm (HIPLA) for real time path planning problems where the computational time is of critical significance. The main idea of HIPLA is to significantly reduce the search space for path computation by searching in a high-level abstraction graph, whose nodes are associated with precomputed risk estimates. The cumulative risk associated with all nodes along a path determines the quality of a path. We present a detailed experimental analysis of HIPLA by comparing it with two well-known approaches viz., shortest path algorithm (SPAH) [1] and Dijkstra's algorithm with pruning [2] for large node-weighted graphs.Keywords
This publication has 15 references indexed in Scilit:
- Geometric containers for efficient shortest-path computationACM Journal of Experimental Algorithmics, 2005
- Experimental Evaluation of a New Shortest Path Algorithm2002
- Hierarchical encoded path views for path query processing: an optimal model and its performance evaluationIEEE Transactions on Knowledge and Data Engineering, 1998
- An Incremental Algorithm for a Generalization of the Shortest-Path ProblemJournal of Algorithms, 1996
- On the computational complexity of dynamic graph problemsTheoretical Computer Science, 1996
- Hierarchical optimization of optimal path finding for transportation applications1996
- Effective graph clustering for path queries in digital map databases1996
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Problem Decomposition and Data Reorganization by a Clustering TechniqueOperations Research, 1972
- A note on two problems in connexion with graphsNumerische Mathematik, 1959