Optimal Trajectory Generation for UAVs Using Dynamic Trajectory Modeling

Optimal Trajectory Generation for UAVs Using Dynamic Trajectory Modeling Alfonso Valenzuela, Damián Rivas, Francisco Gavilán and Rafael Vázquez Department of Aerospace Engineering, Escuela Superior de Ingenieros, Universidad de Sevilla, 41092 Sevilla, Spain, [email protected] Abstract The generation of optimal trajectories for UAVs in the presence of an average horizontal wind is studied. The generation is performed off line (strategic planning). The approach is based on the discretization of the aircraft intent and in the formulation of a parametric optimization problem. For the computation of the trajectory, a dynamic, nonlinear, point-mass model with three degrees of freedom is considered. Keywords: UAV, optimal trajectory generation, dynamic modeling, wind effects. 1 INTRODUCTION The operation of autonomous UAVs require the generation of flyable trajectories that serve as reference for the guidance and control system. These trajectories are, in general, subject to constraints, which complicate the generation process; these constraints arise, among other sources, from the environment (obstacle clearance), from the UAV itself (operational envelope), and from the mission to be carried out. For an overview of this problem see for example Tsourdos et al. [1], where they analyze the more general problem of cooperative path planning for a group of UAVs. Path planning can be seen as one of the layers of the UAV control system, along with the guidance and control (autopilot) layers. Voelker et al. [2] analyze this 3-layer scheme in the case of horizontal trajectories, using a kinematic model. In this work the problem of generation of optimal trajectories is studied, for a given optimality criterium, in the presence of an average wind. The generation is performed off line (strategic planning). The approach considered is based on the discretization of the aircraft intent (which guarantees that the trajectory generated is flyable) and in the formulation of a parametric optimization problem. Once the aircraft intent is discretized, it is defined in terms of a set of parameters, some of which may be fixed (by the mission) whereas some others are free; the optimation is performed on this set of free parameters. This approach has been used by Gill and Maddock [3] and Valenzuela et al. [4] in the optimization of 4D 1 Proc. of the 1st Workshop on Research, Development and Education on Unmanned Aerial Systems (RED-UAS 2011) Seville, Spain, Nov 30th - Dec 1st, 2011 ISBN-978-84-615-6269-5 29 aircraft trajectories, and by Valenzuela and Rivas [5] in the problem of conflict resolution in air traffic management, in which one seeks optimal trajectories free of conflicts. For the computation of the trajectory, the UAV motion is described by a dynamic, nonlinear, pointmass model with three degrees of freedom, which is commonly used for trajectory prediction (see Slattery and Zhao [6]). This model provides more accuracy than other simpler kinematic models also used for path planning. Results are presented for a small fixed-wing UAV (14 kg of mass) powered by fuel cells. 2 PROBLEM DEFINITION The general arquitecture of the problem of generating optimal trajectories is represented in Fig. 1. The input to the optimal trajectory generator (OTG) is the data that define the mission to be performed, which are supplied by the user, and the output is the optimal trajectory y∗(t), where yis the state vector of the UAV. OTG MISSION TCI Figure 1: OTG interfaces. To obtain the trajectory the OTG requires the use of a trajectory computation infrastructure (TCI). This module computes flight segments, which are the elements that form the trajectory. The input to the TCI is in fact a set of parameters which define the trajectory; some of these are free (x), that is, they are the optimization parameters, and some others are fixed (e x). The output is the trajectory y that corresponds to these parameters. In the following sections the mission, the OTG and the TCI modules are described. 3 MISSION To define the mission the user must specify the following sets of data: a) flight plan, b) UAV configuration, c) optimality criterium, and d) wind. a) The flight plan is defined, first, by the horizontal path (the two-dimensional waypoints to be flown), and, second, by the altitudes and speeds with which the UAV is to fly between waypoints. The waypoints must be fixed by the user, who can also fix both altitudes and speeds, although this is optional (those which are not fixed, are free values to be determined by the optimization process). b) For a given UAV platform and a given mission the user must define the payload and the fuel load (or, the weight of the batteries or fuel cells). These two weights plus the known operating empty weight of 2 Proc. of the 1st Workshop on Research, Development and Education on Unmanned Aerial Systems (RED-UAS 2011) Seville, Spain, Nov 30th - Dec 1st, 2011 ISBN-978-84-615-6269-5 30 the UAV determine the take-off weight, which is an important parameter for the computation of the trajectory. In this work the UAV is driven by an electric motor powered by fuel cells. c) The user must define an optimality criterium, which in turn defines the objective function for the optimization. In this work the optimality criterium is minimum energy consumption. d) Wind is an important factor that greatly affects the trajectory of the UAV. The user must define an average wind to be taken into account in the trajectory computation process, depending on the expected wind during the mission. The difference with the actual wind during the flight must be taken care of by the guidance and control system. In this work a nominal horizontal wind is considered, constant both in speed and direction. 4 OPTIMAL TRAJECTORY GENERATOR The optimal trajectory generator (OTG) is formed by two modules: the trajectory discretization module (TDM) and the optimizer (OPT), as shown in Fig. 2. They are described next. TDM USER MISSION OPT TCI OTG Figure 2: OTG structure. 4.1 Trajectory discretization module In this work, the discretization of the trajectory is based on the flight segments that form the trajectory. These flight segments are defined by three flight constraints (in the case of symmetric flight), for example, constant heading, altitude and speed; when a flight constraint changes a new flight segment is defined. The flight constraints are defined by a number of parameters, some of which are fixed and some others may be free, subject to the optimization process. The TDM defines the two sets of free and fixed parameters, as well as the constraints to which the free parameters are subject. Thus, once the flight segments are defined, the input to the TDM is the set of fixed parameters defined by the mission (e x1) and the output is the set of fixed parameters of the 3 Proc. of the 1st Workshop on Research, Development and Education on Unmanned Aerial Systems (RED-UAS 2011) Seville, Spain, Nov 30th - Dec 1st, 2011 ISBN-978-84-615-6269-5 31 problem (e x), the set of free parameters (x) and the constraints to which the free parameters are subject (g). The flight segments are obtained after defining the horizontal and vertical profiles. These profiles can be defined with different levels of detail, but if the level of detail increases then the computational cost also increases (for example, the computation of turns usually requires an iterative procedure). To simplify the computation process, turns, pull-ups and push-downs are not considered. Then, heading and path angle changes are performed instantaneously. As a consequence, the heading angle and the path angle will be discontinuous variables. These discontinuities will be smoothed out by the guidance and control system. The horizontal profile is defined by the waypoints (see Fig. 3). Waypoints WP1,..., WPnare those defined by the user. Waypoints WP0and WPn+1 are needed to define the climb and descent phases, as shown below. WPn+1 and the top-of-descent (TOD) point are calculated iteratively.  Figure 3: Horizontal profile. The vertical profile is defined by the following phases (see Fig. 4): a) initial phase, b) mission phases, and c) final phase. Next, these phases and its segments are described. a) The initial phase consists of the following flight segments (the numeration is that shown in Fig. 4a): 1. Initial climb: rectilinear segment up to the altitude AGL ∆h0, performed at runway heading, constant path angle γ0and constant airspeed V0(γ0and V0are defined by default). 2. Turn: instantaneous heading change towards WP1. 3. Acceleration: rectilinear segment up to the airspeed V1, performed at constant heading, constant altitude and constant acceleration. 4. Climb: performed at constant heading, constant airspeed (V1) and constant electric power, up to the altitude h1(TOC point - Top Of Climb). b) The mission phases can be executed at different altitudes and speeds. Each mission phase, for each waypoint, consists of the following flight segments (the numeration is that shown in Fig. 4b): 1. Cruise: horizontal rectilinear segment, performed at constant heading, constant altitude hiand constant airspeed Vi, up to the waypoint WPi. 2. Turn: instantaneous heading change towards next waypoint WPi+1. 3. Acceleration/deceleration: rectilinear segment up to the airspeed Vi+1, performed at constant heading, constant altitude hiand constant acceleration. 4. Climb/descent: performed at constant heading, constant airspeed (Vi+1) and constant electric power, up to the altitude hi+1. c) In the final phase, the aircraft goes from the final waypoint to the runway. In this phase it is of great importance to determine the position of the TOD (Top Of Descent), that is, the point at which the 4 Proc. of the 1st Workshop on Research, Development and Education on Unmanned Aerial Systems (RED-UAS 2011) Seville, Spain, Nov 30th - Dec 1st, 2011 ISBN-978-84-615-6269-5 32 UAV starts the descent to the final altitude hf. This phase consists of the following flight segments (the numeration is that shown in Fig. 4c): 1. Cruise: horizontal rectilinear segment, performed at constant heading, constant altitude hn+1 and constant airspeed Vn+1, up to the TOD. 2. Descent: performed at constant heading, constant airspeed (Vn+1) and constant electric power, up to the altitude AGL ∆hf. 3. Turn: instantaneous heading change towards runway. 4. Deceleration: rectilinear segment up to the approach airspeed Vap, performed at constant heading, constant altitude and constant acceleration. 5. Final descent: rectilinear segment up to the touch-down point, performed at runway heading, constant path angle γfand constant airspeed Vap (γfand Vap are defined by default). 1 3 4 2 (a) 13 4 13 4 1 3 4 1 2 2 2 (b) 1 2 4 5 3 (c) Figure 4: Vertical profile: a) initial phase; b) mission phases; c) final phase. The set of free parameters is formed by the altitudes hiand the speeds Vinot fixed by the user. The optimization is performed on this set of free parameters. The fixed and free parameters are subject to constraints that, on one hand, guarantee that the UAV is capable to fly the trajectory and, on the other hand, guarantee that the trajectory can be computed by the TCI module. The constraints are: 1. The speeds and altitudes are inside the operational flight envelope of the aircraft. 2. The distance between two waypoints is greater than the minimum necessary distance to perform the turns associated to both waypoints. 3. The speed V1is greater than V0(this constraint is added to ensure that the segment 3 of the initial phase is always an acceleration segment). 4. The speed Vn+1 is greater than Vap (this constraint is added to ensure that the segment 4 of the final phase is always a deceleration segment). 5. The position of the TOC is between the waypoints WP0and WP1. 6. The position of the TOD is between the waypoints WPnand WPn+1. 7. The necessary distance to accelerate/decelerate (segment 3 of the mission phase) and climb/descend (segment 4) between two waypoints is smaller than the distance between both waypoints. 8. The absolute value of the path angle 5 Proc. of the 1st Workshop on Research, Development and Education on Unmanned Aerial Systems (RED-UAS 2011) Seville, Spain, Nov 30th - Dec 1st, 2011 ISBN-978-84-615-6269-5 33 in all climb/descent segments is less than 10 degrees (to avoid sharp changes in path angle). 9. The heading changes are less than 120 degrees (to avoid too narrow inside turns which would take the actual trajectory far from the nominal waypoint). 4.2 Optimizer The parametric optimization is performed on the set of free parameters (x) once the objective function (f) and the constraints (g) are defined. The problem is formulated as follows: minimize f(x) subject to g(x)≤0. (1) For the optimality criterium of minimum energy consumption considered in this work, the objective function is given by f=Ztf 0 Pedt, (2) where Peis the electric power generated on board and tfis the flight time. Both variables depend on the value of the fixed and free parameters. In this work, the optimization solver used is MATLAB’s fmincon, a sequential quadratic programming (SQP) method (see Fletcher [7], for example). 5 TRAJECTORY COMPUTATION INFRASTRUCTURE In this work the model adopted to describe the UAV motion is that of a point mass with three degrees of freedom commonly used for trajectory prediction (Slattery and Zhao [6]); the equations then describe the motion of the UAV center of mass. Since the UAV is driven by an electric motor powered by fuel cells, its mass can be considered constant. Since turns are not considered, in each segment the flight takes place in a vertical plane defined by a heading angle χA. The scalar equations of motion are then the following mdV dt=ηmp(Pe, V, h)Pe V−D(V, h, L)−mg sin γ, mV dγ dt=L−mg cos γ, dx dt=Vcos γcos χA+wx, dy dt=Vcos γsin χA+wy, dh dt=Vsin γ. (3) In these equations V,γare the modulus and the path angle of the aerodynamic speed (true aerodynamic speed TAS), x,y,hare the topocentric coordinates of the UAV center of mass, mis the UAV mass, tthe time, Pethe electric power supplied by the fuel cells, ηmp the overall efficiency of the propulsion system, Lthe lift, Dthe aerodynamic drag, and wx,wythe components of the wind speed on the x,ydirections. 6 Proc. of the 1st Workshop on Research, Development and Education on Unmanned Aerial Systems (RED-UAS 2011) Seville, Spain, Nov 30th - Dec 1st, 2011 ISBN-978-84-615-6269-5 34 In this work the following simplifications are considered: parabolic drag polar of constant coefficients CD=CD0+CD2C2 L, constant overall efficiency ηmp =constant, negligible normal acceleration dγ dt= 0, and constant air density ρin each flight segment (depending on the average altitude). The drag and lift coefficients (CDand CL) are defined by D=1 2ρV 2SCDand L=1 2ρV 2SCL, where Sis the wing surface area. In the computation of the trajectory, the previous equations must be particularized for each flight segment. To compute a given segment, the initial and stopping conditions must be defined. In this work the following stopping conditions are considered: a) reach a given speed, b) reach a given altitude, and c) reach a given waypoint. 6 RESULTS In this section, results obtained for four different cases are shown. In the first one, a reference mission is optimized and the results are compared to a non-optimized trajectory. In the second case, wind is included and the results are compared with the reference mission. Next, a trajectory is analyzed in which the waypoints provided by the user imply heading changes greater than 120 degrees. Finally, another trajectory is analyzed in which the user fixes the altitudes of two waypoints but the distance between them is too short to climb/descend. The specifications of the UAV model considered in all the cases are: m=14 kg, CD0=0.0229, k=0.0174, ηmp =0.56, maximum electric power Pe,max =500 W, minimum electric power Pe,min =0 W. The following values have been considered to define the trajectory: maximum altitude hmax =300 m, minimum altitude hmin =55 m, maximum airspeed Vmax =20.4 m/s, minimum airspeed Vmin =12.3 m/s, V0=13.2 m/s, h0=40 m, χ0=270 degrees, γ0=5 degrees, ∆h0=15 m, Vap =13.2 m/s, hf=30 m, χf=270 degrees, γf=−2 degrees, ∆hf=15 m, acceleration=min(T−D m), electric power for climbs=Pe,max, electric power for descents=Pe,min. 6.1 Case 1 The horizontal profile of this mission is shown in Fig. 5. The total flown distance is 4578 m. In this mission all the speeds are free parameters, whereas the following altitudes are considered as fixed parameters: h2=h3=80 m, h4=60 m. The optimal trajectory obtained by the OTG is shown in Fig. 6. This trajectory is compared with a non-optimized trajectory, where all the free parameters are fixed, with values h1=hn+1 =60 m, and V1=V2=V3=V4=Vn+1 =17 m/s. The total energy consumption of the optimal trajectory is 42.40 kJ, whereas the consumption of the non-optimized trajectory is 45.16 kJ (+6.51%). The altitude profile is shown in Fig. 6a. It can be seen that, for the optimal trajectory, there is no cruise segment between waypoints WP0and WP1. The values V1and h1are such that all the available distance between the waypoints has been used to accelerate and climb. In this mission, the airspeed is 7 Proc. of the 1st Workshop on Research, Development and Education on Unmanned Aerial Systems (RED-UAS 2011) Seville, Spain, Nov 30th - Dec 1st, 2011 ISBN-978-84-615-6269-5 35 −600 −400 −200 0 200 400 600 800 1000 0 200 400 600 800 1000 y [m] x [m] Figure 5: Horizontal profile, case 1. roughly constant, as it can be seen in Fig. 6b. The optimum value is about 14 m/s. The optimization has been performed using MATLAB’s fmincon. The gradient option has been set to central differences and all the tolerances are set to 10−9. The simulation is performed in a 2.8GHz machine running Linux Ubuntu and MATLAB 2009a. In this case, with 7 free parameters, the best solution is found after 1300 trajectory computations and 24 seconds of CPU time. 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 30 40 50 60 70 80 90 r [m] h [m] Optimum trajectory Non−optimized trajectory (a) 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 13 13.5 14 14.5 15 15.5 16 16.5 17 17.5 18 r [m] V [m/s] Optimum trajectory Non−optimized trajectory (b) Figure 6: Vertical profile, case 1: a) altitude; b) airspeed. 6.2 Case 2 The mission in this case is the same that in the previous section, but now, a wind of 2 m/s coming from the East (from the right side of the Fig. 5) is considered. The optimal trajectory obtained by the OTG is shown in Fig. 7. In this case, the total energy consumption of the optimal trajectory is 42.88 kJ, 1% greater than the consumption without wind. 8 Proc. of the 1st Workshop on Research, Development and Education on Unmanned Aerial Systems (RED-UAS 2011) Seville, Spain, Nov 30th - Dec 1st, 2011 ISBN-978-84-615-6269-5 36 Since most of the altitudes are fixed, the altitude profile is analogous to the previous case. Again, there is no cruise segment between waypoints WP0and WP1(all the available distance between the waypoints has been used to accelerate and climb). The main differences are found in the airspeed. Now, the airspeed varies according to the heading of the segment. It goes from 13.5 to 14.5 m/s (lower with tailwinds and higher with headwinds). However, the flight time is very similar with and without wind, 330.6 s and 329.1 s, respectively. 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 30 40 50 60 70 80 90 r [m] h [m] (a) 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 13 13.5 14 14.5 15 15.5 16 16.5 17 17.5 18 r [m] V [m/s] (b) Figure 7: Vertical profile, case 2: a) altitude; b) airspeed. 6.3 Case 3 The horizontal profile of this mission is shown in Fig. 8a, which is a modification of the first mission (Fig. 5). Now, the heading change at WP3is 153 degrees, greater than 120 (the maximum allowed); all the other heading changes are smaller than 120 degrees. The following altitudes are considered as fixed parameters: h2=h3=h4=80 m, and h5=60 m. Since the heading change at WP3is greater than the maximum allowed, it is neccesary to modify the turn at WP3. One way to do this is to insert an auxiliary waypoint between WP3y WP4, called WP3a. The speed and altitude of this waypoint are considered as free parameters. The horizontal profile after the introduction of the auxiliary waypoint WP3ais shown in Fig. 8b. Once this waypoint has been introduced, all the heading changes are smaller than 120 degrees. The location of the new waypoint must meet the constraints described in Section 4.1: the heading changes at WP3, WP3aand WP4, must be less than 120 degrees, and the distances between WP3and WP3aand between WP3aand WP4must be greater than the minimum necessary distances to perform the turns associated to the three waypoints. In this case, the location of the waypoint WP3ahas been chosen in such a way that the turn at WP3is exactly 120 degrees and the distance between WP3and WP3ais 180 m. 9 Proc. of the 1st Workshop on Research, Development and Education on Unmanned Aerial Systems (RED-UAS 2011) Seville, Spain, Nov 30th - Dec 1st, 2011 ISBN-978-84-615-6269-5 37