单调性:单调性是Astar算法非常重要的一个性质,它决定了在用Astar算法进行路径搜索时,一定能找到一条最优路径。 设父节点的坐标为(x0,y0),它的任意一个子节点的坐标为(xi,yi),所以对两者之间的h(x),就一定满足
h
(
x
0
)
≤
h
(
x
i
)
+
C
o
s
t
0
,
i
h({x_{\rm{0}}}) \le h({x_i}) + {\mathop{\rm Cos}\nolimits} {t_{0,i}}
h(x0)≤h(xi)+Cost0,iCost0,i——从父节点到下一个子节点的代价值,恒大于等于0,即要满足代价函数是单调递增的; 父节点到子节点的估价值为h(x0)-h(xi),它总是小于或等于其代价值.
根据启发函数公式可知,对父节点和子节点的f(x),总有
f
(
x
0
)
=
g
(
x
0
)
+
h
(
x
0
)
f({x_{\rm{0}}}) = g({x_{\rm{0}}}) + h({x_{\rm{0}}})
f(x0)=g(x0)+h(x0)
f
(
x
i
)
=
g
(
x
i
)
+
h
(
x
i
)
f({x_i}) = g({x_i}) + h({x_i})
f(xi)=g(xi)+h(xi) 在Astar算法的搜索过程当中,实际代价g(x)是在不断增加的,可以由下式推出:
g
(
x
i
)
=
g
(
x
0
)
+
C
o
s
t
0
,
i
g({x_i}) = g({x_0}) + {\mathop{\rm Cos}\nolimits} {t_{0,i}}
g(xi)=g(x0)+Cost0,i 子节点的代价值等于父节点的代价值加上从父节点到下一个子节点的代价值。代入第二条公式,得到下式:
f
(
x
i
)
=
g
(
x
0
)
+
h
(
x
i
)
+
C
o
s
t
0
,
i
f({x_i}) = g({x_0}) + h({x_i}) + {\mathop{\rm Cos}\nolimits} {t_{0,i}}
f(xi)=g(x0)+h(xi)+Cost0,i 从而有
g
(
x
0
)
+
h
(
x
0
)
≤
g
(
x
0
)
+
h
(
x
i
)
+
C
o
s
t
0
,
i
g({x_{\rm{0}}}) + h({x_{\rm{0}}}) \le g({x_{\rm{0}}}) + h({x_i}) + {\mathop{\rm Cos}\nolimits} {t_{0,i}}
g(x0)+h(x0)≤g(x0)+h(xi)+Cost0,i 即
f
(
x
0
)
≤
f
(
x
i
)
f({x_{\rm{0}}}) \le f({x_i})
f(x0)≤f(xi)在Astar算法的运行过程中,后继的f(x)值时大于当前f(x)的值,即f(x)在之后对子节点的搜索扩展是单调递增的,不会像人工势场法一样出现局部极小值,因此使用Astar算法规划出的路径一定是最优路径.
曼哈顿距离函数在标准坐标系中,表示起始和目标两节点的绝对值总和,其估计值就是从当前点做水平和垂直运动,到达目标点的成本的估计,因此,曼哈顿距离函数中,两点的距离如下
h
(
x
)
=
K
∗
(
∣
x
1
−
x
2
∣
+
∣
y
1
−
y
2
∣
)
h(x) = K*(\left| {{x_1} - {x_2}} \right| + \left| {{y_1} - {y_2}} \right|)
h(x)=K∗(∣x1−x2∣+∣y1−y2∣)K——相邻两节点之间的距离,即单位距离; (x1,y1)——起始节点的坐标; (x2,y2)——目标节点的坐标;
2.5.2 欧几里得距离
欧几里得距离又称为欧式距离,它是衡量两点之间距离远近的最常用的方法之一。欧几里得距离函数的值可以直接看作起始节点和目标节点,在欧式空间中的直线距离,其表达式如下所示
h
(
n
)
=
K
×
(
x
i
−
x
k
)
2
+
(
y
i
−
y
k
)
2
h(n) = K \times \sqrt {{{({x_i} - {x_k})}^2} + {{({y_i} - {y_k})}^2}}
h(n)=K×(xi−xk)2+(yi−yk)2K——相邻两节点之间的距离,即单位距离; (xi,yi)——当前节点的坐标; (xk,yk)——目标节点的坐标;
为了使启发代价的值应该尽量接近于真实值,三维栅格地图中仍然选用欧几里得距离作为估价函数计算启发代价的计算方法。 但本次实验所处的环境为三维避障空间,因此相较于二维空间的路径规划,我们将公式做三维化推广,具体形式如下:
h
(
n
)
=
K
⋅
(
x
0
−
x
k
)
2
+
(
y
0
−
y
k
)
2
+
(
z
0
−
z
k
)
2
h(n) = K \cdot \sqrt {{{({x_0} - {x_k})}^2} + {{({y_0} - {y_k})}^2} + {{({z_0} - {z_k})}^2}}
h(n)=K⋅(x0−xk)2+(y0−yk)2+(z0−zk)2K——相邻两节点之间的距离,即单位距离; (x0,y0,z0)——起始节点的坐标; (xk,yk,zk)——目标节点的坐标; 若要追求最短时间,则可以引入新的代价函数:
f
(
n
)
=
g
(
n
−
1
)
+
D
(
n
−
1
,
n
)
+
h
(
n
)
f(n) = g(n - 1) + D(n - 1,n) + h(n)
f(n)=g(n−1)+D(n−1,n)+h(n)h(n)——当前节点到目标节点的启发代价值; g(n-1)——当前节点到它的父节点之间的路径代价;D(n-1, n)——当前节点与它的子节点之间的代价值。 g(n-1)与二维规划中的距离代价计算方法一致,但D(n-1, n)在计算时用父节点与子节点之间的距离值除以三维避障环境中设定的栅格可通行程度,h(n)也是用当前节点到目标节点的启发代价值除以地图环境中预先设定的栅格可通行程度。
最短路径启发函数:
L
f
(
n
)
=
L
g
(
n
)
+
L
h
(
n
)
{L_{\rm{f}}}\left( n \right) = {L_{\rm{g}}}\left( n \right) + {L_{\rm{h}}}\left( n \right)
Lf(n)=Lg(n)+Lh(n)n——当前节点栅格; Lg(n)——起点栅格与当前节点栅格之间的间隔距离代价(m); Lh(n)——当前节点栅格与目标点栅格之间的间隔距离代价(m)。
L
h
(
n
)
=
∥
n
,
t
a
r
g
e
t
∥
{L_{\rm{h}}}\left( n \right) = \left\| {n,target} \right\|
Lh(n)=∥n,target∥当前节点与目标点之间的欧几里得距离(m).
L
g
(
n
)
=
L
g
(
n
−
1
)
+
c
o
s
t
(
n
−
1
,
n
)
L
{L_{\rm{g}}}\left( n \right) = {L_{\rm{g}}}\left( {n - 1} \right) + cost{\left( {n - 1,n} \right)_{\rm{L}}}
Lg(n)=Lg(n−1)+cost(n−1,n)L上一节点栅格到当前节点栅格之间的间隔距离代价(m)
对以下两种情况做分析,求解出
c
o
s
t
(
n
−
1
,
n
)
L
cost{\left( {n - 1,n} \right)_{\rm{L}}}
cost(n−1,n)L
最终得到的最短路径启发函数如下式:
L
f
(
n
)
=
L
g
(
n
−
1
)
+
1
2
∥
n
−
1
,
n
∥
(
1
cos
(
a
r
c
t
a
n
(
i
n
−
1
)
)
+
1
cos
(
a
r
c
t
a
n
(
i
n
)
)
)
+
∥
n
,
t
a
r
g
e
t
∥
{L_{\rm{f}}}\left( n \right) = {L_{\rm{g}}}\left( {n - 1} \right) + \frac{1}{2}\left\| {n - 1,n} \right\|\left( {\frac{1}{{\cos \left( {{\rm{arctan}}({i_{n - 1}})} \right)}} + \frac{1}{{\cos \left( {{\rm{arctan(}}{i_n})} \right)}}} \right) + \left\| {n,target} \right\|
Lf(n)=Lg(n−1)+21∥n−1,n∥(cos(arctan(in−1))1+cos(arctan(in))1)+∥n,target∥
3.2.2 最短道路损耗功启发函数
道路损耗功启发函数:
W
f
(
n
)
=
W
g
(
n
)
+
W
h
(
n
)
{W_{\rm{f}}}\left( n \right) = {W_{\rm{g}}}\left( n \right) + {W_{\rm{h}}}\left( n \right)
Wf(n)=Wg(n)+Wh(n)n——当前节点栅格; Wg(n)——起点栅格与当前节点栅格的道路损耗功价值(J); Wh(n)——当前节点栅格与目标点栅格的道路损耗功价值(J)。
W
h
(
n
)
=
G
δ
∥
n
,
t
a
r
g
e
t
∥
{W_{\rm{h}}}\left( n \right) = G\delta \left\| {n,target} \right\|
Wh(n)=Gδ∥n,target∥当前节点与目标点之间的欧几里得距离(m).
W
g
(
n
)
=
W
g
(
n
−
1
)
+
c
o
s
t
(
n
−
1
,
n
)
W
{W_{\rm{g}}}\left( n \right) = {W_{\rm{g}}}\left( {n - 1} \right) + cost{\left( {n - 1,n} \right)_{\rm{W}}}
Wg(n)=Wg(n−1)+cost(n−1,n)W上一节点栅格到当前节点栅格之间的的道路损耗功代价(J)
对以下几种情况做分析,求解出
c
o
s
t
(
n
−
1
,
n
)
W
{cost{{\left( {n - 1,n} \right)}_{\rm{W}}}}
cost(n−1,n)W
最终得到的最短道路损耗功启发函数如下式:
W
f
(
n
)
=
W
g
(
n
−
1
)
+
{
G
cos
(
a
r
c
t
a
n
(
i
n
−
1
)
)
δ
n
−
1
+
G
sin
(
a
r
c
t
a
n
(
i
n
−
1
)
)
}
∥
n
−
1
,
n
∥
2
cos
(
a
r
c
t
a
n
(
i
n
−
1
)
)
+
{
G
cos
(
a
r
c
t
a
n
(
i
n
)
)
δ
n
+
G
sin
(
a
r
c
t
a
n
(
i
n
)
)
}
∥
n
−
1
,
n
∥
2
cos
(
a
r
c
t
a
n
(
i
n
)
)
+
G
δ
∥
n
,
t
a
r
g
e
t
∥
\begin{array}{ccccccccccccccc}{{W_{\rm{f}}}\left( n \right) = {W_{\rm{g}}}\left( {n - 1} \right) + \left\{ {G\cos \left( {{\rm{arctan}}({i_{n - 1}})} \right){\delta _{n - 1}} + G\sin \left( {{\rm{arctan}}({i_{n - 1}})} \right)} \right\}\frac{{\left\| {n - 1,n} \right\|}}{{2\cos \left( {{\rm{arctan}}({i_{n - 1}})} \right)}}}\\{\begin{array}{ccccccccccccccc}{}&{}\end{array} + \left\{ {G\cos \left( {{\rm{arctan}}({i_n})} \right){\delta _n} + G\sin \left( {{\rm{arctan}}({i_n})} \right)} \right\}\frac{{\left\| {n - 1,n} \right\|}}{{2\cos \left( {{\rm{arctan}}({i_n})} \right)}} + G\delta \left\| {n,target} \right\|}\end{array}
Wf(n)=Wg(n−1)+{Gcos(arctan(in−1))δn−1+Gsin(arctan(in−1))}2cos(arctan(in−1))∥n−1,n∥+{Gcos(arctan(in))δn+Gsin(arctan(in))}2cos(arctan(in))∥n−1,n∥+Gδ∥n,target∥
3.2.3 综合启发函数
综合启发函数:
L
=
∣
∣
s
t
a
r
t
,
t
a
r
g
e
t
∣
∣
L = ||start,target||
L=∣∣start,target∣∣
W
=
G
δ
∣
∣
s
t
a
r
t
,
t
a
r
g
e
t
∣
∣
W = G\delta ||start,target||
W=Gδ∣∣start,target∣∣
F
(
n
)
=
σ
∗
L
f
(
n
)
/
L
+
τ
∗
W
f
(
n
)
/
W
F\left( n \right) = \sigma *{L_{\rm{f}}}\left( n \right)/L + \tau *{W_{\rm{f}}}\left( n \right)/W
F(n)=σ∗Lf(n)/L+τ∗Wf(n)/W
make an openlist containing only the starting node
make an empty closed listwhile(the destination node has not been reached):
consider the node with the lowest f score in the openlistif(this node is our destination node):
we are finished
ifnot:
put the current node in the closed listand look at all of its neighbors
for(each neighbor of the current node):if(neighbor has lower g value than current andisin the closed list):
replace the neighbor with the new, lower, g value
current node is now the neighbor's parent
elseif(current g value is lower and this neighbor isin the openlist):
replace the neighbor with the new, lower, g value
change the neighbor's parent to our current node
elseif this neighbor isnotin both lists:
add it to the openlistandset its g