# Multiagent Task Allocation in Complementary Teams: A Hunter-and-Gatherer Approach

Authors: Mehdi Dadvar; Saeed Moazami; Harley R. Myler; Hassan Zargarzadeh
Journal: Complexity
 (2020)

---

## Abstract

Consider a dynamic task allocation problem, where tasks are unknowingly distributed over an environment. This paper considers each task comprising two sequential subtasks: detection and completion, where each subtask can only be carried out by a certain type of agent. We address this problem using a novel nature-inspired approach called “hunter and gatherer.” The proposed method employs two complementary teams of agents: one agile in detecting (hunters) and another skillful in completing (gatherers) the tasks. To minimize the collective cost of task accomplishments in a distributed manner, a game-theoretic solution is introduced to couple agents from complementary teams. We utilize market-based negotiation models to develop incentive-based decision-making algorithms relying on innovative notions of “certainty and uncertainty profit margins.” The simulation results demonstrate that employing two complementary teams of hunters and gatherers can effectually improve the number of tasks completed by agents compared to conventional methods, while the collective cost of accomplishments is minimized. In addition, the stability and efficacy of the proposed solutions are studied using Nash equilibrium analysis and statistical analysis, respectively. It is also numerically shown that the proposed solutions function fairly; that is, for each type of agent, the overall workload is distributed equally.


---

## Body

## 1. Introduction

Multirobot systems are expected to undertake imperative roles in a wide variety of fields such as urban search and rescue (USAR) [1, 2], agricultural field operations [3], security patrols [4, 5], environmental monitoring [6], and industrial procedures [7]. Studies have shown that multirobot systems have advantage over single-robot systems by offering more reliability, redundancy, and time efficiency when the nature of the tasks is inherently distributed [8]. Nonetheless, the problem of multirobot task allocation (MRTA) poses many critical challenges that have called for investigation in the past two decades [9, 10]. In this regard, the complexity of MRTA problems increases significantly in a dynamic environment, where the number and location of tasks are unknown for agents [11, 12]. Thus, robots need to explore the environment to find tasks before accomplishing them. In real-world problems, any robot designated to perform one of the tasks in [1–6] needs to be sufficiently dexterous, i.e., to be equipped enough for accomplishing physical tasks such as object manipulation or rubble removal in a rescue mission [13], which inevitably make the robot relatively heavy and incapable of agile exploration. Having said that, the dynamic problem can be turned into a problem where each task is composed of sequential subtasks, each possible to be done only by a certain type of agent. In this case, for each type of subtask, a robot team of appropriate type must be employed. This case poses an unexplored MRTA problem whose coupling and cooperation between those complementary teams are the motivation of this work.In the context of MRTA, notable attention has been devoted for revealing various aspects of dynamic problems [14–17]. For instance, Lerman et al. [18] present a mathematical model of a general dynamic task allocation mechanism where robots use only local sensing and no direct communication is needed between them for task allocation. Disregarding the communication between agents is a deficiency where the information handled by the agents plays an imperative role in the functionality of a decentralized multiagent system in a dynamic environment. In this regard, Liemhetcharat and Veloso [19] introduce a novel weighted synergy graph model to capture new interactions among agents. In the created model, agents work together in a task throughout communication where weight of the edge indicates the communication cost between agents.In contrast to the way that Liemhetcharat and Veloso [19] utilize the communication among agents, there are works employing communications among agents to frame negotiations among them. For instance, Chapman et al. [20] pursue a decentralized game-theoretic approach in which planning is achieved via negotiation between agents. Although the results show that their approach is robust to restrictions on the agents’ communication and observation range, this work is not allowing agents to have differing costs for performing the same task which makes it inapplicable to a wide variety of real-world problems. On the contrary, Michael et al. [21] propose a distributed market-based coordination algorithm in which agents are able to bid for task assignments considering each agent’s cost for accomplishment of tasks to address the dynamic MRTA problem. While in real-world dynamic MRTA problems, tasks are not fully observable for all agents, the authors of this work assumed that the agents have knowledge on all tasks at a time. This assumption is too strong and does not completely reflect a dynamic environment’s situation. In this regard, Sariely and Balch [22] consider a real dynamic environment, present a real-time single-item auction-based task allocation method for the multirobot exploration problem, and investigate new bid evaluation strategies.While the works reviewed above [20–22] present different approaches to address a dynamic MRTA problem, they all similarly do not consider the agents' capabilities while developing the assignment algorithm. On this subject, Wu et al. [23] take agents’ capabilities into account in order to form teams by developing a market-based novel task allocation method based on the Gini coefficient. Although the authors demonstrated that the proposed method can effectively improve the number of tasks completed by a robot system, the effect of cooperation and coupling between the formed teams is still uninvestigated. In a similar effort, Shiroma and Campos [24] model agents’ capabilities as actions and utilize single-round auction to form teams and then form coordination between agents of the same team. In the same way, coupling and cooperation of the formed teams have been left unexplored in this work, though the developed framework was able to successfully resolve the required allocation issues. By the same token, Prorok et al. [25] model the multirobot system as a community of species considering agents’ capabilities and then present decentralized and centralized methods to efficiently control the heterogeneous teams of robots, regardless of interaction and collaboration between those teams. Given the review above, there is a lack of critical attention paid to the cooperation and coupling between robot teams, formed based on agents’ capabilities, to address a dynamic MRTA problem.As we discussed earlier, the number and location of tasks are unknown for agents in a dynamic environment [11, 12]. In this case, robots need to explore the environment to find tasks before accomplishing them. Since tasks usually require immense efforts to be completed in real-world problems such as a rescue mission, a suitable robot needs to be equipped with various sensors and devices, much more complex mechanisms, and a higher number of actuators. As a consequence, the robots inevitably become heavy and ponderous which cannot explore the environment agilely and efficiently. Motivated by this complexity, this paper proposes a nature-inspired approach called “hunter and gatherer” which employs two teams of robots: a team of agile robots that can quickly explore an environment and detect tasks, called “hunters,” and a team of dexterous robots who accomplish detected tasks called “gatherers.” In fact, we are turning a dynamic MRTA problem into a problem where each task is composed of two sequential subtasks: exploration and completion. Considering this, when there are synchronization and precedence (SP) constraints which specify an ordering constraint for time-extended assignment (TA) problems [26], the MRTA is referred to as a TA:SP problem [27]. To the best of the authors’ knowledge, the MT-MR-TA:SP problem has not been tackled in the literature so far, while it is a ubiquitous problem in a wide variety of fields such as USAR and agricultural field operations.Consider the USAR in a disaster site in which a number of victims have got stranded in unknown locations and need immediate rescue operations. Each victim is a task that needs to be detected first and then rescued by a rescue operation that typically needs several dexterity actions, such as providing logistics supports, rubble removal, object manipulation, and in situ medical assessment and intervention [13], which make a rescue robot heavy and incapable of agile search operations. This is because a rescue robot needs to have a heavy-duty manipulator, high-power actuators, tracked locomotion mechanism, high-capacity batteries, and many sorts of sensors, cameras, and communication devices to accomplish those tasks which make the robot relatively heavy and ponderous. Hence, let us consider each task comprises two sequential subtasks: detection and completion, where each subtask can only be carried out by a certain type of robot. Thus, the case encounters an ST-MR-TA:SP or MT-MR-TA:SP problem. In the USAR example, hunters can be a group of small and light-weighted unmanned aerial vehicles (UAVs) which search the site to locate victims and gatherers can be a group of maxi-sized [13] heavy-duty unmanned ground vehicles (UGVs) that rescue detected victims relying on their dexterity capabilities.According to the proposed hunter-and-gatherer scheme, we present a game-theoretic solution which considers coupling and cooperation between complementary agents divided into different teams by (1) utilizing market-based negotiation models, auction [28–30], and reverse auction and (2) introducing decentralized incentive-based decision-making algorithms. Proposed algorithms rely on new notions of certainty and uncertainty profit margins (CPM and UPM) that, respectively, determine the levels of confidence and conservativeness of each agent in negotiations to minimize the collective cost of task accomplishments. To enhance the effectiveness of proposed algorithms, a multitask-planning algorithm is invented for gatherer agents that enables them to queue multiple tasks in their action plan for finding the optimal solution for completing a group of tasks rather than doing one by one. We show that employing two complementary teams of hunters and gatherers can effectually improve the number of tasks completed by agents, while the collective cost of accomplishments is minimized. Moreover, the stability and efficacy of the assignment algorithms are proven by a Nash equilibrium analysis and simulation experiments, respectively. Besides, we investigated the distribution of workload, as the total costs and accomplishments of a mission, among agents and showed that the proposed algorithms function fairly; that is, for each type of agent, the overall workload is distributed equally, and all agents of the same type behave analogously under similar characteristics.The remainder of this paper is organized as follows: The problem statement and formulation are presented in Section2. In Section 3, the methodology including conceptual frameworks, reasoning mechanisms, and algorithms is proposed. Nash equilibrium analysis is carried out in Section 4. In Section 5, statistical analysis on simulation results is presented followed by a concluding discussion in Section 6.


## 2. Problem Statement

In this section, the problem of hunter-and-gatherer mission planning (HGMP) in the context of dynamic MRTA is explained. Assume that there arem tasks distributed randomly over the environment, E. We consider a case that the number and the locations of tasks are unknown for agents before the execution of the HGMP. The set of tasks is denoted as T=T1,...,Tm in which each task is split into hunting and gathering subtasks, i.e., Tk=tkh,tkg with 1≤k≤m, where tkh and tkg represent hunting and gathering subtasks, respectively. In this case, the set of agents is defined as A=Ah,Ag that comprises two teams of hunters Ah=aih and gatherers Ag=ajg, where 1≤i≤nh and 1≤j≤ng. The cost associated with aih for accomplishment of tkh is denoted as ck,ih, and ck,jg is the cost associated with ajg for accomplishment of tkg.


### 2.1. Assumptions

