Improved Consensus-Based Bundle Algorithm for Multi-to-Multi UAV Interception

Siyuan Yang; Shaoming He; Tao Song; Jiang Wang

doi:10.1007/978-981-19-6613-2_439

Improved Consensus-Based Bundle Algorithm for Multi-to-Multi UAV Interception

Siyuan Yang^*, Shaoming He, Tao Song, Jiang Wang

^*Corresponding author for this work

School of Aerospace Engineering

Beijing Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

This paper purposes an algorithm to achieve task allocation of heterogeneous UAV swarm to multiple mission targets constrained by time windows. First, a complete mathematical model for task assignment problem of UAV swarm is established. Second, the process of Consensus-Based Bundle Algorithm (CBBA) is described, while performance and convergence speed of it is analysed. Additionally, based on this algorithm, for the time window constraints of heterogeneous UAV swarm and tasks, some improvement is added into CBBA, which validity is discussed. Finally, both single simulation and multiple Monte Carlo simulations of CBBA with time windows are conducted to verify the effectiveness and robustness of CBBA, and time complexity is speculated.

Original language	English
Title of host publication	Advances in Guidance, Navigation and Control - Proceedings of 2022 International Conference on Guidance, Navigation and Control
Editors	Liang Yan, Haibin Duan, Yimin Deng, Liang Yan
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	4522-4533
Number of pages	12
ISBN (Print)	9789811966125
DOIs	https://doi.org/10.1007/978-981-19-6613-2_439
Publication status	Published - 2023
Event	International Conference on Guidance, Navigation and Control, ICGNC 2022 - Harbin, China Duration: 5 Aug 2022 → 7 Aug 2022

Publication series

Name	Lecture Notes in Electrical Engineering
Volume	845 LNEE
ISSN (Print)	1876-1100
ISSN (Electronic)	1876-1119

Conference

Conference	International Conference on Guidance, Navigation and Control, ICGNC 2022
Country/Territory	China
City	Harbin
Period	5/08/22 → 7/08/22

Keywords

Consensus-based bundle algorithm
Heterogeneous UAV swarm
Task allocation
Time windows

Access to Document

10.1007/978-981-19-6613-2_439

Cite this

Yang, S., He, S., Song, T., & Wang, J. (2023). Improved Consensus-Based Bundle Algorithm for Multi-to-Multi UAV Interception. In L. Yan, H. Duan, Y. Deng, & L. Yan (Eds.), Advances in Guidance, Navigation and Control - Proceedings of 2022 International Conference on Guidance, Navigation and Control (pp. 4522-4533). (Lecture Notes in Electrical Engineering; Vol. 845 LNEE). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-981-19-6613-2_439

Yang, Siyuan ; He, Shaoming ; Song, Tao et al. / Improved Consensus-Based Bundle Algorithm for Multi-to-Multi UAV Interception. Advances in Guidance, Navigation and Control - Proceedings of 2022 International Conference on Guidance, Navigation and Control. editor / Liang Yan ; Haibin Duan ; Yimin Deng ; Liang Yan. Springer Science and Business Media Deutschland GmbH, 2023. pp. 4522-4533 (Lecture Notes in Electrical Engineering).

@inproceedings{92e3085ff02541fabdc40c4a24ffb768,

title = "Improved Consensus-Based Bundle Algorithm for Multi-to-Multi UAV Interception",

abstract = "This paper purposes an algorithm to achieve task allocation of heterogeneous UAV swarm to multiple mission targets constrained by time windows. First, a complete mathematical model for task assignment problem of UAV swarm is established. Second, the process of Consensus-Based Bundle Algorithm (CBBA) is described, while performance and convergence speed of it is analysed. Additionally, based on this algorithm, for the time window constraints of heterogeneous UAV swarm and tasks, some improvement is added into CBBA, which validity is discussed. Finally, both single simulation and multiple Monte Carlo simulations of CBBA with time windows are conducted to verify the effectiveness and robustness of CBBA, and time complexity is speculated.",

keywords = "Consensus-based bundle algorithm, Heterogeneous UAV swarm, Task allocation, Time windows",

author = "Siyuan Yang and Shaoming He and Tao Song and Jiang Wang",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.; International Conference on Guidance, Navigation and Control, ICGNC 2022 ; Conference date: 05-08-2022 Through 07-08-2022",

year = "2023",

doi = "10.1007/978-981-19-6613-2_439",

language = "English",

isbn = "9789811966125",

series = "Lecture Notes in Electrical Engineering",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "4522--4533",

editor = "Liang Yan and Haibin Duan and Yimin Deng and Liang Yan",

booktitle = "Advances in Guidance, Navigation and Control - Proceedings of 2022 International Conference on Guidance, Navigation and Control",

address = "Germany",

}

