[ ARTICLE ]

Journal of Korea Robotics Society - Vol. 9, No. 2, pp.104-110

ISSN: 1975-6291 (Print) 2287-3961 (Online)

Print publication date May 2014

Received 21 Jan 2014 Revised 12 Mar 2014 Accepted 2 Apr 2014

DOI: https://doi.org/10.7746/jkros.2014.9.2.104

표준화된 지도 데이터 표현방법을 이용한 위상지도와 격자지도의 병합

진희선¹ ; 유원필² ; 문형필^†

1기계 공학, 성균관대학교, 한국 jinheeseon@gmail.com
2로봇/Congnitive 시스템 연구부, 한국 전자 통신 연구원, 한국 ywp@etri.re.kr

Merging of Topological Map and Grid Map using Standardized Map Data Representation

Hee-Seon Jin¹ ; Wonpil Yu² ; Hyungpil Moon^†

1Mechanical Engineering, Sungkyunkwan University, Korea jinheeseon@gmail.com
2Robot/Congnitive System Research Department, Electronics and Telecommunications Research Institute, Korea ywp@etri.re.kr

※This work was supported by the R&D program of the Ministry of Trade, Industry & Energy, Republic of Korea and the Korea Evaluation Institute of Industrial Technology (KEIT) [The Development of Low-cost Autonomous Navigation Systems for a Robot Vehicle in Urban Environment, 10035354]
†Corresponding author: Mechanical Engineering, Sungkyunkwan University, Cheoncheon-Dong, Jangan-Gu, Suwon, Korea ( hyungpil@me.skku.ac.kr)

Abstract

Mapping is a fundamental element for robotic services. There are available many types of map data representation such as grid map, metric map, topology map, etc. As more robots are deployed for services, more chances of exchanging map data among the robots emerge and standardization of map data representation (MDR) becomes more valuable. Currently, activities in developing MDR standard are underway in IEEE Robotics and Automation Society. The MDR standard is for a common representation and encoding of the two-dimensional map data used for navigation by mobile robots. The standard focuses on interchange of map data among components and systems, particularly those that may be supplied by different vendors. This paper aims to introduce MDR standard and its application to map merging. We have applied the basic structure of the MDR standard to a grid map and Voronoi graph as a kind of topology map and performed map merging between two different maps. Simulation results show that the proposed MDR is suitable for map data exchange among robots

Keywords:

Map Data Representation, Topological Map, Grid Map, Map Merging

1. 서 론

이동 로봇의 주행 또는 자신의 위치를 알기 위해서 이 동 로봇의 지도 작성은 필수적인 부분이 되었다. 예를 들 어 실내에서 주행하는 로봇의 경우 건물의 도면을 로봇이 알고 있더라도 실제 로봇이 접하는 환경은 다를 수 있다. 건물 내부를 구성하는 요소인 가구, 책상, 의자 등 로봇의 이동 및 작업에 필요한 세세한 정보는 설계도만으로는 알 수 없으며 수시로 위치가 바뀔 수 있다. 또한 상황에 따라 서는 미리 정확한 지도를 제공할 수 없는 경우도 있다. 때 문에 로봇이 주위환경에 대해 스스로 인식하고 지도를 생 성 할 수 있어야 한다.

이동 로봇의 지도들은 일반적으로 격자지도(grid map)^[1] 와 위상지도(topological map)^[2]등의 종류가 있다. 다양한 이 동 로봇들이 각자의 지도를 생성하고 주행을 한다. 하지만 현재 로봇 지도에 대한 표준이 없으므로 다른 이동 로봇 간에 생성한 지도의 정보교환이 어려울 수 있다. 그리고 다른 형식의 격자지도와 위상지도를 가지고 로봇간에 주 행을 하려면 데이터 형식이 다르므로 사용하는 로봇의 데 이터 형식에 맞게 해주어야 하는 단점이 있다.

