밭을 빈틈없이 훑는 드론 경로 만들기

드론 회사에 다닐 때, 드론을 농지에 날려 약을 치는 일도 다뤘습니다. 방제 드론은 밭 위를 일정한 높이로 날면서 아래로 약을 뿌립니다. 이때 중요한 건 두 가지입니다. 빈틈없이, 그리고 고르게. 한 줄이라도 건너뛰면 약이 닿지 않은 곳이 생기고, 같은 자리를 두 번 지나면 그만큼 약이 낭비됩니다.

사람이 조종하면 이걸 눈대중으로 맞춰야 합니다. 그래서 회사에는 밭의 경계를 받아서, 빈틈없이 균일하게 약을 치는 최적의 경로를 알아내는 과정이 있었습니다. 저는 이 경로 자동 생성을 공개된 논문을 바탕으로 구현했습니다.

Coverage Path Planning이란

Coverage Path Planning(커버리지 경로 계획)은 정해진 영역을 빠짐없이 지나가는 경로를 만드는 문제입니다. 방제 드론뿐 아니라 항공 촬영, 청소 로봇, 잔디깎이 로봇도 같은 문제를 풉니다. 모두 "이 영역을 한 군데도 빼놓지 않고, 되도록 짧게 지나가려면?"이라는 질문입니다.

가장 널리 쓰는 답은 왕복 패턴입니다. 밭 끝까지 한 줄을 날고, 옆으로 한 칸 옮겨 반대 방향으로 돌아오기를 반복합니다. 이 패턴을 boustrophedon이라고 부릅니다. 그리스어로 '소가 밭을 갈며 도는 방식'이라는 뜻으로, 쟁기를 끄는 소가 밭 끝에서 돌아서 옆 줄을 가는 모양을 그대로 닮았습니다. 원래는 한 줄은 왼쪽에서 오른쪽으로, 다음 줄은 오른쪽에서 왼쪽으로 번갈아 쓰던 옛 글쓰기 방식을 가리키던 말입니다.

밭처럼 경계가 다각형인 영역에서는 이 왕복 패턴이 단순하면서도 효율적입니다. 줄과 줄 사이 간격만 살포 폭에 맞추면 빈틈이 생기지 않고, 꺾는 횟수도 줄 수만큼으로 정해집니다.

전체 흐름

이 글의 뼈대는 Li 외(2023)의 논문(새 탭에서 열림) "Coverage Path Planning Method for Agricultural Spraying UAV in Arbitrary Polygon Area"입니다. 임의의 다각형 밭에서 방제 드론의 경로를 만드는 방법을 다룹니다. 경계를 안쪽으로 줄이는 방법, 오목한 꼭짓점을 찾는 방법, 비행 방향을 고르는 방법이 들어 있습니다.

전체 흐름은 이렇습니다.

1. 밭 경계의 GPS 좌표를 미터 단위 평면 좌표로 바꿉니다.
2. 경계를 필요한 만큼 안쪽으로 줄입니다.
3. 비행 방향(각도)을 고릅니다.
4. 그 방향으로 평행선을 일정한 간격으로 긋습니다.
5. 평행선 가운데 밭 안에 들어오는 구간만 남깁니다.
6. 남은 구간을 지그재그로 이어 하나의 경로로 만듭니다.

경로 만들기는 두 차례로 나눠 진행합니다.

• 1차 면적 채우기: 밭 전체를 빈틈없이 채웁니다. 위 6단계와, 안쪽으로 파인 오목한 밭까지입니다.
• 2차 금지 구역 피하며 채우기: 밭 안에 드론이 들어가면 안 되는 구역이 있을 때, 그곳은 피하면서 나머지를 최대한 채웁니다.

그리고 문제를 단순하게 하려고, 드론이 늘 같은 폭(살포 폭)으로 같은 양을 고르게 뿌린다고 가정합니다. 실제 방제 드론은 속도나 높이, 바람에 따라 살포 폭과 양을 조절하기도 합니다. 그런 조절은 지금은 넣지 않고, 필요해지면 나중에 덧붙이기로 합니다.

1차: 면적 채우기

먼저 들어가면 안 되는 구역이 없는 밭에서, 밭 전체를 빈틈없이 채우는 경로부터 만듭니다.

