Keywords

1 Introduction

The development of Artificial Intelligence (AI) can be presented as the transition from models of Individual Intelligence to models of both Group Intelligence and Social Intelligence. In terms of agent-oriented approach to AI, nowadays a classical intelligent system gives a way to knowledge-based agent which performs some activity under the requirement of logical omniscience (AI-1 level). The arrival of multi-agent systems (MAS) extends the conventional knowledge lifecycle and turns the problem of knowledge engineering into belief engineering together with organizing collective activity and designing agents interactions. Here MAS may be viewed as a group (team) agent generated via collaboration of individual agents (AI-2 level). Finally, the transformation of cooperating multi-agent systems into artificial societies makes the emphasis on social laws and MAS roles governing both the behavior and the evolution of such societies. The investigation of MAS communities in the framework of social organization can be referred to as AI-3 level [24].

Here two strategies of designing artificial social organizations are worth considering: bottom-up design and top-down design. The bottom-up design deals with the construction of artificial societies from group agents via goal sharing, resource allocation and collaboration strategies. In particular, autopoietic societies and co-evolutionary societal development are worth mentioning. Inversely, the top-down approach focuses on social organization statics and dynamics. It is influenced by changing relationships between interacting MAS (cooperation vs competition, subordination vs coordination, agreement vs conflict, etc.).

Below we will associate synergetic artificial intelligence approaches to the levels of AI-2 and AI-3.

The paper is organized in the following way. The fundamentals of synergetic artificial intelligence and its links with swarm intelligence are considered in Sect. 2. Basic classifications of agents and multi-agent systems are considered, the comparison between intelligent and reactive agents is made. Here conventional group intelligence and swarm intelligence are characterized by different synergy sources. Finally, the concepts of swarms, swarm intelligence and swarm robotics are considered. The problems of simulating and managing static swarms are faced in Sect. 3. The principles and models of swarm tasks distribution via local interactions are formulated in Sect. 4. The results of experimental investigation of pack-hunting task are analyzed in Sect. 5.

2 Synergetic Artificial Intelligence and Group Robotics

2.1 What Is Synergetic AI?

One of recent trends in modern Artificial Intelligence consists in constructing integrated, heterogeneous, hybrid systems. Such systems are formed from various interrelated rious components interrelated.

Integration and hybridization of different methods and technologies allow us to face complex problems, which cannot be solved by applying conventional AI methods and technologies. Here integration is viewed as a necessary condition for hybridization/In biology, hybridization is considered as a specific form of integration, where different genetic characteristics and components are merged in an organism. Hybrid systems in Computer Science use two of more different information technologies.

Two good example of hybrid AI methodologies are Soft Computing [17, 30] and Computational Intelligence [18, 20].

The concept of hybrid system is tightly connected with the idea of synergetic system (which was disseminated by H.Haken and I.Prigogine), i.e. self-organizing, evolutionary system, where the evolution is based on communication, cooperation and coordination.

The term «Synergetics» was coined in late 1970’s by Hermann Haken [8]; it was generated from the Greek word «synergia», that means cooperation, collaboration, joint action. The introduction of the term «synergetics» to specify modern theory of complex, open, self-organizing systems has at least two reasons: (a) cooperation of various (possibly heterogeneous) elements in an evolving system is considered; (b) formulation of general self-organization principles and investigation of its specific mechanisms requires collaboration of various sciences.

The concept of Synergetic Artificial Intelligence (SynAI) was introduced in 2000 (see [23,24,25]). The main research objects of synergetic AI are open, self-organizing, cooperating, evolving intelligent systems. Generally, these systems have such features as: (a) presence and combination of different, heterogeneous components and sub-systems; (b) co-adaptiveness and co-evolution of these components and sub-systems; (c) open, growing structure, flexible network organization; (d) distributed or decentralized control; (e) good ability to cope with such factors as uncertainty, ambiguity, inaccuracy, fuzziness, etc. The field of SynAI includes primarily investigations of such problems as generation, formation, self-organization, evolution, communication, collaboration, cooperation of intelligent systems.

A basic idea of SynAI consists in combining different AI approaches and models (earlier seen as incompatible) for building artificial collective (social) structure to obtain non-linear, synergetic effects, in particular, to compensate individual drawbacks and to enhance advantages of participating sub-systems of the system. Here emergence and destruction, non-stable states, dynamics, mutual transformations of intelligent systems are of special concern. Moreover, a sort of behavioral or cognitive resonance may be reached through contagion or inspiration procedures.

