1. 서 론

최근 드론 기술이 많이 보편화 되면서 다양한 산업에서 드론을 활용한 서비스를 연구하고 있다. 그 중에서 현재까지 가장 많이 상용화된 분야는 단연 물류 배송 분야일 것이다. 초창기 연구에서는 주로 사람이 가기 힘든 오지 환경이나 구급약 같은 긴급한 상황일 때를 고려한 사업 모델이 주로 개발되었는데 최근에는 점차 기술이 안정되면서 우리 주변 도심 환경에서도 활용할 수 있는 연구가 조금씩 진행되고 있다[3].

A* 경로 계획법을 사용하여 Large-Scale 영역을 시도한 연구가 있는데 해당 연구는 전체 영역을 A*가 탐색하도록 Global Grid로 설정한 것이 아니라 Local 영역에서 Grid를 이동하면서 Path Planning을 수행한 연구라서 도심에서 진행하고자 하는 광역 경로 계획과는 방향이 다른 연구이다[2].

Grid 기반 경로 계획 중 Warehouse 환경에서 Multi Agent를 활용한 연구도 진행된 바 있는데 해당 연구도 또한 Grid Size가 일정하게 경로계획을 수행했다[1]. 또한 드론을 활용하여 지형 모니터링을 수행한 연구도 있는데 해당 연구는 Informative Path Planning 분야로 일정한 크기의 격자 공간을 비행하면서 지형에 있는 정보를 얻는 연구이다. 센서 화질에 따라 Information이 적용되는 Grid의 크기가 변하긴 하지만 Grid Size가 바뀌지는 않고 적용되는 Information의 범위가 달라지는 연구라서 본 연구와는 접근법이 다른 연구이다[5].

본 논문은 도심 환경에서 드론을 이용한 자율배송을 수행하는데 필요한 광역 경로계획 알고리즘에 관한 내용이다. 본 연구의 선행 연구로는 장애물 주변을 High Resolution으로만 Grid Size를 나눈 Flexible Grid A* 알고리즘 연구가 있다[4]. 본 연구에서는 이를 기반으로 해서 보다 효율적인 광역 경로계획을 수행하기 위해서 다양한 크기의 격자로 나눌 수 있는 프레임워크를 개발하였다.

본 연구의 본론은 두 가지로 구성되어 있다. 먼저 지도상에 있는 건물, 주차장 등을 장애물로 등록해야 한다. 보통 Grid 기반의 경로계획 알고리즘에서는 장애물의 Geometry가 포함된 셀 전체가 장애물로 취급하는 경우가 많은데 본 연구에서는 지도에 있는 장애물을 사용자가 자유롭게 설정할 수 있도록 구성했다. 두 번째로는 장애물 주변에 있는 Grid를 나누는 작업을 진행한다. 기존의 연구에서는 장애물과 거리의 구분없이 높은 분해능으로 Grid를 나눠서 진행했는데 본 연구에서는 장애물과 먼 거리는 중간 크기의 격자로 나누고 장애물과 근접한 거리는 더 작은 크기의 격자로 나눠 계산 효율을 더 높이고자 한다.

2. 도심형 장애물 등록

2.1 장애물 등록

본 논문은 해당 연구과제에서 드론 배송 실증 단지로 구축 중인 염곡동의 한 주유소를 출발점으로 설정하였다. 격자가 커버하는 영역의 크기는 <Figure 1>에 있는 위성 지도와 같이 대략 1000m×750m으로 넓은 도심지에서 배송하는 시나리오를 가정했다. 서론에 말한 것과 같이 출발점에서 도착점까지 가는 경로를 찾기 위해서 먼저 넓은 격자를 <Figure 1>과 같이 생성한다. 이 영역을 만약 5m 간격으로 격자를 만들었다고 가정하면 격자 전체 개수는 30,000개가 되어 최적 경로를 계산하기 위해 거리의 비용을 계산할 때 계산양이 급격하게 증가한다. 따라서 본 파트의 넓은 격자는 50m 단위로 설정하였고 전체 격자의 크기는 300개가 되도록 설정한다.

격자를 지도에 생성하였다면 우리는 그 위에 장애물을 설정할 수 있다. 위 그림과 같이 위성 지도에서 건물이나 주차장, 또는 만약 드론이 추락하거나 낙하물이 발생했을 때 인명피해가 발생하면 안 되는 영역 등을 장애물로 설정할 수 있다. 장애물 설정은 <Figure 2>와 같이 만들 수 있다. 여기서 X방향은 East 방향으로 LLH(latitude-longitude- height) 좌표계에서 경도(Longitude) 방향이 되고 Y방향은 North 방향으로 LLH 좌표계의 위도(Latitude) 방향이 된다. 따라서 장애물의 영역을 설정할 때 좌측 하단을 잡으면 X, Y 둘다 최소값이 되고 우측 상단을 잡으면 X, Y 둘 다 최대값이 된다. 우리는 이 정보를 이용해 추후에 격자 나누기를 수행할 때 기준으로 삼을 것이다.

