## CS 453: Artificial Intelligence, Spring 2005

Information About the First TestThe 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