Exploration and Mapping of Unknown Polygonal Environments Based on Uncertain Range Data

Abstract

We consider problem of exploration and mapping of unknown indoor environments using laser range finder. We assume a setup with a resolved localization problem and known uncertainty sensor models. Most exploration algorithms are based on detection of a boundary between explored and unexplored regions. They are, however, not efficient in practice due to uncertainties in measurement, localization and map building. The exploration and mapping algorithm is proposed that extends Ekman's exploration algorithm by removing rigid constraints on the range sensor and robot localization. The proposed algorithm includes line extraction algorithm developed by Pfister, which incorporates noise models of the range sensor and robot's pose uncertainty. A line representation of the range data is used for creating polygon that represents explored region from each measurement pose. The polygon edges that do not correspond to real environmental features are candidates for a new measurement pose. A general polygon clipping algorithm is used to obtain the total explored region as the union of polygons from different measurement poses. The proposed algorithm is tested and compared to the Ekman's algorithm by simulations and experimentally on a Pioneer 3DX mobile robot equipped with SICK LMS-200 laser range finder.

Razmatramo problem istraživanja i izgradnje karte nepoznatog unutarnjeg prostora koristeći laserski senzor udaljenosti. Pretpostavljamo riješenu lokalizaciju robota i poznati model nesigurnosti senzora. Većina se algoritama istraživanja zasniva na otkrivanju granica istraženog i neistraženog područja. Međutim, u praksi nisu učinkoviti zbog nesigurnosti mjerenja, lokalizacije i izgradnje karte. Razvijen je algoritam istraživanja i izgradnje karte koji proširuje Ekmanov algoritam uklanjanjem strogih ograničenja na senzor udaljenosti i lokalizaciju robota. Razvijeni algoritam uključuje algoritam izdvajanja linijskih segmenata prema Pfisteru, koji uzima u obzir utjecaje zašuml-jenosti senzora i nesigurnosti položaja mobilnog robota. Linijska reprezentacija podataka udaljenosti koristi se za stvaranje poligona koji predstavlja istraženo područje iz svakog mjernog položaja. Bridovi poligona koji se ne podudaraju sa stvarnim značajkama prostora su kandidati za novi mjerni položaj. Algoritam općenitog isijecanja poligona korišten je za dobivanje ukupnog istraženog područja kao unija poligona iz različitih mjernih položaja. Razvijeni algoritam testiran je i uspore en s izvornim Ekmanovim algoritmom simulacijski i eksperimentalno na mobilnom robotu Pioneer 3DX opremljenim laserskim senzorom udaljenosti STCK LMS-200.

Key words:

• Exploration
• Mapping
• Line extraction
• Mobile robot

Ključne riječi:

• istraživanje
• izgradnja karte
• izdvajanje linijskih segmenata
• mobilni robot

Additional information

Notes on contributors

Marija Đakulović

Marija Đakulović received the B. Sc. degree in 2004 and Ph. D. degree in 2010, all in Electrical Engineering from the Faculty of Electrical Engineering and Computing (FER Zagreb), University of Zagreb, Croatia. Since 2004 she has been with the Department of Control and Computer Engineering at FER Zagreb, where she is currently working as a teaching assistant and a post-doc researcher. Her main research interests are: mobile robotics (especially path planning, obstacle avoidance and motion planning). During her undergraduate and graduate studies she was awarded with two faculty prizes, Vice-chancellor award and with scholarships from the Croatian ministry of science.

Šandor Ileš

Šandor Ileš received dipl. ing. (in Croatia interpreted as M. Eng.) degree in electrical engineering from the University of Zagreb, Croatia in 2009. Currently he is a Ph. D. student working as an assistant at the Department of Electric Machines, Drives and Automation, Faculty of Electrical Engineering and Computing, University of Zagreb. His main research interests are control of mechatronic systems, application of linear matrix inequalities in control and polytopic system representation.

Ivan Petrović

Ivan Petrović received B. Sc. degree in 1983 M. Sc. degree in 1989 and Ph. D. degree in 1998, all in Electrical Engineering from the Faculty of Electrical Engineering and Computing (FER Zagreb), University of Zagreb, Croatia. He had been employed as an R&D engineer at the Institute of Electrical Engineering of the KonÄŤar Corporation in Zagreb from 1985 to 1994. Since 1994 he has been with FER Zagreb, where he is currently a full professor and the head of the Department of Control and Computer Engineering. He teaches a number of undergraduate and graduate courses in the field of control systems and mobile robotics. His research interests include various advanced control strategies and their applications to control of complex systems and mobile robots navigation. Results of his research effort have been implemented in several industrial products. He is a member of IEEE, IFAC—TC on Robotics and FIRA—Executive committee. He is a collaborating member of the Croatian Academy of Engineering.