소형 무인비행체에서의 충돌회피를 위한 비행경로 생성에 관한 연구
신새벽*, 김진배*, 김신덕*, 김정길** 종신회원
A Study of Path-Finding Method of Small Unmanned Aerial Vehicles for Collision Avoidance
Saebyuk Shin*, Jinbae Kim*, Shin-Dug Kim*, Cheong Ghil Kim** Lifelong Member
요 약
소형 무인기(UAV: Unmanned Aerial Vehicle)가 급속히 대중화됨에 따라 최근의 UAV 시스템은 각각의 목적에 따라 다양한 분야에 서 설계되고 활용되고 있다. 이는 UAV 조정과 관련하여 전자, 센서, 카메라, 소프트웨어 프로그램 등에 이르기까지 많은 새로운 기회를 열어 가고 있으며 저비용 및 혁신적 업무 수행 능력으로 UAV의 활용과 응용 영역의 확대는 새로운 기술 혁신을 주도하고 있다. 특히 소형 UAV는 저고도 상황에서 예측이 힘든 돌발 변화나 장애물 출현 발생 확률이 높은 환경에서 비행을 하여야 한다.
본 논문에서는 소형 UAV 시스템의 자율 비행 기술에 관한 최근의 연구를 소개하고 적대적인 환경에서 소형 UAV의 저비용 센서들 을 활용하여 경로 생성과 충돌 회피를 통해 안전하게 목표물에 도착을 유도하는 시험적 방안을 제안 한다.
Key Words : unmanned aerial vehicles, path planning, q-learning algorithm, map creation, adversarial environments
ABSTRACT
With the fast growing popularity of small UAVs (Unmanned Aerial Vehicles), recent UAV systems have been designed and utilized for the various field with their own specific purposes. UAVs are opening up many new opportunities in the fields of electronics, sensors, camera, and software for pilots. Increase in awareness and mission capabilities of UAVs are driving innovations and new applications driven with the help of low cost and its capability in undertaking high threat task. In particular, small unmanned aerial vehicles should fly in environments with high probability of unexpected sudden change or obstacle appearance in low altitude situations. In this paper, current researches regarding techniques of autonomous flight of smal UAV systems are introduced and we propose a draft idea for planning paths for small unmanned aerial vehicles in adversarial environments to arrive at the given target safely with low cost sensors.
*연세대학교 컴퓨터과학과 ([email protected], [email protected], [email protected])
**남서울대학교 컴퓨터학과 ([email protected]) 교신저자 : 김정길
접수일자 : 2017년 01월 22일, 수정완료일자 : 2017년 03월 28일, 최종게재확정일자 : 2017년 03월 29일
I. Introduction
An unmanned aerial vehicle (UAV) is defined as a space traversing vehicle that flies without a human crew on board and that can be remotely controlled or can fly autonomously [1, 2]. Now the their utilizations have been broaden starting from military areas to civil industries including disaster and leisure applications. Therefore, UAVs could be an emerging industry with great
opportunity and market demand. Especially, the fast growing popularity of small UAVs is enabling many related areas such as electronics, sensors, camera, and software to have new opportunities and driving innovative applications. As a result, the market for UAVs has kept growing at an unprecedented rate and one report expects that the global market for UAVs can reach up to grow USD80 billion by 2025 as shown in Fig. 1 [3].
Fig. 1. Global UAV market forecast
Fig. 2. Various types of UAV
In addition, small UAVs could be categorized into small tactical, miniature, and micro UAVs [2] shown in Fig. 2 and they become one of major academic research topics with the merits of low cost, high maneuverability, and easy maintenance. Significant progress in various research areas (e.g., dynamics modeling, flight control, guidance, computer vision, and navigation) have been made and further benefit autonomy enhancement of UAVs [3]. In recent years, researches are being actively conducted on the utilization of unmanned aerial vehicle systems that perform autonomous mission based on multiple sensors with low cost [4].
Small UAVs usually fly in environments with high probability of unexpected sudden change or obstacle appearances in low altitude situations. Also, under the situations and environments of disaster and radio shadow areas, the UAV must complete its own mission through an autonomous flight to avoid obstacles until it reaches the target point safely.
This paper introduces current researches regarding techniques of autonomous flight of small UAV systems and proposes a draft idea for planning paths for small unmanned aerial vehicles in adversarial environments to arrive at the given target safely with low cost sensors.
The rest of this paper is organized as follows. Section 2 covers current researches of UAV. Section 3 proposes a draft idea for autonomous path finding technique under
adversarial environments to arrive at the given target safely with low cost sensors. Section 4 introduces simulation environment. The conclusion is covered in the last section.
Ⅱ. Background
Many researches have been carried out on small UAVs, which can provide a basic understanding of various essential issues of small UAV researches [5, 6, 7]. They includes the issues of design, operation, sensing, development, automation and autonomy, safety assessment and deployment for small UAVs. Fig. 3 shows a block diagram of typical UAVs consisting of onboard flight control systems, aircraft platform, optional manual control backup, and ground control station [2].
Fig. 3. Block diagram of a typical UAV
Path planning is one of the major issues for autonomous flights. This should reflect various factors such as movement to the target point, obstacle avoidance, and shortest path setting. For this purpose, genetic algorithm [8] and TVFG (Tangent Vector Field Guidance) algorithm [9] have been used for path planning. In order to operate the path setting module in real time under the limited hardware performance environment of UAV, complex operations must be reduced and optimized. Vincent et al.
[8] took advantage of genetic algorithms and particle group optimization algorithms; single-program, multiple-data parallel programming paradigms have been used to shorten solution execution time. Chen et al. [9]
proposes a dynamic routing algorithm to set the path of an unmanned aerial vehicle to track ground targets in the constraints of wind resistance and obstacle avoidance. For this, TVFG and the Lyapunov vector field guidance (LVFG) algorithm are presented.
The positioning in UAV ensures flight safety especially in autonomous flight. Currently, GPS (Global Positioning System) is the indispensable technology of the current drone positioning [10]. However, there exists places like indoor environment where GPS does not work; it cannot rely solely on GPS for positioning. Alternatively, since most UAVs use sensor components such as acceleration sensor, gyro sensor, and magnetic sensor to keep their balance, we can use them as inertial measurement unit (IMU) with a very high update frequency [11].
Cesario et al. [12] presented a technique that integrates measurements provided by inertial sensor, GPS, and video systems to estimate the position and attitude of UAVs.
The authors identified a vision-based system with a low-cost camera device. The information carried by the camera is integrated with the classical data from the IMU and GPS in the sensor fusion algorithm. Lingyun Xu et al.
[13] proposed a framework for automatic tracking and landing on moving targets using VTOL (Vertical Take-off and Landing) UAV.
Ⅲ. Proposed Methods
This paper proposes a path planning method for an autonomous flight in the indoor environment where GPS communication is impossible. Q-learning algorithm, a reinforcement learning algorithm, could be used. Thus UAVs may determine their own path based on the learned results. In order to achieve this, a path planning method to avoid obstacles and fly to the target point should be provided. A positioning method for UAV using acceleration, gyro, and magnetic sensors to solve the shift error could be utilized with using lazy recalibration method.
1. Q-learning algorithm
Q-learning algorithm is a kind of model-free reinforcement learning algorithm. It can be used for optimal action-selection policy in the Markov decision process (MDP). Q-learning may use action-value function to learn how to maximize the reward for the current action. That is, the agent can operate according to the policy, and the optimal policy can be configured by selecting the action having the highest value among the action-value functions as the reward for each action. One of the strengths of Q-learning is that it is able to compare
the expected utility of available operations without the need for an environmental model. The specific algorithm is like below [14].
←
max
(1)
In this equation is the current state and is the current action. Then we can know the next state , next action and its reward . is the learning rate and is the discount factor.
Fig. 4. Various learning maps
Map creation module may create learning environments as shown in Fig. 4 may create indoor environment for autonomous flight of UAV. It must consist of four elements: wall, obstacle, starting point and arrival point.
Each of the four components has a reward value of wall:
-10, obstacle: -10, starting point: 0, and arrival point: 50.
Maps are represented by x and y axes, and obstacles and destination points are created at specific coordinates.
2. UAV position and Laxy Recalibration
Ideally, by using formula
, we canestimate the position of the UAV by simply integrating the acceleration value twice. However, we cannot use acceleration sensor’s raw data because acceleration sensor also measures the acceleration of gravity. Therefore we first need to remove gravity acceleration value from the measured data to get the net acceleration. Knowing UAV’s orientation in pitch, roll, and yaw value, we can simply get the net acceleration by subtracting the acceleration of gravity extracted in x,y,z components. We used Kalman
filter to calculate UAV’s orientation from acceleration, gyro, magnetic sensors.After we figure out the pitch, yaw, and roll value, we can get net accelleration value by extracting x,y,z value from the gravity acceleration and subtracting them from the raw data. Following formula shows the method.
If we let and be the acceleration value we measured at time , solving the following expression will get us the velocity at each measured time and position
, where is the final position of an UAV that we need.
× ∆
× ∆(2)
Since we rely on acceleration sensor which needs double integration to get to the final positioning, even if we only get small errors in each measurement, they may accumulate to form a huge error in the final stage. To minimize this problem, we used re-calibration at the landing state of the UAV. If the UAV landed at some point, the velocity should be 0. However, if the error stacked during integration, the calculation would not result in 0. So if ≠ , we can re-calibrate to 0 and change to accordingly. Following is the pseudo-code of a simple re-calibration method we used.
for k = 1 to n-1 ×
(3)
Ⅳ. Simulation Environment
We will learn four virtual maps generated by the map creation module. In Ubuntu OS environment, we can learn by using Q-learning module written in Python language.
The learning conditions may be set as learning rate: 0.1 and discount factor: 0.9, which are repeated 300, 500, and 1000 times, respectively.
The simulator creates a virtual space for the UAV to fly and show its results visually. The simulator gives directions (forward, backward, left, right) to the UAV so that it can be operated. Here, no external environmental variables such as air resistance, wind and air temperature
will be considered and the virtual space of the simulator has the same environment as the map creation module.
We are going to use sensor hub SGO100 model from Standing Egg, which contains tri-axil acceleration, gyro, magnetic sensors. The sensor hub can be connected with Desktop PC with WIFI to record each measurement. For more accurate results, we may use two sensor hubs for measuring, and average values between the two.
Recording will be done in about every 20ms, but since the measuring process also may consume up to 20ms, the measuring took 20-40ms period in practice. As for UAV model AR.Drone2.0 from Parrot to load the sensor hub and fly in our track. The UAV is to be programmed to move forward by 10m forward, turn left, move 50m forward, turn left, and move 50m forward again. The flight may take almost 200 seconds.
V. Conclusion
This paper provided a brief introduction on current researches of small UAVs and proposed a draft idea for planning paths for small unmanned aerial vehicles in adversarial environments to arrive at the given target safely with low cost sensors. For this purpose, this paper creates a map that assumes an indoor environment and suggests a path planning method through reinforcement learning and UAV positioning technique using lazy recalibration. Future work will include real implementations and simulation results.
ACKNOWLEDGMENT
This work was supported by the National Research Foundation of Korea(NRF), grant funded by the Korean government (MSIP:Ministry of Science, ICT and Future Planning) (2016M1B3A1A019376)
REFERENCES
[1] Guowei Cai, Jorge Dias, Lakmal Seneviratne, Unmanned Systems, Vol. 2, No. 2,World Scientific Publishing Company, 2014, 1–25
[2] R. Yanushevsky, Guidance of Unmanned Aerial Vehicles, CRC Press, 2011.
[3] The Global UAV Market 2015–2025
[4] Siam Menna, Ramy ElSayed, and Mohamed ElHelw,
On-board multiple target detection and tracking on camera-equipped aerial vehicles. Robotics and Biomimetics (ROBIO), 2012 IEEE Int’l Conference on IEEE, 2012 [5] S. Baek, F. Bermudezand R. Fearing, Flight control for
target seeking by 13 gramornithopter, Intelligent Robotsand Systems, CA, 2011, 286–292.
[6] R. Austin, Unmanned Aircraft Systems: UAVs Design, Development, and Deployment, Wiley, 2010
[7] H. Chao, Y. Cao and Y. Chen, Autopilots for small unmanned aerial vehicles: A survey, Int. J. Control Autom. 8(1), 2010, 36–44.
[8] Roberge, V., Tarbouchi, M., & Labont, G., Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning. IEEE Transactions on Industrial Informatics, 9(1), 2013, 132-141.
[9] Chen, H., Chang, K., & Agate, C. S., UAV path planning with tangent-plus-Lyapunov vector field guidance and obstacle avoidance. IEEE Transactions on Aerospace and Electronic Systems, 49(2), 2013, 840-856.
[10] Chicarella, S., Ferrara, V., Frezza, F., D'Alvano, A., &
Pajewski, L. (2016, December). Improvement of GPR tracking by using inertial and GPS combined data. In Software, Telecommunications and Computer Networks, 2016 24th Int’l Conference on, pp. 1-5.
[11] Bhatia, S., Yang, H., Zhang, R., & Reindl, L. (2016, March).
Development of an analytical method for IMU calibration. In 2016 13th Int’l Multi-Conference on Systems, Signals &
Devices (SSD), 131-135.
[12] Angelino, C. V., Baraniello, V. R., & Cicala, L. (2012, July).
UAV position and attitude estimation using IMU, GNSS and camera. In Information Fusion, 2012 15th Int’l Conference on, 735-742.
[13] Xu, L., & Luo, H. (2016, June). Towards autonomous tracking and landing on moving target. In Real-time Computing and Robotics (RCAR), IEEE Int’l Conference on, 620-628
[14] YAU, Kok-Lim Alvin; KOMISARCZUK, Peter; TEAL, Paul D. A context-aware and intelligent dynamic channel selection scheme for cognitive radio networks. In: Cognitive Radio Oriented Wireless Networks and Communications, 2009. CROWNCOM'09. 4th International Conference on.
IEEE, 2009. p. 1-6.
저자
신 새 벽(Saebyuk Shin)
․2015년 2월：연세대학교 컴퓨터과학 과 학사졸업
․2015년 3월~현재：연세대학교 컴퓨터 과학과 통합과정
<관심분야> : 무인이동체, 인공지능, 자율 행동
김 진 배(Jinbae Kim)
․2016년 2월 : 호서대학교 컴퓨터공학 과 학사졸업
․2016년 2월 ～ 현재 : 연세대학교 컴퓨 터과학과 석사과정
<관심분야> : 무인이동체, 인공지능, IoT
김 신 덕(Shin-Dug Kim)
․1982년 2월 : 연세대학교 전기전자공 학과 학사졸업
․1982년 8월：Univ. of Oklahoma 컴퓨 터공학과 석사졸업
․1991년 12월：Purdue University 컴퓨 터공학과 박사졸업
․1995년 ～ 현재：연세대학교 컴퓨터과학과 교수
<관심분야> : advanced computer systems, intelligent memory system design, 유비쿼터스 컴퓨팅 플랫폼
김 정 길(Cheong Ghil Kim) 종신회원
․1987년 8월：Univ. of Redlands, USA 컴퓨터과학과 학사졸업
․2003년 8월：연세대학교 컴퓨터과학 과 공학석사 졸업
․2006년 8월 : 연세대학교 컴퓨터과학 과 공학박사 졸업
․2006년 ～ 2007년 : 연세대학교 컴퓨터과학과 박사후 연구원
․2007년 ～ 2008년 : 연세대학교 컴퓨터과학과 연구교수
․2008년 ～ 현재 : 남서울대학교 컴퓨터학과교수
<관심분야> : 멀티미디어 임베디드 시스템, 이기종 컴퓨팅, 모바일 AR, 3D Contents
