文档库 最新最全的文档下载
当前位置:文档库 › Coordination and Control of Multiple UAVs with Timing Constraints and Loitering

Coordination and Control of Multiple UAVs with Timing Constraints and Loitering

Coordination and Control of Multiple UA Vs with Timing Constraints and Loitering

Mehdi Alighanbari,Yoshiaki Kuwata,and Jonathan P.How

Space Systems Laboratory,

Massachusetts Institute of Technology

{mehdi a,kuwata,jhow}@https://www.wendangku.net/doc/358759116.html,

Abstract

This paper describes methods for optimizing the task allocation problem for a?eet of Unmanned Aerial Vehi-cles(UAVs)with tightly coupled tasks and rigid relative timing constraints.The overall objective is to minimize the mission completion time for the?eet,and the task assignment must account for di?ering UAV capabilities and no-?y zones.Loitering times are included as extra degrees of freedom in the problem to help meet the tim-ing constraints.The overall problem is formulated us-ing Mixed-integer Linear Programming(MILP),which gives the globally optimal solution.An approximate decomposition solution method is also used to over-come the computational issues that arise when using MILP for larger problems.The problem is also posed in a way that can be solved using Tabu search.This approach is demonstrated to provide good solutions in reasonable computation times for large problems that are very di?cult to solve using the exact or approxi-mate decomposition methods.

1Introduction

The capabilities and roles of UAVs are evolving,and new methods in planning and execution are required to coordinate the operation of a?eet of UAVs[1].This paper presents results on guidance and control of?eets of cooperating UAVs.This includes the goal assign-ment,resource allocation,and trajectory optimization problems.For many vehicles,obstacles,and targets,?eet coordination is a very complicated optimization problem[1,2],and the computation time increases very rapidly with the problem size.As discussed in this pa-per,the situation is further complicated if the tasks:?Are strongly coupled–e.g.,a waypoint must be visited three times,?rst by a type1UAV,fol-

lowed by a type2and then a type3.

?Have tight relative timing constraints–e.g.,must assign three UAVs to strike a target from three

di?erent directions within2seconds of each other. These tend to cause signi?cant problems(e.g.,“churn-ing”and/or infeasible solutions)for the approximate assignment algorithms based on“myopic algorithms”that have recently been developed[3]–especially to-wards the end of missions.

MILP provides a natural language for codifying these various mission objectives and constraints using a com-bination of binary and continuous variables[2,4,5]. Optimal solutions can be obtained to these problems using commercially available software such as CPLEX, but approximate techniques are required for real-time applications.This paper extends an approximate de-composition algorithm[2,5]to include these relative timing constraints and adds extra degrees of freedom to the formulation that allow the UAVs to loiter dur-ing the mission.Impacts on the computational time by adding these timing constraints to the problem are demonstrated in a complex example with6UAVs and 12waypoints.Tabu search techniques[6]are also inves-tigated to solve the tightly coupled assignment prob-lems for scenarios with a large number of UAVs and waypoints(and a large number of permutations and combinations)for which the decomposition method also becomes computationally intractable.

2Problem Formulation

This section describes how the multiple vehicle routing problems with relative timing constraints and loitering can be written as a MILP.The algorithms assume that the team partitioning has already been performed,and that a set of tasks has been identi?ed that must be performed by the team.The overall objective is to as-sign one set of ordered waypoints to each vehicle that is combined into the mission plan,and adjust the loiter times for the team such that the cost of the mission is minimized and the time of task execution at each waypoint satis?es the timing constraints.

2.1Algorithm Overview

There are three main phases in our algorithm[2,5]:(I) cost calculation,(II)planning and pruning,and(III) task assignment.

I-1.Find the visibility graph between the UAV start-ing positions,waypoints,and obstacle vertices. https://www.wendangku.net/doc/358759116.html,ing the Dijkstra’s algorithm,calculate the shortest length of the all feasible paths between

waypoints,and form the cost table.

II-1.Obtain feasible combinations of waypoints,ac-counting for the capability and the maximum

number of waypoints per UAV.

II-2.Enumerate all feasible permutations from these combinations,subject to the timing constraints.

the task.T O E C

k2≥T O E C

k1

+d k,k=1,...,N C(8)

waypoints.(a)No timing constraints.Solved in2sec.

(b)11timing constraints.Solved in13sec.

where each row of matrix C and vector d represents a

