A multi-responsibility–oriented coalition formation framework for dynamic task allocation in mobile

Abstract

In this article, we study a problem of dynamic task allocation with multiple agent responsibilities in distributed multi-agent systems. Agents in the research have two responsibilities, communication and task execution. Movements in agent task execution bring changes to the system network structure, which will affect the communication. Thus, agents need to be autonomous on communication network reconstruction for good performance on task execution. First, we analyze the relationships between the two responsibilities of agents. Then, we design a multi-responsibility–oriented coalition formation framework for dynamic task allocation with two parts, namely, task execution and self-adaptation communication. For the former part, we integrate our formerly proposed algorithm in the framework for task execution coalition formation. For the latter part, we develop a constrained Bayesian overlapping coalition game model to formulate the communication network. A task-allocation efficiency–oriented communication coalition utility function is defined to optimize a coalition structure for the constrained Bayesian overlapping coalition game model. Considering the geographical location dependence between the two responsibilities, we define constrained agent strategies to map agent strategies to potential location choices. Based on the abovementioned design, we propose a distributed location pruning self-adaptive algorithm for the constrained Bayesian overlapping coalition formation. Finally, we test the performance of our framework, multi-responsibility–oriented coalition formation framework, with simulation experiments. Experimental results demonstrate that the multi-responsibility oriented coalition formation framework performs better than the other two distributed algorithms on task completion rate (by over 9.4% and over 65% on average, respectively).

Keywords

Dynamic task allocation multi-responsibility Bayesian overlapping coalition game overlapping coalition game constrained Bayesian coalition game self-adaptation Bayesian equilibrium

Introduction

Nowadays, distributed multi-agent systems (DMASs) are employed in practice growingly for dealing with sundry tasks, for example, disaster rescue,¹ military operations,^2

–5 and distributed sensor networks.⁶ Since tasks in these systems turn to be increasingly complicated (e.g. arising dynamically and demanding on heterogeneous resource), agents generally need to cooperate with others for responding newly emerging tasks. Due to the high description ability of the coalition game theory in cooperation, some researchers have utilized this theory for solving task allocation problems^7

–10 by forming agent coalitions to respond to tasks. Meanwhile, due to the real limitations, social networks are generally adopted for agent communication in practice.^11

–14 A social network allows agents to directly communicate with their neighbors and transmit information out via neighbors.

As shown in Figure 1, agents in this DMAS take two responsibilities, that is, communication and task execution.

Figure 1.

A typical social network in a disaster rescue system. (agents are heterogeneous with respect to resources. t1 and t2 are two newly emerging random tasks.)

However, most established algorithms on task allocation generally focus on task allocation, without considering the communication. Chapman et al.¹ propose an overlapping potential game approximation algorithm (OPGAA) for dynamic rescue allocation, which is a distributed algorithm on dealing with overlapping coalition formation. However, OPGAA does not take resource optimization into account, which leads to insufficient agent utilization. Bin et al.¹⁵ study a problem of multiple task allocation without considering the relationships among tasks. Tomasz et al.⁹ study a dynamic heterogeneous coalition formation problem and propose the centralized greedy coalition formation algorithm (CGCFA). CGCFA is a centralized algorithm for dynamic coalition formation, which focuses on generating an optimal dynamic coalition structure. CGCFA provides an approach to solve the problem of dynamic coalition formation. But it has a center operator knowing information of the entire system to do all the computation, which does not consider the communication limits and is not feasible for DMASs. In our former work,¹⁶ we proposed a mutual-selecting market-based algorithm (MSMA) for heterogeneous coalition formation, which do not consider the impact of the dynamic changes of the communication structure.

In addition, the studies on communication mainly focus on data transmission and spectrum sharing without considering the limitations of communication range and multiple responsibilities.^17
–19 Although agents in those DMASs, such as disaster rescue or military operations, usually need to respond to their multiple tasks, attention has been rarely paid to this issue.

Multiple responsibilities of agents, for example, communication and task execution, usually have mutual impacts on each other. Agents in Figure 1 need to move geographically for responding dynamic tasks, which will change agent geographical locations and the structure of the social network. Evidently, some changes, such as single points in communication networks caused by agent movements, will break an effective network structure of information transmission. That is, those changes will decrease the system performance on communication and task execution. Therefore, a method for agent multiple responsibility in DMASs is urgently needed. The method should enable agents to reconstruct the network and respond to emerging tasks self-adaptively.

Our main contribution in this article is a multi-responsibility–oriented coalition formation framework (MOCFF) for dynamic task allocation with multiple agent responsibilities. The framework is aimed at forming two kinds of coalitions, for communication and task execution, respectively. Our former proposed algorithm, MSMA, is adopted for task coalition formation. So, our work in this article focuses on the framework and self-adaptation communication coalition (CC) reconstruction. The contributions are summarized as follows:

We study two responsibilities of agents in this problem, that is, communication and task execution, based on which we design a MOCFF for solutions.

We analyze the relationship between the two responsibilities. Based on the analysis, we propose a task-responding–oriented utility function to describe the relationship between CCs and task execution coalitions.

We develop a constrained Bayesian overlapping coalition game (CBOCG) model with location constraints to formulate the CC formation problem. Furthermore, a distributed location pruning self-adaptive algorithm (LPSA) is proposed to calculate its solution, which is an equivalence to a Nash equilibrium.^20,21

The rest of this article is organized as below. In the second section, we introduce system assumptions and related preliminaries; then, we present our main work, an integrated self-adaptive framework in the third section. This framework includes two parts of work, that is, self-adaptation CC formation and task execution coalition formation. In the fourth section, we introduce two algorithms, for self-adaptation CC formation and task execution coalition formation, respectively. Then, in the fifth section, we give out the experiment settings, the results and related analysis, compare our work with some established research studies, and make summaries. Finally, some possible future research directions are mentioned in sixth section.

Related preliminaries and system assumptions

In this section, we firstly introduce some related system assumptions and preliminaries of this study. Then, based on those assumptions and definitions, we analyze the relationship between the two agent responsibilities and the relationship between the two kinds of coalitions. Then, we analyze self-adaptation on CC formation and propose related self-adaptation principles; in the end of this section, we propose agent self-adaptation strategies based on analysis and principles proposed above.

System assumptions and definitions

We consider a scenario with N rational agents transmitting information via their CCs. Communication ranges of agents overlap with each other as in Figure 2. Those overlapping agents are utilized as relay stations for information transmission. As illustrated in Figure 2, the CCs of agents 1, 3, and 5 overlap with each other. Agent 1 can transmit information to agent 5 via agent 3.

Figure 2.

Overlapping CCs. CC: communication coalition.

The communication range of an agent, which is mainly decided by its type, is assumed to be a fixed constant in this article. A social network is adopted for agent communication in this DMAS. Here, neighbors of agent a_i are those in its communication range, and the neighbor set of agent a_i forms its neighborhood. Meanwhile, an agent is assumed to obtain a certain number of neighbors due to the limitation on communication capability.^12,13

Firstly, we introduce some formal definitions. In this article, we use notation A to denote an agent set, notation C to denote a coalition, and notation C to denote a set of coalitions.

Definition 1

[Overlapping coalitions] In a set of coalitions C _A on an agent set A, for any two coalitions $C_{i}, C_{j} \in C_{A}$ , if $C_{i} \cap C_{j} \neq \emptyset$ , then C_i overlaps with C_j on some agents. C_i and C_j are defined as overlapping coalitions.

