Abstract
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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
H. Choset, “Coverage of known spaces: the boustrophedon cellular decomposition,” Autonomous Robots, vol. 9, no. 3, pp. 247–253, December 2000.
S. C. Wong and B. A. MacDonald, “A topological coverage algorithm for mobile robots,” Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 2, pp. 1685–1690, October 2003.
S. C. Wong and B. A. MacDonald, “Complete coverage by mobile robots using slice decomposition based on natural land marks,” Proc. of the 8th Pacific Rim International Conference on Artificial intelligence, vol. 3157, pp. 683–692, August 2004.
J. W. Kang, S. J. Kim, and M. J. Chung, “Path planning for complete and efficient coverage operation of mobile robots,” Proc. of the IEEE International Conference on Mechatronics and Automation, pp. 2126–2131, August 2007.
Y. Mao, L. Dou, J. Chen, H. Fang, H. Zhang, and H. Cao, “Combined complete coverage path planning for autonomous mobile robot in indoor environment,” Proc. of the 7th Asian Control Conference, pp. 1468–1473, August 2009.
S. H. Nam, I. S. Shin, J. J. Kim, and S. G. Lee, “Complete coverage path planning for multi-robots employing flow networks,” Proc. of the International Conference on Control, Automation and Systems, pp. 2117–2120, October 2008.
Y. H. Choi, T. K. Lee, S. H. Baek, and S. Y. Oh, “Online complete coverage path planning for mobile robot based on linked spiral paths using constrained inverse distance transform,” Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5788–5793, October 2009.
S. Surve, N. M. Singh, and B. K. Lande, “CPPA: A Fast Coverage Algorithm,” International Conference on Computational Intelligence and Multimedia Applications, vol. 2, pp. 151–158, 2007.
S. Hert and B. Richards, “Multiple robot motion planning = parallel processing + Geometry,” Sensor Based Intelligent Robots, LNCS 2238, vol. 2238, pp. 195–215, October 2002.
G. H. Kim, H. Kim, B. S. Kim, and S. G. Lee, “Path planning for an intelligent robot using flow networks,” Journal of Korea Institute of Intelligent Systems, pp. 255–262, August 2011.
S. H. Nam and S. B. Moon, “Minimal turning path planning for cleaning robots employing flow networks,” Journal of Control, Automation, and Systems Engineering, vol. 11, no. 9, 2005.
B. Park, J. Choi, and W. K. Chung, “Samplingbased retraction method for improving the quality of mobile robot path planning,” International Journal of Control, Automation, and Systems, vol. 10, no. 5, pp. 982–991, October 2012.
K. Yang, “Anytime synchronized-biased-greedy rapidly-exploring random tree path planning in two dimensional complex environments,” International Journal of Control, Automation, and Systems, vol. 9, no. 4, pp. 750–758, August 2011.
Author information
Authors and Affiliations
Corresponding author
Additional information
Recommended by Editorial Board member Fuchun Sun under the direction of Editor Hyouk Ryeol Choi.
This research was partially supported by the Korea Evaluation Institute of Industrial Technology (No. 10035544) and the Implementation of Technologies for Identification, Behavior, and Location of Human based on Sensor Network Fusion Program (Grant Number: 10041629) of the Ministry of Knowledge Economy (MKE), Korea.
Adiyabaatar Janchiv received his B.E. degree in Mechanical Engineering from Mongolian University of Science and Technology, Ulaanbaatar, Mongolia in 2009 and his M.S degree in Mechanical Engineering from Kyung Hee University, Yongin, Korea in 2012. He is currently working as sales engineer at Wagner Asia Equipment LLC in Mongolia. His research interest mobile robotics, automatic control and power supply network protection.
Dugarjav Batsaikhan received his B.E. degree in Mechanical Engineering from Mongolian University of Science and Technology, Ulaanbaatar, Mongolia in 2009. He is currently a Ph.D. student at the Department of Mechanical Engineering, Kyung Hee University. His research interests include mobile robotics and mechatronics.
ByungSoo Kim received his B.E. degree in Mechanical Design Engineering from Seoul National University of Science and Technology, Seoul, Korea, and his M.S. and Ph.D. degrees in Mechanical Engineering from Kyung Hee University, Yongin, Korea, in 1991, 1993, and 2011, respectively. He is currently as a postdoctoral researcher at the Department of Mechanical Engineering, Kyung Hee University. His research interests include humanoid robot, mechatronics, intelligent control, and mobile robot.
Won Gu Lee received his B.S. and M.S. degrees from the Department of Control & Mechanical Engineering at Pusan National University, and his Ph.D. degree from the School of Mechanical & Aerospace Engineering at Seoul National University, in 1996, 2000, and 2007, respectively. He got trained from the Harvard-MIT Health Sciences and Technology (HST) and Wyss Institute at Harvard University, U.S.A. as postdoctoral researcher. He is currently an Assistant Professor at the Department of Mechanical Engineering, Kyung Hee University. He is also an Adjunct Professor of Xi’an Jiaotong University, China. His research interests are in the area of developing a neural mechatronic system in association with human-on-a-chip in optofluidics.
Soon-Geul Lee received his B.E. degree in Mechanical Engineering from Seoul National University, Seoul, Korea, an M.S. degree in Production Engineering from KAIST, Seoul, Korea, and a Ph.D. degree in Mechanical Engineering from the University of Michigan, in 1983, 1985 and 1993 respectively. Since 1996, he has been with the Department of Mechanical Engineering of Kyung Hee University, Yongin, Korea, where he is currently a Professor. His research interests include robotics and automation, mechatronics, intelligent control, and biomechanics. He likewise served as the Director of the Korean Society of Precision Engineering (KSPE) (2005–2007) and for Institute of Control, Robotics, and Systems (ICROS) (2006).
Rights and permissions
About this article
Cite this article
Janchiv, A., Batsaikhan, D., Kim, B. et al. Time-efficient and complete coverage path planning based on flow networks for multi-robots. Int. J. Control Autom. Syst. 11, 369–376 (2013). https://doi.org/10.1007/s12555-011-0184-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12555-011-0184-5