COEN266- Artificial Intelligence: Homework 2 Solved

Problem 1: Consider a state space where the start state is number 1 and the successor function for state n returns two states, numbers 2n and 2n + 1. 

 (a). Draw the portion of the state space for states 1 to 15. 


 (b). Suppose the goal state is 11. List the order in which nodes will be visited for breadth-first search, depth-limited search with limit 3, and iterative deepening search. 


Problem 2: (Provide derivations of your answer, that is, draw the search tree, and write down the list of visited nodes and the corresponding frontier nodes). Execute Tree Search through this graph (i.e. do not remember visited nodes). S is the start node, and G is the goal node. Step costs are given next to each arc. Heuristic function values are given in the table on the right. The successors of each node are indicated by the arrows out of that node. Use the alphabetical order as tie-breakers, i.e. if nodes A, B, and C are available to expand, expand A before B, B before C. For each search strategy below, show the order in which nodes are expanded, ending with the goal node that is found. Show the solution path from start to goal, and give the cost of the solution path that is found. 

 

2.a depth-first search
Order of node expansion: ____________________________________________________________

Path found: _________________________________   Cost of path found: _____________________ 2.b uniform-cost search 

Order of node expansion: ____________________________________________________________

Path found: _______________________________________   Cost of path found: _______________

2.c greedy (best-first) search with h(n)
Order of node expansion: ____________________________________________________________

Path found: ____________________________________   Cost of path found: __________________

2.d iterative deepening depth-first search
Order of node expansion: ____________________________________________________________

Path found: _________________________________   Cost of path found: _____________________ 2.e A* search with h(n) 

Order of node expansion: ____________________________________________________________

Path found: __________________________________   Cost of path found: ____________________

Problem 3: (Provide derivations of your answer, that is, work on the search tree, write down the list of visited nodes and the corresponding frontier nodes). Consider the search tree below. The two goal states G1 and G2 are indeed the same goal. The numbers on the edges represent step-costs. You also know the following heuristic estimates: h(B→G2) = 9, h(D→G2) =10, h(A→G1)=2, h(C→G1)=1. In what order will A* search visit the nodes? Explain your answer by giving the value of the evaluation function f(n) for those nodes that the algorithm considers. Also give the solution path.

Files you might want to look at
 

pacman.py              The main file that runs Pacman games. This file describes a Pacman GameState  type, which you use in this project.

 

game.py                  The logic behind how the Pacman world works. This file describes several  supporting types like AgentState, Agent, Direction, and Grid.

searchAgents.py     Where all of your search-based agents will reside.

util.py                      Useful data structures for implementing search algorithms.

Files you will not edit
 

agentTestClasses.py            Autograding test classes graphicsDisplay.py              Graphics for Pacman graphicsUtils.py                  Support for Pacman graphics textDisplay.py                     ASCII graphics for Pacman ghostAgents.py                   Agents to control ghosts

keyboardAgents.py             Keyboard interfaces to control Pacman

layout.py                             Code for reading layout files and storing their contents autograder.py                      Project autograder

testParser.py                       Parses autograder test and solution files testClasses.py                     General autograding test classes

test_cases/                          Directory containing the test cases for each question

 

Academic Dishonesty: We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else’s code and submit it with minor changes, we will know, and we will pursue the strongest consequences available to us.

This assignment is based on the Pacman AI projects developed at UC Berkeley, http://ai.berkeley.edu.

Welcome to Pacman
After downloading the code (search_and_games.zip), unzipping it, and changing to the directory, you should be able to play a game of Pacman by typing the following at the command line:

python pacman.py

Pacman lives in a shiny blue world of twisting corridors and tasty round treats. Navigating this world efficiently will be Pacman's first step in mastering his domain.

The simplest agent in searchAgents.py is called the GoWestAgent, which always goes West (a trivial reflex agent). This agent can occasionally win:

python pacman.py --layout testMaze --pacman GoWestAgent

But, things get ugly for this agent when turning is required:

python pacman.py --layout tinyMaze --pacman GoWestAgent

If Pacman gets stuck, you can exit the game by typing CTRL-c into your terminal.

Note that pacman.py supports a number of options that can each be expressed in a long way (e.g., --layout) or a short way (e.g., -l). You can see the list of all options and their default values via:

python pacman.py -h

Also, all of the commands that appear in this portion of the project also appear in commands.txt, for easy copying and pasting. In UNIX/Mac OS X, you can even run all these commands in order with bash commands.txt.

Problem 1: Iterative Deepening
In the iterativeDeepeningSearch function in search.py, implement an iterative-deepening search algorithm

(iterative deepening depth-limited depth-first graph search). You will probably want to make use of the Node class in search.py. Figure 3.17 and Figure 3.18 from the textbook (also given at the end of this document) may help.

Experiments: Test your code using:

python pacman.py -l threeByOneMaze -p SearchAgent -a fn=ids python pacman.py -l testMaze -p SearchAgent -a fn=ids python pacman.py -l tinyMaze -p SearchAgent -a fn=ids python pacman.py -l smallMaze -p SearchAgent -a fn=ids  python pacman.py -l mediumMaze -p SearchAgent -a fn=ids  python pacman.py -l bigMaze -p SearchAgent -a fn=ids 

A few additional notes: 

x      If Pacman moves too slowly for you, try the option --frameTime 0. 

x     All of your search functions need to return a list of actions that will lead the agent from the start to the goal. These actions all have to be legal moves (valid directions, no moving through walls). 

x      We are implementing graph search, not tree search, so IDS might not return the optimal path.

Problem 2: A* Search
Implement A* graph search in the empty function aStarSearch in search.py. A* takes a heuristic function as an argument. Heuristics take two arguments: a state in the search problem (the main argument), and the problem itself (for reference information). The nullHeuristic heuristic function in search.py is a trivial example.

You will probably want to make use of the Node class in search.py and the PriorityQueue class in util.py.

You can test your A* implementation on the original problem of finding a path through a maze to a fixed position using the Manhattan distance heuristic (implemented already as manhattanHeuristic in searchAgents.py).

 
Experiments: 

--frameTi
python pacman.py -l tinyMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic python pacman.py -l smallMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic  python pacman.py -l mediumMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic
 

me 0
 

--frameTime 0
python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic                
 
Note: The following (from the textbook) may be helpful for you to implement the Iterative Deepening depthfirst search algorithm