#  Assuring Safety of Vision-Based Swarm Formation Control

Chiao Hsieh1, Yubin Koh1, Yangge Li1 and Sayan Mitra1 1The authors are with
Coordinated Science Laboratory, University of Illinois Urbana-Champaign,
Champaign, IL, USA {chsieh16, yubink2, li213<EMAIL_ADDRESS>
###### Abstract

Vision-based formation control systems are attractive because they can use
inexpensive sensors and can work in GPS-denied environments. The safety
assurance for such systems is challenging: the vision component’s accuracy
depends on the environment in complicated ways, these errors propagate through
the system and lead to incorrect control action, and there exists no formal
specification for end-to-end reasoning. We address this problem and propose a
technique for safety assurance of vision-based formation control: First, we
propose a scheme for constructing quantizers that are consistent with vision-
based perception. Next, we show how the convergence analysis of a standard
quantized consensus algorithm can be adapted for the constructed quantizers.
We use the recently defined notion of _perception contracts_ to create error
bounds on the actual vision-based perception pipeline using sampled data from
different ground truth states, environments, and weather conditions.
Specifically, we use a quantizer in logarithmic polar coordinates, and we show
that this quantizer is sutiable for the constructed perception contracts for
the vision-based position estimation, where the error worsens with respect to
the absolute distance between agents. We build our formation control algorithm
with this nonuniform quantizer, and we prove its convergence employing an
existing result for quantized consensus.

##  I Introduction

Distributed consensus, flocking, and formation control have been studied
extensively, including in scenarios where the participating agents only have
partial state information (see, for example [1, 2, 3, 4]). With the advent of
deep learning and powerful computer vision algorithms, it is now feasible for
agents to use vision-based state estimation for formation control (See Figure
1). Such systems can be attractive because they do not require expensive
sensors and localization systems, and also can be used in GPS-denied
environments [5, 6, 7]. However, deep learning and vision algorithms are well-
known to be fragile, which can break the correctness and safety of the end-to-
end formation control system. Further, it is difficult to specify the
correctness of a vision-based state estimator, which gets in the way of
modular design and testing of the overall formation control system [8]. In
this paper, we address these challenges and present the first end-to-end
formal analysis of a vision-based formation control system.

Figure 1: Vision-based drone formation using downward facing camera images in
AirSim.

We present analyses for both convergence and safety assurance of a vision-
based swarm formation control system. The computer vision pipeline (See Figure
2) uses feature detection, feature matching, and geometry to estimate the
relative position of the participating drones. The estimated relative poses
are then used by a consensus-based formation control algorithm. There are two
key challenges in analyzing the system:  (1) The perception errors impact the
behavior of neighboring agents and propagates through the entire swarm.  (2)
The magnitude of the perception error is highly nonuniform, and depends on the
ground truth values of the relative position between neighboring agents.  In
general, perception errors can get worse as the system approaches the
equilibrium (desired formation), and thus, make stabilization difficult.
Environmental variations (e.g., lighting, fog) are other factors that can make
the vision-based system unstable.

In addressing the problem, our idea is to view the vision-based formation
control system as a _quantized consensus protocol_ [9]. We start with the
_assumption_ that the impact of the state estimation errors arising from the
vision pipeline can be encapsulated as quantization errors in a non-uniform
quantization scheme. That is, the quantization step size can vary non-
uniformly with respect to the state so that the quantization errors can
overapproximate state dependent perception errors. To discharge this
assumption, our analysis has to meet two requirements. First, we have to
propose a _specific_ quantization scheme under which the formation control
system is indeed guaranteed convergence. For this, we develop a quantized
formation controller (Equation (1)) and a _logarithmic polar quantizer_
(Equation (2) and (3)), and we show in Theorem 1 that indeed the resulting
quantized formation control protocol converges, using sufficient conditions
from [9]. Secondly, we have to show that a quantizer instantiated from the
quantization scheme matches the error characteristics of the vision pipeline.
For this part, we utilize the recently developed idea of _perception
contracts_ [10, 11]. A perception contract (PC) for a vision-based state
estimator bounds the estimation error as a function of the ground truth state.
Earlier in [11], PCs have been used to establish the safety of vision-based
lane keeping systems. For formation control, however, the PCs are dramatically
different because the error has a highly non-uniform dependency on the state;
as the drones get closer, the error drops. Through data-driven construction of
the logarithmic PC, we show that the vision pipeline indeed matches the PC
with high probability in Section IV, and we further adapt to environmental
variations by inferring quantization step sizes for different environments.

In summary, our contributions are as follows:  (1) An approach to construct a
quantizer as the perception contract of the vision component.  (2)
Empiricalanalysis of the impact of environmental variations on the perception
contract with the photorealistic AirSim simulator [12].  (3) Theoretical
analysis of the overall formation control system using the constructed
quantizer, which gives the bounds on the convergence time. Our code of the
vision pipeline, simulation script, and analysis tool are publicly
available111Repository: https://gitlab.engr.illinois.edu/aap/airsim-vision-
formation.

Figure 2: Architecture of an agent in the vision-based formation control
systems.

#### Related Works

Two parallel threads of research have recently addressed formal end-to-end
analysis of vision-based autonomous systems. The works in [13, 14, 15]
approach the problem using discrete state space and stochastic models. Our
previous work [10, 11] develops the idea of perception contracts using the
language of continuous state space models. Thus far all the applications
studies in these threads are related to lane following by a single agent,
which is quite different from distributed formation control.

VerifAI [16] uses techniques like fuzz testing and simulation to falsify the
system specifications. Katz et al. [17] trains generative adversarial networks
(GANs) to produce a network to simplify the image-based NN. NNLander-VeriF
[18] verifies NN perception along with NN controllers for an autonomous
landing system. In contrast, our current work aims to provide safety analyses
for a formation control system with vision-based perception, and we apply the
analysis on convergence to quantized consensus [9] for safe separation and
formation.

#### Paper Organization

In Section II, we introduce the formation control system with the vision-based
perception and review the quantized formation controller. In Section III, we
show the convergence under perception error using our main theory of quantized
consensus. In Section IV, we describe the quantization for perception error
bounds via sampling from vision-based pose estimation with AirSim simulation.
We then conclude in Section V.

##  II Vision-Based Formation Control

We will study a distributed formation control system with $N+1$ identical
aerial vehicles or _agents_ with a leader agent 0 as shown in Figure 1. The
target formation is specified in terms of relative positions between agents.
Each agent $i$ has a downward facing camera, and it uses images from its own
camera and its predecessor $i-1$’s camera to periodically estimate the
relative position of $i$ with respect to $i-1$. Based on the estimated
relative positions to its neighbor, agent $i$ then updates it own position by
setting a velocity, to try and achieve the target formation.

Before describing the vision and control modules in more detail, we introduce
some notations. First, we describe the neighborhood relation between agents by
an undirected connected graph $G=(V,E)$, where $V=\\{0,1,\dotsc,N\\}$. Second,
we only consider planar formations for simplicity though the agents are in
3-dimensional space. Thus, the position of agent $i$ in the world frame is
represented by a vector ${q}_{i}\in\mathbb{R}^{2}$. The state of the overall
system is a sequence $\mathrm{q}=({q}_{0},{q}_{1},\dotsc,{q}_{N})$. The
distributed formation control system evolves with a goal of reaching a target
formation in a set $\mathrm{E}_{\mathrm{q}^{*}}$ that is specified by a vector
$\mathrm{q}^{*}=({q}_{0}^{*},{q}_{1}^{*},\dotsc,{q}_{N}^{*})$ as

$\mathrm{E}_{\mathrm{q}^{*}}=\\{\mathrm{q}\mid\forall
i\in\\{1,\dotsc,N\\},{q}_{i}-{q}_{i-1}={q}_{i}^{*}-{q}_{i-1}^{*}\\}.$

That is, $\mathrm{E}_{\mathrm{q}^{*}}$ is the set of all states that form
$\mathrm{q}^{*}$ up to translations. We also specify a safe set that the where
the distance between no two agents is too close or too far:

$\mathrm{S}_{\mathrm{q}}=\\{\mathrm{q}\mid\forall
i\in\\{1,\dotsc,N\\},d_{\min}<\lVert{q}_{i}-{q}_{i-1}\rVert<d_{\max}\\}$

where $0<d_{\min}<d_{\max}$ defines the range of safe distances.

###  II-A Vision-Based Relative Pose Estimation

Figure 3: Feature matching on an image pair from AirSim.

We now discuss the components of an agent $i$ (Figure 2). Agent $i$’s
downward-facing camera $\mathit{s}$ periodically generates an image of the
ground ${m}_{i}$, which depends on its state ${q}_{i}$ and other environmental
factors like background scenery, lighting, fog, etc. The neighboring agent
$i-1$ generates another image ${m}_{i-1}$ of the ground and shares this with
agent $i$ over the communication channel. We assume the whole system runs
synchronously in lock-step, i.e., both neighboring drones will capture the
image at the same time and there’s no communication delay between drones while
sharing images. The vision-based pose estimation algorithm $\mathit{h}$ takes
a pair of images, ${m}_{i-1}$ and ${m}_{i}$, as an input and produces the
_estimated relative position_ $\hat{y}_{i}$ to estimate the relative position
of agent $i$ with respect to agent $i-1$, i.e., ${q}_{i}-{q}_{i-1}$. The
estimation algorithm in general follows these steps: (1) First, $\mathit{h}$
detects features from each image. Any of the various feature detection
algorithms like SIFT [19], SURF [20], and ORB [21] can be used for this step.
(2) Then, $\mathit{h}$ collects the detected features from the pair of images,
and a feature matching algorithm (such as FLANN [22]) is used to match pairs
of features in each image as shown in Figure 3. (3) For each feature point,
the relationship between the pixel coordinate and the world coordinate of the
feature point [23] is described by $s[u\ v\ 1]^{T}=K[R\mid{t}][X\ Y\ Z\
1]^{T}$ where $[u\ v\ 1]^{T}$ is the pixel coordinate, $[X\ Y\ Z\ 1]^{T}$ is
the world coordinate of each detected feature, $K$ is the camera intrinsic
matrix and $[R\mid{t}]$ is the extrinsic camera parameters. With a set of at
least 8 matched features, we can come up with 8 pairs of equations between the
poses of two cameras, and by solving these equations, we can calculate the
relative rotation and the normalized translation vector using the inverse
geometry of image formation. Examples of this step appear in [24, 25, 26].
Further, the altitude information and drone orientation can be used to
estimate the true distance to ground and recover the length of the translation
vector.

The accuracy of the perception pipeline can be influenced by many factors. The
change of environments such as background, lighting, and weather influence the
quality of the image and the image features, which in turn influence the
accuracy of relative pose estimation.

###  II-B Formation Control in Relative Positions

To simplify the notations, let $Y$ denote the vector space of the _relative
positions_ between pairs of drones. Let $y_{i}\in Y$ be defined as
$y_{i}={q}_{i}-{q}_{i-1}$, for $i=1,\dotsc,N$. A state is a sequence of
relative positions $\mathrm{y}=(y_{1},y_{2},\dotsc,y_{N})$. Let $y_{i}^{*}\in
Y$ be the desired relative vector between drone $i-1$ and $i$, i.e.,
$y_{i}^{*}={q}_{i}^{*}-{q}_{i-1}^{*}$. The target equilibrium state is defined
by:

$\mathrm{y}^{*}=(y_{1}^{*},\dotsc,y_{N}^{*}),$

and the safe set is

$\mathrm{S}_{\mathrm{y}}:=\\{\mathrm{y}\mid\forall
i\in\\{1,\dotsc,N\\},d_{\min}<\lVert y_{i}\rVert<d_{\max}\\}.$

The following proposition relating the $\mathrm{y}$-system with the original
$\mathrm{q}$-system follows immediately.

######  Proposition 1.

The formation control system ($\mathrm{q}$-system) reaches a desired state in
$\mathrm{E}_{\mathrm{q}^{*}}$ if and only if the system in relative positions
($\mathrm{y}$-system) reaches the target $\mathrm{y}^{*}$. In addition, the
formation control system ($\mathrm{q}$-system) stays within the safe set
$\mathrm{S}_{\mathrm{q}}$ if and only if the system in relative positions
($\mathrm{y}$-system) stays within the safe set $\mathrm{S}_{\mathrm{y}}$.

###  II-C Quantized Formation and Perception Contract

Given the system in relative positions with the state at time $t$ represented
by $\mathrm{y}[t]=(y_{1}[t],\dotsc,y_{N}[t])$, we aim to handle perception
errors by designing a _quantizer_ $Q$ and a quantized formation controller
built on top of $Q$. The insight is as follows: If the ground-truth $y_{i}[t]$
and the perceived relative position $\hat{y}_{i}[t]$ always lead to the same
quantized value after quantization, i.e., $Q(y_{i}[t])=Q(\hat{y}_{i}[t])$,
then any quantized formation controller using $Q(\hat{y}_{i}[t])$ instead of
$Q(y_{i}[t])$ will still stabilize the system regardless of perception errors.

More precisely, we follow the definitions in [27] and choose a subset of
positions $W=\\{w_{1},w_{2},\dotsc\\}\subset Y$ selected for quantization. A
_quantizer_ is a function $Q:Y\to W$ which partitions $Y$ into _quantization
regions_ of the form $\\{y\in W\mid Q(y)=w_{k}\\}$ for each $w_{k}\in W$.
Given a target state $\mathrm{y}^{*}=(y_{1}^{*},\dotsc,y_{N}^{*})$ with all
$y_{i}^{*}\in W$, a _quantized formation controller_ ensures that the system
is evolving between states with all $y_{i}[t]\in W$ for all time $t$, and
stabilizes the system to the target $\mathrm{y}^{*}$. The _perception
contract_ (_PC_) then requires that the perceived value is always in the
quantization region defined by the ground-truth quantized value, that is,
$\hat{y}_{i}[t]\in\\{y\mid Q(y)=y_{i}[t]\\}$ or equivalently
$Q(\hat{y}_{i}[t])=Q(y_{i}[t])$.

In this paper, we study a particular template of quantized formation
controllers constructed using a quantizer, a difference function, and a
weighted average function. We assume a generalized difference function
$\mathit{diff}$ to calculate the difference between two relative positions and
a function $\mathit{mean_{\omega}}$ to compute a weighted midpoint
parametrized by a real value $\frac{1}{2}<\omega<\frac{3}{4}$. The system
evolves according to a (nondeterministic) discrete dynamical system with a
pair $(i,j)$ selected randomly at each time step $t$, and the quantized
formation controller updates the pair of states as follows:

$\displaystyle y_{i}[t+1]$
$\displaystyle=Q(\mathit{mean_{\omega}}(Q(y_{i}[t]),\mathit{diff}(Q(y_{j}[t]),\mathit{diff}(y_{j}^{*},y_{i}^{*}))))$
(1) $\displaystyle y_{j}[t+1]$
$\displaystyle=Q(\mathit{mean_{\omega}}(Q(y_{j}[t]),\mathit{diff}(Q(y_{i}[t]),\mathit{diff}(y_{i}^{*},y_{j}^{*}))))$

Note that, by design, the updated states are always quantized values given any
$\mathit{diff}$ and $\mathit{mean_{\omega}}$, and they are unaffected by
perception errors whenever the perception contract holds.

This template allows us to design a quantized formation controller with
vision-based perception in two separate steps:  (1) find sufficient conditions
for the quantizer that ensures the convergence and safety of the quantized
formation controller and  (2) construct the quantizer from observed perception
errors to serve as the perception contract.  In Section III, we derive the
sufficient conditions for the safety and convergence of the quantized
formation. We prove that, given a _quantizer_ over _logarithmic polar_ (log-
polar) coordinates, the system in Equation (1) safely converges to the target
state, and the expected value for the time of convergence is bounded. In
Section IV, we study the empirically observed perception error, and we explain
how to design a quantizer to approximate the perception error.

##  III Convergence of Quantized Formation

In this section, we prove that the true relative positions between agents,
with a quantizer on log-polar coordinates modeling the perception error,
converges to the target formation and stays within the safe distance bounds.
This is done by proving that the system in Equation (1) is simulated by a
_quantized averaging_ algorithm in [9], which is proven to always converge to
quantized consensus and stay within a bounded interval. In addition, the
expected convergence time of the algorithm is bounded. We first provide the
quantizer in Section III-A. We then prove the simulation relation between
formation control systems and quantized averaging algorithms in Section III-B,
and the bound on the convergence time in Section III-C.

###  III-A Quantization on Logarithmic Polar Coordinates

We first define the set of selected positions $W$ in polar coordinates.
Without loss of generality, we choose a quantization _step radius_ $a>1$ and
define the set of quantized radii $R=\\{a^{0},a^{\pm 1},a^{\pm 2},\dotsc\\}$
and a _step angle_ $\theta_{b}=\frac{2\pi}{M}$ to define the set of quantized
angles $\Theta=\\{0,\theta_{b},\dotsc,(M-1)\cdot\theta_{b}\\}$ with an integer
$M\geq 2$; then we define the set of selected points $W$ by $W=R\times\Theta$.
Equivalently, given two positions in polar coordinates
$y_{i}=[r_{i}\,\theta_{i}]^{T}$ and $y_{j}=[r_{j}\,\theta_{j}]^{T}$ with
angles normalized to $[0,2\pi)$, we define the quantizer and other functions
for the radial coordinate as below:

$\begin{gathered}I(r_{i})=\left\lfloor\log_{a}r_{i}\right\rceil;\quad
Q(r_{i})=a^{I(r_{i})};\\\
\mathit{diff}(r_{i},r_{j})=\frac{r_{i}}{r_{j}};\quad\mathit{mean_{\omega}}(r_{i},r_{j})=r_{i}^{(1-\omega)}\cdot
r_{j}^{\omega}\end{gathered}$ (2)

where $\left\lfloor\cdot\right\rceil$ rounds the real number to the nearest
integer. The functions for the angular coordinate are as below:

$\begin{gathered}I(\theta_{i})\equiv_{M}\left\lfloor\frac{\theta_{i}}{\theta_{b}}\right\rceil;\quad
Q(\theta_{i})=I(\theta_{i})\cdot\theta_{b};\\\
\mathit{diff}(\theta_{i},\theta_{j})=\theta_{i}\oplus-\theta_{j};\\\
\mathit{mean_{\omega}}(\theta_{i},\theta_{j})=\theta_{i}\oplus(\omega\cdot(\theta_{j}\oplus-\theta_{i}))\end{gathered}$
(3)

where $\equiv_{M}$ means congruent modulo $M$, $\oplus$ is the addition in the
commutative group $SO(2)$, and $-\theta_{i}$ represents the additive inverse
of $\theta_{i}$. The $\mathit{mean_{\omega}}$ function calculates the weighted
geometric mean of rotations [28].

###  III-B Simulation by Quantized Averaging Algorithms

Following [9], let $\mathrm{z}[t]=(z_{1}[t],\dotsc,z_{N}[t])$ denote the state
in the integer domain at each time step. An instance of quantized averaging
algorithms evolves as Equation (4) below:

$\displaystyle z_{i}[t+1]$
$\displaystyle=z_{i}[t]+\left\lfloor\omega\cdot(-z_{i}[t]+z_{j}[t])\right\rceil$
(4) $\displaystyle z_{j}[t+1]$
$\displaystyle=z_{j}[t]+\left\lfloor\omega\cdot(z_{i}[t]-z_{j}[t])\right\rceil$

The following proposition is directly from [9, Section 5].

######  Proposition 2.

The system in Equation (4) always converges to the set of equilibria:

$\xi=\\{(z_{1},\dotsc,z_{N})\mid z_{i}\in\\{L,L+1\\},i\in\\{1\dotsc
N\\}\sum\limits_{i=1}^{N}z_{i}=S\\}$ where $S=\sum_{i=1}^{N}z_{i}[0]$ is the
initial sum of the system and $L=\lfloor\frac{S}{N}\rfloor$ is the quantized
average.

We now prove the convergence of the formation control system using Proposition
2.

######  Theorem 1.

For any initial state $\mathrm{y}[0]\in\mathrm{Y}_{0}$ where

$\mathrm{Y}_{0}=\left\\{(\begin{bmatrix}r_{1}\\\
\theta_{1}\end{bmatrix},\dotsc,\begin{bmatrix}r_{N}\\\
\theta_{N}\end{bmatrix})\right|\left.\prod\limits_{i}Q(r_{i})=\prod\limits_{i}r_{i}^{*}\land\bigoplus\limits_{i}Q(\theta_{i})=\bigoplus\limits_{i}\theta_{i}^{*}\right\\},$

the formation control system in Equation (1) converges to the target
$\mathrm{y}^{*}=(y_{1}^{*},\dotsc,y_{N}^{*})$ with $y_{i}^{*}\in W$ for all
$i$.

###### Proof.

The proof is to show that the formation control system in Equation (1) is
simulated by the quantized averaging system in Equation (4) for every time
step, and thus we guarantee the convergence using Proposition 2. Recall in
Section III-A that the quantizer $Q$ has a corresponding indexing function
$I$. Let $y_{i}[t]=[r_{i}[t]\,\theta_{i}[t]]^{T}$ and
$y_{i}^{*}=[r_{i}^{*}\,\theta_{i}^{*}]^{T}$, we denote $z_{i}[t]_{r}$ for the
radial coordinate and $z_{i}[t]_{\theta}$ for the angular coordinate, and we
relate the two systems by $z_{i}[t]_{r}=I(r_{i}[t])-I(r_{i}^{*})$ and
$z_{i}[t]_{\theta}=I(\theta_{i}[t])-I(\theta_{i}^{*})$ for all $i$.

We first derive for the radial coordinates. Given the relation
$z_{i}[t]=I(y_{i}[t])-I(y_{i}^{*})$ for all $i$, we apply the indexing
function $I$ on the new state $r_{i}[t+1]$ to calculate $z_{i}[t+1]_{r}$.

$\displaystyle I(r_{i}[t+1])$
$\displaystyle=I(Q(\mathit{mean_{\omega}}(Q(r_{i}[t]),\mathit{diff}(Q(r_{j}[t]),\mathit{diff}(r_{j}^{*},r_{i}^{*})))))$
$\displaystyle=$
$\displaystyle\log_{a}a^{\wedge}\left\lfloor\log_{a}\left(Q(r_{i}[t])^{(1-\omega)}\cdot(\frac{Q(r_{j}[t])\cdot
r_{i}^{*}}{r_{j}^{*}})^{\omega}\right)\right\rceil$ $\displaystyle=$
$\displaystyle\lfloor(1-\omega)\cdot(\log_{a}Q(r_{i}[t]))$ $\displaystyle\
+\omega\cdot(\log_{a}Q(r_{j}[t])-\log_{a}r_{j}^{*}+\log_{a}r_{i}^{*})\rceil$
$\displaystyle\because r_{i}^{*},r_{j}^{*}\text{ are quantized values.}$
$\displaystyle=$ $\displaystyle\lfloor(1-\omega)\cdot I(r_{i}[t])\
+\omega\cdot(I(r_{j}[t])-I(r_{j}^{*})+I(r_{i}^{*}))\rceil$ $\displaystyle=$
$\displaystyle\
I(r_{i}[t])+\lfloor-\omega\cdot(I(r_{i}[t])-I(r_{i}^{*}))+\omega\cdot(I(r_{j}[t])-I(r_{j}^{*}))\rceil$

We now calculate $z_{i}[t+1]_{r}$ as follows:

$\displaystyle z_{i}[t+1]_{r}$ $\displaystyle=I(r_{i}[t+1])-I(r_{i}^{*})$
$\displaystyle=I(r_{i}[t])-I(r_{i}^{*})$
$\displaystyle\quad+\lfloor-\omega\cdot(I(r_{i}[t])-I(r_{i}^{*}))+\omega\cdot(I(r_{j}[t])-I(r_{j}^{*}))\rceil$
$\displaystyle=z_{i}[t]_{r}+\left\lfloor\omega\cdot(-z_{i}[t]_{r}+z_{j}[t]_{r})\right\rceil$

This is exactly the same as the quantized averaging algorithm in Equation (4).
Therefore, we have shown that the indices of the quantized radial coordinates
evolve according to the quantized averaging algorithm.

Similarly, we derive for the angular coordinate. Recall the definitions in
Equation (3). Given two quantized angles $\theta_{i}=Q(\theta_{i})$ and
$\theta_{j}=Q(\theta_{j})$, we can distribute the indexing function over the
addition and inverse as follows:

$\displaystyle
I(\theta_{i}\oplus\theta_{j})\equiv_{M}\left\lfloor\frac{(I(\theta_{i})+I(\theta_{j}))\cdot\theta_{b}}{\theta_{b}}\right\rceil\equiv_{M}I(\theta_{i})+I(\theta_{j})$
$\displaystyle
I(-\theta_{i})\equiv_{M}I(-Q(\theta_{i}))\equiv_{M}\left\lfloor\frac{-I(\theta_{i})\cdot\theta_{b}}{\theta_{b}}\right\rceil\equiv_{M}-I(\theta_{i})$

Additionally, when $\theta_{i}=Q(\theta_{i})$, we can derive for
$\frac{1}{2}<\omega<\frac{3}{4}$:

$I(\omega\cdot\theta_{i})\equiv_{M}\left\lfloor\frac{\omega\cdot
I(\theta_{i})\cdot\theta_{b}}{\theta_{b}}\right\rceil\equiv_{M}\left\lfloor\omega\cdot
I(\theta_{i})\right\rceil$

We now calculate the index of the new state $\theta_{i}[t+1]$.

$\displaystyle I(\theta_{i}[t+1])=\ $ $\displaystyle
I(Q(\mathit{mean_{\omega}}(Q(\theta_{i}[t]),\mathit{diff}(Q(\theta_{j}[t]),\mathit{diff}(\theta_{j}^{*},\theta_{i}^{*})))))$
$\displaystyle\equiv_{M}\ $ $\displaystyle
I(Q(\theta_{i}[t])\oplus(\omega\cdot(Q(\theta_{j}[t])\oplus-\theta_{j}^{*}\oplus\theta_{i}^{*}\oplus-Q(\theta_{i}[t]))))$
$\displaystyle\equiv_{M}\ $ $\displaystyle
I(\theta_{i}[t])+I(\omega\cdot(-Q(\theta_{i}[t])\oplus\theta_{i}^{*}\oplus
Q(\theta_{j}[t])\oplus-\theta_{j}^{*})))$ $\displaystyle\equiv_{M}\ $
$\displaystyle
I(\theta_{i}[t])+\left\lfloor\omega\cdot(-I(\theta_{i}[t])+I(\theta_{i}^{*})+I(\theta_{j}[t])-I(\theta_{j}^{*}))\right\rceil$

