钢铁物流中基于D*的路线规划算法

薄 胜,李 媛,赵静怡

(1.北京乐智科技有限公司,北京 100089;2.中国电信集团有限公司河北雄安新区分公司,河北 雄安 070001; 3.北京邮电大学,北京 100876)

0 引言

路径是连接起点位置和终点位置的序列点或曲线,用于生成路径的策略被称为路径规划算法[1]。路径规划是指在具有障碍物的环境中,按照一定的评判标准,寻找一条从起始状态到目标状态的无碰撞路径。路径规划算法具有广泛的应用领域,如城市道路网规划导航、GPS[2]导航以及基于地理信息系统(GIS)[3]的道路规划等。

对于机器人、飞行器等有关路径寻径和路径规划的研究,通常需要进行环境模拟、路径探索[4]、路径平滑[5]等常见工作步骤。而在钢铁物流场景车辆的路径规划研究中,路径规划算法的性能直接影响物流配送的效率和安全性。因此,路径规划算法需要满足高效和安全性强等要求。

为实现高效率的路径搜索,本文基于钢铁物流场景的路径规划需求和D*算法的反向搜索、动态搜索特点,提出了一种面向钢铁物流场景D*的路径规划算法,此算法对传统D*算法作出了相应改进,以避免传统D*算法为保证路径规划效率而规划出的不安全路径,从而导致配送效率和安全系数较低的问题。通过引入全新的路径规划算法可以极大的提高物流配送效率,加速整体物流自动化进度,提高物流工业化安全系数,保障物流配送流程的高效正常运作。

1 相关研究概述

路径规划算法不论是在物流配送,还是日常导航中都起着至关重要的作用。为此,众多学者对路径规划算法和在不同场景下的应用进行了研究。

路径规划算法是指在给定的地图和起点终点位置下,通过计算和优化算法,找出一条最优路径的算法。1956年,荷兰科学家Dijkstra提出了Dijkstra算法[6],这是一种基于贪心策略的单源最短路径算法,其关键特点是以起始点为中心向外扩展寻找,直到寻找到目标点[7]。在扩展的过程中,算法会优选选取距离起点最近的未访问结点,并利用该节点来计算至其余节点的距离数值。这种算法可以保证找到图中的最优路径。但是,随着扩展的结点增加,算法的效率也会相应降低。1962年,Floyd提出了一种基于动态规划的单源最短路径算法[8]。随后,Hart等人提出了A*算法[9],这是一种智能搜索算法,是一种结合了Dijkstra算法和广度优先搜索算法的启发式搜索算法,可以快速找到最优路径,是求解静态路网中最短路径时最高效的直接搜索算法。该算法利用启发式函数计算节点的综合优先级f(n),其中包括从起始点到该节点的代价值g(n),从该节点到目标点的估计代价值h(n)。当代价值接近于0,A*算法就相当于Dijkstra算法,能够保证找到最短路径,但是速度难以符合预期;当估计代价值接近于0,A*算法就相当于广度优先搜索算法,速度较快但不能完全保证找到路径的概率。通过调校估计代价值的大小,以平衡算法的精度和速度。A*算法适用于搜索范围较小的场景,不适用于动态环境,且当目标点不可达时会造成难以预估的性能消耗。在之后的不断发展中,陆续有学者提出了分支界限算法、遗传算法和模拟退火算法等路径规划算法。A.Wang等人[10]提出了一种改进q学习算法的跨区域定制线路规划算法,使得改进的灰狼优化算法能有效提高路径规划算法的精度和收敛速度。

D*算法旨在解决A*算法遇到环境变化时需重新进行路径规划,有可能降低算法计算效率的不良影响,其会存储场景中每个起终点的最短路径信息,可有效加强重规划能力。与正向搜索的A*算法不同,D*算法采用反向搜索,即从目标点开始搜索。它在首次遍历时与Dijkstra算法类似,会保存各节点数据。这种算法更适合动态环境的路径规划,提供了更高的搜索效率。

