Mobile Robot Navigation on Partially Known Maps using a Fast A Star\n Algorithm Version

Abstract

Mobile robot navigation in total or partially unknown environments is still\nan open problem. The path planning algorithms lack completeness and/or\nperformance. Thus, there is the need for complete (i.e., the algorithm\ndetermines in finite time either a solution or correctly reports that there is\nnone) and performance (i.e., with low computational complexity) oriented\nalgorithms which need to perform efficiently in real scenarios. In this paper\nwe evaluate the efficiency of two versions of the A star algorithm for mobile\nrobot navigation inside indoor environments with the help of two software\napplications and the Pioneer 2DX robot. We demonstrate that an improved version\nof the A star algorithm (we call this the fast A star algorithm) which (a\ndifferent version of this algorithm is widely used in video games) can be\nsuccessfully used for indoor mobile robot navigation. We evaluated the two\nversions of the A star algorithm first, by implementing the algorithms in\nsource code and by testing them on a simulator and second, by comparing two\noperation modes of the fast A star algorithm w.r.t. path planning efficiency\n(i.e., completness) and performance (i.e., time need to complete the path\ntraversing) for indoor navigation with the Pioneer 2DX robot. The results\nobtained with the fast A star algorithm are promising and we think that this\nresults can be further improved by tweaking the algorithm and by using an\nadvanced sensor fusion approach (i.e., combine the inputs of multiple robot\nsensors) for better dealing with partially known environments.\n