A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets

The Dynamic Unmanned Aerial System Routing Problem (DUASRP) is a variant of the classicVehicle Routing Problem (VRP) in which both planned and unplanned targets are observed by afleet of Unmanned Aerial Systems (UASs). In the dynamic environment of UAS, the rapidresponse for the new important targets is a very critical process, especially for the militaryoperations in battle space conditions. This study describes a heuristic method for the solution ofthe dynamic heterogeneous UAS routing problems without causing the initial tour to becompletely changed. For the dynamic routing of Unmanned Aerial Vehicles (UAV), it isnecessary to determine a combination of the least additional costs of vehicle routes through a setof geographically scattered targets, and quick responses for immediate targets during thereconnaissance missions. The most frequent cases assumed in the existing literature of classicalDUASs consider all UASs as identical (homogenous), all targets as having two geographicalcoordinates, and the thread of the targets are ignored. In this paper, a dynamic routing decisionsupport system based on both fuzzy clustering and leveraged cheapest insertion neighborhoodmethod is studied for pop-up threat in the case where the UAV fleet is heterogeneous, andtargets have both three-dimensional information and threads. Instead of selecting an a prioricode, the proposed control methodology dynamically starts with the route based on observedbehavior of the new target and the routes. It describes an efficient heuristic method capable ofproducing quick dynamic solutions on a series of empirical test problems.

PDF

___