Then, we calculate $z_{i}[t+1]_{\theta}$:

$\displaystyle z_{i}[t+1]_{\theta}=\ $ $\displaystyle
I(\theta_{i}[t+1])-I(\theta_{i}^{*})$ $\displaystyle\equiv_{M}\ $
$\displaystyle I(\theta_{i}[t])-I(\theta_{i}^{*})$
$\displaystyle+\left\lfloor\omega\cdot(-I(\theta_{i}[t])+I(\theta_{i}^{*})+I(\theta_{j}[t])-I(\theta_{j}^{*}))\right\rceil$
$\displaystyle\equiv_{M}\ $ $\displaystyle
z_{i}[t]_{\theta}+\left\lfloor\omega\cdot(-z_{i}[t]_{\theta}+z_{j}[t]_{\theta})\right\rceil$

Again, the index of the angular coordinate evolves exactly following the
quantized averaging algorithm in Equation (4). The derivation for $z_{j}[t+1]$
is the same and skipped.

Furthermore, for any initial state $\mathrm{y}[0]\in\mathrm{Y}_{0}$, we can
derive the initial sum of the quantized averaging system as follows:

$\displaystyle\prod_{i}Q(r_{i}[0])=\prod_{i}r_{i}^{*}\ \land\
\bigoplus_{i}Q(\theta_{i}[0])=\bigoplus_{i}\theta_{i}^{*}$
$\displaystyle\Rightarrow$
$\displaystyle\prod_{i}\frac{Q(r_{i}[0])}{r_{i}^{*}}=1\ \land\
\bigoplus\limits_{i}(Q(\theta_{i}[0])\oplus-\theta_{i}^{*})=0$
$\displaystyle\Rightarrow$
$\displaystyle\sum_{i}\log_{a}Q(r_{i}[0])-\log_{a}r_{i}^{*}=0\ \land\
\sum_{i}\frac{Q(\theta_{i}[0])}{\theta_{b}}-\frac{\theta_{i}^{*}}{\theta_{b}}=0$
$\displaystyle\Rightarrow$ $\displaystyle\sum_{i}I(r_{i}[0])-I(r_{i}^{*})=0\
\land\ \sum_{i}I(\theta_{i}[0])-I(\theta_{i}^{*})=0$
$\displaystyle\Rightarrow$ $\displaystyle\sum_{i}z_{i}[0]_{r}=0\ \land\
\sum_{i}z_{i}[0]_{\theta}=0$

