오피스 빌딩 내 학습 기반 내비게이션을 위한 랜덤 2D 환경 생성 프레임워크

1. 서 론

이동식 로봇이 집, 공장, 사무실 등의 새로운 환경에서 작업을 진행하기 위해서는 실내 내비게이션이 필수적이다. 특히, 군사 작전을 진행할 경우 최근에는 인명 피해를 줄이기 위해 무인 로봇의 시가지 건물 침투 및 내비게이션을 진행하기 위한 연구^[1,2]가 활발하게 이루어지고 있다. 이러한 내비게이션은 주로 Simultaneous Localization And Mapping (SLAM) 알고리즘을 통해 이루어졌으나^[3,4], 최근에는 강화학습을 이용해 로봇의 실내 내비게이션을 학습해 더욱 효율적이고 새로운 환경에 쉽게 적응하는 알고리즘^[5,6]이 개발되고 있다.

이동식 로봇이 새로운 환경에서 작업을 수행하기 위해서는 다양한 환경에서 학습을 진행하는 것이 필수적이다. 충분히 다양한 실제 환경을 제공하는 것은 현실적으로 무리가 있기 때문에 이를 위해 다양한 시뮬레이션 환경을 제공하는 연구^[7,8]가 이루어지고 있다. 하지만 기존 연구는 2차원 미로 등 실제의 환경과는 동떨어진 강화학습만을 위한 환경을 개발하거나, 현실적이지 않은 단순한 구조의 건물 환경을 생성하는 경우가 많다.

최근에는 현실적인 건물 도면을 생성하는 연구들^[9,10]이 제안되었다. 하지만, 이러한 연구들은 도면 이미지 자체를 생성하는 것에 초점을 두고 있기 때문에, 해당 도면 이미지에서 각 픽셀이 실제로 건물의 어떤 부분(방, 복도, 문, 벽 등)에 해당하는 지에 대한 정보가 명시적으로 주어져 있지 않다. 이러한 경우에는 생성된 환경 내에서 에이전트와 벽과의 충돌 및 에이전트의 시야 계산 등 강화학습에 필요한 에이전트와 환경간 상호 작용을 계산하기 어렵기 때문에 해당 데이터를 이용하여 사무실 내비게이션 알고리즘을 학습하기에 적합하지 않다.

본 연구에서는 이동식 로봇의 실내 내비게이션 학습을 위해 상호 작용이 가능한 다양한 2차원 사무실 환경을 생성하는 알고리즘을 제안한다. 이 알고리즘은 복도의 너비, 방 크기, 건물 출입구 및 방 출입구의 위치 등을 사용자가 지정한 범위 내에서 랜덤으로 결정하기 때문에 사용자가 원하는 다양한 도면의 생성이 가능하다. 또한, 본 연구에서는 어떠한 관측자가 건물 내부를 탐색하였다고 가정할 때 부분적으로 관측된 건물 도면을 생성하는 알고리즘을 제안한다. 이 알고리즘은 건물 도면으로부터 모서리 및 탐색 경로를 설정하는 부분과, 현재 위치로부터 관측 가능한 건물 정보 영역을 설정하는 부분으로 이루어져 있다. 결과적으로 생성된 부분 관측 도면과 전체 도면을 이용하여, 부분 관측 도면으로부터 완전 도면을 예측하는 지도 학습의 데이터셋 생성에 활용될 수 있다.

2. 랜덤 전체 지도 생성 알고리즘

사무실 건물 환경의 실내 탐색 정책을 머신 러닝 기법을 통해 학습하기 위해서는 다양한 2차원 지도 데이터셋이 필요하다. 이러한 지도 데이터는 에이전트와의 상호작용을 가능하게 만드는 건물 외벽, 복도, 방 및 문 등의 정보가 포함되어야 한다. 2장에서는 몇 가지 파라미터를 입력 값으로 받아 위의 정보들을 포함하는 다양한 무작위 지도 데이터를 생성하는 알고리즘을 제안한다. 아래의 [Fig. 1]은 본 챕터에서 제시하는 알고리즘을 실행한 결과로 생성된 예시 지도 데이터이다. 이 그림에서 건물 외부 공간, 복도, 벽, 방, 문을 각각 검은 색, 파란 색, 빨간 색, 노란 색, 초록색으로 표시하였으며, 이 논문 전반에 걸쳐 이 색상표기법을 유지할 것이다.