1. GPS 좌표를 미터로 바꾸기

밭 경계는 보통 지도에서 꼭짓점을 찍어 얻습니다. 이 꼭짓점은 GPS의 기준 좌표계인 WGS84의 위도·경도입니다. 위도·경도는 지구 중심에서 본 각도라서, 그대로는 "두 점이 몇 m 떨어졌나"를 계산하기 어렵습니다.

밭 하나 정도의 크기라면 땅을 평평하다고 봐도 오차가 작습니다. 그래서 밭 근처의 한 점을 기준으로, 각 꼭짓점이 기준점에서 동쪽으로 몇 m, 북쪽으로 몇 m 떨어졌는지로 바꿉니다.

• 위도 1도는 어디서나 약 111km입니다(위도에 따라 110.6~111.7km).
• 경도 1도는 적도에서 약 111km이고, 위도가 높아질수록 짧아집니다(× cos 위도). 서울 근처(북위 37.5도)에서는 약 88km입니다.

이렇게 바꾸고 나면 나머지 계산은 모두 평면 위의 도형 문제가 됩니다. 경로를 다 만든 뒤에는 거꾸로 위도·경도로 되돌려 드론에 보냅니다.

2. 경계를 안쪽으로 줄이기

밭 가장자리에는 도랑이나 수로가 붙어 있기도 하고, 경계선 바로 위를 날면 약이 밭 밖으로 넘어가기도 합니다. 그래서 경로를 만들기 전에 경계를 필요한 만큼 안쪽으로 줄입니다(경계 축소, margin reduction). 얼마나 줄일지(h)는 지형이나 작물을 보고 사용자가 정합니다.

다각형을 줄이는 방법은 꼭짓점을 하나씩 옮기는 것입니다. 꼭짓점마다 양쪽 두 변이 이루는 각을 반으로 나누는 방향(각의 이등분선)으로 안쪽을 향해 옮깁니다. 이때 두 변이 모두 정확히 h만큼 안으로 들어오려면, 꼭짓점은 h보다 더 멀리, h ÷ sin(각의 절반)만큼 옮겨야 합니다. 각이 뾰족할수록 더 멀리 옮기는 셈입니다.

오목한 꼭짓점, 즉 안쪽으로 파인 꼭짓점은 반대 방향으로 옮깁니다. 이 구분을 빼먹으면 줄인 경계가 꼬이거나 밭 밖으로 튀어나옵니다.

3. 비행 방향 고르기

같은 밭이라도 어느 방향으로 왕복하느냐에 따라 경로가 크게 달라집니다. 좁고 긴 밭을 짧은 쪽으로 왕복하면 줄이 많아지고, 그만큼 자주 꺾어야 합니다. 긴 변과 나란히 날면 줄 수가 줄고 꺾는 횟수도 줄어듭니다.

꺾는 횟수가 중요한 건, 드론이 꺾을 때마다 속도를 줄이고 돌아서 다시 속도를 올려야 하기 때문입니다. 그 사이는 약을 뿌리지 않는 이동 시간입니다. 또 방향에 따라 다각형 가장자리에서 살포 띠가 밭 밖으로 넘치거나 모자라는 면적도 달라집니다.

논문은 이 두 가지를 하나의 점수(적합도, fitness)로 묶었습니다.

• 전체 비행 거리
• 실제로 뿌려지는 면적이 밭 면적보다 얼마나 넘치거나 모자란지(추가 커버리지 비율)

그리고 이 점수가 가장 좋은 각도를 유전 알고리즘(genetic algorithm)으로 찾습니다. 후보 각도를 여럿 만들어 점수가 좋은 것일수록 다음 세대에 뽑힐 확률을 높이고(룰렛 선택), 서로 섞고(교차) 가끔 조금씩 바꾸기(변이)를 반복하며 좋은 각도로 모여 가게 하는 방법입니다. 논문의 예시 밭(꼭짓점 5개짜리 오목한 밭)에서는 후보 200개로 300세대를 돌려 98.958도가 나왔고, 이때 비행 거리는 1,439.6m, 추가 커버리지 비율은 12.59%였습니다.

찾아야 하는 값이 각도 하나뿐이라, 데모에서는 각도를 조금씩 바꿔 가며 전부 계산해 보는 방식으로도 충분합니다.

