Collision Avoidance for Multiple UAVs using Rolling-horizon Policy

Collision A oidance o Mul iple UAVs using Rolling-ho izon Policy S. Ve a, J. A. Cobano, G. He edia and A. Olle o Abs ac —This pape add esses he p oblem o collision a oidance in scena ios wi h mul iple ae ial ehicles and p oposes a me hod based on a Legend e pseudospec al colloca ion in o de o compu e he solu ion ajec o ies and gua an ee ha he sa e y dis ance be ween hem is always main ained. The me hod uses a olling ho izon policy in which ajec o ies a e planned up o a gi en ime ho izon, hus conside ing a much smalle p oblem space. Then, he sys em is applied i e a i ely. S udies ha e been pe o med o se he alues o he look-ahead ime and he numbe o colloca ions poin s. The compu a ional load and scalabili y o he me hod a e also s udied in andomly gene a ed scena ios o es i s applica ion in eal ime. Expe imen s ha e been also ca ied ou in he mul i ehicle ae ial es bed o he Cen e o Ad anced Ae ospace Technologies (Se ille, Spain). I. INTRODUCTION Mul iple UAVs a e being coope a i ely used in he las yea s o ca y ou coo dina ed missions [1] [2]. Coo dina ion and collision a oidance a ises as c i ically impo an aspec s in his kind o applica- ions in dynamic en i onmen s. The e o e, a me hod o plan collision- ee ajec o ies wi h low compu a- ional load should be implemen ed in o de o ensu e he sa e y in hese en i onmen s. Conc e ely, an e icien e-planning is needed o sol e he collisions de ec ed. Many wo ks on planning algo i hms and colli- sion a oidance me hods ha e been published. A de ailed su ey on he o me is p esen ed in [3] and [4] e iews pape s on he la e . Planning me h- ods include Rapidly-explo ing Random T ees (RRT) *This wo k was suppo ed by he Eu opean Commission FP7 ICT P og amme unde he EC-SAFEMOBIL p ojec (288082) and he CLEAR p ojec (DPI2011-28937-C02-01) unded by he Minis e io de Ciencia e Inno acion o he Spanish Go e nmen . The au ho s would like o hank M . Miguel Angel T ujillo o hei unsel ish help du ing he de elopmen o he expe imen s in he es bed o CATEC (Se ille). 1S. Ve a, J. A. Cobano, G. He edia and A. Olle o a e wi h he Robo ics, Vision and Con ol G oup, Enginee ing School, Uni e si y o Se ille, 41092 Se ille, Spain {s e a,jcobano,guille ,aolle o}@us.es [5], pa icle swa m op imiza ion [6], e olu iona y compu a ion me hods [7], an colony op imiza ion me hods [8]. The main d awback o hese me hods is ha he compu a ion ime is no p edic able and he con e gence o a solu ion is no ensu ed in a ini e ime in e al. The e o e, hey a e no good candida es o plan collision- ee ajec o ies in a dynamic en i onmen and a small ime ho izon. An in e es ing op ion could be o use colloca- ion me hods o ajec o y gene a ion, which ha e been inc easingly employed in he las yea s. In colloca ion me hods ajec o y gene a ion is posed as an op imal con ol p oblem and he solu ion is app oxima ed by polynomials. Then, he di e en ial equa ions and cons ain s a e en o ced in colloca ion poin s, and he op imal con ol p oblem is ans- o med in o a nonlinea p og amming p oblem. Among he mos used colloca ion echniques a e he di ec colloca ion and he pseudospec al me h- ods. The o me di ides ime in se e al segmen s, compu es he solu ion conside ing a ixed deg ee polynomial s a e app oxima ion in each segmen and he con e gence is achie ed by inc easing he numbe o segmen s [9]. The la e uses a single segmen and con e gence is achie ed by inc eas- ing he deg ee o he polynomial. Bo h me hods choose he colloca ion poin s based on accu a e quad a u e ules and he basic unc ions a e yp- ically Chebyshe o Lag ange polynomials. The mo e commonly used pseudospec al me hods a e he Gauss pseudospec al me hod (GPM) [10], he Radau pseudospec al me hod [11] (RPM), and he Loba o pseudospec al me hod [12] (LPM). Pseu- dospec al and Di ec Colloca ion me hods ha e been applied o compu e ai c a ajec o ies [13] [14] [15] bu hei compu a ion imes a e oo la ge o plan ajec o ies in dynamic and unce ain en i on- men s. Mo eo e , mos o published wo ks conside ajec o y gene a ion o a s andalone ehicle [13] [14]. P ep in e sion o : Ve a S, Cobano JA, He edia G and Olle o A (2016), Collision A oidance o Mul iple UAVs Using Rolling-Ho izon Policy, Jou nal o In elligen & Robo ic Sys ems, Decembe 2016, Vol. 84 A modi ied pseudospec al me hod is called hp- adap i e [16]. In his me hod, he numbe o seg- men s and he deg ee o he polynomial can be inc eased wi hin a segmen o achie e an e o less han he ole ance e o allowed. Howe e , each segmen adds colloca ion poin s in each i e a ion, so he numbe o colloca ion poin s could quickly g ow and ha p o okes la ge compu a ion imes. This pape add esses he p oblem o collision a oidance wi h mul iple UAVs in dynamic en i on- men s using a olling ho izon policy. The goal is o ensu e he sa e y and eliabili y o he mission. The p oposed me hod is based on pseudospec al colloca ion echniques and is i e a i e. The in o - ma ion o all he UAVs is known up o a ligh ime de ined by he look-ahead ime and he dynamics o he UAVs is conside ed o compu e mo e ealis ic ajec o ies. Look-ahead imes a e de e mined by a olling ho izon app oxima ion in o de o quickly compu e solu ion ajec o ies o he sub-p oblem conside ed. The maneu e s allowed o sol e he de- ec ed collisions a e changes o speed and heading. The main cha ac e is ic o he p oposed me hod is he low compu a ional load and he scalabili y. The look-ahead ime and he numbe o colloca ion poin s in luence he ime o compu a ion and he sa e y o he solu ion. The easible alues o hese pa ame e s a e s udied in his pape . O he impo an imp o emen in he implemen- a ion is he e alua ion o he whole solu ion a- jec o ies because pseudospec al echniques only compu e he solu ion alid in he colloca ion poin s. Tha is, he minimum sepa a ion among ehicles is main ained in hese poin s. The e o e, an e alua ion conside ing a model o ehicle should be ca ied ou in o de o ensu e ha he minimum sepa a ion is no iola ed du ing he whole ajec o y o he sub-p oblem conside ed in each ins an . The pape is o ganized in o se en sec ions. Sec- ion II desc ibes he p oblem o mula ion. The p o- posed me hod is explained in Sec ion III. Simula- ions and expe imen s pe o med a e showed in Sec- ion IV and V, espec i ely. Finally, he conclusions a e de ailed in Sec ion VI. II. PATH PLANNING FOR MULTIPLE UAVS The p oblem o collision a oidance o mul iple UAVs o pe o m he coo dina ed missions is con- side ed in his pape . The goal is o assu e ha he UAVs do no collide wi h each o he . The p oposed me hod o sol e he collisions allows changes o he speed p o ile and he heading o he UAVs in ol ed in he con lic . The ajec o y o each UAV is gi en by an ini ial waypoin and a inal waypoin . Each waypoin is de ined by: 2D coo dina es (x, y), speed module om ha waypoin ( ), and he Es ima ed Time o A i al (ETA) o he waypoin , . I is assumed ha all UAV ajec o ies a e known in he ime in e al gi en by he look-ahead ime. We conside ha he UAVs main ain he sa e y sepa a ion i hey a e sepa a ed by a minimum dis ance, D. The inpu s o he me hod a e he ollowing: •Model o each UAV •Look-ahead ime •Numbe o nodes pe segmen Numbe o nodes pe segmen , also known as colloca ion poin s, de ines he deg ee o he polyno- mial o in e pola ion used in each segmen . Look- ahead ime is he ime in which each UAV knows he in o ma ion o he es o UAVs. This ime in e al de ines he sub-p oblem o he ajec o y planning o each UAV. Bo h look-ahead ime and he numbe o colloca ion poin s should be analyzed. The bes alues o bo h pa ame e s should ensu e a sa e solu ion in each compu a ion and wi h low compu a ional load o i e a i ely pe o m ajec o y e-planning in dynamic en i onmen . Di e en op imiza ion c i e ia can be conside ed. In his pape , wo c i e ia ha e been implemen ed: minimize he changes o he heading angle o each UAV and minimize he changes o he con ol inpu s (pi ch and oll angles). III. LEGENDRE PSEUDOSPECTRAL METHOD The pseudospec al me hod nume ically sol es op imal con ol p oblems. The basic app oach is o ans o m he op imal con ol p oblem in o a se- quence o nonlinea cons ained op imiza ion p ob- lems by disc e izing he s a e and con ol a iables. I compu es a se o colloca ion poin s ha p o ides an accu a e app oxima ion o he solu ion o he op imal con ol p oblem. The p oposed me hod is based on a Legend e pseudospec al me hod known as DIDO [17]. I s no el y is how an i e a i e im- plemen a ion is ca ied ou in o de o ob ain an e icien ajec o y e-planning. The op imal p oblem is modeled as a Bolza p ob- lem in τ[−1,1] domain and he objec i e is o ind he con ol inpu ec o u(τ)and he co esponding s a e χ(τ)which minimize he cos unc ion: J=φ(χ(−1), χ(+1)) + Z1 −1 L(χ(τ), u(τ), τ)dτ (1) subjec o he dynamic cons ain s ˙χ= (χ, u)(2) inequali y pa h cons ain s C(χ, u)≤0(3) and he bounda y condi ions E(χ(−1), χ(+1)) = 0 (4) whe e φ,Cand Ea e unc ions. The no malized ime τ[−1,1] and he ime [ 0, ]a e ela ed by: = − 0 2τ+ − 0 2(5) Eq. (1) should be app oxima ed by applying quad a u e ules. In his pape Legend e-Gauss- Loba o (LGL) quad a u e ule is used, so: J=φ(χ1, χN) + N X j=1 L(χj, uj)wj(6) whe e wja e he LGL quad a u e weigh s, and N is he numbe o nodes o colloca ion poin s. In he used no a ion, he o e line means disc e e a iables and he supe sc ip means he colloca ion poin used χj=χ(τj). LGL nodes a e de ined in he no malized ime domain τ[−1,1] as τ0=−1< τ1< τ2< ... < τN= 1 whe e 1,2, ..., N −1a e he oo s o he de i a i e o he N- h o de Legend e polynomial. The oo s o he de i a i e o he Legend e poly- nomials a e ze os in hese nodes because hey a e o hogonal polynomials. The e o e, χ(τ)and u(τ)could be app oxima ed by χ(τ)and u(τ): χ(τ)≈χ(τ) = N X j=0 χjLj(τ)(7) u(τ)≈u(τ) = N X j=0 ujLj(τ)(8) whe e Lj(τ)a e he basis unc ions o he La- g ange in e pola ing polynomials o o de N. The p oposed me hod is i e a i e in such a way ha i compu es an op imal solu ion o a sub- p oblem in e e y i e a ion. The look-ahead ime, Tla, is de e mined by he knowledge o he en i onmen in e e y i e a ion and he maximum speed o he e- hicle ha is he wo s case o ajec o y e-planning. The numbe o colloca ion poin s conside ed in each i e a ion, Nc, also in luences he p oposed me hod. This numbe a ec s he quali y o he solu ion and he compu a ion ime. The quali y means ha he solu ion could be lown and he minimum sep- a a ion dis ance should be me by all UAVs. I cons ain s a e me in e e y piece o he pa h, i would ensu e he minimum sepa a ion dis ance in he whole ajec o y. Mo eo e , a low compu a ional ime is equi ed. Also, he equency o compu a ion should be de e mined in o de o ensu e ha each UAV does no ly he whole ajec o y compu ed in he p e ious i e a ion du ing he co esponding ime be ween wo i e a ions, T . This ime should be la ge han he compu a ion ime o he UAV ajec o ies, Tc: T > Tc(9) Figu e 1 illus a es he pe o mance o he p o- posed me hod. Fi e colloca ion poin s ha e been conside ed (blue poin s) and a look-ahead ime is conside ed om he knowledge o he en i onmen in e e y i e a ion and he maximum speed o he ehicle. Fi s , he ajec o y o each UAV is com- pu ed wi hin he look-ahead ime. An i e a ion is compu ed e e y T , so he compu a ion ime, Tcin he second i e a ion should ul ill: Tla −T > Tc(10) Figu e 1. Desc ip ion o he p oposed me hod. Finally, a model o UAV by conside ing a sim- pli ied dynamics is used o compu e mo e ealis ic ajec o ies. The al i ude is assumed o be cons an . The s a e ec o is de ined by (xi, yi,Φi,Θi, i) whe e xi, yi he 2D posi ion o he ae ial ehicle, Φi,Θia e he pi ch and oll angles and i he ime o a i al in each colloca ion poin . The con ol inpu s a e he pi ch and oll o ques uΦi, uΘi. The model conside ed is: ¨xi=T m·sin(Φi)(11) ¨yi=T m·sin(Θi)(12) ¨ Θi=uΘi Iy (13) ¨ Φi=uΦi Ix (14) whe e Tis he h us needed o main ain he cons an al i ude, mis he mass, Θiis he oll angle, Φiis he pi ch angle, Ixand Iya e he momen s o ine ia wi h espec o he axes xand y, espec i ely. The mul i-UAV sys em is de ined by conca ena - ing he s a e o all he UAVs. The e o e, he s a e ec o and con ol ec o a e de ined as ollows: X= [x1, y1,Φ1,˙ Φ1,Θ1,˙ Θ1, 1, ...., xn, yn,Φn,˙ Φn,Θn,˙ Θn, n](15) U= [uΦ1, uΘ1, uΦ2, uΘ2...., uΦn, uΘn](16) whe e nis he numbe o UAVs. The solu ion should sa is y cons ain s aking in o accoun he physical limi a ions o he inpu s o each UAV: uθmin ⩽uθi⩽uθmax (17) uΦmin ⩽uΦi⩽uΦmax (18) And he sepa a ion be ween UAViand UAVj should mee : dis ance(UAVi, UAVj)≥D(19) whe e Dis he sa e y dis ance. IV. SIMULATIONS The me hod has been es ed by ca ying ou many simula ions. Di e en scena ios andomly gene a ed wi h se e al UAVs ha e been conside ed. The p oblems ha e been sol ed wi h he pseu- dospec al LGL colloca ion me hod, using he op- imal con ol so wa e named DIDO [17]. These algo i hms ha e been un in a PC wi h a CPU In el Co e i7-3770 @ 3.4 Ghz and 16 GB o RAM. The ope a ing sys em used in he simula ions was Windows 7 OS and he code has been implemen ed in Ma lab. Fi s , he alues o he look-ahead ime, Tla, and he numbe o colloca ion poin s, Nc, should be se . A s udy conside ing one hund ed andom scena ios wi h i e UAVs has been pe o med o analyze he bes alues. The chosen alues should ensu e a sa e solu ion wi h a low compu a ion ime. The possi- ble alues a e: Tla = [1.0,1.5,2.0,2.5,3.0]sand Nc= [3,4,5,6,7,8] poin s. All he combina ions o hese alues a e explo ed in each scena io. The ob ained mean compu a ion ime and i s s anda d de ia ion o each combina ion which ensu es a sa e solu ion in all he scena ios ( ha is, sa is ies all he cons ain s) is shown in Table I. Only eigh combina ions me i . In o de o mee (9), T should be g ea e han 1.107s( he la ge alue o Tc+σT c in Table I), so T = 1.25sis conside ed. Fi s , second, ou h and six h cases only mee (10). Among hese op ions, Tla = 2.5sand Nc= 4 a e chosen because hey ensu e a minimum compu a ion ime. Table I COMBINATIONS THAT ENSURES A SAFE SOLUTION. Tla(s) NcTc(s) σT c (s) 2.5 4 0.808 0.207 2.5 3 0.819 0.212 1.0 4 0.815 0.258 3.0 3 0.824 0.304 1.5 3 0.837 0.197 2.5 6 0.847 0.219 1.0 7 0.851 0.207 2.0 6 0.873 0.234 Once bo h pa ame e s ha e been se , he scalabil- i y is analyzed, ha is, how he compu a ion ime depends on he numbe o UAVs. Figu e 2 shows he scena io conside ed wi h up o eigh UAVs. No e ha in case o 7 o 8 UAVs, he densi y o UAVs in he scena io is e y high. Figu e 2. Scena io S1 conside ed in he simula ions wi h up o eigh UAVs: UAV1 in blue, UAV2 in ed, UAV3 in black, UAV4 in g een, UAV5 in pink, UAV6 in clea blue, UAV7 in yellow and UAV8 in dashed blue. Table II shows he compu a ion mean ime and s anda d de ia ion o he scalabili y es . No e ha scena io S1 is conside ed. The p oposed me hod adap s well conside ing up o se en UAVs because (9) is me . Table II MEAN COMPUTING TIME WHEN THE NUMBER OF UAVS INCREASES BY CONSIDERING THE SCENARIO S1. Numbe o UAVs UAVs Time (s) σ (s) 3 1-3 0.308 0.150 4 1-4 0.374 0.204 5 1-5 0.480 0.269 6 1-6 0.689 0.279 7 1-7 0.961 0.294 8 1-8 1.297 0.472 Figu e 3 p esen s he scena io S2 conside ed wi h ou UAVs o show how he p oposed me hod compu es a solu ion e e y T . Figu es 4, 5, 6 and 7 shows ou ins an s which co espond o = 2.5,7.5,10.0,16.5s. The sub-p oblems sol ed a e p esen ed in e e y i e a ion. No e ha each UAV ajec o y con e ges o i s goal waypoin . Figu e 3. Scena io S2 wi h ou UAVs: UAV1 in blue, UAV2 in ed and UAV3 in black and UAV4 in g een. Figu e 4. T ajec o y compu ed by he me hod a he ins an = 2.5s. Figu e 5. T ajec o y compu ed by he me hod a he ins an = 7.5s. The whole ajec o ies a e shown in Figu e 8. The speed p o ile ob ained is p esen ed in Figu e 9. Figu e 6. T ajec o y compu ed by he me hod a he ins an = 10.0s. Figu e 7. T ajec o y compu ed by he me hod a he ins an = 16.5s. Figu e 8. Final ajec o y o scena io S2: UAV1 in blue, UAV2 in ed and UAV3 in black and UAV4 in g een. V. EXPERIMENTS Expe imen s ha e been ca ied ou in he indoo mul i-UAV es bed o he CATEC wi h ou Hum- Figu e 9. Final speed p o ile o scena io S2: UAV1 in blue, UAV2 in ed and UAV3 in black and UAV4 in g een. mingbi d quad o o s (see Figu e 10) wi h up o 20 minu es ligh au onomy. The es bed has an indoo localiza ion sys em based on 20 VICON came as. This sys em is able o p o ide, in eal ime, he posi ion and a i ude o each UAV wi h cen ime e accu acy. Figu e 10. Indoo mul i-UAV es bed o he CATEC wi h Hum- mingbi d quad o o om Ascending echnologies. This sec ion shows an expe imen o demon- s a e he pe o mance o he p oposed me hod. The minimum sepa a ion is 1.0m. In his case, he op imiza ion c i e ion is o minimize he heading changes. Figu e 11 shows he scena io conside ed. Two collisions a e de ec ed. Fou quad- o o s in hei ini ial posi ion a e shown in Figu e 12. The whole solu ion ajec o ies compu ed a e shown in Figu e 13. The speed p o ile ob ained is p esen ed in Figu e 14. Figu e 11. Scena io conside ed in he expe imen wi h ou UAVs: UAV1 in blue, UAV2 in ed and UAV3 in black and UAV4 in g een. Figu e 12. Fou quad- o o s conside ed in he expe imen . Each quad- o o is in i s ini ial posi ion. Figu e 13. Solu ion ajec o ies de ined by he waypoin s compu ed: UAV1 in blue, UAV2 in ed and UAV3 in black and UAV4 in g een. Each UAV eal ajec o y is ep esen ed in Figu e 15 and Figu e 16 shows he sepa a ion among Figu e 14. Speed p o ile o each UAV: UAV1 in blue, UAV2 in ed and UAV3 in black and UAV4 in g een. UAVs. Each UAV main ains he minimum sepa a- ion dis ance. Figu e 15. UAV eal ajec o ies in he expe imen : UAV1 in black, UAV2 in blue, UAV3 in ed and UAV4 in g een. VI. CONCLUSIONS This pape add esses he p oblem o collision a oidance wi h mul iple UAVs in coo dina ed mis- sions by ensu ing he sa e y and eliabili y o he mission in dynamic en i onmen s. A me hod is p oposed o e icien ly e-plan each UAV ajec o y and pe o m he mission. The me hod akes in o accoun he dynamics o he ehicles o compu e mo e ealis ic ajec o ies. I is based on a Legend e pseudospec al colloca ion o gene a e ajec o ies and a olling ho izon policy is used. I is applied i e a i ely and collision- ee ajec o ies a e planned in a sub-p oblem de ined by he ime ho izon. Figu e 16. Sepa a ion be ween UAVs in he expe imen : UAV1- UAV2 in black, UAV1-UAV3 in blue, UAV1-UAV4 in ed,UAV2- UAV3 in g een, UAV2-UAV4 in clea blue, UAV3-UAV4 in pink and he minimum sepa a ion in dashed black line. Two maneu e s a e allowed: changes o speed and heading. The main ad an age o he p oposed me hod is i s low compu a ional load. Ano he no el aspec is o conside mul iple UAVs and wo possible maneu e s. Mos o wo ks published on colloca ion echniques o UAVs conside one ehicle [13] [16]. Look-ahead ime and numbe o colloca ion poin s a e he mo e ele an pa ame e s o he me hod because o hei in luence on he compu- a ion ime. A lo o es s ha e been ca ied ou o ensu e sa e solu ions and low compu a ion imes by conside ing andom scena ios. The scalabili y o he me hod has been analyzed. Finally, eal expe imen s ha e been ca ied ou in he mul i ehicle ae ial es bed o he Cen e o Ad anced Ae ospace Technologies (Se ille, Spain). REFERENCES [1] J. A. Cobano, J. R. Ma ´ ınez-de Dios, R. Conde, J. M. S´ anchez- Ma amo os, and A. Olle o, “Da a e ie ing om he e ogeneous wi eless senso ne wo k nodes using UAVs ,” Jou nal o In elligen and Robo ic Sys ems, ol. 60, no. 1, pp. 133–151, 2010. [2] L. Me ino, F. Caballe o, J. M. de Dios, I. Maza, and A. Olle o, “An unmanned ai c a sys em o au oma ic o es i e moni o ing and measu emen ,” Jou nal o In elligen and Robo ic Sys ems, ol. 65, no. 1, pp. 533–548, 2012. [Online]. A ailable: h p://dx.doi.o g/10.1007/s10846-011-9560-x [3] C. Goe zen, Z. Kong, and B. Me le , “A su ey o mo ion planning algo i hms om he pe spec i e o au onomous UAV guidance,” Jou nal o In elligen Robo Sys ems, ol. 57, pp. 65–100, 2010. [4] J. K. Kucha and L. C. Yang, “A e iew o con lic de ec ion and esolu ion modeling me hods,” IEEE T ansac ions on In elligen T anspo a ion Sys ems, ol. 1, pp. 179–189, 2000. [5] S. M. La alle, J. J. Ku ne , and J ., “Rapidly-explo ing andom ees: P og ess and p ospec s,” in Algo i hmic and Compu a- ional Robo ics: New Di ec ions, 2000, pp. 293–308. [6] D. Alejo, J. A. Cobano, G. He edia, and A. Olle o, “Pa icle Swa m Op imiza ion o collision- ee 4d ajec o y planning in unmanned ae ial ehicles,” in P oceedings o he In e na ional Con e ence on Unmanned Ai c a Sys ems (ICUAS), A lan a, USA, 28-31 May 2013, pp. 298–307. [7] R. Conde, D. Alejo, J. A. Cobano, A. Vigu ia, and A. Olle o, “Con lic de ec ion and esolu ion me hod o coope a ing un- manned ae ial ehicles,” Jou nal o In elligen & Robo ic Sys- ems, ol. 65, pp. 495–505, 2012, 10.1007/s10846-011-9564-6. [8] N. Du and and J. Allio , “An colony op imiza ion o ai a ic con lic esolu ion,” in P oceedings o he Eigh h USA/Eu ope Ai T a ic Managemen Resea ch and De elopmen Semina (ATM2009), Napa, (CA, USA), 2009. [9] J. T. Be s, P ac ical Me hods o Op imal Con ol using Nonlinea P og amming. SIAM P ess: Philadelphia, 2011. [10] D. A. Benson, G. T. Hun ing on, T. Tho aldsen, and A. V. Rao, “Di ec ajec o y op imiza ion and cos a e es ima ion ia an o hogonal colloca ion me hod,” Jou nal o Guidance, Con ol, and Dynamics, ol. 29, no. 6, pp. 1435–1440, 2006. [11] D. Ga g, M. A. Pa e son, W. W. Hage , A. V. Rao, D. A. Benson, and G. T. Hun ing on, “A uni ied amewo k o he nume ical solu ion o op imal con ol p oblems using pseu- dospec al me hods,” Au oma ica, ol. 46, no. 11, pp. 1843– 1851, 2010. [12] G. Elnaga , M. Kazemi, and M. Razzaghi, “The pseudospec al Legend e me hod o disc e izing op imal con ol p oblems,” IEEE T ansac ions on Au oma ic Con ol, ol. 40, no. 10, pp. 1793–1796, 1995. [13] B. R. Geige , J. F. Ho n, G. L. Sinsley, J. A. Ross, and L. N. Long, “Fligh es ing a eal ime implemen a ion o a UAV pa h planne using di ec colloca ion,” in P oceedings o he AIAA Guidance, Na iga ion and Con ol Con e ence and Exhibi , Sou h Ca olina, USA, 20-23 Augus 2007. [14] G. Basse , Y. Xua, and O. A. Yakimenkob, “Compu ing sho ime ai c a maneu e s using di ec me hods,” Jou nal o Compu e and Sys ems Sciences In e na ional, ol. 49, no. 3, pp. 481–513, 2010. [15] K. P. Bollino and L. R. Lewis, “Collision- ee mul i-UAV op i- mal pa h planning and coope a i e con ol o ac ical applica- ions,” in AIAA Guidance, Na iga ion and Con ol Con e ence and Exhibi , 18-21 Augus 2008, pp. 1–18. [16] C. L. Da by, W. W. Hage , and A. V. Rao, “An hp-adap i e pseudospec al me hod o sol ing op imal con ol p oblems,” Op imal Con ol Applica ions and Me hods, ol. 32, no. 4, pp. 476–502, 2010. [17] I. M. Ross and F. Fah oo, “Use s manual o dido 2002: A ma lab applica ion package o dynamic op imiza ion,” in NPS Technical Repo AA-02-002,, Depa men o Ae onau ics and As onau ics, Na al Pos g adua e School, Mon e ey, CA. (USA), 2002.