Dual representation of 3D map for mobile robots

The paper presents several basic issues that were solved in order to create a complete system of 3D map building with the use of a mobile robot equipped with a two-dimensional range finder SICK LMS 200 and a tilt unit. The concept of a dual representation based on the extraction of planes and an occupancy map is the basic assumption of the system. The robust method of the extraction of planes from single 3D scans is presented, together with fast algorithms of generating and simplifying the triangle mesh. For the occupation map building, an efficient dynamic data structure based on the octree has been designed. It provides fast constant access time to each cell. The resulting dual 3D map is generated in the time period shorter than the overall time of the measurement.

W artykule zaprezentowana została koncepcja systemu do tworzenia map 3D przez roboty mobilne. Pomiary wykonywane są w czasie postoju robota za pomocą dalmierza laserowego SICK LMS 200 zamontowanego na głowicy obrotowej. Założono, że analiza i wstępne uproszczenie modelu odbywa się już na poziomie pojedynczego pomiaru 3D. Opracowane algorytmy pozwalają na obróbkę pomiaru 3D w czasie krótszym niż czas trwania pomiaru. Tworzony system przeznaczony jest dla robota poruszającego się wewnątrz budynku, gdzie większość obiektów składa się z powierzchni płaskich. Dlatego opracowano zestaw algorytmów umożliwiających szybkie wykrycie tego typu powierzchni, połączone z generowaniem i redukcją reprezentujących je siatek trójkątów. Ekstrakcja płaszczyzn pozwala na znaczne uproszczenie modelu otoczenia i będzie użyteczna w przyszłych pracach nad samolokalizacją robota. Mapa złożona z płaszczyzn nie jest wygodna w zadaniu planowania ścieżki, dlatego zaproponowano dualną formę reprezentacji złożoną z płaszczyzn i mapy zajętości opartej na drzewie ósemkowym. Opracowana mapa zajętości umożliwia przedstawienie przeszkód niepłaskich za pomocą voxeli i szybki dostęp w stałym czasie do dowolnej komórki tej mapy.