IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v65y2017i3p674-692.html
   My bibliography  Save this article

Controlling a Fleet of Unmanned Aerial Vehicles to Collect Uncertain Information in a Threat Environment

Author

Listed:
  • Yan Xia

    (Department of Industrial and Systems Engineering, University at Buffalo (SUNY), Buffalo, New York 14260)

  • Rajan Batta

    (Department of Industrial and Systems Engineering, University at Buffalo (SUNY), Buffalo, New York 14260)

  • Rakesh Nagi

    (Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801)

Abstract

Unmanned aerial vehicles (UAVs) have been proved to be successful and efficient for information collection in a modern battlefield, especially in areas that are considered to be dangerous for human pilots. Currently, a UAV is remotely controlled by a ground station through frequent data communications, which make the current system vulnerable in a threat environment. We propose a decentralized control strategy while requiring UAVs to maintain radio silence during the entire mission. The strategy is analyzed based on a scenario where a fleet of vehicles is assigned to search and collect uncertain information in a set of regions within a given mission time. We demonstrate that a region-sharing strategy is beneficial even when there is no extra reward gained from additional information collection. Implementing a region-sharing strategy requires solving a decentralized time allocation problem, which is computationally intractable. To overcome this, an approximate formulation is developed under an independence assumption for information collected by different vehicles. This approximate formulation allows us to decompose, by vehicle, the time allocation problem, and obtain an easily implementable policy that takes on a Markovian form. We develop a sufficient condition under which the approximate formulation becomes exact. A numerical study establishes the computational efficiency of the method; only a few CPU seconds are needed for problems with a planning horizon of 300 time units and 40 regions. We further present a case study to illustrate region-sharing behaviors among UAVs while using practical parameter values. Finally, we compare the obtained policy with the optimal policy found using a complete enumeration method for small instances. Under different parameter settings, the average optimality gap ranges from 0.23% to 19.90%.

