首页 > 编程语言 >路径规划(2)——A*算法

路径规划(2)——A*算法

时间:2024-07-09 10:19:26浏览次数:14  
标签:open 路径 list 算法 方格 规划 节点 起点

1、A*算法原理

  • 搜索区域(The Search Area):图中的搜索区域被划分为了简单的二维数组,数组每个元素对应一个小方格,当然我们也可以将区域等分成是五角星,矩形等,通常将一个单位的中心点称之为搜索区域节点(Node)。  
  • 开放列表(Open List):我们将路径规划过程中待检测的节点存放于Open List中,而已检测过的格子则存放于Close List中。
  • 父节点(parent):在路径规划中用于回溯的节点,开发时可考虑为双向链表结构中的父结点指针。
  • 路径排序(Path Sorting):具体往哪个节点移动由以下公式确定:F(n) = G + H 。G代表的是从初始位置A沿着已生成的路径到指定待检测格子的移动开销。H指定待测格子到目标节点B的估计移动开销。
  • 启发函数(Heuristics Function):H为启发函数,也被认为是一种试探,由于在找到唯一路径前,我们不确定在前面会出现什么障碍物,因此用了一种计算H的算法,具体根据实际场景决定。在我们简化的模型中,H采用的是传统的曼哈顿距离(Manhattan Distance),也就是横纵向走的距离之和。

  如下图所示,绿色方块为机器人起始位置A,红色方块为目标位置B,蓝色为障碍物。

 

 

                        

我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步,简化搜索区域。这个特殊的方法把我们的搜索区域简化为了 2 维数组。数组的每一项代表一个格子,它的状态就是可走 (walkalbe)或不可走 (unwalkable) 。现用A*算法寻找出一条自A到B的最短路径,每个方格的边长为10,即垂直水平方向移动开销为10。因此沿对角移动开销约等于14。具体步骤如下:

从起点 A 开始,把它加入到一个由方格组成的open list(开放列表) 中,这个open list像是一个购物清单。Open list里的格子是可能会是沿途经过的,也有可能不经过。因此可以将其看成一个待检查的列表。查看与A相邻的8个方格 ,把其中可走的 (walkable) 或可到达的(reachable) 方格加入到open list中。并把起点 A 设置为这些方格的父节点 (parent node) 。然后把 A 从open list中移除,加入到close list(封闭列表) 中,close list中的每个方格都是不需要再关注的。

  如下图所示,深绿色的方格为起点A,它的外框是亮蓝色,表示该方格被加入到了close list 。与它相邻的黑色方格是需要被检查的,他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点A。

                                                       

下一步,我们需要从open list中选一个与起点A相邻的方格。但是到底选择哪个方格好呢?选F值最小的那个。我们看看下图中的一些方格。在标有字母的方格中G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方,下方,左方的方格的 G 值都是 10 ,对角线的方格 G 值都是14 。H值通过估算起点到终点 ( 红色方格 ) 的 Manhattan 距离得到,仅作横向和纵向移动,并且忽略沿途的障碍。使用这种方式,起点右边的方格到终点有3 个方格的距离,因此 H = 30 。这个方格上方的方格到终点有 4 个方格的距离 ( 注意只计算横向和纵向距离 ) ,因此 H = 40 。

                                      

比较open list中节点的F值后,发现起点A右侧节点的F=40,值最小。选作当前处理节点,并将这个点从Open List删除,移到Close List中。

                                      

对这个节点周围的8个格子进行判断,若是不可通过(比如墙,水,或是其他非法地形)或已经在Close List中,则忽略。否则执行以下步骤:

    • 若当前处理节点的相邻格子已经在Open List中,则检查这条路径是否更优,即计算经由当前处理节点到达那个方格是否具有更小的 G值。如果没有,不做任何操作。相反,如果G值更小,则把那个方格的父节点设为当前处理节点 ( 我们选中的方格 ) ,然后重新计算那个方格的 F 值和 G 值。
    • 若当前处理节点的相邻格子不在Open List中,那么把它加入,并将它的父节点设置为该节点。

  按照上述规则我们继续搜索,选择起点右边的方格作为当前处理节点。它的外框用蓝线打亮,被放入了close list 中。然后我们检查与它相邻的方格。它右侧的3个方格是墙壁,我们忽略。它左边的方格是起点,在 close list 中,我们也忽略。其他4个相邻的方格均在 open list 中,我们需要检查经由当前节点到达那里的路径是否更好。我们看看上面的方格,它现在的G值为14 ,如果经由当前方格到达那里, G值将会为20( 其中10为从起点到达当前方格的G值,此外还要加上从当前方格纵向移动到上面方格的G值10) ,因此这不是最优的路径。看图就会明白直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。

  当把4个已经在 open list 中的相邻方格都检查后,没有发现经由当前节点的更好路径,因此不做任何改变。接下来要选择下一个待处理的节点。因此再次遍历open list ,现在open list中只有 7 个方格了,我们需要选择F值最小的那个。这次有两个方格的F值都是54,选哪个呢?没什么关系。从速度上考虑,选择最后加入 open list 的方格更快。因此选择起点右下方的方格,如下图所示。

                               

