摘  要： 在RoboCup环境下,针对多机器人的路径规划和任务分配,将LPN-DE方法和组合拍卖法有效结合,综合考虑多机器人的避障、路径规划和角色分配，提出了完整的实现方法和动态模型，并在RoboCup中型组机器人上验证了该方法的实用性和有效性。
　　关键词： LPN-DE； 适应度； 组合拍卖; 路径规划

　　随着RoboCup竞技活动的稳定快速发展，机器人对外部世界的感知和反馈都发生了深刻的变化。目前，基于声学传感的机器人基本过时，利用全景视觉摄像和智能规划的技术成为主流。
　　在全景摄像机(Full View Camera)的支持下，机器人能够完成球、球门、立柱、带有不同色标的双方机器人、球场白线及绿色地面的自主识别，从而建立起反映球场环境的图像空间，通过相关的处理技术，为机器人的路径规划提供条件。
　　由于RoboCup环境的高度动态性，机器人的障碍不再是一些静态的物体，而是位置不断变化的对方和己方机器人，机器人的目标也是运动着的。最初的办法是每隔一段时间采样一次环境信息，再利用静态的处理方法得出每一次采样下的规划路径，它没有考虑到动态变化，而且存在重复性，结果自然不理想，更不能实现多机器人间的协作与配合。因此,要求把目标和障碍物的动态信息同机器人自身的运动、位置状态结合起来，对障碍物和目标的运动状态进行预先的估计，从而规划出更合理的路径。
　　路径规划是机器人正确运动的基础，但目前的RoboCup已是多机器人的团队运动，由之而来的是多机器人的体系结构、任务分配、自主定位、协调通信等一系列问题。其中最主要的就是任务分配和通信问题，只有建立在多机器人的任务分配和通信的基础之上，才能完成多机器人之间的协作，并规划出一条能够到达目标的合理路径。
1 相关研究
　　对于多机器人系统,路径规划就是通过获取全场信息,决定机器人间的角色任务分配,在规划方案的整合下,计算出一条能够快速到达目标的合理路径。参考文献[1]利用基于采样和概率的蒙特卡罗（Monlt Carlo）方法解决机器人的自主定位问题,结合球场三角、白线和中圈定位方法，提高了定位效率和成功率，为路径规划提供了全场物体的运动和位置信息。Konolige在参考文献[2]中提出了线性规划导航梯度方法LPN(Linear Programming Navigation gradient method)，主要解决静态环境下的路径规划问题，它的构想是诸多相关文献包括本文解决问题的理论基础。由于没有考虑到动态环境，因此参考文献[3]提出了动态环境下的LPN方法LPN-DE(LPN for Dynamic Environment)，建立了新的动态模型，基本解决了动态环境下的避障和到达问题；但对于静止和速度线上的避障问题，该模型存在缺陷，参考文献[4]针对此缺陷，提出了改进的动态模型，较好地完善了单机器人的动态避障和路径规划方法。
　　解决了单机器人的路径规划问题后，就涉及到机器人间的任务分配和协作问题。参考文献[5]提出了用单物品拍卖的方法来分配任务，参与拍卖的机器人出价的依据就是机器人目前的位置和到目标的距离，但它有可能得不到最优路径^[6]。参考文献[7]提出了基于适应度的任务分配方法，概括了分配的四个基本目标，并制定了响应的四个选择策略，在此基础上建立了任务和机器人的通用适应度模型。这是一个较好的任务和机器人间的适应度量化模型。
　　本文在LPN-DE理论的基础上，利用子任务和机器人的适应度作为角色分配的组合拍卖条件，提出了完整和可行的解决动态多机器人的路径规划方案，并在真实的机器人环境中进行验证和改进。
2 动态环境下线性规划导航梯度方法（LPN-DE）
　　在全景摄像机的的图像空间内，本方法将全景图像栅格化为10 cm×10 cm的实景离散空间(已解决图像畸变)，如图1所示。为了规划出一条高效可达的路径，必须使：(1)机器人避免同对方或己方机器人碰撞；(2)追踪目标球的路径最短。所以采样图像空间，并用LPN方法为每一个采样栅格赋值，这种赋值方法即为导航函数。沿着导航函数梯度下降的方向就可以得到一条如图1的路径。

