Coalition formation algorithm based on organization and Markov decision process for multi-player pursuit evasion

Article type: Research Article

Authors: Souidi, Mohamed^{; *} | Piao, Songhao | Li, Guo | Chang, Lin

Affiliations: Harbin Institute of Technology, Computer Science and Technology, Harbin, Heilongjiang, China

Correspondence: [*] Corresponding author: Mohamed Souidi, Harbin Institute of Technology, Computer Science and Technology, Harbin 150001, Heilongjiang, China. E-mail: [email protected]

Abstract: Coalition formation in multi-agent systems seeks to create efficient agents' alliances in order to perform complex tasks. The main objective of this paper is to measure the impact of the pursuit groups' formation on the capture of different evaders. In order to achieve this goal, we propose a coalition formation algorithm based on Agent-Group-Role organizational model (AGR). This organizational model is used as coordination mechanism with the aim of regrouping the agents in different groups and assigning the roles adequately. Also, we have used Markov Decision process principles (MDP) to control the motion strategies of our agents in the environment. The achieved simulation results reveal the effectiveness of the given method.

Keywords: Multi-agent system, coalition formation, pursuit problem, organizational model, Markov decision process

DOI: 10.3233/MGS-150226

Journal: Multiagent and Grid Systems , vol. 11, no. 1, pp. 1-13, 2015