分散式無人機群在動態環境中任務重新分配的競標演算法

Auction-based algorithm for distributed UAVs task reallocation in dynamic environment

黃筱薔(Xiao-Qiang Huang)

指導教授 ： 蘇豐文

國立清華大學/電機資訊學院/資訊工程學系所/碩士(2021年)

摘要

分散式無人機群的分配已經被討論許多年了。因為缺少隊長分配任務給其他隊員，無人機需要透過彼此溝通來決定誰會去執行任務。然而，在一個未知且不斷改變的環境中，任務有可能會動態的出現或是消失，所以無人機需要能夠快速地重新分配任務。因此我們修改了CBAA(Consensus based Auction Algorithm)，讓它可以解決這類重新分配任務的問題。為了能夠更快速的重新分配任務，我們提出了一個有效率的拍賣機制策略，這個策略可以減少重新參與拍賣的無人機以減少任務分配的協調時間。在沒有隊長的情況下，無人機群可以透過交換訊息，有效率的達成任務重新分配。

關鍵字

分散式 ； 無人機 ； 任務分配 ； 競標演算法 ； 去中心化

並列摘要

Task allocation for distributed Unmanned Ariel Vehicle (UAV) has been discussed for many years. Without a leader that allocates the tasks to other members, UAVs need to communicate with each other and decide who would perform the tasks. However, in an unknown and changing environment, the tasks might disappear or pop up dynamically, and therefore UAVs are required to reallocate task immediately. Thus, we modified CBAA(consensus-based auction algorithm) so that it can solve such task allocation problem. To reallocate the tasks in less time, we propose an efficient auction-based strategy for such a problem. This strategy can make less UAVs join the re-auction when tasks are changing, thus it can take less time to finish the task coordination. And without leader, the UAVs with the proposed auction-based algorithm can efficiently accomplish the task reallocation through the exchanging of information with each other.

並列關鍵字

distributed ； UAV ； task allocation ； auction algorithm ； decentralized

參考文獻

[1] Brian P Gerkey and Maja J Mataric. A framework for studying multi-robot task allo-cation. 2003.

[2] G Ayorkor Korsah, Anthony Stentz, and M Bernardine Dias. A comprehensive taxon-omy for multi-robot task allocation.The International Journal of Robotics Research,32(12):1495–1512, 2013.

[3] Thomas Lemaire, Rachid Alami, and Simon Lacroix. A distributed tasks allocationscheme in multi-uav context. InIEEE International Conference on Robotics andAutomation, 2004. Proceedings. ICRA’04. 2004, volume 4, pages 3622–3627. IEEE,2004.

[4] Han-Lim Choi, Luc Brunet, and Jonathan P How. Consensus-based decentralized auc-tions for robust task allocation.IEEE transactions on robotics, 25(4):912–926, 2009.

[5] Luc Brunet, Han-Lim Choi, and Jonathan How. Consensus-based auction approachesfor decentralized task assignment. InAIAA guidance, navigation and control confer-ence and exhibit, page 6839, 2008.