In

Paper abstract bibtex

Paper abstract bibtex

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: 0