15-381 / 681, Fall 2018

Artificial Intelligence: Representation and Problem Solving

Overview

Key Information

Tuesdays + Thursdays, 1:30pm - 2:50pm, GHC 4401

Tuesdays 3-4 PM by Prof. Fang (in WEH 4126) when she lectures or by Prof. Touretzky (in GHC 9013) when he lectures.

15-381: Homeworks 50%, midterm 25%, final 25%

15-681: Homeworks 37.5%, midterm 18.75%, final 18.75%, final project 25%

Will be available for registered students.

We will use Piazza for questions, so please try to post your questions there.

Students will turn in their homework electronically using Autolab.

This course is about the theory and practice of Artificial Intelligence. We will study modern techniques for computers to represent task-relevant information and make intelligent (i.e., satisficing or optimal) decisions towards the achievement of goals. The search and problem-solving methods are applicable throughout a large range of industrial, civil, medical, financial, robotic, and information systems. We will investigate questions about AI systems such as: how to represent knowledge, how to effectively generate appropriate sequences of actions and how to search among alternatives to find optimal or near-optimal solutions. We will also explore how to deal with uncertainty in the world and how to learn from experience. We will cover the aggregation of conflicting preferences and computational game theory. Throughout the course, we will discuss topics such as AI and Ethics and introduce applications related to AI for Social Good. We expect that by the end of the course students will have a thorough understanding of the algorithmic foundations of AI, how probability and AI are closely interrelated, and how automated agents make decisions. We also expect students to acquire a strong appreciation of the big-picture aspects of developing fully autonomous intelligent agents.

Levels

The 381 version is for undergraduates and the 681 version is for MS students.

Prerequisites

There are no formal pre-requisites for the course, but students should have previous programming experience (programming assignments will be in Python), as well as general CS background. Please see the instructors if you are unsure whether your background is suitable for the course.

Office Hours

Name Email Hours Location
Fei Fang feif@andrew.cmu.edu Tuesdays 3pm-4pm (Tuesdays when she lectures) Wean Hall (WEH) 4126
Dave Touretzky dst@cs.cmu.edu Tuesdays 3pm-4pm (Tuesdays when he lectures) GHC 9013
Richard Gu rgu1@andrew.cmu.edu Wednesdays 5:00pm-7:00pm GHC 5th Floor Teaching Commons
Yuan Gao yaog1@andrew.cmu.edu Tuesdays 9:45am-10:45am, Saturdays 11:00am-12:00pm GHC 5th Floor Teaching Commons
Gaurav Lahiry glahiry@andrew.cmu.edu Mondays 2:00pm-4:00pm GHC 5th Floor Teaching Commons
Thomas Z Li tzl@andrew.cmu.edu Mondays 12:00pm-1:00pm, Mondays 5:00pm-6:00pm GHC 5th Floor Teaching Commons
Jonathan Lingjie Li jlli@andrew.cmu.edu Tuesdays 5:00pm-6:00pm, Fridays 4:00pm-5:00pm GHC 5th Floor Teaching Commons
Tanay Vakharia tvakhari@andrew.cmu.edu Thursdays 4:30pm-6:30pm GHC 5th Floor Teaching Commons

Schedule (subject to change)

Dates Topic Instructor Slides Video Read
8/28 (Tue) Introduction Fang and Touretzky ppt video R&N Chapters 1 and 2
8/30 (Thu) Search (1): Uninformed Search
HW1 Out
Touretzky ppt video R&N Ch. 3.1-3.4
9/4 (Tue) Search (2): Informed Search and Local Search Touretzky ppt video R&N Ch. 3.5-3.7, 4.1-4.2
9/6 (Thu) Satisfiability (1): Constraint Satisfaction Problems Touretzky ppt video R&N Ch. 6
9/11 (Tue) Satisfiability (2): Propositional Logic and Resolution Touretzky ppt video R&N Ch. 7.1-7.5
9/13 (Thu) Satisfiability (3): Solving SAT
HW2 Out
Touretzky ppt video R&N Ch. 7.6-7.8
9/18 (Tue) Optimization (1): Optimization and Convex Optimization Fang ppt video Convex Optimization, Chapters 1, 4, Stephen Boyd and Lieven Vandenberghe (Cambridge University Press)
9/20 (Thu) Optimization (2): Linear Programming
HW2 Due HW3 Out
Fang ppt video Applied Mathematical Programming, Chapters 2, 4, Bradley, Hax, and Magnanti (Addison-Wesley, 1977)
9/25 (Tue) Deterministic / Symbolic Reasoning (1): First Order Logic Touretzky ppt video R&N Ch. 8
9/27 (Thu) Optimization (3): Integer Programming and Applications Fang ppt video Applied Mathematical Programming, Chapters 9, Bradley, Hax, and Magnanti (Addison-Wesley, 1977)
10/2 (Tue) Deterministic / Symbolic Reasoning (2): Logical Inference
HW3 Due
Touretzky ppt video R&N Ch. 9.1-9.4
10/4 (Thu) Deterministic / Symbolic reasoning (3): Theorem Proving
HW4 Out
Touretzky ppt video R&N Ch. 9.5-9.6
10/9 (Tue) Deterministic / Symbolic reasoning (4): Classical Planning

PROJECT PROPOSALS DUE FOR 15-681 STUDENTS BY THE BEGINNING OF CLASS

