Speeding Up A* Search on Visibility Graphs Defined Over Quadtrees to Enable Long Distance Path Planning for Unmanned Surface Vehicles. Shah, B. & Gupta, S. K. In ![Speeding Up A* Search on Visibility Graphs Defined Over Quadtrees to Enable Long Distance Path Planning for Unmanned Surface Vehicles [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper abstract bibtex 1 download Over the last ten years, substantial progress has been made in the development of low-cost unmanned surface vehicles (USVs). There are a number of civilian applications where deploying USVs can significantly reduce costs, improve safety, and increase operational efficiencies. We are interested in path planning over long distances in complex marine environments. The available free space in marine environment changes over time as a result of tides, environmental restrictions, and weather. Low tides may make it infeasible to go through the regions with shallow waters. Environmental restrictions may present the unmanned surface vehicle to go through certain protected marine regions for certain periods of times. Weather induced waves may prohibit traveling over certain areas due to high collision risks. As a result of these considerations, the free space region in the marine environments needs to be dynamically generated and updated. Consider a representative case of 100 km by 100 km marine region. This region may need thousands of complex polygons to represent the obstacles. We cannot justify the computational time and efforts needed to build roadmaps if they cannot be reused due to changes in the obstacles. Quadtrees are better spatial data structures to represent the complex marine environment compared to grids. 100km by 100km region can often be represented with hundred thousand or fewer nodes in a quadtree. This leads to a reduction of more than a thousand times in terms of spatial complexity over grid based representation. We present an algorithm for long distance path planning in complex marine environments using A* search on visibility graphs defined over quad trees. Visibility graphs have been shown to be useful to compute optimal paths in the presence of complex obstacle fields. However, the computational performance of visibility graphs degrades rapidly as the region to be searched becomes large and the number of nodes in the visibility graph increase rapidly. This paper introduces a number of techniques to speed up the A* search process and makes it feasible to compute paths using visibility graphs over large regions. We exploit the inherent characteristics of quadtree data structures to speed up the geometric computation. We impose spatial constraints to limit the branching factor during the search. We also present an improved heuristic to handle large obstacles in the regions. Path computed using the proposed approach can be used to generate trajectories and support a wide variety of missions.
@inproceedings {icaps16-173,
track = {Robotics Track},
title = {Speeding Up A* Search on Visibility Graphs Defined Over Quadtrees to Enable Long Distance Path Planning for Unmanned Surface Vehicles},
url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13155},
author = {Brual Shah and Satyandra K. Gupta},
abstract = {Over the last ten years, substantial progress has been made in the development of low-cost unmanned surface vehicles (USVs). There are a number of civilian applications where deploying USVs can significantly reduce costs, improve safety, and increase operational efficiencies.
We are interested in path planning over long distances in complex marine environments. The available free space in marine environment changes over time as a result of tides, environmental restrictions, and weather. Low tides may make it infeasible to go through the regions with shallow waters. Environmental restrictions may present the unmanned surface vehicle to go through certain protected marine regions for certain periods of times. Weather induced waves may prohibit traveling over certain areas due to high collision risks. As a result of these considerations, the free space region in the marine environments needs to be dynamically generated and updated. Consider a representative case of 100 km by 100 km marine region. This region may need thousands of complex polygons to represent the obstacles. We cannot justify the computational time and efforts needed to build roadmaps if they cannot be reused due to changes in the obstacles.
Quadtrees are better spatial data structures to represent the complex marine environment compared to grids. 100km by 100km region can often be represented with hundred thousand or fewer nodes in a quadtree. This leads to a reduction of more than a thousand times in terms of spatial complexity over grid based representation. We present an algorithm for long distance path planning in complex marine environments using A* search on visibility graphs defined over quad trees. Visibility graphs have been shown to be useful to compute optimal paths in the presence of complex obstacle fields. However, the computational performance of visibility graphs degrades rapidly as the region to be searched becomes large and the number of nodes in the visibility graph increase rapidly. This paper introduces a number of techniques to speed up the A* search process and makes it feasible to compute paths using visibility graphs over large regions. We exploit the inherent characteristics of quadtree data structures to speed up the geometric computation. We impose spatial constraints to limit the branching factor during the search. We also present an improved heuristic to handle large obstacles in the regions. Path computed using the proposed approach can be used to generate trajectories and support a wide variety of missions.},
keywords = {robot motion; path; task and mission planning and execution,real-world planning applications for autonomous robots}
}
Downloads: 1
{"_id":"bpHfxfWjyScyDsamv","bibbaseid":"shah-gupta-speedingupasearchonvisibilitygraphsdefinedoverquadtreestoenablelongdistancepathplanningforunmannedsurfacevehicles","downloads":1,"creationDate":"2016-03-09T03:04:32.858Z","title":"Speeding Up A* Search on Visibility Graphs Defined Over Quadtrees to Enable Long Distance Path Planning for Unmanned Surface Vehicles","author_short":["Shah, B.","Gupta, S. K."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","track":"Robotics Track","title":"Speeding Up A* Search on Visibility Graphs Defined Over Quadtrees to Enable Long Distance Path Planning for Unmanned Surface Vehicles","url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13155","author":[{"firstnames":["Brual"],"propositions":[],"lastnames":["Shah"],"suffixes":[]},{"firstnames":["Satyandra","K."],"propositions":[],"lastnames":["Gupta"],"suffixes":[]}],"abstract":"Over the last ten years, substantial progress has been made in the development of low-cost unmanned surface vehicles (USVs). There are a number of civilian applications where deploying USVs can significantly reduce costs, improve safety, and increase operational efficiencies. We are interested in path planning over long distances in complex marine environments. The available free space in marine environment changes over time as a result of tides, environmental restrictions, and weather. Low tides may make it infeasible to go through the regions with shallow waters. Environmental restrictions may present the unmanned surface vehicle to go through certain protected marine regions for certain periods of times. Weather induced waves may prohibit traveling over certain areas due to high collision risks. As a result of these considerations, the free space region in the marine environments needs to be dynamically generated and updated. Consider a representative case of 100 km by 100 km marine region. This region may need thousands of complex polygons to represent the obstacles. We cannot justify the computational time and efforts needed to build roadmaps if they cannot be reused due to changes in the obstacles. Quadtrees are better spatial data structures to represent the complex marine environment compared to grids. 100km by 100km region can often be represented with hundred thousand or fewer nodes in a quadtree. This leads to a reduction of more than a thousand times in terms of spatial complexity over grid based representation. We present an algorithm for long distance path planning in complex marine environments using A* search on visibility graphs defined over quad trees. Visibility graphs have been shown to be useful to compute optimal paths in the presence of complex obstacle fields. However, the computational performance of visibility graphs degrades rapidly as the region to be searched becomes large and the number of nodes in the visibility graph increase rapidly. This paper introduces a number of techniques to speed up the A* search process and makes it feasible to compute paths using visibility graphs over large regions. We exploit the inherent characteristics of quadtree data structures to speed up the geometric computation. We impose spatial constraints to limit the branching factor during the search. We also present an improved heuristic to handle large obstacles in the regions. Path computed using the proposed approach can be used to generate trajectories and support a wide variety of missions.","keywords":"robot motion; path; task and mission planning and execution,real-world planning applications for autonomous robots","bibtex":"@inproceedings {icaps16-173,\r\n track = {Robotics Track},\r\n title = {Speeding Up A* Search on Visibility Graphs Defined Over Quadtrees to Enable Long Distance Path Planning for Unmanned Surface Vehicles},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13155},\r\n author = {Brual Shah and Satyandra K. Gupta},\r\n abstract = {Over the last ten years, substantial progress has been made in the development of low-cost unmanned surface vehicles (USVs). There are a number of civilian applications where deploying USVs can significantly reduce costs, improve safety, and increase operational efficiencies. \r\n\r\nWe are interested in path planning over long distances in complex marine environments. The available free space in marine environment changes over time as a result of tides, environmental restrictions, and weather. Low tides may make it infeasible to go through the regions with shallow waters. Environmental restrictions may present the unmanned surface vehicle to go through certain protected marine regions for certain periods of times. Weather induced waves may prohibit traveling over certain areas due to high collision risks. As a result of these considerations, the free space region in the marine environments needs to be dynamically generated and updated. Consider a representative case of 100 km by 100 km marine region. This region may need thousands of complex polygons to represent the obstacles. We cannot justify the computational time and efforts needed to build roadmaps if they cannot be reused due to changes in the obstacles. \r\n \r\nQuadtrees are better spatial data structures to represent the complex marine environment compared to grids. 100km by 100km region can often be represented with hundred thousand or fewer nodes in a quadtree. This leads to a reduction of more than a thousand times in terms of spatial complexity over grid based representation. We present an algorithm for long distance path planning in complex marine environments using A* search on visibility graphs defined over quad trees. Visibility graphs have been shown to be useful to compute optimal paths in the presence of complex obstacle fields. However, the computational performance of visibility graphs degrades rapidly as the region to be searched becomes large and the number of nodes in the visibility graph increase rapidly. This paper introduces a number of techniques to speed up the A* search process and makes it feasible to compute paths using visibility graphs over large regions. We exploit the inherent characteristics of quadtree data structures to speed up the geometric computation. We impose spatial constraints to limit the branching factor during the search. We also present an improved heuristic to handle large obstacles in the regions. Path computed using the proposed approach can be used to generate trajectories and support a wide variety of missions.},\r\n keywords = {robot motion; path; task and mission planning and execution,real-world planning applications for autonomous robots}\r\n}\r\n\r\n","author_short":["Shah, B.","Gupta, S. K."],"key":"icaps16-173","id":"icaps16-173","bibbaseid":"shah-gupta-speedingupasearchonvisibilitygraphsdefinedoverquadtreestoenablelongdistancepathplanningforunmannedsurfacevehicles","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13155"},"keyword":["robot motion; path; task and mission planning and execution","real-world planning applications for autonomous robots"],"metadata":{"authorlinks":{}},"downloads":1,"html":""},"search_terms":["speeding","search","visibility","graphs","defined","over","quadtrees","enable","long","distance","path","planning","unmanned","surface","vehicles","shah","gupta"],"keywords":["robot motion; path; task and mission planning and execution","real-world planning applications for autonomous robots"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}