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