本論文針對多部移動機器人的隊形控制(formation control)議題，提出動態角色指定(dynamic role assignment)演算法。首先定義角色成本(character cost)，用以描述隊形中各機器人被指派為特定角色的難易程度。其次，以角色成本定義隊形中的角色組合適應性(character set fitness)。最後，依據角色組合適應性，選取隊形形成時最適合的角色組合。另外，當隊形變動時，機器人必須迴避行進路徑中的機器人以免碰撞，本論文也完成機器人避障機制的設計。設計的動態角色指定演算法與避障機制應用在全方位驅動機器人系統的隊形控制中。模擬與實測的結果顯示，相較於固定角色指定方法，所設計的動態角色指定演算法使隊形形成或變動過程更具效率。

In this thesis, a dynamic role assignment algorithm is proposed for formation control of multiple mobile robots. First, the degree of difficulty for a robot been assigned a specified character in a formation is defined as the character cost. Second, define the character set fitness of a robot formation by determining the character cost of each robot. Finally, select the best character set of a formation by calculating the character set fitness. Meanwhile, in the procedure of formation changing, an obstacle avoidance mechanism is designed in this research for robots to prevent collision between themselves. The developed dynamic role assignment algorithm and obstacle avoidance mechanism are applied to the formation control of a group omni-directional driven robots. Simulation and experimental results show that the performance the proposed dynamic role assignment algorithm is more efficient than that of fixed role assignment.

中文摘要		Ⅰ
英文摘要		Ⅱ
目錄		Ⅲ
圖目錄		Ⅴ
表目錄		Ⅶ
第一章	緒論	1
1.1研究動機	1
1.2相關文獻探討	1
1.3研究範圍	2
1.4論文架構	2

第二章	隊形控制相關理論	3
2.1隊形形狀	3
2.2隊形控制的參考形式	5
2.3機器人控制	6
2.4動態角色指定	9
2.5避障成本估算	13

第三章	機器人避障機制設計	16
3.1避障機制啟動條件	16
3.2避障候選點之選擇	19
3.3例外狀況的處理	20
3.4多重避障機制設計	23
3.5單一靜態障礙物避障模擬	28
3.6多障礙物避障模擬	30

第四章	隊形控制模擬	33
4.1角色成本參數選擇	33
4.2模擬條件與初始設定	34
4.3角色固定之隊形控制模擬	37
4.4動態角色指定之隊形控制模擬	41
4.5隊形切換模擬	41

第五章	機器人系統與實測	52
5.1機器人機構與外觀	52
5.2隊形控制系統	54
5.3避障機制實測	55
5.4隊形控制實測	59

第六章	結論與建議	64
6.1研究結果討論	64
6.2未來研究方向	64

參考文獻		66


圖2.1	機器人座標系	4
圖2.2	前導與後繼關係圖	4
圖2.3	隊形形狀	5
圖2.4	參考形式	6
圖2.5	全方位驅動機器人基本架構座標圖	8
圖2.6	機器人動態系統方塊圖	8
圖2.7	PID動態系統方塊圖	8
圖2.8	隊形形成示意圖	10
圖2.9	角色成本與角色組合	11
圖2.10	領隊角色成本估算	12
圖2.11	其他角色成本估算	12
圖2.12	三部機器人之角色成本與角色組合適應性	13
圖2.13	避障估算示意圖	14
圖2.14	兩線段間之關係圖	15
圖2.15	鄰近任三點之方向性	15
圖3.1	避障條件示意圖	17
圖3.2	避障完成示意圖	18
圖3.3	角度求算過程	18
圖3.4	避障啟動距離設計	19
圖3.5	向量避障方法	20
圖3.6	候選點計算方式	21
圖3.7	例外情形	23
圖3.8	多重避障情形	25
圖3.9	需要避障陣列	25
圖3.10	障礙物連接陣列	26
圖3.11	new bi陣列	26
圖3.12	a AND (NOT (new b2))	27
圖3.13	new a AND (NOT (new b7))	27
圖3.14	aed=108時SD對路徑之影響	29
圖3.15	aed=66.75時SD對路徑之影響	30
圖3.16	稀疏障礙物避障模擬圖	31
圖3.17	緊密障礙物避障模擬圖	32
圖3.18	複雜障礙場避障模擬圖	32
圖4.1	機器人假想避障路徑	35
圖4.2	模擬初始位置	36
圖4.3	目標隊形	36
圖4.4	固定角色指定模擬結果	40
圖4.5	隊形變換之領隊路徑	42
圖4.6	隊形形狀	42
圖4.7	固定角色指定之模擬結果	45
圖4.8	僅隊形形成時使用動態角色指定演算法之模擬結果	47
圖4.9	隊形形成與切換時使用動態角色指定演算法之模擬結果	50
圖5.1	全方位輪排列方式	52
圖5.2	由兩組轉換輪(Transwheel)所組成的全方位輪	52
圖5.3	全方位驅動機器人機構設計圖	53
圖5.4	全方位驅動機器人實體圖	53
圖5.5	足球機器人系統	54
圖5.6	隊形控制訊號處理流程	54
圖5.7	單一障礙物避障實測路徑	56
圖5.8	稀疏障礙物避障實測路徑	57
圖5.9	緊密障礙物避障實測路徑	58
圖5.10	領隊路徑命令	60
圖5.11	目標隊形	60
圖5.12	機器人辨識	60
圖5.13	固定角色指定實測結果	61
圖5.14	動態角色指定實測結果	62