Suggested Citation

  • Yan Xia & Rajan Batta & Rakesh Nagi, 2017. "Controlling a Fleet of Unmanned Aerial Vehicles to Collect Uncertain Information in a Threat Environment," Operations Research, INFORMS, vol. 65(3), pages 674-692, June.
  • Handle: RePEc:inm:oropre:v:65:y:2017:i:3:p:674-692
    DOI: 10.1287/opre.2017.1590
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2017.1590
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.2017.1590?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Keith P. Tognetti, 1968. "Letter to the Editor—An Optimal Strategy for a Whereabouts Search," Operations Research, INFORMS, vol. 16(1), pages 209-211, February.
    2. Daniel S. Bernstein & Robert Givan & Neil Immerman & Shlomo Zilberstein, 2002. "The Complexity of Decentralized Control of Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 819-840, November.
    3. Chao, I-Ming & Golden, Bruce L. & Wasil, Edward A., 1996. "The team orienteering problem," European Journal of Operational Research, Elsevier, vol. 88(3), pages 464-474, February.
    4. Jesse Pietz & Johannes O. Royset, 2013. "Generalized orienteering problem with resource dependent rewards," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(4), pages 294-312, June.
    5. Joseph B. Kadane, 1971. "Optimal Whereabouts Search," Operations Research, INFORMS, vol. 19(4), pages 894-904, August.
    6. Chase C. Murray & Mark H. Karwan, 2010. "An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(7), pages 634-652, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhang, Guowei & Zhu, Ning & Ma, Shoufeng & Xia, Jun, 2021. "Humanitarian relief network assessment using collaborative truck-and-drone system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    2. Shen, Lixin & Wang, Yaodong & Liu, Kunpeng & Yang, Zaili & Shi, Xiaowen & Yang, Xu & Jing, Ke, 2020. "Synergistic path planning of multi-UAVs for air pollution detection of ships in ports," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    3. Xia, Jun & Wang, Kai & Wang, Shuaian, 2019. "Drone scheduling to monitor vessels in emission control areas," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 174-196.
    4. Zhang, Guowei & Jia, Ning & Zhu, Ning & Adulyasak, Yossiri & Ma, Shoufeng, 2023. "Robust drone selective routing in humanitarian transportation network assessment," European Journal of Operational Research, Elsevier, vol. 305(1), pages 400-428.
    5. Chiang, Wen-Chyuan & Li, Yuyu & Shang, Jennifer & Urban, Timothy L., 2019. "Impact of drone delivery on sustainability and cost: Realizing the UAV potential through vehicle routing optimization," Applied Energy, Elsevier, vol. 242(C), pages 1164-1175.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yu, Qinxiao & Fang, Kan & Zhu, Ning & Ma, Shoufeng, 2019. "A matheuristic approach to the orienteering problem with service time dependent profits," European Journal of Operational Research, Elsevier, vol. 273(2), pages 488-503.
    2. Joseph B. Kadane, 2015. "Optimal discrete search with technological choice," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 81(3), pages 317-336, June.
    3. Qinxiao Yu & Yossiri Adulyasak & Louis-Martin Rousseau & Ning Zhu & Shoufeng Ma, 2022. "Team Orienteering with Time-Varying Profit," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 262-280, January.
    4. Kim, Hyunjoon & Kim, Byung-In, 2022. "Hybrid dynamic programming with bounding algorithm for the multi-profit orienteering problem," European Journal of Operational Research, Elsevier, vol. 303(2), pages 550-566.
    5. Jumbo, Olga & Moghaddass, Ramin, 2022. "Resource optimization and image processing for vegetation management programs in power distribution networks," Applied Energy, Elsevier, vol. 319(C).
    6. Morteza Keshtkaran & Koorush Ziarati & Andrea Bettinelli & Daniele Vigo, 2016. "Enhanced exact solution methods for the Team Orienteering Problem," International Journal of Production Research, Taylor & Francis Journals, vol. 54(2), pages 591-601, January.
    7. Yanling Chang & Alan Erera & Chelsea White, 2015. "Value of information for a leader–follower partially observed Markov game," Annals of Operations Research, Springer, vol. 235(1), pages 129-153, December.
    8. Li, Yuan & Chen, Haoxun & Prins, Christian, 2016. "Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests," European Journal of Operational Research, Elsevier, vol. 252(1), pages 27-38.
    9. Kadri Sylejmani & Jürgen Dorn & Nysret Musliu, 2017. "Planning the trip itinerary for tourist groups," Information Technology & Tourism, Springer, vol. 17(3), pages 275-314, September.
    10. Racha El-Hajj & Rym Nesrine Guibadj & Aziz Moukrim & Mehdi Serairi, 2020. "A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit," Annals of Operations Research, Springer, vol. 291(1), pages 281-316, August.
    11. Kadri Sylejmani & Jürgen Dorn & Nysret Musliu, 0. "Planning the trip itinerary for tourist groups," Information Technology & Tourism, Springer, vol. 0, pages 1-40.
    12. Yu, Bin & Shan, Wenxuan & Sheu, Jiuh-Biing & Diabat, Ali, 2022. "Branch-and-price for a combined order selection and distribution problem in online community group-buying of perishable products," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 341-373.
    13. Wolfgang Wörndl & Alexander Hefele & Daniel Herzog, 2017. "Recommending a sequence of interesting places for tourist trips," Information Technology & Tourism, Springer, vol. 17(1), pages 31-54, March.
    14. Ahn, Jaemyung & de Weck, Olivier & Geng, Yue & Klabjan, Diego, 2012. "Column generation based heuristics for a generalized location routing problem with profits arising in space exploration," European Journal of Operational Research, Elsevier, vol. 223(1), pages 47-59.
    15. Majsa Ammouriova & Massimo Bertolini & Juliana Castaneda & Angel A. Juan & Mattia Neroni, 2022. "A Heuristic-Based Simulation for an Education Process to Learn about Optimization Applications in Logistics and Transportation," Mathematics, MDPI, vol. 10(5), pages 1-18, March.
    16. Zhang, Guowei & Zhu, Ning & Ma, Shoufeng & Xia, Jun, 2021. "Humanitarian relief network assessment using collaborative truck-and-drone system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    17. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    18. Samita Kedkaew & Warisa Nakkiew & Parida Jewpanya & Wasawat Nakkiew, 2024. "A Novel Tourist Trip Design Problem with Stochastic Travel Times and Partial Charging for Battery Electric Vehicles," Mathematics, MDPI, vol. 12(18), pages 1-19, September.
    19. Joseph Kadane, 2015. "Optimal discrete search with technological choice," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 81(3), pages 317-336, June.
    20. Larco Martinelli, J.A. & Dekker, R. & Kaymak, U., 2007. "Distributed Services with Foreseen and Unforeseen Tasks: The Mobile Re-allocation Problem," ERIM Report Series Research in Management ERS-2007-087-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:65:y:2017:i:3:p:674-692. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.