摘 要

在经济全球化的大潮和互联网不断蓬勃的大背景之下，国内外电子商务规模日益庞大，仓库货物管理水平面临的压力也随之加剧，如何对传统仓库进行改造升级，使之具有更高的货物分拣能力是行业面临的一个难题。在Kiva系统影响之下，越来越多的电商中心仓库开始进行类Kiva系统的部署，该类系统不但降低了人力劳动成本，而且提高了仓库货物分拣能力。未来，智能化、无人化势必将对物流行业进行颠覆性的改变。

论文在综述国内外研究现状基础之上，对类Kiva 系统智能管控进行了整体性研究。论文将智能管控这一内容加以拆分，针对其中两大主要问题：路径规划和任务分配，提出了完整的解决方案。

对于路径规划问题，本文在静态路径规划和动态避撞策略两个维度上进行了解决，首先，针对静态路径规划，利用基于转弯次数和算法耗时影响的改进A*算法实现了初始路径的规划；针对动态避撞，建立了基于优先级规则和预约表的碰撞机制，解决了多机器人的碰撞问题。对于任务分配问题，本文基于拍卖算法提出了两种不同的实施流程，一种是将任务当成拍卖资源，另一种是将机器人当成拍卖资源，解决了多机器人的任务分配问题。

最后通过对方案进行了仿真研究和横向对比，证明了方案的可行性并给出总结展望与经济性分析。

关键词：类Kiva系统；智能管控；A*算法；拍卖算法

Abstract

Under the tide of economic globalization and the continuously booming of Internet, electronic commerce is more and more tremendous in both domestic and abroad. Faced with the growing requirements of e-commerce, how to upgrade the traditional warehouse and make higher cargo sorting capacity is an industry question. Since Kiva system spread in warehouse, more and more e-commerce centers begin to deploy Kiva-like systems. Such systems not only reduce labor costs, but also improve the sorting capacity of warehouse goods. In the future, Intelligent and unmanned systems are bound to overturn the logistics industry.

On the basis of summarizing the research status at domestic and abroad, this paper conducts an overall research on the intelligent control of Kiva-like system. By separating the content of intelligent management and control, a complete solution is put forward for two major problems: path planning and task allocation.

For the path planning problem, this paper solves it through two dimensions: static path planning and dynamic collision avoidance. Firstly, the improved A* algorithm is adopted to carry out the static path planning, which is based on the influence of turning times and algorithm running time. Then, under the dynamic environment, the priority rules and appointment table are combined for collision avoidance. For the task allocation problem, this paper put forward two implementation processes based on auction algorithm. One is to take the task as the auction resource, and the other is to take the robot as the auction resource, through these algorithms, task allocation problem is solved.

Finally, the feasibility of the scheme is proved by simulation and comparison, then the summary and the economic analysis is given.

Key Words: Kiva-like system; intelligent control; A* algorithm; auction algorithm

目录

摘要 I

Abstract II

第1章 绪论 1

1.1 研究背景和意义 1

1.2 国内外研究现状 2

1.2.1 路径规划国内外研究现状 2

1.2.2 任务分配国内外研究现状 3

1.3 研究目的及内容、技术路线及论文结构 5

1.3.1 研究目的及内容 5

1.3.2 技术路线 5

1.3.3 论文结构 6

1.5 本章小结 7

第2章 仓库环境建模 8

2.1 Kiva系统简介 8

2.2 仓库环境设定 9

2.3 仓库作业流程设定 11

2.4 本章小结 11

第3章 路径规划问题研究 12

3.1 算法介绍 12

3.1.1 常用距离概念 12

3.1.2 A*算法 12

3.2 路径规划总体思路 13

3.3 静态路径规划 15

3.3.1 问题建模 15

3.3.2 传统A*算法静态路径规划 16

3.3.3 改进A*算法静态路径规划 16

3.4 动态避撞机制 18

3.5 本章小结 21

第4章 任务分配问题研究 22

4.1 算法简介 22

4.1.1 拍卖类型 22

4.2.2 拍卖算法 22

4.2 机器人分配模型 23

4.3 基于拍卖算法的任务分配 23

4.3.1 投标设计 23

4.3.2 匹配机制 25

4.4 本章小结 27

第5章 仿真与分析 28

5.1 仿真环境搭建 28

5.1.1 程序框架 28

5.1.2 环境初始化 29

5.2 仿真分析 30

5.2.1 参数设定 30

5.2.2 静态路径规划仿真 31

5.2.3 动态避撞仿真 34

5.2.4 任务分配仿真 38

5.3 本章小结 40

经济性分析 41

总结与展望 42

致谢 45

第1章 绪论

1.1 研究背景和意义

在现在物流活动中，每一块都是不可或缺的，而仓储物流则是影响着整个物流活动的关键一环。配送中心是仓储物流的重要构成，其货物处理能力和效率深刻影响着整体物流体验。随着近年来货物流量不断攀升，配送中心迎来越来越大的物流挑战。为了提高配送货物拣选速度并节省人力，越来越多配送中心开始采用自动化手段处理订单作业，从“人到货”形式慢慢转变成“货到人”形式。