[Fig. 1]

An example of full indoor map; walls, doors, rooms, corridors, outdoor space are represented with red, green, yellow, blue and black color, respectively

본 지도 생성 알고리즘의 특징 중 하나는 건물의 변과 코너라는 개념을 이용하여 도면을 생성하는 것이다. 여기서 건물의 변이란 [Fig. 2]의 상단과 좌하단에서 푸른 색으로 표시한 직사각형 형태의 영역을 의미하며, [Fig. 3]과 같이 복도와 방으로 분할될 공간을 의미한다. 코너란 두 변이 이루는 교집합이 되는 공간을 의미한다.

[Fig. 2]

Examples of edges and corners of the building; 5 edges (top) come together to form 6 corners (dark blue area of left bottom figure), creating 日-shaped building (right bottom)

이러한 접근법을 사용한 이유는, 후술할 변과 코너로부터 방, 복도, 문을 생성하는 알고리즘을 이용하면 건물의 변과 코너의 위치를 지정함으로써 다양한 형태의 건물들의 도면을 생성하는 것이 용이해지기 때문이다. 예를 들어, [Fig. 2]의 상단과 좌하단처럼 다섯 개의 변과 여섯 개의 코너를 日자 형태로 배치한 후, 이 장에서 제안하는 알고리즘을 이용하면 최종적으로 우하단의 지도 데이터가 생성된다.

하나의 변에 대해 [Fig. 3]과 같이 복도와 방들이 배치될 수 있는데, 방이 존재하는 영역이 없거나, 한 쪽에만 있거나, 양 쪽에 모두 존재할 수 있다. 이는 사용자가 원하는 임의의 확률 카테고리 분포 p_rs로부터 샘플링하여 하나의 형태를 선택한다. 또한, 생성된 방 영역의 너비 역시 사용자가 원하는 임의의 분포 p_rw로부터 샘플링한다. 복도의 너비는 변의 너비로부터 양 쪽 방 영역의 너비를 뺀 값이 된다.

[Fig. 3]

Four types of building edges; (left top) no room space, (right top) one room space on the top side, (left bottom) one room space on the bottom side and (right bottom) two room space on the both sides

이제 두 변이 만나 코너를 이룬 상황을 가정하자. 이 경우, 각 변에서 미리 설정한 복도 및 방 영역이 코너 영역에서 [Fig. 4]의 좌측과 같이 서로 침범하게 된다. 따라서 복도와 방 영역의 재조정이 필요한데, [Fig. 4]에서 제시하는 규칙을 따라 각 코너 형태에 따라 방이 존재하는 영역의 길이를 줄여 복도 영역 및 방 영역을 재설정한다.

[Fig. 4]

Methods to adjust room space and corridors in each corner

이렇게 재설정한 방 영역을 원하는 방의 길이 w_desired에 가깝도록 분할하여 최종적으로 방을 생성한다. 방을 분할하는 과정은 다음과 같다. 방 영역의 길이 L_rs를 방의 길이 w_desired로 나눈 몫 $$ N_{room }=\left[\frac{L_{rs}}{w_{desired }}\right]$$을 방의 개수로 정의하고, 이를 이용하여 보정된 방의 길이 $$ w^{\mathrm{*}}=L_{rs}/\left[\frac{L_{rs}}{w_{desired }}\right]$$를 구한다. 그 후, N_room-1개의 방에 대해, 각 i번째 방의 길이에 균등 분포의 노이즈 $$ w_i^{\text{'}}\in \left[-w_{noise },w_{noise }\right]$$를 더하여 방의 길이에 무작위성을 부여한다. 마지막 방의 길이의 경우 $$ L_{rs}-\sum _{i=1}^{N_{room }-1}\left(w^{\mathrm{*}}+w_i^{\text{'}}\right)$$로 계산한다. 문의 경우, 복도와 방이 만나는 지점에서 랜덤한 위치에 생성한다. [Fig. 5]는 [Fig. 4]의 우측 상단처럼 놓인 길이가 0.8인 두 변으로부터 방 영역을 각각 w_desired = 0.1, w_noise = 0.03과 w_desired = 0.2, w_noise = 0.03로 설정했을 때 나오는 방 분할의 결과이다.

