当前位置：首页 > article >正文

【智能算法应用】正切搜索算法求解二维路径规划问题

article 2024/10/10 3:11:06

摘要

本文提出了基于正切搜索算法的二维路径规划方法，用于解决包含障碍物的复杂路径规划问题。通过在二维平面中建立障碍物模型和路径目标点，利用正切搜索算法进行路径搜索，找出从起点到终点的最优路径。实验结果显示，该算法在不同障碍物布局下均能成功找到一条最优路径，并具有较好的收敛性和稳定性。

理论

路径规划是机器人、无人机等自主系统中的关键问题，涉及如何从起点经过障碍物到达终点。常见的路径规划算法包括A*算法、Dijkstra算法、遗传算法等。然而，在复杂环境中，这些算法可能面临计算复杂度高或难以收敛等问题。正切搜索算法是一种基于局部搜索的路径优化方法，通过沿着目标方向和障碍物的正切方向进行搜索，寻找可行路径，并避免陷入局部最优。

正切搜索算法：正切搜索是一种基于几何的搜索方法，利用障碍物的边界信息和目标方向的关系，动态调整搜索方向。当遇到障碍物时，算法沿障碍物边界的正切方向进行移动，直到找到可行路径。结合全局搜索和局部避障的策略，算法可以有效避开障碍物并优化路径长度。

路径规划问题建模：在二维平面上，起点为 (𝑥0,0)，终点为 (𝑥𝑡,𝑦𝑡)存在若干圆形障碍物，障碍物的中心和半径已知。目标是找到一条从起点到终点的路径，路径上不经过障碍物且路径长度最优。

实验结果

图1显示了正切搜索算法在二维路径规划问题中的运行结果。起点（黄色方块）和终点（绿色星形标记）之间的黑色曲线为算法生成的最优路径，红色的圆形为避开的障碍物。可以看到，算法成功地避开了多个障碍物，并最终到达目标点。

图2则展示了算法的收敛过程。横坐标为迭代次数，纵坐标为适应度值（路径长度）。从图中可以看出，随着迭代次数的增加，适应度逐渐下降，并最终趋于稳定，表明算法能够有效收敛并找到最优路径。

部分代码

% 初始化参数
startPos = [0, 0];  % 起点
endPos = [6, 6];  % 终点
obstacles = [2, 4, 1.5; 4, 3, 1.2; 5, 5, 1; 3, 1, 1; 5, 2, 1];  % 障碍物: [x, y, 半径]

% 正切搜索算法主函数
function path = tangentialSearch(startPos, endPos, obstacles)
    path = startPos;  % 初始化路径
    currentPos = startPos;
    while norm(currentPos - endPos) > 0.1  % 终止条件
        direction = (endPos - currentPos) / norm(endPos - currentPos);  % 朝向目标的方向
        collision = false;
        for i = 1:size(obstacles, 1)
            obsCenter = obstacles(i, 1:2);
            obsRadius = obstacles(i, 3);
            if norm(currentPos - obsCenter) < obsRadius + 0.2  % 检测是否碰撞
                tangentDir = [(currentPos(2) - obsCenter(2)), -(currentPos(1) - obsCenter(1))];
                direction = tangentDir / norm(tangentDir);  % 沿障碍物边界的正切方向
                collision = true;
                break;
            end
        end
        if ~collision
            direction = direction * 0.1;  % 没有碰撞时正常前进
        end
        currentPos = currentPos + direction;  % 更新当前位置
        path = [path; currentPos];  % 更新路径
    end
end

% 运行正切搜索算法
path = tangentialSearch(startPos, endPos, obstacles);

% 绘制路径和障碍物
figure;
hold on;
for i = 1:size(obstacles, 1)
    viscircles(obstacles(i, 1:2), obstacles(i, 3), 'EdgeColor', 'b');  % 绘制障碍物
end
plot(path(:, 1), path(:, 2), 'k-', 'LineWidth', 2);  % 绘制路径
plot(startPos(1), startPos(2), 'ys', 'MarkerSize', 10, 'MarkerFaceColor', 'y');  % 起点
plot(endPos(1), endPos(2), 'g*', 'MarkerSize', 10, 'MarkerFaceColor', 'g');  % 终点
hold off;
grid on;
axis equal;
title('正切搜索路径规划');

% 收敛曲线
figure;
iterations = 1:1000;  % 假设1000次迭代
fitness = 40 - 0.03 * iterations;  % 假设的适应度值随迭代次数下降
plot(iterations, fitness, 'b-');
xlabel('迭代次数');
ylabel('适应度');
title('正切搜索算法收敛曲线');
grid on;

参考文献

❝

Rimon, E., & Koditschek, D. E. (1992). Exact robot navigation using artificial potential functions. IEEE Transactions on Robotics and Automation, 8(5), 501-518.

Latombe, J. C. (1991). Robot Motion Planning. Springer Science & Business Media.

Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5(1), 90-98.

（文章内容仅供参考，具体效果以图片为准）