As a result, the initial sum $S$ in the z-system is 0, the quantized average
$L$ is always 0, and according to Proposition 2 the z-system converges to the
only equilibrium where all $z_{i}=L=0$. Therefore, $y_{i}$ converges to
$y_{i}^{*}$ for all $i\in\\{1,\dotsc,N\\}$. Thus, our formation control system
converges to $\mathrm{y}^{*}$. ∎

We further provide the initial condition such that the system will remain in
the safe set.

######  Theorem 2.

Given a target state in the safe set
$\mathrm{y}^{*}\in\mathrm{S}_{\mathrm{y}}$, if the system starts in an initial
state $\mathrm{y}[0]\in(\mathrm{Y}_{0}\cap\mathrm{S}_{0})$ where

$\mathrm{S}_{0}=\left\\{(\begin{bmatrix}r_{1}\\\
\theta_{1}\end{bmatrix},\dotsc,\begin{bmatrix}r_{N}\\\
\theta_{N}\end{bmatrix})\right|\left.\bigwedge_{i=1}^{N}\frac{Q(d_{\min})}{\min\limits_{j}\\{r_{j}^{*}\\}}<\frac{Q(r_{i})}{r_{i}^{*}}<\frac{Q(d_{\max})}{\max\limits_{j}\\{r_{j}^{*}\\}}\right\\},$

then the system will always stay in the safe set, i.e.,
$d_{\min}<r_{i}[t]<d_{\max}$ for all time $t$.

###### Proof.

Here we show the proof steps for the minimum safe distance $d_{\min}$. We
first derive the lower bound for $z_{i}[0]_{r}$ from the initial condition
$\mathrm{y}[0]\in(\mathrm{Y}_{0}\cap\mathrm{S}_{0})$.

$\displaystyle\frac{Q(d_{\min})}{\min\limits_{j}\\{r_{j}^{*}\\}}<\frac{Q(r_{i}[0])}{r_{i}^{*}}$
$\displaystyle\Rightarrow\ $
$\displaystyle\left\lfloor\log_{a}d_{\min}\right\rceil-\min\limits_{j}\\{\log_{a}r_{j}^{*}\\}<\left\lfloor\log_{a}r_{i}[0]\right\rceil-\log_{a}r_{i}^{*}$
$\displaystyle\Rightarrow\ $ $\displaystyle
I(d_{\min})-\min\limits_{j}\\{I(r_{j}^{*})\\}<I(r_{i}[0])-I(r_{i}^{*})=z_{i}[0]_{r}$

Then, from [9, Theorem 2], we know $z_{i}[t]_{r}$ is bounded by the minimum
initial value, i.e., $\min_{j}\\{z_{j}[0]_{r}\\}\leq z_{i}[t]_{r}$ for all
time $t$. We use it to derive the lower bound on $r_{i}[t]$ for all time $t$
as follows.

$\displaystyle
I(d_{\min})-\min\limits_{j}\\{I(r_{j}^{*})\\}<\min_{j}\\{z_{j}[0]_{r}\\}\leq
z_{i}[t]_{r}$ $\displaystyle\Rightarrow$ $\displaystyle
I(d_{\min})-\min\limits_{j}\\{I(r_{j}^{*})\\}<I(r_{i}[t])-I(r_{i}^{*})$
$\displaystyle\Rightarrow$ $\displaystyle
I(d_{\min})+(I(r_{i}^{*})-\min\limits_{j}\\{I(r_{j}^{*})\\})<I(r_{i}[t])$
$\displaystyle\Rightarrow$ $\displaystyle
I(d_{\min})<I(r_{i}[t])\qquad\because
I(r_{i}^{*})\geq\min\limits_{j}\\{I(r_{j}^{*})\\}$ $\displaystyle\Rightarrow$
$\displaystyle Q(d_{\min})<Q(r_{i}[t])\Rightarrow d_{\min}<r_{i}[t]$

We skip the dual proof for the upper bound $r_{i}[t]<d_{\max}$. ∎

######  Remark 1.

Theorem 2 suggests that we should carefully design the closest and farthest
distances, $\min_{j}r_{j}^{*}$ and $\max_{j}r_{j}^{*}$, in the target state
because they constrain the set of safe initial states. For example, when the
distance in the target state $r_{j}^{*}$ is close to the minimum safe
distances $d_{\min}$, then the bound becomes tighter, and hence fewer initial
states can ensure safety. In addition, $Q$ cannot be too coarse, that is, the
value of the step radius $a$ should not be too large. It should ensure
$\frac{Q(d_{\min})}{\min_{j}\\{r_{j}^{*}\\}}<\frac{Q(d_{\max})}{\max\limits_{j}\\{r_{j}^{*}\\}}$.
Otherwise, $\mathrm{S}_{0}$ becomes an empty set, and no initial states can
ensure safety.

###  III-C Bound on Expected Convergence Time

Now, we analyze the upper bound on the convergence time. We first provide the
existing result on the convergence time of quantized consensus algorithms.
Then, we derive the upper bound for the formation control system.

Following [9], the probability distribution of the convergence time is defined
as
$T_{con}(\mathrm{z})=\inf\\{t\mid\mathrm{z}[t]\in\xi,\mathrm{z}[0]=\mathrm{z}\\}$.
Since our z-system evolves by a quantized gossip algorithm over _linear
networks_ , the upper bound on the expected convergence time is provided in
[9, Lemma 7] as:

$\max_{\mathrm{z}\in\mathrm{Z}_{0}}\mathbb{E}[T_{\mathit{con}}(\mathrm{z})]\leq\frac{(z_{\max}-z_{\min})^{2}}{8}\cdot\frac{N(N^{2}-1)(N-1)}{4}$
(5)

where $z_{\min}$ and $z_{\max}$ are parameters specifying the minimum and
maximum integer values among all possible states, and
$\mathrm{Z}_{0}=\\{(z_{1},\dotsc,z_{N})\mid z_{\min}\leq z_{i}\leq
z_{\max}\\}$ includes all possible initial states. With the upper bound in
Equation (5), we derive the bound on the expected convergence time of our
formation control system.

######  Theorem 3.

The formation control system in Equation (1) converges with the following
upper bound on the expected convergence time:

$\max_{\mathrm{y}\in(\mathrm{Y_{0}}\cap\mathrm{S}_{0})}\mathbb{E}[T_{\mathit{con}}(\mathrm{y})]\leq\frac{\Delta^{2}}{8}\cdot\frac{N(N^{2}-1)(N-1)}{4}$

where $\Delta=\max(I(d_{\max})-I(d_{\min}),M-1)$, $\mathrm{Y_{0}}$ is the same
in Theorem 1, and $\mathrm{S}_{0}$ is the same in Theorem 2.

###### Proof.

The proof is to apply Equation 5 and select $\Delta$ to be the larger upper
bound among the bounds on $z_{\max}-z_{\min}$ for the radial and angular
coordinates in the integer domain. For the radial coordinate, we derive a
lower bound for $z_{\min}=\min_{i}\\{I(r_{i})-I(r_{i}^{*})\\}$ from
$\mathrm{y}\in\mathrm{S}_{0}$ as follows:

$\displaystyle\bigwedge_{i=1}^{N}\frac{Q(d_{\min})}{\min\limits_{j}\\{r_{j}^{*}\\}}<\frac{Q(r_{i})}{r_{i}^{*}}\
\Rightarrow\
\frac{Q(d_{\min})}{\min\limits_{j}\\{r_{j}^{*}\\}}<\min_{i}\\{\frac{Q(r_{i})}{r_{i}^{*}}\\}$
$\displaystyle\Rightarrow\ $ $\displaystyle
I(d_{\min})-\min\limits_{j}\\{I(r_{j}^{*})\\}<\min_{i}\\{I(r_{i})-I(r_{i}^{*})\\}=z_{\min}$

Dually, we find the bound $z_{\max}<I(d_{\max})-\max_{j}\\{I(r_{j}^{*})\\}$.
Using the fact that
$\max_{j}\\{I(r_{j}^{*})\\}\geq\min_{j}\\{I(r_{j}^{*})\\}$, this leads to
$z_{\max}-z_{\min}<I(d_{\max})-I(d_{\min})$.

For the angular coordinate, the value of $I(\theta_{i})-I(\theta_{i}^{*})$ is
bounded by 0 and $M-1$ because of the modulo operator, hence the upper bound
on $z_{\max}-z_{\min}$ is $M-1$. ∎

##  IV Quantization as Perception Contracts

For vision-based perception, uniform worst case bounds on the perception error
between the ground truth and the perceived value can be overly conservative
for system-level analysis. Recent research has shown that state-dependent
error models can strike a balance between the conservatism of the safety
analysis and the precision of characterizing deep learning-based perception
systems [10].

