针对水下UUV集群协作多目标任务分配问题，提出一种基于市场拍卖机制的分层聚类目标分配方法，研究异步/同步2种任务分配模式及模型。相对已有相关研究工作，该方法改进了任务分组的方式，任务分配机制能够较好地适应动态变化的条件。该方法分为3步：首先基于最小生成树距离的分层聚类对目标集分组为若干任务包，然后由UUV群根据各自的状态对各任务包计算执行代价并投标，最后拍卖方根据投标结果确定中标的UUV及所执行的任务包，同时根据UUV系统状态可动态调整任务分配。仿真结果表明，该方法能够较好地解决集群UUV任务分配问题。
To solve the problem of UUVs cooperative multi-objects task assignment, a hierarchical clustering target allocation method based on market auction mechanism is proposed. The asynchronous/synchronous task allocation modes and models are studied. Compared with current attempts made by the researchers, this method improves the performance of task clustering, and the task allocation mechanism can adapt to the dynamic change conditions in a better way. The method has three fold:firstly, the target set is grouped into several packages based on the hierarchical clustering of the minimum spanning tree distance, then the UUV group calculates the execution cost and bids for each package according to the respective states, and finally the auctioneer determines the winner UUV and its task package needs to be executed according to the bidding result. The task assignment can be dynamically adjusted according to the state of the UUVs system. The simulation results show that the proposed method can solve the UUVs task assignment problem.
2019,41(5): 70-75 收稿日期：2018-08-22
DOI：10.3404/j.issn.1672-7649.2019.05.014
分类号：E919
作者简介：马硕(1980-),男,博士研究生,研究方向为作战系统模拟工程
参考文献：
[1] ZHANG F, MARANI G, SMITH R N, et al. Future trends in marine robotics[J]. Robotics & Automation Magazine IEEE, 2015, 22(1):14-122
[2] WILLIAMS D P. Fast target detection in synthetic aperture sonar imagery:a new algorithm and large-scale performance analysis[J]. IEEE Journal of Oceanic Engineering, 2015, 40(1):71-92
[3] CHEIKHROUHOU O, KOUBÂA A, BENNACEUR H. Move and improve:A distributed multi-robot coordination approach for multiple depots multiple travelling salesmen problem[C]//In:IEEE International Conference on Autonomous Robot Systems and Competitions, 2014:28-35.
[4] DENG Y. Task allocation and path planning for acoustic networks of AUVs[D]. Boca Raton Florida:Flodrida Atlantic University The college of engineering and computer science, 2010:25-42.
[5] TRIGUI S, KOUBÂA A, CHEIKHROUHOU O, et al. A clustering market-based approach for multi-robot emergency response applications[C]//International Conference on Autonomous Robot Systems and Competitions, 2016:137-143.
[6] ELANGO M, NACHIAPPAN S, TIWARI M K. Balancing task allocation in multi-robot systems using K -means clustering and auction based mechanisms[J]. Expert Systems with Applications, 2011, 38(6):6486-6491
[7] ASSAF M, NDIAYE M. Solving an open path multiple depot multiple traveling salesman problem after transformation[C]//International Conference on Modeling, Simulation, and Applied Optimization, 2017:1-4.
[8] WANG X, LIU D, HOU M. A novel method for multiple depot and open paths, Multiple Traveling Salesmen Problem[C]//IEEE International Symposium on Applied Machine Intelligence and Informatics, 2013:187-192.
[9] 李亮, 邹金顺. 国外水下无人系统技术发展现状与趋势浅析[J]. 舰船科学技术, 2017, 39(12A):6-9
[10] LINHARES A, SWAMY C. Improved algorithms for MST and Metric-TSP Interdiction[J]. arXiv preprint arXiv:1706. 00034, 2017.
[11] LIU S. A Powerful Genetic Algorithm for Traveling Salesman Problem[J]. arXiv preprint arXiv:1402. 4699, 2014.
