Mixed-integer linear programming collision avoidance method in unmanned aerial vehicles trajectory planning

 

ABSTRACT

The explanatory note to the term paper “Mixed-integer linear programming collision avoidance method in unmanned aerial vehicles trajectory planning”:

The object of investigation – unmanned aerial vehicles.

The objective of the work – modeling of the collision avoidance scenario on the base of mixed-integer linear programming method.

Unmanned aerial vehicles (UAV) are widely used today. The investigation of optimal methods of collision avoidance will allow decreasing the probability of conflicts between UAVs and maintain the required safety level. The mixed-integer linear programming method is quite simple and useful for this purpose. It can be easily implemented not only in UAVs, but also in new systems of collision avoidance.

MIXED-INTEGER LINEAR PROGRAMMING, MILP, UNMANNED AERIAL VEHICLE, COLLISION AVOIDANCE, CONFLICT RESOLUTION, FLIGHTS SAFETY.

 

 

 

 

 

 

 

CONTENTS

LIST OF ACRONYMS…………………………………………………………..….5

INTRODUCTION………………………………………………………..………….6

1. PROBLEM FORMULATION………………………………………………….8

1. Trajectory Design………………………………………………..8 
2. Task Allocation…………………………………………………10

2. RECEDING HORIZON CONTROL USING MIXED-INTEGER LINEAR PROGRAMMING……………………………………………………………..11

1. Overview of the Receding Horizon Controller………………....11
2. Model of Aircraft Dynamics……………………………..……..12

1. Discrete Time System…………………………..…12
2. Speed Constraints…………….…………………..13 
3. Minimum Turning Radius………………….…….16 

3. Collision Avoidance Constraints………………………………..16

1. Obstacle Avoidance………….……………………17
2. Vehicle Avoidance……………………..…………18 

4. Plan beyond the Planning Horizon……………………………..19 
5. Target Visit..……………………………………………………21 
6. Cost Function……………………………………………………23

3. SOFTWARE……………………………………………………………………26
4. MODELING AND ITS RESULTS.……..……………………………………27

1. Annotation……………………………………………………...27
2. Text of the program…………………………………………….29
3. Obtained graphical representations of work done………………35

CONCLUSIONS………………………………………………………………..…..40

REFERENCES…………………………………………………………………..…41

 

LIST OF ACRONYMS

AMPL – A Mathematical Programming Language

CPLEX – Simplex method optimizer

MAC – Midair collision

MILP – Mixed-integer linear programming

MMKP  – Multiple-choice multi-dimension knapsack problem

MPC  – Model predictive control

NTG – Nonlinear trajectory generator

RHC – Receding horizon control

TOA – The time-step of arrival

UAV – Unmanned aerial vehicles

 

 

 

INTRODUCTION

Aviation safety is the number one priority for everyone working in the aviation industry. Over the past decade, the aviation community has witnessed a fundamental shift in its approach to safety. The evolution of the strategies is critical to ensure that international civil aviation remains the safest mode of transportation even as it continues to accommodate the significant growth in global populations and air travel forecast for the near future. Despite improvements in the general aviation safety record in recent years, the number of midair collisions (MACs) shows no corresponding decline. MACs continue to occur about 12 times a year on average, often resulting in multiple fatalities. That is why the lot of mathematical methods of collision avoidance was developed during the last decades and continues to improve day by day.

The object of this work is unmanned aerial vehicles (UAV) that is widely used all around the world. The role of UAV has changed over the past five to ten years as the level of autonomy onboard the vehicle increases. The primary advantage of UAVs is that they can perform missions in dangerous environments, such as battle fields and devastated areas, without risking the life of the human pilots. The variety of application areas include war zones, surveillance, forest fire monitoring, disaster relief, and weather forecast. Because of the absence of the main detector of probable conflict on UAV, it means human eyes, the strong and reliable method of conflict resolution must be used.