Following the same insight, we investigate the relationship between the ground
truth and the perceived relative positions, and we study how to search for the
parameter values for the quantizer according to the empirically observed
perception errors. We randomly sampled pairs of camera images from two drones
under different relative positions in AirSim. We fixed drone $i-1$ as the
origin and uniformly sampled 10,000 positions of drone $i$ within a radius
between 2 m to 20 m in the AirSimNH environment from AirSim. For each sample,
we obtained a pair of true relative position $y_{i}$ from AirSim and perceived
relative position $\hat{y}_{i}$ via vision-based pose estimation pipeline (of
Section II-A).

(a) Radii on a linear scale.

(b) Radii on a log scale.

(c) Angles in $[0,2\pi)$.

(d) Angles in $[0,2\pi)$ and angle errors in $[-\pi,\pi)$.

Figure 4: Perceived relative positions
$\hat{y}_{i}=[\hat{r}_{i}\,\hat{\theta}_{i}]^{T}$ with respect to true
relative position $y_{i}=[r_{i}\,\theta_{i}]^{T}$. Sampled data are blue dots.
The perceived value with no error is the black line. The empirical bounds are
plotted as red lines such that 99% (90%) of dots fall within the solid lines
(the dashed lines).

Figure 4 plots the perceived position
$\hat{y}_{i}=[\hat{r}_{i}\,\hat{\theta}_{i}]^{T}$ with respect to the true
position $y_{i}=[r_{i}\,\theta_{i}]^{T}$. In Figure 4(a), we observe that the
perceived distances $\hat{r}_{i}$ scatter wider when the true distance $r_{i}$
increases. Secondly, much more perceived distances deviate greatly from the
true distance when the true distance crosses a certain threshold, e.g., about
15 meters in Figure 4(a). This is not too surprising: As the two drones become
farther apart, the overlap of the two camera views is smaller and causes fewer
matched features than eight pairs, which leads to inaccuracy in relative pose
estimation.

Our ultimate goal is to design a quantizer whose quantization error
overapproximates the perception error of the vision component, and we
empirically approximate the perception error from collected samples. Recall in
Section II-C, the PC enforced by the quantizer $Q$ is
$Q(\hat{y}_{i})=Q(y_{i})$. We further simplify the PC as
$Q(\hat{y}_{i})=y_{i}$ because $y_{i}$ is a quantized value. We start by
expanding the definitions in Equation 2 for the radial coordinates. The PC can
be rewritten as the following:

$\displaystyle Q(\hat{r}_{i})=r_{i}\Leftrightarrow
a^{\left\lfloor\log_{a}\hat{r}_{i}\right\rceil}=r_{i}\Leftrightarrow\left\lfloor\log_{a}\hat{r}_{i}\right\rceil=\log_{a}r_{i}$
$\displaystyle\Leftrightarrow\ $
$\displaystyle\log_{a}r_{i}-0.5\leq\log_{a}\hat{r}_{i}<\log_{a}r_{i}+0.5$
$\displaystyle\Leftrightarrow\ $ $\displaystyle\log r_{i}-0.5\cdot\log
a\leq\log\hat{r}_{i}<\log r_{i}+0.5\cdot\log a$

This says that the PC defines a pair of _linear bounds_ around the ground
truth on a log scale. We can decrease or increase the value of $a$ to make the
PC more strict or relaxed. Ideally, the PC should hold for all observed data,
but this can lead to an overly relaxed PC that the quantizer $Q$ cannot ensure
safety (See Remark 1). In practice, we may preprocess the data to remove
outliers. For example, the pair of red solid lines in Figure 4(b) depicts the
bounds inferred from ignoring the worst 1% of perceived values and therefore
covering 99% of data, and the pair of red dashed lines depicts the bounds
covering 90% of data. We also plot the bounds transformed back to the linear
scale in Figure 4(a). Similarly, selecting larger or smaller $\theta_{b}$
defines more strict or relaxed _constant bounds_ for the angular coordinates.
It is worth noting that, due to the normalization, angles are wrapped around 0
and $2\pi$ as shown in Figure 4(c). Therefore, we follow the standard approach
to normalize the angle error $\hat{\theta_{i}}-\theta_{i}$ to $[-\pi,\pi)$ and
infer the bounds as shown in Figure 4(d).

Figure 5: Matched feature points found by the feature detection and matching
algorithm under three AirSim environments and four fog levels.  Figure 6:
Perceived distances $\hat{r}_{i}$ and empirical linear bounds with respect to
true distances $r_{i}$ under five fog levels.

The perception contract also depends on environmental factors. To
systematically study the impact of environmental variations on the perception
contract, we experimented with different environments and weather conditions
in the photorealistic AirSim simulator. Figure 5 shows how the feature
matching step degrades across three environments (namely LandscapeMountains,
AirSimNH, and ZhangJiajie) and four fog levels. Note that at the fog level
0.050, only one pair of matching features is detected for the same relative
position under LandscapeMountains.

Figure 7: Inferred step radius $a$ on a log scale covering 99% and 90% of data
with respect to five fog levels.

Figure 6 shows the perception contracts for five fog levels under AirSimNH.
The perception bound increases much faster (against the relative distance) in
a foggier weather. To better visualize this trend, we further plot the
inferred step radius $a$ for covering 99% and 90% of data points under varying
fog levels in Figure 7. Note that the y-axis is on a log scale in Figure 7, so
both values in fact increase faster than exponential growth with respect to
the fog levels, and the step radius for covering 99% data increases more
significantly. Unsurprisingly, when it is too foggy, the value of $a$ is too
large to satisfy the condition for Theorem 2 to ensure safety.

##  V Limitations and Discussions

We presented an analysis for the convergence and safety of a vision-based
formation control system. To tackle the vagaries of the perception component,
our approach uses a perception contract represented as a quantizer. This
quantizer captures the worst perception error in relative position estimates
from the vision component, which is then used to prove that the drones are
safely separated and converges to the desired formation. Especially, we
designed non-uniform quantizers to model the _state-dependent perception
error_. We empirically showed that a quantizer in log-polar coordinates models
the observed perception error more accurately using the high-fidelity
simulator, AirSim. We also systematically studied the impact of environmental
variations on the perception contract. We inferred quantization step sizes
according to data sampled under each environment so that the instantiated
quantizer better models the observed error under the environment.

Our study assumed that all drones run synchronously and exchange image feature
descriptors instantly. This is obviously an idealization. Our analysis will
work without this assumption by bounding the change in relative positions
under a fixed communication delay. We can model the change in relative
positions as part of the perception error.

Finally, this paper suggests a broad research direction on connecting
quantized control and discrete abstractions over the continuous state space
[29]. Both quantization and discrete abstractions are partitioning the state
space, but they are different in that operators for quantized values such as
difference, averaging, maximum, and minimum are not necessarily available for
discrete abstractions. Relating discrete abstractions with quantization will
allow us to reuse the theories in quantized control for formal safety
analyses.

## References

  * [1] V. Blondel, J. Hendrickx, A. Olshevsky, and J. Tsitsiklis, “Convergence in multiagent coordination consensus and flocking,” in _Proc. Joint 44th IEEE Conf. Decision and Control and Eur. Control Conf._ , 2005, pp. 2996–3000.
  * [2] R. Saber and R. Murray, “Flocking with obstacle avoidance: cooperation with limited communication in mobile networks,” in _Proc. 42nd IEEE Int. Conf. Decision and Control_ , vol. 2, 2003, pp. 2022–2028.
  * [3] M. Mesbahi and M. Egerstedt, _Graph Theoretic Methods in Multiagent Networks_. Princeton, NJ, USA: Princeton University Press, 2010.
  * [4] F. Bullo, J. Cortés, and S. Martínez, _Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms_. Princeton, NJ, USA: Princeton University Press, 2009.
  * [5] E. Montijano, E. Cristofalo, D. Zhou, M. Schwager, and C. Sagüés, “Vision-Based Distributed Formation Control Without an External Positioning System,” _IEEE Trans. Robot._ , vol. 32, no. 2, pp. 339–351, 2016.
  * [6] K. Fathian, “Distributed Formation Control of Autonomous Vehicles via Vision-Based Motion Estimation,” Ph.D. dissertation, Dept. Elect. Eng., Univ. Texas at Dallas, Richardson, TX, USA, 2018.
  * [7] M. M. H. Fallah, F. Janabi-Sharifi, S. Sajjadi, and M. Mehrandezh, “A Visual Predictive Control Framework for Robust and Constrained Multi-Agent Formation Control,” _J. Intell. Robot. Syst._ , vol. 105, no. 4, 2022.
  * [8] M. Abraham, A. Mayne, T. Perez, I. R. De Oliveira, H. Yu, C. Hsieh, Y. Li, D. Sun, and S. Mitra, “Industry-track: Challenges in rebooting autonomy with deep learned perception,” in _Proc. 2022 Int. Conf. Embedded Softw._ , 2022, pp. 17–20.
  * [9] A. Kashyap, T. Başar, and R. Srikant, “Quantized consensus,” _Automatica_ , vol. 43, no. 7, pp. 1192–1203, 2007.
  * [10] C. Hsieh, Y. Li, D. Sun, K. Joshi, S. Misailovic, and S. Mitra, “Verifying Controllers With Vision-Based Perception Using Safe Approximate Abstractions,” _IEEE Trans. Comput.-Aided Design Integr. Circuits Syst._ , vol. 41, no. 11, pp. 4205–4216, 2022.
  * [11] A. Astorga, C. Hsieh, P. Madhusudan, and S. Mitra, “Perception Contracts for Safety of ML-Enabled Systems,” _Proc. ACM on Programming Languages_ , vol. 7, no. OOPSLA2, pp. 299:1–299:27, 2023.
  * [12] S. Shah, D. Dey, C. Lovett, and A. Kapoor, “AirSim: High-Fidelity Visual and Physical Simulation for Autonomous Vehicles,” in _Proc. 11th Int. Conf. Field and Service Robot._ , 2018, pp. 621–635.
  * [13] C. S. Păsăreanu, R. Mangal, D. Gopinath, S. Getir Yaman, C. Imrie, R. Calinescu, and H. Yu, “Closed-loop analysis of vision-based autonomous systems: A case study,” in _Proc. 35th Int. Conf. Comput. Aided Verification_ , 2023, pp. 289–303.
  * [14] R. Calinescu, C. Imrie, R. Mangal, G. N. Rodrigues, C. Păsăreanu, M. A. Santana, and G. Vázquez, “Discrete-event controller synthesis for autonomous systems with deep-learning perception components,” arXiv:2202.03360, 2023.
  * [15] C. Păsăreanu, R. Mangal, D. Gopinath, and H. Yu, “Assumption Generation for the Verification of Learning-Enabled Autonomous Systems,” arXiv:2305.18372, 2023\.
  * [16] T. Dreossi, D. J. Fremont, S. Ghosh, E. Kim, H. Ravanbakhsh, M. Vazquez-Chanlatte, and S. A. Seshia, “VerifAI: A Toolkit for the Formal Design and Analysis of Artificial Intelligence-Based Systems,” in _Proc. 31st Int. Conf. Comput. Aided Verification_ , 2019, pp. 432–442.
  * [17] S. M. Katz, A. L. Corso, C. A. Strong, and M. J. Kochenderfer, “Verification of image-based neural network controllers using generative models,” _J. Aerosp. Inf. Syst._ , vol. 19, no. 9, pp. 574–584, 2022.
  * [18] U. Santa Cruz and Y. Shoukry, “NNLander-VeriF: A Neural Network Formal Verification Framework for Vision-Based Autonomous Aircraft Landing,” in _Proc. 14th Int. Symp. NASA Formal Methods_ , 2022, pp. 213–230.
  * [19] D. G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” _Int. J. Comput. Vision_ , vol. 60, no. 2, pp. 91–110, 2004.
  * [20] H. Bay, T. Tuytelaars, and L. Van Gool, “SURF: Speeded Up Robust Features,” in _Proc. 9th Eur. Conf. Comput. Vision_ , 2006, pp. 404–417.
  * [21] E. Rublee, V. Rabaud, K. Konolige, and G. Bradski, “ORB: An efficient alternative to SIFT or SURF,” in _Proc. 2011 Int. Conf. Comput. Vision_ , 2011, pp. 2564–2571.
  * [22] M. Muja and D. G. Lowe, “Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration,” in _Proc. 4th Int. Conf. Comput. Vision Theory Appl._ , 2009, pp. 331–340.
  * [23] Y. Ma, S. Soatto, J. Kosecka, and S. S. Sastry, _An Invitation to 3-D Vision: From Images to Geometric Models_ , 1st ed., ser. Interdisciplinary Applied Mathematics. SpringerVerlag, 2003.
  * [24] E. Malis and M. Vargas, “Deeper understanding of the homography decomposition for vision-based control,” INRIA, Research Report RR-6303, 2007. [Online]. Available: https://hal.inria.fr/inria-00174036
  * [25] D. Nister, “An efficient solution to the five-point relative pose problem,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 26, no. 6, pp. 756–770, 2004\.
  * [26] H. Li and R. Hartley, “Five-Point Motion Estimation Made Easy,” in _18th Int. Conf. Pattern Recognit._ , vol. 1, 2006, pp. 630–633.
  * [27] D. Liberzon, “Hybrid feedback stabilization of systems with quantized signals,” _Automatica_ , vol. 39, no. 9, pp. 1543–1554, 2003.
  * [28] M. Moakher, “Means and Averaging in the Group of Rotations,” _SIAM J. Matrix Anal. Appl._ , vol. 24, no. 1, pp. 1–16, 2002.
  * [29] R. Alur, T. Henzinger, G. Lafferriere, and G. Pappas, “Discrete Abstractions of Hybrid Systems,” _Proc. IEEE_ , vol. 88, no. 7, pp. 971–984, 2000.


