物流工程的路径规划.pptx

路径规划
路径规划
AGV智能化新发展在于自主回避障碍物并到达目标地路径规划。
首先，影响路径规划是AGV自由度数和地图有没有。为了便于了解，以2自由度AGV为例，分别考虑有地图时(环境已知时)和没有地图时(环境未知时)路近障碍物行走
物流工程的路径规划
第12页
路径规划
2．Voronoi图
Voronoi图可用弧表示距两个以上障碍物和墙壁表面等距离点阵，用节点表示它们交叉位置。
首先把对应起始点S和目标点G起始节点ns和目标节点ng标注在图上，然后用搜索算法A*选出安全路径P，最终，使点AGV沿着路径P进行PTP控制和CP控制，把AGV引导到目标地。因为选择是安全路径，所以，即使产生位置误差，AGV也能够在离障碍物足够远路径上走行。
物流工程的路径规划
第13页
路径规划
物流工程的路径规划
第14页
路径规划
* (A)
这里要介绍是，把前面所说切线图和Voronoi图作为搜索图G，选出从起始节点ns到目标节点ng最正确(或满足)路径算法A*(或选出任意路径算法A)。
算法A*(或A)一面计算节点n费用f(n)，一面搜索图G。费用f(n)是从起始节点ns经由当前节点n到目标节点ng最小费用(最短距离)估价函数。
物流工程的路径规划
第15页
路径规划
可用下式计算：
f（n）= g(n)+h(n)
式中，g(n)是起始节点ns和当前节点n之间现时点上最小费用(最短距离)；而h(n)是当前节点n和目标节点ng之间最小费用h*(n)预计值，称为启发式函值。
OPEN是管理以后扩展节点明细表，全部节点按费用f（n）递增次序排列，CLOSED是管理已扩展节点明细表。
物流工程的路径规划
第16页
路径规划
通常A*(或A)等搜索算法，从节点n扩展全部节点n’中，把必要节点同费用f(n’)都标注OPEN上(参看算法第⑤步)，这个操作称为“扩展节点n”。
算法A*(A)程序流程说明：
①把起始节点ns代入OPEN。
②假如OPEN是空表，因为路径不存在，所以算法终止。
③从OPEN取出先头(费用f最小)节点n，并把它移到CLOSED。
物流工程的路径规划
第17页
路径规划
④假如节点n是目标节点ng，则顺次返回到来自节点上(程序上是追寻(返回)指针)。然后，若是抵达起始节点ns，则终止算法，得到一个路径。
⑤ 假如不是这么，扩展节点n，把指针从其子孙节点n’返回到节点n(记住从哪来)。然后，对全部子孙节点n’做以下工作:
物流工程的路径规划
第18页
路径规划
节点n’假如不在OPEN或CLOSED表中，则它就是新搜索节点。所以，首先计算预计值h(n’)(从节点n’到节点ng最短距离预计值).其次,计算评价值 f(n’)=g(n’)+h(n’) (这里g(n’)=g(n)+c(n、n’),g(ns)=0,c(n、n’)是连接节点n和n’弧费用)。然后，把节点n’同预计值f（n’）都代入OPEN。
若节点n’存在于OPEN或CLOSED表中，则它就是已被搜索节点。于是，把指针换到带来最小值g(n’)路径上(变更来自地方)。然后，在这个指针发生替换时，若节点n’存在于CLOSED中，则把它返回到OPEN后，再计算值f(n’)=g(n’)+h(n’)。
物流工程的路径规划
第19页
路径规划
返回到②
算法A*(A)程序流程
物流工程的路径规划
第20页
路径规划
预计值h比真值h*小或相等时，上述算法变为A*，可选出从起始节点ns到目标节点ng最正确路径(总计费用最小路径)。
若预计值h比真值大， h*算法则变为A，可选出从起始节点ns到目标节点ng满足要求路径(总计费用不是最小路径)。
所以，机器人路径规划多用从当前地点( , , )到目标地( , )平方范数
物流工程的路径规划
第21页
路径规划
定义预计值。这个预计值h经常比h*小，成为算法A*，用它可选择最正确路径。
图7-20搜索图G存在预计值h(在节点上用括号给出)比真值h*大节点。比如，节点A和H预计值h是8和4，但抵达目标地最小真值是7和2。因为这个费用评价过大，存在于最短路径上节点H等能够忽略，算法错过了费用8最正确路径，最终得到费用9满足要求路径。
物流工程的路径规划
第22页
路径规划
E
D
F
G
H
I
B
C
A
S
(7)
3
2
(5)