15-281, Fall 2019

Artificial Intelligence: Representation and Problem Solving

Overview

Key Information

Tuesday + Thursday, 1:30 pm - 2:50 pm, GHC 4401

Friday afternoon, see Recitations

Angela Yang, Claire Wang, George Brown, Michelle Ma, Sean Pereira, Tian Owarang, Tina Wu, Vicky Zeng, see the 281 Staff page

Grades will be collected in Canvas.
Midterms 15% (each), Final 30%, Programming homework 20%, Written homework 10%, Online homework 5%, Participation 5%

We will use Piazza for questions and any course announcements.

Students will turn in their homework electronically using Gradescope.

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

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.

Prerequisites + Corequisites

The 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 Fall 2019.

Please see the instructors if you are unsure whether your background is suitable for the course.

Office Hours

This course uses the CMU OHQueue tool as a queueing system for office hours.

Schedule (subject to change)

Dates Topic Reading / Demo Slides
8/27 Tue Introduction AIMA Ch. 1 pptx (inked) pdf (inked)
8/29 Thu Agents and Search AIMA Ch. 3.1-4 pptx (inked) pdf (inked)
9/3 Tue Informed Search AIMA Ch. 3.5-6 pptx (inked) pdf (inked)
9/5 Thu Adversarial Search AIMA Ch. 5.2-5 pptx (inked) pdf (inked)
9/10 Tue Contraint Satisfaction Problems AIMA Ch. 6.1-3, 6.5
CSP Demo
pptx (inked) pdf (inked)
9/12 Thu Local Search AIMA Ch. 4.1, 6.4
CSP Demo
pptx (inked) pdf (inked)
9/17 Tue Propositional Logic AIMA Ch. 7.1-5 pptx (inked) pdf (inked)
9/19 Thu SAT AIMA Ch. 7.6-7 pptx (inked) pdf (inked)
9/24 Tue Classical Planning AIMA Ch. 10 pptx (inked) pdf (inked)
9/26 Thu First Order Logic AIMA Ch. 8.1-3, 9.1-3.2 pptx (inked) pdf (inked)
10/1 Tue MIDTERM 1 EXAM
10/3 Thu Optimization & Linear Programming Boyd and Vandenberghe Ch. 2.2.1, 2.2.4, 4.3-4.3.1 pptx (inked) pdf (inked)
10/8 Tue Integer Programming pptx (inked) pdf (inked)
10/10 Thu Knowledge Representation AIMA Ch. 12; Never-Ending Learning pptx (inked) pdf (inked)
10/15 Tue Markov Decision Process I AIMA Ch. 17.1-3 pptx (inked) pdf (inked)
10/17 Thu Markov Decision Process II pptx (inked) pdf (inked)
10/22 Tue Reinforcement Learning I AIMA Ch. 21.1-3 pptx (inked) pdf (inked)
10/24 Thu Reinforcement Learning II AIMA Ch. 21.4-5 pptx (inked) pdf (inked)
10/29 Tue Bayes Nets: Representation AIMA Ch. 13.1-5, 14.1-2
Bayes Net Demo (highres)
pptx (inked) pdf (inked)
10/31 Thu Bayes Nets: Independence AIMA Ch. 13.4-5, 14.2, Jordan 2.1 pptx (inked) pdf (inked)
11/5 Tue Bayes Nets: Inference AIMA Ch. 14.4 pptx (inked) pdf (inked)
11/7 Thu Bayes Nets: Sampling AIMA Ch. 14.5
Likelihood Demo, Gibbs Demo
pptx (inked) pdf (inked)
11/12 Tue MIDTERM 2 EXAM
11/14 Thu Hidden Markov Models AIMA Ch. 15.2, 15.5 pptx (inked) pdf (inked)
11/19 Tue Particle Filter & HMM Applications AIMA Ch. 15.2, 15.6 pptx (inked) pdf (inked)
11/21 Thu Game Theory: Equilibrium AIMA Ch. 17.5 pptx (inked) pdf (inked)
11/26 Tue Game Theory: Social Choice AIMA Ch. 17.6 pptx (inked) pdf (inked)
11/28 Thu No class: Thanksgiving
12/3 Tue Multi-agent Reinforcement Learning Shoham & Leyton-Brown, Ch. 7.2, Ch. 7.4 pptx (inked) pdf (inked)
12/5 Thu Human Compatible AI pptx (inked) pdf (inked)
12/12 Thu FINAL EXAM 1-4 pm, GHC 4401

Recitations

Recitations start the first week of class, Friday, Aug. 30. Recitation attendence is recommended to help solidfy weekly course topics. 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, Sept. 20.

