Path Finding Method Using Pre-search Data

DOI Web Site 3 References
  • Yoshida Ryoma
    Graduate School of Bionics, Computer and Media Science, Tokyo University of Technology
  • Abe Masaki
    School of Media Science, Tokyo University of Technology
  • Watanabe Taichi
    School of Media Science, Tokyo University of Technology

Bibliographic Information

Other Title
  • 事前探索データを用いた経路探索手法

Description

Pathfinding is the calculation of a path from a point to a destination point. The main methods are Dijkstra method and A* algorithm. In these two methods, when a new target point is set outside the current shortest path, the path search needs to be performed again. The path finding method Moving Target D* Lite can find the shortest path fast under such conditions and when changes occur in the map. However, this method is no longer viable when a new starting point is set at a location that is off the current shortest path. In this study, we propose a search method that can calculate a new shortest path faster than the previous method when a new start point or a new goal point is set outside the current shortest path. In the proposed method, the search information by Dijkstra method is recorded as multiple pre-search data, and the optimal pre-search data is adopted from multiple pre-search data . For squares whose cost needs to be updated based on the pre-search data, the cost is saved as an additional movement cost and the search is performed. As a result of verifying this method, we found that it is useful when setting a new starting point at a location that is off the current shortest path for a map that has almost a single path like a mountain road or regular obstacles like a building district.

Journal

References(3)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top