路径规划——搜索算法详解(六):LPA*算法详解与Matlab代码

上文讲解了D*算法,D*算法为在动态环境下进行路径规划的场景提出了可行的解决方案,本文将继续介绍另外一种动态规划路径的方法——Lifelong Planning A*(LPA*)算法。

该算法可以看作是A*的增量版本,是一种在固定起始点与目标点、动态环境下实时搜索路径的算法。笔者看了很多篇讲解、原文后发现许多文章描述得云里雾里,本文可以看作是笔者对于古月学院LPA*算法的学习笔记,希望本文的算法讲解与MATLAB仿真能够给大家带来理解上的帮助!

一、LPA*算法流程讲解:

1. 基本概念:

  • 符号表示:
    • g(s):之间记录的起点距离代价的最小值;
    • rhs(s):基于父节点g所预测的最小值,设s'为s的父节点,此时有rhs(s)=g(s')+d(ss'),d(ss')表示s与父节点s‘的连接代价
    • 对于每一个节点,其记录着一个代价很熟k(n),其决定了S中的弹出顺序,类比于A*算法中的Openlist弹出的规则,其包含两个值,根据k1优先排序,当k1相同时根据k2排序,其计算方式如下:                                      

    • S:地形图中路径点集合
    • U:优先队列,每次弹出k值最小的节点s;
  • 与D*算法中采用h(X)、k(X)表示每个节点实时更新的代价、最小更新代价类似,LPA*算法采用rhs(s)、g(s)两个值表示每一个搜索点的本次计算中起始点到当前节点的代价值、目前所有次计算中从起始点到当前节点的最小代价值,注意D*是从终点开始搜索的,而LPA*算法是从起点开始搜索,所以衡量指标rhs(s)、g(s)均表示到起点的距离,这要注意不要跟D*混淆。根据rhs(s)、g(s)的大小关系定义节点的状态:
    • rhs(s)=g(s):局部一致状态,表示当前节点并未造成影响,类比于D*算法中的Lower态;
    • rhs(s)<g(s):局部过一致状态,即当前代价小于记录的历史代价,表明当前节点可以寻找到更加适合的父节点以减小到起点的代价值,更新代价:g(s)=rhs(s);此时该节点的后续子节点必定受到影响,此时需要遍历后续子节点,对于每一个后续子节点更新其rhs,检查其子节点是否能恢复到历时最小代价g,当不可恢复时将其插入搜索队列,使节点恢复到局部一致;
    • rhs(s)>g(s):局部欠一致状态,即当前代价大于记录的历史代价,此时表示该节点受到障碍物影响,遍历后续节点更新代价。一般由于父节点突变情况所致,需要将此节点g设置为∞,将其状态改为局部过一致,对于局部过一至的点在下一次循环中更新其g(s)达到局部一致状态。

2. 算法流程解释:

参考论文中的伪代码与符号解释,如下所示:

直接看代码流程会很混乱,待会会有案例讲解,有以下绩点关键需要注意,老规矩留个印象就好,看完例子再回来会有收获的:

1. 搜索过程不断重复事情是:搜索节点达到局部一致;

2. 搜索完成的指标如下(两者之一)如果目标的代价为无穷大,那么从开始到目标没有有限的代价路径。否则,最短路径可以通过向后移动来确定。

        (1)搜索队列U中最小k值大于目标点k值;

        (2)目标节点达到局部一致且不为inf;

3. 当节点s发生变化时,需要检查其所有子节点,更新子节点的rhs值,将局部一致的节点从搜索列表中删除,将受影响导致局部不一致的节点加入到搜索队列U中,并及时更新局部不一致节点的k值,不断循环该过程直到达到2中的搜索指标。

4. 增量式搜索是基于初次完成A*搜索的结果上进行的,需要进行初次搜索。

5. 上述流程中的函数含义如下:

3. 案例讲解(案例出于古月学院):

(1).初始化:

在增量式搜索开始前,求出路径点集合S中每一个自由栅格的起点的实际最小代价g*、终点启发函数h,笔者感觉此处启发函数用的是切比雪夫距离:

(2).起点搜索处理

首先将所有节点的距离起点代价rhs、记录最小的起点代价g初始化为inf,由于起点本身距离为0,所以此时rhs(A3)=0,g(A3)=∞,此时rhs(A3)!= g(A3),局部不一致,此刻将其插入到优先级队列U中。如上图所示,每一个节点处包含k=[k1,k2],后续将根据此从U中弹出元素。

(3).拓展节点(循环1):

此时弹出A3点, 此时到流程中的步骤2(代码09-16),rhs(A3)=0,g(A3)=∞,此时rhs(A3)<g(A3),令g(A3)=rhs(A3)=0(代码12),此时A3点局部一致,g(A3)=rhs(A3)=0,故确定为代价0。

