# Dynamic Decentralized 3D Urban Coverage and Patrol with UAVs

Wai Lun Leong12, Jiawei Cao1, and Rodney Swee Huat Teo1
1National University of Singapore, Singapore.
2Corresponding author. Email<EMAIL_ADDRESS>
###### Abstract

In the event of natural or man-made disasters in an urban environment, such as
fires, floods, and earthquakes, a swarm of unmanned aerial vehicles (UAVs) can
rapidly sweep and provide coverage to monitor the area of interest and locate
survivors. We propose a modular framework and patrol strategy that enables a
swarm of UAVs to perform cooperative and periodic coverage in such scenarios.
Our approach first discretizes the area of interest into viewpoints connected
via closed paths. UAVs are assigned to teams via task allocation to
cooperatively patrol these closed paths. We propose a minimal, scalable, and
robust patrol strategy where UAVs within a team move in a random direction
along their assigned closed path and “bounce” off each other when they meet.
Our simulation results show that such a minimal strategy can exhibit an
emergent behaviour that provides periodic and complete coverage in a 3D urban
environment.

##  I Introduction

In recent years, the urban setting has become a common backdrop for natural or
man-made disasters. In such settings, the vertical dimension becomes an
important consideration and the role of unmanned aerial vehicles or UAVs for
search and rescue purposes have become increasingly prevalent [1]. A
cluttered, low-rise and built-up urban neighbourhood can be cooperatively
searched and continuously monitored using multiple UAVs to locate survivors
who may have emerged from or become trapped in buildings, or are awaiting
rescue in the aftermath of events such as fires, floods, or earthquakes.

In the 3D urban coverage and patrol problem, a team of UAV agents equipped
with cameras is assigned to cover and patrol an urban environment that
consists of buildings represented by right prisms. The facades and roof of
each building within this environment must be covered with some image quality
constraints to enable object detection, therefore, an agent cannot simply move
until the entire facade is fully visible within its camera field of view
(FOV). In addition, we also assume that there are not enough agents to provide
continuous coverage over the environment and therefore the agents must move or
patrol continuously and provide periodic coverage over each part of the
facade.

In the context of this problem, we consider the use of multirotor UAV agents.
Multirotor UAVs offer advantages over their fixed-wing counterparts such as
vertical takeoff and landing, hovering capability, and ease of operation,
making them suited for tasks requiring precise maneuvering in confined or
dynamic urban environments. Their ability to operate at lower altitudes and
excel in close proximity missions further enhances their suitability for
applications such as inspection, surveillance, and search and rescue.

In the following, we examine related works that enable multi-robot systems to
cooperatively solve the coverage and patrol problem in both 2D and 3D domains,
and note that most of such works are in the 2D domain. We suggest that both
cases are relevant to our problem as the 2D and 3D coverage and patrol problem
can often be reduced to a 1D closed path patrol problem.

Freda et. al. described a distributed 3D multi-robot patrolling and
coordination strategy [2]. Their two-level coordination strategy considers
both topological and metric aspects of the problem. The topological strategy
enables each agent to select and deconflict the next node to visit to minimize
the average global idleness, while the metric strategy performs path planning
and deconfliction. Their proposed approach is applied to unmanned ground
vehicles patrolling a 2D manifold in 3D space but does not consider the
complete coverage of buildings.

Piciarelli and Foresti proposed an algorithm for cooperative coverage and
patrol using reinforcement learning applied to a swarm of drones in an
environment where the different parts of the environment have different
coverage priorities [3]. The problem is modeled as a Markov Decision Process
(MDP) where agents can take various actions such as moving or zooming the
camera, resulting in a reward. Reinforcement learning is used to train a Deep
Q-Network (DQN) model to achieve prioritized drone coverage. However, their
approach does not consider topological altitudes of the environment or
buildings.

Cooperative perimeter surveillance strategies have been proposed for problems
such as monitoring of forest fires [4, 5, 6] and perimeter defense [7]. These
solutions assume that a perimeter can be formed over the area of interest such
that multiple agents can cooperatively partition the path and perform
surveillance using a frequency-based approach. Such strategies have inherent
properties of robustness and fault tolerance as agents meet at some interval
for message and information exchange to improve situation awareness for
coordination, decision making, and reporting.

Various strategies and theoretical optimal solutions have been proposed for
the multi-agent boundary and circular patrol problems by [8] and [9].

Kingston et. al. proposed a method for decentralized perimeter surveillance
using agents modeled as point masses that move at uniform constant velocity,
which provably converges to an optimal behaviour in finite time and accounts
for communications constraints [10]. Each agent moves along the segment of the
linear path it is responsible for and reverses direction upon reaching the
endpoints. When an agent encounters another agent, it re-partitions the path
given the perimeter length and the number of agents relative to its left and
right (determined via message exchange of coordination variables), and moves
to patrol its new perimeter segment. When the algorithm converges and agents
are synchronized in time and space, the oscillation of each agent within its
perimeter segment result in surveillance along the perimeter as well as
periodic communications connectivity and information exchange. The authors
suggest that this can be visualized as beads sliding along a wire.

A similar frequency-based approach is proposed by Acevedo et. al in [11] by
partitioning the problem between homogeneous agents for 2D area coverage. The
authors applied the same method to cooperatively patrol a closed path within a
2D area with heterogeneous agents in [12], which was improved for faster
convergence in [13].

We propose a decentralized and modular framework and patrol strategy for the
multi-agent 3D urban coverage and patrol problem. There are two main problems
to be solved: coverage path planning, where we partition a 3D area of interest
and generate a minimal path within each partition, and the patrol strategy,
where decentralized agents assigned to a particular path coordinate to
partition the path and patrol to provide coverage.

Our method works by breaking the problem down into _viewpoint generation_ ,
_task generation_ , _task allocation_ , and _patrol strategy_. We discretize
and generate viewpoints over buildings in an urban environment, connect the
viewpoints belonging to each building to form a closed path, perform task
allocation of multiple agents to each closed path, and finally partition and
patrol each closed path using a minimal approach where agents “bounce” off
each other along the path. Our modular approach to the problem allows each
part of the problem to be solved and improved easily.

In contrast with [10, 12, 13], which aim to optimally partition a continuous
2D perimeter for surveillance, our approach conducts surveillance over
discrete viewpoints along 3D closed paths. This is achieved through emergent
behaviour resulting from the exchange of local information, without relying on
global information and consensus. In addition, our approach directly addresses
the coverage path planning problem in a 3D environment and our patrol strategy
minimizes computation and communication requirements, making it ideal for
resource-constrained platforms operating in urban settings where communication
signals may be sporadic or limited in range.

##  II Problem Formulation

We define an a priori 3D environment by a set of buildings
$\bm{B}=\\{\bm{B}_{1},\bm{B}_{2},\bm{B}_{3},\dots\\}$. Each building
$\bm{B}_{j}$ is an extruded 2D polygon or right prism described by a tuple
consisting of a 2D polygon $\bm{P}_{j}$ with $n$ 2D points, representing its
2D footprint on the ground level and height $h_{j}$:

$\displaystyle\bm{P}_{j}$
$\displaystyle=[(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{n},y_{n})]$ (1)
$\displaystyle\bm{B}_{j}$ $\displaystyle=\set{\bm{P}_{j},h_{j}}$
$\displaystyle\quad\quad\quad\quad\lvert\bm{P}_{j}\rvert\geq 3,\quad h_{j}>0$

Given $\bm{P}_{j}$ and $h_{j}$, we can generate the 2D polygon representing
the roof surface in 3D coordinates $\bm{R}_{j}$:

$\displaystyle\bm{R}_{j}=[(x_{1},y_{1},h_{j}),(x_{2},y_{2},h_{j}),\dots,(x_{n},y_{n},h_{j})]$
(2)

For the same $\bm{P}_{j}$ and $h_{j}$, we generate $n$ vertical 2D surfaces in
3D coordinates representing the facades of the building:

$\displaystyle\bm{F}_{j_{1}}$
$\displaystyle=[(x1,y1,0),(x2,y2,0),(x2,y2,h_{j}),(x1,y1,h_{j})]$ (3)
$\displaystyle\bm{F}_{j_{2}}$
$\displaystyle=[(x2,y2,0),(x3,y3,0),(x3,y3,h_{j}),(x2,y2,h_{j})]$
$\displaystyle\dots$ $\displaystyle\bm{F}_{j_{n}}$
$\displaystyle=[(x_{n},y_{n},0),(x1,y1,0),(x1,y1,h_{j}),(x_{n},y_{n},h_{j})]$
$\displaystyle\bm{F}_{j}$
$\displaystyle=[\bm{F}_{j_{1}},\bm{F}_{j_{2}},\dots,\bm{F}_{j_{n}}]$

The building $\bm{B}_{j}$ can then also be represented by the set of 3D
surfaces $\bm{S}_{j}$ derived from its original definition:

$\bm{S}_{j}=\bm{F}_{j}\cup\bm{R}_{j}=[\bm{F}_{j_{1}},\bm{F}_{j_{2}},\dots,\bm{F}_{j_{n}},\bm{R}_{j}]$
(4)

