Asynchronous Multi-Agent Games With Imperfect Information and Knowledge Based Strategies

Abstract: This project investigates abstract games, which model real life tasks that are projected onto graphs. Strategic planning within these games provide a way of coordinating the participants in order for them to reach some desired objective. This strategic planning results in a set of instructions that each participant can follow in order to make sure that the objective of the game is reached. This is referred to as a strategy. One problem when constructing a strategy for a game is that participants may lack knowledge of what state the game is in, meaning that decision making for the participants becomes more complicated. In such cases the game is said to have imperfect information. This project takes its starting point from previously defined concepts of games, called MAGIIAN, which are games of imperfect information played in a turn-based or synchronous manner, and attempts to use these as a basis for constructing a model of asynchronous games. Within this project we propose a formal definition of asynchronous games with imperfect information. We also suggest methods for finding strategies within these games. This is done by converting these asynchronous games to synchronous games, in order to leverage a previously defined strategy-finding method called MKBSC. Finally these strategies are converted back into strategies that can be used for the asynchronous game.