이러한 문제를 해결하기 위해서 통일된 데이터 형식을 가질 수 있도록 표준화 작업이 필요하다. 다양한 분야에서 표준화 작업이 활발하게 진행 중인데, 그 중 하나로 OGC 를 예로 들 수 있다. OGC(Open Geospatial Consortium)는 비 영리 국제기구로써 공간정보 기술표준을 연구 및 제정을 목적으로 만들어졌으며 글로벌 IT기업과 각국 정부기관 및 시민단체가 회원으로 참여하고 있다. OGC는 여러 분야 에서 표준을 진행 중인데 대표적인 예로 CityGML^[14,15], IndoorGML^[16,17] 등 있다. IndoorGML 이란 실내공간정보에 대한 표현방법에 대한 표준으로, 2014년도 상반기에 표준 초안이 완성될 예정이다. CityGML란 도시 및 지형에 관한 모델을 위한 표준화 작업이다. 하지만 위와 같이 표준화 작업이 활발히 이뤄지고 있음에도 불구하고 로봇지도에 필요한 표준은 없다. 현재 빠르고 다양하게 로봇들이 발전 되고 있는데 다양한 로봇들 간에 정보교환 및 효율적 활 용을 위해서는 로봇 정보에 대한 표준화가 필수적이다. 이 러한 필요성에 의해 로봇주행용 지도에 대한 IEEE 표준안 을 작성하고 있다. 표준의 목적은 격자지도 및 위상지도 등 다양한 로봇지도 데이터에 대한 구체적인 형식을 정의 해주며, 이러한 형식을 준수 함으로써 다양한 로봇들 간의 데이터 교환이 쉽게 이루어 질 수 있도록 한다.

본 논문에서는 표준화된 지도 데이터 방법의 상호 호환 성을 보이기 위해 표준 데이터 기반으로 위상지도와 격자 지도를 생성하였고, 위상지도끼리의 병합, 그리고 위상지 도와 격자지도 간의 병합으로 데이터가 서로 공유가 가능 한지 보였다. 로봇 시뮬레이터 중 하나인 RoboticsLab®를 사용하여 실험을 진행 하였으며, GVG(Generalized Voronoi Graph)^[3]를 이용한 위상지도와 격자지도를 생성하였다.

2장에서는 UML과 표준화된 지도 데이터 표현방법에 대 해 소개하며, 3장에서는 위상지도와 격자지도의 작성을 보 여준다. 4장에서는 위상지도간의 병합 그리고 위상지도와 격자지도 간의 병합 방법 및 결과물을 제시한다.

2. 표준화된 지도 데이터 표현방법

먼저, UML이란 무엇이며 UML을 사용해야 하는 이유에 대해서 설명하고, 표준화된 지도 데이터 표현 방법과 이로 인해 얻을 수 있는 이익에 대해 설명한다.

2.1. UML

UML이란 Unified Modeling Language^[4] 의 약자로 소프트 웨어를 코딩 하기에 앞서 표준화 되고 이해되기 쉬운 방 법으로 모델링 하여 다른 사람들과 효율적으로 의사소통 을 할 수 있는 장점이 있으며 여러 표준화 문서에서는 이 미 많이 사용되고 있다. 또한 표준화된 지도 데이터 방법 에 대한 정의를 UML을 사용하여 표현하였다.

2.2. 표준화된 지도 데이터 표현방법

UML을 사용한 표준화된 지도 데이터 표현방법은 다양 한 사람들과 의사소통이 가능하며 다양한 로봇간에 지도 를 만들기 위한 데이터를 공통적으로 표현할 수 있다. 그 리고 다양한 로봇들이 표준화된 지도 데이터 표현방법을 준수 한다면 로봇간의 데이터 교환은 쉽게 이루어 질 수 있는 이점이 있다.

Fig. 1은 표준화된 지도 데이터의 최상위 계층인 Local map에 대한 UML 모델이다. Local map은 여러 가지 지도를 생성할 수 있는 최상위 계층이며 모든 지도들이 가져야 할 정보인 MapSize, Offset, LocalMapID, LocalMapType, CoordinateInfo 가 지정되어 있다. MapSize는 지도의 크기를 의미하며, Offset은 LocalMap이 global 좌표계에 대해 틀어 진 정도를 나타내고, LocalMapID는 맵을 구별할 수 있는 숫자이다. 그리고 LocalMapType은 각 지도의 종류를 의미 하는데, 이 지도의 종류는 GridMap 은 ‘1’ GeometricMap 은 ‘2’ TopologicalMap 은 ‘3’ 으로 정해져 있다. 마지막으로 CoordinateInfo는 LocalMap의 좌표계를 의미하는데, 이 좌 표계에 대한 정보는 ISO19115 문서를 참조하였다. ISO19115 “Geographic information – Metadata” 란 지리 정보 에 관련된 데이터 와 서비스를 설명하기 위한 표준 문서 이다^[18].

