AAAI Publications, Sixth Annual Symposium on Combinatorial Search

Font Size: 
Planning Paths with Fewer Turns on Grid Maps
Hu Xu, Lei Shu, May Huang

Last modified: 2013-06-19


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.


A*; Theta*; Link*; any-angle path planning; motion planning; minimum-link path; heuristic search

Full Text: PDF