Problem Description

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. Thus a complex surveillance system for a smart house can be “realized” (i.e., implemented) by suitably coordinating the behaviors (i.e., the operational logic) of hundreds (or thousands) of simple devices and artifacts—lights, phones, blinds, a microwave, a vacuum cleaner, video cameras, a floor cleaning robot, etc.—installed in the house. Such embedded systems can provide services that range from simple tasks, such as “turn on the lights in the bedroom,” to more complex ones, such as “bring me a cup of coffee” or “handle house intruder” (by tracking and taking pictures of the intruder, toggling lights rapidly, and alerting the owner by email or phone).

The problem of automatically synthesizing, that is, building, such an embedded controller-coordinator for a given desired target complex system is called the behavior composition problem and is the focus of this project. Behavior here refers to the operational logic of a system. Existing work has aimed at the synthesis of full realizations of the desired component—controllers that implement the desired component in its totality— or at optimal aproximations for problem instances where no perfect controller exists.

The 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. In the areas of complex agent systems such as robot ecologies, ubiquitous robots or intelligent spaces, advanced robotic functionalities are not achieved through the development of extremely advanced robots, but rather through the cooperation of many simple robotic components. This is facilitated by the marked tendency today toward the embedding of many intelligent, networked robotic devices in our homes and offices. In software engineering, component-based development (CBD) requires both formal models of the behavior of software components and effective ways of composing such components. In robotics, sophisticated rescue systems can be built from a pool of available field robots. In agent programming, an intelligent agent may control the execution of a set of predefined non-deterministic plans in order to realize a desired deterministic plan-intention (which may have been obtained via planning), or a multi-agent system may coordinate or merge approximate multiple agents’ plans into a global multi-agent plan. Also, in the context of the semantic web, existing web-services may be composed on the Internet so as to implement a new complex web-service.