위와 같은 방법으로 <Figure 1>에서 설정했던 working space내에 있는 장애물들을 모두 반영하면 <Figure 1>의 오른쪽 그림과 같이 나타나는 것을 확인할 수 있다.

2.2 안전 경계 설정

위의 프로세스로 장애물을 지도상에 만들어 놓으면 사전에 설정해 놓은 안전 경계를 나타낼 수 있다. 사전에 설정한 안전 거리, d_s는 5.0m로 세팅하여 건물로부터 d_s이내 노드들을 제거하여 경로가 생기지 않도록 만들었다. 그리고 안전거리가 고려된 영역으로부터 사전 설정된 격자 크기만큼의 영역을 만들어서 이 영역 이내에 있는 셀들을 Middle Resolution으로 나누려고 한다. 이때 전체 노드의 집합은 아래와 같이 나타낼 수 있다.

여기서 G 는 격자 그래프의 전체 집합을 나타내고 p_i 는 i번째 격자점의 2차원 위치 벡터를 나타낸다.

middle resolution으로 나눌 셀의 격자들을 추리기 위해서 아래와 같은 판별식으로 얻을 수 있다.

위 식에서 M 은 중간 크기의 격자 사이즈로 나눌 격자점들의 집합을 나타낸다. 위 판별식을 통해 장애물의 Safety Line에서 레퍼런스 길이로 격자 간격까지 반영된 Middle Resolution Line 영역 내에 있는 격자들 중 격자 중앙점들이 내부에 존재하는 모든 격자들을 포함하게 된다. 그림으로 보면 <Figure 3>과 같이 나타낼 수 있다.

3. Efficient Grid 경로 생성

3.1 Global Index Mapping

지금까지 2절에서 지도상의 커스텀 장애물을 등록하고 해당 장애물에서 안전 경계에 있는 셀들을 선정하는 것까지 진행했다. 본 절에서는 선택된 셀들을 원하는 크기의 격자로 나누는 작업을 진행하려고 한다. 사실 격자의 크기를 정해진 크기로 나누는 것은 어려운 작업이 아니다. 하지만 우리는 해당 격자를 통해 출발점에서 원하는 목표점까지 가는 경로 계획을 수행하려면 이는 격자의 위치와 격자가 어디에 연결되었는지 그래프로 표현해야 한다. 기존의 A* 알고리즘이 빠르게 동작하는 이유는 이러한 그래프가 일정한 격자로 구성되어 있다는 가정하에 연결을 고려하지 않고 오롯이 인덱스의 위치만으로도 연결을 가정하기 때문에 많은 부분들이 생략되어 빠르게 동작하는 것을 알 수 있다. 하지만 본 연구에서 수행하는 multi size grid 환경에서는 이러한 인덱싱을 가정할 수 없기 때문에 각각의 격자에 대한 인덱스의 연결을 설정해줘야 한다. 여기서 가장 중요한 점은 격자를 나누면서 새로 생성되는 노드들은 모두 unique한 인덱스를 가져야만 하는 것이다.

가장 먼저 수행해야 될 일은 처음에 생성한 Global Grid에 인덱싱을 수행해야 한다. 인덱스의 시작은 왼쪽 하단의 점부터 시작해서 x방향으로 증가하면서 각 꼭지점에 인덱스를 부여한다.

앞에서 설명한 것과 같이 그냥 여기에서 경로계획을 수행하면 일정한 크기 및 형상을 알고 있기 때문에 인덱싱을 하는 것이 곧 노드 간에 연결까지 알려주는 것이지만 우리는 여기서 더 높은 분해능의 격자로 나눌 것이기 때문에 아래와 같은 알고리즘을 통해 그래프와 같이 구성한다. 본 논문에서는 이러한 작업을 Edge Mapping이라고 표현한다. Algorithm 1은 Edge 그래프에 연결을 추가할 때 사용하는 알고리즘인데 src와 dst의 인덱스가 존재할 때 해당 행에 해당하는 Edge 집합에 src와 dst 각각의 인덱스를 추가하는 방식으로 구성된다.

Algorithm 2는 앞서 말한 것과 같이 넓은 격자의 index를 추가하면서 동시에 edge mapping도 같이 수행하는 프로세스를 나타낸다. 해당 연결 구성은 노드의 각 상하 좌우와 더불어 대각선까지 연결하는 것을 포함하고 있다.

3.2 Inner Grid Index Mapping

