These projects are suitable as:
A popular way of looking at practical Artificial Intelligence systems is to characterise them as `autonomous agents'. Such an agent is a system that interacts with an environment, be it a game of chess, a chat room, the stock exchange, or any sort of simulation. An agent typically have a set of sensors to receive information from its environment, and a set of actuators to make changes to it. The main challenge in designing an agent is deciding on a decision making process; on when and how the agent is going to act. The AI community has developed a wide range of technologies to assist in this, such as machine learning and planning techniques. Your task is to investigate ways in which they can be applied to an autonomous agent, and to implement an agent that uses one of more of these technologies in an interesting way.
This project is intended to be a fun way of exploring a range of AI technologies. Applicants should highly motivated by the idea of designing and implementing their own agent. The project can have either a more practical or a more theoretical emphasis at the participant's discretion.
Supervision will be provided on a day-to-day basis by Iain Little
In online transactions we often deal with people we do not know. How can we possibly be sure about who we can trust and who we should better not trust. A popular method is to use a reputation system which keeps track of the past performance of every user of the system and which assists users in forming their opinion about whether another user can be trusted. Even though many reputation systems are being used (the most prominent is probably the eBay Feedback System), their performance is not satisfactory at all and many fraudulent transactions are still happening.
The aim of the project is to develop and implement a reputation system and to compare its performance with existing systems. Interested students should have experience with online transactions and existing reputation systems.
Supervision will be provided on a day-to-day basis by Dr. Jochen Renz
As a subfield in Artificial Intelligence, diagnosis is concerned with the development of algorithms and techniques capable of determining whether the behaviour of a system is correct. If the system is not functioning correctly, the algorithm must determine, as accurately as possible, which part of the system is faulty and what kind of fault it is facing. The computation is based on observations, which provide information about the current behaviour or the system.
In model-based diagnosis for dynamic systems, the diagnosis task generally consists in simulating the system (based on its model) to find the behaviours that explain the observations. Formally, the diagnosis can be defined as the synchronised product of two automata representing the model and the observations. Applying this definition naively leads to an inefficient computation, and several realistic approaches have been developped and are been developped to remedy this: decentralised computations and representations, use of symbolic, abstractions, slicing in temporal windows, etc. With such approaches, the diagnosis is no more an automaton but a set of automata, each of which represents the global diagnosis projected onto a given subsystem or a given period. Manipulating such elements becomes particularly difficult in the sense that the refinement of one of these automata can lead to the refinement of other automata.
This project aims at building an architecture in JAVA to manipulate this set of automata. This architecture must be highly flexible to answer a range of specific diagnosis problems. This project fits to students able to understand mathematical notations, or interested into getting such abilities. The student will also have to make important implementation choices.
Supervision will be provided on a day-to-day basis by Dr. Alban Grastien
Video games are an excellent testbed for artificial intelligence research. They model real-life features such as uncertainty and dynamic worlds, and are suitable for several AI areas such as planning, learning and heuristic search. Commercial games are a fast-growing multi-billion dollar industry. The contacts between industry and academia are more and more present, stimulated in part by the newly created AIIDE conference, meant to bridge the gaps between the two communities.
We offer an opportunity to work on such an exciting application and possibly engage in a longer collaboration. Here are a few more concrete project ideas to begin with:
We expect the applicants to have strong C++ programming skills and an interest in artificial intelligence.
Further links:
Supervision will be provided on a day-to-day basis by Dr. Adi Botea.
General Game Playing is an initiative from Michael Genesereth at Stanford university, which promotes building programs that are capable of playing arbitrary games by looking at the description of their rules. This differs from usual game-playing programs such as Deep Blue which are dedicated to one particular game (namely chess in this case), but are unable to play any other game even if the rules are merely variants of those the system was designed for.
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. Supervision will be provided on a day-to-day basis by Dr. Sylvie Thiebaux.
Games are becoming closer and closer to real life and some tasks we have to solve in games are similar to tasks we have to solve in our real life. One surprising difference is that for many people solving the tasks in games is much more fun and less tiring than in real life. Consequently, it can be useful to transform tasks or work we do not like into a game and do our work by playing a game--or even better, let other players do the work for us.
In this project we will analyse different possible tasks, select one of them, transform it into a game and test its performance. Interested students should be interested in playing games and have experience with different game concepts.
Supervision will be provided on a day-to-day basis by Dr. Jochen Renz or Dr. Alban Grastien.
In computer science and engineering, spatial information (such as the spatial description of a room or a city) is often represented using coordinate systems, but this is not the way humans deal with spatial information. We often describe spatial features by specifying the relationship between objects in space (for example, the book is "on" the table, "to the left of" the screen). This is what is done in the area of Qualitative Spatial Representation and Reasoning, an important subfield of Artificial Intelligence. It is possible to define many different spatial relations for different aspects of space such as direction relations, distance relations, size relations etc. and to express spatial knowledge using these relations.
We offer different projects within this framework. Here is a small selection, other topics available on request:
Since reasoning with these relations is a very complex problem, it requires a detailed theoretical analysis of the different relations in order to find efficient reasoning algorithms for different sets of relations. However, recent advances in the area allow to make this theoretical analysis and to find efficient reasoning algorithms automatically. In this project we look at different spatial calculi, test if we can find efficient algorithms automatically and try to find out what makes reasoning hard.
Using qualitative spatial relations is very helpful for describing routes and for providing navigation assistance as such expressions are easier for users to understand and to remember. In this project we will try to extract qualitative spatial relations using maps, landmarks and the current location of users, plan routes according to different criteria and express the routes in terms of qualitative spatial descriptions.
There are several ways of representing biological entities like proteins, molecules or cells, which are often too complex for applying data-mining, machine learning or other computational techniques. Many of the functional properties of biological entities and of their interactions depend on spatial properties, e.g. a protein might only interact with another protein if it is folded in a way that some of its parts are accessible from the outside to other proteins. The idea of this project is to find examples of biological properties and interactions where spatial relationships are important, identify and categorise these relationships, and based on this find simple functional representations of biological entities which could be used for applying computational techniques. A background in artificial intelligence or biology/bioinformatics would be desirable but not essential.
Supervision will be provided on a day-to-day basis by Dr. Jochen Renz
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 work on developing the best planner in the world based on problem factoring. 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 for further involvement, for instance in the framework of an honours or PhD research project exist.
Supervision will be provided by a group of researchers, with day to day contact with Dr. Adi Botea
In recent years, the Planning Domain Definition Language (PDDL) has become the de facto standard formalism for specifying AI planning problems. PDDL is highly expressive in principle (it can model the dynamics of any finite state transition system, and with recent extensions also some kinds of timed/hybrid transition systems), but viewed as modelling language it does leave a lot to be desired.
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.
Supervision will be provided on a day-to-day basis by Dr. Patrik Haslum.
Characteristic of planning systems is that they develop a complete plan of action for achieving a specified goal, before that plan is considered for execution. Reactive systems, on the other hand, look only at the present state in order to select the next action to execute. In between these extremes are methods using bounded look-ahead, that is, developing a plan for a limited number of actions or a limited time into the future, and using this plan to make the choice of the next action to execute. In control engineering, this method is known as "model predictive" or "receding horizon" control, and it has been successfully applied to hybrid control problems (involving mixed discrete and continuous states).
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.
Supervision will be provided on a day-to-day basis by Dr. Patrik Haslum.
Translation into the classical propositional logic has been proposed as a powerful and general solution technique for classical AI planning. The actions of many planning problems are best represented in terms of schemata that are instantiated with given objects to obtain the actual actions. For example, a generic schema for the movement of vehicles between locations is IN(V,X) => -IN(V,X), IN(V,Y) in which V can be instantiated with any vehicle and X and Y with any locations. Kautz and Selman [1996] and Ernst et al. [IJCAI'1997] have considered compact representations of schematic actions in the propositional logic. The idea is that in a schematic action with parameters X, Y and Z, not all state variables in the schema depend on all of these variables, and this often makes it possible to represent the preconditions and effects of several actions more compactly. However, the afore-mentioned works restrict to sequential plans, and there is a lot of potential to improve the efficiency of planning further by considering some notion of parallel plans which allows the execution of several actions simultaneously.
The goal of the research project is to develop compact representations of schematic actions for parallel plans in the propositional logic. If the regularities in the actions described by an action schema are recognized, a more compact representation of the planning problem is possible, potentially leading to much more efficient planning. The work will include extending the ideas presented by Kautz and Selman and Ernst et al. to parallel plans as well as developing new techniques for compact action representation, and then implementing these techniques as a part of a planning system.
Supervision will be provided on a day-to-day basis by Dr. Jussi Rintanen.
Planning is the process of deciding which tasks to perform and how to schedule them to best achieve a given goal. We are currently working on complex planning domains, featuring probabilistic outcomes, uncertain task durations and resources consumption. The planning tool we have developped is the first one capable of handling these features at once. It is also quite efficient; it is the winner of the most recent International Probabilistic Planning Competition.
Various questions can be addressed in the probabilistic temporal planning framework. There are many opportunities for improving the planning algorithms, may that be in the framework of Markov Decision Processes or in more classical planning settings. Other issues as plan visualization or human-machine interaction are crucial, since complex domain knowledge needs to be captured as easily as possible, the plan should be made easily understandable and the user may need to give feedback to the software (by setting new constraints for planning). Finally many theoretical issues about the expressivity and complexity of different classes of probabilistic temporal planning problems remain, as do remain questions about the generation of finite plans in problems with inifinite (continuous) state spaces. There are several sub-projects available, around the following lines:
The student will work independently and will be supervised by a group of researchers, with day to day contact with one of the supervisors listed above (the precise supervisor will depend on the sub-project). Software developed in this project may end up being used by the Defence Science Technology Organisation.
Planning aims at deciding the actions to perform to best achieve a goal from the current state. When there is no uncertainty in the domain, plans are produced by a deterministic planner and simply take the form of sequences of actions. On the other hand, when actions have probabilistic effects, one option is to use a probabilistic planner which handles this uncertainty upfront by generating conditional plans. These plans prescribe actions as a function of what may happen in the world during execution. Another, more pragmatic option is to assume no uncertainty, use a determinstic planner, and replan when the current state at execution is not anticipated in the sequential plan. Only the first option enables reasoning about the risk associated with various courses of actions. The advantage of the second lies in the efficiency of planning in deterministic domains.
The goal of the project is to determine when replanning is better than handling efficiency upfront. There have been suggestions that, when considering the benchmark domains used in the last International Probabilistic Planning Competition, a simple replanning approach is able to solve more problems (reach a goal state more often on average) than the competition winner, a probabilistic planner. The student will start from these results, analyse them, propose benchmark problems that defeat replanning, and attempt to generalise from their properties to provide an as informative characterisation as possible. At least two models will be considered: a model without cost, where the objective is simply to reach a goal state as often as possible on average, and one which also accounts for the average number of actions performed.
This project will suit a student with an interest in artificial intelligence, a desire to learn about various aspects of AI planning, and good problem-solving skills. Some knowledge of Markov processes might be useful but is not necessary. Supervision will be provided on a day-to-day basis by Dr. Sylvie Thiebaux, and by PhD student Iain Little, the author of one of the competing probabilistic planners.
Probabilistic planning is concerned with domains where the agent wishes to achieve a goal with high probability when its initial state and/or action effects are probabilistic. It is possible to encode probability distributions, as well as the entire probabilistic planning domain, using propositional logic. One can then compile the logic into a special form that allows efficient inference. The key is that the compilation can often be very efficient as it exploits the structure of the planning domain.
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, concurrent 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 next year's International Planning Competition.
Many applications require the representation of data or knowledge in the form of a binary relation or a graph, like "X knows Y" or "location X has a road connection to location Y".
If the number of nodes in a graph is big, 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.
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 approxmation guarantees, and developing improvements to the existing algorithms and identifying heuristics that improve the algorithms.
Supervision will be provided on a day-to-day basis by Dr. Jussi Rintanen.
A number of heuristic search algorithms have been proposed for solving probabilistic and nondeterministic planning problems, including AO*, LAO*, LRTDP and more specialized ones for specific classes of planning problems. Some of these algorithms can be viewed as consisting of two steps that are performed repeatedly: a heuristic search algorithm extending the current set of states, which we call the envelope, and a dynamic programming algorithm which tests whether there is a plan for the current envelope that is also a plan for the original problem consisting of all the states.
The goal of the work is to devise a general algorithm schema that unifies two or more of the afore-mentioned heuristic search algorithms, based on the notion of the envelope. The schema can be instantiated with different heuristics for extending the envelope and with different dynamic programming algorithms for constructing a plan that only visits states within the envelope. An implementation of the algorithm schema will be used to demonstrate the wide applicability of the basic idea and the heuristics for expanding the envelope.
Supervision will be provided on a day-to-day basis by Dr. Jussi Rintanen.
Search is one of the most important technologies in artificial intelligence. Computer-controlled characters in real-time games, for example, need to find paths fast in order for games to be interesting and believable. The summer student will combine two fast search technologies into a system that is able to plan paths in gridworlds, namely a search method that uses abstraction hierarchies and one that uses experience from previous searches to speed up the current one.
The student will be supervised on a daily basis by NICTA researcher Adi Botea and NICTA visitor Sven Koenig, the creators of the two component technologies, but should be able to solve some problems independently. The summer student needs to have sufficient knowledge of artificial intelligence to understand papers that describe the component technologies. Some starter code will be provided. The summer student should be able to program fluently in C/C++. Some knowledge of algorithms and data structures as well as research skills will be helpful.
A* is the most popular search method in artificial intelligence. Incremental search allows one to solve a sequence of similar search problems faster than by solving the individual search problems from scratch. Over the years, several researchers have created incremental versions of A*. Most of these search methods have never been compared experimentally. The summer student will implement them and then compare them experimentally.
The student will be supervised on a daily basis by NICTA researcher Patrik Haslum and NICTA visitor Sven Koenig but should be able to solve some problems independently. Code for some of the incremental search algorithms will be provided. The summer student needs to have sufficient knowledge of artificial intelligence to understand papers about the search algorithms and implement them. The summer student should be able to program fluently in C/C++. Some knowledge of algorithms and datastructures as well as research skills will be helpful.