# Inferring Implicit Trait Preferences for Task Allocation in Heterogeneous
Teams

Vivek Mallampati,Harish Ravichandar  Georgia Institute of Technology
Atlanta, USA
<EMAIL_ADDRESS>
###### Abstract

Task allocation in heterogeneous multi-agent teams often requires reasoning
about multi-dimensional agent traits (i.e., capabilities) and the demands
placed on them by tasks. However, existing methods tend to ignore the fact
that not all traits equally contribute to a given task. Ignoring such inherent
preferences or relative importance can lead to unintended sub-optimal
allocations of limited agent resources that do not necessarily contribute to
task success. Further, reasoning over a large number of traits can incur a
hefty computational burden. To alleviate these concerns, we propose an
algorithm to infer task-specific trait preferences implicit in expert
demonstrations. We leverage the insight that the consistency with which an
expert allocates a trait to a task across demonstrations reflects the trait’s
importance to that task. Inspired by findings in psychology, we account for
the fact that the inherent diversity of a trait in the dataset influences the
dataset’s informativeness and, thereby, the extent of the inferred preference
or the lack thereof. Through detailed numerical simulations and evaluations of
a publicly-available soccer dataset (FIFA 20), we demonstrate that we can
successfully infer implicit trait preferences and that accounting for the
inferred preferences leads to more computationally efficient and effective
task allocation, compared to a baseline approach that treats all traits
equally.

##  I Introduction

Heterogeneous multi-agent systems have demonstrated their effectiveness in
solving complex problems in a wide variety of domains, such as agriculture
[1], environmental monitoring [2, 3], defense [4], construction [5], warehouse
automation [6], and assembly [7]. To effectively coordinate such heterogeneous
teams, researchers have been studying the Multi-Robot Task Allocation (MRTA)
problem [8] and have developed various solution frameworks, ranging from
market-based approaches that auction tasks to agents based on their utilities
[9], to the recent advances in trait-based approaches that reason about how
agents’ capabilities come together to satisfy multi-dimensional requirements
placed on them by tasks [10, 11].

However, existing approaches to MRTA often consider all traits (i.e.,
capabilities) to be equally beneficial to a task, ignoring underlying human
preferences or the relative importance between traits[10, 11]. For instance,
while the color of a robot might be crucial for a task that requires
camouflage, it is likely to be irrelevant in most other tasks. Ignorance of
such distinctions can lead to sub-optimal task allocations that attempt to
satisfy irrelevant requirements, placing an additional and unnecessary burden
on the team’s limited resources (i.e., agents and their capabilities).

In this work, we model and infer task-specific preferences over traits in
contexts requiring the satisfaction of specific multi-dimensional
requirements. While preference learning is a well-studied problem in other
fields (e.g., Human-Robot Interaction (HRI) [12]), it is often overlooked in
MRTA problems. We argue and demonstrate that inferring and explicitly
accounting for such preferences will lead to a more effective allocation of
agents to tasks, especially when dealing with teams with limited capabilities
and tasks that demand the satisfaction of certain minimum requirements.

Figure 1: An overview of the proposed approach to infer implicit trait
preferences from expert demonstrations and perform coalition formation based
on the inferred preferences.

One way to account for trait preferences is to require users to specify them.
However, it is known that humans struggle to explicitly specific preferences
that capture trade-offs between various factors but are adept at solving
complex problems with such characteristics [13]. As such, we take the approach
of inferring preferences that are implicit in expert demonstrations of task
allocation.

To infer implicit preferences, we first leverage the insight from
psychology[14] that the more important or preferred a trait, the more
consistent its appearance in the demonstrations (i.e., observed variation).
For example, if a task is consistently allocated agents who can move at a
certain speed, speed is likely an important trait for that task. We compute
the coefficient of variation of each trait assigned to a task to capture its
consistency.

While capturing the consistency of a trait helps infer preference, it is often
insufficient. Specifically, the extent to which a trait can appear to be
consistent in the demonstrations is limited by how variable the corresponding
capability is in the team prior to allocation (i.e., its inherent diversity).
Indeed, studies in psychology literature demonstrate that humans’ ability to
infer preferences increases with the diversity of demonstrations [15]. For
instance, if all teams used in the demonstrations only have agents that move
at the same speed, the consistency noted in the above example would be
inevitable and uninformative. To account for this influence, we develop a
method to combine observed variation with inherent diversity such that
inherent diversity limits the range of possible preference values based on the
teams that were available to the expert, and observed variation informs the
specific value of importance within this range based on the expert
demonstrations.