For the scope of this work, we define surfaces as the vertical facades and
roofs of buildings, but this method can be applied to any general 3D urban
scenario as long as its features can be decomposed into 3D surfaces, such as
roads, points and areas of interest at ground level, etc.

We assume that our UAV agents are equipped with a gimbal mount that allows the
camera to tilt between forwards and downwards with respect to the UAV’s body
frame. This will allow the agent to view facade surfaces by facing the facade
and pitching the camera forwards, as well as roof surfaces by flying above the
roof and pitching the camera downwards. Given the camera FOV spanning $c_{w}$
degrees in width and $c_{h}$ degrees in height, we select $c_{d}$ such that an
optimal resolution of the surface is obtained for object detection, the width
$f_{w}$, height $f_{w}$, and area $a_{f}$ of the rectangular polygon $p_{v}$
on the surface that can be instantaneously observed by the camera is:

$\displaystyle f_{w}$ $\displaystyle=2\times
c_{d}\times\tan\left(\frac{c_{w}}{2}\right)$ (5) $\displaystyle f_{h}$
$\displaystyle=2\times c_{d}\times\tan\left(\frac{c_{h}}{2}\right)$
$\displaystyle a_{f}$ $\displaystyle=f_{w}\times f_{h}$

Since we do not tilt the camera in directions other than forwards and
downwards with respect to the UAV, the above is sufficient to represent the
camera FOV. In this work, we assume a homogeneous camera capability for all
agents and for heterogeneous cases, it is sufficient to assume the minimum
case.

Given a surface $s\in\bm{S}_{j}$ and its area $a_{s}$, we discretize it into a
set of associated viewpoints $\bm{V}_{s}$, such that:

$\displaystyle\lvert\bm{V}_{s}\rvert=\Bigl{\lceil}\frac{a_{s}}{a_{f}}\Bigr{\rceil}$
(6)

We define $\bm{V}_{j}$ as the set of all viewpoints belonging to $\bm{S}_{j}$:

$\displaystyle\bm{V}_{j}=\bigcup\bm{V}_{s}\quad\forall s\in\bm{S}_{j}$ (7)

Since each set of surfaces $\bm{S}_{j}$ is associated with a building
$\bm{B}_{j}$, the set of all viewpoints in the scenario $\bm{V}$ is:

$\displaystyle\bm{V}=\bigcup\bm{V}_{j}\quad\forall j\in\bm{B}$ (8)

Similar to [14], we define the _idleness_ $i_{v}$ as the period between two
consecutive visits to a viewpoint in $v\in\bm{V}$ and the set of $i_{v}$,
$\forall v\in\bm{V}$ as $\bm{I}$. Our objective is to minimize the maximum
$i_{v}\in\bm{I}$.

We propose to apply our approach to a swarm of UAV agents, and therefore
subject it to the following attributes, requirements and constraints similar
to our prior work in [15]:

  * •

_Decentralization_ : Agents behave as peers without special roles and make
decisions based on local information, increasing flexibility, reliability, and
robustness.

  * •

_Heterogeneous_ : Problems are modeled as heterogeneous tasks (e.g. “3D
coverage and patrol”, “target tracking”, “monitor point of interest”), to be
allocated to a set of heterogeneous agents (e.g. fixed wing UAVs, multirotor
UAVs, ground robots).

  * •

_Scalability_ : The addition of agents and tasks should not have a significant
impact on performance.

  * •

_Adaptability_ : Dynamic and online reconfiguration due to changes in
available agents and mission tasks.

  * •

_Reliability_ : The system is fault tolerant and robust, automatically
reconfiguring if some drones experience partial or total failure, detected by
loss of communications.

  * •

_Communication_ : Local interactions such as broadcasting of messages through
radios with limited range and bandwidth.

  * •

_Convergence_ : Stable, near-optimal solutions are obtained in a finite and
deterministic time horizon.

##  III 3D Urban Coverage and Patrol

We divide the problem into 4 parts to be solved:

  * •

_Viewpoint Generation_ : Generate viewpoints from 3D surfaces that represent
buildings

  * •

_Task Generation_ : Generate tasks consisting of closed paths through sets of
viewpoints, where each set belongs to a single building

  * •

_Task Allocation_ : Allocate agents to tasks

  * •

_Patrol Strategy_ : Agents allocated to a task partition and patrol along its
associated closed path

With the above, we can create a modular solution that can be easily improved
or modified to optimise for different objective functions by changing the
solution for the relevant part.

In the following, we will describe in detail each of the components in our
proposed solution.

###  III-A Viewpoint Generation

Given a surface $\bm{S}_{j}$ such as a building facade or roof, we discretized
it in the previous section into a set of viewpoints $\bm{V}_{j}$. Each
viewpoint $v\in\bm{V}_{j}$ provides complete coverage of a rectangular polygon
in $p_{v}$ in 3D space on the surface of some surface $s\in\bm{S}_{j}$,
$f_{w}\times f_{h}$ in size, corresponding to agent camera’s FOV at a distance
of $c_{d}$. For facades, the edges of $p_{v}$ are parallel and perpendicular
to the ground plane; for roofs, they are parallel and perpendicular to the
principal axis of the roof surface $\bm{R}_{j}$.

Each viewpoint $v$ is defined by $(x_{v},y_{v},z_{v},b_{v},t_{v})$, where
$x_{v},y_{v},z_{v}$ is the 3D position of the agent that allows it to look at
$p_{v}$, $b_{v}$ is the compass bearing representing the orientation of the
agent in the world frame, and $t_{v}$ is the tilt of the camera with respect
to the body frame of the agent. $x_{v},y_{v},z_{v}$ can be obtained by a
tangential projection of $c_{d}$ from the centroid of each $p_{v}$. $b_{v}$
and $t_{v}$ are set such that the agent will yaw and the camera will tilt
towards the centroid of $p_{v}$ and the camera’s FOV $p_{f}$ aligns with
$p_{v}$.

We described how we generate viewpoints for an urban environment consisting of
buildings modeled as right prisms. An example of the generated viewpoints for
a single building is shown in Fig. 1.

Figure 1: Example of viewpoints generated for a single building.

###  III-B Task Generation

From building $\bm{B}_{j}$, we obtained a set of associated viewpoints
$\bm{V}_{j}$. The goal of task generation is to create a closed path
$\bm{H}_{j}$ for each $\bm{B}_{j}$ that passes through every viewpoint in
$\bm{V}_{j}$ to create a task $j$. When one or more agents moves or patrols
along $\bm{H}_{j}$, visiting every $v\in\bm{V}_{j}$, complete coverage over
the building will be achieved.

Each task $j$ consists of an associated closed path $\bm{H}_{j}$, and its
_capacity_ $c_{j}$ ($j=\\{\bm{H}_{j},c_{j}\\}$), which determines how many
agents will be assigned to $j$. We compute the capacity given the number of
available agents and the length of each $\bm{H}_{j}$ to give an even
distribution, but other schemes can be used to give a better result for a
different objective function, e.g. to prioritize the minimization of idleness
values for a particular set of viewpoints by assigning more agents.

Since $\bm{H}_{j}$ is a closed, ordered list of viewpoints in $\bm{V}_{j}$,
the generation of such a closed path while minimizing its length is
essentially a 3D version of the Traveling Salesman Problem (TSP). Since the
TSP is NP-hard [16], it is not practical to obtain an optimal solution for
larger problem sizes and therefore we use the Christofides algorithm, a
heuristic that guarantees the result to be within 1.5 times of the optimal
solution [17]. An example of the resulting closed path can be seen in Fig 2.

Figure 2: Example of viewpoints with closed path.

A non-trivial point for the implementation of the above to note is that the
distance function between two viewpoints should not simply consider the 3D
Euclidean distance, but also the presence of obstacles, including the building
itself. Viewpoints opposite the same building should consider the distance
based on a path that avoids the building itself, which can be done using 3D
visibility graphs [18].

Although we proposed that each building $\bm{B}_{j}$ is associated with a
single task $j$, this is a design decision rather than a constraint and any
given set or union of sets of viewpoints can be used to generate $\bm{H}_{j}$.
For example, $j$ may have a $\bm{H}_{j}$ that consists of viewpoints from 2
adjacent buildings, or a building and adjacent roads surrounding the building.
It is also possible to generate a single closed path for every viewpoint for a
given scenario, resulting in a single task. The advantage of dividing the
scenario into multiple tasks in the manner that we have described above is
that smaller dynamic changes such as the loss of an agent for a particular
task will cause changes only to agents allocated to the task and will not
result in a disturbance for other tasks.

From the above, we obtained a set of tasks
$\bm{T}=\set{\bm{T}_{1},\bm{T}_{2},\bm{T}_{3},\dots,\bm{T}_{n}}$ corresponding
to the set of buildings
$\bm{B}=\set{\bm{B}_{1},\bm{B}_{2},\bm{B}_{3},\dots,\bm{B}_{n}}$. This step
only needs to be performed once for every $\bm{B}$ and requires more computing
power, but it can be performed offline, or at the ground control station (GCS)
which we assume to have sufficient computing capability.

