摘 要

人工智能的快速发展以及其向各个领域的渗透使得许多新兴行业可快速发展起来，电子商务就是其中之一，但其兴起的同时也带了众多的问题。仓储物流机器人可以很有效的解决由于电子商务的快速兴起带来的发货需要速度加快等问题，而快速的找到最佳路径节省机器人运动所消耗的时间正是其关键问题所在。对于仓储物流机器人在各类仓库环境下，由初始位置到目标位置的路径规划问题，本文在基于A*算法的基础上实现了对仓储物流机器人的路径规划，介绍了A*算法中通过选取适当的代价函数来实现最佳路径的选取。在MATLAB R2016a中对该基于A*算法的路径规划系统进行仿真实验，模拟在仓库中障碍物所处位置不同的多种不同仓库环境下的最佳路径的搜索确定。该种方式直接反应出最佳路径，对于无法从初始位置到目标位置的情况，则直接返回没有找到相应路径，验证了该算法的有效性。

关键词:仓储物流 机器人 A*算法 路径规划

Abstract

The rapid development of artificial intelligence and its penetration into various fields make many emerging industries develop rapidly. E-commerce is one of them, but its rise also brings many problems.Warehouse logistics robot can effectively solve the problem of the rapid rise of e-commerce, such as the need to speed up the delivery, and quickly find the best path to save the robot movement time is the key problem.For the path planning problem of warehousing logistics robot from initial position to target position in various warehouse environments, this paper realizes the path planning of warehousing logistics robot based on a * algorithm, and introduces the selection of the best path by selecting the appropriate cost function in a * algorithm.In MATLAB r2016a, the path planning system based on a * algorithm is simulated, which simulates the search and determination of the best path in different warehouse environments where the obstacles are located.This method directly reflects the best path. If it is unable to get from the initial position to the target position, the corresponding path cannot be found directly.The validity of the algorithm is verified.

Key words : warehouse logistics robot a * algorithm path planning

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 课题的研究意义及目的 1

1.2 路径规划 2

1.3 论文的组织与结构 2

第2章 算法介绍 4

2.1 Dijkstra算法介绍 4

2.2 深度优先搜索（DFS）算法 4

2.3 最佳优先搜索（BFS）算法 5

2.4 A*算法 5

2.4.1 A*算法示例介绍 7

2.4.2 A*算法流程图 9

2.4.3 A*算法的不足之处 9

第3章 A*算法改进 11

3.1 引入权值的启发式函数 11

3.2 A*算法改进及实验 11

3.2.1改进算法具体步骤 12

3.2.2 实验结果及比较 12

第4章 模拟仿真实现及分析 16

4.1 仓库模型的建立 16

4.2不同启发式函数路径规划结果分析 17

4.3 不同权值条件下路径规划结果分析 18

第5章 结论 19

致谢 20

参考文献 21

第1章 绪论

1.1 课题的研究意义及目的

二十世纪以来，人工智能一词在人们口中出现的频率越来越高，其无法预计的研究价值掀起了一阵研究的狂潮。随着人工智能以及相关科学技术和信息产业的高速发展，机器人的相关应用与发展也越来越迅速。机器人似乎将成为未来必不可少的大众用具，其在危险性质高或是重复程度高等形式的工作上人类无法比拟的优势可以大大的改善人类生产生活的便利程度。机器人将在未来社会工作中占据越来越重要的位置，与人类生活的联系息息相关。目前，由于人工智能在各个行业的渗透使得基于人工智能的众多新型行业发展迅速。例如正在迅速发展的电商行业，网上购物或是网上下单立即送达等形式甚至超越了实体店购物以及消费成为了大多数消费者购物消费的第一选择。但行业快速发展的同时总是会涌现出各种各样的相关问题，对于迅速发展的电商行业来说，其产生的问题主要表现在人类对其相关服务的要求越来越高，发货速度以及订单处理处理速度成为了消费者选择商家的一项重要的考虑标准。对于大型厂家商家来说，良好的仓库运作情况意味着快速的出库速度，较快的订单处理速度是使得商品出库速度也迅速加快，其在同类型商家中的竞争力将大大上升。

在二十世纪五十年代出现了一种仓储物流机器人，这是一种用于智能搬运的机器人，根据订单任务所得到的目标位置从当前所处位置出发快速自主的进行最佳路径的规划可以大大的节省其在路径上消耗的时间，使得仓库工作效率也大大提升，但其目前在国内的使用率由于其出现及相关研究时间较晚而不高。但是仓储物流机器人简单灵活的操作方式、安全高效的工作形式使得其目前在国内有着广阔的需求及应用市场，因此，对于仓储物流机器人的路径规划问题也成为了一个十分值得研究的课题。

