臺灣博碩士論文加值系統

本論文提出一階層式的群組機器人路徑規劃方式，並使用彌集式演算法 (Memetic Algirothm) 作為搜尋最佳組態。所提出的階層式路徑規劃演算法中包含了整體路徑規劃與區域路徑規劃：整體路徑規劃使用范諾圖法來規劃群組機器人的主要移動方向，區域路徑規劃使用彌集式演算法規劃每一機器人從一組態到下一組態的移動路徑。
藉由整體路徑規劃演算法規劃出的機器人移動路徑資訊提供給彌集式演算法作為避障參考避免移動過程中機器人進入區域極小值 (local minimum)，彌集式演算法則用來產生最佳移動路徑，其中則以固定數量的基因 (Gene) 人口進行演化，並配置給群組機器人一連續性的移動路徑。移動最佳化的計算則是以群組機器人中心位置與范諾圖法當前目標點位置 (local goal) 間，計算兩者的梯度量並輸入演算法中來得到最佳移動位置的適應值 (fitness)，並將其最佳適應值保留至下一演化階段使用，因此就可以得到當前的最佳路徑位置。因此 MA 的區域路徑搜尋方式比上傳統的基因演算法 (Genetic algorithm) 則更有效率也更快速。最後實驗結果比較可以得知 MA 在計算速度優於 GA，且移動路徑更為平順。

In this paper, a hierarchical memetic algorithm (MA) is proposed for the path planning of swarm robots. The proposed algorithm consists of a global path planner (GPP) and a local motion planner (LMP). The GPP plans a trajectory within the voronoi diagram (VD) of the free space. A memetic algorithm with a non-random initial population plans a series of configurations along the path given by the former stage. The MA locally adjusts the robot positions to search for better fitness along the gradient direction of the distance between swarm robots and IGs. Once the optimal configuration is obtained, the better chromosomes will be reserved as the initial population for the next generation. Since the proposed MA is with non-random initial population and potential based local searching, it is more efficient and the planned path is faster than the traditional GA. Simulation result show that the proposed algorithm works well, specifically in terms of path smoothness and computation efficiency.

中文摘要 ……………………………………………………………………... i
英文摘要 ……………………………………………………………………... ii
誌謝 …………………………………………………………………………... iii
目錄 …………………………………………………………………………... iv
表目錄 …………………………………………………………………………... vi
圖目錄 …………………………………………………………………………... vii
符號說明 ……………………………………………………………………... ix
一、序論 1
1.1簡介 1
1.2機器人技術 2
1.3研究目的 6
1.4論文結構 8
二、群組機器人相關研究 9
2.1群組機器人系統 9
2.1.1 同質群組機器人系統 9
2.1.2 異質群組機器人系統 10
2.2路徑規劃系統 11
2.2.1 分散式控制路徑規劃系統 11
2.2.2 集中式控制路徑規劃系統 12
2.2.3 隨機式街圖PRM演算法 13
2.2.4 可視圖規劃法 14
2.2.5 細胞切割法 15
2.3隊形控制系統 17
2.3.1鋼體結構法(Virtual structure) 18
2.3.2頭領領導法(Leader following) 18
2.3.3基礎行為法(Behavior-based) 19
2.3.4位能場法(Potential field) 19
三、彌集式群組機器人路徑規劃演算法 22
3.1整體路徑規劃演算法(Global planning) 23
3.1.2范諾圖法 23
3.2區域路徑規劃演算法(Local planning) 27
四、實驗結果與分析 38
4.1模擬條件 39
4.2模擬結果 40
4.2.1場景一 40
4.2.2場景二 41
4.2.3場景三 41
4.2.4場景四 42
4.2.5場景五 44
4.3距離收斂比較 45
4.4 Memetic演算法強健性實驗 48
4.5 Mutation 與 Crossover 分析實驗 49
五、結論與未來展望 50
5.1結論 50
5.2未來發展 51
參考文獻 52

[1]白忠哲, "日本機器人專利與技術動向調查報告（一）," 工業技術研究院產經中心, 2007.
[2]C. C. Lin, P. Y. Hsiao, K. C. Chen., "A Motion Planning of Swarm Robots Using Genetic Algorithm," Proceedings of the 2010 International Conference on Broadband, Wireless Computing, Communication and Applications, pp. 538 - 543, 2010.
[3]L. E. Barnes, M. A. Fields, K. P. Valavanis., "Swarm formation control utilizing elliptical surfaces and limiting functions," IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 39, Issue:6, pp. 1434-1445, 2009.
[4]G. L. Mariottini, F. Morbidi, D. Prattichizzo, G. J. Pappas, K. Daniilidis., "Leader-Follower Formations: Uncalibrated Vision-Based Localization and Control," Proceedings of IEEE International Conference on Robotics and Automation, pp. 2403-2408, 2007.
[5]C. Belta and V. Kumar, "Optimal Motion Generation for Groups of Robots: A Geometric Approach," Journal of Mechanical Design, Vol. 126, Issue:1, pp. 63-70, 2004.
[6]Y. Zhang, F. B. Bastani, I. L. Yen., "Decentralized Path Planner for Multi-robot Systems," Proceedings of International Conference on Tools with Artificial Intelligence, pp. 171-175, 2009.
[7]J. Shao, G. Xie and L. Wang., "Leader-following formation control of multiple mobile vehicles," IET Control Theory & Applications, Vol. 1, Issue:2, pp. 545-552, 2007.
[8]G. Baldassarre, V. Trianni, M. Bonani, F. Mondada., "Self-Organized Coordinated Motion in Groups of Physically Connected Robots," IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 37, Issue:1, pp. 224-239, 2007.
[9]M. Yang, Y. Tian and X. Qi., "Behavior Analysis of Swarm Robot Systems Based on Vicsek Model," Proceedings of Fourth International Conference on Natural Computation, pp. 594-598, 2008.
[10]Y. Zhu, T. Zhang, and J. Song., "An improved wall following method for escaping from local minimum in artificial potential field based path planning," Proceedings of the 48th IEEE Conference on Decision and Control Conference. , pp. 6017-6022 , 2009.
[11]J. Lee, Y. Nam, S. Hong., "Random force based algorithm for local minima escape of potential field method," Proceedings of 11th International Conference on Control Automation Robotics & Vision (ICARCV), pp. 827-832, 2010.
[12]H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki, and S. Thrun., "Principles of Robot Motion: Theory, Algorithms, and Implementations," IEEE Robotics & Automation Magazine, Vol. 12 , Issue:3, pp.100, 2005.
[13]S. Xue and J. Zeng, "Sense Limitedly, Interact Locally: the Control Strategy for Swarm Robots Search," Proceedings of IEEE International Conference on Networking, Sensing and Control, pp. 402-407, 2008.
[14]D. J. Walton and D. S. Meek, "Cubic B′ezier spiral segments for planar G2 curve design," Proceedings of the 7th International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction, Africa, Franschhoek, South Africa, pp.21-26, 2010.
[15]C. M. Clark and T. D. Barfoot "Motion planning for formations of mobile robots," Robotics and Autonomous System,Vol. 46, Issue:2, pp. 65-78, 2004.
[16]J. Reif and H. Y. Wang "Social potential fields:A distributed behavioral control for autonomous robots," Robotics and Autonomous System, Vol. 27, Issue:3, pp. 171-194, May 1999.
[17]G. A. S. Pereira , V. Kumar, M. F. M. Campos, "Closed loop motion planning of cooperating mobile robots using graph connectivity," Robotics and Autonomous Systems, Vol. 56, Issue:4, pp. 373-384, April, 2008.
[18]L. E. Kavraki, P. Svestka, J. C. Latombe, M. H. Overmars,., "Probabilistic roadmaps for path planning in high-dimensional configuration spaces," IEEE Transactions on Robotics and Automation, Vol. 12, Issue:4, pp. 566-580, 1996.
[19]F. Lingelbach, "Path planning for mobile manipulation using probabilistic cell decomposition," Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol.3, pp. 2807-2812, 2004.
[20]R. V. Cowlagi and P. Tsiotras, "Kinematic feasibility guarantees in geometric path planning using history-based transition costs over cell decompositions," Proceedings of American Control Conference (ACC), pp. 5388-5393, 2010.
[21]M. A. Lewis and K. H. Tan, "High Precision Formation Control of Mobile Robots Using Virtual Structures," Autonomous Robots, Vol. 4, No. 4, pp. 387-403, 1997.
[22]A. Fujimori, T. Fujimoto, G. Boh?駢s., "Mobile robot formation control using a modified leader-follower technique," Integrated Computer-Aided Engineering, Vol. 15, No. 1, pp. 71-84, 2008.
[23]O. Khatib, "Real-time obstacle avoidance for manipulators and mobile robots," Proceedings of IEEE International Conference on Robotics and Automation., pp. 500-505, 1985.
[24]J. Barraquand, B. Langlois, and J. C. Latombe., "Numerical potential field techniques for robot path planning," Proceedings of Fifth International Conference on Advanced Robotics, Vol.2, pp. 1012-1017, 1991.
[25]V. Gazi and K. M. Passino, "Stability analysis of swarms," IEEE Transactions on Automatic Control, Vol. 48, pp. 692-697, 2003.
[26]X. P. Yun and K. C. Tan, "A wall-following method for escaping local minima in potential field based motion planning," Proceedings of International Conference on Advanced Robotics, pp. 421-426, 1997.
[27]R. Mahkovic and T. Slivnik, "Generalized local Voronoi diagram of visible region," Proceedings of IEEE International Conference on Robotics and Automation. , Vol.1, pp. 349-355, 1998.
[28]O. Takahashi and R. J. Schilling, "Motion planning in a plane using generalized Voronoi diagrams," IEEE Transactions on Robotics and Automation. , Vol. 5, Issue:2, pp. 143-150, 1989.
[29]R. Wein, J. P. V. D. Berg and D. Halperin., "The visibility--voronoi complex and its applications," Proceedings of the twenty-first annual symposium on Computational geometry, Pisa, Italy, pp.33-72, 2005.
[30]M. Pablo, "On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts - Towards Memetic Algorithms," Caltech Concurrent Computation Program 158-79, California Institute of Technology, 1989.
[31]M. S. Fontan and M. J. Mataric, "Territorial multi-robot task division," IEEE Transactions on Robotics and Automation, Vol. 14, Issue:5, pp. 815-822, 1998.
[32]L. Moreau, "Stability of multiagent systems with time-dependent communication links," IEEE Transactions on Automatic Control,, Vol. 50, Issue:2, pp. 169-182, 2005.
[33]M. Kloetzer and C. Belta, "Temporal Logic Planning and Control of Robotic Swarms by Hierarchical Abstractions," IEEE Transactions on Robotics, Vol. 23, Issue:2, pp. 320-330, 2007.