The step of _task dissemination_ so that all agents have the same copy of
$\bm{T}$ for task allocation is efficiently achieved through our approach
based on distributed blockchains, but is out of the scope of this work.

###  III-C Task Allocation

We allocate the set of agents $\bm{A}$ to the set of tasks $\bm{T}$ and assume
that $\lvert\bm{A}\rvert\geq\lvert\bm{T}\rvert$. Many of our desired
attributes for a solution that aligns to the swarm paradigm are handled in
this step. In particular, we desire a task allocation approach that is
decentralized, and can handle heterogeneous tasks and agents to achieve
scalability, adaptability and fault tolerance.

The Consensus-Based Bundle Approach (CBBA) [19] is an auction-based approach
for decentralized task allocation that we have successfully implemented and
demonstrated in our prior work ([15, 20]). Agents iterate between two phases:
a bundle building phase where each agent uses score functions to greedily
generate bids for an ordered bundle of tasks to execute, and a consensus phase
where agents communicate with neighbours to deconflict tasks. Each agent acts
as a decentralized relay, consolidating and broadcasting bids for tasks to
neighbours, resulting in global consensus even without a fully connected
communications graph. In addition, score functions to generate bids allow us
to consider constraints to heterogeneous tasks such as agent capabilities,
endurance, task-agent type matching, task priorities, etc. To allow multiple
agents to be assigned to a single task, we implement the extension Consensus-
Based Grouping Algorithm (CBGA) [21]. We suggest that the readers refer to the
above papers for further details. We set the bundle size $L_{t}=1$ as we do
not want agents to be moving from task to task (building to building).

Similar to [19], we define $x_{ij}\in\\{0,1\\}$ as a binary decision variable
to indicate if agent $i$ is assigned to task $j$ and therefore:

$\displaystyle\sum_{j=1}^{\lvert\bm{T}\rvert}x_{ij}\leq 1\quad\forall
i\in\bm{A}$ (9) $\displaystyle\sum_{i=1}^{\lvert\bm{A}\rvert}x_{ij}\leq
c_{j}\quad\forall j\in\bm{T}$

Our task allocation implementation runs as an online and anytime algorithm,
giving us the qualities of scalability, adaptability and fault tolerance. For
the score function $s_{ij}$ for agent $i$ with respect to task $j$ , we
consider the squared distance $d_{ij}$ from $i$ $(x_{i},y_{i},z_{i})$ to the
centroid of the building $\bm{B}_{j}$ associated with $j$
$(x_{j},y_{j},z_{j})$:

$\displaystyle d_{ij}=\max\\{(x_{i}-x_{j})^{2}+$
$\displaystyle(y_{i}-y_{j})^{2}+(z_{i}-z_{j})^{2},1\\}$ (10) $\displaystyle
d_{ij}$ $\displaystyle\geq 1$

We use square distance since the score used for bids are relative and not a
representation of distance. Next, we normalize the above to obtain a score
which will be used to select and bid for tasks by $i$:

$\displaystyle s_{ij}$ $\displaystyle=\frac{1}{d_{ij}}$ (11) $\displaystyle
s_{ij}$ $\displaystyle>0$

A useful formulation to improve (11) is to add a non-negative integer $p_{j}$
to represent the priority of task $j$ ($j=\\{\bm{H}_{j},c_{j},p_{j}\\}$) to
override the distance factor and ensure that higher priority tasks associated
with buildings of higher importance are allocated with agents first:

$\displaystyle s_{ij}$ $\displaystyle=p_{j}+\frac{1}{d_{ij}}$ (12)
$\displaystyle s_{ij}$ $\displaystyle>0,\quad p_{j}\in\mathbb{Z}^{\geq 0}$

It is important to normalize the score with respect to other task types in a
heterogeneous task scenario. For example, during the execution of task $j$, an
object of interest is detected in the polygon $p_{v}$ covered by viewpoint
$v$. A tracking task can be generated at a higher priority than $j$, so that
an agent can be reassigned through task allocation to continuously track the
object of interest, while the remaining agents reconfigure to handle the
original set of tasks.

The task allocation process results in the set of agents $\bm{A}$ being
assigned to the set of tasks $\bm{T}$. This assignment is performed in a
decentralized manner using the greedy auction-based method CBBA and CBGA,
deconflicting the results such that each agent is assigned to not more than 1
task and each task is assigned a number of agents not more than its capacity
constraint.

###  III-D Patrol Strategy

Given a task consisting of a closed path through multiple viewpoints with one
or more agents assigned to it, we require a patrol strategy such that all
viewpoints will be periodically traversed and the path is partitioned among
the assigned agents. The set of agents can assigned to the task can change
during the mission due to reinforcements or losses and therefore the algorithm
must be decentralized, adaptable, reliable and scalable. Each agent is
constrained by size, weight and power (SWaP) limitations, so the computational
and communications complexity of the algorithm should not increase as the
number of agents increase.

In addition, agents have limited broadcast communications capabilities, and
may not be able to communicate due line-of-sight (LOS) constraints in an urban
environment. It is important that agents are able to exchange data to enable
coordination, commands from the GCS such as new tasks, and be able to report
relevant information such as the detection of objects of interest back to the
GCS. In many practical cases, when continuous connectivity is not possible,
periodic connectivity can still achieve the desired results. This means that
an agent does not remain in continuous communication with other agents all the
time, but meets and exchanges information with other agents periodically
(periodic connectivity).

In the previous sections, we have reformulated the original problem of 3D
urban coverage and patrol into a closed perimeter surveillance problem by
discretizing the area of interest into viewpoints and generating a 3D closed
path along the viewpoints. In this section, we present our solution for the
above while aiming to satisfy the requirements with a _minimum_ amount of
computation and communications to enable scalability.

The patrol strategy to be developed is with respect to a particular task $j$
and its associated patrol path $\bm{H}_{j}$. The task of agents $\bm{A}_{j}$
assigned to $j$ is to move along $\bm{H}_{j}$, stop at every viewpoint to
perform object detection, and continue onto the next viewpoint. We attempt to
minimize the idleness $i_{v}$, representing the idleness of a viewpoint $v$,
$\forall v\in\bm{H}_{j}$.

We propose a _minimal_ strategy where each agent in $\bm{A}_{j}$ assigned to
$j$ join $\bm{H}_{j}$ via its respective nearest viewpoint, and move in a
random direction along $\bm{H}_{j}$. Since $\bm{H}_{j}$ is a 3D path in an
urban environment, we do not want an increased risk of collisions caused by
agents moving past each other. Our desired behaviour is to have agents moving
in opposite directions along $\bm{H}_{j}$ meet, exchange messages, and
“bounce” off each other.

Given that $\bm{H}_{j}$ is a closed path, for any $\lvert\bm{A}_{j}\rvert\geq
2$, agents moving in different directions or speeds will eventually meet each
other along $\bm{H}_{j}$ and exchange messages, resulting in oscillation, path
partitioning, and periodic connectivity regardless of the length of
$\bm{H}_{j}$ or cardinality of $\bm{A}_{j}$.

Our proposed approach is also scalable and robust against changes in the
number of agents assigned to the task, as agents only interact with
neighbouring agents within communications range, making decisions based on
local information without global consensus.

For example, if agents $i$ and $k$ would have met at some point in time and
agent $k$ was removed, agent $i$ simply continues travelling in the same
direction, extending its patrol path and covering the viewpoints that $k$
would have covered. Suppose another agent was inserted between agents $i$ and
$k$, it would oscillate between both agents, reducing the number of viewpoints
they would each need to cover and reducing the overall idleness.

Each agent $i$ stores and exchanges the following information vector with its
neighbours:

$\displaystyle\bm{M}_{i}$
$\displaystyle=[x_{i},y_{i},z_{i},c_{i},l_{i},d_{i}]$ (13) $\displaystyle
1\leq c_{i}\leq\lvert\bm{H}_{j}\rvert,$ $\displaystyle\quad 1\leq
l_{i}\leq\lvert\bm{H}_{j}\rvert,\quad d_{i}\in\\{-1,1\\}$

where $x_{i},y_{i},z_{i}$ is the 3D coordinates of $i$, $c_{i}$ is the index
of the current viewpoint that the agent is servicing, $l_{i}$ is the index of
the last viewpoint the agent has serviced, and $d_{i}$ represents the counter-
clockwise and clockwise direction of the agent along $\bm{H}_{j}$.

We elaborate on the rules that enable agents to “bounce” off each other when
servicing discrete viewpoints below and in Algorithm 1