이러한 정보를 가지고 있는 Local Map class 를 상속받아 GridMap , GeometricMap , TopologicalMap 등을 생성하는데, 여기서 상속(Inheritance)란 객체(object)의 새로운 클래스 (class)를 정의할 때 상위 또는 부모 클래스의 데이터 구조 와 메소드(method)를 그대로 이어받을 수 있는 개념이다. 즉, LocalMap을 확장해서 사용을 하며 격자지도, 위상지도, 지오메트릭 지도 등의 다형성을 부여할 수 있다.

Fig. 2는 UML은 위상지도에 관한 정의이다. 위상지도는 노드와 엣지의 집합으로 이루어 져 있으며 노드는 NodeID 와 NodePosition 그리고 NodePrpperties를 가지고 있다. 엣지 는 EdgeID와 EdgeProperties를 가지고 있다. 여기서 NodePrpperties 와 EdgeProperties 는 사용자 정의에 의해 Name, Value, Type 그리고 Description 을 가지는 어떠한 형 태로 정의될 수 있다. Node 는 ConnectedEdges로 연결되며, Edge는 HeadNode와 TailNode 로 서로 연관관계를 가지고 있다.

3. 맵 데이터 생성

본 논문에서는 표준화 된 지도 데이터를 기반으로 지도 를 작성하였다. 지도 작성은 시뮬레이터인 RoboticsLab® 을 이용하였고 주행 환경은 40m×40m의 크기를 가지는 가상의 실내환경을 생성하여 실험을 진행하였다. 3개의 다 른 모바일 로봇이 다른 영역을 주행하여 각각 의 지도를 생성하였다.

3.1. 위상지도 작성

위상 지도는 주위 환경에서 특징적인 정보만 저장하게 되므로 매우 적은 메모리를 사용하여 지도를 표현할 수 있으며, 경로 탐색도 빠르게 처리가 가능하다. 위상지도 중 대표적인 형태로 Voronoi Graph를 이용한 위상지도가 있다. Choset과 Burdick은 GVG(Generalized Voronoi Graph)^[7] 기반의 위상지도 작성 방법을 제안하였으며, 본 연구에서 는 센서기반 GVG 작성기법^{[10, 11]}을 이용하여 표준화 된 지 도 데이터를 기반으로 위상지도를 작성하였다.

GVG는 장애물과의 거리가 동일한 점들의 집합으로 노 드와 엣지로 지도를 구성한다. 로봇이 주행하며 지도를 작 성하기 위해서 레이저 센서에서 측정된 거리 정보를 사용 하며, 로봇이 항상 엣지를 따라가도록 한다. Fig. 3 에서 볼 수 있듯이, 지도 작성 알고리즘은 크게 3부분으로 이루어 진다. 먼저 레이저 센서의 거리 정보 및 로봇의 오도미터 로 현재 위치를 계산한다. 다음으로는 센서 정보를 바탕으 로 장애물들의 분할작업을 수행한다. 연속적인 센서 값은 하나의 장애물로 처리해야 하기 때문에 분할작업을 수행 한 후 장애물들과의 최소 거리를 계산하여 엣지 인지 판 단하고 엣지 위를 따라서 주행할 수 있도록 방향을 설정 한다. 주행 중 장애물의 최소 거리가 3개 이상 같은 지점 을 만나게 되면 노드로 판단하고, 지도에 노드를 추가한다.

3.2. 격자지도 작성

격자지도는 Moravec과 Elfes 에 의해 제안되었으며^[8][9], 로봇의 위치를 정확히 알고 있다는 가정하에 불확실한 센서 데이터를 이용해서 지도를 작성하는 방법이다. 주위 환경을 여러 개의 2차원 격자로 나누고, 거리센서 정보를 이용하여 각 격자의 상태를 지속적으로 업데이트 하여 지도를 작성한다. 위상지도에 비해 상대적으로 구현이 쉽지만 정밀도를 높이거나 격자의 크기를 늘릴 경우 메모리를 많이 차지하는 단점이 있으며 경로탐색에 많은 비용이 드는 단점이 있다.

