• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

移动机器人路径规划算法及思考——A*算法

人工智能 绿竹巷人 1743次浏览 0个评论

A*算法原理

 

A算法是一种经典的路径搜索算法,A算法的原理初学者可以去网上搜索算法原理详解,讲得很好

链接:http://www.gamedev.net/reference/articles/article2003.asp

截图回忆

 

在这里插入图片描述

  算法牛人或者进阶者,可能只是忘了算法的一些关键点,这里进行回顾   A*算法简单来说就是一个寻找一条最小代价路径的算法 核心公式为: F = G + H F:总损失 G:从起点到当前位置的实际移动代价 H:从当前位置到终点的估算代价   FGH好吧,唱首歌ABCDE FGH IJK…  

A*算法理解

 

A*算法的代价

 

换句话说,A*算法为每个路径点贴上了一个标签,标签上写了一个数字,那就是F。F是如何构成的呢,那就是从起点走到当前位置,你付出的代价是多少,你从当前位置到终点,估计你还要付出多少代价 总代价 = 实际移动代价 + 未来移动估算代价

  那么在算法设计过程中,代价的设计就至关重要了。而设计自然也分实际移动代价和估算代价两个部分。   举个例子,一个简单的计算方式就是:   机器人直线运动前进或者倒退的实际代价设为1,向左走或者向右走的实际代价设为2。未来移动估算代价可以设为地图上两点间的曼哈顿距离(d(i,j)=|X1-X2|+|Y1-Y2|)  

A*算法的算法逻辑

  代价的设计方式有很多,假设我们已经定义了一种方式,那么让A*算法生效的逻辑是什么呢?解释如下 算法维护两个list,正确而简单的理解就是 open list:该list中的点还要被搜索 closed list:该list中的点不需要被搜索了   算法步骤如下 1.open list中最开始只有一个点——路径的起点 2.把路径起点周围的点放入open list中,计算他们的F值,并将他们的父节点设为起点,将起点放入closed list中 3.选取open list中F值最小的点,把它自己放入closed list中  

4.重要的一步:

  (1) 第3步中选取的F值最小的点,我们称他为“小明”,称小明的周围点为“小明的同桌们”,同桌们有的已经在open list中了,有的还没有在open list中; (2) 没有在open list中的点,自然没计算过F值,那么现在计算他们的F值,并把小明设为这些同桌的父节点 (3) 已经在open list中的点,以小明作为父亲,重新计算一下已经在open list 的同桌们的G值(注意,是G值); (4) 如果新计算的G值小于他们固有的G值,那么“小明是这位同桌的爸爸”。哈哈,意思就是说:从小明移动到这位同桌的路径,比之前计算得到的、能够移动到这位同桌的路径要好。把小明设置为这些同桌的父节点。 (5) 如果新计算的G值大于他们固有的G值,那么“小明不是这些同桌的爸爸”。小明移动到这些同桌,不如之前计算的路径代价小,那么这些同桌们的爸爸不变。什么操作都不要有…小明,别想当人家爹了,人家的爹还是不变的 (6) 进行过“父亲辨认”后,把同桌们都放入open list中; 循环,请执行第3步,直到第3步在 open list 中选取的F值最小的点其实就是终点。 从终点开始,倒推每个节点的父节点,直到倒推回起点,这就是你要的路径  

A*算法终极理解

  简单几句话:   A*,就是在已知位置中不断地搜索代价最小的点,并且更新一下所有已知位置的最优到达路径,通过在搜索过程中明确点与点之间的父与子关系,最终确定最优路径。  

A*在移动机器人路径规划的应用思考

  A*算法用在移动机器人路径规划是没有问题的,在程序层面需要设计的部分包括 open list的维护:很显然,一个最简单的方法是维护一个有排好序的open list,取值时只取F值最小的位置就行了。小地图这样可以,大地图列表有可能过大影响效率,二叉堆是一个优化效率的好方法(TODO) 多机器人的规划:多机器人怎么处理互相的碰撞,都在运动怎么计算出避免碰撞的路径(设定都首先向一个方向躲避还是?)   寻路速度:   1.使用小地图(呵呵,我就想在大地图里翱翔就没办法了) 2.不要多个机器人一起去规划(没办法的办法)     3.地图分辨率(重要:地图分辨率决定了你的路径规划速度,比如你有100平方米,地图分辨率2cm和2mm规划起来效率肯定不一样啊)     4.路径点系统(重要:大区域规划出来的路径,应该是一系列主要的路径点构成的,不可能移动时你要记住路径的每一个点)     5.设定一些不能到达的区域(重要:因为这是很实际的,移动机器人的工作区域往往只是地图的一小部分,剩余部分是它绝对不能进入的) 6.不同的地形损耗(比如地势高的地方代价就要大,不好走的地方代价就要大。其实这很有必要,只不过目前移动机器人不太需要这一条,实际很少人去用。原因?因为依靠SLAM的移动机器人现在没那么厉害,能够平地不出错就万事大吉了) 7.维护未探测的区域(需要这个时可能偏游戏了,因为移动机器人在路径规划时,已经靠SLAM拥有了一张工作区域完整的地图)     8.平滑路径(重要:A*算法得到的路径并不平滑,移动机器人需要另外的算法去平滑这些路径点。这样机器人走起来不会摆来摆去) 9.非方形搜索区域(也就是不用正方形的格子计算F值了。暂时不知道这个在移动机器人里的应用。因为一般,移动机器人是将地图按照像素划分的)  

待完善的知识点

  根据这篇文章,我们也简单思考了他在移动机器人上的具体应用逻辑。移动机器人能够完全自主的在工作区域行动,哪怕是已知了由SLAM构建完成的地图,只有A*算法仍然是不够的。 这篇文章只是讲了A*算法原理。值得进一步去探索的知识点包括: 提高A*计算效率:快速有效的排序算法 优化小车的行为:平滑路径的算法 解决多机器人会车:多机器人规划算法   我会一一编写文章的,今天就这样,谢谢!


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明移动机器人路径规划算法及思考——A*算法
喜欢 (0)

您必须 登录 才能发表评论!

加载中……