
University of Massachusetts Amherst


COMPSCI 683 
Artificial Intelligence 
Spring 2020 


Lecture 1: Introduction
[notes] Course information. The scope of artificial intelligence, its goals and achievements. Computer systems as intelligent agents. Types of environments, agents, and performance measures. Reading: R&N, Sections 1.12.5 in 3e (1.12.5 in 2e).  
Lecture 2: Problem solving as
search in a graph
[notes] Formulating problems as search in a graph. Measuring the performance of search techniques: completeness, optimality, time and space complexity. Blind search strategies: breadthfirst search, uniformcost search, depthfirst search, depthlimited search, iterative deepening search, bidirectional search. Efficient memory management. Reading: Sections 3.13.4 (3.13.7).  
Lecture 3: Heuristic search strategies
[notes] Guiding search using heuristic information. Greedy bestfirst search, A* and its properties, IDA*. The nature and origin of heuristics. Admissible evaluation functions. The effect of heuristic error. Reading: Sections 3.53.6 (4.14.2). Handout: Homework Assignment #1  
Lecture 4: Abstraction and hierarchical search techniques
[notes] Multilevel search, using abstraction to speed up search, hierarchical A*. Choosing good abstractions, computing abstract distances using pattern databases, disjoint pattern databases. Reading: "Hierarchical A*: Searching abstraction hierarchies efficiently," R.C. Holte, M.B. Perez, R.M. Zimmer, and A.J. MacDonald, Proc. of the 14th National Conference on Artificial Intelligence, 530535, 1996. "Disjoint pattern database heuristics," R.E. Korf and A. Felner, Artificial Intelligence, 134:922, 2002. (optional) "Multiple pattern databases," R.C. Holte, J. Newton, A. Felner, and R. Meshulam, and D. Furcy, Proc. of the 14th International Conference on Automated Planning and Scheduling, 122131, 2004.  
Lecture 5: Search and constraint satisfaction I
[notes] Constraint satisfaction problems (CSPs). Backtracking search for CSPs. Constraint propagation, arc consistency and Kconsistency. Reading: Sections 6.163 (5.15.3).  
Lecture 6: Search and constraint satisfaction II
[notes] Constraint satisfaction techniques continued. Intelligent backtracking. The tradeoff between constraint propagation and search. Local search for CSPs. Complexity and problem structure. Reading: Sections 6.56.6 (5.45.5). (optional) "Backjumpbased backtracking for constraint satisfaction problems," R. Dechter and D. Frost, Artificial Intelligence, 136:147188, 2002.  
Lecture 7: Beyond classical search
[notes] Local search algorithms: hillclimbing search, simulated annealing search, genetic algorithms. Searching with partial information. Searching in unknown environments. Reading: Sections 4.14.4 (4.34.5). Handout: Homework Assignment #2  
Lecture 8: Resourcebounded
search techniques
[notes] Handling the time and space complexity of heuristic search. Recursive bestfirst search (RBFS). Anytime A*. Reading: "Anytime heuristic search," E.A. Hansen and R. Zhou, Journal of Artificial Intelligence Research, 28:267297, 2007.  
Lecture 9: Adversarial search
[notes] Multiagent environments and games. Gameplaying as a search problem. Optimal decisions in twoplayer games. Imperfect, realtime decisions. Minimax and alphabeta pruning. Games that include an element of chance. Reading: Sections 5.15.7 (6.16.6).  
Lecture 10: Principles of knowledge representation and reasoning
[notes] Agents that reason logically. Principles of knowledge representation. The correspondence between symbolic structures and states of the world. The syntax and semantics of propositional logic and firstorder logic. Reading: Sections 7.17.4, 8.18.2 (7.17.4, 8.18.2).  
Lecture 11: Inference in propositional logic
[notes] Knowledge representation and reasoning in propositional logic, theorem proving using satisfiability, local search strategies, hardness of satisfiability. Forward and backward chaining. Inference using resolution. Reading: Sections 7.57.7 (7.57.7). "Local search strategies for satisfiability testing," B. Selman, H. Kautz, and B. Cohen, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26:521532, 1996.  
Lecture 12: Inference in firstorder logic
[notes] Knowledge representation and reasoning in firstorder logic. Representing change in the world. Matching and unification. Forward and backward chaining. Inference using resolution. Reading: Sections 9.19.6 (9.19.6). Handout: Homework Assignment #3  
Lecture 13: Reasoning with
uncertain information using Bayesian networks
[notes] The sources of uncertainty. Different approaches to representing and reasoning with uncertain information. Encoding probabilistic knowledge. Bayes' rule and Bayesian inference. Introduction to Bayesian networks. Graphical models and characterization of independence. The semantics of Bayesian networks. Query types and the complexity of evaluation. Reading: Sections 13.113.5, 14.114.3 (13.113.5, 14.114.3).  
Review Session The review session will be in class during the normal lecture time. This is an opportunity to go over sample midterm problems and discuss general questions.  
Midterm Exam See sample exams  
Lecture 14:
Bayesian networks  exact inference using variable elimination
[notes]
[video] Query types and the complexity of evaluation. The variable elimination algorithm. Dealing with evidence. Complexity and its dependence on the topology of the graph. Reading: Sections 14.4 (14.4). (optional) "Bucket elimination: A unifying framework for probabilistic inference," R. Dechter, Uncertainty in Artificial Intelligence, 211219, 1996. Handout: Homework Assignment #4  
Lecture 15:
Bayesian networks  approximate inference and RPMs
[notes]
[video] Inference in multiply connected belief networks. Clustering methods, cutset conditioning, and stochastic simulation. Relational probability models. Reading: Sections 14.514.6 (14.514.6). (optional) "Learning probabilistic relational models," L. Getoor, N. Friedman, D. Koller, and A. Pfeffer, In Relational Data Mining, S. Dzeroski and N. Lavrac, Eds, SpringerVerlag, 2001.  
Lecture 16:
Decisiontheoretic reasoning
[notes]
[video]
[office hours] Making optimal decisions by maximizing utility. The axioms of decision theory. Utility scales and utility assessment. Human judgment under uncertainty. Reading: Sections 16.116.4 (16.116.4).  
Lecture 17:
Decision networks and the value of information
[notes]
[video] Decision tree methods. The semantics of decision networks. Evaluating decision networks. The value of information. Reading: Sections 16.516.7 (16.516.7), "Evaluating influence diagrams," R. Shachter, Operations Research, 34:871882, 1986. (optional) "A new perspective on algorithms for optimizing policies under uncertainty," R. Dechter, Proc. of the Conference on AI Planning Systems, 2000. "Influence diagrams with memory states: Representation and algorithms," X. Wu, A. Kumar, and S. Zilberstein, Proc. of the 2nd International Conference on Algorithmic Decision Theory, 2011. Handout: Homework Assignment #5  
Lecture 18:
Planning
[notes]
[video]
[office hours] What is planning? Representations of operators and plans. Planning as statespace search, state progression, goal regression, and meansends analysis. Heuristics for statespace search. Search in space of partially ordered plans. Planning graphs. The complexity of planning. Sound and complete planning algorithms. Planning with partially instantiated operators. Reading: Sections 10.110.5 (11.111.5).  
Lecture 19: Planning under
uncertainty: MDPs
[notes]
[video] Formulating planning problems using Markov decision processes. Generating optimal action selection policies using value iteration and policy iteration. Solving Markov decision problems using heuristic search. The LAO* algorithm. Exploiting structured representations in stochastic planning. Reading: Sections 17.117.3 (17.117.3), "LAO*: A heuristic search algorithm that finds solutions with loops," E. Hansen and S. Zilberstein, Artificial Intelligence, 129(12):3562, 2001. (optional) "Optimal and approximate stochastic planning using decision diagrams," J. Hoey, R. StAubin, A. Hu, and C. Boutilier, University of British Columbia, Technical Report 0005, June 2000.  
Lecture 20: Planning under partial
observability: POMDPs.
[notes]
[video]
[office hours] Partially observable domains, belief states and beliefstate MDPs, valueiteration for POMDPs. Representing policies as finitestate controllers. Bounded policy iteration for POMDPs. Optimizing boundedmemory policies using nonlinear programming. Reading: "Planning and acting in partially observable stochastic domains," L.P. Kaelbling, M.L. Littman, and A.R. Cassandra, Artificial Intelligence, 101(12):99134, 1998. (optional) "Solving POMDPs using quadratically constrained linear programs," C. Amato, D.S. Bernstein, and S. Zilberstein, Proc. of the 20th International Joint Conference on Artificial Intelligence, 2007.  
Lecture 21: Reinforcement
learning
[notes]
[video] How to get intelligent systems to learn from success and failure, reward and punishment. Adaptive dynamic programming, temporal difference learning, learning actionvalue functions. RTDP and symbolic RTDP. Reading: Sections 21.121.7 (21.121.6). (optional) "Symbolic generalization for online planning," Z. Feng, E. Hansen, and S. Zilberstein, Proc. of the 19th Conference on Uncertainty in Artificial Intelligence, 2003. Handout: Homework Assignment #6  
Lecture 22: Multiagent
planning under uncertainty: Decentralized POMDPs
[notes]
[video] Modeling collaborative multiagent systems as decentralized MDPs. The complexity of planning. Dynamic programming algorithm for finitehorizon DECPOMDPs. Memorybounded approximation methods, the MBDP algorithm and its descendants. Reading: "The complexity of decentralized control of Markov decision processes," D.S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein, Mathematics of Operations Research, 27(4):819840, 2002. (optional) "Dynamic programming for partially observable stochastic games," E.A. Hansen, D.S. Bernstein, and S. Zilberstein, Proc. of the 19th National Conference on Artificial Intelligence, 2004. (optional) "Memorybounded dynamic programming for DECPOMDPs.," S. Seuken and S. Zilberstein, Proc. of the 20th International Joint Conference on Artificial Intelligence, 2007.  
[optional] Lecture 23: Computational models of bounded rationality
[notes]
[video]
[review session] Reasoning with limited computational resources. Simon's notion of "satisficing" and various ways to formalize it. The value of computation and ways to factor it into a decisionmaking process. Anytime algorithms and deliberation scheduling. Reading: "Using anytime algorithms in intelligent systems," S. Zilberstein, AI Magazine, 17(3):7383, 1996. (optional) "From substantive to procedural rationality," In Herbert Simon, Models of Bounded Rationality, Volume 2, MIT Press, 1982.  
[optional] Lecture 24: Summary and review for final exam
[video]
[review session] Course summary. Historical perspective on AI research: The legacy of Alan Turing. Discussion of selected problems from final exams. Reading: (optional) "Computing machinery and intelligence," A.M. Turing, Mind, 59:433560, 1950.  
Final Exam The exam will take place on Friday, May 1. Check the Exams page for further details. 
© 2020 Shlomo Zilberstein.