Suppose two agents, $i$ and $k$ move into communication range with each other
and exchange messages. If $c_{i}=c_{k}$, the agents are servicing the same
viewpoint. To handle this conflict, we define the conflicting viewpoint
$v=\bm{H}_{j}[c_{i}]=\bm{H}_{j}[c_{k}]$ and compare the distance of $i$ and
$k$ with respect to $v$. The nearer agent continues to service $v$ and the
further agent reverses direction immediately. For the nearer agent, two cases
are possible. If both agents are moving in opposite directions ($d_{i}\neq
d_{k}$) towards $v$, the nearer agent should reverse direction _after_
servicing $v$, as illustrated in Fig 3.

Figure 3: Agents $i$ and $k$, moving in opposite directions, have both
selected the same viewpoint $v=c_{i}=c_{k}$, but since agent $i$ is nearer, it
continues to service $v$ and changes direction after that, while agent $k$
changes direction immediately.

In our next case, if both agents are moving in the same direction
($d_{i}=d_{k})$, the nearer agent should continue in the same direction as
only the further agent needs to change direction as shown in Fig 4. In both
cases, the desired behaviour is for $i$ and $k$ to end up moving in opposite
directions.

Figure 4: Agents $i$ and $k$, moving in the same direction, have both selected
the same viewpoint $v=c_{i}=c_{k}$, but since agent $i$ is nearer, it
continues to service $v$ and move in the same direction while agent $k$
changes direction immediately.

We examine a final case where $i$ and $k$ move into communication range with
each other and exchange messages, but this time,
$c_{i}=l_{k}\;\land\;c_{k}=l_{i}$. This means that the agents are moving
towards each other’s last viewpoint and also implies that the agents are
moving in opposite directions along $\bm{H}_{j}$ and will pass each other. In
this case, both agents reverse direction immediately as shown in Fig 5.

Figure 5: Agents $i$ and $k$, moving in the opposite directions and having
selected each other’s last viewpoints, have just come into communications
range. Both agents reverse direction immediately.

for  _each $\bm{M}_{k}\in M$_ do

if  _$c_{i}=c_{k}$_ then

if  _$\text{distance}(i,c_{i}) <\text{distance}(k,c_{i})$_ then

$d_{i}=d_{i}\times-1$

end if

else if  _$d_{i}\neq d_{k}$_ then

scheduleChangeDirection = true

end if

break

end if

else if  _$c_{i}=l_{k}\;\land\;c_{k}=l_{i}$_ then

$d_{i}=d_{i}\times-1$

break

end if

end for

$v=\bm{H}_{j}[c_{i}]$

if  _$(x_{i},y_{i},z_{i},b_{i},t_{i})\approx(x_{v},y_{v},z_{v},b_{v},t_{v})$_
then

Perform detection

end if

else

Move agent and actuate camera to $v$

end if

if  _detection complete_ then

$l_{i}=c_{i}$

if  _scheduleChangeDirection_ then

$d_{i}=d_{i}\times-1$

scheduleChangeDirection = false

end if

$c_{i}=((c_{i}-1+d_{i}+\lvert\bm{H}_{j}\rvert)\mod\lvert\bm{H}_{j}\rvert)+1$

end if

Algorithm 1 Decentralized Patrol Algorithm from perspective of agent $i$,
periodically receiving and processing a set of messages $\bm{M}$

The scalability of our patrol strategy with regards to computation and
communication is due to the fact that each agent only considers information
from its immediate neighbourhood and does not attempt to achieve global
consensus or consider some shared global state. We note that this advantage
comes at the cost of being unable to obtain an optimal solution where the
closed path is partitioned equally among all agents. An implication is that
the revisit interval for a viewpoint is non-deterministic in most cases, which
may be an advantage when patrolling in a hostile environment.

In addition, our solution is fault-tolerant and enables periodic communication
as long as the task is serviced by $\lvert\bm{A}_{j}\rvert\geq 2$ agents
moving in opposite directions or different speeds.

##  IV Simulation Results and Discussion

We implement and test our proposed algorithm using the Swarm Research
Simulator used in our prior work ([15, 20]). Our scenario consists of 7
buildings ($\lvert\bm{B}\rvert=7$) modeled as right prisms as shown in Fig 6.
Viewpoints and paths are generated for each of the buildings as described in
Section III-A. Viewpoints that intersect with another building are filtered
out. Fig 7 shows the result of viewpoint generation and closed paths for our
scenario.

Given that there are 401 viewpoints, we assign 100 agents to the 7 buildings
such that the ratio of agents to viewpoints is roughly 1:4 for each building
as shown in Table I.

Figure 6: Simulation Scenario: Top Down View of Building Layout and IDs

Each agent moves at 2m/s and stops at each viewpoint for 3 seconds. We assume
that this is required to capture images with greater detail and perform object
detection of the facade with greater precision. For our camera FOV, we set
$c_{d}=10,c_{w}=84,c_{f}=50$, resulting in $f_{w}\approx 18$ and $f_{h}\approx
9$.

Building ID | Viewpoints | Agents | Path Length (m)
---|---|---|---
1 | 80 | 20 | 955
2 | 61 | 15 | 802
3 | 48 | 12 | 662
4 | 52 | 13 | 680
5 | 63 | 16 | 792
6 | 38 | 9 | 533
7 | 59 | 15 | 803
Total | 401 | 100 | 5227
TABLE I: Buildings and Task Details Figure 7: Simulation Scenario: (a) Top
down with viewpoints, (b) Top down with closed paths, (c) Side view with
viewpoints, (d) Side view with closed paths

Our laptop computer system (Intel i7-11850H with 64GB RAM) running our Swarm
Research Simulator was able to run the task allocation and patrol algorithms
at 1Hz, as well as the UAV model at 10Hz for 100 agents in real time. Running
the Christofides algorithm to solve the TSP problem took on the average 3ms
for each building, and each agent took less than 2ms to run the proposed
patrol algorithm at 1Hz intervals.

We repeated the scenario 10 times for 1800 seconds each and obtained the
following results. 100 agents were initialized and performed task allocation
as shown in Fig 8, before moving to their assigned building and executing the
patrol strategy, eventually spreading out among all viewpoints as seen in Fig
9.

Figure 8: Simulation Scenario: 100 agents performed task allocation and moved
towards their assigned buildings. Figure 9: Simulation Scenario: Agents at
their assigned buildings execute the patrol strategy to spread out over time.

We recorded the maximum idleness of all viewpoints at 1Hz for all runs. The
idleness for each viewpoint was set to 0 when the scenario started,
incrementing over time and resetting to 0 when an agent serviced the
viewpoint. This metric allowed us to determine the effectiveness of our
proposed method for minimizing the maximum idleness in the scenario and
ensuring that the algorithm can converge and provide complete coverage. In
addition, we also recorded the time to complete coverage for all runs. This is
a measure of how long it takes for every viewpoint to be visited at least
once. The results are shown in Fig 10

Figure 10: Simulation Scenario: Complete coverage and maximum idleness for 10
experiemental runs show that the patrol strategy is able to converge and
achieve complete coverage despite using minimal computation and
communications.

The simulation results show that our proposed approach to minimize the maximum
idleness is feasible. Our minimal approach for the patrol strategy is able to
constrain the upper bound for the maximum idleness and achieve complete
coverage of all viewpoints. The patrol strategy is also scalable since each
agent only needs to consider messages and deconflict viewpoints for
neighbouring agents.

##  V Conclusion

We proposed a decentralized, modular framework and patrol strategy to solve
the multi-agent 3D coverage and patrol problem. By breaking the 3D coverage
and patrol problem into viewpoint generation, task generation, task
allocation, and patrol strategy, we enable each part of the problem to be
solved and improved in a modular and incremental fashion.

In our experimental results, we have demonstrated that our proposed patrol
strategy can converge to a maximum upper bound for viewpoint idleness and
achieve complete coverage, while requiring minimal computation and
communications. Our solution achieves the desired results in a decentralized,
scalable, and robust manner through the application of simple rules that lead
to the desired emergent behavior, albeit at the cost of some optimality. We
propose that, in general, swarm algorithms characterized by simple rules that
act on local neighborhoods and lead to emergent behavior sacrifice some
optimality in favor of achieving scalability.

In future work, we aim to improve the viewpoint generation step by enabling
UAVs to utilize heterogeneous cameras, distances, and acute angles to observe
surfaces. This will help address challenges such as occlusions or narrow
spaces.