Finally, we formulate a constrained optimization problem that allocates agents
to tasks while accounting for the inferred trait preferences. Notably, since
the inferred preferences are over traits (and not robots), we can perform
preference-informed task allocation on teams with entirely new agents as long
as we have access to the agents’ traits. Further, we can improve computational
efficiency by reducing of the number of traits the optimization problem needs
to consider by removing traits with preference values below a certain
threshold. Figure 1 provides a complete overview of our approach.

In summary, our contributions include

  * •

A method to infer implicit trait preferences from expert demonstrations by
observing the consistency (or variation) in allocations,

  * •

Incorporating insights from psychology to alter inferred preferences based on
the inherent diversity of each trait in the teams prior to allocation, and

  * •

A constrained optimization routine capable of forming coalitions based on the
inferred preference.

We evaluated our approach using extensive numerical simulations and a
publicly-available soccer dataset (FIFA 2020) and compared its performance
against that of a baseline that treats all traits equally. Our results
conclusively demonstrate that inferring and accounting for trait preferences
i) improves computational efficiency and allocation quality and ii) can
significantly reduce the number of dimensions (i.e., traits) that need to be
considered with little to no drop in allocation quality.

##  II Related Works

Reasoning on how to infer preferences from an expert demonstration and use
them in task allocation is a combination of several different research fields.
The total problem can be split into two main sub-problems: i) inferring
preferences and ii) task allocation. Even though there is extensive work done
in each of the fields, the lack of literature on the intersection has caught
our attention and motivated us to take up this problem. We believe that
leveraging the insights in each of field and combining them will provide us
with better performance of heterogeneous teams.

In this section, we discuss the prior works done on the topics which are
closer to our problem and have solved a part of the problem we are looking
into.

###  II-A Coalition Formation

According to the survey [15] of the field of MRTA, the problems can be
categorized based on three dimensions: robot type (Single Robot (SR) vs.
Multi-Robot (MR)), task type (Single-Task (ST) vs. Multi-Task(MT) robots), and
Allocation type (Instantaneous assignment (IA) vs. time-extended assignment
(TA)). Our work addresses the coalition formation problem, which is an
instance of the ST-MR-IA.

Coalition formation (ST-MR-IA) problems have been tackled with utility-based,
market-based approaches [9], and trait-based [10] approaches. Utility-based
approaches showed that they could form optimal coalitions [16], but designing
the utility functions requires domain knowledge and often for specific tasks
and agents. The market-based approaches have successfully tackled a variety of
coalition formation problems using auction mechanisms through which robots bid
on tasks [17]. The extensive reliance on the communication between the agents
and bidding tasks limits the approach’s scalability. The trait-based task
allocation models the agents with capabilities (i.e., traits) and tasks as
trait aggregations. The framework provides with the advantages of scalability
of the size of the robot team and generalizability to new robot teams [10, 18,
11]. We adopt this framework and model our agents as a set of traits and the
tasks as trait aggregation requirements. All the approaches assume that the
task is well-defined, which is not true in complex real-world settings.

###  II-B Learning from Demonstrations

Trying to tackle the challenge of not knowing the task requirements and all
constraints, there are developed learning algorithms that try to learn from
the expert human demonstrations [19]. Learning methods are also used for
market-based coalition formation approaches where the algorithm was trying to
find the prices[20]. There has been a structured prediction approach [21] for
task allocation that uses a combination of reinforcement learning and
quadratic integer programming for learning directly from data to optimize
assignments of homogeneous teams of robots. The recent literature using the
trait-based framework enables us to extract the task requirement and work
under resource constraints [18]. Learning from the demonstrations for trait-
based task allocation [18] enables the algorithms to learn the task
requirements and generalize it to new robot teams. The one fundamental
assumption the existing trait-based task allocation methods make is that they
treat all the traits to be equally important. Our approach tries to loosen
this assumption and uses the inferred preferences in the optimization of
coalition formation.

###  II-C Preference Learning

Preference is a very prevalent topic in the fields relating to human
psychology [22]. From child psychology[15] to the field of Human-Robot
Interaction (HRI) [12], preference has been studied in detail and has been
given great importance. Literature in human behavior[14] talks about how ”not
all dimensions of personality are equally relevant to all persons,” which in
our work is true with the traits of the agents. Even though it is fascinating,
to the best of our knowledge, the concept of preference is ignored in the MRTA
approaches and not considered in solving coalition formation problems.

