Abstract
This work focuses on low-energy collision avoidance and formation maintenance in autonomous swarms of drones. Here, the two main problems are: 1) how to avoid collisions by temporarily breaking the formation, i.e., collision avoidance reformation, and 2) how do such reformation while minimizing the deviation resulting in minimization of the overall time and energy consumption of the drones. To address the first question, we use cellular automata based technique to find an efficient formation that avoids the obstacle while minimizing the time and energy. Concerning the second question, a near-optimal reformation of the swarm after successful collision avoidance is achieved by applying a temperature function reduction technique, originally used in the point set registration process. The goal of the reformation process is to remove the disturbance while minimizing the overall time it takes for the swarm to reach the destination and consequently reducing the energy consumption required by this operation. To measure the degree of formation disturbance due to collision avoidance, deviation of the centroid of the swarm formation is used, inspired by the concept of the center of mass in classical mechanics. Experimental results show the efficiency of the proposed technique, in terms of performance and energy.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Even though the highest formation disturbance state might not totally guarantee not to have collision in TPS-based reformation phase, we take this assumption to simplify finding the moment of switching from GA-based collision avoidance phase to TPS-based resuming the original formation.
References
Wolfram, S.: A New Kind of Science — Online–Table of Contents. Library Catalog. www.wolframscience.com
Alander, J.T.: On finding the optimal genetic algorithms for robot control problems. In: Proceedings IROS 1991: IEEE/RSJ International Workshop on Intelligent Robots and Systems 1991, vol. 3, pp. 1313–1318, November 1991
Balch, T., Arkin, R.C.: Behavior-based formation control for multirobot teams. IEEE Trans. Robot. Autom. 14(6), 926–939 (1998)
Bansal, J.C., Singh, P.K., Pal, N.R.: Evolutionary and Swarm Intelligence Algorithms. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-91341-4
Campion, M., Ranganathan, P., Faruque, S.: A review and future directions of UAV swarm communication architectures. In: 2018 IEEE International Conference on Electro/Information Technology (EIT), pp. 0903–0908, May 2018
Dong, L., Chen, Y., Qu, X.: Formation control strategy for nonholonomic intelligent vehicles based on virtual structure and consensus approach. Proc. Eng. 137, 415–424 (2016). Green Intelligent Transportation System and Safety
Dorigo, M., Roosevelt, A.F.D.: Swarm robotics. In: Special Issue, Autonomous Robots. Citeseer (2004)
Gad, A.: Introduction to Optimization with Genetic Algorithm, July 2018
Guo, P., Hu, W., Ren, H., Zhang, Y.: PCAOT: a Manhattan point cloud registration method towards large rotation and small overlap. In: 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 7912–7917, October 2018
Chui, H., Rangarajan, A.: A new algorithm for non-rigid point matching. In: Proceedings IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2000 (Cat. No. PR00662), vol. 2, pp. 44–51, June 2000
Hamann, H.: Introduction to Swarm Robotics, pp. 1–32. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-74528-2_1
Han, Q., Li, T., Sun, S., Villarrubia, G., de la Prieta, F.: “1-n” leader-follower formation control of multiple agents based on bearing-only observation. In: Demazeau, Y., Decker, K.S., Bajo Pérez, J., de la Prieta, F. (eds.) Advances in Practical Applications of Agents, Multi-Agent Systems, and Sustainability: The PAAMS Collection, pp. 120–130. Springer, Cham (2015)
He, L., Bai, P., Liang, X., Zhang, J., Wang, W.: Feedback formation control of UAV swarm with multiple implicit leaders. Aerosp. Sci. Technol. 72, 327–334 (2018)
Lawton, J.R.T., Beard, R.W., Young, B.J.: A decentralized approach to formation maneuvers. IEEE Trans. Robot. Autom. 19(6), 933–941 (2003)
Li, N.H.M., Liu, H.H.T.: Formation UAV flight control using virtual structure and motion synchronization. In: 2008 American Control Conference, pp. 1782–1787, June 2008
Myronenko, A., Song, X.B.: Point-set registration: coherent point drift. CoRR, abs/0905.2635 (2009)
Kwang-Kyo, O., Park, M.-C., Ahn, H.-S.: A survey of multi-agent formation control. Automatica 53, 424–440 (2015)
Vicencio, K., Davis, B., Gentilini, I.: Multi-goal path planning based on the generalized traveling salesman problem with neighborhoods. In: 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2985–2990, September 2014
Yasin, J.N., et al.: Night vision obstacle detection and avoidance based on bio-inspired vision sensors. In: 2020 IEEE Sensors, pp. 1–4 (2020)
Yasin, J.N., Mohamed, S.A.S., Haghbayan, M., Heikkonen, J., Tenhunen, H., Plosila, J.: Unmanned aerial vehicles (UAVs): collision avoidance systems and approaches. IEEE Access 8, 105139–105155 (2020)
Yasin, J.N., et al.: Energy-efficient formation morphing for collision avoidance in a swarm of drones. IEEE Access 8, 170681–170695 (2020)
Yasin, J.N., Mohamed, S.A.S., Haghbayan, M.-H., Heikkonen, J., Tenhunen, H., Plosila, J.: Navigation of autonomous swarm of drones using translational coordinates. In: Demazeau, Y., Holvoet, T., Corchado, J.M., Costantini, S. (eds.) Advances in Practical Applications of Agents, Multi-Agent Systems, and Trustworthiness. The PAAMS Collection, pp. 353–362. Springer, Cham (2020)
Yasin, J.N., et al.: Dynamic formation reshaping based on point set registration in a swarm of drones (2020)
Yasin, J.N., Haghbayan, M.-H., Heikkonen, J., Tenhunen, H., Plosila, J.: Formation maintenance and collision avoidance in a swarm of drones. In: Proceedings of the 2019 3rd International Symposium on Computer Science and Intelligent Control, ISCSIC 2019. Association for Computing Machinery, New York (2019)
Zhuge, C., Cai, Y., Tang, Z.: A novel dynamic obstacle avoidance algorithm based on collision time histogram. Chin. J. Electron. 26(3), 522–529 (2017)
Acknowledgment
This work has been supported in part by the Academy of Finland-funded research project 314048 and Nokia Foundation (Award No. 20200147).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Yasin, J.N., Mahboob, H., Haghbayan, MH., Yasin, M.M., Plosila, J. (2022). Cellular Formation Maintenance and Collision Avoidance Using Centroid-Based Point Set Registration in a Swarm of Drones. In: Arai, K. (eds) Intelligent Systems and Applications. IntelliSys 2021. Lecture Notes in Networks and Systems, vol 294. Springer, Cham. https://doi.org/10.1007/978-3-030-82193-7_26
Download citation
DOI: https://doi.org/10.1007/978-3-030-82193-7_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-82192-0
Online ISBN: 978-3-030-82193-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)