表3.1	機器人參數	28
表3.2	模擬初始條件	29
表3.3	障礙物位置表	31
表4.1	機器人初始條件	35
表4.2	各種角色組合之安定時間	37
表4.3	角色組合矩陣與角色組合適應性	41
表4.4	Section 2之動態角色指定演算結果	48
表4.5	三種隊形切換方式之最大安定時間	51
表5.1	角色組合適應性	63
表5.2	10%安定時間	63

[1]	R.C. Arkin, Behavior-Based Robotics. MIT Press, 1998.
[2]	R.W. Beard, J. Lawton, and F.Y. Hadaegh, “A coordination architecture for spacecraft formation control,” IEEE Transactions on Control System Technology, vol. 9, no. 6, pp.777-790, November 2001.
[3]	T. Blach and R. C. Arkin, “Behavior-based formation control for multirobot teams,” IEEE Transactions on Robotics and Automation, vol. 14, no. 6, pp. 926-939, December 1998.
[4]	D.M. Bourg and G.Seemann, AI for Game Developers. O’Reilly Media Press, 2004.
[5]	A.K. Das, P. Fierro, V. Kumar, J.P. Ostrowski, J. Spletzer, and C. J. Taylor, “ A vision-based formation control framework,” IEEE Transactions on Robotics and Automation vol. 18, no. 5, pp. 813-825, October 2002.
[6]	J.P.	Desai, J.P. Ostrowski, and V. Kumar, “Modeling and Control of Formations of Noholonomic Mobile Robots,” IEEE Transactions on Robotics and Automation vol. 17, no. 6, pp.905-908, December 2001.
[7]	J.P. Desai, “A graph theoretic approach for modeling mobile robot team formations,” Journal of Robot Systems, vol. 19, no. 11, pp. 511-525, November 2002.
[8]	J. Fredslund and M.J. Mataric, “A general algorithm for robot formations using local sensing and minimal communication,” IEEE Transactions on Robotics and Automation, vol. 18, no. 5, pp. 837-846, October 2002.
[9]	D.E. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison-Wesley, Reading, Massachusetts, 1989.
[10]	J.H. Holland, “Adaptation in Natural and Artificial System,” Ann Arbor: The University of Michigan Press, 1975.
[11]	R. Horowitz and P. Varaiya, “Control design of an automated highway system,” Proceedings of the IEEE, vol. 88, no. 7, pp. 913-925, July 2000.
[12]	H.C.H. Hsu and A. Liu, 2005, “Applying various reference types to formation control of mobile robots,” Journal of Information Science and Engineering.
[13]	P.A. Ioannou, Ed., Automated Highway Systems. Plenum Press, 1997.
[14]	Kornylak Corporation http://kornylak.com/
[15]	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, October 1997.
[16]	T.H.S. Li, R.C. Liu, and I.F. Lin, “Fuzzy Shooting Control of Car-Like Soccer Robot,” Proceedings of IEEE TENCON’01 vol. 1, pp. 447-452, 2001.
[17]	D.P. Scharf, F.Y. Hadaegh, and S.R. Ploen, “A survey of spacecraft formation flying guidance and control (part I): Guidance,” Proceedings of the American Control Conference, vol. 2, pp. 1733-1739, June 2003.
[18]	P. Stone and M. Veloso, “Task decomposition, dynamic role assignment, and low-bandwidth communication for real-time strategic teamwork,” Artificial Intelligence, vol. 110, no. 2, pp. 241-273, June 1999.
[19]	C.C. Wong, M.F. Chou, C.P. Hwang, C.H. Tsai, and S.R. Shyu, “A Method for Obstacle Avoidance and Shooting Action of the Robot Soccer,” Proceedings of the IEEE on Robotics and Automation, vol. 4, pp.3778-3782, May 2001.
[20]	張紹勳，資料結構與演算法C++，旗標出版社，2004。
[21]	鄒宗穎，小型足球機器人系統影像處理、運動命令產生、與機構設計之研究，淡江大學機械與機電工程學系碩士論文，2004。
[22]	黃勻良，全方位移動機器人之機構與驅動設計，淡江大學機械與機電工程學系碩士論文，2005。
[23]	許吳輔，機器人影像伺服控制，淡江大學機械與機電工程學系碩士論文，2006。