dependency between two waypoints.If the k th row of C is[i j],Eq.(8)becomes T O E j≥T O E i+d k.Note that d k can also be negative.This formulation allows

us to encode very general relative timing constraints.

Although each waypoint i has only one time of execu-

tion T O E i associated with it,this formulation can be

used to describe several visits with timing constraints

by putting multiple waypoints at that location.

2.4Cost Function

The cost J to be minimized in the optimization is

J=max

k∈{1,...,N V}t F

k

+

α

N V

N M

i=1

c i x i+

β

N W

N V

j=1

N W

i=1

L ij(9)

where the?rst term gives the maximum completion time of the team,the second gives the average comple-tion time,and the third gives the total loiter times.If the penaltyα≥0on average?ight time were omitted, the solution could assign unnecessarily long trajectories to all UAVs except for the last to complete its mission. Similarly,β≥0can be used to include an extra penalty that avoids excessive loitering.

3Simulation Results

This section presents results from several simulations using the formulation in Section2.The problems were solved using CPLEX(v7.0)running on a2.2GHz PC with512MB RAM.The?rst result investigates how the timing constraints impact the solution times.The sec-ond considers the relationship between the complexity of timing constraints and the computation time.

3.1Problems with and without timing con-straints

A large scenario that includes a?eet of6UAVs of3 di?erent types and12waypoints is used as our base-line.The UAV capabilities are shown in Fig.2(a)(top left).There are also several obstacles in the environ-ment.The objective is to allocate waypoints to the team of UAVs in order to visit every waypoint once and only once in the minimum amount of time.For conve-nience,this problem without timing constraints will be referred to as the“original”problem.Fig.2(a)shows the solution of this original problem.All waypoints are visited subject to the vehicle capabilities in23.90time units.Time of task execution of each waypoint is also shown beside the waypoint in the?gure.

The problem with simultaneous arrival and ordered task was also considered.Timing constraints in this scenario are as follows:

1.Wpts1,7,2must be visited at same time.

2.Wpts4,8,12must be visited at same time.

3.Wpts9,11must be visited at same time.

4.Wpts4,8,12must be visited before Wpts9,11. The solution in this case is shown in Fig.2(b),which is quite di?erent from Fig.2(a).In Fig.2(a),UAV3vis-its waypoints4,8,and12,whereas in Fig.2(b),three UAVs are assigned to these three waypoints since they must all be visited at the same time.More UAVs are assigned to the waypoints in the lower half of the?g-ure in Fig.2(a)than in Fig.2(b)since the priority of waypoints4,8,12are higher than that of waypoints 9,11as a result of the timing constraints.Also,way-point4is visited by UAV6,which is the farthest from it.The mission time for this scenario increased to28.04 time units,and the computation time increased from2 seconds to13seconds.To solve this problem in a rea-sonable time,the following approximations were made:?Select only1best feasible permutation per com-bination.

?If there is a timing constraint T O E i≥T O E j+ t D(t D≥0),then the UAVs can loiter only at

waypoint i.

In order to satisfy the many timing constraints,4UAVs loiter at6waypoints.UAV1loiters on its way to way-point7and8,and UAV3loiters on its way to way-points1and12.If time adjustment is allowed only on the initial position as in Ref.[2],a feasible solution can-not be found in this scenario.Since the loiter matrix L allows UAVs to loiter at any of the waypoints with tim-ing constraints,problems with strongly coupled timing constraints are always solvable.

3.2Complexity of Adding Timing Constraints To investigate the impact of the timing constraints on the performance and computation time,we measured the computation time for the problem in Section3.1, with these four timing constraints:

Case–1:T O E i≥T O E j

Case–2:T O E i≥T O E j+10

Case–3:T O E i≥T O E j≥T O E k

Case–4:T O E i≥T O E j+5≥T O E k+10

In each case,all feasible combinations of waypoints(i, j)or(i,j,k)were tested as the points associated with the timing constraints.The results are summarized in the histograms of Figures3–6.

Figs.3(a),4(a),5(a),and6(a)show the results when all loitering times are included in the problem.Since there are12waypoints and6UAVs with di?erent ca-pabilities,there are52extra degrees of freedom in the

Fig.3:Fig.4:Fig.5:Fig.6:

