English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

Hardness Measures for Maze Problems Parameterized by Obstacle Ratio and Performance Analysis of Real-Time Search Algorithms