臺灣博碩士論文加值系統

完整區域覆蓋環繞路徑(Complete Area Coverage)是一種需要訪問過所有工作區域的特殊機器人導航，CAC在清潔機器人與其他機器人的應用上是一個重要的議題。其中，完整區域覆蓋路徑規劃可以增進許多效能。在本文中，我們應用垂直分解概念(Vertical Cell-decomposition)與最小生成樹概念(Minimum spanning tree)來對自動機器人規劃完整區域覆蓋路徑導航，在本方法裡，我們有效率的集成垂直分解的方法、以生成樹為基礎的方法與最小生成樹的方法於規劃自動機器人導航的完整區域覆蓋路徑，該方法在規劃歐氏空間中矩形障礙物的完整區域覆蓋環繞路徑能以最短軌跡長度、最高效能完成，且時間複雜度為O(n log n)，其中n為障礙物之數目。

Complete area coverage navigation (CAC) requires a special type of robot path planning, where the robots should visit every point of the state workspace. CAC is an essential issue for cleaning robots and many other robotic applications. In addition to cleaning robots, plenty of robotics applications also require CAC, e.g. autonomous underwater coving vehicles, painter robots, lawn mowers, demining robots, automated harvesters, and window cleaners, etc. Real-time complete area coverage path planning is desirable for efficient performance in many applications. In this thesis, a novel vertical cell-decomposition (VCD) with minimum spanning tree (MST) approach is proposed for real-time CAC navigation of autonomous mobile robots. In this model, a vertical cell-decomposition (VCD) methodology and a spanning-tree based approach with minimum spanning tree are effectively integrated to plan a complete area coverage motion for autonomous mobile robot navigation. The computational complexity of this method with minimum trajectory length planned by a cleaning robot in the complete area coverage navigation with rectangle obstacles in the Euclidean space is O(n log n). The performance analysis, computational validation and comparison studies demonstrate that the proposal model is computational efficient, complete and robust.

謝　辭 Ⅰ
Abstract (Chinese) Ⅱ
Abstract (English) Ⅲ
Table of Contents Ⅳ
List of Figures Ⅴ
List of Tables Ⅵ

CHAPTER 1: Introduction 1

CHAPTER 2: Background 5

CHAPTER 3: Algorithm and Illustration 8
3.1 Algorithm: The Real-Time Complete Area Coverage Navigation 8
3.2 Illustration of Algorithm 9

CHAPTER 4: Performance Analysis 15

CHAPTER 5: Experimental Result 18

CHAPTER 6: Conclusion and Future Work 22

REFERENCE 23

