Coverage of an Environment Using Energy Constrained Unmanned Aerial Vehicles - adigoswami/MiniProject1 GitHub Wiki
By Kevin Yu, Jason M. O’Kane, and Pratap Tokekar
Unmanned aerial vehicles (UAV) cannot perform tasks that take longer than 30 minutes because of their short lasting batteries. Setting up fixed charging station is terribly wasteful because the UAV has to constantly fly back and forth between the station and the area of interest. A solution to that is to mount the charging station on top of a unmanned ground vehicle (UGV) that can follow the UAV around. Thus whenever the UAV is about to run out of battery, all it has to do is fly downwards and land on the UGV. This paper applies this technique to the coverage problem.
When thinking about minimizing the coverage time, one should take into account not only the flight time but also the charging time and the landing and take off times that each charging session mandates. So this problem boils down to deciding at which points during the coverage mission to recharge and for how long each time. The area that needs to be covered is decomposed into boustrophedon cells using techniques from prior work. Each cell is a straight line and the UAV can land and take off only at the endpoints of a cell (either the beginning or the end).
The paper assumes that the UAV starts with a full battery and flies at a fixed height and speed. Additionally, it assumes that the UGV never runs out of battery during a mission and can move at roughly a similar pace to the UAV.
When the UAV has finished going through a cell and before it is ready to begin going through the next one, it faces a set of options:
- Fly to the beginning of the next cell.
- Stop to recharge, fly to the beginning of the next cell.
- Fly to the beginning of the next cell, stop to recharge.
- Stop to recharge, fly to the beginning of the next cell, stop to recharge.
- Stop to recharge and get transferred to the next cell by the UGV whilst charging.
The main objective of this paper is to decide in which order to visit the cells, from which side to enter each cell and which of the 5 recharging policies to follow after exiting each cell. This decision making problem can be solved efficiently and optimally but reducing it to the generalized travelling salesman problem. Each GTSP cluster corresponds to the decisions surrounding a single boustrophedon cell. There are no edges between vertices of a single cluster. Each edge represents a transition from the end of a cell to the beginning of an other one.
The paper acknowledges that it is not realist to assume that the UGV can move as fast as the UAV. As a possible remedy, they recommend multiple slow UGVs. This poses the question of what is the minimum number of UGVs required so that the UAV never has to wait for a UGV to arrive. Another modification to the model that would give rise to smarter heuristics is to allow the UAV to take off while it is being transferred.