Throughout this paper, the following are assumed:(1)
Tasks are stationary; that is, they are fixed to their locations.(2)
The cost of accomplishment of each task is equal to the distance that an agent moves to do a task. An agent is considered done with a task when it reaches the task’s location.(3)
All agents of the same team are identical.(4)
All agents are rational; that is, they intend to maximize their expected utility.(5)
All agents are fully autonomous and have their own utility functions; that is, no global utility function exists.(6)
Agents from complementary teams can communicate with each other using a stably connected network.Now, the HGMP problem can be stated as follows: Suppose that there exists a tuple for the mission such that HGMP = (E, α, Τ).Π denotes the assignment function which assigns m tasks to n=nh+ng agents such that Π:T⟼A. Under assumptions (1)–(6), the global objective Θ is to minimize the collective cost of Π:(1)Θ=minxki,ykjρh∑i=1nh∑k=1mck,ihxki+ρg∑j=1ng∑k=1mck,jgykj,where xki and ykj are binary decision variables for tkh and tkg:(2)xki∈1,0,∀i,k,ykj∈1,0,∀j,k.In (1), weighting parameters ρh and ρg are introduced to sum relative collective costs of complementary teams because of the physical differences of each type Table 1.Table 1
Illustration of the notations used globally in this paper.
Symbol
Definition
T
The task set whereT=T1,...,Tm and 1≤k≤m
T
k
Thekth member of T where Tk=tkh,tkg
A
The agent set whereA=Ah,Ag
a
i
h and aig
Theith and jth members of Ah and Ag, respectively
c
k
,
i
h and ck,jg
The cost associated withaih for accomplishment of tkh and the cost associated with ajg for accomplishment of tkg, respectively
n
Defined asn=nh+ng, where nh and ng are the total number of hunters and gatherers, respectively
Π
The assignment function which assignsm tasks to n agents such that Π:T⟼A
Θ
The global objective which is to minimize the collective cost ofΠ
ρ
h and ρg
The weighting parameters of hunters and gatherers, respectively
x
k
i and ykj
The binary decision variables fortkh and tkg, respectively
I
h and Ig
The incentive rewards for accomplishing a hunting or gathering task, respectively
I
ex
An extra incentive for motivating agents from complementary teams to build up a cooperation
ϑ
A generalized subscript designated to denote both hunter and gatherer agents, where:ϑ∈h,g
P
k
,
i
h
Share of theith hunter in Iex for hunting the kth task
P
k
,
j
g
Share of thejth gatherer in Iex for gathering the kth task
n
w
h
Total number of hunters that have detected a task and are waiting for starting a negotiation
α
h and αg
Scaling parameters of certainty profit margins of hunters and gatherers, respectively
β
h and βg
Scaling parameters of uncertainty profit margins of hunters and gatherers, respectively
R
c
h and Rcg
Certainty radius for hunters and gatherers, respectively
R
u
h and Rug
Uncertainty radius for hunters and gatherers, respectively
U
h
t
k
h
The profit earned by a hunter for thekth task
U
g
t
k
g
The profit earned by a gatherer for thekth task
pi
h and pig
Profit interval of a hunter and gatherer, respectively
L
low
h and Luph
Lower and upper bounds of a hunter, respectively
L
low
g and Lupg
Lower and upper bounds of a gatherer, respectively
O
i
,
j
k
An offer made by thejth gatherer to the ith hunter for the kth task
b
j
,
i
k
A bid placed by thejth gatherer to the ith hunter for the kth task
ϒ
j
Action plan of thejth gatherer where ϒj=υ1,...,υq and q≤qmax with qmax as the maximum number of tasks that a gatherer can queueThis problem has a global objectiveΘ which can be achieved by determining the binary decision variables optimally. These variables need to be determined by the agents throughout explorations and negotiations in a distributed manner. Since agents are rational, each agent’s objective is to maximize its own expected utility. As a consequence, the objectives of agents may be conflicting during the HGMP. Hence, the methodology should be developed so that it handles these conflicts in order to maximize the effectiveness of the HGMP and achieve the global objective Θ.


## 2.1. Assumptions

Throughout this paper, the following are assumed:(1)
Tasks are stationary; that is, they are fixed to their locations.(2)
The cost of accomplishment of each task is equal to the distance that an agent moves to do a task. An agent is considered done with a task when it reaches the task’s location.(3)
All agents of the same team are identical.(4)
All agents are rational; that is, they intend to maximize their expected utility.(5)
All agents are fully autonomous and have their own utility functions; that is, no global utility function exists.(6)
Agents from complementary teams can communicate with each other using a stably connected network.Now, the HGMP problem can be stated as follows: Suppose that there exists a tuple for the mission such that HGMP = (E, α, Τ).Π denotes the assignment function which assigns m tasks to n=nh+ng agents such that Π:T⟼A. Under assumptions (1)–(6), the global objective Θ is to minimize the collective cost of Π:(1)Θ=minxki,ykjρh∑i=1nh∑k=1mck,ihxki+ρg∑j=1ng∑k=1mck,jgykj,where xki and ykj are binary decision variables for tkh and tkg:(2)xki∈1,0,∀i,k,ykj∈1,0,∀j,k.In (1), weighting parameters ρh and ρg are introduced to sum relative collective costs of complementary teams because of the physical differences of each type Table 1.Table 1
Illustration of the notations used globally in this paper.
Symbol
Definition
T
The task set whereT=T1,...,Tm and 1≤k≤m
T
k
Thekth member of T where Tk=tkh,tkg
A
The agent set whereA=Ah,Ag
a
i
h and aig
Theith and jth members of Ah and Ag, respectively
c
k
,
i
h and ck,jg
The cost associated withaih for accomplishment of tkh and the cost associated with ajg for accomplishment of tkg, respectively
n
Defined asn=nh+ng, where nh and ng are the total number of hunters and gatherers, respectively
Π
The assignment function which assignsm tasks to n agents such that Π:T⟼A
Θ
The global objective which is to minimize the collective cost ofΠ
ρ
h and ρg
The weighting parameters of hunters and gatherers, respectively
x
k
i and ykj
The binary decision variables fortkh and tkg, respectively
I
h and Ig
The incentive rewards for accomplishing a hunting or gathering task, respectively
I
ex
An extra incentive for motivating agents from complementary teams to build up a cooperation
ϑ
A generalized subscript designated to denote both hunter and gatherer agents, where:ϑ∈h,g
P
k
,
i
h
Share of theith hunter in Iex for hunting the kth task
P
k
,
j
g
Share of thejth gatherer in Iex for gathering the kth task
n
w
h
Total number of hunters that have detected a task and are waiting for starting a negotiation
α
h and αg
Scaling parameters of certainty profit margins of hunters and gatherers, respectively
β
h and βg
Scaling parameters of uncertainty profit margins of hunters and gatherers, respectively
R
c
h and Rcg
Certainty radius for hunters and gatherers, respectively
R
u
h and Rug
Uncertainty radius for hunters and gatherers, respectively
U
h
t
k
h
The profit earned by a hunter for thekth task
U
g
t
k
g
The profit earned by a gatherer for thekth task
pi
h and pig
Profit interval of a hunter and gatherer, respectively
L
low
h and Luph
Lower and upper bounds of a hunter, respectively
L
low
g and Lupg
Lower and upper bounds of a gatherer, respectively
O
i
,
j
k
An offer made by thejth gatherer to the ith hunter for the kth task
b
j
,
i
k
A bid placed by thejth gatherer to the ith hunter for the kth task
ϒ
j
Action plan of thejth gatherer where ϒj=υ1,...,υq and q≤qmax with qmax as the maximum number of tasks that a gatherer can queueThis problem has a global objectiveΘ which can be achieved by determining the binary decision variables optimally. These variables need to be determined by the agents throughout explorations and negotiations in a distributed manner. Since agents are rational, each agent’s objective is to maximize its own expected utility. As a consequence, the objectives of agents may be conflicting during the HGMP. Hence, the methodology should be developed so that it handles these conflicts in order to maximize the effectiveness of the HGMP and achieve the global objective Θ.


## 3. Methodology

### 3.1. Conceptual Frameworks

Hunters are assigned to explore the unknown environment. There isIh as the incentive reward for a hunter, denoted as aih, who detects a task, denoted as Tk. However, the detected task can only be completed by cooperation with a gatherer. Thus, an extra incentive is added for motivating agents from complementary teams to build up a cooperation, denoted as Iex. Hunters and gatherers involve in negotiation processes to reach agreements for completing the tasks and sharing Iex between themselves. In a negotiation, a hunter who has detected a task on one side and one or more gatherers on the other side are involved. An agreement determines which gatherer is assigned to complete the detected task and how much is its share from Iex. Let us denote 0≤Pk,ih≤1 and Pk,jg=1−Pk,ih as the proportions that aih and ajg receive from Iex for accomplishment of Tk, respectively. Also, the gatherer who completes the detected task receives Ig as a gathering incentive, when the task is completed. Since all agents are rational, they intend to maximize their incentives by accomplishing more tasks through building up more cooperation.To establish the process by which agents come into an agreement, we define an online board on which each hunter announces the location of its new detection to find gathering partners for starting a negotiation process. Each gatherer follows the announcements on the online board to choose a waiting hunter for negotiation by analyzing the location information shared by each waiting hunter. A gatherer then sends a readiness message to the chosen hunter to start a negotiation.We consider two possible scenarios in order to develop reasoning mechanisms for agents to negotiate and cooperate: (1) a waiting hunter receives only one readiness message and (2) the waiting hunter receives more than one readiness message. The first scenario resembles the bargaining or reverse auction process as there is only one buyer who aims to bargain for finding the most affordable option. The second scenario is similar to an auction process where usually there is more than one buyer interested in a specific object. We utilize these two market-based methods as negotiation models between negotiating agents. In addition, it is possible that the number of waiting hunters on the board, denoted asnwh, be more than one. In this case, the question that how a gatherer chooses a hunter among nwh waiting agents is addressed in Section 3.5. For the time being, we assume that gatherers already know how to choose a partner and we focus on the negotiation reasoning mechanisms.Fundamentals of reasoning mechanisms are discussed in the next section, and next, we will explain how agents rely on their reasoning mechanisms to behave in the reverse auction and auction scenarios in Sections3.3 and 3.4, respectively.


### 3.2. Reasoning Mechanism

In this section, reasoning mechanisms for both hunters and gatherers are developed to establish their behavior during a mission that determines the way that they communicate, negotiate, and cooperate. Since fundamentals of reasoning mechanisms are similar for both type of agents, for the sake of brevity, we consider a general agent defined asazϑ with ϑ∈h,g, where 1≤z≤nϑ.Moving on, it is time to introduce the CPM and UPM forazϑ. The CPM is a circular margin with a radius of Rcϑ, in which azϑ is certain about a profitable agreement even if its share in Iex is zero. The UPM is a circular margin between two concentric circles with radiuses of Ruϑ and Rcϑ, in which azϑ is uncertain about making a profit in an agreement; that is, its profit strongly depends on its proportion of Iex. Furthermore, azϑ cannot make any profit beyond its UPM even if it receives Iex entirely.Figure1 shows the CPM and UPM as two concentric circles with azϑ as the center. The agent compares its cost for accomplishing the task with its CPM and UPM to realize its state to make profitable decisions during the negotiation.Figure 1
CPM and UPM.T1 and T2 are in the agent’s CPM and UPM, respectively. T3 is beyond the agent’s uncertainty boundary.The following statements explain the states ofazϑ with respect to its cost for accomplishing tkϑ:(i)
State 1: ifck,zϑ<Rcϑ, then azϑ can make a profit regardless of its proportion of Iex(ii)
State 2: ifRcϑ<ck,zϑ<Ruϑ, then the profit of azϑ depends on its proportion of Iex(iii)
State 3: ifck,zϑ>Ruϑ, then azϑ cannot make any profit even if it receives all of IexWe formulize the CPM and UPM forazϑ by defining Rcϑ and Ruϑ. If azϑ accomplishes tkϑ, then it receives Iϑ as an incentive. Since azϑ is certain about receiving Iϑ, we have Rcϑ∝Iϑ. Hence, we define Rcϑ by introducing αϑ as a scaling parameter for the CPM:(3)Rcϑ=αϑIϑ.In addition,azϑ receives a proportion of Iex that will be determined by the negotiation process, so azϑ is uncertain about its share of Iex. Thus, we define Ruϑ by introducing βϑ as a scaling parameter for the UPM:(4)Ruϑ=Rcϑ+βϑIex.Altogether, forazϑ involved in a negotiation, the utility function defined below determines its payoff.Definition 1 (utility function).
U
ϑ
t
k
ϑ gives the profit earned by azϑ for accomplishing tkϑ and building up a cooperation. The utility function of azϑ is defined as(5)Uϑtkϑ=αϑIϑ+βϑPk,zϑIex−ck,zϑ.
Now, we define a profit interval forazϑ, regarding its state for accomplishing tkϑ, by which it evaluates its results in a negotiation. A profit interval is an interval for Pk,zϑ that guarantees the negotiation’s profitability. According to assumption (4), azϑ wants to maximize its payoff, so in each negotiation, azϑ definitely makes a nonnegative profit such that(6)αϑIϑ+βϑPk,zϑIex−ck,zϑ≥0.
This can be written as(7)ck,zϑ−αϑIϑβϑIex−1≤Pk,zϑ.
The overlap of0≤Pk,zϑ≤1 and (7) yields the profit interval for Pk,zϑ. The overlap in all three states is expressed as follows: If azϑ is in state 1, then ck,zϑ<αϑIϑ and the left side of (7) is negative. Hence, the overlap is 0≤Pk,zϑ≤1; that is, in state 1, azϑ makes a profit regardless of its share in Iex. If azϑ is in state 2, then we have ck,zϑ>αϑIϑ. Therefore, the overlap gives ck,zϑ−αϑIϑIexβϑ−1≤Pk,zϑ≤1. And if azϑ is in state 3, then we have ck,zϑ>αϑIϑ+βϑIex, so the left side of (7) is greater than one. Hence, the overlap of (7) and 0≤Pk,zϑ≤1 is a null set; that is, the task is not profitable. Accordingly, the profit interval of azϑ for accomplishing tkϑ is defined as piϑ=Llowϑ,Lupϑ, where Llowϑ and Lupϑ denote lower and upper bounds, respectively.


