볼록영역 로봇 경로계획, 새 탐색 알고리즘으로 속도 향상

한 연구팀이 복잡한 환경 속에서 로봇의 이동 경로를 계획하는 새로운 알고리즘 틀을 제시했다고 arXiv에 게재된 프리프린트 논문에서 밝혔습니다. 제1저자 Jing Tao Tang을 비롯한 연구진은 이 문제를 '볼록집합 그래프 위의 스타이너 외판원 문제(Steiner-TSP on Graphs of Convex Sets)'라고 명명했습니다.

이 문제는 일종의 경로 퍼즐입니다. 로봇은 반드시 방문해야 하는 여러 볼록 영역들을 모두 지나면서 비용이 가장 적은 폐경로를 찾아야 하는데, 동시에 선택적으로 지날 수 있는 '경유' 영역을 활용하거나 필요하면 같은 지점을 다시 방문할 수도 있습니다. 여기서 '볼록집합'이란 영역 안의 임의의 두 점을 직선으로 이었을 때 그 직선이 항상 영역 안에 머무는 공간을 뜻하며, 로봇의 장애물 없는 이동 가능 영역이나 유효한 자세를 표현할 때 흔히 쓰이는 방식입니다. 이런 네트워크에서 가능한 경로의 수는 사실상 무한하기 때문에 정확한 해를 구하는 것은 계산적으로 매우 어렵습니다.

연구진은 이를 해결하기 위해 '뿌리 있는 부분 경로(rooted walk prefix)'를 탐색하는 통합 분기한정(branch-and-bound) 탐색법을 제안했습니다. 이 방법은 두 가지 수학적 하한 계산을 이용해 탐색 범위를 줄입니다. 하나는 이미 확정된 경로에 누적된 비용을 추적하고, 다른 하나는 '컷 분리 연결 흐름 완화(cut-separated connected-flow relaxation)'라는 기법으로 남은 모든 필수 영역을 방문하고 출발점으로 돌아오는 데 필요한 최소 잔여 비용을 추정합니다. 모든 비용이 양수라는 가정 아래, 논문은 최선 우선(best-first) 방식의 탐색이 초기 추정해(인컴번트, incumbent) 없이도 풀 수 있는 모든 사례에서 유한한 단계 안에 종료됨을 증명했으며, 깊이 우선(depth-first) 방식은 초기 추정해가 확보된 이후 종료됨을 보였습니다. 또한 사용자가 지정하는 허용 계수 epsilon(1 이상)을 이용해, 찾아낸 해의 비용이 실제 최적값의 epsilon배를 넘지 않는다는 것을 보장하는 전역 하한값도 제공합니다.

연구진은 이 방법을 이동형 매니퓰레이터(mobile manipulator, 이동 가능한 로봇 팔) 점검 작업에 적용해 검증했습니다. 이 작업에서 로봇은 어떤 센싱 모드를 사용할지, 목표물을 어떤 순서로 방문할지, 그리고 어떤 연속 궤적을 따를지를 동시에 결정해야 하며, 이때 행동 간 순서 제약은 유한 흔적 위의 선형 시간논리(LTL_f, linear temporal logic over finite traces)라는 형식 언어로 표현됩니다.

벤치마크 실험에서 최선 우선과 깊이 우선 두 방식 모두 모든 테스트 사례에서 30초 이내에 실행 가능한 해를 찾았으며, 인증된 평균 최적성 격차(certified optimality gap)는 각각 28.1%와 29.7%로 나타났습니다. 이는 찾아낸 해가 이론상 최적해와 대략 이 비율 이내로 근접함을 의미합니다. 반면 비교 대상이 된 최근 두 가지 기존 방법은 같은 벤치마크 사례 중 절반 정도에서만 해를 찾는 데 성공했다고 논문은 밝혔습니다.

이번 연구는 하드웨어 시연이 아닌 이론 및 벤치마크 기반 결과이지만, 로봇이 어수선하거나 구조화된 환경에서 점검 경로, 센싱 결정, 이동 궤적을 동시에 계획해야 하는 문제, 즉 그동안 효율적이면서도 해의 품질을 보장하며 풀기 어려웠던 조합적 과제를 다루고 있다는 점에서 의미가 있습니다.