Learning real-time A* (LRTA*) 算法求最短路径

本文代码点击这里下载。

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

LRTA*算法的伪代码如下。

LRTA*算法伪代码

假设节点的数量是有限的,并且边的值都是有限的正数。为了达到LRTA*的一些特性,我们必须假设h是“可接受的”(admissible),这里指h(i) \leq h^* (i).

LRTA*算法由如下特点:

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

一个ASYNCDP算法的例子:

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注