Process-Algebraic Approaches for Multi-Agent Systems: An Overview

Very often, cross-fertilisation between seemingly distant research fields is the source of research breakthrough, and brings to the discovery of new solutions to relevant theoretical and practical problems. We focus on two remarkable research contexts: multi-agent systems (MAS) and process algebras (PA). In the literature, PA are typically used to build a formal foundation for a number of basic concepts of computer science such as processes, interaction, and distributed computing. On the other hand, peculiar to the field of MAS is the integration and mutual influence of many ideas coming from heterogeneous areas: agents bring together theory and practice of software engineering, artificial intelligence, robotics and distributed systems with several concepts inspired by social sciences, biology, psychology, and so on. A MAS is a particular sort of distributed system. Primarily composed of a (possibly open) set of autonomous agents, a MAS typically features other sorts of entities and abstractions, such as resources of various kinds (sensors, actuators, physical entities in general, information sources, and the like), human actors, service infrastructures, and so on. An (autonomous) agent is an entity encapsulating its own control, sensing its environment and keeping a representation of it, and also acting on that environment according to a goal of its own. Nevertheless, even though they are driven by their own agenda, agents in a MAS are not necessarily selfish. Instead, they are generally social, and cooperate with other agents in the MAS in order to achieve more general goals – namely, the social goals of the MAS. Hence, the MAS paradigm is very useful to model, engineer, and realise complex distributed systems in terms of different agents with their own specific task, promoting a level of encapsulation (of control, task, goal), decoupling and reusability significantly higher than that of objects or components. Typical applications of MASs are the development of Internet applications, workflow management systems, automatic decision processes such as in network auctions and negotiations, and modelling and simulation of biological and natural systems. On the other hand, PA are a framework for the description of interactive systems which is nowadays widely disseminated, well-understood and adopted. The main representative PA is still Milner's CCS, which has given raise to a huge number of extensions, addressing many different aspects such as mobility, quantitative and stochastic issues, timing, etcetera. A PA can be viewed as a language for describing the behaviour of processes, with a set of operators (closed under the language) including a parallel-composition operator representing concurrency between processes. The semantics of such a language is given in terms of a structural operational semantics (SOS): the language itself can then be used to denote an interactive system as well as its (interactive) state over time. Along the whole engineering process, PA are used at many stages: for the system specification and design, for the implementation in terms of executable specification, for the analysis and verification of the properties of interests such as behavioural equivalence. The application contexts of PA go beyond the mere area of software systems: other than distributed systems, they are also used in electronic circuits, biological systems, telecommunication protocols, authentication protocols, and distributed control networks.