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实际寻路环境范围尺度不会特别大，优化搜索时间效果不明显
• 实际的拓扑图的连通关系由人为决定，会存在单双向路径，双向搜索失能
• 由于启发函数的局限性，即使双向搜索也无法解决slam场景中站点设置出现“凹形”时AMR描边的问题

Lifelong Planning A*

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

没有了原来的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*并不会带来明显的提升

未完待续

Give me miles, give me truth

Base on Sampling

Sampling-based pathfinding algorithm, the main representative is RRT (fast search random tree), according to the search space is divided into 2D RRT and 3D RRT, commonly used in industrial arm path planning, in recent years in the UAV field is hot, generally used in a cluttered environment, fast pathfinding and avoiding moving obstacles and other scenarios. It is less often used directly in AMR scheduling systems, so it is not repeated here.

Base on Search

Search-based pathfinding algorithms, from the most basic BFS and DFS, to the introduction of h(x) best_first, D*, A* (one of the differences with best_first is the treatment of the relationship between h(x) and g(x)), to A* algorithm variants, common ones such as.

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

A*

The most commonly used heuristic search algorithm, the heuristic function will be modified to meet the needs of the actual scene, for example, considering the rotation cost of AMR, the corner cost will be added to h(x) to select the path with the smallest corner in the scene.

TODO: Implementation of corner cost

Bidirectional A*

Bidirectional A*, on the basis of A*, starts the opposite direction search from the starting point at the same time, often using the same set of h(x), until the encounter point s_meet is obtained and the search is ended, a typical space-for-time improvement idea, but not very applicable to the AMR pathfinding environment for the following reasons.

• AMR actual pathfinding environment range scale will not be particularly large, optimize the search time effect is not obvious
• The actual topological map of the connectivity relationship by human decision, there will be a single two-way path, two-way search dysfunction
• Due to the limitation of the heuristic function, even the bidirectional search cannot solve the problem of AMR tracing when the site setting in the slam scenario has a "concave shape".

Lifelong Planning A*

Compared with the basic A* algorithm, the key of the minimum heap is changed from a one-dimensional cost to a two-dimensional one: !

Without the original h(x), a new.

• rhs(x): a look-ahead value based on the g-values of the node predecessors (the minimum of all g(n’) + d(n’, n), where n’ is the predecessor of n and d(x, y) is the cost of the edge connecting x and y)
• U(x): a heap based on node-first k1 sorting, followed by k2 sorting

In the search process constantly calculate the relationship between the size of rhs(x) and g(x), determine whether to remove the point from the queue, and in the case of overfitting, recalculate the local over-consistent points to achieve the purpose of bypassing the barrier

In practice, AMR tends to start the movement according to the earliest calculated path, and whether the unarrived points are occupied or not has limited impact on the current position. The usual practice is to dynamically detect the smoothness of n points in the forward direction according to the AMR running speed, and if congestion is encountered, the path can be sought again to the target point according to the idle situation of the point, and it will not traverse too many nodes, and the simple use of LPA* does not bring no significant improvement

To be continued