The A-r-Star (Ar) Pathfinder

This paper presents a variant of the A-Star (A^*) pathfinder for robot path planning calledA_r^* (pronounced A-r-Star)and demonstrates that the A_r^*algorithm outperforms A^* in a uniformly gridded sparse world and gives performance matching that of A^* in a uniformly gridded cluttered world. This algorithm is simple to implement and understand. It alsohighlights the performance advantages of theA_r^*algorithm and proves its properties experimentally and analytically (where appropriate). Some challenges affecting the performance of A_r^*have been presented and some solutions to these challenges have been developed and implemented. The performance of A_r^*has been compared toA^*running on both uniform and multi-resolution grids of different world scenarios. Results show that on a sparse high-resolution uniform grid worldA_r^*'s search speed scales well and it outperforms A^* by an exponential factor.