11institutetext:  IBM Research – Zurich 22institutetext: ETH Zürich
22email<EMAIL_ADDRESS>
# Towards Learning Abductive Reasoning
using VSA Distributed Representations

Giacomo Camposampiero 1122 Michael Hersche 11 Aleksandar Terzić 1122
Roger Wattenhofer 22 Abu Sebastian 11 Abbas Rahimi 11

###### Abstract

We introduce the Abductive Rule Learner with Context-awareness (ARLC), a model
that solves abstract reasoning tasks based on Learn-VRF. ARLC features a novel
and more broadly applicable training objective for abductive reasoning,
resulting in better interpretability and higher accuracy when solving Raven’s
progressive matrices (RPM). ARLC allows both programming domain knowledge and
learning the rules underlying a data distribution. We evaluate ARLC on the
I-RAVEN dataset, showcasing state-of-the-art accuracy across both in-
distribution and out-of-distribution (unseen attribute-rule pairs) tests. ARLC
surpasses neuro-symbolic and connectionist baselines, including large language
models, despite having orders of magnitude fewer parameters. We show ARLC’s
robustness to post-programming training by incrementally learning from
examples on top of programmed knowledge, which only improves its performance
and does not result in catastrophic forgetting of the programmed solution. We
validate ARLC’s seamless transfer learning from a 2x2 RPM constellation to
unseen constellations. Our code is available at
https://github.com/IBM/abductive-rule-learner-with-context-awareness.

##  1 Introduction

††footnotetext: 18th Conference on Neural-Symbolic Learning and Reasoning
(NeSy 2024).

Abstract reasoning can be defined as the ability to induce rules or patterns
from a limited source of experience and generalize their application to
similar but unseen situations. It is widely acknowledged as a hallmark of
human intelligence, and great efforts have been poured into the challenge of
endowing artificial intelligence (AI) models with such capability.

As a result, a wide range of benchmarks to assess human-like fluid
intelligence and abstract reasoning in AI models has been proposed in the past
decade [1, 2, 3, 4]. In this work, we focus on Raven’s progressive matrices
(RPM) test [1, 5, 6]. RPM is a visual task that involves perceiving pattern
continuation and elemental abstraction as well as deducing relations based on
a restricted set of underlying rules, in a process that mirrors the attributes
of advanced human intelligence [7, 8]. Recently, RPM has become a widely used
benchmark for effectively testing AI capabilities in abstract reasoning,
making analogies, and dealing with out-of-distribution (OOD) data [9, 10, 11,
12, 13].

With the advent of large language models, it was suggested that the attainment
of abstract reasoning abilities required to solve this kind of task may hinge
upon the scale of the model. To support this claim, it was shown that
adequately large pre-trained language models can exhibit emergent abilities
for logical [14] and analogical [15, 16] reasoning. Nevertheless, the internal
mechanisms underlying the emergence of these abilities are still not well
understood. In addition, recent works provided evidence on the acute
brittleness of these abilities [17, 18], while others showed that language
models fail to attain levels of general abstract reasoning comparable to
humans [19, 20, 21, 22].

An alternative and promising direction is neuro-symbolic AI. Neuro-symbolic
approaches combine sub-symbolic perception with various forms of symbolic
reasoning, resulting in cutting-edge performance across a spectrum of domains,
including visual [23, 24, 25, 26], natural language [27], causal [28],
mathematical [29], and analogical [30, 31, 32, 33, 34] reasoning tasks. In the
context of RPM, recent neuro-symbolic architectures focused on abductive
reasoning [33, 34]. Abductive reasoning allows to selectively infer
propositions based on prior knowledge represented in a symbolic form to
explain the perceptual observations in the best possible way [35]. The appeal
of the abductive approach lies in its accommodation of perceptual
uncertainties within symbolic reasoning. Abductive reasoning can be
implemented in systems that leverage distributed vector-symbolic architectures
(VSAs) [36, 37, 38] representations and operators, such as the Neuro-Vector
Symbolic Architecture (NVSA) [34]. However, these neuro-symbolic architectures
[33, 34] necessitate complete knowledge over the application domain (which
might not be available) to program the right inductive bias into the model.

Learn-VRF [39] overcomes this limitation by introducing a probabilistic
abduction reasoning approach that learns a subset of the rules underlying RPM
from data. Learn-VRF transparently operates in the rule space, learning them
through a soft-assignment of VSA attribute representations to a fixed rule
template. During inference, it generates the answer panel by executing all the
learned rules and applying a soft-selection mechanism to their outputs.
Nevertheless, Learn-VRF comes with several limitations, including a sub-
optimal selection mechanism, poor performance on the RPM constellations
involving multiple objects, and a constraint on the expressiveness of the RPM
rules it can learn.

To make progress towards learning-to-reason, we propose the Abductive Rule
Learner with Context-awareness (ARLC) to tackle the main limitations of Learn-
VRF [39]. We advance a novel context-augmented formulation of the optimization
problem and a more expressive rule template, which allow sharing rules with
the same parameters in both execution and selection steps and offer better
interpretability. An overview of ARLC is depicted in Figure 1. ARLC features
programmability and can further learn from data on top of programmed
knowledge. We evaluate ARLC on in-distribution (ID) and out-of-distribution
(OOD) tests of the I-RAVEN dataset, and demonstrate that ARLC significantly
outperforms neuro-symbolic and connectionist baselines, including large
language models. Further, the number of trainable parameters is reduced by two
orders of magnitude compared to Learn-VRF. We experimentally validate the
programmability of ARLC by encoding domain knowledge, and discover that post-
programming training, contrary to other studies [40], does not compromise the
validity of the solution, but rather improves it. Finally, training the model
on a single constellation and evaluating it on all the others, we show that,
unlike previous baselines [39, 34], the learned rules can seamlessly
transferred across constellations of the I-RAVEN dataset.

Figure 1: Proposed ARLC architecture. a) Overview of the end-to-end inference
pipeline. b) Detailed rule computation block, exploded from (a), which
highlights the difference between the two steps of the rule computation: rule
selection and rule execution. We also illustrate the proposed context-
augmentation abstraction (that translates VSA vectors into different sets
$X_{R_{i}}$ and $O_{R_{i}}$ depending on the row ${R_{i}}$), and the parameter
sharing between rules ($r_{1},\dots,r_{R}$) across the selection and execution
steps (rule blocks with the same color share the same parameters $\mathbf{w}$,
$\mathbf{u}$, $\mathbf{v}$).

##  2 Background

###  2.1 Vector Symbolic Architectures

Vector-symbolic architectures (VSAs) [36, 37, 38] are a family of
computational models that rely on the mathematical properties of high-
dimensional vector spaces. VSAs make use of high-dimensional distributed
representations for structured (symbolic) representation of data while
maintaining the advantages of connectionist distributed vector representations
(see [41] for a survey). Here is a formal definition of VSAs:

######  Definition 1 (VSA)

A vector-symbolic architecture (VSA) consists of a 4-tuple
$\mathbb{V}=(\mathbb{C},\oplus,\otimes,\odot)$, where $\mathbb{C}$ is a set of
high-dimensional distributed vectors equipped with two main operations,
$\oplus$ (bundling) and $\otimes$ (binding), and on which it is possible to
define a similarity measure $\odot$.

Bundling is a similarity-preserving operation that creates a superposition of
the operands, that is, the resulting vector will have a high similarity with
the two operands. Binding, on the other hand, is an operation that allows to
bind a vector (value) to another vector (key) and does not preserve
similarities; it usually allows an inverse operation, called unbinding. The
specific realization of the bundling, binding, and vector space constitute the
main difference between members of the VSA family.

###  2.2 Raven’s Progressive Matrices

In this work, we focus on the I-RAVEN dataset [10], a benchmark that provides
RPM tests sampled from unbiased candidate sets to avoid short-cut solutions
that were possible in the original RAVEN dataset [13]. Each RPM test is an
analogy problem presented as a $3\times 3$ pictorial matrix of context panels.
Every panel in the matrix is filled with several geometric objects based on a
certain rule, except the bottom-right panel, which is left blank. Figure 1
includes an I-RAVEN example test. The task is to complete the missing panel by
picking the correct answer from a set of (eight) candidate answer panels that
matches the implicit generation rule on every attribute. The object’s
attributes (color, size, shape, number, position) are governed by individual
underlying rules:

  * •

constant, the attribute value does not change per row;

  * •

arithmetic, the attribute value of the third panel corresponds to either the
sum or the difference of the first two panels of the row;

  * •

progression, the attribute value monotonically increases or decreases in a row
by 1 or 2;

  * •

distribute three, the set of the three different values remains constant
across rows, but the individual attribute values get shifted to the left or to
the right by one position at every row; it also holds column-wise.

Each panel contains a variable number of objects (minimum one, maximum nine)
arranged according to one of seven different constellations (center,
distribute-four, distribute-nine, left-right, up-down, in-out-center, and in-
out-four).

###  2.3 Learning to Reason with Distributed Representations

In this section, we discuss how vector-symbolic architectures can be used to
solve tasks which require analogical and relational reasoning such as RPM. In
particular, we focus on Learn-VRF [39], a simple yet powerful approach that
enables to solve RPM tests by learning the underlying relations between visual
attributes in the VSA representational space.

The key observation behind this approach is that the formulation of every RPM
rule in the VSA algebra is a particular instance of a general rule template,
which is shared among all the rules and consists of a series of binding and
unbinding operations between VSA vectors. Hence, the problem of learning RPM
rules can be framed as an assignment problem between vectors representing
visual attributes and terms in this general rule template. This alternative
formulation allows to tackle one of the main limitations of neuro-symbolic
approaches, differentiability, and therefore enables the use with data-driven
learning algorithms based on gradient optimization.

Learn-VRF includes several sequential steps, ranging from the translation of
visual attributes into the VSA high-dimensional space to the computation of
final results, that are detailed in the following paragraphs.

####  2.3.1 From Visual Attributes to VSA.

Following the same procedure of previous works which assume a perfect
perception [42, 43], the panel’s attribute labels are provided directly by the
I-RAVEN metadata. For every attribute $a$, each panel’s label is translated to
a probability mass function (PMF) $\mathbf{p}_{a}^{(i,j)}$, where $i$ is the
row index and $j$ is the column index of the panel. The panel’s PMF is then
projected into the VSA space as

$\displaystyle\mathbf{v}_{a}^{(i,j)}=\sum_{k=1}^{N}\mathbf{p}_{a}^{(i,j)}\left[k\right]\cdot\mathbf{b}\left[k\right],$

where $N$ is the number of possible values that the attribute $a$ can assume.

The VSA vectors are drawn from a dictionary of binary generalized sparse block
codes (GSBCs) [44] $\mathbb{C}=\\{\mathbf{b}_{i}\\}_{i=1}^{512}$. In binary
GSBCs, the $D$-dimensional vectors are divided into $B$ blocks of equal
length, $L=D/B$, where only one (randomly selected) element per block is set
to 1 ($D=1024$ and $B=4$).

The algebraic operations on binary GSBCs are defined in Table 1. Combining
GSBCs with fractional power encoding (FPE) [45] allows the representation of
continuous attributes (e.g., color or size) and simple algebraic operations,
as addition and subtractions, in the corresponding vector space. In other
words, the FPE initialization allows to establish a semantic equivalence
between high-dimensional vectors and real numbers. This property is
consistently exploited in the framework, as it allows to solve the analogies
in the puzzles as simple algebraic operations in the domain of real numbers.
Finally, we observe that the binding operation for binary GSBCs has properties
analogous to addition in the real number domain, including commutativity,
associativity, and the existence of a neutral element
($\mathbf{e}\in\mathbb{C}$, s.t. $\mathbf{a}\circledast\mathbf{e}=\mathbf{a}$
$\forall\mathbf{a}\in\mathbb{C}$ ).