## References

  * [1] M. Półka, S. Ptak, and Ł. Kuziora, “The use of uav’s for search and rescue operations,” _Procedia engineering_ , vol. 192, pp. 748–752, 2017.
  * [2] L. Freda, M. Gianni, F. Pirri, A. Gawel, R. Dubé, R. Siegwart, and C. Cadena, “3d multi-robot patrolling with a two-level coordination strategy,” _Autonomous Robots_ , vol. 43, pp. 1747–1779, 2019.
  * [3] C. Piciarelli and G. L. Foresti, “Drone swarm patrolling with uneven coverage requirements,” _IET Computer Vision_ , vol. 14, no. 7, pp. 452–461, 2020.
  * [4] D. W. Casbeer, D. B. Kingston, R. W. Beard, and T. W. McLain, “Cooperative forest fire surveillance using a team of small unmanned air vehicles,” _International Journal of Systems Science_ , vol. 37, no. 6, pp. 351–360, 2006.
  * [5] P. Sujit, D. Kingston, and R. Beard, “Cooperative forest fire monitoring using multiple uavs,” in _2007 46th IEEE conference on decision and control_. IEEE, 2007, pp. 4875–4880.
  * [6] K. A. Ghamry and Y. Zhang, “Cooperative control of multiple uavs for forest fire monitoring and detection,” in _2016 12th IEEE/ASME International Conference on Mechatronic and Embedded Systems and Applications (MESA)_. IEEE, 2016, pp. 1–6.
  * [7] A. Matlock, R. Holsapple, C. Schumacher, J. Hansen, and A. Girard, “Cooperative defensive surveillance using unmanned aerial vehicles,” in _2009 American Control Conference_. IEEE, 2009, pp. 2612–2617.
  * [8] J. Czyzowicz, L. Gąsieniec, A. Kosowski, and E. Kranakis, “Boundary patrolling by mobile agents with distinct maximal speeds,” in _Algorithms–ESA 2011: 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings 19_. Springer, 2011, pp. 701–712.
  * [9] A. Kawamura and M. Soejima, “Simple strategies versus optimal schedules in multi-agent patrolling,” in _International Conference on Algorithms and Complexity_. Springer, 2015, pp. 261–273.
  * [10] D. Kingston, R. W. Beard, and R. S. Holt, “Decentralized perimeter surveillance using a team of uavs,” _IEEE Transactions on Robotics_ , vol. 24, no. 6, pp. 1394–1404, 2008.
  * [11] J. J. Acevedo, B. C. Arrue, I. Maza, and A. Ollero, “Cooperative perimeter surveillance with a team of mobile robots under communication constraints,” in _2013 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2013, pp. 5067–5072.
  * [12] ——, “Cooperative large area surveillance with a team of aerial mobile robots for long endurance missions,” _Journal of Intelligent & Robotic Systems_, vol. 70, pp. 329–345, 2013.
  * [13] ——, “Distributed approach for coverage and patrolling missions with a team of heterogeneous aerial robots under communication constraints,” _International Journal of Advanced Robotic Systems_ , vol. 10, no. 1, p. 28, 2013.
  * [14] A. Machado, G. Ramalho, J.-D. Zucker, and A. Drogoul, “Multi-agent patrolling: An empirical analysis of alternative architectures,” in _International workshop on multi-agent systems and agent-based simulation_. Springer, 2002, pp. 155–170.
  * [15] W. L. Leong, N. Martinel, S. Huang, C. Micheloni, G. L. Foresti, and R. S. H. Teo, “An intelligent auto-organizing aerial robotic sensor network system for urban surveillance,” _Journal of Intelligent & Robotic Systems_, vol. 102, no. 2, p. 33, 2021.
  * [16] R. M. Karp, _Reducibility among Combinatorial Problems_. Boston, MA: Springer US, 1972, pp. 85–103.
  * [17] N. Christofides, “Worst-case analysis of a new heuristic for the travelling salesman problem,” _Not Applicable_ , 1976.
  * [18] S. Huang and R. S. H. Teo, “Computationally efficient visibility graph-based generation of 3d shortest collision-free path among polyhedral obstacles for unmanned aerial vehicles,” in _2019 international conference on unmanned aircraft systems (ICUAS)_. IEEE, 2019, pp. 1218–1223.
  * [19] H.-L. Choi, L. Brunet, and J. P. How, “Consensus-based decentralized auctions for robust task allocation,” _IEEE transactions on robotics_ , vol. 25, no. 4, pp. 912–926, 2009.
  * [20] W. L. Leong, J. Cao, S. Huang, and R. Teo, “Pheromone-based approach for scalable task allocation,” in _2022 International Conference on Unmanned Aircraft Systems (ICUAS)_. IEEE, 2022, pp. 220–227.
  * [21] S. Hunt, Q. Meng, C. Hinde, and T. Huang, “A consensus-based grouping algorithm for multi-agent cooperative task allocation with complex requirements,” _Cognitive computation_ , vol. 6, pp. 338–350, 2014.


# Advancing Cultural Inclusivity: Optimizing Embedding Spaces for Balanced
Music Recommendations

Armin Moradi  Mila Quebec AI Institute, Université de MontréalMontréalCanada
<EMAIL_ADDRESS>,  Nicola Neophytou  Mila Quebec AI
InstituteMontréalCanada<EMAIL_ADDRESS>and  Golnoosh Farnadi
Mila Quebec AI Institute, Université de Montréal, McGill
UniversityMontréalCanada<EMAIL_ADDRESS>
(20 May 2024)

###### Abstract.

Popularity bias in music recommendation systems - where artists and tracks
with the highest listen counts are recommended more often - can also propagate
biases along demographic and cultural axes. In this work, we identify these
biases in recommendations for artists from underrepresented cultural groups in
prototype-based matrix factorization methods. Unlike traditional matrix
factorization methods, prototype-based approaches are interpretable. This
allows us to directly link the observed bias in recommendations for minority
artists (the effect) to specific properties of the embedding space (the
cause). We mitigate popularity bias in music recommendation through capturing
both users’ and songs’ cultural nuances in the embedding space. To address
these challenges while maintaining recommendation quality, we propose two
novel enhancements to the embedding space: i) we propose an approach to
filter-out the irrelevant prototypes used to represent each user and item to
improve generalizability, and ii) we introduce regularization techniques to
reinforce a more uniform distribution of prototypes within the embedding
space. Our results demonstrate significant improvements in reducing popularity
bias and enhancing demographic and cultural fairness in music recommendations
while achieving competitive -if not better- overall performance.

music recommendation, popularity bias, prototype-based matrix factorization,
demographic fairness, cultural fairness

††conference: Make sure to enter the correct conference title from your rights
confirmation email; October 14–18, 2024; Bari, Italy††ccs: Information systems
Recommender systems††ccs: Information systems Information retrieval††ccs:
Social and professional topics Computing / technology policy

##  1\. Introduction

Online music recommender systems have revolutionized the way in which we
listen to and discover music, offering a personalized journey through a vast
and diverse soundscape. However, these systems face a critical challenge:
ensuring fair and unbiased recommendations across a global audience with a
multitude of cultural preferences (Deldjoo et al., 2024; Bauer and Schedl,
2018; Lee et al., 2023).

This paper investigates the potential for cultural bias in music recommender
systems, due to the influence of certain dominant cultures among artists
within the data (Lesota et al., 2022). This kind of bias is adjacent to
demographic bias, but refers not just to systemic discrimination, but to how
recommended content can become culturally homogeneous, particularly with the
over-influence of Western styles. Such biases can limit users’ exposure to a
wider range of music, hindering their discovery of diverse cultural
expressions (Bello and Garcia, 2021).

While existing research has explored various strategies to mitigate popularity
and demographic biases in music recommendation (Wei et al., 2021; Kamehkhosh
and Jannach, 2017), such as data pre-processing (Boratto et al., 2021) and
post-processing adjustments (Abdollahpouri et al., 2019; Mansoury et al.,
2021), we examine an in-processing fairness approach (Wei et al., 2021; Zheng
et al., 2021; Rhee et al., 2022) to analyze the model’s use of cultural
nuances within the recommendation model itself. We leverage previous work on
prototype-based recommender systems (ProtoMF) (Melchiorre et al., 2022), which
transforms latent representations of users and items into new embedding
spaces, defined by prototypes which act as anchor points. Our approach
explicitly focuses on ensuring the model can learn from minority cultures,
despite being less prevalent in the data. Further, since we deal directly with
the embedding space, our approach has the additional benefit of transparency
when ensuring equitable treatment of user subgroups. This work therefore also
emphasizes the importance of explainable recommender systems, allowing users
to understand the reasoning behind output recommendations and fostering trust
(Afchar et al., 2022). We make the following key contributions:

  1. (1)

We analyze the embedding space of the Prototype-based Matrix Factorization
(ProtoMF) method to uncover the model’s disparate treatment of cultures among
items and subsequent popularity bias.

  2. (2)

We then propose an extension to ProtoMF, Prototype-$k$-Filtering, that uses
only the $k$ closest prototypes to users and items in the embedding space to
generate their representations.

  3. (3)

We propose a second extension to ProtoMF, Prototype-Distributing Regularizer,
which regularizes the loss function to evenly distribute prototypes throughout
the embedding space.

With these contributions, we investigate the cultural information captured by
representations of prototype-based recommendations, and how this can be
augmented to enhance rather than deteriorate cultural fairness. Our extensive
experimental results on two real-world datasets indicate that cultural bias in
prototype-based recommender systems can be mitigated without any additional
cost to utility. In this work, therefore, we aim to contribute to the
development of more inclusive and equitable digital environments in the
recommendation setting - ones which empower the work of creators from minority
backgrounds and deliver curated and culture-aware diversity to consumers. The
dataset and code will be made publicly available upon publication of this
work.

##  2\. Related Work

