Multi-Agent pursuit a moving target by speed up cover-set and tie-breaking

This is a research that I am doing as a Master student in University of Tsukuba In this research, I proposed a method for multi-agent pursuering a single moving target. Especially this method could be used in real-time video game, such like Pacman or Starwars, Warcraft

According to pacman rules and player frame rate smooth analysis, 0.1 s moves 1 tile, equally maximum planning time 0.1s one turn

Currently, up, down, left and right, only four directions movement.

A Cover-Based Approach to Multi-Agent Moving Target Pursuit

python multiagent.py [map] [algorithm] [agent number] [game number]

Example:

python multiagent.py basicMap speedupcra 3 10

Algorithm: astar, cra (cover-hueristic), speedupcra (speedup cover), abstraction(speedup cra using abstraction)

1. Obstacles 2-dimension array to unconnected graph
2. Unconnected graph to connected graph
3. 2 connected node to a abstracted node (level + 1)
4. Abstracted graph (level + 1)

• Python 2.7
• Ubuntu 16.04
• Inter Core i7-4790

• Round Map (A star algoritm)
• Round Map (Proposed method)
• Round Map (Proposed method)

1. Abstraction
2. Refinement
3. cover: whole map searching costs too much time

Pacman project of Berkeley AI CS188 http://ai.berkeley.edu/home.html