Histograms of case 1–4from left to right –(a)shows the computation time [sec]for the problem with no constraints on the loitering times;(b)shows the com-putation time [sec]for the problem with constrained loitering;and (c)shows the degree of “unnaturalness”.

decision variable L .Figs.3(b),4(b),5(b),and 6(b)show the results when the constrained form of the loi-tering is used.This reduces the degrees of freedom in the loiter matrix L from 52to 8–12,depending on the type of constraints.

C omparing Figs.3(a),(b)with Figs.4(a),(b),and,Figs.5(a),(b)with Figs.6(a),(b),it is clear that the computation time increases as more complicated timing constraints are imposed on the tasks (either by increas-ing the time gaps or by increasing the number of related tasks).With fewer degrees of freedom,the constrained loitering approach solves faster by a factor of two.To approximately determine the complexity of these constraints,we introduce the concept of the “unnat-uralness”of the timing constraints,which is a mea-sure of the degree to which the timing constraints are violated by the solution of the original https://www.wendangku.net/doc/358759116.html,-ing the solution of the original problem to obtain the times associated with waypoints i and j (T O E i and T O E j ),de?ne the unnaturalness of a timing constraint T O E i ≥T O E j +t

D as

max T O E j +t D ?T O E i ,0 (10)If the solution of the original problem happens to satisfy

the timing constraint,the unnaturalness is 0.The sum of the unnaturalness of each timing constraint is used as a measure of the unnaturalness for the constrained problem.Note that other metrics such as the number of timing constraints,and the extent to which they are tightly coupled together can be misleading if the results are “naturally”satis?ed by the solution to the uncon-strained problem.The metric in Eq.(10)gives a direct (albeit approximate)measure of the extent to which the solution must be changed to satisfy the additional

timing constraints.

Figs.3(c),4(c),5(c),and 6(c)show four histograms that give the unnaturalness of the basic problem with timing constraints (cases 1–4).The shapes of the 4histograms re?ect the computation time required to solve these problem.In particular,as the distribution of the unnaturalness shifts towards the right (Fig.3(c)→4(c)and 5(c)→6(c)),the distribution of the computa-tion time also shifts to the right (Fig.3(b)→4(b)and 5(b)→6(b)).Further observations include:

?If all of the timing constraints are natural,then the computation time does not increase signi?-cantly,even if there are many timing constraints.?If all the timing constraints are natural,the best permutation is always feasible without pruning by timing constraints,but that is not the case if there are unnatural timing constraints.

?Additional permutations can be kept to account for unnatural timing constraints,but simulation results have shown that this can cause a combi-natorial explosion and rapidly increase the com-putation time with a marginal improvement in performance.The results show that this algorithm can solve the problem of UAV assignment with relative timing con-straints.It was shown that increasing the number of timing constraints and the degree of “unnaturalness”makes the problem harder to solve,but the proposed algorithm can still be used to obtain the globally opti-mal solution.

4Tabu Search for the UA V Problem

The UAV assignment problem discussed in the previ-ous sections is a generalization of the vehicle routing problem,which is NP-hard.Thus ?nding the opti-mal solution to this problem using exact methods is computationally infeasible for large ?eets,and even the decomposition methods discussed in Section 2becomes intractable when the number of permutations and com-binations increase.However,several researchers have demonstrated that the Tabu search method can be used to rapidly obtain sub-optimal solutions of the VRP problem [10].This section formulates the UAV prob-lem of Sections 2and 3as a VRP with relative timing constraints and uses modi?ed Tabu algorithms to solve this problem.

4.1Tabu Search Method

Glover ?rst proposed the basic ideas of Tabu search [6]and the algorithm has been studied extensively because it has proven to be an e?ective heuristic for solving combinatorial optimization problems such as schedul-ing,telecommunications,transportation and network problems [6].The Tabu method searches a neighbor-hood of a given solution for a better feasible solution,which is the basis for many solution algorithms.The neighborhood of a solution is de?ned to be all solutions that can be reached in a single move ,where the de?ni-tion of a move is problem speci?c (i.e.,changing one bit

from1to0,or swapping the position of two elements in a vector).The problem with most neighborhood meth-ods of this type is that they can get trapped in a local minimum,and loop endlessly.To prevent this looping between the same solutions,Tabu search uses the con-cept of memory and a Tabu list.The detailed discussion on Tabu search method can be found in[6].

4.2Problem Formulation

