改良式蟻群演算法在多機器人路徑規劃和工作分配之模擬研究

The Study on the Simulation of Improved Ant Colony Algorithm for Multi-Robot Path Planning and Task Allocation

陳維修(wei-hsiu chen)

指導教授 ： 莊謙本

國立臺灣師範大學/科技學院/工業教育學系/碩士(2010年)

摘要

機器人的發明是為了替代人類來從事需耗費大量人力的工作和在一些危險環境下工作之人員。隨著機器人的功能逐漸強大，機器人的發展趨勢從單一機器人獨立完成任務演變成由多機器人團隊透過分工合作完成複雜的任務。而我們運用多機器人處理複雜工作的同時，必須考慮到工作分配(Task Allocation)和路徑規劃(Path Planning)的問題。
在2008年的文獻中提出「蟻群演算法」(Ant Colony Algorithm)解決多機器人的工作分配和路徑規劃的問題。其選擇路徑策略係根據費洛蒙(嗅跡強度)的強度，但有些螞蟻會選擇區域最佳的路徑，而非全域最佳路徑，因此失去最好的解。本研究針對此問題提出改良式蟻群演算法解決多機器人的路徑規劃與工作分配的問題，並且設計一個區域路徑規劃的策略以防止機器人彼此間的碰撞問題。
本研究以全域情況作為機器人行動的判斷依據，經模擬實驗後，證實可找到全域最短路徑，並能成功避免機器人之間的碰撞。因此本改良式演算法可以用在靜態環境中多機器人的路徑規劃與工作分配。

關鍵字

多機器人 ； 工作分配 ； 路徑規劃

並列摘要

The invention of robots is to replace overwhelming work for human faculty in hazardous conditions. With the improvement of robot function, it makes the working style come from single robot completing a task independently to multi-robot completing a complex task. For the latter case, the task allocation and path planning should be considered in depth to optimize performance of working group.
The algorithm purposed for task allocation and path planning for multi- robot is called “Ant Colony Algorithm” by a research group in China in 2008. They used pheromone (strength of trail) of past ant to define optimal route for the next ant. But some ants may not be able to follow the optimal route due to their local optimization and not global optimization. This thesis purposed a modified method to find the best route for any ant in the group and they will avoid collision between each other when they are moving.
The experimental results show that any ant (robot) can move on optimal route according to global optimal computation and avoids collision according to local optimal computation. Its performance is better than former Ant Colony Algorithm. Therefore, it can be used for multi-robot task allocation and path planning in the case of static environment.

並列關鍵字

Multi-Robot ； Task Allocation ； Path Planning

參考文獻

[5]T. Balch, R.C Arkin ,“behavior-based formation control for multi-robot

[6]C.Y. Chen, T-H.S. Li,”A real-time role assignment mechanism for five-on-five robot soccer competition” IEEE International Conference Networking, Sensing and Control, Vol. 2, pp.1099-1104,2004.

[7]Taixiong Zheng, Liangyi Yang,”Optimal Ant Colony Algorithm based Multi-Robot Task Allocation and Processing Sequence Scheduling” IEEE International Conference , Control and Automation, June 25-27,2008.

[8] Marco Dorigo,” Optimization by a Colony of Cooperating Agents” IEEE Transaction on Systems,Vol. 26,No.1,pp.29-41,1996.

[9]Marco Dorigo,”Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman problem” IEEE Transactions on Evolutionary Computation,Vol. 1pp.53-66,1997.