### 3.3. The First Scenario: Reverse Auction

Consider the scenario shown in Figure2(a) and suppose that aih has detected Tk at the cost of ck,ih, it has posted an announcement on the online board, and it receives a readiness message only from ajg. This message is a request for a quotation message; that is, aih offers a proportion for sharing Iex and ajg decides to accept or reject the offer. Accordingly, we explain how aih makes offers and ajg makes an acceptance or rejection decision, using the proposed reasoning mechanisms.Figure 2
Possible scenarios: (a) reverse auction scenario and (b) auction scenario.
(a)
(b)According to the process illustrated in Figure3, aih calculates the lower bound, the midpoint, and the upper bound of its profit interval for making 3 offers. Since aih is making offers to ajg, it should send offers using Pk,jg=1−Pk,ih, as follows:(8)Oi,jk=1−Llowh,Oi,j′k=1−12Luph−Llowh,Oi,j″k=1−Luph.Figure 3
Reverse auction process.According to Figure3, at the first decision node, aih makes an offer regarding the explained process, and then at the second step, ajg decides to accept or reject the offer. Algorithm 1 illustrates the bargaining procedure for aih. In this algorithm, acandg denotes the gatherer agent that has sent the readiness message. In line 3 in Algorithm 1, Oi,jk,Oi,j′k,Oi,j″k is assigned to the vector “offers” in a random order.Algorithm 1: Bargaining function for a hunter agent.
(1)
function bargain (ck,ih, αh, βh, acandg)
(2)
pih ⟵ calculate Llowh,Luph
(3)
offers ⟵ calculate offers: Oi,jk,Oi,j′k,Oi,j″k
(4)
for each offer do
(5)
send the offer toacandg
(6)
if an acceptance message is received then
(7)
results⟵acandg,offer
(8)
break for
(9)
else
(10)
results⟵∅
(11)
end if
(12)
end for
(13)
return resultsBesides,ajg uses its own profit interval to make an acceptance or rejection decision. For each received offer made by aih, if the offer is inside pig, then ajg accepts the offer. Otherwise, it rejects the offer.


### 3.4. The Second Scenario: Auction

Consider the auction scenario shown in Figure2(b) and suppose that aih has detected Tk at cost ck,ih, it has posted an announcement on the online board, and it receives readiness messages from nb≥2 gatherers. In this case, aih holds an auction and selects the winner, where gatherers bid for sharing Iex to win the detected task and complete it. Accordingly, both types of agents’ reasoning mechanisms need to be investigated.We utilize the “second-price sealed-bid auction” as the negotiation framework in which the winning bidder is an agent who has placed the highest bid and it pays the amount equal to the second highest bid to the hunter holding the auction. In this auction,ajg, a gatherer bidding in the auction, can bid its valuation. Since it will not pay as much as it bids if it wins, ajg still has a chance to get a positive benefit from the auction. Therefore, the main advantage of the second-price auction over the first-price auction is that truthful bidding is an optimal strategy in a second-price auction, and as a result, it is ensured to converge to an optimal solution. Trustful bidding means that it is an optimal strategy for a bidder in a second-price auction to bid however much it values that object [31]. To that end, we explain how ajg bids using its profit intervals first and then we discuss the way that aih chooses the winning bidder. ajg bids its valuation that is the lowest bound of its profit interval. Since ajg is making an offer to aih by bidding, it should send the bid using Pk,ih=1−Pk,jg, as follows:(9)bj,ik=1−Llowg.Besides,aih chooses the winner bidder after a single round of bidding. Firstly, aih chooses the winning bidder, awg, regarding the maximum bid in the set of bids, denoted as b, such that(10)w=argsmaxb.Secondly,aihchecks if the second highest bid satisfies the minimum acceptable bid determined by its profit interval. Since the share of aih in Iex must satisfy (6), the minimum acceptable bid is the lower bound, Llowh, of its profit interval such that(11)maxj≠wbj≥Llowh.


### 3.5. Multitask Planning

In Figure4, suppose that a1h has detected T2. a2g is the only gatherer agent that can send a readiness message to start a negotiation with a1h because a1g is busy with gathering T1. In this case, t2g⟶a2g is an inefficient planning where c2,1g<c2,2g.Figure 4
An example explaining the necessity of multitasking capability of gatherer agents.Alternatively, ifa1g is able to plan for multiple tasks at a time, it could gather T2 at a lower cost. Accordingly, to prevent such ineffective plannings in the HGMP, in the following, a multitask-planning algorithm for gatherers is proposed.Let us define an action plan in whichajg queues multiple tasks to accomplish in the future such that ϒj=υ1,...,υq, where q≤qmax with qmax as the maximum number of tasks that gatherers can queue. Each task has a profile in the gatherer’s action plan containing required information: υq=tkg,ck,jg,ck,j′g,Pk,jg, where ck,j′g denotes the temporary cost calculated by the agent for tkg. υ1 through υq are the tasks that ajg is already planned to accomplish (actual tasks). In addition, Γj denotes the path that ajg follows to accomplish ϒj. Now, assume that ajg wants to add a new task to ϒj as υi+1, when q<qmax. The first step is choosing a waiting hunter, and the second step is negotiating with the chosen agent. The negotiation processes have been discussed before, so here we focus on the procedure that ajg chooses a waiting hunter to fill up ϒj.The proposed method relies on the CPM and UPM to develop the gatherers’ reasoning mechanism so thatajg fills up ϒj effectually. To that end, a three-step process in which ajg chooses a waiting hunter agent for negotiation is proposed. Before starting the process, ajg follows the online board and lists the waiting hunters in Awaitingh ordered by their waiting time; that is, the oldest is the first in the list. Process steps are elaborated as follows:Step 1:ajg considers the most prior task from Awaitingh, denoted as Tcand. Then, ajg plans the shortest multidestination temporary path, using the A∗ search algorithm [32], denoted as Γj′, to gather all tasks in ϒj plus Tcand. When Γj′ is generated, the temporary cost of each task must be updated in each task’s profile.Step 2:ajg verifies the feasibility of making a profit from Tcand. Thus, it checks whether Tcand is in state 3 regarding Γj′. If Tcand is not in state 3, then ajg goes to the next step. Otherwise, ajg withdraws Tcand and starts over from the first step.Step 3:ajg examines the effect of choosing Tcand on the actual tasks in ϒj. When ajg generates Γj′ in step 1, it may have ck,jg≠ck,j′g for the actual tasks in ϒj. For this reason, ajg checks whether (6) is still true for newly calculated temporary costs for each actual task. If (6) is true for all actual tasks, Tcand is verified for starting a negotiation process; otherwise, ajg withdraws Tcand and starts over from the first step.Algorithm2 illustrates the multitask-planning procedure for ajg. This algorithm is developed as a function for choosing a candidate task detected by a waiting hunter by considering ϒj. Not to mention, the output of this algorithm is not a task in the agent’s action plan, i.e., υq+1. The output is a candidate task detected by a waiting hunter that potentially can be added to ϒj as υq+1 depending on the negotiation process.Algorithm 2: Multitask planning.
(1)
function ChoosePartner (ϒj, αg, βg, qmax, online_board)
(2)
Awaitingh ⟵ list and sort waiting hunters
(3)
for each hunter in Awaitinghαgdo
(4)
acandh ⟵ the selected waiting hunter
(5)
Tcand ⟵ the task detected by acandh
(6)
Γj′ ⟵ generate a path to do ϒj and Tcand
(7)
updateϒj with newly calculated costs
(8)
if ajg is not in state 3 for Tcandthen
(9)
validation_flag⟵true
(10)
for υ1 to υqdo
(11)
if αgIg+βgPk,jgIex<ck,j′gthen
(12)
validation_flag⟵false
(13)
end if
(14)
end for
(15)
end if
(16)
if validation_flag == true then
(17)
results⟵acandh,Tcand
(18)
break for
(19)
end if
(20)
end for
(21)
return
resultsFigure5 illustrates an example in which a1g fills out its action plan where qmax=5. All sequences happen before accomplishing υ1. In sequence 1, a1g has already υ1 in its action plan and chooses TC1 to negotiate. In sequence 2, a1g has reached an agreement for accomplishing TC1 and adds it to its action plan as υ2. Moreover, there are two candidates, and TC2 is chosen to negotiate because TC3 is not feasible and fails to satisfy the condition mentioned in step 2. In sequence 3, a1g has reached an agreement for accomplishing TC2 and adds it to its action plan as υ3. In addition, there are two candidate tasks, namely, TC4 and TC5. TC5 cannot be verified in step 3, though it is feasible itself and passes step 2. Therefore, a1g chooses TC4 for negotiation. In sequence 4, a1g has reached an agreement for accomplishing TC4 and adds it to its action plan as υ4. Moreover, it chooses TC6 to negotiate because it passes all 3 steps. Although choosing TC6 causes change in the path to T2, it does not bring a1g into state 3 for T2.Figure 5
An example of multitask planning by a gatherer agent.


### 3.6. Decision-Making Algorithms

