摘要
近年來機器人的發展與研究，已成為自動化研究中主要的一環，目前這部分的研究要求機器人要有能應付突發狀況的能力，例如當一機器人循一路徑前往一目標點時，若在行進途中出現突如其來的障礙物，機器人要能即時想辦法去迴避，我們稱此種在運作中具有應變能力為動態控制 (dynamic control)。
本論文提出以Voronoi diagram(VD)和Chamfer distance(CD)的技術事先對環境建立一路圖，其中描述環境中靜態障礙物的位置及大小並事先規劃好環境中點與點之間的最佳路徑，其好處是機器人可以將注意力集中在動態障礙物的偵測與處理；此部分我們提出兩種動態障礙物迴避機制，供機器人於行進的途中迴避未知的障礙物。
本系統包含三個主要工作：路圖建置、路線規劃以及迴避機制。路圖的建置主要在於建立一些環境資訊，包括機械人活動的範圍、靜態障礙物的分佈及確切的位置，路圖儲存於機械人端，使得機械人可以得知其活動範圍內那些地方是它可以行走的。路線規劃是於機械人目前之位置，與給予的終點間規劃出一條可以避開靜態障礙物之最佳路徑。迴避系統則是當機械人在原規劃路徑上行進時如遇到動態障礙物，機械人得予即時地規劃出一條可以迴避障礙物的路徑，並於避開障礙物後回到原規劃的路徑繼續行進。
關鍵詞：動態控制、Voronoi diagram、Chamfer distance、路圖、靜態障礙物、動態障礙物。

We use Voronoi diagram(VD) and Chamfer distance(CD) for a robotic vehicle to do motion planning in a dynamic environment.

參考文獻
[1] J. Luh, “An anatomy of industrial robots and their controls,” IEEE Transactions on Automatic Control, Vol. 28, No. 2, pp.133-153, Feb. 1983.
[2] K. Mandel and N. Duffie, “On-line compensation of mobile robot docking errors,” IEEE Journal of Robotics and Automation, Vol. 3, No. 6, pp. 591-598, Dec. 1987.
[3] S. Kawamura, F. Miyazaki,and S. Arimoto, “Realization of robot motion based on a learning method,” IEEE Transactions on Systems, Man and Cybernetics, Vol. 18, No. 1, pp.126-134. Jan. 1988.
[4] T. Lozano-Perez, “A simple motion-planning algorithm for general robot manipulators,” IEEE Journal of Robotics and Automation, Vol. 3, No. 3, pp. 224-238, Jun. 1987.
[5] C. L. Shih, T. T. Lee,and W. A. Gruver, “A unified approach for robot motion planning with moving polyhedral obstacles,” IEEE Transactions on Systems, Man and Cybernetics, Vol. 20, No. 4, pp. 903-915, July-Aug. 1990.
[6] Z. Shiller and Y. R. Gwo, “Dynamic motion planning of autonomous vehicles,” IEEE Transactions on Robotics and Automation, Vol. 7 No. 2, pp. 241-249, April 1991.
[7] F. Lamiraux and J. P. Lammond, “Smooth motion planning for car-like vehicles,” IEEE Transactions on Robotics and Automation, Vol. 17, No. 4, pp. 498-501, Aug. 2001.
[8] J. T. Schwartz and M. A. Sharir, “On the piano movers problem I: A case of a two-dimensional rigid polygonal body moving amidst polygonal barriers,”Commun. Pure Appl. Math., Vol. 36, pp345-398, 1983.
[9] S. W. Hsu and T. Y. Li, “Generating Traditional Shadow Play Animations with Motion Planning Algorithms,” in Proceedings of the Nineth Conference on Artificial Intelligence and Applications, Taiwan, Nov. 2004.
[10] L. E. Kavraki, P. Svestka, J. C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Transactions on Robotics and Automation, Vol. 12, No. 4, pp. 566-580, Aug. 1996.
[11] Kumar Vijay, D. Rus, and Singh Sanjiv, “Robot and sensor networks for first responders,” IEEE Pervasive Computing, Vol. 3, No. 4, pp. 24-33, Oct.-Dec. 2004.
[12] A. Yamashita, T. Arai, Ota Jun, and H. Asama, ”Motion planning of multiple mobile robots for Cooperative manipulation and transportation,” IEEE Transactions on Robotics and Automation, Vol. 19, No. 2, pp. 223-237, April 2003.
[13] S. Yamada, and J. Saito, “Adaptive action selection without explicit communication for multi-robot box-pushing,” IEEE Transactions on Systems, Man and Cybernetics, Part C, Vol. 31, No. 3, pp. 398-404, Aug. 2001.
[14] J. Conway and N. Sloane, “Voronoi regions of lattices, second moments of polytopes, and quantization,” IEEE Transactions on Information Theory, Vol. 28, No. 2, pp. 211-226, Mar. 1982.
[15] I. Gowda, D. Kirkpatrick, D. Lee, and A. Naamad, “Dynamic Voronoi diagrams,” IEEE Transactions on Information Theory, Vol. 29, No. 5, pp. 724-731, Sep. 1983.
[16] M. Tuceryan and A. K. Jain, “Texture segmentation using Voronoi polygons,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 2, pp.211-216, Feb. 1990.
[17] R. Al-Hmouz, T. Gulrez, and. A. Al-Jumaily, “Probabilistic Road Maps with Obstacle Avoidance in Cluttered Dynamic Environment,” Processing conference, intelligent sensors, sensor networks and information, pp.241-245, Dec. 2004
[18] Z. Sun, D. Hsu, T. Jiang, H. Kurniawati, and J. H. Reif, “Narrow passage sampling for probabilistic roadmap planning,” IEEE Transactions on robotics, Vol. 21, No.6, pp.1105-1115 Dec. 2005
[19] O. Takahashi, and R .J. Schilling, “Motion planning in a plane using generalized Voronoi diagrams,” IEEE Transactions on robotics and automation, Vol. 5, No.2, pp.143-150 April, 1989
[20] K. M. Moulton, A. Cornell, and E. Petriu, Fellow, IEEE, “A Fuzzy Error Correction Control System,” IEEE Transactions on instrumentation and measurement, Vol. 50, No. 5, pp.1456-1463 Oct. 2001
[21] S. Rebay “Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm,” Journal of Computational Physics, Academic Press, Vol. 106, No. 1 pp.125-138, May 1993.