一种多机器人搬运系统的动态任务调度方法

1、*一种多机器人搬运系统的动态任务调度方法管贤平 戴先中东南大学摘要：任务调度是多机器人管理控制的一个重要方面，采用改进的合同网方法进行制造环境下多机器人搬运系统的动态任务调度。采用多属性结合的性能指标，根据系统的负载情况动态更新各种属性的权值系数，解决了静态权值设置不适应动态变化的问题。在改进的合同网方法中，允许动态重新分配任务，能适应任务的动态变化，提高了调度的效用。采用有限状态自动机方法，详细设计了合同网中搬运任务智能体和机器人智能体的状态转移过程。关键词：合同网 动态调度 多属性指标Dynamic Task Dispatching Method for Multirobot Transp

2、ortation SystemGuan Xianping Dai XianzhongAbstract: Task dispatching is an important aspect of multirobot management and control. An improved contract net method is adapted in this paper to dynamically dispatching transportation tasks for multirobot system in manufacturing environment. The multi-att

3、ribute criteria are adapted and the coefficients for each attribute are updated dynamically according to the loads in the manufacturing system, thus the problem that static coefficients setting cannot adapt to dynamic changes is conquered. In the improved contract method, dynamic reassignment of tas

4、ks is allowed to adapt to changing tasks, thus the dispatching efficiency is improved. The detailed state transition processes of task agent and robot agent are designed with the finite state machine method. Keywords: contract net dynamic dispatching multi-attribute criteria1 引言物料搬运系统的自动化是制造系统自动化的重要

5、内容。移动机器人具有灵活的路由能力，能适应不同的搬运要求，便于实现自动化，因而在制造系统的物料搬运中得到广泛应用。由于任务和环境的复杂多变，需要合理高效的任务调度方法。已有多机器人任务调度方法有：集中式调度的方法1、基于角色的分配方法2、基于规则的方法3、经济方法4等。集中式调度方法可以得到优化解，缺点是过于依赖中心控制单元，难以适应局部变化情况。基于角色的分配方法根据不同机器人具有的不同功能分配任务，但是在任务* 国家973计划项目(2002CB312204)要求的功能区别不是很明显的情况下难以应用。基于规则的方法简单有效，但是经常只考虑即时的状态，缺乏长远规划。经济方法借鉴人类社会中经济交

6、换的方法，通过设计类似价格的机制，在不同的主体之间传递价格效用信息，使得资源或任务得到有效的分配。合同网方法是一种常用的经济方法，能适应环境和任务的动态变化情况，具有分布式的特点，能有效解决复杂动态任务调度问题。任务调度需要选择合适的性能指标。P. Egbelu 和J. Tanchoco提出了多种可供选择的单项指标5。为了综合考虑不同方面的要求，可以采用多属性结合的性能指标。通过设定各个属性的权重，反映各方面的关键程度。由于制造系统中加工任务和搬运任务的复杂关系，需要考虑多方面的影响，特别需要考虑阻塞和死锁问题。F. Liu和 P. Hung分析了产生死锁的条件6，列出了加工系统中两种死锁的情

7、形：加工缓冲区不足引起的死锁，多机器人路径冲突引起的死锁。为了避免死锁和加工设备空闲，应尽量避免输出缓冲区满和输入缓冲区空，而机器人运行距离与搬运效率紧密相关，所以可以选择机器人运行距离、输入输出缓冲区状态作为性能指标。选定性能指标后，还需要确定各个指标的权值。B. Jeong和S. Randhawa采用神经网络学习的方法选择不同属性的权重系数7。D. Naso和B. Turchiano采用遗传算法学习的方法来调整权重8。在实际中，由于系统环境和任务动态改变，离线训练的权重常常与实际情况不相符。根据这些不足，通过分析影响权重的因素，主要根据系统中加工设备的负载和搬运机器人的负载情况，动态调整权