Table 1: Supported VSA operations and their equivalent in $\mathbb{R}$. Operation |  Binary GSBCs |  Equivalent in $\mathbb{R}$
---|---|---
Binding ($\otimes$) |  Block-wise circular convolution ($\circledast$) |  Addition $+$
Unbinding ($\oslash$) |  Block-wise circular correlation ($\circledcirc$) |  Subtraction $-$
Bundling ($\oplus$) |  Sum & normalization |  —
Similarity ($\odot$) |  Cosine similarity ($\text{cos}(\cdot,\cdot)$) |  —

####  2.3.2 Learning RPM Rules as an Assignment Problem.

The core idea introduced in Learn-VRF is that the rules used in RPM can be
framed in a fixed template which encompasses a series of binding and unbinding
operations,

$\displaystyle
r=\left(\mathbf{c}_{1}\circledast\mathbf{c}_{2}\circledast\mathbf{c}_{3}\right)\circledcirc\left(\mathbf{c}_{4}\circledast\mathbf{c}_{5}\circledast\mathbf{c}_{6}\right),$
(1)

where $\mathbf{c}_{i}$ represents a context panel $\mathbf{v}_{a}^{(i,j)}$ or
the identity $\mathbf{e}$. In this setting, learning the rules of RPM can
hence be interpreted as an assignment problem between VSA vectors and terms of
Equation 1. To make it differentiable, Learn-VRF frames every term
$\mathbf{c}_{i}$ as a convex combination over the VSA vectors of the context
panels’ attributes, augmented with the neutral element

$\displaystyle\mathbf{c}_{k}=\sum_{\text{panels
}(i,j)}w_{k}^{(i,j)}\cdot\mathbf{v}_{a}^{(i,j)}+v_{k}\cdot\mathbf{e},$ (2)

where the following constraints apply to the weights

$\displaystyle\sum_{\text{panels }(i,j)}w_{k}^{(i,j)}+v_{k}=1,\quad\quad 0\leq
w_{k}^{(i,j)}\leq 1\,\forall i,j,\quad\quad 0\leq v_{k}\leq 1,\,\forall k.$

####  2.3.3 Executing and Selecting the Learned Rules.

Inference with the learned rule set is a two-steps process: an execution step
(where all the rules are applied in parallel to the input) and a selection
step (where a prediction for the missing panel is generated). The application
of each rule $r$ to an RPM example generates a tuple of three VSA vectors
$(\hat{\mathbf{v}}_{a,r}^{(i,3)})^{3}_{i=1}$, which corresponds to the result
of the rule execution on the three rows of the RPM matrix, together with a
rule confidence value $s_{r}$. The confidence value is computed as the sum of
the cosine similarities between the predicted VSA vectors and their respective
ground-truth vector,

$\displaystyle{s}_{r}=\sum_{i=1}^{3}\mathrm{cos}\left(\mathbf{v}_{a}^{(i,3)},\hat{\mathbf{v}}_{a,r}^{(i,3)}\right).$
(3)

During inference, the last term of the sum ($i=3$) is omitted, as the ground-
truth for the third row is unknown.

The answer is finally produced by taking a linear combination of the VSA
vectors generated by executing all the rules, weighted by their respective
confidence scores (normalized to a valid probability distribution using a
softmax function). More formally, if we define
$\mathbf{s}=\left[s_{1},\dots,s_{R}\right]$ to be the concatenation of all
rules’ confidence score and
$\hat{\mathbf{V}}_{a}^{(3,3)}=[\hat{\mathbf{v}}_{a,1}^{(3,3)},\dots,\hat{\mathbf{v}}_{a,R}^{(3,3)}]$
to be the concatenation of all rules’ predictions for the missing panel, the
final VSA vector predicted by the model for the attribute $a$ becomes

$\displaystyle\hat{\mathbf{v}}_{a}^{(3,3)}=\text{softmax}\left(\mathbf{s}\right)\cdot\hat{\mathbf{V}}_{a}^{(3,3)}.$
(4)

The use of the weighted combination can be understood as a soft selection
mechanism between rules, and was found to be more effective compared to the
hard selection mechanism provided by sampling [39].

##  3 Methods

In this section, we present our Abductive Rule Learner with Context-awareness
(ARLC) system. An overview of ARLC is depicted in Figure 1. The framework
aligns with the original Learn-VRF at a conceptual level, albeit with key
adjustments that allow to improve its expressiveness and boost its downstream
performance on the I-RAVEN dataset.

###  3.1 Learning Context-Augmented RPM Rules

The soft-assignment problem presented in Equation 2 is designed to assign each
term $\mathbf{c}_{i}$ in Equation 1 with a fixed, absolute position in the
$3\times 3$ RPM matrix. For instance, the rule for arithmetic subtraction
could be learned with one-hot assignment weights as
$\hat{\mathbf{v}}_{a}^{(3,3)}=\mathbf{v}_{a}^{3,1}\circledcirc\mathbf{v}_{a}^{3,2}$.
A major limitation of this approach is that _the rules cannot be shared across
rows of the RPM matrix_. For example, the aforementioned arithmetic
subtraction rule is valid only for the third row, but not for the first and
second rows.

To overcome this limitation, Learn-VRF instantiates and learns three different
rule sets (one per row) simultaneously. During inference, the model leverages
the first two sets to produce confidence values (Equation 3), which are then
used to perform a soft-selection of the output panels produced by the third
rule set (Equation 4). While it was empirically shown to be effective, this
implementation leaves the door open to different criticalities. For instance,
the model has no constraint on the functional equivalence between the three
learned rule sets. This renders the interpretability of the model sensibly
harder and increases the likelihood of learning spurious correlations in the
rule selection mechanism. Furthermore, this formulation diminishes the model’s
versatility, as its design, tailored to the RPM context, cannot seamlessly
transfer to other abstract reasoning tasks without a reconfiguration of its
primary components.

Motivated by these issues and by related works in cognitive sciences and
psychology that argue for the importance of context in the solution of
analogies for humans [46, 47] we propose a more general formulation of the
soft-assignment problem which abstracts away the positional assignment and
instead relies on the notion of context. We propose to rewrite Equation 2 as

$\displaystyle\mathbf{c}_{k}=\sum_{i=1}^{I}w_{k}^{i}\cdot\mathbf{x}_{i}\cdot+\sum_{j=1}^{J}u_{k}^{j}\cdot\mathbf{o}_{j}+v_{k}\cdot\mathbf{e}.$
(5)

Here, $\mathbf{X}=\\{\mathbf{x}_{1},\dots,\mathbf{x}_{I}\\}$ is the set of
attributes that define the current sample, that is, the description of the
problem for which we infer a solution.
$\mathbf{O}=\\{\mathbf{o}_{1},\dots,\mathbf{o}_{J}\\}$ is the set of
attributes that define the context for that sample, that could be interpreted
as a working memory from which additional information to infer the answer can
be retrieved. In Equation 5, $\mathbf{w},\mathbf{u},\mathbf{v}$ are the
learned parameters and, as in Equation 2, they are subject to the following
constraints:

$\displaystyle\sum_{i=0}^{I}w_{k}^{i}+\sum_{j=0}^{J}w_{k}^{j}+v_{k}=1,\quad\quad
0\leq w_{k}^{i}\leq 1\,\forall i,\quad\quad 0\leq u_{k}^{j}\leq 1\,\forall
j,\quad\quad 0\leq v_{k}\leq 1,\,\forall k.$

Note that the notion of the current sample $X$ and its context $O$ depends on
the row chosen for inference, as shown in Figure 2.

The new formulation does not lose expressiveness compared to Equation 2. While
its terms are no longer tied to fixed positions in the RPM matrix, relative
position information can still be preserved by keeping the order of the
current and context samples consistent during training. Both row-wise and
column-wise relations can be correctly represented by the model.

Most importantly, the new context-aware formulation for the soft-selection
allows to have a single set of rules shared across all the rows of the RPM.
Contrary to Learn-VRF, the model can now enforce functional equivalence
between the rules used for selection and execution by construction.
Additionally, the number of trainable parameters is reduced by $66\%$ compared
to Learn-VRF.

In RPM, the number of current and context examples is equal to $I=2$ and
$J=5$, respectively. We do not consider $J=6$ context examples to ensure that
the same rules can be shared across rows. Otherwise, the model would fail when
used to predict $R_{1}$ and $R_{2}$, since the panel in position $(3,3)$ is
unknown.

(a) $X=\\{R_{1}\\},O=\\{R_{2},R_{3}\\}$

(b) $X=\\{R_{2}\\},O=\\{R_{1},R_{3}\\}$

(c) $X=\\{R_{3}\\},O=\\{R_{1},R_{2}\\}$

Figure 2: Visualization of current samples ($X=\\{x_{1},x_{2}\\}$, in yellow)
and context ($O=\\{o_{1},\dots,o_{5}\\}$, in green) panels when predicting the
third panel for different rows, namely the first row (left), second row
(center) and third row (right). Black objects represent panels which are not
used for the computation, while the question mark represents the unknown test
panel, which is unavailable during inference.

###  3.2 Improving Rule Selection through Template Generalization

Compared to Learn-VRF, we increase the number of terms in the general rule
template (Equation 1) as

$\displaystyle
r=\left(\mathbf{c}_{1}\circledast\mathbf{c}_{2}\circledast\mathbf{c}_{3}\circledast\mathbf{c}_{4}\circledast\mathbf{c}_{5}\circledast\mathbf{c}_{6}\right)\circledcirc\left(\mathbf{c}_{7}\circledast\mathbf{c}_{8}\circledast\mathbf{c}_{9}\circledast\mathbf{c}_{10}\circledast\mathbf{c}_{11}\circledast\mathbf{c}_{12}\right).$
(6)

Increasing the representational power of the rule template opens up the
possibility to learn more general—yet functionally equivalent— formulations of
the RPM rules, by also including “validation” terms in their structure,
necessary in specific edge cases of the I-RAVEN dataset, such as Example 1.
This bridges the gap between Learn-VRF, which could learn a set of rules that
are perfect for execution but sub-optimal for selection, and other neuro-
symbolic approaches [34, 33], which hard-coded an optimal rule set for
selection and an optimal rule set for execution. We define the optimality of a
rule set as follows.

######  Definition 2 (Rule Set Optimality)

Consider a rule set $\mathcal{R}=\\{r_{i}\\}_{i=1}^{R}$ and an arbitrary RPM
test $\mathbf{V}_{a}=(\mathbf{v}_{a}^{(1,1)},\dots,\mathbf{v}_{a}^{(3,2)})$.
$\mathcal{R}$ is defined to be optimal for execution if
$\,\exists\,r\in\mathcal{R}$ s.t.
$\mathbf{v}_{a}^{(3,3)}=r\left(\mathbf{V}_{a}\right)$, and optimal for
selection if the probability distribution over $\mathcal{R}$ induced by the
selection mechanism (through confidence values $s_{r}$) concentrates all the
probability on the correct rule.

The importance of this distinction can be understood in the following example.

###### Example 1

Consider the following RPM test example $V$, where different numbers
correspond to different color attribute values,