격자지도에서 점유 상태는 0과 1의 사이 값을 가지는 확률로 나타내며, 상태가 1 인 경우 장애물이 존재하고 0인경우 빈 공간으로 나타낼 수 있다. 또한 아직 탐색하지 않은 공간은 0.5로 표현 하였다. 로그오즈를 사용하면 복잡한 확률 계산이 오즈의 합으로 단순하게 표현 될 수 있기 때문에^[12,13], 실제 지도 작성은 로그오즈를 사용하여 데이터를 업데이트 하였다.

Fig. 4는 RoboticsLab®을 이용하여 만든 주행 환경을 보여주며 Fig. 5는 각각 다른 세 개의 로봇이 생성한 위상지 도 이고 각 색깔 별로 다른 로봇을 의미한다. Fig. 6은 같은 주행환경에서 생성한 격자지도다. 녹색은 장애물이 없는 구간, 빨간색 구간은 장애물이 있는 구간, 파란색 구간은 로봇이 탐색하지 않은 구간으로 표현된다. 격자지도내 주황색선은 로봇의 경로를 나타낸다. 본 실험에서는 로봇이 Voronoi 경로로 이동을 하며 위상지도와 격자지도를 작성하였다.

4. Map merging

표준화된 지도 데이터의 목적은 로봇간의 상호 교환성 이 되도록 하는 것에 있다. 이는 다른 지도들의 병합을 통 해서 지도 정보 교환이 가능함을 보일 수 있다. 현재까지 의 지도 병합에 관한 연구들은 격자지도간의 병합^[5], 위상 지도간의 병합^[6] 이 있었다. 또한, 격자지도 정보를 기반으 로 격자의 프론티러를 이용하여 노드를 지정하고 노드간 연결 상태를 이용하여 위상지도를 작성하는 방법^[19], 가정 집의 실내 공간을 분할하는 문지방의 위치를 이용하여 시 맨틱 지도와 격자지도를 계층화 하는 방법^[20]이 제안되었 다. 하지만 이들 방법은 정확한 표준에 기반한 방법이 아 니기 때문에 각 지도가 가지고 있는 정보 및 구조가 달라 제 3자가 지도 병합을 구현하거나 사용하기엔 어려움이 있을 수 있다. 본 논문에서는 표준화된 지도 데이터에 기 반하여 지도 병합 결과를 보였다. Fig. 6.

지도 병합 방법은 각각의 지도들이 최상위 계층인 Local Map을 상속받으면서 다른 LocalMapID와 LocalMapType을 가지면서 생성이 되고, 상속을 받았기 때문에 각각의 다른 지도들은 공동의 부모인 Local Map class를 가지게 된다. 각 각의 지도들은 LocalMap에서 coordinateInfo 중 하나인 GPS 좌표를 이용하도록 하였다.

각각의 지도는 GPS 정보를 이용하여 같은 영역의 노드 및 셀을 검은 색 선으로 연결하여 다른 여러 가지 지도를 병합하였다. 즉, 최상위 계층의 GPS 좌표를 사용함으로써 다른 종류의 지도들의 데이터 교환이 효율적으로 되며, 공 통적인 데이터를 검색함으로써 하나의 지도로 병합을 할 수 있었다. Fig. 7은 위상지도 간의 병합 결과를 보여주며 Fig. 8 위상지도와 격자지도 간의 병합 결과를 보여준다. 제안된 MDR은 같은 종류의 지도정보를 로봇간 공유할 수 있을 뿐만 아니라 다른 종류의 지도 정보도 상호 교환 가 능한 형태임을 알 수 있다.

5. 결 론

본 논문에서는 표준화된 지도 데이터에 대해 소개하고 이 데이터에 기반한 위상지도와 격자지도를 보였으며 각 각의 지도를 병합함으로써 이 표준화된 지도 데이터가 다 른 정보를 가지고 있는 지도간의 정보교환의 적합함을 보 였다. 추후 연구로 실제 로봇을 이용한 지도 작성 및 병합 된 지도를 이용한 경로생성 등의 연구가 필요하다.

REFERENCES

