Swedish web site
TDDC17 Artificial Intelligence
TDDC17-Lab2
Aim
The aim of this lab is for you to understand how different search strategies work, and to gain experience with a domain-specific application of search algorithms. You will explore the strengths and weaknesses of different search strategies and acquire deeper hands-on knowledge to complement your knowledge about search theory.Preparation
Read chapters 3 and 4 in the course book. All parts of ch. 3 and 4 are not required for completing the lab, but it is recommended that you do this in any case.About the lab
Your task in this lab is to study and compare different search algorithms. You will also study what happens when the different search algorithms are applied in a specific domain. You will run different search algorithms in the vacuum domain. The results you obtain will be the basis for an analysis of the applicability of the different algorithms in this domain. The analysis should include the time and space complexity of the algorithms, and whether they are optimal or complete. To help you in the analysis, there are a number of questions for you to answer. These lab exercises are more concerned with the analysis of algorithms and reasoning about their applicability rather than implementation.Lab system
The lab system can be found at http://www.ida.liu.se/~TDDC17/sw/aima/search/ and the lab itself has many similarities to the previous lab. The idea is to use a search agent, that reasons first about what to do and acts afterwards. The same domain is used as in the previous lab, i.e. the vacuum domain, but in this case, the agent will have complete knowledge about the world.Given a problem description, a vacuum search agent searches a sequence of actions that describe the movements that have to be made for it to clean all dirty squares and then return to the start position and shut itself down. A prerequisite for solution to this problem is that the vacuum agent has complete knowledge about the world, in particular about where the dirt is located. This implies that when the search is performed, no percepts are needed to act since complete information about the world is assumed and no dynamic changes occur other than those caused by the agent.
Search algorithms
Different search algorithms can be found at http://www.ida.liu.se/~TDDC17/sw/aima/search/algorithms/.The file http://www.ida.liu.se/~TDDC17/sw/aima/algorithms/simple.lisp contains functions for the basic search functions
breadth-first-search, depth-first-search, depth-limited-search, iterative-deepening-search. There are also search algorithms that use heuristic functions: uniform-cost-search, greedy-search, and a*-search. The heuristic function h that is used by greedy-search and a*-search to estimate the distance to the goal is defined for the vacuum domain as the number of pieces of dirt that are still left times two. The cost for each action is one.
The file http://www.ida.liu.se/~TDDC17/sw/aima/search/ algorithms/repeated.lisp contains algorithms with loop detection, such as no-cycles-depth-first-search. The loop detector no-returns makes sure that the algorithm does not generate nodes equal to the parent node. no-duplicates makes sure the algorithm avoids generating nodes that have been generated before and no-cycles makes sure no cycles are generated.
To create a problem
The search algorithms take a problem as input and return a sequence of actions that lead to a predefined goal. The problems can be generated using the constructor functions for the problem domain. The function vacuum-problem in the file http://www.ida.liu.se/~TDDC17/sw/aima/search/domains/vacuum.lisp
takes the size of the world in m x n squares as mandatory argument together with a list dirt with squares that are dirty and a probability factor dirt-probability for a square being dirty as an optional argument. If dirt is nil dirt is randomly assigned to all squares using dirt-probability, otherwise not. The constructor to specify a square is @ and takes an x-coordinate and a y-coordinate as arguments.
To create a vaccum problem with 2 x 2 squares and dirt at square (1 1), (the agent starts at square (0 0)), you write:
(setq vp (vacuum-problem 2 2 :dirt (list (list 1 1)))) which returns
#<vacuum world problem state:((1 0) ((1 1)) 2 2 T (0 0)), expanded: 0 > where
((1 0) ((1 1)) 2 2 T (0 0)) represents the root node in the search tree.
(1 0) is the agent's direction to the east.
((1 1)) represents the square with dirt.
2 2 is the size of the world.
T denotes the fact that the vacuum agent is switched on.
(0 0) is the agent's position.
To run search algorithms on problems
The agent solves a problem by building a search tree where each node represents a state. Every action transforms a state into a new state. For instance, if the agent goes forward in the start state, the next node/state is((1 0) ((1 1)) 2 2 T (1 0))
To solve a problem with a specific algorithm, use the function solve.
(solve vp :algorithm #'no-duplicates-breadth-first-search) prints the following information
Searching... Level Number of nodes in queue ===== ===== 0 1 1 4 2 7 3 8 4 8 5 7 6 5 7 5 8 7 9 7 ===== ===== Search completed! (FORWARD (TURN LEFT) FORWARD (TURN LEFT) SUCK FORWARD (TURN LEFT) FORWARD SHUT-OFF)#<NODE f(9) = g(9) + h(0) state:((0 -1) NIL 2 2 NIL (0 0)) >
F(9) means that the cost for the solution is 9 as the number of actions is 9 and each action costs 1. State represents the final state when the search is finished.
You can obtain more information by setting the argument print to t.
(solve vp :algorithm #'no-duplicates-breadth-first-search :print t) gives the following extra information
Action State
===== ======
((1 0) ((1 1)) 2 2 T (0 0))
FORWARD ((1 0) ((1 1)) 2 2 T (1 0))
(TURN LEFT) ((0 1) ((1 1)) 2 2 T (1 0))
FORWARD ((0 1) ((1 1)) 2 2 T (1 1))
(TURN LEFT) ((-1 0) ((1 1)) 2 2 T (1 1))
SUCK ((-1 0) NIL 2 2 T (1 1))
FORWARD ((-1 0) NIL 2 2 T (0 1))
(TURN LEFT) ((0 -1) NIL 2 2 T (0 1))
FORWARD ((0 -1) NIL 2 2 T (0 0))
SHUT-OFF ((0 -1) NIL 2 2 NIL (0 0))
===== ======
Total of 57 nodes expanded.
Note: Some of the algorithms may not find a solution in an acceptable time span and you will have to stop the execution.
Running the search algorithms with chrono
To be able to get information about the resources an algorithm uses to find a solution, you can use the function time which returns the search time as well as the amount of memory used during the search.(time (solve vp :algorithm #'no-cycles-breadth-first-search)) gives the extra information:
; cpu time (non-gc) 4,640 msec user, 360 msec system ; cpu time (gc) 350 msec user, 40 msec system ; cpu time (total) 4,990 msec user, 400 msec system ; real time 5,661 msec ; space allocation: ; 394,524 cons cells, 6,613 symbols, 414,696 other bytes
Running the search algorithms in the vacuum world
To run a search agent in the world as defined in the problem you can use the function run-problem which returns the points for a vacuum agent that uses search:
(run-problem vp :algorithm #'no-duplicates-depth-first-search :display t)
Comparing different algorithms
You can also compare different search algorithms using the function compare-search-algorithms which returns a table with information about the different algorithms' efficiency, among which are the cost and the number of expanded nodes.
(compare-search-algorithms
#'(lambda ()
(vacuum-problem 3 3 :dirt nil))
'(a*-search no-duplicates-breadth-first-search))
returns
Solved Cost Length Nodes Algorithm ====== ====== ====== ======= ========= 10 10.8 10.8 335.7 A*-SEARCH 10 10.8 10.8 398.5 NO-DUPLICATES-BREADTH-FIRST-SEARCHThis means that a*-search found a solution in 10 out of 10 cases; that the cost for the length of the solution was 10.8 in average; and that the algorithm expanded on average 335.7 nodes.
Note! You have to use a lambda-expression. Otherwise the world is not re-initialized between the different executions for the different algorithms.
Task
- Start Allegro from a shell with:
emacs-allegro-cl
:ld ~TDDC17/www-pub/sw/aima/aima(aima-load 'search)
- Conduct a fairly scientific evaluation of the search algorithms to evaluate the theory using the questions listed in the next section.
Questions and Tasks
In your report, you will have to answer all the questions and perform all the tasks in the following list:
1. In the vacuum cleaner domain, what are the states and actions? What is the branching factor?
2. What is the difference between breadth-first search and uniform cost search in a domain where the cost of each action is 1?
Run the two algorithms and compare them. Explain your results.
3. If one would use A* to search for a path to one specific square in the vacuum domain, what could be the heuristic (h)? The cost function (g)? Is it an admissable heuristic?
4. What is the difference between using duplicate-checking in breadth-first and in depth-first search?
5. Run the algorithms iterative-deepening, depth-first and breadth-first and compare them using different types of loop detection (e.g none at all, no-cycles, no-duplicates). Explain why the time and space complexities differ in the manner they do. If any of the algorithms fail due to an infinite loop, explain why.
6. Compare A* with greedy-search empirically and explain the result.
7. Draw and explain. Choose your three favourite search algorithms and apply them to any problem domain (it might be a good idea to use a domain where you can identify a good heuristic function). Draw the search tree for them, and explain how they proceed in the searching. Also include the memory usage.
8. Look at all the offline search algorithms presented in chapter 3 plus A* search. Are they complete? Are they optimal? Explain why!
9. Assume that you had to go back and do lab 1 once more (please feel free to do so if you like!). How would you then use offline search to guide the agent's execution? If you already used search, would you change the search algorithm? Why, or why not?
Examination
Write a report where you present what has been done and which includes answers to the questions above and presents the results of all the tasks.Note!
- In order to evaluate the efficiency of the algorithms - create at least three different problems that are increasingly difficult to solve. Note! If you create a problem by setting a variable to the value of a vacuum-problem, then that variable will contain information about how many nodes have been expanded in order to solve the problem, a number which will be incremented each time the algorithm is run.
- Note! To be able to test
depth-limited-searchyou will have to define your own functions that you have to run.
(defun depth-limited-search-5 (problem) (depth-limited-search problem 5))
(solve vp :algorithm #'depth-limited-search-5)
Page responsible: Fredrik Heintz
Last updated: 2012-08-17
