Sage Journals: Discover world-class research

Abstract

This article proposes a framework for competency adjustment and workload balancing in multirobot task allocation. Competency represents the ability of a robot to execute a task in terms of quality and cost, and workload balancing denotes distribution of workload among robots. This framework considers the quality and cost of a robot for a task and adjusts them in accordance with environmental changes. For workload balancing, the framework utilizes the concept of subsidy to encourage participation from the less active members of the robot team. The proposed framework is implemented in a simulated cleaning mission. Simulation results demonstrate that this framework can adjust the competency in accordance with environmental changes and distribute workload among robots in a balanced manner.

Keywords

Decentralized task allocation multirobot systems competency adjustment workload balancing

Introduction

Coordination of multiple robots has become a significant research area in various application domains. One of the fundamental problems in multirobot system is the task allocation problem, which has received significant and increasing interest from the research community.^1,2 Market-based coordination approach has become popular owing to its low computational and communication overhead with high scalability.^3,4 It is based on market economy principles in which each individual attempts to maximize its profit, thus leading to the redistribution of resources and the efficient production of output. In general, market-based algorithms use the auction protocol, that is, auction announcement, bid valuation and submission, winner determination, award acceptance/rejection, and auction closing, in task allocation.^5,6 Most market-based approaches require manageable communications such that the communication overhead does not prohibit them from providing efficient solutions as the size of team increases.^6,7 The market mechanisms also scale well in applications where a mission can be decomposed into tasks that can be independently carried out by a single robot or a small group of robots. Owing to these advantages, market-based approaches have been widely used in multirobot coordination. Gerkey and Mataric implemented an auction-based task allocation system, MURDOCH, in which the publish/subscribe communication model was used for efficient resource usage.⁸ Dias developed Traderbots, in which auctions are conducted in a peer-to-peer fashion, and any robot is capable of taking on the roles of auctioneer or bidder when required.⁹ Choi et al. proposed a market-based approach for the coordination of a fleet of autonomous vehicles in a decentralized manner.¹⁰

Although most of the aforementioned market-based approaches consider cost, such as energy, travel distance, and task completion time, some of them consider multiple properties, such as quality and cost in task allocation.^11
–13 In these works, each bidder is responsible for a bid generation process, that is, the process of combining properties, such as quality and cost, to generate the robot’s bid for the auctioned task. Once the bid is generated by the bidder, the conventional auction process is applied wherein the bidders submit their bids, and the auctioneer allocates the task to the winner with the best bid. Thus, the bid generation process and the auction process were treated independently. However, there are three main problems when the bid generation process is independently performed by the bidder. First, it is difficult to determine suitable scale factors for the properties. As quality and cost have different units and ranges, scale factors are required to combine them. However, determining unbiased scale factors that can make both the quality and cost have an equal effect on the bid is a difficult problem. As market-based approaches allocate tasks based solely on the bids of the robots, improper scale factors might result in inefficient task performance. Second, the relative difference among the bidders’ properties is not revealed. As the auctioneer determines the winner solely based on the bids, the relative difference among the bidders’ properties should be revealed for efficient task allocation. Third, it is difficult to adjust the relative importance of the properties. In general, all bidders should use the same adjusting factors in bid generation for fair competition. Thus, they either use the same predefined adjusting factor or communicate with each other to decide the same adjusting factor. If a predefined adjusting factor is used, it is fixed such that the robots are not allowed to change it in any case. Thus, the relative importance of the properties is not allowed to be adjusted during the mission. If the adjusting factor is through communication, it requires fully connected communication links among all bidders as each bidder must have the same adjusting factor. Such a requirement is impractical in realistic networks with limited communication range and additional negotiation process among the bidders is required to converge to the same adjusting factor.

In addition to considering multiple properties in task allocation, the workload or energy balancing problem has been widely studied in multirobot coordination. The motivation of workload balancing in task allocation can be summarized in the following three ways. First, the workload balancing extends the lifetime of the distributed system by minimizing the overutilization of some of the robots and underutilization of others. Second, it improves the response time of the robots to service requests. Third, it achieves higher resource utilization, larger throughput, and less response time. Wu et al. proposed a hybrid task allocation method to consider the energy resource constraints of robots.¹⁴ They incorporated the market-based approach into the Gini coefficient–based method to flexibly optimize the number of completed tasks and resource consumption. Lukic et al. proposed a multirobot task allocation method for dispatch tasks in an energy-balanced way.¹⁵ Their centralized and distributed algorithms attempt to minimize the travel paths of the robots and maximize the number of completed tasks. Although both approaches consider energy balancing in task allocation, they do not consider balancing between the the energy distribution of the robots and the quality of their task performance, such as accuracy and delicacy in task execution, which require high-performance robots to spend longer time and more energy. In the case of market-based approaches, the workload balancing problem has not been widely considered. This is because the market-based scheme is based on the concept of free market economy in which it is believed that maximizing the profit of an individual automatically leads to the redistribution of resources and efficient production of output of the system.⁵ Consequently, most tasks are likely to be allocated to highly competent robots, whereas the robots with low competency would have difficulties in participating in the mission although they have sufficient ability and energy to perform the tasks. Although there are some market-based approaches for balanced task allocation, most of them either require high communication cost to continuously monitor the workload of all robots or use an offline task distribution method before the start of the mission.^16,17 Some other approaches use makespan as a bidding mechanism to minimize the largest individual cost among agents.^18,19 They use a bidding rule based on the total cost of the schedule of an agent. Another approach proposed a bidding rule generation heuristic that inflates marginal costs with a monotonically increasing function of time.⁶ However, they require the information of all tasks beforehand in order for the bidders to build time-extended schedules of multiple tasks and to compare their bids with each other to evenly distribute tasks among the robots. Consequently, they are not applicable to a mission in which tasks occur continuously at arbitrary locations.

This article proposes a framework for market-based task allocation to address the aforementioned issues. The contributions of the proposed framework are twofold. First, it allows the market-based algorithms to adjust the relative importance of the properties of the bidders in accordance with environmental changes. The proposed approach allows the auctioneer to evaluate the properties of the bidders and to adjust their relative importance in response to the characteristics of tasks, preference, and environmental changes. Second, it adopts the concept of subsidy for workload balancing in multirobot systems. Subsidy, in general terms, is the aid provided by the government or other regulatory authorities to help an industry or business compete in the market. In the market-based multirobot task allocation approach, the auctioneer acts as a temporal regulatory agent during the task allocation. Thus, subsidy is utilized in task allocation such that auctioneers provide more subsidies to the bidders that have performed less work than others. As the proposed framework follows conventional auction protocol, any types of market-based algorithms can apply this framework as long as they allocate tasks through negotiation between auctioneers and bidders.

Competency and workload balancing framework

