Implements : Bidirectional search that is guaranteed to meet in the middle : link
Team Members :
- Agneet Chatterjee
- Kavya Sree Bachina
- Walstan Baptista
- Souradip Nath
We implement the "Meet in Middle" (MM) algorithm on the Pacman search environemnt defined in “UC Berkeley Pacman AI Projects” developed by the DeNero, J.; Klein, D. Available: link
We develop both the MM algorithm as well as its non-heuristic variant MM0. We implement it for two problem,
- The Position Search - To find the path from the start location to the location of the single food pellet in the pacman maze.
- The Corner Search - To find the path to eat 4 food pellets spread across the 4 corners of the pacman maze.
Instructions to run :
Unzip the code repository go the the "search" directory and execute the following commands.
python pacman.py -l MAZE_NAME -p SearchAgent -a fn=mm,heuristic=HEURISTIC_NAME
Replace MAZE_NAME with 1 amongst the 6 mazes we have created:
- tinyMaze
- smallMaze
- mediumMaze
- contoursMaze
- customMaze
- openMaze
In order to run MM0: Replace HEURISTIC_NAME with nullHeuristic
In order to run MM with Manhattan Heuristic: Replace HEURISTIC_NAME with manhattanHeuristic
In order to run MM with any other Heuristic: Define the heuristic function in search.py, and replace HEURISTIC_NAME with the function name
python pacman.py -l MAZE_NAME -p SearchAgent -a fn=mm_corner,prob=CornersProblem
Replace MAZE_NAME with 1 amongst the 6 mazes we have created :
- tinyCorners
- mediumCorners
- bigCorners
- customTinyCorners
- customMediumCorners
- customBigCorners
The above code will run by default with a heuristic. To run MM0, uncomment these two lines : 1 and 2, and run the code again.
Custom layouts were generated using the CustomPacmanLayoutsGenerator.xlsx file.