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 decisionmaking 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 nearoptimal solutions;
how to deal with uncertainity;
how to take decisions in adversarial environments;
how to learn to make optimal decisions.
Both deterministic and stochastic environments will be considered and treated separately.
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 decisionmaking, supervised and reinforcement learning, deep learning, decisionmaking in multiagent adversarial scenarios.
To develop a thorough understanding of the algorithmic foundations of AI and acquire a strong appreciation of the bigpicture aspects of designing fully autonomous intelligent agents.
To develop operational knownhow about how to build/program AI agents, and analyze and improve their performance.
Students are expected to attend all classes and to actively participate with questions.
Each theory lecture will feature short Quizzes at the beginning and at the end of the lecture.
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 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 involve writing code in Python to implement and test algorithms.
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:
The corequisite for this course is:
For this corequisite, you should either have completed it prior to starting 15281 or have it on your schedule for Spring 2023.
Grading will assigned based on the following weighting: 40% Homework, 30% Final exam, 10% Midterm exam 1, 10% Midterm exam 2, 10% Quizzes. The final exam will include questions about all topics considered in the course, with an emphasis on the topics introduced after the first midterm exam.
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 (available on Canvas) 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.
Dates  Topic  Slides  References  

8/3  AI Problems and agents, Search problems: Taxonomy of problems and types of agents; planning and search problems; performance metrics; search metaalgorithms: Tree and Graph search; Informed vs. Uninformed search  R&N Ch. 3  


8/7  Uninformed search: BFS, DFS, DLDFS, IDS, UCS: algorithms and properties  R&N Ch. 3  
8/10  Recitation: Search algorithms  PDF no solutions  


8/16  Adversarial search 2: More on minimax search; running examples; coordination and cooperation; analysis of properties; depthlimited approaches; evaluation functions; tree pruning and alphabeta pruning; role of ordering and ordering heuristics. (no) pruning.  R&N Ch. 5  
8/17  Adversarial search 3: Search under uncertainty; expectimax search;
properties; probabilistic models, role and impact; other types of games. Recitation: Adversarial search 
PDF Recitation PDF no solutions 



8/23  Classical planning 1: Factored states; STRIPS/PDDL description language; states as conjuction of propositions; structure of actions; goals and subgoals; planning problem: domain, instance, planner; complexity of planning; forward search for planning; quest for heuristics; ignore preconditions and domainindependent heuristics.  R&N Ch. 10  
8/24  Classical planning 2: DomainIndependent heuristics, issues using ignore preconditions; backward search: regression on actions, action selection, state sets; planning graphs for domainindependent heuristics and solution finding: construction, mutex links, properties, use for domainindependent heuristics; GRAPHPLAN algorithm: extract solution and backward search, properties, solutions.  R&N Ch. 10  


8/30  Constraint Satisfaction Problems (CSPs) 2, Local search: Arc
consistency; constraint propagation (inference, message passing); pruning by
inferencepropagation; AC3; Forward checking; Maintaining Arc Consistency
(MAC); complexity and properties of pruning methods; Local search and local
search methods for CSP; hillclimbing; WalkSAT 
R&N Ch. 4, 6 Paper on WalkSAT (Local search for maxSAT) in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, 1996 

8/31  Recitation: CSPs  


9/6  Optimization models 2, Integer optimization: Integer optimization problems; properties, modeling and solution approaches; branchandbound: divideandconquer idea, subproblems and relaxations, MIP gap, anytime properties, design strategies.  BranchandBound, book chapter  
9/7  Recitations: Optimization models and methods  


9/13  Review of concepts so far  
9/14  Midterm Exam 1  


9/18  Fall break  
9/20  Fall break  
9/21  Fall break  


9/27  Bayesian Networks 2: Exact inference by enumeration; complexity of the exact inference; expression trees for optimized computations; approximate inference methods based on sampling / Monte Carlo approaches; direct sampling from Bayesian network; sampling in presence of evidence; rejection sampling; likelihood weighting; limitations of incremental sample construction methods and statebased approaches; Gibbs sampling and Markov Chain Monte Carlo; sampling from a Markov blanket; notion of stationary distribution for state probabilities; Gibbs sampling at work (with exact inference).  R&N Ch. 13, 14  
9/28  Recitations: Bayesian networks  


10/4  Markov Chains 2, Hidden Markov Models (HMM):Review of different cases
for limiting and stationary distribution; state classes: absorbing, periodic,
aperiodic, transient, peristent, recurrent, ergodic; communication classes;
irreducible chains; regular chains; ergodic chains and their properties. Partial state observability; sensor model; reasoning over sequences and HMM formalism; probabilistic model as a Bayesian network; HMM for inference tasks: filtering and prediction; separate belief updates and joint belief updates. 
PDF Markov chains 2 PDF HMMs 
R&N 15.2  15.6  
10/5  Recitations: Markov chains, HMMs  


10/11  Markov Decision Processes 2: Bellman optimality equations; Value Iteration; measures of convergence of Value Iteration; Policy Iteration  BellmanFord algorithm, deterministic dynamic programming, asynchronous, distributed  
10/12  Recitations: MDPs Markov Decision Processes 3: LP formulation, converge properties, different forms of implementing Value Iteration: asynchronous, inplace (GaussSiedel), prioritized, prioritized sweeping, partitioned 
Book extract on variants of Value Iteration  


10/18  Midterm review  
10/19  Break, no class  


10/23  Midterm Exam 2  
10/25  Reinforcement Learning 2: Active RL; exploration vs. exploitation; GLIE; Monte Carlo action learning: exploring starts, generalized policy iteration, soft policies; onpolicy and offpolicy learning; introduction to SARSA and QLearning  
10/26  Reinforcement Learning 3: SARSA and QLearning, algorithms, properties, working examples; how to explore, exploration functions Recitations: Tabular RL 



11/2  Game Theory 2: Mixed strategies; Mixed strategies Nash equilibria: definition, existence, computation; game formalization and analysis using algebra and calculus; Nash equilibria as optima and saddle points of payoff function.  


11/8  Recitation: Game Theory  
11/9  Recitation, Q&A:  

Topic  Files  Due Dates  

HW 2: Informed Search  8/18  
HW 3: Adversarial Search  8/25  
HW 4: Classical planning  9/1  
HW 5: Constraint Satisfaction Problems  9/8  
HW 6: Modeling and solving optimization problems  9/15  
HW 7: Probabilistic modeling, Markov chains  9/29  
HW 8: Bayesian networks  10/6  
HW 9: Hidden Markov Models  10/13  
HW 10: Markov Decision Processes for sequentialdecision making  10/20  
HW 11: Reinforcement learning with tabular methods  10/27  
HW 12: Reinforcement learning with approximation methods  11/3  
HW 13: Game Theory for multiagent adversarial scenarios  11/10  

Homework is due by the posted deadline. Assignments submitted past the deadline will incur the use of late days.
You have 4 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 4 late days have been used you will receive 40% 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/studentandstudentlife/academicintegrity.html
The class includes two midterm exams and one final exam. Midterms are set set for September 14 and October 23, the final is TBD.
During exams students are allowed to consult 1page 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/studentaffairs/officeofhealthandwellness/assistanceforindividualswithdisabilities
Samar Rahmouni  Office hours: Mon, Wed 6:00pm  7:00pm
Name  Hours  Location  

Gianni Di Caro  gdicaro@cmu.edu  Wednesdays 10:301:00pm + Send me an email to set up an appointment  M 1007 
Samar Rahmouni  srahmoun@andrew.cmu.edu  Monday and Wednesday: 6:00pm  7:00pm  ARC 