Strict Theta*: Shorter Motion Path Planning Using Taut Paths. Oh, S. & Leong, H. W. In
Strict Theta*: Shorter Motion Path Planning Using Taut Paths [link]Paper  abstract   bibtex   1 download  
A common way to represent dynamic 2D open spaces in robotics and video games for any-angle path planning is through the use of a grid with blocked and unblocked cells. The Basic Theta* algorithm is an existing algorithm which produces near-optimal solutions with a running time close to A* on 8-directional grids. However, a disadvantage is that it often finds non-taut paths, by making unnecessary turns. In this paper, we demonstrate that by restricting the search space of Basic Theta* to taut paths, the algorithm will, in most cases, find much shorter paths than the original. We describe two novel variants of the Theta* algorithm, which are simple to implement and use, yet produce a remarkable improvement over Basic Theta* in terms of path length, with a very small running time trade-off. Another side benefit is that almost all paths found will be taut, which makes more convincing paths.
@inproceedings {icaps16-26,
    track    = {​Main Track},
    title    = {Strict Theta*: Shorter Motion Path Planning Using Taut Paths},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13049},
    author   = {Shunhao Oh and  Hon Wai Leong},
    abstract = {A common way to represent dynamic 2D open spaces in robotics and video games for any-angle path planning is through the use of a grid with blocked and unblocked cells. The Basic Theta* algorithm is an existing algorithm which produces near-optimal solutions with a running time close to A* on 8-directional grids. However, a disadvantage is that it often finds non-taut paths, by making unnecessary turns. In this paper, we demonstrate that by restricting the search space of Basic Theta* to taut paths, the algorithm will, in most cases, find much shorter paths than the original. We describe two novel variants of the Theta* algorithm, which are simple to implement and use, yet produce a remarkable improvement over Basic Theta* in terms of path length, with a very small running time trade-off. Another side benefit is that almost all paths found will be taut, which makes more convincing paths.},
    keywords = {Planning activities; motions and paths}
}

Downloads: 1