15-281 - Fall 2020

Artificial Intelligence:
Representation and Problem Solving


Key Information

Mondays 1:30pm - 2:50pm, Tuesdays 8:30am - 9:50am

Wednesdays 1:30pm - 2:50pm

Gianni A. Di Caro

12.0

30% Final, 10% Midterm, 40% Homework, 20% Project

(optional) S. Russel and P. Norvig, Artificial Intelligence: A Modern Approach (3rd edition, 2010)

Overview

This course is about the foundations of theory and practice of Artificial Intelligence. But, what AI means/is?
A number of different definitions of AI have been given so far. In general, all include the underlying idea of equipping machines (e.g., computer programs, robots) with "tools" to display behaviors that we, as humans, would be inclined to categorize as "intelligent". This is still quite vague, since it requires to clarify in turn what an intelligent behavior is.

In this course, this is issue is somehow narrowed down to the concept of rationality : the notion of Artificial Intelligence is treated as equivalent to that of Computational Rationality. Given well defined preferences, a rational agent always selects the actions whose outcomes result in the maximization of the expected utility.

The course will provide an overview of modern techniques for rational decision-making under different conditions regarding available information, certainty or uncertainty of the information, presence of one or more agents in both cooperative and adversarial scenarios.

More precisely, during the course, fundamental questions about the design of AI systems will be addressed, such as:

  • how to represent knowledge,

  • how to effectively generate provably optimal sequences of actions, (i.e., how to make optimal decision plans or define decision policies);

  • how to search among (large sets of) alternatives to find optimal or near-optimal solutions;

  • how to learn to make optimal decisions.

Both deterministic and stochastic environments will be considered and treated separately.

Machine learning techniques will be introduced for dealing with supervised classification and regression tasks. Specialized deep learning techniques will be also considered, for image classification tasks. Reinforcement learning will be studied for sequential, interactive decision-making in unknown environments. Decision-making in multi-agent systems will be also investigated, considering multiple agents with conflicting goals (known as games) under different conditions and available information.

Objectives

There are three primary objectives for the course:


  • To provide a broad survey of AI and of the most popular techniques that are employed for: knowledge representation, problem solving, mathematical optimization, automated planning, probabilistic prediction and inference, sequential decision-making, supervised and reinforcement learning, deep learning, decision-making in multi-agent adversarial scenarios.

  • To develop a thorough understanding of the algorithmic foundations of AI and acquire a strong appreciation of the big-picture aspects of designing fully autonomous intelligent agents.

  • To develop operational known-how about how to build/program AI agents, and analyze and improve their performance.

Course Layout

The course will be based on lectures. Students are expected to attend all classes and to actively participate with questions. Each lecture will feature a number of Quizzes to let the students engaged and the instructor check the understanding of the contents from the students as they are delivered.

For each one of the different topics, the course will present relevant techniques, discuss formal results, and show the application to problems of practical and theoretical interest. Weekly recitations will be used to practice together with the algorithms and their application to different problems.

Homework will be assigned (approximately) weekly. Each homework will include both questions to be answered and programming assignments. Written questions will involve working through different algorithms, deriving and proving mathematical results, and critically analyzing the material presented in class. Programming assignments will mainly involve writing code in Python to implement and test algorithms.

During the last four weeks, the students will work on a project that will let them experiencing with and comparing the different approaches presented during the course on a challenging scenario of practical interest.

Prerequisites

Since the course will cover a number of different topics, students should have some background in programming (in Pyhton), algorithms, calculus, linear algebra, and probability theory. Please talk to the instructor if you are unsure whether your background is suitable for the course.

The formal prequisites for this course are:

  • 15-122 Principles of Imperative Computation
  • 21-241 Matrices and Linear Transformations
  • 21-127 Concepts of Mathematics or 15-151 Mathematical Foundations of Computer Science.

The corequisite for this course is:

  • 21-122 Integration and Approximation

For this corequisite, you should either have completed it prior to starting 15-281 or have it on your schedule for Spring 2020.

