基于dijkstra
算法的工厂agv
路径规划方法
技术领域
1.本发明涉及人造金刚石加工车间自动运输路径规划技术领域，尤其涉及一种基于dijkstra算法的工厂agv路径规划方法。
背景技术：
2.agv(automated guided vehicle，自动导引运输车)是能按照作业任务需求结合自身状态，进行自主导航、避障的车辆。可以广泛运用于各种车间、物流、货运等企业。agv小车替代了以前的人工搬运、极大的减少了人力资源的消耗。并且agv所在工作环境的布局具有柔性，能方便的进行路径调整。再投入生产之前可方便的在仿真系统中调试，不影响生产。因此，在自动化物流系统中，最能体现出其自主性和柔性，实现高效、经济、灵活的自主化生产。
3.在自动化加工车间中，地图在相当一段时间不会改变。对于已经确定的拓扑图，任意两个
节点之间的距离是固定的。因此对于agv的动态调度首先对地图进行预计算，之后的路径规划时间会被大大降低。
技术实现要素：
4.本发明目的就是为了弥补已有技术的缺陷，提供一种基于dijkstra算法的工厂agv路径规划方法，在地图没有改变时，动态路径规划以响应不断新增的任务订单时，减少无用节点的搜索从而降低动态路径规划的时间消耗并能够使搜索出来的路径最优，即动态搜索路径等于实际
最短路径；地图偶尔变化时，agv能检测发现并搜索出最优路径。
5.本发明是通过以下技术方案实现的：
6.一种基于dijkstra算法的工厂agv路径规划方法，包括下述步骤：
7.(1)预处理：把工厂地图信息以拓扑图形式存储并上传到本地；以工厂地图各个节点循环地调用dijkstra算法，计算出各节点到其他所有节点的最短距离，计算结果保存在节点间的距离矩阵d并上传到本地，其中元素d[i][j]表示节点i到节点j的最短距离；
[0008]
(2)在某节点处产生任务订单后，需要生成由起点v
start
到终点v
end
的最短路径dist(v
start
，v
end
)，通过距离矩阵d得到由起点v
start
到终点v
end
的最短路径dist(v
start
，v
end
)＝d[v
start
][v
end
]，设到达节点v
mid
累计路径长度为g(v
mid
),则遍历以v
mid
为起点的所有边，则有如下等式(1)
[0009]
dist(v
start
，v
end
)＝＝g(v
mid
)+μ(v
mid
,v
x
)+dist(v
x
,v
end
) (1)
[0010]
其中μ(v
mid
,v
x
)表示工厂地图中以v
mid
为起点的任意一条边，
[0011]
dist(v
x
,v
end
)表示从节点x到终点v
end
的距离；
[0012]
若等式(1)成立，则边μ(v
mid
,v
x
)是起点v
start
到终点v
end
最短路径中的一条边，重复执行步骤(2)，直到搜索出目的节点v
end
；若遍历完工厂地图中以v
mid
为起点的所有边都不能使等式(1)成立，则说明地图中的节点信息发生改变进入步骤(3)；
[0013]
(3)遍历工厂地图中所有以v
mid
为起点的边，则有等式(2)
[0014]
f(v
mid
，v
end
)＝μ(v
mid
,v
x
)+dist(v
x
,v
end
)
ꢀꢀꢀꢀ
(2)
[0015]
其中f(v
mid
，v
end
)表示当地图节点信息发生改变时，从节点x到终点的最短距离估算值；
[0016]
计算出以v
mid
为起点到目标节点v
end
新的最小代价值，并将起点v
start
更替为v
mid
且μ(v
mid
,v
x
)为最短路径的边。
[0017]
步骤(1)中，以工厂地图各个节点循环地调用dijkstra算法，计算出的各节点到其他所有节点的最短距离为以时间为权值的最短距离。
[0018]
对于地图没有变化情况，任意两节点之间的地理最短距离确定不变，所以预处理阶段得到两点间距离d[i][j]所构成的矩阵d与实际车间地理最短距离一致。通过不断循环步骤(2)，逐步从源点向目标点扩展从而得到实际最短路径。该算法不用计算与理论最短路径无关的点，使得只需要搜索最短路径沿途的边以及沿途各点为起点的边。在动态调度中极大程度的降低了一次路径规划的时间成本。
[0019]
对于地图有变化情况即μ(v
mid
,v
x
)不等于dist(v
mid
，v
x
)。该算法把v
mid
替换v
start
重新代入步骤(2)中，能够在较短时间内搜索出到目的节点新的最优路径。
[0020]
本发明的优点是：
[0021]
(1)本发明使用预计算地图信息的路径规划方法，使得算法不用再计算大量的无用节点，极大提高了在工厂中agv动态路径规划时的节点搜索效率。
[0022]
(2)本发明能够在极短时间内动态的计算出从源点到目的点的最短路径。
[0023]
(3)本发明在工厂地图环境发生变化时，及时做出调整并重新规划出从地图变化点到目的点的最优路线。
[0024]
(4)使用此算法，能够在动态调度中极大地降低进行一次路径规划的时间成本，为融合路径算法提供了新的解决方案。
附图说明
[0025]
图1为本发明实施例的整体实施流程图；
[0026]
图2为本发明实施例的路径搜索过程中检索节点示意图；
[0027]
图3为本发明实施例中最短距离示意图。
具体实施方式
[0028]
如图1所示，一种基于dijkstra算法的工厂agv路径规划方法，包括以下步骤：
[0029]
步骤1：工厂地图以拓扑图形式构成表(outedge list)，方便查询；
[0030]
如图2所示，依次对每个节点使用标准dijkstra算法，得出此点到其余各点的最短路径(以时间为权值)，构成矩阵dst，方便查询；
[0031]
步骤2：将当前点设置为起始点，累计距离s置0，从矩阵dst中获取待规划路段的起点s到终点e的最短距离dst
s,e
；
[0032]
步骤3：判断s＝＝dst
s,e
，判断是，程序结束；判断否，继续；
[0033]
步骤4：获取以当前点t为起点的边表(outedge list)，遍历；
[0034]
步骤5：获取当前边的权值t
ecost
，当前边的结束节点out，计算
[0035]
dst
s,e
＝＝s+t
ecost
+dst
out,e
[0036]
其中dst
i,j
代表预存的点i到点j的最短距离。具体如图3所示；
[0037]
步骤6：判断是，当前点置为out,s＝s+t
ecost
,跳到步骤3；判断否，遍历index+1，跳到步骤5；
[0038]
步骤7：当遍历完所有当前节点t为起点的边都不能满足步骤5中的等式，则判定工厂地图发生改变即表(outedge list)发生变化；
[0039]
步骤8：在表(outedge list)中遍历以当前节点t为起点的边，通过计算
[0040]
f(t)＝t
ecost
+dst
out,e
[0041]
得出最小f(t)代价值并得出该边的结束节点out；
[0042]
步骤9：把节点out设为起始节点，并跳到步骤3。
[0043]
经过上述步骤最终遍历到目的节点，算法结束。从该算法不难看出：本发明提供了一种通过预计算地图信息的动态路径规划方法，使得搜索效率极大提高并能够在工厂地图变化或未变化的情况下精确的检索到的最短路径。为今后的融合算法提供了一种新的解决思路。
[0044]
上述的实施方案是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。在本领域的普通技术人员所具备的知识范围内，还可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。
技术特征：
1.一种基于dijkstra算法的工厂agv路径规划方法，其特征在于：包括下述步骤：(1)预处理：把工厂地图信息以拓扑图形式存储并上传到本地；以工厂地图各个节点循环地调用dijkstra算法，计算出各节点到其他所有节点的最短距离，计算结果保存在节点间的距离矩阵d并上传到本地，其中元素d[i][j]表示节点i到节点j的最短距离；(2)在某节点处产生任务订单后，需要生成由起点v
start
到终点v
end
的最短路径dist(v
start
，v
end
)，通过距离矩阵d得到由起点v
start
到终点v
end
的最短路径dist(v
start
，v
end
)＝d[v
start
][v
end
]，设到达节点v
mid
累计路径长度为g(v
mid
),则遍历以v
mid
为起点的所有边，则有如下等式(1)dist(v
start
，v
end
)＝＝g(v
mid
)+μ(v
mid
,v
x
)+dist(v
x
,v
end
) (1)其中μ(v
mid
,v
x
)表示工厂地图中以v
mid
为起点的任意一条边，dist(v
x
,v
end
)表示从节点x到终点v
end
的距离；若等式(1)成立，则边μ(v
mid
,v
x
)是起点v
start
到终点v
end
最短路径中的一条边，重复执行步骤(2)，直到搜索出目的节点v
end
；若遍历完工厂地图中以v
mid
为起点的所有边都不能使等式(1)成立，则说明地图中的节点信息发生改变进入步骤(3)；(3)遍历工厂地图中所有以v
mid
为起点的边，则有等式(2)f(v
mid
，v
end
)＝μ(v
mid
,v
x
)+dist(v
x
,v
end
)
ꢀꢀꢀꢀ
(2)其中f(v
mid
，v
end
)表示当地图节点信息发生改变时，从节点x到终点的最短距离估算值；计算出以v
mid
为起点到目标节点v
end
新的最小代价值，并将起点v
start
更替为v
mid
且μ(v
mid
,v
x
)为最短路径的边。2.根据权利要求1所述的一种基于dijkstra算法的工厂agv路径规划方法，其特征在于：步骤(1)中，以工厂地图各个节点循环地调用dijkstra算法，计算出的各节点到其他所有节点的最短距离为以时间为权值的最短距离。
技术总结
本发明公开了一种基于dijkstra算法的工厂AGV路径规划方法，本发明通过预计算地图信息实现动态路径规划，使得搜索效率极大提高并能够在工厂地图变化或未变化的情况下精确的检索到的最短路径，为今后的融合算法提供了一种新的解决思路。种新的解决思路。种新的解决思路。
技术研发人员：
董玉革 袁康 王虎
受保护的技术使用者：
合肥工业大学
技术研发日：
2022.12.08
技术公布日：
2023/2/23