##  III Problem formulation

In this section, we formulate the problem of inferring trait preferences in
heterogeneous task allocation. We begin with basic terminology and definitions
inspired by recent advances in trait-based task allocation [10, 18, 11].

Let a heterogeneous team composed of $S$ species (i.e., types of agents) with
$A_{s}$ agents in the $s^{th}$ species. This heterogeneous team is required to
perform $M$ concurrent tasks denoted by $T=\\{T_{1},\dots,T_{M}\\}$.

The traits (i.e., capabilities) of the team are encoded by its Species-Trait
matrix $Q=[q_{1},\dots,q_{S}]^{T}\in\mathbb{R}_{\geq 0}^{S\times U}$, where
$q_{s}\in\mathbb{R}_{\geq 0}^{U}$ is a vector of $U$ number of traits
associated with Species $s$.

The Assignment matrix $X\in\mathbb{Z}_{\geq 0}^{M\times S}$ encodes the
allocations, where Assignment $x_{ms}$ is the number of agents from Species
$s$ assigned to Task $T_{m}$.

The Trait-Requirement matrix $Y\in\mathbb{R}_{\geq 0}^{M\times U}$ given by

$\displaystyle{\mathbf{Y}=\mathbf{X}\mathbf{Q}}$ (1)

captures the aggregation of traits assigned to tasks, with $Y_{mu}$ indicating
the amount of the Trait $u$ is required by Task $T_{m}$.

Let $\mathcal{D}=\\{X^{(i)},Q^{(i)}\\}^{N}_{i=1}$ be the set of Expert
Demonstrations, where $X^{(i)}$ represents the expert-specified assignment
matrix for a team with traits encoded by the Species-Trait matrix $Q^{(i)}$.
We assume that the expert allocates tasks by minimizing the following weighted
cost function

$\displaystyle X^{(i)}=\arg\min_{X}||{Y^{*}}-XQ_{i}||_{W^{*}},\forall
i=1,\cdots,N$ (2)

where $Y^{*}$ and $W^{*}\in\mathbb{R}_{\geq 0}^{M\times U}$ are hidden trait
requirements and the associated trait preferences employed by the expert.

Problem Statement: Given Demonstrations $\mathcal{D}$, we wish to infer
implicit trait requirements $\hat{Y}^{*}$ and the associated trait preferences
$\hat{W}$.

##  IV Inferring Trait Preferences

Our proposed approach extracts the trait preferences from the given set of
demonstrations which will be used to enhance the task-trait assignments. A
secondary objective is to fulfill task requirements using as few traits as
possible to reduce the time it takes to optimize the assignment. We begin by
computing the aggregated traits across tasks for each demonstration as
follows:

$\displaystyle Y^{(i)}=X^{(i)}Q^{(i)},\forall i=1,\cdots,N$ (3)

The following two key factors inform our inference method:

  1. 1.

Observed Variation ($CV_{obs}$) captures the variation of each aggregated
trait across the demonstrations for each task. Observed variation captures how
consistently a trait is allocated to a particular task. Our insight here is
that the importance of a trait to a task is inversely proportional to its
variability in the demonstrations. Note that the lower the observed variation,
the higher the chances that the corresponding trait was deliberately chosen to
reflect a consistent value in the allocation. In contrast, larger observed
variation tends to stem from lower preferences for the associated trait. The
key idea is that a trait that a wide variety of values can fulfil is
relatively less preferable as the expert did not focus on matching a specific
value to the considered trait. The observed variation is calculated with the
equation

${CV_{obs}=\frac{\sigma(Y_{\mathcal{D}})}{\overline{Y}_{\mathcal{D}}}}$ (4)

where $Y_{\mathcal{D}}\in\mathbb{R}^{N\times M\times U}$ is the collection of
all aggregated trait matrices from the demonstrations ${Y}^{(i)},\forall
i=1,...,N$,

$\sigma(Y_{\mathcal{D}})$ is the standard deviation of $Y_{\mathcal{D}}$, and
$\overline{Y}_{\mathcal{D}}$ is the mean of $Y_{\mathcal{D}}$, both computed
across demonstrations.

  2. 2.

