The procedure presented within considers the problem of calculating flight time for unmanned aerial vehicles (UAVs) while incorporating a subset of important flight dynamics characteristics in an operational field that contains obstacles. These flight time calculations are parameter inputs in mission planning and dynamic reassignment problems. The addition of pseudonodes and the addition of penalties into the associated edge weights are the basis for how the network generation procedure includes flight dynamics. The procedure includes a method for handling pop-up targets or obstacles in a dynamic reassignment problem. To guarantee that the optimal path includes flight dynamics, a selective Dijkstra’s algorithm computes the shortest path. A complex mission plan consisting of thirty targets and three obstacles is the largest test scenario of nine developed scenarios. Our network generation procedure, along with the shortest path calculations of all 992 node pairs of interest, solves in approximately one second. This procedure allows for the fast computation needed to generate parameters for use in a dynamic domain such as mission planning and dynamic reassignment algorithms.
USAF. The U.S. Air Force remotely piloted aircraft and unmanned aerial vehicle strategic vision, 2005.
2.
KingstonDSchumacherC.Time-dependent cooperative assignment. In: Proceedings of the 2005 American control conference, Portland, OR, USA, 8–10 June 2005, pp.4084–4089.
3.
MufalliFBattaRNagiR.Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans. Comput Oper Res2012; 39(11): 2787–2799.
4.
ShettyVSuditMNagiR.Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles. Comput Oper Res2008; 35: 1813–1828.
5.
ShimaTRasmussenSSparksA. Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms. Comput Oper Res2006; 33: 3252–3269.
6.
WeinsteinASchumacherC.UAV scheduling via the vehicle routing problem with time windows. Technical report afrl-va-wp-tp-2007-306, Air Force Research Laboratory, 2007.
7.
WildeJDibiasoDNervegnaM. Team planning for unmanned vehicles in the risk-aware mixed-initiative dynamic replanning system. In: Oceans 2007, Vancouver, BC, Canada, 29 September–4 October 2007, pp.1–8.
8.
BellinghamJTillersonMRichardsA. Multi-task allocation and path planning for cooperating UAVs. In: Cooperative control: Models, applications and algorithms. Boston, MA, USA: Kluwer Academic Publishers, 2003, pp.1–19.
9.
KinneyGHillRMooreJ.Devising a quick-running heuristic for an unmanned aerial vehicle (UAV) routing system. J Oper Res Soc2005; 56: 776–786.
10.
SchumacherCChandlerPPachterM. Optimization of air vehicles operations using mixed-integer linear programming. J Oper Res Soc2007; 58(4): 516–527.
11.
BergerJBarkaouiMBoukhtoutaA.A hybrid genetic approach for airborne sensor vehicle routing in real-time reconnaissance missions. Aerosp Sci Technol2007; 11: 31–326.
12.
MurrayCKarwanM.An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations. Nav Res Log2010; 57(7): 634–652.
13.
MurrayCKarwanM.A branch-and-bound-based solution approach for dynamic rerouting of airbourne platforms. Nav Res Log2013; 60(2): 141–159.
14.
TavanaMBaileyMBuschT.A multi-criteria vehicle-target allocation assessment model for network-centric joint air operations. Int J Oper Res2008; 3(3): 235–254.
15.
DijkstraEW.A note on two problems in connexion with graphs. Numer Math1959; 1(1): 269–271.
16.
LarsonRCLiVO.Finding minimum rectilinear distance paths in the presence of barriers. Networks1981; 11: 285–304.
17.
LarsonRCSadiqG.Facility locations with the Manhattan metric in the presence of barriers to travel. Oper Res1983; 31(4): 652–669.
18.
SarkarABattaRNagiR.Commentary on facility location in the presence of congested regions with the rectilinear distance metric. Socio Econ Plan Sci2004; 38: 291–306.
19.
ButtSCavalierT.Facility location in the presence of congested regions with the rectilinear distance metric. Socio Econ Plan Sci1997; 31: 103–113.
20.
SarkarABattaRNagiR.Finding rectilinear least cost paths in the presence of convex polygonal congested regions. Comput Oper Res2009; 36: 737–754.
21.
LeeDPreparataF.Euclidean shortest paths in the presence of rectilinear barriers. Networks1984; 14: 393–410.
22.
StorerJAReifJH.Shortest paths in the plane with polygonal obstacles. J ACM1994; 41(5): 982–1012.
23.
MitchellJSB. Shortest paths among obstacles in the plane. Int J Comput Geom Ap1996; 6(3): 309–332.
24.
LeeDT.Proximity and reachability in the plane. PhD Thesis, Champaign, IL, USA, 1978.
25.
WelzlE.Constructing the visibility graph for n-line segments in O(N2) time. Inform Process Lett1985; 20(4): 167–171.
HerschbergerJSuriS.An optimal algorithm for Euclidean shortest paths in the planeSIAM J Comput1997; 28: 2215–2256.
28.
MitchellJS.Geometric shortest paths and network optimization, 1998. Handbook of computational geometry. North-Holland: Elsevier Science Publishers BV, 1998, pp.633–701.
29.
ZabarankinMUryasevSMurpheyR.Aircraft routing under the risk of detection. Nav Res Log2006; 53(8): 728–747.
30.
GoldmanJ.Path planning problems and solutions. In: Proceedings of the IEEE National Aerospace and Electronics Conference, Dayton, OH, USA, 23–27 May 1994, pp.105–108.
31.
BertuccelliLChoiHChoP. Real-time multi-UAV task assignment in dynamic and uncertain environments. In: AIAA guidance, navigation, and control conference, Chicago, IL, USA, 10–13 August 2009.
32.
DivelbissAWWenJT.A path space approach to nonholonomic motion planning in the presence of obstacles. IEEE T Robotic Autom1997; 13(3): 443–451.
33.
RoysetJOCarlyleWMWoodRK.Routing military aircraft with a constrained shortest-path algorithm. Mil Oper Res2009; 14(3): 31–52.
34.
LewisLRossI.A pseudospectral method for real-time motion planning and obstacle avoidance. In: Platform innovations and system integration for unmanned air, land, and sea vehicles (AVT-SCI Joint Symposium), Neuilly-sur-Seine, France 2007, pp.10–1 to 10–22.
35.
KunchevVJainLIvancevicV. Path planning and obstacle avoidance for autonomous mobile robots: A review. Knowledge-Based Intelligent Information and Engineering Systems, Pt 2, Proceedings2006; 4252: 537–544.
ChenDSzczerbaRUhranJ.A framed quadtree approach for determining the Euclidean shortest paths in a 2-D environment. EEE T Robotic Autom1997; 13(5): 668–681.
38.
CasasIMalikADelmelleEM. An automated network generation procedure for routing of unmanned aerial vehicles (UAVs) in a GIS environment. Netw Spat Econ2007; 7(2): 153–176.
39.
KimJHespanhaJ. Discrete approximations to continuous shortest-path: Application to minimum risk path planning for groups of UAVs. In: 42nd IEEE conference on decision and control, Maui, HI, USA, 9–12 December 2003, pp.1734–1740.
40.
HelgasonRVKenningtonJLLewisKR.Cruise missile mission planning: A heuristic algorithm for automatic path generation. J Heuristics2001; 7(5): 473–494.
41.
CaldwellT.On finding minimum routes in a network with turn penalties. Commun ACM1961; 4: 107–108.
HencheyMBattaRKarwanM. A flight time approximation model for unmanned aerial vehicles: Estimating the effects of path variations and wind. Mil Oper Res2014; 19(1): 51–68.
46.
DubinsL.On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am J Math1957; 79(3): 497–516.
47.
ShkelALumelskyV.Classification of the Dubins set. Robot Auton Syst2001; 34: 179–202.
48.
GryminDCrassidisA.Simplified model development and trajectory determination for a UAV using the Dubins set. Presented at the AIAA Atmospheric Flight Mechanics Conference, Chicago, IL, USA, 10–13 August 2009.
49.
MurrayC.Dynamic reassignment and rerouting in cooperative airborne operations. PhD Thesis, University at Buffalo, State University of New York, 2010.
