完整區域覆蓋路徑規劃

Complete area coverage path-planning with minimum length and O(n log n) time

彭德懷(Te-Huai Peng)

指導教授 ： 詹景裕

國立臺北大學/電機資訊學院/電機工程研究所/碩士(2013年)

摘要

我們應用限制Delaunay三角剖分觀念(Constrained Delaunay Triangulation, CDT)來將歐式平面正合剖分 (Exact Cell-Decomposition)並以生成樹(Spanning-Tree)之概念找出最短長度之完整區域覆蓋環繞路徑，其時間複雜為O(n log n)。其中n表示障礙物的數目。以目前我們所知的文獻，我們所提的演算法有下列幾項超越其他研究之優點: (a)可覆蓋完整的區域，(b)且完全沒有重複路徑情況下通過尚未覆蓋區域，(c) 因為不重複路徑，可不浪費能量、時間的情況下機器人結束時回到起始點，(d) 在歐氏平面裡可有凸、凹多邊形的障礙物，(e)這是目前最快的演算法。

關鍵字

完整區域覆蓋 ； 限制Delaunay三角剖分 ； 生成樹

並列摘要

We present a novel method according to the concepts of exact cell-decomposition based model with constrained Delaunay triangulation (CDT) and spanning-tree based approach to plan the path of complete area coverage problem with minimum length and O(n log n) time complexity. The algorithm navigates a mobile robot through a sequence of areas to be covered without wasting energy and time without overlapping, and at the end the robot will return to the starting point. To the best of our knowledge, this is the fastest method with minimum length addressing the complete area coverage problem with convex and concave polygon obstacles in the Euclidean space.

並列關鍵字

Complete area coverage ； constrained Delaunay triangulation ； spanning tree

參考文獻

[1] G. Lawitzky, “A navigation system for cleaning robots,” Autonomous Robots, vol. 9, pp. 255–260, 2000.

[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, pp. 1279–1298, 2008.

[5] 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, SouthKorea, pp. 2089–2093, 2001.

[6] 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, pp.718–726, 2004.

[11] 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, pp. 951–956, 1996.