Inherent Diversity ($CV_{div}$) captures the diversity of each trait in the
demonstrations $\mathcal{D}$. Note that the more abundant a trait, the more
informative the dataset. If all agents in the dataset possess near-identical
amounts of a particular trait, we cannot rely solely on the inevitable low
observed variation and conclude that the trait in question is highly
preferred. The inherent diversity is calculated with the equation

${CV_{div}=\frac{\sigma(Q_{\mathcal{D}})}{\overline{Q}_{\mathcal{D}}}}$ (5)

where $Q_{\mathcal{D}}\in\mathbb{R}^{(N*S)\times U}$ is the collection of all
species-trait matrices from the demonstrations ${Q}^{(i)},\forall i=1,...,N$,

$\sigma(Q_{\mathcal{D}})$ is the standard deviation of $Q_{\mathcal{D}}$, and
$\overline{Q}_{\mathcal{D}}$ is the mean of $Q_{\mathcal{D}}$.

Note that we use the coefficient of variation and not the variance of the
aggregations, as it permits scale-independent comparisons [23] while
quantifying the ”spread” of the data. Directly computing variances will
mislead the algorithm to assign higher importance to lower-magnitude traits
than higher-magnitude traits.

In humans, inferring preferences is a very natural phenomenon [15]. Psychology
studies on human behavior explain how consistent selection and human
preference are related [14]. This insight helps us in modeling the Observed
Variation as a variable that helps infer relative importance. We also came
across a child psychology study on inferring preferences that indicates a
linear relationship between to variation of the demonstrations and the average
number of correct target picks (most preferred object) [15]. We try to
incorporate this idea of the importance of a variety of trait values in
demonstrations through the concept of Inherent Diversity.

Weight Function: We propose the following weight function that encodes the
preference over traits by combining Observed Variation and Inherent Diversity.

${\hat{W}=\frac{CV_{div}}{\tau}cos(\alpha CV_{obs}+\beta)+\textit{c}}$ (6)

Note that the weight function is a cosine function whose amplification factor
is dictated by Inherent Diversity, and the independent variable is Observed
variation. We used the cosine function to combine because of the linear
amplification feature, and with scaling and translations, it is monotonically
decreasing in the desired range. $\tau$ in the equation 6 is the amplification
factor. It regulates how much the inherent diversity affects the weight
function. $\alpha$ and $\beta$ are the factors that manipulate the observed
variation and its impact on the weight function. The range of the weight
function and the possible output values can be altered by the combination of
$\alpha$ and $\beta$. Lastly, c is the centering variable. The weight function
output equal to c means that it essentially has no information about the
relative preference.

${\hat{W}=\frac{CV_{div}}{2}cos(2CV_{obs}+0.5)+0.5}$ (7)

We have defined with $\alpha=2$,$\tau=2$, and $\beta=0.5$ to make the inherent
diversity and observed variation in the range [0,1] and have the inferred
weights values be in the range [0,1]. The weight function in Eq 7 value of 0
means it is not at all important, and the value of 1 means it is the most
important. The result of the weight function being 0.5 indicates that the
trait preference is inconclusive. The $\textit{c}=0.5$ in the weight function
helps us to show that having no inherent diversity will result in inconclusive
weight preference as we can not interpret the lower observed variation because
of a lack of choice in the dataset or because it was an extremely important
trait value. The heat-map from Figure 2 displays the values of the equation 7
over the total input space. We can clearly see that as the inherent diversity
increases, the observed variance’s possible values can increase. Inherent
diversity acts like a range-increasing function for the observed variation
variable in the weight function.

Figure 2: Heatmap of the outputs of the proposed weight function

The algorithm for the weight extraction can be seen in Algorithm 1 to see the
steps for extracting variations and finding the weight matrix for the given
set of demonstrations.

Input : Demonstrations $\mathcal{D}=\\{X^{(i)},Q^{(i)}\\}_{i=1}^{N}$

Output : $\hat{W}$

1 Calculate the trait-aggregation $Y_{\mathcal{D}}$ as shown in Equation 3

2Aggregate all the trait from demonstrations into $Q_{\mathcal{D}}$

3Calculate the observed variation $CV_{obs}$ as shown in Equation 4

4Calculate the inherent diversity $CV_{div}$ as shown in Equation 5

5Calculate the inferred weight $\hat{W}$ using the Equation 7

return $\hat{W}$

Algorithm 1 Inferring Trait Preferences