Firstly, we propose a distributed decision-making algorithm determining the exploration, detection, and negotiating procedure foraih in the HGMP. Basically, we utilize the distributed approach to ensure the reliability of the MAS, where centralized MASs may not be robust for the reason that they are relying on a single central unit. In addition, the inherence of the proposed reasoning mechanism enables agents to make the decision independently regardless of any central unit. Furthermore, the nature of the profit margins limits all interactions between agents to local regions within the environment, so there is no need for a central unit to play a role. Even in the case of auctions, each hunter who has detected a task holds a local auction and plays the role of an action organizer temporally and locally. Having said that, a distributed decision-making algorithm fits the best to the proposed reasoning mechanisms. Accordingly, Algorithm 3 illustrates the decision-making procedure for aih. In each iteration, aih explores the environment to detect a task. When aih detects a task, denoted as Tdetected, it announces the location on the online board and waits to receive readiness messages. According to the number of readiness messages that aihreceives, it starts a reverse auction or auction negotiation process to reach an agreement. If aih reaches an agreement, then it starts exploring the environment again. Otherwise, aih announces its detection on the online board again and does the same procedure. τ denotes the iteration number, and τmax denotes the maximum iterations in a mission.Algorithm 3: Decision-making outer-loop algorithm of aih.
(1)
for
τ
=
1
:
τ
max
do
(2)
if hold = = false then
(3)
explore the environment
(4)
if a new task is detected then
(5)
Tdetected⟵the new detected task
(6)
hold⟵true
(7)
end if
(8)
end if
(9)
if hold == true then
(10)
announceTdetected on the online board
(11)
if one readiness message is received then
(12)
bargain
(13)
else if readiness messages >1 then
(14)
hold an auction
(15)
end if
(16)
if the negotiation is succeeded then
(17)
hold⟵false
(18)
mark the task as accomplished
(19)
end if
(20)
end if
(21)
end forSecondly, we present a distributed decision-making algorithm determining the negotiating and accomplishment procedure in the HGMP forajg regarding the explained reasoning mechanisms. Algorithm 4 illustrates the decision-making procedure for ajg. In each iteration, when q<qmax, ajg manages its action plan by calling the “choose partner” function first and then negotiating with the chosen hunter upon availability. If the negotiation is succeeded, then it adds the new task to ϒj and updates Γj. Moreover, in each iteration, ajg follows Γj to gather tasks in ϒj. When a task is gathered, ajg updates ϒj by removing the accomplished task.Algorithm 4: Decision-making outer-loop algorithm of a gatherer agent.
(1)
for
τ
=
1
:
τ
max
do
(2)
ifq<qmaxthen
(3)
acandh,Tcand⟵choose partner
(4)
ifacandh≠∅then
(5)
send the readiness message toacandh
(6)
if received a bargaining notification then
(7)
bargain
(8)
else
(9)
place a bid for the auction
(10)
end if
(11)
end if
(12)
if the negotiation is succeeded then
(13)
addTcand to ϒj as υq+1
(14)
Γj⟵Γj′
(15)
end if
(16)
end if
(17)
followΓj to accomplish tasks and update ϒj
(18)
end for


## 3.1. Conceptual Frameworks

Hunters are assigned to explore the unknown environment. There isIh as the incentive reward for a hunter, denoted as aih, who detects a task, denoted as Tk. However, the detected task can only be completed by cooperation with a gatherer. Thus, an extra incentive is added for motivating agents from complementary teams to build up a cooperation, denoted as Iex. Hunters and gatherers involve in negotiation processes to reach agreements for completing the tasks and sharing Iex between themselves. In a negotiation, a hunter who has detected a task on one side and one or more gatherers on the other side are involved. An agreement determines which gatherer is assigned to complete the detected task and how much is its share from Iex. Let us denote 0≤Pk,ih≤1 and Pk,jg=1−Pk,ih as the proportions that aih and ajg receive from Iex for accomplishment of Tk, respectively. Also, the gatherer who completes the detected task receives Ig as a gathering incentive, when the task is completed. Since all agents are rational, they intend to maximize their incentives by accomplishing more tasks through building up more cooperation.To establish the process by which agents come into an agreement, we define an online board on which each hunter announces the location of its new detection to find gathering partners for starting a negotiation process. Each gatherer follows the announcements on the online board to choose a waiting hunter for negotiation by analyzing the location information shared by each waiting hunter. A gatherer then sends a readiness message to the chosen hunter to start a negotiation.We consider two possible scenarios in order to develop reasoning mechanisms for agents to negotiate and cooperate: (1) a waiting hunter receives only one readiness message and (2) the waiting hunter receives more than one readiness message. The first scenario resembles the bargaining or reverse auction process as there is only one buyer who aims to bargain for finding the most affordable option. The second scenario is similar to an auction process where usually there is more than one buyer interested in a specific object. We utilize these two market-based methods as negotiation models between negotiating agents. In addition, it is possible that the number of waiting hunters on the board, denoted asnwh, be more than one. In this case, the question that how a gatherer chooses a hunter among nwh waiting agents is addressed in Section 3.5. For the time being, we assume that gatherers already know how to choose a partner and we focus on the negotiation reasoning mechanisms.Fundamentals of reasoning mechanisms are discussed in the next section, and next, we will explain how agents rely on their reasoning mechanisms to behave in the reverse auction and auction scenarios in Sections3.3 and 3.4, respectively.


## 3.2. Reasoning Mechanism

In this section, reasoning mechanisms for both hunters and gatherers are developed to establish their behavior during a mission that determines the way that they communicate, negotiate, and cooperate. Since fundamentals of reasoning mechanisms are similar for both type of agents, for the sake of brevity, we consider a general agent defined asazϑ with ϑ∈h,g, where 1≤z≤nϑ.Moving on, it is time to introduce the CPM and UPM forazϑ. The CPM is a circular margin with a radius of Rcϑ, in which azϑ is certain about a profitable agreement even if its share in Iex is zero. The UPM is a circular margin between two concentric circles with radiuses of Ruϑ and Rcϑ, in which azϑ is uncertain about making a profit in an agreement; that is, its profit strongly depends on its proportion of Iex. Furthermore, azϑ cannot make any profit beyond its UPM even if it receives Iex entirely.Figure1 shows the CPM and UPM as two concentric circles with azϑ as the center. The agent compares its cost for accomplishing the task with its CPM and UPM to realize its state to make profitable decisions during the negotiation.Figure 1
CPM and UPM.T1 and T2 are in the agent’s CPM and UPM, respectively. T3 is beyond the agent’s uncertainty boundary.The following statements explain the states ofazϑ with respect to its cost for accomplishing tkϑ:(i)
State 1: ifck,zϑ<Rcϑ, then azϑ can make a profit regardless of its proportion of Iex(ii)
State 2: ifRcϑ<ck,zϑ<Ruϑ, then the profit of azϑ depends on its proportion of Iex(iii)
State 3: ifck,zϑ>Ruϑ, then azϑ cannot make any profit even if it receives all of IexWe formulize the CPM and UPM forazϑ by defining Rcϑ and Ruϑ. If azϑ accomplishes tkϑ, then it receives Iϑ as an incentive. Since azϑ is certain about receiving Iϑ, we have Rcϑ∝Iϑ. Hence, we define Rcϑ by introducing αϑ as a scaling parameter for the CPM:(3)Rcϑ=αϑIϑ.In addition,azϑ receives a proportion of Iex that will be determined by the negotiation process, so azϑ is uncertain about its share of Iex. Thus, we define Ruϑ by introducing βϑ as a scaling parameter for the UPM:(4)Ruϑ=Rcϑ+βϑIex.Altogether, forazϑ involved in a negotiation, the utility function defined below determines its payoff.Definition 1 (utility function).
U
ϑ
t
k
ϑ gives the profit earned by azϑ for accomplishing tkϑ and building up a cooperation. The utility function of azϑ is defined as(5)Uϑtkϑ=αϑIϑ+βϑPk,zϑIex−ck,zϑ.
Now, we define a profit interval forazϑ, regarding its state for accomplishing tkϑ, by which it evaluates its results in a negotiation. A profit interval is an interval for Pk,zϑ that guarantees the negotiation’s profitability. According to assumption (4), azϑ wants to maximize its payoff, so in each negotiation, azϑ definitely makes a nonnegative profit such that(6)αϑIϑ+βϑPk,zϑIex−ck,zϑ≥0.
This can be written as(7)ck,zϑ−αϑIϑβϑIex−1≤Pk,zϑ.
The overlap of0≤Pk,zϑ≤1 and (7) yields the profit interval for Pk,zϑ. The overlap in all three states is expressed as follows: If azϑ is in state 1, then ck,zϑ<αϑIϑ and the left side of (7) is negative. Hence, the overlap is 0≤Pk,zϑ≤1; that is, in state 1, azϑ makes a profit regardless of its share in Iex. If azϑ is in state 2, then we have ck,zϑ>αϑIϑ. Therefore, the overlap gives ck,zϑ−αϑIϑIexβϑ−1≤Pk,zϑ≤1. And if azϑ is in state 3, then we have ck,zϑ>αϑIϑ+βϑIex, so the left side of (7) is greater than one. Hence, the overlap of (7) and 0≤Pk,zϑ≤1 is a null set; that is, the task is not profitable. Accordingly, the profit interval of azϑ for accomplishing tkϑ is defined as piϑ=Llowϑ,Lupϑ, where Llowϑ and Lupϑ denote lower and upper bounds, respectively.


## 3.3. The First Scenario: Reverse Auction

Consider the scenario shown in Figure2(a) and suppose that aih has detected Tk at the cost of ck,ih, it has posted an announcement on the online board, and it receives a readiness message only from ajg. This message is a request for a quotation message; that is, aih offers a proportion for sharing Iex and ajg decides to accept or reject the offer. Accordingly, we explain how aih makes offers and ajg makes an acceptance or rejection decision, using the proposed reasoning mechanisms.Figure 2
Possible scenarios: (a) reverse auction scenario and (b) auction scenario.
(a)
(b)According to the process illustrated in Figure3, aih calculates the lower bound, the midpoint, and the upper bound of its profit interval for making 3 offers. Since aih is making offers to ajg, it should send offers using Pk,jg=1−Pk,ih, as follows:(8)Oi,jk=1−Llowh,Oi,j′k=1−12Luph−Llowh,Oi,j″k=1−Luph.Figure 3
Reverse auction process.According to Figure3, at the first decision node, aih makes an offer regarding the explained process, and then at the second step, ajg decides to accept or reject the offer. Algorithm 1 illustrates the bargaining procedure for aih. In this algorithm, acandg denotes the gatherer agent that has sent the readiness message. In line 3 in Algorithm 1, Oi,jk,Oi,j′k,Oi,j″k is assigned to the vector “offers” in a random order.Algorithm 1: Bargaining function for a hunter agent.
(1)
function bargain (ck,ih, αh, βh, acandg)
(2)
pih ⟵ calculate Llowh,Luph
(3)
offers ⟵ calculate offers: Oi,jk,Oi,j′k,Oi,j″k
(4)
for each offer do
(5)
send the offer toacandg
(6)
if an acceptance message is received then
(7)
results⟵acandg,offer
(8)
break for
(9)
else
(10)
results⟵∅
(11)
end if
(12)
end for
(13)
return resultsBesides,ajg uses its own profit interval to make an acceptance or rejection decision. For each received offer made by aih, if the offer is inside pig, then ajg accepts the offer. Otherwise, it rejects the offer.


## 3.4. The Second Scenario: Auction