[Fig. 5]

Rooms are generated by dividing the room space and doors are created where the rooms and the corridors are met; all lengths of edges are 0.8, (left) wdesired=0.1, wnoise=0.03, (right) wdesired=0.25, wnoise=0.03

이제 상술한 알고리즘들을 이용하면 임의의 건물 도면을 생성할 수 있다. i번째 변의 위치, 너비 및 길이에 대한 분포를 각각 $$ p_{ep}^i,p_{el}^i,p_{ew}^i$$라고 하자. 이들은 원하는 건물 개형에 따라 서로 종속되어 있는 분포일 수 있음에 유의하라. 예를 들어 [Fig. 5]와 같은 건물의 경우 두 변의 좌하단 모서리가 일치해야 한다는 제약조건이 존재한다. 또한, 상술했던 변수들 p_rs, p_rw, w_desired, w_noise에 대해 i번째 변에 해당하는 경우 위 첨자 i를 표기하자. 마지막으로, 건물을 구성하는 변의 개수를 N_edge로 표기하자. 이제 랜덤 전체 지도 생성 알고리즘을 알고리듬 형태로 표현하면 다음과 같다 [Algorithm 1].

[Algorithm 1]

Algorithm to generate random full map

3. 부분 관측 지도 생성 알고리즘

효율적인 실내 탐색을 위해서, 부분적으로 관측된 지도로부터 전체 지도를 예측하는 과정이 필요할 수 있다. 이러한 예측을 머신러닝의 지도학습 기법을 이용하여 해결하려고 할 경우, 전체 지도와 부분 관측 지도가 쌍을 이루는 데이터셋이 필요하다.

이 장에서는 건물 도면 이미지로부터 부분 관측 지도를 생성하는 알고리즘에 대해 설명한다. 해당 알고리즘은 크게 두 부분으로 나누어져 있는데, 하나는 주어진 건물 도면에 대해 건물 복도를 탐색하는 경로를 생성하는 알고리즘이고, 다른 하나는 관찰자가 이러한 탐색 경로를 따라간다고 가정할 때 관측하게 되는 지도 영역을 판별하는 알고리즘이다. 이 알고리즘과 2장에서 제안한 알고리즘을 함께 이용하면 다양한 랜덤 생성된 전체 지도들과 부분 관측 지도들의 쌍으로 이루어진 데이터셋을 생성할 수 있다.

3.1 건물 탐색 경로 생성 알고리즘

이 장에서 제안하는 알고리즘의 목표는 건물 도면 데이터가 주어져 있을 때 건물의 입구에서 출발하여 복도 영역을 탐색하고 입구로 돌아오는 경로를 생성하는 것이다. 이러한 경로는 흔히 미로 찾기의 해법으로 알려진 우수법/좌수법으로 구현하거나, 혹은 건물에 특징이 되는 여러 경유점을 찾은 후 이들을 랜덤으로 이어서 탐색하는 경로를 고려할 수 있다. 이 장에서는 우수법/좌수법으로 대표되는 개략 탐색 경로 생성 알고리즘과, 복도의 코너를 랜덤으로 방문한 후 돌아오는 랜덤 탐색 경로 생성 알고리즘을 제안한다.

이 알고리즘은 벽, 문, 복도의 픽셀이 구분되어 있는 지도 이미지를 대상으로 작동한다. 2장에서 생성한 지도 이미지 데이터는 이를 충족하며, 본 연구에서 생성한 지도 데이터가 아니더라도 이와 같이 구분되어 있는 임의의 지도 데이터를 대상으로 알고리즘이 작동할 수 있다.

