Embedded Files
Course delivered within the ERASMUS+ KA107 Mobility Exchange Program - 2019
1 page flyer here and a pack of overview slides.
Dates and time schedule: Thursday March 28 - Wednesday April 3 (11am to 1pm)
Location: IIIA-CSIC, http://iiia.csic.es/en/location
Language: English
Instructor: A/Prof. Sebastian Sardina, RMIT University, Melbourne, AUSTRALIA
This course will survey some of the main developments in agent behavior synthesis and composition, the problem of automatically synthesizing a coordinator controller that implements a given desired but non-existing target complex behavior (e.g., a home system) by using a set of available existing behavior modules (e.g., cameras, TVs, lights, blinds, music system, phone). A behaviour here refers to the operational logic of a system and is general represented as a transition system. The composition problem is relevant and important in that with computers now present in everyday devices like mobile phones, credit cards, cars and planes or places like homes, offices and factories, the trend is to build embedded complex systems from a collection of simple components. Also, the problem can be recast in a variety of forms within several sub-areas of Artificial Intelligence and Computer Science, including verification, automated planning, intelligent spaces, agent programming, web-services, and business processes. The course will mix technical presentation with small exercises, and a final small project.
(image from pixabay)
Course Schedule
Course Schedule
This is the tentative schedule for the course. As the course progresses, the schedule may be adjusted to fit how the students are learning the material.
Session 1 [Introduction, Motivation, Preliminaries] (slides)
Session 1 [Introduction, Motivation, Preliminaries] (slides)
- Introduction.
- Course Overview.
- Motivation on Behavior Composition: behavior composition and automatic program synthesis; domains of applicability; relevant areas of CS and AI.
- Preliminaries: Behaviors as Transition systems, nondeterminism, reachability, simulation, bisimulation.
Session 2 [Service Orchestration via Simulation]
Session 2 [Service Orchestration via Simulation]
- The Roman Model for Service Orchestration. (SLIDES)
- AI Composition with nondeterministic agent behaviors. (SLIDES)
- Orchestration and Composition via Simulation. (SLIDES)
- Service Orchestration via Simulation.
- Behavior Composition via ND-Simulation.
- Just in time, failures, parsimonious refinements.
Session 3 [Composition via 2-player Games] - (SLIDES)
Session 3 [Composition via 2-player Games] - (SLIDES)
- Game Structures: Behavior synthesis against opponent, two player game structure and game goals, LTL for goals, safety (goal) games.
- Composition via 2GS model checking.
Session 4 [Behavior Composition via TLV] - (SLIDES)
Session 4 [Behavior Composition via TLV] - (SLIDES)
- Realizing a 2GS for composition in TLV.
- Get TLV from this git repo.
Session 5 [Supremal Composition] - (SLIDES)
Session 5 [Supremal Composition] - (SLIDES)
- Review: Composition as a 2-player game over TLV.
- Step-by-step review of a TLV encoding.
- Composition optimization: Supremal Realizable Target.
- Unsolvable composition problems: what to do?
Main References
Main References
- Giuseppe De Giacomo, Fabio Patrizi, Sebastian Sardiña: Automatic behavior composition synthesis. Artificial Intelligence 196: 106-142 (2013)
- Giuseppe De Giacomo, Alfonso Emilio Gerevini, Fabio Patrizi, Alessandro Saetti, Sebastian Sardiña: Agent planning programs. Artificial Intelligence 231: 64-106 (2016).
- 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
- Giuseppe De Giacomo, Massimo Mecella, Fabio Patrizi: Automated Service Composition Based on Behaviors: The Roman Model. Web Services Foundations 2014: 189-214
Material
- Overview of course: a very compact summary of the course here.
- Full slides for the tutorial will be available later as the course progresses.
- Some tools:
- Temporal Logic Verifier (TLV): http://www.cs.nyu.edu/acsys/tlv/
- But best to get it from my TLV repo here.
- NuGAT: A game Solver with GR(1) and LTL specifications.
- MCMAS: Model checking for multi-agent systems.
- SynKit: A synthesis tool for rapid prototyping of LTL and LTLf specifications.
- SLUGS: Stand-alone reactive synthesis tool for generalized reactivity(1) synthesis.
- LTLMo P (Linear Temporal Logic MissiOn Planning): collection of Python applications for designing, testing, and implementing hybrid controllers generated automatically from task specifications written in Structured English or Temporal Logic.
- Temporal Logic Verifier (TLV): http://www.cs.nyu.edu/acsys/tlv/
Who should be interested?
Who should be interested?
Students interested in the ambitious “automatic programming” or “program synthesis” problem (the “Church Problem”): automatically building an executable piece of code given (high-level) user intent. Behavior Composition is a “nice” special case. It is easy to understand for the non-expert in synthesis, and is complex enough (hard to do it manually), intuitive (can be grounded in many domains); complete (includes all the main synthesis components/features); has full output (synthesis is a finite program); and is feasible (can be done computationally!)
What would be good to know before?
- Mandatory: knowledge of discrete mathematics for Computer Science (e.g., graphs, propositional logic, set theory).
- Desirable: automata theory (e.g., finite state machines).
Google Sites
Report abuse