Automatic Synthesis & Composition of Agent Behaviors

IJCAI'15 Tutorial

Giuseppe De Giacomo, Fabio Patrizi and Sebastian Sardina

The tutorial will survey some of the major developments in agent behavior synthesis and composition. The tutorial will cover the problem specification, the various techniques developed to solve it, and the relationship with various problems in several areas of CS and AI.

The behavior 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.

Topics covered

  1. Intro - Motivation, domains of applicability, areas.

  2. Background

    1. Transition systems

    2. Bisimulation and Simulation

  3. Service Composition

    1. Deterministic stateful service as transition systems

    2. Service composition

  1. Agent Behavior Composition

    1. Nondeterministic agent behaviors as transition systems

    2. Behavior composition

      1. Composition by ND-simulation

    3. Just in time, failures, parsimonious refinements

  1. Game Structures

      1. Behavior synthesis against opponent

    1. Two player game structure and game goals

    2. Mu-calculus for goals

      1. Model checking game structures

  1. Composition via 2GS Model Checking

    1. Safety (goal) games

      1. Composition via 2GS model checking

    2. Controller Synthesis

    3. Relationship with LTL and ATL synthesis

    4. Tools: TLV, MCSMAS, NuGAT

  1. Approximations

    1. Unsolvable problems: what to do?

    2. Decision-theoretic composition

    3. Supremal Realizable Target

  1. Further work

    1. Agent Planning Programs

    2. Data box/planning domain

    3. Partial Observability

    4. Multitarget composition

    5. Program composition

    6. Planning-based composition

Main References

Tutorial Material

    • Overview of tutorial: a compact summary of the tutorial.

      • Obs: The set of slides to be used in the actual tutorial will be different and more comprehensive. Still this set of slides should provide a good idea of the topics to be covered.

  • Full slides for the tutorial can be downloaded below.