企业官网建设流程全解析

仅供参考。 建议看时有一定A*基础 主要示例 根据坐标推一次

A*

核心公式

f(n) = g(n) + h(n)

g(n)：从起点走到当前点 n，已经花费的真实代价
h(n)：从当前点 n 到终点的预估代价
f(n)：总代价评分，越小越优先探索

g：已经走了多远
h：估计还要走多远
f：这条路线看起来总共要多远

如果h = 0，A* 就退化成 Dijkstra。

曼哈顿距离

h = |当前x - 目标x| + |当前y - 目标y|

h = |3 - 3| + |2 - 7| = 5

open、closed、parent

open

open是待探索的候选点集合。

可以理解为：

所有已经发现、但还没正式展开的边界点。

A* 每一轮都会从open里选f最小的点作为当前点。

closed

closed是已经探索过的点集合。

一个点进入closed后，表示它已经被展开过，通常不再重复处理。

parent

parent用来记录路径。

算法流程

1. 把起点 S 加入 open
2. 从 open 中选出 f 最小的点，作为 current
3. 如果 current 是终点 G，结束搜索
4. 把 current 从 open 移到 closed
5. 检查 current 的上下左右邻居
6. 如果邻居是障碍物，跳过
7. 如果邻居已经在 closed 中，通常跳过
8. 计算邻居的新 g、h、f
9. 如果邻居不在 open 中，加入 open，并记录 parent
10. 如果邻居已经在 open 中，但这次路线更短，更新 g、f、parent
11. 重复第 2 步
12. 找到终点后，根据 parent 反向追踪路径

open = {S} closed = {} g[S] = 0 parent[S] = none while open 不为空: current = open 中 f 最小的点 if current == G: return 根据 parent 反向追踪出的路径 从 open 移除 current 把 current 加入 closed for neighbor in current 的邻居: if neighbor 是障碍物: continue if neighbor 在 closed 中: continue new_g = g[current] + 移动代价 if neighbor 不在 open 中: parent[neighbor] = current g[neighbor] = new_g h[neighbor] = 曼哈顿距离(neighbor, G) f[neighbor] = g[neighbor] + h[neighbor] 把 neighbor 加入 open else if new_g < g[neighbor]: parent[neighbor] = current g[neighbor] = new_g f[neighbor] = g[neighbor] + h[neighbor]

推导示例

地图：

y=0 . . . S . . . .
y=1 . . . . . . . .
y=2 . . # . . # . .
y=3 . . # . . # . .
y=4 . . # . . # . .
y=5 . . # # # # . .
y=6 . . . . . . . .
y=7 . . . G . . . .

其中S是起点 G是终点 #是障碍物

每一轮都从 open 里选 f (代价)最小的点

(3,0) -> (3,1) -> (3,2) -> (3,3) -> (3,4) 不会回头 从open里找最小的点

Jump Point Search

对一次jump来说，确实可以理解为：给定起始点 + 跳跃方向，然后沿这个方向一直检测，直到遇到终点、障碍/边界、强制邻居。

从 open 里取 f 最小的点
根据来时方向剪枝邻居方向
对保留下来的方向分别 jump
jump 找到跳点后加入 open

跳点

跳点可以理解为：

必须停下来做决策的关键格子。

常见跳点来源：

1. 当前点是终点 2. 当前点有强制邻居 3. 斜向跳跃时，横向或纵向子方向能找到跳点或终点(空旷环境下没有障碍物 咳咳)

如果沿某个方向遇到障碍或边界，通常表示这个方向失败，返回null

jump(当前点, 方向): 沿方向走一步 如果越界或遇到障碍: 这里注意啦 方向上有障碍物的不算喔 return null 如果当前点是终点: return 当前点 如果当前点有强制邻居: return 当前点 如果当前方向是斜向: 如果横向 jump 能找到跳点: return 当前点 如果纵向 jump 能找到跳点: return 当前点 继续沿同方向 jump

Hybrid A

Hybrid A= A搜索框架 + 车辆运动学模型 + 姿态离散化 + 碰撞检测 + 启发函数加速。**

普通 A* 的状态通常是二维位置

它假设机器人可以从一个格子直接走到相邻格子，比如上、下、左、右、斜向。

但汽车不行。汽车有几个限制：

不能横向平移
不能原地旋转
有最小转弯半径
车头朝向会影响下一步能去哪

所以对于汽车来说，只知道(x, y)不够，还必须知道朝向

Hybrid A* 的“混合”主要体现在：

连续运动 + 离散搜索

普通 A* 扩展邻居：

上、下、左、右、左上、右上...

Hybrid A* 扩展的是车辆可执行动作，例如：

前进左转
前进直行
前进右转
后退左转
后退直行
后退右转

Hybrid A* 的核心是：

f = g + h

Hybrid A* 的g往往不只是路径长度。

它通常会惩罚一些“不舒服”或者“不合理”的驾驶行为：

倒车惩罚
频繁换挡惩罚
大转角惩罚
方向盘快速变化惩罚
靠近障碍物惩罚

障碍物检测：

普通 A* 通常检查某个格子是不是障碍物。

Hybrid A* 不能只检查车辆中心点，因为车有长宽。

它要检查整个车辆矩形在当前姿态下是否和障碍物重叠。

也就是说，每个状态 (x, y, theta)

都对应一个旋转后的车辆轮廓。

路径上一小段运动也要检查中间过程是否碰撞。

所以 Hybrid A* 的碰撞检测通常比搜索本身还耗时。

流程

1. 从起点姿态开始
2. 根据车辆模型生成若干可行动作
3. 对每个动作形成一个新姿态
4. 检查新姿态和中间轨迹是否碰撞
5. 计算 g、h、f
6. 选择 f 最小的节点继续扩展
7. 接近目标时尝试 Reeds-Shepp 直接连接
8. 找到路径后回溯节点，得到轨迹
9. 再进行平滑优化

所以 Hybrid A* 特别适合：

自动泊车
无人车低速规划
仓储 AMR 带拖挂或类车体约束
狭窄空间掉头
非完整约束机器人路径规划

但它不适合追求全局大范围高速规划。