Sebastian Sardina, Giuseppe De Giacomo
Imagine a collection of available devices, such as a camera, a vacuum cleaner, or robotic arm, each of which is able to act (that is, perform actions) according to a given behavior specification, expressed as a finite transition system. Imagine next a set of virtual independent and autonomous agents, such as a surveillance agent or a cleaning agent, which are meant to operate concurrently, each within a given specification of its capabilities, again expressed as a finite transition system. The question then is: can we guarantee the realization of every agent by intelligently scheduling the available devices while fully preserving the agents' autonomy? In this paper, we define the problem formally, and propose a technique to actually generate a solution by appealing to recent results in LTL-based synthesis of reactive systems. We also show that the proposed technique is optimal with respect to computational complexity.
Subjects: 7.1 Multi-Agent Systems; 11. Knowledge Representation
Submitted: Jun 27, 2008