Cluster-Based Hungarian Approach to Task Allocation for Unmanned Aerial Vehicles

被引:0
作者
Samiei, Arezoo [1 ]
Ismail, Sarah [2 ]
Sun, Liang [2 ]
机构
[1] New Mexico State Univ, Klipsch Sch Elect & Comp Engn, Las Cruces, NM 88003 USA
[2] New Mexico State Univ, Dept Mech & Aerosp Engn, Las Cruces, NM 88003 USA
来源
PROCEEDINGS OF THE 2019 IEEE NATIONAL AEROSPACE AND ELECTRONICS CONFERENCE (NAECON) | 2019年
关键词
NETWORK FLOW PROBLEMS; MULTIROBOT; ASSIGNMENT; ALGORITHM;
D O I
暂无
中图分类号
V [航空、航天];
学科分类号
08 ; 0825 ;
摘要
In the context of autonomy for Unmanned Aerial Vehicles (UAVs), task allocation plays a significant role for collaborative UAVs to make decisions in dynamic environments. This paper presents a novel Hungarian-based approach to challenging multi-task allocation (MTA) problems, where the number of UAVs is smaller than the number of tasks. We developed the Cluster-Based Hungarian Algorithm (CBHA), in which (1) tasks are grouped such that the number of UAVs is the same as the number of task groups, (2) the original Hungarian algorithm is applied, and (3) an algorithm for travel-salesman-problem (TSP) is applied to perform path planning for individual UAVs. The performance of the proposed CBHA was compared with the Consensus-Based Bundle Algorithm (CBBA) in Monti Carlo simulations, where different numbers of UAVs and tasks were adopted in the scenario of a team of unmanned aerial vehicles traveling through a number of targeting locations. The simulation result shows that the CBHA outperforms CBBA in all cases.
引用
收藏
页码:148 / 154
页数:7
相关论文
共 35 条
[1]  
[Anonymous], 2000, EXPT COMP HUNGARIAN
[2]  
[Anonymous], 2006, ROLE ASSIGNMENT MULT
[3]  
Bakker Tim., 2014, 52nd Aerospace Sciences Meeting, page, P0991
[4]  
Bererton C, 2004, ADV NEUR IN, V16, P879
[5]   RELAXATION METHODS FOR NETWORK FLOW PROBLEMS WITH CONVEX ARC COSTS [J].
BERTSEKAS, DP ;
HOSEIN, PA ;
TSENG, P .
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1987, 25 (05) :1219-1243
[6]   THE AUCTION ALGORITHM FOR ASSIGNMENT AND OTHER NETWORK FLOW PROBLEMS - A TUTORIAL [J].
BERTSEKAS, DP .
INTERFACES, 1990, 20 (04) :133-149
[7]  
Bewley A, 2016, IEEE IMAGE PROC, P3464, DOI 10.1109/ICIP.2016.7533003
[8]   Consensus-Based Decentralized Auctions for Robust Task Allocation [J].
Choi, Han-Lim ;
Brunet, Luc ;
How, Jonathan P. .
IEEE TRANSACTIONS ON ROBOTICS, 2009, 25 (04) :912-926
[9]   A Distributed Version of the Hungarian Method for Multirobot Assignment [J].
Chopra, Smriti ;
Notarstefano, Giuseppe ;
Rice, Matthew ;
Egerstedt, Magnus .
IEEE TRANSACTIONS ON ROBOTICS, 2017, 33 (04) :932-947
[10]   Market-based multirobot coordination: A survey and analysis [J].
Dias, M. Bernardine ;
Zlot, Robert ;
Kalra, Nidhi ;
Stentz, Anthony .
PROCEEDINGS OF THE IEEE, 2006, 94 (07) :1257-1270