Consider the auction scenario shown in Figure2(b) and suppose that aih has detected Tk at cost ck,ih, it has posted an announcement on the online board, and it receives readiness messages from nb≥2 gatherers. In this case, aih holds an auction and selects the winner, where gatherers bid for sharing Iex to win the detected task and complete it. Accordingly, both types of agents’ reasoning mechanisms need to be investigated.We utilize the “second-price sealed-bid auction” as the negotiation framework in which the winning bidder is an agent who has placed the highest bid and it pays the amount equal to the second highest bid to the hunter holding the auction. In this auction,ajg, a gatherer bidding in the auction, can bid its valuation. Since it will not pay as much as it bids if it wins, ajg still has a chance to get a positive benefit from the auction. Therefore, the main advantage of the second-price auction over the first-price auction is that truthful bidding is an optimal strategy in a second-price auction, and as a result, it is ensured to converge to an optimal solution. Trustful bidding means that it is an optimal strategy for a bidder in a second-price auction to bid however much it values that object [31]. To that end, we explain how ajg bids using its profit intervals first and then we discuss the way that aih chooses the winning bidder. ajg bids its valuation that is the lowest bound of its profit interval. Since ajg is making an offer to aih by bidding, it should send the bid using Pk,ih=1−Pk,jg, as follows:(9)bj,ik=1−Llowg.Besides,aih chooses the winner bidder after a single round of bidding. Firstly, aih chooses the winning bidder, awg, regarding the maximum bid in the set of bids, denoted as b, such that(10)w=argsmaxb.Secondly,aihchecks if the second highest bid satisfies the minimum acceptable bid determined by its profit interval. Since the share of aih in Iex must satisfy (6), the minimum acceptable bid is the lower bound, Llowh, of its profit interval such that(11)maxj≠wbj≥Llowh.


## 3.5. Multitask Planning

In Figure4, suppose that a1h has detected T2. a2g is the only gatherer agent that can send a readiness message to start a negotiation with a1h because a1g is busy with gathering T1. In this case, t2g⟶a2g is an inefficient planning where c2,1g<c2,2g.Figure 4
An example explaining the necessity of multitasking capability of gatherer agents.Alternatively, ifa1g is able to plan for multiple tasks at a time, it could gather T2 at a lower cost. Accordingly, to prevent such ineffective plannings in the HGMP, in the following, a multitask-planning algorithm for gatherers is proposed.Let us define an action plan in whichajg queues multiple tasks to accomplish in the future such that ϒj=υ1,...,υq, where q≤qmax with qmax as the maximum number of tasks that gatherers can queue. Each task has a profile in the gatherer’s action plan containing required information: υq=tkg,ck,jg,ck,j′g,Pk,jg, where ck,j′g denotes the temporary cost calculated by the agent for tkg. υ1 through υq are the tasks that ajg is already planned to accomplish (actual tasks). In addition, Γj denotes the path that ajg follows to accomplish ϒj. Now, assume that ajg wants to add a new task to ϒj as υi+1, when q<qmax. The first step is choosing a waiting hunter, and the second step is negotiating with the chosen agent. The negotiation processes have been discussed before, so here we focus on the procedure that ajg chooses a waiting hunter to fill up ϒj.The proposed method relies on the CPM and UPM to develop the gatherers’ reasoning mechanism so thatajg fills up ϒj effectually. To that end, a three-step process in which ajg chooses a waiting hunter agent for negotiation is proposed. Before starting the process, ajg follows the online board and lists the waiting hunters in Awaitingh ordered by their waiting time; that is, the oldest is the first in the list. Process steps are elaborated as follows:Step 1:ajg considers the most prior task from Awaitingh, denoted as Tcand. Then, ajg plans the shortest multidestination temporary path, using the A∗ search algorithm [32], denoted as Γj′, to gather all tasks in ϒj plus Tcand. When Γj′ is generated, the temporary cost of each task must be updated in each task’s profile.Step 2:ajg verifies the feasibility of making a profit from Tcand. Thus, it checks whether Tcand is in state 3 regarding Γj′. If Tcand is not in state 3, then ajg goes to the next step. Otherwise, ajg withdraws Tcand and starts over from the first step.Step 3:ajg examines the effect of choosing Tcand on the actual tasks in ϒj. When ajg generates Γj′ in step 1, it may have ck,jg≠ck,j′g for the actual tasks in ϒj. For this reason, ajg checks whether (6) is still true for newly calculated temporary costs for each actual task. If (6) is true for all actual tasks, Tcand is verified for starting a negotiation process; otherwise, ajg withdraws Tcand and starts over from the first step.Algorithm2 illustrates the multitask-planning procedure for ajg. This algorithm is developed as a function for choosing a candidate task detected by a waiting hunter by considering ϒj. Not to mention, the output of this algorithm is not a task in the agent’s action plan, i.e., υq+1. The output is a candidate task detected by a waiting hunter that potentially can be added to ϒj as υq+1 depending on the negotiation process.Algorithm 2: Multitask planning.
(1)
function ChoosePartner (ϒj, αg, βg, qmax, online_board)
(2)
Awaitingh ⟵ list and sort waiting hunters
(3)
for each hunter in Awaitinghαgdo
(4)
acandh ⟵ the selected waiting hunter
(5)
Tcand ⟵ the task detected by acandh
(6)
Γj′ ⟵ generate a path to do ϒj and Tcand
(7)
updateϒj with newly calculated costs
(8)
if ajg is not in state 3 for Tcandthen
(9)
validation_flag⟵true
(10)
for υ1 to υqdo
(11)
if αgIg+βgPk,jgIex<ck,j′gthen
(12)
validation_flag⟵false
(13)
end if
(14)
end for
(15)
end if
(16)
if validation_flag == true then
(17)
results⟵acandh,Tcand
(18)
break for
(19)
end if
(20)
end for
(21)
return
resultsFigure5 illustrates an example in which a1g fills out its action plan where qmax=5. All sequences happen before accomplishing υ1. In sequence 1, a1g has already υ1 in its action plan and chooses TC1 to negotiate. In sequence 2, a1g has reached an agreement for accomplishing TC1 and adds it to its action plan as υ2. Moreover, there are two candidates, and TC2 is chosen to negotiate because TC3 is not feasible and fails to satisfy the condition mentioned in step 2. In sequence 3, a1g has reached an agreement for accomplishing TC2 and adds it to its action plan as υ3. In addition, there are two candidate tasks, namely, TC4 and TC5. TC5 cannot be verified in step 3, though it is feasible itself and passes step 2. Therefore, a1g chooses TC4 for negotiation. In sequence 4, a1g has reached an agreement for accomplishing TC4 and adds it to its action plan as υ4. Moreover, it chooses TC6 to negotiate because it passes all 3 steps. Although choosing TC6 causes change in the path to T2, it does not bring a1g into state 3 for T2.Figure 5
An example of multitask planning by a gatherer agent.


## 3.6. Decision-Making Algorithms

Firstly, we propose a distributed decision-making algorithm determining the exploration, detection, and negotiating procedure foraih in the HGMP. Basically, we utilize the distributed approach to ensure the reliability of the MAS, where centralized MASs may not be robust for the reason that they are relying on a single central unit. In addition, the inherence of the proposed reasoning mechanism enables agents to make the decision independently regardless of any central unit. Furthermore, the nature of the profit margins limits all interactions between agents to local regions within the environment, so there is no need for a central unit to play a role. Even in the case of auctions, each hunter who has detected a task holds a local auction and plays the role of an action organizer temporally and locally. Having said that, a distributed decision-making algorithm fits the best to the proposed reasoning mechanisms. Accordingly, Algorithm 3 illustrates the decision-making procedure for aih. In each iteration, aih explores the environment to detect a task. When aih detects a task, denoted as Tdetected, it announces the location on the online board and waits to receive readiness messages. According to the number of readiness messages that aihreceives, it starts a reverse auction or auction negotiation process to reach an agreement. If aih reaches an agreement, then it starts exploring the environment again. Otherwise, aih announces its detection on the online board again and does the same procedure. τ denotes the iteration number, and τmax denotes the maximum iterations in a mission.Algorithm 3: Decision-making outer-loop algorithm of aih.
(1)
for
τ
=
1
:
τ
max
do
(2)
if hold = = false then
(3)
explore the environment
(4)
if a new task is detected then
(5)
Tdetected⟵the new detected task
(6)
hold⟵true
(7)
end if
(8)
end if
(9)
if hold == true then
(10)
announceTdetected on the online board
(11)
if one readiness message is received then
(12)
bargain
(13)
else if readiness messages >1 then
(14)
hold an auction
(15)
end if
(16)
if the negotiation is succeeded then
(17)
hold⟵false
(18)
mark the task as accomplished
(19)
end if
(20)
end if
(21)
end forSecondly, we present a distributed decision-making algorithm determining the negotiating and accomplishment procedure in the HGMP forajg regarding the explained reasoning mechanisms. Algorithm 4 illustrates the decision-making procedure for ajg. In each iteration, when q<qmax, ajg manages its action plan by calling the “choose partner” function first and then negotiating with the chosen hunter upon availability. If the negotiation is succeeded, then it adds the new task to ϒj and updates Γj. Moreover, in each iteration, ajg follows Γj to gather tasks in ϒj. When a task is gathered, ajg updates ϒj by removing the accomplished task.Algorithm 4: Decision-making outer-loop algorithm of a gatherer agent.
(1)
for
τ
=
1
:
τ
max
do
(2)
ifq<qmaxthen
(3)
acandh,Tcand⟵choose partner
(4)
ifacandh≠∅then
(5)
send the readiness message toacandh
(6)
if received a bargaining notification then
(7)
bargain
(8)
else
(9)
place a bid for the auction
(10)
end if
(11)
end if
(12)
if the negotiation is succeeded then
(13)
addTcand to ϒj as υq+1
(14)
Γj⟵Γj′
(15)
end if
(16)
end if
(17)
followΓj to accomplish tasks and update ϒj
(18)
end for


## 4. Nash Equilibrium Analysis

It is important to study the stability of the proposed algorithms to ensure that agents do not have motivation to change their behavior during the HGMP, i.e., to make sure that agents can make optimal decisions in the scenarios and do not vacillate in negotiations and task accomplishments. In this section, we study the stability of the proposed algorithms in both reverse auction and auction scenarios.


### 4.1. The First Scenario: Reverse Auction

