Reading:

• R&N: Chapter 3, Sections 4.1-2

Problem 3.1 [10 points]

Problem 3.2 [10 points]

Problem 3.3 [20 points]

• Problem 4.1 of R&N. Draw a figure as in Figure 4.3(f), page 98 of R&N but make sure each node is labeled with f=g+h and a circled number relating to its order of expansion.

• Redo using a different heuristic, h', based on h and one-step look-ahead. That is, let

  h' (n) = min over all i that are successors n of { c(n,i) + h(i) }.

Problem 3.4 [5 points]

Problem 3.5 [5 points]

The following problem requires signficant programming:

Problem 3.6 [50 points]

Specifically, you are to implement routines that solve planning problems that take place in an N by M grid of cells, with initial and goal cells specified by integer pairs: (iinit, jinit) and (igoal, jgoal). The actions available are moving left (decrementing i), right (incrementing i). down (decrementing j), and up (incrementing j). Moves are possible only if the destination cell is within the grid and not an obstacle cell. Each move has a cost of 1.

In all cases, the cost-to-reach is the number of moves and the heuristic estimate of the cost-to-go you should use is the "straight-line" Manhattan distance, that is, the sum of the absolute differences in both dimensions (which is admissible because it is the cost associated with the relaxed problem involving no obstacles). For example,

h(xinit) = | iinit - igoal | + | jinit - jgoal |

1. Implement a general program for such worlds with routines for
   1. Breadth-First Search (BFS)
   2. Greedy Best-First Search
   3. A*
   In each case, implement your routine according to the template in Figure 3.19 (page 83) of R&N. Turn in your code.
2. As a test, try your routines on the example grid we used in class on 31 JAN. Briefly comment on, but do not turn in, your results.
3. Run your routines on the 100 by 100 discrete "bug trap" problem [from an early edition of Steve LaValle's Planning Algorithms], with initial, goal, and obstacle locations given by the following pseudo-code:

   (iinit,jinit)=(50,55);
   (igoal,jgoal)=(75,70);
   
   obs=zeros(100,100); % initialize to "no obstacles"
   for i=1:100,
     for j=1:100,
       if i<50,    % rear of bugtrap
         d=abs(i-51)+abs(j-50);
         if d==50, obs(i,j)=1;  end;
       else        % front of bugtrap
         if j>50,  % upper lobe
           d=abs(i-50)+abs(j-75);
           if d==24, obs(i,j)=1; end;
         end;
         if j<50,  % lower lobe
           d=abs(i-50)+abs(j-25);
           if d==24, obs(i,j)=1; end;
         end;
       end;
     end;
   end;
   

   For each of the three routines, report the number of cells in closed, the number of cells on fringe, and the length of the path found. There is no need to draw/report the path.

4. Repeat the experiment above with the initial and goal points reversed.
5. Comment on your results and on the potential of bidirectional search for this class of problems.

Problem G3.1 [10 points]

Problem G3.2 [10 points]