Both sides previous revisionPrevious revisionNext revision | Previous revision |
public:t-622-arti-11-1:program_1 [2011/01/27 00:55] – hannes | public:t-622-arti-11-1:program_1 [2024/04/29 13:33] (current) – external edit 127.0.0.1 |
---|
===== Introduction ===== | ===== Introduction ===== |
| |
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 [[http://ana.lcs.mit.edu/~jnc//humour/lisp.tree|tree data structure]] - a basic AI problem solving technique that relies on the generation of a tree structure. It is, therefore, one of the best languages of choice for a "**Blind Search**" programming assignment. | 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 [[http://ana.lcs.mit.edu/~jnc//humour/lisp.tree|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. |
| |
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. | 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 asset code provided in step 1, since it is only written in LISP. | 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. |
| |
===== Description ===== | ===== Description ===== |
- Download and unzip the file {{:public:t-622-arti-11-1:search.zip|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. | - Download and unzip the file {{:public:t-622-arti-11-1:search.zip|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. |
- 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. | - 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. |
- Implement a **breadth-first** (**BF**), **depth-first** (**DF**) and **iterative-deepening** (**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). | - 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). |
- 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. | - 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. |
- Write a **summary** of your findings - inside a comment block in the returned LISP file. | - Write a **summary** of your findings - inside a comment block in the returned LISP file. |