Logic-Based Action Model Induction

Scope: 2-3 students

Objective

There is a growing landscape of logic-based approaches to induce action theories for state traces. What is possible, and the techniques available, correspond to a growing web of inteconnected approaches. This project aims to document and reify this web.

Required Expertise

There are two key expertise required for this position:

  1. Knowledge of automated planning and representations of actions (e.g., preconditions + effects)
  2. Knowledge of propositional logic and SAT encodings

The former can be found in CISC 352 and the latter in CISC 204. In exceptional circumstances, students may be eligible with only one of the two elements.

Description

Models for planning are made up of fluents (what might be true or false in the environment) and actions (what can cause a change in the fluents). Above, there are fluents describing the location of the knight, where they’ve visited, etc. and there is a single action that moves the knight around the board.

Traditionally, models are specified manually and the actions hand-designed. However, a core area of research is how these action models may be induced from data alone. The form of the data is a sequence of states, possibly with action labels included. Key considerations into the framing of the problem lead to different approaches:

  • Is every state in a state sequence seen?
  • Is every fluent fully observed?
  • Are there noisy observations?
  • What partial information do we have about the actions (if any)?

This project aims to capture the space of existing approaches in a unified framework for re-use, and further to highlight the key deficiencies in the field of data-driven action model induction. The techniques to be explored and reproduced are a mix of algorithmic processing and logic-based encodings. Depending on the success of the project, novel techniques will also be introduced, some of which incorporating elements of machine learning to the process.

Successful students need not have research experience, but the project will introduce students to advanced research topics in the field of automated planning. Learning how to navigate these areas of research, under the guidance of Prof. Christian Muise, is a key element of this position.

Deliverables

At the conclusion of this project, students will have produced a library for action model induction that covers a wide variety of existing and new techniques depending on the assumptions of the input data. Further, a high-level analysis of the existing techniques will be delivered in a summary write-up, including a matrix matching problem setting to applicable techniques.

Application Procedure

To apply for the above project, please email Prof. Muise with the following details:

  1. Your name and a bit of background about yourself.

  2. The project name and expression of your interest in the area.

  3. Your Queen’s transcript.

  4. If you are Canadian (affects funding sources you may be eligible for).

  5. (if available) A CV/Resume

  6. (if available) A link to any software/projects you’ve worked on (e.g., GitHub profile).

  7. At least one of the roles is reserved for a member of an underrepresented group (race/ethnicity, gender, sexual orientation, disability, etc.). Please self-identify what underrepresented/minority group(s) you belong to if you feel comfortable doing so and you would like to be considered for this role.

We will reach out to interested students and possibly interview if there is high demand for the project. If necessary, the interview process will involve a small coding exercise as well as meeting with Prof. Muise and/or Mu Lab members.