Grading

Grading will assigned based on the following weighting: 40% Homework, 30% Final exam, 10% Midterm exam, 20% Project. The final exam will include questions about all topics considered in the course, with an emphasis on the topics introduced after the midterm exam.

Readings

There is no required textbook for this class. The students should be able to learn everything from lecture handouts and homework. However, the Russel and Norvig textbook will cover good parts of the course. During the course, other books will be pointed out by the instructor to cover specific parts of the course.

Schedule (subject to changes)

Dates Topic Slides References
8/24 Introduction: Concepts, History, Definitions, Problems, Road map R&N Ch. 1,2,26,27, Brief AI history, 2016 Stanford AI report
8/25 AI Problems and agents, Search problems: Taxonomy of problems and types of agents; planning and search problems; performance metrics; search meta-algorithms: Tree and Graph search; Informed vs. Uninformed search R&N Ch. 3
8/26 Uniformed search: BFS, UCS, DFS, DL-DFS, IDS R&N Ch. 3
8/31 Informed Search: A*, Properties and applications R&N Ch. 3
9/1 Informed Search for Path planning problems: Theta* paper at AAAI-07
9/2 Recitation: Search algorithms
9/7 Adversarial search 1: Adversarial scenarios and games; types of games; zero-sum games and minimax search; algorithm and properties; evaluation functions; minimax for n players; tree pruning and alpha-beta pruning R&N Ch. 5
9/8 Adversarial search 2: Adversarial search under uncertainty; role of chance; probabilities, expected values, and expectimax search; algorithm and properties; (no) pruning. R&N Ch. 5
9/9 Recitation: Adversarial search
9/14 Classical planning 1: Factored states, Description language, Forward and Backward search R&N Ch. 10
9/15 Classical planning 2: Planning graphs, GRAPHPLAN, Relaxed plans, Domain-independent heuristics R&N Ch. 10
9/16 Recitation: Classical planning
9/21 Constraint Satisfaction Problems (CSPs) 1: Definitions and Taxonomy, Backtracking, Arc consistency, Constraint propagation, Pruning R&N Ch. 4, 6
9/22 Constraint Satisfaction Problems (CSPs) 2, Local search: CSP: Inference-propagation methods; Local search and local search methods for CSP; hill-climbing; WalkSAT
 R&N Ch. 4, 6