우선 복도 영역을 탐색하는 경로의 경유점을 찾기 위해서, 지도 이미지로부터 [Fig. 6]에서 하얀 색으로 표시한 부분과 같이 복도에 노출되어 있는 벽의 모서리에 해당하는 부분들의 위치 및 형태를 추출해야 한다. 벽의 모서리에는 총 8가지 형태가 있는데, 이는 [Fig. 7]과 같다. 그림에서 파란색 픽셀은 복도를, 빨간색 픽셀은 벽을 의미하며, 하얀 원은 코너에 해당하는 픽셀을 나타낸다.

[Fig. 6]

Corners of the walls exposed to the corridors are represented with white color

[Fig. 7]

8 types of wall corners; Blue pixels represent corridor, red pixels represent walls, and pixels with white circles represent pixels that are the corners of the walls

편의상 [Fig. 7]의 위쪽 행의 모서리들을 열린 모서리, 아래쪽 행의 모서리들을 닫힌 모서리라 부르자. 열린 모서리의 경우, 모서리 픽셀은 다음과 같은 성질을 만족한다; 1. 해당 픽셀 및 인접한 상하좌우 방향의 픽셀이 모두 복도 픽셀이며; 2. 인접한 대각 방향에 위치한 어느 한 픽셀은 벽 혹은 문 픽셀에 해당한다. 이미지의 모든 픽셀에 대해 이러한 성질을 만족하는지 체크함으로써 열린 모서리 픽셀을 전부 찾을 수 있으며, 2번 성질에서 언급한 벽(문) 픽셀이 위치한 대각선 방향을 통해 모서리의 방향을 알 수 있다.

닫힌 모서리 픽셀의 경우, 다음과 같은 성질을 만족한다; 1. 해당 픽셀은 복도 픽셀이며, 2. 상하좌우 픽셀 중 마주보는 픽셀은 서로 다른 픽셀이며, 두 픽셀은 복도 픽셀, 다른 두 픽셀은 벽(문) 픽셀이다. 마찬가지로 모든 이미지에 대해 위 성질을 만족하는지 확인함으로써 닫힌 모서리에 해당하는 모든 픽셀을 찾을 수 있으며, 2번 성질에서 복도 픽셀이 존재하는 두 방향을 통해 4가지 형태의 닫힌 모서리 중 어떠한 모서리에 해당하는지 알 수 있다.

이와 같이 발견한 모서리들을 이용하면 우수법/좌수법을 이용하여 건물의 출입구에서 출발하여 다시 돌아오는 개략 탐색 경로의 경유점 및 순서를 생성할 수 있다. 우선, 건물 출입구에서 출발하여 벽에 인접한 복도 픽셀을 따라 모서리 픽셀이 등장할 때까지 이동하고, 미리 식별해둔 모서리의 방향을 따라 회전한 후 다음 모서리가 등장할 때까지 이동한다. 이를 건물 출입구가 등장할 때까지 반복하여 찾은 모서리 픽셀들이 경유점이 되며, 각 모서리 픽셀이 발견된 순서가 경유점의 순서가 된다. 경유점 생성 예시는 [Fig. 8]에서 볼 수 있다. 최종적으로 생성된 경유점들을 이용하여, 벽을 장애물로 간주하고 A* 알고리즘^[11]을 이용하여 건물 개략 탐색 경로를 생성한다. 우수법/좌수법의 선택은 1/2 확률의 랜덤 샘플을 통해 결정한다.

[Fig. 8]

Example of waypoint creation; white arrows indicate the navigation route, and black in-circled numbers indicate the order of waypoints

개략 탐색 경로 외에도, 부분 관측 지도의 다양성을 높이기 위해 건물 내부 복도의 임의의 지점을 탐색하는 랜덤 탐색 경로를 추가로 생성한다. 랜덤 탐색 경로는 복도 픽셀 중 임의의 픽셀들을 균일 분포로 샘플링하여 경유점으로 지정한 후, 이들을 A* 알고리즘을 이용하여 연결한 경로를 의미한다.

