Lab3

This lab will introduce students to search problems. We will first start by representing problems in terms of state space graph. Given a state space graph, starting state and a goal state, students will then perform a basic Breadth First Search solution within that graph. The output will be a set of actions or a path that will begin from initial state/node and end in the goal node.

Activity Outcomes:

This lab teaches you the following topics:

How to represent problems in terms of state space graph
How to use find a solution of those problems using Breadth First Search.
Instructor Note:

Introduction:

Sometimes, very different-sounding problems turn out to be similar when you think about how to solve them. What do Pac-Man, the royal family of Britain, and driving to Orlando have in common? They all involve route-finding or path-search problems:

How is the current Prince William related to King William III, who endowed the College of William and Mary in 1693?

What path should a ghost follow to get to Pac-Man as quickly as possible?

What’s the best way to drive from Dallas, Texas to Orlando, Florida?

We have to be given some information to answer any of these questions. This information about each question can be represented in terms of graph. This lab will enable students to represent problems in terms of graph and then finding a solution in terms of a path using breadth first search.

Lab Activities:

Activity 1:

Consider a toy problem that can be represented as a following graph. How would you represent this graph in python?

Solution:

Remember a node of a tree can be represented by four attributes. We consider node as a class having four attributes namely,

1- State of the node
2- Parent of the node
3- Actions applicable to that node
4- The total path cost of that node starting from the initial state until that particular node is reached

We can now implement this class in a dictionary. This dictionary will represent our state space graph. As we will traverse through the graph, we will keep updating parent and cost of each node.

Activity 2:

For the graph in previous activity, imagine node A as starting node and your goal is to reach F. Keeping breadth first search in mind, describe a sequence of actions that you must take to reach that goal state.

Solution:

Remember that in theory class, we discussed the following implementation of breadth first search.

What follows is python implementation of above mentioned algorithm,

Now the function definition is complete which can be called as follows,

There is one additional line of graph[child].parent=currentNode in python code which is missing in pseudocode. This allows us to update each parent of a node as we traverse the graph. Afterwards, the function actionSequence() is called which returns a series of actions when a goal state is reached. Given a start state, end state and a graph, this function recursively iterated through each parent until the starting state is reached.

Calling BFS() will return the following solution,

[‘A’, ‘C’, ‘F’]

Activity 3:

Change initial state to D and set goal state as C. What will be resulting path of BFS search?

Solution:

[‘D’, ‘B’, ‘A’, ‘C’]

Home Activities:

Activity 1:

Imagine going from Arad to Bucharest in the following map. Implement a BFS to find the corresponding path.

Activity 2:

Consider a maze as shown below. Each empty tile represents a separate node in the graph. There are maximum of four possible actions i.e., to move up, down, left or right on any given tile/node. Using BFS, find out how to get out of the maze if you’re in the start position depicted below.