一种多机器人系统任务分配规划算法.pdf

《一种多机器人系统任务分配规划算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Vol.39，No.5火力与指挥控制第39卷第5期May，2014FireControl&CommandControl2014年5月文章编号：1002-0640（2014）05-0107-04一种多机器人系统任务分配规划算法*郭季1，周明2（1.安阳师范学院物理与电气学院，河南安阳455000；2.海军大连舰艇学院水下作战研究所，辽宁大连116018）摘要：针对一类可将复杂任务分解为多目标集合的任务分配问题，提出了一种基于网络图的多机器人系统任务分配规划算法。首先根据目标集合和机器人系统的初始状态，建立对应的网络图。在此基础上，将任

2、务分配问题转换为受约束的最少成本流程问题。为保证获得目标集合的最优解，提出一种结合分支界限原理和拉格朗日松弛原理的最优求解算法。在仿真中，利用提出的算法求解随机设定位置的机器人和目标点集，仿真结果表明，提出的算法可以实现目标点集的优化分配。关键词：机器人，任务分配，成本流程中图分类号：TP242文献标识码：AAKindofMulti-robotSystemTaskAllocationPlanningAlgorithmGUOJi1，ZHOUMing2（1.SchoolofElectricalandPhysical，AnyangNorm

3、alUniversity，Anyang455000，China；2.InstituteofUnderwaterOperations，DalianNavalAcademy，Dalian116018，China）Abstract：Amultiplerobotstaskallocationalgorithmforatypeofproblemwhichcanbedividedintomultipletargetssetispresented.Firstly，anetworkbasedontheinitialconditionoftarget

4、ssetandrobotssystemisintroduced，thenthetaskallocationproblemistransferredtoaconstrainedminimumcostproblemoverthenetwork.Inordertoobtaintheoptimalsolution，akindofoptimalalgorithmcombinedwiththetheoryofBranchandBoundandLagrangerelaxationisproposed.Theproposedalgorithmisu

5、sedinsimulationtoresolvetheproblemthatfromrandommultiplerobotspositionandtargetsset.Simulationresultsshowthatthemethodcouldsatisfythegoalofoptimalallocation.Keywords：robot，taskallocation，thecostoftheprocess代价约束的前提下，使得遍历所有目标点的总体代引言价最优。本文研究了一种多机器人系统任务分配规划算1问题定义和分析法，该算法在实

6、现任务集合的分配时，同时考虑了任务子集的划分以及这些划分的任务子集在多机器人设多机器人系统为，Qi为机之间的分配，任务分配的目标是使得多机器人执行器人运动规划的位形空间，多任务目标点集为多目标规划的总体代价最优。为了便于描述规划算，对于机器人Ai，法，将机器人多任务用多任务目标点集来代替，任务规划的代价包括机器人从起始点到目标点的运动代为目标点集G在位形空间Qi中对应的目标点集，价和在各目标点工作的工作代价组成［1］。任务规划为机器人Ai在各目标点的工作代的目标是使得多机器人系统在满足单个机器人任务价，为Ai到各目标点的运动代价，收

7、稿日期：2013-03-11修回日期：2013-04-07*基金项目：国家自然科学基金资助项目（51209174）作者简介：郭季（1983-），女，河南安阳人，硕士研究生。研究方向：智能控制。·107·（总第39-0846）火力与指挥控制2014年第5期0为机器人A在其位形空间的初始位形，任务qi沂Qii分配的目标是将G分解为独立目标点子集S1，…，Sm，满足。设机器人Ai完成Si的代价为准（Si），则规划的任务集合需要满足：（1）图1对应的网络图。（4）其中，Tlim为单个机器人完成目标子集的最大允许代价［2-3］。对于每个目标点

8、子集S，机器人A实现对ii其遍历，考虑到机器人的初始位形q0决定着最优遍i历目标，对子集划分产生重要的影响，为计算的简便起见，利用一种启发函数对目标点gj在Si环路中的代式（4）中参数定义如下：价c进行估计，用该估计值对式（1）进行求