Comparing BFS and A* Search

Code

%matplotlib inline
%config InlineBackend.figure_format = 'retina'

import numpy as np
import maze_helper as mh

#f = open("small_maze.txt", "r")
#f = open("medium_maze.txt", "r")
#f = open("large_maze.txt", "r")    # this has only one solution!
#f = open("open_maze.txt", "r")
#f = open("empty_maze.txt", "r")
#f = open("empty_2_maze.txt", "r")
#f = open("loops_maze.txt", "r")
f = open("L_maze.txt", "r")

maze_str = f.read()
maze = mh.parse_maze(maze_str)

# tree_search_solution.py has my actual implementation (not published)
import tree_search_solution as ts


# order in which we add new states to the frontier
ts.set_order("NESW")
#ts.set_order(random=True)

Directions are checked in the order ['N', 'E', 'S', 'W']

BFS

Breadth-first search is an optimal algorithm. BFS is an _uninformed search algorithm and has no idea where the goal is. It expands the search in concentric circles around the start till it hits the goal.

%time result = ts.best_first_search(maze, strategy = "BFS", debug = False, vis = False, animation = True)

ts.animate_maze(result)

CPU times: user 7.58 ms, sys: 0 ns, total: 7.58 ms
Wall time: 7.37 ms
Path length: 16
Reached squares: 151
Action sequence: ['E', 'E', 'E', 'E', 'S', 'E', 'E', 'N', 'N', 'N', 'N', 'N', 'N', 'N', 'N', 'E']

Note that BFS explores almost the whole maze. BFS keeps the whole tree (notes are represented by gray squares) in memory. This is a problem for many AI problems with large state spaces.

A* Search - Euclidean Heuristic

A* Search is an informed search algorithms. It gets information about where the goal is using the heuristic function. The value of the heuristic function tends to decrease the closer we get to the goal. It is optimal if A* is an admissible heuristic.

# set heuristic for my A* search implementation
#ts.heuristic = ts.manhattan
ts.heuristic = ts.euclidean

%time result = ts.best_first_search(maze, strategy = "A*", debug = False, vis = False, animation = True)
ts.animate_maze(result)

CPU times: user 3.57 ms, sys: 0 ns, total: 3.57 ms
Wall time: 3.59 ms
Path length: 16
Reached squares: 87
Action sequence: ['E', 'E', 'E', 'E', 'S', 'E', 'E', 'N', 'N', 'N', 'N', 'N', 'N', 'N', 'E', 'N']

A* Search - Manhattan Heuristic

# set heuristic for my A* search implementation
ts.heuristic = ts.manhattan
#ts.heuristic = ts.euclidean

%time result = ts.best_first_search(maze, strategy = "A*", debug = False, vis = False, animation = True)
ts.animate_maze(result)

CPU times: user 2.53 ms, sys: 0 ns, total: 2.53 ms
Wall time: 2.54 ms
Path length: 16
Reached squares: 66
Action sequence: ['E', 'E', 'E', 'E', 'S', 'E', 'E', 'E', 'N', 'N', 'N', 'N', 'N', 'N', 'N', 'N']

Comparison

• BFS and A* search are both optimal and find the shortest possible path.
• BFS explores 142 states and needs to store a tree of that size, while A* explores significantly less.
• The effectiveness of A* depends on how good the heuristic is. Manhatten distance is a very good heuristic for this problem.
• For some AI problems, the smaller tree that A* creates may still be too large for the available memory. Here other methods weighted A* search or, iterative deepening search may need to be used.