8、重系数，这样可以适应不同任务，在效率和避免死锁方面得到很好的均衡。在一般合同中，任务分配关系确定后，就不再改变。这可能不适应任务的动态变化，针对这一不足，提出改进的合同网方法，允许动态任务重分配，即在任务或机器人情况改变时，对分配方案进行调整，这样可以适应系统状态和任务的动态变化，降低等待、空载时间，提高搬运效率。动态调度常常偏向短期效率而忽视了长远效率，为了兼顾这两方面，考虑机器人前后任务之间的联系，在任务调度时，考虑已加载任务的机器人和空闲的机器人，而正在向加载位置运行的空载机器人不考虑，这样已加载的任务就和即将加载的任务关联起来，而不考虑已分配任务的空载机器人，是为了避免机器人的来回空载

9、运行。这样容易使得前后关联的任务分配到同一个机器人，降低机器人的空载路程。2 问题描述2.1 多机器人搬运系统的任务模型系统环境设置描述和假设条件：制造系统环境下，多个机器人，在特定的路径网络环境下，机器人以一个特定的速度行驶，每个路径只允许单个机器人通过，节点允许机器人暂时停靠，机器人每次搬运一个工件，空闲机器人向最近的临时停靠点停靠；任务以一定到达率到达，允许有不同的任务，任务执行时间确定，任务通过输入点进入系统，加工完成后，经过输出点离开系统；每个工作台输入和输出缓冲区有限，输入点缓冲区也有限，但是容量比工作台缓冲区更大，超过输入缓冲区容量的任务放弃，输出点缓冲区无限。在制造系统中，工作

10、台集合为，输入点为0，输出点为M+1，每个工作台，有个加工设备或加工容量，加载点和卸载点分别为，输入缓冲区容量和当前输入WIP数量分别为：，输出缓冲区容量和当前输出WIP数量分别为：，路径网络采用图论的表示方法：，图中的节点和边分别表示工作台的加载点卸载点和连接节点的路径，从路径网络图可以得到各个站点之间的最短路径矩阵，每个元素，其中表示站点i的p点到站点j的d点的最短距离，表示站点i的d点到站点j的p点的最短距离。机器人集合。任务集合，每种任务的加工工序为：，混合比，每步加工为：，加工时间，分配的加工设备为，相应的搬运任务，表示从到，的搬运任务，需要的搬运时间为，搬运任务总数为根据起始工作台

11、和目标工作台是否瓶颈设备来确定每个任务的关键程度。每个工作台的负载：，其中 每个工作台的关键度：则任务的关键程度：输入输出点的关键度假设为1，即希望尽快输入输出。假设预计的工作时间为：，任务到达率为，总的加工量：总的搬运量：。系统加工能力：搬运能力系统加工负载为搬运负载为2.2 多属性结合指标的任务调度为了尽快搬运工件，需要选择尽量短的路径，所以距离是调度中首先考虑的方面。而为了避免由于缓冲区不足引起的死锁，通常优先考虑输出缓冲区将满的任务，而为了避免工作台空闲，应尽量将工件搬运的到输入缓冲区将空的工作台。所以主要考虑机器人到任务起点的距离、任务起始工作台的输出缓冲区状态、目标工作台的输入缓冲

12、区状态。通过综合这3个方面的参数来确定搬运任务的紧急程度，紧急程度越高，越容易得到机器人的执行。已有多属性结合的调度方法中，各个方面的权重一般都预先给定或者经过离线训练得到，由于系统的加工负载是影响缓冲区大小的主要因素，而搬运负载主要影响距离的权重，所以采用根据系统加工负载和搬运负载情况实时更新权重的方法，能适应系统状态的动态变化。搬运任务的表示方法：式中：为搬运任务的起始工作台；为目标工作台；为搬运任务的关键程度。工作台m的输入情况式中：为已加载。目标工作台为m的任务数量，输出情况 根据系统的不同加工负载和搬运负载情况，各方面的紧急程度是不一样的，如在搬运机器人足够的时候，搬运距离的重要程度