Definition 2

[Overlapping Coalition Game] Let a tuple $G =< A, C_{A}, U, ≻ >$ describe an overlapping coalition game, where some coalitions in $C_{A}$ are overlapping coalitions. And A is a set of agents, $C_{A}$ is a set of all existing coalitions on the agent set A, U is a set of utility functions of coalitions in $C_{A}$ and ≻ is a set of preference describing agents’ preference over coalitions in $C_{A}$ .

Also, we give out a formal definition of neighbor and neighbor set in definition 3.

Definition 3

[Neighbor, Neighbor set] Agents in agent a_i’s communication range are defined as agent a_i’s neighbors. A set of neighbors can be called as agent a_i ’s neighbor set, denoted as $N b_{a_{i}}$ .

Definition 4

[Sub-neighbor, Sub-neighbor set] Agent a_j is defined as agent a_i ’s sub-neighbor if a_j is not a neighbor of a_i but is in the CC of a neighbor of a_j . A set of agent a_i’s sub-neighbors is called its sub-neighbor set.

As shown in Figure 2, the network’s structure is over complicated for problem formulation. Thus, we propose a notion of CC to describe the network structure, which helps to formulate the problem we study and to define its utility function.

Definition 5

[Communication coalition] For agent a_i, its CC is a set of agents, including its neighbor agents and itself. We denote agent a_i ’s CC by $C_{a_{i}}$ , and $C_{a_{i}} = {a_{i}} \cup N b_{a_{i}}$ . Agent a_i is defined as a center agent in its CC.

Here, $C_{a_{i}}$ indicates how many neighbors it has and how many resources its neighbors own. In other word, $C_{a_{i}}$ indicates the total resources it can directly call for a task. Overlapping is allowed in CCs.

Relationship between the two coalitions

Agents obtain information to form task execution coalition via their social network, thus task execution coalition relies on CC. The relationship between the two kinds of coalitions is illustrated in Figure 3.

Figure 3.

Relationship between the two kinds of coalitions.

Executing tasks faster will be beneficial to gaining more system rewards because of the task deadline. That is, a good structure of CCs will help to improve the efficiency of task execution coalition formation. Self-adaptation CC reconstruction requires topological optimization in social networks.

Analysis of topological optimization in social networks

As mentioned above, we adopt a social network for agent communication. Taking agent 3 in Figure 2 for example, the process of information transmission goes like this: when agent 3 receives a task announcement, it transmits the task announcement to its neighbors who, upon receipt, will also transmit such announcements to their neighbors for task coalition formation.

The adopted social network can be regarded as a combination set of agent local social networks. An overlapping CC of a certain agent includes some overlapping nodes, like neighbors or sub-neighbors, which will result in repeated and useless information transmission. Therefore, a good network structure the will help to avoid or alleviate those issues. Here, we will introduce an analysis on topological optimization of local social networks at first.

Agents 3, 5, and 6, as shown in Figure 2, are neighbors with each other, which leads to a closed loop in agent 3’s local social networks. Taking agent 3’s local network as an example, we give out a detailed description of agent 3’s local social network in the tree structure in Figure 4, where arrows indicate the directions in which information flows.

Figure 4.

Tree structure of agent 3’s local social network.

Considering the issues discussed above, an ideal local social network should be capable of transmitting task announcements in a range as wide as possible to form task-executing coalitions in time. That is, expanding the information transmission range of an agent as possible helps to avoid useless and unnecessary announcement transmission. Therefore, the performance of the social network could be improved based on the following considerations.

Local performance: Agents should make their personal decisions to improve their contribution on the global utility in the following three aspects:

To avoid unnecessary information transmission, closed loops should be removed from the topology structure, which means some edges need to be removed.

Meanwhile, to form optimal or suboptimal executing coalitions, task announcements need to be transmitted to agents as many as possible, which is conducive to the optimization for a better solution.

Considering the consumption of time and fuel for agents’ movements to task locations, we only consider three levels of the local social network, including a task announcer (the center agent of this local social network), its neighbors, and sub-neighbors.

Self-adaptive triggers: There are many possibilities for triggering self-adaptive reconstruct of networks. An agent decides to adapt or not based on its performance and local network structure, like agent density in its neighborhood.

Rewiring: How does an agent decide on removing a certain connection, or select an agent to establish a new connection? The utility of a single agent is the main consideration that we take.^16,21

Since “a local Bayesian equilibrium is formally equivalent to a Nash equilibrium of a standard game,”²¹ we utilize the utility of an individual agent to find a local Bayesian equilibrium, which is an equilibrium of our problem.

When its local network self-adapts, an agent has two states, $s_{n} = {Available, No-available}$ , which indicate whether it could be able to rewire its communication network.

Self-adaptation principles and uncertainty in agent strategies

An ideal local social network of an agent should have enough nodes but as few redundant neighbors as possible. Based on the conception of agent density in a neighborhood, we class agent local neighborhood networks into the following three categories that are, sparse local network, reasonable local network, and crowded local network.

Agents that are not in reasonable networks need to adjust their locations for their local social network reconstruction for better information delivery. As on the previous studies,^10,11 a self-adaptive network is an agent interaction topology, which is the result of local rewiring decisions made by individual agents. Based on the analysis above, we propose self-adaptation principles for reorganized networks.

Definition 6: Self-adaptation principles

For a social network topology optimization, any unreasonable local social network should make its self-adaptive decision based on its local network states:

[Sparse local network] An agent in a sparse local network will try to improve its communication in the local network via adding a new neighbor by location change.

[Crowded local network] An agent in a crowded local network will remove repeated nodes or some useless nodes in their neighbor sets or sub-neighbor sets by location change.

Considering the uncertainties, each agent has two choices for self-adaptation, maintaining the current local social network or reconstructing its local social network. Considering the location effect on the network structure, the self-adaptation choices, like leaving a certain CC or staying in a certain CC, mean two choices on its current locations, that is, leaving or staying. Thus, for any agent in the system:

An available agent will stay in the current location when it cannot enhance its utility if it leaves.

An available agent will leave its current location when the local social network utility increases, after leaving for adding a new neighbor or removing a redundant neighbor.

Here, an agent is supposed to add or remove only one neighbor at a time. More specifically, the self-adaptation strategies can be defined as follows:

[Sparse local network] A strategy set of an available agent in a sparse local network, is its sub-neighbor set, in which one sub-neighbor is one strategy, denoting a potential neighbor to add. The agent compute its future optimal locations and its future utility based on those potential neighbors; then the agent chooses a sub-neighbor with the maximum future utility as its new neighbor and moves to the future optimal location; else, if no strategy helps to increase its future utility, it will choose to stay in its current location.

[Crowded local network] A strategy set of an available agent in a crowded local network, is its neighbor set, in which one neighbor is one strategy, denoting a neighbor to remove. The agent computes its future locations and its future utility based on those strategies; then it chooses the neighbor with the maximum future utility that need to be removed and moves to the future location; else, if no strategy helps to increase its future utility, it will choose to stay in its current location.

[Reasonable local network] Agents in reasonable local networks choose to stay in its current location.

Constrained agent strategy

As discussed above, the aim of an agent’s self-adaptation is to keep its local social network reasonable and avoid crowded or sparse networks. Apparently, the self-adaptation strategies of an agent are constrained by its current locations. Here agents are assumed to share information with their neighbors honestly. So, agents can obtain the information of their neighbors and sub-neighbors.

