臺灣博碩士論文加值系統

最佳化路徑規劃是移動機器人研究重要議題之一。它是指在擁有障礙物的空間環境下，搜尋出一條從起點至目標點的較佳運動路徑，讓移動機器人不能與障礙物有任何碰撞，使之能安全通過，且為最短路徑。而本研究採用粒子群演算法來設計，其具有下列優點，包括：參數調整容易，以公式為主體而沒有太多繁瑣的過程，且能夠有效率地獲得全域最佳解。

首先，設計三種不同尺寸的環境地圖，其中每種地圖皆含兩種不同地形變化。其次，再結合開放式車輛路徑問題來討論移動機器人路徑規劃。模擬結果顯示：即使地圖含有地形變化與路由條件，粒子群會隨著迭代而找到最佳路徑，亦即其可以找到具最短時間的最佳路徑。

Optimal path planning is one of the important issues in mobile robot study. It tries to find the shortest path from the start point to the end point for a mobile robot and to avoid the collision with obstacles at the same time. This study adopts the Particle Swarm Optimization (PSO) algorithm to design the optimal path planning. This algorithm less owns the benefits of easy adjustment for parameters, tedious process based on the formula, and being able to efficiently to obtain the optimal global solution.
First, we design three classes of maps with different sizes. Therein, each map has two terrain changes. Moreover, we incorporate the Vehicle Routing Problem (VRP) in mobile robot path planning. Simulation results indicate that the particle swarm will find the optimal path even under terrain changes and routing conditions, that is to say, it can find the optimal path with the minimum time cost.

中文摘要
Abstract
誌謝
目錄
圖索引
表索引
第一章 緒論
1.1 研究背景與動機
1.2 研究議題
1.3 論文研究架構
第二章 預備知識
2.1 機器人路徑規劃
2.1.1 柵格法
2.2 車輛路徑問題(Vehicle Routing Problem)
2.2.1 車輛路徑問題定義
2.3 基因演算法(Genetic Algorithm)
2.4 粒子群演算法(Particle Swarm Optimization)
2.4.1 PSO背景
2.4.2 PSO基本原理
2.4.3 參數選擇
2.4.4 歸納比較
第三章 粒子群演算法之路徑規劃
3.1 路徑規劃之問題描述
3.2 演算法設計
3.2.1 環境建立
3.2.2 粒子群體初始化
3.2.3 插入與刪除
3.2.4 適應值函數
3.2.5 演算法設計
第四章 開放式車輛路徑問題
4.1 開放式車輛路徑問題之問題描述
4.2 開放式車輛路徑問題設計
4.2.1 設計想法
4.2.2 適應值函數
4.2.3 演算法設計
第五章 模擬結果
5.1 路徑規劃模擬
5.1.1 20×20地圖
5.1.2 30×30地圖
5.1.3 50×50地圖
5.2 開放式車輛路徑問題模擬
5.2.1 20×20地圖
5.2.2 30×30地圖
5.2.3 50×50地圖
第六章 結論與建議
6.1 結論
6.2 未來展望
參考文獻

[1] H.-C. Huang and C.-C. Tsai, “Global Path Planning for Autonomous Robot Navigation Using Hybrid Metaheuristic GA-PSO Algorithm,” Proceedings of SICE Annual Conference (SICE), pp. 1338-1343, 2011.

[2] Y. Hu, S. X. Yang, L.-Z. Xu, and M. Q.-H. Meng, “A Knowledge Based Genetic Algorithm for Path Planning in Unstructured Mobile Robot Environments,” IEEE International Conference on Robotics and Biomimetics (ROBIO), Shenyang, China, Aug. 22-26, 2004, pp. 767-772.

[3] Q. Li, Y. Tang, L.-J. Wang, C. Zhang, and Y. Yin, “A Specialized Particle Swarm Optimization for Global Path Planning of Mobile Robots,” Third International Workshop on Advanced Computational Intelligence (IWACI), Suzhou, China, Aug. 25-27, 2010, pp. 271-276.

[4] Z. Qian, M. Li, X.-S. Wang, “Global Path Planning Method of Mobile Robot in Uncertain Environment,” Chinese Control and Decision Conference (CCDC), Xuzhou, China, May 26-28, 2010, pp. 4320-4324.

[5] Y. Zhang, L. Zhang, X.-H. Zhang, “Mobile Robot Path Planning Base on the Hybrid Genetic Algorithm in Unknown Environment,” Eighth International Conference on Intelligent Systems Design and Applications (ISDA), Jinan, China, Nov. 26-28, 2008, pp. 661-665.

[6] M. Clerc and J. Kennedy, “The particle swarm - Explosion, Stability, and Convergence in a Multidimensional Complex Space,” IEEE Transactions on Evolutionary Computation, Vol. 6, No.1, pp. 58-73, 2002.

[7] A. K. H. Ali and M. A. Abidi, “A 2-D and 3-D Robot Path Planning Algorithm Based on Quadtree and Octree Representation of Workspace,” IEEE Conference Proceedings Southeastcon, Apr. 11-13, 1988, pp. 391-396.

[8] M. Brand, M. Masuda, N. Wehner, and Y. Xiao-Hua, “Ant Colony Optimization Algorithm for Robot Path Planning,” International Conference on Computer Design and Applications (ICCDA), Qinhuangdao, China, June 25-27, 2010, pp. 3536-3540.

[9] I. Chaari, A. Koubaa, H. Bennaceur, S. Trigui, and K. Al-Shalfan, “SmartPATH: A Hybrid ACO-GA Algorithm for Robot Path Planning,” IEEE World Congress on Evolutionary Computation (CEC), Brisbane, Australia, June 10-15, 2012, pp. 1-8.

[10] A. Ghorbani, S. Shiry, and S. Nodehi, “Using Genetic Algorithm for a Mobile Robot Path Planning,” International Conference on Future Computer and Communication (ICFCC), Kuala Lumpar, Malaysia, Apr. 3-5, 2009, pp. 164-166.

[11] T. Jianping and S. X. Yang, “Genetic Algorithm Based Path Planning for a Mobile Robot,” IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, Setp. 14-19, 2003, pp. 1221-1226.

[12] J. Zhao, L. Zhu, G.-F. Liu, G. Liu and Z.-F. Han, “A Modified Genetic Algorithm for Global Path Planning of Searching Robot in Mine Disasters,” International Conference on Mechatronics and Automation (ICMA), Changchun, China, Aug. 9-12, 2009, pp. 4936-4940.

[13] L. Lin, H.-J. Wang, and Q.-S. Wu, “Improved Genetic Algorithms Based Path Planning of Mobile Robot Under Dynamic Unknown Environment,” IEEE International Conference on Mechatronics and Automation , Luoyang, China, June 25-28, 2006, pp. 1728-1732.

[14] M.-Y. Ju and C.-W. Cheng, “Smooth Path Planning Using Genetic Algorithms,” 9th World Congress on Intelligent Control and Automation (WCICA), Taipei, Taiwan, June 21-25, 2011, pp. 1103-1107.

[15] K. Sugihara and J. Smith, “Genetic Algorithms for Adaptive Motion Planning of an Autonomous Mobile robot,” IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA), Monterey, California, USA , July 10-11, 1997, pp. 138-143.
[16] S. Zhao and M. Li, “Path Planning of Inspection Robot Based on Ant Colony Optimization Algorithm,” International Conference on Electrical and Control Engineering (ICECE) , Wuhan, China , June 25-27, 2010, pp. 1474-1477.

[17] Y.-R. Hu and S.-X. Yang, “A Knowledge Based Genetic Algorithm for Path Planning of a Mobile Robot,” IEEE International Conference on Robotics and Automation (ICRA), New Orleans, LA, USA, Apr. 2004, pp. 4350-4355.

[18] Fred W. Glover and M. Laguna, Tabu search, Springer, 1997.

[19] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man, and Cybernetics, Vol. 26, No. 1, pp. 29-41, 1996.

[20] M. Dorigo and L. M. Gambardella, ”Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66, 1997.

[21] M. Dorigo and C. Blum, “Ant Colony Optimization Theory: A Survey,” Theor. Comput. Sci., Vol. 344, pp. 243-278, 2005.

[22] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680, May 13, 1983.

[23] G.-E. Jan, K.-Y. Chang, and Parberry. Ian, “Optimal Path Planning for Mobile Robot Navigation,” IEEE/ASME Transactions on Mechatronics , vol. 13, No. 14, pp. 451-460, 2008.

[24] N. Takemura, Y. Nakamura, Y. Matsumoto, and H. Ishiguro, “A Path-Planning Method for Human-Tracking Agents Based on Long-Term Prediction,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 42, No. 6, pp. 1543-1554, 2012.

[25] L. Wang, Y.-S. Liu, H.-B. Deng, and Y.-Q. Xu, “Obstacle-Avoidance Path Planning for Soccer Robots Using Particle Swarm Optimization,” IEEE International Conference on Robotics and Biomimetics(ROBIO), Kunming, China, Dec. 17-20, 2006, pp. 1233-1238.

[26] B.-B. Meng and X.-G. Gao, “UAV Path Planning Based on Bidirectional Sparse A* Search Algorithm,” International Conference on Intelligent Computation Technology and Automation (ICICTA), Changsha, China, May 11-12, 2010, pp. 1106-1109.

[27] Z.-N. Dong, Z.-G. Chen, R. Zhou, and R.-L. Zhang, “A Hybrid Approach of Virtual Force and A* Search Algorithm for UAV Path Re-Planning,” 6th IEEE Conference on Industrial Electronics and Applications (ICIEA), Beijing, China, June 21-23, 2011, pp. 1140-1145.

[28] H.-Q. Min, J.-H. Zhu, X.-J. Zheng, “Obstacle Avoidance with Multi-Objective Optimization by PSO in Dynamic Environment,” International Conference on Machine Learning and Cybernetics, Guangzhou, China, Aug. 18-21, 2005, pp. 2950-2956.

[29] P. Raja and S. Pugazhenthi, “Path Planning for Mobile Robots in Dynamic Environments Using Particle Swarm Optimization,” International Conference on Advances in Recent Technologies in Communication and Computing, Kottayam, Kerala, India, Oct. 27-28, 2009, pp. 401-405.

[30] S. M. A. Salehizadeh, P. Yadmellat, and M. B. Menhaj, “Local Optima Avoidable Particle Swarm Optimization,” IEEE Swarm Intelligence Symposium, Mar. 30-Apr. 2, 2009, pp. 16-21.

[31] L. P. Tomas, “Automatic Planning of Manipulator Transfer Movements,” IEEE Transactions on Systems, Man and Cybernetics, Vol. 11, No. 10, pp. 681-698, 1981.

[32] S. S. Ge and Y. J. Cui, “New Potential Functions for Mobile Robot Path Planning,” IEEE Transactions on Robotics and Automation, Vol. 16, No. 15, pp. 615-620, 2000.

[33] Y. Koren and J. Borenstein, “Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation,” IEEE International Conference on Robotics and Automation, Sacramento, California, Apr. 9-11, 1991, pp. 1398-1404.

[34] K.-C. Fan and P.-C. Lui, “Solving Find Path Problem in Mapped Environments Using Modified A* Algorithm,” IEEE Transactions on Systems, Man and Cybernetics, Vol. 24, No. 6, pp. 1390-1396, 1994.

[35] M. Noto and H. Sato, “A Method for the Shortest Path Search by Extended Dijkstra Algorithm,” IEEE International Conference on Systems, Man, and Cybernetics, Nashville, Tennessee, Oct. 8-11, 2000, pp. 2316-2320.

[36] F. Wang and B. Lu, “The Robot Path Planning Based on PSO Algorithm Integrated with PID,” International Conference on Information Engineering and Computer Science (ICIECS), Wuhan, China, Dec. 19-20, 2009, pp. 1-4

[37] K.-Y. Lei, Y.-H. Qiu, and Y. He, “A Novel Path Planning for Mobile Robots Using Modified Particle Swarm Optimizer,” 1st International Symposium on Systems and Control in Aerospace and Astronautics (ISSCAA), Harbin, China, Jan. 19-21, 2006, pp. 981-984.

[38] Y. Tang, Q. Li, L.-J. Wang, C. Zhang, and Y.-X. Yin, “An Improved PSO for Path Planning of Mobile Robots and its Parameters Discussion,” International Conference on Intelligent Control and Information Processing (ICICIP), Dalian, China, Aug. 13-15, 2010, pp. 34-38.

[39] N. ZakeriNejad, A. H. Bakhtiary, and M. R. J. Motlagh, “Use of Particle Swarm Optimization in Path Planning for Rough Terrain,” 19th International Workshop on Robotics in Alpe-Adria-Danube Region, Budapest, Hungary, June 23-25, 2010, pp. 205-209.

[40] M. Metea and J.-P. Tsai, “Route Planning for Intelligent Autonomous Land Vehicles Using Hierarchical Terrain Representation," IEEE International Conference on Robotics and Automation, May 1987, pp. 1947-1952.

[41] G. B. Dantzig and J. Ramser, “The Truck Dispatching Problem,” Management Science, vol.6, pp. 80-91, 1959.

[42] T. Davies and A. Jnifene, “Multiple Waypoint Path Planning for a Mobile Robot Using Genetic Algorithms,” IEEE International Conference on Computational Intelligence for Measurement Systems and Applications, La Coruna, Spain, July 12-14, 2006, pp. 21-26

[43] Y. Toda and N. Kubota, “Path Planning Using Multi-Resolution Map for a Mobile Robot,” Proceedings of SICE Annual Conference (SICE), Tokyo, Japan, Sep. 13-18, 2011, pp. 1276-1281.

[44] F. Rubin, “A Search Procedure for Hamilton Paths and Circuits,” Journal of the Association for Computing Machinery, Vol. 21, No. 21, pp. 576-580, 1974.

[45] J. H. Holland, Adaptation in natural and artificial systems, MIT Press, 1992.

[46] D. E. Goldberg, “Genetic Algorithm in Search. Optimization and Machine Learning,” Addision-Wesley, New York , 1989.

[47] J. Kennedy and R. Eberhart, “Particle Swarm Optimization,” IEEE International Conference on Neural Networks, Nov/Dec 1995, pp. 1942-1948.

[48] S. Yuhui and R. Eberhart, “A Modified Particle Swarm Optimizer,” IEEE International Conference on Evolutionary Computation, Computational Intelligence, Anchorage, Alaska, May 4-9, 1998, pp. 69-73.

[49] J.-B. Park, K.-S. Lee, J.-R. Shin, and K.-Y. Lee, “A Particle Swarm Optimization for Economic Dispatch with Nonsmooth Cost Functions,” IEEE Transactions on Power Systems, Vol. 20, No. 1, pp. 34-42, 2005.

[50] J. Kennedy, “Small Worlds and Mega-Minds: Effects of Neighborhood Topology on Particle Swarm Performance,” Proceedings of the 1999 Congress on Evolutionary Computation, Washington, D.C, USA, July 6-9, 1999, pp. 1931- 1938.