Time Location Section TAs Other
Fri, 12:30 - 1:20 pm SH 220 A + B Claire, Sean, and Tina
Fri, 1:30 - 2:20 pm WEH 5421 C Angela and George
Fri, 1:30 - 2:20 pm SH 222 D Tina
Fri, 2:30 - 3:20 pm PH A22 E Angela and Vicky
Fri, 3:30 - 4:20 pm GHC 4211 G Michelle and Vicky
Dates Recitation Handout Code
8/30 Fri Recitation 1 pdf (solutions) candygrab.zip
9/6 Fri Recitation 2 pdf (solutions)
9/13 Fri Recitation 3 pdf (solutions)
9/20 Fri Recitation 4 pdf (solutions)
9/27 Fri Recitation 5 pdf (solutions)
10/4 Fri Recitation 6 pdf (solutions) hanoi.py
10/11 Fri Recitation 7 pdf (solutions)
10/18 Fri No recitation pdf (solutions)
10/25 Fri No recitation pdf (solutions)
11/1 Fri Recitation 8 pdf (solutions)
11/8 Fri Recitation 9 pdf (solutions)
11/15 Fri Recitation 10 pdf (solutions)
11/22 Fri Recitation 11 pdf (solutions)
11/29 Fri No recitation
12/6 Fri Recitation 12 pdf (solutions)

Exams

The course includes two midterm exams and a final exam. The midterms will be in class on Oct. 1 and Nov. 12. The final exam is on Dec. 12. Plan any travel around exams, as exams cannot be rescheduled.

Assignments

There will be five 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 due dates

Assignment Link (if released) Due Date
HW1 (online) Gradescope 9/3 Tue, 10 pm
P0 P0: Tutorial (required, worth zero points) 9/5 Thu, 10 pm
HW2 (written) hw2_blank.pdf, hw2.zip (tex src) 9/10 Tue, 10 pm
P1 P1: Search and Games 9/12 Thu, 10 pm
HW3 (online) Gradescope 9/17 Tue, 10 pm
HW4 (written) hw4_blank.pdf, hw4.zip (tex src) 9/24 Tue, 10 pm
P2 P2: Planning 10/5 Sat, 10 pm
HW5 (written) hw5_blank.pdf, hw5.zip (tex src) 10/8 Tue, 10 pm
HW6 (online) Gradescope 10/15 Tue, 10 pm
P3 P3: Optimization 10/17 Thu, 10 pm
HW7 (online) Gradescope 10/22 Tue, 10 pm
HW8 (written) hw8_blank.pdf, hw8.zip (tex src) 10/29 Tue, 10 pm
P4 P4: Reinforcement Learning 10/31 Thu, 10 pm
HW9 (online) Gradescope 11/5 Tue, 10 pm
HW10 (written) hw10_blank.pdf, hw10.zip (tex src) 11/20 Wed, 10 pm
P5 P5: Ghostbusters 11/25 Mon, 10 pm
HW11 (online) Gradescope 12/2 Mon, 10 pm
HW12 (written) hw12_blank.pdf, hw12.zip (tex src) 12/6 Fri, 10 pm

Policies

Grading

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:

  • 15% Midterm exams (each)
  • 30% Final exam
  • 20% Programming homework
  • 10% Written homework
  • 5% Online homework
  • 5% Participation

Participation Grades

Participation will be based on the percentage of in-class polling questions answered:

  • 5% for 80% or greater poll participation
  • 3% for 70%
  • 1% for 60%

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.

Final Grade

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:

  • A: above 90%
  • B: 80-90%
  • C: 70-80%
  • D: 60-70%

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.

Late Policy

Projects:

  • 5 slip days
  • Use up to two per programming assignment
  • You may use these at your discretion, but they are intended for minor illness and other disruptive events outside of your control, and not for poor time management
  • You are responsible to keep track of your own slip days. Gradescope will not enforce the total number of slip days

Written homework:

  • No slip days
  • May turn in up to 24 hours late with 50% penalty

Online homework:

  • No slip days
  • May turn in up to 24 hours late with 50% penalty

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:

  • I have so many deadlines this week: you know your deadlines ahead of time — plan accordingly.
  • It's a minute before the deadline and the network is down: you always have multiple submissions -- it's no a good idea to wait for the deadline for your first submission.
  • My computer crashed and I lost everything: Use Dropbox or similar to do real-time backup -- recover your files onto AFS and finish your homework from a cluster machine.
  • My fraternity/sorority/club has that big event that is taking all my time: Schedule your extra-curricular activities around your classes, not vice versa.

Collaboration Policy

We encourage you to discuss course content and assignments with your classmates. However, these discussion must be kept at a conceptual level only.

  • You may NOT view, share, or communicate about any artifact that will be submitted as part of an assignment. Example artifacts include, but are not limited to: code, pseudocode, diagrams, and text.
  • You may look at another student's Python error messages and discuss what the error means at a conceptual level. However, you may NOT give specific instructions to fix the error.
  • All work that you present must be your own.
  • Using any external sources of code or algorithms in any way must have approval from the instructor before submitting the work. For example, you must get instructor approval before using an algorithm you found online for implementing a heuristic function in a programming assignment.

Programming Assignment Partners

The only exception to the above collaboration policy is when you share programming code directly with your programming assignment partner.

  • You are allowed to work in groups of at most two on each programming assignment, i.e. you and one partner
  • You must specify your parnter when you submit each assignment
  • Once you start working with a partner on an assignment, you may not switch to another partner for that assignment
  • You may change partners between assignments. In fact, you are strongly encouraged to change partners occasionally
  • Important: You are responsible for making sure that both you AND your partner understand the work that you submit. If we discover that one partner cannot answer basic questions about the submitted work, both students in the group will be reported for an academic integrity violation.

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.

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 visit their website.

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, 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.