Since the problem is formulated based on the coalition game, to ensure that the calculation converges to a Bayesian equilibrium, we make some rules on agent location self-adaptation.

Rule 1. An agent is supposed to self-adapt in its local social network only when it is available and its local social network is not reasonable.

Rule 2. An agent in a sparse network forms a location self-adaptation strategy set from its sub-neighbor set. That is, a sub-neighbor is a strategy for location self-adaptation.

Rule 3. An agent in a crowded network forms a location self-adaptation strategy set from the neighbor set. That is, a neighbor is a strategy in location self-adaptation.

Rule 1 ensures that the algorithm we proposed for self-adaptation communication formation in “Algorithms in MOCFF” section will converge to a Bayesian equilibrium. The proof is given in the same section. The location self-adaptation calculation process is shown in Figure 5.

Figure 5.

Agent location self-adaptation process.

Freedom and probability calculation

By updating its beliefs about the agents in its CC based on observations, an agent can estimate those agents’ strategies about staying or leaving. Besides, CCs can be overlapped in our problem, which is derived from practices.^22
–24 Although agents make decisions independently, their decisions are mutually affected. To model the uncertainty in CC reconstruction, we use the Bayesian coalition game theory^25

–28 to formulate the problem. Therefore, we could calculate the probabilities over agents’ strategies.

Since agents make decisions simultaneously, they could build an observation to estimate the decisions of other agents. For agent a_i, it will stay in the current location with probability ς. In other words, the probability that an agent leaves its current location will be $1 - ς$ . The probability is related to agent a_i’s historical decisions and its current network states, both of which are mutually independent. Thus, based on the conditional probability theory (here we use notation p to denote a conditional probability function), the probability is calculated as in equation (1)

\begin{array}{l} ς (a_{i}) = p {(Stay}_{a_{i}} {|NetStatus}_{a_{i}}) \\ = \frac{p {(Stay}_{a_{i}}) \cdot p (NetStatus(a_{i} {)|Stay}_{a_{i}})}{\sum_{k} p {(Strategy}_{a_{i}}) \cdot p (NetStatus(a_{i} {)|Strategy}_{a_{i}})} \end{array}

where $p {(Stay}_{a_{i}} {|NetStatus}_{a_{i}})$ is the probability for agent a_i to stay in its current network states, $p {(Stay}_{a_{i}})$ is the observed probability for agent a_i to stay based on its historical decisions. $p ({NetStatus}_{a_{i}})$ is the probability of agent a_i’s freedom in this calculation, a notion to describe agents’ freedom on its strategies. Freedom is defined as follows.

Definition 7

[Freedom] A freedom degree of an agent is a ratio about its neighbor number against the upper limit of neighbors. It is denoted as equation (2)

p ({NetStatus}_{a_{i}}) = 1 - \frac{| N b_{a_{i}} |}{upper (N b_{a_{i}})}

where $| N b_{a_{i}} |$ is the number of agent a_i’s neighbors, and $upper (N b_{a_{i}})$ is the upper limit of the number of agent a_j’s neighbors.¹³

Based on the Bayesian equilibrium definition,²³ the more neighbors a_i obtains, the lower possibility that it could leave. An agent is totally free to make any decision on location change when it has no neighbors.

For agent a_i, we define a set of staying and leaving acknowledgements as $L_{i} = {l_{l_{i}}, l_{s_{i}}}$ . Also, we define a set of observation of staying and leaving acknowledgements as $O_{i} = {o_{l_{i}}, o_{s_{i}}}$ . Since agents are honest, the observation of agent a_i remains the same regardless of the observers.

Besides, a Bayesian equilibrium is also a Nash equilibrium,^22,23 thus a Nash-stable coalitional structure is an equivalent solution to a Bayesian equilibrium.²⁰

Definition 8

A coalitional structure $C S = {{C}_{1}, ..., C_{l}, ... C_{j}}$ is Nash-stable if $\forall a_{i} \in C S, C_{l}^{a_{i}} ≻_{a_{i}} C_{k} \cup {a_{i}}$ for all $C_{k} \in C S \ C_{l}^{a_{i}} \cup {ϕ}$ .¹⁶

Based on definition 8, if a coalition structure (i.e. a set of coalitions) is stable, then it can be obtained that:

No agent a_i has an incentive to leave the current coalition $C_{l}^{a_{i}}$ and act alone (i.e. $C_{l}^{a_{i}} ≻_{a_{i}} {a_{i}}$ ), which implies that no agent believes that it will be better off by acting alone;

Given an agent’s beliefs about the others, no agent will have an incentive to leave from the current coalition $C_{l}^{a_{i}}$ for any others that make the total utility decrease (here we assume that the other coalitions do not change). That implies no agent believes that it will be better off by joining (leaving) the new (current) coalition when making its coalition members worse off.

An integrated framework for dynamic task allocation

In this section, we firstly introduce an integrated framework for dynamic task allocation under multiple agent responsibilities. This framework is deigned to cope with two responsibilities by forming two kinds of coalitions, that is, CCs and task execution coalitions.

Then, we introduce our CBOCG model for CC formation. Considering agents’ obligations and cost, we define a utility function for an overlapping CC, which helps to cast our issue into a problem for an optimal utility calculation. After that, we give out the belief update calculation. In the end of this section, we introduce a formerly proposed algorithm for task allocation,¹⁶ which is integrated in this framework for task execution coalition formation.

A multi-responsibility–oriented coalition formation framework

Agents need to form two kinds of coalitions to deal with two responsibilities. Here, agents are assumed to have different states regards to different kinds of coalitions respectively. For task execution, agents have three states ${Idle,Waiting, Busy}$ . For CC, agents have two states in self-adaptation, ${Available, Unavailable}$ .

Considering the system reward, task execution has higher priority. That is, at each time step, idle agents will check whether they receive task coalition announcements at first. When agents receive no task coalition information and remain idle, they are granted to self-adapt in this step. The agent state transition is shown in Figure 6.

Figure 6.

Agent state transition.

Based on agent state transition, we designed a MOCFF, as shown in Figure 7.

Figure 7.

The framework of a multi-responsibility–oriented coalition formation.

As illustrated in Figure 7, the two kinds of coalitions, CC and task execution coalition, respond to the two responsibilities, respectively. Agents update their states for multi-responsibility–oriented coalition formation via our two proposed algorithms.

Task execution coalition formation

In this article, we use a distributed task allocation algorithm proposed by Bing et al.,¹⁶ the MSMA, for dynamic coalition formation. MSMA is designed on market-based methods and utilizes auction methods to realize the optimization. The process of MSMA is shown in Figure 8. (Any interested readers can refer to our previous work¹⁶ for details).

Figure 8.

The Process of MSMA. MSMA: mutual-selecting market–based algorithm

CC formation

For CC formation, we consider a social network consisting of N agents, and the set of those N agents is denoted by $A = {a_{1}, ..., a_{n}}$ . Different from the Bayesian overlapping coalition game by Yong and Chen,²⁹ location constraints and strategy constraints exist in our problem, which are not considered in aforementioned study.²⁹ Therefore, we propose a CBOCG to formulate the problem we study. A CBOCG is defined as equation 3

G = < A, C_{A}, S, L, O, p, {({\bar{u}}_{i})}_{i \in A}, {(≻_{i})}_{i \in A} >

Agents. The set A consists of N rational agents, which is denoted by $A = {a_{1}, ..., a_{n}}$ .

