Any-angle path planning on non-uniform costmaps

Abstract

A* on grid maps generates a path with zig-zag pattern, but Theta* is known to be free from this disadvantage. Theta* assumes that cost of each cell, cell-cost, is uniform, but non-uniform costs are effective ways to represent traversability on grid maps. Theta* does not work on non-uniform costmaps. In this paper, we generalize Theta* toward non-uniform costmaps. To extend Theta*, we propose two kinds of cost functions considering non-uniform cell-costs. The first function adopts the arithmetic mean under the assumption that all cells contribute equally to the overall cost. The second function uses the weighted mean by considering the true traversal length on each cell. We applied the proposed methods to two types of maps: synthetic and real maps. An experiment on synthetic maps quantifies performance of the two methods in terms of accuracy and computing time. The other experiment on real maps presents the effectiveness of Theta* with the proposed methods. The generalized Theta* generated the least-cost path compared with the original Theta* and A* on non-uniform costmaps.