Artificial Intelligence: Representation and Problem Solving
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.
This 15-281 course is for undergraduates. There is no masters level version offered this semester (15-681).
15-281 used to be 15-381 in previous semesters. This is not a significant change to the course, but rather a recognition that many students are able to complete the necessary prerequisites and are prepared to take this course in their second year.
The prequisites for this course are:
The corequisite for this course is:
For this corequisite, you should either have completed it prior to starting 15-281 or have it on your schedule for Spring 2023.
Please see the instructors if you are unsure whether your background is suitable for the course.
This course uses the CMU OHQueue tool as a queueing system for office hours.The calendar of in-person and online office hours is below.
|Dates||Topic||Reading / Demo||Slides||Activity|
|1/17 Tue||Introduction/Agents||AIMA Ch. 1||blank pptx/pdf inked pptx/pdf||blank/sol|
|1/19 Thu||Search||AIMA Ch. 3.1-4||blank pptx/pdf inked pptx/pdf||blank/sol|
|1/24 Tue||Informed Search||AIMA Ch. 3.5-6||blank pptx/pdf inked pptx/pdf||blank/sol|
|1/26 Thu||Adversarial Search||AIMA Ch. 5.2-5||blank pptx/pdf inked pptx/pdf||blank/sol|
|1/31 Tue||Contraint Satisfaction Problems|| AIMA Ch. 6.1-3, 6.5
|blank pptx/pdf inked pptx/pdf||CSP activity sheet|
|2/2 Thu||Local Search||AIMA Ch. 4.1, 6.4||blank pptx/pdf inked pptx/pdf||blank/sol|
|2/7 Tue||Optimization & Linear Programming|| Boyd and Vandenberghe
Ch. 2.2.1, 2.2.4, 4.3-4.3.1
|2/9 Thu||Integer Programming||
|2/14 Tue||Ethics 1||blank/sol|
|2/16 Thu||MIDTERM 1 EXAM||In class|
|2/21 Tue||Propositional Logic and Logical Agents||AIMA Ch. 7.1-7|| blank pptx/pdf
|2/23 Thu||Classical Planning||AIMA Ch. 10||
|2/28 Tue||Markov Decision Process I||AIMA Ch. 17.1-3||
|3/2 Thu||Markov Decision Process II||
|3/7 Tue||No class: Spring Break|
|3/9 Thu||No class: Spring Break|
|3/14 Tue||Reinforcement Learning I||AIMA Ch. 21.1-3||
|3/16 Thu||Reinforcement Learning II||AIMA Ch. 21.4-5||
|3/21 Tue||Bayes Nets: Representation|| AIMA Ch. 13.1-5, 14.1-2
Bayes Net Demo (highres)
|3/23 Thu||Bayes Nets: Independence||AIMA Ch. 13.4-5, 14.2, Jordan 2.1||
Bayes Ball handout
|3/28 Tue||Ethics 2|
|3/30 Thu||MIDTERM 2 EXAM||In class|
|4/4 Tue||Bayes Nets: Inference||AIMA Ch. 14.4|
|4/6 Thu||Bayes Nets: Sampling|| AIMA Ch. 14.5
Likelihood Demo, Gibbs Demo
|4/11 Tue||Hidden Markov Models||AIMA Ch. 15.2, 15.5|
|4/13 Thu||No class: Carnival|
|4/18 Tue||Particle Filter & HMM Applications||AIMA Ch. 15.2, 15.6|
|4/20 Thu||Game Theory: Equilibrium||AIMA Ch. 17.5|
|4/25 Tue||Game Theory: Social Choice||AIMA Ch. 17.6|
Recitations start the first week of class, Friday, Jan. 20. Recitation attendence is recommended to help solidfy weekly course topics. Students frequently say that the recitations are one of the most important aspects of the course. Attendance is taken and counts towards your course participation grade. That being said, the recitation materials published below are required content and are in-scope for midterm and final exams.
Recitation section assignments will be locked-down after the third week. Until then, you may try attending different recitation sections to find the best fit for you. In the case of any over-crowded recitation sections, priority goes to students that are officially registered for that section in S3. The process to select your final recitation assignment will be announced on Piazza as we get closer to Recitation 4.
|Fri, 12:00 - 12:50 pm||WEH 2302||A||TAs: Alex and Simrit||Slides|
|Fri, 1:00 - 1:50 pm||PH 125B||B||TAs: Lily and Simrit||Slides|
|Fri, 1:00 - 1:50 pm||PH A22||C||TAs: Ihita and Josep||Slides|
|Fri, 2:00 - 2:50 pm||PH A22||D||TAs: Ihita and Olivia||Slides|
|Fri, 2:00 - 2:50 pm||WEH 4709||E||TAs: Mansi and Raashi||Slides|
|1/20 Fri||Recitation 1: Search||pdf (solutions)||nim.zip|
|1/27 Fri||Recitation 2: Informed and Adversarial Search||pdf (solutions)|
|2/3 Fri||Recitation 3: CSPs and Local Search||pdf (solutions)|
|2/10 Fri||Recitation 4: LP and IP||pdf (solutions)|
|2/17 Fri||Recitation 5||pdf (solutions)|
|2/24 Fri||Recitation 6: Logic and Classical Planning||pdf (solutions)|
|3/3 Fri||Recitation 7: MDPs||pdf (solutions)|
|3/10 Fri||No recitation: Spring Break|
|3/17 Fri||Recitation 8: RL||pdf(solutions)|
|3/24 Fri||Recitation 9: Bayes Nets||pdf (solutions)|
|3/31 Fri||Recitation 10||
|4/7 Fri||Recitation 11: Bayes Nets 2|
|4/21 Fri||Recitation 13: PF and Game Theory|
|4/28 Fri||Recitation 14: Social Choice and Review|
The course includes two midterm exams and a final exam. The midterms will be in class on Feb. 16 and Mar 30. The final exam date is to-be-determined. Plan any travel around exams, as exams cannot be rescheduled.
Midterm 1 Learning Objectives and Practice Exams
There will be five programming assignments and ten written/online assignments (subject to change). Written/online assignments 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.
For any assignments that aren't released yet, the dates below are tentative and subject to change.
For helpful information about getting started with our written and programming assignments, visit our FAQ page.
|Assignment||Link (if released)||Due Date|
|P0||P0: Tutorial (required, worth zero points)||1/20 Fri, 10 pm|
|HW1 (online)||Gradescope||1/24 Tue, 10 pm|
|HW2 (written)||hw2_blank.pdf, hw2.zip (tex src)||1/31 Tue, 10 pm|
|P1||P1: Search and Games||2/6 Monday, 10 pm|
|HW3 (online)||Gradescope||2/7 Tue, 10 pm|
|HW4 (online)||Gradescope||2/14 Tue, 10 pm|
|P2||P2: Optimization||2/23 Thu, 10 pm|
|HW5 (written)||hw5_blank.pdf, hw5.zip (tex src)||2/28 Tue, 10 pm|
|P3 Checkpoint (12 points)||P3: Logic/Classical Planning||3/3 Fri, 10 pm|
|HW6 (online)||Gradescope||3/14 Tue, 10 pm|
|P3 Final (25 points)||P3: Logic/Classical Planning||3/17 Fri, 10 pm|
|HW7 (written)||hw7_blank.pdf, hw7.zip (tex src)||3/21 Tue, 10 pm|
|HW8 (online)||Gradescope||3/28 Tue, 10 pm|
|P4||P4: Reinforcement Learning||4/6 Thu, 10 pm|
|HW9 (written)||4/11 Tue, 10 pm|
|HW10 (written)||4/25 Tue, 10 pm|
|P5||4/27 Thu, 10 pm|
Below are course notes developed by the course staff over the years.
|Topic||Link (if released)|
|Local Search||Local Search Notes|
|Linear and Integer Programming||LP/IP Notes|
|Propositional Logic and SAT||Prop Logic and SAT Notes|
|Classical Planning||Classical Planning Notes|
|Markov Decision Process||MDP Notes|
|Reinforcement Learning||RL Notes|
|Bayes Nets||Bayes Nets Notes|
|HMMs and Particle Filters|
|1||Lecture: Intro/Agents||Lecture: Search|| Recitation 1
|2|| Lecture: Informed Search
|Lecture: Adversarial Search||Recitation 2|
|3|| Lecture: CSPs
|Lecture: Local Search||Recitation 3|
|4||P1 due|| Lecture: Optimization
|Lecture: Linear/Integer Programming||Recitation 4|
|5|| Lecture: Ethics I
|EXAM 1||Recitation 5|
|6||Lecture: Logic|| Lecture: Classical Planning
|7|| Lecture: MDPs I
|Lecture: MDPs II|| Recitation 7
P3 1-6 due
|8|| Lecture: RL I
|Lecture: RL II|| Recitation 8
P3 1-10 due
|9|| Lecture: Bayes Representation
|Lecture: Bayes Independence||Recitation 9|
|10|| Lecture: Ethics II
|EXAM 2||Recitation 10|
|11||Lecture: Bayes Inference|| Lecture: Bayes Sampling
|12|| Lecture: HMMs
|NO CLASS: CARNIVAL||NO RECITATION|
|13||Lecture: Particle Filters||Lecture: Game Theory I||Recitation 13|
|14|| Lecture: Game Theory II
| Lecture: AMA
Grades will be collected and reported in Canvas. Please let us know if you believe there to be an error the grade reported in Canvas.
Final scores will be composed of:
Participation will be based on the percentage of in-class polling questions answered:
Correctness of in-class polling responses will not be taken into account for participation grades. Illness, homeworks, and travel are built into this policy. However, if you need to miss more than one lecture, please reach out to the professor to make up missed work.
It is against the course academic integrity policy to answer in-class polls when you are not present in lecture. Violations of this policy will be reported as an academic integrity violation. Information about academic integrity at CMU may be found at https://www.cmu.edu/academic-integrity.
This class is not curved. However, we convert final course scores to letter grades based on grade boundaries that are determined at the end of the semester. What follows is a rough guide to how course grades will be established, not a precise formula — we will fine-tune cutoffs and other details as we see fit after the end of the course. This is meant to help you set expectations and take action if your trajectory in the class does not take you to the grade you are hoping for. So, here's a rough, very rough heuristics about the correlation between final grades and total scores:
This heuristic assumes that the makeup of a student’s grade is not wildly anomalous: exceptionally low overall scores on exams, programming assignments, or written assignments will be treated on a case-by-case basis.
Precise grade cutoffs will not be discussed at any point during or after the semester. For students very close to grade boundaries, instructors may, at their discretion, consider participation in lecture and recitation, exam performance, and overall grade trends when assigning the final grade.
Programming assignments, written homework, and online homework:
Aside from this, there will be no extensions on assignments in general. If you think you
really really need an extension on a particular assignment, contact the instructor as soon as
and before the deadline. Please be aware that extensions are entirely discretionary and will be granted only
in exceptional circumstances outside of your control (e.g., due to severe illness or major personal/family
emergencies, but not for competitions, club-related events or interviews). The instructors will require
confirmation from University Health Services or your academic advisor, as appropriate.
Nearly all situations that make you run late on an assignment homework can be avoided with proper planning — often just starting early. Here are some examples:
Again, you should be keeping track of how many slip days you have used, and ensure that you are both using no more than the allowed slip days per assignment and using no more than 6 slip days in the semester. If you submit an assignment late but do not have enough slip days to use for either reason, one of two things will happen:
You are encouraged to submit a version of your assignment early. It is not a good idea to wait for the deadline for your first submission.
We encourage you to discuss course content and assignments with your classmates. However, these discussion must be kept at a conceptual level only.
The only exception to the above collaboration policy is when you share programming code directly with your programming assignment partner.
Violations of these policies will be reported as an academic integrity violation. Information about academic integrity at CMU may be found at https://www.cmu.edu/academic-integrity. Please contact the instructor if you ever have any questions regarding academic integrity or these collaboration policies.
We will be using Zoom for lectures, recitations, and exams. If you cannot attend on Zoom for any reason, the recorded lectures will be available within a few hours of classes. If your Internet does not support Zoom consistently for exams or you have other concerns, please let the professors know at least 1 week before an exam and we can try to make an accommodation. The course will also make use of Canvas, Diderot, and Gradescope. If you have trouble accessing these technologies, please let us know ASAP. If you have general concerns about this policy and your ability to access class materials, please let us know ASAP.
If you cannot attend lecture live, must let the professor know ASAP and before class to plan accommodations. As always, the professors are happy to answer questions about lectures via posts on the lecture slides on Diderot or office hours or via email.
Recitations will take place in person or online depending on feasibility. At least one online recitation will be recorded so that remote students who cannot attend any recitation sections can view it. We will re-examine recitation sections and office hours in the weeks we are online.
In this course, being able to see one another helps to facilitate a better learning environment and promote more engaging discussions. Therefore, our default will be to expect students to have their cameras on during lectures and discussions and particularly during proctored exams. However, we also completely understand there may be reasons students would not want to have their cameras on. If you have any concerns about sharing your video during exams, please email us as soon as possible and we can discuss possible adjustments. Note: You may use a background image in your video if you wish; just check in advance that this works with your device(s) and internet bandwidth.
You are responsible for adhering to all CMU policies. If you do not comply, please remember that you will be subject to student conduct proceedings, up to and including removal from CMU. Accordingly, we will be obliged to take other measures for the safety of the whole class.
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 visit their website.
Take care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well,
getting enough sleep, and taking some time to relax. This will help you achieve your goals and cope with
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.
We must treat every individual with respect. We are diverse in many ways, and this diversity is fundamental to building and maintaining an equitable and inclusive campus community. Diversity can refer to multiple ways that we identify ourselves, including but not limited to race, color, national origin, language, sex, disability, age, sexual orientation, gender identity, religion, creed, ancestry, belief, veteran status, or genetic information. Each of these diverse identities, along with many others not mentioned here, shape the perspectives our students, faculty, and staff bring to our campus. We, at CMU, will work to promote diversity, equity and inclusion not only because diversity fuels excellence and innovation, but because we want to pursue justice. We acknowledge our imperfections while we also fully commit to the work, inside and outside of our classrooms, of building and sustaining a campus community that increasingly embraces these core values.
Each of us is responsible for creating a safer, more inclusive environment.
Unfortunately, incidents of bias or discrimination do occur, whether intentional or unintentional. They contribute to creating an unwelcoming environment for individuals and groups at the university. Therefore, the university encourages anyone who experiences or observes unfair or hostile treatment on the basis of identity to speak out for justice and support, within the moment of the incident or after the incident has passed. Anyone can share these experiences using the following resources:
All reports will be documented and deliberated to determine if there should be any following actions. Regardless of incident type, the university will use all shared experiences to transform our campus climate to be more equitable and just.