基于图搜索的自动驾驶规划算法 - BFS,Dijstra,A*

2023-12-27 13:45

本文主要是介绍基于图搜索的自动驾驶规划算法 - BFS,Dijstra,A*,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文将讲解BFS,Dijstra,A*,动态规划的算法原理,不正之处望读者指正,希望有兴趣的读者能在评论区提出一些这些算法的面试考点,共同学习,一起进步

0 图论基础

图有三种:无向图、有向图、带权重的图
无向图
Alt有向图
Alt

带权重的图
Alt

1 BFS

广度优先搜索算法
利用队列queue数据结构实现:先进先出
在这里插入图片描述
算法流程(伪代码):

BFS(G, start, goal):let Q be queue;Q.push(start);mark start as visited;while (!Q.empty()){v = Q.front();Q.pop();if (v is the goal) return v;for all neighbours n of v in GQ.push(n);n->parent = v;mark n as visited;}

BFS总结:
(1)相同探索所有的方向
(2)如果所有边权重为1,那么用BFS搜索出来的路径是cost最优的
(3)在不同的场景中,不能保证所有的边权重为1,对于这些场景,BFS受限

2 Dijstra

核心思想:
(1)相比BFS,Dijstra维护一个新变量g(n),g(n)表示从起始节点到当前节点的累积成本
(2)从openset(Min-priority queue)中访问累积成本g最低的节点

算法流程(伪代码):

Dijstra(G, start, goal):let open_list be priority_queue;open_list.push(start, 0);g[start] = 0;while (!open_list.empty()){current = open_list.pop();mark current as visited;if (current is the goal) return current;for (all unvisited neightbours next of current in G){next_cost = g[current] + cost(current, next);if (next is not in open_list)open_list.push(next, next_cost);else {if (g[next] > next_cost)g[next] = next_cost;}}}

优点:
(1)Dijstra算法能找到从起始节点到图上所有其他节点的最短路径
(2)Dijstra算法满足最优性
缺点:每次都会从open_list寻找代价最少的节点,但是并不知道终点在哪,如果用这个算法做图中特定两个点的最短路径,是比较低效的

3 A*算法

A*算法手撕版本见手撕A算法(详解A算法)

核心思想:

(1)相比Dijstra,A*将目标点的成本估计为启发式信息以提高效率
(2)启发式函数h(n):表示从节点n到目标的估计成本
(3)评估每个节点的成本函数:f(n)=g(n)+h(n)
(4)从open_list选择f-score最低的节点,而不是Dijstra算法中的g-score

算法流程(伪代码):
Astar(G, start, goal):let open_list be priority_queue;g[start] = 0;f[start] = g[start] + h[start];open_list.push(start, f[start]);while (!open_list.empty()){current = open_list.pop();mark current as visited;if (current is the goal) return current;for all unvisited neighbours next of current in Gnext_cost = g[current] + cost(current, next);if (next is not in open_list)open_list.push(next, next_cost + h[next]);else{if (g[next] > next_cost) {g[next] = next_cost;f[next] = next_cost + h[next];}}}
启发式函数设计

在路径搜索过程中,没有唯一启发函数设计原则,需要根据特定的任务来设计,如果最优性和距离相关,则可以计算节点之间的直线距离来估计

三种常用的距离:
起点: ( p 1 , p 2 ) (p_1, p_2) (p1,p2) 终点: ( q 1 , q 2 ) (q_1, q_2) (q1,q2)
(1)Euclidian distance
d ( p , q ) = ( q 1 − p 1 ) 2 + ( q 2 − p 2 ) 2 d(p,q)=\sqrt{(q_1-p_1)^2+(q_2-p_2)^2} d(p,q)=(q1p1)2+(q2p2)2
(2)Manhattan distance
d ( p , q ) = ∣ q 1 − p 1 ∣ + ∣ q 2 − p 2 ∣ d(p,q)=|q_1 - p_1|+|q_2 - p_2| d(p,q)=q1p1+q2p2
(3)Great circle distance
Alt
△ σ = a r c c o s ( s i n ϕ 1 s i n ϕ 2 + c o s ϕ 1 c o s ϕ 2 c o s ( △ λ ) ) \bigtriangleup \sigma =arccos(sin\phi _1sin\phi_2+cos\phi_1cos\phi_2cos(\bigtriangleup\lambda )) σ=arccos(sinϕ1sinϕ2+cosϕ1cosϕ2cos(λ))

d = r △ σ d = r\bigtriangleup \sigma d=rσ

最优性

启发式函数 h ( n ) < c o s t ( n , g o a l ) h(n)<cost(n,goal) h(n)<cost(n,goal)
只要启发式函数提供了小于实际成本的估计,A*将始终找到最优路径,并且通常比Dijstra快
在这里插入图片描述
实际上A->B->D是最短路径
因为B的启发式函数高估了对目标的成本

