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

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

移动机器人具有灵活的路由能力，能适应不同的搬运要求，便于实现自动化，因而在制造系统的物料搬运中得到广泛应用由于任务和环境的复杂多变，需要合理高效的任务调度方法已有多机器人任务调度方法有：集中式调度的方法[1]、基于角色的分配方法[2]、基于规则的方法[3]、经济方法[4]等集中式调度方法可以得到优化解，缺点是过于依赖中心控制单元，难以适应局部变化情况基于角色的分配方法根据不同机器人具有的不同功能分配任务，但是在任务* 国家973计划项目(2002CB312204)要求的功能区别不是很明显的情况下难以应用基于规则的方法简单有效，但是经常只考虑即时的状态，缺乏长远规划经济方法借鉴人类社会中经济交换的方法，通过设计类似价格的机制，在不同的主体之间传递价格效用信息，使得资源或任务得到有效的分配合同网方法是一种常用的经济方法，能适应环境和任务的动态变化情况，具有分布式的特点，能有效解决复杂动态任务调度问题任务调度需要选择合适的性能指标P. Egbelu 和J. Tanchoco提出了多种可供选择的单项指标[5]为了综合考虑不同方面的要求，可以采用多属性结合的性能指标通过设定各个属性的权重，反映各方面的关键程度。

由于制造系统中加工任务和搬运任务的复杂关系，需要考虑多方面的影响，特别需要考虑阻塞和死锁问题F. Liu和 P. Hung分析了产生死锁的条件[6]，列出了加工系统中两种死锁的情形：加工缓冲区不足引起的死锁，多机器人路径冲突引起的死锁为了避免死锁和加工设备空闲，应尽量避免输出缓冲区满和输入缓冲区空，而机器人运行距离与搬运效率紧密相关，所以可以选择机器人运行距离、输入输出缓冲区状态作为性能指标选定性能指标后，还需要确定各个指标的权值B. Jeong和S. Randhawa采用神经网络学习的方法选择不同属性的权重系数[7]D. Naso和B. Turchiano采用遗传算法学习的方法来调整权重[8]在实际中，由于系统环境和任务动态改变，离线训练的权重常常与实际情况不相符根据这些不足，通过分析影响权重的因素，主要根据系统中加工设备的负载和搬运机器人的负载情况，动态调整权重系数，这样可以适应不同任务，在效率和避免死锁方面得到很好的均衡在一般合同中，任务分配关系确定后，就不再改变这可能不适应任务的动态变化，针对这一不足，提出改进的合同网方法，允许动态任务重分配，即在任务或机器人情况改变时，对分配方案进行调整，这样可以适应系统状态和任务的动态变化，降低等待、空载时间，提高搬运效率。

动态调度常常偏向短期效率而忽视了长远效率，为了兼顾这两方面，考虑机器人前后任务之间的联系，在任务调度时，考虑已加载任务的机器人和空闲的机器人，而正在向加载位置运行的空载机器人不考虑，这样已加载的任务就和即将加载的任务关联起来，而不考虑已分配任务的空载机器人，是为了避免机器人的来回空载运行这样容易使得前后关联的任务分配到同一个机器人，降低机器人的空载路程2 问题描述2.1 多机器人搬运系统的任务模型系统环境设置描述和假设条件：制造系统环境下，多个机器人，在特定的路径网络环境下，机器人以一个特定的速度行驶，每个路径只允许单个机器人通过，节点允许机器人暂时停靠，机器人每次搬运一个工件，空闲机器人向最近的临时停靠点停靠；任务以一定到达率到达，允许有不同的任务，任务执行时间确定，任务通过输入点进入系统，加工完成后，经过输出点离开系统；每个工作台输入和输出缓冲区有限，输入点缓冲区也有限，但是容量比工作台缓冲区更大，超过输入缓冲区容量的任务放弃，输出点缓冲区无限在制造系统中，工作台集合为，输入点为0，输出点为M+1，每个工作台，有个加工设备或加工容量，加载点和卸载点分别为，输入缓冲区容量和当前输入WIP数量分别为：，，输出缓冲区容量和当前输出WIP数量分别为：，，路径网络采用图论的表示方法：，图中的节点和边分别表示工作台的加载点卸载点和连接节点的路径，从路径网络图可以得到各个站点之间的最短路径矩阵，每个元素，其中表示站点i的p点到站点j的d点的最短距离，表示站点i的d点到站点j的p点的最短距离。

机器人集合任务集合，每种任务的加工工序为：，混合比，每步加工为：，加工时间，分配的加工设备为，相应的搬运任务，表示从到，的搬运任务，需要的搬运时间为，搬运任务总数为根据起始工作台和目标工作台是否瓶颈设备来确定每个任务的关键程度每个工作台的负载：，其中 每个工作台的关键度：则任务的关键程度：输入输出点的关键度假设为1，即希望尽快输入输出假设预计的工作时间为：，任务到达率为，总的加工量：总的搬运量：系统加工能力：搬运能力系统加工负载为搬运负载为2.2 多属性结合指标的任务调度为了尽快搬运工件，需要选择尽量短的路径，所以距离是调度中首先考虑的方面而为了避免由于缓冲区不足引起的死锁，通常优先考虑输出缓冲区将满的任务，而为了避免工作台空闲，应尽量将工件搬运的到输入缓冲区将空的工作台所以主要考虑机器人到任务起点的距离、任务起始工作台的输出缓冲区状态、目标工作台的输入缓冲区状态通过综合这3个方面的参数来确定搬运任务的紧急程度，紧急程度越高，越容易得到机器人的执行已有多属性结合的调度方法中，各个方面的权重一般都预先给定或者经过离线训练得到，由于系统的加工负载是影响缓冲区大小的主要因素，而搬运负载主要影响距离的权重，所以采用根据系统加工负载和搬运负载情况实时更新权重的方法，能适应系统状态的动态变化。

2.2.1 任务价格参数的设置搬运任务的表示方法：式中：为搬运任务的起始工作台；为目标工作台；为搬运任务的关键程度工作台m的输入情况式中：为已加载目标工作台为m的任务数量，输出情况 根据系统的不同加工负载和搬运负载情况，各方面的紧急程度是不一样的，如在搬运机器人足够的时候，搬运距离的重要程度下降，而在加工设备足够的时候，则需要尽量降低搬运距离，以平衡加工负载和搬运负载，基于这种考虑，由系统负载状态确定各个权重：距离权重为输入缓冲区权重为输出缓冲区权重为任务的价格为2.2.2 机器人参数的设置机器人r执行任务Tjk成本的计算方法：假设机器人当前位置为Mv，如果是空闲机器人，则机器人到起始点的距离（需要的时间）：tv=t(Mv,Mp)，机器人预计的完成时间：tc=tv+tjk如果机器人是有负载的机器人，已加载任务的目标工作台为：Md0，到待分配任务起始点需要的时间为：tv=t(Mv,Md0)+t(Md0,Mp)，预计完成待分配任务的时间为：tc=tv+tjk这里的是按照最短距离计算出所需的搬运时间，在考虑路由问题时，可以由交通管理智能体根据交通状况得到参数和用于确定搬运任务和机器人的分配。

3 基于改进合同网的多机器人任务调度方法合同网的任务分配方法是通过需要分配的资源和任务之间的相互选择来确定分配方案的合同网的一般过程是：任务发布，资源根据任务要求投标，任务根据收到的投标选择最合适的资源分配任务任务分配以后，就签订合同，确定任务分配关系但是有时情况动态变化，原先的分配方案不再合适，如出现机器人故障时，需要改变任务调度方案，所以允许动态调整分配方案，即允许任务分配的取消、重新分配为了降低机器人空载距离，考虑同一个机器人分配的前后任务在空间上的连续性即尽量将前一个任务的目标工作台和后一个任务的起始工作台接近的两个任务分配给同一个机器人，这样可以减少机器人的空载距离为此在分配任务时，空载机器人和已经加载了工件的机器人作为可分配的机器人，这样已加载任务的机器人在选择离已加载任务目标工作台近的任务有更大的适应度，不过需要一定的预知信息来处理提前的任务分配而未加载任务但已经分配任务的机器人不再进行分配，避免无效的重复空载运行为了适应动态变化，允许任务的取消和重新分配当新的任务到达时，考虑所有可分配的机器人，选择最合适的机器人，如果机器人原来已有任务，则该任务进行重新分配；当机器人空闲或者刚加载任务时，变成可分配机器人，也可以接收其他机器人的已分配任务。

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