/Bi-Directional-Search

Implementing bi directional search as a part group project for CSE571 AI

Primary LanguagePython

Bi-Directional-Search

This is the implementation of the paper 'Bidirectional Search That Is Guaranteed to Meet in the Middle' link:- https://webdocs.cs.ualberta.ca/~holte/Publications/MM-AAAI2016.pdf

Team 12 CSE 571 AI ASU

Requirements:-

  1. python == 3.6
  2. scipy == 1.5.4
  3. scikit-learn == 0.24.2

You can choose from the following arguments for search strategies:

  • bfs --> breadthFirstSearch
  • dfs --> depthFirstSearch
  • astar --> aStarSearch
  • ucs --> uniformCostSearch
  • bid --> bidirectionalsearch for the MM version
  • standard_bid --> standard_biderictional

You can choose from the following arguments for heuristics:

  • nullHeuristic --> no heurisitc involved
  • euclideanHeuristic --> heuristic used is Euclidean distance
  • manhattanHeuristic --> heuristic used is Manhattan distance
  • mazeHeuristic --> hueristic used is the actual maze distance

You can choose from the following arguments for layouts:

  • tinyMaze
  • smallMaze
  • mediumMaze
  • bigMaze
  • customSmallMaze1
  • customSmallMaze2
  • customSmallMaze3
  • customMediumMaze2
  • customMediumMaze3
  • customMediumMaze1
  • customBigMaze1
  • customBigMaze2
  • customBigMaze3
  • customBigMaze1_t
  • customBigMaze2_t
  • customMediumMaze1_t
  • customMediumMaze2_t
  • customMediumMaze3_t
  • openMaze_t
  • customMaze1
  • customMaze2_t
  • customMaze1_t
  • Opposites
  • openMaze
  • openMaze_1

To run the code on a single layout use the following format:

  • python pacman.py -l Layout_name -p SearchAgent -a fn=search_strategy,heuristic=heuristic_name -q

For example:

python pacman.py -l Opposites -p SearchAgent -a fn=bid,heuristic=nullHeuristic -q

To run T-test use the following format:

  • python t_test.py [search_strategy_1,heuristic=heuristic_name:search_strategy_2,heuristic=heuristic_name]

Some examples:

python t_test.py [astar,heuristic=manhattanHeuristic:bid,heuristic=manhattanHeuristic]
python t_test.py [bid,heuristic=nullHeuristic:bid,heuristic=manhattanHeuristic]
python t_test.py [bid,heuristic=manhattanHeuristic:bfs]
python t_test.py [bid,heuristic=mazeHeuristic:bid,heuristic=nullHeuristic]

Some notes:

  • The 'bid' argument represents the bidirectional search strategy from the paper.
  • For mm0 version put heuristic=nullHeuristic while calling the bid serach strategy and for mm version any of the euclidean,manhattan or maze heuristics would do.
  • The maze heuristic may cause delay in execution time for some layouts.
  • If no heuristic name is provided in t-test command then nullHeuristic is chosen by default.