仓储物流机器人在国内得到广泛应用首先需要解决的问题即路径规划问题，可以将路径规划问题描述为：机器人在一个具有障碍物，但障碍物所处位置确定不变或变化的静态环境中对其路径根据需求进行规划，使得在该环境中，机器人可以实现以最迅速的速度无碰撞的到达目标位置。一般来说，路径规划的实现是通过高级语言编译的算法，通常可以将相应算法分为两类：非进化型和进化型。非进化型算法一般设计思路简单但同时处理效率也十分不错，但其无法在实现过程中完成自我学习并进行自我更新。进化型算法的设计思路则一般比较复杂，处理效率也不如非进化型算法，但其优势在于拥有自我学习、自我更新及记忆能力。根据算法的数学特征，又可以将非进化型算法分成经典数学与几何图论两种。经典数学类包括图搜索概率法、模拟退火算法、人工势场法、A*算法、Dijkstra算法和Floyd算法。其中，最经典的算法是Dijkstra算法，属于遍历搜索型算法。它易于使用，并且能够得到最短的路径。但是，当网络中的节点数量较大时，算法的效率将会很低。因此，人们在其基础上提出了一些启发式搜索算法，如局部最优搜索法、最优优先搜索法、A*算法等。 A*算法是1980年Peter Hart等人提出的一种基于Dijkstra算法的启发式路径规划算法，是一种基于区域的全局规划算法，属于启发式搜索的最佳搜索方法。但是A*算法在路径规划方面的计算效率较低，所选路径与最优路径有一定偏差。

1.2 路径规划

路径规划问题一直以来都是人工智能领域中的基础问题，其主要是为了解决不同但相关联区域的通路问题，路径规划的好坏直接影响着系统表现的好坏。从不同的角度考虑路径规划问题其所要求的技术指标也不相同，例如，从时间效率考虑、从空间效率考虑等。路径规划问题的解决一般可以通过三个步骤来完成：环境建模、函数构造和实际分析。首先，根据所需规划路径一般情况下的环境信息对环境进行相关模型构造，使其更加形象具体化便于后续研究，再根据所构建的环境模型进行相关函数的构造，函数的构造是路径规划问题的关键，最后，根据现实环境以及具体情况对前面的过程进行具体分析，是否达到相关技术指标。但是通常在现实情况中，所面对的环境情况一般较为复杂，人们模拟相关环境就会变的十分困难，多年以来，人们在对路径规划的探索中参考自然界的一些生物运动轨迹，提出一些相关算法，如蚁群算法等等。这些算法都有着各自的优势，但同时也存在着一些方面的不足，与传统的算法相比他们可能无法保证搜索到的路径是最优的路径，但是也正是因为这些算法的出现使得人们对路径规划的相关研究更加深入。

本文的路径规划问题是基于方形的仓库环境并在具有一定障碍物的情况下，将环境模型以及障碍物均构建为栅格图模型，寻找从某一随机位置到另一随机位置的最佳路径以及比较当初始位置及目标位置都相同时不同的代价函数下的最佳路径

1.3 论文的组织与结构

本文总共分为五章，第一章为绪论，介绍了课题的研究背景、意义、国内外研究现状以及路径规划，同时，介绍了本文的组织结构。第二章为算法介绍，介绍了A*算法及其基础Dijkstra算法，深度优先搜索（DFS）算法、最佳优先搜索（BFS）算法，同时对A*算法进行详细介绍，包括A*算法基本原理、流程图以及不同的启发式函数的选取，最后通过了具体的例子解释了A*算法的具体过程。第三章为A*算法的改进，提出了通过改变启发式函数权值的方式对A*算法进行改进的方法，并得出了改进后的模拟仿真结果。第四章模拟与仿真及分析，通过MATLAB R2016a模拟障碍物随机分布的仓库模型，随机设置初始位置及目标位置，对A*算法路径规划进行验证，并比较了在相同出发点和目标点的情况下基于不同的距离计算方式下的不同代价函数以及相同代价函数条件下不同权值时对路径规划结果的影响。

第2章 算法介绍

2.1 Dijkstra算法介绍

Dijkstra算法是A*算法的基础，Dijkstra算法是1959年荷兰科学家Dijkstra提出的一种使用贪婪算法求解单个源点到有向图中某一点的最短路径问题的经典算法，它的主要特点是从源点开始，当前节点所选择的下一个顶点是都是除了规范点之外的距离源点最近的顶点，据此不断从源点向外扩展延伸直到到达目标点，在此延伸过程中找到出发点到目标位置的最短距离。Dijkstra算法是以牺牲计算速度为代价，同时Dijkstra算法会搜索所有节点，因此其可以达到很高的精度和综合性。