本論文主旨在實現自走車（autonomous car-like robots）路徑規劃演算法於ARM-based系統發展平台。論文中提出一種改良式可見度圖之路徑規劃演算法（visibility graph algorithm）應用在自走車上所發生的問題。由於自走車系統在運動上有所限制，所以無法做出橫向平移的動作，移動方式必須依照自走車車體有限的迴轉角度前進。因此規劃出來的路徑必須為平滑軌跡，如此方能作為自走車行進追尋的指標。如何由障礙物環境中，找出起點至終點間平滑且最短的路徑，即為本論文路徑規劃的主要目標。
待改良可見度圖之路徑規劃演算法於軟體驗證無誤後，我們將此路徑規劃演算法實現於ARM-based系統發展平台上，並且建立一個障礙物環境模擬平台來驗證此系統之準確性。由軟體模擬實驗之結果，證實本論文所設計之路徑規劃系統，可在任意多邊形障礙物環境中找出一條最短且平滑之路徑曲線。

The main focus of this thesis is to develop a path planning algorithm for car-like robots on an ARM-based development board. We modified a visibility graph algorithm to solve the motion planning problems for car-like robots. Because car-like robots are confined to their kinematics constraints such as limited steering angles, the path for car-like robots must be a smooth trajectory. Therefore, our aim of the path planning is to find the shortest smooth path among a set of polygonal obstacles without violating the constraints.
After the software validation of the modified visibility graph algorithm, we implement this algorithm on an ARM-based development board. Moreover, we construct a simulation platform to verify the feasibility and accuracy of the path planning system. Our simulation results indicate that the proposed path planning algorithm is capable of finding a shortest smooth trajectory among an obstacle environment.