Coalitions. The set $C_{A}$ , a set of existing coalitions on agent set A, is denoted by $C_{A} = {C_{1}, ..., C_{m}}, m \leq 2^{| A |}$ ; for any $C_{i} \in C_{A}$ , $C_{i} \subseteq A$ , there exists $\exists C_{i}, C_{j} \in C_{A}$ that $C_{i} \cap C_{j} \neq \emptyset$ , where ∅ is an empty set. That is, $\exists C_{i}, C_{j} \in C_{A}$ , $C_{i}$ , and $C_{j}$ overlap on some agents.

Constrained strategy. The strategy space can be denoted by $S = S_{1} \times \cdot \cdot \cdot \times S_{N}$ , where $S_{i} = {s_{l_{i}}, s_{s_{i}}}$ denotes an agent a_i’s strategy set. $s_{l_{i}}$ , $s_{s_{i}}$ are strategy vectors describing an agent a_i’s decisions on coalitions. Here, $s_{l_{i}}$ and $s_{s_{i}}$ are vectors consisted of Bool items (each item represents an agent whether in one certain coalition or not). Here, we define a set of constrained location choice (CLC) to map constrained strategies to agent potential locations. The CLC set is denoted as $L = {L_{1}, ..., L_{N}}$ . $L_{i} = {l_{l_{i}}, l_{s_{i}}}$ represents agent a_i’s choices on its current location, where $l_{s_{i}}$ indicates that agent a_i stays in its current location and $l_{l_{i}}$ indicates that agent a_i leaves its current location.

Observation. The observation space is denoted as $O = {O_{1}, ..., O_{N}}$ . $O_{i j} = {o_{l_{j}}, o_{s_{j}}}$ is agent a_i’s observation about historical decisions of agent a_j, where $o_{l_{j}}$ implies agent a_j leaves its location, $o_{s_{j}}$ implies agent a_j stays. The observation is utilized to update agent a_i’s belief on agent a_j’s future decisions.

Probability distribution. p is a common a priori probability over the CLC set L . Here, we set $P_{j}^{i} (l_{l_{j}}) = {p^{'}}_{i j}$ and $P_{j}^{i} (l_{s_{i}}) = 1 - {p^{'}}_{i j}$ to denote an agent a_i’s belief about the leaving choice $l_{l_{j}}$ and the staying choice $l_{s_{j}}$ of agent a_j, respectively.

Payoff. ${({\overline{p f}}_{i})}_{i \in A}$ is defined as an expected payoff of agent a_i. Given agent a_i’s beliefs about the CLC of those agents in CCs, it attempts to join/leave, and ${({\overline{p f}}_{i})}_{i \in A}$ is the difference between an expected utility and an expected cost. For agent $a_{i} \in A$ , its expected utility is calculated on its strategies and beliefs about related agents. With a discrete CLC space, the expected payoff of agent a_i can be defined as follows