目前在配送中心应用比较成熟且自动化程度较高的是自动化立体仓库，一般都由分拣机、堆垛机和长距离输送设备等构成。此类搭配固然能提高效率，但占地面积大、配套设施多，一次性资金投入大且缺少柔性和灵活性。

近年来以Kiva MFS系统（为Kiva Systems公司推出，后被亚马逊收购，改名为Amazon Robotics）为代表的基于移动机器人的自动化仓储形式开始兴起，为行业提供了一种新的高度柔性化的智能物流解决方案。该类系统采用活动式货架结构和移动机器人来处理传统货物拣货和分拣过程，一套Kiva MFS系统包含上万个可移动活动式货架和上百个Kiva移动机器人，根据订单信息，Kiva机器人将装载着目标货物的货架运输至工作台，执行分拣和包装等工作。

不同于传统AGV设备依赖线圈、导线的方式，Kiva机器人通过读取地上视觉记号进行运动规划，极大提高了机器人的活动范围和灵活性^[1]。Kiva机器人之间及与控制器之间都通过无线网络进行通信连接，结合一定的软硬件结构，实现了智能高效的拣货操作，极适合于货架灵活性要求高，多品种、小体积、低重量货物的仓储场景。

在Kiva机器人应用于仓库并取得显著成效后，类似Kiva MFS系统的思路得到大量关注和研究，也引发从业者对行业新的认识和考量，Kiva只是“货到人”的一种，未来机器人在物流行也前景无限，可能将彻底改变整个物流业^[2]。近些年随着国内经济的稳步发展，物流业迎来了繁荣发展。在去年双十一期间，即便在中美贸易摩擦影响下，仅阿里系淘宝天猫平台就超过了2000亿人名币，国内的消费能力和潜力可见一斑，随之而来的便是对物流更高的效率要求。随之国内类Kiva机器人迎来蓬勃发展，不断推陈出新，各类智能仓储机器人公司相继涌现，以Geek （极智嘉）、海康威视、快仓、牧星智能等品牌为主，广泛应用于苏宁、唯品会、京东、一汽大众等公司。

尽管国内类Kiva机器人系统的发展已初具规模，并在众多企业仓库中得到部署，但对于该类系统的关键技术——机器人的智能管控还处于继续探索和不断改善期间，随着大数据、机器学习的不断发展，更多新技术会在该领域得到应用。论文以类Kiva机器人系统为背景，研究了仓库系统中路径规划和任务分配两大问题，提出了完整的解决方法，有着一定的应用价值和现实意义。

1.2 国内外研究现状

对于类Kiva多移动机器人的管控工作，主要集中于两大块内容：任务分配与路径规划。任务分配负责将仓库需求任务化、数字化并高效地分发至对应的机器人，使机器人承担起具体的分拣任务；路径规划则是关于机器人如何在仓库中确定各段运动的具体执行路径，力求确定效用（通常通过机器人运行时间或运行步数表达）最大的实现形式完成任务，并有效处理移动机器人之间的碰撞问题。

1.2.1 路径规划国内外研究现状

随着科学发展和技术更新迭代，机器人技术日趋成熟，由此而衍生出一系列与智能机器人相关的研究问题，其中路径规划是许多学者的重点研究内容。

近年来，路径规划问题已经取得许多较为成熟的研究成果，其中，关于算法的研究尤其突出。A*算法是一种较为典型的图类搜索算法，其基本思想是通过增加启发式的估计信息，有效缩小求解空间，从而大幅度提升算法的全局搜索速度。D*算法同A*算法类似，通过维护一个有限队列来对场景中的路径结点进行搜索，其不同之处在于D*算法是通过逆向方式进行搜索求解的，即搜索的起始位置从目的地开始，并非以起始位置作为初始搜索点，通过将目标点置于队列中开始搜索，直到机器人当前位置节点由队列中出队为止。

Kuffner和LaValle结合RRT（快速拓展随机树）和启发式算法提出了一种单查询路径规划的随机化方法RRT-connect算法，并从理论上证明了其概率完备性，可用于7自由度机器人手臂的运动^[3]。S.Karaman和E.Frazzoli提出了RRT的改进型算法RRT*，引入了对新生成结点相邻结点的搜索，并重新布线进一步减少了路径代价^[4]。近年来，各种类型的仿生智能算法成为学术界研究重点，其中尚梦雨针对无人机的实时路径规划问题，对蚁群算法进行了一定改进，使得无人机能在短时间内对路径变化做出相应反应，有着较高实时性^[5]。

