隨著科技的進步及物聯網的興起，機器人逐漸從工業應用走入到我們的日常生活中。除了常見的大型機器人外，由多個弱小機器人所組成的群體機器人也逐漸受到重視。相較於大型機器人將所有功能集於一身，群體機器人則藉由互助合作來為人類提供服務，因此在任務排程上具有更高的彈性，能隨環境快速調整自身的狀態並且不容易有單點故障的問題。然而群體機器人是由多個獨立的機器人所組成，因此當需要透過合作完成任務時，對於該如何尋找適當的機器人尋求協助便成了重要的議題。許多研究提出了使用拍賣作為資源交易的策略，但大多數研究僅專注提升拍賣效益，而忽略集中式拍賣帶來的安全相關問題。
因此本研究提出基於區塊鏈的資源拍賣，利用區塊鏈不可修改及智能合約透明公平的運作機制，由智能合約執行拍賣並透過區塊鏈上的資料辨識惡意機器人，提供群體機器人一個公平安全的交易環境。在拍賣演算法上，我們使用多資源雙重拍賣來提升多買家和多賣家競標拍賣時的整體效率，並使用博弈論作為訂價策略，將資源間的替代關係加入考量以提升整體效益，同時考慮任務需求的優先程度，讓緊急任務能夠優先被完成。在實驗上我們將提出的方法與其他文獻方法進行比較，並查看在效益及各項指標上的表現。結果表示本研究的方法除了能兼顧需求間的優先程度外，還能同時藉由訂價策略帶來較佳的效益。另外我們也嘗試將惡意機器人放入拍賣環境中，結果顯示區塊鏈能有效辨別出惡意機器人並將其剔除在拍賣外，避免整體效益受到影響。

With the advancement of technology and the rise of the IOT, robots have gradually entered our daily life. In addition to the large-scale robots, swarm robotics composed of multiple simple robots have gradually received attention.
Swarm robotics provide services through teamwork. Therefore, it has higher flexibility in task can quickly adjust its state according to the environment. However, swarm robotics are composed of multiple independent robots, so when it is necessary to cooperate to complete tasks, how to find suitable robots for assistance has become an important issue.
Therefore, we use the unmodifiable characteristics of the blockchain and the fair operation characteristics of smart contract to establish resource auctions. The smart contract executes the auction and uses the data stored on the blockchain to identify byzantine robots. Using this method to provide a fair and safe trading environment for swarm robotics. In addition, we use combinatorial double auction to solve the overall efficiency of multi-buyers and multi-sellers in the auctions. Game theory is used as a pricing strategy and the substitution relationship between resources is considered to improve the overall utility. At the same time, we consider the priority of task so that urgent tasks can be completed first.
In the experiment, the result shows that our algorithm can not only consider the priority of the task, but also bring better utility through the pricing strategy at the same time. The results also show that the blockchain can effectively identify byzantine robots and exclude them from the auction, avoiding the overall utility from being affected.

論文審定書 i
摘要 ii
Abstract iii
目錄 iv
圖目錄 vi
表目錄 vii
第一章.緒論 1
1.1研究背景 1
1.2研究動機 2
1.3研究目的 4
1.4研究流程 5
第二章.背景與文獻回顧 7
2.1區塊鏈與智能合約 7
2.2群體機器人 10
2.3資源拍賣 12
2.4博弈論 14
第三章.研究架構與方法 17
3.1區塊鏈拍賣架構及流程 17
3.2訂價策略 20
3.3拍賣流程 26
3.3.1排序機制 28
3.3.2信譽機制 30
3.3.3交易方法 32
第四章.實驗設置 38
4.1任務情境與群體機器人定義 38
4.2實驗環境 39
4.3實驗設置 40
4.4比較算法 41
第五章.實驗結果 42
5.1無惡意機器人之環境 42
5.1.1效益 42
5.1.2資源使用率 45
5.1.3等待回合 46
5.1.4 PCDA與PCDA_sep比較 47
5.2含惡意機器人之環境 50
5.2.1賣家惡意情況 50
5.2.2買家惡意情況 54
5.3實驗結論 57
第六章.結論與未來展望 58
6.1結論 58
6.2未來研究 58
參考文獻 60

