This topic is proposed as part of the French-Australian Science and Technology cooperation project "Planning Approaches to Sofware Verification", whose partners are INRIA, ANU, and UWA.
Games are a computational model used in computer science, economics, biology, and social sciences to name a few. The motivation for the present project arises from the area of multi-agent planning in artificial intelligence, but the results are applicable to other areas.
Given a description of the possible states of the game, of the states that are considered as winning positions, and of the actions that agents can take in each state, the basic problem is to find a winning strategy for a given agent coalition (a set of agents). Such a strategy specifies the actions that the coalition agents must take in each state, and guarantees that the coalition will end up in a winning state, regardless of the actions taken by agents outside the coalition. In the project, we focus on a slightly different problem, where the coalition is not given. Instead, we want to find the smallest size coalition which has a winning strategy. This is a computationally hard problem, so we will be building efficient algorithms which attempt to perform well on average. Such algorithms will use symbolic representations of set of states based on binary decision diagrams, and will automatically derive heuristics to guide the search from the description of the input game.
The student will start from a basic algorithm idea, which (s)he will flesh out, implement and extend to more complex cases such as: 1) computing a coalition of minimal cost, given a specification of the cost of collaboration, 2) partially observable games (agent decisions are based on partial information about the current state of the game), 3) more complex objectives than just reaching a winning state.
This topic is proposed as part of a collaboration with CNRS in the framework of the ROSACE project funded by the French Scientific and Technological Research Network for Aeronautics and Space. ROSACE studies the design, specification, implementation and deployment of a fleet of mobile autonomous cooperating robots with well-established properties particularly in terms of safety, self-healability, ability to achieve a set of missions and self-adaptation in a dynamic environment.
In the ROSACE project, a high-level mission is expanded into a set of goals which are allocated to the robots. The robots must act cooperatively to achieve these goals, and this might require explicitly delegating subgoals to other robots. Cooperatively synthesizing plans of actions is still a largely open problem. The student will design and implement a cooperative and distributed version of a standard planning algorithm. The algorithm will have to guarantee a number of desirable properties (termination, correctness, etc). This will require becoming familiar with automated planning, constraint satisfaction and distributed search methods.
This project is best suited to a student with interest and background in artificial intelligence, distributed algorithms, and with good programming skills.