论文部分内容阅读
自动引导车（Automated Guide Vehicle,AGV）的广泛使用,使得大型仓储系统（Large Automated Storage and Retrieval Systems,LAS/RSes）仅需少量人工即可完成货物运输工作。AGV的路径规划是一个多目标组合优化问题,除了要关注算法快速性外,还要考虑路径距离最短、时间最小和系统能耗最低,对于多AGV情形,还要考虑多AGV之间无碰撞。随着LAS/RSes规模的扩大,路径计算速度成为限制LAS/RSes发展的主要瓶颈。本文的主要研究内容如下:1.构建仓储环境模型是进行路径规划的前提,传统的环境建模方法是:通过人工线下对实际仓库的尺寸进行测量,然后汇总测量情况,根据实际要求（如AGV/货架尺寸等）划分仓储环境的功能区域,但是该方法需要大量人力/物力资源。鉴于此,本文提出基于计算机视觉的仓储环境模型自动建立的方法:首先,采用常见的单目摄像机采集地面图像;然后,对该图像进行透视矫正,获得仓储环境的标准矩形图像;绘制储存区域的大致范围,计算其正外接矩形;其次,根据AGV/货架的尺寸计算工位点的尺寸,并对仓储环境栅格化;最后,构建仓储系统的模型,即仓储环境地图。通过仿真实例验证了所提出的自动构建仓储环境地图的方法的有效性。2.仓储AGV调度与路径规划同属于路径寻优问题,二者密不可分,它们共同决定LAS/RSes的效率。本文针对常见调度算法（基于k-NN、基于Manhattan距离的调度算法）已不适用于LAS/RSes的问题,提出了符合LAS/RSes特点的AGV调度算法——基于改进Dijkstra算法的调度算法。本文对比分析了上述两种常用调度算法在LAS/RSes环境中不可行性;通过添加转弯权值改进了经典的寻路算法（Dijkstra算法）,并将其用于AGV调度问题。仿真实例验证所提出的改进Dijkstra算法能在有障碍的仓储环境中确定可最快到达目标点的AGV,并同时计算其路径。3.针对单AGV路径规划问题,本文将Dijkstra算法与强化学习（Reinforcement Learning,RL）相结合,提出适用于LAS/RSes的改进型Q-learning算法:该方法将Dijkstra算法的邻接矩阵和Q-learning算法的奖励矩阵相结合,构成邻接-奖励矩阵（Adjacent-Reward,A-R）,通过引入节点间的邻接关系提高Q-learning算法的迭代效率;同时,根据AGV的起点/目标点对A-R矩阵进行降维处理,从而减少了训练样本数,提高了路径搜索效率;最后,计算AGV与可行路径的角度偏差,找到距离-时间最短路径。4.针对所提出的改进型Q-learning算法在构建A-R矩阵时过程繁琐、可扩展性较低的问题,本文提出结合动态规划（Dynamic Programming,DP）思想和蒙特卡洛树搜索（Monte Carlo Tree Search,MCTS）的单AGV路径规划方法——区域分割DP-MCTS算法,同时,考虑到经典的MCTS算法在节点搜索过程中缺乏选择机制（“盲目搜索”）,不能平衡探索与利用。鉴于此,本文对MCTS算法提出了改进:通过引导搜索树向AGV目标点的方向扩展,提高单次搜索速度;搜索树每进行一次节点扩展便进行一次性能评价,避免了反向传播过程的时间浪费;然后,将DP算法的多阶段优化的思想与改进的MCTS算法结合,提出了区域分割DP-MCTS算法,通过划分路径规划区域缩小搜索范围,进一步提高路径规划效率。该算法将算法计算复杂度从O（n~2）到O（nlog（n））,显著提高路径规划效率,降低系统的能源消耗。此外,该方法可显著提高路径规划效率,降低LAS/RSes的能量消耗。5.针对多AGV同时行驶会出现碰撞的问题,考虑到传统的时间窗方法不能根据路径冲突的类型自适应调整检测的精度,本文提出基于基因测序的路径冲突检测方法:首先,对节点和路段进行编号,格式化所构建的仓储环境地图;然后,建立AGV的路径和时间得分矩阵;最后,回溯上述两个矩阵,综合回溯结果得到冲突发生的区域。6.针对传统多AGV路径规划方法不能满足多目标优化的需求,且忽略了系统吞吐量以及能源消耗的问题。本文提出基于冲突关键段的自适应多AGV无碰撞路径规划方法,综合考虑了提高系统吞吐量和降低能源消耗的问题,该方法的功能简述如下:（1）对于多AGV之间潜在的路径冲突,系统根据AGV的优先级自适应选择冲突解决策略（等待或选择备选路径）,并根据任务目标点的位置实时确定等待的时间;（2）当出现突发状况（行驶路径上有人出现或有货物掉落）,系统实时判断此AGV是否需要在障碍物前等待;（3）当有新的运输任务下达,系统实时调度可最快到达任务起点的空闲AGV,提高LAS/RSes的动态性。仿真实例验证本文所提出的方法可用于LAS/RSes的AGV路径规划,能够为AGV规划距离和时间均最短的路径。同时,该方法可解决多AGV同时行驶产生潜在和突发路径冲突的问题,可有效降低LAS/RSes的能源消耗,有利于提高整个LAS/RSes的实时性。