Scan matching online cell decomposition for coverage path planning in an unknown environment

详细信息    查看全文

• 作者：Batsaikhan Dugarjav ; Soon-Geul Lee…
• 关键词：Scan matching ; Sensor ; based online incremental cell decomposition ; Oriented rectilinear decomposition complete coverage ; Path planning
• 刊名：International Journal of Precision Engineering and Manufacturing
• 出版年：2013
• 出版时间：September 2013
• 年：2013
• 卷：14
• 期：9
• 页码：1551-1558
• 全文大小：1192KB
• 参考文献：1. Latombe, J. C., “Robot motion planning,-Kluwer Academic Publishers, 1991. CrossRef
  2. Choset, H., “Coverage of known space: the boustrophedon cellular decomposition,-Autonomous Robots, Vol. 9, No. 3, pp. 247-53, 2000. CrossRef
  3. Acar, E., Choset, H., Rizzi, A. A., Atkar, P. N., and Hull, D., “Morse decompositions for the coverage task,-Int. J. of Robotics Research, Vol. 21, pp. 331-44, 2002. CrossRef
  4. Janchiv, A., Batsaikhan, D., Kim, B. S., Lee, W. G., and Lee, S. G., “Time-efficient and complete coverage path planning based on flow networks for multi-robots,-International Journal of Control, Automation and Systems, Vol. 11, No. 2, pp. 369-76, 2013. CrossRef
  5. Choset, H., Acar, E., Rizzi, A. A., and Luntz, J., “Exact cellular decompositions in terms of critical points of morse functions,-Proc. IEEE International Conference on Robotics and Automation, Vol. 3, pp. 2270-277, 2000.
  6. Acar, E. U. and Choset, H., “Robust sensor-based coverage of unstructured environment,-Proc. IEEE International Conference on Intelligent Robots and Systems, Vol. 1, pp. 61-8, 2001.
  7. Acar, E. and Choset, H., “Sensor-based coverage of unknown environments: incremental construction of Morse decompositions,-Int. J. Robotics Research, Vol. 21, pp. 345-66, 2002. CrossRef
  8. Choset, H. and Burdick, J., “Sensor-based motion planning: incremental construction of the hierarchical generalized Voronoi graph,-Int. J. of Robotics Research, Vol. 19, No. 2, pp. 126-48, 2000. CrossRef
  9. Acar, E., Choset, H., and Lee, J. Y., “Sensor-based coverage with extended range detectors,-IEEE Transactions on Robotics, Vol. 22, No. 1, 2006.
  10. Gabriely, Y. and Rimon, E., “Spiral-STC: an on-line coverage algorithm of grid environments by a mobile robot,-Proc. IEEE International Conference on Robotics and Automation, Vol. 1, pp. 954-60, 2002.
  11. Gonzalez, E., Alvarez, O., Diaz, Y., Parra, C., and Bustacara, C., “BSA: A Complete Coverage Algorithm,-Proc. IEEE International Conference on Robotics and Automation, pp. 2040-044, 2005.
  12. Choi, Y. H., Lee, T. K., Baek, S., and Oh, S. Y., “Online complete coverage path planning for mobile robots based on linked spiral paths using constrained inverse distance transform,-Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5788-793, 2009.
  13. Lee, T. K., Baek, S. H, Choi, Y. H., and Oh, S. Y., “Smooth coverage path planning and control of mobile robots based on highresolution grid map representation,-Int. J. Robotics and Autonomous Systems, Vol. 59, pp. 801-12, 2011. CrossRef
  14. Lee, T. K., Baek, S. H., and Oh, S. Y., “Sector-based maximal online coverage of unknown environments for cleaning robots with limited sensing,-Int. J. of Robotics and Autonomous Systems, Vol. 59, No. 10, pp. 698-10, 2011. CrossRef
  15. Myung, H., Jeon, H. M., and Jeong, W. Y., “Virtual door algorithm for coverage path planning of mobile robot,-Proc. IEEE International Symposium on Industrial Electronics, pp. 658-63, 2009.
  16. Hara, Y., Kawata, H., Ohya, A., and Yuta, S., “Map building for mobile robots using a SOKUIKI sensor robust scan matching using laser reflection intensity,-Int Joint Conf. on SICE-ICASE, pp. 5951-956, 2006.
  17. Lee, H. C., Lee, S. H., Lee, S. H., Lee, T. S., Kim, D. J., Park, K. S., Lee, K. W., and Lee, B. H., “Comparison and analysis of scan matching techniques for cooperative-SLAM,-Int. Conf. on Ubiquitous Robots and Ambient Intelligence, pp. 165-68, 2011.
  18. Diosi, A. and Kleeman, L., “Laser Scan Matching in Polar Coordinates with Application to SLAM,-IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3317-322, 2005.
  19. Chang, H. J., Lee, C. S. G., Lu, Y. H., and Hu, Y. C., “P-SLAM: Simultaneous Localization and Mapping With Environmental Structure Prediction,-IEEE Transactions on Robotics, Vol. 23, No. 2, pp. 281-93, 2007. CrossRef
  20. Nguyen, V., Harati, A., Martinelli, A., Tomatis, N., and Sa, B., “Orthogonal SLAM: a step toward lightweight indoor autonomous navigation,-Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2006.
  21. Saitov, D. and Lee, S. G., “Mobile robot navigation based on EWA with adaption of particle filter and map merging algorithms for localization and mapping,-Int. J. Precis. Eng. Manuf., Vol. 12, No. 3, pp. 451-59, 2011 CrossRef
  22. Batsaikhan, D., Janchiv, A., and Lee, S. G., “Sensor-Based Incremental Boustrophedon Decomposition for Coverage Path Planning of a Mobile Robot, in: Lee, S., Cho, H., Yoon, K. J., and Lee, J. (Eds.), Intelligent Autonomous Systems 12,-Springer, Vol. 193, pp. 621-28, 2013. CrossRef
  23. Censi, A., Iocchi, L., and Grisetti, G., “Scan matching in the Hough domain,-Proc. IEEE International Conference on Robotics and Automation, pp. 2739-744, 2005.
  24. Nguyen, V., Martinelli, A., Tomatis, N., and Siegwart, R., “A comparison of line extraction algorithms using 2D laser range finder for indoor mobile robotics,-Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1929-934, 2005.
  25. Baek, S., Lee, T. K., OH, S. Y., and Ju, K., “Integrated On-Line Localization, Mapping and Coverage Algorithm of Unknown Environments for Robotic Vacuum Cleaners Based on Minimal Sensing,-Advanced Robotics, Vol. 25, pp. 1651-673, 2011. CrossRef
  26. Butler, Z. J., Rizzi, A. A., and Hollis, R. L., “Cooperative coverage of rectilinear environments,-Proc. IEEE International Conference on Robotics and Automation, Vol. 3, pp. 2722-727, 2000.
  
• 作者单位：Batsaikhan Dugarjav (1)
  Soon-Geul Lee (1)
  Donghan Kim (2)
  Jong Hyeong Kim (3)
  Nak Young Chong (1) (4)
  
  1. School of Mechanical Engineering, Kyung Hee University, Seocheon-dong, Giheung-gu, Yongin, 446-701, South Korea
  2. School of Electronic Engineering, Kyung Hee University, Seocheon-dong, Giheung-gu, Yongin, 446-701, South Korea
  3. Dept. of Mechanical System Design Eng., Seoul National University of Science & Technology, Gongneung-dong, Nowon-ku, Seoul, 139-743, South Korea
  4. School of Information Science, Japan Advanced Institute of Science and Technology, Asahidai, Nomi, Ishikawa, 923-1292, Japan
  
• ISSN：2005-4602

文摘

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.