13、下降，而在加工设备足够的时候，则需要尽量降低搬运距离，以平衡加工负载和搬运负载，基于这种考虑，由系统负载状态确定各个权重：距离权重为输入缓冲区权重为输出缓冲区权重为任务的价格为机器人r执行任务Tjk成本的计算方法：假设机器人当前位置为Mv，如果是空闲机器人，则机器人到起始点的距离（需要的时间）：tv=t(Mv,Mp)，机器人预计的完成时间：tc=tv+tjk。如果机器人是有负载的机器人，已加载任务的目标工作台为：Md0，到待分配任务起始点需要的时间为：tv=t(Mv,Md0)+t(Md0,Mp)，预计完成待分配任务的时间为：tc=tv+tjk。这里的是按照最短距离计算出所需的搬运时间，在考虑路

14、由问题时，可以由交通管理智能体根据交通状况得到。参数和用于确定搬运任务和机器人的分配。3 基于改进合同网的多机器人任务调度方法合同网的任务分配方法是通过需要分配的资源和任务之间的相互选择来确定分配方案的。合同网的一般过程是：任务发布，资源根据任务要求投标，任务根据收到的投标选择最合适的资源分配任务。任务分配以后，就签订合同，确定任务分配关系。但是有时情况动态变化，原先的分配方案不再合适，如出现机器人故障时，需要改变任务调度方案，所以允许动态调整分配方案，即允许任务分配的取消、重新分配。为了降低机器人空载距离，考虑同一个机器人分配的前后任务在空间上的连续性。即尽量将前一个任务的目标工作台和后一个

15、任务的起始工作台接近的两个任务分配给同一个机器人，这样可以减少机器人的空载距离。为此在分配任务时，空载机器人和已经加载了工件的机器人作为可分配的机器人，这样已加载任务的机器人在选择离已加载任务目标工作台近的任务有更大的适应度，不过需要一定的预知信息来处理提前的任务分配。而未加载任务但已经分配任务的机器人不再进行分配，避免无效的重复空载运行。为了适应动态变化，允许任务的取消和重新分配。当新的任务到达时，考虑所有可分配的机器人，选择最合适的机器人，如果机器人原来已有任务，则该任务进行重新分配；当机器人空闲或者刚加载任务时，变成可分配机器人，也可以接收其他机器人的已分配任务。这样可以通过动态改变任务

16、分配的方法，提高搬运效率。采用多智能体系统的方法构建多机器人搬运系统的任务调度框架，其中主要的智能体是搬运任务智能体和移动机器人智能体，按照合同网协议，在智能体之间传递投标消息，实现任务调度。由于允许任务的动态重分配，搬运任务智能体和机器人智能体的状态和状态转移过程比较复杂，因此采用有限状态自动机的方法建模，详细设计各种事件处理和状态转移过程。3.1 任务调度机制任务调度根据发起主体的不同分为：工作台发起的调度，机器人发起的调度。这里采用两者结合的动态调度方法，在产生空闲机器人，或者出现新的搬运任务时，重新进行任务调度。工件到达输入点，或者工件在某个工作台完成加工，放到输出缓冲区等待搬运到下一

17、个工作台时，生成相应的搬运任务。搬运任务到达后，计算相应的价格，将任务请求、计算的价格和投标期限组成任务发布消息（call for bid）CFB=（Tik(Mp，Md，KTjk)，PRjk，Tb）发送到当前可分配的机器人，机器人根据接收的任务，按照价格参数从大到小的顺序选择一个任务，计算相应的预期完成时间tc，发送投标消息，其中为机器人投标的价格，任务智能体根据收到的投标消息，选择执行时间最少的机器人分配任务，为了有一定的提前时间，将空闲的机器人和已加载任务的机器人看作可分配的机器人，而已经接受任务，正在向任务运行的机器人看作不可分配的机器人，这样可以避免机器人重复空载运行。如果该机器人为空

18、闲机器人，则任务开始执行，如果是已经加载任务的机器人，则任务等待执行。如果没有机器人投标，则任务进入等待状态。机器人出现空闲或可分配时，发送可分配机器人到达消息（New Robot Available），其中为机器人r当前所在的位置，通知所有可分配的任务，这些任务将任务发布消息发送给该机器人，机器人通过任务选择算法，选择价格最大的任务，请求执行任务，如果该任务已分配，则比较新的机器人预期完成时间和已分配的机器人完成时间，如果新的机器人完成时间更短，则任务分配给新的机器人，原来的分配关系取消，通知原来分配的机器人。这样机器人和任务都可能发起任务分配。3.2 搬运任务智能体的处理过程搬运任务的状态

