TÌM KIẾM BẦY ĐÀN HIỆU QUẢ BẰNG THUẬT TOÁN BRT SỬ DỤNG AGENT CÓ NGƯỠNG TĂNG NHANH
171 lượt xemDOI:
https://doi.org/10.54939/1859-1043.j.mst.CSCE5.2021.102-108Từ khóa:
Bài toán best-of-n; Thuật toán BRT; Robot bầy đàn; Ra quyết định tập thể.Tóm tắt
Thuật toán BRT là một phương pháp cho bài toán best-of-n, nó cho phép một nhóm robot phân tán đưa ra quyết định tập thể và tìm ra phương án thích hợp nhất trong nhiều phương án khác nhau. Kết quả thí nghiệm chỉ ra rằng thời gian cần thiết để tìm ra phương án tốt nhất tỷ lệ thuận với số lượng các phương án trong bài toán. Trong bài báo này, chúng tôi đưa ra phương pháp sử dụng một vài robot có ngưỡng tăng nhanh hơn ngưỡng bình thường để rút ngắn thời gian tìm kiếm và nâng cao khả năng mở rộng cho thuật toán BRT. Kết quả thí nghiệm cho thấy thời gian tìm kiếm không chỉ giảm mà còn cải thiện được độ biến thiên, đặc biệt là trong các bài toán khó khi robot cần đưa ra quyết định giữa một lượng lớn các lựa chọn khác nhau.
Tài liệu tham khảo
[1]. G. Valentini, E. Ferrante and M. Dorigo, “The Best-of-n Problem in Robot Swarms: Formalization, State of the Art, and Novel Perspectives”, Frontiers in Robotics and AI, Vol. 9, no. 9, pp. 1-18, 2017.
[2]. J. Wessnitzer and C. Melhuish, “Collective Decision-Making and Behaviour Transitions in Distributed Ad Hoc Wireless Networks of Mobile Robots: Target-Hunting”, in Advances in Artificial Life. ECAL 2003, Lecture Notes in Computer Science (W. Banzhaf, J. Ziegler, T. Christaller, P. Dittrich, and J. T. Kim, eds.), Vol. 2801, pp. 893–902, 2003.
[3]. S. Garnier, F. Tache, M. Combe, A. Grimal, and G. Theraulaz, “Alice in pheromone land: an experimental setup for the study of ant-like robots”, Proceeding of 2007 IEEE Swarm Intelligence Symposium, pp. 37-44, 2007.
[4]. A. Scheidler, A. Brutschy, E. Ferrante, and M. Dorigo, “The k- Unanimity Rule for Self-Organized Decision Making in Swarms of Robots”, IEEE Transactions on Cybernetics, Vol. 46, no. 4, pp. 1175-1188, 2016.
[5]. S. Garnier, J. Gautrais, M. Asadpour, C. Jost, and G. Theraulaz, “Selforganized aggregation triggers collective decision making in a group of cockroach- like robots,” Adapt. Behav, Vol. 17, pp. 109–133, 2009.
[6]. H. Hamann, T. Schmickl, H. Wörn, and K. Crailsheim, “Analysis of emergent symmetry breaking in collective decision making”, Neural Comput. Appl, vol. 21, pp. 207–218, 2012.
[7]. A. Okubo, “Dynamical aspects of animal grouping: swarms, schools, flocks, and herds”, Adv. Biophys. Vol. 22, pp. 1–94, 1986.
[8]. D. J. T. Sumpter, “Collective Animal Behavior. Princeton”, NJ: Princeton University Press, 2010.
[9]. A. Reina, G. Valentini, C. Fernandez-Oto, M. Dorigo, V. Trianni, “A design pattern for decentralised decision-making”, PloS One 10 (10), 2015.
[10]. A. Reina, J. A. R. Marshall, V. Trianni, T. Bose, “Model of the best-of-N nest-site selection process in honeybees”, Physical Review E, Vol. 95, 2017.
[11]. E. Hasegawa, N. Mizumoto, K. Kobayashi, S. Dobata, J. Yoshimura, S. Watanabe, Y. Murakami, K Matsuura, “Nature of collective decision-making by simple yes/no decision units”, Scientific Reports, Vol. 7, no. 14436, 2017.
[12]. N. H. Phung, M. Kubo, and H. Sato, “Agreement algorithm with trial and error method at macro level”, Artificial life and robotics, Vol. 23, no. 4, pp. 564–570, 2018.
[13]. S. Iwanaga and A. Namatame, “The complexity of collective decision”, Nonlinear Dynamics, Psychology and Life Sciences, Vol. 6, no. 2, pp. 137–158, 2002.
[14]. D. Charbonneau, C. Poff, H. Nguyen, M. C. Shin, K. Kiestead and A. Dornhaus, “Who Are the “Lazy” Ants? The Function of Inactivity in Social Insects and a Possible Role of Constraint: Inactive Ants Are Corpulent and May Be Young and/or Selfish”, Vol. 57, no. 3, pp. 649-667, 2017
[15]. E. Bonabeau, G. Theraulaz and J. Deneubourg, “Fixed response thresholds and the regulation of division of labor in insect societies”, Vol. 60, pp. 753-807, 1998.
[16]. N. H. Phung, M. Kubo, and H. Sato, “Efficient searching by bias and raising threshold algorithm using multiple voting in the best-of-n problem”, Vol. 11, no. 3, pp. 39-45, 2019.