본 논문에서는 각 지도별로 개략 탐색 경로와 랜덤 탐색 경로를 1:1의 비율로 생성하였으며, 개략 탐색 경로의 경우 경로의 진행 비율을 0.0 ~ 1.0 사이에서 균일 분포로 랜덤하게 선택하고, 랜덤 탐색 경로의 경우 경유점의 개수는 1~10개 중 균일 분포로 랜덤하게 정한다.

4. 지도 생성 결과 예시

이 장에서는 본 논문에서 제안한 알고리즘의 산출물 예시를 보여준다. [Fig. 9]는 2장의 전체 지도 생성 알고리즘의 결과이다. 생성에 사용한 건물 개형의 모양은 ㅡ, ㄴ, ㄷ, ㅁ, H, 日, ㅒ의 7가지이며, 각 개형에 맞게 복도의 크기, 위치, 코너의 형태 및 분포를 지정해주었다. [Fig. 10]은 해당 알고리즘이 동일한 구조가 반복되는 창고와 같은 환경을 생성할 수 있음을 보이기 위하여, 모든 파라미터의 분포를 상수로 고정 한 후 생성한 지도 데이터의 예시이다. [Fig. 11]은 3장의 부분 관측 지도 생성 결과 예시이다. 좌측의 ㅡ, ㄴ, ㄷ, ㅁ 형태의 전체 지도에 대해, 우측의 부분 관측 지도는 순서대로 왼쪽 출입구로부터 오른쪽으로 진입하여 직진한 후, 상단 출입구로 진입하여 좌회전을 한 후, 우상단의 출입구로 진입하여 두 번의 좌회전을 한 후 그리고 상단의 출입구로 진입하여 좌회전 이후 우회전을 한 후의 상태에서 부분적으로 관측된 지도를 묘사하였다. 해당 부분 관측 지도들은 3.1.장의 좌수법 형태의 개략 탐색 방법을 통해 생성된 경로를 이용하였고, 관측 영역의 범위는 3.2.장에서 소개한 알고리즘을 이용하여 계산하였다. 관측되지 않은 영역은 회색 픽셀로 표시하였다.

[Fig. 9]

Examples of generated various full map images

[Fig. 10]

An example of a warehouse-type map created using an overall map data generation algorithm

[Fig. 11]

Examples of generated partially observed map images; the left figures are the original the buildings being searched, and the right figures are partially observed maps obtained by searching along the randomly generated paths. The generated paths are represented with white arrows and unobserved areas are shown in gray pixels

5. 결론 및 향후 계획

본 논문에서는 오피스 건물 내부 탐색을 위한 상호작용이 가능한 지도 데이터 생성을 위한 알고리즘을 제안한다. 도면 이미지를 생성하는 기존 연구와 달리 본 연구에서 생성한 지도 데이터는 각 픽셀이 어떠한 공간(방, 복도, 벽 등)을 나타내는지 정보를 포함하고 있기에 상호작용에 용이하다. 또한, 이와 같이 생성한 지도가 상호작용이 가능하다는 이점을 이용하여 부분 탐색 지도 데이터를 생성하는 알고리즘을 제안한다. 이러한 전체-부분 지도 쌍으로 이루어진 데이터셋은 부분 관측된 지도로부터 건물 전체 형상을 예측하는 지도 학습 등 여러 러닝 기반 방법에 이용될 수 있다.

향후 본 논문의 데이터셋을 이용하여 부분 관측된 지도로부터 관측되지 않은 영역의 불확실성을 예측하는 모듈과, 이러한 모듈을 활용한 전체 지도 탐색 알고리즘을 연구할 것이다.

Acknowledgments

This work was supported by Korea Research Institute for defense Technology planning and advancement (KRIT) grant funded by the Korea government (DAPA (Defense Acquisition Program Administration)) since 2022 (No.KRIT-CT-22-006-005, Control technology for collective operation of military ultra-small ground robots (Contribution rate : 100%)).

