本論文利用雙機器人實現滾球迷宮任務遊戲，其結合路徑規劃策略，即時影像分享與結合，雙機器人溝通與互動等功能與策略。滾球迷宮任務主要透過視覺影像資訊，結合雙機器人動作規劃，讓球由迷宮之起點，移動至迷宮終點。在任務過程中，機器人或許無法獲得迷宮之整體圖像，必須透過即時影像分享系統，整合圖像並規劃解決迷宮之路徑。因此，本論文提出一個影像分享系統，讓機器人互享彼此的影像資訊，透過影像校正與結合，整合出完整之迷宮圖像。為了解決迷宮路徑規劃之問題，本論文提出一個GA-PSO演算法。此演算法基於粒子群最佳化演算法(PSO)，再結合基因演算法(GA)的突變機制。當粒子在一段時間內都處於較差的適應值時，突變的機率將會被提高。本論文提出的粒子編碼方式，與其他演算法比較，能提升找到不經過障礙物路徑的機率。為了雙機器人間有效溝通與互動，本論文設計在遊戲過程中，機器人將會依其所得之資訊，交換領導者或追隨者之角色，讓系統可以即時做出有效之決策。本論文利用兩個實驗展現在不同情況下，雙機器人溝通合作之能力。在實驗一當中，兩個機器人所獲得之迷宮資訊是相同的，因此系統將指派一個機器人擔任領導者，另一個為追隨者。而在實驗二當中，迷宮上方放置隔板，機器人只能獲得靠近自身那邊的影像，因此，雙機器人必須溝通與傳遞訊息以結合迷宮影像，並且依據球的位置，交換其角色，實驗結果展現了機器人合作的有效性。

This thesis presents a method of robot cooperation for the ball maze game, which includes path planning strategy, real-time image sharing, robot communication and cooperation. The ball maze game requires the robots to plan a path from start point to end point in a maze, and the robots have to cooperate with each other to move the ball. In the process, the robots may have only partial image information of the maze, so this thesis proposes an image sharing system which allows the robots to do real-time exchange and merging of images. For the path planning problem, the thesis proposes a GA-PSO algorithm which is based on particle swarm optimization (PSO) and is combined with a mutation mechanism of genetic algorithm (GA). When the particles have a poor fitness value for a long time, the probabilities for mutation will increase. Compared with other algorithms, the proposed GA-PSO algorithm shows a better performance. In order to cooperatively accomplish the ball maze game, a cooperation method is proposed in which the robots communicate and exchange information with each other. In addition, the robots can change roles between leader and follower using the information they receive. There are two experiments in this thesis. In experiment I, both robots have the same information, so the system assigns roles to the robots. In experiment II, a white board is placed on the maze so the two robots can only see the maze on their own side. In this case, the roles of the robots may change during the game. The leader robot merges the maze images and finds a collision-free path. The experimental results demonstrate the effectiveness of robot cooperation.

