Optimisation of embedded virtual complex systems by re-using a library of available components

Project Summary

• Sebastian Sardina - Chief Investigator - RMIT University, Melbourne, Australia
  
• Maurice Pagnucco - Chief Investigator - UNSW University, Sydney, Australia.
  
• Giuseppe De Giacomo - Partner Investigator - La Sapienza University, Rome, Italy.
  

Research Position Available - Reasoning about action, automated planning and synthesis, intelligent agents, optimisation
KR & Agent Postdoctoral Position: RMIT University, Melbourne, Australia
Seeking Expression of Interest

[ THIS POSITION HAS BEEN FILLED ALREADY AND IS NOT ANYMORE AVAILABLE ]]

We will be advertising a postdoctoral position between 2-3 years, starting early to mid 2012, working within the Intelligent Agents Group at RMIT University in Melbourne, and the Artificial Intelligence Laboratory at University of New South Wales in Sydney. The project will also involve collaboration with staff from "La Sapienza" University in Rome, Italy. The specific position is as a postdoc on the ARC grant ``Optimisation of embedded virtual complex systems by re-using a library of available components''. This project involves developing principled representation and reasoning mechanisms for tackling the so-called behaviour composition problem in ways amenable for practical implementation.

We are looking for a person with an excellent record of working on practical knowledge representation and reasoning problems, producing high quality publications with good impact. We are looking for expertise in areas of artificial intelligence such as automated planning, optimisation, knowledge representation and reasoning, intelligent agents, verification, and synthesis. The person should be able to work well in a team, but should also be able to take a lead role in driving forward the research. 

RMIT has a large computer science department with a well established and internationally recognised research group in the area of Intelligent Agents. Melbourne is a hub for a significant amount of research and development in Intelligent Agents and their applications and is the home of "Agents Victoria" a group of industry, government and university groups, involved in agent research and applications. UNSW is ranked among the top 100 for Computer Science in the Academic Ranking of World Universities. It is a partner in the ARC Centre of Excellence for Autonomous Systems (CAS) which is the second largest robotics research group in the world with a leading reputation for both fundamental
research and the application of this to industry.

Please email expressions of interest to Sebastian Sardina <sebastian.sardina@rmit.edu.au>. Please put POSTDOC in the subject header.

Some URLs:

• Intelligent Agents Group at RMIT
• RMIT School of Computer Science and IT
• UNSW School of Computer Science and Engineering
• AI Group at UNSW
  

Project Description

In a nutshell, the behaviour composition problem involves automatically synthesising a controller-coordinator that can implement a given desired but non-existing target complex behaviour (e.g., a home entertainment system) by using a set of available existing behaviour modules (e.g., video cameras, TVs, lights, music and game devices, etc.). A behaviour here refers to the operational logic of a system and is general represented as a transition system. This composition synthesis problem is important in that it can be recast in a variety of forms within several sub-areas of Artificial Intelligence and Computer Science, including robot ecologies and intelligent spaces, agent programming and multi-agent system, web-service composition, automated planning, among others.

In particular, whereas previous work has exclusively aimed at the synthesis of full realisations of the desired component—controllers that implement the desired component in its totality—, this project aims at developing a framework for behaviour composition optimisation that will cater for: (a) unsolvable problem instances where no perfect controller exists; (b) difficult instances where sub-optimal solutions may suffice; and (c) relevant domain specific information that is not being considered by any approach to date.

Indeed with the exception of our AAMAS'11 paper, all the literature on behaviour composition has only dealt with perfect compositions to date: the composition controller ought to guarantee the realisation of every possible target step always. This poses a major limitation in that for many, if not most, problem instances there will be no composition at all. For such cases, a (merely) “no solution” outcome is extremely unsatisfactory. What is more, while many composition problem instances may accept a perfect controller, the synthesis of suchcontroller may be computationally intractable (the problem in its various forms has been proven EXPTIME-complete). The overarching objective of this project is to develop a new composition framework and techniques for the actual computation of solutions, that will accommodate non-solvable and difficult problem instances. Since those instances are indeed the most common ones in any realistic setting, this will make behaviour composition problem applicable to a much wider range of cases.

The project may involve dealing and applying various techniques from CS and AI, including generalized versions of planning, intelligent agent approaches, synthesis of reactive systems (e.g., LTL-syntesis), PDL satisfiability and game-theoretic ATL verification, decision theoretic approaches (e.g., MDPs), and even genetic algorithms.

Some references related to the project:

1. Nitin Yadav and Sebastian Sardina. Decision theoretic behavior composition. In Tumer, Yolum, Sonenberg, and Stone, editors, <em>Proceedings of  Autonomous Agents and Multi-Agent Systems (AAMAS), pages 575-582, Taipei,  Taiwan, May 2011. ACM Press.
2. Ströder, T., Pagnucco, M. Realising Deterministic Behavior from Multiple Non-Deterministic Behaviors, In Proceedings of the Twentyfirst International
   Joint Conference on Artificial Intelligence (IJCAI'09), pp. 936 -- 941, Pasedena, USA, July 2009.
3. Sebastian Sardina, Fabio Patrizi, and Giuseppe De Giacomo. Behavior composition in the presence of failure. In Gerhard Brewka and Jerome Lang, editors, Proceedings of Principles of Knowledge Representation and Reasoning (KR), pages 640-650, Sydney, Australia, September 2008. AAAI Press
4. ] P. Balbiani, F. Cheikh, and G. Feuillade. Composition of interactive web services based on controller synthesis. In Proc. of the IEEE Congress on Services (SERVICES), pages 521–528, 2008.
5. Y. Lustig and M. Y. Vardi. Synthesis from component libraries. In Proc. of the International Confernece on Foundations of Software Science and Computational Structures (FOSSACS), volume 5504 of LNCS, pages 395–409. Springer, 2009.
   
6. Giuseppe De Giacomo and Sebastian Sardina. Automatic synthesis of new behaviors from a library of available behaviors. In Manuela M. Veloso, editor, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 1866-1871, Hyderabad, India, January 2007.
   

More Information

Please email Sebastian Sardina if you are interested.