Deterministic Search Algorithms Part 1

Learning to solve AI Planning Problems with Deterministic Search Algorithms

Read previous post to understand the generic implementation of Deterministic-search algorithms.

To understand more easily we use real life examples, a game, to visualize how the algorithms solve the planning problems.

The example that we will use here is Pacman Game. You can read the link for the details of the gameplay and other information. In short, the mission of Pacman is to eat all smaller dots (foods) while avoiding ghosts.

If Pacman meets a ghost, it loses. It wins after it has eaten all foods.

The bigger dots are capsules which when eaten by Pacman, gives temporary power to Pacman to eat the ghosts.

You can search in Github to find the implementation of Pacman game engine written in Python.

Pacman World Representation

For us to solve planning problems in Pacman, first we need to represent how Pacman World looks like. The following are all the objects in Pacman World:

1. Pacman
2. Ghosts
3. Foods
4. Capsules
5. Walls

Walls are rigid, the positions and number of walls are fixed. Foods and Capsules are fixed in positions but the number of them can reduce.

Pacman and ghosts do not reduce in number but their positions can change throughout the game.

We can write the Pacman World like shown in the code snippet above. You can see that we have all the objects implemented in our class along with their getters.

The most important thing is the implementation of the equality operators (== and !=), which will be used frequently by the algorithms to compare the states of the world.

Action Templates and State Predictor

The next bit that we need is the action template and its state predictor. There are 4 actions that Pacman can do, they are:

1. Go up (north)
2. Go down (south)
3. Go left (west)
4. Go right (east)

The implementation of action template looks like this:

Recall that the action templates has input parameters, preconditions and effects. Read this post:

When the algorithm looks for applicable actions, it simply calls precondition functions and to get the predicted state of the world, it simply call effect function.

for action in actions:
 if action.pre(pacman_world):
  predicted_pacman_world = action.eff()

The preconditions of all simple actions that we have are:

1. the action is legal (not moving towards the wall)
2. will not meet ghost

Another thing worth noting here is we provide the cost incurred to perform the action as well to the search algorithm.

Planning Problem

We’ll look at one example of Planning Problem, start with a simple one.

From this initial state with 4 foods in the corner and without ghosts.

We want to have this goal state with 0 food, which means our AI agent, Pacman, has to eat all 4 foods intelligently.

Algorithms

Let’s look at how deterministic search algorithms solve this problem. In these implementations we are not using heuristics. Heuristics will be discussed in a separate post.

Breadth-first Search

We implement BFS as an instance of Deterministic search algorithm with node selection and node pruning as follows:

1. Node selection Choose a node with shortest length
2. Pruning Remove from Children and Frontier nodes which are already in Expanded

When running this algorithm on our planning problem we will get optimal solution but long planning time. For relative comparisons, I will write each algorithm’s planning time when I ran it.

• Planning time: 185 seconds

Depth-first Search

1. Node Selection Choose node with longest length
2. Pruning Cycle checking

Running this algorithm on our planning problem gives us non-optimal solution but much shorter planning time.

• Planning time: 37 seconds

Hill Climbing

1. Node Selection Choose node that minimizes heuristic, for our implementation this is just any nodes because we have not implemented heuristic function
2. Pruning Clear Frontier so that we only follow current path

As we can see in the pruning process it is not guaranteed that we will have a solution. This algorithm fails to solve our planning problem.

Uniform-cost Search

1. Node Selection Choose node that minimizes total cost
2. Pruning Remove from Frontier and Children nodes that are already in Expanded

This algorithm gives us optimal solution and shorter planning time compared to BFS.

• Planning time: 106 seconds

A*

1. Node Selection Choose node that minimizes f(v) = cost + heuristic. For our current implementation this will be exactly the same as Uniform-cost search because we have not implemented heuristics
2. Pruning Remove duplicated paths with higher cost

Because of the pruning process, the planning time is shorter than Uniform-cost search. The result is optimal.

• Planning time: 24 seconds

Depth-first Branch and Bound (DFSBB)

This algorithm evaluates all possible paths in DFS and get the best. However, for our planning problem this algorithm takes too long to run. We’ll skip this algorithm this time.

Greedy Best-First Search (GBFS)

1. Node Selection Choose node that minimizes heuristic
2. Pruning Same as A*

Normally this algorithm runs quicker than A*, however because we haven’t implemented heuristic, the planning time is a little bit longer.

• Planning time: 51 seconds

Now we have looked into different algorithms to solve our first simple planning problem. In the next posts, we’ll solve more difficult planning problems and techniques to solve them.