Planning Paths with Fewer Turns on Grid Maps

Proceedings of the International Symposium on Combinatorial Search, 6

Volume

Vol. 6 No. 1 (2013): Sixth Annual Symposium on Combinatorial Search

Full Papers

In this paper, we consider the problem of planning any-angle paths with small numbers of turns on grid maps. We propose a novel heuristic search algorithm called Link* that returns paths containing fewer turns at the cost of slightly longer path lengths. Experimental results demonstrate that Link* can produce paths with fewer turns than other any-angle path planning algorithms while still maintaining comparable path lengths. Because it produces this type of path, artificial agents can take advantage of Link* when the cost of turns is expensive.

10.1609/socs.v4i1.18298