The algorithm for the task allocation, unlike the optimizations in prior works
[10, 11, 18], incorporates weights. One critical note is that the estimation
of $\hat{Y}^{*}$ is done simply by taking the mean of the $Y_{\mathcal{D}}$ we
calculated from the demonstrations. The key assumption here is that all the
demonstrations are optimal; hence, the average of the task-trait aggregations
will provide us with the optimal $\hat{Y}^{*}$ that the new teams need to
reach. The algorithm 2 outlines the procedure taken by the algorithm to do the
weighted optimization for allocating a new team of agents for the same set of
tasks.

Input : New species-trait matrix ($Q_{j}$), $\hat{W}$, and $Y_{\mathcal{D}}$

Output : $\hat{X}_{j}$

1 $\hat{Y}^{*}=$ mean of $Y_{\mathcal{D}}$

2$\hat{X}_{j}=\underset{X}{\mathrm{argmin}}||{\hat{Y}^{*}}-XQ_{j}||_{\hat{W}}$

return $\hat{X}_{j}$

Algorithm 2 Preferential Task Allocation

##  V Experimental Evaluation

We evaluated the efficacy and need for the proposed approach using the
following sets of experiments.

###  V-A Numerical Simulations

Setup: The first step of the experiment is creating a demonstration set that
mimics expert behavior. The basic setup of the demonstrations included agents
from three species allocated to three tasks. Each of the species has three
traits and 15 agents available. Handcrafting the optimal weights ($W^{*}$),
which describe the behavior of the demonstrations, we created a pipeline that
consistently models Species-trait matrices $Q$ and solves for the assignment
matrices $X$ using equation 2 to simulate the expert demonstrations for
allocating robots for the given tasks. In order to simulate the $Q$ for the
demonstrations, we use the following hand-crafted mean ($\mu$) and standard
deviation ($\sigma$) matrices:

$\mu_{(M\ X\ U)}=\begin{bmatrix}10&5&20\\\ 5&20&10\\\ 20&10&5\\\
\end{bmatrix}\sigma_{(M\ X\ U)}=\begin{bmatrix}2&1&3\\\ 1&3&2\\\ 3&2&1\\\
\end{bmatrix}$

To make the simulations extensive, we create 1000 demonstrations with various
optimal weights which simulate intrinsic preferences. Across all the three
tasks, few optimal weights we test on are:

  1. 1.

Single important trait: $W^{*}=[0,1,0]$ This is where there is one most
crucial trait and model the demonstration such that the expert only considers
that trait when allocating.

  2. 2.

Unique Large Weight differences: $W^{*}=[0.6,0.3,0.1]$ This is where there is
one trait that has a lot higher preference. The three traits are non zero
distinct values indicating that the user has some preference associated.

  3. 3.

Equal Large Weight differences: $W^{*}=[0.8,0.1,0.1]$ This is where there is
one trait that has a lot higher preference. The other two traits are equal non
zero indicating that the user has some preference associated.

  4. 4.

Closer Weights: $W^{*}=[0.5,0.3,0.2]$ This is where all three traits have some
preference. We can see that relative importance is different for each trait.

Baselines: We compare the performance of our approach against the following
baselines:

  1. 1.

No Preference: The baseline was implemented by previous works[10, 18] where
the preferences of the traits are not considered. The baseline uses the
$\hat{Y}^{*}$ shown in the algorithm 2. Calculates the $\hat{X}_{j}$ using the
equation 2

  2. 2.

No Inherent Variation: The baseline follows the algorithm 2, with a variation
in algorithm 1. The baseline skips line 4 of the algorithm 1 and assigns
$CV_{div}$ to be an array of $0.5$s. Inherent diversity set to 0.5 for all
traits in every task indicates that there is no consideration of inherent
variation.

Results: We evaluate our numerical experiments using quantitative metrics on
the performance of the task allocation and inferring preferences.

The primary metric we used to evaluate the inferring of preferences is
ordering. The ordering of the weights is a crucial metric when we know the
optimal weights, as the order of preferences is directly implied by the
arrangement of the weights.

We observe that for all the different scenarios mentioned in setup, where
demonstrations were constructed with different optimal weights, the Algorithm
1 100% successfully extracts the weights, preserving the weights’ ordering
across the tasks. Even in the situations where the weights are close, the
ordering of the weights were not compromised.

Knowing that the weights inferred are evaluated to be good, we explore the
impact of using the weights in task allocation. We use the metric of
allocation quality by computing the trait mismatch error. A lower weighted
mismatch error indicates that the allocation quality has increased, implying
the most important traits have been fulfilled.

Figure 3: In numerical simulations, inferring and accounting for preferences
consistently results in lower ground-truth-weighted trait mismatch errors.

Figure 3 shows the comparison between our approach against the baselines
across all three tasks. We can observe that across the tasks, our method
outperforms the baseline methods by having a median, mode, and mean lower for
the weighted error. These observations are consistent across various scenarios
with different hand-crafted weights ($W^{*}$).

We have done a statistical analysis of the results from all three methods. We
ran Kruskal Wallis on all three methods for each task to see that there is
significance between all three methods. We went on to do a pairwise Mann-
Whitney U Test to check the relationships between the two methods.

The table below provides the p-value of the Mann-Whitney U Test, in which Pair
1 is the comparison between the two baselines (No preference and No inherent
diversity). Pair 2 is the comparison between the No preference baseline and
our approach. Pair 3 is the comparison between the No inherent diversity
baseline and our approach.

Task Number | Pair 1 | Pair 2 | Pair 3
---|---|---|---
Task 1 | 7.595e-07 | 8.326e-11 | 0.027
Task 2 | 4.388e-08 | 5.061e-12 | 0.057
Task 3 | 1.831e-05 | 1.077e-07 | 0.231
TABLE I: Non-parametric test p-values

Figure 3 has pair-wise relationships, and in situations where the p-value $>$
0.05 is denoted with ‘ns’ to indicate non-significance. We see a significant
difference between the no preference baseline and our approach, indicating
that utilizing the preferences results in better trait satisfaction. We can
also observe that using only the Observed Variation can enhance performance.
Further, using the inherent diversity along with observed variation results in
the best allocations in terms of trait satisfaction.

We also investigated if the number of demonstrations plays a crucial role in
the extraction of weights and in the weighted error difference between the
target requirements $\hat{Y}^{*}$ and the trait aggregation achieved by the
formed coalition ($Y=XQ$). Our results suggest that our ability to infer trait
preference gracefully degrades as we reduce the number of demonstrations (1000
demos: 100%, 900 demos: 98.5%, 800 demos: 95.4% … 200 demos: 86.3%, 100 demos:
81.3%)

###  V-B Soccer Dataset

Idea: Most multi-agent task allocation approaches to showcase their results on
simulated data or data explicitly created for a set of robots. We have taken a
step forward in extending our work to test real-life datasets from the domain
of sports. We have chosen the game of soccer and tried to map it into a multi-
agent task allocation problem.

Each game position is modeled as the tasks and the players as agents. The task
allocation problem, in this scenario, is allocating given agents (players) to
one of the four tasks (game positions): forward, midfield, defense, and
goalkeeper. Given new soccer players with traits, the optimization tries to
match the trait aggregation requirement for every task (game position) to
create a soccer team of 11 players with 1 goalkeeper, 2 forwards, 4 defenders
and 4 midfielders.

Figure 4: Our inference and allocation approach helps significantly increase
the percentage of successful allocations in FIFA 2020 dataset.

Setup: Using the open source FIFA 2020 dataset from Kaggle [24], we started to
design the experiment. Pre-processing the data was crucial to fit the modeling
framework we chose in our approach. Similar to our numerical simulations, we
wanted to have a set of demonstrations. The FIFA 2020 player dataset has 18278
players, each with 104 columns of information. As part of the pre-processing,
the dataset was trimmed down only to contain the necessary numerical
capabilities of players. We removed all the inactive and substitute players
and players with missing capabilities to make the dataset consistent. To make
the demonstrations consistent, we have filtered our dataset to have players
with FIFA 2020 players’ ’Overall’ between 60-70 (inclusive). The final
demonstrations we use have 37 traits and around 3600 players. We have taken
the average of all players’ traits assigned to a particular task (game
position) given in the dataset to create the $\hat{Y}^{*}$.

From the processed dataset, both the $Q_{\mathcal{D}}$ and $Y_{\mathcal{D}}$
for the soccer experiment were generated directly. Knowing the
$Q_{\mathcal{D}}$ and $Y_{\mathcal{D}}$, we can use the algorithm 1 to get the
weight matrix which indicates inferred preferences of traits for every task.
Creating a new 11-player team from the dataset, we ran algorithm 2 to see if
the algorithm could classify the players to their original game positions in
the FIFA 2020 dataset.

