I. Path Planning for Large Marine Environments
Abstract:
We introduce an algorithm for long distance path planning in complex marine environments. The available free space in marine environment 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.
Published Work:
B. C. Shah, and S. K. Gupta. Speeding up A* Search on Visibility Graphs Defined Over Quadtrees to Enable Long Distance Path Planning for Unmanned Surface Vehicles. International Conference on Automated Planning and Scheduling (ICAPS’ 16), London, UK, June 12 – 17, 2016. PDF
II. Energy-efficient Path Planning for Unammned Vehicles
Abstract:
Significant fluid medium flows such as strong currents may influence the maximum velocity and energy consumption of unmanned vehicles. Weather forecast reports provide an estimate of the medium flow and can be utilized to generate low-cost paths that exploit medium flow to aid the motion of the vehicle and conserve energy. Conserving energy also has an indirect benefit of extending the range of operation. This paper presents an A* based path planning approach that can handle complex dynamic obstacles and arbitrary cost functions. Traditional admissible heuristics that are based on shortest distance or time are not suitable for this problem as exploiting the medium flow to propel the vehicle forward often requires longer time or distance to reach the goal. We have developed new admissible heuristics for estimating cost-to-go by taking into account flow considerations. The proposed method also selects the start time for commencing the mission by waiting for the favorable medium flow conditions.
Published Work:
B. C. Shah, A. Thakur, P. Švec, and S. K. Gupta. Path Planning for Unmanned Vehicles Operating in Time-Varying Flow Fields. Planning and Robotics (PlanRob) Workshop at International Conference on Automated Planning and Scheduling (ICAPS’ 16), London, UK, June 12 – 17, 2016 (Submitted). PDF
Brual Shah 