[3J1] [General Session] 7. Agent

[3J1-01] k-partition problem with uncertainty of agents' participation

Kazuki Nomoto¹, 〇Yuko Sakurai², Yoshio Okamoto^3,4, Makoto Yokoo^1,4 (1. Kyushu University, 2. National Institute of Advanced Industrial Science and Technology, 3. The university of Electro-Communications, 4. RIKEN, Center for Advanced Intelligence Project AIP)

Keywords:Multi agent systems

In this paper, we consider a k-partition problem with uncertainty of agents' participation. In a traditional k-partition problem, all agent are guaranteed to join the assigned partitions. However, some agents cannot join them in more real-world problem settings. In such a case, some remaining agents have to move from the current partition to another partition to guarantee k-partitions. However, it requires some costs and loses efficiency. Therefore, we need to determine a k partitions by taking into account the uncertainty of agent's participation. In our problem setting, we assume that at most one agent is not going to participate. If one agent cannot participate, we allow one agent among the remaining agents to move from her current partition to another partition. We formalize our problem as an integer programing and show the results of computational experiment.