基于AGV的智能停车库调度系统设计

(北京星航机电装备有限公司 装备制造技术研发中心，北京 100074)

0 引言

无人搬运车(automated guided vehicle，AGV)，指装备有电磁或光学等自动导引装置[1]，能够按照预先设定的路径自动行驶的运输车，自动化程度高，具有无人驾驶、安全可靠等特点，通常采用蓄电池来为其供电，并可通过电脑来控制其行进路线以及行为。与物料搬运中常用的其他运输载体相比，AGV的活动区域不受场地、道路和空间的限制。因此，在智慧物流中，最能充分体现其灵活性和柔性，在无人状态下完成物料的快速转运。

所谓全方位移动，是指运动系统具有平面内三个自由度，即可同时独立的在前后、左右和原地旋转三个方向上运动[2]，并在保持自身位姿不变的情况下实现任意方向的移动。全方位运动机构运动灵活多变，克服了传统运动机构不能横向移动、回转半径达、运动不灵活的缺陷。

本文调度系统所控制的AGV亦具备全向移动特性，其采用麦克纳姆轮先进技术，四轮独立驱动，可利用不同的轮组转速和转向组合，以任意姿态在二维平面内移动，不需要车体做出任何转动即可实现平面上任意方向移动，可在原地任意角度旋转，且能够沿着平面上连续轨迹走到要求的位置，能够最大限度的满足精确定位和高精度轨迹控制的要求。其凭借着全方位运动机构横向移动以及零半径旋转的特性，可以灵活方便的穿梭于狭小的空间中。

调度系统作为AGV自动运输系统的“大脑”，很大程度上决定了AGV自动运输系统是否可以高效运行。随着司机驾驶技术差导致的停车难、城市道路停车位紧张等问题的日益暴露，市场对无人智慧泊车系统的需求越来越强烈。本文基于全向移动的AGV对智慧泊车调度系统进行了详细的研究，并在此基础上，给出了各个核心模块的设计与整体框架图。

1 智慧泊车系统总体方案

1.1 智慧泊车系统组成

智慧泊车系统主要由AGV小车、导航系统、调度系统、其他辅助设备等部分组成。

AGV主要由车架、驱动机构、动力系统、控制系统、手动移动系统、安全防撞系统等六部分组成，见图1。其中驱动机构是整车的驱动部件，系统采用四套独立的麦克纳姆轮系，通过四轮速度合成完成车辆的各种运动；动力系统是整车各种能源的供应源，由动力电池和电源变换管理模块组成；控制系统是整车的中央处理系统，完成车辆的运动控制。控制系统中的遥控模块用于遥控架车运动，由遥控接收器和遥控发射端组成；安全防撞系统主要用于障碍物检测，防止车辆之间或者车辆与其他设施的碰撞。

图1 AGV小车的结构架构图

导航系统的主要用于引导AGV沿着提前设定的路径行走，同时确定自身的位置，具体包括引导线路(磁钉、二维码、激光反射板等)和定位标识。目前常用的导航方式有磁条导航、视觉导航、激光导航等。

调度系统作为整个系统的核心，主要由上位机服务器、调度管理软件等组成。

其他辅助设备，主要包括AGV充电设备、无线通信设备等。整个智慧泊车调度系统的网络架构如图2所示。

图2 智慧泊车系统网络拓扑图

1.2 智慧泊车调度系统总体设计

智慧泊车调度系统由后台管理模块、外部通讯模块(消息子系统)、路径规划模块、数据库模块、电子地图模块、行车引导模块、前端监控模块、任务调度模块几个模块构成，系统结构如图3所示。其中数据库模块和通讯模块是其他模块的基础，而路径规划模块则是整个智慧泊车调度系统的研究重点，也是本文的讲述重点。

图3 智慧泊车调度系统结构图

1.3 数据库模块

数据库模块编程选用基于COM和面向对象的ADO接口，开发时需要库文件msado15.dll的支持。

数据库子系统为其他各软件模块提供数据库访问服务，让各软件系统与数据库表的设计及读写实现细节相剥离，只关心数据读写内容即可。整个数据库包含14张表结构，对表数据的操作全部封装在iParkDB类中。所有调用该模块的上层系统，都需要在应用程序初始化里边添加COM初始化函数AfxOleInit()，以创建ADO连接。所有数据库查询都采用无缓冲模式，查询结果以数据集的形式返回给上层调用系统后，立即关闭查询结果集。同时，数据库子系统作为底层接口，可能会被不同的线程同时访问调用，因此在设计实现时增加了并发访问机制来避免不同线程之间的干扰。具体的数据库设计如图4所示。

图4 智慧泊车调度系统数据库设计

1.4 通讯模块

通讯模块即消息子系统，该模块为各软件系统间的协同工作提供消息传递服务，将各软件系统要传递的逻辑消息(数据内容)转换物理消息(字节流)，通过socket接口进行传递。当用户在人机交互一体机上按下存车或取车操作时，服务器端需要快速做出响应，因此服务器端与人机交互一体机(存/取车一体机)之间的消息传递采用UDP协议，允许网络存在丢包现象。上层调用系统在设计实现时，对于超时未收到消息回复的情况，进行消息重发处理。消息传递流程如图5所示。

图5 消息子系统传递流程图

由于停车位、充电位等资源为共享资源，在程序设计中需要为这些共享资源设置临界区保护。

1.5 前端监控模块

前端监控模块实时监控停车场及各AGV状态，便于管理人员掌握停车场车位情况和AGV的运行状态，并在必要的时候进行人工路径干预。系统初始从数据库读取电子地图数据，画出电子地图，与AGV建立连接后，在地图上实时更新各AGV的状态。前端监控页面如图6所示。

图6 前端监控页面

1.6 后台管理模块

后台管理模块提供用户管理、AGV资料管理、固定客户管理、历史数据管理、财务管理、系统参数配置等信息的增删改查操作。该模块与系统的其他模块没有交互，只是对数据库中的数据进行管理和操作。当后台管理软件对数据库中的数据进行读操作时，数据从数据库流向该模块；当后台管理软件对数据库中的数据进行写操作时，数据从后台管理软件流向数据库。

1.7 任务调度模块

任务调度模块的主要功能是当接收到存/取一体机发送过来的停车/取车消息时，生成相应的停车/取车任务。在本调度系统中，对于空闲车位和空闲AGV的分配原则为：优先选用距离入口最近的停车位，对于有双排车位的情况，优先选择外侧停车位；分配AGV时，优先选择距离停车位最近的空闲AGV。存/取车交互流程如图7所示。

图7 存/取车流程图

1.8 行车引导模块

行车引导模块的主要功能是将路径规划算法计算出来的路径转化为AGV小车可识别的动作指令，完成AGV行车引导。调度系统将规划好的整条路径发送给AGV，如在AGV行驶过程中调度系统检测到可能发生碰撞，则需要单独向AGV发送禁行/通行指令。

AGV在行进过程中，遵循右侧通行规则。车辆在路口转弯或者出入库时，会占用对向车道，此时后续车辆或对向车辆需等待避让。同时，调度系统根据AGV车辆实时上报的状态位姿信息，判断AGV小车之间是否为争夺同一资源出现死锁现象，如出现死锁，则需要锁定系统进行解锁。死锁严重的情况下，则需要为AGV重新进行路径规划。

AGV小车采用Trio MC405控制器，调度系统与控制器之间通讯采用标准ModbusTCP协议，该协议稳定可靠，数据传输效率高。

2 系统路径规划问题分析

2.1 AGV系统的路径规划问题

AGV系统的路径规划问题研究的是在指定的AGV运行环境中按照某一性能指标搜索一条从起始点到目标点的最优或近似最优的路径[3]，同时保证在行进过程中AGV之间无碰撞，无死锁情况出现。

AGV的行走路径规划主要是通过地图数据、任务参数和路径规划算法，获得实际运行中最优的运行路径，解决运行中可能出现的多个AGV路径冲突、路径重叠、时间浪费等问题。

AGV的路径规划问题，按照路径规划的目标范围可分为全局路径规划和局部路径规划，按照地图环境是否随时间变化可分为静态环境路径规划和动态环境路径规划，按照运行AGV的数量可分为单AGV路径规划和多AGV路径规划。在本调度系统中，各AGV在固定的区域内运行，所以本项目在路径规划目标范围上属于全局路径规划。地图环境方面，由于目标运行环境是固定的停车场环境，故属于静态环境路径规划。在AGV运行数量上，属于多AGV的路径规划。此外，当接收到新的停车/取车任务时，系统需要依据现有任务进展情况对新任务进行路径计算，所以亦是动态路径规划问题。

综上所述，智慧泊车调度系统的路径规划模块主要解决的是全局规划、静态环境中的多AGV动态路径规划问题。在进行多AGV(多任务)路径规划时，除了获得多个AGV的最短路径之外，还需要避免冲突、优化总体运行时间，以最大化提高系统效率。

2.2 电子地图建模

在AGV系统中，获取系统环境信息是路径规划的先决条件[4]。路径规划问题的基础，首先是将待搜寻最短路劲的物理空间转化成计算机可以识别的电子地图，以便能够将位置数据传递给路径规划算法进行分析处理。电子地图是真实环境在计算机中的展现，其中包含了各种道路节点、充电位、停车位、维修位等相关信息，这些信息是定位导航和路径规划的根本。对于已知的全局环境，AGV运行所需要的路径信息按照特定的方式存储在电子地图中，AGV通过本身安装的各种传感器得到相关信息，通过定位系统将自身的位姿信息和全局坐标系匹配从而得到在电子地图中的实时位置。

在本调度系统中，采用基于图论的方法来进行电子地图建模。在电子地图中，环境中的关键位置(如停车位、充电位、车库出入口等)使用节点来进行表示，节点之间的可行连线表示AGV可行走路径[5]，即道路。基于该模型进行路径规划时，AGV的运行路线通过有序的节点集来表示，而节点之间的顺序则指明了AGV的运行方向。

结合道路容纳车辆的数量，路径的行驶车道主要分为三种形式：单车道单向行驶、双车道双向行驶、单车道双向行驶[6]。在本系统中，道路设计成双车道双向行驶模式，即两个节点之间的路径表示两条行驶方向相反的平行车道。结构化的地图由节点和边组成，用G=(V,E,W)来表示，其中V表示所有节点的集合，E表示所有边的集合，W表示边的权值，即节点之间的距离，该值是进行路径规划时的关键数值。结构化地图模型如图8所示，图例所示为双车道双向行驶。

图8 结构化地图模型

2.3 路径规划算法——改进A*算法

路径规划算法维护一个经过计算的运行中任务路径数据，当获得新的任务之后，进行一定的数据预处理，然后提交给核心的路径规划算法进行最短路径计算。路径规划算法将新任务的数据与运行中任务的数据作为参数，加上任务优先级、交通规则定义、运行时间优化等，计算得出新的运行中任务路径数据。该模块的具体处理流程如图9所示。

图9 路径规划模块处理流程图

在本调度系统中，选用A*算法作为基础算法来计算任务的最短路径。A*算法是一种启发式搜索算法，通过建立合适的估价函数，来获得有利于问题求解的启发信息，从而利用这些启发信息区搜素最优路径。该算法不用遍历整个地图，因此时间复杂度低。本调度系统地图环境固定，且各个节点都有准确的坐标参数，所以可以方便的建立A*算法的估价函数。

A*算法的评价函数可以表示为：

f(x)=g(x)+h(x)

(1)

其中:g(x)表示起始点s到当前节点x的最短路径代价函数值，h(x)表示当前节点x到目标节点t的最短路径代价的启发函数值，f(x)表示起始点s经过当前节点x到目标节点t的评价函数。在本调度系统开发实现中，使用两节点之间的欧式距离来计算g(x)和h(x)。

除上述代价评估函数外，A*算法在代码实现过程中需要用到open表和close表这两个数据结构，其中open表中存放当前考虑的点及其周边需要添加进来作为可能的路径上的点，close表存放所有不需要再次检查的节点。A*算法总结如下：

1)把起点加入open表。

2)重复如下过程：

(1)遍历open表，查找F值最小的节点，把它作为当前要处理的节点，然后移到close表中；

(2)对当前节点的8个邻居进行检查，如果他是不可抵达的或者已经在close表中，忽略它，否则做如下操作：

①如果它不在open表中，把它加入open表，并且把当前节点设置为其父节点；

②如果它已经在open表中，检查这条路径(即经由当前节点到达该节点)是否更近，如果更近，把当前节点设置为其父节点，并重新计算它的G值和F值。如果open表是按照F值进行排序的，则改变后可能需要重新排序。

(3)遇到下面情况停止搜索：

①目标节点已经加入到open表中，此时路径已经找到；

②查找目标节点失败，并且open表为NULL，此时没有路径。

3)从目标节点开始沿着父节点进行追溯，直至起点，形成路径。

因道路设计为双车道双向行驶模式，故AGV在转弯时，需要提前横移到道路中央，这就需要额外消耗时间，降低系统的运行效率，故当起点和终点一定的情况下，规划的路径AGV转弯越少越好。传统的A*算法在计算g(x)和h(x)并没有考虑转弯消耗，无法在两种路径间选取转弯次数更少的路径。针对此问题，对A*算法进行了改进，如规划的路径中AGV需要转弯，则转弯点的g(x)会增加转弯代价。通过引入转弯因子，改进后的A*算法可根据实际应用来调节转弯对路径规划的影响，在不降低搜索效率的前提下，使得搜索出来的路径转弯次数最少。改进后的A*算法运行流程如图10所示。

图10 改进A*算法算法流程图

2.4 冲突检测

冲突和死锁检测是多AGV路径规划面临和解决的一个重要问题。AGV在行走过程中，要实时检测是否与其他AGV存在冲突，即空间冲突和时间冲突。所谓存在空间冲突，即当前AGV的运行路径与其他AGV的运行路径存在重叠；判断是否存在时间冲突则需要检测AGV在重叠路径上是否存在时间上的重叠。如果空间冲突和时间冲突同时发生，则说明不同AGV之间会为争夺同一路径资源而产生死锁。

在本调度系统中，为了解决AGV之间的冲突问题，对路径对应任务分配了优先级顺序，同时为每一个任务中的AGV关联本体区域、已占用区域和拟占用区域，其中本体区域指AGV(带托盘)所在区域；已占用区域指AGV本体进入转弯区，则将转弯区设为占用区；拟占用区域指AGV行进方向的若干米，设为拟占用区，若此拟占用区进入转弯区，则将转弯区也设为拟占用。若两个AGV存在区域重叠，则区域优先级低的AGV要等待避让。若冲突区域的优先级相同，则根据任务优先级，让优先级低的任务避让等待。距离终点越近，相应任务的优先级越高。

2.5 开发与运行环境

整个调度系统开发基于MS Windows7 Professional操作系统，开发语言为C++，采用C/S架构，IDE环境为VS2013或以上版本，数据库平台为SQL Server 2008。开发过程中运用了面向对象、模块化以及多线程编程技术。

人机交互终端为一体机，集成打印与扫描功能；前端监控终端、后台管理终端选用普通PC机。

2.6 实验结果与分析

调度系统功能验证采用双向两车道两出入口，3台AGV 、8个托盘、30个车位，AGV的定位精准度误差控制在5 mm以内，行驶速度最高可达1.5 m/s。经过将近6个月的调试，平均存取车时间不超过90 s，基本验证了调度系统各模块功能设计的可行性。

受到现实条件的限制，不能进行真实的多AGV调度测试，利用多线程技术，编写了仿真验证程序，可同时验证90台AGV同时下线的情况，证明路径规划算法是可行的。但由于仿真状态下为理想状态，在实际调试时，路径规划算法还需根据具体应用环境进行完善。

3 单车独占模式(单车道)与双车共享模式(双车道)比较

从经济效益方面进行比较。单车独占模式仅需要占用较少的场地面积进行道路铺设，而双车共享模式需要占用更多的场地面积以提供更宽的运行道路以满足运行安全性。经实际停车位设计计算发现，单车独占模式场地的有效利用率高出双车独占模式5%左右，并且单层面积越大，单车独占模式的场地有效利用率提高越显著。

从路径规划系统的性能方面进行比较。单车独占模式仅提供较少的转弯节点，且行车主路线、支线的总体节点较少，便于路径规划系统进行快速计算，同时路径规划算法的准确性也会更高，系统运行速度和稳定性较好。双车共享模式中，道路中具有两条并行行车主路线，在路径规划时会产生更多的可用路径，同时转弯节点并不在行车主路线之上，在进行路径规划时需要增加AGV平移运动；另一方面，虽然每个道路具有两条行车主路线，但是一旦AGV在道路中间执行转弯任务时，会同时阻塞两条主路线，增加阻塞节点，转弯完成后阻塞节点又立即消失，这种动态干扰增大了路径规划难度。

从系统运行效率方面进行比较。单车独占模式在运行中可在主路线的转弯点直接转弯，节约了额外动作时间，但是多台AGV进行会车避让时，需要优先级较低的AGV进行额外移动(如提前进入支线)以避让等待。双车共享模式在运行中转弯时需要从行车主路线上移动到转弯点，增加了额外动作时间，且会同时堵塞两条主路线(此时的堵塞状态与单车独占模式相近)，不过在多个AGV会车时只需要提前进行变道且并行移动，效率较高。两种模式在运行效率方面的对比结果，需要根据实际运行过程中AGV各个动作的实际执行时间(直行、转弯、横移)以及系统的负载进行测算。

4 结束语

随着企业信息化、自动化的快速发展，智慧物流成为一种必然趋势，而AGV自动运输系统正是这种趋势的典型代表。本文基于正在实施的智能停车项目，对调度系统所涉及的电子地图建模、路径规划算法、数据库设计、行车引导、避障解锁等模块进行了详细描述，同时提出了一种改进的A*算法，引入转弯因子，使得在起点和目标点确定的情况下，AGV转弯次数最少，行走路径更平滑。多AGV路径规划是一个复杂的过程，在实际调试中，路径规划算法还需不断改进和完善。