基于matlab的AGV行驶地图数据结构设计研究

凌忠奇，武启平，金亚萍，赵 玮，牛海颐

（机械科学研究总院，北京 100044）

0 引言

AGV是Automatic Guided Vehicles 的简称，属于轮式移动机器人（WMR――Wheeled Mobile Robot）的范畴。根据美国物流协会定义，AGV是指装备有电磁或光学自动导引装置，能够沿规定的导引路径行驶，具有安全保护以及各种移载功能的运输车。随着科学的发展和技术的不断进步，物流系统越来越朝着智能化的方向发展。AGV系统在企业自动化生产过程和计算机综合生产系统(CIMS)中，尤其是高度自动化的烟草、汽车、民航、钢铁、邮政、印钞等行业，高度清洁的电子、医药、食品等行业，冷冻、核材料、感光材料等特种行业有着广阔的应用前景[1]。因为具有较高的柔性、能够实时监视和控制、安全可靠和维护方便等特点，是现代物流系统的关键装备，也是现代物流自动化的关键桥梁。

AGV小车的核心技术包括导航技术、路径规划技术和导引控制技术。地图数据是以上核心技术的基础，因此对于地图数据的存储和利用吸引了越来越多科研人员的关注。

根据机器人对环境信息获取的程度不同，路径规划可分为两种类型：环境信息完全知道的全局路径规划和环境信息完全未知或部分未知的局部路径规划。环境信息完全知道的全局路径规划，适用于静态环境，路径是离线规划的；环境信息完全未知或部分未知的局部路径规划是通过传感器在线地对机器人的工作环境进行探测，获取障碍物的位置、形状和尺寸等信息来完成规划的，路径是在线规划的[2]。

1 行驶空间的数据描述

要实现AGV小车在场地内沿固定路线行走，就要对小车的行驶空间做数学的区分，标记固定的行驶路线。整个地图由点和线段组成，点的两端是线段，线段的两端是点。点作为AGV小车的正常情况下最小的停靠单元。在点上可以供AGV小车实现预设的动作。在AGV小车有行走请求时，采用申请线段的方式，如果申请通过，小车向前行进，否则原地等待。

其数据结构如表1所示。

表1 点的基本信息数据结构

线段是AGV小车的行驶路线，应记录线段的线段号、起点、终点、行驶形式、线段长度和设计速度等信息，其数据结构如表2所示。

表2 线段的基本信息数据结构

点和点之间由线段做作为连接，可以有连接关系矩阵表示。其中纵向表头是起点点号，横向表头是终点点号。点和本身用0表示，有逻辑连接用10表示，无逻辑连接用inf（无穷大）表示。以八个点为例，表示形式如表3所示。

表3 拓扑关系矩阵

点和线段之间的逻辑关系采用结构体的形式。根部是点号，一级支路是与点直接相连点的点号，二级支路是以根部为起点，一级支路为终点的线段，而且要区分正行和逆行。

图1 AGV行驶地图

2 外廓线的绘制和作用

外廓线是指AGV小车沿着路线行驶，外轮廓所扫过的区域。这个区域的形状与AGV小车外形尺寸、主动轮的个数及位置相关。根据外廓线的形状可以得到AGV小车线路之间的干涉关系表格，作为考虑小车外轮廓条件下避碰的基础依据。

外廓线的形成方式是将线段分成若干小点，每个点显示出AGV小车走在上面的外轮廓和角度，用叠加的的方式得到行走在整条线段上的外廓线。

外廓线是考虑小车外轮廓条件下避碰的必要数据。根据检测外廓线的相互关系，可以得到线路行走的相互干涉区域，形成线段分配相互影响的逻辑。如图2所示。

图2 线段外廓线干涉图例

A小车预设路径是线段6—7—4，B小车预设路径是线段1—2—3—4，但明显7号线段和2、3、4号线段有干涉。当A小车通过对7号线段的占用时，B小车将停在2号线段的起点，等待A小车离开干涉线段再向前行进。

3 路径搜索功能及实现

AGV小车要实现自动行走就必须有小车从起点到终点的完整形式路径。同时，在多车系统中，并非所有车辆沿着各自的最短路径行进就能够使系统效率达到最高。还应输出所有可达的路径，为车辆调度和系统优化提供基础。由于同向行驶的两点之间的可以是正行也可以是逆行，分别对应不同的线段号。因此所得的结果应是结合小车此时的位置、初始朝向和目标地终点朝向要求筛选出来的合理的线段链路序号。本文路劲搜素采用深度搜索算法，主要分成点的链路搜索、线段可行链路搜索和根据终点朝向要求的链路筛选。

3.1 采用深度搜索得出点之间的可行链路

深度优先遍历图的方法是，从图中某顶点A出发。

1）访问顶点A；

2）依次从A的未被访问的邻接点出发，对图进行深度优先搜索；直至图中和A有路径相通的顶点都被访问；

3）遍历所有点，直至所有点都作为搜索的起点访问过为止。

深度优先搜索（DFS）的基本框架如下：

DFS（Node）

if(Node=目标点）

then//找到目标，结束

for eachnext∈d[Node]

doDFS(next);

end

3.2 线段可行链路搜索

根据已有点的链路，搜索两点间的可行线路，根据小车初始的朝向选择可以行走的线段ID，在没有调头信号时，小车保持原来朝向，选择线段；当遇到调头信号，并且满足调头条件时，更改小车朝向，根据新朝向选取合适的线段，直到到达目的地，输出结果。

3.3 根据终点朝向要求的链路筛选

有些点充当了站台的作用，可以在该点上实现取卸货动作。但是由于物理空间的要求，对朝向有固定要求。在所有可行的线段链路中，取到达终点前的最后一条线段的朝向作为选择对象，如果满足进站朝向要求，则保留；如果不满足则舍去。

4 地图的属性数据

在点和线段上还应预留好属性位。可以用来标记以下信息：

1）此点是否可以停靠。由于多车系统中点位置选取不当可能会导致系统正常资源不能激发，从而使局部达到资源容量最大化，导致死锁。解决此问题可以把导致资源不能激发的点标记为不可停靠。

2）线段上是否要加堵塞。由于再多车系统中会产生冲突型死锁和资源型死锁。在对应的入口线段上添加有条件的堵塞，避免此类死锁发生。

3）标记小车动作。根据实际项目要求，某些点和线段上会有相关的动作或者输出，可以通过在对应的点和线段上添加标记实现。

5 结论

物流自动化系统是一个新型的现代化高科技产业。AGV作为高性能工业机器人的典型产品。本文以《数据结构》[3]为基础进行研究和开发，侧重实用性，建立了行驶环境的电子地图，实现了地图数据的存储和复杂网状道路上单车所有可达路径输出，为AGV小车控制技术、车辆调度与系统优化提供了关键技术支持。

[1] 引入AGV提升竞争力——访机科发展公司智能输送事业部总经理武启平[J].物流技术与应用.2005,(7):81-83.

[2] 李磊,叶涛,等,移动机器人技术研究现状与未来[J].机器人,2002,24(9).

[3] 汪沁,奚李峰.数据结构[M].清华大学出版社:2009.