这种高估导致搜索算法相信节点C总成本低于节点B,使得节点C在节点B之前访问,导致结果不是最优路径

在gridmap中如何设计启发式函数
在这里插入图片描述

使用8连接,曼哈顿距离启发式高估了成本
欧几里得距离总是可以接受

A*算法的精度和效率
在这里插入图片描述

(1) h ( n ) = 0 h(n)=0 h(n)=0:A退化为Dijstra
(2) h ( n ) < c o s t ( n , g o a l ) h(n)<cost(n,goal) h(n)<cost(n,goal):A
满足最优性,效率比Dijstra更高
(3) h ( n ) = c o s t ( n , g o a l ) h(n)=cost(n,goal) h(n)=cost(n,goal):A满足最优性,并且有最高的效率
(4) h ( n ) > c o s t ( n , g o a l ) h(n)>cost(n,goal) h(n)>cost(n,goal):A
不满足最优性,高估实际成本

BFS、Dijstra、A*总结:

BFSDijstraA*
(1)BFS算法会朝着周围等价扩展(1)相比BFS,Dijstra倾向于累积成本最小化,不是平等地搜索所有可能的路径,能在加权图中满足最优性(1)A*是Dijstra的修改,添加了启发式函数h(n)提高搜索效率
(2)如果每条边权重为1,BFS搜索出来的path也是最优解(2)如果每条边权重为1,BFS=Dijstra(3)启发式函数的设计会影响效率和准确性

搜索算法可视化参考:http://qiao.github.io/PathFinding.js/visual/

4 动态规划

  1. 定义:

一种计算机编程方式,首先把算法问题分解为子问题,求解这些子问题,并把这些结果保存下来,然后优化子问题找到整个问题的最优解

  1. 动态规划的性质:

(1)最优子结构

面对一个大问题可以分解为一系列子问题。如果能找到每个小问题的最优解,并且能够把小问题拼成大的问题。这种问题就叫最优子结构

(2)重复的子问题

动态规划不会重新计算重复的子问题,会事先保存结果

在这里插入图片描述
在这里插入图片描述
3. 计算方法
(1)前向法
在这里插入图片描述

(2)逆向法
在这里插入图片描述

这篇关于基于图搜索的自动驾驶规划算法 - BFS,Dijstra,A*的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/543325

相关文章

Python脚本实现自动删除C盘临时文件夹

《Python脚本实现自动删除C盘临时文件夹》在日常使用电脑的过程中,临时文件夹往往会积累大量的无用数据,占用宝贵的磁盘空间,下面我们就来看看Python如何通过脚本实现自动删除C盘临时文件夹吧... 目录一、准备工作二、python脚本编写三、脚本解析四、运行脚本五、案例演示六、注意事项七、总结在日常使用

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

SpringBoot项目启动后自动加载系统配置的多种实现方式

《SpringBoot项目启动后自动加载系统配置的多种实现方式》:本文主要介绍SpringBoot项目启动后自动加载系统配置的多种实现方式,并通过代码示例讲解的非常详细,对大家的学习或工作有一定的... 目录1. 使用 CommandLineRunner实现方式:2. 使用 ApplicationRunne

Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单

《Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单》:本文主要介绍Springboot的ThreadPoolTaskScheduler线... 目录ThreadPoolTaskScheduler线程池实现15分钟不操作自动取消订单概要1,创建订单后

python实现自动登录12306自动抢票功能

《python实现自动登录12306自动抢票功能》随着互联网技术的发展,越来越多的人选择通过网络平台购票,特别是在中国,12306作为官方火车票预订平台,承担了巨大的访问量,对于热门线路或者节假日出行... 目录一、遇到的问题?二、改进三、进阶–展望总结一、遇到的问题?1.url-正确的表头:就是首先ur

Spring使用@Retryable实现自动重试机制

《Spring使用@Retryable实现自动重试机制》在微服务架构中,服务之间的调用可能会因为一些暂时性的错误而失败,例如网络波动、数据库连接超时或第三方服务不可用等,在本文中,我们将介绍如何在Sp... 目录引言1. 什么是 @Retryable?2. 如何在 Spring 中使用 @Retryable

使用 Python 和 LabelMe 实现图片验证码的自动标注功能

《使用Python和LabelMe实现图片验证码的自动标注功能》文章介绍了如何使用Python和LabelMe自动标注图片验证码,主要步骤包括图像预处理、OCR识别和生成标注文件,通过结合Pa... 目录使用 python 和 LabelMe 实现图片验证码的自动标注环境准备必备工具安装依赖实现自动标注核心

QT实现TCP客户端自动连接

《QT实现TCP客户端自动连接》这篇文章主要为大家详细介绍了QT中一个TCP客户端自动连接的测试模型,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录版本 1:没有取消按钮 测试效果测试代码版本 2:有取消按钮测试效果测试代码版本 1:没有取消按钮 测试效果缺陷:无法手动停

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系