Programming Assignment 1: Implementing Blind Search

Weight: 5%
Due: Thursday, February 10th, by 23:59
Group Size: 1-2
Programming Language: LISP or Another Language of your choice

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 because basic AI problem solving techniques rely on its generation and manipulation. It is, therefore, one of the best languages of choice for a “Blind Search” programming assignment.

This assignment is an opportunity to experiment with basic search strategies that underlie many important problem solving techniques. But also consider the assignment an opportunity to write some classic LISP code.

However, you are absolutely free to use a programming language of your choice (i.e. Python, Java, C++, …). In that case, however, you will not be able to take advantage of the helper code provided in step 1, since it is only written in LISP.

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. Download and unzip the file search.zip into your working directory. You will use the file search.lisp as a starting point. It contains some useful structures and functions. Read the comments above each function in order to have an overall idea before you start.
   NOTE: you should take a look at this file also if you are using a different programming language. You might implement the same functions in order to have the same settings, in addition you can take inspiration on how to define/create environments.
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 depth-first (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 is provided into the assets file). 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).
   NOTE: if you are not using LISP, you could define several environments in a text file using your own notation (i.e. you can have several lines describing each one a row in your environment. In each line, you can use '0' for empty squares, 'W' for impassable walls and 'G' for gold. You can separate different environments with an empty line). Then you can read the environments from that file and you should be able to experiment different performances by simply changing the file contents and running again your program without any change to your source code.
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 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). NOTE: if you use a compiled language (i.e. C or C++), in addition to the source code you have to submit the binary compiled version too.

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.