위와 같이 Global Grid의 index를 모두 mapping을 수행했다면 2절에서는 선택된 셀들을 나누는 작업을 진행한다.

High-resolution Grid를 만들기 위해서는 <Figure 5>와 같이 선택된 셀을 s개 격자로 나눠야 한다. 우리는 나누는 변의 Geometry를 이용하기 위해서 위 그림과 같이 Zone을 설정하여 해당 구역을 Local Memory로 데이터를 저장하게 된다. 예를 들어 Zone A의 경우, 해당 영역에서는 인덱스가 증가할 때 x방향으로 증가하는 것을 알 수 있다. 그리고 Zone B의 경우 인덱스가 y방향으로 증가하는 것을 Geometric하게 추측할 수 있다. 그러므로 각 Zone의 Geometry 정보를 이용해 각 변의 인덱스를 mapping하게 된다.

만약에 아래 그림과 같이 앞선 프로세스에서 Inner Grid Mapping이 수행되어 어느 한 Zone의 메모리가 이미 다른 인덱스로 mapping이 되어 있다면 해당 Zone의 인덱스를 새로 만들지 않고 이미 있는 인덱스를 저장하여 인덱스의 중복을 피하도록 한다.

위와 같이 각 셀의 변을 쪼개어 인덱스를 생성하고 Zone의 메모리에 저장했다면 다음으로는 내부에 새로 생성된 노드들의 인덱스를 mapping 해야 한다. 다음 그림과 같이 내부에서 Grid가 생성되는 영역을 Local Grid Area라고 한다.

Local Grid Area를 인덱싱하는 방법은 앞의 3.1절에서 Global Grid의 인덱스를 추가하는 방법과 동일하다. Algorithm 2의 프로세스를 그대로 진행하여 Local Grid 영역 내의 격자점들을 모두 인덱싱 했다고 하면 마지막으로 Local Grid 영역의 외부 변의 인덱스와 앞서 진행한 Zone의 인덱스를 연결해야 한다. 이 과정을 한번에 수행하는 Pseudo Code는 Algorithm 3과 같이 나타낼 수 있다.

3.3 단계별 Grid 생성

3.2절에서 제시한 방법은 resolution에 상관없이 셀의 내부를 일정한 간격 s로 나누고 새로 생긴 노드에 인덱싱을 수행하는 방법을 나타냈다. 본 연구에서는 서론에서 말한 것과 같이 두 가지의 resolution으로 Grid를 나눠서 좀 더 효율적인 경로 계획을 수행하려고 한다.

제2장에서 안전 경계에 있는 셀을 판별하여 먼저 Middle Resolution으로 나누면 새로 생성된 인덱스는 G에 추가가 되므로 High Resolution으로 나눌 셀을 G에서 한번 더 판별해야 한다. Middle Resolution을 s라고 한다면 우리는 아래와 같은 판별식을 만들 수 있다.

위 판별식은 노드 집합인 G에서 새로 추가된 노드에서 탐색을 수행하고 탐색 범위는 안전 거리가 고려된 w_hη/s만큼 떨어진 영역으로 설정했다. 이때 w_h는 얼마나 High Resolution의 영역을 크게 만들 것인지 정하는 가중치인데 본 연구에서는 1.5의 값으로 설정하였다. 위의 판별식으로 선별된 노드들을 H 라는 집합으로 만들고 해당 집합 내에 있는 Grid를 High Resolution으로 쪼개면서 장애물 주변을 최적 경로로 회피할 수 있게 만든다.

위 과정들을 통해 Multi Grid Mapping이 끝나게 되면 <Figure 8A>와 같이 여러 가지 격자 사이즈가 존재하는 Efficient Grid 환경이 만들어지는 것을 볼 수 있고 <Figure 8B>는 각 노드가 연결되어 있는 Edge를 보여주는 그래프로 Safety Distance가 고려된 영역은 노드들이 삭제되어 장애물들을 회피할 수 있게 만들어진 것을 볼 수 있다.

4. 시뮬레이션 분석

4.1 시뮬레이션 시나리오

본 연구에서 개발된 시스템을 검증하기 위해서 시뮬레이션을 수행하였다. 시뮬레이션 시나리오는 앞서 제시한 것과 같이 염곡동의 주유소를 출발점으로 하고 그 주변에 있는 어린이공원에 물품을 배달하기 위해서 사전에 설치된 드론 배송 스테이션을 도착점으로 설정하였다.

알고리즘 비교는 Original Grid A*와 모든 셀을 High Resolution으로 격자를 만든 High Resolution Grid A*, 레퍼런스 연구인 High & Low Resolution Grid 환경을 가지는 Flexible Grid A* 그리고 본 연구에서 제안하고 있는 Efficient Grid A*의 결과들을 비교하였다.

4.2 시뮬레이션 결과 비교