Consider a hunter and a gatherer agent whose preferences over outcomes are given by the utility functionsUhtkh and Ugtkg, respectively. As shown in Figure 3, the model in which agents negotiate in the first scenario is a simplified reverse auction or bargaining process. According to assumption (6), each agent obtains sufficient information about all actions and utilities. Thus, the model turns into a perfect-information extensive form game which resembles a sharing game. We know that every (finite) perfect-information game in the extensive form has a pure-strategy Nash equilibrium (PSNE) [33]. However, the existence of PSNE does not necessarily ensure that the output of the first scenario is a PSNE. It strongly depends on the decision-making algorithm of each agent. Therefore, we need to prove if the output of the proposed reasoning mechanisms in the first scenario is a PSNE.According to the proposed reasoning mechanisms, each agent calculates a profit interval to make the most profitable decision. To be specific,aih makes its best response by making offers that fall into its profit interval. Similarly, ajg makes its best response to the scenario by accepting the offers within its profit interval. In other words, the decision of each agent is its best possible response to the scenario, and it knows that the counterpart agent is also making its best response. We know that the strategy profile in which each agent is making its best response to another agent is a PSNE [33]. Consequently, the HGMP’s outcome is a PSNE in the first scenario.Although the model itself ensures the existence of PSNE and the reasoning mechanisms’ outcome is a PSNE, the desirability of PSNE is still a considerable concern. The following numerical example explains the details on how scaling parameters can affect the PSNE in the first scenario.In the reverse auction scenario, pure strategies foraih and ajg are defined as Sh=Oi,jk,Oi,j′k,Oi,j″k and Sg=AAA,AAR,ARA,ARR,RAA,RAR,R,R,A,RRR, respectively, where A and R stand for acceptance and rejection actions of ajg, respectively. Now, let us assume that Ih=Ig=Iex=10, αh=βh=1, and αg=βg=1. If we have ck,hh=8 and ck,jg=10 for accomplishing Tk, then offers are calculated from (8), as follows: Oi,jk=0, Oi,j′k=5, and Oi,j″k=10. Hence, {(A, A, A), offer1} is one of the equilibria; that is, ajg accepts the first offer which results Ugtkg<0. On the contrary, if we only change scaling parameters of ajg such that αg=βg=0.9, then {(A, A, A), offer1} is no longer a PSNE. Instead, {(R, R, R), offer1} is a PSNE; that is, ajg rejects the first offer. In conclusion, the desirability of PSNE in the first scenario can be guaranteed by designating appropriate scaling parameters αh, βh, αg, and βg.


### 4.2. The Second Scenario: Auction

In the second scenario, we investigate the existence of NE by a theorem based on the CPM and UPM concepts. We investigate 3 conditions to find the NE in an auction process. We will prove the theorem by contradiction; that is, we show that no agent, involving in an auction scenario, has a motivation to deviate from a strategy profile which satisfies all 3 conditions.Theorem 1.
Consider the HGMP in the second scenario associated with the second-price sealed-bid auction with participation of a hunter and gatherers whose preferences over outcome are given by the utility functionsUhtkh and Ugtkg, respectively. Then, b is a Nash equilibrium if and only if conditions (i) and (ii) are satisfied for w=argsmaxb and condition (iii) is satisfied for the hunter agent:(i)
maxj≠wαgIg+βgIex−ck,jg≤bw, i.e., the winner submitted a sufficiently high bid(ii)
maxj≠wbj≤αgIg+βgIex−ck,wg, i.e., the winner’s valuation is sufficiently high(iii)
αhIh+βhPk,ihIex−ck,ih≥0, i.e., the second highest bid satisfies the minimum bid determined by the hunterProof.
If (i) does not hold,maxj≠wαgIg+βgIex−ck,jg>bw, then aj≠wg has an interval to increase its bid, klowg,Pk,wg, in which it can lower its share to klowg and place even a higher bid than bw and win the auction. Hence, aj≠wg has a motivation to deviate and increase its payoff. If (ii) does not hold, maxj≠wbj>αgIg+βgIex−ck,wg, then for awg, denoted as the winner, we have Ugtkg<0; that is, its payoff is negative. Therefore, it can deviate by submitting a losing bid and increasing its payoff to 0. Finally, if (iii) does not hold, αhIh+βhPk,ihIex−ck,ih<0, then the hunter agent’s payoff is negative for the second highest bid. Thus, it can deviate by rejecting all bids and increase its payoff to 0 because it has a strong motivation to hold another auction in the following iterations and avoid a negative payoff.Nevertheless, the existence of NE does not necessarily ensure that the scenario’s output is a NE. It strongly depends on the decision-making algorithm of each agent. In this regard, we know that each gatherer involving in the auction scenario places a bid according to (9). This means each gatherer agent bids its own valuation, i.e., bj=vj. Accordingly, conditions (i) and (ii) are always true because not only the winner has placed the highest bid among all bidders but also it does not have a negative payoff. Besides, the hunter agent is using (10) to choose the winning bidder and (11) to verify the minimum requirement satisfaction of the second highest bid. Hence, condition (iii) is also true. As a conclusion, according to Theorem 1 and also the decision-making algorithms of all agents participating in an auction, the result of the auction scenario is a NE.


## 4.1. The First Scenario: Reverse Auction

Consider a hunter and a gatherer agent whose preferences over outcomes are given by the utility functionsUhtkh and Ugtkg, respectively. As shown in Figure 3, the model in which agents negotiate in the first scenario is a simplified reverse auction or bargaining process. According to assumption (6), each agent obtains sufficient information about all actions and utilities. Thus, the model turns into a perfect-information extensive form game which resembles a sharing game. We know that every (finite) perfect-information game in the extensive form has a pure-strategy Nash equilibrium (PSNE) [33]. However, the existence of PSNE does not necessarily ensure that the output of the first scenario is a PSNE. It strongly depends on the decision-making algorithm of each agent. Therefore, we need to prove if the output of the proposed reasoning mechanisms in the first scenario is a PSNE.According to the proposed reasoning mechanisms, each agent calculates a profit interval to make the most profitable decision. To be specific,aih makes its best response by making offers that fall into its profit interval. Similarly, ajg makes its best response to the scenario by accepting the offers within its profit interval. In other words, the decision of each agent is its best possible response to the scenario, and it knows that the counterpart agent is also making its best response. We know that the strategy profile in which each agent is making its best response to another agent is a PSNE [33]. Consequently, the HGMP’s outcome is a PSNE in the first scenario.Although the model itself ensures the existence of PSNE and the reasoning mechanisms’ outcome is a PSNE, the desirability of PSNE is still a considerable concern. The following numerical example explains the details on how scaling parameters can affect the PSNE in the first scenario.In the reverse auction scenario, pure strategies foraih and ajg are defined as Sh=Oi,jk,Oi,j′k,Oi,j″k and Sg=AAA,AAR,ARA,ARR,RAA,RAR,R,R,A,RRR, respectively, where A and R stand for acceptance and rejection actions of ajg, respectively. Now, let us assume that Ih=Ig=Iex=10, αh=βh=1, and αg=βg=1. If we have ck,hh=8 and ck,jg=10 for accomplishing Tk, then offers are calculated from (8), as follows: Oi,jk=0, Oi,j′k=5, and Oi,j″k=10. Hence, {(A, A, A), offer1} is one of the equilibria; that is, ajg accepts the first offer which results Ugtkg<0. On the contrary, if we only change scaling parameters of ajg such that αg=βg=0.9, then {(A, A, A), offer1} is no longer a PSNE. Instead, {(R, R, R), offer1} is a PSNE; that is, ajg rejects the first offer. In conclusion, the desirability of PSNE in the first scenario can be guaranteed by designating appropriate scaling parameters αh, βh, αg, and βg.


## 4.2. The Second Scenario: Auction

In the second scenario, we investigate the existence of NE by a theorem based on the CPM and UPM concepts. We investigate 3 conditions to find the NE in an auction process. We will prove the theorem by contradiction; that is, we show that no agent, involving in an auction scenario, has a motivation to deviate from a strategy profile which satisfies all 3 conditions.Theorem 1.
Consider the HGMP in the second scenario associated with the second-price sealed-bid auction with participation of a hunter and gatherers whose preferences over outcome are given by the utility functionsUhtkh and Ugtkg, respectively. Then, b is a Nash equilibrium if and only if conditions (i) and (ii) are satisfied for w=argsmaxb and condition (iii) is satisfied for the hunter agent:(i)
maxj≠wαgIg+βgIex−ck,jg≤bw, i.e., the winner submitted a sufficiently high bid(ii)
maxj≠wbj≤αgIg+βgIex−ck,wg, i.e., the winner’s valuation is sufficiently high(iii)
αhIh+βhPk,ihIex−ck,ih≥0, i.e., the second highest bid satisfies the minimum bid determined by the hunterProof.
If (i) does not hold,maxj≠wαgIg+βgIex−ck,jg>bw, then aj≠wg has an interval to increase its bid, klowg,Pk,wg, in which it can lower its share to klowg and place even a higher bid than bw and win the auction. Hence, aj≠wg has a motivation to deviate and increase its payoff. If (ii) does not hold, maxj≠wbj>αgIg+βgIex−ck,wg, then for awg, denoted as the winner, we have Ugtkg<0; that is, its payoff is negative. Therefore, it can deviate by submitting a losing bid and increasing its payoff to 0. Finally, if (iii) does not hold, αhIh+βhPk,ihIex−ck,ih<0, then the hunter agent’s payoff is negative for the second highest bid. Thus, it can deviate by rejecting all bids and increase its payoff to 0 because it has a strong motivation to hold another auction in the following iterations and avoid a negative payoff.Nevertheless, the existence of NE does not necessarily ensure that the scenario’s output is a NE. It strongly depends on the decision-making algorithm of each agent. In this regard, we know that each gatherer involving in the auction scenario places a bid according to (9). This means each gatherer agent bids its own valuation, i.e., bj=vj. Accordingly, conditions (i) and (ii) are always true because not only the winner has placed the highest bid among all bidders but also it does not have a negative payoff. Besides, the hunter agent is using (10) to choose the winning bidder and (11) to verify the minimum requirement satisfaction of the second highest bid. Hence, condition (iii) is also true. As a conclusion, according to Theorem 1 and also the decision-making algorithms of all agents participating in an auction, the result of the auction scenario is a NE.


## 5. Simulation Results

In this section, we present simulation results to (1) validate the fairness of the proposed algorithms, i.e., to ensure that the overall workload is distributed equally among agents of both types, by comparing agents’ effectiveness in a set of experiments and analyzing the results by pairedT-test and ANOVA [34] methods, (2) study the effect of profit margins on the total effectiveness of the HGMP, (3) demonstrate the efficacy of the proposed multitask-planning algorithm for gatherers by investigating its effect on the HGMP’s total effectiveness, and (4) verify the functionality of the hunter-and-gatherer scheme, i.e., considering each task comprising two sequential exploration and completion subtasks, by a comparison between the HGMP and a basic alternative method in which each agent does both hunting and gathering tasks itself.To simulate the proposed approaches, we developed a multirobot simulation platform in MATLAB from scratch. In this platform, we can implement the simulations on any custom map, while the number of agents of each type is adjustable. We provide some basic functions for each type of agent to enable them maneuver over the determined environment. For gatherers, we utilized theA∗-based motion planning algorithm which enables them to move along two points in a grid environment. In addition, we provided a basic frontier-based exploration algorithm [35] for hunters. Besides, the number of tasks is also adjustable while they get located randomly over the environment. As a matter of fact, we also provided the perpetual mode for implantation of the simulations where for each gathered task, another task will be distributed randomly in the environment. Accordingly, at each iteration, there are a certain number of tasks available in the environment which is adjustable for each mission. Furthermore, in the perpetual mode, each explored and known grid of the environment turns into an unknown grid after certain iterations. The perpetual mode helps the analysis be done in a much more accurate and evidence-based way.All simulations have been executed under the following conditions: (1) the environment is sectioned as aneL×eWgrid of tiles where eL=eW=100, (2) the quantities of each type of agent are adjusted as nh=4 and ng=2, (3) there are always mp=50 tasks in the environment, (4) the maximum number of iterations is determined as τmax=1000, (5) the rewards are assigned to be Ih=Ig=Iex=140, and (6) we considered the weighting parameters as ρh/ρg=0.2.


### 5.1. Fairness of the HGMP

