Polar Coordinate-based Differential Evolution for Moving Target Search Using Vision Sensor on Unmanned Aerial Vehicles

당신이 숨바꼭질을 하고 있는데, 상대방은 도망가고 있고, 지도는 거대하며, 당신에게는 햇빛이 너무 강하면 흐릿해지거나 바람이 너무 강하면 흔들리는 쌍안경 한 쌍뿐이라고 상상해 보십시오. 이것이 실종된 등산객이나 재난 지역의 생존자를 찾으려는 구조대원들이 마주하는 일상의 현실입니다. 과학계에서는 이를 "최적 탐색(optimal search)"이라 부르며, 컴퓨터가 소중한 시간을 낭비하지 않기 위해 취해야 할 최선의 경로를 찾아내려는 하나의 퍼즐과 같습니다. 여기서 핵심 아이디어는 시간이 적이라는 것입니다. 찾는 시간이 길어질수록, 대상의 위치는 사실이 아닌 추측이 되어 찾기가 더 어려워지기 때문입니다. 이를 해결하기 위해 과학자들은 카메라를 장착한 "드론(UAV, 무인 항공기)"을 사용하지만, 드론에게 완벽한 경로를 비행하도록 프로그래밍하는 것은 매우 어렵습니다. 왜냐하면 드론에는 물리적 한계가 있기 때문입니다. 즉, 즉각적으로 회전할 수 없고, 최대 속도가 정해져 있으며, 영원히 날 수는 없습니다.

이 논문은 드론이 움직이는 표적(예를 들어 길을 잃은 사람이나 물에 떠 있는 생존자)을 추적하도록 가르치는 영리한 새로운 방법을 소개합니다. 베트남과 한국의 연구진은 "극좌표 기반 차분 진화(Polar coordinate-based Differential Evolution, 줄여서 PDE)"라는 새로운 알고리즘을 개발했습니다. 이것은 단순히 드론에게 어디로 가라고 말하는 것이 아니라, 그곳에 도달하기 위해 몸을 어떻게 움직여야 하는지 알려주는 초스마트 코치와 같습니다. 표준 지도 좌표(예: "오른쪽으로 10미터, 위로 5미터 이동")를 사용하는 대신, PDE 알고리즘은 드론의 모국어로 말합니다: "이 각도로 회전하여 이 거리만큼 비행하라." 이렇게 함으로써 드론은 막다른 길에 갇히거나 불가능한 회전을 시도하는 상황을 피할 수 있습니다. 연구진은 컴퓨터 시뮬레이션과 실제 들판에서 드론을 이용해 이 방법을 테스트했으며, 특히 표적이 움직이고 탐색 영역이 넓을 때 PDE가 다른 대중적인 방법들보다 더 빠르게 표적을 찾는 데 효과적임을 발견했습니다.

문제: "골든 타임"과의 경주

수색 및 구조 작업에는 "골든 타임"이라는 개념이 있습니다. 이는 누군가 실종된 직후, 생존 가능성이 가장 높은 짧은 시간 창을 의미합니다. 시간이 흐를수록 확률은 떨어집니다. 왜일까요? 사람이 움직일 수도 있고, 바람이 그들을 밀어낼 수도 있으며, 지형이 그들을 숨길 수도 있기 때문입니다. 전통적인 수색 방식은 종종 지상 팀이나 유인 항공기에 의존하는데, 이는 느리거나 위험할 수 있습니다. 여기서 드론(UAV)이 등장합니다. 드론은 위험한 지형을 가로질러 빠르게 이동할 수 있으며 인간이 볼 수 없는 것을 볼 수 있습니다. 하지만 여기에는 함정이 있습니다. 만약 드론에게 무작정 무작위로 비행하라고 한다면 표적을 놓칠 수 있습니다. 그렇다고 완벽한 격자 모양으로 비행하라고 한다면 빈 공간을 지나다니며 시간을 낭비할 수도 있습니다. 목표는 최대한 빨리 표적을 발견할 확률을 극대화하는 완벽한 비행 경로를 찾는 것입니다.

두뇌: 드론은 어떻게 "생각"하는가

최적의 경로를 찾기 위해 드론은 표적이 어디에 있을지 예측할 수 있는 두뇌가 필요합니다. 저자들은 표적의 움직임을 "마르코프 과정(Markov process)"으로 모델링했습니다. 쉽게 말해, 이는 표적의 다음 움직임이 한 시간 전의 위치가 아니라, 현재 위치와 현재 움직임에 주로 의존한다는 것을 의미합니다. 이는 마치 강물에 떠 내려가는 나뭇잎을 예측하는 것과 같습니다. 현재의 흐름을 알고 있다면, 몇 초 후에 나뭇잎이 어디에 있을지 짐작할 수 있는 것과 같습니다.

또한 드론은 자신의 "눈"이 얼마나 좋은지도 알아야 합니다. 이 논문은 표적을 발견할 확률을 계산하기 위해 NVESD라는 모델을 사용합니다. 이는 단순히 표적이 얼마나 멀리 있느냐의 문제가 아니라, 이미지의 품질에 관한 문제입니다. 햇빛이 너무 눈부시거나 표적이 작고 흐릿하다면, 그들을 포착할 확률은 떨어집니다. 알고리즘은 이 두 가지 요소, 즉 표적이 있을 법한 곳과 카메라가 그들을 볼 가능성을 결합하여 "신념 지도(belief map)"를 생성합니다. 이 지도는 열지도(heat map)와 같아서, 가장 밝은 부분이 표적이 존재할 확률이 가장 높은 곳을 나타냅니다.

해결책: 극좌표의 기술

