Mini Project 2 - adigoswami/Mini_Project_2 GitHub Wiki

• Aditya Goswami
• Lambros Mertzanis

"Coverage of an Environment Using Energy-Constrained Unmanned Aerial Vehicles." by Kevin Yu, Jason M. O’Kane, and Pratap Tokekar

This webpage shows the results of the implementation of an algorithm from one of the research papers discussed in mini-project 1. In the paper, "Coverage of an Environment Using Energy-Constrained Unmanned Aerial Vehicles", the problem of covering an environment, a set of boustrophedon cells, using an Unmanned Aerial Vehicle (UAV) with a limited battery capacity is studied.

The authors considered a scenario where the UAV can land on an Unmanned Ground Vehicle (UGV) and recharge the onboard battery. The UGV can also recharge the UAV while transporting the UAV to the next take-off site. They present an algorithm to solve a new variant of the area coverage problem that takes into account this symbiotic UAV and UGV system. The input consists of a set of boustrophedon cells — rectangular strips whose width is equal to the field-of-view of the sensor on the UAV. The goal is to find a tour for the UAV that visits and covers all cells in minimum time. This includes flight time for visiting and covering all cells, recharging time, as well as the take-off and landing times. The paper shows how to reduce this problem to a known NP-hard problem, Generalized Traveling Salesperson Problem (GTSP). Given an optimal GTSP solver, our approach finds the optimal coverage paths for the UAV and UGV. They evaluate the algorithm through simulations and proof-of-concept experiments.

Please refer https://github.com/adigoswami/MiniProject1/wiki/Coverage-of-an-Environment-Using-Energy-Constrained-Unmanned-Aerial-Vehicles for a detailed summary and https://ieeexplore.ieee.org/document/8794150 for the complete paper.

The input to this algorithm is a set of n boustrophedon cells that need to be covered by the UAV. A boustrophedon cell is a rectangular strip whose width is equal to the diameter of the field-of-view (FOV) of the sensor onboard the robot. An example is shown in Figure 1 and a larger example is shown in Figure 2.

Some assumptions that were made are as following:

• The UAV has an initial battery charge of 100%.
• The UAV flies at a fixed-altitude plane when covering a boustrophedon cell.
• The UAV travels at unit speed.
• The battery discharges at a unit rate (one unit per unit time and per unit distance traveled).
• The battery gets recharged at a rate of r units per unit time.
• The UGV has unlimited fuel/battery capacity.

Since it is assumed that the UAV travels with unit speed, we can use time and distance interchangeably. The terms, t_TO and t_L, are used to represent the time taken by the UAV to take-off from the UGV to reach the fixed-altitude plane and land from this plane onto the UGV, respectively. The battery capacity has been discretized into C levels.

The actual cost of traveling from vertex i (entry of one boustrophedon cell) to vertex j (entry of next boustrophedon cell) depends on the three binary indicator variables (ref. paper/section IV). This gives a total of 2³ possible travel options. However, three of these eight options are redundant. Therefore, of these 2³ possibilities, we can eliminate three, leaving a total of five possibilities for the second leg. These are shown in Figure 3.

Let's jump to the code. Following is the snippet of a function for the first possibility type: 'F-F'. (ref. Eq.3 (in paper/section_IV/Edges ))

def T_F_F(vertex_ai, vertex_aj, vertex_bi, ki, kj):

dist1= distance(vertex_ai[0],vertex_ai[1],vertex_bi[0],vertex_bi[1])
dist2= distance(vertex_bi[0],vertex_bi[1],vertex_aj[0],vertex_aj[1])

cost = dist1 + dist2

if (cost > (kj - ki)*10):
    return 999999
else:
    return cost

Similarly, all five functions are developed using the corresponding equations. Using these functions, first, we find the cost of the edge using every function. Then the minimum cost is found using the min function over the five calculated costs.

cost1 = T_F_F(temp1, point, temp2, i, k)
cost2 = T_F_FDU(temp1, point, temp2, i, k)
cost3 = T_F_DUFDU(temp1, point, temp2, i, j, k)
cost4 = T_F_DUF(temp1, point, temp2, i, j, k)
cost5 = T_F_DTU(temp1, point, temp2, i, j, k)
                    
costs = [cost1, cost2, cost3, cost4, cost5]
cost = min(costs)

Further while storing these edges between the vertices are stored along with details like the two vertices which form the edge, the class: type of possibility.

Then we generate the edge costs in the matrix form which becomes the input for GNLS Solver. Similarly, a file is generated in a form suitable for the GNLS input file. (ref. Matrix: https://github.com/adigoswami/Mini_Project_2/blob/master/Matrix.txt and for Clusters:https://github.com/adigoswami/Mini_Project_2/blob/master/Cluster.txt).

Yes, we're going to explain the GTSP Solver package GNLS that we have been talking about.

GLNS is a solver for the Generalized Traveling Salesman Problem (GTSP), implemented in Julia. More information on the solver is given at https://ece.uwaterloo.ca/~sl2smith/GLNS/ The GLNS solver and its settings are described in the following paper DOI PDF:

Further, you can try this out at this repo: https://github.com/stephenlsmith/GLNS.jl

Without further ado, let's see the format of input this solver requires. Following is the snippet of the same, you

Therefore, we need to generate this data. But this data is important to solve the Travelling Salesman Problem and signifies the implementation of the algorithm.

Following is a snippet of the original data that we generated along with the text files: Matrix, Clusters.

The screenshot is shown below in figure 5 and figure 6:

After a bit of struggle, we were able to adjust these required inputs according to the GLNS solver. After running the solver (which is pretty quick!), we finally had the output path that had exactly one vertex from each cluster. Following is the output:

• First, if you'll encounter C 'The discretized battery levels', it does not come straightforward. Then the use of different notation k_i makes it really hard to grasp the concept and understand the equations.
• The notation could have been a bit easier.
• Some guidance on using the solver could have been really helpful and timesaver.
• Some takeaways for future use: try to generate the matrix such that there is no space after every row of the matrix. Do not generate the cluster input for the solver where the index starts at '0'.
• Not much information is provided on UGV.
• Sometimes the notations are not consistent which creates confusion.

We have promising results as the data (edges) generated is accepted by the solver and a tour (path) is generated as is evident from the output of the solver which includes exactly one node from each cluster. We are yet to generate the final graph due to time constraints.

But will definitely make the complete working code of the algorithm along with the 'graph maker' file available on the repository. (Code).