Path Generation Method of UAV Autopilots Using Max-Min Algorithm

Jeonghoon Kwak* and Yunsick Sung*

Abstract

Abstract: In recent times, Natural User Interface/Natural User Experience (NUI/NUX) technology has found widespread application across a diverse range of fields and is also utilized for controlling unmanned aerial vehicles (UAVs). Even if the user controls the UAV by utilizing the NUI/NUX technology, it is difficult for the user to easily control the UAV. The user needs an autopilot to easily control the UAV. The user needs a flight path to use the autopilot. The user sets the flight path based on the waypoints. UAVs normally fly straight from one waypoint to another. However, if flight between two waypoints is in a straight line, UAVs may collide with obstacles. In order to solve collision problems, flight records can be utilized to adjust the generated path taking the locations of the obstacles into consideration. This paper proposes a natural path generation method between waypoints based on flight records collected through UAVs flown by users. Bayesian probability is utilized to select paths most similar to the flight records to connect two waypoints. These paths are generated by selection of the center path corresponding to the highest Bayesian probability. While the K-means algorithm-based straight-line method generated paths that led to UAV collisions, the proposed method generates paths that allow UAVs to avoid obstacles.

Keywords: Autopilot , Max-Min Algorithm , Path Generation , Unmanned Aerial Vehicle

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).

(1)
[TeX:] $$\arg max _ { r ^ { \prime } } \sum _ { r = 1 } ^ { \left| s _ { k k ^ { \prime } } \right| } \text { FréchetDistance } \left( S _ { k , k ^ { \prime } , r ^ { \prime } } , S _ { k , k ^ { \prime } , r } \right)$$

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).

(2)
[TeX:] $$\arg min _ { r ^ { \prime } } \sum _ { r = 1 } ^ { \left| s _ { k, k ^ { \prime } } \right| } \text { FréchetDistance } \left( S _ { k , k ^ { \prime } , r ^ { \prime } } , S _ { k , k ^ { \prime } , r } \right)$$

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).

Biography

Jeonghoon Kwak
https://orcid.org/0000-0003-2546-1041

He is a PhD student in the department of Multimedia Engineering at the Dongguk University, Seoul, Korea. He received the B.S. degree in Game Mobile Contents from Keimyung University, Daegu, Korea, in 2015 and the M.S. degree in Computer Engineering from Keimyung University, Daegu, Korea, in 2017. His research interests are focused on the areas of unmanned aerial vehicle, ground control station, and demonstration-based learning.

Biography

Yunsick Sung
https://orcid.org/0000-0003-3732-5346

He is currently an Assistant Professor in the department of Multimedia Engineering at Dongguk University, Seoul, Korea. He received the B.S. degree in Division of Electrical and Computer Engineering from Pusan National University, Busan, Korea, in 2004, the M.S. degree in Computer Engineering from Dongguk University, Seoul, Korea, in 2006, and the Ph.D. degree in Game Engineering from Dongguk University, Seoul, Korea, in 2012. He was employed as a Member of the Researcher at Samsung Electronics in Republic of Korea, between 2006 and 2009. He was the Plural Professor at Shinheung College, Gyeonggi-do, Korea, in 2009, and at Dongguk University, Seoul, Korea, in 2010. He was also the postdoctoral fellow at University of Florida, FL, USA, between 2012 and 2013. His research interests are focused on the areas of games, pervasive computing, and robotics. He is a managing editor in Journal of Information Processing Systems from 2017 and is a managing editor in Human-centric Computing and Information Sciences from 2015. He was a guest editor in one of special issues of Symmetry in 2017 and is a guest editor in one of special issues of Journal of Ambient Intelligence Humanized Computing in 2018. He has a lot of conference service experiences with International Conference on Multimedia and Ubiquitous Engineering (MUE), International Conference on Future Information Technology (FutureTech), World Congress on Information Technology Applications (WorldIT Congress) and Services, Global Conference on Information Technology, Computing, and Applications (GlobalIT), International Conference on Big data, IoT, and Cloud Computing (BIC), International Conference on Parallel and Distributed Computing Applications, and Technologies (PDCAT), International Conference on Ubiquitous Computing Application and Wireless Sensor Network (UCAWSN), International Conference on Ubiquitous Information Technologies and Applications (CUTE), and International Conference on Computer Science and its Applications (CSA).

References

• 1 P. Fahlstrom, T. Gleason, Introduction to UAV Systems, 4th ed. ChichesterUK: John Wiley Sons, 2012.custom:[[[-]]]
• 2 L. Merino, F. Caballero, J. R. Martinez-De-Dios, I. Maza, A. Ollero, Journal of Intelligent Robotic Systems, vol. 65, no. 1-4, pp. 533-548, 2012.custom:[[[-]]]
• 3 L. Zhang, B. Wang, W. Peng, C. Li, Z. Lu, Y. Guo, "A method for forest fire detection using UAV," in Advanced Science and Technology Letters, 2015;vol. 81, pp. 69-74. custom:[[[-]]]
• 4 J. Kwak, Y. Sung, "Beacon-based indoor location measurement method to enhanced common chord-based trilateration," Journal of Information Processing Systems, vol. 13, no. 6, pp. 1640-1651, 2017.doi:[[[10.3745/JIPS.04.0053]]]
• 5 F. Zhang, D. Gao, I. W. Joe, "A tier-based duty-cycling scheme for forest monitoring," Journal of Information Processing Systems, vol. 13, no. 5, pp. 1320-1330, 2017.doi:[[[10.3745/JIPS.04.0043]]]
• 6 M. T. N. Truong, S. Kim, "Parallel implementation of color-based particle filter for object tracking in embedded systems," Human-centric Computing and Information Sciencesarticle no. 2,, vol. 7, no. article 2, 2017.doi:[[[10.1186/s13673-016-0082-1]]]
• 7 L. V. Santana, A. S. Brandao, M. Sarcinelli-Filho, "Outdoor waypoint navigation with the AR.Drone quadrotor," in Proceedings of 2015 International Conference on Unmanned Aircraft Systems (ICUAS), Denver, CO, 2015;pp. 303-311. custom:[[[-]]]
• 8 L. V. Santana, A. S. Brandao, M. Sarcinelli-Filho, "An automatic flight control system for the AR.Drone quadrotor in outdoor environments," in Proceedings of 2015 Workshop on Research, Education and Development of Unmanned Aerial Systems (RED-UAS), Cancun, Mexico, 2015;pp. 401-410. custom:[[[-]]]
• 9 J. Kwak, J. H. Park, "Linear motor primitive generation method based on observation spots," Advanced Science Letters, vol. 22, no. 9, pp. 2566-2569, 2016.doi:[[[10.1166/asl.2016.7843]]]
• 10 J. Kwak, J. H. Park, Y. Sung, "Unmanned aerial vehicle flight point classification algorithm based on symmetric big data," Symmetryarticle no. 1,, vol. 9, no. article 1, 2017.doi:[[[10.3390/sym9010001]]]
• 11 T. Eiter, H. Mannila, "Computing discrete Fréchet distance," Information Systems DepartmentTechnical University of Vienna, Report No. CD-TR 94/64,, 1994.custom:[[[-]]]
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.
K waypoints are generated using the K-means algorithm by classifying the points included in the four flight records.
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.
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.
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.