To demonstrate that the accomplishment workload is distributed equally for each type of agent, the concept of fairness is introduced. To that end, we define an effectiveness factor for each agent of both types based on their costs and accomplishment. Then, using the statistical analysis, we prove the fairness of the HGMP by comparing effectiveness of different agents of each type. Letηih and γih denote the effectiveness of aih and the number of tasks hunted by the agent, respectively, as follows:(12)ηih=γih∑k=1mck,ihxki.Similarly,ηjg and γjgdenote the effectiveness of ajg and the total number of tasks gathered by the agent, respectively, such that(13)ηjg=γjg∑k=1mck,jgykj.Figure6(a)shows the statistical results of ηih for all hunters in 200 missions. As nh>2, an ANOVA test has been applied to the collected data to statistically prove the fairness of the HGMP for hunters. The ANOVA test has been applied as follows: H0:μ1h=μ2h=μ3h=μ4h, H1:μ1h≠μih, and α=0.05, where μih denotes the average of ηih for aih in 200 tests and α denotes the significance level. According to the results of the ANOVA test, F=0.377, F−crit=2.61, and pvalue=0.77. Since F<F−crit and pvalue>α, we have to retain the null hypothesis. Thus, it has been proved that μ1h=μ2h=μ3h=μ4h, which means that there is no significant difference between averages of hunters’ effectiveness in 200 tests.Figure 6
Investigating the fairness of the HGMP for (a) hunter agents and (b) gatherer agents. Statistically, for each type of agent, there is no significant difference in agents’ effectiveness that demonstrates the fairness of the HGMP.
(a)
(b)In addition, asng=2, a paired T-test has been applied to the data to investigate the fairness of the HGMP for gatherers. The hypothesis testing has been done in a manner such that H0:μ1g−μ2g=D0, H1:μ1g−μ2g≠D0, D0=0, ns=200, dof=199, and α=0.05. According to the test, pvalue=0.315. Since pvalue>α, we must retain the null hypothesis. Therefore, it has been proven that μ1g−μ2g=D0=0, as it is illustrated in Figure 6(b), which means that there is no significant difference between averages of gatherers’ effectiveness in 200 tests.Both statistical analyses indicate that all agents of the same type behave analogously under similar characteristics. In fact, this analysis numerically validates the Nash equilibrium analysis proved for the HGMP. It means that if the fairness concept investigated above is not valid for the HGMP and favors certain agents unfairly, then there are strong motivations for other agents to deviate from the proposed negotiation structure.


### 5.2. Effects of Agents’ Profit Margins on Mission’s Effectiveness

The effects of scaling parameters of profit margins,αg, βg, αh, and βh, on the total effectiveness of the HGMP need to be investigated in order to show the functionality of the CPM and UPM for both types of agents. To that end, we define an effectiveness factor for the HGMP, ηt, which is the ratio of the total number of completed tasks, γt, and the collective cost of the whole mission, Ct, as follows:(14)Ct=ρh∑i=1nh∑k=1mck,ihxki+ρg∑j=1ng∑k=1mck,jgykj,(15)γt=∑j=1ngγjg,(16)ηt=γTCT.We ran the algorithms for all values ofαg and βg that are multiples of 0.025 such that 0≤αg≤0.5 and 0≤βg≤0.5, while αh=βh=0.35. ηt has been calculated for each set of values for αg and βg, as illustrated in Figure 7. Basically, this figure explains the correlation between the total effectiveness of the HGMP and the profit margin parameters of gatherers. The yellow area shows the area in which the total effectiveness is maximum. In this figure, the horizontal and vertical axes are αg and βg, respectively, i.e., the scaling parameters of gatherers, and the color mapping represents the total effectiveness of the HGMP, i.e., ηt. According to the results, ηt is vanishingly small when αg+βg<0.2 which means agents cannot reach an agreement for completing the detected tasks. Furthermore, ηt reaches its maximum when 0.2<αg+βg<0.5. Next, ηt falls gradually when αg+βg>0.5 because each gatherer’s CPM and UPM are large so that the agent does not fall into state 3 and easily reach any agreement. As a result, each gatherer accomplishes a significant number of tasks inefficiently which reduces ηt.Figure 7
Investigating the effect of gatherers’ CPM and UPM on the HGMP’s effectivenessηt: (a) contour plot of the results using a polynomial curve fitting and (b) polynomial curve fitting.
(a)
(b)In the same way, we ran the algorithms for all values ofαh and βh that are multiples of 0.05 such that 0≤αh≤1 and 0≤βh≤1, while αg=βg=0.15. ηt has been calculated for each set of values for αh and βh, as illustrated in Figure 8. Basically, this figure explains the correlation between the total effectiveness of the HGMP and the profit margin parameters of hunters. The yellow area shows the area in which the total effectiveness is maximum. In this figure, the horizontal and vertical axes are αh and βh, respectively, i.e., the scaling parameters of hunters, and the color mapping represents the total effectiveness of the HGMP, i.e., ηt. Accordingly, ηt is too low when αh+βg<0.4 approximately, which means the CPM and UPM of hunters are too small and only a few agreements are reached. Then, for αh+βg>0.4, ηt increases gradually to reach its maximum and then again decreases.Figure 8
Effect of hunters’ CPM and UPM on the HGMP’s effectivenessηt: (a) contour plot of the results using a polynomial curve fitting and (b) polynomial curve fitting.
(a)
(b)According to the proposed reasoning mechanism, when the scaling parameter of an agent’s CPM decreases, the agent gets less confident. And when the scaling parameter of an agent’s UPM increases, the agent gets less conservative. In this regard, for both types of agents, the best strategy to reach the maximum ofηt is neither being completely confident nor being fully conservative, but a combination of both leads to the optimum result.The oblique yellow area in Figure7(b), exposing the maximum values of ηt, is much narrower than the one in Figure 8(b). It shows that the CPMs and UPMs of gatherers have a more distinct influence on ηt than the ones of hunters. The rationale behind this dissimilarity is that hunters rely on their CPMs and UPMs after hunting a task, i.e., after accomplishing a task, and then consider them only for finding a gatherer to complete the task. On the contrary, gatherers consider their CPMs and UPMs before gathering a task, i.e., before any accomplishment. Consequently, this difference causes a much more distinct influence of gatherers’ CPMs and UPMs on ηt.


### 5.3. The Effect of Multitask Planning on the HGMP’s Effectiveness

In this section, we aim to study the effect of the proposed multitask-planning algorithm for gatherers on the total effectiveness of the HGMP defined in (16). Accordingly, we investigate the effect of qmax, which is the queue size of each gatherer, on ηt. To that end, we ran 200 missions for each value of qmax, varying from 1 to 10, and measured ηt in each mission, as illustrated in Figure 9.Figure 9
Investigating the effect ofqmax on ηt. The results show a significant increase in ηt when we increase qmax from 1 to 10.To understand how muchηt increase when qmax changes from qmax=1 to qmax=10, we applied a paired T-test to the two of collected data sets. The first data set contains 200 measures of ηt for qmax=1, and the second data set comprises 200 measures of ηt for qmax=10. The test has been conducted considering H0:μ2−μ1≤D0, H1:μ2−μ1>D0, D0=0.7μ1, ns=200, dof=199, and α=0.05, where μ1 and μ2 denote the average of ηt for the first and second data sets, respectively. According to the test result, pvalue=0.0004, t=3.39, and t0.05,199=1.65. Since t>t0.05,199and pvalue<α, we reject H0. Therefore, the results prove that ηt increases more than 70% by changing qmax from 1 to 10. Moreover, the results also show that the HGMP remains fair for gatherer agents by increasing qmax. Figure 10 demonstrates that there is no significant difference between effectiveness of two gatherers for each value of qmax.Figure 10
Fairness of the HGMP for gatherer agents for each value ofqmax. The results demonstrate that the workload is still distributed equally on both gatherers when qmax increases.Besides, Figure11 shows how the HGMP’s total effectiveness converges for different values of qmax in a manner such that qmax=1, qmax=4, and qmax=10. According to the results, by increasing the value of qmax, ηt becomes more variant and the convergence time decreases, while ηt enhances significantly as was proven before.Figure 11
Convergence of the HGMP’s total effectiveness forqmax=1, qmax=4, and qmax=10, during τmax=1000 iterations.


### 5.4. Functionality Validation of the HGMP by a Comparison

In this section, we are intended to analyze the functionality of the proposed hunter-and-gatherer scheme. As discussed before, we consider a dynamic problem to be a TA:SP problem where each task is composed of two sequential detection and completion subtasks. Although we have discussed different aspects of the proposed approach in the previous sections, here we want to explicitly compare the proposed approach with an alternative approach in which there is only one type of agent doing both exploration and completion of tasks together.According to the rationale behind the hunter-and-gatherer approach, hunters must be more agile and cost-efficient in exploration and maneuvering. Therefore, we first plotted the total effectiveness of the HGMP with respect toρh/ρg which ranges from ρh≪ρg, i.e., ρh/ρg=0, to ρh≈ρg, i.e., ρh/ρg=1. Second, we ran the explained alternative approach to be able to judge the HGMP’s functionality. Since in this approach there is no hunter-and-gatherer scheme, we only have one type of agent and the obtained total effectiveness is dependent on the ratioρh/ρg. By this comparison, we basically wanted to answer the following question: Is the HGMP profitable compared to the alternative method? Figure 12 shows the results of the implemented simulations for that purpose, as explained above. Thus, the answer is that it depends to the ratio ρh/ρg and this is why we ended up in having a criterion for the HGMP to be profitable. According to the results, for ρh/ρg<0.2, the HGMP has distinct advantage in terms of ηt over the alternative model for any value of qmax. Furthermore, the HGMP still remains advantageous for ρh/ρg<0.6. Consequently, it is economic to employ the HGMP for the stated dynamic problem if and only if we utilize the hunter-and-gatherer agent that satisfies ρh/ρg<0.6. In other words, if we employ two robots from different types as a hunter and gatherer such that the hunter’s cost for following a certain path is less than 0.6 of the gatherer’s cost for following the same path, then employing the HGMP will be profitable. Considering the USAR example, the hunter can be a small UAV, while the gatherer should necessarily be a heavy-duty UGV. If we consider the cost as the power consumption, then the ρh/ρg<0.6 criterion will be satisfied easily.Figure 12
Comparing the HGMP with an alternative model where each agent does both exploration and completion together.A screen capture video of the simulation results can be found as a supplementary material along with this paper, by using the YouTube link “youtu.be/HJuiP5DMZfo,” or by scanning the following QR code.


## 5.1. Fairness of the HGMP

