障害物密度に応じた迷路探索問題の難易度指標と実時間探索アルゴリズムの性能解析

概要

論文の詳細を見る
Although the maze (or gridworld) is one of the most widely used benchmark problems for real-timesearch algorithms, it is not sufficiently clear how the difference in the density of randomly positioned obstaclesaffects the structure of the state spaces and the performance of the algorithms. In particular, recent studiesof the so-called phase transition phenomena that could cause dramatic change in their performance in arelatively small parameter range suggest that we should evaluate the performance in a parametric way withthe parameter range wide enough to cover potential transition areas.In this paper, we present two measures for characterizing the hardness of randomly generated mazesparameterized by obstacle ratio and relate them to the performance of real-time search algorithms. The firstmeasure is the entropy calculated from the probability of existence of solutions. The second is a measurebased on total initial heuristic error between the actual cost and its heuristic estimation. We show thatthe maze problems are the most complicated in both measures when the obstacle ratio is around 41%.We then solve the parameterized maze problems with the well-known real-time search algorithms RTA*,LRTA*, and MARTA* to relate their performance to the proposed measures. Evaluating the number ofsteps required for a single problem solving by the three algorithms and the number of those required for theconvergence of the learning process in LRTA*, we show that they all have a peak when the obstacle ratio isaround 41%. The results support the relevance of the proposed measures. We also discuss the performanceof the algorithms in terms of other statistical measures to get a quantitative, deeper understanding of theirbehavior.
人工知能学会の論文
2006-11-01

障害物密度に応じた迷路探索問題の難易度指標と実時間探索アルゴリズムの性能解析

スポンサーリンク

概要

著者

関連論文

スポンサーリンク