Description
For this problem, handin a lab report pdf (include name, date, assignment and class number
in pdf) which studies statistics of using variations of A∗
search on the Wumpus World
problem. The measure of complexity is the total number of nodes generated during a
search; this means that when a node is expanded, all its children are added to the tree
(unless their state has already been created). For A∗
search use the heuristic of Manhattan
distance between the current state and the goal state. You are to compare two ways to insert
nodes into the priority queue for the frontier: (1) insert before greater than or equal cost
states, (2) insert after less than or equal cost states. Run 2000 trials using random boards
with Wumpus and 20% probability of a pit in each (non-start) cell. Test the hypothesis that
option 1 A∗
search (given above) is 10% better than option 2 at the 95 % confidence level.
Do the following:
1. Pose specific questions in the Introduction (e.g., What is the mean number of search
tree nodes produced by A* options 1 and 2 on these problems).
2. Give specific details on the following aspects of each algorithm:
(a) Are the (new) children nodes added to the tree immediately when a node is
expanded from the frontier?
(b) When is a node checked to see if it is a solution?
(c) Produce results even for boards with no solution to goal (i.e., include statistics
of search trees that fail).
1
(d) Other issues which you deem important to understand the data taken.
3. Give a 4×4 table with the number of nodes in the search tree for each of these options
when the goal is the [x;y] location of the table entry.
4. For the verification section
(a) Pick 3 example boards, and show hand developed solutions for each of the two
options, and compare to the results of the Matlab functions.
(b) Determine what the min and max tree sizes are for each method and report if
the actual minima and maxima from the experiments are within that range.
5. Make sure that the data section contains both a plot the actual sizes of the individual
trial results and a histogram of those.
Function header:
function [solution,nodes] =
CS4300_Wumpus_A_star1(board,initial_state,…
goal_state,h_name,option)
% CS4300_Wumpus_A_star1 – A* algorithm for Wumpus world
% On input:
% board (4×4 int array): Wumpus board layout
% 0: means empty cell
% 1: means a pit in cell
% 2: means gold (only) in cell
% 3: means Wumpus (only) in cell
% 4: means gold and Wumpus in cell
% initial_state (1×3 vector): x,y,dir state
% goal_state (1×3 vector): x,y,dir state
% h_name (string): name of heuristic function
% option (int): picks insertion strategy for equal cost states
% 1: insert state before equal or greater than states
% 2: insert after equal or less than states
% On output:
% solution (nx4 array): solution sequence of state and the action
% nodes (search tree data structure): search tree
% (i).parent (int): index of node’s parent
% (i).level (int): level of node in search tree
% (i).state (1×3 vector): [x,y,dir] state represented by node
% (i).action (int): action along edge from parent to node
2
% (i).g (int): path length from root to node
% (i).h (float): heuristic value (estimate from node to goal)
% (i).cost (float): g + h (called f value in text)
% (i).children (1xk vector): list of node’s children
% Call:
%[so,no] = CS4300_Wumpus_A_star1([0,0,0,0;0,0,0,1;0,2,1,3;0,0,0,0],…
% [1,1,0],[2,2,1],’CS4300_A_star_Man’,1)
% so =
% 1 1 0 0
% 2 1 0 1
% 2 1 1 3
% 2 2 1 1
%
% no = 1×9 struct array with fields:
% parent
% level
% state
% action
% cost
% g
% h
% children
% Author:
% T. Henderson
% UU
% Summer 2016
%
You should handin the report pdf as well as the source code used in the study. The code
should conform to the style requested in the class materials.
In addition, please turn in a hardcopy of the report in class before the start of class on
September 8, 2016.
Write a lab report in the format (please do not deviate from this format!) described in the
course materials.
Discuss the statistical framework to establish a confidence interval on the means, and the
hypothesis test.
3
