Applied ASP

Jump to Today

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 amsmith@soe.ucsc.edu 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 (amsmith@soe.ucsc.edu)

Lecture: Tuesdays and Thursdays 11:40am - 1:15pm in Soc Sci 1 149

Office hours:

Mondays 3:30 - 4:30pm in E2-269

Wednesdays noon - 2pm in E2-269

Fridays 3:30 - 4:30pm in E2-269

Resources

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

Grading

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.

Lecture Outline

Course Summary:

Date Details Due