赵文政，刘银华+，金 隼

(1.上海理工大学 机械工程学院，上海 200093；2.上海交通大学 机械与动力工程学院，上海 200240)

0 引言

多机器人光学测量系统以其非接触、可在线等特点在汽车制造领域得到广泛推广，检测系统的路径规划研究也逐渐受到学者们的关注[1]。在实际应用中，多机器人光学检测系统的运动规划需要综合考虑任务分配、机器人路径规划和多机器人协调等问题[2-4]，其中在线检测的任务分配是光学测量路径规划的重要环节，也是影响检测周期、多机器人冲突以及测量路径结果的重要因素[5]。

多机器人任务分配问题是典型的混合整数线性规划问题(Mixed Integer Linear Programming, MILP)，需要对考虑机器人路径规划和机器人之间协调等条件下的多约束问题进行优化求解。典型的方法有基于MILP模型的求解策略研究[6-7]，另外Spensieri等[8]通过建立的MILP模型，利用分支定界的方法实现焊点分配，并搜索得到最优解;Lopes等[9]在MILP模型框架下，考虑机器人参数变换、分布限制、运动时间和机器人干扰约束等因素，对机器人焊接生产线进行任务分配。MILP求解可获得最优解，但其计算资源占用量大，计算效率低，因此不适合大规模问题求解。为了提高求解效率，一些学者利用启发式算法进行任务分配，如遗传算法(genetic algorithm)、拍卖算法模型(auction algorithm)及博弈论(game theory)[10-12]等。进一步，Jones等[13]提出双层拍卖方法解决路径约束的多机器人任务分配问题；Garapati等[14]通过比较博弈论算法找到无人机之间的冲突平衡，并通过投票制度获得最终的分配结果……