이 논문의 핵심 혁신은 드론의 비행 경로를 계획하는 방식에 있습니다. 대부분의 컴퓨터 알고리즘은 그래프 용지의 격자처럼 x와 y 값을 사용하는 "데카르트 좌표계(Cartesian coordinates)"를 사용합니다. 수학적으로는 유용하지만, 드론에게는 최악입니다. 만약 드론이 비행 중에 회전해야 한다면, 데카르트 알고리즘은 드론이 즉각적으로 원을 그리며 돌거나 엔진이 허용하는 것보다 빠르게 비행해야 하는 경로를 계산할 수 있습니다. 이는 자동차에게 최소 회전 반경을 고려하지 않고 "북쪽으로 5미터, 동쪽으로 5미터 이동하라"고 명령하는 것과 같습니다.

저자들은 대신 "극좌표(Polar coordinates)"를 사용할 것을 제안했습니다. "지점 (x, y)로 가라"고 말하는 대신, 알고리즘은 드론에게 "이 각도($\psi$)로 이 거리($\rho$)만큼 비행하라"고 명령합니다. 이는 드론이 실제로 움직이는 방식과 일치합니다. 이 방식을 사용함으로써, 알고리즘은 자연스럽게 드론의 물리적 한계를 존중하게 됩니다. 처음부터 이러한 한계들을 바탕으로 수학이 설계되었기 때문에, 너무 급격한 회전이나 너무 빠른 속도를 요구하는 경로를 제안할 수 없게 됩니다.

그들은 이 아이디어를 "차분 진화(Differential Evolution, DE)" 알고리즘 안에 담았습니다. DE는 "군집 지능(swarm intelligence)"의 일종으로, 탐험가 팀처럼 작동합니다. 안개 낀 산맥에서 가장 높은 봉우리를 찾으려는 등산객 그룹을 상상해 보십시오. 그들은 전체 지도를 알지 못하지만, 서로 노트를 공유합니다. 만약 한 명의 등산객이 높은 지점을 발견하면, 다른 이들도 그 구역을 향해 이동하지만, 동시에 더 높은 곳을 찾을 수 있는지 확인하기 위해 약간씩 다른 방향을 시도합니다. "차분(Differential)"이라는 부분은 두 등산객의 위치 차이를 보고 다음 점프 방향을 결정한다는 것을 의미합니다.

저자들은 이 군집 지능을 극좌표 시스템과 결합했습니다. 그들은 이를 PDE라고 부릅니다. 시뮬레이션에서 이 가상의 드론 팀은 표준적인 방법들을 사용하는 팀보다 훨씬 더 효율적으로 탐색 영역을 조사했습니다.

결과: 시뮬레이션과 실제 비행

연구진은 600m x 600m의 작은 구역부터 2000m x 2000m의 거대한 구역에 이르기까지 여섯 가지 다른 시나리오에서 PDE 알고리즘을 테스트했습니다. 그들은 PDE를 입자 군집 최적화(PSO), 유전 알고리즘(GA), 그리고 표준 차분 진화(DE)와 같은 유명한 알고리즘들과 비교했습니다.

컴퓨터 시뮬레이션에서 PDE는 일관되게 더 높은 확률로 표적을 더 빠르게 찾아냈습니다. 예를 들어, 한 시나리오에서 PDE는 약 0.529의 탐지 확률을 달-성한 반면, 표준 DE 알고리즘은 0.410에 그쳤습니다. 논문은 표준 DE가 종종 "지역 최적점(local optima)"에 갇히는 경향이 있다고 언급했습니다. 즉, 좋은 지점을 찾긴 했지만 루프에 빠져서 최선의 지점을 보지 못했다는 뜻입니다. 극좌표를 사용한 PDE는 이러한 루프를 탈출하여 전역 최적 경로(global best path)를 찾는 데 더 뛰어났습니다.

그들은 컴퓨터 게임 수준에서 멈추지 않았습니다. 이론을 테스트하기 위해 실제 들판으로 3DR Solo 드론을 가지고 나갔습니다. 드론은 PDE 경로를 입력받아 80m x 80m 구역 위를 비행하도록 프로그래밍되었습니다. 표적(사람)은 1.5 m/s의 속도로 걸었습니다. 드론은 알고리즘이 생성한 경로를 따라 비행했고, 실제로 비행한 경로는 계획과 매우 유사했습니다. 드론은 표적이 있을 것으로 예상되는 구역 위를 성공적으로 비행했고, 카메라는 그 사람을 포착했습니다. 저자들은 실제 테스트가 성공적이었지만, 표적이 예측대로 정확히 움직였다는 점에 기반하고 있다고 언급했습니다. 실제 재난 상황은 더 혼란스럽겠지만, 이 테스트는 해당 알고리즘이 실제 드론이 비행 가능한 경로를 생성한다는 것을 증명했습니다.

이것이 중요한 이유

이 논문은 드론의 언어(극좌표)를 사용하고 스마트한 팀 기반 탐색 전략을 활용함으로써 수색 및 구조 작업을 더 효과적으로 만들 수 있음을 시사합니다. PDE 알고리즘은 단순히 경로를 찾는 것이 아니라, 드론의 한계를 존-중하면서 구조 확률을 극대화하는 실행 가능한(feasible) 경로를 찾아냅니다. 저자들은 단일 드론이 배터리 수명 때문에 커버할 수 있는 영역이 제한적이라는 점을 인정하면서도, 이 방법이 향ate 협력하는 드론 함대의 기초가 될 수 있다고 제안합니다. 현재로서는, 이것이 우리의 비행 로봇을 더 똑똑하고, 더 빠르고, 매 초가 절박한 순간에 더 도움이 되도록 만드는 중요한 단계입니다.