References

• J. Han, D. Kim, Y.-B. Ko, and D. Kwon, “Centralized TDMA slot assignment scheme based on traffic direction for QoS guarantee in unmanned robot systems,” The Journal of Korean Institute of Communications and Information Sciences, vol. 41, no. 5, pp. 555564, May, 2016. [https://doi.org/10.7840/kics.2016.41.5.555]
• J. E. Kye, “Trends and acquisition strategies on defense unmanned robot core technology,” Electronics and Telecommunications Trends, vol. 29, no. 3, pp. 118-130, Jun., 2014. [https://doi.org/10.22648/ETRI.2014.J.290313]
• X. Zhang, B. Li, S. L. Joseph, J. Xiao, Y. Sun, Y. Tian, P. J. Muñoz, and C. Yi, “A slam based semantic indoor navigation system for visually impaired users,” 2015 IEEE International Conference on Systems, Man, and Cybernetics, Hong Kong, China, pp. 1458-1463, 2015. [https://doi.org/10.1109/SMC.2015.258]
• Q. Zou, Q. Sun, L. Chen, B. Nie, and Q. Li, “A comparative analysis of LiDAR SLAM-based indoor navigation for autonomous vehicles,” IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 7, pp. 6907-6921, Jul., 2021. [https://doi.org/10.1109/TITS.2021.3063477]
• M.-Y. Choi, W. Shin, M. Kim, H.-S. Park, Y. You, M. Lee, and H. Oh, “Collective navigation through a narrow gap for a swarm of UAVs using curriculum-based deep reinforcement learning,” The Journal of Korea Robotics Society, vol. 19, no. 1, pp. 117-129, Feb., 2024. [https://doi.org/10.7746/jkros.2024.19.1.117]
• Y. Zhu, R. Mottaghi, E. Kolve, J. J. Lim, A. Gupta, L. Fei-Fei, and A. Farhadi, “Target-driven visual navigation in indoor scenes using deep reinforcement learning,” 2017 IEEE international conference on robotics and automation (ICRA), Singapore, pp. 3357-3364, 2017. [https://doi.org/10.1109/ICRA.2017.7989381]
• S. Oh, J.-H. Park, H.-Y. Choi, and S.-H. Ok, “Development of simulation environment for a ROSbased mobile robot reinforcement learning,” KIIT Conference, pp. 533-536, 2022, [Online], https://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE11183874, .
• H. J. Kim, S.-M. Kang, and D. Kim, “Development of autonomous driving algorithm for robots in high-rise buildings using Gazebo simulator,” Journal of Institute of Control, Robotics and Systems, vol. 28, no. 8, pp. 758767, Aug., 2022. [https://doi.org/10.5302/J.ICROS.2022.22.0093]
• S.-H. Choi and J.-K. Lee, “Generative AI for automated urban housing floor plan generation,” Korean Journal of Computational Design and Engineering, vol. 28, no. 4, pp. 514-523, Dec., 2023. [https://doi.org/10.7315/CDE.2023.514]
• J. Shim, H. Kim, J. Lee, and E. Hwang, “Building plan generation technique using Pix2Pix,” Korea Information Science Society Conference, pp. 638640, 2021, [Online], https://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE11035802, .
• P. E. Hart, J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100107, Jul., 1968. [https://doi.org/10.1109/TSSC.1968.300136]
• S. Suzuki and A. Keiichi, “Topological structural analysis of digitized binary images by border following,” Computer vision, graphics, and image processing, vol. 30, no. 1, pp. 32-46, Apr., 1985. [https://doi.org/10.1016/0734189X(85)90016-7]
• T. Asano, “Efficient algorithm for finding the visibility polygon for a polygonal region with holes,” Transactions of the Institute of Electronics and Communication Engineers of Japan. Section E, vol. 68, no. 9, pp. 557-559, Sept., 1985. [https://doi.org/10.24517/00062806]