同时遍历A3在第一次搜索时候的子节点(看(1)中相连接且以A3作为父节点的A2、B3),此时将A2、B3分别带入UpdateVertex函数(代码06-08)中此时根据节点A3更新rhs(A2)=g(A3)+d(A2、A3之间的距离) = 0+1=1、rhs(B3)=g(A3)+d(A3、B3之间的距离) = 0+1=1,此时由于初始化时候g(A2)=g(B3)=inf>1,此时A2、B3局部过一致,将其加入到队列U中,此时U中元素为U={A2(6,1),B3(5,1)}。

(4).弹出节点(循环2):

跟上述流程相同,弹出k最小的节点,此时U中最小的为B3,首先令其g(B3)=rhs(B3)=1,达到局部一致,此时记为1,将流程(1)中对应的子节点(C3)带入代码(代码06-08)中,步骤与上次循环一样,应该很好理解。

(5).不断循环直到结束:

不断循环计算,更新节点状态,直到满足跳出循环的条件,按照序号排序即可得到一条最佳轨迹。

(6).节点状态改变处理步骤:

如上图所示,当D1节点突变为障碍物时,此时rhs(D1)=inf,此时节点D1变为欠一致状态,此时检查其所有与之相连接的节点(代码21-23行),此时如上图#1-#4所示,其子节点(子节点定义为在路径中排列在该节点后的所有路径节点E1、F0,而F1父节点为E1,也会受到影响)由于其状态变化也变为了欠一致状态(代码14-16行),此时rhs(E1、F0、E1)= inf,故此时的图变为了#4的状态,灰色的为上次搜索得到结果后在U序列中的节点。此时U={A0(8,3)、E3(7,4)}。此时弹出E3,循环执行代码步骤2,根据上述流程即可得到一条新的路径

大家看完案例讲解后再看一遍上述的1、2部分,相信会有新的收获!

二、LPA*算法代码:

这是笔者按照课程打出来的代码,已经上传到了本人Github,需要的自取:
Adamaser/Path-Planning (github.com)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520477.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

P8749 [蓝桥杯 2021 省 B] 杨辉三角形

[蓝桥杯 2021 省 B] 杨辉三角形 题目描述 下面的图形是著名的杨辉三角形: 如果我们按从上到下、从左到右的顺序把所有数排成一列&#xff0c;可以得到如下数列&#xff1a; 1 , 1 , 1 , 1 , 2 , 1 , 1 , 3 , 3 , 1 , 1 , 4 , 6 , 4 , 1 , … 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1, …

背包问题---

一、背包模型 有一个体积为V的背包,商店有n个物品,每个物品有一个价值v和体积w,每个物品只能被拿一次,问能够装下物品的最大价值。 这里每一种物品只有两种状态即"拿"或"不拿". 设状态dp[i][j]表示到第i个物品为止,拿的物品总体积为j的情况下的最大价…

网络网络层之(3)IPv6地址

网络网络层之(3)IPv6协议 Author: Once Day Date: 2024年4月2日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文档可参考专栏&#xff1a;通信网络技术_Once-Day的…

简化备案域名查询的最新API接口

随着互联网的发展&#xff0c;越来越多的网站和域名被注册和备案。备案域名查询是一个非常重要的功能&#xff0c;可以帮助用户在特定时间段内查询已备案的域名信息。现在&#xff0c;我将介绍一个简化备案域名查询的最新API接口&#xff0c;该接口可以帮助用户快速查询备案域名…

SQL 注入神器:jSQL Injection 保姆级教程

一、介绍 jSQL Injection是一种用于检测和利用SQL注入漏洞的工具&#xff0c;它专门针对Java应用程序进行SQL注入攻击。以下是关于jSQL Injection的一些介绍&#xff1a; 功能特点&#xff1a; 自动化扫描&#xff1a; jSQL Injection具有自动化扫描功能&#xff0c;能够检测J…

Cesium入门路上的问题解决和知识点集合

想要进行cesium事件处理&#xff0c;必然会涉及到Cesium.ScreenSpaceEventHandler(viewer.scene.canvas)但是与js不同&#xff0c;viewer的位置要先于viewer调用代码大小写错了&#xff0c;就会找不到构造的东西​ 练习时这个方法无效主要是setInputAction方法的括号位置错误应…

精品推荐-2024护网HVV实战教程资料合集(共20章)

以下是资料目录&#xff0c;如需下载&#xff0c;请前往星球获取&#xff1a;https://t.zsxq.com/19vwYrf4t 精品推荐&#xff0c;2024护网HVV实战教程资料合集&#xff0c;压缩包内涵大量实战资料&#xff0c;共20章。星球内会持续更新教程包。 01-HW介绍.zip 02-HTTP&Bu…

揭秘微信如何设置自动回复