此外，随着各界学者对深度学习算法的深入研究，针对路径规划问题的深度学习算法逐渐形成了一种新的研究领域。祖丽楠等人以多机器人避障问题作为核心内容，首先将机器人的行为进行分解，形成一系列较为简单的行为，然后让机器人在离线情况下进行独立学习，最后对不同层次的结构和参数进行了特别界定，从而设计出了一种分层强化学习算法^[6]。窦佳佳对强化学习在智能仓储中的应用进行了研究分析，通过遗传算法和强化学习实现了仓库机器人的任务分配和路径规划^[7]。Chen、Everett等人通过深度强化学习提出了一种分散式非通信多机器人避碰算法，建立了一个价值网络，该网络能对给定机器人和其附近机器人（位置和速度）条件下的估计时间进行编码，并将强化学习的决策由在线计算转到离线学习过程，实现了非通信条件下的多机器人协调避碰^[8]。

1.2.2 任务分配国内外研究现状

多机器人任务分配问题（MRTA，multi-robot task allocation）作为近年来研究的热点，许多文献对这方面进行了研究。MRTA研究如何将任务在多机器人间实现有效分配，既将任务集向机器人集映射的过程，可以看作调度问题、线性规划问题、网络流、博弈论、组合优化问题和最优分配问题（OAP）等不同形式来进行分析和求解^[9]。

Gerkey将MRTA问题进行了深入的介绍^[10]，并做出了形式化的分析。首先定义了MRTA问题中的效用，效用基于每个机器人执行一个操作的价值（或成本），随后将MRTA问题进行了分类，按照任务、机器人和分配延时性三个维度一共分成了八类，如表1.1所示，其中ST表示一个任务由一个机器人完成，MT表示一个任务由多个机器人完成，SR表示一个机器人同时只能接收一个任务，MR表示一个机器人同时能接收多个任务，IA表示瞬时分配，TA表示延时分配。

表1.1 任务分配种类

在MRTA问题的研究中，早期主要以集中式算法为主。在集中式任务分配中，每个机器人都和控制器建立连接，通常为WIFI无线网络连接，该连接负责将任务分配给机器人队列，独立的机器人将所拥有的所有信息发送至中央控制器，而中央控制器反过来处理这些信息并向机器人队列发送适当的命令来执行任务的分配。集中式任务分配是由一个主机器将任务分配给一个机器人集合，属于组合优化问题，利用全局信息进行静态分配。解决算法以单纯形法和匈牙利法为主。

虽然集中式系统得到了广泛实现，但在MRTA问题中存在着许多缺点。在问题规模不大时集中式系统能够迅速找出最优解，但随着问题规模增大，运算量会迅速增长，使得对机器人的任务分配存在高延时的问题；由于所有控制和计算任务都依赖于中央控制器，集中式系统存在着健壮性不够、单点瓶颈等问题；此外，系统的可伸缩性也收到限制，由于中央控制器的处理能力限制，使得系统对机器人数量的承受能力有限，无法满足数量庞大的机器人队列。因此，当机器人和任务数量较少，且环境是静态或全局状态信息容易获得时，集中式是最适合的解决方案。集中式系统是文献中广为应用的解决任务分配问题的方法之一^[11]。Coltin等人为了将任务分配给移动设备，提出了一种集中式算法来解决MRTA问题^[12]。Kartal等人提出了一种新的集中式方案，用例基于随时采样的蒙特卡洛树搜索，使用上置信区间（UCB）来平衡探索和利用，证明了带UCB的蒙特卡洛树收敛于有限层问题的最优解^[13]。

分布式系统是中央控制器在机器人间分散管理任务和权限的过程，分布式任务分配中，规划分配的权利被赋予给只具有局部信息的单个机器人，机器人通过传感器信息来进行决策和规划。在此类系统中，每个机器人都直接与其它机器人进行信息通信，每个机器人都具有高度自主性，可以独立工作，只需间或与其它机器人进行任务和控制信息的交换，便可与其它机器人进行协调高效完成任务。分布式系统的主要优点就是健壮性，即在分布式系统中，如果一个机器人出现故障，其它机器人仍可独立工作并与剩下的机器人进行协作。由于没有集中控制的瓶颈，系统可以在出现故障是添加新的机器人，这也意味着可扩展性不再是分布式系统的问题。综合而言，相对于集中式系统，分布式系统具有多种优势，如灵活性、健壮性、低延时和较低的通信需求。然而，由于一个好的局部解决方案可能不是一个好的全局性解决方案，分布式系统可能产生的是次优的解决方案。

对于MRTA问题，主要合同网、拍卖算法、基于群体的智能算法等方法。拍卖算法由Bertsekas提出^[14]，通过价格设定来进行匹配工作。Giordani等人提出了匈牙利法的分布式实现^[15]。Choi和Brunet提出了两种分布式拍卖的算法，即基于协商的拍卖算法和基于协商的捆绑算法，来解决自主移动机器人车队的MRTA问题^[16]。Trigui等人提出了两种基于市场的分布式分配算法来解决个机器人竞争个任务的分配问题^[17]。 Michael等人对通讯受限下多机器人的任务分配问题进行了研究^[18]，给出较常用的6种不同方式拍卖算法，在该场景下进行了仿真和实际实验，对比了该类场景下各算法的性能优劣。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：