Improving efficiency in any-angle path-planning algorithms
Pablo Muñoz, Maria Rodriguez-Moreno · 2012
Searching for optimal paths over grids has been widely discussed using search algorithms such as A*. It is an efficient but restricted to artificial heading changes method. Lately, some algorithms have tried to obtain better paths, such as A* Post Smoothed or Theta*. These two variants of A* get an any-angle path avoiding its main limitation but at the expense of an increment in the computational cost. In this paper we propose two contributions. First, we introduce a new parameter that can help us to compare path-planning algorithms under a different view, not only time and expanded nodes. Second, a new heuristic function that allows us to guide the process towards the objective, improving the computational cost of the search. Results show that our algorithm gets better runtime and memory usage than the others.