Hierarchical path computation approach for large graphs

Ramesh Rajagopalan, Kishan G. Mehrotra, Chilukuri K. Mohan, Pramod K. Varshney

Research output: Contribution to journalArticle

24 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)427-440
Number of pages14
JournalIEEE Transactions on Aerospace and Electronic Systems
Volume44
Issue number2
DOIs
StatePublished - Apr 1 2008

Keywords

  • Aerodynamics
  • Complexity theory
  • Computational modeling
  • Heuristic algorithms
  • Joining processes
  • Partitioning algorithms
  • Path planning

ASJC Scopus subject areas

  • Aerospace Engineering
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Hierarchical path computation approach for large graphs'. Together they form a unique fingerprint.

  • Cite this