Programming Assignment 1: Blind Search in LISP

Weight: 5%
Due: Monday, February 9th, by 23:59
Group Size: 1-2
Programming Language: LISP

LISP is the second oldest high-level programming language and was the leading language in AI research from its infancy. It has greatly influenced other languages and computer science in general, for example by pioneering the tree data structure. It is therefore only appropriate that it is the language of choice for a “Blind Search” programming assignment - It is a basic AI problem solving technique that relies on the generation of a tree structure.

Consider this assignment as an opportunity to both write your own LISP code and to experiment with basic search strategies that underlie many important problem solving techniques.

You have an agent in a tiled environment of size W*H. The goal of the agent is to capture a bag of gold that is sitting somewhere in that environment. The agent can travel horizontally or vertically across clear tiles, but some of the tiles will actually contain impassable walls. Consider the edges of the environment also impassable.

The environment is fully observable and static, meaning that the agent can explore its full state space before executing its moves. The difficulty lies in the fact that it must try to come up with an optimal path from its current location to the bag of gold. To come up with this path, it should approach this as a search problem.

The project consists of the following steps:

1. Use the file search.lisp as a starting point. It contains some useful structures and functions.
2. Formulate the problem as a basic search problem (initial state, goal test, successor function) - write this information clearly as comments at the beginning of your file.
3. Implement a breadth-first (BF), depth-first (DF) and iterative-deepening DF (ID) search strategies. Try to re-use your search mechanism as much as possible (i.e. see if you can plug the search strategy into a general mechanism).
4. Compare your strategies by collecting performance measures, both for particular environments and averaged over runs of the search with different environments (a set of environments will be provided). The measures should include whether the gold was found (completeness), the length of the chosen path to the gold (optimality), the number of node expansions (time) and the maximum number of search nodes in the search tree (memory).
5. Write a summary of your findings - inside a comment block in the returned LISP file.
6. See if you can improve any of your strategies, for example by detecting loops. If you modify any of the basic strategies, make sure to explain the modification and include their performance measures alongside the other ones.
7. OPTIONAL BONUS: Feel free to explore the incorporation of heuristics, though this is not required. For example, would the A* algorithm perform much better than these basic ones? You can still get a full grade for this project if you omit this part, but doing it may give you some bonus points.

Submit a single zip or rar file into MySchool with all of the LISP code required to run your search tests. Include a readme.txt file that explains how to run the tests (when run, each test should print out the performance measures).

It is not necessary to visually show chosen paths (or even executing them for the agent), although such visualization would of course be nice when analyzing the characteristics of each strategy.