[1] Y. Sakagami, R. Watanabe, C. Aoyama, S. Matsunaga, N. Higaki and K. Fujimura, “The intelligent ASIMO: System overview and integration,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 3, pp. 2478–2483, 2002.
[2] S. Chitta, E. G. Jones, M. Ciocarlie and K. Hsiao, “Perception, planning, and execution for mobile manipulation in unstructured environments,” IEEE Robotics and Automation Magazine, Special Issue on Mobile Manipulation, vol. 19, 2012.
[3] H. Tianyun, W. Xiaonan, C. Xuebo and X. Wangbao, “Architecture analysis and design of swarm robot systems based on the multi-task’s,” in Proceedings of the 27th Chinese Control Conference, pp. 300-304, 2008.
[4] F. D. Rango and N. Palmieri, “A swarm-based robot team coordination protocol for mine detection and unknown space discovery,” in Proceedings of the 8th International Wireless Communications and Mobile Computing Conference, pp. 703 -708, 2012.
[5] S. Chattunyakit, T. Kondo, I. Nilkhamhang, T. Phatrapornnant and I. Kumazawa, “Two foraging algorithms for a limited number of swarm robots,” in Proceedings of 52nd Annual Conference of the Society of Instrument and Control Engineers of Japan, pp. 1056-1061, 2013.
[6] G. Yahui and D. Xianzhong, “Kinematic cooperation analysis and trajectory teaching in multiple robots system for welding,” in Proceedings of Conference on Emerging Technologies & Factory Automation, pp. 1-8, 2011.
[7] L. Chaimowicz, T. Sugar, V. Kumar and M. F. Campos, “An architecture for tightly coupled multi-robot cooperation,” in Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3, pp. 2992-2997, 2001.
[8] Y. Wang and C. W. de Silva, “Sequential-learning with Kalman filtering for multirobot cooperative transportation,” IEEE/ASME Transactions on Mechatronics, vol. 15, pp. 261-268, 2010
[9] Y. Cai and S. X. Yang, “Fuzzy logic-based multi-robot cooperation for object-pushing,” in Proceedings of IEEE International Conference on Information and Automation, pp. 273-278, 2011.
[10] M. T. Khan and C. W. de Silva, “Autonomous fault tolerant multi-robot cooperation using artificial immune system,” in Proceedings of IEEE International Conference on Automation and Logistics, pp. 623-628, 2008.
[11] A. Viguria, I. Maza and A. Ollero, “S+ T: an algorithm for distributed multirobot task allocation based on services for improving robot cooperation,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 3163-3168, 2008.
[12] T. Liu and M. H. Meng, “Study on cooperation between humanoid robot Nao and Barrett WAM,” in Proceedings of IEEE International Conference on Robotics and Biomimetics, pp. 980-983, 2012.
[13] L. Ng and M. Reza Emami, “A concurrent approach to robot team learning,” in Proceedings of IEEE Workshop on Robotic Intelligence in Informationally Structured Space, pp. 50-57, 2013.
[14] L. E. Parker, “Decision making as optimization in multi-robot teams,” in Proceedings of IEEE International Conference on Distributed Computing and Internet Technology, pp. 35-49, 2012.
[15] D. Yingying, et al., “Introducing ‘Personality’ into the multi-robot cooperation,” in Proceedings of American Control Conference, pp. 5003-5008, 2005.
[16] B. Rahnama, M. C. Ozdemir, Y. Kiran and A. Elci, “Design and implementation of a novel weighted shortest path algorithm for maze solving robots,” in Proceedings of IEEE 37th Annual Computer Software and Applications Conference Workshops, pp. 328-332, 2013.
[17] M. S. Mahmud, U. Sarker, M. M. Islam and H. Sarwar, “A greedy approach in path selection for DFS based maze-map discovery algorithm for an autonomous robot,” in Proceedings of 15th International Conference on Computer and Information Technology, pp. 546-550, 2012.
[18] K. Lutvica, J. Velagic, N. Kadic, N. Osmic, G. Dzampo and H. Muminovic, “Remote path planning and motion control of mobile robot within indoor maze environment,” in Proceedings of IEEE International Symposium on Intelligent Control, pp. 1596-1601, 2014.
[19] Y. Murata and Y. Mitani, “A study of shortest path algorithms in maze images,” in Proceedings of SICE Annual Conference, pp. 32-33, 2011.
[20] D. Osmankovic and S. Konjicija, “Implementation of Q-Learning algorithm for solving maze problem,” in Proceedings of the 34th International Convention on MIPRO, pp. 1619-1622, 2011.
[21] D. J. Chitra, P. Karpagam and P. D. Manju, “Knowledge based reinforcement learning robot in maze environment,” International Journal of Computer Applications, vol. 14, pp. 22-30, 2011.
[22] Y. Tang, Q. Li, L. Wang, C. Zhang and Y. Yin, “An improved PSO for path planning of mobile robots and its parameters discussion,” in Proceedings of International Conference on Intelligent Control and Information Processing, pp. 34-38, 2010.
[23] Q. Zhang and S. Li, “A global path planning approach based on particle swarm optimization for a mobile robot,” in Proceedings of the 7th WSEAS International Conference on Robotics, Control & Manufacturing Technology, pp. 263-267, 2007.
[24] Y. Li and X. Chen, “Mobile robot navigation using particle swarm optimization and adaptive NN,” Advances in Natural Computation, vol. 3612. pp. 628-631, 2005.
[25] C. Purcaru, R. E. Precup, D. Iercan, L. O. Fedorovici and R. C. David, “Hybrid PSO-GSA robot path planning algorithm in static environments with danger zones,” in Proceedings of the 17th International Conference System Theory, Control and Computing, pp. 434-439, 2013.
[26] K. Premalatha and A. M. Natarajan, “Hybrid PSO and GA for global maximization,” International Journal of Open Problems in Computer Science and Mathematics, vol. 2, pp. 597-608, 2009.
[27] H. C. Huang and C. C. Tsai, “Global path planning for autonomous robot navigation using hybrid metaheuristic GA-PSO algorithm,” in Proceedings of SICE Annual Conference, pp. 1338-1343, 2011.
[28] W. Li and G. Y. Wang, “Application of improved PSO in mobile robotic path planning,” in Proceedings of International Conference on Intelligent Computing and Integrated Systems, pp. 45-48, 2010.
[29] M. Xue and C. Zhu, “The socket programming and software design for communication based on client/server,” in Proceedings of Pacific-Asia Conference on Circuits, Communications and Systems, pp. 775-777, 2009.
[30] Kinect for Windows. Available: http://www.microsoft.com/en-us/kinectforwindowsdev/default.aspx
[31] P. Jain, “An adaptive single seed based region growing algorithm for color image segmentation,” in Proceedings of Annual IEEE India Conference, pp. 1-6, 2013.
[32] B. D. Choi, J. W. Han, C. S. Kim and S. J. Ko, “Frame rate up-conversion using perspective transform,” IEEE Transactions on Consumer Electronics, vol. 52, pp. 975-982, 2006.
[33] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proceedings of IEEE International Conference on Neural Networks, pp. 1942-1948, 1995.
[34] D. Karaboga and B. Basturk, “A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm,” Journal of global optimization, vol. 39, pp. 459-471, 2007.
[35] J. Yao, C. Lin, X. Xie, A. J. Wang and C. C. Hung, “Path planning for virtual human motion using improved A* star algorithm,” in Proceedings of International Conference on Information Technology, pp. 1154-1158, 2010.
[36] ROBOTIS. Available: http://www.robotis.com/xe