먼저 본 연구에서 제안하고 있는 Efficient Grid A* 의 경로 계획 결과는 <Figure 9>와 같이 나오는 것을 확인할 수 있다. 앞 절에서 만든 Multi Size Grid 환경에서 A* 경로 계획 알고리즘을 실행하여 찾은 경로를 나타내고 있다. 그래프 결과를 보면 장애물이 없는 환경에서는 기존의 격자에서 생성된 경로로 가다가 장애물 영역에 들어서면 Middle Resolution의 격자에서 경로가 탐색되고 장애물 근처에서는 High Resolution 격자에서 최적 경로가 탐색되는 것을 볼 수 있다.

각 환경의 성능 비교는 경로 계획 수행 시 소요되는 Computing Time과 이때 생성된 경로의 Path Distance를 비교하였다. Computing Time은 알고리즘의 계산양이 얼마나 많은지 알려주는 척도가 되고 Path Distance는 경로의 최적성을 알려주는 척도가 된다.

<Figure 10>은 각각의 알고리즘을 10회씩 수행하여 Computing Time과 Path Distance를 측정한 결과를 나타내고 있다. 먼저 본 연구에서 제안된 알고리즘인 Efficient Grid의 경우 10회 평균 계산 시간은 약 0.037초이고 이때 경로 길이는 약 913m 정도 측정되었다. Original Grid의 경우 생성된 경로의 길이가 약 920m로 가장 길게 나와서 비효율적인 경로가 생성된 것을 알 수 있고 계산 시간은 거의 0초에 가깝게 측정되었다. 반면 High-Resolution Grid의 경우 경로 길이가 약 900m로 최소로 측정되어 최적에 가까운 경로를 생성하지만 계산 시간이 약 0.986초로 측정되어 제안된 알고리즘이 26배 정도 빠른 것을 알 수 있다. 레퍼런스 연구인 Flexible Grid의 경우에는 제안된 Efficient Grid와 유사한 경로 길이가 측정되었으나 계산 시간은 약 0.18초로 측정되었으며 제안된 알고리즘이 5배 정도 빠른 것을 확인할 수 있다.

<Figure 11>은 각각의 알고리즘이 어떤 형태로 경로를 생성하는지 알 수 있다. Original Grid의 경우 격자의 Resolution이 50m이므로 이보다 작은 장애물의 경우 회피를 수행하지 못하는 것을 볼 수 있다. High-Resolution의 경우 전체 영역에서 최적 경로를 생성하기 때문에 장애물이 없는 영역에서도 대각선의 경로가 생성되는 것을 볼 수 있다.

<Figure 12>는 제안된 경로계획 알고리즘 결과의 3차원 형상을 나타낸 그림이다. Efficient Grid에 따라 생성된 경로를 보면 장애물 근처에서는 최적으로 회피를 수행하고 장애물이 없는 지역에서는 Low Resolution의 격자에서 Computing Cost를 절약하는 경로가 생성되는 것을 볼 수 있다.

5. 결 론

본 연구는 광역 도심 환경에서 드론 및 로봇 배송을 수행하기 위해 격자 기반의 경로 계획 알고리즘을 제안하였고 실시간성을 유지하고 장애물 회피의 최적성을 유지하기 위해서 Multi Size Grid 환경을 만들어 효율적인 경로 계획을 개발하였다.

제안된 연구를 수행하기 경로 생성이 필요한 영역에 장애물을 등록하였다. 등록된 장애물의 정보를 통해 Middle Resolution으로 격자를 나눌 영역과 High Resolution으로 격자를 나눌 영역을 구분하였다. 셀이 선택되면 고유한 인덱스를 부여하여 셀을 쪼개어 새로운 격자를 만드는데 기존의 node와 edge를 고려하여 충돌이 발생하지 않도록 알고리즘을 구성하였다.

개발된 알고리즘 성능을 분석하기 위해서 기존의 알고리즘과 함께 Computing Time과 경로 비용으로 판단할 수 있는 Path Distance 등을 비교 분석하였는데 계산 시간의 경우 High-Resolution Grid 보다 약 26배, Flexible Grid보다 약 5배 정도 성능이 개선된 것을 볼 수 있었다.

향후에는 제안된 알고리즘이 탑재된 GCS를 통해 실제 배송 현장에 적용하여 알고리즘 성능을 검증 및 개선할 것이며 드론의 고도 별 장애물까지 고려한 3차원 구조의 Multi Grid를 만들어서 3차원 경로 계획을 수행할 수 있도록 추가 연구를 진행하려고 한다. 또한 본 연구에서 개발한 Grid 분할법을 바탕으로 드론이나 로봇의 실시간 위치에 대한 Local Path Planning 분야에 적용시켜 연구를 확장해 나갈 예정이다.