　　对于环境中的任意一个栅格，在此定义2个函数：
　　A：邻接耗费函数。代表栅格与障碍物的距离远近。
　　I：本质耗费函数。代表相邻栅格间的距离。
　　从机器人到目标球的一条路径为一组有序采样点集：P_n={p_n,p_n-1,…,p₀}，路径的耗费函数由其上每一点的A和I组成。耗费函数F可表示为：
　　

　　机器人的导航函数表示为从n点出发到目标点的最小路径耗费的耗费值：
　　
　　式中，P_k^j是j条从p_n开始到达目标点的路径，m是两点间存在路径的数量。
　　显然，即使采样空间很小，计算空间中每一点的导航函数都是很大的计算量。而LPN方法可以大大简化这一过程。LPN方法更新过程如图2所示主要有如下三步：

　　(1) 开始时，为目标点赋0值，其余点赋无穷大值。
　　(2) 把目标点放入链表中。
　　(3) 循环更新链表中的每一点，扩展它的8相邻点，并删除该点。
　　如图3中更新点p的操作：对p的任一邻点q，它的耗费值为p点的值加上p到q的邻接耗费再加上q的本质耗费。若q的值比原值小，则把q放入链表。图中右下角q的值为20+10+10=40，大于原值30，故不能把该点的值放入链表。LPN方法规划路径如图3所示。LPN方法可算出每一个采样点到目标点的最小耗费路径。图1所示的2条路径即为LPN方法的更新结果，但只有其中一条是合理的，原因是没有考虑到障碍物的动态速度。

　　考虑障碍物的动态信息，必须建立障碍物的动态信息模型。参考文献[3]首创了F动态函数模型：
　　
式中，α(p)为采样点与障碍物速度方向的夹角，‖v‖是障碍物速度的模，d(p)是二者间距离，如图4所示。当α(p)或‖v‖为0时，即机器人在障碍物速度线上或障碍物静止时规划不出有效的路径。参考文献[4]提出了改进的F动态函数模型：
　　

　　该模型既保留了前者的动态影响特性，又较好地解决了存在的问题，只需要根据场地要求和机器人的特性调整、a、b参数的值即可。基于此F函数，提出了新的障碍物动态模型：
   

    其中，C是障碍物点的本质耗费，为较大值；ε为略小于1的常数，以免在F为零时规划出的路径经过障碍物，出现比赛中常见的双方机器人的长时间原地纠缠和抵触。图5为本模型在动态障碍下的路径仿真，图6为本模型在静态和动态混合障碍下的路径仿真。由图可以看出，机器人能较好地避开了动、静态的障碍，找到目标球。

3 多机器人的适应度组合拍卖模型
3.1 多机器人适应度模型
　　LPN-DE方法很好地解决了单机器人的动态路径规划问题，但在多机器人的环境下带来了很多问题，从理论分析和作者的参赛经验:在发现了球之后，众多机器人都会追赶而去，在球的周围乱作一团，出现很多不可预测的情况，拿球的效率很低。因此必须让机器人有所分工和协作，才能更好地适应多机器人的环境。
　　为了解决多机器人任务分配的准则，本文提出了适应度的概念。适应度是指机器人对当前各任务的适应程度和完成能力。在这个准则约束下，把机器人的任务分为4个等级：
　　(1)射门：机器人拿到球之后，将球射入对方球门。
　　(2)追球：机器人发现球之后，向球运动，并拿到球。
　　(3)拦截：拦截对方射门或追球的机器人。
　　(4)回防：机器人没有发现球后，主动回撤己方区域防守。
　　其中，各等级的标号就是它们的优先级。同时，根据机器人的当前状态因素，为机器人建立了一个适应度模型，包含如下参数：
　　(1)机器人当前任务标号As：参数为变量，取值由机器人当前选择的任务确定。
　　(2)机器人当前功能状态St：参数为变量，如果机器人具备执行任务i的能力，则S_t(i)的值为1，否则取0。
　　根据当前的任务特点和机器人状态之间的匹配，利用拍卖的方法进行任务分配，并根据球场的变化适时调整机器人的角色，从而最终完成拿球和射门的任务。
3.2 基于适应度的组合拍卖方法
　　多件物品组合拍卖问题(Multi-unit Combinatorial Auctions)可描述为：设M表示为拍卖物品的集合，用M={1,2,…,m}表示,每种物品数量表示为U={u₁,u₂,…,u_m}，竞标集合B={B₁,…,B_n}，若P_j是此竞标的一个出价，S_j是一个物品集合。则一个竞标就是一个二元组B_j=j,P_j>，将每一个竞标j注为胜利(x_j=1)或失败(x_j=0)，满足以下约束：
　　

