基于交换树的多机器人任务协调与负荷平衡方法.docVIP

基于交换树的多机器人任务协调与负荷平衡方法 　　摘 要：针对多机器人任务分工与协调过程中，未能有效解决的带任务偏序关系的负荷平衡问题，提出一种基于交换树的多机器人任务协调与负荷平衡方法。首先，通过有向赋权图（约束图）对带偏序关系约束的多机器人任务分工问题进行描述；其次，根据有向赋权图提出了初始任务分工策略，通过改进Dijkstra算法解决多机器人之间任务协调问题；最后，提出负荷平衡策略，通过交换树竞拍的方法解决机器人之间任务负荷不平衡问题。仿真结果表明，与一般Dijkstra方法相比，执行完任务负荷平衡策略之后，工作效率明显提高了12%，机器人之间的任务负荷差也减少了30%，验证了该方法的有效性。 　　关键词：偏序关系约束；任务协调；工作负荷平衡；多机器人 　　中图分类号：TP242.6 　　文献标志码：A 　　文章编号：1001-9081（2016）11-3127-04 　　0 引言 　　随着机器人技术的发展，机器人在我们日常生活的应用范围越来越广。多机器人任务分工与协调问题是多机器人协调领域的热点问题，广泛应用于工业、服务、军事等领域，比如多机器人车辆装配、机器人餐厅、多机器人侦察排雷等。多机器人任务分工与协调的目的是使每个机器人都承担一部分任务，并且为每个机器人找到一个任务计划满足任务之间的偏序关系（即，先后顺序关系），使得机器人完成任务的总代价最小，如时间最少、能耗最少等。通常，任务分工与协调问题可分为两步：首先，将任务分割成几个能被单独执行的子任务；其次，根据每个机器人的性质和需求进行分配[1-4]。 　　近年来，学界或工业界提出大量关于多机器人任务分工与协调的方法。Dias等[5]提出了一种基于市场法的分布式求解方法，解决了机器人团队中复杂任务的有效分工问题；但是该方法只是局限于把复杂任务分割为用布尔逻辑算子表示的多个子任务，忽略了对任务进行均等化分割，导致机器人之间存在负载不平衡现象。Zhang等[6]基于免疫算法和粒子群算法对装配序列规划问题展开研究，首先对这类问题设计命名规则，然后假定几何可行性和一致性约束条件，即目标函数；虽然该算法能解决任务之间的偏序关系问题，但是却忽略了任务分配过程中负荷不均等的问题。文献[7-8]提出了一种基于Voronoi图的等质量分割方法进行多机器人并行组装，机器人通过使用Voronoi图分割后的小区域内的组装零件质量差异最小化不断调整它们的位置平衡工作量，每个机器人只需完成自己区域内的任务；虽然该方法分配给每个机器人近似相等的任务，但是不能确保机器人是否能够顺利、高效地到达组装地点执行任务，同时没有明确解释零件之间在组装过程中存在的偏序约束关系。 　　因此，本文主要针对多机器人任务分工与协调过程中如何考虑任务偏序关系和任务负荷平衡问题，提出一种基于交换树的多机器人任务协调与负荷平衡方法。首先，将带偏序关系约束的多机器人任务分工问题描述为有向赋权图；其次，提出任务协调与负荷平衡两步策略：前者通过改进Dijkstra算法解决多机器人之间任务协调问题，并给出多机器人初始任务分工算法，后者通过交换树竞拍的方法解决机器人之间任务负荷不平衡问题，并给出基于交换树的多机器人负荷平衡算法；最后，通过多机器人机场维修/搬运仿真，验证了方法的有效性。 　　4 结语 　　本文提出的基于换树的多机器人任务协调与负荷平衡方法主要解决多机器人之间存在偏序约束的任务分工和协调问题。通过对Dijkstra算法的改进解决了任务之间存在偏序约束的问题，同时通过交换树的方法使得多机器人之间的任务负荷达到基本趋于平衡，提高了任务完成的效率。 　　在今后研究中，将对负荷平衡算法进一步改进，提高其计算效率；并且设计一种新的约束型任务描述的方法，使得该算法适用范围更广，可以用到机器人实验平台进行验证。 　　参考文献： 　　[1] LAVENDELIS E. Responsibility area based task allocation method for homogeneous multi robot systems[C]// Proceedings of the 2014 International Workshops on Ad Hoc Networks and Wireless. Berlin： Springer， 2015： 232-245. 　　[2] BRAMBILLA M， FERRANTE E， BIRATTARI M， et al. Swarm robotics： a review from the swarm engineering perspective[J]. Swarm Intelligence， 2013， 7（1）： 1-41. 　　[3] AYDI