路径规划算法matlab_路径规划——Lifelong Planning A*算法

作者：小小林熬夜学编程 | 2024-03-09 07:29:36

踩

lifelong planning

简介

LPA*算法，即Lifelong Planning A*算法，该算法于2001年由Sven Koenig和Maxim Likhachev提出，是一种增量启发式搜索版本的A*算法，这种路径规划算法适用于随着时间改变导致有限栅格地图上的边缘代价c(s1,s2)改变的问题，也就是随着时间改变障碍物增多或减少，网格点发生增删等，在许多场合下比再利用A*重新搜索更高效。

启发式搜索和增量式搜索的区别在于，启发式搜索是利用启发函数来对搜索进行指导，从而实现高效的搜索，启发式搜索是一种“智能”搜索，典型的算法例如A*算法、遗传算法等。增量搜索是对以前的搜索结果信息进行再利用来实现高效搜索，大大减少搜索范围和时间，典型的例如LPA*、D* Lite算法等。

和A*算法一样，LPA*算法采用非负、一致性的启发函数

表示当前位置网格点

到目标点

的距离的估计，

一致性体现在服从以下三角不等式，可以由简单的三角形几何性质可以推出：

其中

且

，如图1所示：

图1

或

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/213926?site