The architecture of the proposed framework is shown in Figure 1. The sensor module and energy storage module in the figure provide information about the local environment and energy level of the robot, respectively. The capability matrix contains information about the available capabilities of the robot. The requirement matrix is defined to represent the characteristics of tasks, such as the capabilities required to perform them. As missions for multirobot systems consist of various types of tasks, it can be helpful for the systems to explicitly represent the requirements of each task. For ease of reading, the notations in this article are summarized in Table 1.

Figure 1.

The architecture of the competency and workload balancing framework.

Table 1.

Summary of notations.

$R_{i}$	The capability matrix of robot i
$R_{i k}$	The k th capability vector in $R_{i}$
$r_{i k}^{q}$	The capability quality in $R_{i k}$
$r_{i k}^{e}$	The energy consumption rate in $R_{i k}$
$r_{i k}^{b}$	The consumption unit index in $R_{i k}$
$M_{j}$	The requirement matrix of task j
$M_{j k}$	The k th requirement vector in $M_{j}$
$m_{j k}^{h}$	The requirement identifier in $M_{j k}$
$m_{j k}^{w}$	The capability quality weight in $M_{j k}$
$B_{i j}$	Robot i that bids on task j
$V_{i j}$	The bid vector of $B_{i j}$
$Q_{i j}$	The task quality of $B_{i j}$
$C_{i j}$	The task cost of $B_{i j}$
$Y_{i j}$	The yield of $B_{i j}$
$U_{i j}^{C}$	The competency utility of $B_{i j}$
$U_{i j}^{S}$	The subsidy utility of $B_{i j}$
$U_{i j}^{T}$	The total utility of $B_{i j}$

Robot capability matrix

The capability matrix of a robot consists of capability vectors, each of which contains information about each of the capabilities, that is, the capability quality, energy consumption rate, and consumption unit index. The capability matrix $R_{i}$ of robot i is defined as

R_{i} = [\begin{matrix} R_{i 1} & R_{i 2} & \dots & R_{i N_{C}} \end{matrix}]

where $R_{i}$ is a 3 × N_C matrix, N_C is the number of capabilities, and the k th capability vector, $R_{i k}$ , is defined as

R_{i k} = {[\begin{matrix} r_{i k}^{q} & r_{i k}^{e} & r_{i k}^{b} \end{matrix}]}^{T}

where $r_{i k}^{q}$ ( $0.0 \leq r_{i k}^{q} \leq 1.0$ ) is the capability quality, $r_{i k}^{e}$ ( $r_{i k}^{e} \geq 0.0$ ) is the energy consumption rate, and $r_{i k}^{b}$ $(r_{i k}^{b} \in {0, 1, 2})$ is the consumption unit index which represents the unit of the energy consumption rate. The capability quality represents the performance quality including the accuracy, precision, and success rate. It is determined by the characteristics of tasks, environments, and hardware resources. The capability qualities for the capabilities not possessed by a robot are set to zero. Moreover, if one of the capabilities of the robot malfunctions, the capability quality of the broken capability is set to zero. This prevents the robot from bidding on a task that it does not have the required capabilities to perform. The energy consumption rate describes how much energy is consumed by the capability with respect to the unit distance, unit time, or each trial, which is determined by the type of the hardware resource. The consumption unit index is defined to represent the unit of the energy consumption rate. It is set to zero if the unit of the energy consumption rate is Joule per second (J/s); it is set to one for Joule per meter (J/m) and two for Joule per trial (J/trial).

Task requirement matrix

The requirement matrix of a task represents the required capabilities of a robot to perform the task. The requirement matrix $M_{j}$ of task j is defined as

M_{j} = [\begin{matrix} M_{j 1} & M_{j 2} & \dots & M_{j N_{C}} \end{matrix}]

where $M_{j}$ is a 2 × N_C matrix and the kth requirement vector, $M_{j k}$ , is defined as

\begin{matrix} M_{j k} = {[\begin{matrix} m_{j k}^{h} & m_{j k}^{w} \end{matrix}]}^{T} \end{matrix}

where $m_{j k}^{h}$ ( $m_{j k}^{h} \in {0, 1}$ ) denotes the requirement identifier of the k th capability for task j, which is set to one if the k th capability is required for the task and zero otherwise, and $m_{j k}^{w}$ ( $0.0 \leq m_{j k}^{w} \leq 1.0$ ) is the capability quality weight of the k th capability, which denotes the degree of importance of the capability quality for task j.

Bid process

In the proposed framework, the auctioneer receives the properties of each bidder, instead of its bid. The auctioneer subsequently generates the normalized quality and cost of each bidder by dividing each value from the sum of the values of all bidders. By normalizing the quality and the cost, the relative difference among the properties of the bidders is revealed. Moreover, it is not required to determine unbounded scale factors by normalizing the properties. The problem of adjusting the relative importance of the properties can be also solved using the proposed method. Unlike the traditional approaches where each bidder is responsible for adjusting the relative importance of its properties, the proposed method transfers the responsibility to the auctioneer. The advantage of the proposed method is that the relative importance can be easily adjusted by controlling the adjusting factor of the auctioneer in response to the characteristics of tasks, preference, and environmental changes.

When a robot receives an auction call, it decides whether to bid on an auctioned task using its capability matrix and the requirement matrix of the auctioned task. If the robot has sufficient capabilities to perform the task, it generates a bid vector for the task using the bid generation module. The bid generation module generates a bid vector consisting of the task quality, task cost for the auctioned task, and yield. The task quality represents the performance quality of the robot such that a robot with high task quality would guarantee high accuracy, high precision, and high success rate for the task with fewer errors and mistakes. The robot i that bids on task j is denoted as $B_{i j}$ , and the bid vector of $B_{i j}$ is defined as

V_{i j} = [\begin{matrix} Q_{i j} & C_{i j} & Y_{i j} \end{matrix}]

where $Q_{i j}$ , $C_{i j}$ , and $Y_{i j}$ are the task quality, the task cost, and the yield of $B_{i j}$ , respectively. The task quality $Q_{i j}$ of $B_{i j}$ is defined as

\begin{matrix} Q_{i j} = \sum_{k = 1}^{N_{C}} m_{j k}^{h} m_{j k}^{w} r_{i k}^{q} \end{matrix}

where $r_{i k}^{q}$ is from equation (2), and $m_{j k}^{h}$ and $m_{j k}^{w}$ are from equation (4). As the bidder has high capability qualities for the capabilities required for the task, it can achieve high task quality for the task.

The task cost is defined as the estimated energy consumed by the robot to complete the task. The task cost $C_{i j}$ of $B_{i j}$ is defined as

\begin{matrix} C_{i j} = C_{i j}^{v} + C_{i j}^{r} \end{matrix}

with

