Academic Research

My research focuses on an area of Artificial Intelligence called Automated Planning; a field dedicated to synthesizing and executing strategies in an automated fashion in order to achieve a given goal. E.g., plans that enable a robot to perform a complex set of tasks in order to achieve an objective. In particular, I developed methods for planning under the assumption that we cannot control the outcomes of our actions fully (i.e., they are non-deterministic).

Recent work applies automated planning techniques to the fields of multi-agent planning and epistemic reasoning. My research aim is to devise new methods for relaxing two common assumptions found in Automated Planning: omniscience (where agents are all-knowing about the world) and omnipotence (where the planning agent assumes control over all other agents).


Multi-agent Planning

My work into multi-agent planning (MEP) focuses on removing two key assumptions that typically go hand-in-hand with multi-agent planning approaches: omniscience and omnipotence.

Logical omniscience allows the reasoning agent to know everything there is to know about the world, including what all of the other agents think. We remove this assumption by using a syntactic form of nested belief for the agents in the world, and the resulting planner can solve a wide class of epistemic planning problems.

Logical omnipotence allows the reasoning agent to control the actions of every agent in the world. Instead of assuming control over all of the agents, the reasoning agent must consider all possible actions that they may take. We re-cast the multi-agent planning problem as a fully observable non-deterministic problem where the actions of other agents are treated as separate non-deterministic outcomes. We improve the efficiency of the planner by focusing on the outcomes that correspond to the most plausible actions for the agents; as predicted using a model of their goal.

Moving forward, my research will combine both approaches to produce a reasoning agent that does not need to know everything about the world or have to control all of the agents in the environment.

Related Publications

Non-deterministic Planning

A large portion of my research focuses on efficient fully observable non-deterministic (FOND) planning, and its applications to various planning formalisms. As part of my dissertation, I created a state-of-the-art planner for non-deterministic problems, PRP, and I continue to maintain it along with various extensions that allow PRP to solve related problems. These include handling probabilistic action outcomes, partial observability, and multi-agent settings.

The planner's efficiency stems from the focus on relevance. Many aspects of the planner consider only the relevant part of what holds true in the state of the world. In doing so, it improves the reasoning techniques, solution representation, plan generality, etc. It is because of these techniques that PRP can compute solutions to problems that have trillions of reachable states, faster than any other planner to date.

Related Publications

Knowledge Compilation

Knowledge compilation is a compelling technique for dealing with the intractability of propositional reasoning. One particularly effective target language is Deterministic Decomposable Negation Normal Form (d-DNNF). We created DSHARP to exploit recent advances in #SAT solving in order to produce a new state-of-the-art CNF -> d-DNNF compiler. DSHARP is an open source CNF-to-dDNNF compiler based on sharpSAT. Similar to the c2d software, DSHARP takes a boolean theory in conjunctive normal form as input, and compiles it into deterministic decomposable negation normal form.

In collaboration with others, DSHARP has been applied to information flow programs and also extended to compile answer-set programs as input as well as theories where a subset of the variables should be projected away. See [here] for a brief discussion of the related work.

Related Publications

Execution Monitoring

Execution monitoring (EM) is the area of automated planning that focuses on what to do once a plan is found. The real world does not always behave as our models predict, and monitoring the execution of a plan is vital if we wish to discover when the plan no longer will achieve the goal.

My research into the area of execution monitoring looks at how we can compile a partial order plan, possibly with temporal constraints restricting the execution, into a form that can be used for efficient execution. It allows for robust behaviour by repeating parts of the plan that become required again, as well as serendipitous behaviour by skipping over parts of the plan that are no longer needed to achieve the goal.

Related Publications