부산대학교 도서관

Biological inspiration from honeybees, insects, and other animals has been used to create interesting implementations of multi-robot swarms. When the robots in a swarm are completely distributed, that is they lack any form of centralized control, the swarm acts as an agent-based model (ABM) wherein each agent implements its own controller and collective behavior emerges from the interactions between agents. Differential equation and graph-based models of some types of swarms have been used to guarantee collective behavior, but guaranteeing or predicting outcomes for hub-based agent colonies with finite numbers of robots remains an open problem. This paper presents a case study of designing an agent-based, hub-based swarm that solves the best-of-N problem with predictable success rates and completion times. The key innovation is modifying a tripartite graph formulation (TGF) from previous work so that it acts as a graph schema which abstracts an ABM into a simplified four state model, which in turn leads to a large discrete time Markov chain (DTMC) that describes how the collective state evolves over time. The DTMC can be used to compute success rates and completion times, which act as predictions for the ABM. Deviations between observed ABM outcomes and DTMC predictions lead to modifications in the ABM so that the swarm becomes more predictable.