Order formations in multi-agent search problem: A game theoretic approach

In this paper we investigate a search problem for a swarm of agents to find a target which appears randomly and stays for a fixed time interval. We assume that there are two search areas and the target appears in either of them. Under the situation, the objective of this paper is to achieve two types of orders: macro and micro orders. The former means that the population share of agents converges to an ordered value, and the latter means that the agents´ motion converges to an ordered one. In order to achieve macro order, we first present a probabilistic decision-making model on which area to search called Win-Stay-Lose-Shift. Then, we prove convergence of the expectation value of population share based on the knowledge of evolutionary game theory when two specific payoff structures are taken. In order to achieve micro order, we next present a search strategy used after the area to be searched is decided, and prove that agents´ trajectories converge to periodic ones respectively. Finally, simulation results show the validity of the proposed method.