Suppose there are N W waypoints and N V UAVs.We represent a solution to the problem as a sequence of UAVs and waypoints,as shown in Fig.7.The sequence consists of a list of UAV numbers followed by the way-points that it visits(in order).If a UAV number is im-mediately followed by another UAV number,then the ?rst vehicle does not visit any waypoints.The Tabu search algorithm in[7]is used in our implementation.

UAV1WP1

Fig.7:Solution sequence when UAV1visits WP1, WP2,WP3;UAV2does not visit any waypoints;and UAV3visits WP4,WP5,WP6.

The objective function to be minimized here is the?eet completion time:

J=max

i (finish i)+

α

N V

i

(finish i)

where,finish i is the time that UAV i?nishes its mis-sion andα 1scales the average completion time compared to maximum completion time.

4.3Adding Side Constraints

The type of timing constraints implemented in this algorithm are the same as introduced in Section2.3. There are two di?erent ways to deal with these con-straints,one is to treat them as hard constraints and exclude any solution that violates them.An alternative is to treat them as soft constraints and add a penalty to the objective functions for the solution that violate the constraints[7].One advantage of using soft constraints is that the initial solution does not have to be a feasi-ble solution.This is important in cases that?nding a feasible solution itself is di?cult.Another advantage of soft constraints is that the algorithm is not restricted to feasible regions and can move through an infeasible region to?nd a better feasible solution.Our algorithm treats the timing constraints as soft constraints.In this case,if there is a constraint on waypoint i being visited after j,but in a solution we have start j>start i (start i represents the time that waypoint i is visited), then a penalty is added to the objective value of this solution.By increasing the magnitude of this penalty, we can move from soft to hard timing constraints.

The problem formulation also includes capability con-straints on the di?erent UAVs,which have a signi?cant impact on the solution of the assignment problem.The

problems with heterogeneous UAVs and relative timing constraints.

UAV capabilities are given by the binary matrix K. Similar to the timing constraints,the UAV capabilities can be added in two ways.If,in a solution,waypoint x is in the list of missions for a UAV of type i that is not capable of visiting that waypoint(i.e.,K ix=0),then the solution is either rejected or kept as a solution with a penalty for violating the constraint.

In the environments with obstacles,Tabu search can be applied with a slight change in the algorithm.A matrix that represents the distance between all pairs of points is given to the algorithm as an input.In the case that there is no obstacle,these distances are simply straight lines between the two points.But when there are obstacles,these distances can be calculated using visibility graph and Dijkstra’s algorithm,as discussed earlier.

4.4Simulation Results

To show di?erent capabilities of the algorithm for this application,it is?rst applied to a small problem.Fig.8 shows the result of a UAV assignment problem for a small?eet facing four di?erent scenarios.There are two UAVs and four waypoints,and the objective is to minimize the mission completion time.The top left ?gure shows the result for the scenario in which the two UAVs have the same capabilities and there are no timing constraints.As expected,one UAV visits the waypoints at the top and the other UAV visits the ones at the bottom.The top right?gure shows the solu-tion of the same problem with timing constraints not satis?ed by the solution to the?rst problem.In this scenario,waypoint5is constrained to be visited after waypoints4and6.As shown,the cost has increased compared to the?rst scenario,but the constraints are now satis?ed.The bottom left?gure shows the scenario without the timing constraint,but with heterogeneous UAVs.In this scenario,UAV1is capable of visiting all the waypoints,while UAV2can just visit waypoints3 and4.Therefore UAV2visits the waypoints that it is capable of visiting and UAV1visits the rest.The bot-

Fig.9:(a)Result of Tabu search applied to a problem with4UAVs and20waypoints.(b)Result with timing constraints(waypoint22to be visited after waypoints15and24)

