영역완전탐사경로계획 (Coverage Path Planning (CPP))
쉽게 풀면
청소기 로봇이 방 구석구석을 하나도 빠뜨리지 않고 지나가도록 이동 경로를 짜는 방법입니다.
왜 중요한가
청소·잔디깎기·농약 살포·해저 탐사처럼 영역 전체를 빠짐없이 지나야 하는 작업의 경로를 만드는 문제로, 청소로봇 상용화와 함께 가장 실용적 성과를 낸 계획 분야입니다. 중복 방문률과 총 경로 길이, 미탐사 면적이 표준 평가 지표입니다. 논밭에 농약을 살포하는 드론이나 해저 지형을 조사하는 수중 로봇처럼, 특정 지점이 아니라 영역 전체를 대상으로 하는 작업 전반에서 이 계획 방식이 핵심 역할을 한다.
논문에서는 이렇게 쓰입니다
전체 공간을 작은 조각으로 나누고, 그 조각들을 겹치는 부분을 최소화하면서 하나도 빠짐없이 지나가는 순서를 찾는다는 뜻입니다.
여러 경로 계획 방법을 서로 비교해서, 전체 영역을 빠짐없이 지나가는 데 걸리는 시간과 같은 곳을 두 번 지나가는 비율이 어떻게 다른지를 살펴보았다는 뜻입니다.
조금 더 깊게 보면
A에서 B로 가는 일반 경로계획과 목표가 반대여서, 최단 경로가 아니라 모든 셀을 최소 중복으로 방문하는 문제이며 격자 크기가 커지면 순회 판매원 문제와 같은 난도가 됩니다. 영역을 볼록 조각으로 분할해 각 조각을 지그재그로 덮는 셀 분할 방식이 표준이지만, 위치추정 오차가 커지면 계획 자체가 완벽해도 실제로는 빈 줄이 생깁니다. 영역을 여러 개의 볼록한 하위 영역(셀)으로 나눈 뒤 각 셀을 지그재그 패턴으로 훑고 셀 사이를 이동하는 셀 분할 방식이 표준적인 접근이며, 셀을 어떻게 나누는지에 따라 총 이동 거리와 방향 전환 횟수가 크게 달라진다. 완전 탐사를 우선하면 경계 부분에서 여러 번 겹쳐 지나가야 해 비효율이 생기고, 효율을 우선하면 구석 영역이 누락될 위험이 커지는 상충 관계가 있어 두 목표 사이의 비중을 조정하는 파라미터가 실무에서 중요하게 다뤄진다.
주의할 점
완전 탐사와 효율성(이동 거리 최소화)은 서로 상충하는 목표라 두 기준 사이의 균형 설계가 필요합니다.
위치추정 오차가 누적되면 계획 자체는 완벽해도 실제 로봇이 지나간 궤적에는 미세하게 빠진 줄무늬(누락 영역)가 생길 수 있어, 위치추정 정확도가 실질적 커버리지율을 좌우한다.