Touretzky ppt video R&N Ch. 10
10/11 (Thu) MIDTERM Fang & Touretzky
10/16 (Tue) Knowledge Representation (1): Structured Knowledge Representation
HW4 Due
HW5 Out
Touretzky ppt video R&N Ch. 12
10/18 (Thu) Knowledge Representation (2): Knowledge Graph Touretzky ppt video T. Mitchell et al. (2018) Never-Ending Learning
10/23 (Tue) Probabilistic Reasoning (1): Probability Model Fang ppt video R&N Ch. 13; (Optional) Pattern Recognition and Machine Learning, Chapter 8.1, Christopher Bishop (Available and Reserved in CMU Library)
10/25 (Thu) Probabilistic Reasoning (2): Bayesian Networks
HW6 Out
Fang ppt video R&N Ch. 14.1-14.2; Pattern Recognition and Machine Learning, Chapter 8.2, Christopher Bishop (Available and Reserved in CMU Library, pdf for Chapter 8.2 available on Piazza)
10/30 (Tue) Probabilistic Reasoning (3): Sampling Methods Fang ppt video R&N Ch. 14.3
11/1 (Thu) Probabilistic Reasoning (4): Temporal Models
HW5 Due
Fang ppt video R&N Ch. 15.1, 15.2.1,15.2.3, 15.3.1, 15.4.2
11/6 (Tue) Sequential Decision Making (1): Markov Decision Processes and Value Iteration Touretzky ppt video R&N Ch. 16.1-16.3, 17.1-17.2
11/8 (Thu) Sequential Decision Making (2): Policy Iteration
HW6 Due
HW7 Out
Touretzky ppt video R&N Ch. 17.3 - 17.4
11/13 (Tue) Sequential Decision Making (3): Passive Reinforcement Learning Fang R&N Ch. 21.2; (Optional) Reinforcement Learning: An Introduction, Chapter 6, Richard S. Sutton and Andrew G. Barto
11/15 (Thu) Sequential Decision Making (4): Active Reinforcement Learning Fang R&N Ch. 21.3; (Optional) Reinforcement Learning: An Introduction, Chapter 6, Richard S. Sutton and Andrew G. Barto
11/20 (Tue) Multi-agent Systems (1): Adversarial Search
HW7 Due
HW8 Out
Fang R&N Ch. 5
11/22 (Thu) Thanksgiving NO CLASS
11/27 (Tue) Multi-agent Systems (2): Basic Concepts in Game Theory Fang R&N Ch. 17.5
11/29 (Thu) Multi-agent Systems (3): Compute Equilibrium Fang
12/4 (Tue) Multi-agent Systems (4): Social Choice and Mechanism Design Fang R&N Ch. 17.6
12/6 (Thu) AI and Ethics
HW8 Due
Fang and Touretzky
TBD FINAL PROJECT WRITE-UPS DUE
12/10 8:30-11:30 FINAL EXAM Fang and Touretzky
TBD Final project presentations (MS students present their 681 projects; optional for 381 students)
Room: TBD
Fang and Touretzky

Assignments

There will be eight homework assignments, one for each theme or topic. They may involve both written questions and programming assignments. Written questions will involve working through algorithms presented in the class, deriving and proving mathematical results, and critically analyzing material presented in class. Programming assignments will involve writing code in Python to implement various algorithms.

Homework due dates

Topic Files Due Dates
Homework 1 9/11 (Tue)
Homework 2 9/20 (Thu)
Homework 3 zip 10/2 (Tue)
Homework 4 zip 10/16 (Tue)
Homework 5 zip 11/1 (Thu)
Homework 6 zip 11/8 (Thu)
Homework 7 11/20 (Tue)
Homework 8 12/6 (Thu)

Homework 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. All homeworks (programming and theoretical) are always submitted individually. Make sure that you include a README file with your andrew id.

  • Strict honor code with severe punishment for violators. CMU’s academic integrity policy can be found here. You may discuss assignments with other students as you work through them, but writeups must be done alone. No downloading / copying of code or other answers is allowed. If you use a string of at least 5 words from some source, you must cite the source

15-681 Project

  • Students enrolled in 15-681 will also complete a course project. Late days may not be used on the course project. The projects are to be approved by the professors. They can be done individually or by a pair of students. Projects done by a pair of students should be roughly double in scope.

  • Project proposals are due in hardcopy on 10/9/2018 at the beginning of class. The proposal should be as concrete as possible so it can be evaluated for topical fit, feasibility, and scope. Of the 25% of the grade that comes from the project, 2% will be from the proposal and 23% of the actual project.

  • We encourage creativity in the projects. Projects could include using one of the algorithms from class on a new application, making a new algorithm, or both. Projects can also inlcude developing a system that uses AI techniques. Typically projects involve programming, but they can also be proving theorems.

  • Each project must be presented orally and as a paper.

Exams

The class includes both a midterm and final exam. The material for the midterm includes all lectures before and on 10/9/2018.

Other

Accommodations for Students with Disabilities:
If you have a disability and have an accommodations letter from the Disability Resources office, we encourage you to discuss your accommodations and needs with us as early in the semester as possible. We will work with you to ensure that accommodations are provided as appropriate. If you suspect that you may have a disability and would benefit from accommodations but are not yet registered with the Office of Disability Resources, we encourage you to contact them at access@andrew.cmu.edu.


Statement of Support for Students’ Health & Well-being
Take care of yourself.  Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.
All of us benefit from support during times of struggle. There are many helpful resources available on campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is almost always helpful.
If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit their website at http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.
If you have questions about this or your coursework, please let us know. Thank you, and have a great semester.