This document contains topics for medium-length projects suitable for honours students and as shorter variants for summer scholars, Erasmus Mundus and other similar projects, as well as PhD thesis projects which take 3 years to complete. The list of PhD topics is incomplete: it is best to discuss the possible PhD thesis topics with the individual researchers by first contacting them by email.
If you want to start PhD studies you have to follow the ANU application procedures and contact a potential supervisor to write a research plan.
The aim of this project is to apply the method of model predictive control to planning problems, in particular problems with such hybrid domains (involving metric time and resources) and where optimization of the cost of the plan carried out is a main concern. One of the main differences between control and planning is that while the objective of automatic control is typically to keep the controlled system stable or near a reference point, the objective in planning is to drive the controlled system to a specified goal state. Thus, one of the the main challenges of this project is taking into account the estimated cost of eventually achieving to the goal while optimizing a plan for the near future, particularly in the context of hybrid constraint optimization methods (such as LP/SAT, MILP and similar).
This project requires a good understanding of "formal stuff" (such as hybrid state/transition systems, admissible heuristics, etc.), though it's not particularly mathematical in nature. Programming skills are also likely to be required, though for the heaviest part of the implementation (optimization of hybrid constraint systems) there are probably systems/libraries available that can be used.
Contact: Dr. Patrik Haslum
The aim of this project is to create a more convenient (easy to use) modelling language for planning problems, that can be efficiently compiled into PDDL, and to implement this compilation. Such a modelling language could borrow concepts or constructs from modern programming languages, for instance object orientation (inheritance and polymorphism) or templates, but also build on concepts from research in automated planning, for instance finite domain variable representations or generic types. The envisioned language is primarily intended for modelling finite and deterministic planning problems (so called "classical planning"), and the compilation to generate problems in the corresponding subset of PDDL, but could also be extended to capture problems with metric time and resources, "soft goals", or uncertainty (which would then be compiled into one of the extended PDDL fragments). The compilation could also be extended with more advanced forms of problem analysis and simplification.
This project requires good software design and programming skills (it is, after all, about creating something close to a programming language), and some familiarity with elementary logic is also very useful. Knowledge of AI planning and knowledge representation techniques is an advantage, but not strictly necessary.
Contact: Dr. Patrik Haslum
Another area of artificial intelligence, AI planning, has developed very efficient general tools to solve problems consisting in finding a sequence of actions (or moves) to reach a goal state. The most successful planners use search guided by heuristics that they automatically generate from the problem description. This is directly applicable to single-player games, such as Sokoban, the Freecell card game, or the old Rubik's Cube, but not to multi-player games.
The project consists in building a general game playing agent by extending a to-be-chosen AI planner and its automatic heuristic generation to solve a class of multi-player games of complete information, described in the Game Description Language (GDL). The player should be able to connect to the Stanford game manager, and will hopefully be able to enter the next General Game Playing Competition -- there is 10,000 USD prize to the winner!
This project will suit a student with an interest in artificial intelligence and a desire to learn about various aspects of games and planning, with good problem-solving skills and decent programming skills. Some knowledge of these topics and of elementary logic would be appreciated but is not necessary.
Contact: Dr. Sylvie Thiebaux
Diagnosis is determining what happens on a system (car, plane, telecommunication network, water supply network, etc.) from observations on this system. This is an important task for monitoring and maintenance of expensive or critical systems. The main difficulty is usually to manage complexity. Discrete-event systems is a modeling of dynamic systems based on discrete (i.e. not continuous) variables.
Satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the specified formula evaluate to TRUE. This 50-years-old problem is still very active and attracts a lot of attention as many problems in Computer Science can be translated into SAT.
The possibilities of SAT solvers for diagnosis have not completely been investigated. Extensions of the recent results in order to improve both efficiency and expressiveness of this approach include:
A. Grastien, Anbulagan, J. Rintanen and E. Kelareva, Diagnosis of discrete-event systems using satisfiability algorithms, Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-07), AAAI Press, 2007
J. Rintanen and A. Grastien, Diagnosability testing with satisfiability algorithms, in M. Veloso, ed., Proceedings of the 20th International Joint Conference on Artificial Intelligence, pages 532-537, AAAI Press, 2007.
Contact: Dr. Alban Grastien
This task requires time, expertise, and can be unsuccessful in some cases. We propose to use the diagnosis techniques to diagnose the server, and also to determine which level of verbosity is required for each software in the server (diagnosability). The system behaviour is described in a model and a reasoning is performed on the model to understand what happens on the system.
You will be involved in the first task (modelling of a mail server) to enable the second task (diagnosability and diagnosis). The former is not independent from the latter and you will have to understand the diagnosis techniques and test your modelling to improve or refine the modelling.
This project requires knowledge in Linux and networks (and ideally, in mail servers). Knowledge in AI techniques is an advantage but not necessary. It suits particularly for students who want to have a practical application.
Contact: Dr. Alban Grastien
Planning is the problem of finding a sequence of actions that reach a goal starting from a given initial state. Factored planning is a relatively new family of decomposition approaches which are useful when a problem is too large to be solved as one piece and has an appropriate structure. We integrate this into the SuperCom project, where a large real-life system (e.g., the water network in a city) is monitored and automatically reconfigured to a normal state (using planning) when faults are detected.
There are many possible factored planning methods, and many ways of improving their performance. The project will consist in helping in the design and implementation (in JAVA) of one such method.
We expect the applicants to have good programming and problem-solving skills and an interest in artificial intelligence. Joining this project is an excellent opportunity to learn about planning and do exciting and rewarding work that will be used to solve real problems. Opportunities exits for further collaboration, for instance as an honours or PhD student.
Contact: Dr. Adi Botea
Diagnosis and planning are two techniques at the core of the AI component of an immobot. Diagnosis processes sensor data and makes inferences about the system status. When a fault is detected, planning tells how to automatically reconfigure the system back to a normal state.
The goal of the project is to design and implement a model that integrates planning and diagnosis.
The applicants should have good Java programming skills. The project can be extended into an honours and/or PhD program.
Contact: Dr. Adi Botea, Dr. Alban Grastien
If the number of nodes in a graph is high, like tens of thousands or millions, and the graph is dense, then representing all the edges explicitly one at a time leads to very inefficient processing of the data. By recognizing regularities in the graph and utilizing the regularity to represent the graph more compactly, big improvements in efficiency can be obtained. One regularity in many big and dense graphs is the presence of complete bipartite subgraphs N,M in which there is an edge between every node in N and every node in M. Each such subgraph could be represented simply by representing N and M, without enumerating all the |N| X |M| edges explicitly. Another regularity, complete subgraphs (cliques), can be compactly represented in terms of bipartite subgraphs too.
The goal of the research is to develop efficient algorithms for compressing the representation of graphs by identifying complete bipartite subgraphs in them. Finding the maximal bipartite subgraph of a graph is an NP-hard problem. Some polynomial time approximation algorithms with approximation guarantees exist, but it seems that they are not very practical for graphs consisting of tens of thousands or millions of nodes.
The work will proceed by implementing and comparing existing approximation algorithms with and without approximation guarantees, and developing improvements to the existing algorithms and identifying heuristics for improving them.
Contact: Dr. Jussi Rintanen
Satisfiability (SAT) is the problem of determining whether a Boolean formula can evaluate to true (i.e., be satisfied) under some assignment of truth values to its variables. For example, the formula ((X or (not Y)) and (X or Y or (not Z)) and ((not X) or (not Y) or (not Z))) can be satisfied by assigning false to all three variables.
Problems in many areas of AI and computer science can be reduced to SAT. Although SAT is NP-complete, problem instances arising from real-world applications often have special structure allowing them to be solved efficiently. Current SAT solvers are frequently able to solve instances with over a million variables.
This project will involve a review of the latest SAT technology, particularly a class of algorithms known as clause learning, followed by an attempt to advance the state of the art by proposing new algorithms or improvements to existing algorithms. On the practical side, the student will have access to an existing simple (yet competitive) SAT solver, written in C++, and will modify it and conduct experiments to explore the possibilities of improving its performance. The final product could be either an extension of the existing solver or an entirely new solver, which can then be entered into next year's International SAT Competition.
Contact: Dr. Jinbo Huang
This compilation-based approach has greatly improved the efficiency and scalability of probabilistic reasoning with Bayesian networks, which has much in common with probabilistic planning. We would therefore like to investigate the possibility of carrying this success over to probabilistic planning. The main challenge would be to design and implement new domain encoding methods, and new algorithms to work with these encodings, that can solve a given type of planning task (e.g., conformant planning, contingent planning, etc.). The compilation part will be accomplished using an existing state-of-the-art knowledge compiler. The new planner implemented can then be entered into the next International Planning Competition.
Contact: Dr. Jinbo Huang
The goal of the project is to implement a very efficient planner based on SAT/CSP technology by integrating the constraint solver with the problem representation that is specific to planning problems. This way it is possible to utilize constraint reasoning techniques for planning more efficiently while still benefiting from powerful inferences sanctioned by techniques like constraint propagation and clause-learning.
Contact: Dr. Jussi Rintanen
The purpose of this project is to cast the layout problem as a constraint satisfaction problem and demonstrate its utility as a fast prototyping method and possibly as a method for finding non-obvious designs a human designer might overlook. Finding better designs is an important factor in cost effectiveness of a building. Constraint Satisfaction provides a general and powerful framework for expressing and solving design problems.
Depending on the desired extent of the project, the work could initially restrict to the design of residential buildings. Constraints on the room layout express spatial relations between the locations of the rooms, between building features such as doors and windows, as well as typical pieces and setups of furniture. For example, a typical living room in a small apartment includes a couch, armchairs, a table and television, the placement of which has to satisfy certain constraints derived from their intended functions.
Contact: Dr. Jussi Rintanen
Chronicles Recognition [Dousson, 2002] is a diagnosis technique that has been successfully applied to several domains including the diagnosis of telecommunication networks and the diagnosis of cardiac arrhytmia (see for instance [Fromont et al., 2003]). Basically, a chronicle is a list of temporally-constrainted events. A chronicle is recognised when an instance of each event is found in the flow of observations that satisfies the constraints. The chronicle are usually made ``by hand''.=20 Automatic generation of chronicles are challenging, although it has investigated for Petri-Nets-modelled system [Guerraz--Dousson, 2004] or cardiac arrythmias (through Machine Learning techniques).
In this project, we propose to automatically generate chronicles-like patterns from a finite-state-machine-based model. This task is difficult as it must avoid ambiguities and false recognitions. The work will be theoretical but also applied to the monitoring of mail servers.
References:
Elisa Fromont, Marie-Odile Cordier, Ren=E9 Quiniou, and Alfredo Hernandez: Kardio and Calicot: a comparison of two cardiac arrhythmia classifiers , AIME'03 Workshop: Qualitative and Model-based Reasoning in Biomedicine
Christophe Dousson : Extending and unifying chronicle representation with event counters, ECAI'02
Bruno Guerraz and Christophe Dousson Chronicles Construction Starting from the Fault Model of the System to Diagnose, DX'04
Contact: Dr. Alban Grastien
The project is an investigation of implementation techniques for network-oriented planning. The basis is a planning language which is based on a modal logic for expressing network properties. The goal is the development of an efficient planning system for this language by using heuristic search and the state space representation of the planning problem. The main goal of the project is an implemented planning system, but the topic provides ample possibilities for more theoretical/analytical excursions to more fundamental questions about network-oriented planning.
Contact: Dr. Jussi Rintanen
Contact: Dr. Jussi Rintanen
The goal of the PhD thesis is to cover all aspects of application-specific control of SAT solvers. This includes
An ideal PhD candidate would have a strong theoretical background in computational logic and some of its spplications as well as strong practical skills in applying them to real world problems, and also strong programming skills.
Contact: Dr. Jussi Rintanen
An important extension of the SAT problem, QBF, is a natural basis for solving many extended reasoning tasks for which SAT is not expressive enough. The algorithmic basis of QBF is similar to SAT but not as well understood.
For both SAT and QBF there currently exist no theory why the CDCL+restarts based solvers work so well.
The goal of the thesis is to investigate the proof systems and proof procedures for SAT and QBF and potentially develop new and more efficient ones for both. The focus of the work will be in QBF solving, but understanding the state of the art in both areas it will be necessary to first establish a better understanding of the functioning of algorithms for solving SAT as well. Specific questions to be asked and answered include the following.
An ideal candidate for this project has a deep interest in analytic questions about fundamental problems in computer science, including complexity theory and NP-hardness, proof systems and algorithms, and also strong practical skills in applying the analytic skills for solving challenging theoretical and practical problems.
Contact: Dr. Jussi Rintanen