Time-efficient and complete coverage path planning based on flow networks for multi-robots

详细信息    查看全文

• 作者：Adiyabaatar Janchiv (1184)
  Dugarjav Batsaikhan (1184)
  ByungSoo Kim (1184)
  Won Gu Lee (2184)
  Soon-Geul Lee (2184)
  
• 关键词：Cellular decomposition ; cleaning robot ; complete coverage path planning ; multi ; robot ; time efficiency
• 刊名：International Journal of Control, Automation and Systems
• 出版年：2013
• 出版时间：April 2013
• 年：2013
• 卷：11
• 期：2
• 页码：369-376
• 全文大小：865 KB
• 参考文献：1. H. Choset, 鈥淐overage of known spaces: the boustrophedon cellular decomposition,鈥? / Autonomous Robots, vol. 9, no. 3, pp. 247鈥?53, December 2000. CrossRef
  2. S. C. Wong and B. A. MacDonald, 鈥淎 topological coverage algorithm for mobile robots,鈥? / Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 2, pp. 1685鈥?690, October 2003.
  3. S. C. Wong and B. A. MacDonald, 鈥淐omplete 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鈥?92, August 2004.
  4. J. W. Kang, S. J. Kim, and M. J. Chung, 鈥淧ath planning for complete and efficient coverage operation of mobile robots,鈥? / Proc. of the IEEE International Conference on Mechatronics and Automation, pp. 2126鈥?131, August 2007.
  5. Y. Mao, L. Dou, J. Chen, H. Fang, H. Zhang, and H. Cao, 鈥淐ombined complete coverage path planning for autonomous mobile robot in indoor environment,鈥? / Proc. of the 7th Asian Control Conference, pp. 1468鈥?473, August 2009.
  6. S. H. Nam, I. S. Shin, J. J. Kim, and S. G. Lee, 鈥淐omplete coverage path planning for multi-robots employing flow networks,鈥? / Proc. of the International Conference on Control, Automation and Systems, pp. 2117鈥?120, October 2008.
  7. Y. H. Choi, T. K. Lee, S. H. Baek, and S. Y. Oh, 鈥淥nline 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鈥?793, October 2009.
  8. S. Surve, N. M. Singh, and B. K. Lande, 鈥淐PPA: A Fast Coverage Algorithm,鈥? / International Conference on Computational Intelligence and Multimedia Applications, vol. 2, pp. 151鈥?58, 2007.
  9. S. Hert and B. Richards, 鈥淢ultiple robot motion planning = parallel processing + Geometry,鈥? / Sensor Based Intelligent Robots, LNCS 2238, vol. 2238, pp. 195鈥?15, October 2002. CrossRef
  10. G. H. Kim, H. Kim, B. S. Kim, and S. G. Lee, 鈥淧ath planning for an intelligent robot using flow networks,鈥? / Journal of Korea Institute of Intelligent Systems, pp. 255鈥?62, August 2011.
  11. S. H. Nam and S. B. Moon, 鈥淢inimal turning path planning for cleaning robots employing flow networks,鈥? / Journal of Control, Automation, and Systems Engineering, vol. 11, no. 9, 2005.
  12. B. Park, J. Choi, and W. K. Chung, 鈥淪amplingbased retraction method for improving the quality of mobile robot path planning,鈥? / International Journal of Control, Automation, and Systems, vol. 10, no. 5, pp. 982鈥?91, October 2012. CrossRef
  13. K. Yang, 鈥淎nytime 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鈥?58, August 2011. CrossRef
  
• 作者单位：Adiyabaatar Janchiv (1184)
  Dugarjav Batsaikhan (1184)
  ByungSoo Kim (1184)
  Won Gu Lee (2184)
  Soon-Geul Lee (2184)
  
  1184. Department of Mechanical Engineering, Kyung Hee University, Yongin, Korea
  2184. Industrial Liaison Research Center, Kyung Hee University, Yongin, Korea
  
• ISSN：2005-4092

文摘

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.