[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Flocks formation model for self-interested UAVs

  • Original Research Paper
  • Published:
Intelligent Service Robotics Aims and scope Submit manuscript

Abstract

In recent years, unmanned aerial vehicles (UAVs) have been used in a wide range of domains. As the number of UAV flights increases, central flight areas may become overcrowded. This may cause delays in UAV traffic or gridlock on UAV routes. To address this challenge, we propose a flocking protocol that enables individual UAVs to optimize their flight preferences, while receiving the benefits of traveling in a group. Flocking can reduce overcrowding, and as a result, UAVs will be able to travel on less congested routes and have fewer encounters with other UAVs, thus reducing flight time and conserving energy. The protocol allows each UAV to create a flock or join an existing flock for all or part of its journey. We perform a simulation of UAV flights in an urban area and compare the average flight time of the UAVs based on various flight situations (e.g., different routes and participation in groups of UAVs). The simulation results demonstrate that the use of the flocking protocol significantly reduced the average flight time, and the flight saving rate increased with an increase in the UAV mean number. A similar effect is also observed in situations where each UAV and flock formed a dynamic A*-based path in advance to avoid collisions.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. Another possibility may be the union of two flocks listed on the blackboard, which may decide to move together on a particular route. In this case, the estimated departure time, estimated arrival time, and common route will be decided together by the flock managers and agreed upon by all the participating flocks. However, the detailed union protocol is beyond the scope of the current study .

  2. https://data.cityofchicago.org.

References

  1. Valavanis KP, Vachtsevanos GJ (eds) (2015) Handbook of unmanned aerial vehicles. Springer, Berlin

    Google Scholar 

  2. Yang L, Qi J, Song D, Xiao J, Han J, Xia Y (2016) Survey of robot 3D path planning algorithms. J Control Sci Eng 2016:1–22

    MathSciNet  MATH  Google Scholar 

  3. Wang X, Yadav V, Balakrishnan SN (2007) Cooperative UAV formation flying with obstacle/collision avoidance. IEEE Trans Control Syst Technol 15(4):672–679

    Article  Google Scholar 

  4. McInnes CR (2003) Velocity field path-planning for single and multiple unmanned aerial vehicles. Aeronaut J 107(1073):419–426

    Article  Google Scholar 

  5. Bemporad A, Rocchi C (2011) decentralized linear time-varying model predictive control of a formation of unmanned aerial vehicles. In: 50th IEEE conference on decision and control and european control conference

  6. Sundar K, Rathinam S (2016) Algorithms for heterogeneous, multiple depot, multiple unmanned vehicle path planning problems. Journal of Intelligent Robot Systemswith a special section on Unmanned Systems, J Intell Robot Syst

  7. Yadav V, Wang X, Balakrishnan SN (2006) Neural network approach for obstacle avoidance in 3-d environments for UAVs. In: Proceedings of the (2006) American control conference. Minneapolis, Minnesota, USA

  8. Owen M, Beard RW, McLain TW (2015) Implementing Dubins airplane paths on fixed-wing UAVs. In: Valavanis K, Vachtsevanos G (eds) Handbook of unmanned aerial vehicles. Springer, Berlin

    Google Scholar 

  9. Chen Y, Yu J, Su X, Luo G (2015) Path planning for multi-UAV formation. J Intell Robot Syst 77:229–246

    Article  Google Scholar 

  10. Edwards DB, Bean TA., Odell DL, Anderson MJ (2004) A leader–follower algorithm for multiple AUV formations. In: IEEE/OES autonomous underwater vehicles

  11. Gao XZ, Hou ZX, Zhu XF, Zhang JT, Chen XQ (2013) The shortest path planning for manoeuvres of UAV. Acta Polytech Hung 10(1):221–239

    Google Scholar 

  12. Ingersoll B, Ingersoll K, DeFranco P, Ning A (2016) UAV path-planning using bezier curves and a receding horizon approach. In: AIAA modeling and simulation technologies conference

  13. Qie H, Shi D, Shen T, Xu X, Li Y, Wang L (2019) Joint optimization of multi-UAV target assignment and path planning based on multi-agent reinforcement learning. In: IEEE access 7

  14. Wu Z, Li J, Zuo J, Li S (2018) Path planning of UAVs based on collision probability and Kalman filter. IEEE Access 6:34237–34245

    Article  Google Scholar 

  15. Daifeng Z, Haibin D (2018) Social-class pigeon-inspired optimization and time stamp segmentation for multi-UAV cooperative path planning. Neurocomputing 313:229–246

    Article  Google Scholar 

  16. Cekmez U, Ozsiginan M, Sahingoz OK (2018) Multi-UAV path planning with multi colony ant optimization. In: Abraham A, Muhuri P, Muda A, Gandhi N (eds) Intelligent systems design and applications. ISDA 2017. Advances in intelligent systems and computing, vol 736. Springer

  17. Hosak DG (2010) Optimal geometrical path in 3D with curvature constraint. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (IROS), pp 113–118, Taipei

  18. Seo J, Kim Y, Kim S, Tsourdos A (2017) Collision avoidance strategies for unmanned aerial vehicles in formation flight. IEEE Trans Aerosp Electron Syst 53(6):2718–2734

    Article  Google Scholar 

  19. Azoulay R, Reches S (2019) UAV flocks forming for crowded flight environments. In: ICAART

  20. Hart P, Nilsson N, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4:100–107

    Article  Google Scholar 

  21. Zeng W, Church RL (2009) Finding shortest paths on real road networks: the case for A*. Int J Geogr Inf Sci 23(4):531–543

    Article  Google Scholar 

  22. Le AV, Prabakaran V, Sivanantham V, Mohan RE (2018) Modified a-star algorithm for efficient coverage path planning in tetris inspired self-reconfigurable robot with integrated laser sensor. Sensors 18:2585

    Article  Google Scholar 

  23. Singh Y, Sharma S, Sutton R, Hatton D, Khan A (2018) A constrained A* approach towards optimal path planning for an unmanned surface vehicle in a maritime environment containing dynamic obstacles and ocean currents. Ocean Eng 169:187–201

    Article  Google Scholar 

  24. Canny J, Reif J (1987) New lower bound techniques for robot motion planning problems. In: Proceedings of the symposium on the foundations of computer science

  25. Mitchell JSB, Sharir M (2004) New results on shortest paths in three dimensions. In: Proceedings of the ACM twentieth annual symposium on computational geometry, Brooklyn, New York, USA, pp 124–133

  26. Garcia M, Viguria A, Ollero A (2012) Dynamic graph-search algorithm for global path planning in presence of hazardous. J Int Robot Syst 69:285–295

    Google Scholar 

  27. Zhong L, Xiao-Guang G, Xiao-Wei F (2015) Coalition formation for multiple heterogeneous UAVs in unknown environment. In: Fifth international conference on instrumentation and measurement, computer, communication and control (IMCCC), Qinhuangdao, pp 1222–1227

  28. Kuriki Y, Namerikawa T (2015) formation control with collision avoidance for a multi-UAV system using decentralized MPC and consensus-based control. SICE J Control Meas Syst Integr 8(4):285–294

    Article  Google Scholar 

  29. Park S, Kim K, Kim H (2018) Formation control algorithm of multi-UAV-based network infrastructure. Appl Sci 8:1740

    Article  Google Scholar 

  30. Kuriki Y, Namerikawa T (2014) Consensus-based cooperative formation control with collision avoidance for a multi-UAV system. In: American control conference, pp 2077–2082

  31. Danilechenko K (2016) Distributed cluster formation and management for maritime network. M.Sc. thesis, Beer Sheva University

  32. McCord C, Queralta JP, Gia TN, Westerlund T (2019) distributed progressive formation control for multi-agent systems: 2D and 3D deployment of UAVs in ROS/Gazebo with RotorS. In: European conference on mobile robots (ECMR), Prague, Czech Republic, pp 1–6

  33. Li X, Zhu D, Qian Y (2014) A survey on formation control algorithms for multi-AUV system. Special issue on autonomous underwater robots. Unmanned Syst 2(4):351–359

    Article  Google Scholar 

  34. Mercado, DA, Castro1 R, Lozano R (2013) Quadrotors flight formation control using a leader–follower approach. In: European control conference (ECC)

  35. Ullaha Z (2020) A survey on hybrid, energy efficient and distributed (HEED) based energy efficient clustering protocols for wireless sensor networks. Wirel Pers Commun 112:2685–2713

    Article  Google Scholar 

  36. Younis O, Fahmy S (2004) HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Trans Mob Comput 3(4):366–379. https://doi.org/10.1109/TMC.2004.41

    Article  Google Scholar 

  37. Beaver LE, Malikopoulos AA (2020) An overview on optimal flocking. arXiv:2009.14279

  38. Kraus S, Shehory O, Taase G (2004) The advantages of compromising in coalition formation with incomplete information. In: AAMAS

  39. Shehory O, Kraus S, Yadgar O (1999) Emergent cooperative goal-satisfaction in large-scale automated-agent systems. Artif Intell 110(1):1–55

    Article  MATH  Google Scholar 

  40. Sklab Y, Aknine S, Shehory O, Tari A (2020) Coalition formation with dynamically changing externalities. Eng Appl Artif Intell 91:103577

    Article  Google Scholar 

  41. Ismail A, Bagula BA, Tuyishimire E (2018) Internet-of-Things in motion: a UAV coalition model for remote sensing in smart cities. Sensors 18(7):2184

    Article  Google Scholar 

  42. Fu X, Zhang J, Zhang L et al (2019) Coalition formation among unmanned aerial vehicles for uncertain task allocation. Wireless Netw 25:367–377

    Article  Google Scholar 

  43. Sujit PB, George JM, Beard RW (2008) Multiple UAV coalition formation. In: 2008 American control conference. Seattle, WA, pp 2010–2015

  44. Bardhan R, Ghose D (2013) Resource allocation and coalition formation for UAVs: a cooperative game approach. In: IEEE international conference on control applications (CCA), Hyderabad, pp 1200–1205

  45. George JM, Pinto J, Sujit PB, Sousa JB (2010) Multiple UAV coalition formation strategies. In: AAMAS

  46. Chen J, Li LR (2005) Path planning protocol for collaborative multi-robot systems. In: Proceedings IEEE international symposium on computational intelligence in robotics and automation

  47. Sinay M, Agmon N, Maksimov O, Levy G, Bitan M, Kraus S (2018) UAV/UGV search and capture of goal-oriented uncertain targets. In: IEEE/RSJ international conference on intelligent robots and systems (IROS), pp 8505–8512

  48. Yang Y, Polycarpou MM, Minai AA (2007) Multi-UAV cooperative search using an opportunistic learning method. J Dyn Syst Meas Control 129(5):716–728

    Article  Google Scholar 

  49. Passino K, Polycarpou M, Jacques D, Pachter M, Liu Y, Yang Y, Flint M, Baum M (2002) Cooperative control for autonomous air vehicles. In: Murphey R, Pardalos PM (eds) Cooperative control and optimization. Applied optimization, vol 66. Springer, Berlin

    Google Scholar 

  50. Bayındır L (2016) A review of swarm robotics tasks. Neurocomputing 172:292–321

    Article  Google Scholar 

  51. Brutschy A, Pini G, Pinciroli C, Birattari M, Dorigo M (2014) Self-organized task allocation to sequentially interdependent tasks in swarm robotics. Auton Agents Multi-Agent Syst 28(1):101–125

    Article  Google Scholar 

  52. Cianci CM, Raemy X, Pugh J, Martinoli A (2007) Communication in a swarm of miniature robots: the e-puck as an educational tool for swarm robotics. In: Sahin E, Spears WM, Winfield AFT (eds) Swarm robotics. SR (2006) Lecture notes in computer science, vol 4433. Springer, Berlin

  53. Sahin E, Winfield A (2008) Special issue on swarm robotics. Swarm Intell 2:69–72

    Article  Google Scholar 

  54. Douchan Y, Kaminka GA (2019) Swarms can be rational. In: Proceedings of the 18th international conference on autonomous agents and multiagent systems (AAMAS 2019)

  55. Altmann A, Niendorf M, Bednar M, Reichel R (2014) Improved 3D interpolation-based path planning for a fixed-wing unmanned aircraft. J Intell Robot Syst 76:185–197

    Article  Google Scholar 

  56. Duan H, Li P (2012) Path planning of unmanned aerial vehicle based on improved gravitational search algorithm. Sci China Technol Sci 55(10):2712–2719

    Article  Google Scholar 

  57. Roberge V, Tarbouchi M, Labonte G (2013) Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning. IEEE Trans Ind Inform 9(1):132–141

    Article  Google Scholar 

  58. Duan H, Li P (2014) Bio-inspired computation in unmanned aerial vehicles. Springer, Berlin, pp 99–142

    Book  Google Scholar 

  59. Gebhardt C (2016) Efficient transport system scheduling based on maximum flow algorithms. M.Sc. thesis, Institut für Informatik Lehrstuhl für Programmierung und Softwaretechnik, Ludwig-Maximilians-Universitat, Muenchen

  60. Brown A, Rogers J (2016) A sampling-based probabilistic path planner for multirotor air vehicles in cluttered environments. Proc Inst Mech Eng Part G J Aerosp Eng 231(1):143–162

    Article  Google Scholar 

  61. Temizer S, Kochenderfer M, Kaelbling L, Lozano-Perez T, Kuchar J (2010) Collision avoidance for unmanned aircraft using Markov decision processes. In: AIAA guidance, navigation, and control conference, guidance, navigation, and control and co-located conferences

  62. Ragi S, Chong EKP (2013) UAV path planning in a dynamic environment via partially observable Markov decision process. IEEE Trans Aerosp Electron Syst 49(4):2397–2412

    Article  Google Scholar 

  63. Vikranth Dabbiru R, Siddhabathula K (2016) Autonomous air traffic control–collision avoidance for UAVs using MDP. Int J Comput Sci Inf Technol Secur 6(1):447–454

    Google Scholar 

  64. Nash, A, Daniel, K, Koenig, S, Felner, A (2007) Theta*: any-angle path planning on grids. In: Proceedings of the AAAI conference on artificial intelligence

  65. Nash A, Koenig S, Tovey, C (2010) Lazy theta*: any-angle path planning and path length analysis in 3D. In: Proceedings of the twenty-fourth AAAI conference on artificial intelligence (AAAI’10), pp 147–154

  66. Ferrera E, Alcántara H, Capitán J, Castaño AR, Marrón PJ, Aníbal Ollero A (2018) Decentralized 3D collision avoidance for multiple UAVs in outdoor environments. Sensors (Basel) 18(12):4101

    Article  Google Scholar 

  67. Stiene S, Hertzberg J (2009) Virtual range scan for avoiding 3D obstacles using 2D tools. In: International conference on advanced robotics, Munich, 2009, pp 1–6

  68. Cakir M (2015) 2D path planning of UAVs with genetic algorithm in a constrained environment, In: 6th international conference on modeling, simulation, and applied optimization (ICMSAO), Istanbul, 2015, pp 1–5

  69. Rana T, Shankar A, Sultan MK, Patan R, Balusamy B (2019) An intelligent approach for UAV and drone privacy security using blockchain methodology. In: 9th international conference on cloud computing, data science and engineering (confluence), Noida, India, 2019, pp 162–167

  70. Chen CL, Deng YY, Weng W, Chen CH, Chiu YJ, Wu CM (2020) A traceable and privacy-preserving authentication for UAV communication control system. Electronics 9(1):62

    Article  Google Scholar 

  71. Lagkas T, Argyriou V, Bibi S, Sarigiannidis P (2018) UAV IoT framework views and challenges: towards protecting drones as “things”. Sensors 18(11):4015

    Article  Google Scholar 

  72. Arafat MY, Moh S (2018) A survey on cluster-based routing protocols for unmanned aerial vehicle networks. IEEE Access 7:498–516

    Article  Google Scholar 

  73. Wang G, Lee B-S, Ahn JY, Cho G (2018) A UAV-aided cluster head election framework and applying such to security-driven cluster head election schemes: a survey. Secur Commun Netw 2018:6475927. https://doi.org/10.1155/2018/6475927

  74. Ahmad M, Hameed A, Ikram AA, Wahid I (2019) State-of-the-art clustering schemes in mobile ad hoc networks: objectives, challenges, and future directions. IEEE Access 7:17067–17081

    Article  Google Scholar 

  75. Koushik AM, Hu F, Kumar S (2019) Deep Q-learning-based node positioning for throughput-optimal communications in dynamic UAV swarm network. IEEE Trans Cognit Commun Netw 5(3):554–566

    Article  Google Scholar 

  76. Klaine PV, Nadas JPB, Souza RD et al (2018) Distributed drone base station positioning for emergency cellular networks using reinforcement learning. Cognit Comput 10:790–804

    Article  Google Scholar 

  77. Medeiros FLL, da Silva JDS (2010) A Dijkstra algorithm for fixed-wing UAV motion planning based on terrain elevation. In: Advances in artificial intelligence—SBIA 2010. Springer, Berlin, pp 213–222

  78. Tseng FH, Liang TT, Lee CH, Der Chou L, Chao HC (2014) A star search algorithm for civil UAV path planning with 3G communication. In: Tenth international conference on intelligent information hiding and multimedia signal processing

  79. Liao T (2012) UAV collision avoidance using A* algorithm. M.Sc. thesis, Auburn, Alabama

Download references

Acknowledgements

We thank the anonymous reviewers for their helpful remarks, which have enabled us to significantly improve the quality of this paper.

Author information

Authors and Affiliations

  1. Jerusalem College of Technology, Jerusalem, Israel

    Rina Azoulay & Shulamit Reches

Authors
  1. Rina Azoulay
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shulamit Reches
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rina Azoulay.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Azoulay, R., Reches, S. Flocks formation model for self-interested UAVs. Intel Serv Robotics 14, 157–174 (2021). https://doi.org/10.1007/s11370-021-00354-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11370-021-00354-x

Keywords

Search

Navigation