機器人的發明是為了替代人類來從事需耗費大量人力的工作和在一些危險環境下工作之人員。隨著機器人的功能逐漸強大，機器人的發展趨勢從單一機器人獨立完成任務演變成由多機器人團隊透過分工合作完成複雜的任務。而我們運用多機器人處理複雜工作的同時，必須考慮到工作分配(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.

[1] 王維漢，“智慧機器人技術專輯主編前言”，機械工業雜誌，281期.
[2] iRobot, http://store.irobot.com/corp/index.jsp.
[3] WowWee,http://www.wowwee.com/.
[4]E.W. Justh, P.S. Krishnaprasad,“A Simple Control Law for UAV Formation Flying ”, Institute for Systems Research Technical Reports ,2002.
[5]T. Balch, R.C Arkin ,“behavior-based formation control for multi-robot
teams ”, Robotics and Automation, Vol. 6, Issue 14, pp.926-939,1998.
[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.
[10]Marco Dorigo,”Positive Feedback as a Search Strategy ” Technical Report 91-016,Dipartmento di Elettronica,Politecnico di Milano,IT,1991.
[11]Marco Dorigo,”Ant Algorithms for Discrete Optimization ” Artificial Life,Vol. 5,No. 2,pp. 137-172,1999.
[12] Marco Dorigo,”Optimization, Learning and Natural Algorithms” Ph. D Thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy,1992.
[13] Bullnheimer,C.Stauss,”A New Rank Based Version of the Ant System –A Computational Study” Technical Report POM-03/97, Institute of Management Science, University of Vienna,Austria,1999.
[14]Taillard, E.D and L.M. Gambardella,”Adaptive Memories for the Quadratic Assignment Problem” Technical Report IDSIA-87-97, Lugano,1997.
[15] Stutzle, T. and H. Hoos,”Improvement on the Ant System: Introduction the MAX-MIN Ant System” In R.F Albrecht G.D.Smith, N.C.Steele, editors, Artificial Neural Networks and Genetic Algorithms, pp.245-249, Springer Verlag,New York,1998.
[16]Maniezzo,V.”Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem” Technical Report CSP 98-1,Universita di Bologna,Italy,1998.
[17]CX.Botelho and R.Alami,”M+:A scheme for multi-robot cooperation through negotiated task allocation and achievement” In Proceedings of the 1999, IEEE International Conference on Robotics and Automation , pp.1234-1239,1999.
[18]T.Dahl,M.J.Mataric,and G.S.Sukhatme,” Multi-Robot Task Allocation through Vacancy Chains” IEEE International Conference on Robotics and Automation.2003.
[19]Z.J.Czech and Piotr Czarnas,”Parallel Simulated Annealing for the Vehicle Routing Problem With Time Windows” Proc. 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands, Spain, pp. 376-383.2002.
[20]Yi Guo and Lynne E.parker,”A distributed and optimal motion planning approach for multiple mobile robots”, Proceedings of IEEE international Conference on Robotics & Automation.2002.
[21]Amui,”Multi-Robot Path Planning for Dynamic Environments: A case study” Proceedings of IEEE international Conference on Intelligent Robots and Systems, pp 1245-1250,2001.
[22]B.Gerkey and M.Mataric,”Sold! auction methods for multi-robot coordination”IEEE Transaction on Robotics and Automation ,vol.18 , no.5
758-768,2002.
[23]R.Simmons, D.Apfelbaum, W.Burgard, and D.Fox”Coordination for multi-robot exploration and mapping”Proceedings of the National Conference on Artificial Ingelligence,pp.852-858,2000.
[24]M.Berhault, H.Huang, and A .Kleywegt,” Robot exploration with
combinatorial auction”Proceedings of the International Conference on Intelligent Robots and Systems,vol.2,pp.1957-1962,2003.
[25]L.Lin and Z.Zheng,”Combinatorial bids based multi-robot task allocation method”Proceedings of the IEEE International Conference on Robotics and Automation,pp.1145-1150,2005.
[26]S.N.Maheshwari and S.Kapoor,”Efficiently constructing the visibility graph of a simple polygon with obstacles”SIAM Journal on Computing,vol.30,pp.847-871,2000.
[27]B.R.Donald.”Motion Planning with six degrees of freedom”Technical Report AIM-791,MIT Artificial Intelligence Laboratory,1984.
[28]K.L.Trovato and L.Dorst,”Differential A*”,IEEE Transactions on Knowledge and Data Engineering,vol.14,pp.1218-1299,2002.
[29]S.S.Ge,and Y.J.Cui,”New potential functions for mobile robot path planning”IEEE Transactions on Robotics and Automation, vol.16, no5,pp.
915-620,2000
[30]N.W.Wu,”A potential field based method for path planning of autonomous guided vehicles”M.S Thesis,Department of Electrical Engineering,National Yunlin University of Science and Technology,2004.
[31]Y.Koren and J.Borenstein,”Potential field methods and their inherent limitations for mobile robot navigation”Proceedings of the IEEE International Conference on Robotics and Automation,pp.1398-1404,1991.
[32]P.Turennout,and M.C.Lee,”Obstacle avoidance for mobile robots using artificial potential field approach with simulated annealing”Proceedings of
the IEEE International Symposium on Industrial Electronics ,pp. 1530-15
35,2001.
[33]P.Vadallepat,T.C.Kay,and M.L.Wang,”Evolutionary artificial potential fields and their application in real time robot path”Proceedings of IEEE
Congress on Evolutionary Computation,pp.256-263,2000.
[34]蕭宗勝,”螞蟻族群演算法應用在組合問題之研究”,銘傳大學資訊管理研究所碩士論文,2002.
[35]Li Ping,Yang Yi-Ming,and KangHui,”Task Allocation Based on Market and Limited-Task Tree for Multirobot System,”Chinese Control and Decision Conference,pp.909-913,2008.
[36]Sang-Hyun Nam,Ik-Sang Shin,Jae-Jun Kim,and Soon-Geul Lee,”Complete Coverage Path Planning for Multi-Robots Employing Flow Networks, ” Interna-
tional Conference on Control,Automation and Systems,pp.2117-2120,2008.