Combinatorial search and optimization problems are pervasive in applied computing, but we often don't have the time, interest, or background required to apply the latest algorithms from the literature. Meanwhile, in most applied settings, we work with problems of a fixed scale that exhibit domain-specific structure, allowing us to bypass many concerns about general tractability.
Answer Set Programming (ASP) is a declarative logic programming paradigm oriented towards compactly modeling and efficiently solving these problems. The language of ASP looks like Prolog, and it runs like a SAT solver. Rather that digging deeply into how answer set solvers are implemented, this course focuses on modeling, solving, and deploying ASP-based solutions using an existing open-source solver. Several motivating applications are taken from the domain of game design automation where ASP has been used to implement gameplay analysis/verification systems and high-assurance content generators.
In this lecture-style course, students will respond to readings from the recent literature on ASP and game design automation, complete programming assignments using AnsProlog and Python (to be submitted as Jupyter Notebook documents), and develop a creative research project applying ASP to a new problem related to the students’ own research interests.
Prior exposure to logic programming or CSP/SAT/SMT solvers not required. Fluency with computational complexity theory will bring additional insights but is also not required.
CS grads: You may use this class (Spring 2017) to count towards the AI/ML breadth requirement category. Even though I expect the entire class to come from CS, you'll still need a permission code to add this CM course. Email email@example.com to request one.
Note to future instructors: Borrow what materials you like from this course. Solutions to programming assignments are available upon request. (Independent folk who are interested in seeing the solutions outside of any organized course, you're welcome to ask too.)
Instructor: Adam M. Smith (firstname.lastname@example.org)
Lecture: Tuesdays and Thursdays 11:40am - 1:15pm in Soc Sci 1 149
Mondays 3:30 - 4:30pm in E2-269
Wednesdays noon - 2pm in E2-269
Fridays 3:30 - 4:30pm in E2-269
Optional textbook: Answer Set Solving in Practice by Martin Gebser, Roland Kaminski, Benjamin Kaufmann, and Torsten Schaub
Textbook companion website: https://potassco.org/teaching/
Supporting documentation: Potassco Guide
30% readings (~18 1-page responses) [Reading Response Document Format].
25% programs (~4 1-week assignments)
45% creative project (4.5 weeks, 6-page paper and presentation)
Until finals week, late work is subject to a penalty of 10% per week applied to the maximum points available, not as a multiplier on the score. Additionally, there will be no late penalty for resubmissions of work that earned at least 20% of the available points by the original date. No late work will be accepted during finals week without prior arrangement.
- (04/04/2017) L01: Course Intro
- (04/06/2017) L02: ASP in Context
- (04/11/2017) L03: Basic Modeling and Solving
- (04/13/2017) L04: Applications Teaser
- (04/18/2017) L05: Modeling Optimization Problems
- (04/20/2017) L06: Temporal Modeling
- (04/25/2017) L07: Grounding / Integer Programming
- (04/27/2017) L08: Software Engineering for ASP
- (05/02/2017) L09: Projected Enumeration / Brave or Cautious Reasoning
- (05/04/2017) L10: Beyond NP Formulations
- (05/09/2017) L11: Grokking Disjunction
- (05/11/2017) L12: Predicting Grounding and Solving Times / Deploying ASP Systems
- (05/16/2017) L13: Creative Project Setup
- (05/18/2017) L14: Deep Dive: Design Automation for Infinite Refraction
- (05/23/2017) L15: Domain-specific Heuristics / Domain-specific Theory Propagation
- (05/25/2017) L16: Creative Project Components
- (05/30/2017) L17: Cancelled
- (06/01/2017) L18: Formulation reviews / Meta-interpretive Programming
- (06/06/2017) L19: Progress Presentations / Sampling, Counting and Integration Problems
- (06/08/2017) L20: Future of ASP / Course Recap
- (06/15/2017 8am!) Finals: Project presentations
The syllabus page shows a table-oriented view of the course schedule, and the basics of course grading. You can add any other comments, notes, or thoughts you have about the course structure, course policies or anything else.
To add some comments, click the "Edit" link at the top.