Skip to main content
SpringerLink
Log in

Cooperative Mission and Path Planning for a Team of UAVs

  • Reference work entry
  • First Online:
Handbook of Unmanned Aerial Vehicles

Abstract

This chapter addresses the cooperative mission and path-planning problem of multiple UAVs in the context of the vehicle-routing problem. Since the conventional vehicle-routing algorithms approximate their path to straight lines to reduce computational load, the physical constraints imposed on the vehicle are not to be taken into account. In order to mitigate this issue, this chapter describes a framework allowing integrated mission and path planning for coordinating UAVs using the Dubins theory based on the differential geometry concepts which can consider non-straight path segments. The main advantage of this approach is that the number of design parameters can be significantly reduced while providing the shortest, safe, and feasible path, which leads to a fast design process and more lightweight algorithms. In order to validate the integrated framework, cooperative mission and path-planning algorithms for two missions are developed: (1) road-network search route-planning patrolling every road segment of interest efficiently based on the optimization and approximation algorithm using nearest insertion and auction negotiation and (2) communication-relay route planning between a ground control station and the friendly fleet satisfying the constraints on the UAV speed and the avoidance of nonflying zones. Lastly, the performance of the proposed algorithms is examined via numerical simulations.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 1,399.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
USD 1,999.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  • A. Ahmadzadeh, G. Buchman, P. Cheng, A. Jadbabaie, J. Keller, V. Kumar, G. Pappas, Cooperative control of UAVs for search and coverage, in Conference on Unmanned Systems (SPIE, Bellingham, 2006)

    Google Scholar 

  • D. Ahr, Contributions to multiple postmen problems. Ph.D. thesis, Heidelberg University, 2004

    Google Scholar 

  • B. Alspach, Searching and sweeping graphs: a brief survey. Matematiche (Catania) 59, 5–37 (2006)

    MathSciNet  Google Scholar 

  • T. Bektas, The multiple traveling salesman problem: an overview of formulations and solution procedures. Int. J. Manag. Sci. 34(3), 209–219 (2006)

    Google Scholar 

  • J. Bellingham, M. Tillerson, A. Richards, J. How, Multi-Task Allocation and Path Planning for Cooperating UAVs, Cooperative Control: Models, Applications and Algorithms (Kluwer, Dordrecht, 2003)

    Google Scholar 

  • C. Cerasoli, N.J. Eatontown, An analysis of unmanned airborne vehicle relay coverage in urban environments, in Proceedings of MILCOM (IEEE, Piscataway, 2007)

    Google Scholar 

  • P. Chandler, M. Pachter, D. Swaroop, J. Hewlett, S. Rasmussen, C. Schumacher, K. Nygard, Complexity in UAV cooperation control, in American Control Conference, Anchorage (American Control Conference, Evanston, 2002)

    Google Scholar 

  • L.E. Dubins, On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am. J. Math. 79(3), 497–516 (1957)

    Article  MATH  MathSciNet  Google Scholar 

  • K. Easton, J. Burdick, A coverage algorithm for multi-robot boundary inspection, in IEEE International Conference on Robotics and Automation (IEEE, Piscataway, 2005)

    Google Scholar 

  • A. Gibbons, Algorithmic Graph Theory (Cambridge University Press, Cambridge/New York, 1999)

    Google Scholar 

  • J. Gross, J. Yellen, Handbook of Graph Theory (CRC, Boca Raton, 2003)

    Book  Google Scholar 

  • M. Hifi, M. Michrafy, A. Sbihi, A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem. Comput. Optim. Appl. 33, 271–285 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  • S. Kim, P. Silson, A. Tsourdos, M. Shanmugavel, Dubins path planning of multiple unmanned airborne vehicles for communication relay. Proc. IMechE G 225, 12–25 (2011)

    Article  Google Scholar 

  • I. Maza, A. Ollero, Multiple UAV cooperative searching operation using polygon area decomposition and efficient coverage algorithms, in Distributed Autonomous Robotic Systems 6, vol. 5 (Springer, Tokyo/New York, 2007), pp. 221–230

    Chapter  Google Scholar 

  • N. Nigam, I. Kroo, Persistent surveillance using multiple unmanned air vehicles, in Aerospace Conference, 2008 IEEE, Big Sky (IEEE, Piscataway, 2008)

    Google Scholar 

  • H. Oh, S. Kim, A. Tsourdos, B. White, Cooperative road-network search planning of multiple UAVs using dubins paths, in AIAA Guidance, Navigation and Control Conference, Portland (AIAA, Reston, 2011a)

    Google Scholar 

  • H. Oh, H. Shin, A. Tsourdos, B. White, P. Silson, Coordinated road network search for multiple UAVs using dubins path, in 1st CEAS Specialist Conference on Guidance, Navigation and Control, Munich (Springer, Berlin/Heidelberg, 2011b)

    Google Scholar 

  • H. Oh, S. Kim, A. Tsourdos, B. White, Coordinated road-network search route planning by a team of UAVs. Int. J. Syst. Sci., (2012) In press

    Google Scholar 

  • T. Parsons, Pursuit-evasion in a graph, in Theory and Applications of Graphs (Springer, Berlin, 1976)

    Google Scholar 

  • N. Perrier, A. Langevin, J. Campbell, A survey of models and algorithms for winter road maintenance. Part IV: Vehicle Routing and Fleet Sizing for Plowing and Snow Disposal. Comput. Oper. Res. 34, 258–294 (2007)

    Article  MATH  Google Scholar 

  • M.F.J. Pinkney, D. Hampel, S. DiPierro, Unmanned aerial vehicle (uav) communications relay, in IEEE Military Communications Conference, 1996. MILCOM’96, Conference Proceedings (IEEE, Piscataway, 1996)

    Google Scholar 

  • D. Rosenkrantz, R. Stearns, P. Lewis, An analysis of several heuristics for the traveling salesman problem. Fundam. Probl. Comput. 1, 45–69 (2009)

    Article  Google Scholar 

  • J. Royset, H. Sato, Route optimization for multiple searchers. Nav. Res. Logist. 57, 701–717 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  • J. Ryan, T. Bailey, J. Moore, W. Carlton, Reactive tabu search in unmanned aerial reconnaissance simulations. in 30th Conference on Winter Simulation, Washington, DC, 1998

    Google Scholar 

  • T. Ralphs, L. Ladanyi, M. Guzelsoy, A. Mahajan, SYMPHONY 5.2.4 (2010), http://projects.coin-or.org/SYMPHONY

  • T. Samad, J. Bay, D. Godbole, Network-centric systems for military operations in urban terrain: the role of UAVs. Proc. IEEE 95(1), 92–107 (2007)

    Article  Google Scholar 

  • M. Shanmugavel, Path planning of multiple autonomous vehicles. Ph.D. thesis, Cranfield University, 2007

    Google Scholar 

  • M. Shanmugavel, A. Tsourdos, B.A. White, R. Zbikowski, Differential geometric path planning of multiple UAVs. J. Dyn. Syst. Meas. Control 129, 620–632 (2007)

    Article  Google Scholar 

  • A. Tsourdos, B. White, M. Shanmugavel, Cooperative Path Planning of Unmanned Aerial Vehicles (Wiley, Chichester, 2010)

    Book  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Engineering Physics, School of Engineering, Cranfield University, Cranfield, Bedfordshire, UK

    Hyondong Oh, Hyo-Sang Shin, Antonios Tsourdos & Brian A. White

  2. Department of Aerospace Engineering, Chungnam National University, Daejeon, South Korea

    Seungkeun Kim

Authors
  1. Hyondong Oh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hyo-Sang Shin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Seungkeun Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Antonios Tsourdos
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Brian A. White
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Hyo-Sang Shin , Seungkeun Kim , Antonios Tsourdos or Brian A. White .

Editor information

Editors and Affiliations

  1. Department of Electrical and Computer Engineering, University of Denver, Denver, Colorado, USA

    Kimon P. Valavanis

  2. School of Electrical and Computer Engineering, The Georgia Institute of Technology, Atlanta, Georgia, USA

    George J. Vachtsevanos

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer Science+Business Media Dordrecht

About this entry

Cite this entry

Oh, H., Shin, HS., Kim, S., Tsourdos, A., White, B.A. (2015). Cooperative Mission and Path Planning for a Team of UAVs. In: Valavanis, K., Vachtsevanos, G. (eds) Handbook of Unmanned Aerial Vehicles. Springer, Dordrecht. https://doi.org/10.1007/978-90-481-9707-1_14

Download citation

Publish with us

Policies and ethics

Search

Navigation