#  AMSwarm: An Alternating Minimization Approach for Safe Motion Planning of
Quadrotor Swarms in Cluttered Environments

Vivek K. Adajania, Siqi Zhou, Arun Kumar Singh, and Angela P. Schoellig Vivek
K. Adajania, Siqi Zhou, and Angela P. Schoellig are with the Learning Systems
and Robotics Lab (http://www.learnsyslab.org) at the University of Toronto
Institute for Aerospace Studies, Canada, and the Technical University of
Munich, Germany. They are also with the Vector Institute for Artificial
Intelligence. Arun Kumar Singh is with the University of Tartu, Estonia. This
research was in part supported by the European Social Fund via the ICT program
measure and grant PSG753 from the Estonian Research Council. Emails:
{vivek.adajania<EMAIL_ADDRESS><EMAIL_ADDRESS>and
<EMAIL_ADDRESS>
###### Abstract

This paper presents a scalable online algorithm to generate safe and
kinematically feasible trajectories for quadrotor swarms. Existing approaches
rely on linearizing Euclidean distance-based collision constraints and on
axis-wise decoupling of kinematic constraints to reduce the trajectory
optimization problem for each quadrotor to a quadratic program (QP). This
conservative approximation often fails to find a solution in cluttered
environments. We present a novel alternative that handles collision
constraints without linearization and kinematic constraints in their quadratic
form while still retaining the QP form. We achieve this by reformulating the
constraints in a polar form and applying an Alternating Minimization algorithm
to the resulting problem. Through extensive simulation results, we demonstrate
that, as compared to Sequential Convex Programming (SCP) baselines, our
approach achieves on average a 72% improvement in success rate, a 36%
reduction in mission time, and a 42 times faster per-agent computation time.
We also show that collision constraints derived from discrete-time barrier
functions (BF) can be incorporated, leading to different safety behaviours
without significant computational overhead. Moreover, our optimizer
outperforms the state-of-the-art optimal control solver ACADO in handling BF
constraints with a 31 times faster per-agent computation time and a 44%
reduction in mission time on average. We experimentally validated our approach
on a Crazyflie quadrotor swarm of up to 12 quadrotors. The code with
supplementary material and video are released for reference.

##  I Introduction

Quadrotor swarms have a great potential in applications such as search and
rescue [1], mapping and environmental monitoring [2], and payload transport
[3]. As compared to single quadrotors, quadrotors swarms offer increased
flexibility, efficiency, and robustness [4].

In this paper, we consider the problem of motion planning for quadrotor swarms
in cluttered environments and treat it as a trajectory optimization problem to
be solved. In this context, the most straightforward approach is to formulate
one joint optimization problem that computes trajectories for all quadrotors.
Existing works have used both global mixed-integer linear programming [5] and
local optimization-based Sequential Convex Programming (SCP) [6] approaches
for solving the joint trajectory optimization problem. The solution space of
these approaches is large but they quickly become intractable as the number of
quadrotors grows.

Distributed approaches provide a more scalable alternative, where each
quadrotor solves an independent trajectory optimization problem taking into
account the predicted trajectories of its neighbours [7, 8, 9, 10]. The
predicted trajectories are often assumed to be shared by the neighbouring
quadrotors. These approaches have successfully demonstrated swarm motion
planning for tens of quadrotors. However, we will show that their performance
in terms of scalability, mission time, and computation time remains poor in
highly cluttered environments. While there exist works that further
incorporate a high-level discrete planner to improve the swarm performance in
cluttered environments [11, 12, 13], in this work, we focus on the low-level
trajectory optimization problem and propose an algorithm that addresses the
limitations of existing distributed trajectory optimization baselines.

Figure 1: Experimental demonstration of our distributed alternating
minimization based approach for quadrotor swarm motion planning in challenging
scenes. Link to video: http://tiny.cc/AMSwarmVideo. Link to code and
supplementary material: https://github.com/utiasDSL/AMSwarm.

Some of the limitations of [7, 8, 9] and other related works such as [6] and
[14] can be attributed to the underlying trajectory optimizer that relies on
axis-wise decoupling of kinematic constraints and linearization of collision
avoidance constraints. These affine approximations are made to obtain a
quadratic program (QP) that can be solved efficiently. However, the
computational benefits come at the expense of a reduced solution space.
Moreover, while replanning in a receding horizon setting, the collision
constraints are not active until the planned trajectories intersect with the
neighbouring quadrotors or obstacles [15]. This reduces the responsiveness of
the collision avoidance behaviour. One way to mitigate this issue is to use a
longer prediction horizon; however, this increases the computation time.

Our proposed optimizer addresses both limitations discussed above: the
conservativeness of existing approaches due to approximations and the late
responsiveness to neighbouring quadrotors or obstacles. We show that by
reformulating the quadratic kinematic constraints and collision constraints
into polar form and applying an Alternating Minimization (AM) algorithm to the
resulting optimization problem, we can retain a QP without requiring any
linearization. As a result, we obtain more aggressive motions with improved
metrics for swarm planning, such as mission time and success rate. Our
formulation naturally extends to the case when collision avoidance is modelled
by a discrete-time barrier function (BF) [15]. This dramatically improves
safety metrics such as clearance to neighbouring quadrotors and obstacles
while incurring no significant computational cost. To the best of our
knowledge, only a few works, such as [16], [17], have incorporated BF
constraints over the entire planning horizon; most works such as [18] and [19]
consider a one-step reactive planning approach. Among the multi-step
approaches, ours is the first to formulate trajectory planning with BF
constraints as a QP (see Section II-C).

We compare our approach with the SCP baselines from [7, 8, 9] and show on
average a $72\%$ improvement in success rate, a $36\%$ reduction in mission
time, and a $42$ times faster per-agent computation time. Additionally, we
show that the proposed approach with BF constraints allows us to introduce
different safety behaviours. We further show that our optimizer’s handling of
discrete-time BF constraints outperforms the state-of-the-art solver ACADO
[20] with a $31$ times faster per-agent computation time and a $44\%$
reduction in mission time on average.

##  II Distributed Motion Planning Problem

Our goal is to generate smooth, collision-free, and kinematically feasible
trajectories that navigate $N$ quadrotors from their initial positions
$\mathbf{p}_{i,o}$ to their desired goal positions $\mathbf{p}_{i,g}$ in an
obstacle-rich and possibly dynamic environment. The vector
$\mathbf{p}=[x,\>y,\>z]^{T}$ is the three-dimensional position of the
quadrotor, the subscript $i$ is the quadrotor index, and the subscripts $o$
and $g$ denote initial and goal variables.

Similar to [7, 8], we formulate the quadrotor swarm motion planning as a
distributed trajectory optimization problem, where the computation for each
quadrotor is parallelized. At each time step, the quadrotors exchange the
planned trajectories from the previous step and re-optimize the trajectories
towards their goal positions subject to constraints. The distributed
optimization problem is solved in a receding horizon fashion until each
quadrotor reaches its goal position.

We note that, in this work, the quadrotors’ trajectories are optimized online
to account for possible dynamic obstacles. We assume that the obstacles’
current positions and velocities are available to each quadrotor.

###  II-A Optimization Problem Formulation

At each planning step, the optimization problem solved by quadrotor $i$ is
formulated as follows:

$\displaystyle\min_{\mathbf{p}_{i}}\hskip 5.0pt$ $\displaystyle
w_{g}\sum_{k=K-\kappa}^{K-1}\left\|\mathbf{p}_{i}[k]-\mathbf{p}_{i,g}\right\|^{2}+w_{s}\sum_{k=0}^{K-1}\left\|\mathbf{p}_{i}^{(q)}[k]\right\|^{2}$
(1a) s.t.
$\displaystyle\mathbf{p}_{i}^{(q)}[0]=\mathbf{p}_{i,a}^{(q)},\>\forall
q=\\{0,1,2\\}$ (1b)
$\displaystyle\mathbf{\underline{p}}\preceq\mathbf{p}_{i}[k]\preceq\mathbf{\overline{p}},\>\forall
k$ (1c)
$\displaystyle\left\|\dot{\mathbf{p}}_{i}[k]\right\|^{2}\leq\overline{v}^{2},\>\forall
k$ (1d)
$\displaystyle\underline{f}^{2}\leq\left\|\ddot{\mathbf{p}}_{i}[k]+\mathbf{g}\right\|^{2}\leq\overline{f}^{2},\forall
k$ (1e) $\displaystyle
h_{ij}[k]=\left\|\boldsymbol{\Theta}_{ij}^{-1}(\mathbf{p}_{i}[k]-\boldsymbol{\xi}_{j}[k])\right\|^{2}-1\geq
0,\>\forall k,j,$ (1f)

where $k$ is the discrete-time index, $K$ is the planning horizon length,
$||\cdot||$ denotes the Euclidean norm, and the superscript $(q)$ denotes the
$q$-th time derivative of a variable.

The cost function consists of two terms. The first term is the goal cost that
penalizes the deviation of the position of the quadrotor from the specified
goal position over the last $\kappa<K$ steps in the prediction horizon; the
second term is the smoothness cost that penalizes the $q$-th derivatives of
the position trajectory. The constants $w_{g}$ and $w_{s}$ are weights trading
off the respective cost terms.

The equality constraints (1b) set the initial position of the trajectory and
the higher derivatives to be consistent with the current values of the
quadrotor. The inequalities (1c)-(1e) enforce bounds on the position
($\underline{\textbf{p}},\overline{\textbf{p}}$), bounds on the velocity
($-\overline{v},\overline{v}$), and bounds on the acceleration
($\underline{f},\overline{f}$). The inequalities (1f) enforce the collision
avoidance requirement with either the $j$-th neighbouring quadrotor or
obstacle with position $\boldsymbol{\xi}_{j}[k]$. The matrix
$\boldsymbol{\Theta}_{ij}$ is a diagonal matrix with $(a,b,c)$ being its
element. These scalars $(a,b,c)$ characterize the axis lengths of the
ellipsoidal envelopes around the neighbouring quadrotors or the obstacles. The
vector $\mathbf{g}=[0,\>0,\>g]^{T}$ is the gravitational acceleration vector,
where $g$ is the acceleration due to gravity.

Alternative Collision Avoidance Constraint: The condition in (1f) is commonly
found in works on quadrotor swarms (e.g., [7, 8, 21, 13]). A fundamental
problem with the standard collision avoidance constraint (1f) is that these
inequalities do not get activated until the planned trajectory intersects with
the neighbouring quadrotors or obstacles [15]. Due to the receding horizon
nature of the planning, a quadrotor only tries to avoid collisions with its
neighbours or obstacles when it is sufficiently close to them. Increasing the
planning horizon can mitigate this issue but at the cost of increased
computation time. An alternative approach is to use BF constraints to induce a
desired collision avoidance behaviour [15]:

$\displaystyle h_{ij}[k]-h_{ij}[k-1]\geq-\gamma\>h_{ij}[k-1],\>\forall k,j,$
(2)

where $\gamma\in[0,1]$ is a constant controlling how fast the quadrotor is
allowed to approach the constraint boundary given by $h_{ij}=0$. Smaller
values of $\gamma$ generally result in more gradual and conservative collision
avoidance behaviours. With $\gamma=1$, we recover the original collision-
avoidance constraint in (1f).

###  II-B Trajectory Parameterization

We parameterize the $x$-, $y$-, and $z$-position trajectories for each
quadrotor as Bernstein polynomials of degree $n$. For instance, the
$x$-position trajectory for the $i$-th quadrotor is

$\displaystyle\begin{bmatrix}x_{i}[0]&x_{i}[1]&\ldots&x_{i}[K-1]\end{bmatrix}^{T}=\mathbf{W}\mathbf{c}_{i,x},$
(3)

where $\mathbf{W}\in\mathbb{R}^{K\times(n+1)}$ is the Bernstein basis matrix
and $\mathbf{c}_{i,x}$ are the coefficients associated with it. The $k$-th row
and $m$-th column element of $\mathbf{W}$ is $[\mathbf{W}]_{km}={n\choose
m}(1-t/(K-1)\delta t)^{n-m}(t/(K-1)\delta t)^{m}$, where $\delta t$ is the
discrete-time step size, and $t=k\delta t$ is the continuous-time variable.
The higher derivatives of the position trajectory have the general form
$\mathbf{W}^{(q)}\mathbf{c}_{i,x}$, where $\mathbf{W}^{(q)}$ is the $q$-th
derivative of the Bernstein basis matrix. The position trajectories for the
$y$\- and $z$-directions are defined in a similar way.

###  II-C Challenges in Solving the Optimization Problem

The optimization problem in (1a)-(1f) is a non-convex quadratically
constrained quadratic program (QCQP). Existing works (e.g., [6, 7, 8]) achieve
a more favourable QP form by deriving the convex approximation of (1d)-(1f):
the velocity and acceleration bounds are split into axis-wise affine bounds,
and the non-convex collision avoidance constraints are approximated as affine
constraints through linearization along a trajectory. These approximations can
lead to a substantial loss of the feasible space (see Fig. 3 in [22], Fig. 2
in [23]).

Achieving a QP structure with the BF constraints (2) is even more challenging.
To see this, we rewrite (2) as

$\displaystyle-h_{ij}[k]+(1-\gamma)h_{ij}[k-1]\leq 0,\>\forall k,j.$ (4)

The constraint is non-convex, and the non-convexity comes from the first term
$-h_{ij}[k]$. If we linearize the first term, we get an exact but a more
conservative convex substitute for the BF constraint. However, the resulting
constraint still remains quadratic in the decision variables due to the
presence of $h_{ij}[k-1]$. Linearizing the complete right-hand side of (4)
will lead to a QP form. However, satisfaction of a completely linearized
version may not imply satisfaction of (4) [24].

##  III The Alternating Minimization Algorithm

This section presents our main algorithmic results: an AM-based linearization-
free trajectory optimizer for solving the motion planning problem introduced
in Sec. II-A. We first present the solution for the case with standard
collision constraints (1f). We then show how it naturally extends to the BF
constraints (2).

###  III-A Constraints Reformulation

In our proposed approach, one key ingredient that enables us to bring the QCQP
problem to a QP form is a polar reformulation of the quadratic constraints
(1d)-(1f). Here we present a general form of the polar representation
presented in [25] for quadratic constraints.

Consider an inequality of the form
$||\mathbf{M}(\mathbf{v}-\mathbf{v}_{0})||^{2}\leq\eta^{2}$ (or
$||\mathbf{M}(\mathbf{v}-\mathbf{v}_{0})||^{2}\geq\eta^{2}$) with $\mathbf{M}$
being a diagonal matrix with positive entries. The inequality constraint can
be equivalently written in a polar form as follows:
$\mathbf{f}=\mathbf{M}(\mathbf{v}-\mathbf{v}_{0})-d\>\boldsymbol{\omega}(\alpha,\beta)=0$
with $d\leq\eta$ (or $d\geq\eta$). Here,
$\boldsymbol{\omega}(\alpha,\beta)=[\cos\alpha\sin\beta,\>\sin\alpha\sin\beta,\>\cos\beta]^{T}$
is a unit direction vector pointing from $\mathbf{v}_{0}$ to $\mathbf{v}$ with
$\alpha$ being the azimuthal angle and $\beta$ being the polar angle, and the
scalar $d$ is the magnitude of the vector
$\mathbf{M}(\mathbf{v}-\mathbf{v}_{0})$.

Using the polar reparametrization, we can write the quadratic constraints
(1d), (1e), and (1f) as the following constraint sets:

$\displaystyle\mathcal{C}_{i,v}[k]$
$\displaystyle=\\{\dot{\mathbf{p}}_{i}[k]\in\mathbb{R}^{3}\>|\>\mathbf{f}_{i,v}[k]=0,d_{i,v}[k]\leq\overline{v}\\},\>\forall
k,$ (5) $\displaystyle\mathcal{C}_{i,a}[k]$
$\displaystyle=\\{\ddot{\mathbf{p}}_{i}[k]\in\mathbb{R}^{3}\>|\>\mathbf{f}_{i,a}[k]=0,\underline{f}\leq
d_{i,a}[k]\leq\overline{f}\\},\>\forall k,$ (6)
$\displaystyle\mathcal{C}_{ij,c}[k]$
$\displaystyle=\\{\mathbf{p}_{i}[k]\in\mathbb{R}^{3}\>|\>\mathbf{f}_{ij,c}[k]=0,d_{ij,c}[k]\geq
1\\},\>\forall k,j,$ (7)

where the functions $\mathbf{f}_{ij,c}$, $\mathbf{f}_{i,v}$, and
$\mathbf{f}_{i,a}$ are

$\displaystyle\mathbf{f}_{i,v}[k]$
$\displaystyle=\dot{\mathbf{p}}_{i}[k]-d_{i,v}[k]\>\boldsymbol{\omega}(\alpha_{i,v}[k],\beta_{i,v}[k]),$
$\displaystyle\mathbf{f}_{i,a}[k]$
$\displaystyle=\ddot{\mathbf{p}}_{i}[k]+\mathbf{g}-d_{i,a}[k]\>\boldsymbol{\omega}(\alpha_{i,a}[k],\beta_{i,a}[k]),$
$\displaystyle\mathbf{f}_{ij,c}[k]$
$\displaystyle=\boldsymbol{\Theta}^{-1}_{ij}(\mathbf{p}_{i}[k]-\boldsymbol{\xi}_{j}[k])-d_{ij,c}[k]\boldsymbol{\omega}(\alpha_{ij,c}[k],\beta_{ij,c}[k]).$

Note that $(\alpha_{\cdot,\cdot},\beta_{\cdot,\cdot},d_{\cdot,\cdot})$ are the
parameters of the polar form representations of the constraints and will be
computed by our optimizer together with the trajectory.

###  III-B Reformulated Problem

Before deriving the final form of our reformulated problem, we rewrite the
polar form constraints derived in the previous subsection in a compact matrix
form. Given the parametrization in (3), the equality part of constraints (5),
(6), (7) can be represented as

$\displaystyle\overbrace{\begin{bmatrix}\widetilde{\mathbf{A}}&&\\\
&\widetilde{\mathbf{A}}&\\\
&&\widetilde{\mathbf{A}}\end{bmatrix}}^{\mathbf{A}}\overbrace{\begin{bmatrix}\mathbf{c}_{i,x}\\\
\mathbf{c}_{i,y}\\\
\mathbf{c}_{i,z}\end{bmatrix}}^{\boldsymbol{\zeta}_{i,1}}=\overbrace{\begin{bmatrix}\mathbf{d}_{i,v}\cos\boldsymbol{{\alpha}}_{i,v}\sin\boldsymbol{{\beta}}_{i,v}\\\
\mathbf{d}_{i,a}\cos\boldsymbol{{\alpha}}_{i,a}\sin\boldsymbol{{\beta}}_{i,a}\\\
\boldsymbol{\xi}_{x}+a\mathbf{d}_{i,c}\cos\boldsymbol{{\alpha}}_{i,c}\sin\boldsymbol{{\beta}}_{i,c}\\\
\hline\cr\mathbf{d}_{i,v}\sin\boldsymbol{{\alpha}}_{i,v}\sin\boldsymbol{{\beta}}_{i,v}\\\
\mathbf{d}_{i,a}\sin\boldsymbol{{\alpha}}_{i,a}\sin\boldsymbol{{\beta}}_{i,a}\\\
\boldsymbol{\xi}_{y}+b\mathbf{d}_{i,c}\sin\boldsymbol{{\alpha}}_{i,c}\sin\boldsymbol{{\beta}}_{i,c}\\\
\hline\cr\mathbf{d}_{i,v}\cos\boldsymbol{{\beta}}_{i,v}\\\
-\widetilde{\mathbf{g}}+\mathbf{d}_{i,a}\cos\boldsymbol{{\beta}}_{i,a}\\\
\boldsymbol{\xi}_{z}+c\mathbf{d}_{i,c}\cos\boldsymbol{{\beta}}_{i,c}\end{bmatrix}.}^{\mathbf{b}}$
(8)

Here,
$\widetilde{\mathbf{A}}=\begin{bmatrix}\dot{\mathbf{W}}^{T}&\ddot{\mathbf{W}}^{T}&\mathbf{F}_{c}^{T}\end{bmatrix}^{T}$,
the matrix $\mathbf{F}_{c}$ is constructed by vertically stacking the matrix
$\mathbf{W}$ as many times as the number of neighbouring quadrotors and
obstacles present in the environment. The vectors
$(\boldsymbol{\xi}_{x},\boldsymbol{\xi}_{y},\boldsymbol{\xi}_{z})$ are formed
by vertically stacking the corresponding variables
$({\xi}_{j,x}[k],{\xi}_{j,y}[k],{\xi}_{j,z}[k])$ at different time steps of
the prediction horizon and for all the neighbouring quadrotors and obstacles.
In a similar fashion,
$(\boldsymbol{\alpha}_{\cdot,\cdot},\boldsymbol{\beta}_{\cdot,\cdot},\mathbf{d}_{\cdot,\cdot})$
are formed by vertically stacking
$({\alpha}_{\cdot,\cdot}[k],{\beta}_{\cdot,\cdot}[k],{d}_{\cdot,\cdot}[k])$.
The vector $\widetilde{\mathbf{g}}$ is formed by vertically stacking $g$ as
many times as the length of prediction horizon.

Using the derivations above, we now write the reformulated optimization
problem as

$\displaystyle\min_{\boldsymbol{\zeta}_{i,1},\boldsymbol{\zeta}_{i,2},\boldsymbol{\zeta}_{i,3}}\hskip
5.0pt$
$\displaystyle\frac{1}{2}\boldsymbol{\zeta}_{i,1}^{T}\mathbf{Q}\boldsymbol{\zeta}_{i,1}+\mathbf{q}^{T}\boldsymbol{\zeta}_{i,1}$
(9a) s.t.
$\displaystyle\mathbf{A}\boldsymbol{\zeta}_{i,1}=\mathbf{b}(\boldsymbol{\zeta}_{i,2},\boldsymbol{\zeta}_{i,3})$
(9b) $\displaystyle\mathbf{G}\boldsymbol{\zeta}_{i,1}\preceq\mathbf{h}$ (9c)
$\displaystyle\boldsymbol{\zeta}_{i,1}\in\mathcal{C}_{{\zeta}_{i,1}},\boldsymbol{\zeta}_{i,3}\in\mathcal{C}_{{\zeta}_{i,3}},$
(9d)

where
$\boldsymbol{\zeta}_{i,1}=[\mathbf{c}_{i,x}^{T},\>\mathbf{c}_{i,y}^{T},\>\mathbf{c}_{i,z}^{T}]^{T}$,
$\boldsymbol{\zeta}_{i,2}=[\boldsymbol{\alpha}_{i,c}^{T},\>\boldsymbol{\alpha}_{i,a}^{T},\>\boldsymbol{\alpha}_{i,v}^{T},\>\boldsymbol{\beta}_{i,c}^{T}$,
$\boldsymbol{\beta}_{i,a}^{T},\>\boldsymbol{\beta}_{i,v}^{T}]^{T}$, and
$\boldsymbol{\zeta}_{i,3}=[\mathbf{d}_{i,c},\>\mathbf{d}_{i,a},\>\mathbf{d}_{i,v}]^{T}$
are the variables to be optimized. The matrix $\mathbf{Q}$ and vector
$\mathbf{q}$ are formed from the objective function (1a). The matrix
$\mathbf{G}$ and vector $\mathbf{h}$ in the inequality constraint (9c) stem
from the positional bounds (1c).

The set
$\mathcal{C}_{\boldsymbol{\zeta}_{i,1}}\mathord{=}\\{\boldsymbol{\zeta}_{i,1}\in\mathbb{R}^{3n}\>|\>\mathbf{C}\boldsymbol{\zeta}_{i,1}=\mathbf{e}\\}$
encodes the initial conditions (1b). Here, the matrix
$\mathbf{C}=[\mathbf{W}_{0}^{T},\>\dot{\mathbf{W}}_{0}^{T},\>\ddot{\mathbf{W}}_{0}^{T}]^{T}$,
and the subscript $0$ represents the $0$-$th$ row of the respective matrices.
The vector
$\mathbf{e}=[\mathbf{p}_{i,a}^{T},\>\dot{\mathbf{p}}_{i,a}^{T},\>\ddot{\mathbf{p}}_{i,a}^{T}]^{T}$
contains the current position, velocity and acceleration values. The set
$\mathcal{C}_{\boldsymbol{\zeta}_{i,3}}$ consists of the conditions on each of
the variables $(\mathbf{d}_{ij,c},\mathbf{d}_{i,v},\mathbf{d}_{i,a})$ derived
from the polar reformulation.

###  III-C Relaxation and Solution by AM

The optimization (9a)-(9d) has some hidden convex structures which makes it
suitable for AM-based approaches. To exploit these structures, we first relax
the non-convex equality (9b) and affine (9c) constraints as penalties in the
following form:

$\displaystyle\min_{\boldsymbol{\zeta}_{i,1}\in\mathcal{C}_{{\zeta}_{i,1}},\boldsymbol{\zeta}_{i,3}\in\mathcal{C}_{{\zeta}_{i,3}}}\frac{1}{2}\boldsymbol{\zeta}_{i,1}^{T}\mathbf{Q}\boldsymbol{\zeta}_{i,1}+\mathbf{q}^{T}\boldsymbol{\zeta}_{i,1}-\langle\boldsymbol{\lambda}_{i},\boldsymbol{\zeta}_{i,1}\rangle$
$\displaystyle+\frac{\rho}{2}\left\|\mathbf{A}\boldsymbol{\zeta}_{i,1}-\mathbf{b}(\boldsymbol{\zeta}_{i,2},\boldsymbol{\zeta}_{i,3})\right\|^{2}+\frac{\rho}{2}\left\|\mathbf{G}\boldsymbol{\zeta}_{i,1}-\mathbf{h}+{\mathbf{s}_{i}}\right\|^{2}.$
(10)

The parameter $\rho$ trades-off satisfaction of constraint residual with the
minimization of primary cost function. The slack variable
$\textbf{s}_{i}\geq\mathbf{0}$ is unknown, and we discuss shortly how these
are obtained within an AM setup. The vector $\boldsymbol{\lambda}_{i}$ is
called the Lagrange multiplier and is crucial for driving the constraint
residuals to zero [26].

Algorithm 1 summarizes the AM steps for minimizing (10), wherein the
superscript $l$ in ${}^{l}{(.)}$ represents the value of $(.)$ at $l$-th
iteration of the algorithm. At each step of the AM, only one of
$\boldsymbol{\zeta}_{i,1},\boldsymbol{\zeta}_{i,2},\boldsymbol{\zeta}_{i,3}$
are optimized while the rest are held fixed at values obtained in the previous
update. Each step in Algorithm 1 is either a convex QP or has a closed-form
solution. We discuss these observations below in detail.

Step (S1): We solve for $\boldsymbol{\zeta}_{i,1}$ while keeping the other
variables constant. We see that the problem is an equality-constrained convex
QP whose solution boils down to solving a set of linear equations:

$\displaystyle\begin{bmatrix}\check{\mathbf{A}}&\mathbf{C}^{T}\\\
\mathbf{C}&\mathbf{0}\end{bmatrix}\begin{bmatrix}{}^{l+1}\boldsymbol{\zeta}_{i,1}\\\
\boldsymbol{\mu}\end{bmatrix}=\begin{bmatrix}{}^{l}\check{\mathbf{b}}\\\
\mathbf{e}\end{bmatrix},$ (11)

where the matrix
$\check{\mathbf{A}}\mathord{=}\mathbf{Q}+\rho\mathbf{G}^{T}\mathbf{G}+\rho\mathbf{A}^{T}\mathbf{A}$,
the vector
${}^{l}\check{\mathbf{b}}\mathord{=}\mathbf{q}+\rho\mathbf{G}^{T}(\mathbf{h}-^{l}\mathbf{s}_{i})+\rho\mathbf{A}^{T}{{}^{l}}\mathbf{b}-{{}^{l}}\boldsymbol{\lambda}_{i}$,
and $\boldsymbol{\mu}$ are the dual variables associated with the equality
constraints.

Step (S2): We now solve for $\boldsymbol{\zeta}_{i,2}$. As an example, the
optimization problem for the variables
$(\boldsymbol{\alpha}_{i,c},\boldsymbol{\beta}_{i,c})$ is

$\displaystyle{{}^{l+1}}\boldsymbol{\alpha}_{i,c},{{}^{l+1}}\boldsymbol{\beta}_{i,c}\mathord{=}\arg\min_{\alpha_{i,c},\beta_{i,c}}$
$\displaystyle\left\|\mathbf{F}_{c}{{}^{l+1}}\mathbf{c}_{i,x}-\boldsymbol{\xi}_{x}-a{{}^{l}}\mathbf{d}_{i,c}\cos\boldsymbol{{\alpha}}_{i,c}\sin\boldsymbol{{\beta}}_{i,c}\right\|^{2}$
$\displaystyle+\left\|\mathbf{F}_{c}{{}^{l+1}}\mathbf{c}_{i,y}-\boldsymbol{\xi}_{y}-b{{}^{l}}\mathbf{d}_{i,c}\sin\boldsymbol{{\alpha}}_{i,c}\sin\boldsymbol{{\beta}}_{i,c}\right\|^{2}$
$\displaystyle+\left\|\mathbf{F}_{c}{{}^{l+1}}\mathbf{c}_{i,z}-\boldsymbol{\xi}_{z}-c{{}^{l}}\mathbf{d}_{i,c}\cos\boldsymbol{{\beta}}_{i,c}\right\|^{2}.$
(12)

The minimization (12) is simply a projection of
$(^{l+1}{\mathbf{c}_{i,x}},^{l+1}{\mathbf{c}_{i,y}},^{l+1}{\mathbf{c}_{i,z}})$
onto ellipsoids centered at
$(\boldsymbol{\xi}_{x},\boldsymbol{\xi}_{y},\boldsymbol{\xi}_{z})$ and has a
closed-form solution [25]. Similarly, we can obtain
$(^{l+1}\boldsymbol{\alpha}_{i,v},^{l+1}\boldsymbol{\beta}_{i,v})$ and
$(^{l+1}\boldsymbol{\alpha}_{i,a},^{l+1}\boldsymbol{\beta}_{i,a})$.

Step (S3): The optimization over $\textbf{d}_{i,c}$ involves solving the
following QP:

$\displaystyle{{}^{l+1}}\mathbf{d}_{i,c}=\arg\min_{\mathbf{d}_{i,c}\geq 1}$
$\displaystyle\left\|\mathbf{F}_{c}{{}^{l+1}}\mathbf{c}_{i,x}-\boldsymbol{\xi}_{x}-a\mathbf{d}_{i,c}\cos{{}^{l+1}}\boldsymbol{{\alpha}}_{i,c}\sin{{}^{l+1}}\boldsymbol{{\beta}}_{i,c}\right\|^{2}$
$\displaystyle+\left\|\mathbf{F}_{c}{{}^{l+1}}\mathbf{c}_{i,y}-\boldsymbol{\xi}_{y}-b\mathbf{d}_{i,c}\sin{{}^{l+1}}\boldsymbol{{\alpha}}_{i,c}\sin{{}^{l+1}}\boldsymbol{{\beta}}_{i,c}\right\|^{2}$
$\displaystyle+\left\|\mathbf{F}_{c}{{}^{l+1}}\mathbf{c}_{i,z}-\boldsymbol{\xi}_{z}-c\mathbf{d}_{i,c}\cos{{}^{l+1}}\boldsymbol{{\beta}}_{i,c}\right\|^{2}.$
(13)

Each element of $\textbf{d}_{i,c}$ is decoupled from each other. Thus (13)
reduces to parallel single variable QPs, each of which can be solved in closed
form. We clip the resulting solution to $(1,\infty)$ to satisfy the lower
bound on $\textbf{d}_{i,c}$ (recall the definition of
$\mathcal{C}_{{\zeta}_{i,3}}$). We obtain $\mathbf{d}_{i,v}$ and
$\mathbf{d}_{i,a}$ in a similar fashion with their respective clipping bounds.

Step (S4): The slack variables $\mathbf{s}_{i}$ is updated based on [27].

Step (S5): The Lagrange multipliter $\boldsymbol{\lambda}_{i}$ is updated
using the approach presented in [26].

Algorithm 1 The AM algorithm used by quadrotor $i$ at each planning step

1:Initialize
${{}^{l}}\boldsymbol{\zeta}_{i,2}=\mathbf{0},{{}^{l}}\boldsymbol{\zeta}_{i,3}=\mathbf{0},{{}^{l}}\boldsymbol{\lambda}_{i}=\mathbf{0},{{}^{l}}\mathbf{s}_{i}=\mathbf{0}$
at $l=0$

2:while $l\leq\text{maxiter}$ or residuals $\geq$ thresold do

3: $\displaystyle{{}^{l+1}}\boldsymbol{\zeta}_{i,1}$
$\displaystyle=\text{arg}\min_{\boldsymbol{\zeta}_{i,1}\in\mathcal{C}_{\boldsymbol{\zeta}_{i,1}}}\frac{1}{2}\boldsymbol{\zeta}_{i,1}^{T}\mathbf{Q}\boldsymbol{\zeta}_{i,1}+\mathbf{q}^{T}\boldsymbol{\zeta}_{i,1}-\langle{{}^{l}}\boldsymbol{\lambda},\boldsymbol{\zeta}_{i,1}\rangle$
$\displaystyle+$
$\displaystyle\frac{\rho}{2}\left\|\mathbf{A}\boldsymbol{\zeta}_{i,1}-\mathbf{b}({{}^{l}}\boldsymbol{\zeta}_{i,2},{{}^{l}}\boldsymbol{\zeta}_{i,3})\right\|^{2}+\frac{\rho}{2}\left\|\mathbf{G}\boldsymbol{\zeta}_{i,1}-\mathbf{h}+{{}^{l}}\mathbf{s}_{i}\right\|^{2}$
(S1) $\displaystyle{{}^{l+1}\boldsymbol{\zeta}_{i,2}}=$
$\displaystyle\text{arg}\min_{\boldsymbol{\zeta}_{i,2}}\frac{\rho}{2}\left\|\mathbf{A}{{}^{l+1}}\boldsymbol{\zeta}_{i,1}-\mathbf{b}(\boldsymbol{\zeta}_{i,2},{{}^{l}}\boldsymbol{\zeta}_{i,3})\right\|^{2}$
(S2) $\displaystyle{{}^{l+1}\boldsymbol{\zeta}_{i,3}}=$
$\displaystyle\text{arg}\min_{\boldsymbol{\zeta}_{i,3}\in\mathcal{C}_{\boldsymbol{\zeta}_{i,3}}}\frac{\rho}{2}\left\|\mathbf{A}{{}^{l+1}}\boldsymbol{\zeta}_{i,1}-\mathbf{b}({{}^{l+1}}\boldsymbol{\zeta}_{i,2},\boldsymbol{\zeta}_{i,3})\right\|^{2}$
(S3) $\displaystyle{{}^{l+1}}\mathbf{s}_{i}=$
$\displaystyle\text{max}\left(0,-\mathbf{G}{{}^{l+1}}\boldsymbol{\zeta}_{i,1}-\mathbf{h}\right)$
(S4) $\displaystyle{{}^{l+1}}\boldsymbol{\lambda}_{i}=$
$\displaystyle{{}^{l}}\boldsymbol{\lambda}_{i}-\frac{\rho}{2}\mathbf{A}^{T}\left(\mathbf{A}{{}^{l+1}}\boldsymbol{\zeta}_{i,1}-\mathbf{b}({{}^{l+1}}\boldsymbol{\zeta}_{i,2},{{}^{l+1}}\boldsymbol{\zeta}_{i,3})\right)$
$\displaystyle-$
$\displaystyle\frac{\rho}{2}\mathbf{G}^{T}\left(\mathbf{G}{{}^{l+1}}\boldsymbol{\zeta}_{i,1}-\mathbf{h}+{{}^{l+1}}\mathbf{s}_{i}\right)$
(S5)

4:end while

###  III-D Incorporating BF Constraints

In (7), $d_{i,c}[k]\mathord{=}1$ corresponds to the boundary of the feasible
set of the collision avoidance constraints (1f). In other words,
$d_{ij,c}[k]\mathord{=}1$ ensures $h_{ij}[k]\mathord{=}0$. Along similar
lines, $d_{ij,c}[k]<1$ would correspond to the interior of the set. With this
insight, we can define the polar reformulation of BF constraints in the
following form:

$\displaystyle\mathcal{C}_{ij,bf}[k]=\\{\mathbf{p}_{i}[k]\>|\>\mathbf{f}_{ij,c}[k]=0,$
$\displaystyle\hskip 20.00003ptd_{ij,c}[k]\geq
1+(1-\gamma)(d_{ij,c}[k-1]-1)\\},\>\forall k,j,$ (14)

By comparing (7) and (14), we can see that the constraints differ only in the
feasible region definition of $d_{ij,c}[k]$. When $\gamma\mathord{=}1$, the
constraints are equivalent.

We integrate (14) into Algorithm 1 through a minor modification in Step (S3),
specifically QP (13). Let ${}^{l}d_{ij,c}[k]$ be the value of $d_{ij,c}[k]$
obtained at the $l$-th iteration of Algorithm 1. We can use this value to
approximate the feasible region of $d_{ij,c}[k]$ for BF constraints at the
$(l+1)$-th iteration as

$\displaystyle d_{ij,c}[k]\geq 1+(1-\gamma)({{}^{l}}d_{ij,c}[k-1]-1).$ (15)

The right-hand side of (15) is constant, and thus the feasible region of
$d_{ij,c}[k]$ for BF constraints is approximated through a simple lower bound.
We can now just solve the QP (13) and clip the obtained value to this lower
bound to solve for the optimal $d_{ij,c}[k]$ at iteration $(l+1)$.

##  IV Simulation Results

This section provides a simulation analysis and comparison of our approach
against the state-of-the-art baselines [7, 9, 20]. We denote our approach as
“Ours (Quadratic)”, and the “Quadratic” in the parenthesis refers to quadratic
kinematic constraints. The proposed approach and the baselines are implemented
in C++. The codes are available here [28]. All the simulations were executed
on a PC with Intel Xeon CPU with 8 cores and 16 GB of RAM, running at 3 GHz.

The prediction horizon length is set to $K\mathord{=}30$ with a discretization
of $0.1s$. The Bernstein polynomials used to parameterize the position
trajectories have a degree of $n\mathord{=}10$. In the trajectory optimization
problem (1a)-(1f), we set $w_{g}\mathord{=}7000$, $w_{s}\mathord{=}100$,
$\kappa\mathord{=}5$ and penalize the acceleration $(q\mathord{=}2)$
trajectory in the cost. In the constraints, we set
$\overline{v}\mathord{=}1.73ms^{-1}$, $\underline{f}\mathord{=}0.3g$ and
$\overline{f}\mathord{=}1.5g$. For collision avoidance with neighbouring
quadrotors, we set
${\boldsymbol{\Theta}}_{ij}\mathord{=}\text{diag}(0.17m,0.17m,0.45m)$, but a
collision is declared with
${\boldsymbol{\Theta}}_{coll}\mathord{=}\text{diag}(0.13m,0.13m,0.40m)$. A
quadrotor $j$ is considered to be a potential conflict for quadrotor $i$ if at
any prediction step of the horizon,
$\left\|(\boldsymbol{\Theta}_{ij}+\boldsymbol{\Theta}_{p})^{-1}(\mathbf{p}_{i}[k]-\boldsymbol{\xi}_{j}[k])\right\|^{2}\mathord{\geq}1$
holds, where $\boldsymbol{\Theta}_{p}\mathord{=}\text{diag}(0.2m,0.2m,0.2m)$.
Similarly, we choose appropriate parameters for the collision constraints with
obstacles. In Algorithm 1, we set maxiter$\mathord{=}2000$,
thresold$\mathord{=}0.01$, and the penalty parameter
$\rho\mathord{=}min(1.3^{l},5e10^{5})$, where $l$ is the iteration count of
the algorithm.

###  IV-A Distributed Swarm Baselines

We compare our proposed approach Ours (Quadratic) with $\gamma\mathord{=}1$
with three different distributed swarm baselines:

  1. 1.

SCP (On-demand) [8]: This approach relies on linearization of collision
avoidance constraints and axis-wise decoupling of the kinematic bounds. It
uses a so-called On-demand strategy where it tries to resolve only the first
predicted collision.

  2. 2.

SCP (Continuous) [9]: This approach is similar to SCP (On-demand) but it adds
collision constraints over the entire prediction horizon.

  3. 3.

Ours (Axiswise): This approach is the same as Ours (Quadratic) in the sense
that it does not rely on linearizing collision constraints but has axis-wise
kinematic bounds. The maximum and minimum values for the axis-wise velocity
bounds are $\pm{\overline{v}}/{\sqrt{3}}$, and the acceleration limits can be
computed such that it satisfies extreme cases (see (13) and (14) of [6]).

We consider a cluttered environment with $16$ cylindrical static obstacles in
a volume of $4m\times 4m\times 2m$ and vary swarms from $10$ to $50$. We
tested the approaches in $100$ configurations for each swarm size with
randomized start-goal and obstacle positions. A trial is successful if all the
quadrotors reach their assigned goal positions without collisions and under a
time limit of $20s$.

###  IV-B Comparative Analysis

Success Rate: The first plot in Fig. 2 summarizes the improvement achieved by
Ours (Quadratic) and Ours (Axiswise) over SCP (On-demand), and SCP
(Continuous) in the success-rate metric. For swarm size up to 30, our
approaches provide around $11\%$-$62\%$ improvement over SCP (On-demand) and
$1\%$-$19\%$ over SCP (Continuous). As swarm size increase to 50, the
performance gap between our approaches and the SCP (On-demand) and SCP
(Continuous) swell to $39\%$-$72\%$. The explanation is that the SCP baselines
replace the non-convex collision constraints as hyperplane constraints, a
conservative approximation of free space. Furthermore, SCP (On-demand) adds
only a handful of collision constraints that result in unsafe separation and,
ultimately, collisions in highly cluttered settings. For swarm size $50$, we
also see that Ours (Quadratic) has $15\%$ more success rate than Ours
(Axiswise) as the former has larger access to acceleration and velocity
bounds.

Computation Time per Agent: The middle plot in Fig. 2 shows the average
computation time per agent for the different swarm sizes. Both of our
approaches have similar computation time per agent and are substantially
faster than SCP (On-demand) and SCP (Continuous). For the swarm size of $10$
case, we see that our approaches are $1.7$ times faster than SCP (On-demand),
and $18.7$ times faster than SCP (Continuous). With a swarm size of $50$, our
approaches are still $1.7$ times faster than SCP (On-demand) but are $42$
times faster than SCP (Continuous). This excellent performance of our
approaches can be attributed to the fact that AM optimizer of Algorithm 1
requires us to solve only one equality-constrained QP per iteration. On the
contrary, the SCP (Continuous) solves constrained QP with a large number of
inequality constraints. Moreover, it has to incorporate one slack variable per
collision constraint to prevent potential in-feasibility in the optimization
problem. The strategy of incorporating only the most imminent collision in SCP
(On-demand) offers improvement in computation time per agent but at the
expense of success rate as described previously.

Mission Time: The rightmost plot in Fig. 2 presents the average time taken by
the swarm to reach their desired goal positions. We see that SCP (On-demand)
performs the worst as the on-demand strategy leads to agents being closer to
each other and obstacles, thus, slowing down the progress toward their goals.
SCP (Continuous) performs relatively better than SCP (On-demand), but our
approaches have the lowest mission times. For swarm size $40$, we see that
Ours (Quadratic) on average shows $36\%$ and $15\%$ reduction in mission time
than SCP (On-demand) and SCP (Continuous), respectively. Interestingly, the
trends show that Ours (Axiswise), on average, completed the task $0.5s$-$0.9s$
faster than Ours (Quadratic).

Figure 2: Average performance comparison of approaches in point-to-point
transition setting with an increasing number of swarm sizes in a fixed volume
of $32m^{3}$ and with $16$ static obstacles. 100 configurations were run for
each swarm size.

###  IV-C Trade-off Between Performance and Safety

Figure 3 showcases the performance comparison of Ours (Quadratic) with three
different values of $\gamma$. We ran the same $100$ configurations and
recorded the smallest inter-agent distance and distance-to-obstacles observed
at each time step. With $\gamma\mathord{=}0.95$, we see $3.98\%$-$8.69\%$
improvement in inter-agent distances over $\gamma\mathord{=}1$. The
improvements increase to $7.11\%$-$12.35\%$ with a more conservative
$\gamma\mathord{=}0.9$. We see a similar trend in distance-to-obstacles. This
improvement in clearance comes at the expense of increased mission time (see
first plot in Fig. 3). We also observed that the computation time per agent
increased with decreasing $\gamma$. For swarm size $50$, the average
computation time per agent is $1.61ms$, $82\%$ increase over
$\gamma\mathord{=}1$. Nevertheless, our approach is still real-time.

Figure 3: Average performance comparison of our approach in point-to-point
transition setting with different values of $\gamma$ in the barrier function
constraints. The environment is of $32m^{3}$ in volume and has $16$ static
obstacles. For each swarm size, $100$ configurations were executed.

###  IV-D Off-the-shelf Solver Baseline

We now compare Ours (Quadratic) against the optimal control solver ACADO [20].
ACADO is provided with the original BF constraints (2), while Ours (Quadratic)
uses the reformulation presented in (14). We ran an antipodal position
exchange with a swarm size of $2$, $4$, $6$, and $8$ with no static obstacles.
Figure 4 presents the observed metrics. We see that the computation time per
agent scaling for Ours (Quadratic) is linear, while for ACADO, it increases
quadratically with the number of agents. Furthermore, Ours (Quadratic) can
complete the task faster than ACADO.

Figure 4: Performance comparison of our approach and ACADO with BF constraints
($\gamma=0.9$) in antipodal position exchange scenario with no static
obstacles. ACADO could accomodate only a maximum of 8 agents.

##  V Experimental Evaluation

We tested our approach on our Crazyflie 2.0 swarm testbed. The quadrotors’
trajectories are computed on a single computer, and we send position and
velocity trajectories to the underlying lower controller based on [29]. More
details about the testbed can be found here [28].

A video summarizing the experimental results can be found here:
http://tiny.cc/AMSwarmVideo. The algorithm is tested on various challenging
scenarios. First, a 12 quadrotor swarm performs a head-on transition where a
single quadrotor is in conflict with other 11 quadrotors at a time in an
obstacle-free environment. Second, we repeat the same transition but with 6
static obstacles in the environment. We see that our approach navigates the
quadrotors to their desired goals in an agile and smooth manner. Third, we
qualitatively show a 12 drone random transition in an obstacle-free setting
with two values of $\gamma$. We see quadrotors with conservative $\gamma$ show
a safe, evasive behaviour. Lastly, a formation of 8 quadrotors performs a
transition in the presence of an unpredictable human. With the help of BF
constraints, each quadrotor is able to navigate around the human safely.

##  VI Conclusion

We presented a novel contribution toward making quadrotor swarm navigation
more reliable and scalable. We showed how to formulate the original problem
with quadratic collision and kinematic constraints as a QP without relying on
conservative approximations. Furthermore, our approach can naturally handle
more sophisticated collision avoidance constraints based on discrete-time BFs.
In simulation, our optimizer significantly outperformed SCP-based approaches
that have been common in recent works. Similarly, our approach also proved to
be more computationally efficient than the state-of-the-art optimal control
solver ACADO when considering BF constraints. In experiments, we showed the
efficacy of the proposed algorithm in challenging scenarios in both obstacle-
free and cluttered environments.

## References

  * [1] L. Marconi, C. Melchiorri, M. Beetz, D. Pangercic, R. Siegwart, S. Leutenegger, R. Carloni, S. Stramigioli, H. Bruyninckx, P. Doherty _et al._ , “The SHERPA project: Smart collaboration between humans and ground-aerial robots for improving rescuing activities in alpine environments,” in _Proc. of the IEEE International Symposium on Safety, Security, and Rescue Robotics_ , 2012, pp. 1–4.
  * [2] P. Schmuck and M. Chli, “Multi-UAV collaborative monocular SLAM,” in _Proc. of the IEEE International Conference on Robotics and Automation (ICRA)_ , 2017, pp. 3863–3870.
  * [3] S. Tang and V. Kumar, “Mixed integer quadratic program trajectory generation for a quadrotor with a cable-suspended payload,” in _Proc. of the IEEE International Conference on Robotics and Automation (ICRA)_ , 2015, pp. 2216–2222.
  * [4] S.-J. Chung, A. A. Paranjape, P. Dames, S. Shen, and V. Kumar, “A survey on aerial swarm robotics,” _IEEE Transactions on Robotics_ , vol. 34, no. 4, pp. 837–855, 2018.
  * [5] T. Schouwenaars, B. De Moor, E. Feron, and J. How, “Mixed integer programming for multi-vehicle path planning,” in _Proc. of the IEEE European Control Conference (ECC)_ , 2001, pp. 2603–2608.
  * [6] F. Augugliaro, A. P. Schoellig, and R. D’Andrea, “Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach,” in _Proc. of the IEEE/RSJ international conference on Intelligent Robots and Systems (IROS)_ , 2012, pp. 1917–1922.
  * [7] C. E. Luis and A. P. Schoellig, “Trajectory generation for multiagent point-to-point transitions via distributed model predictive control,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 375–382, 2019\.
  * [8] C. E. Luis, M. Vukosavljev, and A. P. Schoellig, “Online trajectory generation with distributed model predictive control for multi-robot motion planning,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 604–611, 2020\.
  * [9] E. Soria, F. Schiano, and D. Floreano, “Distributed predictive drone swarms in cluttered environments,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 1, pp. 73–80, 2021.
  * [10] ——, “Predictive control of aerial swarms in cluttered environments,” _Nature Machine Intelligence_ , vol. 3, no. 6, pp. 545–554, 2021.
  * [11] D. Zhou, Z. Wang, S. Bandyopadhyay, and M. Schwager, “Fast, on-line collision avoidance for dynamic vehicles using buffered voronoi cells,” _IEEE Robotics and Automation Letters_ , vol. 2, no. 2, pp. 1047–1054, 2017.
  * [12] X. Zhou, J. Zhu, H. Zhou, C. Xu, and F. Gao, “Ego-swarm: A fully autonomous and decentralized quadrotor swarm system in cluttered environments,” in _Proc. of the IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 4101–4107.
  * [13] J. Park, D. Kim, G. C. Kim, D. Oh, and H. J. Kim, “Online distributed trajectory planning for quadrotor swarm with feasibility guarantee using linear safe corridor,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 4869–4876, 2022.
  * [14] D. Morgan, G. P. Subramanian, S. Bandyopadhyay, S.-J. Chung, and F. Y. Hadaegh, “Probabilistic guidance of distributed systems using sequential convex programming,” in _Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2014, pp. 3850–3857.
  * [15] J. Zeng, B. Zhang, and K. Sreenath, “Safety-critical model predictive control with discrete-time control barrier function,” in _Prof. of the IEEE American Control Conference (ACC)_ , 2021, pp. 3882–3889.
  * [16] P. Mali, K. Harikumar, A. K. Singh, K. M. Krishna, and P. Sujit, “Incorporating prediction in control barrier function based distributive multi-robot collision avoidance,” in _Proc. of the IEEE European Control Conference (ECC)_ , 2021, pp. 2394–2399.
  * [17] V. Varun, A. P. Vinod, and S. Kolathaya, “Motion planning with dynamic obstacles using convexified control barrier functions,” in _Proc. of the IEEE Indian Control Conference (ICC)_ , 2021, pp. 81–86.
  * [18] Y. Chen, A. Singletary, and A. D. Ames, “Guaranteed obstacle avoidance for multi-robot operations with limited actuation: A control barrier function approach,” _IEEE Control Systems Letters_ , vol. 5, no. 1, pp. 127–132, 2020\.
  * [19] L. Wang, A. D. Ames, and M. Egerstedt, “Safety barrier certificates for collisions-free multirobot systems,” _IEEE Transactions on Robotics_ , vol. 33, no. 3, pp. 661–674, 2017.
  * [20] B. Houska, H. J. Ferreau, and M. Diehl, “Acado toolkit—an open-source framework for automatic control and dynamic optimization,” _Optimal Control Applications and Methods_ , vol. 32, no. 3, pp. 298–312, 2011.
  * [21] W. Hönig, J. A. Preiss, T. S. Kumar, G. S. Sukhatme, and N. Ayanian, “Trajectory planning for quadrotor swarms,” _IEEE Transactions on Robotics_ , vol. 34, no. 4, pp. 856–869, 2018.
  * [22] M. W. Mueller and R. D’Andrea, “A model predictive controller for quadrocopter state interception,” in _Proc. of the IEEE European Control Conference (ECC)_ , 2013, pp. 1383–1389.
  * [23] D. Morgan, G. P. Subramanian, S.-J. Chung, and F. Y. Hadaegh, “Swarm assignment and trajectory optimization using variable-swarm, distributed auction assignment and sequential convex programming,” _The International Journal of Robotics Research_ , vol. 35, no. 10, pp. 1261–1285, 2016\.
  * [24] T. Lipp and S. Boyd, “Variations and extension of the convex–concave procedure,” _Optimization and Engineering_ , vol. 17, no. 2, pp. 263–287, 2016.
  * [25] V. K. Adajania, H. Masnavi, F. Rastgar, K. Kruusamae, and A. K. Singh, “Embedded hardware appropriate fast 3d trajectory optimization for fixed wing aerial vehicles by leveraging hidden convex structures,” in _Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2021, pp. 571–578.
  * [26] G. Taylor, R. Burmeister, Z. Xu, B. Singh, A. Patel, and T. Goldstein, “Training neural networks without gradients: A scalable admm approach,” in _Proc. of the International Conference on Machine Learning (ICML)_ , 2016, pp. 2722–2731.
  * [27] E. Ghadimi, A. Teixeira, I. Shames, and M. Johansson, “Optimal parameter selection for the alternating direction method of multipliers (admm): quadratic problems,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 3, pp. 644–658, 2014.
  * [28] V. K. Adajania, S. Zhou, A. K. Singh, and A. P. Schoellig, “AMSwarm,” https://github.com/utiasDSL/AMSwarm, 2022.
  * [29] D. Mellinger and V. Kumar, “Minimum snap trajectory generation and control for quadrotors,” in _Proc. of the IEEE International Conference on Robotics and Automation (ICRA)_ , 2011, pp. 2520–2525.


* (170) S. Kuroyanagi, T. Chiba and N. Sugiyama, Phys. Rev. D 79, 103501 (2009) [arXiv:0804.3249 [astro-ph]].
  * (171) D. G. Figueroa and E. H. Tanin, JCAP 10, 050 (2019) [arXiv:1811.04093 [astro-ph.CO]].
  * (172) S. Ahmad, A. De Felice, N. Jaman, S. Kuroyanagi and M. Sami, Phys. Rev. D 100,no.10, 103525 (2019) [arXiv:1908.03742 [gr-qc]].


# A Virtual Reality Game to Improve Physical and Cognitive Acuity

Blooma John  Faculty of Science & Technology, University of CanberraFaculty of
Science & TechnologyCanberraACTAustralia<EMAIL_ADDRESS>,
Ramanathan Subramanian  Faculty of Science & Technology, University of
CanberraCanberraACTAustralia<EMAIL_ADDRESS>and  Jayan
Chirayath Kurian  School of Computer Science, University of Technology
SydneyFaculty of Science & TechnologyCanberraACTAustralia
<EMAIL_ADDRESS>
(2023)

###### Abstract.

We present the Virtual Human Benchmark (VHB) game to evaluate and improve
physical and cognitive acuity. VHB simulates in 3D the BATAK lightboard game,
which is designed to improve physical reaction and hand-eye coordination, on
the Oculus Rift and Quest headsets. The game comprises the reaction,
accumulator and sequence modes; along with the reaction and accumulator modes
which mimic BATAK functionalities, the sequence mode involves the user
repeating a sequence of illuminated targets with increasing complexity to
train visual memory and cognitive processing. A first version of the game (VHB
v1) was evaluated against the real-world BATAK by 20 users, and their feedback
was utilized to improve game design and obtain a second version (VHB v2).
Another study to evaluate VHB v2 was conducted with 20 users, whose results
confirmed that the deign improvements enhanced game usability and user
experience in multiple respects. Also, logging and visualization of
performance data such as reaction time, speed between targets and completed
sequence patterns provides useful data for coaches/therapists monitoring
sports/rehabilitation regimens.

Virtual Reality Game; BATAK lightboard; Physical and cognitive acuity; Sports
and rehabilitation

††journalyear: 2023††copyright: acmlicensed††conference: ; December 10–13,
2023; Hyderabad, India††ccs: Human-centered computing††ccs: Human-centered
computing Virtual reality Figure 1. Virtual Human Benchmark (VHB) Game: We
present a virtual simulation of the BATAK lightboard game (left) to benchmark
and improve physical and cognitive performance. The VHB game (middle) is
implemented on the Oculus Rift and Quest devices and offers users a 3D
immersive experience. Users can activate either of the reaction, accumulator
or sequence game modes (right).

##  1\. Introduction

Physical and mental health are both integral to healthy living and ageing, and
a causal-cum-symbiotic relationship has been observed between the two
(Ohrnberger et al., 2016). Motor skills are critical for performing everyday
physical activities such as walking, running, etc., for individuals and
especially for athletes. Memory also represents a key cognitive skill that we
employ on a daily basis for guiding our physical activities, and recalling and
planning events. Brain regions responsible for motor functions and memory are
highly vulnerable to age-related effects (Seidler et al., 2010), and these
skills can be severely impaired by disorders such as dementia, depression and
stroke.

Physical and cognitive activities such as exercise and board games (Altschul
and Deary, 2019) are known to promote healthy ageing and regularly feature in
intervention activities at residential aged-care homes (Parekh et al., 2018).
In this regard, the highly engaging BATAK lightboard game (Wood, 2010) known
to improve hand-eye coordination, reflexes, motor skills, and stamina for
sportspersons and individuals holds promise as a stimulating physical
activity. Recently, video and virtual reality (VR) games (D’Cunha et al.,
2019, 2021) have also been found to be effective in engaging users, and
improving dementia and stroke-related outcomes. Immersivity of VR games can
transform mundane and repetitive exercise routines into competitive and
stimulating experiences, and they can utilized by users to improve physical
and cognitive performance from the comfort of their homes.

This work presents the Virtual Human Benchmark (VHB) VR game, which simulates
the BATAK lightboard in a 3D immersive space. The VHB game works with the
Oculus Rift and Quest headsets, and comprises the reaction, accumulator and
sequence game modes; while the reaction and accumulator modes behave similar
to BATAK functionalities, the sequence mode requires users to repeat a
flashing light sequence thereby testing their visual memory. Overall, the VHB
VR game can be utilized to train and improve one’s physical and cognitive
acuity. Fig. 1 presents snapshots of the BATAK and VHB games, while Fig. 2
presents a user playing the real-word BATAK and VHB versions.

Apart from game-play, the VHB gaming software also logs user performance data
which can be visualized and analyzed via the VHB Insights tool. Logged data
include hand used for button press (left/right), time taken between button
activations, hand distance from button over time, etc.111Exemplar game
animations, user data logs and generated insights can be viewed at
https://virtual-human-benchmark.web.app/. Focus group interviews with health
and sports experts revealed that the VHB game plus analytics can benefit
sports training as well as physical and cognitive rehabilitation of people
recovering from dementia and stroke. To evaluate VHB user experience, we
performed a study where 20 users played both the BATAK and VHB games, and
assessed them with respect to multiple attributes. VHB limitations inferred
from the user study were addressed via improvements in game design, and a
second user study confirmed that these improvements enhanced game usability
and user experience. Overall, we make the following contributions:

  * 1.

We present the Virtual Human Benchmark, a virtual version of the BATAK
lightboard game for training and improving physical and cognitive acuity. The
game can be played from the comfort of the home using off-the-shelf Oculus
Rift and Quest headsets. Also, the lightboard was made configurable to support
users with varied requirements and abilities following recommendations from
experts, who opined that the VHB game would benefit both the sports and health
domains.

  * 2.

The gaming software also logs user performance data to generate analytics and
visualizations conveying various measures. These measures can provide
actionable insights to sports coaches and rehabilitation therapists.

  * 3.

Two user studies were conducted to evaluate VHB usability and user experience.
The first user study compared VHB against the real-world BATAK, and
limitations with the VHB game were addressed via design improvements. The
second study confirmed that design changes enhanced game usability and user
experience.

Figure 2. Snapshots of a user playing the BATAK game left), and the VHB game
on the Oculus Quest headset (right). Best-viewed under color and zoom.
Figure 3. Alternative lightboard configurations to accommodate users with
diverse requirements and abilities.

##  2\. VHB Game Overview

The objective of the Virtual Human Benchmark game is to create a set of
challenges based on the BATAK lightboard game in the 3D VR space to evaluate
physical and cognitive acuity. The game modes are derived from the Human
Benchmark web application (https://humanbenchmark.com/) and the BATAK reaction
test (Wood, 2010). VHB is developed using the Unity game engine, and other
major software packages used include the Jetbrains Rider integrated
development environment, Oculus software development kit (SDK), Universal
Render Pipeline for rendering shadows and textures, and the Windows Mixed
Reality SDK. The game has been successfully tested on the Oculus Rift, Quest 2
and HP Reverb G2 VR headsets, and the minimum hardware specifications for an
optimal development and testing experience, and game launching onto PC
include: Nvidia GTX 970/AMD R9 290 GPU, Intel i5-4590 equivalent CPU, 8GB RAM,
HDMI 1.3 video output, 3x USB 3.0 ports and 1x USB 2.0 port for the base
station to track controller movements, and Windows 7 SP1 64-bit OS.

The VHB BATAK lightboard is shown in Fig. 1(middle), while the menu for game
mode selection via the Oculus touch controllers is shown in Fig. 1(right). The
VHB game comprises the following challenge modes.

  * •

Reaction mode: The VHB lightboard will light all targets at random intervals,
and the user reacts by pressing the controller button as fast as possible.
This process repeats over a stipulated number of trials (typically 5 or 10),
and the reaction time for each trial is recorded. This mode assesses the
user’s ability to process visual information and physical reflexes.

  * •

Accumulator mode: Replicating the real-world BATAK functionality, the VHB
lightboard will light up a single target button at random intervals, following
which the user needs to strike the lit target quickly for another target to
light up. This mode seeks to motivate the user to strike as many targets as
possible during a set time limit of 30/60 seconds, and challenges the user’s
motor agility, hand reach range and dexterity.

  * •

Sequence mode: While the reaction and accumulator modes primarily assess
physical acuity, the sequence mode seeks to examine visual memory and
cognitive processing. In this mode, the VHB lightboard will flash a sequence
of targets one after another, which the user must repeat. The sequence pattern
complexity will increase over trials until the user makes an error or the game
completion following maximum number of trials.

To ensure that the VHB game seamlessly renders on multiple screens, a low-
polygon design is adopted to design the scene model and assets (such as
hands). To further enable the application to render at 75fps or higher frame
rate so that the user feels immersed in a 3D environment, complementary colors
like white, blue and orange are utilized for scene guidance. Blue color is
used to denote non-interactive assets, while interactables such as the game
buttons or mode selection menu are colored orange. An initial screen to inform
and obtain user consent for data collection, is followed by the game selection
menu. Upon selecting the desired game mode, the user will move towards the
BATAK lightboard at the center-stage and press the ‘start’ button to begin
playing. A game manager module manages the game modes, controls how the BATAK
lightboard buttons should behave in each mode, and how user data should be
saved following play. A lightboard manager is also implemented to provide
granular control relating to button activation, track activated buttons, and
record whether the user presses the correct targets (for the accumulator and
sequence modes). An walk-through of the three game modes is provided in the
supplementary video.

Figure 4. User data analytics: User performance logs in the form of achieved
score, buttons pressed and their locations, hand used and distance covered are
stored in a json file (left), to generate visualizations via the insights tool
(middle and right). These visualizations can provide actionable insights to
allied stakeholders for charting training and rehabilitation regimens (best
viewed under zoom).

In terms of the data logged for each user, apart from summary data in the form
of the score achieved and time taken, snapshots relating to each trial are
also recorded (Fig. 4). A reaction snapshot includes reaction time and the
time between successive lightboard flashes (random interval between 5–15s).
The accumulator snapshot records details such as the button position, time
between two button presses, and remaining time, while key entries within a
sequence snapshot include the flashed sequence and sequence length, repeated
sequence pattern, time taken to repeat pattern and time between target
presses. The summary plus snapshot data per user are stored via json files.

Figure 4 illustrates how the user performance data are used to generate
visualizations. Feedback from health experts suggests that these analytics can
provide actionable insights to allied stakeholders like sports
coaches/therapists and clinicians utilizing VHB for training/rehabilitation
purposes. The json accumulator log (Fig. 4(left)) is the input to the VHB
insights tool to generate visualizations shown in Fig. 4(middle) and Fig.
4(right). Fig. 4(middle) presents details like the user score, cumulative hand
displacement (in meters), distribution of left/right hand usage as a pie-
chart, button press sequence and a scatter plot showing remaining game time vs
elapsed time between successive button presses (in seconds). We also utilize
the hand-tracking capability of the Oculus device to output the distance
between the user’s hand and target button over time Fig 4(right). Hand
tracking can be particularly useful for evaluating stroke rehabilitation
outcomes, as stroke patients need repeated training to reach out for objects
and grip them (Dean and Shepherd, 1997).

###  2.1. Expert Feedback

An initial version of the VHB game (VHB v1) was presented to a focus group of
industry and academic experts for their evaluation and feedback. These
included a VR specialist, a neuro-rehabilitation specialist, two sports health
experts, a biomechanist and two researchers developing VR applications for
health and well-being. Their comments are summarized as follows:

  * 1.

Experts conveyed positive impressions, and concurred that the VHB game could
induce positive outcomes in the sports and health domains. Specifically, the
VHB reaction and accumulator modes (and equivalently the BATAK lightboard
game) can improve visual processing and visio-spatial skill which involves
recognizing brightness/darkness, and is crucial for sports training and hand-
eye coordination (Millard et al., 2021). Additionally, the sequence mode
induces cognitive stimulation, which is known to benefit patients with mild-
to-moderate dementia (Woods et al., 2012).

  * 2.

A number of experts preferred to have a game version that supports seated
users, and where the score was computed based on user ability and independent
of time. One expert recommended a game mode where the user had to reach beyond
150% arm’s length. These recommendations were aimed at addressing requirements
of specific demographics such as stroke patients, and training them to improve
their sitting balance and object reaching abilities (Dean and Shepherd, 1997).

  * 3.

One expert also recommended the use of multiple lightboard layouts to support
users with diverse requirements and abilities. All experts advocated the need
for user experience surveys involving both gamers and non-gamers.

In response to these recommendations, the game design was adapted to include
multiple lightboard layouts as shown in Fig. 3. The 3$\times$3 grid and small
circle layouts were designed to support users with limited reach, while the
large circle, four corner and border layouts were intended to support users
requiring training specific to upper limb strengthening and object reaching.
We also proceeded to perform a user study to compare user experience with the
real-world BATAK and the VHB counterpart as detailed below.

##  3\. User Study 1– BATAK vs VHB v1 Comparison

Figure 5. User study results summary: (Top row, left-to-right) Scatter plot
revealing a linear correlation between BATAK vs VHB user performance (Pearson
$r=0.45$). Distribution of 20 user responses conveying which
(physical/virtual) version was more enjoyable and comfortable. (Bottom row,
left-to-right) Bar graphs depicting mean user scores for various game
attributes. Orange lines and *’s denote significant BATAK vs VHB Version-1
score differences as given by a paired student $t$-test. Green lines and *’s
denote significant VHB Version-1 vs Version-2 score differences conveyed by a
two-sample $t$-test (* $\implies p<0.05,***\implies p<0.001$).

###  3.1. Objectives

To compare the VHB game experience against with the real-world BATAK
lightboard, we performed a study with 20 healthy users at Questacon, Canberra.
For a fair and exact comparison, users played the BATAK game and the VHB
accumulator mode back-to-back, and filled a questionnaire soon after. The
specific aims of the study was to examine if (a) user performance was similar
in the physical and virtual game versions (assuming similar levels of comfort
with both), and (b) there were significant differences in user impressions
with respect to game attributes such as engagement, ease of play, ease of
light tracking, simplicity of button press/control (physically vs via the VR
touch controller) and level of focus/distraction during game play in the
physical vs virtual contexts (see Fig. 5(bottom row)).

###  3.2. Apparatus

Eligible visitors, who were aged over 18 and had no physical disabilities,
arriving at the BATAK board exhibit in Questacon were recruited for the study.
Informed consent was obtained from these participants as per ethics approval,
following which they were asked to additionally play the VHB accumulator game
with the default lightboard layout (see Fig. 1) using an Oculus Quest headset.
The BATAK and VHB lightboards identically comprised 12 targets. Figure 2
presents an exemplar user playing the BATAK and VHB games within the same
physical environment. The order of playing the virtual and real games was
counterbalanced across participants. Upon completing both the games, users had
to complete three online questionnaires; two concerning the physical and
virtual game versions, and a third comparing the two. Users needed to provide
both quantitative and qualitative responses in the game-specific
questionnaires. Quantitative responses mainly involved specifying scores on a
1–5 Likert scale for the attributes specified in Section 3.1, while
qualitative responses denoted justifications for these scores. The comparison
form involved selecting one of two alternate choices, plus explanations to
support the selections. Including user preparation time, game play and
questionnaire completion, each user took about 20 minutes to complete the
study.

###  3.3. Participants

20 users (9 female, age range 31.2$\pm$ 13.7, 13 right-handed) took part in
this study. 11 users reported that they frequently played video and VR games.

###  3.4. Results

Fig. 5 presents the user study results. We found a moderate and statistically
significant Pearson correlation between the user BATAK and VHB scores (Fig. 5
(top-left)), implying that the VHB game is ecologically valid, and agile users
generally score well in both versions. Fig. 5 (top-center, top-right) present
a summary of the BATAK vs VHB comparisons, and convey that while users
generally enjoyed playing both versions, the physical BATAK was more
comfortable to play. Fig. 5 (bottom row) summarizes mean user scores
corresponding to multiple attributes of the BATAK and VHB (v1) games. The
orange lines and *s denote significant score differences between the two, as
conveyed by a paired $t$-test. The physical BATAK is perceived as being
significantly better than VHB with respect to engagement, ease of play, button
control and extent of focus (i.e., being less distracting), while the VHB
version was seen to facilitate light tracking much better. The pros and cons
of the physical BATAK were further highlighted by qualitative comments, some
of which are listed below:

  * •

It is easier than it looks, the field of view limits visibility of lit buttons
in the corners of your vision.

  * •

I’m only 152cm tall and the lights at the extremities were harder to reach and
spot via peripheral vision.

  * •

The BATAK lightboard was quite good, however, I found it difficult to see the
peripheral buttons when they lit up.

The above remarks confirm that while the BATAK game play was facile, there
were limitations with respect to its physical design and tracking of lights,
especially those at the corners. Comments on the VHB game included:

  * •

Highly engaging, I found myself immersed to a point that it felt realistic and
enjoyable.

  * •

I found it more difficult to hit the buttons. The game wasn’t as fluid as I
thought it would be.

  * •

Interesting, difficult at first mostly with pressing the virtual buttons.

  * •

The experience was good. The application was well built, and easy to use, the
contrast of a lit button was higher which made identification easier. The
triangular pattern made for a more efficient eye scanning pattern as opposed
to the physical BATAK test.

These impressions convey that (a) the VHB game design was perceived to be
immersive and realistic, and (b) the lightboard structure plus the
illumination contrast made light tracking much easier. However, button
activation via the touch controller was difficult, and considerably
contributed to user frustration and distraction. These observations were
further reinforced along with other issues such as weight of the VR headset in
some comparative remarks listed below:

  * •

I would rate the virtual version higher, as I found myself more immersed and
had a higher quality experience.

  * •

The physical board was more comfortable and easier to use.

  * •

The virtual version was slightly less intuitive.

  * •

Physical- No added weight on the head, the buttons were easier to press and
more responsive.

###  3.5. Discussion of results and subsequent VHB design improvements

Overall, the user study revealed limitations of using VR devices and the VHB
game design in particular. Discomfort with wearing the VR headset can be
addressed via a more ergonomic VR device design and greater VR exposure.
Usability issues with the VHB game were mainly noted with respect to executing
physical movements such as button control; it needs to be noted here that
while the VHB game can be simultaneously projected onto a monitor during game-
play, the fact that the user study was conducted in an exhibit hall precluded
this possibility. In the absence of any visual feedback, experimenters were
only able to provide general guidance to users on executing game actions which
was insufficient, and resulted in user distraction and frustration.

To better guide users to execute physical movements through game play, a
second VHB game version (VHB v2) was developed with the following additional
features:

  * •

Tooltips: Tooltips including a text panel succinctly instructing users on how
to perform physical actions (e.g., activate buttons or walk through the scene)
were added to provide visual feedback.

  * •

Radial View Displays: Adaptive animations that were rendered according to
perspective (head pose) were created to demonstrate the game mode to users.

  * •

3D Audio: 3D spatial audio cues were incorporated to guide user attention to
directions they are not facing. Examples include: helper arrows with a
pulsating sound communicating to the user to select/start a game mode, audio
feedback of button clicks and auditory notifications signifying game starting
and completion.

  * •

Haptic Feedback: In addition to 3D audio, haptic feedback was implemented to
signify the start and finish of a game mode, button activations, incorrect
button presses and attempting to change game mode amidst play. The intensity
and duration of feedback is variable depending on the performed action; e.g.,
incorrect actions trigger more pronounced feedback, whereas haptics
accompanying valid button activations are light and short-lived.

##  4\. User Study 2– VHB v1 vs VHB v2 Comparison

We then proceeded to evaluate user experience with the updated VHB version
(VHB v2) via a second user study.

Objective: The purpose of the study was to examine if user impressions and
experience improved on incorporating visual, audio and haptic guidance
features (Section 3.5) in the VHB game design.

Apparatus: This study was conducted in a university lab, where users played
the VHB (v2) accumulator game using an Oculus Quest headset. They then
completed the questionnaire specific to the virtual version in the first
study. As in the first study, the VR headset was not connected to a display
monitor so that experimenters did not have any visual feedback to guide users;
users were solely guided by visual, audio and haptic game features.

Participants: 20 users (8 male, age range 33.8$\pm$9.1, 18 right-handed), not
part of the first study, were recruited for the second upon providing informed
consent.

Results and Discussion: As users completed identical questionnaires in both
user studies, we compared mean scores corresponding to VHB (v1) and VHB (v2)
for the different game attributes, and the comparisons are depicted in Fig.
5(bottom row). Green lines and *s denote significant inter-version score
differences, as conveyed by a two-sample $t$-test. While scores similar to VHB
(v1) were observed for engagement and ease of light tracking, significantly
higher scores for VHB (v2) were noted for the ease of play, button control and
extent of focus attributes. These results confirm that the incorporated
features considerably enhanced game play, and consequently, user experience.
Some qualitative user comments provided below are also reflective of these
observations.

  * •

I liked the simplicity of the game, it was very clear in what was required
from the player and it was easy to play.

  * •

Seemed well designed and immersive but generally feels more like a test than a
game.

  * •

It was clear and easy to manage, the recognition of hand movements was
precise. The buttons were very low for me as 6ft, I had to bend down.

  * •

The overall experience has been good but would love to have more time in
playing the game.

  * •

Certainly immerses you and with future visual advancement (unreal engine), it
will be life-like and will blur lines between real and virtual.

Going forward, the VHB game design needs to be extended so that all three game
modes involve multiple levels of difficulty, and can engage different
demographics such as sportspersons, dementia and stroke patients to train
tasks repetitively over long time-periods to achieve outcomes superior to
traditional approaches.

##  5\. Conclusion

Expert opinions as well as qualitative and quantitative user opinions
comparing the BATAK game with VHB (v1) revealed that the VHB game (a) can
induce positive outcomes in the sports and health areas, (b) is engaging and
(c) enables easier light tracking as compared to the physical BATAK. However,
usability issues were noted, which hampered overall user experience. These
issues were addressed via the implementation of visual, auditory and haptic
user guidance features to obtain VHB (v2). A second study with an independent
user group revealed that VHB (v2) usability and user experience were
considerably superior to VHB (v1). Future work will involve tailoring the VHB
game design to suit the requirements of specific demographics such as
sportspersons, dementia and stroke patients, and validating with these
communities if the VHB game achieves better user experience and
physical/cognitive outcomes with respect to existing practices.

## References

  * (1)
  * Altschul and Deary (2019) Drew M Altschul and Ian J Deary. 2019.  Playing Analog Games Is Associated With Reduced Declines in Cognitive Function: A 68-Year Longitudinal Cohort Study.  _The Journals of Gerontology: Series B_ 75, 3 (11 2019), 474–482.  https://doi.org/10.1093/geronb/gbz149
  * Dean and Shepherd (1997) Catherine M. Dean and Roberta B. Shepherd. 1997.  Task-Related Training Improves Performance of Seated Reaching Tasks After Stroke.  _Stroke_ 28, 4 (1997), 722–728.  https://doi.org/10.1161/01.STR.28.4.722
  * D’Cunha et al. (2021) Nathan M D’Cunha, Stephen T Isbel, Jane Frost, Angie Fearon, Andrew J McKune, Nenad Naumovski, and Jane Kellett. 2021\.  Effects of a virtual group cycling experience on people living with dementia: A mixed method pilot study.  _Dementia_ 20, 5 (2021), 1518–1535.  https://doi.org/10.1177/1471301220951328
  * D’Cunha et al. (2019) N M D’Cunha, D Nguyen, N Naumovski, A J McKune, J Kellett, E N Georgousopoulou, J Frost, and S Isbel. 2019\.  A Mini-Review of Virtual Reality-Based Interventions to Promote Well-Being for People Living with Dementia and Mild Cognitive Impairment.  _Gerontology_ 65 (2019), 430–440.  Issue 4. https://doi.org/10.1159/000500040
  * Millard et al. (2021) Lourens Millard, Ina Shaw, Gerrit Jan Breukelman, and Brandon S Shaw. 2021.  Visio-spatial skills in athletes: comparison of rugby players and non-athletes.  _Sport Sciences for Health_ 17 (2021), 137–143.  Issue 1. https://doi.org/10.1007/s11332-020-00663-1
  * Ohrnberger et al. (2016) Julius Ohrnberger, Eleonora Fichera, and Matt Sutton. 2016\.  The dynamics of physical and mental health in the older population.  _The Journal of the Economics of Ageing_ 9 (07 2016).  https://doi.org/10.1016/j.jeoa.2016.07.002
  * Parekh et al. (2018) Viral Parekh, Pin Sym Foong, Shengdong Zhao, and Ramanathan Subramanian. 2018.  AVEID: Automatic Video System for Measuring Engagement In Dementia. In _International Conference on Intelligent User Interfaces_ (Tokyo, Japan). 409–413.  https://doi.org/10.1145/3172944.3173010
  * Seidler et al. (2010) Rachael D. Seidler, Jessica A. Bernard, Taritonye B. Burutolu, Brett W. Fling, Mark T. Gordon, Joseph T. Gwin, Youngbin Kwak, and David B. Lipps. 2010.  Motor control and aging: Links to age-related brain structural, functional, and biochemical effects.  _Neuroscience and biobehavioral reviews_ 34, 5 (2010), 721–733.
  * Wood (2010) Robert J Wood. 2010\.  Complete Guide to Fitness Testing.  https://www.topendsports.com/testing/
  * Woods et al. (2012) Bob Woods, Elisa Aguirre, Aimee E Spector, Martin Orrell, and Bob Woods. 2012.  Cognitive stimulation to improve cognitive functioning in people with dementia.  _Cochrane database of systematic reviews_ 2012, 2 (2012), CD005562–CD005562.