ISSN 20751087, Gyroscopy and Navigation, 2010, Vol. 1, No. 4, pp. 279–284. © Pleiades Publishing, Ltd., 2010. Published in Russian in Giroskopiya i Navigatsiya, 2009, No. 2, pp. 3–11.
Adaptive Path Planning for VTOLUAVs O. Meister, N. Frietsch, Ch. Ascher, and G. F. Trommer Institute of Systems Optimization, University of Karlsruhe, Karlsruhe, Germany Received April 21, 2009
Abstract—This paper addresses the development of an adaptive path planning algorithm for a small vertical takeoff and landing (VTOL) unmanned aerial vehicle (UAV) with a take off weight below 1 kg. The UAV was developed for versatile surveillance and reconnaissance applications in closeup range up to 10 km. The UAV platform with the onboard navigation system is described. Improvements of new adapted ranging sensors— mandatory for adaptive path planning algorithms—on the platform are discussed. The adaptive path plan ning algorithms including collision avoidance strategies of the platform are investigated. The development of a powerful simulation environment of the complete UAV including identified sensor characteristics which is essential for developing and testing of path planning algorithms is presented. The benefits of different plan ning algorithms are discussed and compared using a powerful simulation tool and validated by real test flight experiments. DOI: 10.1134/S2075108710040073
INTRODUCTION Unmanned aerial vehicles (UAV) can be used for surveillance and reconnaissance purposes. The first fields of applications were mainly in the domain for military users. The platforms were expensive, large and heavy and also required the support of infrastructure. Due to maturing and miniaturization of applicable technologies during the last decades nowadays versa tile UAV systems are available for civil applications as well—e.g., support of rescue forces, security, photo grammetry, aerial photographs, etc. If a UAV is capable of flying automatically on a pre defined path, the range of possible applications is wid ened significantly: Surveillance tasks can be auto mated, and as the operator does not need to pilot the vehicle he can focus on the mission goals. Wind influ ences and other disturbances are compensated auto matically. With the help of an adaptive path planning frame work a further increase of the level of autonomy can be achieved. During missions in urban environments interferences with obstacles can occur easily. There are several reasons why this problem can arise. First, the underling planning data from the georeferenced maps, terrain elevation models or geographic infor mation system (GIS) can be inaccurate, obsolete or even absence. Second, the data can be incomplete e.g. no data about vegetation like trees is available. Third, due to outer influences like wind disturbances the UAV position does not match with the predefined flight path. An adaptive path planning algorithm using addi tional sensor information can help the UAV to avoid collisions with obstacles without the need for a pilot. Path planning algorithms have been applied to a variety of applications of mobile robots [1–3, 10, 11].
Due to the limited degree of freedom of driving robotic platforms most path planning algorithms cope with two dimensional problems like the bug algorithm [9] or improvements like bug2 [8] or tangentbug [6]. In the dynamic windows approach (DWA) [4] the dynamics of the robot platform are also considered. These path planning strategies cannot dispose directly to the three dimensional problems of an UAV plat form. Most of the algorithms run in hierarchical steps [7]. In the top layer, an optimized trajectory information is generated. The middle layer is the execution layer where, the optimized trajectory information is used in order to follow the preplanned path together with a subroutine called in case of detected obstacles. The lowest layer imparts the set values from the upper layers into actuator commands to control the UAV position. This paper addresses the development of an adap tive path planning algorithm for a small VTOL UAV with a take off weight below 1000 g. The UAV platform with the onboard navigation system is described in Section 2. Also improvements of new adapted ranging sensors—mandatory for adaptive path planning algo rithms—on the platform are discussed. Section 3 focuses on the adaptive path planning algorithms including collision avoidance strategies of the plat form. In Section 4, the development of a simulation environment of the complete UAV which is essential for developing and testing of path planning algorithms is presented. In Section 5, the results of the simulation and experiments are presented. Finally, conclusions are drawn in Section 6.
279
280
MEISTER et al.
Fig. 1. VTOLUAV in flight with camera payload.
UAV PLATFORM The platform of the fourrotor VTOLUAV with a take off weight below 1000 g and a maximal diameter of less then 1 m is shown in Fig 1. With these properties it belongs to the class of micro aerial vehicles. The platform can carry payloads of 200 g for sensors and optical cameras in missions up to 25 min—which allows an operation range of more than 5 km. Due to small dimension and the capability to hover, the rotary winged UAV is well suited for mis sions in urban environments. This vehicle is controlled by the speed of the rotors only. A major advantage of this design is the mechanical simplicity. Navigation System The onboard navigation system consists of low cost MEMS inertial sensors. Due to inherent sensor errors augmentation with complementary sensors is manda tory. Employed with a GPS receiver—for position and velocity information—a magnetometer—for deter mination of the north direction—and a baro altimeter for precise height information a long term precise nav igation information was realized. For the integration a robust error state space Kalman filter was developed (block diagram shown in Fig. 2).
GPS
MAG
BALT
Fig. 2. MEMS based navigation system.
Payload and Sensors Because of the limited payload capacity only small scale sensors can be used. This induces that the perfor mance of those sensors are limited. For an adaptive path planning, it is mandatory to sense the environ ment of the UAV in order to evade collisions with obstacles. Primary sensors for that application are ranging sensors. There are several sensor technologies that can be considered here. Table shows a comparison of different available ranging sensor modules suitable for the platform. Beside the difference in range the sensors also vary in the azimuth angle direction. The IR sensor is very narrow and also very sensitive for sun light and there fore only applicable for indoor environments. The ultrasonic module SRF08 has a broad beam pattern but has no azimuth information it only gives the short est range to the nearest obstacle. The most powerful sensor is the URG04LX LASER range finder. It has an azimuth range from 240° with a resolution of 0.36°. Especially in the horizontal plane the direction infor mation is mandatory for a robust collision avoidance
Ranging sensor modules Technology
IR
Ultrasonic
2D LASER
Module
Sharp 2Y0A02
Devantech SRF08
Hokuyo URG04LX
Range
0.20–2.00 m
0.03–6.00 m
0.01–4.00 m
Weight
4g
7g
160 g
GYROSCOPY AND NAVIGATION
Vol. 1
No. 4
2010
ADAPTIVE PATH PLANNING FOR VTOLUAVs (а)
(b)
2Y0A02
281 (c)
SRF08
URG04LX
Fig. 3. Ranging sensor modules.
Fig. 4. Global path planning.
functionality. With the limited payload capacity of the UAV, the following configuration of the sensor devices was selected: Two ultrasonic rangefinder SRF08 for the vertical obstacle detection and auto landing—up and downlooking. One URG04LX LASER range finder for the horizontal plane—center frontlooking and 120° to either side. The IR sensor 2Y0A02 is not applicable for outdoor environments. The sensors are shown in Fig. 3. ADAPTIVE PATH PLANNING As mentioned before most path planning algo rithms run in hierarchical steps. The first step is the optimized global path planning which is realized in a GYROSCOPY AND NAVIGATION
Vol. 1
No. 4
pre flight setup phase. During this path planning phase the operator specific the trajectory information by positions and observation point data. With the help of georeferenced maps terrain elevation modules, or a precise geographic information system (GIS) the operator has a easy to handle toolbox. The current path is displayed that the operator can identify inter ferences with surrounding know obstacles—see Fig. 4. Beside the basic information concerning position and height the planning tool influences also on the dynamic of the UAV. In higher elevations where no obstacles are expected higher velocities are set. In lower elevations nearby buildings the velocity is reduced.
2010
282
MEISTER et al. Analyze Navigation system State propagation
Path planning guidance UAV dynamics
Flight control
+
Force calculation Disturbances
Fig. 5. SiL simulation block diagram.
The operator can also influence the reaction of the UAV when unexpected incidences occur. These inci dences are loss of the radio link connection to the base station, loss of GPS information, and critical battery charge condition. Reactions on those incidences can be e.g., return to the home position in a secure height level, initiate an emergency landing or climb/sink to reestablish the radio link to the base station. The out put of the global path planning phase is a detailed tra jectory information that is stored for the actual flight phase onboard the UAV platform. During the flight phase, the path planning onboard the UAV is realized using the specified information on current trajectory. Because of high dynamics of the UAV platform, the path planning algorithms onboard must be optimized in order to achieve a smooth flight trajectory. This is essential for missions especially with imaging sensors. Rough trajectories would have bad influences on the quality of the acquired image data. A cascaded position and velocity controller were developed to realize that. The flight information from the global path planning algorithm is given in absolute navigation coordinates. The guidance algorithm transforms that information with the attitude informa tion into the body coordinates. This normal flight mode is active as long as the distance to nearby obsta cles is not below a certain threshold. In case that obstacles underrun this defined lower threshold the collision avoidance subroutines becomes active. This subroutine is responsible to avoid interfer ences with obstacles. The preplanned trajectory is left and the algorithm start searching for alternate paths to the defined destination. A UAV has obviously more possibilities to deter mine a new path to the destination than a driving plat form. A flying platform can change its horizontal and vertical position along obstacles to avoid them. There fore the search domain becomes three dimensional which yield to tremendous calculation effort. To make that feasible onboard such small UAV vehicles with limited calculation power, the collisions avoidance algorithm search separate in the vertical and horizon tal planes.
The vertical collision avoidance avoids obstacles by climbing along the boundary to surmount them. In the horizontal collision avoidance case the UAV avoid the obstacle by horizontal movements along the boundary. Both algorithms must ensure that the sensed obstacle keeps in view of the ranging sensor devices. This was solved in the horizontal plane by a modi fied dynamic window approach (DWA). This algo rithm has the advantage that the dynamic of the plat form can be considered too. The LASER range sensor acquires the cutting between the obstacle and the two dimensional scanning plane. The DWA calculates based on the current position and velocity and the tol erable dynamics of the vehicle a set of admissible velocities that avoid the obstacle successfully. In this stage the best admissible velocity is determined by three factors: —heading (small angular difference between new estimated position and attitude of the UAV to the planned target), —distance (highest distance to the obstacle), and —velocity (higher velocities are preferred). The sensor only provides two dimensional ranging or only ranging information in case of the LASER or ultrasonic sensors respectively. In order to determine the lowest distance to the obstacle several assumptions were made. First, the surface of the obstacles is rectan gular. Second, the detected obstacles are lengthen in downwards direction to the ground and lengthen 2 meters in upward direction. This tends to bigger assumed obstacles in the vertical direction. Without this assumption, robust collision avoidance with the described sensors devices was not possible. SIMULATION ENVIRONMENT For the evaluation of the path planning algorithms a powerful simulation environment was developed. Due to the closed loop between the path planning algorithms generating the set values of the UAV and the vehicle state comprising position, velocity, and attitude the path planning must consider the dynamics and state transition of the UAV. This can be shown by the example of the collision avoidance subroutine. When the onboard sensors determine an nearby obsta cle the collision avoidance will calculate new set values for position and velocity in order to avoid a collision. This results in a different attitude of the UAV which has a direct influence of the now available sensor data of the onboard sensors. Each sensor onboard has it own set of parameters defining the position, orienta tion and coverage area. In case of the two dimensional LASER scanner the position is at the center of the UAV looking forward, in the horizontal plane. For an easy developing process the simulation was realized using softwareintheloop (SiL). The whole operational software onboard the UAV is also used in the SiL. Only the interfaces like sensor data are gener
GYROSCOPY AND NAVIGATION
Vol. 1
No. 4
2010
ADAPTIVE PATH PLANNING FOR VTOLUAVs
283
Up, m 20 15 10 5 0 50 40 30 20 North, m
10 0
20
10
0
30 East, m
50
40
Fig. 6. Result vertical collision avoidance.
50 45 40 35
Up, m
30
40 20 0 0
25 North, m 20 15 10 5
10
15
5 20 25 East, m
30
35
40
0
Fig. 7. Result horizontal collision avoidance.
ated with the simulation. Figure 5 shows the block dia gram of the SiL simulation tool. The blocks from the upper are implemented onboard the microcontroller of the UAV.
fied transfer functions of the motors the acting forces on the airframe. The vehicles state is propagate with the UAV dynamic model to calculate the new sensor data set for the next loop.
The navigation system determines the state of the UAV. The path planning calculate the set values for position, velocity, and attitude according to the stored path. The flight controller represents the low level controller of the UAV for attitude and height which outputs the set values for the motor actuators. The lower line is the framework from the simulation envi ronment. It calculates from set values with the identi
The parameters of the simulation were obtained by real test flights. These test flight implied dedicated maneuvers allowing the identification of the moments of inertia etc. The relationship between the motor commands and the resulting lift forces was obtained by measurements. Hereby, the dynamical behavior was identified too.
GYROSCOPY AND NAVIGATION
Vol. 1
No. 4
2010
284
MEISTER et al.
RESULTS With the help of the SiL it is possible to analyze and compare the performance and robustness of the implemented adaptive path planning algorithms. Dur ing missions in urban environments the implemented adaptive path planning algorithms enable the UAV to avoid collisions. Figure 6 shows the result of the collision avoidance where the UAV platform approaches an obstacle dur ing the transfer between two planned path points of the trajectory. The red dots on the boundary of the obstacle represent the measurements of the two dimensional LASER range finder. The UAV is capable to avoid the collision that otherwise obviously would have occurred. The downlooking ultrasonic sensor ensures an ade quate clearance to the top of the obstacle. Figure 7 shows the result of the horizontal collision avoidance. The algorithm allows the UAV to fly along the contour of the obstacle. Even in situations with cluttered environment the UAV has the ability to per form sharp turns. Due to the limited sensor range and therefore short notice time the velocity of the UAV has to be small. Otherwise the UAV is not able to decelerate in time. First tests with the characteristics of three dimensional ranging devices with an extended range shows that this is not longer a limiting factor. In such scenarios the notice time is sufficient to avoid collisions with obsta cles at higher velocities.
new sensor technologies and more calculation power further improvements like advanced collision notice and global path planning onboard small UAVs are attainable. ACKNOWLEDGMENTS The authors wish to thank the Microdrones GmbH. REFERENCES 1. Brock, O. and Oussama, K., HighSpeed Navigation Using the Global Dynamic Window Approach, Pro ceedings of the IEEE International Conference on Robot ics and Automation, 1999. 2. Dong, A. and Hong, W., VPH a New Laser Radar Based Obstacle Avoidance Method for Intelligent Mobile Robots, Intelligent Control and Automation, WCICA, Fifth World Congress, 2004, vol. 5, pp. 4681– 4685. 3. Egerstedt, M., Hu, X., Rehbinder, H., and Stotsky, A., Path Planning and Robust Tracking for a Car Like Robot, Proceedings of the 5th Symposium on Intelligent Robotic Systems, 1997, pp. 237–243. 4. Fox, D., Burgard, W., and Thrun, S., The Dynamic Window Approach to Collision Avoidance, IEEE Robotics Automation Magazine, 1997, vol. 4, pp. 23–33. 5. Gutmann, J.S., Fukuchi, M., and Fujita, M., Real Time Path Planning for Humanoid Robot Navigation, Proceedings of the International Joint Conference on Arti ficial Intelligence, 2005, pp. 1232–1238. 6. Kamon, I., Rimon, E., and Rivlin, E., Tangent Bug A RangeSensorBased Navigation Algorithm, Int. J. Robotics Res., 1998, vol. 17.
CONCLUSIONS This paper described the development of path planning algorithms of a small unmanned fourrotor helicopter. A simulation environment of the whole UAV system—including the characteristics of the ranging sensors for the collision avoidance was devel oped. This is essential for the developing, testing, and verifying of the algorithms. Different collision avoid ance strategies for VTOL UAVs were presented. Enhancements and miniaturization will offer more powerful sensor technologies regarding size, range and power in future. Very promising are improvements of sensor modules and new technologies like three dimensional LASER range finder, PMD sensors, RADAR range finder, and stereo camera tracking sys tem. Because of the general high level simulation tool introduced in this paper they can be easily validated and tested without the need and effort of a real hard ware implementation. The results showed that adaptive path planning including collision avoidance is already applicable onboard of small UAV vehicles. With the mentioned
7. Latombe, J.C., Robot Motion Planning, Kluwer Aca demic, 1991. 8. Lumelsky, V.J. and Skewis, T., Dynamic Path Planning for a Mobile Automaton with Limited Information on the Environment, Automatic Control, IEEE Trans., 1986, vol. 31, pp. 1058–1063. 9. Lumelsky, V.J. and Skewis, T., Incorporating Range Sensing in the Robot Navigation Function, Systems, Man Cybernetics, IEEE Trans., 1990, vol. 20. 10. Shigang, C., Zhengguang, L., Li, Z., Zhigang, B., and Hongda, C., Design and Path Planning for a Remote Brained Service Robot, Natural Computation ICNC 2007, Third International Conference (2007). 11. Wzorek, M. and Doherty, P., Reconfigurable Path Planning for an Autonomous Unmanned Aerial Vehi cle, Proceedings of the 16th International Conference on Automated Planning and Scheduling, pp. 438–441. 12. Xu, Z., Schwarte, R., Heinol, H., Buxbaum, B., and Ringbeck, T., Smart Ppixel—Photonic Mixer Device (PMD), New System Concept of a 3DImaging Cam eraonaChip, PMDTec Technical Report, 2005.
GYROSCOPY AND NAVIGATION
Vol. 1
No. 4
2010