臺灣博碩士論文加值系統

在集中式多機器人系統中，系統會依照機器人的能力與數量，將一項完整的任務分成若干個子任務，再分配給多隻機器人系統去執行，透過這樣的分工方式，提高整體工作效率。除此之外，當有機器人發生故障時，其餘的機器人仍能接替完成該任務，使系統具有較佳的強健性。然而，隨著負責的工作量增加，機器人的數目卻未隨之增加，系統必須要提供一個有效的資源分配方式，使每隻機器人皆能適得其所並發揮所長。
本論文提供了一個基於k-means與Steiner tree演算法之多機器人任務分配系統。該方法可適用在一般的大樓環境中，藉由縮短回應任務請求之時間，使機器人在最短的時間內，執行完所指定的任務，以提昇系統工作效率。在有障礙物的環境中，該系統透過最短路徑法則，計算出機器人與欲執行任務之距離，再由k-means演算法將任務請求點分群並指派給機器人負責管理，接著根據Steiner tree演算法在所指派群集中找出最佳的待命位置，使系統達到縮短回應任務請求時間之訴求。除此之外，在機器人執行任務時，本論文也提供了一個多機器人的合作模式，透過機器人的相互支援，更加縮短了任務執行的時間。最後，透過系統的模擬以及實際軟硬體的整合，使本論文所提出的方法得以驗證與實現。

In the centralized multi-robot system, a full task is accomplished by dividing it into several subtasks and distributing these subtasks to the individual robots. Thus, the efficiency can be increased by executing the subtasks simultaneously. In addition, if any robot is out of service, the others can take over its task instantly, thus increasing the robustness of the system. However, as the number of tasks increase, the system is constrained by the fact that there are more requesting points than available robots. In this situation, the key challenge of the multi-robot system is how to coordinate these robots to achieve a satisfactory performance of the overall task.
To address this, we present a task-allocation approach, based on the k-means with Steiner tree algorithm, to dispatch a platoon of mobile robots in a constrained environment. It is capable to increase the efficiency of the multi-robot tasks execution by reducing the task response time. The proposed method clusters the requesting points based on the k-means algorithm. Then, the robots are pre-positioned in the standby point of their assigned clusters according to the k-means with Steiner tree algorithm. In this method, the distance in the obstacle environment is calculated by the shortest path approach. In addition, a switching strategy of the robots is also presented in this thesis. By switching the clusters, the robots can share the workload. Thus, the total task execution time can be reduced. The efficiency of the proposed methods is demonstrated through simulation study and practical implementation.

Abstract...........................................................................................................................I
Abstract in Chinese........................................................................................................II
Acknowledgement in Chinese......................................................................................III
Contents.......................................................................................................................IV
List of Figures.............................................................................................................VII
List of Tables................................................................................................................IX
Chapter 1 Introduction...................................................................................................1
1.1 Background........................................................................................................1
1.2 Research Motivation..........................................................................................3
1.3 Working Conditions............................................................................................4
1.4 Research Objective.............................................................................................6
1.5 Related Work......................................................................................................7
1.6 Approaches.........................................................................................................9
1.7 Contributions....................................................................................................10
1.8 Thesis Organization..........................................................................................13
Chapter 2 Multi-Robot Dispatching Method...............................................................14
2.1 The Shortest Path Solution...............................................................................14
2.1.1 Visibility Graph.......................................................................................15
2.1.2 Dijkstra’s Algorithm................................................................................18
2.2 Task Allocation Policy……..............................................................................21
2.2.1 Clustering Requesting Points..................................................................22
2.2.2 Pre-Positioning Robot.............................................................................25
2.3 Relocation Strategy………..............................................................................32
2.3.1 Deployment Decision………..................................................................32
2.3.2 Switching Strategy...................................................................................33
Chapter3 Pre-Positioning in a Complex Floor Plan….................................................36
3.1 Simulation Procedure.......................................................................................36
3.2 The Results of Clusters and the Pre-Positions..................................................38
3.3 Simulated Task Schedule..................................................................................43
3.4 Simulated Results.............................................................................................45
3.5 Discussion........................................................................................................75
Chapter 4 Platform for Real-Time Dispatching….......................................................48
4.1 System Platform...............................................................................................48
4.2 Functional Block Diagram……………….......................................................53
4.3 Real-Time Control............................................................................................55
4.3.1 Image Processing……….........................................................................55
4.3.2 Robot Motion Control….........................................................................59
4.3.2 Coordination Strategy for Switching.......................................................64
4.4 Experiment Results..........................................................................................69
4.5 Discussion........................................................................................................73
Chapter 5 Conclusion...................................................................................................75
5.1 Comparison to Existing Solutions....................................................................75
5.2 Future Work......................................................................................................78
Reference......................................................................................................................80
Appendix......................................................................................................................84
Glossary………………………………………………………………………………85