Elfes, A, “Using Occupancy Grids for Mobile Robot Perception and Navigation”, IEEE Computer, (1989), 22(6), p46-57. [https://doi.org/10.1109/2.30720]
Zwynsvoorde, D. V, Simeon, T, Alami, R, “Incremental topological modeling using local voronoilike graphs”, (2001), 2, Proc. of IEEE/RSJ Int. Con. On Intelligent Robots and Systems, p897-902.
Choset, H, Burdick, J, “Sensor-based exploration: the hierarchical generalized voronoi graph,”, Int. Journal of Robotics Research, (2000), 19(2), p96-125. [https://doi.org/10.1177/02783640022066770]
D’souza, D. F, Wills, A. C, “Objects, Components, and Frameworks with UML: The Catalysis Approach,”, (1998), Addison-Wesley Professional.
Birk, A, Carpin, S, "Merging Occupancy Grid Maps From Multiple Robots", Proceedings of the IEEE, (2006, July), 94(7), p1384-1397. [https://doi.org/10.1109/jproc.2006.876965]
Huang, W. H, Beevers, K. R, “Topological map merging,”, The International Journal of Robotics Research, (2005), 24(8), p601-613. [https://doi.org/10.1177/0278364905056348]
Choset, H, Konukseven, I, Burdick, J, “Mobile robot navigation: Issues in implementation the generalized voronoi graph in the plane”, Proc. of IEEE/MFI, (1996), p241-248. [https://doi.org/10.1109/mfi.1996.572184]
Moravec, H. P, “Sensor fusion in certainty grids for mobile robots,”, AI magazine, (1988), 9(2), p61-74. [https://doi.org/10.1007/978-3-642-74567-6_19]
Moravec, H. P, Elfes, A. E, “High resolution maps from wide angle sonar”, (1985), In Proceedings of IEEE International Conference on Robotics and Automation, p116-121. [https://doi.org/10.1109/robot.1985.1087316]
Shi, C, Wang, Y, Yang, J, “Online Topological Map Building and Qualitative Localization in Large-Scale Environment”, Robotics and Autonomous Systems, (2010), 58(5), p488-496. [https://doi.org/10.1016/j.robot.2010.01.009]
Choset, H, Nagatani, K, “Topological Simultaneous Localization and Mapping(SLAM): Toward Exact Localization without Explicit Localization,”, IEEE Tran. Robotics and Automation, (2001), 17(2), p125-137. [https://doi.org/10.1109/70.928558]
Yamauchi, B, Schultz, A, Adams, W, “Mobile Robot Exploration and Map-Building with Continuous Localizaton,”, (1998), 4, In Proceedings of IEEE International Conference on Robotics and Automation, p3715-3720. [https://doi.org/10.1109/robot.1998.681416]
Konolige, K, “Improved Occupancy Grids for Map Building,”, Autonomous Robots, (1997), 4(4), p351-367.
Kolbe, T.H, Gröger, G, Plümer, L, “CityGML: Interoperable Access to 3D City Models”, Geoinformation for Disaster Management, (2005), p883-899. [https://doi.org/10.1007/3-540-27468-5_63]
Kolbe, T. H, “Representing and Exchanging 3D City Models with CityGML,”, 3D Geo-Information Sciences Lecture Notes in Geoinformation and Cartography, (2009), p15-31. [https://doi.org/10.1007/978-3-540-87395-2_2]
Li, K.J, Lee, J, "Indoor spatial awareness initiative and standard for indoor spatial data", (2010), 18, Proceedings of IROS 2010 Workshop on Standardization for Service Robot.
Kim, Y.J, Kang, H. Y, Lee, J, "Development of Indoor Spatial Data Model Using CityGML ADE", Journal of Korea Spatial Information Society, (2013), XL-2/W2, p41-45. [https://doi.org/10.5194/isprsarchives-xl-2-w2-41-2013]
Wei, Y, Di, L, Zhao, B, Liao, G, Chen, A, "Transformation of HDF-EOS metadata from the ECS model to ISO 19115-based XML", Computers & Geosciences, (2007), 33, p238-247. [https://doi.org/10.1016/j.cageo.2006.06.006]
Ryu, H, Chung, W. K, “Local map-based exploration strategy for mobile robots”, Journal of Korea Robotics Society, (2013), 8(4), p256-265. [https://doi.org/10.7746/jkros.2013.8.4.256]
Park, J. T, Song, J. B, “Building of a hierarchical semantic map with classified area information in home environments,”, Journal of Korea Robotics Society, (2012), 7(4), p252-258. [https://doi.org/10.7746/jkros.2012.7.4.252]