基于改进合同网算法的异构多AUV协同任务分配
|
摘要
传统合同网算法应用在异构多自主式水下航行器(AUV)协同任务分配时,存在招标过程中多种招标者并存的情况,不易产生有效招标者;在投标过程中,潜在投标者增加了无效投标数量及其招标者对投标结果的评估负担,极易产生任务不合理的情况。针对以上2种问题,文中提出了一种基于改进合同网算法的异构多AUV任务分配策略。该方法将任务负载率指标和令牌环网概念结合起来,有效解决选择招标者及其任务不合理的问题。基于MATLAB的三维任务环境的仿真实验表明,对于异构型多AUV进行任务分配,文中提出的改进合同网算法能够有效提高整体效能并进行合理的任务分配。
When traditional contract net algorithm is applied to heterogeneous multi-AUV collaborative task allocation,co-existence of a variety of bid inviters occurs in bid winning process,leading to difficulty for producing effective inviter,while in bidding process,potential bidders raise the number of invalid bids,and hence increase burden on the inviter for evaluating the bid,which is easy to result in unreasonable tasks.Aiming at the above two problems,this paper proposes a heterogeneous multi-AUV task allocation strategy based on improved contract net algorithm.This strategy combines the task load rate and the token ring network to solve the problems of selecting bid inviter and its unreasonable task.Three-dimensional environment simulation based on MATLAB shows that the improved contract net algorithm can effectively enhance the overall performance and make reasonable task allocation scheme for task allocation of heterogeneous multi-AUV.
When traditional contract net algorithm is applied to heterogeneous multi-AUV collaborative task allocation,co-existence of a variety of bid inviters occurs in bid winning process,leading to difficulty for producing effective inviter,while in bidding process,potential bidders raise the number of invalid bids,and hence increase burden on the inviter for evaluating the bid,which is easy to result in unreasonable tasks.Aiming at the above two problems,this paper proposes a heterogeneous multi-AUV task allocation strategy based on improved contract net algorithm.This strategy combines the task load rate and the token ring network to solve the problems of selecting bid inviter and its unreasonable task.Three-dimensional environment simulation based on MATLAB shows that the improved contract net algorithm can effectively enhance the overall performance and make reasonable task allocation scheme for task allocation of heterogeneous multi-AUV.
引文
[1]Choudhury B B,Biswal B B.Alternative Methods for Multi-robot Task Allocation[J].Journal of Advanced Manufacturing Systems,2011,8(2):163-176.
[2]赵敏.分布式多类型无人机协同任务分配研究及仿真[D].南京:南京理工大学,2009.
[3]Shima T,Rasmussen S J,Sparks A G,et al.Multiple Task Assignments for Cooperating Uninhabited Aerial Vehicles Using Genetic Algorithms[J].Computers&Operations Research,2006,33(11):3252-3269.
[4]寇英信,王琳,周中良.多目标攻击条件下作战任务分配模型研究[J].系统仿真学报,2008,20(16):4408-4411.Kou Ying-xin,Wang Lin,Zhou Zhong-liang.Study of Combat Task Allocation Model in Multi-target Attack Condition[J].Journal of System Simulation,2008,20(16):4408-4411.
[5]李炜,张伟.基于粒子群算法的多无人机任务分配方法[J].控制与决策,2010,25(9):1359-1363.Li Wei,Zhang Wei.Method of Tasks Allocation of Multi-UAVs Based on Particles Swarm Optimization[J].Co-ntrol and Decision,2010,25(9):1359-1363.
[6]Nedjah N,Mendonc R M D,Mourelle L D M.PSO-based Distributed Algorithm for Dynamic Task Allocation in a Robotic Swarm[J].Procedia Computer Science,2015,51(1):326-335.
[7]Polat K,Güne?S.A New Method to Forecast of Escherichia Coli Promoter Gene Sequences:Integrating Feature Selection and Fuzzy-AIRS Classifier System[J].Expert Systems with Applications,2009,36(1):57-64.
[8]Owliya M,Saadat M,Jules G G,et al.Agent-Based Interaction Protocols and Topologies for Manufacturing Task Allocation[J].IEEE Transactions on Systems Man&Cybernetics Systems,2010,43(1):38-52.
[9]Kim S K,Russell J S.Framework for an Intelligent Earthwork System:Part II.Task Identification/scheduling and Resource Allocation Methodology[J].Automation in Construction,2003,12(1):15-27.
[10]Hayano M,Dai H,Sugawara T.Role and Member Selection in Team Formation Using Resource Estimation for Large-scale Multi-agent Systems[J].Elsevier Science Publishers B.V.,2014,146(C):164-172.
[11]Gerkey B P,Mataric M J.Sold!:Auction Methods for Multi Robot Coordination[J].IEEE Transactions on Robotics and Automation,Special Issue on Multi-Robot Systems,2002,18(5):758-768.
[12]李新亮,翟江涛,戴跃伟.动态环境下基于改进合同网的多Agent任务分配算法[J].科学技术与工程,2013,13(27):1671-1815.Li Xin-liang,Zhai Jiang-tao,Dai Yue-wei.A Task Allocation Algorithm Base on Improved Contract Net Protocol under the Dynamic Environment[J].Science Technology and Engineering,2013,13(27):1671-1815.
[13]Smith R G.Thecntract Net Protocol High Level Communication and Control in Distributed Problem Solver[J].IEEE Transaction on Computers,1980,29(12):1104-1113.
[14]邸斌,周锐,丁全心.多无人机分布式协同异构任务分配[J].控制与决策,2013,28(2):274-278.Di Bin,Zhou Rui,Ding Quan-xin.Distributed Coordinated Heterogeneous Task Allocation for Unmanned Aerial Vehicles[J].Control and Decision,2013,28(2):274-278.
[15]钱艳平,夏洁,刘天宇.基于合同网的无人机协同目标分配方法[J].系统仿真学报,2011,23(8):1672-1676.Qian Yan-ping,Xia Jie,Liu Tian-yu.Task Assignment Scheme Based on Contract Net[J].Journal of System Simulation,2011,23(8):1672-1676.
[16]Ponda S S,Johnson L B,How J P.Distributed Chanceconstrained Task Allocation for Autonomous Multi-agent Teams[C]//American Control Conference.Piscataway.USA:IEEE,2012.
[17]Liang H,Kang F.A Novel Task Optimal Allocation Approach Based on Contract Net Protocol for Agentoriented UUV Swarm System Modeling[J].Optik-International Journal for Light and Electron Optics,2016,127(8):3928-3933.
[18]Valentinis F,Donaire A,Perez T.Energy-based Guidance of an Underactuated Unmanned Underwater Vehicle on A Helical Trajectory[J].Control Engineering Practice,2015,44(13):138-156.
[2]赵敏.分布式多类型无人机协同任务分配研究及仿真[D].南京:南京理工大学,2009.
[3]Shima T,Rasmussen S J,Sparks A G,et al.Multiple Task Assignments for Cooperating Uninhabited Aerial Vehicles Using Genetic Algorithms[J].Computers&Operations Research,2006,33(11):3252-3269.
[4]寇英信,王琳,周中良.多目标攻击条件下作战任务分配模型研究[J].系统仿真学报,2008,20(16):4408-4411.Kou Ying-xin,Wang Lin,Zhou Zhong-liang.Study of Combat Task Allocation Model in Multi-target Attack Condition[J].Journal of System Simulation,2008,20(16):4408-4411.
[5]李炜,张伟.基于粒子群算法的多无人机任务分配方法[J].控制与决策,2010,25(9):1359-1363.Li Wei,Zhang Wei.Method of Tasks Allocation of Multi-UAVs Based on Particles Swarm Optimization[J].Co-ntrol and Decision,2010,25(9):1359-1363.
[6]Nedjah N,Mendonc R M D,Mourelle L D M.PSO-based Distributed Algorithm for Dynamic Task Allocation in a Robotic Swarm[J].Procedia Computer Science,2015,51(1):326-335.
[7]Polat K,Güne?S.A New Method to Forecast of Escherichia Coli Promoter Gene Sequences:Integrating Feature Selection and Fuzzy-AIRS Classifier System[J].Expert Systems with Applications,2009,36(1):57-64.
[8]Owliya M,Saadat M,Jules G G,et al.Agent-Based Interaction Protocols and Topologies for Manufacturing Task Allocation[J].IEEE Transactions on Systems Man&Cybernetics Systems,2010,43(1):38-52.
[9]Kim S K,Russell J S.Framework for an Intelligent Earthwork System:Part II.Task Identification/scheduling and Resource Allocation Methodology[J].Automation in Construction,2003,12(1):15-27.
[10]Hayano M,Dai H,Sugawara T.Role and Member Selection in Team Formation Using Resource Estimation for Large-scale Multi-agent Systems[J].Elsevier Science Publishers B.V.,2014,146(C):164-172.
[11]Gerkey B P,Mataric M J.Sold!:Auction Methods for Multi Robot Coordination[J].IEEE Transactions on Robotics and Automation,Special Issue on Multi-Robot Systems,2002,18(5):758-768.
[12]李新亮,翟江涛,戴跃伟.动态环境下基于改进合同网的多Agent任务分配算法[J].科学技术与工程,2013,13(27):1671-1815.Li Xin-liang,Zhai Jiang-tao,Dai Yue-wei.A Task Allocation Algorithm Base on Improved Contract Net Protocol under the Dynamic Environment[J].Science Technology and Engineering,2013,13(27):1671-1815.
[13]Smith R G.Thecntract Net Protocol High Level Communication and Control in Distributed Problem Solver[J].IEEE Transaction on Computers,1980,29(12):1104-1113.
[14]邸斌,周锐,丁全心.多无人机分布式协同异构任务分配[J].控制与决策,2013,28(2):274-278.Di Bin,Zhou Rui,Ding Quan-xin.Distributed Coordinated Heterogeneous Task Allocation for Unmanned Aerial Vehicles[J].Control and Decision,2013,28(2):274-278.
[15]钱艳平,夏洁,刘天宇.基于合同网的无人机协同目标分配方法[J].系统仿真学报,2011,23(8):1672-1676.Qian Yan-ping,Xia Jie,Liu Tian-yu.Task Assignment Scheme Based on Contract Net[J].Journal of System Simulation,2011,23(8):1672-1676.
[16]Ponda S S,Johnson L B,How J P.Distributed Chanceconstrained Task Allocation for Autonomous Multi-agent Teams[C]//American Control Conference.Piscataway.USA:IEEE,2012.
[17]Liang H,Kang F.A Novel Task Optimal Allocation Approach Based on Contract Net Protocol for Agentoriented UUV Swarm System Modeling[J].Optik-International Journal for Light and Electron Optics,2016,127(8):3928-3933.
[18]Valentinis F,Donaire A,Perez T.Energy-based Guidance of an Underactuated Unmanned Underwater Vehicle on A Helical Trajectory[J].Control Engineering Practice,2015,44(13):138-156.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |