基于路段时间窗考虑备选路径的AGV路径规划研究

曾祥苹

(广州南洋理工职业学院，广州 510925)

1 AGV发展历程

AGV全称为自动导引小车，指的是能够按照设置好的导引路径，安装有光学或电磁扥自动导引装置的小车编程和选择停车功能的装置，它具有多样化的移载方式，安装有安全保护装置，能够实现多种操作任务[1]。AGVs指的是自动导引车系统，主要构成系统为数据传递子系统、管理计算机系统、若干自动导引小车及地面子系统等，可以实现AGV分派移载的指定任务，起到实时监测效果。

AGV技术从叉车技术延伸发展而来，还有一种AGV技术是来源于机器人研发技术。两类AGV技术主要的研发目的是完成对货物路径的自动搬运。从导航技术发展来看，包括电磁导航、光学导航、激光导航及无路径视觉导航等。从控制系统发展来看，主要是从速度闭环控制系统发展到现在的位置闭环控制系统。从控制系统构成体系来看，主要是从专用封闭结构发展到目前的开放式结构[2]。从驱动技术来看，则是从直流电机驱动发展到直流无刷电机驱动，再到交流伺服电机驱动。从能源发展经历来看，主要是从铅酸电池发展到可以快速充电的镍铬电池能源，已经逐渐放弃需要充电的感应式供电方式[3]。从发展经历来看，相比于传统运输工具，AGV应用范围更广、更可靠、更智能，还具有监控系统。

2 AGV技术的组成和分类

AGV主要由转向系统、驱动系统、能源储存装置、车体、控制系统、通信系统、导引系统、安全系统构成。AGV自动导引车分为有轨道型自动导引车、无轨道型自动导引车。根据用途分类，可分为自动叉车、装配性自动导引车、搬运型自动导引车以及自动拖车等。根据行驶方式分类，可分为履带式和轮式两种类型的自动导引车。根据驱动方式可分为差速驱动、单轮驱动、全向轮驱动。根据导引方式分类，可分为激光导引、电磁导引、惯性导引、视觉导引、GPS导引以及声波导引等。根据搬运机构来分，则可以分为侧叉式、牵引式、后叉式。根据是否有导引路径来分类，包括自有路径自动导引车和固定路径的自动导引车。根据自动化水平分类，可分为AGV全自动化导引车和AGV-AGC简易自动导引车[4]。

3 基于路径时间窗算法的AGVS路径规划

3.1 时间窗算法概述

系统交通状况的检测是最早应用时间窗算法的，AGV在双向和有向图中搜索无冲突最优路径，而时间窗算法能够有效预测和预防小车失去控制而引发冲突。

假设目前系统中有n台数量的小车，R={r1，r2，r3…rn}，AGVs分配了m台数量的小车去执行任务，M={m1，m2，m3…mn}，对于每一个任务，都有相应的路径来相对应。每条路径都是从的Oi-Di(起始位置到终点位置)之间的弧段路径。诸多路径的集合也可以被称为有序弧段集合，即Oi={ej，ek…eq}，其中ei…eq都属于自然数，也就是环境中集合的路段，而每个任务都有相应的优先级Pi。

每个任务、起点/终点位置、分配任务都和时间变化无关，小车路径如果没有发生冲突，也不随之产生关系。但是如果在任务执行中，冲突只有通过路径改变才能解决，则可以将路径改为动态化的。每个小车在第一次任务分配中会有一个相对应的优先级，如果任务执行时间延长，则对应的优先级也会逐步变高。

当AGV小车在沿着有序路径上执行任务时，在驶入和驾驶出的时间段内，小车一直会在该路径上行驶，不准行驶第二辆小车。驶入时间和驶出时间段则被称为是路径时间窗。被小车所占用的时间属于保留时间窗，路径上没有小车占用，则被称为自由时间窗。自由时间窗意味着可以分配任务给这个小车到这个路径上，且不会产生小车碰撞的冲突。假设小车路径被分配为n，则需要观测小车行驶速度和转弯速度，计算出小车驶入和驶出所要花费的时间窗。

3.2 时间窗计算方法

任务需要按照其对应的优先级来进行排序，根据优先级的调度来设置任务的调度。最高优先级需要选择一个尚未被分配任务的小车，用Dijkstra的时间窗算法对其完成该任务所用的最短路径进行计算，计算出驶入时间和驶出时间，并对各个阶段上存在的时间窗向量表进行初始化。其次是次优级的任务，要先检查控线小车数量，如果暂时没有，则需要进入暂时的等待状态，然后再进行路径规划。同样用Dijkstra的时间窗算法来对小车驶入时间和驶出时间及性能计算，对各个路段上的时间窗向量表进行初始化。要检查每个时间窗中是否会发生冲突。如果不发生冲突，则路径规划工作完成。如果有冲突发生的可能性，则需要将第一个冲突的时间窗做一个不可用的标记，然后再进行最短路径的规划计算，直到不会发生冲突[5]。如果不能计算出最短路径，则需要对该任务的调度进行暂停，继续其他任务的执行。最后是对最次优级的任务进行分配小车和规划路径的计算。如果在路径规划以后也对时间窗向量表进行了更新，同样需要检查是否会发生冲突。通过这样循环往复的计算，就可以设置出多个任务并行但是无冲突发生的最短AGV自动小车路径。

3.3 冲突解决方法

等待策略。对于路径冲突的解决，等待策略的应用是比较有效的。比如：在路口发生冲突，根据人物优先级决定让哪辆车先停下来让路，具体的计算则是对来两辆小车，如i和j之间的距离dij的计算。计算公式为，d比设定值小的话，则需要判断交叉路口两辆车之间的距离。如果其中一辆小车与路口之间的距离大于另一辆小车，则需要暂停先让距离近的小车通过。如果两辆车与交叉路口之间的距离是相等或者差距很小的时候，则需要按照任务优先级来决定哪辆车先过，哪辆车后过。而后过的那辆车在没有小车发生冲突的时候，则可以继续运行[6]。

另一种冲突是赶超冲突，后车需要暂时的等待。如果发生了相向冲突，即两辆车都要面对同一段公共交叉路段，也可以用等待策略，如果是多个公共交叉路段，则不能用等待策略来解决。

重新规划路径策略。这个策略比较适用于当两辆小车都处于对方下一段路径的冲突情况的解决。可以先标记冲突路段不可用，然后再重新根据路径搜索算法探寻到其他可用的路径，对时间窗向量表进行初始化，循环往复，直到可用路径规划成功为止。

4 结语

时间窗算法比较容易操作，检查冲突也更为准确，对于环境变化有较快的反应能力，但是一旦小车数量增多，就会造成系统运算增加，路径优化工作也将会变得迟钝或者失效。