[1] G. Lawitzky, “A navigation system for cleaning robots,” Autonomous Robots, vol. 9, 2000, pp. 255–260.
[2] C. Luo and S. X. Yang, “A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environ¬ments,” IEEE Trans. on Neural Networks, vol. 19, no. 7, 2008, pp. 1279–1298.
[3] J. S. Oh, J. B. Park, and Y. H. Choi, “Complete coverage navigation of clean robot based on triangular cell map,” in Proc .of IEEE Intl. Symp. on Industrial Electronics, Pusan, Korea, 2001, pp. 2089–2093.
[4] J. S. Oh, Y. H. Choi, J. B. Park, and Y. F. Zheng, “Complete coverage navigation of cleaning robots using triangular-cell-based map,” IEEE Trans. on Ind. Elec., vol. 51, no. 3, 2004, pp.718–726.
[5] F. Yasutomi, D. Takaoka, M. Yamada, and K. Tsukamoto, “Cleaning robot control,” in Proc. of IEEE Intl. Conf. on Robotics and Automation, Philadelphia, USA, 1988, pp. 1839–1841.
[6] D. W. Gage, “Randomized search strategies with imperfect sensors,” in Proc. of SPIE, Mobile Robots VIII - The Intl. Society for Optical Engineering, Boston, USA, 1994, pp. 270–279.
[7] H. Najjaran and N. Kircanski, “Path planning for a terrain scanner robot,” in Proc. of the 31st Intl. Symp. on Robotics, Montreal, Canada, 2000, pp. 132–137.
[8] M. Ollis and A. Stentz, “Vision-based perception for an automated harvester,” in Proc. of IEEE/RSJ Intl. Conf. on Intelligent Robot and Systems, Grenoble, France, 1997, pp. 1838–1844.
[9] M. Ollis and A. Stentz, “First results in vision-based crop line tracking,” in Proc. of IEEE Intl. Conf. on Robotics and Automation, Minneapolis, USA, 1996, pp. 951–956.
[10] M. Farsi, K. Ratcliff, P. J. Johnson, C. R. Allen, K. Z. Karam, and R. Pawson, “Robot control system for window cleaning,” in Proc. of 11th Intl. Symp. on Automation and Robotics in Construction, Brighton, UK, 1994, pp. 617–623.
[11] A. Pirzadeh and W. Snyder, “A unified solution to coverage and search in explored and unexplored terrains using indirect control,” in Proc. IEEE Int. Conf. Robotics Automation, Raleigh, NC, 1990, pp. 2113–2119.
[12] H. P. Moravec and A. Elfes, “High resolution maps from wide angle sonar,” in Proc. IEEE Int. Conf. Robotics Automation, St. Louis, MO, 1985, pp. 116–121.
[13] A. Zelinsky, R. A. Jarvis, J. C. Byarne, and S. Yuta, “Planning paths of complete coverage of an unstructured environment by a mobile robot,” in Proc. IEEE Int. Conf. Robotics Automation, Tokyo, Japan, 1993, pp. 533–538.
[14] Y. Gabriely and E. Rimon, “Spanning-tree based coverage of continuous areas by a mobile robot,” Ann. Math. Artificial Intelligence, vol. 31, no. 1–4, 2001, pp. 77–98.
[15] N. Agmon, N. Hazon, and G. A. Kaminka, “Constructing spanning trees for efficient multi-robot coverage,” in Proc. of IEEE Intl. Conf. on Robotics and Automation, Orlando, USA, 2006, pp. 1698–1703.
[16] S. X. Yang, and C. Luo “A neural network approach to complete coverage path planning”, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 34(1), 2004, pp. 718-725.
[17] C. Luo, S. X. Yang, D. A. Stacey, and J. C. Jofriet, “A solution to vicinity problem of obstacles in complete coverage path planning”, Proc. of IEEE Intl. Conf. on Robotics and Automation (ICRA), Washington D.C., USA, May 11-15, 2002, pp. 612-617.
[18] R. Mannadiar and A. I. Rekleitis, “Optimal Coverage of a Known Arbitrary Environment,” in Proc. of IEEE/RSJ Intl. Conf. on Intelligent Robots and Automation, 2010, pp. 5525–5530.
[19] G. Zuo, P. Zhang, and J. Qiao, “Path planning algorithm based on sub-region for agricultural robot,” in Proc. of the 2nd international Asia conf. on Informatics in control, automation and robotics, vol. 2, 2010, pp. 197–200.
[20] S. W. Ryu, Y. H. Lee, T. Y. Kuc, S. H. Ji, and Y. S. Moon, “A Search and Coverage Algorithm for Mobile Robot,” in Proc. of the 2nd International Conf. on Ubiquitous Robots and Ambient Intelligence, Incheon, Korea, Nov. 23–26, 2011.
[21] H. M. Choset, E. U. Acar, A. A. Rizzi, and J. E. Luntz, “Sensor-based planning: Exact cellular decompositions in terms of critical points,” in Proc. SPIE—Int. Soc. Opt. Eng., Boston, MA, 2001, pp. 204–215.
[22] E. U. Acar, H. Choset, and P. N. Atkar, “Complete sensor-based coverage with extended-range detectors: A hierarchical decomposition in terms of critical points and Voronoi diagrams,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst., Maui, HI, 2001, pp. 1305–1311.
[23] J. Y. Park and K. D. Lee, “A study on the cleaning algorithm for autonomous mobile robot under the unknown environment,” in Proc. 6th IEEE Int. Workshop Robot Human Commun., Sendai, Japan, 1997, pp. 70-75.
[24] W. H. Huang, “Optimal line-sweep-based decompositions for coverage algorithms”, in Proc. IEEE International Conference on Robotics and Automation, 2001, pp. 27 - 32.
[25] H. Choset, “Coverage for robotics - a survey of recent results,” Annals of Mathematics and Artificial Intelligence, vol. 31, 2001, pp. 113–126.
[26] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, MA: MIT Press, 2009.
[27] C. O’Dunlaing and C. K. Yap., “A retraction method for planning the motion of a disc,” Journal of Algorithms, 6:104–111, 1982.
[28] T. H. Peng, “Complete Area Coverage Path-planning with Minimum Length And O(n log n) Time,” M.S. thesis, Dept. Elect. Eng., National Taipei Univ., Taipei, 2013.