[AI] LRTA*(K) 搜索算法

一、理论

LRTA*(K) 是LRTA* 算法的进阶版，关于LRTA*的回顾请点此处， LRTA*(K) 论文请点此处

该文作者把LRTA算法归为 无界传播(unbounded propagation, 中文用谷歌翻译的。。。囧)，LRTA(K)归为有界传播(bounded propagation)

所谓无界传播：先让agent移动到新的位置，然后更新上一个位置的 h(n)， 这样并不会立即更新该新位置的 h(n)，而是指望未来再次移动后才会更新该位置的值。被更改 h 后的位置的影响会进一步传播给其后继，依此类推。 该过程不断迭代，直到没有执行进一步的更改。

有界传播：限制一步最多只能更新有限K个位置的h ，这样用于传播的计算量就是有界的。在此说明：这k个位置只能是从初始位置到当前位置的路径之间的位置

LRTA* 算法的缺点如下：

• 在有限的时间内移动。无界传播中涉及的状态数在连续步骤中可能不同，因此所需的计算量可能会在步骤之间发生变化（说实话，这里我没看懂）。 这违背了实时搜索必须在限定时间内执行单个移动的要求。

• 作用于附近。 无界传播可以远离当前状态。 这违反了实时搜索的基本假设，即前瞻和更新操作只能在当前状态附近完成。（我没明白，无界传播不也是在当前状态附近来回震荡直到跳出局部最小值吗？）

LRTA*(K)优势如下：

• 初解：如果第一个解不涉及循环，LRTA*(K)将表现为LRTA*，然而，这种情况很少发生。实验上，LRTA*(K)在较短的计算时间内发现了比LRTA更短的解。

• 收敛：LRTA*(K)记录的h值更接近精确值，这导致LRTA*(K)在测试基准中比LRTA*(步骤数、试验次数和总CPU时间)更快地收敛。其他算法(FALCONS)也会出现这种情况。

• 解的稳定性：获得更高质量的解使解决方案和增加的稳定性之间的差异更小。

二、实际应用步骤

题目介绍：

• 如图A左侧，有这么一个网格，每个格子都用字母标了号便于说明

• 右侧是每个格子初始的h值，“-” 表示墙，数字表示可走的路径。

• 格子m是起点，p是终点，每个格子之间的代价 g = 1。

使用 LRTA*(K) 算法的步骤如下：

• 首先先设定 k=5， 那么m的h值就直接更新到 h(m) = 5。由于路径上没有其他位置，也就没有传播。在这次迭代中，1个位置(m)被考虑更新

• Agent移动到位置 i， h(i) 直接更新 h(i) = h(m) + g(m, i) = 5 + 1 = 6。 此时考虑当前位置 i 的前一个位置 m 的 h 值，考虑 m 的 h 值更新 h(m)=6+1=7，考虑 m 的后继 h(i)的值，h(i)不变。在这次迭代中，3个位置(i, m, i) 被考虑到

• Agent移动到位置 e，h(e) 更新到h(e) = h(i) + g(i, e) = 6+1 = 7。考虑当前位置 e 的前一个位置 i 的h值，h(i) = 7+1=8, i 有两个后继 m 和 e（均在路径上），h(e) 不更新，h(m) = 8+1=9。然后考虑m的后继 i，h(i)不变。在这次迭代中，5个位置(e, i, e, m, i) 被考虑到。

• Agent移动到a，最终移动到目标 g

写在最后，其实我也理解的不是很深，具体算法如下：