Paper on WalkSAT (Local search for max-SAT) in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, 1996
9/23 Recitation: CSPs
9/28 Optimization models 1, Convex optimization: Optimization problems; General concepts and notation; Convex problems; Properties of convex optimization; Gradient methods Survey on gradient descent algorithms
9/29 Optimization models 2, Integer optimization: Integer optimization problems; properties, modeling and solution approaches; branch and bound Branch-and-Bound, book chapter
9/30 Recitation: Optimization models and methods
10/5 Probabilistic models: Review of probabilities; joint probability distributions; conditional probabilities; Bayes rules; chain rule
10/6 Random processes: Prediction and analysis of random processes; Markov property; taxonomy of Markov Processes; rewards and policies. Markov chains, general properties and formalism; limiting and Stationary distributions in Markov Chains; state classification R&N Ch. 15
S. Ross, Introduction to probability models, Ch. 4
10/7 Recitation: Probabilities and random processes
10/12 Fall break
10/13 Fall break
10/14 Fall break
10/19 Bayesian Networks 1: Grahical models; Conditional probability network; BN Construction, Global and local semantics, Information propagation R&N Ch. 13, 14
10/20 Bayesian Networks 2: Exact inference, Sampling-based methods for inference R&N Ch. 13, 14
10/21 Recitation: Bayesian networks
10/26 Hidden Markov Models (HMM) 1:Partial state observability; sensor model; reasoning over sequences and HMM formalism; probabilistic model; HMM for inference tasks: filtering, prediction, smoothing, explanation; application examples; filtering algorithm R&N 15.2 - 15.6
10/27 Hidden Markov Models (HMM) 2: Robot localization problems; Particle filtering, sampling and resampling; application to SLAM problems. R&N 15.2 - 15.6
10/28 Recitation: HMM
11/2 Markov Decision Processes 1: Utilities, Bellman equations, Policy evaluation R&N Ch. 17
Book extract on variants of Value Iteration
Diagram summarizing course topics + MDPs
11/3 Markov Decision Processes 2: Value Iteration, Measures of convergence of Value Iteration, Variants of Value Iteration, Policy Iteration Bellman-Ford algorithm, deterministic dynamic programming, asynchronous, distributed
11/4 Recitation: MDPs
11/9 Reinforcement Learning 1: Models, challenges, Monte Carlo, Temporal Differences R&N Ch. 21
Sutton and Barto RL book, May'18 Draft
11/10 Reinforcement Learning 2: Active RL, Exploration vs. exploitation, Monte Carlo action learning, SARSA, Q-Learning Diagram summarizing the topics investigated in the RL lectures
11/11 Recitation: RL
11/16 Reinforcement Learning 3: Dealing with large state-action spaces; approximation methods; value function approximation
11/17 Reinforcement Learning 4: Approximate methods for online policy control; policy gradient methods; deep reinformement learning
11/18 Recitation: RL and approximation
11/23 Game Theory 1: General Concepts, examples, dominance, Nash equilibrium R&N Sec. 17.5-17.6
Book on Multi-agents systems, Ch. 3-4
11/24 Game Theory 2: Mixed strategies, computing Nash equilibria, game formalization and analysis using algebra and calculus
11/25 Recitation: Game Theory
11/30 Game Theory 3: Correlated equilibrium, Stackelberg games, security games
12/1 Game Theory 4: Social choice, voting theory
12/2 Ethics and AI

Homework Assignments

Topic Files Due Dates
HW 1: Problems and Agents, Uninformed Search
HW 2: Informed Search
HW 3: Adversarial Search
HW 4: Classical planning
HW 5: Constraint Satisfaction Problems
HW 6: Modeling and solving optimization problems
HW 7: Probabilistic modeling, Markov chains
HW 8: Bayesian networks
HW 9: Hidden Markov Models
HW 10: Markov Decision Processes for sequential-decision making
HW 11: Reinforcement learning with tabular methods
HW 12: Reinforcement learning with approximation methods
HW 13: Game Theory for multi-agent adversarial scenarios

HW Policies

  • Homework is due on Autolab by the posted deadline. Assignments submitted past the deadline will incur the use of late days.

  • You have 6 late days, but cannot use more than 2 late days per homework. No credit will be given for homework submitted more than 2 days after the due date. After your 6 late days have been used you will receive 20% off for each additional day late.

  • You can discuss the exercises with your classmates, but you should write up your own solutions. If you find a solution in any source other than the material provided on the course website or the textbook, you must mention the source. You can work on the programming questions in pairs, but theoretical questions are always submitted individually. Make sure that you include a README file with your andrew id and your collaborator's andrew id.

  • In general, for both assignments and exams, CMU's directives for academic integrity apply and must be duly followed. Students are required to refer to CMU's general policies on cheating and plagiarism: https://www.cmu.edu/policies/student-and-student-life/academic-integrity.html

Exam dates and policies

The class includes both a midterm and a final exam. The midterm is set for TBD and the final for TBD.

During exams students are allowed to consult 1-page cheatsheet (written in any desired format). No other material is allowed, including textbooks, computers/smartphones, or copies of lecture handouts.

Students with special needs or disabilities are kindly asked to talk about it to the teacher at the beginning of the semester and make use of the assistance procedures provided by CMU https://scotty.qatar.cmu.edu/qword/student-affairs/office-of-health-and-wellness/assistance-for-individuals-with-disabilities

Office Hours

Name Email Hours Location
Gianni Di Caro gdicaro@cmu.edu Thursdays 1:30-2:30pm + Drop in at my office any time ... M 1007