아래 '직접 플레이' 데모는 0도부터 179도까지 1도씩, 180개 방향을 모두 계산합니다. 점수는 논문의 두 가지를 데모에 맞게 풀어 쓴 것으로, 전체 비행 거리에 안 뿌려진 면적과 뿌리면 안 되는 곳에 뿌려진 면적을 더합니다. 면적은 살포 폭으로 나눠 거리와 같은 단위로 맞추고, 두 면적 가운데 어느 쪽을 더 무겁게 볼지는 데모에서 직접 정할 수 있습니다.

4. 평행선 긋기

방향을 정했으면 계산을 쉽게 하려고 밭 전체를 돌려서, 비행 방향이 가로가 되게 만듭니다(좌표 회전). 그러면 평행선은 모두 가로줄이 됩니다.

가로줄은 일정한 간격으로 긋습니다. 간격은 드론이 한 번에 뿌리는 폭(살포 폭, swath)입니다. 첫 줄은 경계에서 살포 폭의 절반만큼 안쪽에 둡니다. 그래야 첫 줄의 살포 띠가 경계에 딱 맞게 닿습니다.

실제로는 바람이나 위치 오차 때문에 줄 사이에 틈이 생길 수 있어서, 간격을 살포 폭보다 조금 좁게 잡아 띠끼리 살짝 겹치게 하기도 합니다(겹침 비율, overlap).

• 줄 간격 = 살포 폭 × (1 − 겹침 비율)

이 글에서는 앞에서 정한 가정대로 살포 폭이 늘 같고 고르게 뿌려진다고 보고, 겹침 비율을 0으로 둡니다. 줄 간격이 곧 살포 폭입니다.

줄을 다 그은 뒤에는 다시 원래 방향으로 돌려 놓습니다.

5. 밭 안의 구간만 남기기

가로줄은 밭 경계와 여러 번 만납니다. 만나는 점(교점)을 왼쪽부터 정렬하면 들어가고, 나오고, 들어가고, 나오기를 반복합니다. 그래서 교점을 두 개씩 짝지으면(1번과 2번, 3번과 4번) 각 짝이 밭 안의 구간 하나가 됩니다.

볼록한 밭이면 한 줄에 교점이 두 개뿐이라 구간도 하나입니다. 하지만 L자처럼 파인 밭이면 한 줄이 경계를 네 번 만나고, 구간이 두 개로 나뉩니다.

여기서 흔한 실수가 교점 중 가장 바깥 두 개만 쓰는 것입니다. 그러면 L자 밭에서 두 구간이 하나로 이어져, 드론이 파인 부분, 즉 밭 밖을 가로질러 날게 됩니다. 그때 구현을 정리해 둔 문서에도 이 문제가 가장 큰 문제로 적혀 있었습니다.

6. 지그재그로 잇기

마지막으로 구간들을 하나의 경로로 잇습니다. 첫 줄은 왼쪽에서 오른쪽으로, 다음 줄은 오른쪽에서 왼쪽으로, 방향을 번갈아 가며 잇습니다. 이게 boustrophedon입니다.

드론에 보내는 건 각 구간의 양 끝점입니다. 이 점들을 경로점(waypoint)이라고 합니다. 구간 위를 날 때는 약을 뿌리고, 줄 끝에서 다음 줄로 넘어가는 동안에는 끕니다.

오목한 밭

여기까지는 볼록한 밭이면 깔끔하게 끝납니다. 문제는 실제 밭이 늘 볼록하지는 않다는 점입니다. 논밭은 길이나 수로를 따라 파인 모양이 흔합니다.

꼭짓점이 오목한지는 그 꼭짓점의 안쪽 각이 180도를 넘는지로 정해집니다. 논문은 이걸 토폴로지 매핑이라는 방법으로 판별합니다. 꼭짓점에 작은 원을 그리고, 이웃한 두 변이 그 원과 만나는 점을 꼭짓점 위아래의 가상의 선(투영선)에 비춰서, 어느 쪽에 떨어지는지에 따라 네 가지 경우로 나눠 판단합니다.

모든 오목한 꼭짓점이 문제가 되는 건 아닙니다. 논문은 비행 방향을 기준으로 오목한 꼭짓점을 두 종류로 나눕니다.

