-This paper presents a novel approach to planning a path for unmanned aerial vehicles (UAVs) for searching lost targets under uncertainty. A new basic approach for fast and effective solutions is developed which outperforms standard local hill climbing (LHC) approach. This can be improved using a clusterization of probabilities in the area. The idea allows us to simplify the problem of planning a UAV path to a problem of choosing several clusters. Finally, the proposed method is compared with other methods in simulated scenarios. The comparison shows its high efficiency to solve searching problems. Index Terms-unmanned aerial vehicles (UAVs), path planning, object detection, probability distribution
There are various types of UAVs with different characteristics, but we will have the following assumptions: UAVs can maintain a constant height above the ground; UAVs have a gimballed camera; at some constant height, UAVs see below using the camera a square of size a on the ground; UAVs travel with known constant speed;
UAVs can make a 90-degree turn if necessary.
In the paper, we supposed that the area of search is discretized into N = W H squares of size r which means that flying above the center of a square at known constant height a UAV can see it fully. For each square (i; j) (denoted by the number of its column and row) the probability that the target is in this square is known and equal to pi;j 2 [0; 1]. See Fig. 1 for the example of such discretization with known probabilities.
Fig. 1: Example of a probability grid [
A typical size of a probability grid for a search problem
is tens of thousands squares [
We denote a UAV path as R = (R1; : : : Rk), where Ri 2 f1; : : : ; W g f1; : : : ; H g, the initial cell where the drone is located as S 2 f1; : : : ; W g f1; : : : ; H g and the length of the path as L.
Then the search problem then can be formulated as follows: Given probability grid with known probabilities pi;j , the initial position of an UAV S and maximum length of the path L we should: (1) maximize
R subject to and
∑ (x;y)2R
px;y R1 = S k 1 ∑ distance(Ri; Ri+1) i=1
L; where distance(a; b) is Euclidean distance between centers of cells a and b.
visits some squares and collects probabilities from them by performing a scan; has a length no more than L; maximizes probability collected.
Note that there is no benefit from visiting (scanning) the same square twice.
This problem is a special case of Orienteering problem [
The considered problem may be solved with mixed integer
linear programming (MILP) [
The basic approach for fast solutions of this problem usually
is local hill climbing [
Different authors tried to overcome the problem. Lanillos
et al. supposed to calculate not only real probability the drone
collects flying in a direction but also expected probability that
it can collect there [
As it was stated before, effective (fast) solutions for the
problem are usually based on local hill climbing algorithm.
However, as a consequence, these algorithms ([
Fig. 3: Example of problems in solutions generated by algorithms based on local hill climbing. In black circles there are cells that are visited twice. In purple circles there are cells with high probability that are skipped by the solution. In the yellow circle there are cells that can be skipped instead of cells in purple circles.
Lemma. Any area of cells consisting of connected cells of double size (i.e. consisting of four small cells) may be covered with a hamiltonian cycle which goes through centers of small cells.
The proof of the lemma may be found in [
The algorithm to get the hamiltonian cycle is simple: 1) Build a spanning tree on cells of double size (Fig. 4). It can be built because the area is connected. 2) A path along the spanning tree is a hamiltonian cycle needed (Fig. 5) Final routes visit a lot of cells twice. Visiting a cell more than once doesn’t increase the probability of detecting. It This lemma brings us to the following idea: Instead of building a path we will build an area of cells of double size. To maintain connectivity we may add to the area only cells that are neighboring to it. As in local hill climbing, we can use greedy algorithms, i.e. among all possible cells of double size add the one that contains more probability (this can be done effectively by using, e.g., a heap data structure). Note that at every step we preserve connectivity of an area of cells of double size and it is the only constraint needed to use the lemma.
After building the area we will build a hamiltonian cycle using the lemma and it will be the final route of a UAV. Note that as we will build a hamiltonian cycle we know how many cells we need to add to the area not to exceed the constraint on the length of the final route.
This idea may be improved by the use of clustering.
Suppose we have detected all clusters (subareas of high probability). If we join centers of all clusters and the starting position of a drone by an area of cells of double size (e.g, using minimal spanning tree (MST) or Steiner tree, Fig. 6) and then run our greedy algorithm then the area will grow accurately in clusters (Fig. 7). In some cases (when the constraint on the length of the route is tight) it is better to join not all cluster but only a few of them. To choose what clusters to join we may iterate over all possibilities (if there are a small number of clusters, which is a pretty common case) or just try to pick the nearest cluster step by step (increasing complexity of an algorithm in a linear of the number of clusters time).
Then combining two ideas we get the following algorithm: 1) Choose what clusters to join. 2) Join them and the starting position of a UAV with an area of cells of double size. 3) Grow the area step by step while not exceeding the constraint on the route length. 4) Get the hamiltonian cycle from the area using the lemma.
The total complexity of steps 2-4 is O(L log N ) if using a heap to pick the cell with the highest probability effectively.
We will call the algorithm "cluster area-growth algorithm".
The proposed cluster area-growth algorithm was
implemented and compared with local hill climbing algorithm and
lhc-gw-conv algorithm from [
The comparison was performed on several test areas. Some of the areas were generated using several Gaussian distributions and some of these areas were obtained from height maps of real locations (because the form of those maps and real probability maps are similar). For every area, there were several measurements with different constraints on the length of the route (L). In the cells, there are total probabilities collected by solutions in given constraints on a particular test.
As it can be seen in Table I the proposed algorithm outperformed other algorithms almost in every case. Basic local hill climbing approach gives dramatically worse results in all tests. The proposed solution gained worse result only when constraint on the length of the route is tight. It is because other solutions were not obliged to return the drone to its starting position (i.e. to form a cycle). As a result, their routes got the opportunity to cover more clusters or to cover more distant clusters (see Fig. 8 and Fig. 9). However, as the constraint increases the proposed solution becomes to get better and better results in comparison with other solutions (see Fig. 10 and Fig. 11), because of the absence of those issues mentioned above. L=3000 L=7000 L=15000 L=3000 L=7000 L=15000 L=3000 L=7000 L=15000 L=3000 L=7000 L=15000 The proposed solution has following next advantages: The idea simplifies the problem of building a path over an area to a problem of choosing several clusters (number of clusters is far less than the number of cells in the area); The solution can not visit the same cell twice because we have a hamiltonian cycle; The solution does not miss probabilities because an area can grow in all directions (not only 4 adjacent cells may be added); As a result, it has better efficiency (according to the tests); It always returns a drone to the starting position which is good when the constraint on the length of the route is due to limited battery charge of a UAV.
We compared the solution with other solutions in simulated scenarios to show its high efficiency. The ideas from the paper may be also used in other search problems to simplify them and get more practical solutions. In future work this approach can be improved by considering the number of turns in the path (which should be also minimized).
This paper was done under research work in Simlabs Inc. (sim-labs.com)