Results: Given the lack of ground-truth trait preference ($W^{*}$) in this
dataset, we cannot directly evaluate the accuracy of our inferred preferences.
Instead, we extensively analyzed the impact of preference-based task
allocation on computation time and allocation score.

Figure 4 clearly shows that our method using both observed variation and
inherent diversity increases the allocation score. The statistical
significance (p-value $>$ 0.05) calculated using Kruskal–Wallis test between
the Baseline allocation score and Our Method allocation score, clearly shows
our method outperforms the baseline.

Inferring the preferences has enabled our approach to use the k-most important
traits with higher preferences than others, where k is the number of traits we
want to use in allocation. Reduction in the dimensionality of the optimization
problem has resulted in a decrease in computational time. The green line in
Figure 5 shows how the time increases with the number of traits used. The time
is normalized with the total time taken by the baseline, which doesn’t
consider preference.

Figure 5: Our inference and allocation approach helps significantly reduce the
trait dimensions without sacrificing allocation quality in FIFA 2020 dataset.

The second metric of evaluation we used was the successful allocation
percentage. We define the successful allocation by comparing the allocations
made by the algorithm and the original game positions given in the dataset.
The total number of possible allocations is the team size (11 for soccer). The
percentage is taken by the number of positions matching between the dataset
and allocation divided by team size. The pink line in Figure 5 shows how the
score (i.e., successful allocations) increases with the number of traits used.
The score is normalized with the score achieved by the baseline, which doesn’t
consider preference. The light pink region shows the standard deviation of the
teams’ scores across different traits.

We have plotted both time and successful allocation percentages across the
number of traits to show that our approach can significantly reduce the number
of dimensions (i.e., traits) that needs to be considered while allocating
agents without compromising allocation quality. We can infer from the graph
that an allocation using only 12 trait weights can achieve the baseline’s
accuracy by being more than 52% faster. Compromising on less than 5% of
baseline accuracy can result in a reduction of 75% of the time taken by the
baseline. Experiments on the FIFA 2020 dataset show that learning preferences
and preference-based task allocation can increase task performance.

##  VI Conclusion

We proposed a novel method to infer implicit trait preference from
heterogeneous multi-agent task allocation demonstrations. Our method reasons
about i) observed variation: the consistency with which traits appear across
demonstrated allocation, and ii) inherent diversity: the variability of traits
in the overall teams prior to allocation. Our results demonstrate that
inferring and accounting for preferences during allocation can considerably
improve trait satisfaction and computational efficiency. While not considered
in this work, the proposed preferential task allocation can be integrated into
larger frameworks, such as GRSTAPS [11], in which task allocation serves as
one of the many layers of coordination. While our relatively simple method has
proven effective, future work must address how one can reliably infer
preferences in more complex settings using advanced learning techniques, such
as contrastive learning, especially when dealing with noisy and low-diversity
datasets. A notable limitation of our work is that it is limited to contexts
with tasks that require meeting specific trait requirements. As such, our
method can not handle tasks in which certain capabilities merely need to be
maximized. Inferring preferences in such circumstances remains an unsolved
problem.

## References

  * [1] P. Tokekar, J. Vander Hook, D. Mulla, and V. Isler, “Sensor planning for a symbiotic uav and ugv system for precision agriculture,” in _2013 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2013, pp. 5321–5326.
  * [2] T. Salam and M. A. Hsieh, “Heterogeneous robot teams for modeling and prediction of multiscale environmental processes,” _CoRR_ , vol. abs/2103.10383, 2021.
  * [3] M. S. Couceiro, D. Portugal, J. F. Ferreira, and R. P. Rocha, “Semfire: Towards a new generation of forestry maintenance multi-robot systems,” in _2019 IEEE/SICE International Symposium on System Integration (SII)_ , 2019, pp. 270–276.
  * [4] C. J. McCook and J. M. Esposito, “Flocking for heterogeneous robot swarms: A military convoy scenario,” in _2007 Thirty-Ninth Southeastern Symposium on System Theory_ , 2007, pp. 26–31.
  * [5] J. Werfel, K. Petersen, and R. Nagpal, “Designing collective behavior in a termite-inspired robot construction team,” _Science_ , vol. 343, no. 6172, pp. 754–758, 2014. [Online]. Available: https://www.science.org/doi/abs/10.1126/science.1245842
  * [6] N. Baras and M. Dasygenis, “An algorithm for routing heterogeneous vehicles in robotized warehouses,” in _2019 Panhellenic Conference on Electronics & Telecommunications (PACET)_, 2019, pp. 1–4.
  * [7] A. Stroupe, T. Huntsberger, B. Kennedy, H. Aghazarian, E. Baumgartner, A. Ganino, M. Garrett, A. Okon, M. Robinson, and J. Townsend, “Heterogeneous robotic systems for assembly and servicing,” 08 2005.
  * [8] B. P. Gerkey and M. J. Matarić, “A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems,” _The International Journal of Robotics Research_ , vol. 23, no. 9, pp. 939–954, Sep. 2004. [Online]. Available: http://journals.sagepub.com/doi/10.1177/0278364904045564
  * [9] K. Ayorkor, S. Anthony, and D. Bernardine, “A comprehensive taxonomy for multi-robot task allocation - G. Ayorkor Korsah, Anthony Stentz, M. Bernardine Dias,,” 2013. [Online]. Available: https://journals.sagepub.com/doi/10.1177/0278364913496484
  * [10] H. Ravichandar, K. Shaw, and S. Chernova, “STRATA: A Unified Framework for Task Assignments in Large Teams of Heterogeneous Agents,” _arXiv:1903.05149 [cs]_ , Feb. 2020, arXiv: 1903.05149. [Online]. Available: http://arxiv.org/abs/1903.05149
  * [11] A. Messing, G. Neville, S. Chernova, S. Hutchinson, and H. Ravichandar, “GRSTAPS: Graphically Recursive Simultaneous Task Allocation, Planning, and Scheduling,” _The International Journal of Robotics Research_ , vol. 41, no. 2, pp. 232–256, Feb. 2022. [Online]. Available: http://journals.sagepub.com/doi/10.1177/02783649211052066
  * [12] S. Rossi, F. Ferland, and A. Tapus, “User profiling and behavioral adaptation for hri: A survey,” _Pattern Recognition Letters_ , vol. 99, pp. 3–12, 2017, user Profiling and Behavior Adaptation for Human-Robot Interaction.
  * [13] J. Rieskamp, J. Busemeyer, and T. Laine, “How do people learn to allocate resources? comparing two learning theories,” _Journal of experimental psychology. Learning, memory, and cognition_ , vol. 29, pp. 1066–81, 12 2003.
  * [14] S. V. Paunonen, “Trait relevance and the differential predictability of behavior,” _Journal of Personality_ , vol. 56, no. 3, pp. 599–619, 1988\. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-6494.1988.tb00904.x
  * [15] T. Kushnir, F. Xu, and H. M. Wellman, “Young children use statistical sampling to infer the preferences of others,” _Psychological science_ , vol. 21, no. 8, pp. 1134–1140, Aug. 2010. [Online]. Available: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3785083/
  * [16] L. Vig and J. Adams, “Multi-robot coalition formation,” _IEEE Transactions on Robotics_ , vol. 22, no. 4, pp. 637–649, 2006.
  * [17] J. Guerrero and G. Oliver, “Multi-robot task allocation strategies using auction-like mechanisms,” _Artificial Research and Development in Frontiers in Artificial Intelligence and Applications_ , vol. 100, pp. 111–122, 2003.
  * [18] A. Srikanthan and H. Ravichandar, “Resource-Aware Generalization of Heterogeneous Strategies for Coalition Formation,” _arXiv:2108.02733 [cs]_ , Aug. 2021, arXiv: 2108.02733. [Online]. Available: http://arxiv.org/abs/2108.02733
  * [19] L. Panait and S. Luke, “Cooperative multi-agent learning: The state of the art,” _Autonomous agents and multi-agent systems_ , vol. 11, no. 3, pp. 387–434, 2005.
  * [20] F. Duvallet and A. Stentz, “Imitation learning for task allocation,” in _2010 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2010, pp. 3568–3573.
  * [21] N. Carion, N. Usunier, G. Synnaeve, and A. Lazaric, “A structured prediction approach for generalization in cooperative multi-agent reinforcement learning,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [22] D. Kahneman and A. Tversky, “The psychology of preferences,” _Scientific American_ , vol. 246, no. 1, pp. 160–173, 1982. [Online]. Available: http://www.jstor.org/stable/24966506
  * [23] C. E. Brown, _Coefficient of Variation_ , 1998, pp. 155–157.
  * [24] S. Leone. FIFA 20 complete player dataset, kaggle. [Online]. Available: https://bit.ly/3Sd516U