• 파인 곳을 지나가도 경로가 끊기지 않는 꼭짓점(1형)
• 비행 방향으로 지나가다 이 꼭짓점에 가로막혀, 밭 밖으로 나가지 않고는 건너편 밭에 닿을 수 없게 만드는 꼭짓점(2형)

2형 꼭짓점이 있으면 밭을 나눕니다. 그 꼭짓점에서 비행 방향과 나란한 선을 그어 경계와 만나는 곳까지 자르면, 2형 꼭짓점이 n개일 때 밭이 n + 1개로 나뉩니다. 나뉜 조각은 각각 볼록한 밭처럼 경로를 만들고, 조각과 조각을 이어 하나의 경로로 합칩니다.

재미있는 점은 같은 꼭짓점이라도 비행 방향을 바꾸면 종류가 바뀐다는 것입니다. 0도로 날 때는 2형이던 꼭짓점이 90도로 날면 1형이 되기도 합니다. 그래서 비행 방향을 잘 고르면 밭을 나눌 필요 자체가 줄어듭니다. 앞에서 방향 고르기가 중요하다고 한 또 하나의 이유입니다.

2차: 들어가면 안 되는 구역을 피하며 채우기

1차는 밭 전체를 채우는 문제였습니다. 실제 밭에는 드론이 들어가면 안 되는 구역(비행 금지 구역, no-fly zone)이 있기도 합니다. 전신주나 나무, 창고 둘레처럼 부딪힐 수 있는 곳, 민가나 축사 근처처럼 약이 닿으면 안 되는 곳입니다. 2차의 목표는 이런 금지 구역에는 절대 들어가지 않으면서, 나머지 밭을 최대한 빠짐없이 채우는 것입니다.

금지 구역을 부풀려서 표시하기

먼저 금지 구역을 지도에서 다각형으로 찍습니다. 그리고 경계를 줄일 때와 같은 방법으로, 이번에는 금지 구역을 바깥쪽으로 안전 거리만큼 부풀립니다(버퍼). 드론의 위치 오차와 크기, 약이 바람에 날리는 거리까지 생각한 여유입니다. 이렇게 하면 밭은 '바깥 경계 안에 구멍이 몇 개 뚫린 다각형'이 됩니다.

줄마다 구간이 갈라지는 곳에서 칸 나누기

금지 구역이 있으면 가로줄 하나가 밭 경계뿐 아니라 금지 구역 경계와도 만납니다. 5단계처럼 교점을 둘씩 짝지으면 금지 구역 양옆으로 구간이 두 개, 세 개로 갈라집니다.

이걸 그대로 지그재그로 이으면, 금지 구역 왼쪽 구간 끝에서 오른쪽 구간으로 넘어갈 때 금지 구역을 가로지르게 됩니다. 그래서 줄을 아래에서 위로 차례로 훑으면서, 구간 개수가 바뀌는 곳마다 영역을 칸(cell)으로 나눕니다. 금지 구역이 나타나기 시작하는 줄에서 칸 하나가 둘로 갈라지고, 금지 구역이 끝나는 줄에서 둘이 다시 하나로 합쳐집니다.

이렇게 나눈 칸 안에는 금지 구역이 없습니다. 칸마다 1차의 지그재그 경로를 그대로 만들면 됩니다. 이 방법을 boustrophedon cellular decomposition이라고 부르며, Choset와 Pignon이 1997년에 정리했습니다. 1차에서 오목한 밭의 2형 꼭짓점을 기준으로 밭을 나눈 것도 같은 생각입니다. 금지 구역은 밭 안쪽에 생긴 오목한 경계인 셈입니다.

칸을 도는 순서 정하기

칸이 여러 개면 어떤 순서로 돌지 정해야 합니다. 서로 맞닿은 칸끼리 선으로 이으면 칸들의 연결 지도(인접 그래프)가 생깁니다. 이 지도를 따라 모든 칸을 한 번씩 들르는 순서를 정하는데, 되도록 칸과 칸 사이를 옮겨 다니는 거리가 짧게 고릅니다. 칸이 적으면 가까운 칸부터 차례로 고르는 정도로도 충분합니다.

