1 Introduction

Agents in a multi-agent system (MAS) face complex problems and do not always have all the capabilities to solve them alone. Thus, agents need to share theirs capacities in cooperative groups in order to reach the overall goal of their system. They need to find the best suited agents to compose their group in order to maximize the overall performance for the task resolution. This problem is called the coalition formation problem and has been addressed in many forms. To illustrate with a realistic example, in case of a large scale natural disaster [10] robots with different capabilities may rescue victims and they need to make coalitions owning the complete capabilities to rescue people. In this work we present an approach inspired by the group dynamics field in the Humanities and Social Sciences (HSS) using a swarming model with heterogeneous agents. Related work is quoted in Sect. 2 and 3 introduces our approach and defines the problem. A swarming model inspired from the literature is presented in Sect. 4. The integration of group dynamics features into a swarming context is described in Sect.  5 and experimental results shown in Sect. 6.

2 Related Work

The coalition formation problem is a broad problem addressed from different point of views as multi-agent system [16], robotic [6] or swarming [9]. It can be derived into very similar problems called Task allocation problem [12] or Knapsack problem [2]. Swarming approaches [1] are one method used to address this problem. They often use an optimization method technique called Ant Colony Optimization (ACO) [19] in order to find optimal coalitions but in this work we focus on swarming based on social potential field. Social potential field [13] is a distributed method used to make swarm from individuals by using attraction and repulsion forces between each individual. Social potential field is used to bring out a global behavior to individuals. [13] uses it for autonomous multi-robot control and [15] uses it into the multi-agent system field to make agents patrol on a terrain with obstacles. Among the swarming literature, some works are using heterogeneous agents or robots [6, 7, 17] that have different characteristics from others: they may have type, abilities or dynamics. [7] uses swarming with heterogeneous agents in order to achieve a self-organization of a MAS by modifying force fields depending on the type of agents. The swarming method used in this paper is inspired from this work. Yet, this work makes possible the self-organisation of agents into a system based on one characteristic (the type of agents) in order to make groups of homogeneous agents. The reality is often more complex and we would like to reuse this method to tackle the coalition formation problem where agents come together to try to achieve an overall goal based on more factors than a type or a weight.

3 The Coalition Formation Problem

In a large scale natural disaster scenario, robots can be stuck or destroyed because of debris. Thus the process of coalition formation has to be dynamic and robust. It has to be able to take into account the variability of agents and the openness of the system. This is why we choose a swarming method with social potential fields to make coalitions: their formation is processed distributively by each agent allowing to add or remove agents from the system without stopping it. In addition, agents characteristics can be modified at any time making this swarming method very robust.

As seen in the Sect. 2 some works focus on segregation of agents into heterogeneous swarming models. To the best of our knowledge, work that focuses on sorting heterogeneous swarms uses heterogeneous agents that differ only in one characteristic. But in a complex scenario we need agents to own a lot of characteristics as physical characteristics (e.g. battery state, sensors, etc.), capacities (moving, taking objects, etc.), mental characteristics (e.g. personal goal, desires, learning skills, etc.), etc. Thus, we propose a social approach of heterogeneous swarming able to make coalitions from several factors. Because humans are well suited to form groups and work efficiently in them, we draw inspiration from the group dynamics field [3] in HSS and use it with the swarming method as a new approach for the coalition formation problem. The group dynamics is a field that describes what small groups are, how they are formed and how they are maintained. This approach makes the group formation possible by taking into account several factors making heterogeneous swarming more relevant.

In the decentralized task allocation problem, we consider a set of N individuals \(A = \{a_0, a_1, ..., a_n\}\) in a 1-dimension Euclidean space. Agents have heterogeneous characteristics \(C = \{c_0, c_1, ..., c_n\}\) and desires \(D = \{d_0, d_1, ..., d_n\}\). A characteristic \(c_i\) is meeting a desire \(d_i\). Each individual \(a_n\) has its own set of characteristics and desires such that \(C_{a_n} = \{c^i_{a_n}, c^j_{a_n}, ..., c^m_{a_n}\}\) and \(D_{a_n} = \{d^k_{a_n}, d^l_{a_n}, ..., d^o_{a_n}\}\). Each individual is a point, unaware of its dimension, that knows the characteristics of all the other agents. The objective of the agents is to form groups with other agents who best meet their desires such that \(C_{a_j} \subset D_{a_i}\). The distance between two agents in the space is an attraction metric representing the attraction value that two individuals have for each other. It depends on the extent to which the agent’s desires are satisfied. The shorter the distance, the stronger the attraction between the agents. A group is a set of agents \(g_i\) for which all the agents have an attraction value for each other below a given threshold such that \(g_i = \{a_i, a_j, ..., a_m\}\) where \(\forall a_i, a_j \in g_i\), \(attraction(a_i \rightarrow a_j) < threshold\) and \(attraction(a_j \rightarrow a_i) < threshold\). Processing rules of the attraction are described in the next section through a swarm intelligence method. We assume here that agents can be part of only one group. In other word, \(\forall g_i, g_j\), \(g_i \cap g_j = \emptyset \).