　　投标者之间必须满足：
　　(1)中标者之间不存在物品上的冲突;
　　(2)中标者所带来的收益最大。
　　针对适应度模型的4个等级，以机器人和目标球之间的距离为拍卖的竞标出价，具体的拍卖策略是：
　　(1)若某个机器人处于“射门”状态，则不再执行其他任务，其余机器人皆需配合它的动作，执行“拦截”任务。
　　(2)若无机器人处于“射门”状态，则距离目标球最近的机器人执行“追球”任务，其余机器人执行“拦截”任务，并根据球场状态适时调整机器人执行任务的角色。
　　(3)若机器人都没有发现球，则首先旋转360°，若仍然没有发现，则距离己方区域最近的两个机器人执行“回防”任务。
　　(4)拍卖是基于协商主义的，多机器人系统在设定的协议基础上通过机器人间的协商、谈判来完成任务分配，本文的协议就是机器人对任务的适应度。
4 基于适应度拍卖的多机器人实验
　　本文采用的是RoboCup中型组4:4平台，球场环境尺寸为12m×8m。为了验证LPN-DE和适应度拍卖方法的有效性，截取了开球后的某个典型状态，此时机器人都发现了球，通过LPN-DE方法的计算，每个机器人规划出了自己的追球路径，如图7所示。在LPN-DE方法的基础上，利用适应度拍卖的方法对四级任务分配给多机器人，规划出的路径如图8所示。

　　多机器人系统所存在的问题就是让机器人能够相互配合，优化协同解决问题，而不是各自单独按照同样的方式运动。从图8可以看出，在距离球最近的那个机器人追球后，其余的机器人执行的是拦截任务，拿到球的概率提高了。

　　在RoboCup动态环境下的多机器人协同问题实时性高、运算量大、系统复杂，需要整合环境信息，己方、对方机器人状态等诸多静态和动态信息。本文把诸多文献中解决各个子问题的方法结合起来，利用LPN-DE方法计算出单机器人的最优路径，再将任务分解为4个等级，根据LPN-DE的结果即可算出机器人对各等级的适应度，在此基础上，用组合拍卖的方法进行任务分配，得到每个机器人的最佳角色。此综合规划方法已应用于苏州大学RoboCup中型组“骑士”队中，取得了较好的效果。

参考文献
[1] 刘松国，朱世强.移动机器人的蒙特卡罗自主定位算法研究. 机电工程, 2005.
[2] KONOLIGE K. A gradient method for realtime robot control.IEEE International Conference on Intelligent Robots and Systems, 2000.
[3] FARINELI A, IOCCHI L. Planning trajectories in dynamic  environments using a gradient method. Proc. the International RoboCup Symposium,Padua,Italy, 2003.
[4] 王建中，尹义龙.基于动态信息模型的LPN路径规划方法.计算机工程, 2006(9).
[5] GERKEY B P, MATARIC M J.Sold!:auction methods for multirobot coordinational. IEEE Transactions on Robotics and Automation, 2002.
[6] BERHAULT M, HUANG H. Robot exploration with combinatorial auctions.Georgia Instiute of Technology,2003.
[7] 董炀斌,蒋静坪.基于适应度的多机器人任务分配策略. 浙江大学学报(工学版), 2007(2).