The objective of this work is to use mathematical programming techniques to find the optimal path between two states for a single vehicle. This path will be optimized with respect to both fuel and/or time, and must ensure that the vehicle does not collide with fixed obstacles. For this purpose the mixed-integer linear programming is used. It is well-suited for trajectory planning because it can directly incorporate logical constraints such as obstacle avoidance and waypoint selection and because it provides an optimization framework that can account for basic dynamic constraints such as turn limitations and maximum rate of climb.  Background The capabilities and roles of unmanned aerial vehicles (UAVs) are evolving, and new concepts are required for their control. For example, today’s UAVs typically require several operators per aircraft, but future UAVs will be designed to make tactical decisions autonomously and will be integrated into coordinated teams to achieve high-level goals, thereby allowing one operator to control a group of vehicles. Thus, new methods in planning and execution are required to coordinate the operation of a fleet of UAVs.

An overall control system architecture must also be developed that can perform optimal coordination of the vehicles, evaluate the overall system performance in real time, and quickly reconfigure to account for changes in the environment or the fleet. This thesis presents results on the guidance and control of fleets of cooperating UAVs, including goal assignment, trajectory optimization, and hardware experiments. For many vehicles, obstacles, and targets, fleet coordination is a very complicated optimization problem where computation time increases very rapidly with the problem size.  

 

 

 

 

 

 

 

1. PROBLEM FORMULATION
1. Trajectory Design 

Optimizing a kinematically and dynamically constrained path is a significant problem in controlling autonomous vehicles, and has received attention in the fields of robotics, undersea vehicles, and aerial vehicles. Planning trajectories that are both optimal and dynamically feasible is complicated by the fact that the space of possible control actions in extremely large and non-convex, and that simplifications reducing the dimensionality of the problem without losing feasibility and optimality are very difficult to achieve. Previous work demonstrated the use of mixed-integer linear programming (MILP) in off-line trajectory design for vehicles under various dynamic and kinematic constraints.

MILP allows the inclusion of non-convex constraints and discrete decisions in the trajectory optimization. Binary decision variables allow the choice of whether to pass “left” or “right” of an obstacle, for example, or the discrete assignment of vehicles to targets to be included in the planning problem. Optimal solutions can be obtained for these trajectory generation problems using commercially available software such as CPLEX. Using MILP, however, to design a whole trajectory with a planning horizon fixed at the goal in very difficult to perform in real time because the computational effort required grows rapidly with the length of the route and the number of obstacles to be avoided. This limitation can be avoided by using a receding planning horizon in which MILP in used to form a shorter plan that extends towards the goal, but does not necessarily reach it. This overall approach is known as either model predictive control (MPC) or receding horizon control (RHC) [1].

The performance of a RHC strongly depends on the proper evaluation of the terminal penalty on the shorter plan. This evaluation is difficult when the feasibility of the path beyond the plan must be ensured. Previous work presented a heuristic to approximate the trajectory beyond the shorter plan that used straight line paths 18 to estimate the cost-to-go from the plan’s end point to the goal. This RHC makes full use of the future states predicted through a model in order to obtain the current control inputs. In a trajectory design problem, the future states can be predicted by the straight line paths. This is because the shortest path from any location to the goal is a connection of straight lines, if no vehicle dynamics are involved and no disturbances act on the vehicle. As such, generating a coarse cost map based on straight line approximations (and then using Dijkstra’s algorithm) provides a good prediction of the future route beyond the planning horizon. The receding horizon controller designs a detailed trajectory over the planning horizon by evaluating the terminal state with this cost map. While this planner provides good results in practice, the trajectory design problem can become infeasible when the positioning of nearby obstacles leaves no dynamically feasible trajectory from the state that is to be reached by the vehicle. This is because the Dijkstra’s algorithm neglects the vehicle dynamics when constructing the cost map. In such a case, the vehicle cannot follow the heading discontinuities where the line segments intersect since the path associated with the cost-to-go estimate is not dynamically feasible. 

This work presents one way to overcome the issues with the previous RHC approach by evaluating the cost-to-go estimate along straight line paths that are known to be “near” kinodynamically feasible paths to the goal. This new trajectory designer is shown to: (a) be capable of designing trajectories in highly constrained environments; and (b) travel more aggressively since the turn around an obstacle corner is designed at the MILP optimization phase, unlike a trajectory designer that allows only predetermined turns at each corner.