Besides, it means introducing synergetic dimension into classical AI models and methods. Its key principle is the impossibility to reduce the development of artificial general intelligent system [1] to classical knowledge engineering. Apart knowledge (or, more generally, belief) engineering other «dimensions of intelligence» ought to be considered, including agent’s interaction engineering, activity self-organization, conative management, etc. Furthermore, such items as open dynamic knowledge bases (and belief bases), plausible, defeasible, modifiable reasoning, synthesis of integrated cognitive procedures, computing with words and perceptions [31], as well as computing with figures are worth mentioning.

Some differences between classical AI and synergetic AI are shown in Table 1.

Table 1. Classical AI vs Synergetic AI
Full size table

According to synergetic paradigm in AI, a basic investigation object for SynAI is a group or society of (generally heterogeneous) interacting agents.

2.2 Classifications of Agents and Multi-Agent Systems

The generation of synergetic intelligent systems may be based on both intelligent and reactive agents. Any full-function agent is supposed to possess at least four basic subsystems: cognitive, regulative (behavior formation), conative and organizational. An artificial intelligent agent has a well-developed knowledge base, reasoning on action facilities and friendly user interface. In particular, cognitive agent constructs a rather complete internal model of its environment and obtains current data by using sensor systems/Any intelligent agent exhibits goal-directed or purposeful behavior; it also tends to use the resources of other agents to achieve proper goals.

Contrarily, reactive agents function mainly on stimulus-reaction level; they usually have rather poor individuality and strong dependency on their community. The properties of both intelligent and reactive agents are shown in Table 2.

Table 2. Comparison of intelligent and reactive agents
Full size table

Thus, two main trends in developing multi-agent systems are group intelligence-the development of MAS on the basis intelligent agents and swarm intelligence – the formation of collective intelligence structures from non-intelligent and even weakly individualized agents. In the first case, we can obtain the synergetic effects through goal sharing, joint use of different resources and intensive collaboration between intelligent agents. In the second case, the main sources of synergy are proximity of reactive agents (generation of collective behavior through contagion), distribution of functions and advanced social structure.

Below we shall pay special attention to artificial swarms, swarm intelligence and swarm robotics.

2.3 From Artificial Swarms to Swarm Robotics

Artificial Swarm is a set of artificial agents able to interact, create and modify functional patterns and collectively perform various tasks by parallel acts. In other words, the swarm represents a dynamic network of interacting agents, where both consistent collective perception of signals and concerted action to environment are observed. Basic principles of swarm formation and operation are [6]: (1) principle of agents neighborhood; (2) principle of specifying habitat quality; (3) principle of swarm adaptation; (4) principle of necessary diversity of swarm responses; (5) principle of swarm stability.

A high-level view of a swarm [2] suggests that the N agents in the swarm are cooperating to achieve some collective behavior. This apparent «collective intelligence” seems to emerge from interactions in large groups of relatively simple agents. The agents use local rules to govern their actions and via the joint acts of the entire group, the swarm achieves its objectives.

It is obvious that swarm intelligence may be viewed as a specific example of synergetic AI, where synergy of reactive agents in the form of their local interactions brings about the emergence of global intelligent behavior (selection of habitat, development of social structure, and so on). For example, the highest level of animal sociality is eusociality that is defined by the following characteristics: cooperative brood care (including brood care of offspring from other individuals), overlapping generations within a colony of adults, and a division of labor into reproductive and non-reproductive groups. The division of labor creates specialized behavioral groups within an animal society which are sometimes called castes. Eusociality is distinguished from all other social systems because individuals of at least one caste usually lose the ability to perform at least one behavior characteristic of individuals in another caste.

Swarm intelligence is the emergent collective intelligence branch that considers groups of simple reactive agents [6, 24, 28]. Here, reactive agent is a subsystem that interacts with its environment, which consists of other agents, and acts together with them [2]. For example, a bird to participate in a flock, adjusts its movements to coordinate with the movements of its flock mates, typically its «neighbors» that are close to it in the flock. It tries to stay close to its neighbors, but avoid collisions with them. Each bird can fly in the front, center and back of the swarm. Swarm behavior helps birds take advantage of several things including protection from predators (especially for birds in the middle of the flock), and searching for food (essentially each bird is exploiting the eyes of every other bird – it is the essence of swarm cognition phenomenon).

Swarm robotics [2,3,4, 11, 12, 19, 27, 29] is a useful approach to organizing multi-robot systems which consist of large numbers of mostly simple reactive robots. It is supposed that a desired collective behavior emerges from the interactions between the robots and interactions of robots with the environment. This approach in the field of artificial swarms is based on biological studies of insects, ants and other fields in nature, where swarm behavior occurs.