本文提出的基于改进的D*的路径规划算法,对钢铁物流领域的路径规划需求作出了详尽的分析。不仅规避了车辆与障碍物的碰撞或摩擦问题,也尽可能的减少了车辆拐动幅度和频率,最大程度的提高了大型装卸车在园区内部运输的安全性。该算法可以禁止车辆从两个障碍物间狭缝穿过,同时也引入拐点惩罚因子以避免规划出与理想路径偏差较大的路径,尽可能避免拐动行为。

2 基于D*的路径规划算法

在钢铁物流场景中,配送钢材的车辆主要为大型装卸车。传统D*算法由于选取子节点的不合理,导致规划的路径可能会引导车辆从两障碍物间狭小的缝隙穿过,考虑到参与钢铁物流的车辆规格,此算法设计会影响规划路径的安全性;传统D*算法可能会忽略了动态障碍物而导致最终规划路径出现非必要转弯的情况,由于大型车辆的拐弯速度相对较慢,多拐点的最终路径会降低整体的物流运输效率。

2.1 二维地图建模

二维地图建模技术是为车辆导航提供精准的地理信息支持,主要是通过地图和路况等信息,构建二维地图模型。可为车辆导航提供更加准确和实时的地理位置信息,实现精确的路径规划和导航。本文将基于钢铁物流企业所提供的园区地图,使用栅格法为园区地图进行二维建模。

常见的对工作环境进行二维地图建模的技术方法为栅格法[14],此方法通过将环境中的各种障碍物和信息划分成小方格的集合,实现对场景中所有事物进行权值替代和描述。该方法能够有效地表达空间的可变性,为路径规划算法提供重要前提条件。采用单元间计算路线的方法,能够显著降低连续环境空间寻径计算的负担,同时保证计算结果的精度。栅格法将园区地图离散化为栅格点,使得车辆路径规划问题被转化为了单元间计算路线的问题求解。栅格类型的对应含义见表1。

表1 栅格类型对应含义

在栅格法对地图建模后,原始地图信息将被映射到一个对应的二维矩阵,矩阵的元素为0或1。0代表自由区域,1代表障碍物区域。栅格法模拟后的结果示例如图1所示[1]。

图1 环境栅格化示意图

最后为验证算法的性能,本文在仿真阶段将使用随机生成障碍物的方式验证算法可用性和普适性。

2.2 参数定义

算法参数定义与说明见表2。

2.3 传统D*算法

对路径规划算法进行数学建模,首先需要将实时地图信息转化为存储必要信息的二维矩阵,此处可以调用栅格化算法对外开放的统一函数Map2Matrix,如公式(1):

Dm=Map2Matrix(map)

(1)

式中:map为存储地图信息的地图文件,Dm为转换后的w*h矩阵,Dm的元素即对应节点的地图信息。

D*算法以节点间的欧式距离作为计算节点间损失的依据,任意两节点的欧式距离计算如公式(2):

(2)

式中:XN为N节点在矩阵中的一维索引,YN为N节点在矩阵中的二维索引。

表2 算法参数定义与说明

为规划全局最优路径,D*算法需要计算并更新每个节点到达目标点的全局损失,每次计算先更新节点的h损失,再更新节点的k损失。损失计算如公式(3)和公式(4):

(3)

(4)

为了规划从起点到终点的最优路径,D*算法进行反向搜索,每次从待搜索节点集合Oopen中选择全局损失k最小的节点作为当前节点C,之后遍历当前节点C的候选子节点集合Ccan,计算并更新每个候选子节点Ccan的k损失和h损失,计算完成后将候选子节点放入待搜索集合Oopen中,并将当前节点放入已搜索集合Cclose中,这样就完成了一次完整的损失计算过程。重复该过程直到已搜索集合出现起点或待搜索集合为空,此时已搜索集合即为最优路径的节点集合。