[1] G. Beni, "From swarm intelligence to swarm robotics" in International Workshop on Swarm Robotics, 2004, pp. 1-9: Springer.
[2] M. Brambilla, E. Ferrante, M. Birattari, and M. J. S. I. Dorigo, "Swarm robotics: a review from the swarm engineering perspective" Swarm Intelligence, vol. 7, no. 1, pp. 1-41, 2013.
[3] M. Dorigo et al., "Swarmanoid: a novel concept for the study of heterogeneous robotic swarms" IEEE Robotics & Automation Magazine 20.4 (2013), vol. 20, no. 4, pp. 60-71, 2013.
[4] M. A. Joordens and M. J. I. S. J. Jamshidi, "Consensus control for a system of underwater swarm robots" IEEE Systems Journal 4.1 (2010), vol. 4, no. 1, pp. 65-73, 2010.
[5] V. Strobel, E. Castelló Ferrer, and M. Dorigo, "Managing byzantine robots via blockchain technology in a swarm robotics collective decision making scenario" in Proc. 17th Int. Conf. Auto. Agents MultiAgent Syst. International Foundation for Autonomous Agents and Multiagent Systems:Stockholm, Sweden, Jul. 2018, 2018.
[6] E. Şahin, "Swarm robotics: From sources of inspiration to domains of application" in International workshop on swarm robotics, 2004, pp. 10-20: Springer.
[7] Y. Rizk, M. Awad, and E. W. J. A. C. S. Tunstel, "Cooperative heterogeneous multi-robot systems: a survey" in ACM Computing Surveys (CSUR) 52.2 (2019), 2019, vol. 52, no. 2, pp. 1-31.
[8] E. Ayari, S. Hadouaj, and K. Ghedira, "A dynamic decentralised coalition formation approach for task allocation under tasks priority constraints" in 2017 18th International Conference on Advanced Robotics (ICAR), 2017, pp. 250-255: IEEE.
[9] B. P. Gerkey, M. J. J. I. t. o. r. Mataric, and automation, "Sold!: Auction methods for multirobot coordination" IEEE transactions on robotics and automation 18.5 (2002), vol. 18, no. 5, pp. 758-768, 2002.
[10] F. Higgins, A. Tomlinson, and K. M. Martin, "Survey on security challenges for swarm robotics" in 2009 Fifth International Conference on Autonomic and Autonomous Systems, 2009, pp. 307-312: IEEE.
[11] Z. Yang, K. Yang, L. Lei, K. Zheng, and V. C. J. I. I. o. T. J. Leung, "Blockchain-based decentralized trust management in vehicular networks" IEEE Internet of Things Journal 6.2 (2018), vol. 6, no. 2, pp. 1495-1505, 2018.
[12] G. Baranwal, D. P. J. J. o. s. Vidyarthi, and software, "A fair multi-attribute combinatorial double auction model for resource allocation in cloud computing" in Journal of systems and software, 2015, 2015, vol. 108, pp. 60-76.
[13] U. Gürel, N. Adar, and O. Parlaktuna, "Priority-based task allocation in auction-based applications" in 2013 IEEE INISTA, 2013, pp. 1-5: IEEE.
[14] H. Izakian, A. Abraham, and B. T. J. F. G. C. S. Ladani, "An auction method for resource allocation in computational grids" in Future Generation Computer Systems 26.2 (2010), 2010, vol. 26, no. 2, pp. 228-235.
[15] Q. Li, C. Huang, H. Bao, B. Fu, and X. Jia, "A Game-Based Combinatorial Double Auction Model for Cloud Resource Allocation" in 2019 28th International Conference on Computer Communication and Networks (ICCCN), 2019, pp. 1-8: IEEE.
[16] Y. Mao, X. Xu, L. Wang, and P. Ping, "Priority Combinatorial Double Auction Based Resource Allocation in the Cloud" in 2020 IEEE Sixth International Conference on Big Data Computing Service and Applications (BigDataService), 2020, pp. 224-228: IEEE.
[17] P. Samimi, Y. Teimouri, and M. J. I. S. Mukhtar, "A combinatorial double auction resource allocation model in cloud computing" in Information Sciences 357 (2016), 2016, vol. 357, pp. 201-216.
[18] Y. Zhang, D. Niyato, and P. Wang, "An auction mechanism for resource allocation in mobile cloud computing systems" in International Conference on Wireless Algorithms, Systems, and Applications, 2013, pp. 76-87: Springer.
[19] C. Chen, J. Wu, H. Lin, W. Chen, and Z. J. I. T. o. V. T. Zheng, "A secure and efficient blockchain-based data trading approach for Internet of vehicles" IEEE Transactions on Vehicular Technology 68.9 (2019), vol. 68, no. 9, pp. 9110-9121, 2019.
[20] Y. Zhao, Z. Huang, W. Liu, J. Peng, and Q. Zhang, "A combinatorial double auction based resource allocation mechanism with multiple rounds for geo-distributed data centers" in 2016 IEEE International Conference on Communications (ICC), 2016, pp. 1-6: IEEE.
[21] E. Broadbent, R. Tamagawa, N. Kerse, B. Knock, A. Patience, and B. MacDonald, "Retirement home staff and residents' preferences for healthcare robots" in RO-MAN 2009-The 18th IEEE International Symposium on Robot and Human Interactive Communication, 2009, pp. 645-650: IEEE.
[22] Y. Zhang, Z. Xiong, D. Niyato, P. Wang, and J. Jin, "A game-theoretic analysis of complementarity, substitutability and externalities in cloud services" in GLOBECOM 2017-2017 IEEE Global Communications Conference, 2017, pp. 1-6: IEEE.
[23] M. Zghaibeh, U. Farooq, N. U. Hasan, and I. J. I. A. Baig, "SHealth: a blockchain-based health system with smart contracts capabilities" IEEE Access 8 (2020), vol. 8, pp. 70030-70043, 2020.
[24] K. Christidis and M. J. I. A. Devetsikiotis, "Blockchains and smart contracts for the internet of things" in IEEE Access 4 (2016), 2016, vol. 4, pp. 2292-2303.
[25] H. Wang, C. Guo, and S. J. F. G. C. S. Cheng, "LoC—A new financial loan management system based on smart contracts" Future Generation Computer Systems 100 (2019), vol. 100, pp. 648-655, 2019.
[26] E. C. Ferrer, O. Rudovic, T. Hardjono, and A. J. a. p. a. Pentland, "Robochain: A secure data-sharing framework for human-robot interaction" arXiv preprint arXiv, 2018.
[27] Y. Hanada, L. Hsiao, and P. Levis, "Smart contracts for machine-to-machine communication: Possibilities and limitations" in 2018 IEEE International Conference on Internet of Things and Intelligence System (IOTAIS), 2018, pp. 130-136: IEEE.
[28] L. C. C. De Biase, P. C. Calcina-Ccori, G. Fedrecheski, G. M. Duarte, P. S. S. Rangel, and M. K. J. I. I. o. T. J. Zuffo, "Swarm economy: a model for transactions in a distributed and organic iot platform" in IEEE Internet of Things Journal 6.3 (2018), 2018, vol. 6, no. 3, pp. 4561-4572.
[29] W. Xiong and L. J. I. A. Xiong, "Smart contract based data trading mode using blockchain and machine learning" in IEEE Access 7 (2019), 2019, vol. 7, pp. 102331-102344.
[30] B.-M. Han, S.-J. Song, K. M. Lee, K.-S. Jang, and D.-R. Shin, "Multi-agent system based efficient healthcare service" in 2006 8th International Conference Advanced Communication Technology, 2006, vol. 1, pp. 5 pp.-51: IEEE.
[31] T. T. Nguyen, A. Hatua, and A. H. Sung, "Blockchain approach to solve collective decision making problems for swarm robotics" in International Congress on Blockchain and Applications, 2019, pp. 118-125: Springer.
[32] E. C. Ferrer, "The blockchain: a new framework for robotic swarm systems" in Proceedings of the future technologies conference, 2018, pp. 1037-1058: Springer.
[33] Z. Yu, L. Shuhua, F. Shuai, and W. Di, "A quantum-inspired ant colony optimization for robot coalition formation" in 2009 Chinese Control and Decision Conference, 2009, pp. 626-631: IEEE.
[34] D. Teodorovic, M. J. A. O. Dell’Orco, and A. m. i. transportation, "Bee colony optimization–a cooperative learning approach to complex transportation problems" Advanced OR and AI methods in transportation 51 (2005), vol. 51, p. 60, 2005.
[35] M. Irfan and A. Farooq, "Auction-based task allocation scheme for dynamic coalition formations in limited robotic swarms with heterogeneous capabilities" in 2016 International Conference on Intelligent Systems Engineering (ICISE), 2016, pp. 210-215: IEEE.
[36] M. Hoeing, P. Dasgupta, P. Petrov, and S. O'Hara, "Auction-based multi-robot task allocation in comstar" in Proceedings of the 6th international joint conference on autonomous agents and multiagent systems, 2007, pp. 1-8.
[37] Z. Guan, X. Lu, N. Wang, J. Wu, X. Du, and M. J. F. G. C. S. Guizani, "Towards secure and efficient energy trading in IIoT-enabled energy internet: A blockchain approach" in Future Generation Computer Systems 110 (2020)s, 2020, vol. 110, pp. 686-695.
[38] M. J. Yang, "A design of data trading platform based on cryptology and blockchain technology" in Inf. Commun. Technol. 10 (2016), 2016, vol. 10, pp. 24-31.
[39] R. Buyya, D. Abramson, J. Giddy, H. J. C. Stockinger, c. practice, and experience, "Economic models for resource management and scheduling in grid computing" Concurrency and computation: practice and experience 14.13‐15 (2002), vol. 14, no. 13‐15, pp. 1507-1542, 2002.
[40] R. B. J. M. o. o. r. Myerson, "Optimal auction design," Mathematics of operations research 6.1 (1981), vol. 6, no. 1, pp. 58-73, 1981.
[41] B. Pourebrahimi, K. Bertels, G. Kandru, and S. Vassiliadis, "Market-based resource allocation in grids" in 2006 Second IEEE International Conference on e-Science and Grid Computing (e-Science'06), 2006, pp. 80-80: IEEE.
[42] X. Peng, K. Ota, and M. J. I. I. o. T. J. Dong, "Multiattribute-based double auction toward resource allocation in vehicular fog computing" IEEE Internet of Things Journal 7.4 (2020), vol. 7, no. 4, pp. 3094-3103, 2020.
[43] B. H. Zaidi and S. H. J. E. E. Hong, "Combinatorial double auctions for multiple microgrid trading" Electrical Engineering 100.2 (2018), vol. 100, no. 2, pp. 1069-1083, 2018.
[44] H. Izakian, A. Abraham, and B. T. J. F. G. C. S. Ladani, "An auction method for resource allocation in computational grids" Future Generation Computer Systems 26.2 (2010), vol. 26, no. 2, pp. 228-235, 2010.
[45] Q. Wang, H. Zhao, Q. Wang, H. Cao, G. S. Aujla, and H. J. F. G. C. S. Zhu, "Enabling secure wireless multimedia resource pricing using consortium blockchains" Future Generation Computer Systems 110 (2020), vol. 110, pp. 696-707, 2020.
[46] O. Morgenstern and J. Von Neumann, Theory of games and economic behavior. Princeton university press, 1953.
[47] T. J. C. o. t. A. Roughgarden, "Algorithmic game theory" Communications of the ACM 53.7 (2010), vol. 53, no. 7, pp. 78-86, 2010.
[48] L. Han, T. Morstyn, and M. J. I. T. o. P. S. McCulloch, "Incentivizing prosumer coalitions with energy management using cooperative game theory" IEEE Transactions on Power Systems 34.1 (2018), vol. 34, no. 1, pp. 303-313, 2018.
[49] Z. Liu et al., "A survey on applications of game theory in blockchain" arXiv preprint arXiv:1902.10865 (2019). 2019.
[50] A. W. J. P. s. D. Tucker, "A two-person dilemma" Prisoner's Dilemma (1950), 1950.
[51] Y. Zhang, Z. Xiong, D. Niyato, P. Wang, H. V. Poor, and D. I. J. I. T. o. C. Kim, "A game-theoretic analysis for complementary and substitutable IoT services delivery with externalities" IEEE Transactions on Communications, vol. 68, no. 1, pp. 615-629, 2019.
[52] V. Hassija, V. Chamola, D. N. G. Krishna, and M. J. I. T. o. V. T. Guizani, "A distributed framework for energy trading between uavs and charging stations for critical applications" in IEEE Transactions on Vehicular Technology 69.5 (2020), 2020, vol. 69, no. 5, pp. 5391-5402.
[53] H. Yao, T. Mai, J. Wang, Z. Ji, C. Jiang, and Y. J. I. T. o. I. I. Qian, "Resource trading in blockchain-based industrial Internet of Things" in IEEE Transactions on Industrial Informatics 15.6 (2019), 2019, vol. 15, no. 6, pp. 3602-3609.
[54] D. Lehmann, L. I. Oćallaghan, and Y. J. J. o. t. A. Shoham, "Truth revelation in approximately efficient combinatorial auctions" Journal of the ACM (JACM) 49.5 (2002), vol. 49, no. 5, pp. 577-602, 2002.
[55] V. Strobel, E. Castelló Ferrer, M. J. F. i. R. Dorigo, and AI, "Blockchain technology secures robot swarms: a comparison of consensus protocols and their resilience to byzantine robots" Frontiers in Robotics and AI 7 (2020), vol. 7, p. 54, 2020.