Here a key component is communication between members of the group that builds a system of constant feedback. The swarm behavior involves constant change of individuals in cooperation with others, as well as the dynamic behavior of the whole group.

Unlike distributed systems of cognitive robots, swarm robotics emphasizes a large number of functionally various simple robots. Such a functional granulation is viewed as an important mechanism of swarm behavior.

3 Static Swarms

One of the models describing the organisation of a great number of locally interacting agents or robots is the so-called static swarm. This arrangement is characterised by the absence of a control centre and represents the given network fixed at some time interval as a set of agents [10, 22, 24].

It is a rather natural scheme. A majority of works on decentralized AI have a fundamentally static view: the structures that describe the degree of «local centralization» are fixed during the assignment process [14].

The main feature of a static swarm is that at some moment, instead of a set of separated agents, the computing structure is completely defined, enabling the solution of difficult calculation and data processing tasks. It follows that a static swarm can be considered as a wholistic object with emergent properties – other than a simple set of agents properties.

The main properties of a static swarm are collective activity, locality of interactions and functional heterogeneity.

Collective Activity. The network of agents is able to perceive signals from the environment, and to produce some effector functions (such as motion) in order to have an impact on its nearest environment.

Locality of interaction. An important feature of a static swarm is essentially the local nature of interaction: agents communicate only with their neighbors.

Functional heterogeneity. The solution of complex tasks (i.e. manifestation of emergent properties of a system) assumes the formation of heterogeneous groups.

This heterogeneity arises from differentiation of functions performed by agents: strategic and tactical management, gathering and processing information, realisation of effector functions, and so on. The mechanism of this functional heterogeneity in natural swarm still remains an open problem.

From the practical point of view, the static swarm is a temporary structure. Naturally, the movement of agents changes links between elements and leads to structural changes in the swarm. Therefore, functioning of the entire system is reduced to some timepoint agents. It forms the static structure for the joint solution of a task, for example, exchange of information, logical inference, and so forth. The agents gather for some kind of «conference», after which the static swarm breaks up and its elements function according to the received roles before the «conference».

Let us consider the following task. Let us take a set of agents (robots) capable of local information exchange between nearest neighbors. At some time point, the static swarm has to realize a procedure for role distribution: some individual should act as a control centre, another one must serve as data processing function, and another one has to collect information from external environment, etc.

General principles of roles distribution can be based on the following obvious ideas: a node (agent) with a maximum number of links (neighbors) becomes a candidate for the control centre role. Its nearest neighbors are information analyzers; they prepare information for decision-making. Furthermore, nodes located on the periphery of the network are responsible for gathering information. An example of such a network of agents is shown in Fig. 1.

Fig. 1.
figure 1

An example of swarm network organization

Full size image

4 Task Distribution

In the absence of morphological distinctions between agents, role distribution in a static swarm is defined exclusively by the current topology of the system. The distribution process is presented as a well-known procedure of control wave distribution. The initiator of distribution is the leader, whose role is designated as R0. Direct neighbors of this leader receive an initial message, according to which a role R1 is assigned to them, and so on. Thus, the role of robot i is defined by the roles in its environment:

$$ R_{i} = \mathop {\hbox{max} }\limits_{k \in Z} R_{k} + 1 $$

The wave distribution of roles is realized exclusively by local interactions, but there exists an essential problem. For successful functioning of the system, M roles are required, with the process of distribution of a wave consisting of L steps (Fig. 2).

Fig. 2.
figure 2

Actual (L) and required role number (M)

Full size image

If M = L, there is no problem. If M < L, there are too many performers of the role R M . This is not a good situation, but it is not fatal because in a static swarm we are not interested in role distribution optimization (like in [9]). If M > L, however, the situation is worse, as there is a deficiency of performers, which is extremely undesirable. Agents playing several roles at once (combination of specializations) can cover the performance deficit, so that definition of the procedure whereby an agent should assume additional functions seems simple. For example, if an agent with a role number L has no neighbors with roles bigger than L, it means that this agent is at the periphery. Further, if we know that M roles are needed, this agent has to assume roles from L to M. The prevention of any deficiency can also be specified in advance. If there exists a group of N agents with maximum connectivity to each agent s (the maximum number of neighbors), it is possible to estimate the minimum number of roles M. The estimate of the M value is M ~ log S N.

5 Pack-Hunting Task

Now we shall consider the following task. Let us define a field, on which there are agents of two kinds, predators and their victims. The field has a limited size and forms a toroidal surface, i.e. the edges of the field are closed. The task consists of defining rules of predator behavior so that they are victims for minimum time. In some sense, we have a variant of the pursuit-evasion problem here.