Mitigating popularity and demographic biases have both emerged as critical
areas of research in recommender systems. In-processing fairness methods aim
to integrate fairness considerations directly into the learning process of the
recommendation system. These methods offer advantages in terms of transparency
and control over the model’s behavior (Burke et al., 2018; Patro et al.,
2020). One promising approach is fair matrix factorization, which incorporates
fairness constraints into the objective function during model training (Rhee
et al., 2022; Wei et al., 2021; Zheng et al., 2021; Rhee et al., 2022).
However, such approaches do not consider adapting properties of the embedding
space indirectly. Our approach, which enhances prototype-based Matrix
Factorization, introduces constraints to the learning process that are
independent of the original loss function. This allows us to mitigate bias
without sacrificing recommendation quality.

Incorporating prototypes into the learning process has emerged as a recent
concept, primarily to address cold-start issues; Sankar et al. (2021) leverage
prototypes for recommending long-tail items with sparse interactions as a few-
shot learning problem with collaborative filtering (ProtoCF). A similar but
alternative approach is identifying representatives for the cold-start
problem. Shi et al. (2017) select local representative items from user groups
using an interview-based model, while Aleksandrova et al. (2017) propose a
method to automatically interpret representative users. Anchor-based
collaborative filtering (ACF), from Barkan et al. (2021), shares this concept,
requiring items to select single representative anchors. These approaches
capture user/item characteristics with representative elements for
recommendations with limited data.

While these prototype-based methods prove to be competitive due to capturing
“genre”-adjacent information, none have yet been considered for addressing
cultural fairness issues. As such, we address these gaps in the existing work;
we propose augmenting a prototype-based matrix factorization approach, ProtoMF
(Melchiorre et al., 2022), and adapting properties of prototypes in the
embedding space to promote cultural diversity among items and reduce
popularity bias. Our approach is distinguished by its adaptations to the
embedding space, which do not directly affect the loss function and therefore
maintain competitive performance. While ProtoMF, without offering solutions,
revealed gender bias among users, we extend this work by demonstrating
cultural bias among items and propose solutions to mitigate both cultural and
popularity biases.

##  3\. Preliminaries

###  3.1. Prototype-based Matrix Factorization

Music recommender systems typically rely on matrix factorization techniques to
model user-item interactions. In this case, a user-item matrix with $N$ users
and $M$ items ($R\in\mathbb{R}^{N\times M}$) is decomposed into user factor
matrix ($U\in\mathbb{R}^{N\times d}$) and an item factor matrix
($T\in\mathbb{R}^{d\times M}$) where $d$ is the embedding space dimension
(Dziugaite and Roy, 2015). These factor matrices represent latent factors that
capture user preferences and item characteristics separately. The affinity
score can be calculated between user and item representations in order to
capture some notion of how well-matched users and items are. We define the
affinity score for user $\mathbf{u}=U^{T}_{i,:}\in\mathbb{R}^{d\times 1}$ and
item $\mathbf{t}=T_{:,j}\in\mathbb{R}^{d\times 1}$ as:

(1) $\text{Aff}(u,t)=\mathbf{u}^{T}\mathbf{t}.$

Prototype-based Matrix Factorization (ProtoMF) extends traditional matrix
factorization by incorporating $L$ prototypes
($P_{u}\in\mathbb{R}^{L_{u}\times d}$ for users, and
$P_{t}\in\mathbb{R}^{L_{t}\times d}$ for items) in potentially both embedding
spaces of users and items. These prototypes act as anchor points in the latent
factor space. Using these points, new embeddings ($U^{*}\in\mathbb{R}^{N\times
L_{u}}$ and $T^{*}\in\mathbb{R}^{M\times L_{t}}$) are calculated for each user
and item using the cosine similarity (sim) with respect to each prototype in
$P_{u}$ and $P_{t}$.

The affinity between users and items can therefore be expressed using the new
embedding coordinates $\mathbf{u}^{*}$ and $\mathbf{t}^{*}$:

(2)
$\text{Aff}(u,t)={\mathbf{u}^{*}}^{T}\cdot\hat{t}+{\mathbf{t}^{*}}^{T}\cdot\hat{u}$

where $\hat{u}$ and $\hat{t}$ are linear transformations of $u^{*}$ and
$t^{*}$ to create a common space where affinity scores can be calculated. The
affinity score is then used as the final recommendation score of a user-item
pair. The use of prototypes therefore provides extra degrees of freedom for
representing users and items such to better calibrate affinity to the training
examples.

##  4\. Methodology

(a) Prototypes (triangles) cluster more around popular items (US) than less
popular items (NL).

(b) Prototypes (triangles) are more evenly distributed, and the less popular
items (NL) become grouped.

Figure 1. t-SNE visualizations of the item embedding space for (a) the
baseline ProtoMF model and (b) the model after applying both Prototype
k-Filtering and the Prototype-Distributing Regularizer. Larger dots represent
more popular items. The triangles indicate the positions of prototypes. NL and
US represent an underrepresented and overrepresented country, respectively.

We introduce our novel contributions for enhancing the ProtoMF approach to
mitigate both cultural and popularity bias.

###  4.1. Prototype K-filtering

Our first contribution, Prototype K-filtering, filters-out prototypes that are
further from the item or user in their relative embedding spaces. As such, the
model only uses the $k$ nearest prototypes for generating user and item
representations during training, which is a hyperparameter that we
heuristically train using 2 insights. This allows the prototypes to grasp more
local information that relates to the closer neighboring examples in the
embedding space, and forces the model to learn a less “global” set of
prototypes. Formally, we can write the new embeddings as

(3)
$u^{**}=\text{TopK}(u^{*},k_{u})\in\mathbb{\mathbb{R}}^{k_{u}},k_{u}<L_{u}$
(4)
$t^{**}=\text{TopK}(t^{*},k_{t})\in\mathbb{\mathbb{R}}^{k_{t}},k_{t}<L_{t}$

where the TopK function outputs a $k$-dimensional feature vector for each user
and item, which is representative of its $sim$ to the $k$ nearest prototypes.

Figure 2. Average distance of items to k nearest prototypes, grouped by
popularity, for the baseline ProtoMF method. The gap in average distances
between items of different popularity levels narrows with smaller k values.

###  4.2. Prototype-Distributing Regularizer

For our second approach, we add a regularization term to the loss function to
spread the angular position of prototypes across the embedding space.
Formally, we add the following to the original loss function:

(5)
$L=L_{original}+\lambda_{u}\cdot||\hat{P}_{L_{u}}\hat{P}_{L_{u}}^{T}||_{2}^{2}+\lambda_{t}\cdot||\hat{P}_{L_{t}}\hat{P}_{L_{t}}^{T}||_{2}^{2}$

Where $\hat{P}_{L_{u}}\in\mathbb{R}^{L_{u}\times d}$ and
$\hat{P}{L_{t}}\in\mathbb{R}^{L_{t}\times d}$ are matrices representing the
normalized prototype vectors for both user and item spaces, and $L_{original}$
is the original loss function. In these matrices, each of the prototype
vectors has been normalized to have a L2-norm of 1. By enforcing
orthonormality of the prototype vectors, we encourage the prototypes to serve
as the basis vectors of the embedding space. This approach prevents prototypes
from gravitating towards the same regions of the embedding space, thereby
redistributing them to cover more marginal areas. This leads to more
information gain, as it ensures a more effective and diverse utilization of
the embedding space. This concept is akin to the discrete latent space
representation in van den Oord et al. (2018)’s work, where the effective use
of embedding vectors is crucial for capturing the latent structure of the
data.

##  5\. Empirical Evaluation

In this section, we first outline our experimental set up, and then we answer
two research questions to explore the effectiveness of our prototype-based
contributions in mitigating cultural bias compare to existing approaches.

#### Datasets

We conduct our experiments on two datasets. Firstly, we use a subset of the
_LastFM-2b dataset_ (Melchiorre et al., 2021) which consists of around 15,258
users, and 4,082,530 million songs with 30,357,786 number of interactions that
we integrate into the learning process to avoid losing insights from the
minority groups. In order to obtain the artists’ country, we augment the
dataset using musicbrainz.com data and matching the artists by name. Secondly,
we also use the _MovieLens-1M_ (Harper and Konstan, 2015) dataset, which
contains 1,000,209 ratings of 3,900 movies from 6,040 users and use the movie
genre as the attribute to group the under and over-represented items.

#### Baselines

To compare our model with existing work, we select four baselines: standard
Matrix Factorization (Koren et al., 2009), anchor-based collaborative
filtering (Barkan et al., 2021), and the standard prototype-based matrix
factorization (ProtoMF) (Melchiorre et al., 2022). We include an additional
benchmark to compare with existing popularity bias mitigation, ZeroSum, by
incorporating Rhee et al. (2022)’s method into ProtoMF to fairly compare its
effectiveness with our own approach. We perform hyperparameter tuning to
ensure optimal performance of each baseline and also our own contribution by
tuning $K$ and $\lambda$.

