In this project we implement and test ICTS and EPEA*, and compare the algorithms in both typical and pathological search spaces.

Our solution is built on top of the skeleton code provided in the assignment Model AI Assignments 2020: A Project on Multi-Agent Path Finding (MAPF) by Wolfgang Hönig, Jiaoyang Li, and Sven Koenig of the University of Southern California.

Note: I am running these commands on a windows machine using powershell. If you are not, please use the appropriate slash (\ or /) for your terminal. It is a requirement you have python (at least 3.7 or higher), pip, and git already installed on your machine

Clone the repo using either of the commands

HTTPS: git clone https://github.com/AdamBignell/ICTS-vs-EPEA.git

Navigate to the ICTS-vs-EPEA folder and create a virtual environment using this command:

python -m venv venv

To activate your virtual environment, consult the documentation, https://docs.python.org/3/library/venv.html. For windows powershell, I use the following command to activate my virtual environment

.\venv\Scripts\Activate.ps1

To deactivate the environment, simply run the command 'deactivate'

To install all the necessary packages, run this command:

pip install -r requirements.txt

To verify the installation was correct, the output of 'pip list' should print this to your console

Package         Version
--------------- -------
cycler          0.10.0
kiwisolver      1.2.0
matplotlib      3.2.1
numpy           1.18.3
pandas          1.0.3
pip             19.0.3
pyparsing       2.4.7
python-dateutil 2.8.1
pytz            2019.3
scipy           1.4.1
seaborn         0.10.0
setuptools      40.8.0
six             1.14.0

Map instances have already been generated for you and are provided in the 'mazes' and 'open_maps' directories. If you would like to generate your own maps, you can run the following commands

Note: Running these commands will overwrite the maps provided.

For Open Maps:

python open_map_generator.py --dim 50 50 --agents 3 --startnum 1 --nummaps 10 --probability 0.42 --adjacentprobability -0.08

The probability parameter sets the probability an open space becomes an obstacle. The adjacent probability parameter is added to the probability parameter for each adjacent obstacle. This prevents having too many adjacent obstacles.

For Mazes:

python maze_map_generator.py --dim 50 50 --agents 3 --startnum 1 --nummaps 10 --probability 0.75

The probability paramter sets the probability of opening a (non-cycle creating) cell during BFS from some seed location. 0.75 will branch in 3 directions on average. 0.50 will branch in 2 directions on average.

Note: if the below commands do not work, try use the same commands without the tick character (') around the --instance argument. Powershell and Git Bash terminals worked fine but the command prompt on windows interprets the ' character differently.

The results of these commands will be saved to a file in a 'results' folder. This command will run all open map instances that are 12 by 12 and write the results to the file 'results/open12x12_3_ICTS_results.txt'.

Testing ICTS:

python run_experiments.py --batch --instance 'open_maps\open12x12_3_*' --solver ICTS

Testing EPEA*:

python run_experiments.py --batch --instance 'open_maps\open12x12_3_*' --solver EPEA

Here is a sample of the results:

{"algorithm": "ICTS", "map_name": "mazes\\maze12x12_3_0.txt", "heuristic_time": 0.0009975433349609375, "time": 0.0069463253021240234, "expanded nodes": 7}
{"algorithm": "ICTS", "map_name": "mazes\\maze12x12_3_1.txt", "heuristic_time": 0.0, "time": 0.006977081298828125, "expanded nodes": 11}
{"algorithm": "ICTS", "map_name": "mazes\\maze12x12_3_10.txt", "heuristic_time": 0.0, "time": 0.003987789154052734}
{"algorithm": "ICTS", "map_name": "mazes\\maze12x12_3_100.txt", "heuristic_time": 0.0009891986846923828, "time": 0.0029921531677246094, "expanded nodes": 4}

To run a single instance with an animation showing the solution, use the following command:

For ICTS:

python run_experiments.py --instance 'open_maps\open12x12_3_0.txt' --solver ICTS

For EPEA*:

python run_experiments.py --instance 'open_maps\open12x12_3_0.txt' --solver EPEA