一、基本思路
先简单回顾一下 A算法的基本原理。A算法是一种启发式搜索算法,主要通过评价函数 ( f(n) = g(n) + h(n) ) 来衡量从起点到目标点的路径代价。其中,( g(n) ) 是从起点到当前节点的实际代价,( h(n) ) 是从当前节点到目标节点的启发式估计代价。
这次改进的核心思想是:
- 增加搜索方向:从传统的 8 个方向减少到 5 个方向,优化搜索策略。
- 避免斜穿障碍物顶点:确保路径不会穿过障碍物的顶点,避免碰撞。
- 删除中间多余节点:减少路径中的转折点,使路径更加平滑。
- 改进评价函数:将 ( f(n) = g(n) + h(n) ) 修改为 ( f(n) = g(n) + (1 + r/R) \cdot h(n) ),引入比例因子 ( r/R ) 以平衡路径代价和启发式估计。
接下来,我会逐个分析这些改进点,并展示如何在 Matlab 中实现。
二、具体改进及实现
1. 增加搜索方向
传统的 A*算法允许 8 个移动方向(上、下、左、右、4 个对角线)。但在实际应用中,这种 8 方向的移动可能会导致路径过于曲折。因此,将搜索方向减少到 5 个,具体包括:
- 4 个正方向(上下左右)
- 1 个对角线(根据实际需要选择)
在 Matlab 代码中,可以通过定义移动方式的数组来实现:
% 定义 5 个移动方向(上、下、左、右、左上对角)
move_directions = [ ...
[-1, 0], % 上
[1, 0], % 下
[0, -1], % 左
[0, 1], % 右
[-1,-1] % 左上对角(可调整)
];
2. 避免斜穿障碍物顶点
为了避免路径斜穿障碍物的顶点,需要在碰撞检测中增加额外的判断。具体来说,当生成一个新的节点时,不仅需要判断当前节点是否在障碍物内部,还需要检查其周围的顶点是否也在障碍物内部。
例如,可以通过以下代码判断某个点是否在障碍物内部:
function isInside = isPointInsideObstacle(x, y, obstacleMap)
[rows, cols] = size(obstacleMap);
if x < 1 || x > rows || y < 1 || y > cols
isInside = false;
else
isInside = obstacleMap(x, y) == 1; % 假设障碍物标记为 1
end
end
在搜索过程中,每次生成新节点时,都会调用上述函数进行判断,避免进入障碍物区域。
3. 删除中间多余节点
为了减少路径中的转折点,可以在路径生成后对节点进行优化。具体方法是删除那些位于直线上的多余节点,只保留关键点。
例如,可以通过以下代码实现路径平滑:
function smoothPath = smoothPath(path)
smoothPath = path;
i = 2;
while i < length(smoothPath)-1
% 判断当前点是否在前两个点的连线上
x1 = smoothPath(i-1,1); y1 = smoothPath(i-1,2);
x2 = smoothPath(i,1); y2 = smoothPath(i,2);
x3 = smoothPath(i+1,1); y3 = smoothPath(i+1,2);
if (y2 - y1) * (x3 - x2) == (y3 - y2) * (x2 - x1)
% 判断共线
smoothPath(i,:) = [];
i = max(i-1, 2); % 调整索引
else
i = i+1;
end
end
end
4. 改进评价函数
传统的 A*算法评价函数为 ( f(n) = g(n) + h(n) )。为了平衡路径代价和启发式估计,将其改进为:
[ f(n) = g(n) + (1 + r/R) \cdot h(n) ]
其中,( r ) 是当前节点到目标节点的剩余距离,( R ) 是整个地图的范围。这个改进可以使得算法在全局搜索和局部优化之间找到更好的平衡。
具体实现如下:
function f = evaluateFunction(g, h, r, R)
factor = (1 + r/R);
f = g + factor * h;
end