01 自动通过好友后自动回复设置 02 个人聊天的关键字自动回复设置 不仅如此&#xff0c;在微信私域管理系统上还可以进行批量多个号自动添加好友、批量群发、定时发朋友圈等操作&#xff0c;可以大幅度提升工作效率&#xff0c;将繁琐的任务交给系统来完成&#xff0c;从而节省…

【【萌新的Pytorch入门之Python的学习】】

学习记录 - 参考记录来自B站up主 -爆肝杰哥 ① NumPy 包为 Python 加上了关键的数组变量类型&#xff0c;弥补了 Python 的不足&#xff1b; ② Pandas 包在 NumPy 数组的基础上添加了与 Excel 类似的行列标签&#xff1b; ③ Matplotlib 库借鉴 Matlab&#xff0c;帮 Python 具…

论文《Structural Information Enhanced Graph Representation for Link Prediction》阅读

论文《Structural Information Enhanced Graph Representation for Link Prediction》阅读 论文概况Introduction问题一&#xff1a;**现有的节点标记技巧只能帮助感知路径深度&#xff0c;而缺乏对路径“宽度”的感知&#xff0c;例如节点度或路径数量**。问题二&#xff1a;G…

软考117-上午题-【计算机网络】-杂题+小结

一、杂题 真题1&#xff1a; 真题2&#xff1a; 真题3&#xff1a; 真题4&#xff1a; 真题5&#xff1a; 真题6&#xff1a; 真题7&#xff1a; 真题8&#xff1a; 真题9&#xff1a; 真题10&#xff1a; 真题11&#xff1a; 真题12&#xff1a; 真题13&#xff1a; 真题14&a…

【算法集训】基础算法:二分查找 | 概念篇

二分枚举&#xff0c;也叫二分查找&#xff0c;指的就是给定一个区间&#xff0c;每次选择区间的中点&#xff0c;并且判断区间中点是否满足某个条件&#xff0c;从而选择左区间继续求解还是右区间继续求解&#xff0c;直到区间长度不能再切分为止。 由于每次都是把区间折半&am…

AUTOSAR MCAL for SemiDrive E3 功能模块使用介绍:I2C

一、 概述 本文主要介绍如何使用芯驰提供的 AUTOSAR MCAL 软件包&#xff0c;开发 SemiDrive E3 的 I2C 模块&#xff0c;对 RTC 芯片进行读写操作。 硬件使用 E3640 GATEWAY 开发板&#xff0c;软件包为 mcal3.1。 图1 硬件环境 二、模块简介 E3 系列最多支持 8 个 I2C&am…

【51单片机入门记录】A/D D/A转换器概述

目录 一、A/D D/A转换器简介 &#xff08;1&#xff09;模数转换器-ADC &#xff08;analogue-to-digital conversion&#xff09; &#xff08;2&#xff09;数模转换器-DAC&#xff08;digital-to-analogue conversion&#xff09; &#xff08;3&#xff09;应用场景 二…

全国计算机等级考试三级Linux应用与开发技术考试-习题汇总

https://blog.csdn.net/qq_42025798/article/details/119155696 3.第1章-计算机体系结构与操作系统-练习题-简答题 https://blog.csdn.net/qq_42025798/article/details/119186151 4.第1章-计算机体系结构与操作系统-练习题-填空题 https://blog.csdn.net/qq_42025798/article/…

gulp项目配置,压缩css,压缩js,进行监听文件改动

1&#xff0c;创建项目 npm install -g gulp这个应该很熟悉&#xff0c;就是全局安装gulp 2&#xff0c;创建一个工程&#xff0c;使用node创建&#xff0c;统一命令 npm init -y3,创建后&#xff0c;目录出现一个package.json文件&#xff0c;没错&#xff0c;就是我们用vu…

【Leetcode每日一题】模拟 - 外观数列(难度⭐⭐)(51)

1. 题目解析 题目链接&#xff1a;38. 外观数列 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 2.算法原理 所谓“外观数列”&#xff0c;其实只是依次统计字符串中连续且相同的字符的个数。依照题意&#xff0c;依次模拟即 可。…

Java面向对象进阶基础知识

面向对象进阶 static 静态变量 被该类的所有的对象共享 不属于对象,属于类 随着类的加载而加载,优先于对象存在 类名调用(推荐) 对象名调用 static的注意事项 静态方法中没有this关键字 静态方法,只能访问静态 非静态方法可以访问所有 在Java中&#xff0c;static关…

元宇宙虚拟空间的碰撞体检测(四)

前言 该文章主要讲元宇宙虚拟空间的碰撞体检测&#xff0c;基本技术点&#xff0c;不多说&#xff0c;直接引入正题。 碰撞体检测 这里可以看到检测代码的逻辑是经过一系列判断&#xff0c;最后判断模型类型属性如果是trimesh&#xff0c;那么通过解析出来的顶点来生成我们的…