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

环境感知与规划专题(九)——基于采样的路径规划算法(一)

人工智能 遥远的乌托邦 2216次浏览 0个评论

前言

  在环境感知与规划专题(一)——A*算法入门一文中阐述了广泛应用于机器人路径搜索问题的求解算法——A*,它是一种基于图搜索的路径规划算法。而主流的路径规划算法分为基于图搜索的路径规划算法基于采样的路径规划算法。   本文将阐述一种基于采样的路径规划算法——快速搜索随机树RRT)。

 

快速搜索随机树(RRT

  快速搜索随机树RRT)算法从起始点开始,在地图上进行随机采样(如Monte Carlo Sample),或者说随机撒点,进而,根据采样点信息,结合障碍物检测等约束条件,构建一颗搜索树,直到树的枝叶延伸至目标点或达到预设的采样次数为止。   RRT的算法流程如下图所示,  

环境感知与规划专题(九)——基于采样的路径规划算法(一)

  算法主要包含如下部分:  

  • 随机采样得到采样点[公式]
  • 寻找搜索树种距离采样点最近的点[公式]
  • [公式][公式]的连线上向前延伸一段距离[公式],从而得到[公式]

 

环境感知与规划专题(九)——基于采样的路径规划算法(一)

 

  • 对于[公式][公式]之间的路径[公式],我们需要对其进行碰撞检测,若该路径是[公式]的,那么我们将[公式][公式]加入搜索树;反之,则放弃该节点

 

环境感知与规划专题(九)——基于采样的路径规划算法(一)

 

  • 以此迭代,最终找到目标点为止

 

环境感知与规划专题(九)——基于采样的路径规划算法(一)

 

环境感知与规划专题(九)——基于采样的路径规划算法(一)

总结

  本篇阐述了基于采样的路径搜索算法——快速搜索随机树(RRT),在地图维度较高或尺寸较大时,基于采样的路径规划算法较基于图搜索的路径规划算法(如A*等)有更高的搜索效率。然而,该算法得到的路径并非全局最优的,甚至每一次计算的得到的结果都有所不同。   下一篇中,我们将阐述快速搜索随机树算法在工程中存在的问题及其改进算法。  


作者简介: 一个被Coding耽误的无人机算法工程师,控制、导航略懂一二,热衷技术,喜欢乒乓、音乐、电影,欢迎交流。 知乎: @遥远的乌托邦 GitHub: github.com/DistantUtopi 微信公众号: @遥远的乌托邦

发布于 2020-05-26


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明环境感知与规划专题(九)——基于采样的路径规划算法(一)
喜欢 (0)

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

加载中……