Matlab遗传算法2D路径规划忽略障碍物问题求助

问题描述 #

使用Matlab Global Optimization Toolbox的遗传算法（GA）实现2D空间起点到终点的最短路径规划，要求避开静态多边形障碍物，但算法始终忽略障碍物直接走直线，调整种群规模、最大迭代次数后问题仍存在。

问题根源分析 #

1. 碰撞检测不完整：当前仅检查路径的顶点（起点、中间点、终点）是否在障碍物多边形内，但路径的线段可能穿过障碍物内部，只要顶点不在障碍内就不会触发惩罚，导致直线穿障的路径被判定为合法。
2. 惩罚机制失效：10000的惩罚权重可能不足以抵消直线路径的长度优势，GA会优先选择带惩罚的短路径，而非绕路的长路径。
3. 无硬约束限制：约束函数为空，仅靠目标函数的软惩罚约束避障，GA的搜索优先级仍偏向最短路径。

解决方案与修改代码 #

核心修改点 #

• 新增线段与障碍物的相交检测，覆盖顶点和线段两种碰撞场景
• 强化惩罚力度，确保穿障路径的代价远高于绕路路径
• 可选：将避障设为硬约束（通过约束函数返回冲突值）

修改后的完整代码 #

start_point = [65, 275];
end_point = [510, 210];
num_points = 4; % 起点终点间的中间点数
% 2D空间边界
x_min = 0; 
x_max = 600;
y_min = 0;
y_max = 600;

% 障碍物多边形顶点
obstacle_x = [30, 100, 170, 220, 195, 130, 130, 100];
obstacle_y = [215, 170, 210, 260, 330, 340, 280, 230];
obstacle_poly = [obstacle_x', obstacle_y']; % 转为矩阵格式方便计算

% 变量上下界
lb = repmat([x_min, y_min], num_points, 1);
ub = repmat([x_max, y_max], num_points, 1);

% GA参数设置
options = optimoptions('ga', ...
    'PopulationSize', 150, ... 
    'MaxGenerations', 200, ... 
    'Display', 'iter', % 显示迭代过程方便观察
    'UseParallel', true, ...
    'CrossoverFraction', 0.8, ...
    'MutationRate', 0.1);

% 目标函数句柄
objective_function = @(points) objective(points, start_point, end_point, obstacle_poly);

% 运行GA，这里可以选择用硬约束还是软惩罚，示例用强化软惩罚
[best_points, fval] = ga(objective_function, num_points * 2, [], [], [], [], lb, ub, [], options);

% 可视化结果
full_path = [start_point; reshape(best_points, num_points, 2); end_point];

figure;
plot(full_path(:, 1), full_path(:, 2), '-o', 'LineWidth', 2);
xlabel('X');
ylabel('Y');
title('避障最短路径规划结果');
grid on;
hold on;
scatter(start_point(1), start_point(2), 100, 'g', 'filled');
scatter(end_point(1), end_point(2), 100, 'r', 'filled');

fill(obstacle_x, obstacle_y, [0.7, 0.7, 0.7], 'EdgeColor', 'k');

legend('规划路径', '起点', '终点', '障碍物', 'Location', 'Best');
hold off;

% 目标函数：计算路径长度 + 碰撞惩罚
function d = objective(points, start_point, end_point, obstacle_poly)
    full_points = [start_point; reshape(points, [], 2); end_point];
    % 计算路径总长度
    path_length = sum(sqrt(sum(diff(full_points).^2, 2)));
    d = path_length;
    
    collision_count = 0;
    % 检查每个路径线段是否与障碍物相交
    for i = 1:size(full_points,1)-1
        seg_start = full_points(i,:);
        seg_end = full_points(i+1,:);
        % 用polyxpoly检测线段与多边形的交点
        [x_intersect, y_intersect] = polyxpoly(seg_start(1), seg_start(2), seg_end(1), seg_end(2), ...
            obstacle_poly(:,1), obstacle_poly(:,2));
        % 如果有交点（排除线段端点刚好在多边形顶点的情况）
        if ~isempty(x_intersect)
            % 过滤端点重合的情况
            is_endpoint = (x_intersect == seg_start(1) & y_intersect == seg_start(2)) | ...
                         (x_intersect == seg_end(1) & y_intersect == seg_end(2));
            if any(~is_endpoint)
                collision_count = collision_count + 1;
            end
        end
    end
    
    % 检查顶点是否在障碍物内部
    [in_poly, ~] = inpolygon(full_points(:, 1), full_points(:, 2), obstacle_poly(:,1), obstacle_poly(:,2));
    collision_count = collision_count + sum(in_poly);
    
    % 强化惩罚：每次碰撞加100000的代价，确保穿障路径远劣于绕路
    if collision_count > 0
        d = d + 100000 * collision_count;
    end
end

% 可选硬约束函数：如果需要禁止任何碰撞，可启用此函数替换GA调用中的空约束
% function [c, ceq] = constraints(points, start_point, end_point, obstacle_poly)
%     full_points = [start_point; reshape(points, [], 2); end_point];
%     c = [];
%     % 检查线段相交
%     for i = 1:size(full_points,1)-1
%         seg_start = full_points(i,:);
%         seg_end = full_points(i+1,:);
%         [x_intersect, y_intersect] = polyxpoly(seg_start(1), seg_start(2), seg_end(1), seg_end(2), ...
%             obstacle_poly(:,1), obstacle_poly(:,2));
%         if ~isempty(x_intersect)
%             is_endpoint = (x_intersect == seg_start(1) & y_intersect == seg_start(2)) | ...
%                          (x_intersect == seg_end(1) & y_intersect == seg_end(2));
%             if any(~is_endpoint)
%                 c = [c; 1]; % 返回非零值表示违反约束
%             end
%         end
%     end
%     % 检查顶点在障碍内
%     [in_poly, ~] = inpolygon(full_points(:, 1), full_points(:, 2), obstacle_poly(:,1), obstacle_poly(:,2));
%     c = [c; in_poly];
%     ceq = [];
% end

额外优化建议 #

• 若使用硬约束，GA会直接排除穿障路径，搜索效率更高，但需确保初始种群中存在合法路径，否则GA可能无法找到可行解。
• 调整中间点数量num_points：如果障碍物较大，可适当增加中间点数量，给GA更多绕路的自由度。
• 启用Display为iter，观察迭代过程中适应度的变化，判断惩罚是否有效。

内容的提问来源于stack exchange，提问作者Tsidia