Finetuning Randomized Heuristic Search For 2D Path Planning: Finding The Best Input Parameters For R* Algorithm Through Series Of Experiments
This work provides incremental improvements for researchers and practitioners in AI path planning by fine-tuning an existing algorithm to enhance its efficiency in 2D environments.
The paper tackles the problem of optimizing input parameters for the R* path planning algorithm by formulating assumptions about parameter bounds and interdependencies, then validating them through extensive experiments to derive heuristic rules for parameter initialization that achieve the algorithm's best performance.
Path planning is typically considered in Artificial Intelligence as a graph searching problem and R* is state-of-the-art algorithm tailored to solve it. The algorithm decomposes given path finding task into the series of subtasks each of which can be easily (in computational sense) solved by well-known methods (such as A*). Parameterized random choice is used to perform the decomposition and as a result R* performance largely depends on the choice of its input parameters. In our work we formulate a range of assumptions concerning possible upper and lower bounds of R* parameters, their interdependency and their influence on R* performance. Then we evaluate these assumptions by running a large number of experiments. As a result we formulate a set of heuristic rules which can be used to initialize the values of R* parameters in a way that leads to algorithm's best performance.