Chapter 1: Understand figure 1.1 *** I do not expect you to know all the names and terms in this chapter. It is a particularly tough chapter because as an introduction to the book, it introduces many terms without explaining them. syllogisms satisficing operations research intractability cognitive science control theory Allen Newell Herbert Simon Turing Test physical symbol system Why is linguistics so frequently paired with AI? Understand the major catergories in AI's development as described in section 1.3. In particular, try to identifiy the problems of choice of each era and the fundamental tools researchers thought were best suited to those problems. Chapter 2: agent sensors actuators percept rational agent performance measures What are the properties of task environments? observability, stochasticity, temporality, continuity... PEAS What is a "model" in the context of agent programs? goals vs. utility functions How do models, goals, and utility functions influence the way an agent program might work? Why is there randomness in agent programs? Problems 2.10 and 2.11 Chapter 3: Make sure you've reviewed Appendix A for coverage of NP Complete and big-Oh notation Know the parts of a well-defined problem and how to define a general problem in these terms. Why does breadth-first search generate O(b^(d+1)) nodes? and why is this equivalent to the space complexity? Could you write a breadth-first search with O(b^d) space complexity? When would the branching factor be infinite? how about max depth? When is iterative deepening depth-first search a particularly wasteful technique? What are we gaining/losing with the iterative algorithm compared to others? What if memory is cheap relative to computation? Understand why uniform-cost search space and time complexity of O (b^(ceil(C*/epsilon))) Why is iterative deepening BFS preferred when the search space is large and the depth of the solution is unknown? How can you avoid repeated states and what is the cost? What does optimal mean in the context of searching? Problems 3.7, 3.8, 3.9(a, c), 3.12, 3.13, 3.17(a, d) Chapter 4: Why is greedy not optimal an incomplete? admissible heuristic consistent heuristic What happens if a heuristic is admissible but not consistent? Can a heuristic that is consistent not be admissible? What is a contour? optimally efficient What is a shortcoming of IDA* Explain how RBFS may explore same state many times. Why would SMA* ever become intractable for computation time? meta learning Manhattan distance If a heuristic is learned from experience like the one described in the text book, will it be admissible and consistent? Know the varieties of hill climbing Why is local beam search not simply parallel hill climbing? gradient Newton-Raphson Hessian Problems 4.1, 4.3, 4.11 Chapter 6: zero-sum games pruning What is an optimal strategy? What is a "feature" of an evaluation function? What is the horizon effect and how could a competitor take advantage of this weakness in an opponent? Be able to graphically indicate minimax and alpha-beta. *** No card games Know the basics of 6.6 Problems 6.1, 6.2, 6.14, Chapter 7: be familiar with the Wumpus world syntax vs. semantics does entailment == implication? truth tables Backus-Naur Form (BNF) Figure 7.11 Modus Ponens How is proving like searching? What does it mean to say that proving can be an efficient process because you can ignore all irrelevant propositions? monotonic Understand: "Any complete (remember the def of complete!) search algorithm, applying only the resolution rule, can derive any conclusion entailed by any knowledge base in propositional logic", p. 214 satisfiability and proof by contradiction Why are conjunctive normal form (CNF) and Horn clauses a good thing in the context of proving? Can we guarantee that any knowledge base can be converted into Horn clauses? If so, what does this buy us? Simpler search algorithms? More certainty that we'll find an answer? forward chaining: PL-FC-Entails() backtracking: WalkSAT() critical point *** No circuit-based agents Problems: 7.1, 7.4, 7.8, convert sentences of 7.8 to CNF and Horn Clauses Chapter 8: What is the role of first-order logic? Why do we care about it? ontology epistemological commitment FOL syntax - arity, symbols quantifiers and complex complex sentences axioms vs. theorems wumpus world - understand the game diagnostic rules vs. causal rules diagnostic vs. model-based reasoning knowledge engineering, knowledge base Chapter 9: what does "lifting" mean in this context? universal/existential instantiation Skolem constant transforming FOL to propositional logic - limitations, semidecidable unification implementations of storage/retrieval first-order definite clause first-order literals proof trees Col. West forward-chaining example - most constrained variable - efficiency in forward chaining (matching rules, incremental, irrelevant facts) soundness and completeness of inference algorithms know the basic backward-chaining algorithm understand how forward/backward chaining are interchangeable *** don't need to parts of 9.4 starting from "Logic Programming" resolution why are resolution proofs of existential goals nonconstructive? completeness of resolution - refutation complete *** nothing from pages 300-308 why is logical inference used as theorem prover? - what is practical use?