데모에서는 칸이 8개 이하이면 가능한 순서를 모두 따져, 칸 안을 도는 길이와 칸 사이를 옮겨 다니는 거리를 더한 값이 가장 짧은 순서를 고릅니다. 칸마다 어느 모서리에서 출발할지도 함께 고릅니다. 칸이 더 많으면 지금 칸에서 가장 가까운 칸부터 차례로 고릅니다. 칸 사이 거리는 바로 다음에 설명할, 금지 구역을 돌아가는 길로 잽니다.

칸 사이를 금지 구역을 돌아서 잇기

한 칸을 다 돌고 다음 칸의 시작점으로 갈 때는 약을 끄고 이동만 합니다. 이때도 금지 구역 위를 지나면 안 됩니다. 그래서 금지 구역을 돌아가는 가장 짧은 길을 찾습니다.

자주 쓰는 방법은 가시성 그래프(visibility graph)입니다. 출발점, 도착점, 부풀린 금지 구역의 꼭짓점들을 서로 직선으로 잇되, 금지 구역을 가로지르지 않는 선만 남깁니다. 그러면 '서로 보이는 점끼리 이은 지도'가 생기고, 이 지도에서 가장 짧은 길을 찾으면(Dijkstra 알고리즘) 금지 구역 모서리를 스치듯 돌아가는 최단 경로가 나옵니다.

금지 구역 둘레의 빈틈

부풀린 여유만큼은 금지 구역 둘레에 약이 닿지 않는 띠가 남습니다. 들어가면 안 되는 곳을 지키기 위한 빈틈이라, '최대한 채운다'는 말은 이 띠를 뺀 나머지를 빠짐없이 채운다는 뜻입니다. 필요하면 칸 경로를 다 돈 뒤 금지 구역 둘레를 따라 한 바퀴 도는 경로를 덧붙여 빈틈을 줄이기도 합니다.

주의할 점

• 위도에 따른 경도 보정: 1단계의 경도 길이(× cos 위도)를 빼먹으면 밭이 옆으로 늘어나고, 줄 간격도 틀어집니다. 아주 넓은 영역이면 평면 근사 대신 제대로 된 지도 투영을 써야 합니다.
• 꼭짓점 순서: 꼭짓점이 시계 방향으로 찍혔는지 반시계 방향으로 찍혔는지에 따라 '안쪽'이 바뀝니다. 경계를 줄이기 전에 방향을 한쪽으로 맞춰 둡니다.
• 너무 좁은 밭: 경계를 줄이고 나면 좁은 부분이 아예 사라지거나 꼬일 수 있습니다. 줄인 결과가 올바른 다각형인지 확인해야 합니다.
• 금지 구역 안전 거리: 부풀리는 여유가 너무 작으면 위치 오차로 금지 구역에 들어가고, 너무 크면 빈틈이 넓어집니다. 금지 구역끼리 가까우면 부풀린 구역이 서로 붙어 그 사이 땅은 아예 건너뛰게 됩니다.
• 칸이 너무 잘게 나뉘는 경우: 금지 구역이 많거나 모양이 복잡하면 칸이 잘게 쪼개져 이동 구간과 꺾는 횟수가 늘어납니다. 이럴 때는 비행 방향을 바꿔 보면 칸 수가 줄기도 합니다.

직접 플레이

예시 밭에서 선을 두 번 누르면 점이 생기고, 점을 두 번 누르면 지워집니다. 점과 장애물은 끌어서 옮기고, 장애물은 설정의 새 장애물 그리기로 더합니다. 시작을 누르면 드론이 경로를 따라 날며 약을 뿌립니다. 하늘색은 뿌린 자리, 산호색은 장애물과 회피 영역, 금색은 고른 꼭짓점입니다.

설정에서 살포 폭, 겹침, 안전 거리, 비행 방향을 바꾸면 경로가 바로 다시 계산됩니다. 중요도를 안 뿌린 곳 쪽으로 기울이면 밭 가장자리 너머까지 넉넉히 뿌리고, 잘못 뿌린 곳 쪽으로 기울이면 넘치기 전에 살포를 끕니다. 비행이 끝나면 결과 칸에 뿌린 비율과 안 뿌린 곳, 뿌리면 안 되는 곳에 뿌린 비율이 확정되고, 안 뿌린 자리는 빗금으로 남습니다.

정리