\begin{array}{l} C_{i j}^{v} = t_{i j} (\sum_{\forall k | r_{i k}^{b} = 0} m_{j k}^{h} r_{i k}^{e}) + d_{i j} (\sum_{\forall k | r_{i k}^{b} = 1} m_{j k}^{h} r_{i k}^{e}) \\ C_{i j}^{r} = l_{i j} (\sum_{\forall k | r_{i k}^{b} = 2} m_{j k}^{h} r_{i k}^{e}) \end{array}

where $C_{i j}^{v}$ and $C_{i j}^{r}$ are the travel cost and trial cost, respectively, $t_{i j}$ and $d_{i j}$ are the estimated task completion time and distance, respectively, and $l_{i j}$ is the estimated number of trials.

The yield of a robot represents the amount of work performed by the robot, which is measured in terms of the total energy consumed by the robot. Higher energy consumption of a robot can result from either its higher workload or its lower energy efficiency. In either case, a robot with higher yield has consumed more energy than the other members of the robot team. Therefore, regulating the yields of the robots can ensure diminished participation from the robots that already have much higher yields. Such yield regulation can prevent the breakdown of robots owing to high energy dissipation resulting from excessive workload or low energy efficiency. The yield $Y_{i j}$ of $B_{i j}$ is defined as

\begin{matrix} Y_{i j} = \sum_{k \in A_{i}} E_{i k} + C_{i j} \end{matrix}

where $A_{i}$ is the set of tasks performed by robot i, and $E_{i k}$ is the amount of energy consumed the robot for task k. As $C_{i j}$ is the estimated energy consumption of $B_{i j}$ , $Y_{i j}$ can be considered the estimated total amount of energy consumed by the robot after completing task j. From the perspective of market economy, this yield can be directly related to the revenue earned by each bidder. Therefore, the yield of a robot was used as a criterion for calculating its subsidy. Lower yield results in higher subsidy because it indicates that the bidder is not sufficiently competitive and it needs some help from the framework to actively participate in the market-based process.

Auction process

When a robot desires to allocate a task to other robots, it acts as an auctioneer and broadcasts an auction call for the task. After receiving the bids from bidders, the auctioneer generates their total utilities to select a winner. To generate them, the utility weight module calculates the competency weight for adjusting the relative importance of the task quality over the task cost and the subsidy weight for regulating the workload distribution.

Utility weight generation module

The utility weights consist of the competency weight and subsidy weight. By using them, the proposed framework can adjust the relative importance of the competency and distribute workload among the robots in a balanced manner.

The competency weight of robot i, $w_{i}^{c} (t)$ , $(w_{min}^{c} \leq w_{i}^{c} (t) \leq w_{max}^{c})$ is updated as

\begin{matrix} w_{i}^{c} (t) = w_{i}^{c} (t - T_{c}) + β ({\hat{w}}_{i}^{c} (t) - w_{i}^{c} (t - T_{c})) \end{matrix}

where ${\hat{w}}_{i}^{c} (t)$ is the reference competency weight, $T_{c}$ is the control period, β $(0.0 \leq β \leq 1.0)$ is the update rate, and $w_{min}^{c}$ and $w_{max}^{c}$ are the minimum and maximum competency weights, respectively. The reference competency weight is updated using environmental variables, such as sunlight intensity and the amount of minerals in the environment. The environmental variables are measured by the robots such that the robots in the same environment should have the same competency weight. However, some of them might have different competency weights owing to their sensory noise. Such erroneous competency weights might cause undesirable task allocation. To solve this problem, each robot updates its competency weight depending on its current state. If the robot is neither bidding on nor auctioning any task (i.e. it is not participating in task trading), it updates its competency weight from the environmental variables. On the other hand, if it is either auctioning or bidding on a task, it updates its competency weight by the average of the competency weights of the other bidders. To do this, when an auctioneer broadcasts an auction call, bidders send their competency weights along with their bids. After receiving the competency weights of the bidders, the auctioneer calculates the average of the received competency weights, updates its competency weight from the average competency weight, and broadcasts it along with the task award message. The bidders receive the average competency weight from the auctioneer and update their competency weights accordingly. The reference competency weight of robot i, ${\hat{w}}_{i}^{c} (t)$ $(w_{min}^{c} \leq {\hat{w}}_{i}^{c} (t) \leq w_{max}^{c})$ is defined as