Although RHC has been successfully applied to chemical process control, applications to systems with faster dynamics, such as those found in the field of aerospace, have been impractical until recently. The on-going improvements in computation speed has stimulated recent hardware work in this field, including the on-line use of nonlinear trajectory generator (NTG) optimization for control of an aerodynamic system. The use of MILP together with RHC enables the application of the real-time trajectory optimization to scenarios with multiple ground and aerial vehicles that operate in dynamic environments with obstacles.  

2. Task Allocation

 

 A further key aspect of the UAV problem is the allocation of different tasks to UAVs with different capabilities. This is essentially a multiple-choice multi-dimension knapsack problem (MMKP), where the number of possible allocations grows rapidly as the problem size increases. The situation is further complicated if the tasks: - are strongly coupled – e.g., a waypoint must be visited three times; -have tight relative timing constraints – e.g., three UAVs must be assigned to strike a target from three different directions within 2 seconds of each other [2]. 

With limited resources within the team, the coupling and timing constraints can result in very tight linkages between the activities of the various vehicles. Especially towards the end of missions, these tend to cause significant problems (e.g., “churning” and/or infeasible solutions) for the approximate assignment algorithms based on “myopic algorithms” (e.g. iterative “greedy” or network flow solutions) that have recently been developed. MILP, again, provides a natural language for codifying these various mission objectives and constraints using a combination of binary (e.g., as switches for the discrete/logical decisions) and continuous (e.g., for start and arrival time) variables. MILP allows us to account for the coupling and relative timing constraints and to handle large fleets with many targets and/or pop-up threats. 

 

 

2. RECEDING HORIZON CONTROL USING MIXED-INTEGER LINEAR PROGRAMMING

2.1 Overview of the Receding Horizon Controller 

Improvements in UAV capabilities make it possible for UAVs to perform longer and more complicated missions and scenarios. In these missions and scenarios, optimal path navigation through complicated environments is crucial to mission success. As more vehicles and more targets are involved in the mission, the complexity of the trajectory design problem grows rapidly, increasing the computation time to obtain the optimal solution. One alternative to overcome this computational burden is to use receding horizon control (RHC).

The RHC uses a plant model and an optimization technique to design an input trajectory that optimizes the plant’s output over a period of time called the planning horizon. Ap ortion of the input trajectory is then implemented over the shorter execution horizon, and the optimization is performed again starting from the state that is to be reached. If the control problem is not completed at the end of the planning horizon, the cost incurred past the planning horizon must be accounted for in the cost function. The selection of the terminal penalty in RHC design is a crucial factor in obtaining reasonable performance, especially in the presence of obstacles and no-fly zones [1].  

In general, the cost function of a receding horizon controller’s optimization problem estimates the cost-to-go from a selected terminal state to the goal. For vehicle trajectory planning problems in a field with no-fly zones, presented a receding horizon controller that uses the length of a path to the goal made up of straight line segments as its cost-to-go. This is a good approximation for minimum time of arrival problems since the true minimum distance path to the goal will typically touch the corners of obstacles that block the vehicle’s path. In order to connect the detailed trajectory designed over the planning horizon and the coarse cost map beyond it, the RHC selects an obstacle corner that is visible from the terminal point and is associated with the best path. This approach has another advantage in terms of real-time applications.

The cost map not only gives a good prediction of vehicle behavior beyond the planning horizon, but because it is very coarse, in also can be rapidly updated when the environment and/or situational awareness changes. The following sections focus on solving the vehicle trajectory design problem after a set of ordered goals are assigned to each vehicle. The MILP formulation presented here extends an existing algorithm to incorporate more sophisticated scenarios (e.g., multiple vehicles, multiple goals) and detailed dynamics (e.g., constant speed operation). 

2.2 Model of Aircraft Dynamics 