\begin{array}{l} {\bar{p f}}_{a_{i}} (L_{s_{j}}, s_{j})= \sum (u_{a_{i}} (L_{s_{j}}, s_{j}) - {cost}_{a_{i}} (L_{s_{j}}, s_{j})) \\ = \sum ς_{i j}^{'} (L_{s_{j}}) (u_{a_{i}} (L_{s_{j}}, s_{j}) - {cost}_{a_{i}} (L_{s_{j}}, s_{j})) \end{array}

where $u_{a_{i}}$ and ${cost}_{a_{i}}$ denote, respectively, the utility and the cost of agent a_i when it chooses strategy s_j. $ς_{i j}^{'} (L_{s_{j}})$ is agent a_i’s estimated probability vector about agent a_j’s leaving decision $l_{l_{j}}$ and staying decision $l_{s_{j}}$ . ${ς^{'}}_{i j}^{} (L_{s_{j}}) = {ς^{'}}_{i j}^{} (l_{l_{j}}, l_{s_{j}})$ could be updated by agent a_i’s observation and its belief on agent a_j. The functions of $u_{a_{i}}$ and ${cost}_{a_{i}}$ will be given in detail in the rest of this article.

Preference. $≻_{i}$ describes agent a_i’s preference. For instance, $s_{k} ≻_{a_{i}} s_{j}$ means, agent a_i prefers to adopt strategy s_k than strategy s_j . The preference order is decided by the expected payoff that agent a_i believes it can receive when a certain strategy is adopted. A strategy is preferred when it brings a greater expected payoff.

In addition, we use a tuple to represent an agent, so that the problem can be described more specifically. For agent $a_{i} \in A$ , we describe agent a_i as a tuple $a_{i} = < l_{a_{i}}, s t_{a_{i}}, N b_{a_{i}} >$ . Detailed description is given as follows.

$l_{a_{i}}$ is agent a_i’s location, which will change when a_i moves to execute assigned tasks.

$s t_{a_{i}}$ is agent a_i’s states, including task-states $s t_{t}$ and network-states $s t_{n}$ , denoted by $s t_{a_{i}} = < s t_{a_{i}}_{t}, s t_{a_{i}}_{n} >$ . $s t_{a_{i}}_{t}$ is agent a_i’s task states denoted by $s t_{a_{i}}_{t} = {Busy, Waiting, Idle}$ . $s t_{a_{i}}_{n}$ is agent a_i’s network states, denoted by $s t_{a_{i}}_{n} = {Available, No-available}$ .

$N b_{a_{i}}$ is agent a_i’s neighbor set.

In the rest of this article, we use the tuple to describe agents.

A solution of a CBOCG

A solution of CBOCG is to find its Bayesian equilibrium, which is also a Nash equilibrium of a dynamic game.²⁵ Given the beliefs about the types of and strategies played by other agents, a Bayesian equilibrium is defined as a strategy profile that maximizes the expected payoff for each agent.

Based on the definition of the Bayesian equilibrium, the strategy each agent adopts should be aimed at optimizing its utility.²⁵ Thus, each agent in the CBOCG should make its strategy to seek its optimal payoff. In other words, for any agent $a_{i} \in A$ , it will adopt the strategy with the maximum payoff at any time step.

In the following part, we will give out functions on a coalition utility and cost, based on which we will define a payoff function.

A coalition payoff function definition

A coalition payoff function can be defined as $u : 2^{| A |} \to ℝ$ that assigns a value to every possible coalition. A payoff function $p f (C_{i})$ decides a given coalition $C_{i}$ ’s payoff via the total amount of the coalition resource and resource excess, which is also constrained by the time and fuel consumed on the way to task locations. Therefore, how a task coalition constructed and when the task will be processed will both impact the payoff of the corresponding executing coalition.

Resource excess or resource insufficiency cause low an agent utilization rate. Also, for a certain task, the earlier it gets processed, the more effective the system will be. In a CC, agents generally have two obligations: first, they need to transmit task announcements for forming task coalitions; second, agents need to execute tasks with others in a coalition form. Thus, how many resources are possessed by an agent and its CC, and how many outer-agents of CC members can respond the CC’s task announcement directly impact whether a qualified task coalition can be formed to execute the task in time or not.

Based on those considerations, we define that the payoff of an agent’s CC consists of three parts: the CC’s resource utility, transmission utility, and the self-adaptation cost. A CC’s resource utility depends on how many resources it possesses. The transmitting ability can be defined as an ability of how many outer-coalition resources a CC can directly transmit task announcements to, which indicates how many resources that the CC can call for task execution in time.

Thus, we can give a payoff function of $C_{a_{i}}$ , agent a_i’s CC, as in equation (5)

p f (C_{a_{i}}) = u_{r} (C_{a_{i}}) + u_{t} (C_{a_{i}}) - cost (C_{a_{i}})

where u_r is $C_{a_{i}}$ ’s resource utility, u_t is $C_{a_{i}}$ ’s transmission utility and $cost (C_{a_{i}})$ is the self-adaptation cost of $C_{a_{i}}$ . Specifically, u_r indicates what and how many resources $C_{a_{i}}$ possesses, u_t indicates what kind of resources the neighbor set of $C_{a_{i}}$ possesses.

Resource utility and transmission utility

For resource utility $u_{r} (C_{a_{i}})$ , it can be defined as equation (6)

u_{r} (C_{a_{i}}) = \sum_{a_{j \in} C_{a_{i}}} u_{r} (a_{j})

where $u_{r} (a_{_{j}}) = ω \cdot r (a_{_{j}})$ is agent a_j’s resource utility. Here, ω is a weight vector of resources. $r (a_{j})$ is an amount vector that describes how many resources agent a_j possesses, with one item representing an amount of a certain resource it possesses.

The transmission utility $u_{t} (C_{a_{i}})$ is represented by the total resources which $C_{a_{i}}$ ’s neighbor set possesses, which describes the resources that $C_{a_{i}}$ can access. $u_{t} (C_{a_{i}})$ is defined as equation (7)

u_{t} (C_{a_{i}}) = \sum_{a_{j} \in C_{a_{i}}} u_{r} (a_{j}) + \sum_{a_{z} \in S N_{a_{i}}} u_{r} (a_{z})

Thereafter, the utility of $C_{a_{i}}$ can be redefined as equation (8)

\begin{array}{l} u (C_{a_{i}}) = \sum_{a_{i} \in C_{a_{i}}} u (a_{i}) \\ = \sum_{a_{i} \in C_{a_{i}}} u_{r} (a_{i}) + \sum_{a_{i} \in C_{a_{i}}} u_{t} (a_{i}) \\ = \sum_{a_{i} \in C_{a_{i}}} u_{r} (a_{i}) + \sum_{a_{z} \in S N_{C_{a_{i}}}} u_{r} (a_{z}) \end{array}

where $S N_{a_{i}}$ is $C_{a_{i}}$ ’s sub-neighbor set and $S N_{a_{i}} = \underset{a_{j} \in C_{a_{i}}}{\cup} S N_{a_{j}}$ . Here, $S N_{a_{i}}$ excludes all overlapped agents.

Cost

The topological reconstruction of a local social network comes with cost, which can be expressed as a function. Since there is no resource consumption, a CC’s resource utility would not change. So, the cost of an agent’s self-adaptation is mainly decided by its movement. Specifically, the location change of an agent brings cost on its movement, that is, time cost. Thus, we can define a cost function as equation (9)

cost (C_{a_{i}}) = {cost}_{m} (a_{i})

where ${cost}_{m} (a_{i})$ is agent a_i’s movement. The cost can be represented as equation (10)

{cost}_{m} (a_{i}) = \frac{dis (a_{i}, a_{j})}{{speed}_{a_{i}}}

where $dis(a_{i}, a_{j})$ is the distance between agent a_i and a_j, and ${speed}_{a_{i}}$ is the speed of agent a_i. Although equation (10) is a simple function, it still reflects the relation between cost and distance, which is that cost increases with distance. Thus, it is employed for simplification but with generalization.

Considering all the cost above, $C_{a_{i}}$ ’s payoff function can be modified as

\begin{array}{l} p f (C_{a_{i}}) = u_{r} (C_{a_{i}}) + u_{t} (C_{a_{i}}) - cost (C_{a_{i}}) \\ = \sum_{a_{i} \in C_{a_{i}}} u_{r} (a_{i}) + \sum_{a_{z} \in S N_{C_{a_{i}}}} u_{r} (a_{z}) - {cost}_{m} (a_{i}) \end{array}

Based on the CC utility function, we design an agent strategy-making model.

Belief Update

In a CBOCG, each agent holds beliefs about other agents’ decisions. For agent a_i, it calculates its best reply based on those beliefs on other agents’ potential strategies. Due to dynamics of the DMAS, agents need to update the beliefs about their neighbors via related acknowledgments and observations.

Under our assumption, each agent could build their observations about its neighbors and sub-neighbors, which will help to update corresponding beliefs for more accurate utility computation.

Let $o_{i j} (L_{j} = l_{s_{j}})$ denote the event that agent a_i observes a staying acknowledge $l_{s_{j}}$ of agent a_j, implying that a_i knows that agent a_j stays in its locations. $o_{i j} (L_{j} = l_{l_{j}})$ denotes the event that agent a_i observes a leaving acknowledge $l_{l_{j}}$ , implying that a_i knows agent a_j leaves.

Given an observation $o_{i j} (L_{j} = l_{s_{j}}) = p_{i j}^{τ} (L_{j} = l_{s_{j}})$ at the $τ_{i j}$ time of observation, where $τ_{i j} > 0$ , agent a_i can update the estimated probability for agent a_j’s decisions according to the Bayes’ theorem as shown in equations (12) and (13).

\begin{array}{l} ς_{i j}^{τ + 1} (L_{j} = l_{s_{j}} |NetStatus (a_{i})|) \\ = \frac{p_{i j}^{τ} (L_{j} = l_{s_{j}}) \cdot p_{i j}^{τ} (NetStatus (a_{i}) | L_{j} = l_{s_{j}})}{\sum_{k} p_{i j}^{τ} (L_{j}) \cdot p_{i j}^{τ} (NetStatus (a_{i}) | L_{j})} \end{array}

\begin{array}{l} ς_{i j}^{τ + 1} (L_{j} = l_{l_{j}}) = 1 - ς_{i j}^{τ + 1} (L_{j} = l_{s_{j}}) \\ =1 - \frac{p_{i j}^{τ} (L_{j} = l_{s_{j}}) \cdot p_{i j}^{τ} (NetStatus (a_{i}) | L_{j} = l_{s_{j}})}{\sum_{k} p_{i j}^{τ} (L_{j}) \cdot p_{i j}^{τ} (NetStatus (a_{i}) | L_{j})} \end{array}

where $p_{i j}^{τ} (L_{j} = l_{s_{j}})$ is agent a_j’s staying probability observed by agent a_i, and $p_{i j}^{τ} (NetStatus (a_{i}) | L_{j} = l_{s_{j}})$ is agent a_j’s freedom observed by agent a_i when agent a_j takes strategy $l_{s_{j}}$ . $p_{i j}^{τ} (L_{j})$ is agent a_j’s strategy distribution observed by agent a_i, $p_{i j}^{τ} (NetStatus (a_{i}) | L_{j})$ is agent a_j’s freedom of $NetStatus(a_{i})$ observed by agent a_i.

Algorithms in MOCFF

In this section, we will introduce two distributed algorithms adopted in the MOCFF. One is the MSMA for task execution coalition formation; the other is the LPSA for self-adaptive CC formation.

First, we will give a brief introduction of MSMA. Then, we will introduce the LPSA and prove that its result converges to a Nash-stable coalition structure. At the end of this section, the working process of MOCFF will be presented in detail.

MSMA for task execution formation

As introduced in “An integrated framework for dynamic task allocation” section, the MSMA is designed for task execution coalition formation. The detailed process of the MSMA is given by Bing et al.¹⁶

LPSA for CC formation

Here, we design the LPSA based on agents’ strict preferences and constraints on locations, as presented in definition 5, to find a solution of the CBOCG.

Algorithm 2 works in the following steps: first, at time step τ, each agent updates its current CC and sub-neighbor set; then, each available agent for self-adaptation forms a strategy space based on its network states; after that, each available agent estimates the probabilities of potential strategies and computes the corresponding expected payoffs. If the utility of strategy $s_{_{a_{i}}}^{l}$ is higher when compared to agent a_i’s current neighbor coalition, agent a_i adds strategy $s_{_{a_{i}}}^{l}$ to its possible strategies. After finding all possible strategies, agent a_i chooses a strategy with the maximum utility increase and moves to the optimal location to form a new CC. Otherwise, agent a_i will stay in the current CC.

Algorithm 2.

Distributed location pruning self-adaptive algorithm at time step τ

For each agent $a_{i} \in A$ , it computes its CC and sub-neighbors set

If $a_{i} \in A$ is idle

a_i forms its strategy space

For each strategy $s_{a_{i}} \in S_{a_{i}}$ , agent a_i compute its optimal location and expected payoff ${({\bar{u}}_{i})}_{s_{a_{i}} \in S}$ .

a_i forms its possible strategies from ${({\bar{u}}_{i})}_{s_{_{a_{i}}}^{l} \in S}$ when ${({\bar{u}}_{i})}_{s_{_{a_{i}}}^{l} \in S} > u_{i}$

Agent a_i choose strategy ${s^{*}}_{_{a_{i}}}^{l}$ , which brings the maximum ${({\bar{u}}_{i})}_{s_{_{a_{i}}}^{l} \in S}$ among its strategy space, moves to the related optimal location and forms a new CC.

If $\exists {({\bar{u}}_{i})}_{s_{_{a_{i}}}^{l} \in S}$ such that ${({\bar{u}}_{i})}_{s_{_{a_{i}}}^{l} \in S} > u_{i}$

Then agent a_i stay in its current location

End If

End For

End

Next, we will consider whether any coalition structure obtained from algorithm 2 is Nash-stable.

Theorem 1

Algorithm 2 will converge to a Nash-stable coalitional structure.

Proof

According to definition 8 about the Nash-stable coalitional structure, any agent could be able to move to another coalition only when none in the new coalition is worse off (i.e. the agents believe that they will not be worse off in terms of expected payoff after the one joins). Based on a CC’s payoff in equation (5), a new agent’s join will always bring increase to the payoff of a coalition.

Starting with any coalition structure CS, we suppose that algorithm 2 will not converge to a Nash-stable coalition structure. In other words, for $\exists a_{i} \in A$ , $\exists C_{_{l}}^{a_{i}} \in C S$ satisfies $C_{l}^{a_{i}} ≻_{a_{i}} C_{k} \cup {a_{i}}$ for all $C_{k} \in C S \ C_{l}^{a_{i}} \cup {ϕ}$ . Then the current coalition structure is not Nash-stable. Consequently, the current coalition structure will change into a new one after agents move to new coalitions. Since there can be $2^{N} - 1$ overlapping coalitions, this implies that there are at maximum $2^{N} - 1$ coalitions, including an empty coalition for each agent to possibly join.

Base on algorithm 2, agent a_i finds a new coalition to join, which means that it finds a new coalition satisfying ${({\overline{u}}_{i})}_{s_{_{a_{i}}}^{l} \in S} > u_{i}$ . That is, for all $C_{k} \in C S \ C_{l}^{a_{i}} \cup {ϕ}$ , $\exists C_{k} \in C S$ satisfies that $C_{k} \cup {a_{i}} ≻_{a_{i}} C_{l}^{a_{i}}$ until agent a_i cannot find a nonempty coalition to join. Agent a_i then stays in its current coalition. Note that the number of coalitions of which each agent can be a member is finite. The algorithm will converge to a Nash-stable coalition structure $C S *$ .

The process of MOCFF

The working process of MOCFF is shown in Figure 9.

Figure 9.

The process of MOCFF. MOCFF: multi-responsibility–oriented coalition formation framework; CC: communication coalition.

Task execution is prior to communication self-adaptation; therefore, idle agents are available for self-adaptation in CC only when it has not received any offer for task execution coalitions.

Result analysis

In this section, we will test MOCFF in a dynamic task allocation problem. In the same simulation experiments, this mechanism will be compared with three established algorithms, namely, MSMA, OPGAA, and CGCFA. Here, CGCFA is utilized as a measure on the rationality of simulation data.

Firstly, we will introduce the settings of our simulation experiments; then, three performance measures will be defined for algorithm performance evaluation. Finally, we will set two groups of experiments for the algorithm performance comparison and analyze the results.

Simulation settings

For simplification, we assume that each agent possesses two kinds of resources and the quantity of resources it carries varies randomly. Tasks are assumed to have different requirements on resources and their locations are generated randomly.

When dynamic heterogeneous tasks are allocated, task requirements usually could not be satisfied exactly due to agents’ heterogeneity and distribution. Therefore, the total resources that a coalition possesses for a task might be beyond the task’s requirement, which will impact the task completion rate (TCR) directly.

For comprehensive performance comparison under different settings, we set two groups of experiments. To achieve statistical significance, each group will be set with a series of scenarios. Each scenario will be run 10 times with different task flow simulations.

Experiments group 1 is designed to compare the performance of the four algorithms. Here, we set three scenarios, 1-1, 1-2, and 1-3, in group 1. The detailed settings in group 1 are given in Table 1.

Table 1.

Simulation settings in group 1.

Parameter	Value
Number of agents	Scenario 1-1	100
	Scenario 1-2
	Scenario 1-3
Number of tasks	Scenario 1-1	40
	Scenario 1-2	50
	Scenario 1-3	60
Number of resource types	2
Ranges of agent resource	Resource 1	(0, 6]
Ranges of agent resource	Resource 2	(0, 6]
Ranges of task resource	Resource 1	(0, 20]
Ranges of task resource	Resource 2	(0, 20]

Group 2 is designed to identify improvements in MOCFF when compared to MSMA. Firstly, we propose a parameter, task density, to help analyze the results. The definition is given as follows

d_{t} = \frac{| N_{t} |}{t_{total} \cdot | N_{a} |}

where $| N_{t} |$ is the number of tasks, $t_{total}$ is the total time, and $| N_{a} |$ is the total number of agents in the settings.

For detailed comparisons under different settings, that is, task reduction and total time, we divide group 2 into two subgroups, 2-1 and 2-2.

Here, we set 9 scenarios in subgroups 2-1 and 2-2 respectively. The settings of subgroup 2-1 are listed in Table 2, including scenarios 2-1 to 2-9.

Table 2.

Settings in simulation subgroup 2-1.

Scenario	Total time	Number of tasks	Number of agents	d_t
Scenario 2-1	100	40	100	0.004
Scenario 2-2			70	0.0057
Scenario 2-3			50	0.008
Scenario 2-4		50	100	0.005
Scenario 2-5			70	0.0071
Scenario 2-6			50	0.01
Scenario 2-7		60	100	0.006
Scenario 2-8			70	0.0086
Scenario 2-9			50	0.012

The settings of group 2-2 are listed in Table 3, including scenarios 3-1 to 3-9.

Table 3.

Settings in simulation subgroup 2-2.

Scenario	Number of agents	Number of tasks	Total time	d_t
Scenario 3-1	100	40	100	0.004
Scenario 3-2			150	0.0027
Scenario 3-3			200	0.002
Scenario 3-4		50	100	0.005
Scenario 3-5			150	0.0033
Scenario 3-6			200	0.0025
Scenario 3-7		60	100	0.006
Scenario3-8		60	150	0.004

For each scenario, we generate and run 10 random groups of task data for the statistical analysis of results. In our simulation experiments, tasks are generated randomly with each resource requirement $r_{t_{i}} \in (1, 20]$ and task handling duration $τ_{t_{i}} \in (1, 20]$ . The locations of all the tasks are randomly generated within the task area.

Performance evaluation

We adopt three standard measurements, M1, M2, and TCR, to review the performances of these four algorithms. The results are analyzed with respect to three performance measures:

M1: The number of completed tasks;

M2: The number of non-responded tasks, which include the tasks that have no idle agent to announce coalition formation demands, and the tasks that announce their requirements but get no responding coalitions;

TCR: It can be obtained by dividing the number of completed tasks by the total number of emerging tasks during the experiment.

Here, we give the definition of TCR as in equation (15)

R_{t c} = \frac{N_{c}}{N_{t}}

where N_t is the total number of tasks during calculation, and N_c is the number of tasks completed during the same period.

Result analysis

In this section, we will present the performance comparisons in the two groups of experiments, respectively. Firstly, in scenarios with sufficient agents, we will compare the performance of the four coalition formation algorithms and give out relative analysis. Then, we will present performance comparisons of MSMA and MOCFF in scenarios with resource shortages.

Comparison of four algorithms

Here, we give out the results of the experiments in group 1. The performances of the four methods (CGCFA, OPGAA, MSMA, and MOCFF) are compared in the TCR. The results of comparisons are shown in Figure 10.

Figure 10.

TCR comparison: Comparison of TCR in scenarios 1-1, 1-2, and 1-3. TCR: task completion rate.

Figure 10 shows a comparison of TCRs of the four algorithms, where blue, green, and red indicate scenarios 1-1, 1-2, and 1-3, respectively. From this figure, we can see that our algorithm helps to improve the performance of task response, especially when agents are insufficient. MOCFF performs better than the other two distributed algorithms, that is, MSMA and OPGAA.

The results on M1, M2, and TCR of the three distributed algorithms (OPGAA, MSMA, and MOCFF) are presented in Table 4.

Table 4.

Results in simulation experiments.

Scenario 1-1
Parameter	OPGAA	MSMA	MOCFF
M1	17.4	23.9	25.6
M2	22.6	16.1	14.4
TCR	0.435	0.5975	0.64
Scenario 1-2
Parameter	OPGAA	MSMA	MOCFF
M1	16.1	25.6	28.2
M2	33.9	24.4	21.8
TCR	0.322	0.512	0.564
Scenario 1-3
Parameter	OPGAA	MSMA	MOCFF
M1	17.2	27.9	31.1
M2	42.8	32.1	28.9
TCR	0.2867	0.465	0.5183

TCR: task completion rate; MSMA: mutual-selecting market-based algorithm; MOCFF: multi-responsibility oriented coalition formation framework; OPGAA: overlapping potential game approximation algorithm.

In Table 4, M1 and M2 are statistical mean values of the total experiments in scenarios 1-1, 1-2, and 1-3 respectively.

As presented above, MOCFF performs better on average than the other two distributed algorithms, OPGAA and MSMA, in all the three scenarios. It illustrates that MOCFF helps to improve the practical efficiency of coalition formation through more efficient communication. Specifically, MOCFF performs increasingly better as agents get reduced in number, with improvement rate of 7.11% in scenario 1, 10.15% in scenario 2, and 11.46% in scenario 3, respectively, compared to MSMA.

Comparison between MOCFF and MSMA

In this section, we give out the results of experiments in group 2. The performances of the two algorithms (MSMA and MOCFF) are compared with respect to the TCR.

Firstly, we test the performance of MOCFF and MSMA in experiments of group 2-1, that is, scenarios of task reduction. The results of comparisons are shown in Figure 11.

Figure 11.

Comparison of tasks completion rate with MSMA and MOCFF in 100 time units. (a) TCR in scenarios 2-1, 2-2, and 2-3 with 40 tasks; (b) TCR in scenarios 2-4, 2-5, and 2-6 with 50 tasks; (c) TCR in scenarios 2-7, 2-8, and 2-9 with 60 tasks. MSMA: mutual-selecting market–based algorithm; MOCFF: multi-responsibility–oriented coalition formation framework; TCR: task completion rate.

Figure 11 presents a comparison of scenarios involving 40, 50, and 60 tasks, respectively, within 100 time units. Figure 11(a) illustrates the comparison among scenario 2-1, 2-2, and 2-3, Figure 11(b) illustrates the comparison among scenario 2-4, 2-5, and 2-6, and Figure 11(c) illustrates the comparison among scenarios 2-7, 2-8, and 2-9.

As seen directly from Figure 11, MOCFF performs better than MSMA in each scenario of group 2-1, no matter agents are sufficient or not. When the number of tasks decreases, the total requirement of all tasks declines, therefore the two algorithms perform better. When the number of agents decrease under certain number of tasks, the growth rate of TCRs in MOCFF increases, compared to that of MSMA. This means, our self-adaptation mechanism works more efficiently when agents are insufficient. Also, as shown in Figure 11, under the same $d_{t t d}$ , sufficient agents can help the algorithms work more efficiently. When comparing the TCR of MOCFF and when the number of agents keeps constant, we can see that MOCFF performs better when d_t gets smaller.

Then, we test the performance of MOCFF and MSMA in experiments of group 2-2, that is, scenarios with different total time. The results of comparisons are shown in Figure 12.

Figure 12.

TCR comparison with MSMA and MOCFF with 100 agents. (a) TCR in scenarios 3-1, 3-2, and 3-3 with 40 tasks; (b) TCR in scenarios 3-4, 3-5, and 3-6 with 50 tasks; (c) TCR in scenarios 3-7, 3-8, and 3-9 with 60 tasks. MSMA: mutual-selecting market-based algorithm; MOCFF: multi-responsibility–oriented coalition formation framework; TCR: task completion rate.

As seen in Figure 12, MOCFF performs better than MSMA in each scenario of group 2-2 as well. Although when agents and the number of tasks remain the same, the total time apparently has little impact on the performance of the two algorithms, respectively.

When agents remain the same in number, the influence of d_t on the performance of MOCFF is not obvious compared with that on MSMA. Thus, we draw a data chart about the potential of TCR about d_t in all scenarios from 2-1 to 3-9, as shown in Figure 13.

Figure 13.

Comparison of the MSMA tasks completion rate with MSMA and MOCFF with 100 agents. MSMA: mutual-selecting market-based algorithm; MOCFF: multi-responsibility–oriented coalition formation framework.

In Figure 13, we arrange d_t in ascending order in the chart and use the data about the corresponding TCR. The TCP trend descends along with the ascending d_t in general, which indicates that d_t has impact on the performance of MOCFF. In other word, the number of agents, the number of tasks, and the total time of tasks influence the effect of our self-adaptive mechanism due to the time cost required by the self-adaptive mechanism. Also, Figures 8 and 9 show us that the performance of MOCFF relies on the structure of the original communication network.

Concluding remarks

This article presents an MOCFF for dynamic task allocation. In the proposed self-adaptive framework, two agent responsibilities are identified, that is, communication and task execution. Thus, the framework is designed to form two kinds of coalitions to fulfill the two responsibilities. The two algorithms, LPSA and MSMA, are proposed in the framework to address two kinds of coalition formation.

Our formerly proposed algorithm, MSMA, is integrated for forming task execution coalitions. The self-adaptive mechanism enables the social network to achieve better task information announcements. With the self-adaptation CC formation algorithm, the framework works more efficiently on dynamic task allocation. The results of experiments show that, compared to other methods, such as OPGAA and CGCFA, our framework works more efficiently on the optimization of coalition formation.

Additionally, for the proposed CBOCG model, we intend to further study its features and more equilibriums. We also find the problem studied here is a complex network problem.³⁰ Thus, in the future work, we plan to formulate this problem based on the complex networks theory, which helps to analyze the unknown topological structure of a dynamical network for a better solution. Besides, we do not consider the impact of the task execution procedure on CC procedure in this work, which is also a valuable research subject in the future.

Footnotes

Acknowledgements

The authors are grateful for helpful comments by the editor and the anonymous referees for their suggestions and comments which have resulted useful for improving the article.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Bing Xie

References

Chapman

Micillo

Kota

. Decentralised dynamic task allocation: a practical game: theoretic approach. In: International joint conference on autonomous agents & multiagent systems, 2009; 2: 915–922.

Han-Lim

Brunet

How

. Consensus-based decentralized auctions for robust task allocation. IEEE Trans Robot 2009; 25(4): 912–926.

Whitten

Choi

Johnso

. Decentralized task allocation with coupled constraints in complex missions. In: Proceedings of the 2011 American control conference, San Francisco, CA, USA, 29 June–01 July 2011:1642–1649.

Ponda

Redding

Choi

. Decentralized planning for complex missions with dynamic communication constraints. In: Proceedings of the 2011 American control conference, Baltimore, MD, USA, 30 June–2 July 2010, 58(8): 3998–4003.

Choi

Whitten

How

. Decentralized task allocation for heterogeneous teams with cooperation constraints. In: Proceedings of the 2011 American control conference, Baltimore, MD, USA, 30 June–2 July 2010; 58(8): 3057–3062.

Dayong

Zhang

. Self-adaptation-based dynamic coalition formation in a distributed agent network: a mechanism and a brief survey. IEEE Trans Parallel Distrib Systt 2013; 24(5): 1042–1051.

Onn

Kraus

. Methods for task allocation via agent coalition formation. Artif Intell 1998; 101(1–2): 165–200.

Matthias

Gerber

. Dynamic coalition formation among rational agents. Intell Syst IEEE. 2002; 17(3): 42–47.

Tomasz

Sroka

Rahwan

. A distributed algorithm for anytime coalition structure generation. In: International conference on autonomous agents & multiagent systems, 2010; 1: 1007–1014.

10.

Haluk

Bozma

. Coalition formation games for dynamic multirobot tasks. Int J Robot Res 2015; 107: 37–54.

11.

Jeremy

Ramirez-Cano

Draief

. Interleaving multi-agent systems and social networks for organized adaptation. Comput Math Organ Theory 2011; 17(4): 344–378.

12.

Matthew

Desjardins

. Agent-organized network for dynamic team formation. In: International Joint Conference on Autonomous Agents & Multiagent Systems, Utrecht, Netherlands, 25–29 July 2005, 230–237.

13.

Robin

Sycara

Scerri

. Agent organized networks redux. In: Proceedings of the twenty-third AAAI conference on artificial intelligence, Chicago, USA, 2008.

14.

Samuel

Shoham

. Bayesian coalitional games. In: National Conference on Artificial Intelligence, Chicago, USA, 13–17 July 2008, 95–100.

15.

Bin

Liu

. Active crowd: a framework for optimized multi-task allocation in mobile crowdsensing systems. IEEE Trans Hum Mach Syst 2017; 47(3): 392–403.

16.

Bing

Chen

. A mutual-selecting market-based mechanism for dynamic coalition formation. Int J Adv Robot Syst, accepted for publication 2018. DOI: 10.1177/1729881418755840.

17.

Neeraj

Lee

Rodrigue

. Intelligent mobile video surveillance system as a Bayesian coalition game in vehicular sensor networks: learning automata approach. IEEE Trans Intell Transp syst 2015; 16(3): 1148–1161.

18.

Tanzil

Gharehshiran

Krishnamurthy

. A distributed coalition game approach to femto-cloud formation. IEEE Trans Cloud Comput 2016; 99: 1–1.

19.

Militano

Orsino

Araniti

. Trust-based and social-aware coalition formation game for multihop data uploading in 5G systems. Comput Netw 2016; 111: 141–151.

20.

John

. Games with incomplete information played by “Bayesian” players, I-III Part I. Manag Sci 1968; 14(5).

21.

Sadler

. Complex networks and local Bayesian equilibrium. Soc Sci Electron Publ 2015; 78(4): 575–586.

22.

Chalkiadakis

Elkind

Markakis

. Cooperative games with overlapping coalitions. J Artif Intell Res 2010; 39(1): 179–216.

23.

Dang

Dash

Rogers

. Overlapping coalition formation for efficient data fusion in multi-sensor networks. In: National Conference on Artificial Intelligence, Boston, USA, 2006; 1: 635–640.

24.

Chalkiadakis

Elkind

Markakis

. Overlapping coalition formation. In: Workshop on Internet and Network Economics, 2008: 307–321.

25.

John

. Games with incomplete information played by Bayesian players. Levines Working Paper Archive 1968; 14(5): 320–334.

26.

Eric

Smith

WD.

A Bayesian approach to relevance in game playing. Artif Intell 1997; 97(1–2): 195–242.

27.

Zinovi

Naroditskiy

Gerding

. Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types. Artif Intell 2013; 195(1): 106–139.

28.

Akkarajitsaku

Hossain

Niyato

. Coalition-based cooperative packet delivery under uncertainty: a dynamic Bayesian coalitional game. IEEE Trans Mobile Comput 2013; 12(2): 371–385.

29.

Yong

Chen

. A Bayesian overlapping coalition formation game for device-to-device spectrum sharing in cellular networks. IEEE Trans Wirel Commun 2015; 14(7): 4034–4051.

30.

Arun

. Local network effects and complex network structure. BE J Theor Econ 2008; 7(7): 1319–1319.

A multi-responsibility–oriented coalition formation framework for dynamic task allocation in mobile–distributed multi-agent systems

Abstract

Keywords

Introduction

Related preliminaries and system assumptions

System assumptions and definitions

Definition 1

Definition 2

Definition 3

Definition 4

Definition 5

Relationship between the two coalitions

Analysis of topological optimization in social networks

Self-adaptation principles and uncertainty in agent strategies

Definition 6: Self-adaptation principles

Constrained agent strategy

Freedom and probability calculation

Definition 7

Definition 8

An integrated framework for dynamic task allocation

A multi-responsibility–oriented coalition formation framework

Task execution coalition formation

CC formation

A solution of a CBOCG

A coalition payoff function definition

Resource utility and transmission utility

Cost

Belief Update

Algorithms in MOCFF

MSMA for task execution formation

LPSA for CC formation

Theorem 1

Proof

The process of MOCFF

Result analysis

Simulation settings

Performance evaluation

Result analysis

Comparison of four algorithms

Comparison between MOCFF and MSMA

Concluding remarks

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iD

References