接下来把起点右下角F值为54的方格作为当前处理节点,检查其相邻的方格。我们发现它右边是墙(墙下面的一格也忽略掉,假定墙角不能直接穿越),忽略之。这样还剩下 5 个相邻的方格。当前方格下面的 2 个方格还没有加入 open list ,所以把它们加入,同时把当前方格设为他们的父亲。在剩下的 3 个方格中,有 2 个已经在 close list 中 ( 一个是起点,一个是当前方格上面的方格,外框被加亮的 ) ,我们忽略它们。最后一个方格,也就是当前方格左边的方格,检查经由当前方格到达那里是否具有更小的 G 值。没有,因此我们准备从 open list 中选择下一个待处理的方格。

  不断重复这个过程,直到把终点也加入到了 open list 中,此时如下图所示。注意在起点下方 2 格处的方格的父亲已经与前面不同了。之前它的G值是28并且指向它右上方的方格。现在它的 G 值为 20 ,并且指向它正上方的方格。这是由于在寻路过程中的某处使用新路径时G值更小,因此父节点被重新设置,G和F值被重新计算。

                                 

那么我们怎样得到实际路径呢?很简单,如下图所示,从终点开始,沿着箭头向父节点移动,直至回到起点,这就是你的路径。

                               

 

 

标签:open,路径,list,算法,方格,规划,节点,起点
From: https://www.cnblogs.com/Zhouce/p/18291083

相关文章

  • 大模型算法方向实习会经常提问哪些问题?看完手撕面试官拿下offer!
    现互联网研发一枚,曾拿过多个算法/研发岗SPoffer,简要介绍一下大模型算法岗面试内容和如何准备面试。大模型算法岗的面试内容,实际上可以拆解成两部分,一是算法岗通用的面试内容,二是大模型专有相关部分。算法岗通用面试内容这部分内容很重要,因为通用的面试内容可以适用于不同......
  • 分享一些算法开局技巧(C++)
    目录一、万能头文件二、一些宏定义操作三、提前定义好一些常用的值四、快读五、一键获取题目的案例数据六、一键生成代码模板总结:个人心得一、万能头文件一般算法需要用到各种头文件,但是万能头文件包括了绝大多数的头文件,能缩减一些代码量。但是也有一点副作用,由于......
  • 算法题里存储数据的方式(C++)
    这里分享的不是如邻接矩阵邻接表的算法存储,仅仅是一些特殊数据的简易存储,以方便操作1、map<int,vector<int>>mp当给出很多串数字,每一串数字都需要单数放一个一维数组里,但是开辟一个二维数组内存又过大,并且不好操作时,可以用map<int,vector<int>>mp来存储,这样就可以单独操......
  • 计及需求响应的改进灰狼优化算法求解风、光、柴、储容量优化配置(Matlab代码实现)
     ......
  • 【深度学习】探讨最新的深度学习算法、模型创新以及在图像识别、自然语言处理等领域的
    深度学习作为人工智能领域的重要分支,近年来在算法、模型以及应用领域都取得了显著的进展。以下将探讨最新的深度学习算法与模型创新,以及它们在图像识别、自然语言处理(NLP)等领域的应用进展。一、深度学习算法与模型创新新型神经网络结构Transformer及其变种:近年来,Transformer......
  • ScreenAI ——能理解从信息图表到用户界面的图像和文本算法解析
    概述论文地址:https://arxiv.org/pdf/2402.04615.pdf信息图表(图表、示意图、插图、地图、表格、文档布局等)能够将复杂的数据和想法转化为简单的视觉效果,因此一直以来都被视为传播的重要元素。这种能力来自于通过布局和视觉线索使信息直观易懂。在当今日益数字化的世界中,移......
  • 算法金 | 时间序列预测真的需要深度学习模型吗?是的,我需要。不,你不需要?
    大侠幸会,在下全网同名「算法金」0基础转AI上岸,多个算法赛Top「日更万日,让更多人享受智能乐趣」参考论文:https://arxiv.org/abs/2101.02118更多内容,见微*公号往期文章:审稿人:拜托,请把模型时间序列去趋势!!使用Python快速上手LSTM模型预测时间序列1.时间序列预测......
  • 基于opencv + GPU cuda的光流算法demo
    该demo来自learnopencv.com网站,是作为opencvcuda模块的启蒙示例。看来这是一个简单的例子,但是由于从未接触过opencvcuda图像处理,我个人仍感觉比较新颖和有趣,特别是运行效果很惊奇,这里和大家一起学习解读以下。想看一手内容可以在网络直接搜索GettingStartedWithOpencvcuda......
  • 代码随想录算法训练营第27天 | 122.买卖股票的最佳时机 II 55. 跳跃游戏 1005.K次取反
    122.买卖股票的最佳时机II给你一个整数数组prices,其中prices[i]表示某支股票第i天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买,然后在同一天出售。返回你能获得的最大利润。解题:思路:最终利润是可......
  • R语言实现 Copula 算法建模相依性案例分析报告
    原文链接:http://tecdat.cn/?p=6193原文出处:拓端数据部落公众号 copula是将多变量分布函数与其边缘分布函数耦合的函数,通常称为边缘。Copula是建模和模拟相关随机变量的绝佳工具。Copula的主要吸引力在于,通过使用它们,你可以分别对相关结构和边缘(即每个随机变量的分布)进行建模。......