1. Introduction
As Natural User Interface/Natural User Experience (NUI/NUX) technologies are developed, unmanned aerial vehicles (UAVs) [1] are increasingly utilized to monitor fires and roads using attached cameras [2-6]. Autonomous flight for surveillance uses UAV’s autopilot. UAV surveillance flights are based on waypoints specified by the user using autopilot [7,8]. Flight paths are generated by classifying UAV flight record [9,10] generating straight paths connecting the waypoints. Approaches to generating the paths between two waypoints that consider the locations of obstacles are required to ensure UAVs avoid collisions.
This paper proposes a natural flight path generation method based on paths to connect two waypoints that are developed using flight records collected through UAV controls. The flight records are classified by the K-means algorithm [10] and then multiple waypoints are produced. The paths between two waypoints are classified. The Bayesian probability of the classified paths is calculated. The paths with the highest Bayesian probability are recommended. The proposed method makes it possible to generate obstacle-avoidant paths from obstacle data instead of being restricted to a straight path between the two waypoints.
The structure of this paper is as follows: Section 2 details the path generation using flight records. Section 3 details the proposed method for temporal path generation between two waypoints. Section 4 discusses the experimental results, and Section 5 describes conclusions.
2. Path Generation Method Based on Flight Records
This paper proposes a method of generation a path connecting two waypoints based on the flight paths collected by UAV flights as shown in Fig. 1. The Path Record stage collects UAV flight records. The flight record Pr is the flight record collected on the rth flight. The flight record Pr is the set [TeX:] $$\left[ P _ { r , 1 } , P _ { r , 2 } , \ldots , P _ { r , t } , \ldots \right]$$, where the position of the UAV measured at time t in the rth flight record is defined as the point Pr,t. The point Pr,t is composed of a UAV position, [TeX:] $$\left[ x _ { r , t } , y _ { r , t } \right]$$. Fig. 2 shows the collected flight paths.
Generation a path using the user’s records consists of four stages: Path Record, Point Classification, Temporal Path Generation, and Concreted Path Generation.
Result of collecting four flight records: (a) 1st flight record, (b) 2nd flight record, (c) 3th flight record, and (d) 4th flight record.
The Point Classification stage generates waypoints by classifying flight records using the K-means algorithm [10]. The kth set of points by the K-means algorithm is defined as a Cluster Ck. The average of points in the kth cluster kth is defined as centroid [TeX:] $$\mu _ { k } \text { with } \left[ x _ { k } , y _ { k } \right]$$. Centroids are defined as the waypoints as shown in Fig. 3.
K waypoints are generated using the K-means algorithm by classifying the points included in the four flight records.
The Temporal Path Generation stage generates temporal paths between all possible connectable two waypoints based on max–min algorithm. Therefore, between two waypoints, multiple temporal paths are deducted.
The Concreted Path Generation stage generates flight paths using waypoints and temporal paths to connect the two waypoints. The result of connecting the waypoints to generate the flight path is shown Fig. 4. The possibility exists for collisions with obstacles when moving a waypoint in a straight line to another point generated by the K-means algorithm [10]. However, the proposed method avoids obstacles by generating natural flight paths.
Resultant flight path generated. (a) is the result of generating the flight path using the proposed method, and (b) is the result of generating the flight path based on the K-means algorithm-based straightline method.
3. Temporal Path Generation Method Using Max-Min Algorithm
The temporal path connecting two waypoints, [TeX:] $$\mu _ { k } \text { and } \mu _ { k ^ { \prime } } , \text { in } r ^ { t h }$$ flight record Pr is defined as the temporal path [TeX:] $$S _ { k , k ^ { \prime } , r }$$. The temporal path [TeX:] $$S _ { k , k ^ { \prime } , r }$$ can be extracted if the points, [TeX:] $$P _ { r , t } \text { and } P _ { r , t ^ { \prime } }$$, are in the two different clusters, [TeX:] $$C _ { k } \text { and } C _ { k ^ { \prime } } \text { and } t ^ { \prime } = t + 1$$ of the points, [TeX:] $$P _ { r , t } \text { and } P _ { r , t ^ { \prime } }$$, which means that the point [TeX:] $$P _ { r , t ^ { \prime } }$$ is collected right after the point [TeX:] $$P _ { r , t ^ { \prime } }$$. The temporal path [TeX:] $$S _ { k , k ^ { \prime } , r }$$ finds the two points having the minimum Euclidean distance from two waypoints, [TeX:] $$\mu _ { k } \text { and } \mu _ { k ^ { \prime } }$$, in the flight record Pr for finding temporal paths as shown in Fig. 5.
It is the result of extracting the temporal path [TeX:] $$S _ { k , k ^ { \prime } , r }$$ connecting the two waypoints, [TeX:] $$\mu _ { k } \text { and } \mu _ { k ^ { \prime } }$$, in the flight record Pr.
The temporal path [TeX:] $$S _ { k , k ^ { \prime } , r }$$ having the greatest sum of the Fréchet distance [11] among the temporal paths is identified for classifying temporal paths as in Eq. (1).
The interval to quantize the temporal paths is defined as the interval α. Similar temporal paths are derived through quantization. The quantized section to be included in [TeX:] $$\left\lfloor \frac { \text { FréchetDistance } \left( S _ { k , k ^ { \prime } , r ^ { \prime } } , S _ { k , k ^ { \prime } , r } \right) } { \alpha } \right \rfloor$$ calculated considering the temporal paths for the centroids, [TeX:] $$\mu _ { k } \text { and } \mu _ { k ^ { \prime } }$$, based on the temporal path [TeX:] $$S _ { k , k ^ { \prime } , r ^ { \prime } }$$, is selected. The Bayesian probability is calculated after the quantization of the numbers for all temporal paths.
A quantized section having a high Bayesian probability is selected. Among the temporal paths including the selected quantization section, a temporal path having a smallest sum of the Fréchet Distance [11] is generated as a path connecting two waypoints, as shown in Eq. (2).
4. Experiments
In the experiment, the flight record was collected three times as shown in Fig. 6. K was set by 20 to generate 20 waypoints considering the number of the collected flight records.
Interval α was set to 5. The flight path connecting the waypoints by the proposed method is shown in Fig. 7(a). The result of generation the flight path by the K-means algorithm-based straight-line method is shown in Fig. 7(b). When the flight path was generated by the proposed method, the generated paths were similar to the flight records. However, when the K-means algorithm-based straight-line method, the generated flight path did collide with obstacles or not resemble the specified flight path.
Flight records collected by three flights.
Comparison between the proposed method and the K-means algorithm-based straight-line method. (a) Result of generating the flight path by the proposed method. (b) Result of generating the Kmeans algorithm-based straight-line method.
5. Conclusion
This paper proposes a flight records-based flight path generation method to connect two waypoints. The waypoints were generated by classification of the collected flight records by the K-means algorithm. The temporal paths connecting the waypoints in the flight record were searched and classified using similar temporal paths. The flight path that connects the waypoints was generated based on the path with the highest Bayesian probability among similar temporal paths.
In the experiment, existing flight paths were utilized to generate the UAV’s flight paths. The flight path created by the proposed method was more natural than that resulting from generation using the K-means algorithm-based straight line. Results prove that more natural paths that avoid obstacles can be generated using the proposed method.
Acknowledgement
This research was supported by the Ministry of Science and ICT, Korea, under the Information Technology Research Center support program (No. IITP-2018-2013-1-00684) supervised by the Institute for Information & communications Technology Promotion (IITP).