无人机控制算法

American Institute of Aeronautics and Astronautics 1 Multiple UAV Dynamic Task Allocation using Mixed Integer Linear Programming in a SEAD Mission Marjorie A. Darrah*, William M. Niland†, and Brian M. Stolarik‡ Institute for Scientific Research, Inc., Fairmont, WV, 26555-2720 This paper extends previous work using Mixed Integer Linear Programming (MILP) to efficiently assign vehicles in a Suppression of Enemy Air Defense (SEAD) mission by adding important new assumptions that increase the complexity of the task allocation problem. The new assumptions include survivable vehicles modeled after unmanned combat aerial vehicles, heterogeneous teams, and dynamic target discovery. With the addition of a new vehicle and mission type, constraints formulated in the previous MILP research are modified or replaced. A dynamic constraint builder is constructed in MATLAB and integrated into the MultiUAV research tool. This allows the new tasking and timing constraints to be formulated based upon the number of mission specified vehicles and the number of targets that have either been detected or partially prosecuted. These constraints can easily be altered based upon rules designated throughout the MATLAB software. Integration into MultiUAV allows the testing of this approach in a dynamic environment. Nomenclature i = index for start node j = index for assignment completion node J = cost function k = index for tasks Mv = munitions remaining on vehicle v. n = number of targets ),( , kv jit = time required to complete a task )(k jt = time task k is completed on target j tf = time to complete all tasks on all targets T = maximum endurance of any UAV Ti,j = flight time between nodes Tv = endurance of UAVv v = index for vehicles w = number of UAVs ),( , kv jix = binary task assignment variable )( 1, v wnix ++ = binary task assignment for null tasks )2,( , v iix = binary task assignment for a vehicle to complete a second task on the same target * Principal Scientist, Visualization and Informatics Branch, mdarrah@isr.us, AIAA Member † Member Research Staff, Sensors & Electronics, wniland@isr.us, AIAA Member ‡ Project Manager, Defense Programs, bstolarik@isr.us, AIAA Member Infotech@Aerospace 26 - 29 September 2005, Arlington, Virginia AIAA 2005-7164 Copyright © 2005 by the American Institute of Aeronautics and Astronautics, Inc. The U.S. Government has a royalty-free license to exercise all rights under the copyright claimed herein for Governmental purposes. All other rights are reserved by the copyright owner. American Institute of Aeronautics and Astronautics 2 I. Introduction ECENT interest in using autonomous vehicles to complete “the dull, the dirty, and the dangerous”1 missions have led to numerous investigations into using teams of collaborating UAVs to accomplish complex missions with strongly coupled tasks. Given a team goal, these vehicles autonomously coordinate their activities to most efficiently accomplish the mission. To minimize necessary inter-vehicle communication when coordinating activities, decentralized algorithms that are redundantly implemented on each team member have been proposed. Given identical information about the battlespace, each vehicle can use its local copy of the algorithm to calculate its individual action and the action of every other team member to achieve the mission. This paper extends previous work in using Mixed Integer Linear Programming (MILP) to efficiently assign vehicles to tasks to prosecute ground targets. Schumacher et al2 used MILP to solve the optimal task assignment and timing problem of a team of homogeneous UAVs detecting, classifying, attacking, and verifying the destruction of enemy ground targets. This paper demonstrates the effectiveness of those principles in a Suppression of Enemy Air Defense (SEAD) mission with important differences in the assumptions that increase the complexity of the task allocation problem. First, we model the team members as Unmanned Combat Aerial Vehicles (UCAV) that have the capability to fire weapons and survive attacks as opposed to Wide Area Search Munitions (WASM) that perish in an attack3,4. Thus the number of team members does not decrease with each target attack. Secondly, though each vehicle persists beyond the attack task (assuming the ground target didn’t fire back and shoot down the UCAV), it has a limited number of weapons onboard. Thus, when a vehicle depletes its weapon payload during a mission, it can no longer be assigned the attack task and is limited to target classification or kill verification. This change causes the team to become heterogeneous since mission capabilities are not consistent across the vehicles. Finally, since targets are not known prior to mission commencement but are discovered during the mission, the MILP must be dynamically updated and solved with the discovery of each new target. With the addition of a new vehicle and mission type, many constraints formulated in the previous MILP research were modified or replaced. Since the search munitions could only attack by flying into a threat, many constraints were concerned with limiting vehicles after an attack. Using a UCAV eliminated this, since subsequent attacks were possible. The constraints generated around an attack task are now concerned with the number of weapons left on the vehicle. In order to use the MILP approach in a dynamic environment, a constraint builder is constructed in MATLAB and integrated into the MultiUAV5,6 research tool. This allowed all possible tasking and timing constraints to be formulated based upon the current number of vehicles and each vehicle’s capability and the number of targets which had either been detected or partially prosecuted. These constraints can easily be altered based upon rules designated throughout the MATLAB software. Integration into MultiUAV allows the testing of this approach in a dynamic environment. Through environment changes in the MultiUAV mission, such as pop-up targets, a vehicle depleting its weapon payload, or a vehicle being shot-down, the number of tasking and timing constraints will change accordingly. The task allocation component of MultiUAV houses multiple algorithm approaches. For this effort, the MILP was added as a new resource. This paper will introduce the MILP constraint formulation problem in a SEAD mission versus the previous work done by Schumacher et al. The dynamic constraint builder will be discussed with sample graphics showing the varying nature of the mission campaign as the environment changes. Results will then be presented in various MultiUAV simulation runs showing successful task allocation on a group of UCAVs using a MILP strategy. In conclusion, future objectives with the simulation environment will be highlighted. II. The SEAD Mission Scenario The SEAD scenario assumes that there are a number of air vehicles searching an area for unknown targets. Vehicles travel in a predefined serpentine search pattern with a sensor that is capable of detecting and identifying potential targets. When a potential target is discovered, it is necessary to classify the target as a threat or non-threat. If the target is identified as a threat, then a vehicle must attack the target. After the attack, a vehicle must verify that it has been destroyed. There are three tasks to be executed per target, classify, attack, and verify. However, due to the complexity of the resulting MILP, the classification task always deems the target a threat and the MILP is formulated with only two tasks to solve, attack and verify. This mission described in the paper has been adapted in three ways from the original scenario, in Schumacher et al7, of non-survivable, homogenous teams of vehicles with a priori knowledge of the targets. R American Institute of Aeronautics and Astronautics 3 The following list details the new assumptions: • The UCAVs are survivable and do not perish in an attack task. Number of aerial vehicles in the team does not decrease with each target attack. • The targets are not known a priori and are discovered during the mission, the target tasking assignments must be completed with the discovery of each new target. • The team of aerial vehicles becomes heterogeneous since weapons are depleted and mission capabilities are not consistent across the team. The number of weapons onboard each aerial vehicle is limited. III. MILP Constraints Adapted for the SEAD Mission In the previous paper, Schumacher et al7, an objective function was identified along with timing constraints and six categories of non-timing constraints. This section will go through each category of the timing and non-timing constraints and discuss how each set of constraints is changed. “Original constraints” in each section below refers to the constraints set up by Schumacher et al2. There also is a new set of constraints added to accommodate for the ability of a vehicle to revisit a target since the vehicles are now survivable. To accommodate the new assumptions two new variables are introduced. A. New variables 1. Since the vehicles are now survivable a new variable, or edge, must be added from a target to itself. This is a loop edge and will be represented by x vii )2,(, . The loop edge can only be used after an attack has been preformed on a target to allow the vehicle to go back to the target to verify. 2. Since the vehicles have a limited amount of weapons onboard, a new variable is added to represent the number of weapons remaining on the vehicle. This will be represented as Mv, the number of munitions remaining on vehicle v. B. Objective Function The objective function has not changed. Minimize the final time. ∑∑ = = += n j k j k j k f tctJ 1 )()( 2 1 (1) Where 0)( ≥kjc is a small weight on the completion time of each individual task. C. Modified Non-timing Constraints 1. Original constraints: Each task is performed on each target exactly once. New constraints: Each task is performed on each target exactly once, with new loop edges allowing task 2 to be done by same vehicle. The loop edges are added to the list of edges that could perform a task 2. If k = 1,2 and j = 1,…n, then equation 2 below yields the constraints to do a task 1 and equation 3 yields the constraints to do a task 2 and included the loops. These equations yield 2n constraints. 1 1 )1,( , 1 1 )1,( , =+∑∑ ∑ = + = ≠= w v v jnv w v n jii v ji xx (2) American Institute of Aeronautics and Astronautics 4 1 1 )2,( , 1 1 )2,( , =+∑∑∑ = + = = w v v jnv w v n i v ji xx (3) 2. Original constraints: Only two tasks can be performed on each target, and the first task (classify and attack) results in the loss of the attacking agent. Vehicles only enter the sink once. New constraints: Only two tasks can be performed on each target. The vehicles are survivable, allowing them to do more than one task on each target. There was no change to the inequality in 4 when the vehicle only enters the sink once. The change required for this set of constraints was that the loop edge was added to the left hand side of the constraints generated by inequality 5. The right hand side of the inequality was also changed from 1 to 2. In the following inequalities let v= 1,…,w and j=1,…,n. These inequalities yield nw + w = (n+1)w constraints. 1)( 1, 1 )( 1, ≤+ +++ = ++∑ v wnvnn i v wni xx (4) 2 2 1 )2,( , )2,( , 2 1 ,1 ),( , ≤++ ∑∑ ∑ = + = ≠= k v jvn v jj k n jii kv ji xxx (5) 3. Original constraints: A vehicle is perishable. A vehicle can be assigned to attack at most one target. New constraints: A vehicle is survivable and can be assigned to attack targets as long as it has weapons remaining. This required the introduction of a new variable Mv, the number of weapons on vehicle v, which was used on the right hand side of the inequality in 6 below. For the inequality below v= 1,…,w. This yields w constraints. ∑∑ ∑ = + = ≠= ≤+ n j v v jnv n i n ijj v ji Mxx 1 )1,( , 1 ,1 )1,( , (6) 4. Original constraints: A vehicle cannot leave a target node if it performed task one. New constraints: This set of constraints was dropped because the vehicles are now survivable. 5. Original constraints: A vehicle cannot leave a node it has not entered. New constraints: This constraint remained the same. The addition of the loop edges could not be handled in this constraint because they allowed both entry and exit from the node. This yields nw constraints ∑∑ ∑ = ≠= + ≠= ++ =+ 2 1 1 1 )2,( , )( 1, ),( , k n ji i wn ji i v ji v wnj kv ij xxx (7) 6. Original constraints: All vehicles leave the source node. New constraints: This constraint did not change. For the equation 8 below v =1…w. This yields w constraints. ∑∑ = +++ = + =+ 2 1 )( 1, 1 ),( , 1 k v wnvn n j kv jvn xx (8) 7. New constraints: The vehicle may only choose a loop edge if it has already entered the node. This required nw new constraints to be formed that would ensure that the number of entering edges for a vehicle was greater than or equal to the loop edge chosen for that vehicle. For the equation in 9 below j=1,…,n and v=1,…w. American Institute of Aeronautics and Astronautics 5 ∑ ≠= = n jii v ji v jj xx ,1 )1,( , )2,( , (9) The overall number of not-timing constraints remained the same because constraint set 4 with nw constraints was dropped and constraint set 7 was added with nw constraints. The total non-timing constraints is 3nw + 3w + 2n. D. Modified Timing Constraints The timing constraints are also modified to include the assumption that the vehicles are survivable. The new loop edges and other edges associated with the vehicle surviving after performing a task 1 on a target were added to the appropriate existing constraints. Because the vehicles are now survivable, new timing constraints were added for each vehicle related to doing task 1 or 2 on a given target. The vehicles can leave a target after doing task 1 and either return to the same target node or enter another target node to do either a task 1 or a task 2. Two new timing constraints are added for each vehicle related to doing task 1 on a given target and four new timing constraints were added for each vehicle related to doing task 2 on a given target. For example, in the case with 3 vehicles and 2 targets this added an additional 36 constraints (2nw + 4nw) to the original MILP timing constraint set2. The timing constraints fall into four categories: 1. Vehicles leaving from origin nodes to execute a task. For inequalities 10 and 11 below j=1,…,n, k = 1,2 and v=1,…w. This yields 4nw constraints. wTxttt kv jvn kv jvnv k j )1( ),( , ),( , )( ++ −++≤ (10) wTxttt kv jvn kv jvnv k j )1( ),( , ),( , )( ++ −−+≥ (11) 2. Vehicles leaving from target nodes to execute task 1. For inequalities 12 and 13 below i=1,…,n, j=1,…,n, k = 1,2 and v=1,…w. In each equation loop edges are possible in the summation portion of the equation. This yields 4n(n-1)w constraints. ∑+ =≠ −−++≤ wn l kv il kv ji kv ji ji k ij wTxxttt 1 ),( , ),( , ),( , )()1( )2( (12) ∑+ =≠ −−−+≥ wn l kv il kv ji kv ji ji k ij wTxxttt 1 ),( , ),( , ),( , )()1( )2( (13) 3. Vehicles leaving from a target node to execute task 2 utilizing a loop edge. For inequalities 14 and 15 below i=1,…,n, j=1,…,n, k = 1,2 and v=1,…w. This yields 2nw constraints. ∑+ ≠= −−++≤ wn jll kv jl v jj v jjjj wTxxttt ,1 ),( , )2,( , )2,( , )1()2( )2( (14) ∑+ ≠= −−−+≥ wn jll kv jl v jj v jjjj wTxxttt ,1 ),( , )2,( , )2,( , )1()2( )2( (15) 4. Vehicles leaving from a target node to execute task 2 on a non-loop edge. For inequalities 16 and 17 below i=1,…,n, j=1,…,n, k = 1,2 and v=1,…w. In each equation loop edges are possible in the summation portion of the equation. This yields 4n(n-1)w constraints. American Institute of Aeronautics and Astronautics 6 ∑+ =≠ −−++≤ wn l kv jl kv ji kv ji ji k ij wTxxttt 1 ),( , ),( , ),( , )()2( )2( (16) ∑+ =≠ −−−+≥ wn l kv il kv ji kv ji ji k ij wTxxttt 1 ),( , ),( , ),( , )()2( )2( (17) 5. The last set of constraints assures task precedence where α can be chosen to represent any desired minimum delay between tasks k=1 and k=2. This yields 2n constraints. )2()1( jj tt ≥+α nj ...1=∀ (18) fj tt ≥)2( nj ...1=∀ (19) The total number of timing constraints is 6nw + 8n(n-1)w + 2n. IV. MILP Integration with MultiUAV In order to test the MILP approach in the MultiUAV simulation environment, a series of MATLAB functions were written to dynamically generate the appropriate inputs needed for the MILP solver. This section will briefly describe the MultiUAV research tool and then discuss the effort required to integrate the MILP task allocation approach into MultiUAV. A. MultiUAV The U.S. Air Force Research Laboratory (AFRL) developed the MultiUAV simulation environment as a stand-alone tool to implement and evaluate cooperative control strategies for UAVs. MultiUAV is organized in the MATLAB/Simulink environment, easing the effort for outside researchers to study and contribute to the tool. Figure 1 provides a functional view of the latest public release version of MultiUAV§. The internal functionality of MultiUAV resides in a combination of MATLAB and C++ functions. Nominally there are eight vehicles and ten targets in the public release version of MultiUAV. The number of homogeneous vehicles and targets can be easily increased in the simulation by copying new instances from a library and placing them into the respective subsystems. Each vehicle contained within the Simulink block has an identical set of embedded flight software (EFS) components and vehicle dynamics. The EFS contains six managers with the following responsibilities: 1) Route Manager - calculates tasking trajectories to the targets, calculates costs to perform the tasks, and tracks the mission status of the vehicle. 2) Cooperation Manager - calculates assignments for the vehicle based on the type of assignment algorithm, sensed information, and information received from the other vehicles. 3) Tactical Maneuvering Manager - takes waypoints generated for the assignment and produces autopilot commands, causing the vehicle to follow the waypoints. 4) Sensor Manager - executes the Automatic Target Recognition (ATR) system which combines single-look ATR values into multiple-look ATR values, also performs target kill verification. § MultiUAV Public Release Access Site, http://www.isr.us/research_sim_muav.asp Figure 1. Top Level MultiUAV in Simulink. American Institute of Aeronautics and Astronautics 7 5) Target Manager - monitors the state of any known targets. 6) Weapons Manager - fires weapons and tracks the number of weapons on the vehicle. The goal of the EFS is to optimally8, if possible and feasible, allocate the mission’s tasks among the vehicles. At the beginning of the mission the vehicles start a predetermined search pattern. Once a vehicle detects a target a notification is sent to all other vehicles, triggering a replan. Once triggered, the EFS on each vehicle will calculate the next set of tasks for all known vehicles. The EFS duplication allows each vehicle to compute the same set of tasks for all vehicles with minimal inter-vehicular communication. B. MILP Dynamic Constraint Builder To solve the task allocat