移動機器人為具有可靈活移動特性的載具，配合定位與導航等技術，可讓機器人認知自身的環境位置並能自主性地移動。多個移動機器人相互協調合作，各個機器人之間的感測器訊息可有效的互補，系統將有更好的空間分佈與工作效率，可以更有效率地完成許多單一機器人難以完成的任務。
本論文旨在探討多個移動機器人之間如何藉由溝通與協調合作使群體在行進過程中保持特定的隊形，並在前往既定目標或軌跡的同時，設法避開環境中的障礙物，系統並建立隊形的容錯機制以解決隊形中出現機器人故障時的問題。多個移動機器人以跟隨領導者法的概念，將群體中的機器人組成階層式隊形，並以各機器人的速度和曲率限制，確保隊形的穩定性。模擬環境中以凸形封包建立模擬環境中任意形狀的障礙物，並藉由各種行為演算法則，使得階層式隊形中的領導者與跟隨者相互協調完成整個多機器人群體的協調控制。本論文並提出以圖形理論的深度優先搜尋法概念使得階層式隊形在機器人故障時，設法以最小的變動和影響將隊形重建，實現階層式隊形的容錯控制，模擬結果以圖形理論與隊形誤差描述與分析整個系統的控制性能。

Mobile robots are high mobility vehicles which can explore the environment autonomously and discover the position of robot itself by adopting the localization and navigation techniques. Through the coordination between robots, the information provided by sensors on each robot can be utilized more efficiently; also, the system will have better efficiency and space coverage to fulfill the mission which is difficult to achieve for a single robot.
This thesis is dedicated to exploit the communication and coordination in multiple mobile robots in order to maintain the specific formation. In addition, the formation needs to possess the obstacle avoidance mechanism for the robots while approaching the target or following the trajectory; besides, the formation requires the fault tolerance mechanism to overcome the problems when one or some robots break down in the formation. Based on the method of leader-follower, robots are controlled to form a hierarchical formation and maintain the formation through the constraints on velocity and curvature of each robot. In the simulation environment, the random shape obstacles are constructed by using convex hull, and the formation control is accomplished by algorithms for coordination behavior of leader and followers in the hierarchical formation. This thesis also proposes a depth-first search algorithm based fault tolerance control which enables the hierarchical formation to reconstruct the formation at the least variation and influence while there is a robot breaks down. The simulation results are provided to illustrate the coordinate control methods.

