Paper Info
Title
Speeding Up A* Search on Visibility Graphs Defined Over Quadtrees to Enable Long Distance Path Planning for Unmanned Surface Vehicles.
Abstract
We introduce an algorithm for long distance path planning in complex marine environments. The available free space in marine environments changes over time as a result of tides, environmental restrictions, and weather. As a result of these considerations, the free space region in marine environments needs to be dynamically generated and updated. The approach presented in this paper demonstrates that it is feasible to compute optimal paths using A* search on visibility graphs defined over quadtrees. Our algorithm exploits quadtree data structures for efficiently computing tangent edges in visibility graphs. We have developed an admissible heuristic that accounts for large islands while estimating the cost-to-go and provides a better lower bound than the Euclidean distance-based heuristic. During the search over visibility graphs, the branching factor of A* can be large due to the large size of the region. We introduce the idea of focusing the search by limiting the child nodes to be in certain regions of the workspace. Our results show that focusing the search significantly improves the computational efficiency without any noticeable degradation in path quality. We have also developed a method to estimate bounds on how far the computed path can be from the optimal path when methods for focusing the search are utilized for speeding up the computation.
Year
Venue
Field
2016
Proceedings of the International Conference on Automated Planning and Scheduling
Motion planning,Mathematical optimization,Visibility,Any-angle path planning,Heuristic,Computer science,Admissible heuristic,Euclidean distance,Longest path problem,Quadtree
DocType
ISSN
Citations 
Conference
2334-0835
1
PageRank 
References 
Authors
0.40
14
2
Name
Order
Citations
PageRank
Brual C. Shah1154.85
Satyandra K Gupta268777.11