tom right?gure shows the result of the scenario with heterogeneous UAVs and relative timing constraints.In this scenario,again UAV1can visit all waypoints and UAV2can only visit waypoints3and4.The timing constraints are that waypoint4should be visited after waypoints5and6.As shown,the?nal result satis?es all of the constraints by having UAV2just visit way-point3and UAV1taking care of the rest of waypoints. To show the capability of the algorithm on larger prob-lems,an example with4UAVs and20waypoints is shown in Figs.9(a,b).Fig.9(a)shows the solution with no constraints,while Fig.9(b)has two timing con-straints that force waypoint22to be visited after way-points15and24.As shown,the solution in Fig.9(b) gives a cost(315.7)that is slightly lower than the cost (316.9)for the solution in Fig.9(a).In the optimal case this should not be the case since Fig.9(a)has no constraints.However,the Tabu search is a heuristic method and optimality of the solution is not guaran-teed.Many studies have shown that it is possible to get very close to the optimal solution if the parame-ters in the problem are chosen correctly.The initial solution is another important factor in a Tabu search. The initial solution impacts the convergence rate for the algorithm,and it can also e?ects the?nal solu-tion.However,in2000trials of this UAV problem with di?erent initial conditions,the result shows that more than95%of the solutions are within3%of the best solution.The computation time for these trials using a non-optimized code in MATLAB,varies between12 to15seconds.Better results can be achieved by using more e?cient codes.

The Tabu solutions in this section meet the relative timing constraints by arranging the vehicle paths so that the UAVs arrive at the waypoints at the correct times.However,with complicated constraints of the type shown in Fig.2(b),it is possible that this sub-optimal approach could result in a poor solution.The solution in Section2was to add loitering times to in-crease the number of degrees of freedom in the prob-lem,thereby yielding better solutions.Loitering could be added to Tabu search by including(discrete)time increments to the solution sequence in Fig.7.These times would then be used to separate the arrival and departure times of the preceding UAV at the preceding WP number.

5Conclusions

This paper presents an extension of the multiple UAV task allocation problem that explicitly includes the rel-ative timing constraints found in many mission scenar-ios.This not only allows us to determine which ve-hicle should go to each waypoint,but it also allows us to account for the required ordering and relative timing in the task assignment.The allocation prob-lem was also extended to include loiter times as extra (continuous)degrees of freedom to ensure that,even with very complicated timing constraints,feasible so-lutions still exist.Simulation results clearly showed that adding these timing constraints to the problem increases the computational time when the constraints are active(i.e.,“unnatural”).The constrained alloca-tion problem was also formulated in a way that can be solved using Tabu search,which was demonstrated to provide good solutions in reasonable computation times for large problems that are very di?cult to solve using the exact or approximate decomposition methods.

Acknowledgments

Research funded in part by AFOSR grant#F49620-01-1-0453.

References

[1]P.Chandler,M.Pachter,D.Swaroop,J.Fowler,et al.

“Complexity in UAV cooperative control,”ACC2002.

pp.1831-1836

[2]J.Bellingham,M.Tillerson,A.Richards,and J.How,

“Multi-Task Allocation and Path Planning for Cooper-ating UAVs,”Second Annual Conference on Cooperative Control and Optimization,Nov2001.

[3] C.Schumaker,P.Chandler,S.Rasmussen,“Task Al-

location for Wide Area Search Munitions via Network Flow Optimization”AIAA GNC,Aug.2001.

[4] A.Bemporad and M.Morari,“Control of Systems Inte-

grating Logic,Dynamics,and Constraints,”Automat-ica,Pergamon/Elsevier Science,Vol.35,pp.407-427, 1999.

[5] A.Richards,J.Bellingham,M.Tillerson,and J.P.How,

“Co-ordination and Control of Multiple UAVs,”AIAA Guidance,Navigation,and Control Conference,Mon-terey,CA,August2002.AIAA Paper2002-4588

[6] F.Glover and https://www.wendangku.net/doc/358759116.html,guna,Tabu Search,Kluwer

Acad.Publ.,1997.

[7]K.P.O’Rourke,T.G.Bailey,R.Hill and W.B.Carlton,

“Dynamic Routing of Unmanned Aerial Vehicles Using Reactive Tabu Search,”Military Operations Research Journal,Vol.6,2000.

[8]M.Gendreau, A.Hertz and https://www.wendangku.net/doc/358759116.html,porte,“A Tabu

Search Heuristic for the Vehicle Routing Problem,”

Management Science,Vol.40,pp.1276-1289,1994. [9] E.D.Taillard,P.Badeau,M.Gendreau,F.Guertin,

J.Y.Potvin,“A Tabu search heuristic for the vehicle routing problem with soft time windows,”Transporta-tion science Vol.31,pp.170-186,1997.

[10] A.V.Breedam,“Comparing Descent Heuristics and

Metaheuristics for the Vehicle Routing Problem”,Com-puters and Operations Research,Vol.28,pp.289-315, 2001.

相关文档