1. Capuchin Search Algorithm 개요

Capuchin Search Algorithm(CSA)은 자연계의 카푸친 원숭이(Capuchin)의 먹이 탐색 행동을 모방한 메타휴리스틱 최적화 기법이다. 원숭이 무리가 숲에서 최적의 먹이원을 찾아다니는 과정을 수학적으로 모델링하여, 복잡한 최적화 문제의 해를 탐색한다.

알고리즘의 핵심 동작 원리는 다음과 같다:

• 초기 무리 구성: 임의의 위치에 원숭이 개체(해 후보)를 배치
• 적합도 평가: 각 개체의 위치에 따른 목적함수 값 계산
• 리더 선정: 우수한 적합도를 가진 개체를 리더 원숭이로 선별
• 탐색 행동: 리더 원숭이 주변에 무작위 변동(Levy flight) 적용하여 새로운 위치 생성
• 해 갱신: 새 위치가 기존 해보다 우수하면 대체
• 종료 판정: 최대 반복 수 도달 또는 수렴 조건 만족 시 종료

CSA는 구현이 간단하고, 문제의 특성에 덜 민감하며, 다중 모드 함수와 불연속 함수에서도 효과적인 탐색 능력을 보인다. 다만, 매개변수 설정과 지역 최적해 탈출이 과제로 남아있다.

2. 그리드 맵 환경 표현

2.1 그리드 기반 환경 모델링

경로 계획의 전제는 환경 정보의 효과적 획득과 표현이다. 정적 환경에서는 그리드 분할 방식이 널리 활용된다. 작업 공간을 동일한 크기의 정사각형 셀로 분할하여 이산화하며, 각 셀의 통과 가능 여부를 이진값으로 표현한다.

셀 크기 선정은 정보 정확도와 계산 효율성의 트레이드오프를 고려해야 한다. 작은 셀은 세밀한 환경 표현을 제공하나 저장 공간과 계산 부하가 증가한다. 반대로 큰 셀은 계산이 빠르나 장애물 근처의 세부 경로 표현이 흐려진다.

표기 칙:

• 장애물 영역: 검은색, 행렬 값 1
• 자유 통행 영역: 흰색, 행렬 값 0

2.2 10×10 환경 맵 생성

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 환경 맵 시각화 %%%%%%%%%%%%%%%%%%%%%%%%%%%%
function visualizeGrid(env)
    [rows, cols] = size(env);
    step = 1;
    x_grid = 0:step:cols;
    y_grid = 0:step:rows;
    
    figure(1);
    axis([0 cols 0 rows]);
    set(gca, 'xtick', x_grid, 'ytick', y_grid, ...
             'GridLineStyle', '-', 'xGrid', 'on', 'yGrid', 'on');
    hold on;
    
    idx = 1;
    for r = 1:rows
        for c = 1:cols
            if env(r,c) == 1
                obs(idx,1) = c - 1;
                obs(idx,2) = r - 1;
                fill([obs(idx,1), obs(idx,1)+step, obs(idx,1)+step, obs(idx,1)], ...
                     [obs(idx,2), obs(idx,2), obs(idx,2)+step, obs(idx,2)+step], 'k');
                idx = idx + 1;
                hold on;
            end
        end
    end
    
    % 셀 번호 표시
    cell_id = 1:1:rows*cols;
    for k = 1:rows*cols
        [r_idx, c_idx] = ind2sub([cols, rows], k);
        text(c_idx-0.9, r_idx-0.5, num2str(cell_id(k)), ...
             'FontSize', 8, 'Color', [0.7 0.7 0.7]);
    end
    hold on;
    axis square;
end

환경 행렬 정의 예시:

env = [0 0 0 1 0 0 1 0 0 0;
       1 0 0 0 0 1 1 0 0 0;
       0 0 1 0 0 0 1 1 0 0;
       0 0 0 0 0 0 0 0 0 0;
       0 0 0 0 0 1 0 0 1 0;
       1 0 0 0 0 1 1 0 0 0;
       0 0 0 1 0 0 0 0 0 0;
       1 1 1 0 0 0 1 0 0 0;
       0 0 0 0 0 1 1 0 0 0;
       0 0 0 0 0 1 1 0 0 0];

visualizeGrid(env);

2.3 대각선 이동 제약 조건

8방향 이동 체계에서 장애물 인접 셀의 대각선 이동은 충돌 위험이 있다. 이를 방지하기 위해 장애물 셀의 대각 인접 셀 간 이동을 제한한다.

인접 행렬 수정을 통해 구현:

%%%%%%%%%%%%%%%%%% 대각선 이동 제약 적용 %%%%%%%%%%%%%%%%%%
function adjMat = applyDiagonalConstraint(env, adjMat)
    [rows, cols] = size(env);
    total_cells = rows * cols;
    
    for r = 1:rows
        for c = 1:cols
            if env(r,c) == 1
                current = c + (r-1)*cols;
                
                % 상단 행 장애물
                if r == 1
                    if c == 1
                        adjMat(current+1, current+cols) = Inf;
                        adjMat(current+cols, current+1) = Inf;
                    elseif c == cols
                        adjMat(cols, cols+cols*(r-1)) = Inf;
                        adjMat(cols+cols*(r-1), cols) = Inf;
                    else
                        adjMat(c-1, c+r*cols) = Inf;
                        adjMat(c+r*cols, c-1) = Inf;
                        adjMat(c+1, c+r*cols) = Inf;
                        adjMat(c+r*cols, c+1) = Inf;
                    end
                end
                
                % 하단 행 장애물
                if r == rows
                    if c == 1
                        adjMat(c+cols*(r-2), c+cols*(r-1)+1) = Inf;
                        adjMat(c+cols*(r-1)+1, c+cols*(r-2)) = Inf;
                    elseif c == cols
                        adjMat(total_cells-1, (rows-1)*cols) = Inf;
                        adjMat((rows-1)*cols, total_cells-1) = Inf;
                    else
                        adjMat((r-2)*cols+c, (r-1)*cols+c-1) = Inf;
                        adjMat((r-1)*cols+c-1, (r-2)*cols+c) = Inf;
                        adjMat((r-2)*cols+c, (r-1)*cols+c+1) = Inf;
                        adjMat((r-1)*cols+c+1, (r-2)*cols+c) = Inf;
                    end
                end
                
                % 좌측 열 장애물 (비가장자리)
                if c == 1 && r ~= 1 && r ~= rows
                    adjMat(c+(r-2)*cols, c+1+(r-1)*cols) = Inf;
                    adjMat(c+1+(r-1)*cols, c+(r-2)*cols) = Inf;
                    adjMat(c+1+(r-1)*cols, c+r*cols) = Inf;
                    adjMat(c+r*cols, c+1+(r-1)*cols) = Inf;
                end
                
                % 우측 열 장애물 (비가장자리)
                if c == cols && r ~= 1 && r ~= rows
                    adjMat((r+1)*cols, r*cols-1) = Inf;
                    adjMat(r*cols-1, (r+1)*cols) = Inf;
                    adjMat(r*cols-1, (r-1)*cols) = Inf;
                    adjMat((r-1)*cols, r*cols-1) = Inf;
                end
                
                % 내부 장애물
                if r ~= 1 && r ~= rows && c ~= 1 && c ~= cols
                    adjMat(c+(r-1)*cols-1, c+r*cols) = Inf;
                    adjMat(c+r*cols, c+(r-1)*cols-1) = Inf;
                    adjMat(c+r*cols, c+(r-1)*cols+1) = Inf;
                    adjMat(c+(r-1)*cols+1, c+r*cols) = Inf;
                    adjMat(c+(r-1)*cols-1, c+(r-2)*cols) = Inf;
                    adjMat(c+(r-2)*cols, c+(r-1)*cols-1) = Inf;
                    adjMat(c+(r-2)*cols, c+(r-1)*cols+1) = Inf;
                    adjMat(c+(r-1)*cols+1, c+(r-2)*cols) = Inf;
                end
            end
        end
    end
end

3. CSA 기반 경로 계획 구현

3.1 메인 시뮬레이션 코드

clc; clear; close all; tic;

%% 환경 설정
raw_map = [0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
           0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
           0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
           0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
           0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
           0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
           0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0;
           0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0;
           0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0;
           0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0;
           0 0 0 0 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 0;
           0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0;
           0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0;
           0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0;
           1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0;
           1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0;
           0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0;
           0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0;
           0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0;
           0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0;];

% 좌우 대칭 변환
for i = 1:10
    for j = 1:20
        tmp = raw_map(i,j);
        raw_map(i,j) = raw_map(21-i,j);
        raw_map(21-i,j) = tmp;
    end
end

%% 경로 계획 영역 설정
start_pos = [1 1];
goal_pos = [20 20];
working_map = raw_map(start_pos(1):goal_pos(1), start_pos(2):goal_pos(2));
[grid_h, grid_w] = size(working_map);
search_dim = grid_w - 2;

%% CSA 파라미터
max_iter = 200;
pop_size = 50;
lower_b = 1;
upper_b = grid_h;

% 적합도 함수 핸들
obj_func = @(x) pathCost(x, working_map, lower_b, upper_b);

% 최적화 실행
[best_fit, best_sol, conv_history] = CapSA(pop_size, max_iter, ...
    lower_b, upper_b, search_dim, obj_func);
toc;

%% 결과 분석 및 시각화
rounded_path = round(best_sol);
disp(['최적 적합도: ', num2str(best_fit)]);

% 수렴 곡선
figure(1);
plot(conv_history, 'b-', 'LineWidth', 1.5);
xlabel('반복 횟수');
ylabel('적합도 값');
title('Capuchin Search Algorithm 수렴 곡선');
grid on;

% 최종 경로 생성
complete_route = [start_pos(1), rounded_path, goal_pos(1)];
smooth_path = createContinuousRoute(complete_route, working_map);
smooth_path = refinePath(smooth_path, working_map);
smooth_path = refinePath(smooth_path, working_map);

% 경로 시각화
figure(2);
% 원본 맵 복원
for i = 1:10
    for j = 1:20
        tmp = raw_map(i,j);
        raw_map(i,j) = raw_map(21-i,j);
        raw_map(21-i,j) = tmp;
    end
end

n = 20;
for i = 1:n
    for j = 1:n
        x1 = j-1; y1 = n-i;
        x2 = j;   y2 = n-i;
        x3 = j;   y3 = n-i+1;
        x4 = j-1; y4 = n-i+1;
        if raw_map(i,j) == 1
            fill([x1,x2,x3,x4], [y1,y2,y3,y4], 'r');
        else
            fill([x1,x2,x3,x4], [y1,y2,y3,y4], [1,1,1]);
        end
        hold on;
    end
end

xlabel('환경 좌표계');
renderPath(smooth_path, raw_map);
title('Capuchin Search Algorithm 기반 그리드 맵 로봇 경로 계획');

4. 참고 문헌

최정, 하해남, 곽양관. "차분 진화 알고리즘을 활용한 그리드 맵 로봇 최단 경로 계획." 기계와 유압, 2020년 9호.