[AI] LRTA*ls(k)搜索算法
LRTA*LS[K]
- 一、LRTA*(K)算法的缺点
- 二、LRTA∗LS(k)LRTA*_{LS}(k)LRTA∗LS(k)算法
- 1、选择局部空间
- 2、更新局部空间
论文在这里！
一、LRTA*(K)算法的缺点
LRTA*(K)算法每次要更新队列Q里的state，但有三点缺陷：
-
如果state y进入 Q，但重考虑后 h(y) 不会改变，这是一种浪费时间的努力
-
可能有的state进入Q不止一次，要经过多次更新才能打到最终值
-
进入Q的state的顺序以及K的取值都会影响最终结果
下面举个栗子说明：
如图（i）， a, b, c, d是state，最左侧那一列是迭代次数，state下边的数字是 h 值，每次移动 g = 1，后继按左-右的顺序改变。
下边是每次迭代运行的具体步骤(一定注意是左右的顺序进入Q，然后每次迭代就是从Q里按顺序取state)：
-
第零次迭代：当前state是d，迭代0那一行的数字是初始 h 值，h(d)一开始是2，得先考虑d，把d加入Q，Q = {d}，这就是为什么后文说d进Q两次，这里还有一次他没写出来！
-
第一次迭代：h(d)=4， Q={c} -----这里就是，d改变后，考虑左边的c，右边没东西
-
第二次迭代：h( c ) = 5, Q={b, d} -----这里是第一次移动，移动到c点，然后考虑c左右的state{b, d}，放入Q
-
第三次迭代：h(b)不变 ----这里并没有移动，agent还在c，b是从Q里取出来的，看它要不要更新，下一个就取d出来。
-
第四次迭代：h(d) = 6, Q = {c} -----你看我说要取d出来看看要不要更新吧？d需要更新，如果d更新了，那下一个就要考虑d的后继了，那就是c，c就先进入Q
-
第五次迭代：h( c )不变 ----然后把c从Q取出来，c不变
-
然后没有需要更新的就停下了。
在这个过程中，c和d进入Q两次，d更新了两次，c只更新了一次。整个流程，一共就走了一步，走之前的整个Q={d}， 走一步移动到c后，Q = {c, b, d, c}。
然后文中说，如果K=3，且还是左右顺序进入Q，那么进入Q的顺序就是d, c, b，就如图 (ii) 所示。我不理解，第一个 d 是第一步呀，为啥要加在这里？不加d的话，走了第一步到C，Q={c, b, d}，我觉得和上边结果一样的呀？不理解。。。
二、LRTA∗LS(k)LRTA*_{LS}(k)LRTA∗LS(k)算法
算法概览：LRTA∗LS(k)LRTA*_{LS}(k)LRTA∗LS(k) 算法把states分为内部states（用集合 I∈XI \in XI∈X 表示, X是所有state的集合）和边缘states （用集合 F∈XF \in XF∈X 表示），I∩F=∅I \cap F=\emptysetI∩F=∅，LRTA∗LS(k)LRTA*_{LS}(k)LRTA∗LS(k) 选择当前状态的局部空间并更新其内部state, 内部states只更新一次值，内部states的数量上限为K（集合 I 的长度最高为K），该算法继承 LRTA* 和 LRTA*(K) 的良好属性。
1、选择局部空间
步骤如下：
-
设 I=∅I = \emptysetI=∅, Q = {x| x是当前state}
-
循环直到 Q 空了或者 ∣I∣==K|I| == K∣I∣==K:
从Q中提取state w， 如果 w 就是目标，就跳出循环。否则，检查是否存在 h(w)
其中h(w)h(w)h(w)是state w的启发值，{Succ(w)−I}\{Succ(w)-I\}{Succ(w)−I}表示w的所有后继state Succ(w)Succ(w)Succ(w) 减去 I 集合中的交集，剩下的不在 I 中的后继state，g(w, v)表示从state w 到 v 的路程代价。
如果满足上式（文中称之为“更新条件”），就把 w 加入 I，v 加入 Q -
把 I 中所有state的不在I中的后继state加入边缘集合 F
下面是一个例子说明（我觉额的原文说的好像不太对呢，虽然最后结果对，但中间过程和他上边步骤里写的不太一样啊，而且一点都没提Q更新的事儿，下面是我按他的步骤+我自己理解写的，各位有兴趣可以去看看原文这部分）
在这里插入图片描述
如上图所示，state之间的路程代价 g = 1，
-
从 d 点开始，那么一开始 Q=d,I=∅Q={d}, I = \emptyQ=d,I=∅
-
然后开始进入第二步的循环，从Q中取出d，判断 h(d)
-
把 c 从 Q 中取出，c的后继有俩，b和d，其中d已经在 I 中了，所以只看b就行了，3<4+13<4+13<4+1也成立，那么把 c 加入 I，现在 I = {c, d}，把 b 加入 Q
-
把 b 从Q中取出，b也有俩后继，a和c，因为 c 在 I 中了，所以只考虑 a，4=3+14 = 3+14=3+1，条件不成立了，就不能把 b 加入 I， 同样 a 也不能进入 Q
-
a 没有进入 Q，那么 Q 就空了，循环终止！
-
此时我们得到了内部state的集合 I={c,d}I = \{c, d\}I={c,d} ， 然后把c，d的不在 I 的后继加入边缘集合F={b}
-
程序终止！
2、更新局部空间
步骤如下：
当 内部集合 I 非空时置行下列循环：
-
计算连接state对 (i,f),i∈I,f∈F,f∈Succ(i)(i, f), i \in I, f \in F, f \in Succ(i)(i,f),i∈I,f∈F,f∈Succ(i)
-
更新 h(i)=g(i,f)+h(f)h(i) = g(i, f) + h(f)h(i)=g(i,f)+h(f)
-
把 iii从 III 中移除，把 iii 加入 FFF
还是上边那个例子，我们第一部分已经计算好了局部空间 I=c,d,F=bI = {c, d}, F={b}I=c,d,F=b，开始更新局部空间
-
I=c,dI = {c, d}I=c,d，非空，此时先进入while循环
-
由于F里只有b，满足条件的对儿就一对儿，(c, b)
-
开始更新 h(c)=g(c,b)+h(b)=1+4=5h(c) = g(c, b) + h(b) = 1+4=5h(c)=g(c,b)+h(b)=1+4=5
-
把 c 从 I 中移除，把 c 加入 F
-
此时 I={d}，非空，继续循环
-
此时 F={c}，那么就只有一对儿 (d, c)
-
开始更新 h(d)=g(d,c)+h(c)=1+5=6h(d) = g(d, c) + h(c) = 1+5=6h(d)=g(d,c)+h(c)=1+5=6
-
将 d 从 I 中移除，并加入 F
-
此时 I 空了，跳出循环
-
程序结束！
感觉有点东西哦兄弟们，喜欢就一键三连吧，有任何问题或者见解也请评论区留言！