방제 드론의 경로는 결국 '밭 모양을 받아 지그재그 선을 긋는 일'입니다. 하지만 GPS 좌표를 평면으로 바꾸고, 경계를 줄이고, 방향을 고르고, 밭 안의 구간만 골라 잇는 단계마다 빠지기 쉬운 함정이 있습니다. 특히 오목한 밭과 금지 구역이 있는 밭은 구간을 짝짓는 것부터 영역을 칸으로 나누고, 칸 사이를 금지 구역을 돌아 잇는 것까지 따로 신경 써야 합니다.

이 경로는 날기 전에 미리 그려 두는 길입니다. 실제 비행에서는 여기에 지도에 없던 것을 만났을 때 비켜 가는 장애물 회피가 더해져야, 드론이 사람 손 없이 밭 하나를 끝까지 날 수 있습니다.

용어 설명

글에서는 기술 용어를 원어로 쓰고, 우리말로 옮길 수 있는 말은 괄호에 함께 적었습니다.

• Coverage Path Planning(커버리지 경로 계획): 정해진 영역을 빠짐없이 지나가는 경로를 만드는 문제.
• boustrophedon: 한 줄을 끝까지 간 뒤 옆으로 옮겨 반대 방향으로 돌아오기를 반복하는 왕복 패턴.
• WGS84: GPS가 쓰는 기준 좌표계. 위치를 위도·경도·높이로 나타냅니다.
• margin reduction(경계 축소): 다각형 경계를 일정 거리만큼 안쪽으로 줄이는 처리.
• swath(살포 폭): 드론이 한 번 지나갈 때 약이 뿌려지는 폭.
• overlap(겹침 비율): 이웃한 살포 띠가 서로 겹치는 비율. 빈틈을 막으려고 둡니다.
• waypoint(경로점): 드론이 차례로 지나가도록 보내는 지점.
• fitness(적합도): 유전 알고리즘에서 후보가 얼마나 좋은지 매긴 점수.
• genetic algorithm(유전 알고리즘): 후보 여러 개를 만들어 좋은 것끼리 섞고 조금씩 바꾸기를 반복하며 답을 찾는 방법.
• 볼록·오목 다각형: 모든 꼭짓점의 안쪽 각이 180도보다 작으면 볼록, 하나라도 180도를 넘으면 오목.
• no-fly zone(비행 금지 구역): 드론이 들어가면 안 되는 구역.
• buffer(버퍼): 금지 구역 다각형을 안전 거리만큼 바깥으로 부풀린 여유 영역.
• cell(칸): 금지 구역이 없도록 나눈 영역 조각. 칸마다 왕복 경로를 만듭니다.
• boustrophedon cellular decomposition: 줄마다 구간 개수가 바뀌는 곳에서 영역을 칸으로 나누고, 칸마다 왕복 경로를 만드는 방법.
• adjacency graph(인접 그래프): 맞닿은 칸끼리 이어 놓은 연결 지도. 칸을 도는 순서를 정할 때 씁니다.
• visibility graph(가시성 그래프): 금지 구역을 가로지르지 않고 서로 직선으로 보이는 점끼리 이은 그래프. 금지 구역을 돌아가는 최단 경로를 찾을 때 씁니다.
• Dijkstra 알고리즘: 그래프에서 한 점에서 다른 점까지 가장 짧은 길을 찾는 방법.

더 알아보기

• J. Li, H. Sheng, J. Zhang, H. Zhang, Coverage Path Planning Method for Agricultural Spraying UAV in Arbitrary Polygon Area(새 탭에서 열림), Aerospace, 2023: 이 글의 뼈대가 된 논문(오픈 액세스)
• H. Choset, P. Pignon, Coverage Path Planning: The Boustrophedon Decomposition(새 탭에서 열림), Field and Service Robotics, 1997: 장애물이 있는 영역을 칸으로 나눠 왕복 경로로 덮는 방법
• E. Galceran, M. Carreras, A Survey on Coverage Path Planning for Robotics(새 탭에서 열림), Robotics and Autonomous Systems, 2013: Coverage Path Planning 방법들을 정리한 서베이
• M. Coombes 외, Optimal Polygon Decomposition for UAV Survey Coverage Path Planning in Wind(새 탭에서 열림), Sensors, 2018: 바람까지 고려해 다각형을 나누는 측량 드론 경로 계획