naa a22 4500 510822479 CHVBK 20180411083540.0 cr unu---uuuuu 180411e20130901xx s 000 0 eng 10.1007/s12541-013-0209-5 doi (NATIONALLICENCE)springer-10.1007/s12541-013-0209-5 Scan matching online cell decomposition for coverage path planning in an unknown environment [Elektronische Daten] [Batsaikhan Dugarjav, Soon-Geul Lee, Donghan Kim, Jong Kim, Nak Chong] This paper presents a novel sensor-based online coverage path-planning algorithm that guarantees the complete coverage of an unknown rectilinear workspace for the task of a mobile robot. The proposed algorithm divides the workspace of the robot into cells at each scan sample. This division can be classified as an exact cell decomposition method, which incrementally constructs cell decomposition while the robot covers an unknown workspace. To guarantee complete coverage, a closed map representation based on a feature extraction that consists of a set of line segments called critical edges is proposed. In this algorithm, cell boundaries are formed by extended critical edges, which are the sensed partial contours of walls and objects in the workspace. The robot uses a laser scanner to sense the critical edges. Sensor measurement is sampled twice in each cell. Scan matching is performed to merge map information between the reference scan and the current scan. At each scan sample, a two-direction oriented rectilinear decomposition is achieved in the workspace and presented by a closed map representation. The construction order of the cells is very important in this incremental cell decomposition algorithm. To choose the next target cell from candidate cells, the robot checks for redundancy in the planned path and for possible positions of the ending points of the current cell. The key point of the algorithm is memorizing the covered space to define the next target cell from possible cells. The path generation within the defined cell is determined to minimize the number of turns, which is the main factor in saving time during the coverage. Therefore, the cell's long boundary should be chosen as the main path of the robot. This algorithm is verified by an experiment under the LABVIEW environment. Korean Society for Precision Engineering and Springer-Verlag Berlin Heidelberg, 2013 Scan matching nationallicence Sensor-based online incremental cell decomposition nationallicence Oriented rectilinear decomposition complete coverage nationallicence Path planning nationallicence Dugarjav Batsaikhan School of Mechanical Engineering, Kyung Hee University, Seocheon-dong, Giheung-gu, 446-701, Yongin, South Korea aut Lee Soon-Geul School of Mechanical Engineering, Kyung Hee University, Seocheon-dong, Giheung-gu, 446-701, Yongin, South Korea aut Kim Donghan School of Electronic Engineering, Kyung Hee University, Seocheon-dong, Giheung-gu, 446-701, Yongin, South Korea aut Kim Jong Dept. of Mechanical System Design Eng., Seoul National University of Science & Technology, Gongneung-dong, Nowon-ku, 139-743, Seoul, South Korea aut Chong Nak School of Mechanical Engineering, Kyung Hee University, Seocheon-dong, Giheung-gu, 446-701, Yongin, South Korea aut International Journal of Precision Engineering and Manufacturing Springer Berlin Heidelberg 14/9(2013-09-01), 1551-1558 2234-7593 14:9<1551 2013 14 12541 https://doi.org/10.1007/s12541-013-0209-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s12541-013-0209-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Dugarjav Batsaikhan School of Mechanical Engineering, Kyung Hee University, Seocheon-dong, Giheung-gu, 446-701, Yongin, South Korea aut NATIONALLICENCE 700 1- Lee Soon-Geul School of Mechanical Engineering, Kyung Hee University, Seocheon-dong, Giheung-gu, 446-701, Yongin, South Korea aut NATIONALLICENCE 700 1- Kim Donghan School of Electronic Engineering, Kyung Hee University, Seocheon-dong, Giheung-gu, 446-701, Yongin, South Korea aut NATIONALLICENCE 700 1- Kim Jong Dept. of Mechanical System Design Eng., Seoul National University of Science & Technology, Gongneung-dong, Nowon-ku, 139-743, Seoul, South Korea aut NATIONALLICENCE 700 1- Chong Nak School of Mechanical Engineering, Kyung Hee University, Seocheon-dong, Giheung-gu, 446-701, Yongin, South Korea aut NATIONALLICENCE 773 0- International Journal of Precision Engineering and Manufacturing Springer Berlin Heidelberg 14/9(2013-09-01), 1551-1558 2234-7593 14:9<1551 2013 14 12541 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer