CS 453: Artificial Intelligence, Spring 2005
Information About the First Test

The first test for this course will be given in class on Monday, February 21. It will cover Chapters 2, 3, and 4 from the textbook, omitting Sections 3.6 and 4.5. It is important that you read this material. There might also be a short question on Lisp programming. I will not ask you to do any actual programming on the test. I might, however, ask you to give an outline of an algorithm or read a bit of Lisp code. Other than that, the test will consist of definitions, short-answer questions, and essay questions.

Here are some of the terms and ideas that you should be familiar with:

    agent                                     expanding a node                              
    intelligent agent                         fringe                                        
    rational agent                            completeness of a search strategy             
    environment                               optimality of a search strategy               
    sensors                                   time complexity                               
    actuators                                 space complexity                              
    percept                                   breadth-first search                          
    percept history                           depth-first search                            
    agent function                            uniform-cost search                           
    performance measures                      iterative deepening depth-first search        
    task environment                          bidirectional search                          
    PEAS descriptions                         avoiding repeated stated                      
    properties of task environments:          "closed" list (or "visited" list)             
       fully vs. partially observable         TREE-SEARCH vs. GRAPH-SEARCH                  
       deterministic vs. stochastic                                                         
       static vs. dynamic                     informed search                               
       discrete vs. continuous                heuristic function                            
       single agent vs. multiagent            f(n) = g(n) + h(n)                            
         (competitive or cooperative)         A* search                                     
   simple reflex agent                        admissible heuristic                          
   model-based reflex agent                   consistent heuristic                          
   goal-based agent                           how A* search decrease the number             
   planning                                      of nodes that have to be expanded          
   learning agent                             straight-line distance heuristic              
   vacuum cleaner worlds                      Manhattan distance heuristic                  
   thermostat agent                           local search                                  
   soda machine agent                         optimization problems                         
   conversation agent (eg, ALICE)             objective function                            
   poker-playing agent                        state space landscape                         
                                              hill-climbing                                 
   search                                     hill-climbing is greedy local search          
   uninformed search                          sideways moves in hill-climbing               
   problem-solving agent                      random-restart hill-climbing                  
   state space                                local beam search                             
   goals                                      genetic algorithm                             
   initial state                                fitness function, population of             
   goal test                                    possible solutions, reproduction,           
   successor function                           mutation, crossover                         
   actions
   path cost                                  LISP                                          
   solution of a problem                        atoms, lists, prefix notation, functions    ,
   optimal solution                             evaluation of atoms and list, recursion,    
   8-puzzle problem                             car, cdr, cons, quote, setq, defun,         
   missionaries and cannibals                   if, loop, return, cond, let                 
   8-queens problem
   shortest-path problem
   traveling salesman problem
   path tree
   nodes (in the path tree)
      state, parent node, action,
      path-cost, depth
   difference between nodes and states
   difference between path tree and state space