[1]Jun Ota, “Multi-agent robot systems as distributed autonomous systems,” Advanced Engineering Informatics, vol. 20, no. 1, pp. 59-70, January 2006.
[2]Roland Siegwart and Illah R. Nourbakhsh, “Introduction to autonomous mobile robots,” the MIT Press, pp. 261-264, 2004.
[3]Iris F. A. Vis, “Survey of research in the design and control of automated guided vehicle systems,” European Journal of Operation Research, vol. 170, no. 3, pp. 677-709, May 2006.
[4]Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf, “Computational geometry: algorithms and applications,” 2nd Edition, Springer, 2000.
[5]劉浚明, 《數學規劃》, 宏明書局, 1995
[6]Laura M. Hiatt and Reid Simmons , “Pre-positioning assets to increase execution efficiency,” IEEE International Conference on Robotics and Automation, pp. 324-329, April 2007
[7]K. Kamali, D. Ventura, A. Garga, and S.R.T. Kumara, “Geometric task decomposition in a multi-agent environment,” Applied Artificial Intelligence, vol. 20, no. 5, pp. 437-456, June 2006.
[8]Y. Jin, A. A. Minai, and M. M. Polycarpou, “Cooperative real-time search and task allocation in UAV teams,” IEEE International Conference on Decision and Control, 2003.
[9]Anmin Zhu and Simon X. Yang, “A neural network approach to dynamic task assignment of multirobots,” IEEE Transactions on Neural Networks, vol. 17, no. 5, pp. 1278-1287, Sept. 2006.
[10]Zu Li-Nan, Tian Yan-Tao, Fu Jia-Cai, and Liu Ji-Fang, “Algorithm of task-allocation based on realizing at the lowest cost in multi mobile robot system,” IEEE Conference on Machine Learning and Cybernetics, vol. 1, pp. 152-156, Aug. 2004.
[11]M. Ahmadi and P. Stone, ” A multi-robot system for continuous area sweeping tasks,” IEEE Conference on Robotics and Automation, vol. 2006, pp. 1724-1729, May 2006.
[12]A.K. Jain, M.N. Murty, and P.J. Flynn, “Data Clustering: A Review,” ACM Computing Surveys, vol. 31, no. 3, pp. 264-323, Sept. 1999.
[13]A.K. Jain, M.N. Murty, and P.J. Flynn, “Data clustering: a review,” ACM Computer Surveys, vol. 31, no. 3, pp.264-323, Sept. 1999.
[14]Daniel T. Larose, “Discovering knowledge in data: an introduction to data mining,” John Wiley & Sons, 2005.
[15]J. McQueen, “Some methods for classification and analysis of multivariate observations,” Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, pp. 281–297, 1967.
[16]J.S. Chen, R.K.H. Ching, and Y.S. Lin, “An extended study of the k-means algorithm for data clustering and its applications,” Journal of the Operational Research Society, vol. 55, no. 9, pp. 976 – 987, Sept. 2004.
[17]R.O. Duda, P.E. Hart, and D.G. Stork, “Pattern Classification,” Wiley-Interscience Publication, 2000.
[18]T. Kanungo, D.M. Mount, N.S. Netanyahu, C.D. Piatko, R. Silverman, and A.Y. Wu, “An efficient k-means clustering algorithm: analysis and implementation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 7, pp. 881 – 892, July 2002.
[19]J.M. Peña, J.A. Lozano, P. Larrañaga, “An empirical comparison of four initialization methods for the k-means algorithm,” Pattern Recognition Letters, vol. 20, pp. 1027-1040, 1999.
[20]M.R. Anderberg, “Cluster analysis for applications,” Academic Press, New York, 1973.
[21]F.K. Hwang, D.S. Richardr, and P. Winter, “The Steiner tree problem,” Annals of Discrete Mathematics, 1992.
[22]Pawel Winter and Martin Zachariasen, “Euclidean Steiner minimum tree: an improved exact algorithm,” Networks, vol.30, pp. 146-166, 1997.
[23]L.G. Alberto, “Probability and random processes for electrical engineering,” 2nd Edition, Addison-Wesle, 1994.
[24]http://www.parallax.com/
[25]http://www.billionton.com/
[26]http://www.logitech.com/
[27]蔡栢樟，《視窗51模擬實務-C語言篇》，知行文化，2002。
[28]張智星，《MATLAB程式設計—入門篇》，清蔚科技，2005。
[29]鍾國亮，《影像處理與電腦視覺》，東華書局，2006。
[30]Rafael C. Gonzlez, Richard E. Woods, and Steven L. Eddins，《數位影像處理: 運用 MATLAB》，繆紹綱譯，東華書局，2005。
[31]Hartmut Surmann and Antonio Morales, “Scheduling Tasks to a Team of Autonomous Mobile Service Robots in Indoor Environments,” Jornal of Universal Computer Science, vol. 8, no. 8, pp.809-833, 2002.