4 Control Law Definition

4.1 Attraction/Repulsion Function

Agents attraction update is processed following this equation:

$$\begin{aligned} \dot{x}^i&= \sum _{j = 1, j \ne i }^{N} f\left( x^i - x^j \right)&f(y)&= -y \left( \frac{a}{\Vert y\Vert } - \frac{b}{\Vert y\Vert ^4} \right) \end{aligned}$$
(1)

where \(x^i\) and \(x^j\) are the position of individuals i and j into the Euclidean space. f(y) being the attraction/repulsion function inspired from [14] where a and b are two constants and ||y|| the Euclidean norm given by \(||y|| = \sqrt{y^Ty}\) which is the distance between two agents in the Euclidean space. We also made two parameter functions to choose the right a and b constants

$$\begin{aligned} f_a(z)&= \frac{0.05^z}{2}&f_b(z)&= 20^{(3+z)} \cdot z^3 \end{aligned}$$
(2)

z being a bias representing social factors described in Sect. 4.2. \(f_a\) and \(f_b\) were both made after empirical tests. They allow to keep a good ratio between a and b and are well managing the attraction/repulsion function whatever the z value is. However, these functions were not designed to be optimal.

Note that because the attraction/repulsion function is very similar to the one from [14], we do not give the theoretical proof of stabilization of this function in this document. However, you can find it in an extended version on ArXiv and HAL.

4.2 Social Factors Integration

In group dynamics, the Group Formation subfield focuses on the processes that generates bonds of attraction between members of groups. The group formation process is a complex phenomenon implying numerous dimensions. Among these dimensions, the attraction principles takes a large part. There are two types of attraction, the social attraction and the personal attraction. Social attraction is an attraction for a group whereas the personal attraction is “based on idiosyncratic preferences grounded in personal relationships” [5]. Because in swarming individuals are not aware of groups they are making, we focus on the personal attraction allowing to predict whether an individual is attracted to another one or not. The following principles are based on personal attraction [3, 11]:

  • proximity principle (p): proximity allows individuals to increase the number of their interactions. We see here the proximity principle as a distance between individuals.

  • similarity principle (s): individuals like people who are similar to them [4, 18]. In our system, the similarity is a distance between mind states of agents.

  • complementarity principle (c): individuals like other whose qualities complement their own. We represent it by the complementarity of the agents’ capacities.

  • reciprocity principle (r): liking tends to be mutual.

  • physical attractiveness principle (a): individuals are more attracted to people who have a great physical attractiveness [4]. In our system the physical attractiveness is seen as the adequacy between the characteristics of an individual and desires of others.

  • minimax principle (m): individuals are attracted to people that offer them maximum reward and minimal cost [4].

We want agents to be able to assess the attraction they have for other agents in order to allow to form groups into the system. To do so, we build the Eq. 3 that integrates these principles. However, group dynamics is only an inspiration source to build our equation. Even if we try to be consistent with the literature, we are not claiming that this equation can be used to predict the attraction between two real people.

$$\begin{aligned} z = (0.5 + p)~ \cdot ~average(a, s, c, m) \end{aligned}$$
(3)

5 Experimentation

In order to evaluate our mechanisms, we integrated them in an agent model. As our approach is socially inspired we have chosen the cognitive agent architecture Soar [8] to which we add specific features involving control laws. We characterize an agent by four modules that can be seen as sets of information.

  • personal characteristics (P): are physical or mental characteristics agents have (e.g. battery state, weight, shape),

  • capacities (C): are skills of the agent, actions it can execute on its environment, virtual processing it can do, or perceptions it can get from the environment (e.g. moving, taking objects, etc.),

  • beliefs (B): are the facts agents have about their environment (e.g. acquaintances characteristic, attraction for acquaintances, its group quality),

  • desires (D): are objectives or situations that the agent would like to accomplish or bring about (e.g. making a high quality group, resolving its personal goal, help its group mates);

In this experiment, we are using a 1-dimensions matrix of three floats between 0 and 1 to represent information of each module of our agents. The size of matrices does not have any importance for the proper functioning of the system. In order to use these information, we need to integrate the attraction principles from the Sect. 4.2 to our experimentation. Each principle undergoes a filter function used to scale each result between 0 and 1.

