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-381 course is for undergraduates. There is no masters level version offered this semester (15-681).
The prequisite for this course is 15-122, which implies that:
The corequisites for this course are 21-122 Integration and Approximation (or higher level calculus) and 21-241 Matrices and Linear Transformations (or 21-242). For each corequisite, you should either have completed it prior to starting 15-381 or have it on your schedule for Spring 2019.
Please see the instructors if you are unsure whether your background is suitable for the course.
|1/14 Mon||Introduction||AIMA Ch. 1||pptx (inked) pdf (inked)|
|1/16 Wed||Agents and Search||AIMA Ch. 3.1-4||pptx (inked) pdf (inked)|
|1/21 Mon||No class. Martin Luther King Jr. Day|
|1/23 Wed||Informed Search||AIMA Ch. 3.5-6||pptx (inked) pdf (inked)|
|1/28 Mon||Adversarial Search||AIMA Ch. 5.2-5||pptx pdf|
|1/30 Wed||No class. Polar Vortex|
|2/4 Mon||Contraint Satisfaction Problems||AIMA 6.1-3, 6.5||pptx pdf|
|2/6 Wed||Linear Programming||Boyd and Vandenberghe 2.2.1, 2.2.4, 4.3-4.3.1||pptx (inked) pdf (inked)|
|2/11 Mon||Integer Programming||pptx (inked) pdf (inked)|
|2/13 Wed||Propositional Logic||AIMA Ch. 7.1-5, 7.6.1||pptx (inked) pdf (inked)|
|2/18 Mon||MIDTERM 1 EXAM|
|2/20 Wed||Logical Agents||AIMA Ch. 7.7||pptx (inked) pdf (inked)|
|2/25 Mon||First Order Logic||AIMA Ch. 8.1-3, 9.1-3.2||pptx (inked) pdf (inked)|
|2/27 Wed||Classical Planning||AIMA Ch. 10||pptx pdf|
|3/4 Mon||Knowledge Representation||AIMA Ch. 12; Never-Ending Learning||pptx (inked) pdf (inked)|
|3/6 Wed||Markov Decision Process I||AIMA 17.1-3||pptx (inked) pdf (inked)|
|3/11 Mon||No class. Spring Break|
|3/13 Wed||No class. Spring Break|
|3/18 Mon||Markov Decision Process II||pptx (inked) pdf (inked)|
|3/20 Wed||Reinforcement Learning I||AIMA Ch. 21.1-3||pptx pdf|
|3/25 Mon||Reinforcement Learning II||AIMA Ch. 21.4-5||pptx (inked) pdf (inked)|
|3/27 Wed||Probability||AIMA Ch. 13-1.5||pptx (inked) pdf (inked)|
|4/1 Mon||Bayes' Nets: Representation||AIMA Ch. 14.1-2, 14.4||pptx (inked) pdf (inked)|
|4/3 Wed||Bayes' Nets: Independence||AIMA Ch. 14.1-2, 14.4||pptx (inked) pdf (inked)|
|4/8 Mon||MIDTERM 2 EXAM|
|4/10 Wed||Bayes' Nets: Inference||AIMA Ch. 14.3||pptx (inked) pdf (inked)|
|4/15 Mon||Bayes' Nets: Sampling||AIMA Ch. 14.4-5||pptx (inked) pdf (inked)|
|4/17 Wed||Hidden Markov Models||AIMA Ch. 15.2, 15.5||pptx (inked) pdf (inked)|
|4/22 Mon||Particle Filter & HMM Applications||AIMA Ch. 15.2, 15.6||pptx (inked) pdf (inked)|
|4/24 Wed||Game Theory: Equilibrium||AIMA Ch. 17.5||pptx (inked) (pdf inked)|
|4/29 Mon||Game Theory: Social Choice||AIMA Ch. 17.6||pptx (inked) pdf (inked)|
|5/1 Wed||Human Compatible AI||pptx (inked) pdf (inked)|
|5/9 Thur||FINAL EXAM 1-4 pm|
|1/18 Fri||Recitation 1||pdf (solutions)||candygrab.zip|
|1/25 Fri||Recitation 2||pdf (solutions)|
|2/1 Fri||Recitation 3||pdf (solutions)|
|2/8 Fri||Recitation 4||pdf (solutions)|
|2/15 Fri||Recitation 5||pdf (solutions)|
|2/22 Fri||Recitation 6||pdf (solutions)|
|3/1 Fri||Recitation 7||pdf (solutions)||hanoi_sol.py|
|3/22 Fri||Recitation 8||pdf (solutions)|
|3/29 Fri||Recitation 9||pdf (solutions)|
|4/5 Fri||Recitation 10||pdf (solutions)|
|4/19 Fri||Recitation 11||pdf (solutions)|
|4/26 Fri||Recitation 12||pdf (solutions)|
|5/3 Fri||Recitation 13||pdf (solutions)|
The course includes two midterm exams and a final exam. The midterms will be in class on Feb. 18 and April 8. The final exam is on May 9, 1-4 pm. Plan any travel around exams, as exams cannot be rescheduled.
There will be six programming assignments and twelve 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.
|Assignment||Link (if released)||Due Date|
|HW1 (online)||Gradescope||1/22 Tue, 10 pm|
|P0||P0: Tutorial (required, worth zero points)||1/24 Thur, 10 pm|
|HW2 (written)||hw2_blank.pdf, hw2.zip (tex src)||1/28 Mon, 10 pm|
|HW3 (online)||Gradescope||2/6 Wed, 10 pm|
|P1||P1: Search and Games||2/7 Thur, 10 pm|
|HW4 (written)||hw4_blank.pdf, hw4.zip (tex src)||2/12 Tue, 10 pm|
|P2||P2: Optimization||2/21 Thur, 10 pm|
|HW5 (online)||Gradescope||2/26 Tue, 10 pm|
|HW6 (written)||hw6_blank.pdf, hw6.zip (tex src)||3/5 Tue, 10 pm|
|P3||P3: Planning||3/7 Thur, 10 pm|
|HW7 (online)||Gradescope||3/20 Wed, 10 pm|
|HW8 (online)||Gradescope||3/26 Tue, 10 pm|
|P4||P4: Reinforcement Learning||3/28 Thur, 10 pm|
|HW9 (written)||hw9_blank.pdf, hw9.zip (tex src)||4/2 Tue, 10 pm|
|HW10 (online)||Gradescope||4/17 Wed, 10 pm|
|HW11 (written)||hw11_blank.pdf, hw11.zip (tex src)||4/25 Thur, 10 pm|
|HW12 (online)||Gradescope||4/30 Tue, 10 pm|
|P5||P5: Ghostbusters||5/2 Thur, 10 pm|
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.
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.
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 possible 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:
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.
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, exercising, 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.