19、有：初始化IN，活动未分配UA，不活动等待UI，已分配未确认A，已确认CF，完成F，状态转移图如图1所示。图1 任务调度过程中搬运任务的状态转移图1）生成任务请求消息，计算任务价格，完成初始化，状态从IN变为UA。2）（在状态UA）生成新的可分配任务到达事件，发布任务，等待机器人的投标消息，到了投标期限，查看收集投标消息，如果收到投标消息：跳到3，否则，跳到5。3）根据投标机器人排序方法对投标机器人排序；选择最前面的一个机器人分配任务，如果该机器人是已加载任务的机器人，跳到4，如果是空闲机器人，跳到6。4）状态设置为已分配A，等待机器人任务分配请求消息或任务分配变更消息，如果没有任务变更，而且

20、对应的机器人完成已加载的任务，则跳到6，如果有任务变更消息，则跳到2。5）状态设置为不活动等待UI，等待机器人任务分配请求消息，如果有新的可分配机器人选中，跳到4，否则，经过一定时间，修改任务要求，跳到2。6）状态变为确认CF，机器人运行到任务起始工作台执行任务，如果任务完成，则状态为F，结束，如果出现故障或者任务执行失败，跳到1。在状态UI、A, 任务都可以接收机器人请求信息，发送任务要求给请求的机器人。3.3 搬运机器人智能体的处理过程状态有：初始IN，空闲活动IUA，空闲不活动IUI，已加载未分配LUA，已加载不活动LUI，已加载已分配LA，已确认CF。状态转移图如图2所示。图2 任务调

21、度过程中搬运机器人的状态转移图1）机器人初始化，状态从IN变为IUA。2）向各可分配任务发送可分配机器人到达消息，如果收到回应消息，跳到3,否则，跳到5。3）根据任务排序方法对任务排序，选择最前面的任务，分配该任务，向任务的起始工作台运行，状态变为CF，跳到4。4）运行到加载点加载任务，发送可分配机器人到达事件，状态变为已加载未分配LUA，跳到6。5）状态变为空载未分配IUI，等待任务请求，并且向最近的空闲停靠位置运行，如果接收任务，则跳到3。6）在状态LUA，发送投标请求，如果收到任务，则跳到7,否则跳到8。7）状态变为LA，继续执行当前任务，当前任务完成，状态变为CF，有其他机器人接收了已

22、分配的任务，状态变为LUA，跳到6。8）状态变为LUI，继续执行当前任务，任务完成，状态变为IUA，如果在执行途中，收到任务请求，状态变为LUA，跳到6。4 结论在制造系统多机器人搬运任务模型的基础上，通过多属性指标的综合，可以适应系统状态和任务的动态变化。根据系统负载状态设定权重，可以更真实反应系统的状态，在加工负载和搬运负载之间平衡。考虑了任务的关键度，瓶颈加工设备的任务更可能得到优先执行。允许任务的动态重分配，可以实现任务和机器人多对多的选择，避免多对一分配的不足，分配任务时考虑已加载了任务的机器人，可以有更好地处理前后任务之间在空间位置上的联系，相对即时调度，有一定的调度时间长度，即考

23、虑了较长时间段，能得到更好的优化效果。参考文献1 Kap Hwan Kim, Jong Wook Bae. A Look-Ahead Dispatching Method for Automated Guided Vehicles in Automated Port Container Terminals,J. Transportation Science, 2004,38(2):2242342 Luiz Chaimowicz, Mario Campos F M, Vijay Kumar. Dynamic Role Assignment for Cooperative RobotsJ. Pro

24、ceedings of the 2002 IEEE International Conference on Robotics &Automation, 2002, (1):293-2983 Hark Hwang, Sang Hwi Kim. Development of Dispatching Rules for Automated Guided Vehicle SystemsJ. Journal of Manufacturing Systems,1998,17(2):137-1434 Jae Kook Lim, Kap Hwan Kim, Kazuho Yoshimoto et al. A Dispatching Method for Automated G