Proximity principle is the distance between two agents, represented as:

$$\begin{aligned} ||p||&= x^i - x^j&p&= filter(\sqrt{u^Tu}, d) \end{aligned}$$
(4)

where \(x^i\) and \(x^j\) are the position of agents i and j into the Euclidean space and d a parameter to be adjusted.

Similarity, Physical attractiveness and Minimax principle are processed in the same way as the Proximity principle. The similarity principle is a distance between the beliefs of two agents. The physical attractiveness principle is a distance between physical characteristics of one agent and the personal desires of another agent. The minimax principle is a distance between capacities of one agents and the desires of another one. Let \(\lceil M \rceil \) be the number of elements of a N dimensions matrix M.

$$\begin{aligned} ||u||&= x^i_{B} - x^j_{B}&s&= filter(\sqrt{u^Tu}, \lceil B \rceil ) \end{aligned}$$
(5)

where \(x^i_{b}\) and \(x^j_{b}\) are the Belief matrix of agents i and j. The Physical attractiveness principle and the minimax principle are processed exactly the same equation replacing the matrix used depending on the above description.

Complementarity principle is a distance between skills of two agents:

$$\begin{aligned} ||c||&= x^i_{C} - x^j_{C}&c&= 1 - filter(\sqrt{u^Tu}, \lceil C \rceil ) \end{aligned}$$
(6)

where \(x^i_{s}\) and \(x^j_{s}\) are the skills matrix of agents i and j and \(\lceil C \rceil \) the number of elements in the Capacities matrix.

Reciprocity principle is the mean of z between two individuals.

$$\begin{aligned} r = mean(z^{ij}, z^{ji}) \end{aligned}$$
(7)

where \(z^{ij}\) and \(z^{ji}\) are a real number representing the attraction of i to j and j to i. Previous equations undergoing the filter function defined as

$$\begin{aligned} filter(x, x_{max}) = min(\frac{x}{x_{max}}, 1) \end{aligned}$$
(8)

Finally, each agent process the control law from the Sect. 4 in 1-dimension for each other agent of the system.

6 Evaluation

In order to make each agent characteristics attractive to others, we pseudo-randomly generate populations of individuals. If the generation was fully random the characteristics of individuals could not be appropriate to be attractive to other agents and the number of groups would be unpredictable. Though, agents characteristics are not known in advance and it allows us to better illustrate the process of group formation.

Fig. 1.
figure 1

Attraction an agent i has for other agents of the system.

Full size image

Figures 1 illustrate the attraction each agent have for each of their acquaintances depending on the number of steps of the simulation. Firstly this simulation confirms experimentally the proof of stabilization of the attraction. Secondly, we can see that agents converge towards different attraction values. For example, agent 0 has a strong attraction for agents 1 and lower ones for agents 2 and 3. These differences are explained by a difference of characteristics that made agents 2 and 3 unattractive to agent 0. Finally, as illustrated, each agent has an attraction value over all the others allowing an outside viewer to visualize these links on a graph. To do so, we process a Gaussian mixture model clustering on attraction values allowing us to make clusters and to find agents for which they have the strongest attraction. Taking the cluster where attraction has the lowest average and linking agent to each agent of this cluster makes possible to build a graph representing groups as illustrated on the Fig. 2(a). Repeating the same process on a larger agent population (fifty agents, six groups), we obtain the Fig. 2(b). Moreover, each individual is capable to assess dynamically the attraction for its acquaintances. It means that even if groups are stabilized for a specific state of the system they can changed if an agent characteristic is modified. Note that this visualization is only a representation of the attraction agent have for each other. Links and groups made on these graphs can be modified depending on how clusters are built or what you consider being a strong attraction.

Fig. 2.
figure 2

Graph showing formed groups on two cases.

Full size image

7 Conclusion

This work tackles the coalition formation problem using a group dynamics inspired swarming approach. Its dynamicity allows to form groups of agents in an open system with a decentralized manner making this method very robust. In addition, the group dynamics inspiration from HSS allows the system to make swarms with heterogeneous agents made by a high number of characteristics.

We showed that our approach is robust and adapted to the coalition formation problem. However, this problem can be enhanced by some realistic constraints as overlapping groups or by making agents unaware of all the other agents. This work will be used into a decision support system for the remanufacturing and the repurposing of post-used products for the Circular project (ANR-15-IDEX-02). This project focuses on developing the necessary technologies and conditions to make new circular industrial systems able to transform post-used products into new products. In this context, formed groups will represent the new products proposed by the system.