Scan Matching Online Cell Decomposition for Coverage Path Planning in an Unknown Environment

Dugarjav, Batsaikhan,Lee, Soon-Geul,Kim, Donghan,Kim, Jong Hyeong,Chong, Nak Young Korean Society for Precision Engineering 2013 International Journal of Precision Engineering and Vol.14 No.9

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.

Scan Matching Online Cell Decomposition for Coverage Path Planning in an Unknown Environment

Batsaikhan Dugarjav,이순걸,김동한,김종형,정낙영 한국정밀공학회 2013 International Journal of Precision Engineering and Vol. No.

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.

Adaptive Online Cell Decomposition with a Laser Range Finder in Unknown Non-Rectilinear Environments

Batsaikhan Dugarjav,이순걸,Tan Bui Quang,곽관웅,이범주 한국정밀공학회 2017 International Journal of Precision Engineering and Vol.18 No.4

Although the use of autonomous mobile robots in a known workspace has become increasingly popular, their application in an unknown workspace remains a challenge. This paper presents a sensor-based online cell decomposition method that is supported by online coverage; it allows a robot to simultaneously explore an unknown workspace and achieve adaptive cell decomposition to ensure the coverage of a non-rectilinear environment. Assumptions on the proposed method are established to obtain a viable solution. First, map building and position correction are simplified under the following assumptions. The workspace of the robot is nonrectilinear and structured, in which several convex obstacles are distributed. The orthogonality assumption follows the previous assumption. The orthogonality assumption posits that major structures of the indoor environment can be modeled by sets of lines and curves. Second, the decomposed cell must be as large as possible. Lastly, cells are composed by considering their adaptability to an explored map, that is, each cell is composed and updated until it is unchanged. The main process to construct cells is performed after a visibility map is built to guarantee that all visible maps have been seen by a mobile robot previously. The performance evolution of the proposed method is verified through an experiment.

Complete Coverage Path Planning for Multi-Robots Based on

Adiyabaatar Janchiv,Dugarjav Batsaikhan,Gook hwan Kim,Soon-Geul Lee 제어로봇시스템학회 2011 제어로봇시스템학회 국제학술대회 논문집 Vol.2011 No.10

Complete coverage path planning is major problem for autonomous mobile robot, which concerns both efficiency and completeness of coverage. In this paper, a complete coverage path planning algorithm is proposed for two indoor floor-caring robots, such as cleaning or inspecting industrial and public floor areas, to have the minimal turning path based on the shape and size of the cell covering the whole working area. The proposed algorithm divides the whole cleaning area into cells by cellular decomposition method, and then provides efficient covering order over the cells based on distance among centroids of cells. It also provides more optimal coverage path and reduces the rate of energy consumption and working time. Both simulation and experimental results demonstrate the effectiveness of the algorithm. As compared performance indices between experiment and simulation, the total number of turns and the working time show the practical efficiency and robustness of the proposed algorithm.

Time-Efficient and Complete Coverage Path Planning Based on Flow Networks for Multi-Robots

Adiyabaatar Janchiv,Dugarjav Batsaikhan,김병수,이원구,이순걸 제어·로봇·시스템학회 2013 International Journal of Control, Automation, and Vol.11 No.2

Complete coverage path planning (CCPP), specifically, the efficiency and completeness of coverage of robots, is one of the major problems in autonomous mobile robotics. This study proposes a path planning technique to solve global time optimization. Conventional algorithms related to template-based coverage can minimize the time required to cover particular cells. The minimal turning path is mostly based on the shape and size of the cell. Conventional algorithms can determine the optimum time path inside a cell; however, these algorithms cannot ensure that the total time determined for the coverage path is the global optimum. This study presents an algorithm that can convert a CCPP problem into a flow network by exact cell decomposition. The total time cost to reach the edge of a flow network is the sum of the time to cover the current cell and the time to shift in adjacent cells. The time cost determines a minimum-cost path from the start node to the final node through the flow network, which is capable of visiting each node exactly once through the network search algorithm. Search results show that the time-efficient coverage can obtain the global optimum. Simulation and experimental results demonstrate that the proposed algorithm operates in a time-efficient manner.

A Study on Scan Matching Method Using Procrustes Analysis

Hyung Kim,Batsaikhan Dugarjav,Kwang-Hun Lee,Soon-Geul Lee 제어로봇시스템학회 2014 제어로봇시스템학회 국제학술대회 논문집 Vol.2014 No.10

A mobile robot must know its position within an unknown environment in order to perform tasks reliably. In this paper, enhancing the scan-matching algorithm for accurate map building and localization using a laser range finder in an unknown environment is proposed. When using the encoder, consideration of the error by slip and backlash of wheels is required for accurate localization. In this paper, more accurate translation and rotation between the reference position where the previous pose was obtained and the current position of the mobile robot is obtained by combining with the scanned data of the laser range finder while the robot navigates and using Procrustes analysis. This scan matching method is consecutively applied to the scan data of the environment and the odometer information of the robot. The pose of the robot and the map information of the environment are revised accordingly. Experimental result shows that the proposed scan matching algorithm for a mobile robot facilitates reduction of the error of map building from environmental information with the revised pose information of the robot.