搬运机器人行走路径图建模及搜索算法

邱源　邱胜海

摘 要：该文研究了制造车间物料搬运机器人行走路径图建模的过程及使用Dijkstra算法求解最短路径方法，描述了物料搬运机器人的构成及行走原理，结合一个具体的曲轴零件加工车间机床设备布局，用图数据库进行行走路径图建模，并应用Dijkstra算法实现了图路径搜索，实践表明图数据库建模具有简单性和易学性，对解决复杂机器人的行走路径建模提供一种新的解决方案。

关键词：搬运机器人 行走路径 图数据库建模 Dijkstra算法

中图分类号：TP319 文献标识码：A 文章编号：1672-3791（2017）02（b）-0255-02

近年来，为了适应激烈的市场竞争，各制造企业纷纷购置高水平的数控加工设备、物料搬运机器人等辅助设备来提升产品的生产效率，使得各制造企业的物料自动化的程度不断提升，这有助于我国实施“中国制造2025”。据资料统计：在物料的整个生产过程中，用于加工与检验环节的时间仅占5%，而其余95%的时间则处于储存、装卸、输送和等待状态，而制造成本的20%～40%直接与物流环节的流通时间相关[1]。物料搬运机器人作为物料运输自动化的重要设备在国外应用比较广泛，尤其在欧美等发达国家，发展迅速，应用广泛，而亚洲日本韩国的发展技术水平、装备数量及自动化程度等已经达到标准化、系列化生产的程度。在我国，由于劳动力成本低和工厂自动化程度低等因素，研究起步慢，近年来，随着市场的需求提高，我国在物料搬运设备的设计制造等方面的投入逐步提高[2]。许多学者在机器人的路径规划研究中提出了先进算法，如在全局路径规划中常用的算法有图论算法、A*启发式算法、最短路径算法等；局部路径规划中常用的算法有遗传算法[3-4]、蚁群算法等，该文结合最短路径算法对搬运机器人的全局路径进行建模及搜索应用。

1 搬运机器人简述

物料搬运机器人是制造车间物流系统的重要组成部分，是配置有电磁感应或光学感应等自动导引装置，能够沿事先设计的路径行走，具有安全保护以及各种装卸功能的自动设备，且大多数以轮式行走为主，比步行、爬行等非轮式的移动机器人行动更快捷、工作效率更高，且结构简单。近年来，技术相对成熟的RFID技术应用在机器人上降低了成本，并使得路径规划更柔性。常见的物料搬运机器人是由车架、蓄电池（含充电装置）、控制单元、驱动单元、转向装置（脚轮，可双向行走）、传感引导装置（导航传感器、地标传感器、地板磁条等）以及物料装卸装置等构成。

其行走原理描述为：搬运机器人通过控制单元接收到控制计算机的行走到某目标点命令时，先将自己的位置状态发送至控制计算机，由控制中心计算机根据事先设置的路径搜索目标点的位置，计算并发出机器人需要前进还是后退的命令，由机器人控制单元接收命令通过驱动单元控制自己前进或后退，机器人的运动方向由导航传感器与地板磁条相配合，当转弯时，由脚轮旋转控制，当通过某个机床设备时，地标传感器检测到该设备，并将测到的设备信息发送给控制计算机，判断如果不是目标设备，则通知机器人继续前进，如果是目标设备，则通知机器人停止运行，准备装卸物料。

2 行走路径图建模

制造车间中的搬运机器人行走路径与设备的布局关系密集，既要保持设备的物流高效通畅，又要保持搬运的安全性，其路径规划是指在具有障碍物的车间环境中，根据工艺路线，按照一定的评价标准（如行走路径最短、转弯次数最少等），寻找一条从起点到目标点的最优路径。设施初始布局可以采用SLP方法进行设计[5]，一般采用两种路径设计方法：第一种是考虑二维平面图规划，另一种采用传感器规划，该文以前者为例进行详细的描述。

2.1 图数据库建模元素

图数据库模型是一种用有向图的方式建模，并将数据储存在图中的数据结构[9]。图数据库可在图模型的任意两个节点间进行最短路径的计算。图数据库的模型一般用圆圈加一个方框表示节点，方框中用文字描述节点的标签，用带箭头的线段表示关系，关系名称写在线段的两侧，节点和关系一般都具有属性，属性用来描述节点或关系的特征，如机床表示节点，机床有机床型号、名称、加工零件、制造日期等属性。

在制造车间中，常见的对象有车床、铣床、镗床、装卸站等设备，在图模型中这些实体用节点表示，如果设备之间存在有加工工艺顺序严格约束关系，则用带箭头的线段表示从一台设备到另一台设备，其中箭尾表示源设备，箭头表示目标设备，如果两个设备之间互通，则用无箭头线段描述，图模型是由有单向关系的多节点、有双向关系的多节点及有多个汇聚和分支关系的多节点等四种基本类型组成，一个复杂的图模型基本上由这四种基本元素组合构成。

2.2 机器人行走路径图建模

该文在文献[6]提供的某车间设施规划方案II的基础上进行行走路径设计，设计原则为：根据车间设备的分布情况，按照物流通道划分为若干行走路线，在设备之间有双向可达通道，则在图模型中绘制2个设备节点之间的双向联系，否则为单向联系；在十字、T字及L字交叉路口的行走轨迹规定则按照交通行走规则制订。

2.3 使用Dijkstra算法求解模型最短路径

Dijkstra算法是经典的以宽度优先搜索最短路径问题的算法，该算法可以搜索指定任意节点到其他各个节点间的最短路径，限于篇幅，略去算法步骤。

3 结语

该文研究了制造车间物料搬运机器人行走路径图建模的过程及使用Dijkstra算法求解最短路径方法。图数据库建模不但能减少多种因素对算法的影响，而且使搜索算法具有准确性和简单性。此外通过建立图数据库模型，将各个设备信息储存在数据库中，能减少模型后期维护的工作量。限于水平，该文只研究单个搬运机器人的路径模型建模及搜索算法，进一步需要研究多个搬运机器人的行走路径规划及调度算法。

参考文献

[1] 董鹏.制造业内部物流痛点与突破点[J].建设机械技术与管理，2015（11）：96-97.

[2] 刘洪伟，齐二石.基础工业工程[M].化学工业出版社，2011.

[3] 姬东.图论最短路径问题在消防选址中的应用[J].武警学院学报，2009，25（12）：10-12.

[4] 夏谦，雷勇，叶小勇.遗传算法在AGV全局路径优化中的应用[J].四川大学学报：自然科学版，2008，45（5）：1129-1136.

[5] 方庆琯，王转.现代物流设施与规划[M].2版.机械工业出版社，2013.

[6] 邱胜海，樊树海，高成冲，等.CIMS 环境下车间设施规划方案综合评价方法研究[J].現代制造工程，2014（4）：1-6.