$\displaystyle{V}=\begin{matrix}\begin{bmatrix}\leavevmode\hbox
to51.66pt{\vbox to46.5pt{\pgfpicture\makeatletter\hbox{\hskip
25.83205pt\lower-23.24867pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{\offinterlineskip{}{}{{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}}{{{}}}{{}{}{{
{}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} {
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-22.49904pt}{-19.91566pt}\pgfsys@invoke{
}\hbox{\vbox{\halign{\pgf@matrix@init@row\pgf@matrix@step@column{\pgf@matrix@startcell#\pgf@matrix@endcell}&#\pgf@matrix@padding&&\pgf@matrix@step@column{\pgf@matrix@startcell#\pgf@matrix@endcell}&#\pgf@matrix@padding\cr\hfil\hskip
7.49968pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.16667pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{9 }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip
7.49968pt\hfil&\hfil\hskip 7.49968pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.16667pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{0 }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip
7.49968pt\hfil&\hfil\hskip 7.49968pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.16667pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{9 }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip
7.49968pt\hfil\cr\vskip 0.0pt\cr\hfil\hskip
7.49968pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.16667pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{6 }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip
7.49968pt\hfil&\hfil\hskip 7.49968pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.16667pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3 }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip
7.49968pt\hfil&\hfil\hskip 7.49968pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.16667pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{9 }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip
7.49968pt\hfil\cr\vskip 0.0pt\cr\hfil\hskip
7.49968pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.16667pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3 }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip
7.49968pt\hfil&\hfil\hskip 7.49968pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.16667pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2 }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip
7.49968pt\hfil&\hfil\hskip 7.36078pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.02777pt}{0.0pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{? }}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip
7.36078pt\hfil\cr}}}\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}}{{{{}}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\end{bmatrix}\end{matrix}\text{,
with }\begin{cases}x_{1}=9,x_{2}=0,o_{1}=6,o_{2}=3,o_{3}=9\text{ when
}X=R_{1}\\\ x_{1}=6,x_{2}=3,o_{1}=9,o_{2}=0,o_{3}=9\text{ when }X=R_{2}\\\
x_{1}=3,x_{2}=2,o_{1}=9,o_{2}=0,o_{3}=9\text{ when }X=R_{3}\end{cases}$

and a rule set $\mathcal{R}$ including the two rules that were proposed in
Learn-VRF [39] to solve arithmetic plus (+) and distribute three (d3),
rewritten accordingly to our context-augmented formulation

$\displaystyle\mathbf{v}^{+}=\mathbf{x}_{1}\circledast\mathbf{x}_{2}\equiv{x}_{1}+{x}_{2}=v^{+}$
$\displaystyle\mathbf{v}^{\text{d3}}=\left(\mathbf{o}_{1}\circledast\mathbf{o}_{2}\circledast\mathbf{o}_{3}\right)\circledcirc\mathbf{x}_{1}\circledcirc\mathbf{x}_{2}\equiv\left({o}_{1}+{o}_{2}+{o}_{3}\right)-{x}_{1}-{x}_{2}={v}^{\text{d3}}$

where the equivalence between vector space and $\mathbb{R}$ is given by FPE.

Performing the selection using $\mathcal{R}$ can potentially result in a
failure of the model for this RPM test. In fact, we can see that both
${v}^{+}$ and ${v}^{\text{d3}}$ will produce the correct answer on the first
two rows, and the confidence values (cosine similarity between the output and
the true attribute) will be 1 for both. As a result, the model will assign
equal probabilities to both rules (even if only one of them is valid),
rendering the probability of choosing the correct one equal to a coin toss.

Incorporating a validation term in the rule definition for distribute three
can, in this case, solve the issue. Consider the functionally equivalent rule

$\displaystyle{v}^{\text{d3++}}=\underbrace{\left({o}_{1}+{o}_{2}+o_{3}\right)-x_{1}-x_{2}}_{\text{execution}}+\underbrace{\left({o}_{1}+{o}_{2}+o_{3}\right)-\left({o}_{1}+{o}_{4}+{x}_{1}\right)}_{\text{validation}}.$

The last two additional terms only cancel out when the sum of the elements of
the first context row is equal to the sum of the elements of the first column,
which is a property that is always verified for distribute three but not for
the other RPM rules. Hence, using ${v}^{\text{d3++}}$ instead of
${v}^{\text{d3}}$ the model will be able to rule it out from the list of valid
rules, correctly putting all the probability mass into the arithmetic plus
rule instead. Note that learning ${v}^{\text{d3++}}$ would not have been
possible only with the 6 terms available in Equation 1.

Therefore, we claim that Equation 6, even if still not optimal for selection,
will increase the robustness of the model to RPM edge cases. However, the
increase in expressiveness also comes at a cost in terms of the number of
trainable parameters, which scales linearly with the number of terms of
Equations 6.

###  3.3 Training Loss and other Implementation Aspects

We follow the training recipe provided by Learn-VRF [39]. The training loss is
defined as the inverse cosine similarity between the three predicted panels
and their corresponding ground-truth

$\displaystyle\mathcal{L}=1-\sum_{i=1}^{3}\mathrm{cos}\left(\mathbf{v}_{a}^{(i,3)},\hat{\mathbf{v}}_{a}^{(i,3)}\right).$
(7)

As in Learn-VRF, we set the number of rules to $R=5$. A single set of rules is
instantiated and shared between all RPM attributes. In previous works [39],
the execution of the rules on the position and number attributes is performed
in superposition, since either the number or the position attribute
contributes to the generation of the answer. However, the superposition
requires a preliminary binding operation with (trainable) key vectors to avoid
the binding problem [48]. As a result, vector arithmetic is no longer
supported on these attributes. We disentangle the two attributes, speculating
that the trade-off between the additional noise introduced by the “unused”
attribute, for which no rule is formally defined, and the increased computing
accuracy will be significantly in favor of the latter. Removing the
superposition also allows us to remove the keys used by the binding, which
were trainable parameters in Learn-VRF and constituted the majority of
parameters of the model (81%).

##  4 Results

###  4.1 In-distribution (ID) Results

Table 2 shows the ARLC’s in-distribution downstream accuracy on I-RAVEN
compared to a range of neuro-symbolic and connectionist baselines. We present
results for three different versions of ARLC: $\text{ARLC}_{\text{progr}}$,
where the model’s weights are manually programmed with RPM rules ($R=4$, since
constant can be considered as a special case of progression),
$\text{ARLC}_{\text{p}\mapsto\text{l}}$, where the model is initialized with
the programmed rules and then trained with gradient descent, and
$\text{ARLC}_{\text{learn}}$, where the rules are learned from scratch from
data.

| I-RAVEN constellation accuracy (%)
---|---
Method | Approach | Param. | Avg. | C | 2x2 | 3x3 | L-R | U-D | O-IC | O-IG
GPT-3 [49] | Selective | 175 b | 86.5 | 86.4 | 83.2 | 81.8 | 83.4 | 84.6 | 92.8 | 93.0
MLP [39] | Predictive | 300 k | 87.1 | 97.6 | 87.1 | 61.8 | 99.4 | 99.4 | 98.7 | 65.6
SCL [50] | Selective | 961 k | $84.3^{\pm 1.1}$ | $\mathbf{99.9^{\pm 0.0}}$ | $68.9^{\pm 1.9}$ | $43.0^{\pm 6.2}$ | $98.5^{\pm 2.9}$ | $99.1^{\pm 1.5}$ | $97.7^{\pm 1.3}$ | $82.6^{\pm 2.5}$
PrAE [33] | Predictive | n.a. | $71.1^{\pm 2.1}$ | $83.8^{\pm 3.4}$ | $82.9^{\pm 3.3}$ | $47.4^{\pm 3.2}$ | $94.8^{\pm 2.1}$ | $94.8^{\pm 2.1}$ | $56.6^{\pm 3.0}$ | $37.4^{\pm 1.7}$
NVSA [34] | Predictive | n.a. | $88.1^{\pm 0.4}$ | $99.8^{\pm 0.2}$ | $\mathbf{96.2^{\pm 0.8}}$ | $54.3^{\pm 3.2}$ | $\mathbf{100^{\pm 0.1}}$ | $\mathbf{99.9^{\pm 0.1}}$ | $\mathbf{99.6^{\pm 0.5}}$ | $67.1^{\pm 0.4}$
Learn-VRF [39] | Predictive | 20 k | $79.5^{\pm 4.3}$ | $97.7^{\pm 4.1}$ | $56.3^{\pm 7.3}$ | $49.9^{\pm 2.8}$ | $94.0^{\pm 5.0}$ | $95.6^{\pm 5.0}$ | $98.3^{\pm 2.5}$ | $64.8^{\pm 3.4}$
$\text{ARLC}_{\text{progr}}$ | Predictive | n.a. | $92.4^{\pm 0.0}$ | $97.2^{\pm 0.0}$ | $84.9^{\pm 0.0}$ | $81.7^{\pm 0.0}$ | $97.8^{\pm 0.0}$ | $96.8^{\pm 0.0}$ | $98.2^{\pm 0.0}$ | $90.0^{\pm 0.0}$
$\text{ARLC}_{\text{p}\mapsto\text{l}}$ | Predictive | 240 | $\mathbf{92.6^{\pm 0.2}}$ | $97.6^{\pm 0.0}$ | $84.7^{\pm 0.4}$ | $80.7^{\pm 0.4}$ | $98.5^{\pm 0.0}$ | $97.9^{\pm 0.0}$ | $98.5^{\pm 0.0}$ | $90.3^{\pm 0.3}$
$\text{ARLC}_{\text{learn}}$ | Predictive | 240 | $92.4^{\pm 1.5}$ | $98.4^{\pm 1.5}$ | $83.4^{\pm 1.6}$ | $80.0^{\pm 2.1}$ | $98.7^{\pm 1.2}$ | $98.4^{\pm 1.4}$ | $98.8^{\pm 1.2}$ | $89.4^{\pm 1.6}$

Table 2: In-distribution accuracy (%) on the I-RAVEN dataset. The results for
PrAE and ARLC are obtained training only on the 2x2 constellation and testing
on all the others. Among the baselines, we replicate Learn-VRF; the other
results are taken from [34]. The standard deviations are reported over 10
random seeds.

ARLC achieves the best average accuracy on the in-distribution I-RAVEN
dataset, improving the second-best result (NVSA [34], where the rules are
hard-wired into the model) by almost $5\%$, while having orders of magnitude
fewer parameters than any other baseline model. ARLC also shows lower variance
compared to the other baselines on almost every constellation.

Contrary to all the other methods (with the exception of PrAE [33]), ARLC is
exclusively trained on the 2x2 constellation, effectively reducing the number
of trained parameters and training samples by 85% ($\nicefrac{{6}}{{7}}$). Its
seamless adaptation to unseen constellations demonstrates the generality of
the learned rules but prevents the model from outperforming the baselines in
each single constellation.

ARLC produces close to perfect results on all the constellations without the
position/number attribute (that is, C, L-R, U-C, and O-IC), strongly
outperforming GPT-3 and PrAE. On the other hand, its accuracy degrades for the
constellations that include the position/number attribute (that is, 2x2, 3x3,
and O-IG). This degradation arises because of three specific rules on the
position attribute: progression (corresponding to a circular bit-shifting
operation), arithmetic plus (corresponding to the logical operation $a\lor
b$), and arithmetic minus (corresponding to the logical operation $a\land\neg
b$). These rules, which operate at the granularity of objects, cannot be
easily captured by the model, which operates at the granularity of panels.

Finally, comparing the three proposed versions of ARLC, it is interesting to
observe that $\text{ARLC}_{\text{p}\mapsto\text{l}}$ outperforms both its
fully-learned and fully-programmed equivalents. The post-programming training
allows to extend the knowledge of the model, rather than completely erasing it
as shown in other settings [40], resulting in a monotonic increase in
downstream accuracy.

Table 3: Ablation on the proposed improvements, as in-distribution accuracy
(%) on the I-RAVEN dataset. The ablations are row-wise incremental.

Method | C | 2x2 | 3x3 | L-R | U-D | O-IC | O-IG | Avg. | $\Delta$
---|---|---|---|---|---|---|---|---|---
Learn-VRF [39] | $97.7^{\pm 4.1}$ | $56.3^{\pm 7.3}$ | $49.9^{\pm 2.8}$ | $94.0^{\pm 5.0}$ | $95.6^{\pm 5.0}$ | $98.3^{\pm 2.5}$ | $64.8^{\pm 3.4}$ | $79.5^{\pm 4.3}$ | –
p/n sup, 2x2 train | $92.1^{\pm 6.5}$ | $78.5^{\pm 5.4}$ | $76.1^{\pm 5.3}$ | $92.4^{\pm 6.8}$ | $92.3^{\pm 6.6}$ | $95.1^{\pm 4.2}$ | $86.6^{\pm 3.4}$ | $87.6^{\pm 5.5}$ | $\mathbf{+8.1}$
context-awareness | $95.2^{\pm 4.2}$ | $81.9^{\pm 3.4}$ | $78.9^{\pm 3.6}$ | $95.1^{\pm 4.4}$ | $94.9^{\pm 4.5}$ | $96.6^{\pm 2.7}$ | $88.8^{\pm 2.1}$ | $90.2^{\pm 3.6}$ | $+2.6$
12 terms (ARLC) | $\mathbf{98.4^{\pm 1.5}}$ | $\mathbf{83.4^{\pm 1.6}}$ | $\mathbf{80.0^{\pm 2.1}}$ | $\mathbf{98.7^{\pm 1.2}}$ | $\mathbf{98.4^{\pm 1.4}}$ | $\mathbf{98.8^{\pm 1.2}}$ | $\mathbf{89.4^{\pm 1.6}}$ | $\mathbf{92.4^{\pm 1.5}}$ | $+2.2$

Table 3 reports a thorough ablation on the novelties introduced in our
framework. We can observe that the biggest contribution comes from removing
the position/number superposition ($+8.1\%$), which consistently increases the
performance on the constellations involving these attributes. However, in all
the other constellations we observe a consistent drop in accuracy, due to the
evaluation of the model in the “transfer” setting (trained on 2x2, evaluated
on all the others). This drop is compensated by the two novel components of
the model, the context-awareness and the generalized rule template, which
allow ARLC to match and outperform Learn-VRF on every constellation.
Interestingly, they also contribute to reduce the variance of the results,
suggesting that the two improvements might be increasing the model invariance
to weight initialization.

###  4.2 Out-of-distribution (OOD) Results

We validate ARLC’s out-of-distribution generalization capabilities by
following the same recipe proposed by Learn-VRF [39]: the model is trained on
a subset of the rule-attributes pairs of the center constellation, and
evaluated on its complement. As shown in Table 4, ARLC matches the OOD
performance previously showed by Learn-VRF, attaining perfect accuracy on
almost every unseen rule-attribute pair in the center constellation.

Table 4: OOD accuracy (%) on unseen rule-attribute pairs on I-RAVEN.

| Type | Size | Color
---|---|---|---
| Const. | Progr. | Dist.3 | Const. | Progr. | Dist.3 | Arith. | Const. | Progr. | Dist.3 | Arith.
GPT-3 [39] | 88.5 | 86.0 | 88.6 | 93.6 | 93.2 | 92.6 | 71.6 | 94.2 | 94.7 | 94.3 | 65.8
MLP baseline [39] | 14.8 | 14.9 | 30.2 | 22.8 | 75.0 | 47.0 | 46.6 | 56.3 | 60.5 | 44.4 | 48.9
Learn-VRF [39] | 100 | 100 | 99.7 | 100 | 100 | 99.8 | 99.8 | 100 | 98.8 | 100 | 100
ARLC | 100 | 98.6 | 99.7 | 100 | 100 | 99.6 | 99.6 | 100 | 100 | 100 | 99.8

##  5 Conclusions and Future Work

In this work, we proposed the Abductive Rule Learner with Context-awareness
(ARLC), a model built on top of Learn-VRF [39] to enhance its downstream
accuracy, interpretability, model size, and coherence. We conducted
evaluations on the I-RAVEN dataset, demonstrating significant performance
improvements compared to a diverse array of neuro-symbolic and connectionist
baselines, including large language models, across both ID and OOD data.
Furthermore, we presented empirical results on the programmability of the
model and the generalization across different constellations of the I-RAVEN
dataset.

A potential avenue for future research involves addressing the remaining
challenge posed by this dataset, specifically, the development of suitable
representations to allow the learnability of arithmetic and progression rules
on the position attributes. These rules are currently impossible to learn for
the model and would allow it to attain perfect accuracy on I-RAVEN.
Additionally, extending the evaluation of ARLC to include other reasoning
benchmarks, such as ARC [3], also represents a promising direction for further
investigation. In fact, while the scope of this work was mostly focus on
developing and studying a prototype that could solve RPM, the proposed general
formulation of the problem could transfer to other settings that require
relations and analogies data-driven learning. Furthermore, as our experiments
on learning of top programmed knowledge show, our framework holds potential
for application in scenarios where only a partial knowledge on the dynamics is
available, and it is necessary to discover and build new knowledge on top of
it.

####  5.0.1 Acknowledgments

This work is supported by the Swiss National Science foundation (SNF), grant
200800.

## References

  * [1] Bilker, W.B., Hansen, J.A., Brensinger, C.M., Richard, J., Gur, R.E., Gur, R.C.: Development of abbreviated nine-item forms of the Raven’s standard progressive matrices test. Assessment (2012)
  * [2] Cherian, A., Peng, K., Lohit, S., Smith, K.A., Tenenbaum, J.B.: Are deep neural networks smarter than second graders? In: 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). pp. 10834–10844. IEEE Computer Society, Los Alamitos, CA, USA (2023)
  * [3] Chollet, F.: On the measure of intelligence. arXiv preprint arXiv:1911.01547 (2019)
  * [4] Niedermayr, Y., Lanzendörfer, L.A., Estermann, B., Wattenhofer, R.: RLP: A reinforcement learning benchmark for neural algorithmic reasoning. OpenReview (2023)
  * [5] Carpenter, P.A., Just, M.A., Shell, P.: What one intelligence test measures: a theoretical account of the processing in the Raven progressive matrices test. Psychological review (1990)
  * [6] Raven, J., Court, J., Raven, J.: Raven’s progressive matrices. Oxford Psychologists Press (1938)
  * [7] Snow, R.E., Kyllonen, P.C., Marshalek, B., et al.: The topography of ability and learning correlations. Advances in the psychology of human intelligence 2(S 47), 103 (1984)
  * [8] Snow, R.E., Lohman, D.F.: Toward a theory of cognitive aptitude for learning from instruction. Journal of educational psychology 76(3), 347 (1984)
  * [9] Benny, Y., Pekar, N., Wolf, L.: Scale-localized abstract reasoning. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (2021)
  * [10] Hu, S., Ma, Y., Liu, X., Wei, Y., Bai, S.: Stratified rule-aware network for abstract visual reasoning. In: Proceedings of the AAAI Conference on Artificial Intelligence (AAAI) (2021)
  * [11] Małkiński, Mikołaj and Mańdziuk, Jacek: Deep learning methods for abstract visual reasoning: A survey on Raven’s progressive matrices. arXiv preprint arXiv:2201.12382 (2022)
  * [12] Mitchell, M.: Abstraction and analogy-making in artificial intelligence. Annals of the New York Academy of Sciences 1505(1), 79–101 (2021)
  * [13] Zhang, C., Gao, F., Jia, B., Zhu, Y., Zhu, S.C.: Raven: A dataset for relational and analogical visual reasoning. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2019)
  * [14] Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., Chi, E.H., Hashimoto, T., Vinyals, O., Liang, P., Dean, J., Fedus, W.: Emergent abilities of large language models. Transactions on Machine Learning Research (2022)
  * [15] Hu, X., Storks, S., Lewis, R., Chai, J.: In-context analogical reasoning with pre-trained language models. In: Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1953–1969. Association for Computational Linguistics, Toronto, Canada (2023)
  * [16] Webb, T., Holyoak, K.J., Lu, H.: Emergent analogical reasoning in large language models. Nature Human Behaviour 7(9), 1526–1541 (2023)
  * [17] Gendron, G., Bao, Q., Witbrock, M., Dobbie, G.: Large language models are not strong abstract reasoners (2024)
  * [18] Wu, Z., Qiu, L., Ross, A., Akyürek, E., Chen, B., Wang, B., Kim, N., Andreas, J., Kim, Y.: Reasoning or reciting? exploring the capabilities and limitations of language models through counterfactual tasks (2024)
  * [19] Camposampiero, G., Houmard, L., Estermann, B., Mathys, J., Wattenhofer, R.: Abstract visual reasoning enabled by language. In: 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW). pp. 2643–2647. IEEE Computer Society, Los Alamitos, CA, USA (2023)
  * [20] Lewis, M., Mitchell, M.: Using counterfactual tasks to evaluate the generality of analogical reasoning in large language models. arXiv preprint arXiv:2402.08955 (2024)
  * [21] Odouard, V.V., Mitchell, M.: Evaluating understanding on conceptual abstraction benchmarks. arXiv preprint arXiv:2206.14187 (2022)
  * [22] Thomm, J., Terzic, A., Karunaratne, G., Camposampiero, G., Schölkopf, B., Rahimi, A.: Limits of transformer language models on algorithmic learning. arXiv preprint arXiv:2402.05785 (2024)
  * [23] Han, C., Mao, J., Gan, C., Tenenbaum, J., Wu, J.: Visual concept-metaconcept learning. In: Advances in Neural Information Processing Systems (NeurIPS) (2019)
  * [24] Mao, J., Gan, C., Kohli, P., Tenenbaum, J.B., Wu, J.: The neuro-symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision. In: International Conference on Learning Representations (ICLR) (2019)
  * [25] Mei, L., Mao, J., Wang, Z., Gan, C., Tenenbaum, J.B.: FALCON: Fast visual concept learning by integrating images, linguistic descriptions, and conceptual relations. In: International Conference on Learning Representations (ICLR) (2022)
  * [26] Yi, K., Wu, J., Gan, C., Torralba, A., Kohli, P., Tenenbaum, J.: Neural-symbolic VQA: Disentangling reasoning from vision and language understanding. In: Advances in Neural Information Processing Systems (NeurIPS) (2018)
  * [27] Schlag, I., Schmidhuber, J.: Learning to reason with third-order tensor products. In: Advances in Neural Information Processing Systems (NeurIPS) (2018)
  * [28] Yi, K., Gan, C., Li, Y., Kohli, P., Wu, J., Torralba, A., Tenenbaum, J.B.: CLEVRER: Collision events for video representation and reasoning. In: International Conference on Learning Representations (ICLR) (2020)
  * [29] Schlag, I., Smolensky, P., Fernandez, R., Jojic, N., Schmidhuber, J., Gao, J.: Enhancing the transformer with explicit relational encoding for math problem solving. arXiv preprint arXiv:1910.06611 (2019)
  * [30] Yang, Y., Sanyal, D., Michelson, J., Ainooson, J., Kunda, M.: A conceptual chronicle of solving raven’s progressive matrices computationally. In: Proceedings of the 8th International Workshop on Artificial Intelligence and Cognition (2022)
  * [31] Shah, V., Sharma, A., Shroff, G., Vig, L., Dash, T., Srinivasan, A.: Knowledge-based analogical reasoning in neuro-symbolic latent spaces. In: Proceedings of the 16th International Workshop on Neural-Symbolic Learning and Reasoning (NeSy) (2022)
  * [32] Zhao, S., You, H., Zhang, R.Y., Si, B., Zhen, Z., Wan, X., Wang, D.H.: An interpretable neuro-symbolic model for raven’s progressive matrices reasoning. Cognitive Computation 15(5), 1703–1724 (2023)
  * [33] Zhang, C., Jia, B., Zhu, S.C., Zhu, Y.: Abstract spatial-temporal reasoning via probabilistic abduction and execution. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2021)
  * [34] Hersche, M., Zeqiri, M., Benini, L., Sebastian, A., Rahimi, A.: A neuro-vector-symbolic architecture for solving raven’s progressive matrices. Nature Machine Intelligence 5(4), 363–375 (2023)
  * [35] Magnani, L.: Abductive Cognition: The Epistemological and Eco-Cognitive Dimensions of Hypothetical Reasoning. Springer Berlin, Heidelberg (2009)
  * [36] Gayler, R.W.: Vector symbolic architectures answer Jackendoff’s challenges for cognitive neuroscience. In: Joint International Conference on Cognitive Science (ICCS/ASCS) (2003)
  * [37] Kanerva, P.: Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors. Cognitive Computation 1(2), 139–159 (2009)
  * [38] Plate, T.A.: Holographic reduced representations. IEEE Transactions on Neural Networks 6(3), 623–641 (1995)
  * [39] Hersche, M., di Stefano, F., Hofmann, T., Sebastian, A., Rahimi, A.: Probabilistic abduction for visual abstract reasoning via learning rules in vector-symbolic architectures. In: The 3rd Workshop on Mathematical Reasoning and AI at NeurIPS’23 (2023)
  * [40] Wu, X., Zhang, X., Shu, X.: Cognitive deficit of deep learning in numerosity. In: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence. AAAI Press (2019)
  * [41] Kleyko, D., Rachkovskij, D.A., Osipov, E., Rahimi, A.: A survey on hyperdimensional computing aka vector symbolic architectures, part I: models and data transformations. ACM Comput. Surv. (2022)
  * [42] Hu, X., Storks, S., Lewis, R.L., Chai, J.: In-context analogical reasoning with pre-trained language models. In: Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Long Paper) (2023)
  * [43] Webb, T., Holyoak, K.J., Lu, H.: Emergent analogical reasoning in large language models. Nature Human Behaviour 7(9), 1526–1541 (2023)
  * [44] Hersche, M., Terzic, A., Karunaratne, G., Langenegger, J., Pouget, A., Cherubini, G., Benini, L., Sebastian, A., Rahimi, A.: Factorizers for distributed sparse block codes. arXiv preprint arXiv:2303.13957 (2023)
  * [45] Plate, T.A.: Holographic Reduced Representations: Distributed Representation for Cognitive Structures. Center for the Study of Language and Information, Stanford (2003)
  * [46] Chalmers, D.J., French, R.M., Hofstadter, D.R.: High-level perception, representation, and analogy: A critique of artificial intelligence methodology. Journal of Experimental & Theoretical Artificial Intelligence 4(3), 185–211 (1992)
  * [47] Cheng, Y.: Context-dependent similarity. In: Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence. p. 41–50. UAI ’90, Elsevier Science Inc., USA (1990)
  * [48] Greff, K., Van Steenkiste, S., Schmidhuber, J.: On the binding problem in artificial neural networks. arXiv preprint arXiv:2012.05208 (2020)
  * [49] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J.D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.: Language models are few-shot learners. Advances in Neural Information Processing Systems (NeurIPS) 33, 1877–1901 (2020)
  * [50] Wu, Y., Dong, H., Grosse, R., Ba, J.: The scattering compositional learner: Discovering objects, attributes, relationships in analogical reasoning. arXiv preprint arXiv:2007.04212 (2020)