CECS 375 Assignment 2: Intro to Search

Due Monday, Sept. 29 by noon, Email your work to Matt Williams at mgw5a2@mizzou.edu. As before, include a log file that illustrates your program execution. And always use meaningful variable names and helpful comments.

The assignment is worth 8% of your semester grade.

This assignment is adapted from Problems 3.15 and 4.17 and uses Figure 3.22 in the text.

1. Do problem 3.15 as outlined in the text.  This includes answering some questions and writing some lisp code. For part (d), choose one algorithm from chapter 3, implement it in lisp, and try it out on several problems using different starting points and goal points. Track the performance for each test case. Note: the (x,y) coordinates are not given for the obstacles in Figure 3.22; estimate them from the figure so you have an (x,y) point for each vertex.

2. Implement the A* algorithm and try it out with the environment in Figure 3.22, using the straight-line distance as the heuristic. Again, test it using the same set of starting points and goal points as in part 1 above. Compare the performance with your algorithm in part 1.

3. Repeat for the hill-climbing algorithm. Again, track the performance. Does your agent ever get stuck in a local minimum? Is it possible for it to get stuck with convex obstacles?

4. Construct an environment with nonconvex obstacles in which the agent does get stuck using the hill-climbing algorithm and illustrate this with a test.