機器人路徑規劃功能需考慮：最短路徑、避免與障礙物碰撞、平滑的路徑以及快速的運算處理，基本上是一最佳化的問題。故本論文提出一最佳路徑規劃的作法，利用基因演算法(Genetic Algorithm)所具備之最佳化搜尋能力，配合菁英化策略與路徑優化處理，有效提高收斂效率以及導航成功率。實驗結果證明，本論文所提出的路徑規劃法有效改進了傳統基因演算法，實現更安全、更高效率的機器人路徑規劃。以及考慮到近年來智慧型手機應用程式的普及化，本文將改良後的基因演算法實現在Android系統並應用於室內行動機器人導航，發展出讓人類與機器人的互動更為貼近的室內行動機器人導航App。

Path planning for mobile robots needs to consider several issues including the shortest path, obstacle avoidance, and computation efficiency, which can be regarded as an optimization problem. Taking advantage of the genetic algorithms to solve various optimization problems, this paper first proposes a Cooperative Genetic Optimization (CGO) Algorithm, including the establishment of an elite policy and larger selection region to minimize the occurrence of local optima so as to increase the speed of convergence. Based on the proposed CGO, a global path planning approach for robots is then presented. As a result, the proposed method leads to a better performance to reach the goal in terms of a safer and shorter path in comparison with the traditional genetic algorithm. Considering of App development is very popular recently. In this paper, App based development of robots path planning using Cooperative Genetic Optimization is a great contribution and innovation for development of indoor mobile robot navigation.

[1] C. Petres, Y. Pailhas, P. Patron,Y. Petillot, J. Evans, and D. Lane, “Path Planning for Autonomous Underwater Vehicles,” IEEE Transactions on Robotics, vol. 23, no. 2, pp. 331-341, Apr. 2007.
[2] I. Mas and C. Kitts, “Obstacle Avoidance Policies for Cluster Space Control of Nonholonomic Multirobot Systems,” IEEE/ASME Transactions on Mechatronics, vol. 17, no. 6, pp. 1068-1079, Dec. 2012.
[3] C. Keonyup, L. Minchae, and S. Myoungho, “Local Path Planning for Off-Road Autonomous Driving With Avoidance of Static Obstacles,” IEEE Transactions on Intelligent Transportation Systems, vol. 13, no. 4, pp. 1599-1616, Dec. 2012.
[4] P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol.4, no. 2, pp. 100-107, July. 1968.
[5] Y. Lu and X. Huo, “Incremental Multi-Scale Search Algorithm for Dynamic Path Planning With Low Worst-Case Complexity,” IEEE Transactions on Systems, vol. 41, no. 6, pp. 1556–1570, Dec. 2011.
[6] J. H. Holland, Adaptation in Natural and Artificial Systems. Ann Arbor, MI: Univ. Michigan Press, 1975.
[7] H.C. Lau, T.M. Chan, W.T. Tsui, and W.K. Pang, “Application of genetic algorithms to solve the multidepot vehicle routing problem,” IEEE Trans. Autom. Sci. Eng., vol. 7, no. 2, pp. 383–392, Apr. 2010.
[8] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol.1, no.1, pp 269-271, 1959.
[9] http://en.wikipedia.org/wiki/A*_search_algorithm
[10] Y. Lu and X. Huo, “A Beamlet-Based Graph Structure for Path Planning Using Multiscale Information,” IEEE Transactions on Automatic Control, vol. 57, no. 5, pp. 1166–1178, May. 2012.
[11] X. Huayang and Z. Mengjie, “Parent Selection Pressure Auto-Tuning for Tournament Selection in Genetic Programming,”, IEEE Transactions on Evolutionary Computation, vol. 17, no. 1, pp. 1-19, Feb. 2013.
[12] http://www.scielo.br/scielo.php?pid=S0104-66322008000400017&script=sci_arttext
[13] http://biology.about.com/od/basicgenetics/ss/gene-mutation.htm
[14] T.W. Manikas, K. Ashenayi, and R.L. Wainwright, “Genetic Algorithms for Autonomous Robot Navigation,” IEEE Instrumentation & Measurement Magazine, vol. 10, no. 6, pp. 26–31, Dec. 2007.
[15] N. Xie and H. Leung, “Reconstruction of Piecewise Chaotic Dynamic Using a Genetic Algorithm Multiple Model Approach,” IEEE Transactions on Circuits and System, vol. 51, no. 6, pp. 1210–1222, June. 2004.
[16] E.A.M. Cruz and A.S. Morris, “Fuzzy-GA-based trajectory planner for robot manipulators sharing a common workspace,” IEEE Transactions on Robotics, vol. 22, no. 4, pp. 613–624, Aug. 2006.
[17] F. Benavides, G. Tejera, M. Pedemonte, and S. Casella, “Real Path Planning based on Genetic Algorithm and Voronoi Diagrams,” IEEE IX Latin American and IEEE Colombian Conference on Automatic Control and Industry Applications, Bogota, Oct. 2011, pp. 1–6.
[18] M. Gemeinder and M. Gerke, “GA-based path planning for mobile robot systems employing an active search algorithm,” Appl. Soft Comput., vol. 3, no. 2, pp. 149-158, Sep. 2003.
[19] Cen. Zeng, Qiang. Zhang, and Xiaopeng. Wei, “GA-based Global Path Planning for Mobile Robot Employing A* Algorithm,” Journal of computers, vol. 7, no. 2, pp. 470–474, Feb. 2012.
[20] Y. Zhang, L. Zhang, and X. Zhang, “Mobile Robot Path Planning Base on the Hybrid Genetic Algorithm in Unknown Environment,” International Conference on Intelligent Systems Design and Applications, Kaohsiung, Nov. 2008, pp. 661–665.
[21] C.C. Tsai, H.C. Huang, and C.K. Chan, “Parallel Elite Genetic Algorithm and Its Application to Global Path Planning for Autonomous Robot Navigation,” IEEE Transactions on Industrial Electronics, vol. 58, no. 10, pp. 4813–4821, Oct. 2011.
[22] A.W. Iorio and X. Li, “A Cooperative Coevolutionary Multiobjective Algorithm Using Non-dominated Sorting,” Genetic and Evolutionary Computation Conference, Seattle, WA, USA, June. 2004, pp. 537–548.
[23] V.D.L Cueva and F. Ramos, “Cooperative genetic algorithms: a new approach to solve the path planning problem for cooperative robotic manipulators sharing the same work space,” IEEE Intelligent Robots and Systems, Victoria, Oct. 1998, pp. 267–272.
[24] http://en.wikipedia.org/wiki/Cooperative_coevolution
[25] 張文修、梁怡，遺傳算法的數學基礎，西安交通大學出版社，2000。
[26] 謝奇均，具遠端控制服務型移動機器人之研究，中原大學電機工程學系碩士論文，台灣，民國100年。
[27] http://zh.wikipedia.org/wiki/Android
[28] 曾吉弘、林毓祥、Juan Antonio，機器人程式設計與實作--使用JAVA，碁峯資訊，2010。
[29] 吳雅峰、蘇亞光，深入淺出Android遊戲程式開發範例大全，博碩文化，2011。
[30] http://iknow.stpi.narl.org.tw/Post/Read.aspx?PostID=9734
[31] http://shop.asus.com/store/asustw/zh_TW/pd/ThemeID.31533000/productID.280669900/categoryID.61631300
[32] 張真誠、蔡文輝、胡育誠，資料結構導論C語言實作，全華圖書公司，2007。
[33] http://www.mobilerobots.com/ResearchRobots/PioneerP3DX.aspx