\begin{matrix} {\hat{w}}_{i}^{c} (t) = {\begin{array}{l} w^{c}, & \begin{array}{l} if robot i is either \\ an auctioneer or a bidder \end{array} \\ η_{i} (x_{i} (t)), & otherwise \end{array} \end{matrix}

where w^c is the average of the received competency weights of the bidders, $x_{i} (t) \in ℝ^{N_{E}}$ is a vector of $N_{E}$ environmental variables measured by robot i, $η_{i} (x_{i} (t))$ $(w_{min}^{c} \leq η_{i} (x_{i} (t)) \leq w_{max}^{c}$ ) is the environment function of $x_{i} (t)$ . If the environmental variables indicate that the robots can easily recharge themselves in the environment, the output of the environment function increases. Consequently, the competency weight increases with the reference competency weight. However, if the environmental situation is so hostile that the robots cannot recharge themselves easily, the output of the environment function decreases. This leads a decrease in the competency weight with a decrease in the reference competency weight.

In this framework, the subsidy weight is used to balance between the competency utility and the subsidy utility. The competency utility represents the competency of the bidder for the auctioned task. The subsidy utility is evaluated from the yield such that the bidder with lower yield obtains higher subsidy utility, and vice versa. The competency utility and subsidy utility are described in detail in the following subsection. Unlike the other market-based algorithms, which do not have arbitrators, the proposed framework makes the auctioneer act as a temporal government such that it can provide subsidies to the bidders for workload distribution. The subsidy weight, $w^{s}$ $(w_{min}^{s} \leq w^{s} \leq w_{max}^{s})$ is defined as

\begin{matrix} w^{s} = (w_{max}^{s} - w_{min}^{s}) \tilde{σ} + w_{min}^{s} \end{matrix}

with

\begin{matrix} \tilde{σ} = \frac{min (σ, σ_{a})}{σ_{a}}, σ = \sqrt{\frac{1}{| B |} \sum_{k \in B} {(Y_{k j} - \bar{Y})}^{2}} \end{matrix}

where σ is the standard deviation of the yields of the bidders, $\tilde{σ}$ is the normalized standard deviation, $σ_{a}$ is the allowable upper limit of the standard deviation, B denotes the set of bidders, $| \cdot |$ is the cardinality of the set, $\bar{Y}$ is the average yield of the bidders, and $w_{min}^{s}$ and $w_{max}^{s}$ are the minimum and maximum subsidy weights, respectively. The standard deviation of the yields of the bidders is used as the indicator for unbalanced workload distribution. When $\tilde{σ}$ is close to zero, it indicates that the workload has been evenly distributed among the robots. In this case, the subsidy weight is decreased to $w_{min}^{s}$ such that the task is allocated to the robot with higher competency utility than the others as described in equation (17). If $\tilde{σ}$ is close to one, the subsidy weight is increased to $w_{max}^{s}$ such that the auctioneer would provide higher subsidies to the bidders with lower yields to encourage them to participate in the mission.

Utility generation module

Based on the bids from the bidders and the utility weights from the utility weight generation module, the auctioneer evaluates three types of utilities, that is, competency utility, subsidy utility, and total utility, of each bidder in the utility generation module. As shown in Figure 2, each bidder submits its bid, which consists of the task quality, task cost, and yield. The auctioneer subsequently normalizes the bids and generates the competency utility, subsidy utility, and total utility of each bidder. The relative importance of the properties is adjusted using the competency weight and subsidy weight.

Figure 2.

The utility generation process of the proposed framework.

The competency utility represents the competency of the bidder for the task from the viewpoint of task quality and task cost. The competency utility of $B_{i j}$ , $U_{i j}^{C}$ $(0.0 \leq U_{i j}^{C} \leq 1.0)$ is defined as

\begin{matrix} U_{i j}^{C} = 0.5 (w^{c} {\tilde{Q}}_{i j} - (1.0 - w^{c}) {\tilde{C}}_{i j} + 1.0) \end{matrix}

with

\begin{matrix} {\tilde{Q}}_{i j} = \frac{Q_{i j}}{\sum_{k \in B} Q_{k j}}, {\tilde{C}}_{i j} = \frac{C_{i j}}{\sum_{k \in B} C_{k j}} \end{matrix}

where ${\tilde{Q}}_{i j}$ and ${\tilde{C}}_{i j}$ are the normalized task quality and normalized task cost, respectively, and $w^{c}$ is the average competency weight of the auctioneer from equation (11). The coefficients 1.0 and 0.5 in equation (14) are used to scale the competency utility range to [0, 1].

The subsidy utility is evaluated from the yield such that a bidder with lower yield obtains higher subsidy utility, and vice versa. This encourages the bidders that have performed less work than others to participate more in the mission. The subsidy utility of $B_{i j}$ , $U_{i j}^{S}$ $(0.0 \leq U_{i j}^{S} \leq 1.0)$ is defined as

\begin{matrix} U_{i j}^{S} = \frac{1 / {(ε + Y)}_{i}}{\sum_{k \in B} 1 / (ε + Y_{k})} \end{matrix}

where ε is a small positive constant, added to avoid division by zero. As this framework provides higher subsidy utility to the bidder with lower yield, it is capable of distributing workload in a balanced manner.

The combination of the competency and subsidy utilities is defined as total utility, and their relative importance is adjusted using the subsidy weight in equation (12). The total utility of $B_{i j}$ , $U_{i j}^{T}$ $(0.0 \leq U_{i j}^{T} \leq 1.0)$ is defined as

\begin{matrix} U_{i j}^{T} = (1.0 - w^{s}) U_{i j}^{C} + w^{s} U_{i j}^{S} \end{matrix}

where $w^{s}$ is the subsidy weight from equation (12) and $w^{s} U_{i j}^{S}$ is the subsidy of $B_{i j}$ . Using the total utility, both competency and yield of a bidder are considered in task allocation.

Task trading

The task trade module manages task trading communication between bidders and auctioneers. For an auction mechanism, a single-item auction method is used with repeating auctions after each task has been completed.^20,21 In sequential single-item auctions, the auctioneers auction tasks individually, and the bidders bid on tasks accounting for their previously assigned tasks. For task trading, four types of messages, that is, Auction, Bid, Award, and Accept messages, are defined. If a robot attempts to allocate a task, it becomes an auctioneer and broadcasts the Auction message to the other robots. After receiving the bids from the bidders, the auctioneer calculates their total utilities. If there are several bidders with the same total utilities, some heuristic methods, such as selecting a winner that has the highest or lowest ID number, can be used. After selecting a winner, the auctioneer broadcasts the Award message with the ID and the total utility of the winner. If the bidder receives Award messages from several auctioneers, it compares its total utilities for the tasks, and subsequently broadcasts Accept message for the task for which it has the highest total utility. After the auctioneer receives the Accept message from its selected winner, it clears its auction. Otherwise, it auctions again and repeats the auction procedure until the task is allocated.

An example of the task trading procedure is illustrated in Figure 3, where auctioneer 1 and auctioneer 2 auction task 1 and task 2, respectively, and robot 1 and robot 2 bid on both tasks by sending their bids to the auctioneers. When the auction deadline elapses, the auctioneers calculate the total utilities of the bidders and award their tasks to robot 1, which has higher total utilities for both tasks than robot 2. After receiving two $A w a r d$ messages from the auctioneers, robot 1 compares its total utilities for both tasks and subsequently broadcasts Accept message for task 1 as it has higher total utility for task 1 than for task 2. This procedure is repeated until all the tasks are allocated.

Figure 3.

Illustration of task trading procedure. In this example, robot 1 has higher utilities for both task 1 and task 2 than robot 2. After receiving its total utilities from both auctioneers, robot 1 accepts task 1 as $U_{11}^{T}$ is higher than $U_{12}^{T}$ .

Comparison with existing approaches

Although the proposed framework is based on market-based approaches, it is different from conventional market-based task allocation systems as summarized in Table 2. The number of properties in the table represents the number of valuation bases, such as quality and cost, used by the auctioneer for selecting the winner in task allocation, and the bid structure denotes the form of bid information when the bidder submits its bid to the auctioneer. The property combiner and property arbitrator in the table represent the subjects that combine the properties and adjust the relative importance of the properties, respectively. The scaling factors scale the properties with different units and magnitude ranges.

Table 2.

Comparison between the traditional approaches and the proposed approach.

Type	Traditional	Proposed
Number of properties	Single or multiple	$Q, C, Y$
Bid structure	Single value	$[Q C Y]$
Property combiner	Bidder	Auctioneer
Property arbitrator	Bidder	Auctioneer
Scaling factors	Required	n/a
Winner selection	The bidder with minimum bid	The bidder with maximum utility

In the traditional approaches, each bidder constructs a bid either from a single property or from multiple properties and submits it to the auctioneer. In the case of multiple properties, as they have different units and magnitude ranges, the bidder should determine heuristic scaling factors to combine them. However, such scaling factors cannot include information about the heterogeneity and local state of the other bidders. Moreover, as the relative importance of the properties is adjusted by each bidder, the bids from different bidders might be generated with different standards. This hinders the fair evaluation of bids by the auctioneer.

In the proposed framework, each bidder submits a bid, consisting of task quality, task cost, and yield, to the auctioneer, and the auctioneer generates the utility of each bidder, as shown in Figure 2. Unlike the traditional approaches in which the bidder combines multiple properties with scaling factors, the auctioneer in the proposed approach normalizes the properties of the bidders, as shown in equation (15). Thus, the auctioneer can merge the properties of each bidder without heuristic scaling factors. It also clarifies the relative differences between the properties of the bidders. Moreover, as the relative importance of the properties is adjusted by the auctioneer as shown in equation (10) and (12), the auctioneer can compare the bidders with the same standards.

Cleaning mission

To demonstrate the effectiveness of the proposed framework, simulations for a cleaning mission were carried out using a commercially available robot simulator called Webots.²² (Please refer to the video clip of the overall cleaning mission in https://youtu.be/8cGZbQkwxGohttps://youtu.be/8cGZbQkwxGo) The cleaning mission consists of various types of tasks that require different types of robot capabilities to be executed, such as collecting garbage bags around zones, carrying them to the disposal plant, and sorting them by their types. In the simulation, eight heterogeneous robots are employed to perform the mission. The robots are solar-powered, and they recharge themselves using their solar panels. The source code is available at https://github.com/nuitvolgit/MRTAhttps://github.com/nuitvolgit/MRTA.

Figure 4(a) shows the screenshot of the simulation. The three fan-shaped sectors on the bottom right of the figure are the three zones where the cleaning mission is carried out by the robots. In each zone, three different types of garbage bags, that is, disposable waste, recyclable waste, and organic waste, pop out randomly. The building on the top left of the figure is the disposal plant where the garbage bags are sorted and carried to their designated storage rooms.

Figure 4.

Screenshot of the cleaning mission simulation is shown in (a). (b) shows two robots that form a team and collect garbage bags together in the zone. (c) shows a robot that collects and carries garbage bags in the zone. In (d) and (e), robots load the garbage bags to $T r a y_{1}$ . (f) shows two robots that transport $T r a y_{1}$ to the disposal plant. A garbage bag sorting task is shown in (g) and (h). (i) shows a robot that carries a small tray to the storage room. (j) and (k) show the burst of garbage bags owing to the localization error and gripping error of a robot, respectively. (l) shows the failure of sorting of a garbage bag owing to the garbage bag recognition error of a robot.

Heterogeneous robots

Eight heterogeneous robots are used to perform various tasks in the mission. Each robot has different combinations of the following six capabilities: localization, garbage bag recognition, mobility, garbage gripping, garbage storage, and tray holding. The localization capability is required for the robots to transport an object to a target position, as shown in Figure 4(d) to (f) and (i). If the localization quality of a robot is low, it might not be able to carry garbage bags correctly to a tray. Figure 4(j) shows the bursting of garbage bags that are placed out of the tray. The garbage bag recognition capability is used to sort the garbage bags, as shown in Figure 4(g) and (h). If the recognition quality of a robot is low, it often fails to correctly sort the garbage bags, as shown in Figure 4(l). The gripping capability is necessary to grip and sort the garbage bags, as shown in Figures 4(b), (c), (g), and (h). If the gripping quality is low, the garbage bags would burst owing to the gripping error of a robot as shown in Figure 4(k). The garbage storage capability represents the storage capacity of the robot for carrying the garbage bags. The large-capacity storage can stock up to four garbage bags, as shown Figure 4(b) and (c), whereas the small-capacity storage can store a maximum of two garbage bags as shown in Figure 4(e). The tray holding capability is required for robots to transport trays, as shown in Figure 4(f) and (i).

Each of the capabilities has different characteristics depending on its hardware resource as shown in Table 3, where $r^{q}$ , $r^{e}$ , and $r^{b}$ are the capability quality, energy consumption rate, and its unit, respectively from equation (2). For each capability, except for the tray holding capability, two types of hardware resources, one with high capability quality and the other with low capability quality, are defined to increase the heterogeneity among the robots. The values in Table 3 are designed to distinguish between the hardware resources with high and low capability qualities.

Table 3.

Six capabilities with different hardware resources.

Capability	Hardware resource	$r^{q}$	$r^{e}$	$r^{b}$
LOC (localization)	LRF (laser-range finder)	0.9	0.3	0
LOC (localization)	USS (ultrasonic sensors)	0.6	0.2	0
RCG (garbage recognition)	HQC (high-quality camera)	0.9	0.6	0
RCG (garbage recognition)	LQC (low-quality camera)	0.6	0.2	0
MOB (mobility)	HTD (high torque drive)	0.9	4.0	1
MOB (mobility)	LTD (low torque drive)	0.6	2.5	1
GRP (garbage gripping)	PRG (prismatic grip)	0.9	2.0	2
GRP (garbage gripping)	ROG (rotational grip)	0.6	1.5	2
STR (garbage storage)	LAC (large capacity)	0.9	3.0	2
STR (garbage storage)	SMC (small capacity)	0.6	2.0	2
HLD (tray holding)	THD (tray holder)	0.9	3.0	2

The capability quality of a hardware resource is used as a measure of its performance in the simulations. In case of the capability quality for garbage gripping, the value is used as the probability of gripping a garbage bag without bursting it. When a robot attempts to grip a garbage bag in the simulation, it generates a random value between 0.0 and 1.0. If the random value is lower than the capability quality value of garbage gripping, it successfully grips the garbage bag. If the random value is higher than the capability quality value, the garbage bag bursts, as shown in Figure 4(k), and the robot recognizes that it has not been able to grip the garbage bag successfully.

There are five capabilities, that is, localization (LOC), garbage recognition (RCG), mobility (MOB), garbage gripping (GRP), and garbage storage (STR). Each capability has two different hardware resources with different qualities and costs. For localization, each robot used either laser range-finder (LRF) or ultrasonic sensors (USS). In the case of garbage recognition, the robots with IDs 1 to 4 used either a high-quality camera (HQC) or low-quality camera (LQC), and the other robots did not have the garbage recognition capability. For mobility, either high torque drive (HTD) or low torque drive (LTD) is used. For garbage gripping, either prismatic gripper (PRG) or rotational gripper (ROG) is used by the robots with IDs 1 to 4, and other robots did not have the garbage gripping capability. In the case of garbage storage capacity, only the robots with IDs 3 to 8 had either small capacity (SMC) or large capacity (LAC), and others did not have storage capacity. Finally, the robots with IDs 4 to 8 had tray-holding capability, called tray holder (THD), and other robots did not have this capability.

In the simulations, each of the eight heterogeneous robots in Figure 5 consists of different combinations of the six capabilities with different hardware resources, as shown in Tables 3 and 4. The robots with the same capabilities can have different bids for the same task owing to their different hardware resources. For example, although both robots 1 and 2 have the same capabilities, that is, $L R F$ , $R C G$ , $M O B$ , and $G R P$ , they have different hardware resources for their capabilities. This would also affect the results depending on the task allocation methods.

Figure 5.

The eight heterogeneous robots in the cleaning mission.

Table 4.

Hardware resources of robots.

Robot ID	$L O C$	$R C G$	$M O B$	$G R P$	$S T R$	$H L D$
1	LRF	HQC	HTD	PRG	n/a	n/a
2	LRF	LQC	HTD	PRG	n/a	n/a
3	USS	HQC	LTD	ROG	SMC	n/a
4	USS	LQC	LTD	ROG	SMC	n/a
5	LRF	n/a	HTD	n/a	LAC	THD
6	LRF	n/a	LTD	n/a	LAC	THD
7	USS	n/a	HTD	n/a	LAC	THD
8	USS	n/a	LTD	n/a	LAC	THD

LOC: localization; RCG: garbage recognition; MOB: mobility; GRP: garbage gripping; STR: garbage storage; HLD: tray holding; LRF: laser-range finder; USS: ultrasonic sensors; LTD: low torque drive; SMC: small capacity; LAC: large capacity; THD: tray holder; LQC: low-quality camera; HQC: high-quality camera.

Tasks

There are five tasks in the cleaning mission as shown in Table 5 and each task requires different capabilities. The requirement matrices of the tasks are shown in Table 6, where h and $w^{q}$ are the capability requirement indicator and the capability quality weight, respectively, from equation (4). In each zone in Figure 4(a), a garbage monitoring agent monitors the number of garbage bags in the zone, and when there are more than six garbage bags in the zone, it holds an auction for task 1. The winner of task 1 holds an auction for task 2 to form a team for collecting garbage bags in the zone and carrying them to $T r a y_{1}$ , located at the center of the three zones, as shown in Figure 4(a). If the robot that holds the auction for task 2 becomes the winner by itself, it performs both task 1 and task 2, as shown in Figure 4(c) and (e). Otherwise, two robots, the winners of tasks 1 and 2, work together to collect the garbage bags, as shown in Figure 4(b). If the number of garbage bags on $T r a y_{1}$ is more than 10, the last robot that has piled up the garbage bags on the tray becomes the auctioneer of task 3. In the case of task 3, the auctioneer determines the first and second winners by selecting two bidders with the highest and second highest total utilities to transport $T r a y_{1}$ to the disposal plant, as shown in Figure 4(f). After transporting $T r a y_{1}$ , the first winner of task 3 holds an auction for task 4 to sort the garbage bags to small trays. The winner of task 4 sorts the garbage bags and carries them to the designated small trays, as shown in Figure 4(g) and (h). When three garbage bags are piled up in any of the small trays, the robot that performs task 4 holds an auction for task 5. The winner of task 5 carries the small tray to the designated storage room, as shown in Figure 4(i).

Table 5.

Descriptions of tasks.

Task ID	Description
1	Find and pick up garbage bags
2	Transport garbage bags to $T r a y_{1}$
3	Transport $T r a y_{1}$ to the disposal plant
4	Sort garbage bags to small trays
5	Transport small tray to the designated storage room

Table 6.

Requirement matrices of the tasks in the mission.

		$M_{1}$	$M_{2}$	$M_{3}$	$M_{4}$	$M_{5}$
$L O C$	$m^{h}$	1	1	1	1	1
$L O C$	$m^{w}$	0.7	0.9	0.9	0.7	0.9
$R C G$	$m^{h}$	1	0	0	1	0
$R C G$	$m^{w}$	0.7	0.0	0.0	0.8	0.0
$M O B$	$m^{h}$	1	1	1	1	1
$M O B$	$m^{w}$	0.7	0.7	0.9	0.7	0.7
$G R P$	$m^{h}$	1	0	0	1	0
$G R P$	$m^{w}$	0.9	0.0	0.0	0.9	0.0
$S T R$	$m^{h}$	0	1	0	0	0
$S T R$	$m^{w}$	0.0	0.9	0.0	0.0	0.0
$H L D$	$m^{h}$	0	0	0	0	1
$H L D$	$m^{w}$	0.0	0.0	0.0	0.0	0.9

LOC: localization; RCG: garbage recognition; MOB: mobility; GRP: garbage gripping; STR: garbage storage; HLD: tray holding.

Performance evaluation

To evaluate the overall performance of the robots in the mission, the mission quality and mission cost are defined. The mission quality represents how well the mission is performed in terms of task accuracy. The mission cost is the sum of the energy consumed by all the robots. The mission quality $Q^{O}$ and mission cost $C^{O}$ are, respectively, defined as

\begin{matrix} Q^{O} = \frac{1}{3} \sum_{i = 1}^{3} Q_{i}^{O}, C^{O} = \sum_{i = 1}^{N_{R}} E_{i} \end{matrix}

with

Q_{i}^{O} = Q_{i}^{O -} + γ (\frac{S u c c e s s_{i}}{T r i a l_{i}} - Q_{i}^{O -})

where $Q_{1}^{O}$ , $Q_{2}^{O}$ , and $Q_{3}^{O}$ are garbage grip quality, garbage classification quality, and transportation quality, respectively, $E_{i}$ is the amount of energy consumed by robot i, and N_R is the number of robots. $Q_{i}^{O -}$ is the previous value of the i th mission quality, and γ is the update rate. The success rate of the garbage grip quality, $S u c c e s s_{1} / T r i a l_{1}$ , increases if the robots successfully grip garbage bags per trial without burst. The success rate of the classification quality, $S u c c e s s_{2} / T r i a l_{2}$ , increases if the robots sort garbage bags correctly per trial. The success rate of the transportation quality, $S u c c e s s_{3} / T r i a l_{3}$ , increases if the robots accurately carry the garbage bags to the designated position per trial.

To observe the inequality among the yields of the robots, the Lorenz curve and Gini coefficient were used.^23
–25 The Lorenz curve is used as a graphical representation of the cumulative distribution function of the distribution of wealth in economics. It is a continuous piecewise linear function connecting the points $(X_{i}, L_{i})$ , defined as

\begin{matrix} (X_{i} = \frac{i}{N_{R}}, L_{i} = \frac{\sum_{j = 1}^{i} Z_{j}}{\sum_{j = 1}^{N_{R}} Z_{j}}) \end{matrix}

where $X_{i}$ is the cumulative percentage of the i th population and $Z_{i}$ is the i th yield at the termination time, sorted in non-decreasing order $(Z_{i} \leq Z_{j}, i < j)$ . The Gini coefficient has been used in the study of inequalities in disciplines as diverse as sociology, economics, and health science. To observe the inequality among the yields of the robots, the Gini coefficient G is defined as

\begin{matrix} G = \frac{2 \sum_{i = 1}^{N_{R}} i Y_{i}}{N_{R} \sum_{i = 1}^{N_{R}} Y_{i}} - \frac{N_{R} + 1}{N_{R}} \end{matrix}

where $Y_{i}$ is the yield of robot i. A low Gini coefficient indicates a more equal distribution, with 0.0 corresponding to complete equality, whereas a higher Gini coefficient indicates more uneven distribution.

Simulation results

In the simulation, the task quality was defined as the capability qualities of the robot for the auctioned task such that if the bidder has high qualities for the required capabilities of the task, it achieves high task quality. The task cost was defined as the estimated energy consumed by the robot to perform the task, and the yield was defined as the amount of energy consumed by the robot.

After receiving the bid vectors, the proposed framework was applied for the bid valuation and winner determination stages of the conventional auction protocol. To compare the simulation results with different bid valuations and winner determinations, five types of task allocations are defined in Table 7. In the quality-based task allocation (QBTA), a bid was defined as the task quality, and the auctioned task was allocated to the bidder with the highest task quality. The cost-based task allocation (CBTA) used the task cost as a bid to allocate the task to the bidder with minimum cost. The yield-based task allocation (YBTA) allocated the task to the robot that has worked less than the others. The quality and cost-based task allocation (QCBTA) used the competency utility to adjust the competency in accordance with environmental changes. The quality, cost and yield-based task allocation (QCYBTA) used the total utility to consider both competency adjustment and workload distribution. (Please refer to the video clips of the cleaning mission to compare the characteristics of task allocations with different task allocation algorithms. [Video 1: QBTA] (https://youtu.be/pdViqqpu0d8https://youtu.be/pdViqqpu0d8), [Video 2: CBTA] (https://youtu.be/RWiMYW0havEhttps://youtu.be/RWiMYW0havE), [Video 3: YBTA] (https://youtu.be/cHm8Tz3H56shttps://youtu.be/cHm8Tz3H56s), [Video 4: QCBTA] (https://youtu.be/8ycIWXpHJ0Qhttps://youtu.be/8ycIWXpHJ0Q), [Video 5: QCYBTA] (https://youtu.be/5UaEYA-IxbMhttps://youtu.be/5UaEYA-IxbM).)

Table 7.

Five types of task allocation strategies.

Type	Bid of $B_{i j}$	Winner selection
QBTA	$Q_{i j}$	$arg {max}_{i \in B} Q_{i j}$
CBTA	$C_{i j}$	$arg {min}_{i \in B} C_{i j}$
YBTA	$Y_{i j}$	$arg {min}_{i \in B} Y_{i j}$
QCBTA	$Q_{i j}, C_{i j}$	$arg {max}_{i \in B} U_{i j}^{C}$
QCYBTA	$Q_{i j}, C_{i j}, Y_{i j}$	$arg {max}_{i \in B} U_{i j}^{T}$

QBTA: quality-based task allocation; CBTA: cost-based task allocation; YBTA: yield-based task allocation; QCBTA: qality and cost-based task allocation; QCYBTA: qality, cost, and yield-based task allocation.

In the simulation, the termination time was set to 3000 s, and 30 simulation runs were performed per algorithm. The sunlight intensity in the simulation changed over time and hence, the solar panel voltage of the robot was defined as the environmental variable. The solar panel voltage level of robot i was defined as $x_{i} (t)$ , and the environment function for the solar panel voltage level, $η (x_{i} (t))$ was defined as

\begin{matrix} η (x_{i} (t)) = w_{min}^{c} + \sqrt{\frac{x_{i} (t) - x_{min}}{x_{max} - x_{min}}} (w_{max}^{c} - w_{min}^{c}) \end{matrix}

where $x_{min}$ and $x_{max}$ are the minimum and maximum solar panel voltages, respectively. The initial competency weights of the robots were randomly defined to show that the proposed method in equation (11) can minimize the differences between the competency weights of the robots. Figure 6 shows the average of the normalized solar panel voltages and the average of the competency weights of the robots owing to the change in sunlight intensity. Until 500 s, the normalized solar panel voltage was lower than 0.5 owing to the low sunlight intensity. As the solar panel voltage continuously increased, the competency weight also increased, as described in equations (10), (11), and (22). As the initial values of the competency weights of the robots were randomly defined, the standard deviation of the competency weights of the robots was initially high. As the mission progressed, their competency weights converged to the average of the competency weights of the robots through the continuous update from the environment and sharing of the competency weights during the task trading, as described in equations (10) and (11).

Figure 6.

The average of the normalized solar panel voltages and the competency weights due to the change of sunlight intensity.

Figure 7(a) and (b) show the simulation results of the mission quality and mission cost for different types of task allocation methods over time. In the case of the QBTA, the mission quality was the highest among all the methods. However, as the task cost of the bidder was not considered in task allocation, this method resulted in the highest mission cost. In contrast, the CBTA could minimize the mission cost. However, the mission quality was the lowest among all the methods. When YBTA was applied, neither the mission quality maximization nor the mission cost minimization was accomplished as the method only attempted to minimize the standard deviation of the yields of the robots for workload distribution. In the case of the QCBTA and QCYBTA, the mission quality and mission cost changed over time with the change in the competency weight, as shown in Figure 6. Until 500 s, where the competency weight was low, the results of both methods were similar to those of the CBTA. As the competency weight increased after 500 s, the mission qualities of the QCBTA and QCYBTA also increased as they attempted to allocate the tasks to the bidders with high task qualities. However, after 1500 s, the mission quality and mission cost of the QCYBTA decreased whereas those of the QCBTA continuously increased, as shown in Figure 7. This trend appeared because the QCYBTA began to support the robots with lower yields by providing higher subsidies to regulate the unbalanced workload distribution.

Figure 7.

The results of the mission with different types of task allocation methods. (a) mission quality. (b) mission cost.

To observe the effect of the subsidy in task allocation, the yields of the robots with the QCBTA and QCYBTA are shown in Figure 8. In the case of the QCBTA, while the yield of robot 5 rapidly increased, the yields of the other robots did not increase significantly, as shown in Figure 8(a). As the QCBTA attempted to maximize the mission quality after 500 s, the result in Figure 8(a) indicates that robot 5 had higher task qualities than others for the tasks auctioned after 500 s. Consequently, the tasks were continuously allocated to robot 5 after 500 s. It demonstrates that although the QCBTA could adjust the competency in accordance with environmental changes, it could not distribute workload in a balanced manner. In the case of using the QCYBTA, robot 5 was not as overworked as it was in the QCBTA. Instead, the yields of all the robots gradually increased, as shown in Figure 8(b). It indicates that all the robots could participate in the mission by utilizing their subsidies.

Figure 8.

The energy consumption of the robots. (a) Results from QCBTA and (b) results from QCYBTA. QCBTA: quality and cost-based task allocation; QCYBTA: quality, cost and yield-based task allocation.

To measure the workload distribution among the robots with different types of task allocation methods, the Lorenz curve and Gini coefficient were used, as shown in Figure 9. The results show that the Lorenz curves of the YBTA and QCYBTA, which used subsidy, became close to the line of equality, whereas the Lorenz curves of other methods, which did not provide subsidy to the robots, receded from the line of equality, as shown in Figure 9(a). Similarly, the Gini coefficients of the YBTA and QCYBTA were lower than those of the other methods, as shown in Figure 9(b). The results demonstrate that the task allocation with subsidy can regulate the workload distribution among the robots.

Figure 9.

Lorenz curves and Gini coefficients with respect to different types of task allocation methods. (a) Lorenz curve and (b) Gini coefficient.

Conclusion

In this article, a framework for competency adjustment and workload balancing in market-based coordination was proposed. To consider both task quality and task cost in task allocation, the robot capability matrix and task requirement matrix are proposed, and the relative importance of them is adjusted by the competency weight. The subsidy utility is also proposed for the robots in a team to equally participate in the mission. The relative importance of the competency utility and the subsidy utility is adjusted by the subsidy weight. The simulation results of the cleaning mission demonstrated that the proposed framework can adjust the relative importance of the task quality and task cost in accordance with environmental changes. The effects of the subsidy were also tested, and the Lorenz curve and Gini coefficient showed that the proposed framework can regulate the workload distribution among the robots using subsidy.

Footnotes

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Brain Korea 21 Plus Project (Dept. of IT Convergence Engineering, Kumoh National Institute of Technology); the MSIT (Ministry of Science, ICT), Korea, under the ITRC (Information Technology Research Center) support program (IITP-2018-2014-1-00639) supervised by the IITP (Institute for Information & communications Technology Promotion).

ORCID iD

Dong-Hyun Lee

References

Michael

Zavlanos

Kumar

. Distributed multirobot task assignment and formation control. In: IEEE international conference on robotics and automation (ICRA), Pasadena, CA, USA, 19–23 May 2008, pp. 128–133. IEEE.

Liu

Shell

. Large-scale multi-robot task allocation via dynamic partitioning and distribution. Auton Robot 2012; 33(3): 291–307.

Dias

Stentz

. A free market architecture for distributed control of a multirobot system. In: 6th international conference on intelligent autonomous systems (IAS-6), Giudecca Island, Venice, Italy, 25–27 July 2000, pp. 115–122.

Kalra

Stentz

. A market approach to tightly-coupled multi-robot coordination: first results. In: Proceedings of the ARL collaborative technologies alliance symposium, May 2003.

Dias

Zlot

Kalra

. Market-based multirobot coordination: a survey and analysis. Proc IEEE 2006; 94(7): 1257–1270.

Zlot

Stentz

. Complex task allocation for multiple robots. In: Proceedings of the IEEE international conference on robotics and automation (ICRA), Barcelona, Spain, 18–22 April 2005, pp. 1515–1522. IEEE.

Lee

Zaheer

Kim

. Ad hoc network-based task allocation with resource-aware cost generation for multirobot systems. IEEE Trans Ind Electron 2014; 61(12): 6871–6881.

Gerkey

Mataric

. Sold!: auction methods for multirobot coordination. IEEE Trans Robot Autom 2002; 18(5): 758–768.

Dias

. Traderbots: a new paradigm for robust and efficient multirobot coordination in dynamic environments. Robot Inst 2004; 153. https://www.ri.cmu.edu/publications/traderbots-a-new-paradigm-for-robust-and-efficientmultirobot-coordination-in-dynamic-environments/.

10.

Choi

Kim

Johnson

. Potential game-theoretic analysis of a market-based decentralized task allocation algorithm. In: Distributed autonomous robotic systems. Springer, 2016, pp. 207–220.

11.

Sheng

Yang

. Multi-robot area exploration with limited-range communications. In: Proceedings of IEEE/RSJ international conference on intelligent robots and systems (IROS), Sendai, Japan, 28 September–2 October 2004, vol. 2, pp. 1414–1419. IEEE.

12.

Tang

Parker

. Distributed multi-robot coalitions through ASyMTRe-D. In: IEEE/RSJ international conference on intelligent robots and systems (IROS), Edmonton, Alberta, Canada, 2–6 August 2005, pp. 2606–2613. IEEE.

13.

Gerkey

Matarić

. A formal analysis and taxonomy of task allocation in multi-robot systems. Int J Robot Res 2004; 23(9): 939–954.

14.

Zeng

Meng

. Gini coefficient-based task allocation for multi-robot systems with limited energy resources. IEEE/CAA J Autom Sin 2018; 5(1): 155–168.

15.

Lukic

Barnawi

Stojmenovic

. Robot coordination for energy-balanced matching and sequence dispatch of robots to events. IEEE Trans Comput 2015; 64(5): 1416–1428.

16.

McMillen

Stubbs

Rybski

. Resource scheduling and load balancing in distributed robotic control systems. Robot Auton Syst 2003; 44(3-4): 251–259.

17.

Lee

Han

Kim

. Market-based multiagent framework for balanced task allocation. In: Robot intelligence technology and applications 2012 Advances in intelligent systems and computing, Vol. 208, 2013, pp. 549–559. Berlin, Heidelberg: Springer. https://link.springer.com/chapter/10.1007/978-3-642-37374-9_53.

18.

Lagoudakis

Markakis

Kempe

. Auction-based multi-robot routing. In: Robotics: science and systems (RSS), Cambridge, MA, USA, 8–11 June 2005, Vol. 5, pp. 343–350.

19.

Tovey

Lagoudakis

Jain

. The generation of bidding rules for auction-based robot coordination. In: Multi-robot systems. From swarms to intelligent automata, 2005, Vol. 3, pp. 3–14. Dordrecht: Springer. https://link.springer.com/chapter/10.1007/1-4020-3389-3_1.

20.

Koenig

Keskinocak

Tovey

. Progress on agent coordination with cooperative auctions. In: AAAI, Atlanta, USA, 11–15 July 2010, Vol. 10, pp. 1713–1717.

21.

Nanjanath

Gini

. Repeated auctions for robust task execution by a robot team. Robot Auton Syst 2010; 58(7): 900–909.

22.

Michel

Cyberbotics ltd. Webots™: professional mobile robot simulation. Int J Adv Robot Syst 2004; 1(1): 5.

23.

Lorenz

. Methods of measuring the concentration of wealth. Pub Am Stat Assoc 1905; 9(70): 209–219.

24.

Gini

. Concentration and dependency ratios. Riv Polit Econ 1997; 87: 769–792.

25.

Sadras

Bongiovanni

. Use of Lorenz curves and Gini coefficients to assess yield inequality within paddocks. Field Crop Res 2004; 90(2-3): 303–310.

Competency adjustment and workload balancing framework in multirobot task allocation

Abstract

Keywords

Introduction

Competency and workload balancing framework

Robot capability matrix

Task requirement matrix

Bid process

Auction process

Utility weight generation module

Utility generation module

Task trading

Comparison with existing approaches

Cleaning mission

Heterogeneous robots

Tasks

Performance evaluation

Simulation results

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References