For tuning our own models, we first identify the best-performing standard
ProtoMF model through hyperparameter tuning. Subsequently, to maintain
computational feasibility, we tune our models only for the new parameters
introduced by our contributions, $k$ and $\lambda$, while keeping the other
parameters fixed at their optimal values from the standard ProtoMF model.

#### Fairness Metrics

We evaluate fairness of the output recommendations using the following
metrics:

  * •

Average Item Ranking: Ranking is crucial for fairness as users interact
differently based on item positions (Ursu, 2018). We report the average
ranking of items in underrepresented ($\mu(r_{under})$) and majority groups
($\mu(r_{over})$) over model outputs of 100 items.

    * –

In Last-FM, we define the majority group as the set of artists from the top
three most popular countries by listen counts {US, UK}. The underrepresented
groups are {BR, NL, PL}.

    * –

For ML-1M, we categorize subgroups based on genres. The overrepresented genres
are {Drama, Comedy}, while the underrepresented genres are {War, Sci-fi,
Western}.

  * •

Long-Tail Item Visibility: We also report the proportion of long-tail items in
the top 10 recommendations for all users, including repeated appearances. We
define long-tail items as the top 10% of items with the least interactions,
using the logarithmic interaction count discussed by Salganik et al. (2024).

Table 1. Performance and fairness results of baseline methods compared to
prototype-$k$-filtering, Prototype-distributing regularization, and a
combination of the two. Arrows indicate whether higher or lower values are
more desirable.

Model |  HitRatio@10 $\uparrow$ |  NDCG@10 $\uparrow$ |  $\mathbf{\mu(r_{under})}$ $\downarrow$ | $\mathbf{\mu(r_{over})}$ |  LT Ranking $\downarrow$
---|---|---|---|---|---
LFM | ML | LFM | ML | LFM | ML | LFM | ML | LFM | ML
MF (Koren et al., 2009) | 0.159 | 0.452 | 0.083 | 0.248 | 49.299 | 56.041 | 49.755 | 49.226 | 25.991 | 35.842
ACF (Barkan et al., 2021) | 0.569 | 0.618 | 0.317 | 0.345 | 53.970 | 57.198 | 43.458 | 49.652 | 20.009 | 18.142
ProtoMF (Melchiorre et al., 2022) | 0.581 | 0.656 | 0.337 | 0.381 | 51.106 | 54.061 | 44.300 | 49.510 | 29.008 | 36.365
ZeroSum (Rhee et al., 2022) | 0.564 | 0.615 | 0.327 | 0.347 | 52.233 | 53.513 | 44.733 | 49.339 | 21.543 | 23.669
Our Models | Prototype $k$-Filtering ($k_{t}$) | 0.594 | 0.651 | 0.344 | 0.379 | 49.849 | 53.984 | 43.852 | 49.780 | 21.995 | 16.375
Prototype-Distributing Regularizer ($\lambda_{t}$) | 0.598 | 0.660 | 0.348 | 0.386 | 51.111 | 53.486 | 44.085 | 48.774 | 18.995 | 18.369
$k$-Filtering and Distributing ($k_{t}$, $\lambda_{t}$) | 0.600 | 0.657 | 0.352 | 0.383 | 49.552 | 51.600 | 44.296 | 49.678 | 18.013 | 18.135

#### RQ1: Do prototypes in the embedding space of ProtoMF possess inherent
properties that can lead to cultural bias?

To answer this question, we analyze the embedding space of the baseline
ProtoMF method. The baseline embedding space in Figure 2 indicates that
popular items tend to be closer to prototypes. Proximity to prototypes
provides an advantage to items, since it increases the cosine similarity
values in its representation (Equation 4), and therefore the chance of a
higher affinity score with users (Equation 2). This observation provides an
initial justification for using a subset of prototypes for recommendations to
enhance fairness.

Not only do prototypes in the baseline model optimize for proximity to popular
items, but they also concentrate together in these regions (see Figure 1(a)).
This concentration exacerbates the issue of providing advantages to more
popular items, leading to further disparities in rankings between popular and
less popular items. This could leave many regions in the embedding space
without representative prototypes, leading to systemic unfairness for less
popular items, and therefore cultures.

#### RQ2: How successful are our proposed approaches, which modify the
learning process of the embedding space to enhance the discoverability of
minority cultures and mitigate popularity bias, compared to existing methods?

To answer this question, we analyze the impact of our contributions on the
embedding space.

Figure 1 illustrates the difference in prototype placement in the embedding
space between the baseline ProtoMF model (1(a)) and our model with the
regularizer (1(b)). The regularization increases the space between prototypes,
reducing the dominance of popular items in the embedding space. Moreover, the
effect of our model on popularity bias can be seen in the Figure 3. Our
contributions forces less popular items to have a lower ranking (higher on the
recommendation list), and popular items to appear in higher ranks (lower on
the recommendation list). Our model therefore provides greater visibility to
less popular items than the baseline model (Ursu, 2018).

Figure 3. Average rank of overrepresented items (from US, GB, CA) and
underrepresented items (from BR, NL, PL), comparing ProtoMF, ZeroSum and our
model using $k$ and $\lambda$.

The quantitative results of the contributions, comparing variations of our
best-performing models against existing baselines, can be found in Table 1. We
report recommendation performance metrics, including HitRatio@10 and NDCG@10,
as well as fairness metrics. Our findings reveal that our models outperform
standard MF in terms of performance and are on par with ProtoMF and ACF on
both datasets. Additionally, our models successfully reduce the difference
between the average rank for under- and over-represented groups, demonstrating
improved fairness. Furthermore, they are more inclusive towards less popular
items, as evidenced by the decrease in the average long-tail rank. Notably,
while both k-filtering and the regularizer independently improve fairness,
their combined effect amplifies these improvements, leading to the fairest
outcomes.

##  6\. Conclusion & Future Directions

In this work, we introduced two novel enhancements to the ProtoMF model’s
embedding space, enabling us to effectively mitigate cultural and popularity
bias in music recommendation. Crucially, these enhancements operate
independently of the model’s original loss function. This decoupling of
fairness and accuracy optimization is a key advantage of our approach, as it
allows us to directly target and mitigate biases without the inherent trade-
offs that often plague methods that modify the loss function. Our results
demonstrate that this approach is not only effective in significantly
improving fairness metrics, but also maintains, and in some cases even
enhances, the overall recommendation quality across both datasets.

Further extensions to this work include expanding the evaluation across
diverse music datasets with broader cultural and genre representation to
enhance our understanding of the model’s generalizability, especially given
the limited data available on non-Western countries. Future work will focus on
cultural matchings of users and items, considering the behaviors of various
cultures as highlighted by Lesota et al. (2022), and emphasize user-side
fairness. Additionally, we plan to investigate prototype collisions in the
embedding space using explainability techniques to understand and theorize
these collisions beyond popularity bias measures, which will also apply to the
new embedding space after training our updated models. Lastly, we also
acknowledge the ethical considerations surrounding the use of cultural
attributes in recommender systems, as discussed in Appendix A.

## Acknowledgments

Funding support for project activities has been partially provided by Canada
CIFAR AI Chair, and Facebook award. We also express our gratitude to Compute
Canada for their support in providing facilities for our evaluations.