[1] B.D.O. Anderson, Y. Changbin, B. Fidan, and J. M. Hendrickx, “Rigid Graph Control Architectures for Autonomous Formations,” IEEE Control Systems Magazine, Vol. 28, No. 6, pp. 48-63, 2008.
[2] T. Balch and R. C. Arkin, “Behavior-Based Formation Control for Multirobot Teams,” IEEE Transactions on Robotics and Automation, Vol.14, pp. 926-939, 1998.
[3] C. B. Barber, D. P. Dobkin, and H. Huhdanpaa, “The Quickhull Algorithm for Convex Hulls,” ACM Transactions on Mathematical Software, Vol. 22, No. 4, pp. 469-483, 1996.
[4] W. Burgard, M. Moors, C. Stachniss, and F. E. Schneider, “Coordinated Multi-Robot Exploration,” IEEE Transactions on Robotics, Vol. 21, No. 3, pp. 376-386, 2005.
[5] Z. Cao, M. Tan, S. Wang, Y. Fan, and B. Zhang, “The Optimization Research of Formation Control for Multiple Mobile Robots,” in Proceedings of the 4th World Congress on Intelligent Control and Automation, pp. 1270-1274, 2002.
[6] D. R. Chand and S. S. Kapur, “An Algorithm for Convex Polytopes,” Journal of the Association for Computing Machinery, Vol. 17, No. 1, pp. 78-86, 1970.
[7] L. Consolinia, F. Morbidib, D. Prattichizzob, and M. Tosquesc, “Leader–Follower Formation Control of Nonholonomic Mobile Robots with Input Constraints,” Automatica, Vol. 44, No. 5, pp. 1343-1349 , 2008.
[8] L. Consolini, F. Morbidi, and D. Prattichizzo, “Stabilization of a Hierarchical Formation of Unicycle Robots with Velocity and Curvature Constraints,” IEEE Transactions on Robotics, Vol. 25, No. 5, pp. 1176-1184, 2009.
[9] J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage Control for Mobile Sensing Networks,” IEEE Transactions on Robotics and Automation, Vol. 20, NO. 2, 2004.
[10] D. Cruz, J. McClintock, B. Perteet, O.A.A. Orqueda, Y. Cao, and R. Fierro, “Decentralized Cooperative Control - A Multivehicle Platform for Research in Networked Embedded Systems,” IEEE Control Systems Magazine, Vol. 27 , No. 3 pp. 58-78, 2007.
[11] J.P. Desai, “A Graph Theoretic Approach for Modeling Mobile Robot Team Formations,” Journal of Robot Systems, Vol. 19, No. 11, pp. 511-525, 2002.
[12] J. P. Desai, J. P. Ostrowski, and V. Kumar, “Modeling and Control of Formations of Nonholonomic Mobile Robots,” IEEE Transactions on Robotics and Automation, Vol. 17, No. 6, pp. 905-908, 2001.
[13] W. B. Dunbar and R. M. Murray, “Model Predictive Control of Coordinated Multi-Vehicle Formations,” in Proceedings of the 41st IEEE Conference on Decision and Control, pp. 4631-4636, 2002.
[14] W. B. Dunbar and R. M. Murray, “Distributed Receding Horizon Control for Multi-Vehicle Formation Stabilization,” Automatica, Vol. 42, No. 4, pp. 549-558, 2006.
[15] F. Fahimi, “Sliding-Mode Formation Control for Underactuated Surface Vessels,” IEEE Transactions on Robotics, Vol. 23, No. 3, pp. 617-622, 2007.
[16] A. Farinelli, L. Iocchi, and D. Nardi, “Multi-Robot Systems: A Classification Focused on Coordination,” IEEE Transactions on System Man and Cybernetics, Vol. 34 , No. 5, pp. 2015-2028, 2004.
[17] E. Fiorelli, N.E. Leonard, P. Bhatta, D. A. Paley, R. Bachmayer, and D.M. Fratantoni, “Multi -AUV Control and Adaptive Sampling in Monterey Bay,” IEEE Journal of Oceanic Engineering, Vol. 31, No. 4, pp. 935-948, 2006.
[18] R. L. Graham, “An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set,” Information Processing Letters, Vol. 1, No. 4, pp. 132-133, 1972.
[19] Y. Gu, B. Seanor, G. Campa, M. R. Napolitano, L. Rowe, S. Gururajan, and S. Wan, “Design and Flight Testing Evaluation of Formation Control Laws,” IEEE Transactions on Control Systems Technology, Vol. 14, No. 6, pp. 1105-1112, 2006.
[20] M. Ji, A. Muhammad, and M. Egerstedt, “Leader-Based Multi-Agent Coordination: Controllability and Optimal control,” in Proceedings of the 2006 American Control Conference, pp. 1358-1363, 2006.
[21] O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,” The International Journal of Robotics Research, Vol. 5, No. 1, pp. 90-98, 1986.
[22] Y. Kui, L. Yuan, and F. Li-Xin, “Multiple Mobile Robot Systems: A Survey of Recent Work,” Acta Automatica Sinica, Vol. 33, No. 8, pp. 785-794, 2007.
[23] Y. Kuwata, A. Richards, T. Schouwenaars, and J. How, “Robust Constrained Receding Horizon Control for Trajectory Planning,” in Proceedings of the AIAA Guidance, Navigation, and Control Conference, 2005.
[24] J. Lavaei, A. Momeni, and A. G. Aghdam, “A Model Predictive Decentralized Control Scheme With Reduced Communication Requirement for Spacecraft Formation,” IEEE Transactions on Control Systems Technology, Vol. 16, No. 2, pp. 268-278, 2008.
[25] J. Leitner, “Multi-Robot Cooperation in Space: A Survey,” in Proceedings of the 2009 Advanced Technologies for Enhanced Quality of Life, pp. 144-151, 2009.
[26] Y. Lei, Q. Zhu, X. Leng, Z. Feng, and J. Song, “The Application of Fuzzy Neural Networks in Formation Control for Multi-Robot System,” in Proceedings of the 2008 IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application, pp. 69-73, 2008.
[27] 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.
[28] M. Lindhe, P. Ogren, and K. H. Johansson, “Flocking with Obstacle Avoidance: A New Distributed Coordination Algorithm Based on Voronoi Partitions,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1785-1790, 2005.
[29] B. Liu, R. Zhang, and C. Shi, “Formation Control of Multiple Behavior-based robots,” in Proceedings of the IEEE International Conference on Computational Intelligence and Security, pp. 544-547, 2006.
[30] S. Mastellone, D. M. Stipanović, C. R. Graunke, K. A. Intlekofer, and M. W. Spong, “Formation Control and Collision Avoidance for Multi-agent Non-holonomic Systems: Theory and Experiments,” International Journal of Robotics Research Archive, Vol. 27, No. 1, pp. 107-126, 2008.
[31] P. Ogren and N.E. Leonard, “Obstacle avoidance in Formation”, in Proceedings of the 2003 IEEE International Conference on Robotics and Automation, pp. 2492-2497, 2003.
[32] R. Olfati-Saber and R. M. Murray, “Graph Rigidity and Distributed Formation Stabilization of Multi-Vehicle Systems,” in Proceedings of the 41st IEEE Conference on Decision and Control, pp. 2965-2971, 2002.
[33] F. P. Preparata and S. J. Hong, “Convex Hulls of Finite Sets of Points in Two and Three Dimensions,” Communications of the ACM, Vol. 20, No. 1, pp. 87-93, 1977.
[34] A. Richards and J. How, “Decentralized Model Predictive Control of Cooperating UAVs,” in Proceedings of the IEEE Conference on Decision and Control, pp. 4286-4291, 2004.
[35] E. Rimon and D. E. Koditschek, “Exact Robot Navigation using Artificial Potential Functions,” IEEE Transactions on Robotics and Automation, Vol. 8, No. 5, pp. 501-518, 1992.
[36] R. Rocha, J. Dias, and A. Carvalho, “Cooperative Multi-Robot Systems: A Study of Vision-Based 3-D Mapping using Information Theory,” Robotics and Autonomous Systems, Vol. 53, No. 3-4, pp. 282-311, 2005.
[37] J. Shao, G. Xie, J. Yu, and L. Wang, “Leader-following Formation Control of Multiple Mobile Robots,” in Proceedings of the 2005 IEEE International Symposium on Intelligent Control, pp. 808-813, 2005.
[38] G. Shi and H. Fang, “Fault Tolerance of Multi-Robot Formation Based on Adjacency Matrix,” Journal of Huazhong University of Science and Technology, Vol.33, No.3, pp. 39-42, 2005
[39] S. Spry and J. K. Hedrick, “Formation Control using Generalized Coordinates,” in Proceedings of the 43rd IEEE Conference on Decision and Control, pp. 2441-2446, 2004.
[40] D. M. Stipanović, P. F. Hokayem, M. W. Spong, and D. D. Šiljak, “Cooperative Avoidance Control for Multiagent Systems,” Journal of Dynamic Systems, Measurement and Control, Vol. 129, No.5, pp. 699-707, 2007.
[41] H. G. Tanner and A. Kumar, “Towards Decentralization of Multi-robot Navigation Functions,” in Proceedings of the 2005 IEEE International Conference on Robotics and Automation, pp. 4132-4137, 2005.
[42] J. Wang, X.-B. Wu, and Z.-L. Xu, “Decentralized Formation Control and Obstacles Avoidance Based on Potential Field Method,” in Proceedings of the Fifth International Conference on Machine Learning and Cybernetics, pp. 803-808, 2006.
[43] P. K. C. Wang, “Navigation Strategies for Multiple Autonomous Mobile Robots Moving in Formation,” Journal of Robotic Systems, Vol. 8, No. 2, pp. 177-195, 1991.
[44] W. Wang and J. E. Slotine, “A Theoretical Study of Different Leader Roles in Networks,” IEEE Transactions on Automatic Control,” Vol. 51, No. 7, pp. 1156-1161, 2006.
[45] Z. Wang and D. Gu, “Distributed Leader-Follower Flocking Control,” Asian Journal of Control, Vol. 11, No. 4, pp. 396-406, 2009.
[46] D. B. West, Introduction to Graph Theory, 2nd Edition, Prentice Hall, 2001
[47] T. Zhang, X. Li, Y. Zhu, S. Chen, Y. Cheng, and J. Song, “Formation and Obstacle Avoidance in the Unknown Environment of Multi-Robot System,” in Proceedings of the 2009 IEEE International Conference on Robotics and Biomimetics, pp. 729-734, 2009.
[48] 林雍倫，多群組系統中利用位能場之分散式隊型控制，國立臺灣大學電機工程學系碩士論文，2005。
[49] 蔡自興、賀漢根、陳虹，未知環境中移動機器人導航控制理論與方法，21世紀先進製造技術叢書，科學出版社，中國，2009。
[50] 譚民、王碩、曹志強，多機器人系統，清華大學出版社，中國，2005。