To demonstrate that the accomplishment workload is distributed equally for each type of agent, the concept of fairness is introduced. To that end, we define an effectiveness factor for each agent of both types based on their costs and accomplishment. Then, using the statistical analysis, we prove the fairness of the HGMP by comparing effectiveness of different agents of each type. Letηih and γih denote the effectiveness of aih and the number of tasks hunted by the agent, respectively, as follows:(12)ηih=γih∑k=1mck,ihxki.Similarly,ηjg and γjgdenote the effectiveness of ajg and the total number of tasks gathered by the agent, respectively, such that(13)ηjg=γjg∑k=1mck,jgykj.Figure6(a)shows the statistical results of ηih for all hunters in 200 missions. As nh>2, an ANOVA test has been applied to the collected data to statistically prove the fairness of the HGMP for hunters. The ANOVA test has been applied as follows: H0:μ1h=μ2h=μ3h=μ4h, H1:μ1h≠μih, and α=0.05, where μih denotes the average of ηih for aih in 200 tests and α denotes the significance level. According to the results of the ANOVA test, F=0.377, F−crit=2.61, and pvalue=0.77. Since F<F−crit and pvalue>α, we have to retain the null hypothesis. Thus, it has been proved that μ1h=μ2h=μ3h=μ4h, which means that there is no significant difference between averages of hunters’ effectiveness in 200 tests.Figure 6
Investigating the fairness of the HGMP for (a) hunter agents and (b) gatherer agents. Statistically, for each type of agent, there is no significant difference in agents’ effectiveness that demonstrates the fairness of the HGMP.
(a)
(b)In addition, asng=2, a paired T-test has been applied to the data to investigate the fairness of the HGMP for gatherers. The hypothesis testing has been done in a manner such that H0:μ1g−μ2g=D0, H1:μ1g−μ2g≠D0, D0=0, ns=200, dof=199, and α=0.05. According to the test, pvalue=0.315. Since pvalue>α, we must retain the null hypothesis. Therefore, it has been proven that μ1g−μ2g=D0=0, as it is illustrated in Figure 6(b), which means that there is no significant difference between averages of gatherers’ effectiveness in 200 tests.Both statistical analyses indicate that all agents of the same type behave analogously under similar characteristics. In fact, this analysis numerically validates the Nash equilibrium analysis proved for the HGMP. It means that if the fairness concept investigated above is not valid for the HGMP and favors certain agents unfairly, then there are strong motivations for other agents to deviate from the proposed negotiation structure.


## 5.2. Effects of Agents’ Profit Margins on Mission’s Effectiveness

The effects of scaling parameters of profit margins,αg, βg, αh, and βh, on the total effectiveness of the HGMP need to be investigated in order to show the functionality of the CPM and UPM for both types of agents. To that end, we define an effectiveness factor for the HGMP, ηt, which is the ratio of the total number of completed tasks, γt, and the collective cost of the whole mission, Ct, as follows:(14)Ct=ρh∑i=1nh∑k=1mck,ihxki+ρg∑j=1ng∑k=1mck,jgykj,(15)γt=∑j=1ngγjg,(16)ηt=γTCT.We ran the algorithms for all values ofαg and βg that are multiples of 0.025 such that 0≤αg≤0.5 and 0≤βg≤0.5, while αh=βh=0.35. ηt has been calculated for each set of values for αg and βg, as illustrated in Figure 7. Basically, this figure explains the correlation between the total effectiveness of the HGMP and the profit margin parameters of gatherers. The yellow area shows the area in which the total effectiveness is maximum. In this figure, the horizontal and vertical axes are αg and βg, respectively, i.e., the scaling parameters of gatherers, and the color mapping represents the total effectiveness of the HGMP, i.e., ηt. According to the results, ηt is vanishingly small when αg+βg<0.2 which means agents cannot reach an agreement for completing the detected tasks. Furthermore, ηt reaches its maximum when 0.2<αg+βg<0.5. Next, ηt falls gradually when αg+βg>0.5 because each gatherer’s CPM and UPM are large so that the agent does not fall into state 3 and easily reach any agreement. As a result, each gatherer accomplishes a significant number of tasks inefficiently which reduces ηt.Figure 7
Investigating the effect of gatherers’ CPM and UPM on the HGMP’s effectivenessηt: (a) contour plot of the results using a polynomial curve fitting and (b) polynomial curve fitting.
(a)
(b)In the same way, we ran the algorithms for all values ofαh and βh that are multiples of 0.05 such that 0≤αh≤1 and 0≤βh≤1, while αg=βg=0.15. ηt has been calculated for each set of values for αh and βh, as illustrated in Figure 8. Basically, this figure explains the correlation between the total effectiveness of the HGMP and the profit margin parameters of hunters. The yellow area shows the area in which the total effectiveness is maximum. In this figure, the horizontal and vertical axes are αh and βh, respectively, i.e., the scaling parameters of hunters, and the color mapping represents the total effectiveness of the HGMP, i.e., ηt. Accordingly, ηt is too low when αh+βg<0.4 approximately, which means the CPM and UPM of hunters are too small and only a few agreements are reached. Then, for αh+βg>0.4, ηt increases gradually to reach its maximum and then again decreases.Figure 8
Effect of hunters’ CPM and UPM on the HGMP’s effectivenessηt: (a) contour plot of the results using a polynomial curve fitting and (b) polynomial curve fitting.
(a)
(b)According to the proposed reasoning mechanism, when the scaling parameter of an agent’s CPM decreases, the agent gets less confident. And when the scaling parameter of an agent’s UPM increases, the agent gets less conservative. In this regard, for both types of agents, the best strategy to reach the maximum ofηt is neither being completely confident nor being fully conservative, but a combination of both leads to the optimum result.The oblique yellow area in Figure7(b), exposing the maximum values of ηt, is much narrower than the one in Figure 8(b). It shows that the CPMs and UPMs of gatherers have a more distinct influence on ηt than the ones of hunters. The rationale behind this dissimilarity is that hunters rely on their CPMs and UPMs after hunting a task, i.e., after accomplishing a task, and then consider them only for finding a gatherer to complete the task. On the contrary, gatherers consider their CPMs and UPMs before gathering a task, i.e., before any accomplishment. Consequently, this difference causes a much more distinct influence of gatherers’ CPMs and UPMs on ηt.


## 5.3. The Effect of Multitask Planning on the HGMP’s Effectiveness

In this section, we aim to study the effect of the proposed multitask-planning algorithm for gatherers on the total effectiveness of the HGMP defined in (16). Accordingly, we investigate the effect of qmax, which is the queue size of each gatherer, on ηt. To that end, we ran 200 missions for each value of qmax, varying from 1 to 10, and measured ηt in each mission, as illustrated in Figure 9.Figure 9
Investigating the effect ofqmax on ηt. The results show a significant increase in ηt when we increase qmax from 1 to 10.To understand how muchηt increase when qmax changes from qmax=1 to qmax=10, we applied a paired T-test to the two of collected data sets. The first data set contains 200 measures of ηt for qmax=1, and the second data set comprises 200 measures of ηt for qmax=10. The test has been conducted considering H0:μ2−μ1≤D0, H1:μ2−μ1>D0, D0=0.7μ1, ns=200, dof=199, and α=0.05, where μ1 and μ2 denote the average of ηt for the first and second data sets, respectively. According to the test result, pvalue=0.0004, t=3.39, and t0.05,199=1.65. Since t>t0.05,199and pvalue<α, we reject H0. Therefore, the results prove that ηt increases more than 70% by changing qmax from 1 to 10. Moreover, the results also show that the HGMP remains fair for gatherer agents by increasing qmax. Figure 10 demonstrates that there is no significant difference between effectiveness of two gatherers for each value of qmax.Figure 10
Fairness of the HGMP for gatherer agents for each value ofqmax. The results demonstrate that the workload is still distributed equally on both gatherers when qmax increases.Besides, Figure11 shows how the HGMP’s total effectiveness converges for different values of qmax in a manner such that qmax=1, qmax=4, and qmax=10. According to the results, by increasing the value of qmax, ηt becomes more variant and the convergence time decreases, while ηt enhances significantly as was proven before.Figure 11
Convergence of the HGMP’s total effectiveness forqmax=1, qmax=4, and qmax=10, during τmax=1000 iterations.


## 5.4. Functionality Validation of the HGMP by a Comparison

In this section, we are intended to analyze the functionality of the proposed hunter-and-gatherer scheme. As discussed before, we consider a dynamic problem to be a TA:SP problem where each task is composed of two sequential detection and completion subtasks. Although we have discussed different aspects of the proposed approach in the previous sections, here we want to explicitly compare the proposed approach with an alternative approach in which there is only one type of agent doing both exploration and completion of tasks together.According to the rationale behind the hunter-and-gatherer approach, hunters must be more agile and cost-efficient in exploration and maneuvering. Therefore, we first plotted the total effectiveness of the HGMP with respect toρh/ρg which ranges from ρh≪ρg, i.e., ρh/ρg=0, to ρh≈ρg, i.e., ρh/ρg=1. Second, we ran the explained alternative approach to be able to judge the HGMP’s functionality. Since in this approach there is no hunter-and-gatherer scheme, we only have one type of agent and the obtained total effectiveness is dependent on the ratioρh/ρg. By this comparison, we basically wanted to answer the following question: Is the HGMP profitable compared to the alternative method? Figure 12 shows the results of the implemented simulations for that purpose, as explained above. Thus, the answer is that it depends to the ratio ρh/ρg and this is why we ended up in having a criterion for the HGMP to be profitable. According to the results, for ρh/ρg<0.2, the HGMP has distinct advantage in terms of ηt over the alternative model for any value of qmax. Furthermore, the HGMP still remains advantageous for ρh/ρg<0.6. Consequently, it is economic to employ the HGMP for the stated dynamic problem if and only if we utilize the hunter-and-gatherer agent that satisfies ρh/ρg<0.6. In other words, if we employ two robots from different types as a hunter and gatherer such that the hunter’s cost for following a certain path is less than 0.6 of the gatherer’s cost for following the same path, then employing the HGMP will be profitable. Considering the USAR example, the hunter can be a small UAV, while the gatherer should necessarily be a heavy-duty UGV. If we consider the cost as the power consumption, then the ρh/ρg<0.6 criterion will be satisfied easily.Figure 12
Comparing the HGMP with an alternative model where each agent does both exploration and completion together.A screen capture video of the simulation results can be found as a supplementary material along with this paper, by using the YouTube link “youtu.be/HJuiP5DMZfo,” or by scanning the following QR code.


## 6. Conclusion

Inspired by the problem of “MRTA in an unknown environment,” we proposed the idea of task allocation based on coupling and cooperation between complementary teams in a hunter-and-gatherer scheme. Furthermore, this work presented distributed reasoning mechanisms relying on the notions of certainty and uncertainty profit margins in which levels of confidence and conservativeness are modeled, while an effective multitask-planning algorithm for gatherers is proposed that allows them to queue multiple tasks for finding the optimal solution for completing a group of tasks rather than doing one by one. By comparing the proposed hunter-and-gatherer scheme with an alternative method, where there is only one type of agent doing both exploration and completion of tasks together, we established a criterion to judge profitability of the proposed method. Examining the real-world problems mentioned earlier confirms that the profitability criterion is reasonably satisfiable. We also found that the extreme behavior of an agent, being too confident or too conservative, hurts the total effectiveness of the mission. Furthermore, statistical analysis demonstrates a significant improvement of total effectiveness effected by the multitask-planning algorithm. However, while computational complexities for execution of the multitask-planning algorithm manifold by increasing the size of an agent’s queue size, the total effectiveness of the HGMP does not increase linearly.Future works will consider the problem of adjusting the scaling parameters by an agent during a mission to achieve the optimal performance from both agent and team points of view. We also intend to develop a multirobot exploration algorithm based on the notions of profit margins in the context of dynamic MRTA problems and investigate the effect of different multirobot exploration algorithms on the HGMP.



---

*Source: 1752571-2020-03-26.xml*