Give me miles, give me truth

Give me miles, give me truth

Open eyes, open roof

风雨过后睁开双眼 打开车顶天窗

Give me miles, give me truth

日出之时再行万里 用我双眼靠近真相

​ —— 《Lone Ranger》Rachel Platten

Base on Sampling

基于采样的寻路算法,主要代表是RRT(快速搜索随机树),根据搜索空间分为2D RRT和3D RRT,常用于工业手臂路径规划,近几年在UAV领域比较火热,一般用于杂乱的环境中快速寻路及避开移动障碍物等场景。较少直接用于AMR调度系统,这里不再赘述。

Base on Search

基于搜索的寻路算法,从最基础的BFS和DFS,再到引入h(x)的best_first、D*、A*(与best_first的区别之一在于对h(x)和g(x)关系的处理),再到A*算法的变种,常见的比如:

  • Bidirectional A*
  • Anytime Repairing A*
  • Lifelong Planning A*
  • Learning Real-time A*
  • Jump Point Search A*
  • Dynamic A*
  • D* Lite

A*

最常用的启发寻路算法,会根据实际场景对启发函数进行修改以满足需要,比如考虑到AMR的旋转代价,会在h(x)中添加转角代价,用来选取场景中转角最小的路径。

TODO: 转角代价的实现

Bidirectional A*

双向A*,在A*的基础上,从起始点同时开始对向搜索,往往使用同一套h(x),直到得到相遇点s_meet,结束搜索,典型的以空间换时间的改进思路,但不太适用于AMR寻路环境,理由是:

  • AMR实际寻路环境范围尺度不会特别大,优化搜索时间效果不明显
  • 实际的拓扑图的连通关系由人为决定,会存在单双向路径,双向搜索失能

Lifelong Planning A*

与基础的A*算法相比,最小heap的key由原先的一维代价变成二维的:

2018122121002358.png

没有了原来的h(x),新增了:

  • rhs(x):一个基于节点前任的g值的前瞻值(所有g(n’)+d(n’, n)的最小值,其中n’是n的前任,d(x, y)是连接x和y的边的代价)
  • U(x):一个基于节点优先k1排序,其次k2排序的堆

在搜索过程中不断计算rhs(x)与g(x)的大小关系,判定是否从队列中移除该点,在过拟合的情况下,重新计算局部过一致的点来达到绕障的目的

在实际使用中,AMR往往会按照最早计算的路径开始运动,而未到达的点的是否占用的情况对当位置的影响有限,通常做法是根据AMR运行速度动态检测前向n个点的通畅情况,如果遇到拥堵,可以根据点的空闲情况再次寻路到目标点,也不会遍历过多节点,单纯的使用LPA*并不会带来明显的提升

未完待续

赞赏
Nemo版权所有丨如未注明,均为原创丨本网站采用BY-NC-SA协议进行授权,转载请注明转自:https://nemo.cool/928.html

Nemo

文章作者

推荐文章

发表回复

textsms
account_circle
email

Give me miles, give me truth
Open eyes, open roof 风雨过后睁开双眼 打开车顶天窗 Give me miles, give me truth 日出之时再行万里 用我双眼靠近真相 ​ —— 《Lone Ranger》Rachel Platten Base on Sampl…
扫描二维码继续阅读
2022-11-22