Assignment 2: Search Homework

HOMEWORK MOTIVATION:  You will get the opportunity to code up the standard search algorithms in the lab.  For this homework, I want to give you the chance to experiment with some of the more advanced search concepts.

GOAL: Think hard about iterative searches, use a learning-based search, and experiment with various local searches.
  1. Problem 3.11 parts a, b, and c.
  2. Suppose your implementation of Iterative Deepening takes 10 times as much space per node as your Bidirectional implementation. If b=3 at what depth (d) should you switch algorithms assuming you are motivated only by space concerns.
  3. Consider the following graph.   In the graph, o is the origin (all trials start from this state) and g is the goalLRTA* Graph (all trials end in this state).  Show what the heuristic values for each state (o,a,b,c,d,g) are after one trip (one episode) from the origin to the goal when the LRTA* algorithm is used. Initially, all heuristics are set to 0.  When there is a tie, choose the node which comes first in the alphabet.   Repeat and show what the heuristic values for each state are after a second trip (two episodes) from the origin to the goal when the LRTA* algorithm is used.
  4. This problem has you experiment with creating a graph in a BZFlag-like world using the principles of probabilistic roadmaps.  Download this MATLAB file.  Vary the following parameters: NumObst, NumVert, and EdgeLengthThreshold.  For NumObst, try values of 8 and 80.  For NumVert, try values of 200, 400, and 20.  For EdgeLengthThreshold, try values of 0.2*DIM, 0.1*DIM, and 0.4*DIM.  What happens when you change these parameters and why?
  5. In this problem, you will apply some of the steps for using gradient
    ascent to find the maximum of a function. Consider the function f(x, y) = x3y − 2xy2 + x − 4.
    If we use gradient ascent beginning at (x0, y0) = (1,−1) and a “stepping” factor of k = 0.1,
    what values of (x, y) will be reached after one step? Recall that gradient ascent computes the
    step direction by creating the vector of partial derivatives.
  6. Complete the following experiments with the hill-climbing, random restart hill-climbing, and beam-forming algorithms using MATLAB.  Run each experiment 10 times, summarize the solutions that were found each time, and explain what you observe.  What would happen if you changed from taking the 7 best solutions to the 10 best solutions.  (Do not simply generate the plots from each experiment.  Presenting three or four plots is appropriate, but I am mostly interested in your summary of what you learn by repeating the experiments.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Create a grid of states     %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
x=[0:1:100];
y=[100:1:200];
% Create a function to be minimized over this grid
[X,Y]=meshgrid(x,y);  % A MATLAB shortcut
f = (X-50).^2 + 4*(Y-150).^2; f=-f;

figure(1);
clf;
surf(x,y,f);


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Hill Climbing               %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Pick a starting location, and try and find the maximum state by hill climbing.
s=floor(100*rand(2,1)) + [0;100];
hold on;
set(plot3(s(1),s(2),-((s(1)-50)^2 + 4*(s(2)-150)^2),'k.'),'markersize',15);
set(plot3(s(1),s(2),-min(min(f)),'k.'),'markersize',15);
% Generate successors, and compute the one with the maximum value.
% Only consider states to the N, S, E, W, and NoMove.
for (i=1:100)
    % Find successors
    s0=s;
    sE=s+[1;0];
    sW=s+[-1;0];
    sN=s+[0;1];
    sS=s+[0;-1];
    % Find values of the successors
    f0=-((s0(1)-50)^2 + 4*(s0(2)-150)^2);
    fN=-((sN(1)-50)^2 + 4*(sN(2)-150)^2);
    fS=-((sS(1)-50)^2 + 4*(sS(2)-150)^2);
    fE=-((sE(1)-50)^2 + 4*(sE(2)-150)^2);
    fW=-((sW(1)-50)^2 + 4*(sW(2)-150)^2);
    [v,vi] = max([f0,fN,fS,fE,fW]);
    switch (vi)
    case 1, s=s0;
    case 2, s=sN;
    case 3, s=sS;
    case 4, s=sE;
    case 5, s=sW;
    end;
    set(plot3(s(1),s(2),-((s(1)-50)^2 + 4*(s(2)-150)^2),'k.'),'markersize',15);     
    set(plot3(s(1),s(2),-min(min(f)),'k.'),'markersize',15);
end
hold off;
% Run this several times and watch how the path of states reaches the maximum of the surface.

%break

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Hill Climbing: Problems     %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Consider a surface with more than one bump
f = sqrt((X-50).^2 + 4*(Y-150).^2) + 20*cos(2*pi*X/30) + 20*cos(2*pi*Y/40); f=-f;

figure(2);
clf;
surf(x,y,f);
% Pick a starting location, and try and find the maximum state by hill climbing.
s=floor(100*rand(2,1)) + [0;100];
hold on;
set(plot3(s(1),s(2),-(sqrt((s(1)-50).^2 + 4*(s(2)-150).^2) + 20*cos(2*pi*s(1)/30) + 20*cos(2*pi*s(2)/40)),'k.'),'markersize',15);
set(plot3(s(1),s(2),-min(min(f)),'k.'),'markersize',15);
% Generate successors, and compute the one with the maximum value.
% Only consider states to the N, S, E, W, and NoMove.

%break;

for (i=1:100)
    % Find successors
    s0=s;
    sE=s+[1;0];
    sW=s+[-1;0];
    sN=s+[0;1];
    sS=s+[0;-1];
    % Find values of the successors
    f0=-(sqrt((s0(1)-50).^2 + 4*(s0(2)-150).^2) + 20*cos(2*pi*s0(1)/30) + 20*cos(2*pi*s0(2)/40));
    fN=-(sqrt((sN(1)-50).^2 + 4*(sN(2)-150).^2) + 20*cos(2*pi*sN(1)/30) + 20*cos(2*pi*sN(2)/40));
    fS=-(sqrt((sS(1)-50).^2 + 4*(sS(2)-150).^2) + 20*cos(2*pi*sS(1)/30) + 20*cos(2*pi*sS(2)/40));
    fE=-(sqrt((sE(1)-50).^2 + 4*(sE(2)-150).^2) + 20*cos(2*pi*sE(1)/30) + 20*cos(2*pi*sE(2)/40));
    fW=-(sqrt((sW(1)-50).^2 + 4*(sW(2)-150).^2) + 20*cos(2*pi*sW(1)/30) + 20*cos(2*pi*sW(2)/40));
    [v,vi] = max([f0,fN,fS,fE,fW]);
    switch (vi)
    case 1, s=s0;
    case 2, s=sN;
    case 3, s=sS;
    case 4, s=sE;
    case 5, s=sW;
    end;
    set(plot3(s(1),s(2),-(sqrt((s(1)-50).^2 + 4*(s(2)-150).^2) + 20*cos(2*pi*s(1)/30) + 20*cos(2*pi*s(2)/40)),'k.'),'markersize',15);
    set(plot3(s(1),s(2),-min(min(f)),'k.'),'markersize',15);
end
hold off;
% Run this several times and watch how the path of states reaches the maximum of the surface.
% notice how different maximum points are reached, depending on where things start.
% This is true even though there is only one true maximum.

% It turns out that for this world, neither Stochastic hill climbing not first-choice
% climbing will work.  Can you see why?

%break

% However, Random-restart hill climbing will work.  Let's try it out.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Hill Climbing: Random restart %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Consider a surface with more than one bump
f = sqrt((X-50).^2 + 4*(Y-150).^2) + 20*cos(2*pi*X/30) + 20*cos(2*pi*Y/40); f=-f;

figure(3);
clf;
surf(x,y,f);

best = -100000000;  % Best value found so far.

for (j=1:20)
    % Pick a starting location at random, and try and find the maximum state by hill climbing.
    % Repeat this a (to be precise, repeat it until j = 20).
    s=floor(100*rand(2,1)) + [0;100];
    hold on;
    set(plot3(s(1),s(2),-(sqrt((s(1)-50).^2 + 4*(s(2)-150).^2) + 20*cos(2*pi*s(1)/30) + 20*cos(2*pi*s(2)/40)),'k.'),'markersize',15);
    set(plot3(s(1),s(2),-min(min(f)),'k.'),'markersize',15);
    % Generate successors, and compute the one with the maximum value.
    % Only consider states to the N, S, E, W, and NoMove.
    for (i=1:100)
        % Find successors
        s0=s;
        sE=s+[1;0];
        sW=s+[-1;0];
        sN=s+[0;1];
        sS=s+[0;-1];
        % Find values of the successors
        f0=-(sqrt((s0(1)-50).^2 + 4*(s0(2)-150).^2) + 20*cos(2*pi*s0(1)/30) + 20*cos(2*pi*s0(2)/40));
        fN=-(sqrt((sN(1)-50).^2 + 4*(sN(2)-150).^2) + 20*cos(2*pi*sN(1)/30) + 20*cos(2*pi*sN(2)/40));
        fS=-(sqrt((sS(1)-50).^2 + 4*(sS(2)-150).^2) + 20*cos(2*pi*sS(1)/30) + 20*cos(2*pi*sS(2)/40));
        fE=-(sqrt((sE(1)-50).^2 + 4*(sE(2)-150).^2) + 20*cos(2*pi*sE(1)/30) + 20*cos(2*pi*sE(2)/40));
        fW=-(sqrt((sW(1)-50).^2 + 4*(sW(2)-150).^2) + 20*cos(2*pi*sW(1)/30) + 20*cos(2*pi*sW(2)/40));
        [v,vi] = max([f0,fN,fS,fE,fW]);
        switch (vi)
        case 1, s=s0;
        case 2, s=sN;
        case 3, s=sS;
        case 4, s=sE;
        case 5, s=sW;
        end;
        set(plot3(s(1),s(2),-(sqrt((s(1)-50).^2 + 4*(s(2)-150).^2) + 20*cos(2*pi*s(1)/30) + 20*cos(2*pi*s(2)/40)),'k.'),'markersize',15);
        set(plot3(s(1),s(2),-min(min(f)),'k.'),'markersize',15);
    end
    hold off;
    drawnow;
    fprintf(1,'Restart number %d\n',j);
    %pause(1);
   
    % What is the best solution found so far?
    v = -(sqrt((s(1)-50).^2 + 4*(s(2)-150).^2) + 20*cos(2*pi*s(1)/30) + 20*cos(2*pi*s(2)/40));
    if ((v > best) | (j==1))
        best = v;
        bestx=s(1);
        besty=s(2);
    end;
end;
[by,bx]=find(f==max(max(f)));  % Do an exhaustive search to find the true best.
fprintf(1,'The true best is (%d,%d).\n The best found by our search is (%d,%d).\n',x(bx),y(by),bestx,besty);
fprintf(1,'The true best value is %f.\n  The best found value is %f.\n',-(sqrt((x(bx)-50).^2 + 4*(y(by)-150).^2) + 20*cos(2*pi*x(bx)/30) + 20*cos(2*pi*y(by)/40)),-(sqrt((bestx-50).^2 + 4*(besty-150).^2) + 20*cos(2*pi*bestx/30) + 20*cos(2*pi*besty/40)))   
% Run this several times and watch how the path of states reaches the maximum of the surface.
% How few runs do you think it would take to guarantee that the true best solution would be reached with high
% probability?  Try changing the line "for j=1:20" to "for j=1:5" and see what happens.

%break

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Local Beam Search           %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Consider a surface with more than one bump
f = sqrt((X-50).^2 + 4*(Y-150).^2) + 20*cos(2*pi*X/30) + 20*cos(2*pi*Y/40); f=-f;
% Local beam search handles this a bit differently from the random restart searches.

figure(4);
clf;
surf(x,y,f);
% Pick seven starting locations, and try and find the maximum state by hill climbing.
sbeam=floor(100*rand(2,7)) + [zeros(1,7);100*ones(1,7)];
hold on;
%set(plot3(s(1),s(2),-(sqrt((s(1)-50).^2 + 4*(s(2)-150).^2) + 20*cos(2*pi*s(1)/30) + 20*cos(2*pi*s(2)/40)),'k.'),'markersize',15);
%set(plot3(s(1),s(2),-min(min(f)),'k.'),'markersize',15);
% Generate successors for each of these states, and compute the seven with the highest values.
% Only consider states to the N, S, E, W, and NoMove.
v = -10000000 * ones(1,7);  % The seven best values so far
bs = sbeam;  % The seven best states so far
for (i=1:100)
    % Find successors, and see if they are among the seven best.  Since I
    % have seven states and five successors for each state, I have 35 possible successor
    % states to consider.
    for (k=1:7)  % For each element in my beam
        s = sbeam(:,k);
        s0=s;
        sE=s+[1;0];
        sW=s+[-1;0];
        sN=s+[0;1];
        sS=s+[0;-1];
        % Find values of the successors
        f0=-(sqrt((s0(1)-50).^2 + 4*(s0(2)-150).^2) + 20*cos(2*pi*s0(1)/30) + 20*cos(2*pi*s0(2)/40));
        fN=-(sqrt((sN(1)-50).^2 + 4*(sN(2)-150).^2) + 20*cos(2*pi*sN(1)/30) + 20*cos(2*pi*sN(2)/40));
        fS=-(sqrt((sS(1)-50).^2 + 4*(sS(2)-150).^2) + 20*cos(2*pi*sS(1)/30) + 20*cos(2*pi*sS(2)/40));
        fE=-(sqrt((sE(1)-50).^2 + 4*(sE(2)-150).^2) + 20*cos(2*pi*sE(1)/30) + 20*cos(2*pi*sE(2)/40));
        fW=-(sqrt((sW(1)-50).^2 + 4*(sW(2)-150).^2) + 20*cos(2*pi*sW(1)/30) + 20*cos(2*pi*sW(2)/40));
        if (f0>min(v)) & (isempty(find(f0==v)))  % The right half of the and eliminates repeats so that the beam always has unique members.
            [tmp,m] = min(v);  % Find the arg min of v, and replace this one.
            bs(:,m) = s0;
            v(m) = f0;
        end;
        if (fN>min(v)) & (isempty(find(fN==v)))
            [tmp,m] = min(v);  % Find the arg min of v, and replace this one.
            bs(:,m) = sN;
            v(m) = fN;
        end;
        if (fS>min(v)) & (isempty(find(fS==v)))
            [tmp,m] = min(v);  % Find the arg min of v, and replace this one.
            bs(:,m) = sS;
            v(m) = fS;
        end;
        if (fE>min(v)) & (isempty(find(fE==v)))
            [tmp,m] = min(v);  % Find the arg min of v, and replace this one.
            bs(:,m) = sE;
            v(m) = fE;
        end;
        if (fW>min(v)) & (isempty(find(fW==v))) 
            [tmp,m] = min(v);  % Find the arg min of v, and replace this one.
            bs(:,m) = sW;
            v(m) = fW;
        end;
    end;
    sbeam=bs;  % Set the beam to the best successor states.
    % Plot the best state so far.
    [tmp,m]=max(v);
    best = bs(:,m);
    set(plot3(best(1),best(2),-(sqrt((best(1)-50).^2 + 4*(best(2)-150).^2) + 20*cos(2*pi*best(1)/30) + 20*cos(2*pi*best(2)/40)),'k.'),'markersize',15);     
    set(plot3(best(1),best(2),-min(min(f)),'k.'),'markersize',15);
end
hold off;

[tmp,m]=max(v);
best=sbeam(:,m);
bestx=best(1);besty=best(2);
[by,bx]=find(f==max(max(f)));  % Do an exhaustive search to find the true best.
fprintf(1,'BEAM SEARCH\n');
fprintf(1,'The true best is (%d,%d).\n The best found by our search is (%d,%d).\n',x(bx),y(by),bestx,besty);
fprintf(1,'The true best value is %f.\n  The best found value is %f.\n',-(sqrt((x(bx)-50).^2 + 4*(y(by)-150).^2) + 20*cos(2*pi*x(bx)/30) + 20*cos(2*pi*y(by)/40)),-(sqrt((bestx-50).^2 + 4*(besty-150).^2) + 20*cos(2*pi*bestx/30) + 20*cos(2*pi*besty/40)))   

% Run this several times.  Note that having a beam of width 7 makes it less likely that we will stumble into
% a local maximum, but it does not guarantee this --- especially since the best successors tend to cluster
% around a bit.  Would stochastic beam search help this?  Yes.