1.1 目的及意义

随着机器人技术的发展，机器人应用领域越来越广泛。由于电子商务快速崛起，网络购物等促使物流变的更加频繁，使得仓储物流越来越庞大。仓储系统是对物流中暂时处于停滞状态的物资进行保管的物流系统，是物流运作中不可或缺的一个重要环节。在现代物流系统领域，随着物料运输工业的不断发展，仓储规模不断的扩大，将机器人引进仓储系统是物流发展的必然趋势。

为了提高分类拣选效率，越来越多配送中心和物流仓储采用了自动化方式管理。在这个过程中，使用多机器人完成拣选任务很明显比单机器人具有更大优势。首先，在物流系统中某些任务不是单个机器人能够完成的，例如某些货物的质量特别大，如果设计一个专门针对重物的搬运机器人，从机器人设计的复杂性和实用性来看，这种设计很明显不如多个机器人搬运更加合理，而且某些机器人系统，例如足球竞赛机器人，很明显不是单个机器人能够完成的；其次，对于某些任务场景，例如探索地形和物流运输，单个机器人的用时是多机器人的几倍甚至几十倍，使得时间成本大幅度增加，这在物流和救灾这种场景中，很明显是致命的；最后，有些任务是完全不同的，需要机器人具有各种不同功能，如果将这些功能全部集成到一个机器人上，设计的复杂性会大幅度提升，而如果将多个功能分别设计到不同的机器上，不仅设计的复杂性会降低，完成多个任务的效率也会提高。例如亚马逊在2012年收购了自动化物流提供商Kiva的机器人仓储业务，自主机器人的数量达到了10,000个，Kiva让货架“走到”取货者前，方便取货省分珠，减少了不必要劳动，并让整个物流过程更加自动化，从而节省了大量人工成本并提高了效率；在国内富士康也在2012年将一万个“Foxbots”运用到了生产中，不同种类的机器人多达十种，用来完成不同任务。这些都是多机器人系统在仓储物流中的实际应用。

二十世纪九十年代以来，人工智能的发展推动物流仓储系统向智能化方向发展，即智能仓储。智能仓储系统是典型的多智能体系统，它运用大量具有负载能力的智能移动机器人，将传统的“人找货物”思想转变为“货物到人”，具有节约劳动力，作业迅速准确等特点，极大地提高了仓储业的服务效率和服务质量，对提高整个仓储的运行效率和经济效益具有深远意义。

目前，智能仓储系统还处于发展阶段，还有很多需要改进的问题。仓储系统的智能化是顺应时代发展的，将具有广阔的运用前景。

1.2 内外的研究现状分析

1.2.1 多机器人任务分配问题的研究现状

任务分配问题存在于社会生活的多个领域。在对任务分配问题的早期研究成果中，结合分布式人工智能的任务分配研究成为主要的研究趋势。

任务分配是多机器人系统的关键模块之一，任务分配机制决定着每个仓储机器人的任务选择(Navdeep K Singly 2008 ) 。多机器人任务分配问题是多机器人系统实现最终目标的基础，体现了多机器人系统的高层组织形式和运行机制 (张嵛等，2008)。同时，任务分配问题是多机器人系统的设计与应用中的基本问题之一，是整个多机器人系统畅通运行的基础(周菁等，2014)。可以把多机器人任务分配问题看作是调度问题、最优分配问题(OAP )、网络流问题、整数线性规划问题和组合优化问题(GERKEY B P,2003)，通常被认为是NP-complete问题(Lagoudakis M et al, 2004 )。

多机器人任务分配本质上是一种动态任务分配的过程(么立双等，2013)在静态环境中，由于机器人探索的环境信息量相对较少，且环境信息相对固定，各机器人之间主要通过静态环境信息和子任务信息传递通信内容。如果将整个多机器人系统完成全部任务所需移动的总路径长度作为评价任务分配的最优指标，则多机器人任务分配问题可归结为求解各机器人起点和终点不一定相同的多旅行商问题(蔡自兴等，2011)。在动态环境中，Brian和Mataric等著名学者提出了动态任务分配问题，认为在多机器人系统中工作环境、任务出现的时间和空间位置等均具有动态不确定性(Brian et al, 2004)。无论在静态环境中，还是在动态环境中，各机器人都是在执行任务的动态过程中发现新任务。

1.2.2 多机器人任务分配方法的研究现状

多机器人任务分配与多机器人系统的组织结构、通讯机制、协调机制、学习及感知等多方面因素紧密相关。目前，针对多机器人任务分配方法主要从集中式任务分配方法和分布式任务分配方法两个方面进行研究。

1. 集中式任务分配方法

在多机器人任务分配问题的最初发展阶段，大部分采用集中式任务分配方法。在多机器人系统中，首先由一个中央控制系统负责收集周围相关环境信息，然后将一个大任务分割成若干个子任务，最后分配各机器人去完成相应子任务。其中基于匈牙利算法的任务分配方法是比较具有代表性的集中式任务分配方法。该方法虽然能够成功得到全局最优分配方案，实现机器人个体之间行动的紧密协调和最优协调，但是为完成任务往往需要收集所有机器人和所有任务的详细环境信息，并且仅仅只有一个中央控制系统来处理这些信息，因此当智能系统内机器人数量越多或任务规模越大时，其系统扩展性能就越差，效率也随之降低。