Multi-agent routing problems have drawn significant attention nowadays due to their broad industrial applications in, e.g., ware- house robots, logistics automation, and traffic control. Conventionally they are modelled as classical planning problems. In this work, we argue that it is beneficial to formulate them as universal planning problems. We therefore propose universal plans, also known as policies, as the solution concepts, and implement a system based on Answer Set Programming (ASP) for computing them. Given an arbitrary two-dimensional map and a profile of goals for a group of partially observable agents, the system translates the problem configuration to a logic program, and finds a feasible universal plan for each agent that ensures no collision with others.

conda create -n mapf python=3.9.7
conda activate mapf
pip install -r requirements.txt

usage: run.py [-h] [--agents AGENTS [AGENTS ...]] [--map MAP] [--goals GOALS [GOALS ...]] [--lp-file LP_FILE] [--vis] [--save SAVE]

Partially Observable Multi-Agent Path Finding.

optional arguments:
  -h, --help            show this help message and exit
  --agents AGENTS [AGENTS ...]
                        Specify a team of agents
  --map MAP             Specify a map
  --goals GOALS [GOALS ...]
                        Specify the goals for each agent,e.g. 2_0 0_2
  --lp-file LP_FILE     Use an existing human-written lp file
  --vis                 Visulize the process
  --save SAVE           Specify the path to save the animation

Example:

python run.py --agents sensor_1 sensor_1 --map 3by3 --goals 3_2 3_3 --vis

The above command will instantiate two agents of sensor range 1 on a 3x3 map with the two specified goals, respectively. If a feasible universal plan exists, you will enter an interactive mode for inputting initial positions (locations separated with whitespaces), which resembles the following,

Logic program translated.
Solving time: 0.04840087890625
Policy saved as tmp.sol

Specify an initial position for agent p1: 1 1
Specify an initial position for agent p2: 2 2

Upon your input, it will generate a trajectory and render an animation,

STARTS:
{'p1': (1, 1), 'p2': (2, 2)}
-------------

[(1, 1), (2, 2)]
p1: ((1, 1), (2, 2)) -> nil
p2: ((2, 2), (1, 1)) -> left
	|
	V
[(1, 1), (2, 1)]
p1: ((1, 1), (2, 1)) -> right
p2: ((2, 1), (1, 1)) -> up

...

	|
	V
[(3, 2), (2, 3)]
p1: ((3, 2), (2, 3)) -> nil
p2: ((2, 3), (3, 2)) -> down
	|
	V
Goals reached!

Note that, the plan is called a universal one, as it supports all possible initial positions for the two agents (no re-computation will be needed). Thus, once an episode is over, the program will ask you to specify another set of initial positions.

One can also run an existing logic program that is complied before, considering some could be reuse for multiple times, by specifying the --lp-file option.

Here is a demo animation, where 4 agents coordinate themselves with sensors of range 2. While agents are connected by a dotted line, it means one can observe the other.

For users' reference, the following table shows the computing time for solving various scales.

Feel free to open any issue or pull-request. Have fun!