U.S. DoD Home Page, “Unmanned System Integrated Roadmap 2010-2035”. http://www.dtic.mil. (2011).
Goraj, Z., Aviation, Vol VII, No 1: 3-15, (2003).
Shima, Tal, and Steven J. Rasmussen, UAV cooperative decision and control: challenges and practical approaches. Vol. 18. SIAM, (2009).
Laporte, Gilbert, Michel Gendreau, J‐Y. Potvin, and Frédéric Semet, "Classical and modern heuristics for the vehicle routing problem." International transactions in operational research 7, no. 4‐5: 285-300, (2000).
Toth, P., and Vigo, D., The Vehicle Routing Problem, SIAM Monograhs on Discrete Mathematics and Applications, Philadelphia, PA: SIAM Publishing, (2001).
Psaraftis, Harilaos N, Vehicle Routing Methods and Studies: Dynamic Vehicle Routing Problems: 223-248. (North Holland), Amsterdam: Elsevier Science Publishers B.V., (1998).
Larsen, Allan, "The dynamic vehicle routing problem." PhD diss., Technical University of DenmarkDanmarks Tekniske Universitet, (2000)
Larsen, A., Madsen, O. B. G., and Solomon, M.G., Dynamic Fleet Management Concepts, Systems, Algorithms, and Case Studies: Classification of Dynamic Vehicle Routing Systems (38): 19-40, Springer Science & Business Media. Springer, (2007).
Ichoua, Soumia, Michel Gendreau, and Jean-Yves Potvin, "Diversion issues in real-time vehicle dispatching." Transportation Science 34, no. 4: 426-438, (2000).
Powell, Warren B., Patrick Jaillet, and Amedeo Odoni, "Stochastic and dynamic networks and routing." Handbooks in operations research and management science 8: 141-295, (1995).
Lund, K., H.F Madsen, and J.M. Rygaard, "Vehicles Routing Problems with Varying Degrees of Dynamism", Technical Report IMM-REP-1996-1, Technical University of Denmark, Denmark, (1996).
Bianchi, Leonora, "Notes on dynamic vehicle routing-the state of the art." Technical Report IDSIA-05-01 (ftp://ftp.idsia.ch/pub/techrep), (2000).
Psaraftis, Harilaos N., "Dynamic vehicle routing: Status and prospects." Annals of Operations Research 61, no. 1: 143-164, (1995).
Gendreau, Michel, Francois Guertin, Jean-Yves Potvin, and Eric Taillard, "Parallel tabu search for real-time vehicle routing and dispatching." Transportation Science 33, no. 4: 381-390, (1999).
O’Rourke, K., William B. Carlton, T. Glenn Bailey, and Raymond R. Hill. "Dynamic routing of unmanned aerial vehicles using reactive tabu search." 67th MORS Symposium.
Peape, W.E., “Complexity Results and Competitive Analysis for Vehicle Routing Problems”, PhD diss., Technical University of Eindhoven, (2002).
Chitty, Darren M., and Marcel L. Hernandez, "A hybrid ant colony optimisation technique for dynamic vehicle routing." Genetic and Evolutionary Computation–GECCO: 48-59. Springer Berlin Heidelberg, (2004).
Angelelli, Enrico, M. Grazia Speranza, and Martin WP Savelsbergh, "Competitive analysis for dynamic multiperiod uncapacitated routing problems." Networks 49, no. 4: 308-317, (2007).
Branke, Jürgen, Martin Middendorf, Guntram Noeth, and Maged Dessouky, "Waiting strategies for dynamic vehicle routing." Transportation Science 39, no. 3: 298-312, (2005).
Montemanni, Roberto, Luca Maria Gambardella, Andrea Emilio Rizzoli, and Alberto V. Donati, "Ant colony system for a dynamic vehicle routing problem." Journal of Combinatorial Optimization 10(4):327-343, (2005).
Ichoua, Soumia, Michel Gendreau, and Jean-Yves Potvin, "Exploiting knowledge about future demands for real-time vehicle dispatching." Transportation Science 40, no. 2: 211-225, (2006).
Jin, Yan, Yan Liao, Ali Minai, and Marios M. Polycarpou, "Balancing search and target response in cooperative unmanned aerial vehicle (UAV) teams." Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on 36, no. 3: 571-587, (2005).
Kim, Yoonsoo, Da-Wei Gu, and Ian Postlethwaite, "Real-time path planning with limited information for autonomous unmanned air vehicles." Automatica 44, no. 3: 696-712, (2008).
Shetty, Vijay K., Moises Sudit, and Rakesh Nagi, "Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles." Computers & Operations Research 35, no. 6: 1813- 1828, (2008).
Duan, Hai-bin, Xiang-yin Zhang, Jiang Wu, and Guan-jun Ma., "Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments." Journal of Bionic Engineering 6, no. 2: 161-173, (2009).
Murray, Chase C., and Mark H. Karwan, "An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations." Naval Research Logistics 57, no. 7: 634-652, (2010).
Mufalli, Frank, Rajan Batta, and Rakesh Nagi, "Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans." Computers & Operations Research 39, no. 11: 2787-2799, (2012).
Royset, Johannes O., W. Matthew Carlyle, and R. Kevin Wood, "Routing military aircraft with a constrained shortest-path algorithm." Military Operations Research 14, no. 3: 31-52, (2009).
Turban, Efraim, J. Aronson, and Ting-Peng Liang, Decision Support Systems and Intelligent Systems. 7th ed. Pearson Prentice Hall, (2005).
Zucker, Matt, James Kuffner, and Michael Branicky, "Multipartite RRTs for rapid replanning in dynamic environments." Robotics and Automation, IEEE International Conference: 1603-1609. IEEE, (2007).
Yang, Kwangjin, and Salah Sukkarieh, "3D smooth path planning for a UAV in cluttered natural environments." In Intelligent Robots and Systems. IROS. IEEE/RSJ International Conference: 794-800. IEEE, (2008).
Ahuja, Ravindra K., James B. Orlin, and Dushyant Sharma, "Very large‐scale neighborhood search." International Transactions in Operational Research 7, no. 4‐5: 301-317, (2000).
Chu, Chao-Hsien, and Jack C. Hayya, "A fuzzy clustering approach to manufacturing cell formation." The International Journal of Production Research 29, no. 7: 1475-1487, (1991).
Frazzoli, Emilio, Munther Dahleh, and Eric Feron, Real-time motion planning for agile autonomous vehicles. In American Control Conference. IEEE Proceedings, vol. 1: 43-49, (2001).
Beard, Randal W., Timothy W. McLain, Michael Goodrich, and Erik P. Anderson, "Coordinated target assignment and intercept for unmanned air vehicles." Robotics and Automation, IEEE Transactions on 18, no. 6: 911-922, (2002).
Duan, Haibin, Yaxiang Yu, Xiangyin Zhang, and Shan Shao, "Three-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm." Simulation Modelling Practice and Theory 18, no. 8: 1104-1115, (2010).
Kwak, D. J., Moon, S., Kim, S., & Kim, H. J., "Optimization of decentralized task assignment for heterogeneous UAVs." IFAC Proceedings Volumes, 46(11), 251-256, (2013).
Gencer, Cevriye, Emel Kızılkaya Aydoğan, and Sercan Kocabaş, "İnsansız Hava Araçlarının Rota Planlaması İçin Bir Karar Destek Sistemi." Savunma Bilimleri Dergisi 8, no.1, (2009).
Lenstra, J. K., Local search in combinatorial optimization. Princeton University Press., (2003).