Automatic behavior composition synthesis

Giuseppe De Giacomo

doi:10.1016/j.artint.2012.12.001

2013-03-01

Giuseppe De Giacomo

Fabio Patrizi

Sebastian Sardiña *

DOI：10.1016/j.artint.2012.12.001

原文链接

查看原文

摘要

En 中文

The behavior composition problem amounts to realizing a virtual desired module (e.g., a surveillance agent system) by suitably coordinating (and re-purposing) the execution of a set of available modules (e.g., a video camera, vacuum cleaner, a robot, etc.). In particular, we investigate techniques to synthesize a controller implementing a fully controllable target behavior by suitably coordinating available partially controllable behaviors that are to execute within a shared, fully observable, but partially predictable (i.e., non-deterministic), environment. Both behaviors and environment are represented as arbitrary finite state transition systems. The technique we propose is directly based on the idea that the controller job is to coordinate the concurrent execution of the available behaviors so as to mimic the target behavior. To this end, we exploit a variant of the formal notion of simulation to formally capture the notion of mimicking, and we show that the technique proposed is sound and complete, optimal with respect to computational complexity, and robust for different kind of system failures. In addition, we demonstrate that the technique is well suited for highly efficient implementation based on synthesis by model checking technologies, by relating the problem to that of finding a winning strategy in a special safety game and explaining how to actually solve it using an existing verification tool. (C) 2013 Elsevier B.V. All rights reserved.

Keyword:

Knowledge representation and reasoning

Intelligent agents

Reasoning about actions and change

Automated planning

Synthesis of reactive systems