Learning Heuristic A*: Efficient Graph Search using Neural Network

Authors
Soonkyum KimByungchul An
Issue Date
2020-05
Publisher
IEEE
Citation
2020 IEEE International Conference on Robotics and Automation (ICRA), pp.9542 - 9547
Abstract
In this paper, we consider the path planning problem on a graph. To reduce computation load by efficiently exploring the graph, we model the heuristic function as a neural network, which is trained by a training set derived from optimal paths to estimate the optimal cost between a pair of vertices on the graph. As such heuristic function cannot be proved to be an admissible heuristic to guarantee the global optimality of the path, we adapt an admissible heuristic function for the terminating criteria. Thus, proposed Learning Heuristic A* (LHA*) guarantees the bounded suboptimality of the path. The performance of LHA* was demonstrated by simulations in a maze-like map and compared with the performance of weighted A* with the same suboptimality bound.
Keywords
Path Planning; Neural Network; Graph Search
ISSN
1050-4729
URI
https://pubs.kist.re.kr/handle/201004/77932
DOI
10.1109/ICRA40945.2020.9197015
Appears in Collections:
KIST Conference Paper > 2020
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML

qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE