（计算机应用技术专业论文）多智能机器人系统任务分配与协作.pdf

硕士论文多智能机器人系统任务分配与协作 摘要 随着机器人技术的发展，人们越来越将研究的重点集中到多智能机器人 系统中。而机器人团队中多个机器人之f b j 的任务分配与协作则是当代人工智 能领域中的研究热点。 本文首先介绍了蚁群算法的生物学原理来描述了一种多a g e n t 之间的相 互协作方法。然后具体以t s p 问题为研究对象，阐述蚁群算法中多a g e n t 如 何彼此协作求解问题。接着本文以物流配送问题为研究对象，分别利用遗传 算法和蚁群算法为研究工具，讨论了在静态确定环境下，多机器人之间如何 任务分配和相互协作。接着，我们将讨论动态不确定环境下，多机器人之间 任务分配和相互协作的四种常见策略和各自适用的领域。最后，我们将具体 介绍一种基于竞价方式的多机器人任务分配策略和一种基于矩阵分析的快速 任务分配方法。 关键字： 多智能体，多智能机器人系统，协作，任务分配，蚁群算法，物流 配送问题，遗传算法 顾十论文 多智能机器人系统任务分配与协作 a b s t r a c t w i t ht h ed e v e l o p m e n to fr o b o tt e c h n o l o g y ，p e o p l ea r ep u t t i n gm o r ee m p h a s i s 0 nt h er e s e a r c ho f 姒r s t h ei s s u eo ft a s k sa l l o c a t i o na n dc o o p e r a t i o na m o n g r o b o tt e a mi st h em o s t p o p u l a ri s s u e i nt h er e s e a r c ho f h u m a n i n t e l l i g e n c ef i e l d ， t h i st h e s i sw i l lf i r s t l yi n t r o d u c eo n ew a yo f c o o p e r a t i o na m o n gm u l t i - a g e n t s b yd e s c r i b i n gt h eb i o l o g i c a lp r i n c i p l eo fa n t - g r o u pa r i t h m e t i c ；s e c o n d l y , m a k e t h et s pi s s u ea st h e t a r g e to f r e s e a r c ha n d e x p l a i nh o w t h em u l t i a g e n t sc o o p e r a t e w i t he a c ho t h e rt or e s o l v ep r o b l e m su n d e rt h ea n t g r o u pa r i t h m e t i c ；t h i r d l y ，m a k e t h el o g i s t i c sf r e i g h tp r o b l e ma st h et a r g e to fr e s e a r c ha n dt a k eu s eo ft h eg e n e t i c a r i t h m e t i ca n da n t g r o u pa r i t h m e t i ct od i s c u s st h ei s s u eo fh o wt h em u l t i - r o b o t s d i v i d et h et a s k sa n d c o o p e r a t e w i t he a c ho t h e ri nt h es t a t i cc i r c u m s t a n c e s ；f o u r t h l y d i s c u s st h ef o u rc o m m o n p r i n c i p l e so f h o wt h em u l t i - r o b o t sa l l o c a t et h et a s k sa n d c o o p e r a t e “me a c ho t h e ri nt h ed y n a m i ca n du n c o n f i r m e dc i r c u m s t a n c e sa n d t o w h i c hf i e l dt h a te a c hp r i n c i p l ea p p l i e s a tl a s t ，t h et h e s i sw i l li n t r o d u c et w o p r i n c i p l e so f t a s k sa l l o c a t i o na m o n gm u l t i r o b o t si nd e t a i l e dw a y ：o n ei sb a s e do n t h em e a n so f a u c t i o n ，t h eo t h e ri sb a s e do nt h ea n a l y s i so f m a t r i x k e y w o r d s ：m u l t i a g e n t s ，m a r s ( 氍u l t i a g e n tr o b o t i cs y s t e m ) ，c o o p e r a t i o n ， t a s k sa ll o c a tio n ，a n t g r o u pa r i t h m e t i c ，l o g i s t i c s f r e i g h tp r o b l e m ，g e n e t i c a r i t h m e t i c 、6 24 2 2 2 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：垫拯 、w 严- 年月8 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：郄虹j 山牛年6 月矽日 硕士论文 多智能机器人系统任务分配与协作 1 引言 1 1 引言 随着计算机、通讯、电子、传感、控制等技术以及人工智能的飞速发展， 机器人的开发与应用得到了不断地提高机器人的发展经历了三个阶段：( 1 ) 可编程的、示教再现型机器人；( 2 ) 带有一定的视觉、触觉，具有一定适应能 力的机器人；( 3 ) 带有多种传感器，具有自适应能力、自学习功能的自主式机 器人，即所谓的“智能化机器人”。智能机器人是多种学科技术的集成，涉及到 机构学、控制工程、计算机技术、人工智能、传感技术、仿生学和其它些相 关的领域，针对智能机器人，国内外都展开了相关技术的研究。 随着智能人技术的发展，人工智能领域的研究重点已经转到多智能机器人 系统的研究上。多机器人群体协作系统具备自己的特点：( 1 ) 空间分布：多 个机器人分布在工作空间的各个区域同时作业，( 2 ) 功能分布：功能不同的 机器人或具有不同目标任务的多机器人可以协同工作；( 3 ) 时间分布：多个机 器人可以在不同时间分布内执行任务【1 】 事实证明，一个相互协调的多机器人系统有着单个机器人系统所无法比拟 的优势： 1 ) 相互协调的n 个机器入系统的能力可以远大于一个单机器人系统的n 倍， 多机器人系统还可以实现单机器人系统所无法实现的复杂任务； 2 ) 当环境或任务极其复杂，需要机器人具有多种能力，而设计这种集所有能 力于一体的单机器人成为不可能时，多机器人系统是最佳解决方案： 3 ) 设计和制造多个简单机器人比单个复杂机器人更容易、成本更低： 4 ) 使用多机器人系统可以大大节约时间，提高效率： 5 ) 多机器人系统的平行性和冗余性可以提高系统的柔性、鲁棒性和容错性，等 等， 然而，多机器人系统也存在单机器人系统所不存在的问题： 1 ) 如何在各智能体间表达、描述问题，分解和分配任务： 2 ) 如何使智能体间相互通讯和相互作用： 3 ) 如何保证各智能体行为协调一致： 4 ) 智能体间如何识别和解决冲突，等等 多机器人协调系统涉及到社会科学( 组织理论、经济学) 、生命科学f 理论生 物学、动物行为学) 和认识科学d 理学、信息理论、人工智能) 等的学科理论 堡主堡兰 墨塑丝塑墅叁墨竺堡鱼型堕生皇! ! 堡一 和关键技术。 1 2 现状 机器人群体协作系统的应用领域是很广阔的具有潜在的巨大的技术市 场如( 1 ) 工业领域：未来自动化生产线中，机器人群体系统可以担负起人类 的作用，如组织物料运输，生产加工和其它一些复杂的任务在一些危险环境 或恶劣环境中可以代替人类自主完成一些复杂作业。( 2 ) 医学领域：大量的微 机器人进入场道、胃或血管等人体内狭窄部位进行校查、发现和修补病变；( 3 ) 军事领域：使用机器人群体进行侦察、巡逻，排雷等；( 4 ) 航天领域：利用机 器人群体进行卫星和空间站的内外维护以及星球探索等。【l 】 经过二十几年的发展，多机器入系统的研究已在理论和实践方面取得很大 进展，并建立了一些多机器人的仿真系统和实验系统目前，国内的多机器人 系统的研究刚刚起步而国外的研究则比较活跃欧盟设立专门进行多机器入 系统研究的m a r t h a 课题用于搬运的多自主机器人系统( m u l t i p l e a d t o n o m o u sr o b o tf o rt r a n s p o r t a n dh a n d l i n ga p p l i c a t i o n ) “。美国海军 研究部和能源部也对多机器人系统的研究进行了资助。但从总体上讲，目前多 机器人系统的研究还处于发展的初期阶段，离实用化还有很远的距离。【2 】 1 3 多机器人系统的主要研究内容 目前多机器人领域的研究内容主要有控制结构( 或体系结构) ，通信相冲突 的解决等问题。其中，控制结构和通信问题屑于多机器人系统中的高级控制任 务，而冲突的解决( 包括防止死锁和避障及路径规划等问题) 则属于多机器人系 统中的低级控制任务。下面我们将对这三方面的研究内容进行简要的介绍： i 多机器人系统的控制结构 多机器人系统是出大量具有环境观察、任务规划和操作功能的智能机器人 组成。随着科技的发展，这些智能机器人的智能、秉性和自主性变得越来越高。 为了把这些智能机器人组织起来构成一个复杂系统，就需要一个控制结构。控 制结构是描述为实现预定的行为必须如何把这些智能机器人连系到一起的，从 而有效地完成某些任务。多智能体的控制结构可分为集中式和分散式，而分散 式又分为分层式相分布式，分布式结构中所有的智能体相对于控制是平等的， 分层式结构在局部则是集中的。普遍认为分散式结构比集中式结构在可靠性相 鲁捧性方面具有较高的性能。控制结构的主要研究问题是设计出正确而合理的 局部控制方案，以能够使多机器人系统能高效率地解决给定的问题。主要内容 堡：! 丝竺 兰矍墼塑矍查竺堡墨坌墼：堂一 包括相应的任务选择( 任务分配) 、通信、冲突的解决等。经过十几年的研究， 科研工作者已经提出了一些控制结构方案，但是由于多种原因，大多数控制结 构只适用于特定的系统，不具有推广和普及性，同时由于大多数研究者汉有考 虑系统实际应用中的需要，因此控制结构缺乏实用性。一个通用性好的多机器 人控制结构需要 包括以下方面： a ) 如何在多机器人系统中用公式表示、描述、分解和分配问题； b ) 如何使机器人进行通信和相互作用： c ) 如何使机器人在行动中保持一致性； d ) 如何使机器人意识到和解决彼此的冲突。 除了满足上述要求，开发一个多机器人控制结构的主要目标是使多机器人 系统具有鲁棒性，可靠性和柔性。【2 】 2 多机器人系统在执行某项任务时，为了实现协调与合作，个体机器人的 传感器必须提供足够的环境描述及其他机器人的信息。由于目前使用的各种 传感器还不能达到这个要求，因此机器人之间或上层控制和下层合作之间的 通信是必不可少的。机器人间的通信方式主要有两种，即直接通信和间接通 信。直接通信要求发送和接收信息时能保持致性，因此在机器人之间就需 要一种通信协议。直接通信的最重要特征是通信时发送者和接收者同时“在线 上”。而间接通信不需要发送和接收信息之问保持一致性。例如，广播是种 间接通信方式，它不要求一定有接收者，也没有必要保证信息正确地传送到 其他机器人，换句话说，发送的信息有可能被忽略，广播通信的重点在发送 者。观察是另一种间接通信方式，它的重点在接收者( 观察者) 。尽管不是有 意识地交换信息，但是无论信息是通过何种方式获得的，间接通信总是起作 用。般来讲，直接通信存在于有智能的机器人之间，而间接通信存在的范 围就比较广，可存在于个体和个体通信，个体和群体通信，个体和环境通信 等。目前，移动机器人系统的通信主要采取直接通信与广播相结合的混合方 式。通常个体机器人与主控机器人( 或控制中心) 的信息交互( 主要是工作 信息和任务分配) 通过直接通信实现，这样减少了其余机器人的网络负载； 而主控机器人通常将机器人群中各机器人的当前位置和状态以广播形式发 出，供个体机器人参考，简化了发送方的工作。由于工业机器人一般位置固 定，因此系统中多采取直接通信的方式，通过以太网( e t h e m e t ) 等通信网将 多台工业机器人连接在一起根据某种协议进行有线通信。选择通信方式的 基本要求是保证通信的有效性和实时性。但由于目前通信还存在许多瓶颈问 题，如负载量大则通信速度下降等，在应用中直接通信过多会导致系统的动 态性下降等 2 1 。 堕主堡塞 童塑墼塑壁垒墨竺堡墨坌墼皇堡堡 3 在多机器人系统中还有一个很重要的问题就是解决系统中的冲突。系统 中冲突的形式是多种多样的，主要有任务冲突、路径冲突和空间冲突等。多 机器人系统中的冲突很容易造成系统的混乱，严重地影响系统的总体性能。 解决冲突除了要有合理的控制结构和通信方式外，也需要相应的解决策略。 在多机器人系统中，每个机器人都把其他机器人当成障碍物来处理，并通过 传感器探测障碍物的有无。同时机器人也根据定期接收到的信息来处理传感 器的不确定性，并区分机器人障碍物和非机器人障碍物，由此选择不同的处 理方法。多机器人系统的冲突解决办法很多，最直接的方法是采用集中控制 器来决定所有机器人的无冲突路径，但这种方法在实用性方面具有一定的缺 陷。另一种方法就是冲突的机器人中有个做主控，指挥其他机器人以解决 冲突问题。另外有学者提出了基于交通规则的分散式方法，但它适应于结构 化的网络环境。近来提出的分布式方法将工作空间分成由离散的空问资源表 示的公路网，如通道、十字路口和单元等。机器人沿预定的路径前进并互相 通信，采用互相排斥的方法共享资源和协调彼此的运动。 除了上述的几个主要问题外，多机器人系统中需要研究的问题还有多机 器人系统的学习问题和环境观察问题等。【2 】 t 4 本文所研究内容及目的 1 4 1 本文的研究目的 多机器人系统应用广泛，近几年国防投入大量人力、财力用于多机器人 系统的研究和开发。多机器人系统的研究目的就是试图让多个机器人通过协 作，来完成单个机器人无法完成的任务，并且提到完成任务的总体性能。这 就决定了多机器人之间的协作是多机器人系统研究的重点方向之一。 目前，机器人群体协作与机器人社会系统的研究还刚刚开始，有许多方 面的阀题还有待更深入地研究。f 1 ) 集成分布式人工智能、分布式控制和复杂 系统控制理论等方面的研究，建立研究机器人群体协作系统理论体系：( 2 ) 实 时动态环境下，机器人不确定性知识的表达以及基于不确定性知识的推理模 型的研究：( 3 ) 机器人行为动力学及其群体行为动力学的描述：( 4 ) 多机器人系 统中协作性、容错性、柔性、鲁律性等概念的研究；( 5 ) 多机器人系统组织结 构的描述方法；( 6 ) 多机器人系统建模。 本文就多机器人之间的协作问题进行了简单研究，特别对物流配送问题， 提出了一些路径规划的方法。同时，通过对动态环境下多机器人协作方法和 多器人系统中任务分配策略的研究，希望对以后的研究工作提供指导思想和 硕1 一论史 多智能机器人系统任务分配与协作 借鉴。 1 4 2 本文研究内容 当一个多机器人系统给定一个任务时，首先的问题是如何组织多个机器 人去完成任务。这时要解决的问题是多机器人之间怎么进行有效地合作。当 经过某中继站确定了各自任务和关系后，问题便为如何保持机器人之问的运 动协调一致，即多机器人协调。因此多机器人协调和多机器人合作是多机器 人系统研究中两个不同而又有联系的概念。前者研究的重点是机器人之间合 作关系确定后具体的运动控制问题，后者则是高层的组织与运行机制问题， 重点是实现系统可以快速组织与重构的柔性控制机制。 实现多机器人的合作所要解决的问题主要有： ( 1 ) 、多机器人系统的结构 系统结构是系统的最高层部分，夺机器人之间的合作机制就是通过它来 体现的，它决定了多机器人系统在任务分解，分配，规划，决策及执行等过 程中的运行机制及系统各个机器人个体所担当的角色，如个机器人个体在系 统中的相对地位如何? 是平等自主的互惠互利式协作还是有等级差别的统筹 规划协调? 任务分解、分配、规划、决策及执行等对某个个体而言是一物( 即 没有做与不做的决定权) 还是权力( 特权) ? 总之，正如社会制度只作用于 人类社会，它决定了多机器人系统的运作机制，事关协作效率的高低。从系 统设计的角度而言，系统结构要有利于个体能力最大程度的发挥和任务的最 高效完成。另外协作机器人系统面向的是动态变化的环境，因此系统结构 要对环境有自组织适应能力。 ( 2 ) 、建模与规划 机器的智能大致可以通过两种形式实现：其中一种是基于行为的方式， 采用这种方式是不用建立协作对象、环境及自身的状态及行为方式的模型， 其智能表现为一个反应是行为驱动规则基；另一种方式则是建立在形式化模 型的基础之上，个体根据它建立的其协作个体和自身的心智状态及行为能力 模型进行决策和实现协作。 规划则包括从全局任务级至局部( 个体) 行为动作级规划，这些规划应 能在自主个体之间动态进行，以适应动态变化的系统和环境。避免资源冲突 也是规划过程中所要考虑的。 ( 3 ) 、通信和商议 多机器人系统不是因为个体之间的信息交互而发生了相互作用，是因为 相互作用的需要而产生了个体之间的信息交互。它是实现多机器人合作的一 硕 ：论义多智能帆器人系统任务分配与协作 种手段。多机器人系统作为一种分布式信息及决策系统，网络结构是其重要 结构特征。通信是个体信息的交换，而商议是有目的的信息交互。商议是建 立在信息交互基础上的。 ( 4 ) 、感知和学习 感知是指机器人通过它的传感系统获取信息并经信息融合后加以利用。 不论是基于行为方式还是基于模型方式的协作，感知都是必不可少的。感知 作为机器人与局部外界的一种交互，对机器人而言与通信一样是机器人获取 信息的一种方式。 制订控制策略对人而言是比较方便的，但要确定控制参数，机器做起来 就快而且准，因此为了系统获取理想协作行为的控制参数并使它适应动态变 化的环境，在系统中引入学习机制是非常重要的。 从上可知，刨痛意义上的多机器人合组系统研究的还是具体问题，即对 每一个特定的任务，都要有自己特定的体系、建模与规划、协商与通讯等等。 当任务改变时，他的体系结构、组织管理与运行机制等都要随之改变。这给 多机器人合作系统的应用带来很大的不便，人们因此想到能否从理论上找到 一个通用的方法即不局限于每个具体的问题而从总体上考虑一个解决方 法，使多机器人合作系统在这种理论的指引下。能够完成各种任务而无需改 变体系结构、组织运行机制等。 本文的研究内容是多机器人系统中多机器人之间的协作和任务分配问 题。 首先介绍种多智能体合作解决问题的算法蚁群算法，该算法模仿自 然界中蚁群觅食的原理，通过群体之间的协作，完成特定任务。本文中我们 利用该算法，通过系统中的多个a g e n t 之间的合作，来求解t s p 问题。 接下来，我们将以物流配送问题为模型，研究下多机器人之间的协作 问题。这属于一种机器人之间的静态协作，即一旦多机器人之间完成协商， 得到全局的路径规划之后，机器人之间不再彼此之间动态的协商和规划，直 到完成任务。我们将讨论和研究一些算法，可以从总体上得到一个较优的全 局路径规划，从而从总体上提高系统性能。本文中，我们将分别利用遗传算 法和蚁群算法来解决物流配送问题。 然后，我们将讨论动态不确定环境下的多机器人协作。也就是在多机器 入系统中，为了完成一个任务，在任务执行过程中，系统中的机器人之间会 根据现实环境中外部环境的动态变化和各个机器人自身的状态，动态的相互 协调，楣互配合提高或优化系统的性能。我们将简单介绍一下机器入协作 的几个阶段的划分和影响机器人协作的几个因素。最后再简单讨论一下常见 的几种动态协作策略和各自适用的领域。 塑：! 堡苎 兰塑墼垫壁垒墨竺堡墨坌墼里堡生 最后再具体介绍_ 一种基于拍卖的任务分配策略和一种基于矩阵分析的快 速任务分配方法。通过这两种方法可以快速有效的实现动态不确定环境下多 机器人任务分配，具有一定的鲁棒性和健壮性，并且实现相对简单。 1 4 3 内容安排 本文的内容安排如下： 1 ) 、第一章介绍多机器人的研究现状和多机器人系统的主要研究内容。 概要介绍本文的研究目的和研究内容。 2 ) 、第二章介绍蚁群算法的生物学原理、算法内容，并通过t s p 问题的 研究，体现多a g e n t 之间通过协作从而得到系统总体较优解的方法。 3 ) 、第三章介绍了一个以物流配送问题为研究对象，通过多机器人之间 的静态协作，得到一个全局较优的路径规划的方法。 4 ) 、第四章研究了动态不确定环境下多机器人之间动态协作的几个阶段 和影响多机器人之间动态协作的各种情景和因素。接着分析了动态不确定环 境下多机器人协作的四种策略和各自适用的领域。 5 ) 、第五章具体介绍了一种基于拍卖的任务分配策略和一种基于矩阵分 析的快速任务分配方法。 烦i 论文多智能竖缝笙堡塑坌墼兰塑掺 2 多a g e n t 之间群体协作 蚂蚁是最古老的社会昆虫之一，它的个体结构和行为虽简单，但由这些 简单个体构成的蚂蚁群体，却表现出高度结构化的社会组织。蚂蚁王国俨然是 一个小小“社会”。这挈，有专司产卵的蚁后：有为数众多的从事觅食打猎、 兴建屋穴、抚育后代的工蚁：有负责守卫门户、对敌作战的兵蚁等等。蚂蚁是 社会性昆虫，组成社会的三要素之一就是社会成员除有组织、有分工之外，还 有相互的通讯和信息传递。研究表明，蚁群有着奇妙的信息系统。其中包括视 觉信号、声音通讯和更为独特的无声语言，即包括化学物质不同的组合、触角 信号和身体动作在内的多个征集系统，来策动其它个体。蚂蚁特有的控制自身 环境的能力，是在高级形式的社会性行为及不断进化过程中获得的。 觅食行为是蚁群一个重要而有趣的行为。据昆虫学家的观察和研究。发现 蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能 随环境变化适应性地搜索新的路径，产生新的选择。虽然单个蚂蚁的行为极其 简单，但由大量的蚂蚁个体组成蚂蚁群体却表现出极其复杂的行为，能够完 成复杂的任务。 2 1 蚁群算法的原理 蚂蚁算法所依据的自然模型是蚂蚁群。蚂蚁能够找出一条从食物到它巢 穴的最短路径。这是通过释放一种称作弗罗蒙的信息素，而不是使用某种可 见的线索。在行走过程中，蚂蚁释放出弗罗蒙，并且通过它来前进，而这些 弗罗蒙可能是以前其它蚂蚁释放的。蚂蚁根据弗罗蒙在两点之间寻找一条最 短路径的方法如图1 1 所示。 如图所示，蚂蚁到达一个决策点，在此，蚂蚁将决定它是该向右还是该向 左由于它没有关于哪条路是最优路径的任何线索，它就随机的选择。可以预 计，平均大约有一半的蚂蚁决定向右转。而另一半向左转。这对那些从左向右 移动的蚂蚁( 以l 开头) 的蚂蚁和那些从右向左的蚂蚁( 以r 开头) 都适用。图 l _ 1b 和图1 _ lc 显示出如果所有的蚂蚁以近似相同的速度移动时将发生的情 况。虚线的数量和蚂蚁在行走过程中所释放的弗洛蒙的数量成正比。由于下 面的那条路径比上面的那条要短，平均看来将有更多的蚂蚁访问这条路径。 因此弗洛蒙将更快地积聚。很快两条路上的弗洛蒙的数量的差别将变得非常 大，以至于将影响新进入系统的蚂蚁的选择。( 如图2 1d 所示) 从现在开始 蚂蚁将倾向于选择下面的那条路径，因为在决策时，蚂蚁将从下面的那条路 径接收到更多的弗洛蒙。随着正向反馈效果地增加，选择下面路径( 最短路 硕j ：论文多智能机器人系统任务分配与协作 径) 的蚂蚁数量也将增加。很快，所有的蚂蚁都将选择这条最短路径。 圈2 ，l 蚂蚁巡径原理图 2 2 蚁群算法及程序简单流程图 蚂蚁的这种行为启发了蚁群算法。它是这样的一种算法：一些人造的蚂蚁 通过在图的边缘上释放的弗洛蒙来交换信息，交互合作来找到一个问题的方 案。以下，我们以t s p 问题为研究模型，用蚁群算法来求解得出一个较优解。 其主要的思想是让一些称之蚂蚁的a g e n t 通过以弗洛蒙为媒介的间接的全局的 通信来寻找t s p 耐题中的最优方案。不正式地说，每个蚂蚁以交互方式得出一 个t s p 方案：它通过从过去得来的信息和贪婪启发式来为某一方案增加新的城 市。记忆代替了被蚂蚁在t s p 边上释放的弗洛蒙，而启发式信息可以被简单地 赋予一个边长。 蚁群按照如下原理工作：m 个蚂蚁位于按照某种初试化条件( 如随机的) 在n 个城市中选择一个城市。每只蚂蚁重复应用随机贪婪法则( 状态转移法则) 构建一个巡游( t s p 问题合理的方案) 。在巡游过程中，蚂蚁将应用局部更新 准则修改其所访问的边上的弗洛蒙的量。一旦所有蚂蚁完成了它的巡游，每条 边上的弗洛蒙的数量将被再次修改( 通过全局更新法则) 。在蚁群系统中就是 这样。在巡游过程中，蚂蚁被两种信息所引导。一是启发式信息：它们倾向于 选择较短的边；另一个是弗洛蒙信息；一条有更多弗洛蒙的边总是被优先选择 的。该算法在图2 2 中给出。下面，我们将讨论状态转移法则，全局更新法则， 9 坝卜论义多智能机器人系统任务分配与协作 局部更新法则。 l o o p 每只蚂蚁位于一个开始节点 l o o p 每只蚂蚁各自运用状态变化法则逐步构建出一个解， 同时局部更新法则 u n t i l 所有蚂蚁都构建出一个完整的解 运用全局更新法则进行全局更新 u n t i l 达到结束条件 图2 2t s p i 问题蚁群算法流程图 a a c s 状态转移法则 在a c s 中状态转移法则如下：位于结点r 的蚂蚁根据如下所给出的法则( 公 式2 i ) 来选择城市s 前往。 a r g 妻缘) 1 ( 【f ( 删) m ) r j i f q q 。 s o l h e r w i s e ( 2 1 ) 等式中t 是弗洛蒙，n = 1 8 是距离6 ( r ，s ) 的倒数，j k ( r ) 是在城市r 的蚂蚁k 为使方案合理还要访问城市的集合，b 是一个用来决定与距离相对的 弗洛蒙的相对重要性的参数( 8 ) 0 ) 。在等式中我们将边( r ，s ) 上的弗洛蒙和其 相对的启发式值n ( r ，s ) 相乘。 这里q 是一个均匀分布在0 l 之间的随机数，q 。是一个参数( 0 q 。1 ) 。 当q q 一，时我们总是选取离当前所在节点最近且弗洛蒙最多的下一个节点否 则，我们将用公式2 2 来选定下一个城市。 p k ( t j ) 2 陋剑：随! ! 鲎 ，硼 h ( ，“) r h e ( r ) 0 i fs 五( ，) ( 2 2 ) o 硕卜沦立 多智能机器人系统任务分配与坍作 这个等式给出了在城市r 的蚂蚁k 选择前往城市s 的概率。我们随机得到一 个o l 之间的数，按照概率论，上式中求出的概率大的节点更有可能被选中， 通过这种方法我们支持那些更短的有更多弗洛蒙的边。 b a c s 全局更新法则 在a c s 中只有全局最优的蚂蚁( 也就是从巡游开始起构建最短回路的蚂蚁) 被允许释放弗洛蒙。这个选择，加之伪随机比例法则的应用将使搜寻变得更加 直接：蚂蚁从通过迭代算法得出的最优路径上搜寻一个邻接点。全局更新只在 所有的蚂蚁完成了它们的巡游后才执行。弗洛蒙通过应用公式2 3 得出的全局 更新法则被更新。 f ( ，s ) 一( 1 一a ) f ( ，s ) 十积- a f ( n s ) i( 如r i f ( ，+ ，j ) g l o b a l b e s t - t o m w h e r e 一，j s ) = ( 2 3 ) 【 oo t h e x w i 跹 0 1 0 一 9 一 4 2 一 3 一 1 - 5 - 6 一 8 长度为9 1 0 5 。 接着我运用遗传算法进行实验： l 、编码方式 采用巡回路线所经过的各个城市的顺序进行编码城市以阿拉伯数字代表 如： x l ：1 2 3 4 5 6 7 8 9 x 2 ：3 4 5 7 6 8 9 1 2 2 、交叉方式 采用部分映射交叉( p m x ) 3 、变异算子：交换变异 4 、适应度函数：n l e n g t h ( t ) ：城市规模为1 0 ： 5 、运行参数： m ：群体规模为2 0 ； t ：进化代数位2 0 0 ； p c ：交叉概率为o 7 ； 2 塑主堡苎 兰塑! ! 垫堂查墨堕堡墨坌望兰塑笪 p m ：变异概率为0 1 ： 实验结果路径为1 5 一 9 4 一 3 1 0 一 7 一 6 一 2 8 一 1 ，巡游长度为1 4 4 8 2 。 根据以上两个实验可以看出，蚁群算法相比遗传算法就求解t s p 问题上 拥有较高的效率，性能较为优越。 2 4 蚁群算法在组合优化中的应用 蚁群算法作为一种新的仿生启发式优化算法，它在解决许多复杂组合优 化问题方面，显示出了明显的优势。 蚁群算法主要用于求解不同的组合优化问题，一类应用于静态组合优化 问题，另一类用于动态组合优化问题。静态问题指一次性给出问题的特征，在 解决问题过程中，问题的特征不再改变。这类问题的范例就是经典旅行商问题 ( t s p ) ：动态问题被定义为一些量的函数，这些量的值由隐含系统动态设置。 因此，问题在运行时间内是变化的。而优化算法须在线适应不断变化的环境。 这类问题的典型例子是网络路由问题。 2 4 1 在静态组合优化中的应用 ( 1 ) 旅行商问题( t s p ) ：蚁群优化算法首先应用于一个测试问题就是旅行 商问题。t p s 问题是组合优化中研究最多的np l h a r d 问题之，该问题就是 寻找通过n 个城市，各1 次且最后回到原出发城市的最短路径。许多研究表明， 应用蚁群优化算法求解t s p 问题优于模拟退火法、遗传算法、神经网络算法、 禁忌算法等多种优化方法 ( 2 ) 二次分配问题( o a p ) ：二次分配问题是指分配r t 个设备给n 个地点， 从而使得分配的代价最小，其中代价是设备被分配到位置上方式的函数。q a p 是继t s p 之后蚁群算法应用的第一个问题，实际上，o a p 是一般化的t s p 。 ( 3 ) 车间任务调度问题( j s e ) ：j s p 问题指已知一组m 台机器和一组t 个 任务，任务由一组指定的将在这些机器上执行的操作序列组成。车间任务调度 问题就是给机器分配操作和时问间隔，从而使所有操作完成的时间最短，并 且规定两个工作不能在同一时间在同一台机器上进行。c o l o r ni ，d o r i g o 等 人将蚂蚁算法应用于车问任务调度问题。 混流装配线问题：混流装配线是j i t 生产方式的具体应用之一，它可以 在不增加产品库存条件下满足用户多样化的需求。混流装配线有时也特指混合 车型组装线，即在一定时问内，在一条生产线上根据顾客需求的变化生产出各 种不同型号的产品，这一类问题同属生产调度问题。 硕士论文 多智能机器人系统任务分配与协作 ( 4 ) 车辆路线问题( v r p ) ：v r p 问题来源于交通运输。已知m 辆车，每辆 车的容量为d ，目的是找出最佳行车路线在满足某些约束条件下使得运输成本 最小。 ( 5 ) 图着色问题( g c p ) ：已知一个图g = ( n ，e ) ，g 的一个q 个颜色的 着色是一个映射c ：n 一 l ，q 使得如果( i ，j ) e ，则c ( i ) c ( j ) 。6 c p 就是找出图g 的一种着色从而使得所使用的颜色数量q 最小。c o s t a 和h e i t s 提出使用两条外激素轨迹解决图着色问题。 ( 6 ) 有序排列问题( s o p ) ：给定一个有向图，图上的弧和节点都加了权， 服从于节点间先后次序的约束，s o p 指在有向图上找出一个最选权值的哈密顿 路径。s o p 是n p 难题，它以许多工程实际问题为模型，如有着接载和运送乘客 约束的单车选路径问题，生产计划以及柔性制造系统中的运输问题等。g a f 【i b a r d e l l a 和d o r i g o 应用扩展的蚂蚁算法解决s o p 。 2 4 2 在动态组合优化中的应用 在动态组合优化问题中，通讯网络是一个典型例子。网络优化问题有一些 特征，如信息和计算分布，非静态随机动态，以及不同时的网络状态更舐等。 路由是网络控制中最关键的组件之一，它涉及到建立和使用路由表来指导数 据通信量在网络范围内的分配活动。普通路由问题可以理解为是要建立一个路 由表使得网络性能的一些量度最大化。 ( 1 ) 有向连接的网络路由：在有向连接的网络中，同一个话路的所有数 据包沿着一条共同的路径传输，这条路径由一个初步设置状态选出。在国际上 s c h o o n d e r w e r d 等人首先将a c o 算法应用于路由问题。后来，w h i t e 等人将a c o 算法用于单对单点和单对多点的有向连接网络中路由，b o n a b e a u 等人通过引 入一个动态规则机制改善a c o 算法。d i c a r o g y 、d o r i g o 研究将蚁群算法用于 高速有向连接网络系统中，达到公平分配效果最好的路由。在国内张素兵、刘 泽民等人提出了基于蚂蚁算法的q o s 路由调度方法及分段q o s 路由调度方法。 ( 2 ) 无连接网络系统路由：在无连接或数据包中，同一话路的网络系统 数据包，可以沿着不同的路径传输，在沿着信道从源节点到终节点的每一个 中间结点上，一个具体决策是由局部路由组件做出。随着i n t e r n e t 规模不断 扩大，在网络上导入q o s 技术，以确保实时业务的通信质量。q o s 组播路由的 目的是在分布的网络中寻找最优路径，要求从源节点出发，历经所有的目的 节点，并且在满足所有的约束条件下，达到花费最小或达到特定的服务水平。 在分析路由问题时，为方便可将网络看成无向带权的连通图，顾军华等人用蚂 蚁算法研究解决包含带宽、延时、延时抖动、包丢失率和最小花费等约束条件 顿i 论义多智能机器人系统任务分配t j 协作 在内的q o s 组播路由问题，效果优于模拟退火算法及遗传算法。【5 】 蚁群算法本质上构成了一个多智能体的复杂适应系统。蚂蚁行为的实质 是简单的自组织行为体现出来的群体行为。每个蚂蚁行为对环境产生影响， 环境的改变影响着蚂蚁的群体行为。蚂蚁个体之间、群体之问以及与环境之 间的相互作用、相互影响、相互协作，可以完成的复杂的任务，这种适应性 表现为蚁群算法的鲁棒性。自组织使得蚂蚁群体的行为趋向结构化，其原因 在于包含了个正反馈的过程。这个过程利用了全局信息作为反馈，正反馈 使系统演化过程中较优解的自增强作用，使得问题的解向着全局最优化的方 向不断变化，最终能有效地获得相对较优解。蚂蚁系统的另个重要特征是 分布式计算，这种分布式计算方法保证了算法在全局的多点同时进行解的并 行搜索，有效地避免了陷入局部最优解。 虽然蚁群算法具有较强的鲁棒性、通用性、并行搜索等优点，但也存在着 搜索时间较长，在算法模型、收敛性及理论依据等方面还有许多工作有待进一 步深入研究。此外，将蚁群算法与遗传算法、免疫算法等优化方法相结合，也 是改善和提高蚁群算法性能的有效途径。 2 5 本章小结 本章首先介绍了蚁群算法的生物学原理，然后构造出蚁群算法来求解t s p 问题。就求解t s p 问题的效率来看，蚁群算法与遗传算法、模拟退火算法等 启发式算法相比较有较优的性能。最后，介绍了蚁群算法在其它领域中的运 用。 碗】j 论文 多智能机器人系统任务分配与协作 3 静态环境下多机器人之间的协作 随着市场经济的发展和物流技术专业化水平的提高，物流配送业得到了 迅猛发展。物流配送是指按用户的订货要求，在配送中心进行分货、配货，并 将配好的货物及时送交收货人。在物流配送业务中，存在许多优化决策问题 我们讨论其中的物流配送路径优化问题，即通过制定合理的配送路径，快速 而经济地将货物送达用户手中。配送路径的选择是否合理，对加快配送速度、 提高服务质量、降低配送成本及增加经济效益都有较大影响。 研究表明，配送路径优化问题是一个np 难题，只有在需求点和路段较少 时，才能求得精确解。因此，用启发式算法求解该问题就成为人们研究的一个 重要方向并出现了多种启发式算法，如c l a r k e 和w r i g h t 提出的节约法 g i l l e t t 和m i l l e r 提出的扫描法等，虽然这些算法为求解配送路径优化问题 提供了有效的方法，但也存在一定的问题，如节约法虽然具有运算速度快的 优点，但也有组合点零乱、边缘点难以组合的问题，扫描法为非渐进优化等。 如何针对物流配送路径优化问题的特点，构造运算简单、寻优性能优良的启发 式算法，是一个值得深入研究的课题。 3 1物流配送路径优化问题的数学模型 物流配送路径优化问题可以描述为：从配送中心( 物流据点) 用多辆汽车 向多个需求点( 顾客) 送货，每个需求点的位置和需求量一定，每辆汽车的载 重量一定。要求合理安排汽车路线，使总运距最短，并满足以下条件： ( 1 ) 每条配送路径上各需求点的需求量之和不超过汽车载重量： ( 2 ) 每条配送路径的长度不超过汽车一次配送的最大行驶距离： ( 3 ) 每个需求点的需求必须满足，且只能由一辆汽车送货。 设配送中心有k 辆汽车，每辆汽车的载重量为qk ( k = 1 ，2 。，k ) ，其 一次配送的最大行驶距离为dn ，需要向l 个需求点送货，每个需求点的需求 量为q 。( i = 1 ，2 ，l ) ，需求点i 到j 的运距为d 。，配送中心到各需 求点的距离为do j ( i 、j = l ，2 ，l ) 。再设n k 为第k 辆汽车配送的需求 点数( n k = 0 表示未使用第k 辆汽车) ，用集合rk 表示第k 条路径，其中的 元素r ki 表示需求点r tt 在路径k 中的顺序为i ( 不包括配送中心) ，令r “o = 0 表 示配送中心，则可建立如下物流配送路径优化问题的数学模型【4 】 硕：b 论文多智自 机器人系统任务分配与协作 st 昂q t ) 十d 锄s 适l l0 i ) 】 孕训) + d 撕s 如( 片t ) d t 暑舻工 足= ( m l 腑( 1 2 、l ) 。产i ，2 ，h 砖 r l ln 矗1 2 = o ( v k t 七：) 蛐扣b 麓： ( 31 ) ( 32 ) ( 3 3 ) ( 34 ) ( 3 5 ) ( 36 ) ( 3 7 ) ( 3 8 ) 上述模型中，公式3 1 为目标函数，既要求得到最短路径。公式3 2 保证 每条路径上各需求点的需求量之和不超过汽车的载重量：公式3 3 保证每条 配送路径的长度不超过汽车一次配送的最大行驶距离：公式3 ，4 表明每条路 径上的需求点数不超过总需求点数：公式3 5 表明每个需求点都得到配送服 务：公式3 6 为每条路径的需求点的组成：公式3 7 限制每个需求点仅能由 一辆汽车送货：公式3 8 为当第k 辆汽车服务的客户数1 时，说明该辆汽车 参加了配送，则取s i g n ( n ) = 1 ，当第k 辆汽车服务的客户数 一一一o 、 ! 、 、 ? 、一。2 川j + 9 、孑 幽3 3 经过部分配送喊虚拟配送中心 硕卜论义多智能机器人系统任务分配与掷作 3 ) 、只经过一个配送或虚拟配送中心：巡游路径为1 4 5 3 2 6 7 8 ，在这种情 况下巡游结束，此时只用到一辆车。巡游路径为8 ( 0 ) 1 4 5 3 2 6 7 8 ( 0 ) 。 图3 4 只经过一个目e 送或虚拟配送中心 当一只蚂蚁被放置在物流配送中心时，同样由于上述原因，也可能出现 以下几种情况： i ) 、除了起点和终点不经过其它配送中心或虚拟配送中心：巡游路径 0 1 3 2 4 7 5 6 8 ，在这种情况下巡游结束，共用了一辆车路径为0 1 3 2 4 7 5 6 8 ( 0 ) 。 。，8j 9 卜少5 、 io - j 幢，、3 j ：。 、“1 1 2 ) 、除了起点和终点还经过某些其它配送中心或虚拟配送中心：巡游路 径为0 1 3 2 4 9 7 5 6 8 ，在这种情况下巡游结束，共用了两辆车，路径为0 1 3 2 4 9 ( 0 ) 、 9 ( 0 ) 7 5 6 8 ( 0 ) 。 8 7j 、 广少3 kk 。3 l， 图3 6 除了起点和终点还经过某些其它配送中心或虚