## References

  * (1)
  * Abdollahpouri et al. (2019) Himan Abdollahpouri, Robin Burke, and Bamshad Mobasher. 2019.  Managing popularity bias in recommender systems with personalized re-ranking.  _arXiv preprint arXiv:1901.07555_ (2019).
  * Afchar et al. (2022) Darius Afchar, Alessandro Melchiorre, Markus Schedl, Romain Hennequin, Elena Epure, and Manuel Moussallam. 2022.  Explainability in music recommender systems.  _AI Magazine_ 43, 2 (2022), 190–208.
  * Aleksandrova et al. (2017) Marharyta Aleksandrova, Armelle Brun, Anne Boyer, and Oleg Chertov. 2017.  Identifying representative users in matrix factorization-based recommender systems: application to solving the content-less new item cold-start problem.  _Journal of Intelligent Information Systems_ 48, 2 (2017), 365–397.
  * Barkan et al. (2021) Oren Barkan, Roy Hirsch, Ori Katz, Avi Caciularu, and Noam Koenigstein. 2021.  Anchor-based collaborative filtering. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. 2877–2881.
  * Bauer and Schedl (2018) Christine Bauer and Markus Schedl. 2018.  On the importance of considering country-specific aspects on the online-market: an example of music recommendation considering country-specific mainstream.  (2018).
  * Bello and Garcia (2021) Pablo Bello and David Garcia. 2021.  Cultural Divergence in popular music: the increasing diversity of music consumption on Spotify across countries.  _Humanities and Social Sciences Communications_ 8, 1 (2021), 1–8.
  * Boratto et al. (2021) Ludovico Boratto, Gianni Fenu, and Mirko Marras. 2021.  Interplay between upsampling and regularization for provider fairness in recommender systems.  _User Modeling and User-Adapted Interaction_ 31, 3 (2021), 421–455.
  * Burke et al. (2018) Robin Burke, Nasim Sonboli, and Aldo Ordonez-Gauger. 2018.  Balanced neighborhoods for multi-sided fairness in recommendation. In _Conference on fairness, accountability and transparency_. PMLR, 202–214.
  * Deldjoo et al. (2024) Yashar Deldjoo, Dietmar Jannach, Alejandro Bellogin, Alessandro Difonzo, and Dario Zanzonelli. 2024.  Fairness in recommender systems: research landscape and future directions.  _User Modeling and User-Adapted Interaction_ 34, 1 (2024), 59–108.
  * Dziugaite and Roy (2015) Gintare Karolina Dziugaite and Daniel M Roy. 2015.  Neural network matrix factorization.  _arXiv preprint arXiv:1511.06443_ (2015).
  * Harper and Konstan (2015) F Maxwell Harper and Joseph A Konstan. 2015.  The movielens datasets: History and context.  _Acm transactions on interactive intelligent systems (tiis)_ 5, 4 (2015), 1–19.
  * Kamehkhosh and Jannach (2017) Iman Kamehkhosh and Dietmar Jannach. 2017.  User perception of next-track music recommendations. In _Proceedings of the 25th conference on user modeling, adaptation and personalization_. 113–121.
  * Koren et al. (2009) Yehuda Koren, Robert Bell, and Chris Volinsky. 2009.  Matrix factorization techniques for recommender systems.  _Computer_ 42, 8 (2009), 30–37.
  * Lee et al. (2023) Harin Lee, Romain Hennequin, and Manuel Moussallam. 2023.  Understanding Individual and Collective Diversity of Cultural Consumption through Large-Scale Music Listening Events.  _Proceedings http://ceur-ws. org ISSN_ 1613 (2023), 0073.
  * Lesota et al. (2022) Oleg Lesota, Emilia Parada-Cabaleiro, Stefan Brandl, Elisabeth Lex, Navid Rekabsaz, and Markus Schedl. 2022.  Traces of Globalization in Online Music Consumption Patterns and Results of Recommendation Algorithms.. In _ISMIR_. 291–297.
  * Mansoury et al. (2021) Masoud Mansoury, Himan Abdollahpouri, Mykola Pechenizkiy, Bamshad Mobasher, and Robin Burke. 2021.  A graph-based approach for mitigating multi-sided exposure bias in recommender systems.  _ACM Transactions on Information Systems (TOIS)_ 40, 2 (2021), 1–31.
  * Melchiorre et al. (2022) Alessandro B Melchiorre, Navid Rekabsaz, Christian Ganhör, and Markus Schedl. 2022.  Protomf: Prototype-based matrix factorization for effective and explainable recommendations. In _Proceedings of the 16th ACM Conference on Recommender Systems_. 246–256.
  * Melchiorre et al. (2021) Alessandro B. Melchiorre, Navid Rekabsaz, Emilia Parada-Cabaleiro, Stefan Brandl, Oleg Lesota, and Markus Schedl. 2021.  Investigating gender fairness of recommendation algorithms in the music domain.  _Information Processing & Management_ 58, 5 (2021), 102666.  https://doi.org/10.1016/j.ipm.2021.102666
  * Patro et al. (2020) Gourab K Patro, Arpita Biswas, Niloy Ganguly, Krishna P Gummadi, and Abhijnan Chakraborty. 2020.  Fairrec: Two-sided fairness for personalized recommendations in two-sided platforms. In _Proceedings of the web conference 2020_. 1194–1204.
  * Rhee et al. (2022) Wondo Rhee, Sung Min Cho, and Bongwon Suh. 2022.  Countering popularity bias by regularizing score differences. In _Proceedings of the 16th ACM Conference on Recommender Systems_. 145–155.
  * Salganik et al. (2024) Rebecca Salganik, Fernando Diaz, and Golnoosh Farnadi. 2024.  Fairness Through Domain Awareness: Mitigating Popularity Bias for Music Discovery. In _European Conference on Information Retrieval_. Springer, 351–368.
  * Sankar et al. (2021) Aravind Sankar, Junting Wang, Adit Krishnan, and Hari Sundaram. 2021.  Protocf: Prototypical collaborative filtering for few-shot recommendation. In _Proceedings of the 15th ACM Conference on Recommender Systems_. 166–175.
  * Shi et al. (2017) Lei Shi, Wayne Xin Zhao, and Yi-Dong Shen. 2017.  Local representative-based matrix factorization for cold-start recommendation.  _ACM Transactions on Information Systems (TOIS)_ 36, 2 (2017), 1–28.
  * Ursu (2018) Raluca M Ursu. 2018.  The power of rankings: Quantifying the effect of rankings on online consumer search and purchase decisions.  _Marketing Science_ 37, 4 (2018), 530–552.
  * van den Oord et al. (2018) Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. 2018.  Neural Discrete Representation Learning.  arXiv:1711.00937 [cs.LG]
  * Wei et al. (2021) Tianxin Wei, Fuli Feng, Jiawei Chen, Ziwei Wu, Jinfeng Yi, and Xiangnan He. 2021.  Model-agnostic counterfactual reasoning for eliminating popularity bias in recommender system. In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_. 1791–1800.
  * Zheng et al. (2021) Yu Zheng, Chen Gao, Xiang Li, Xiangnan He, Yong Li, and Depeng Jin. 2021.  Disentangling user interest and conformity for recommendation with causal embedding. In _Proceedings of the Web Conference 2021_. 2980–2991.

##  Appendix A Ethical Considerations and Broader Impacts

While this research did not involve direct interaction with human subjects or
the collection of new data, it utilizes existing datasets (LastFM-2b and
MovieLens-1M) that represent the behaviors and preferences of real users. We
acknowledge that these datasets, while anonymized, may contain inherent biases
or reflect societal inequalities. We strive to use these datasets responsibly
and critically analyze any potential biases in our findings.

Our work aims to mitigate cultural bias in music recommender systems, which
has important implications for fairness and equity in the digital music
landscape. By promoting greater visibility for artists from underrepresented
cultural groups, our methods could potentially:

  * •

Empower creators from marginalized communities

  * •

Enhance cultural diversity in music consumption

  * •

Counteract existing biases in the music industry

However, we also acknowledge potential ethical concerns:

  * •

Oversimplifying culture: In our analysis, we used country of origin as a proxy
for cultural background. While this provides a useful starting point, it’s
important to acknowledge that culture is a complex and multifaceted concept
that cannot be fully captured by a single attribute like nationality. This
simplification could potentially lead to inaccurate assumptions or
generalizations about the cultural preferences.

  * •

Unintended consequences: Our methods could inadvertently introduce new biases
or reinforce existing ones if not carefully evaluated and monitored.

  * •

Overemphasis on culture: Focusing solely on cultural fairness could
potentially neglect other important factors like individual preferences or
musical quality.

  * •

Limited generalizability: Our findings may not generalize to other recommender
systems or cultural contexts.

To address these concerns, we emphasize the importance of ongoing research and
continuous evaluation of fairness metrics in deployed recommender systems. We
also advocate for transparency in the design and implementation of these
systems, allowing users to understand and control how recommendations are
generated.

##  Appendix B Complimentary Experiment Results

In Appendix B (Table 2), we present a comprehensive set of results across
various combinations of hyperparameters $k$ (prototype filtering) and
$\lambda$ (regularization strength) for the ProtoMF model on the LastFM
dataset. The table includes performance metrics (HitRatio@10, NDCG@10). These
detailed results allow for a deeper exploration of the impact of different
hyperparameter values on recommendation quality.

Table 2. Performance and Fairness of ProtoMF on the LastFM-2b Dataset Across Different Combinations of $k$ (Prototype Filtering) and $\lambda$ (Regularization Strength), where $k=-1$ indicates using all prototypes. $K_{u}$ | $\lambda_{u}$ | $K_{t}$ | $\lambda_{t}$ | HitRatio@10 | NDCG@10
---|---|---|---|---|---
-1 | 0.0 | 60 | 0.0 | 0.593 | 0.348
60 | 0.003 | 60 | 0.1 | 0.577 | 0.338
60 | 0.0 | 25 | 0.003 | 0.569 | 0.332
-1 | 0.0 | 25 | 0.003 | 0.569 | 0.329
-1 | 0.0 | 60 | 0.9 | 0.562 | 0.326
-1 | 0.0 | 40 | 0.0 | 0.559 | 0.321
12 | 1.0 | 12 | 0.1 | 0.552 | 0.323
-1 | 0.0 | 60 | 0.25 | 0.552 | 0.320
-1 | 0.0 | 12 | 0.0 | 0.543 | 0.310
-1 | 0.0 | 60 | 0.387 | 0.534 | 0.307
-1 | 0.1 | 25 | 0.0 | 0.519 | 0.301
60 | 0.003 | 60 | 0.003 | 0.515 | 0.301
25 | 0.0 | 25 | 10.0 | 0.513 | 0.294
-1 | 10.0 | 40 | 40 | 0.505 | 0.291
-1 | 0.0 | 12 | 0.0 | 0.488 | 0.273