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:
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.