[1] 黃悅民、陳敬、侯廷偉、陳中和、黃慶祥、林志敏，嵌入式系統設計-以ARM處理器基礎之SOC平台，初版，滄海，民95。
[2] 新華電腦，ARM9 S3C2410嵌入式SOC原理，初版，全華科技股份有限公司，台北，民94。
[3] 新華電腦，ARM9 S3C2410嵌入式SOC實作，初版，全華科技股份有限公司，台北，民94。
[4] 新華電腦，Embedded Linux在ARM9 S3C2410（PreSOCes）上實作，初版，全華科技股份有限公司，台北，民94。
[5] ARM Corporation, http://www.arm.com
[6] J.-C. Latombe, Robot Motion Planning, Kluwer Academic, 1991.
[7] J. A. Reeds and R. A. Sheep, “Optimal path for a car that goes both forward and backward, ” Pacific J. Marth., vol. 145, no. 2, pp. 367-393, 1990.
[8] D. Gu and H. Hu, “Neural predictive control for a car-like mobile robot,” Int. Journal of Robotics and Autonomous Systems, vol. 39, no. 2-3, May 2002.
[9] J. P. Laumond, P. E. Jacobs, M. Taix, and R. M. Murry, “A motion planner for nonholonomic mobile robots,” IEEE Trans. Robotics and Automation, vol. 10, no. 5, Oct. 1994.
[10] H. Haddad, M. Khatib, S. Lacroix, and R. Chatila, “Reactive navigation in outdoor environments using potential fields,” in Proc. of IEEE Int. Conf. Robotics and Automation, vol. 2, pp. 1232 -1237, 1998.
[11] P. Veelaert and W. Bogaerts, “Ultrasonic potential field sensor for obstacle avoidance,” IEEE Trans. Robotics and Automation, vol. 15, no. 4, Aug. 1999.
[12] K. Sugihara and J. Smith, “Genetic algorithms for adaptive motion planning of an autonomous mobile robot,” in Proc. of IEEE Int. Symposium Computational Intelligence in Robotics and Automation, pp.138 -143, 10-11 July, 1997.
[13] T. H. S. Li, M. S. Chiang, and S. S. Jian, “Motion planning of an autonomous mobile robot by integrating GA and fuzzy logic control,” in Proc. of the 9th IEEE Int. Conf. of Fuzzy Systems, vol. 2, pp.933-936, 2000.
[14] S. H. Kim, C. Park, and F. Harashima, “A self-organized fuzzy controller for wheeled mobile robot using an evolutionary algorithm,” IEEE Trans. Industrial Electronics, vol. 48, no.2, pp. 467-474, 2001.
[15] Y. K. Na and S. Y. Oh, “Hybrid control for autonomous mobile robot navigation using neural network based behavior modules and environment classification,” Autonomous Robots, vol. 15, no. 2, pp.193-206, Sept. 2003.
[16] C. J. Taylor and D. J. Kriegman, “Vision-based motion planning and exploration algorithms for mobile robots,” IEEE Trans. Robotics and Automation, Vol.14, No.3, pp. 417-426, June 1998.
[17] J. H. Chuang and N. Ahija, “An analytically tractable potential field model of free space and its application in obstacle avoidance,” IEEE Trans. Systems, Man, and Cybernetics, Part B, vol. 28, no. 5, pp. 729-736, Oct. 1998.
[18] J. H. Chuang, “Potential-based modeling of three-dimensional workspace for obstacle avoidance,” IEEE Trans. Robotics and Automation, vol. 14, no. 5, pp. 778-785, Oct. 1998.
[19] S. S. Ge and Y. J. Cui, “New potential functions for mobile robot path planning,” IEEE Trans. Robotics and Automation, vol. 16, no. 5, pp. 615-620, Oct. 2000.
[20] Y. Koren and J. Borenstein, “Potential field methods and their inherent limitations for mobile robot navigation,” in Proc. IEEE Int. Conf. Robotics and Automation, vol. 2, pp. 1398-1404, April 1991.
[21] P. Turennout, G. Honderd, and L. J. Schelven, “Wall-following control of a mobile robot,” in Proc. IEEE Int. Conf. Robotics and Automation, vol. 1, pp. 280-285, May 1992.
[22] X. Yun and K. C. Tan, “A wall-following method for escaping local minima in potential field based motion planning,” in Proc. IEEE Int. Conf. Advanced Robotics, pp. 421-426, July. 1997.
[23] 蘇木春、張孝德，機器學習：類神經網路、模糊系統以及基因演算法則，全華科技股份有限公司，民91。
[24] 周鵬程，遺傳演算法原理與應用—活用Matlab，修訂版，全華科技股份有限公司，民94。
[25] W. G. Han, S. M. Beak, and T. Y. Kuc, “Genetic algorithm based path planning and dynamic obstacle avoidance of mobile robots,” in Proc. of IEEE Int. Conf. System, Man, and Cybernetics, vol. 3, pp. 2747-2751, Oct. 1997.
[26] K. Sugihara and J. Smith, “Genetic algorithms for adaptive motion planning of an autonomous mobile robot,” IEEE Int. Symposium Computational Intelligence in Robotics and Automation, pp. 138-143, July 1997.
[27] Y. Hu and S. X. Yang, “A knowledge based genetic algorithm for path planning of a mobile robot,” in IEEE Int. Conf. Robotics and Automation, vol. 5, pp. 4350-4355, April 2004.
[28] T. Lozano-Perez and M. Wesley, “An algorithm for planning collision-free paths among polyhedral obstacles,” Commun. ACM, vol. 22, pp. 560-570, 1979.
[29] J. P. Laumond, “Finding collision-free smooth trajectories for a non-holonomic mobile robot,” in Proc. of the 10th Int. Joint Conf. Artificial Intelligence, pp. 1120-1123, 1987.
[30] A. Scheuer and Th. Fraichard, “Continuous-curvature path planning for car-like vehicles,” in Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, vol. 2, pp. 997-1003, Sept. 1997.
[31] A. Scheuer and Th. Fraichard, “From Reeds and Shepp’s to continuous-curvature paths,” IEEE Trans. Robotics, vol. 20, no. 6, pp. 1025-1035, Dec. 2004.
[32] 黃文增（譯），Jean J. Labrosse著，嵌入式系統構件Embedded Systems Building Blocks，初版，全華，台北，民93。
[33] 范逸之、江文賢、陳立元，C++ Builder與RS-232串列通訊控制，文魁資訊，民91。
[34] 范逸之、陳立元，Visual Basic與RS-232串列通訊控制最新版，文魁資訊，民90。