Abstract: In task decomposition and coordination for multi-robot, the problem of workload imbalance in task with partial order constraint still exists. To overcome this problem, a task coordination and workload balance method for multi-robot based on trading-tree was proposed. Firstly, the task decomposition problem satisfying partial order constraint was described as a constraint graph. Secondly, an initial task assignment strategy was proposed according to the directed weighted graph, and the problem of task coordination among multiple robots was solved by using the improved Dijkstra algorithm. At last, the strategy of workload balance was proposed to balance each robot's workload without violating any constraints via a protocol based on trading-tree. The experimental results show that, compared with Dijkstra algorithm, after finishing the strategy of workload balance, the efficiency signifiantly increases by 12% and the difference of workload reduces by 30%.

Key words: partial order constraint, task coordination, workload balance, multi-robot

摘要： 针对多机器人任务分工与协调过程中，未能有效解决的带任务偏序关系的负荷平衡问题，提出一种基于交换树的多机器人任务协调与负荷平衡方法。首先，通过有向赋权图（约束图）对带偏序关系约束的多机器人任务分工问题进行描述；其次，根据有向赋权图提出了初始任务分工策略，通过改进Dijkstra算法解决多机器人之间任务协调问题；最后，提出负荷平衡策略，通过交换树竞拍的方法解决机器人之间任务负荷不平衡问题。仿真结果表明，与一般Dijkstra方法相比，执行完任务负荷平衡策略之后，工作效率明显提高了12%，机器人之间的任务负荷差也减少了30%，验证了该方法的有效性。

关键词: 偏序关系约束, 任务协调, 工作负荷平衡, 多机器人