Yang, S, He, S , Song, T & Wang, J 2023, Improved Consensus-Based Bundle Algorithm for Multi-to-Multi UAV Interception. in L Yan, H Duan, Y Deng & L Yan (eds), Advances in Guidance, Navigation and Control - Proceedings of 2022 International Conference on Guidance, Navigation and Control. Lecture Notes in Electrical Engineering, vol. 845 LNEE, Springer Science and Business Media Deutschland GmbH, pp. 4522-4533, International Conference on Guidance, Navigation and Control, ICGNC 2022, Harbin, China, 5/08/22. https://doi.org/10.1007/978-981-19-6613-2_439

Improved Consensus-Based Bundle Algorithm for Multi-to-Multi UAV Interception. / Yang, Siyuan; He, Shaoming ; Song, Tao et al.
Advances in Guidance, Navigation and Control - Proceedings of 2022 International Conference on Guidance, Navigation and Control. ed. / Liang Yan; Haibin Duan; Yimin Deng; Liang Yan. Springer Science and Business Media Deutschland GmbH, 2023. p. 4522-4533 (Lecture Notes in Electrical Engineering; Vol. 845 LNEE).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Improved Consensus-Based Bundle Algorithm for Multi-to-Multi UAV Interception

AU - Yang, Siyuan

AU - He, Shaoming

AU - Song, Tao

AU - Wang, Jiang

PY - 2023

Y1 - 2023

N2 - This paper purposes an algorithm to achieve task allocation of heterogeneous UAV swarm to multiple mission targets constrained by time windows. First, a complete mathematical model for task assignment problem of UAV swarm is established. Second, the process of Consensus-Based Bundle Algorithm (CBBA) is described, while performance and convergence speed of it is analysed. Additionally, based on this algorithm, for the time window constraints of heterogeneous UAV swarm and tasks, some improvement is added into CBBA, which validity is discussed. Finally, both single simulation and multiple Monte Carlo simulations of CBBA with time windows are conducted to verify the effectiveness and robustness of CBBA, and time complexity is speculated.

AB - This paper purposes an algorithm to achieve task allocation of heterogeneous UAV swarm to multiple mission targets constrained by time windows. First, a complete mathematical model for task assignment problem of UAV swarm is established. Second, the process of Consensus-Based Bundle Algorithm (CBBA) is described, while performance and convergence speed of it is analysed. Additionally, based on this algorithm, for the time window constraints of heterogeneous UAV swarm and tasks, some improvement is added into CBBA, which validity is discussed. Finally, both single simulation and multiple Monte Carlo simulations of CBBA with time windows are conducted to verify the effectiveness and robustness of CBBA, and time complexity is speculated.

KW - Consensus-based bundle algorithm

KW - Heterogeneous UAV swarm

KW - Task allocation

KW - Time windows

UR - http://www.scopus.com/inward/record.url?scp=85151131331&partnerID=8YFLogxK

U2 - 10.1007/978-981-19-6613-2_439

DO - 10.1007/978-981-19-6613-2_439

M3 - Conference contribution

AN - SCOPUS:85151131331

SN - 9789811966125

T3 - Lecture Notes in Electrical Engineering

SP - 4522

EP - 4533

BT - Advances in Guidance, Navigation and Control - Proceedings of 2022 International Conference on Guidance, Navigation and Control

A2 - Yan, Liang

A2 - Duan, Haibin

A2 - Deng, Yimin

A2 - Yan, Liang

PB - Springer Science and Business Media Deutschland GmbH

T2 - International Conference on Guidance, Navigation and Control, ICGNC 2022

Y2 - 5 August 2022 through 7 August 2022

ER -

Yang S, He S , Song T , Wang J. Improved Consensus-Based Bundle Algorithm for Multi-to-Multi UAV Interception. In Yan L, Duan H, Deng Y, Yan L, editors, Advances in Guidance, Navigation and Control - Proceedings of 2022 International Conference on Guidance, Navigation and Control. Springer Science and Business Media Deutschland GmbH. 2023. p. 4522-4533. (Lecture Notes in Electrical Engineering). doi: 10.1007/978-981-19-6613-2_439