Learning real-time A* (LRTA*) 算法

本文代码点击这里下载。

在 learning real-time A* (LRTA*) 算法中，智能体从一个已知的节点开始，进行一个与异步动态规划方法类似的操作，之后移动到一个到目标节点估算距离最短的节点。

LRTA*算法的伪代码如下。

LRTA*算法伪代码

假设节点的数量是有限的，并且边的值都是有限的正数。为了达到LRTA*的一些特性，我们必须假设是“可接受的”（admissible），这里指.

LRTA*算法由如下特点：

• 的值不减少，且是“可接受的”(admissible)。
• 算法停止后，从起始节点到目标节点的路径被称为trial.
• 如果算法在相邻trial中维护h的值，那么算法最终会找到一条从起始点到目标点的最短路径
• 如果算法在相邻的两次循环中找到一样的trial，则此trial即为最优解。

一个ASYNCDP算法的例子：

LRTA*算法寻找最短路径的例子