Optimum Path Finding Framework for Drone Assisted Boat Rescue Missions

In boat rescue operations, Unmanned Aerial Vehicles (UAVs or drones) can travel long distances by utilizing the grid of floating charging stations (CSs) on the sea. To respond quickly and/or in an economic way to rescue calls, the “optimum path” from the Base Station (BS) to the boat and back to the BS should be estimated for the missions. Generally the optimum path is the shortest path involving hops from the BS via CSs to the boat and back to the BS. However, multiple objectives can be considered for two parties, drones and boats, like priority of boats, the number of chargings for the UAV, and the average waiting time for the boats. We proposed an heuristic extension called “red-gray path” which provides savings for the flight distance, depending on the boat position in the CS grid. The “drone range”, which is the maximum flight range that UAV can fly with the battery, is the fundamental parameter for the design of the rescue infrastructure. The choices for the geometry of the CS grid plays important role in the effectiveness of the heuristic we proposed. We presented mathematical analysis on the effectiveness of two different deployment strategies for the CSs based on the degree of benefiting from the heuristic we proposed. Namely the triangular and square CS grids. While the square grid provides better savings for the red-gray path heuristic, the triangular grid offers better coverage for the proposed heuristic with less number of CSs for the same mission area.