Hardness measures for gridworld benchmarks and performance analysis of real-time heuristic search algorithms |
| |
Authors: | Masataka Mizusawa Masahito Kurihara |
| |
Institution: | 1.Graduate School of Information Science and Technology,Hokkaido University,Sapporo,Japan |
| |
Abstract: | Gridworlds are one of the most popular settings used in benchmark problems for real-time heuristic search algorithms. However,
no comprehensive studies have been published so far on how the difference in the density of randomly positioned obstacles
affects the hardness of the problems. This paper presents two measures for characterizing the hardness of gridworld problems
parameterized by obstacle ratio, and relates them to the performance of the algorithms. We empirically show that the peak
locations of those measures and actual performance degradation of the basic algorithms (RTA* and LRTA*) almost coincide with
each other for a wide variety of problem settings. Thus the measures uncover some interesting aspects of the gridworlds. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |