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]](https://bibbase.org/img/filetypes/link.svg "link")
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
{"_id":"FWwZ4Rz87FJ2nCQ7Y","bibbaseid":"oh-leong-strictthetashortermotionpathplanningusingtautpaths","downloads":1,"creationDate":"2016-03-09T03:04:32.914Z","title":"Strict Theta*: Shorter Motion Path Planning Using Taut Paths","author_short":["Oh, S.","Leong, H. W."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","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":[{"firstnames":["Shunhao"],"propositions":[],"lastnames":["Oh"],"suffixes":[]},{"firstnames":["Hon","Wai"],"propositions":[],"lastnames":["Leong"],"suffixes":[]}],"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","bibtex":"@inproceedings {icaps16-26,\r\n track = {Main Track},\r\n title = {Strict Theta*: Shorter Motion Path Planning Using Taut Paths},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13049},\r\n author = {Shunhao Oh and Hon Wai Leong},\r\n 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.},\r\n keywords = {Planning activities; motions and paths}\r\n}\r\n\r\n","author_short":["Oh, S.","Leong, H. W."],"key":"icaps16-26","id":"icaps16-26","bibbaseid":"oh-leong-strictthetashortermotionpathplanningusingtautpaths","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13049"},"keyword":["Planning activities; motions and paths"],"metadata":{"authorlinks":{}}},"search_terms":["strict","theta","shorter","motion","path","planning","using","taut","paths","oh","leong"],"keywords":["planning activities; motions and paths"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}