2.4 改进的D*算法

本文改进的D*算法优化如下:首先,为提高运输过程中的安全系数,本算法禁止车辆斜穿两个障碍物间的狭缝,提出了一种局部规划算法对候选子节点进行约束,避免规划路径斜穿障碍物可能造成的车辆碰撞危险。其次,本算法引入拐点惩罚因子以减小路径拐动频率,通过惩罚拐弯幅度与理想路径偏差较大的路径,尽可能避免车辆出现不必要的拐动行为。

2.4.1 局部候选子节点约束

D*算法以当前节点的8个方向节点作为候选子节点,如图2(a)所示。由于传统D*算法以欧式距离为参考计算每个节点的损失,计算过程中算法到达局部最优,得到的路径可能会穿过两障碍物间的狭小空隙,如图2(b)当前节点到候选子节点3所示。为提高最终路径的安全性,本算法对局部候选子节点进行规则约束,从而禁止规划路径横穿两障碍物,如图2(c)所示。

图2 局部候选子节点约束

栅格法输出的矩阵Dm元素数值为0或1,这样的设计结合局部候选子节点约束,节点的候选优先级计算公式如下:

(5)

2.4.2 引入拐点惩罚因子

由于传统D*算法没有考虑出现动态障碍物后重新规划的路径容易出现不必要的拐点,导致在动态环境下,传统D*算法规划的路径并不平滑。针对这个问题本算法引入了拐点惩罚因子,通过惩罚偏离理想路径的候选路径,使得选择的最优路径拐点更少。拐点惩罚因子的定义如公式(6):

(6)

其中θ为待选路径与理想行驶路径间的夹角,μ为环境因子,取值与环境中障碍物的占比有关。由于θ的实际范围为(-180°,180°),显然当90°≤|θ|≤180°时,此时路径方向为前进方向;而当0°≤|θ|≤60°时,此时路径方向为回退方向。当出现回退现象时,算法会增大拐角惩罚因子值,并在原基础上加倍惩罚,以降低路线回退的可能性。引入拐点惩罚因子后,对节点h损失的计算即对公式(3)更新得到公式(7):

(7)

图3 20%障碍物覆盖密度对比仿真结果

图4 25%障碍物覆盖密度对比仿真结果

2.5 改进的D*算法仿真与分析

为了对改进的算法性能进行验证,对传统D*算法和改进的D*算法对比仿真,使用Python在Visual Studio Code平台进行编译执行。为保证实验的普适性,避免栅格地图中的特定环境因子给算法带来偏差,采用不同数据在同一主机中进行仿真,随机生成障碍物后以相同的障碍物覆盖率执行仿真。最终得到的本算法多次仿真结果如图3—图5所示,其中图中(a)、(b)分别为传统D*算法和改进的D*算法的路径规划结果。根据仿真结果可知,对于不同障碍物覆盖密度,改进后的D*算法不会穿过障碍物间隙,保障了车辆的行驶安全。

图5 30%障碍物覆盖密度对比仿真结果

为验证本文算法的改进目标完成度,进行了数十次实验以对比不同障碍物覆盖率和分布的情况,并记录了本实验路径的平均拐点数量指标,结果见表3。从表3可知,在不同障碍物比率下,改进的D*算法规划出的路径明显降低了拐点数量。

表3 仿真路径的平均拐点数量指标

3 结论

本文提出了一种面向钢铁物流场景改进的基于D*的路径规划算法。该算法可根据园区实际配送需求,标准化拐角惩罚因子系数;可细化原始的子节点选取角度,以避免不同角度的障碍物摩擦;可与钢铁物流实际业务流程结合,根据物流装卸货阶段进行具体分阶段导航。该算法有效地避免了钢铁物流中大型装卸车辆从障碍物间缝隙穿过的危险性,也降低了车辆拐弯次数,增加了车辆工作在园区配送中的安全性。