Agents can move and they are equipped with four sensors. Every sensor can detect another agent in front, behind, at the left and to the right of it. The field of vision of the agent is limited. The agent can send a broadcasting message. This message can be accepted only its close neighbors.

A victim is an agent with very primitive behavior. When a predator appears in its field of vision, it victim runs away in the opposite direction. They are pure individualists. The victim perishes when the predator appears near it in the next field.

We assume that the speed of the victim is twice that of the predator.

For a toroidal surface and low predator speed, it becomes a very complex challenge to catch up with the victim. Thus, formation of groups of hunters, i.e. packs, can be useful.

The formation of a pack is not a primitive process. If predators have a behavioral rule ‘IF (sensor detects a predator) THEN (move to it)’ then after some time all predators will form compact motionless groups. In this situation, predators need a leader to lead this pack. This leader can be named as Local Leader.

As mentioned above, there is a simple technical escape. Each agent has its individual and unique parameter, an identifier ID. This ID can play the role of the agent’s weight. The agent with the greatest weight becomes the Local Leader. The Local Leader does not use the rule «move to the nearest neighbor». It tries to find a victim and uses a wandering strategy. All other members of the group follow it.

A set of wandering packs with Local Leaders (red color) is shown in Fig. 3.

Fig. 3.
figure 3

The set of packs. Local Leaders are red. The others predators (white) follow them

Full size image

A schema of pack-hunting is given below and consists of two stages: Search for Victim and Hunting Procedure.

This compact (packing) motion is not enough for successful hunting. The pack does not catch up with a fast victim. The pack has to surround it. This means that it is necessary to cast beaters. So, we have a situation with role distribution.

Search for Victim:

  1. 1.

    A pack formation. Hunters follow Local Leaders.

  2. 2.

    If some agent detects a victim, then start Hunting Procedure.

Hunting Procedure:

  1. 1.

    Leader election. The initial weight of a candidate is neither its ID number nor the number of neighbours. Initial weights are determined by proximity to the victim.

  2. 2.

    Role distribution. In this task, predators have two roles: the left and right beaters. The main objective is to bypass the victim from two sides and not to allow it to escape.

An example of three stages of the hunting procedure is given in Fig. 4.

Fig. 4.
figure 4

(a) Hunters detect a victim. (b) Roles are distributed. Hunters bypass a victim. (c) Hunters «attack» a victim

Full size image

A series of experiments was carried out. Parameters of experiments are:

Agent number: 30 hunters (Nh), 10 victims (Nv)

Size of field: 100 × 100 cells (a toroidal surface)

Hunter’s speed: 1 (one step per timepoint)

Victim speed: 2

Modelling time, T: 500 steps

Two strategies of hunting were estimated: individual hunting and pack-hunting.

The averaged results of 50 experiments are shown in Fig. 5.

Fig. 5.
figure 5

Dependence of victims number on time. «Pack» shows a pack-hunting strategy, and «Indiv» shows individual hunting.

Full size image

It is clear that an individual strategy is more preferable in a situation when there is a lot of «food». It is easy to hunt. A pack-hunting strategy gets advantages when ‘food’ becomes scarce. In general, this strategy is more successful.

We want to point out that the cornerstone of this solution is a symbiosis of the leader election and role distribution procedures.

6 Conclusion

The converging trends of synergetic artificial intelligence and swarm robotics have been analyzed. Simple and effective methods have been proposed for the solution of important problems of swarm robotics such as role distribution and eusociality in a group of agents. Efficiency is understood as the acceptability of robots with limited cognitive abilities (insufficiency of sensory abilities, computing capacities, communications channels, etc.- in short, all that is peculiar to a swarm).

The leader definition and role distribution introduce a differentiation of functions in homogeneous groups of robots, which provides a growth of cognitive abilities of a swarm and transition to complex task performance. Advantages of this approach are, for example, the task of cooperative hunting by distributed mobile robots. In some sense, we can say that the cognitive abilities of a pack of hunters in a static swarm are higher than those of an ‘ordinary’ swarm (a homogenous set of individuals without functional differentiation).

Despite of its simplicity, the implementation of these mechanisms opens the basic opportunity of forming very complex structures in organizing homogeneous groups, and again confirms that distinctions between a swarm, flock and collective of robots are somewhat artificial.

The static swarm model is a convenient way of looking at swarm robot organization. While it is limited to exclusively local interaction between agents, it offers all the advantages of a system understood as a network of connected agents, allowing solutions to problems such as storage and data processing, coordinated movement and so on (see [10]).

In further work, we hope to investigate the mechanism of inference in static swarms, hypothesizing that these procedures can be implemented by exclusively local interaction methods.