We describe a heuristic search algorithm that finds a provably optimal solution subject to a specified time interval. While this algorithm is amenable to previous works to retain the specified time interval by changing the value of epsilon during the search, our basic strategy is that node expansion around the starting node is pessimistic (exact search), and we accomplish the approximate exploration of nodes around the goal by increasing epsilon . This strategy is suitable for real-time route finding in automobile navigation systems. We conducted our experiments to clarify the practical features of the algorithm, using a digital map of a commercial automobile navigation system. The resulting advantage is that the estimation of the finishing time of the search is quite accurate, and optimal solutions are produced by making full use of the permissible search time, regardless of different machine performances.
Time-constrained heuristic search for practical route finding
Titel japanisch
Transactions of the Information Processing Society of Japan ; 40 , 11 ; 4021-4029
1999
9 Seiten, 13 Quellen
Aufsatz (Zeitschrift)
Japanisch
ROUTE-FINDING SYSTEM, ROUTE-FINDING METHOD, AND ROUTE-FINDING PROGRAM
Europäisches Patentamt | 2017
|Route-finding system, route-finding method, and route-finding program
Europäisches Patentamt | 2015
|Best Neighbor Heuristic Search for Finding Minimum Paths in Transportation Networks
Transportation Research Record | 1998
|Best Neighbor Heuristic Search for Finding Minimum Paths in Transportation Networks
Online Contents | 1998
|