A Novel Heuristic Emergency Path Planning Method Based on Vector Grid Map

Bowen Yang, Jin Yan, Zhi Cai, Zhiming Ding, Dongze Li, Yang Cao, Limin GuoISPRS Int. J. Geo Inf 2021 · DOI

TL;DR

This paper introduces a novel heuristic emergency path planning method (EGEPP) that addresses the challenges of dynamic urban road networks during emergencies. By employing a situational grid road network model and a heuristic search algorithm, it aims to find optimal detour paths that minimize travel time, even in congested conditions.

What Problem Does This Paper Address?

Emergency situations, such as accidents or natural disasters, can drastically alter urban road network conditions, leading to severe congestion and rendering traditional static path planning methods ineffective. Existing approaches often struggle with the dynamic nature of these networks, failing to account for real-time traffic changes and the need for rapid detours. This paper tackles the problem of efficiently planning emergency detour paths in a dynamic, situation-aware manner, ensuring vehicles can bypass congested areas and reach their destinations as quickly as possible.

Methods

The paper proposes an Equidistant Grid Emergency Path Planning (EGEPP) framework. Key components include:

  • Situational Grid Road Network Model (SGRN): This model represents the road network with spatio-temporal characteristics, allowing it to adapt to dynamic changes in road conditions.
  • Dynamic Grid PageRank (DGPR): An improved PageRank algorithm that sorts grids based on real-time traffic capacity (road network speed), assigning different grade values to each grid.
  • Situational Grid Heuristic Search (SGHS*) Algorithm: This algorithm plans detour paths by considering sorted grids and a time-based heuristic function. It incorporates a pruning strategy to optimize search efficiency.
  • Graph Acceleration Algorithms (SCH, SGCH, SGMRCH): Three algorithms designed to accelerate path planning by contracting the road network graph, reducing the number of vertices to search.

Datasets

  • Beijing City Road Network: Extracted from OpenStreetMap, processed to contain 83,884 vertices and 222,778 directed edges.
  • Vehicle Trajectory Data: Approximately 500GB of data used for experiments.

Key Insights and Ideas

  • Dynamic Road Network is Crucial: The paper strongly emphasizes that static road network weights are insufficient for emergency path planning due to the unpredictable nature of traffic during emergencies.
  • Grid-Based Approach for Situational Awareness: Dividing the city into a grid allows for localized analysis and adaptation to changing road conditions within specific areas.
  • DGPR for Real-Time Ranking: The DGPR algorithm's ability to dynamically rank grids based on real-time road speed is a significant improvement over static ranking methods.
  • Heuristic Search with Pruning for Efficiency: The SGHS* algorithm's combination of heuristic search and a pruning strategy effectively balances finding optimal paths with computational efficiency.
  • Graph Acceleration for Scalability: The proposed graph contraction algorithms (SCH, SGCH, SGMRCH) are essential for handling large road networks and improving the overall performance of the path planning system.

Key Results

  • Improved Detour Paths: The EGEPP framework, particularly with SGHS + SGCH and SGHS + SGMRCH, demonstrated better detour path planning compared to the GMEPP framework in emergency scenarios.
  • Reduced Travel Time: In congested conditions, the SGHS algorithm significantly reduced vehicle travel time compared to other algorithms like Dijkstra, A, and RTA. For example, on a 49.8 km path, SGHS achieved 98.7 min, while Dijkstra took 133.8 min.
  • Faster Convergence: The DGPR algorithm showed a higher convergence rate than the traditional GPR algorithm.
  • Efficiency Gains with Graph Acceleration: The graph acceleration algorithms (SGCH and SGMRMCH) significantly improved the running efficiency of path planning, especially for longer paths. For instance, with a path length of 26km, SGHS* + SGMRCH achieved a search time of 38.6ms, compared to 88.4ms without acceleration.
  • Optimal Query Time Window: The study suggests an optimal query time window of Tq = 15 minutes for path planning.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that when the query time window is too small (e.g., < 15 min), repeated path planning searches are needed.
  • When the query time window is too large (> 15 min), the algorithm might explore congested areas.
  • The current model primarily focuses on road speed and doesn't explicitly consider factors like road slope or maximum vehicle carrying capacity.
  • Future Work:
    • Investigate the impact of situational information on road network weights, such as road slope and maximum vehicle carrying capacity.
  • Further explore the influence of related factors between passing vehicles on urban road networks on path planning.
  • Continue to refine the EGEPP framework and its components.

Summary updated

BibTeX
@article{yang2021novel,
  author = {Bowen Yang and Jin Yan and Zhi Cai and Zhiming Ding and Dongze Li and Yang Cao and Limin Guo},
  title = {{A Novel Heuristic Emergency Path Planning Method Based on Vector Grid Map}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2021},
  doi = {10.3390/ijgi10060370},
}
Figure