Student research opportunities

Decision-Theoretic Planning via Boolean Satisfiability

Project Code: CECS_815

This project is available at the following levels:
CS single semester, Engn4200, Engn R&D, Honours, Summer Scholar, Masters, PhD

Keywords:

"Automated Planning" "Artificial Intelligence" "Probabilistic Reasoning"

Supervisors:

Dr Scott Sanner
Dr Charles GRETTON
Dr Phil Kilby

Outline:

Mobile and immobile robots perform many functions that are key to the
productivity and scientific gains made in the last 20 years. For
example, robotic arms pack chocolate bars onto crates at the Cadbury
chocolate factory in Bournville (Birmingham, UK). Robot platforms
perform geological surveys of extraterrestrial surfaces (on Mars), and
study the geochemistry of hydrothermal plumes on our ocean floors
(e.g.,the Endeavor segment of the Juan de Fuca Ridge). Closer to home,
they dig and cart ores from mine pits to other transport
infrastructure (Pilbara, Western Australia). Such robots must
deliberate intelligently according to sensed aspects of their
environment, and synthesize action strategies in order to perform
their assigned tasks reliably and efficiently.

In this project the student will develop general, efficient, and
scalable techniques for the automated synthesis of such action
strategies. As the title suggests, the plan synthesis algorithms that
we will develop and study in this project shall leverage recent
developments in decision procedures for solving Boolean satisfiability
problems.

Goals of this project

(2 months -- Summer Scholar) Develop a compilation of
decision-theoretic planning problems to a Partially Weighted Maximum
Satisfiability representation.

(honours/engineering project) In addition, develop a fast, efficient,
and scalable procedure to perform decision-theoretic planning using
the above representation.

(Higher Degree -- PhD) There are very significant research questions (both theoretical and empirical) in this direction that can underlie an ambitious higher degree project. Please contact/write-to me if this interests you, and I can provide further details.

Although the student might pursue algorithm development in a
programming language of their choice, implementation aspects of this
project can be done by modifying an existing C++ codebase.

Requirements/Prerequisites

Ambitious hard working student with a strong track record in technical subjects.

A keen interest in Optimisation and Artificial Intelligence.

A student who applies for this project should wish to pursue a career
in research, either as a research engineer, or academic.

Student Gain

Experience working at NICTA, a world-class ITC research organisation.

Graduate level knowledge of key topics in Uncertainty in Artificial
Intelligence and Constraints Processing.

Background Literature

Nathan Robinson, Charles Gretton, Duc Nghia Pham, Abdul Sattar:
Partial Weighted MaxSAT for Optimal Planning. PRICAI 2010: 231-243.

Moritz Göbelbecker, Charles Gretton, Richard Dearden: A Switching
Planner for Combined Task and Observation Planning. AAAI 2011.

Nathan Robinson, Charles Gretton, Duc Nghia Pham, Abdul Sattar:
SAT-Based Parallel Planning Using a Split Representation of
Actions. ICAPS 2009.

Duc Nghia Pham, John Thornton, Charles Gretton, Abdul Sattar:
Combining Adaptive and Dynamic Local Search for Satisfiability. JSAT
4(2-4): 149-172 (2008).

Charles Gretton: Gradient-Based Relational Reinforcement Learning of
Temporally Extended Policies. ICAPS 2007: 168-175.

Charles Gretton, Sylvie Thiébaux: Exploiting First-Order Regression in
Inductive Policy Selection. UAI 2004: 217-225.

Silvia Richter, Matthias Westphal: The LAMA Planner: Guiding
Cost-Based Anytime Planning with
Landmarks. J. Artif. Intell. Res. (JAIR) 39: 127-177 (2010)