Automatic Behavior Synthesis & Composition

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

Intro - Motivation, domains of applicability, areas.
Background
1. Transition systems
2. Bisimulation and Simulation
Service Composition

1. Deterministic stateful service as transition systems
2. Service composition

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

Game Structures
1. 1. Behavior synthesis against opponent

1. Two player game structure and game goals
2. Mu-calculus for goals
  1. Model checking game structures

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

Approximations

1. Unsolvable problems: what to do?
2. Decision-theoretic composition
3. Supremal Realizable Target

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

Giuseppe De Giacomo, Fabio Patrizi, Sebastian Sardiña: Automatic behavior composition synthesis. Artificial Intelligence 196: 106-142 (2013)
- Giuseppe De Giacomo, Paolo Felli, Fabio Patrizi, Sebastian Sardiña: Two-Player Game Structures for Generalized Planning and Agent Composition. AAAI 2010
- Nitin Yadav, Paolo Felli, Giuseppe De Giacomo, Sebastian Sardiña: Supremal Realizability of Behaviors with Uncontrollable Exogenous Events. IJCAI 2013
- Nitin Yadav, Sebastian Sardiña: Qualitative Approximate Behavior Composition. JELIA 2012: 450-462
- Giuseppe De Giacomo, Fabio Patrizi, Sebastian Sardiña: Agent programming via planning programs. AAMAS 2010: 491-498

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.