Artificial Intelligence Tentti 4.10.2004

You may answer either in Finnish or in English


1. Explain the following agent architectures (draw a picture of each of them) and discuss briefly their strengths and weaknesses.
   - stimulus-response agent
   - state machine
   - agent using an iconic representation
   
   
2. Explain the search routines depth-first search, breadth-first search and iterative deepening. Suppose that the shallowest goal node is at depth d and the search space has an uniform branching factor b. How much does each of these techniques consume space and time
   - in the best case and
   - in the worst case?
   
3. Function cons(x,y) denotes the list formed by inserting the element x at the head of list y. We denote the empty list with Nil; the list (2) by cons(2,Nil); the list (1,2) by cons(1,cons(2,Nil)) and so on. We have the following axioms:
   
   
   
   Prove the following theorem from these axioms by the method of resolution refutation.
   
   
   
   
4. Many search algorithms use some kind of a heuristic to guide their execution. How can an agent learn such heuristics itself?