It has been shown that the point mass dynamics subject to two-norm constraints form in approximate model for limited turn-rate vehicles, provided that the optimization favors the minimum time, or minimum distance, path. By explicitly including minimum speed constraints, this formulation can be applied to problems with various objectives, such as expected score and risk, with a minimal increase in computation time. 

2.2.1. Discrete Time System 

Aircraft dynamics is expressed as a simple point mass with position and velocity     [x, y, v_x, v_y]^T as state variables and acceleration [a_x, a_y]^T as control inputs [1],[2].

(2.1)

The zero-order hold equivalent discrete time system in

(2.2)

     where k expresses a time step and Δt is the time interval. Note that the control input [a_x, a_y]_k ^T stays constant over each time interval Δt under the zero-order hold assumption. 

2.2.2 Speed Constraints 

The constraint on the maximum speed v_max is written as a combination of linear constraints on the velocity vector v using uniformly distributed unit vectors

	(2.3)
	(2.4)

where n_vmax is the number of unit vectors i_k onto which the velocity vector in projected. The speed constraint is effectively a constraint on the length of the projection of the velocity vector onto a unit vector. Eqs. 2.3 and 2.4 require that the velocity vector be inside a regular polygon with n_vmax sides circumscribed about a circle of radius v_max. Aconstrain t on the minimum speed v_min can be expressed in the similar way: the dot product of the velocity vector and a unit vector must be larger than v_min. However, it in different from the maximum speed constraint in that at least one of the constraints must be active, instead of all of them,  

	(2.5)
	(2.6)

        Here, n_vmin is the number of unit vectors onto which the velocity vector is projected. Eq. 2.5 is a non-convex constraint and is written as a combination of mixed-integer linear constraints

(2.7)

 

(2.8)

        where M_v is a number larger than 2v_min, and the b_speed,k are binary variables that express the non-convex constraints in the MILP form.

Note that if b_speed,k = 1, the inequality in Eq. 2.7 is active, indicating that the minimum speed constraint is satisfied. On the other hand, if b_speed,k = 0, the k^th constraint in Eq. 2.7 is not active, and the constraint on minimum speed is relaxed. Eq. 2.8 requires that at least one constraint in Eq. 2.7 be active. Eqs. 2.6 to 2.8 ensure that the tip of the velocity vector lies outside of a regular polygon with n_vmin sides circumscribed on the outside of a circle with radius v_min.  Since the minimum speed constraints require binary variables, which typically slows down the MILP optimization process, n_vmin is typically much smaller than n_vmax . Note that the speed constraints can become infeasible if v_max and v_min are set equal unless n_vmax = n_vmin.   

2.2.3 Minimum Turning Radius 

UAVs usually fly at roughly a constant speed v and have a minimum turning radius r_min. The constraint on the turning radius r is 

(2.9)

         and this constraint can be written as a constraint on lateral acceleration,

(2.10)

        where a is the magnitude of the acceleration vector and a_max is the maximum acceleration magnitude. Similar to the maximum speed constraint, the constraint on the maximum acceleration is written as a combination of linear constraints on the acceleration vector a 

(2.11)

 

(2.12)

       where n_a is the number of unit vectors onto which the acceleration vector is projected. The constraints on velocity in Eqs. 2.3 to 2.8 keep the speed roughly constant, so the allowable acceleration vector direction is perpendicular to the velocity vector [3]. The state equation (Eq. 2.2) for the vehicle uses a zero-order hold on the inputs, so the acceleration vector stays the same over the time-step Δt. Figure 2-3 shows a turn with the maximum lateral acceleration. The actual minimum turning radius r_{min actual} is a radius of the polygon. It is geometrically calculated, using the relation between a_max and r_min in Eq. 2.10, as

(2.13)

       and is slightly smaller than r_min.  

 

2.3. Collision Avoidance Constraints 

2.3.1. Obstacle Avoidance 

During the overall mission, UAVs must stay outside of no-fly-zones, which are modelled as obstacles in our formulation. Obstacle avoidance is a non-convex constraint and requires binary variables and a large number M in MILP. At each time step k, the vehicle must stay outside of a rectangular obstacle defined by four parameters [x_l, y_l, x_u, y_u].