# Learning to Estimate the Pose of a Peer Robot in a Camera Image
by Predicting the States of its LEDs

Nicholas Carlotti1, Mirko Nava1, and Alessandro Giusti1 1All authors are with
the Dalle Molle Institute for Artificial Intelligence (IDSIA), USI-SUPSI,
Lugano, 6962, Switzerland<EMAIL_ADDRESS>work is supported by
the Swiss National Science Foundation, grant number 213074.

###### Abstract

We consider the problem of training a fully convolutional network to estimate
the relative 6D pose of a robot given a camera image, when the robot is
equipped with independent controllable LEDs placed in different parts of its
body. The training data is composed by few (or zero) images labeled with a
ground truth relative pose and many images labeled only with the true state
(on or off) of each of the peer LEDs. The former data is expensive to acquire,
requiring external infrastructure for tracking the two robots; the latter is
cheap as it can be acquired by two unsupervised robots moving randomly and
toggling their LEDs while sharing the true LED states via radio. Training with
the latter dataset on estimating the LEDs’ state of the peer robot (_pretext
task_) promotes learning the relative localization task (_end task_).
Experiments on real-world data acquired by two autonomous wheeled robots show
that a model trained only on the pretext task successfully learns to localize
a peer robot on the image plane; fine-tuning such model on the end task with
few labeled images yields statistically significant improvements in 6D
relative pose estimation with respect to baselines that do not use pretext-
task pre-training, and alternative approaches. Estimating the state of
multiple independent LEDs promotes learning to estimate relative heading. The
approach works even when a large fraction of training images do not include
the peer robot and generalizes well to unseen environments.

©2024 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.

## Supplementary Material

Videos, dataset and code of the proposed approach are available at
https://github.com/idsia-robotics/ssl-pretext-multi-led.

##  I Introduction

Estimating the relative pose of a peer robot is a key capability for multi-
robot systems [1], with wide-ranging applications spanning surveillance [2,
3], surveying or exploration [4, 5], acrobatic and light shows [6, 7, 8].
Solving the problem using visual inputs typically involves training a
convolutional neural network with images and associated ground truth labels,
representing the true relative pose of the peer robot. Collecting such a
dataset can be expensive: generating ground truth labels requires specialized
tracking hardware, e.g., often a fixed infrastructure; at the same time,
generalizing to different environments and conditions requires training with a
dataset that is large and varied. To minimize the need for expensive labeled
training data for the pose estimation task, i.e., our _end task_ , one can
train the model to solve an auxiliary _pretext task_ [9]. A good pretext task
has two distinctive characteristics: it promotes learning visual features that
are relevant to the end task and uses ground truth labels that are easy to
collect.

In previous work [10], we have shown that learning to estimate the shared
boolean state of the LEDs on the peer robot (being either all turned on, or
all off) is an effective pretext task to learn the end task of 2D localization
of the peer robot in the image plane, also called detection in the literature.
This pretext task entails a powerful idea: predicting whether the peer robot’s
LEDs are on or off given an image requires understanding where the peer robot
is in the image. The task can be trained using images labeled only with the
true state of the peer robot’s LEDs; this data is easy to get from a
collaborative peer, e.g., via radio, and large datasets can be collected
autonomously by the pair of robots in any environment, without the need for
external infrastructure or supervision.

Figure 1: A DJI RoboMaster S1 visually estimating the relative pose of a peer
robot, using a model trained on an autonomously-collected dataset in which the
four LED states of its peer robot are known for all images; instead, the true
relative pose of its peer is known in few, or even zero images.

This paper extends our previous work [10] in multiple directions. We show that
the pretext task alone, _without any labels for the end task_ , leads to the
model learning to localize the peer robot on the image plane. This is due to
the inductive bias induced by our fully convolutional network [11]
architecture. It predicts the state of an LED as the weighted average of an
output LED state map while the weights are given by an output robot position
map. This weighting can be seen as an attention mechanism exploited for
localization, similar to weakly supervised learning for object localization
[12], but using autonomously-collected LED state labels instead of semantic
labels. Instead of a single state shared by all of the peer’s LEDs, our
pretext task estimates _four independent states_ , one for each LED placed on
a different side of the peer robot, as shown in Figure 1.

Solving the pretext task requires not only help to localize the peer in the
image but also to understand its relative orientation, as shown in Figure 2.
Experiments confirm that the proposed pretext task helps to learn to estimate
the peer’s relative orientation. Further, previous work [10] only considered
the position of the peer robot in the image and assumed it to be always
visible in images used to train the pretext task; here, we estimate the 6D
relative pose of the peer and also consider the two robots autonomously
collecting training data while roaming a confined environment: less than a
quarter of the resulting images have the peer robot visible at all, with each
LED being visible only for 8% of images. We show that the pretext task is
effective in this challenging but realistic case.

Our main contribution is the improved methodology for an LED-based pretext
task, presented in Section III. We extensively validate our approach on real-
world data on the task of estimating the pose of a wheeled ground robot from
the feed of an RGB monocular camera in Section IV. Results, reported in
Section V, show the ability of the robot to localize its peer without training
on ground truth pose labels, and significant improvements when the model
trained on the pretext task is fine-tuned for the end task on 10, 100 or 1000
labeled images; compared to a baseline that does not use the pretext task, and
to a baseline trained on CLIP [13] features, our approach significantly
improves performance on 2D image localization, relative orientation
estimation, and 3D pose estimation. As a secondary contribution, we release
the code and real-world dataset used for our experiments. Finally, we conclude
the article and describe future work directions in Section VI.

Figure 2: Our fully convolutional network model takes an image as input and
predicts maps for the robot’s image space position $\bm{\hat{P}}$, distance
$\bm{\hat{D}}$, orientation $\bm{\hat{O}}$ and state of the LEDs
$\bm{\hat{L}}_{i}$. We obtain scalar values from the maps by element-wise
multiplication (denoted as $\circ$) with $norm(\bm{\hat{P}})$, acting as an
attention mechanism. By optimizing $\hat{l}_{i}$, the model learns to estimate
the robot’s LED state and position in the image; gradients for $\bm{\hat{P}}$
resulting from the optimization of $\hat{d}$ and $\hat{\psi}$ are blocked (see
Section III-A for details).

##  II Related Work

###  II-A Visual 6D Robot Pose Estimation

Visual robot pose estimation problems are solved using hand-crafted [6, 14,
15] or learned [16, 17] features. Hand-crafted approaches propose algorithms
to extract geometrical features of either paper-printed patterns [14] or
fiducial markers [6] and process them to reconstruct the pose of the robot
relative to the camera. In the absence of markers or patterns, Yu et al. [15]
leverage dense information from an RGB-D camera to extract features and then
localize the robot. However, these techniques do not generalize to
environmental settings not conceived at design time. To address this
limitation, practitioners resort to deep neural networks; these models are
used for pose estimation of a robot arm’s joints by predicting keypoints [16],
and further optimize the keypoint placement [17].

Our approach uses a self-supervised pretext task to train a deep neural
network model, learning relevant visual features and enabling relative pose
estimation of a peer robot given a single image.

###  II-B Self Supervised Learning for Visual Pose Estimation

Training neural networks to solve complex visual tasks requires a large amount
of labeled data. Labeling this data is often expensive and time-consuming,
involving specialized tracking hardware or tedious hand-labeling. This issue
is tackled by self-supervised learning techniques, where an autonomous robot
collects its own training data [18, 19, 20] and uses it to train on a pretext
task, learning features that are useful for solving perception problems [10,
21, 22]. Automated data collection with a robot arm involves recording
interactions with objects and the view of the scene, later used to learn
object features [18] or its pose, starting from models pre-trained in
simulation and fine-tuned on real data [19]. Nano-drone’s poses are estimated
from monocular cameras, training on labels generated from ultra-wide band
sensors [20].

Approaches that rely on a pretext task in robotics use masked autoencoders to
learn object pose estimation and manipulation [21]; improve the detection of a
drone by solving the pretext task of estimating the sound produced by its
rotors [22]; or the shared state of the drone’s LEDs [10], which are assumed
to be either all on or off. In contrast, the present work estimates the
independent state of multiple robot-mounted LEDs: which of these are actually
visible depends on the robot relative orientation. This defines a more complex
pretext task; learning to solve it leads to learning features that are
informative not only for image-space localization, but also for estimating the
relative orientation of the peer robot.

Additionally, we demonstrate that our approach is robust to training with
images that depict the robot infrequently, as it commonly occurs with a robot
autonomously collecting data.

###  II-C Weakly Supervised Learning in Computer Vision

In computer vision, weakly supervised learning focuses on reducing the need
for lots of labeled examples for solving object localization [12] and
segmentation [23] tasks. The general framework consists in training
classification models using coarse image labels, e.g., the textual description
of the subject of a picture; by training on these labels, models learn to
extract finer information, such as image segmentations, by analyzing neural
network activations [24, 25] or employing feature clustering mechanisms [26].

The most notable approach that analyzes the network’s hidden state for
segmentation is Class Activation Mapping (CAM) [27], and more recently
Ablation-CAM [28]. These approaches use a trained image classifier to detect
discriminative areas of the input image, i.e., those responsible for making
the model predict the image class. For Ablation-CAM [28], the activation maps
are extracted with a gradient-free method, disabling feature maps and
measuring its impact on the model’s output. Another proposed solution modifies
a pre-trained classifier to predict a class for a set of regions partitioning
the input image [29]. The individual scores for every region are then combined
to allow for the detection of objects of interest in the input image. Semantic
segmentation is achieved by training a fully convolutional network to predict
image labels using a weak supervision loss [30]. The loss enforces soft
constraints based on the number of classes and number of elements within the
class to improve segmentation results. The introduction of attention
mechanisms to visual models [24, 25] paved the way for novel weakly supervised
segmentation approaches: attention mechanism for convolutional neural networks
have been proposed for segmenting images through the learning of
classification tasks [31, 32]; while vision transformers segment images using
a novel patch-based attention dropout layer [33].

The discussed approaches learn to detect objects in images by training on
semantic class labels. Here, instead, we employ the state of a robot’s on-
board LEDs as multi-class labels; this information can be easily collected by
letting the robot broadcast the LEDs’ state, enabling the automated collection
of training data. Further, our deep neural network model employs a soft
attention mechanism: it designates one feature map as a mask applied to the
other feature maps to predict the LEDs’ state. After training, this map is
used to locate the robot in the image.

##  III Method

We focus on relative visual robot localization tasks where the goal is to
estimate the relative pose of a target robot w.r.t. the frame of a peer robot,
called observer, using as input the feed of a monocular camera. To this end,
we train a deep learning model using collected data, consisting of samples
$\\{\langle\bm{i}_{j},\bm{p}_{j},\bm{l}_{j}\rangle\\}_{j=1}^{N}$ where
$\bm{i}\in\mathbb{R}^{whc}$ is the image of $w\times h$ pixels and $c$
channels, $\bm{p}\in SE(3)$ is the 6D relative pose of the target robot
consisting of $\langle x,y,z,\varphi,\theta,\psi\rangle$, and
$\bm{l}\in\\{\textsc{off},\textsc{on}\\}^{k}$ is the state of the robot’s
fitted LEDs consisting of $\langle l_{1},\dots,l_{k}\rangle$. Since our
application involves a ground robot, $\phi$ and $\theta$ are assumed to be
always zero.

We consider scenarios where the ground truth labels for the relative robot
pose might only be measurable in dedicated lab environments with specialized
hardware, e.g., tracking systems, while in other environments, this
information in unknown and collected images might not feature a visible robot.
As such, the collected samples are said to be labeled if they feature known
relative robot poses or unlabeled otherwise. Based on this notion, we define
three disjoint sets: the labeled training set $\mathcal{T}_{\ell}$ containing
a limited amount of labeled samples, the unlabeled training set
$\mathcal{T}_{u}$ containing unlabeled samples, and the testing set
$\mathcal{Q}$ containing labeled samples. For our experiments, we additionally
consider the subset of the unlabeled testing set having samples with the robot
visible, named $\mathcal{T}_{u}^{\nu}$, and denote the full unlabeled set as
$\mathcal{T}_{u}^{a}$.

Using these samples, we learn a convolutional neural network
$\bm{m_{\theta}}(\bm{i})$ parametrized by $\bm{\theta}$ and whose input is the
image $\bm{i}$. The model learns to predict the image-space position of the
robot on the horizontal $u$ and vertical $v$ axes, also called 2D detection in
the literature, the distance of the robot $d$ and its roll $\varphi$, pitch
$\theta$, and yaw $\psi$ rotation. Given the camera intrinsics, we reconstruct
the 3D position $xyz$ of the robot by projecting a ray passing through the
$uv$ pixel and selecting the point lying at distance $d$ from the camera. As
the architecture of choice, we propose a fully convolutional network (FCN)
architecture [11], being composed solely of convolution and pooling layers and
producing maps of $w^{\prime}\times h^{\prime}$ cells as the output. We take
full advantage of the inductive bias of FCNs, namely that a cell’s value
depends only on a portion of the input image based on the model’s receptive
field, and that the weight-sharing of convolutions forces the model to
recognize local patterns regardless of its location within the image. Indeed,
this helps the model to focus more on the robot’s appearance and less on the
background, and is a desirable property due to our expectation that the robot
occupies a small portion of the field of view.

The model produces estimates for the position map
$\bm{\hat{P}}\in[0,1]^{w^{\prime}h^{\prime}}$, whose cells represent the
likelihood of depicting a robot in the respective location; the distance map
$\bm{\hat{D}}\in[0,d_{\text{max}}]^{w^{\prime}h^{\prime}}$, representing the
distance of the robot up to a maximum parametrized by $d_{\text{max}}$; the
orientation maps $\bm{\hat{O}}\in[-1,1]^{w^{\prime}h^{\prime}2}$, representing
the robot’s orientation and consisting of sine
$\bm{\hat{O}}_{\text{sin}}^{\psi}$ and cosine maps
$\bm{\hat{O}}_{\text{cos}}^{\psi}$; and the LED state maps
$\bm{\hat{L}}\in[0,1]^{w^{\prime}h^{\prime}k}$, where the $i$-th map
represents the state of $l_{i}$ and $1\\!\leq\\!i\\!\leq\\!k$. We obtain
scalar values from the model’s predicted maps by weighting them with the
predicted position map $\bm{\hat{P}}$ according to
$\operatorname{\bm{wm_{\hat{P}}}}(\bm{X})=\sum_{i=1}^{h^{\prime}}\sum_{j=1}^{w^{\prime}}\bigl{(}\text{norm}(\bm{\hat{P}})_{ij}\cdot\bm{X}_{ij}\bigr{)}$,
where $\text{norm}(\cdot)$ normalizes the map s.t. its cells sum to one.
Specifically for orientation, we obtain the value of the angle from the
predicted sine and cosine maps as
$\hat{\psi}=\text{atan2}\bigl{(}\operatorname{\bm{wm_{\hat{P}}}}(\bm{\hat{O}}_{\text{sin}}^{\psi}),\operatorname{\bm{wm_{\hat{P}}}}(\bm{\hat{O}}_{\text{cos}}^{\psi})\bigr{)}$.

###  III-A Losses

We train our model on one of two losses based on the availability of labels
for the pose estimation task: we define the downstream or end task loss as
$\mathcal{L}_{\text{task}}=\frac{1}{3}(\mathcal{L}_{\text{pos}}+\mathcal{L}_{\text{dist}}+\mathcal{L}_{\text{ori}})$,
trained on the labeled set $\mathcal{T}_{\ell}$, and the LED-based pretext
loss $\mathcal{L}_{\text{led}}$, trained on $\mathcal{T}_{u}^{a}$ or the
visible subset $\mathcal{T}_{u}^{\nu}$; all losses are designed to be bounded
between zero and one. To compute the position loss we first generate the
ground truth map $\bm{{P}}$. To do this, we set cells in a circle of radius
$r$ centered in $uv$ to one while the remaining cells are set to zero. We then
calculate the element-wise product between the normalized position map and the
ground truth one using $\operatorname{\bm{wm_{\hat{P}}}}$. By doing this, we
measure the portion of pixels with high value in the predicted map
$\bm{\hat{P}}$ that share the same coordinates with high-valued elements in
$\bm{P}$. This loss reaches zero only when predicted and ground truth maps
perfectly overlap.

$\mathcal{L}_{\text{pos}}=1-\operatorname{\bm{wm_{\hat{P}}}}(\bm{P})$ (1)

The distance loss uses $\operatorname{\bm{wm_{\hat{P}}}}$ to recover $\hat{d}$
and then computes the mean squared error with the ground truth distance

$\mathcal{L}_{\text{dist}}=\frac{1}{d_{\text{max}}^{2}}\text{mse}\bigl{(}d,\operatorname{\bm{wm_{\hat{P}}}}(\bm{\hat{D}})\bigr{)}$
(2)

The orientation loss is defined as the sum of the mean squared error on the
sine and cosine maps of each angle

$\mathcal{L}_{\text{ori}}=\frac{1}{4}\sum_{f\in\\{\text{sin},\text{cos}\\}}\text{mse}\bigl{(}f(\psi),\operatorname{\bm{wm_{\hat{P}}}}(\bm{\hat{O}}_{f}^{\psi})\bigr{)}$
(3)

The LED state loss is defined as the mean of the binary cross entropy for each
of the $k$ robot LEDs

$\mathcal{L}_{\text{led}}=\frac{1}{k}\sum_{i=1}^{k}\text{bce}\bigl{(}l_{i},\operatorname{\bm{wm_{\hat{P}}}}(\bm{\hat{L}}_{i})\bigr{)}$
(4)

It is important to note that in $\mathcal{L}_{\text{led}}$, we allow gradients
to flow through the predicted position map $\bm{\hat{P}}$, enabling the
optimization of the robot position map without using labels; this results in
an attention-like mechanism, where the position map weights the cells of the
LED map, assigning higher values to pixels containing relevant information for
estimating the LEDs’ state, i.e., those depicting the robot. Instead,
$\mathcal{L}_{\text{dist}}$ and $\mathcal{L}_{\text{ori}}$ block the gradients
from flowing through the predicted position map $\bm{\hat{P}}$; this avoids
having the gradients for the $\bm{\hat{P}}$ map applied twice when optimizing
$\mathcal{L}_{\text{task}}$.

##  IV Experimental Setup

The proposed approach is applied to the problem of peer-to-peer localization
of DJI S1 RoboMasters, omnidirectional ground robots equipped with four
Swedish wheels and a front-facing monocular camera with a resolution of
$640\times 360$ pixels mounted on a pan-and-tilt turret. The robot features
six RGB LEDs: four are mounted on the base of the robot, one for each cardinal
direction, and two are mounted on the left and right sides of the robot’s
turret; in our experiments we consider four LEDs: the two turret ones and the
front and back ones of the robot base, while the left and right base LEDs are
always off and ignored in our evaluation.

Figure 3: Six samples from the unlabeled training set $\mathcal{T}_{u}^{a}$,
where only 22% of images feature a visible robot; ground truth robot poses are
depicted with a blue bounding box.

###  IV-A Dataset

The data collection setup consists of two robots roaming a $4\times 4$ meters
area inside our lab with a random policy: it keeps robots moving in a straight
line until they collide with the edges of the area or with one another; when
it happens, they rotate in-place in one of the two directions by $None$ $\pm\
\mathcal{U}($$None$, $None$$)$. Every five seconds, each of the four LEDs of
the target robot is randomly toggled, and its state is stored. During data
collection, we keep the turret at a fixed relative orientation w.r.t. the base
of the robot, gathering images at 3 fps and the precise pose of the robots
using a motion-tracking system featuring 18 infra-red cameras.

In total, we collected 37k samples over two recording sessions lasting
approximately 1 hour each. The samples are divided into 34k for the unlabeled
training set $\mathcal{T}_{u}^{a}$, out of which only 7k have the robot
visible (22%) in them, 1k for the labeled training set $\mathcal{T}_{\ell}$,
and 2k for the testing set $\mathcal{Q}$, the last two featuring the robot
always visible; we show samples from $\mathcal{T}_{u}^{a}$ in Figure 3.

###  IV-B Training Strategies

We devise different training strategies based on the availability of robot
pose labels. With no access to labels, we train the model with
$\mathcal{T}_{u}^{\nu}$ on the LED state estimation pretext task with
$\mathcal{L}_{\text{led}}$, learning features that are also useful for pose
estimation; additionally, we explore the effectiveness of the LED-based
pretext task by training with the entire unlabeled training set
$\mathcal{T}_{u}^{a}$, including the predominant type of image featuring no
robot visible (88%).

We compare our pretext strategy with Ablation-CAM, a gradient-free CAM
technique producing a score for each pixel of the input image. High scores are
assigned to areas of the image responsible for making the model predict the
image class. In weakly supervised learning, this technique is used to localize
objects from a pre-trained classification model [12]. This strategy involves
training a custom MobileNet-V2 model [34], featuring 380k parameters, on the
LED state estimation pretext task with $\mathcal{T}_{u}^{\nu}$. Then, the
model is fed to Ablation-CAM to generate the robot image-space position based
on the four class activation maps (one for each LED). Given these maps, we
obtain the robot’s position in the image as the average coordinates of the
pixel with maximum value within each map.

Assuming access to a limited amount of labeled data, the most straight-forward
strategy is to directly train with $\mathcal{T}_{\ell}$ on the pose task loss
$\mathcal{L}_{\text{task}}$, representing a baseline. We compare this baseline
with the strategy that takes the pretrained model on the LED state estimation
pretext task and transfers its skills to the downstream or end task, training
with $\mathcal{T}_{\ell}$ on the pose task loss $\mathcal{L}_{\text{task}}$.
Additionally, we compare it against a different pretext approach of
Contrastive Language-Image Pre-training (CLIP). CLIP is a vision-language
model trained on a large corpus of data to learn a similar encoding for images
and associated captions, whose performance has been shown to outperform
supervised counterparts on multiple tasks [13]. Specifically, we consider
features extracted by the image encoder, and train a small feed forward neural
network with $\mathcal{T}_{\ell}$ on the pose task loss
$\mathcal{L}_{\text{task}}$ to predict the robot pose from CLIP’s features.

Finally, we consider an upperbound model trained with
$\mathcal{T}_{u}^{*}\cup\mathcal{T}_{\ell}$ on the pose task loss
$\mathcal{L}_{\text{task}}$, representing the best performance achievable with
our setup under the assumption of having unlimited access to robot pose
labels, even for $\mathcal{T}_{u}^{*}$ marked with an asterisk to denote the
inclusion of pose labels.

###  IV-C Neural Network Training

In our experiments, we consider the pose of a ground robot; as such, we only
consider the model performance on the heading $\psi$ and modify
$\mathcal{L}_{\text{ori}}$ accordingly. Additionally, we estimate the state of
$k=4$ LEDs and set the maximum distance parameter $d_{\text{max}}=5$ meters,
as robots do not exceed this relative distance in the collected data. All
strategies train on their respective datasets for 100 epochs with the Adam
optimizer, using a cosine annealing learning rate schedule starting at
$10^{-3}$ and decaying to $10^{-5}$ at the end of the training, and a batch
size of 64 samples. We employ the following data augmentations to increase the
variability of the images: additive simplex noise; random translation and
rotation ($\pm$ 64 px, $\pm$ $None$); and random hue shift, brightness and
contrast. FCN models produce output maps of size $w^{\prime}\times
h^{\prime}=80\times 45$ pixels; they are evaluated using weights $\bm{\theta}$
at the last epoch of training with the exception of upperbound, which reaches
its best performance after 40 epochs.

###  IV-D Evaluation Metrics

Models trained using the different strategies are evaluated on the testing set
$\mathcal{Q}$. For the LED state estimation task, we consider the area under
the receiver-operator characteristic curve (AUC) averaged over the four LEDs.
An ideal model has an AUC of 100%, while a naive classifier scores 50%. We
introduce an evaluation metric for each of the pose task losses: for the 2D
detection task, we report the median euclidean distance between ground truth
$uv$ and predicted $\widehat{uv}$ pixel position of the robot in the image
plane $E_{uv}$; for the distance task, we report the median absolute
difference of ground truth $d$ and predicted $\hat{d}$ relative robot distance
$E_{d}$; and for the orientation task, we report the median circular distance
between ground truth $\psi$ and predicted $\hat{\psi}$ robot heading
$E_{\psi}$. The circular distance measures the difference between two angles
accounting for the discontinuity at zero. Additionally, we consider the median
of the euclidean distance of the ground truth $xyz$ and predicted
$\widehat{xyz}$ 3D position of the robot $E_{xyz}$, computed from
$\widehat{uv}$ and $\hat{d}$ using the camera intrinsics, as described in
Section III.

##  V Results

In this section, we report a detailed analysis of our experimental results.
Specifically, we show that the proposed approach enables learning of the robot
detection task without position labels in Section V-A. The trained models are
then transferred to the 3D position and heading tasks, investigating how the
amount of labeled training data affects performance in Section V-B, and the
role of the pretext in learning the robot’s heading in Section V-C.

The robustness of the pretext approach is explored in Section V-D by training
on the unlabeled dataset $\mathcal{T}_{u}^{a}$ in which only 22% of the images
depict the target robot, whereas the rest only feature the background.
Finally, we test the generalization ability by deploying the model in never-
seen-before environments in Section V-E.

###  V-A LED Pretext Task Learns Robot Detection Without Labels

We report in the first panel of Table LABEL:tab:table the performance of our
pretext strategy compared with a dummy mean and the upperbound. Without having
access to robot pose labels, the pretext model has learned to detect the robot
in the image-plane simply by optimizing the LED-based pretext loss
$\mathcal{L}_{\text{led}}$. Remarkably, it achieves a median 2D position error
of only 51 pixels for an input image of $640\times 480$ pixels, a considerable
feat given the very limited supervision it received. This result indicates
that our strategy of weighting the LED maps with the position map, combined
with the inductive bias of FCNs, described in Section III, induces the model
to recognize the area of the image where information of the LEDs’ state is
found, i.e., the area where the robot is depicted.

Comparing pretext with Ablation-CAM, we note that our approach is outperformed
by Ablation-CAM on robot detection; however, this strategy does not lend
itself to skill transfer to a downstream task as it requires pre-training a
separate classification model. In addition, this strategy is not feasible for
real-time inference: on a NVIDIA RTX 2080, Ablation-CAM requires about 10
seconds per image, while our FCN model takes only 2.1 ms.

###  V-B LED Pretext Task Transfers Well to Pose Estimation

In the second panel of Table LABEL:tab:table, we compare the performance of
the baseline strategy with the downstream one, the only difference being the
initial weights: for baseline they are randomly initialized, while for
downstream we use the weights of the pretext model. Additionally, we
investigate how the size of the labeled training set affects the performance
by training the two strategies with 10, 100 or 1000 samples from
$\mathcal{T}_{\ell}$; we represent these sets respectively as
$\mathcal{T}_{\ell}^{10}$, $\mathcal{T}_{\ell}^{100}$, and
$\mathcal{T}_{\ell}^{1000}$. Regardless of the amount of labels, the
downstream model outperforms the baseline counterpart on all metrics; in
particular, the two score closest when training on
$\mathcal{T}_{\ell}^{1000}$, where the downstream model achieves a
statistically significant111P-values computed using the one tailed Welch’s
T-test on four replicas. improvement on the median $uv$ error of 11 pixels,
p-value=0.005, and on $\psi$ by $None$, p-value$<$0.001.

More interestingly, the downstream model trained with
$\mathcal{T}_{\ell}^{100}$ achieves the same performance on $uv$ of the
baseline model trained with $10\times$ the amount of labeled data, and the
downstream model trained with $\mathcal{T}_{\ell}^{1000}$ reduces the gap to
just 4 pixels of $uv$ error with the upperbound model, which is trained on 35k
labeled samples. Baseline models trained on $\mathcal{T}_{\ell}^{10}$ and
$\mathcal{T}_{\ell}^{100}$ perform equal or worse to the dummy mean model,
while the downstream model trained on $\mathcal{T}_{\ell}^{100}$ outperforms
dummy on all metrics and the downstream model trained on
$\mathcal{T}_{\ell}^{10}$ on all metrics except for $\psi$. Comparing with
CLIP demonstrates that our LED pretext better captures geometrical information
about the robot; instead, CLIP’s language-image pretext does not lend itself
well to pose estimation, and further lacks the inductive bias that our FCN
architecture posses, resulting in a worse performance than baseline trained on
the same data.

On the 3D position, the downstream model consistently outperforms the
respective baseline model across all percentages of $\mathcal{T}_{\ell}$ in a
statistically significant manner, with the closest example being of models
trained on $\mathcal{T}_{\ell}^{1000}$ where p-value=0.013.

Figure 4: Predicted LED maps by the pretext model trained on random 3.5k
samples from $\mathcal{T}_{u}^{\nu}$. From left to right, input image, left
LED map, and right LED map. Top image depicts the robot with left LED visible
and turned on; bottom image depicts right LED visible and turned off. Position
map cells with low probability of having a robot are depicted in gray.
Predicted LED state scalars are reported on the top right corners of the LED
maps. Figure 5: Six images from unseen environments and predicted robot’s
bounding boxes (red) generated by the downstream model trained on
$\mathcal{T}_{\ell}^{1000}$.

###  V-C LED Pretext Task Captures Robot Heading

So far, we considered each LED to be independent from the others and
speculated that this helps the pretext in learning useful features for the
robot’s heading. In the following, we address this point with an experiment in
which we consider the downstream training strategy using a subset of samples
of $\mathcal{T}_{u}^{\nu}$. We compare two models pretrained on the pretext
task: the first uses 3.5k samples where the left and right turret LEDs have
the same state, while the second uses 3.5k random samples from the same
dataset; the models are then transferred to the downstream task of pose
estimation using $\mathcal{T}_{\ell}^{1000}$. We report a median heading
estimation error of $None$ for the downstream model trained with synchronized
LEDs, and an error of $None$ for the downstream model trained with all
possible LEDs combination. Using the same statistical test as in Section V-B,
we report a statistically significant improvement on $\psi$ w.r.t. the
synchronized LEDs pretext training, with a p-value of 0.003 obtained from four
replicas of the experiment.

To further highlight the understating of the robot’s heading achieved with the
LED-based pretext training, we show in Figure 4 the left and right LED maps
when the pretext model is fed images with the robot placed on its side. The
maps for the visible LED are very consistent in its values, showing high
confidence, while the maps for the invisible LED are divergent, showing
uncertainty about the state; this indicates that our strategy does allow a
model to capture the robot’s orientation.

###  V-D LED Pretext Task is Robust to Images Without Robots

In the last panel of Table LABEL:tab:table, we report the performance of our
approach when considering the entirety of $\mathcal{T}_{u}^{a}$, which
features the robot visible only for 22% of images, based on trajectories of
the random controller described in Section IV-A. The median $uv$ error of the
pretext and downstream models are in line with their counterparts trained
using only images with visible robot of $\mathcal{T}_{u}^{\nu}$, highlighting
the strength of this simple approach when applied to collected data without
any filtering. The robot heading and distance estimation suffer from training
with a large quantity of images with no robot visible, degrading the
performance of downstream models.

The notable exception is the downstream-$a$-10 model, which shows large
instability during training and has a higher error than the downstream-10
model, at 76 pixels. The cause is the different $\bm{\hat{P}}$ map’s behavior
in the pretext and downstream models: in the former case, the $\bm{\hat{P}}$
map activates over a large area around the center of the robot; in the latter,
the activations are more punctual and centered on the robot’s body. By fine-
tuning the model on the downstream task, the position map $\bm{\hat{P}}$
transitions from a coarser and broader response to a more punctual one.
Transferring the model’s skills from the pretext to the downstream pose task
using only the 10 samples contained in $\mathcal{T}_{\ell}^{10}$ is not enough
to correctly drive the optimization, whereas more samples are enough.

###  V-E LED Pretext Task Generalizes to Unseen Environments

To test the generalization ability of our approach and the effect of the LEDs’
state on pose estimation, we show in Figure 5 the prediction of the downstream
model trained with $\mathcal{T}_{\ell}^{1000}$ on data collected in never-
seen-before environments. Despite the different visual appearance of
environments, the model correctly predicts the robot pose. The environments
highlight the increase in difficulty when estimating the robot’s distance and
heading, which show larger errors than image-space detection. Failure cases
occur when the robot is further away than the maximum of 5 meters of the
training set and when it is partially visible in the field of view.

##  VI Conclusions

We presented a self-supervised learning approach for peer-to-peer robot pose
estimation, leveraging robot LEDs to define a pretext task in order to learn
useful features for pose estimation. By predicting the state of LEDs from a
given image, our approach improves in the estimation ability when compared to
a baseline trained using the same amount of labeled data.

Results show that the approach is able to capture the 3D position and heading
of ground robots, even when trained on images that feature the robot visible
only 22% of the times. It also shows good generalization ability to never-
seen-before environments.

Interestingly, our FCN model trained on the LED pretext using the attention-
like mechanism has led the model to learning robot localization in images
without using ground truth pose labels with a fair accuracy. Future work will
focus on exploring pose estimation without ground truth labels, improving the
presented results in terms of performance, and integrating additional
supervision sources.

## References

  * [1] M. Dorigo, G. Theraulaz, and V. Trianni, “Swarm robotics: Past, present, and future,” _IEEE Point of View_ , vol. 109, no. 7, pp. 1152–1165, 2021.
  * [2] M. Vrba, D. Heřt, and M. Saska, “Onboard marker-less detection and localization of non-cooperating drones for their safe interception by an autonomous aerial system,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 4, pp. 3402–3409, 2019.
  * [3] B. Mishra, D. Garg, P. Narang, and V. Mishra, “Drone-surveillance for search and rescue in natural disaster,” _Elsevier Computer Communications_ , vol. 156, pp. 1–10, 2020.
  * [4] K. McGuire, C. De Wagter, K. Tuyls, H. Kappen, and G. C. de Croon, “Minimal navigation solution for a swarm of tiny flying robots to explore an unknown environment,” _Science Robotics_ , vol. 4, no. 35, p. eaaw9710, 2019.
  * [5] L. A. Nguyen, T. L. Harman, and C. Fairchild, “Swarmathon: a swarm robotics experiment for future space exploration,” in _IEEE International Symposium on Measurement and Control in Robotics_ , 2019, pp. B1–3.
  * [6] D. Dias, R. Ventura, P. Lima, and A. Martinoli, “On-board vision-based 3d relative localization system for multiple quadrotors,” in _IEEE International Conference on Robotics and Automation_ , 2016, pp. 1181–1187.
  * [7] G. Vásárhelyi, C. Virágh, G. Somorjai, T. Nepusz, A. E. Eiben, and T. Vicsek, “Optimized flocking of autonomous drones in confined environments,” _Science Robotics_ , vol. 3, no. 20, p. eaat3536, 2018.
  * [8] K.-C. Weng, S.-T. Lin, C.-C. Hu, R.-T. Soong, and M.-T. Chi, “Multi-view approach for drone light show,” _Springer The Visual Computer_ , vol. 39, no. 11, pp. 5797–5808, 2023.
  * [9] L. Jing and Y. Tian, “Self-supervised visual feature learning with deep neural networks: A survey,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2020.
  * [10] M. Nava, N. Carlotti, L. Crupi, D. Palossi, and A. Giusti, “Self-supervised learning of visual robot localization using led state prediction as a pretext task,” _IEEE Robotics and Automation Letters_ , vol. 9, no. 4, pp. 3363–3370, 2024.
  * [11] J. Long, E. Shelhamer, and T. Darrell, “Fully convolutional networks for semantic segmentation,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2015, pp. 3431–3440.
  * [12] D. Zhang, J. Han, G. Cheng, and M.-H. Yang, “Weakly Supervised Object Localization and Detection: A Survey,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 44, pp. 5866–5885, 2022.
  * [13] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, _et al._ , “Learning transferable visual models from natural language supervision,” in _PMLR International Conference on Machine Learning_ , 2021, pp. 8748–8763.
  * [14] M. Saska, T. Baca, J. Thomas, J. Chudoba, L. Preucil, T. Krajnik, J. Faigl, G. Loianno, and V. Kumar, “System for deployment of groups of unmanned micro aerial vehicles in gps-denied environments using onboard visual relative localization,” _Springer Autonomous Robots_ , vol. 41, no. 4, pp. 919–944, 2017.
  * [15] H. Yu, Q. Fu, Z. Yang, L. Tan, W. Sun, and M. Sun, “Robust robot pose estimation for challenging scenes with an rgb-d camera,” _IEEE Sensors Journal_ , vol. 19, no. 6, pp. 2217–2229, 2018.
  * [16] T. E. Lee, J. Tremblay, T. To, J. Cheng, T. Mosier, O. Kroemer, D. Fox, and S. Birchfield, “Camera-to-Robot Pose Estimation from a Single Image,” in _IEEE International Conference on Robotics and Automation_ , 2020, pp. 9426–9432.
  * [17] J. Lu, F. Richter, and M. C. Yip, “Pose Estimation for Robot Manipulators via Keypoint Optimization and Sim-to-Real Transfer,” _IEEE Robotics and Automation Letters_ , vol. 7, pp. 4622–4629, 2022.
  * [18] E. Jang, C. Devin, V. Vanhoucke, and S. Levine, “Grasp2vec: Learning object representations from self-supervised grasping,” in _PMLR Conference on Robot Learning_ , 2018, pp. 99–112.
  * [19] X. Deng, Y. Xiang, A. Mousavian, C. Eppner, T. Bretl, and D. Fox, “Self-supervised 6d object pose estimation for robot manipulation,” in _IEEE International Conference on Robotics and Automation_ , 2020, pp. 3665–3671.
  * [20] S. Li, C. De Wagter, and G. C. De Croon, “Self-supervised monocular multi-robot relative localization with efficient deep neural networks,” in _IEEE International Conference on Robotics and Automation_ , 2022, pp. 9689–9695.
  * [21] I. Radosavovic, T. Xiao, S. James, P. Abbeel, J. Malik, and T. Darrell, “Real-world robot learning with masked visual pre-training,” in _PMLR Conference on Robot Learning_ , 2023, pp. 416–426.
  * [22] M. Nava, A. Paolillo, J. Guzzi, L. M. Gambardella, and A. Giusti, “Learning visual localization of a quadrotor using its noise as self-supervision,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 2218–2225, 2022.
  * [23] M. Zhang, Y. Zhou, J. Zhao, Y. Man, B. Liu, and R. Yao, “A survey of semi-and weakly supervised semantic segmentation of images,” _Springer Artificial Intelligence Review_ , vol. 53, pp. 4259–4288, 2020.
  * [24] S. Woo, J. Park, J.-Y. Lee, and I. S. Kweon, “Cbam: Convolutional block attention module,” in _European Conference on Computer Vision_ , 2018, pp. 3–19.
  * [25] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, _et al._ , “An image is worth 16x16 words: Transformers for image recognition at scale,” _International Conference on Learning Representations, Virtual Event_ , 2021.
  * [26] N. Pourian, S. Karthikeyan, and B. S. Manjunath, “Weakly supervised graph based semantic segmentation by learning communities of image-parts,” in _IEEE/CVF International Conference on Computer Vision_ , 2015, pp. 1359–1367.
  * [27] B. Zhou, A. Khosla, A. Lapedriza, A. Oliva, and A. Torralba, “Learning deep features for discriminative localization,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 2921–2929.
  * [28] H. G. Ramaswamy _et al._ , “Ablation-cam: Visual explanations for deep convolutional network via gradient-free localization,” in _IEEE/CVF Winter conference on applications of computer vision_ , 2020, pp. 983–991.
  * [29] H. Bilen and A. Vedaldi, “Weakly supervised deep detection networks,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 2846–2854.
  * [30] D. Pathak, P. Krahenbuhl, and T. Darrell, “Constrained convolutional neural networks for weakly supervised segmentation,” in _IEEE/CVF International Conference on Computer Vision_ , 2015, pp. 1796–1804.
  * [31] Z. Ma, M. Yuan, J. Gu, W. Meng, S. Xu, and X. Zhang, “Triple-strip attention mechanism-based natural disaster images classification and segmentation,” _Springer The Visual Computer_ , vol. 38, no. 9, pp. 3163–3173, 2022.
  * [32] Y. Liang, Z. Chen, D. Lin, J. Tan, Z. Yang, J. Li, and X. Li, “Three-dimension attention mechanism and self-supervised pretext task for augmenting few-shot learning,” _IEEE Access_ , 2023.
  * [33] S. Gupta, S. Lakhotia, A. Rawat, and R. Tallamraju, “Vitol: Vision transformer for weakly supervised object localization,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 4101–4110.
  * [34] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen, “Mobilenetv2: Inverted residuals and linear bottlenecks,” in _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 4510–4520.


# On the Relational Translation Method for Propositional Modal Logics††thanks:
Supported in part by the National High Technology Program under grant No.
863-306-05-03-3.

Jian Zhang
Laboratory for Computer Science
Institute of Software
Chinese Academy of Sciences
P.O.Box 8718, Beijing 100190, P.R. China

(December 2021††thanks: Reprinted (with a few minor changes) with permission
from Technical Report ISCAS-LCS-96-12, Laboratory of Computer Science,
Institute of Software, Chinese Academy of Sciences, Dec. 1996. Some of the
results were published as a short paper in Chinese: “A Translation Approach to
Modal Logic Reasoning”, Computer Research & Development, Vol. 35, No. 5,
pp.389–392, 1998.)

###### Abstract

One way of proving theorems in modal logics is translating them into the
predicate calculus and then using conventional resolution-style theorem
provers. This approach has been regarded as inappropriate in practice, because
the resulting formulas are too lengthy and it is impossible to show the non-
theoremhood of modal formulas. In this paper, we demonstrate the practical
feasibility of the (relational) translation method. Using a state-of-the-art
theorem prover for first-order predicate logic, we proved many benchmark
theorems available from the modal logic literature. We show the invalidity of
propositional modal and temporal logic formulas, using model generators or
satisfiability testers for the classical logic. Many satisfiable formulas are
found to have very small models. Finally, several different approaches are
compared.

##  1 Introduction

Modal logics have been studied by many researchers in computer science and
artificial intelligence. There are roughly two classes of methods for
automated reasoning in these logics. With the translational approach, we
transform modal formulas to first-order predicate logic (FOPL) formulas and
then use existing tools for the classical logic. Alternatively, we can design
tools specifically for modal logics. Such methods are classified as the direct
approach. They include, among others, semantic tableaux, modal resolution, and
matrix-based procedures. See, for example, [1, 5, 22].

The translational approach can be further divided into syntactic and semantic
methods [16]. To use the syntactic method, we introduce a special unary
predicate $P$ which means its argument is provable, and translate the axioms
and rules into classical logic. This method can only be applied to
propositional modal logics. On the other hand, the semantic methods are based
on Kripke semantics. Such a method is applicable to first-order modal logics,
but properties of the accessibility relation should be defined by a finite set
of sentences in predicate logic. This can be done in a number of ways. In the
standard way [16], we introduce a special binary predicate $R$ to describe the
accessibility relation between the possible worlds. This is now called
relational translation. In addition, there are so-called functional
translation and semi-functional  translation [18, 17].

The relational translation approach is very simple and quite general. It can
deal with many modal logics, and it benefits from the power of existing tools
for the classical logic. But there are also some problems with it. To quote
Goré [8] (page 2), “by translating into first order logic, the translational
methods immediately surrender the decidability of the propositional modal
logic they translate.” Another problem is that, the result of translation is
usually a complicated formula, which makes its proof difficult to find.
Ohlbach and Weidenbach [19] gave the following example:

Prove that $(\Diamond\Box p\leftrightarrow\Diamond\Box\Diamond\Box p)$ is
valid in KD45.

Using the standard translation method and the popular resolution-style prover
OTTER 3.0 [13], they failed in finding a proof.

For these reasons, the (relational) translation method has been neglected by
many researchers. Is it really that bad? Our experiments show that it is quite
competitive. In this paper, we shall describe some of the results. We suggest
using both theorem provers and counterexample finders to decide the validity
of modal formulas. In addition, we study the problem of satisfying
propositional temporal logic formulas.

##  2 Translating Normal Modal Logics

###  2.1 Propositional Normal Modal Logics

We first review some relevant definitions and facts. For more details, see [2,
10]. There are many modal logic systems. But in this paper, we shall consider
only normal modal logics.

The smallest normal system is called K. It can be extended by defining
additional axioms. The most well-known axiom schemas include D, T, B, 4, 5.
There are only 15 distinct normal systems (including K itself) produced by
taking the schemas (as axioms) in all combinations. They are named K, KD, KT4,
and so on. Among them, KT4 and KT5 are also known as S4 and S5, respectively.

The semantics of modal logics is often defined in terms of the possible worlds
structures. Many propositional modal systems have the finite model property,
which means, every non-theorem is false in some finite model. This property
implies decidability, if the logic is finite axiomatizable. It is well known
that each of the above 15 modal logics has the finite model property.
Moreover, in some systems (e.g. S5), any satisfiable formula can be satisfied
in a small finite model (whose size does not exceed the length of the
formula).

###  2.2 The Relational Translation Method

Roughly speaking, the modal operators $\Box$ and $\Diamond$ correspond to
universal and existential quantifiers in FOPL respectively. There is a
standard way of translating modal formulas into FOPL formulas. To do so, we
add a ‘world’ argument to each proposition, and introduce a new binary
predicate $R$ to describe the accessibility relation between worlds. If the
current world is $w$, then the formula $\varphi$ will be translated to
$Tr(\varphi,w)$, which means $\varphi$ is true at $w$. The basic translation
rules are defined inductively as follows:

$\displaystyle Tr(p,w)$ $\displaystyle~{}\equiv~{}p(w)$ $\displaystyle
Tr(\neg\psi,w)$ $\displaystyle~{}\equiv~{}\neg Tr(\psi,w)$ $\displaystyle
Tr(\psi_{1}\wedge\psi_{2},w)$ $\displaystyle~{}\equiv~{}Tr(\psi_{1},w)\wedge
Tr(\psi_{2},w)$ $\displaystyle Tr(\Box\psi,w)$
$\displaystyle~{}\equiv~{}\forall v(R(w,v)\rightarrow Tr(\psi,v))$
$\displaystyle Tr(\Diamond\psi,w)$ $\displaystyle~{}\equiv~{}\exists
v(R(w,v)\wedge Tr(\psi,v))$

where $v$ is a new ‘world’ variable. The proposition $p$ in the original
formula becomes a unary predicate. For example, $Tr(\Diamond\Box p,o)$ is the
formula

$\exists w(R(o,w)\wedge\forall v(R(w,v)\rightarrow p(v)))$

The following theorem [16, 15] forms the basis of the relational translation
method.

Theorem. A formula $\varphi$ is valid in a modal logic system $S$ if and only
if $Ax(S)\rightarrow\forall wTr(\varphi,w)$ is valid in first-order predicate
logic, where $Ax(S)$ is a set of axioms describing properties of the
accessibility relation.

For example, $(\Box p\rightarrow\Diamond p)$ is valid in KT, because the
sentence

$\displaystyle\forall x$ $\displaystyle R(x,x)~{}\rightarrow$
$\displaystyle\forall w$ $\displaystyle(\forall v(R(w,v)\rightarrow
p(v))~{}\rightarrow~{}\exists v(R(w,v)\wedge p(v)))$

is a theorem in the predicate calculus.

###  2.3 A Concurrent Program as the Decision Procedure

The concurrent program in Algorithm 1 consists of a theorem proving process
($P_{1}$) and a model finding process ($P_{2}$). The theorem proving process
can be based on any refutationally complete proof procedure. To find a model
of some fixed size, one can either use a decision procedure for the classical
propositional calculus (such as the Davis-Putnam algorithm) or use a finite
model search program for the first-order predicate logic. The input parameter
$\varphi$ is a propositional modal logic formula and $S$ is a normal modal
logic system.

We assert that the concurrent program can serve as a decision procedure for
many propositional modal logics like K, KT, KD, S4, …. Such a modal system
should possess the finite model property, and the accessibility relation
should be characterized by a finite set of sentences in first-order predicate
logic. The program terminates under the fairness assumption. (It is unfair if
one process, e.g., the theorem prover, never has a chance to be executed.)

Input: $\varphi$, $S$

cobegin

$\phi:=Ax(S)\rightarrow\forall w\ Tr(\varphi,w)$ ;

$P_{1}::$

repeat

apply a suitable set of inference rules to $\phi$;

until  _(contradiction is deduced)_ ;

kill$(P_{2})$;

$P_{2}::$

var $n=0$;

repeat

$n:=n+1$;

find an $n$-element model of $\phi$;

until  _(a model is found)_ ;

kill$(P_{1})$;

coend

Algorithm 1 The decision procedure CDP

##  3 Experimental Results

For non-classical logics, there are not so many automated reasoning tools and
test problems. Here we describe some experimental results on the benchmarks
used by other authors [1, 3, 9, 6]. We shall not elaborate on the programs’
performances, because they are affected by several factors such as the data
structures and the programming languages. Moreover, not all timing information
are available in the related papers.

It is very easy to implement a tool for translating modal logic formulas. (The
translation time will be neglected.) To show the satisfiability of the
formulas, we may use various tools, such as FINDER, MGTP, LDPP, SATO, MACE and
SEM [20, 21, 23, 14, 25]. In the following, we only report the size of the
smallest model satisfying each formula. In many cases, the models are very
small, and can be easily found by any of the tools.

To prove modal theorems, we use the resolution-style theorem prover OTTER
3.0.4 [13], running on a SPARCstation 20 with 32 MB memory. We did not take
much advantage of OTTER’s special features to achieve high performances. It
was instructed to run in autonomous mode. However, since the prover is not so
good at proving “if-and-only-if” theorems [12], we broke each theorem of the
form $A\leftrightarrow B$ into two cases $A\rightarrow B$ and $B\rightarrow
A$. In such a way, Ohlbach and Weidenbach’s example mentioned earlier can be
proved within 2 seconds.

### Problem Set 1111Some early results on this set of problems were described
in [24].

In [1] Catach describes a tableaux-based program called TABLEAUX, and gives
the validity status of 31 formulas in 16 modal logic systems. The formulas are
very simple, and TABLEAUX completed all 496 tests in less than 1 minute. For
simplicity, we consider only the logics K, KD45, S4 and S5, which are very
important in knowledge representation and reasoning.

There are totally $31\times 4=124$ tests to be performed. Among these, 67
cases are validity proofs. With only a few exceptions, OTTER finds each proof
within 1 second. In the remaining 57 cases, we found the smallest structures
which show the invalidity of the formulas. Of these 57 countermodels, only 8
are of size 3. The others are of size 1 or 2.

For those formulas containing the equivalence connective, if we give them
directly to the translator and then to OTTER, it will be much more difficult
to find the proofs. For example, the last formula $\Box\Box
p\leftrightarrow\Diamond\Box p$ is valid in KD45. It takes OTTER about 2
minutes to find a proof. But each of the formulas $\Box\Box
p\rightarrow\Diamond\Box p$ and $\Diamond\Box p\rightarrow\Box\Box p$ can be
proved to be valid in less than 0.25 second.

### Problem Set 2

Demri [3] analyses several different strategies in a tableau-based S4 prover,
and compares them on a set of 9 valid formulas. Here we list 4 of them:

  * 4.

$\Box_{c}(\neg PC\rightarrow\Box_{b}\neg PC)$
$\wedge\Box_{c}\Box_{b}\Box_{a}(PC\vee PB\vee PA)$
$\wedge\Box_{c}\Box_{b}(\neg PB\rightarrow\Box_{a}\neg PB)$
$\wedge\Box_{c}\Box_{b}(\neg PC\rightarrow\Box_{a}\neg PC)$
$\wedge\Box_{c}\neg\Box_{b}PB$
$\wedge\Box_{c}\Box_{b}\neg\Box_{a}PA$
$\rightarrow\Box_{c}PC$

  * 5.

$\Diamond\Box(\Box(p\vee\Box q)\leftrightarrow(\Box p\vee\Box q))$

  * 6.

$\Diamond\Box((p\rightarrow q)\leftrightarrow F(q,F(p,q)))$
where $F(A,B)$ stands for $(\neg A\vee\neg\Diamond(A\wedge
B)\vee(B\wedge\Diamond(A\wedge\neg B)))$

  * 9.

$\Box(\Box(\Box p\rightarrow\Box(\Box q\rightarrow\Box
r))~{}\rightarrow~{}\Box(\Box(\Box p\rightarrow\Box q)\rightarrow\Box r))$

The first one is a multimodal formula, encoding McCarthy’s 3 Wise Men puzzle.
(C is the wisest man.) There are typos in formulas (6) and (9). The correct
versions are as follows [4]:

  * 6a.

$\Diamond\Box((p\rightarrow q)\leftrightarrow F(p,F(p,q)))$

  * 9a.

$\Box(\Box(\Box p\rightarrow\Box(\Box q\rightarrow\Box
r))~{}\rightarrow~{}\Box(\Box(\Box p\wedge\Box q)\rightarrow\Box r))$

Formulas (5) and (6a) are obtained from S5-valid formulas. A formula $\phi$ is
satisfiable in S5 iff $\Diamond\Box\phi$ is satisfiable in S4. Instead of
proving the validity of $\Diamond\Box\phi$ in S4, we prove directly $\phi$ is
valid in S5. As previously, we divide each “if-and-only-if” theorem into two
cases. In this way, 8 of the 9 theorems are easily proved, each requiring less
than 2 seconds. The exception is formula (6a) whose proof is found in about 1
minute.

It is interesting to note that some non-theorems are falsified in very small
models. For example, the negation of (6) and (9) are satisfied in 1-world
models. And, if we substitute $\Box_{b}PB$ for $\Box_{c}PC$ in formula (4),
then there is also a countermodel of size 1, which can be easily found by
exhaustive search.

### Problem Set 3

Recently Goré, Heinle and Heuerding [9] studied the relations between some
propositional normal modal logics, using the Logics Work Bench (LWB). As a
side-effect of this work, they collected a database of theorems which can be
used to test modal theorem provers.

LWB has automated proof procedures for only a few modal logics, namely, K, KT,
KT4, KT45 and KW. To deal with extensions of these logics, one can add some
modalised instances of the new axioms to the premises. The user has to provide
the appropriate instances. For more details about this technique, see [9].

In the appendix of [9], 72 K-theorems are listed. Most of them are easy for
OTTER to prove, but there are also some difficult ones. The results are
summarized in the following table.

OTTER time | number of theorems
---|---
<10 sec. | 51
10-100 sec. | 4
100-1000 sec. | 5
>1000 sec. | 12

So about 3 quarters of the theorems can be proved within 2 minutes. The 12
difficult formulas are very complicated. Some of them can be easily proved if
we work in a different modal system rather than in K. For example, using our
translation tool and OTTER, we can prove that $M\rightarrow Pt$ is valid in K4
within 10 seconds. Here $M$ and $Pt$ stand for the following two formulas:

$M~{}\equiv~{}\Box\Diamond p\rightarrow\Diamond\Box p\ \ \ \ \
Pt~{}\equiv~{}\Box(p\vee\Diamond p)\rightarrow\Diamond(p\wedge\Box p)$

Instead of proving the theorem directly, Goré, Heinle and Heuerding prove the
following K-theorem:

$\phi_{1}\wedge\phi_{2}\wedge\phi_{3}\wedge M\rightarrow Pt$

where $\phi_{1}$ is an instance of _4_ , $\phi_{2}$ and $\phi_{3}$ are
instances of $\Box$_4_. The resulting formula is quite lengthy, and OTTER has
difficulty finding a proof for it. I am not indicating that the “modalised
instance” technique is not useful. But the generality and power of the
translation approach should be emphasized. Of course, a powerful prover for
the predicate calculus is very important.

Based on the formulas given in [9], we also examined some conjectures which
are not valid in K. They are usually falsified in very small Kripke
structures. The following are some examples:

formula | size of structure
---|---
$M\rightarrow Pt$ | 2
$H\rightarrow L$ | 3
$H^{+}\rightarrow L^{+}$ | 2
$L\rightarrow L^{+}$ | 2
$L^{++}\rightarrow L^{+}$ | 2
$Dum4\rightarrow Dum$ | 2

The formulas $H$, $H^{+}$, $L$, $L^{+}$ and $L^{++}$ are defined as follows:

$\displaystyle H$ $\displaystyle~{}\equiv~{}(\Box(p\vee q)\wedge\Box(\Box
p\vee q)\wedge\Box(p\vee\Box q))\rightarrow(\Box p\vee\Box q)$ $\displaystyle
H^{+}$ $\displaystyle~{}\equiv~{}(\Box(\Box p\vee q)\wedge\Box(p\vee\Box
q))\rightarrow(\Box p\vee\Box q)$ $\displaystyle L$
$\displaystyle~{}\equiv~{}\Box((p\wedge\Box p)\rightarrow
q)\vee\Box((q\wedge\Box q)\rightarrow p)$ $\displaystyle L^{+}$
$\displaystyle~{}\equiv~{}\Box(\Box p\rightarrow q)\vee\Box(\Box q\rightarrow
p)$ $\displaystyle L^{++}$ $\displaystyle~{}\equiv~{}\Box(\Box
p\rightarrow\Box q)\vee\Box(\Box q\rightarrow\Box p)$ $\displaystyle Dum$
$\displaystyle~{}\equiv~{}\Box(\Box(p\rightarrow\Box p)\rightarrow
p)\rightarrow(\Diamond\Box p\rightarrow p)$ $\displaystyle Dum4$
$\displaystyle~{}\equiv~{}\Box(\Box(p\rightarrow\Box p)\rightarrow
p)\rightarrow(\Diamond\Box p\rightarrow(p\vee\Box p))$

To show that $Dum$ holds in KTDum2, Goré, Heinle and Heuerding proved the
K-theorem:

$\varphi_{1}\wedge\varphi_{2}\wedge\Box Dum2\rightarrow Dum$

where $\varphi_{1}$ and $\varphi_{2}$ are instances of $T$ and $\Box T$,
respectively. $Dum2$ is defined by :

$Dum2~{}\equiv~{}\Box(\Box(p\rightarrow\Box p)\rightarrow\Box
p)\rightarrow(\Diamond\Box p\rightarrow p)$

We tried to find a small reflexive structure falsifying $Dum2\rightarrow Dum$,
but failed. The formula turned out to be KT-valid, which can be proved in
about 1 second. So $Dum$ is implied by either $Dum2$ or $\Box Dum2$ in KT.

### Problem Set 4

Giunchiglia and Sebastiani [6] developed a SAT-based decision procedure for K,
called KSAT. It has been tested against a large number of randomly generated
3CNF modal formulas. We implemented a similar method for generating random
formulas, and found that quite some satisfiable formulas have very small
models. But the number of formulas that have been tested is not enough for us
to make any conclusion.

We did not spend much time on this set of problems. There are two reasons for
this. Firstly, the generated formulas usually contain repetitive or
complementary literals in the same clause, e.g. $\Box(p_{1}\vee p_{2}\vee\neg
p_{1})$. This problem is quite serious when there are only a few variables
(say, fewer than 5). Secondly, we are more interested in structured formulas.
But when only the average timings are recorded, some hard formulas (e.g.,
formulas of the form $A\leftrightarrow B$) can be hided in many other easy
formulas.

##  4 Satisfying Propositional Temporal Logic Formulas

Temporal logic was introduced into computer science by Amir Pnueli about 20
years ago. It is a convenient tool for specifying and verifying concurrent
programs [11]. There are many versions of temporal logic. For example, time
may be discrete or dense, a time point can have only one successor or several
successors. Here we consider the linear time temporal logic (LTL), where time
is modeled by the set of natural numbers. In addition to the ‘box’ and
‘diamond’ operators, LTL has such operators as ‘next-time’ and ‘until’.

Since LTL is based on the natural numbers, induction is needed to prove some
theorems. A resolution-style automatic theorem prover is not enough if we
translate LTL formulas into FOPL formulas. However, propositional LTL also has
the finite model property, i.e., a formula is satisfiable iff it has a model
consisting of a finite number of states. And we can still use model generation
tools in FOPL to find models of satisfiable propositional temporal logic
formulas. But we have to check the generated model can be translated into some
LTL model.

For simplicity, let us consider only the next-time operator. In this case, we
need a new unary successor operator $S$. The binary relation $R$ is reflexive
and transitive. In addition, we have to add such axioms as $R(x,S(x))$.

Let us give a simple example to illustrate the difference between models found
in this way and models obtained by the tableau method. Consider the formula
$\bigcirc\bigcirc\Box p$, where $\bigcirc$ denotes next-time. With the tableau
method, we get a 3-state model: $\\{s_{0},s_{1},s_{2}\\}$, where
$S(s_{0})=s_{1}$, $S(s_{1})=s_{2}$, $S(s_{2})=s_{2}$, $p$ can take any value
in the first two states, but it is true in $s_{2}$. In general, if there are
$k$ next-time operators, we shall get a $(k+1)$-state model. However, with the
translation method, a 1-state model is produced: $\\{s_{0}\\}$,
$S(s_{0})=s_{0}$, $p$ holds at $s_{0}$.

##  5 Related Work

As we mentioned in the introduction, there are quite some methods for the
automated reasoning in modal logics. But relatively few implementations are
available. The matrix method and the functional translation method require
specialized unification algorithms. In contrast, it is very easy to write a
relational translator.

Another advantage of the translational approach is its generality. It can be
applied to many modal logic systems. Changing from one system to another, we
need only modify the axioms. On the other hand, many other methods and tools
are designed for a few specific systems. For example, semi-functional
translation [17] and the technique described in [19] are most suitable for
serial modal logics like KD and KD45. Modal resolution rules are discussed in
[5], within 5 systems, i.e., K, Q, T, S4 and S5. The program LWB has built-in
proof procedures for 5 selected logics, and KSAT [6, 7] works only in K.
TABLEAUX can deal with many modal systems. But if one was to extend it with
new systems, new procedures (encoding the semantic properties) would have to
be added.

Tableau-based decision procedures can be used both to prove theorems and to
show the satisfiability of formulas. As we point out in the previous section,
the models found by our method are usually different from those generated by
tableau procedures. An example in linear time temporal logic has been given to
show the difference. For another example, the formula _4_. $\Box
p\rightarrow\Box\Box p$ is not valid in K. Catach [1] gives a 3-world
countermodel produced by the tableau-based procedure. But with our method, we
shall first find the smallest model having 2 worlds:

$R$ |  $w_{0}$ |  $w_{1}$ |  | $p$ |  $w_{0}$ |  $w_{1}$
---|---|---|---|---|---|---
$w_{0}$ |  $False$ |  $True$ |  |  |  $False$ |  $True$
$w_{1}$ |  $True$ |  $False$ |  |  |  |

where $w_{0}$ is the real world.

According to our experiences, many satisfiable formulas have very small
models. Thus it is practical to use model generation tools in the classical
logic to show the satisfiabiliy of propositional modal formulas. However, for
some modal logics (like K), there are some specially constructed formulas [10]
which are satisfiable only in exponential-size models. They present much
difficulty for methods based on the Kripke semantics. The program KSAT can
deal with such formulas efficiently [7].

##  6 Concluding Remarks

The (relational) translation technique has been known for a long time. But few
reports on its practical performances are available, and previously no one has
studied the generation of countermodels with this method. Our experiments show
that, the method is quite competitive. Without spending much effort, we can
prove a lot of theorems in many modal logics, using existing tools in the
classical logic. Moreover, by combining a theorem prover with a model
generator, we can decide the satisfiability as well as the validity of
propositional formulas. It is interesting that many non-theorems turn out to
have very small countermodels.

Compared with other methods, relational translation has some appealing
features. (See the previous section.) Theoretically, it provides decision
procedures for various important logics. Practically, we expect that it can
deal with a large number of formulas of reasonable sizes. It should be very
useful in those applications where first-order reasoning is inevitable, and in
the applications which have several modal operators belonging to different
systems.

It is certainly not true that the translational approach is better than other
approaches in all respects. The method has some drawbacks. But it is not so
weak as thought previously. Rather than proposing an entirely new method, we
try to identify and overcome some difficulties. The power of the translation
approach is largely dependent on the tools available in predicate calculus. In
our experiments, only OTTER (in its autonomous mode) was used to prove
theorems. This may not be the best choice. One can use other types of provers
(e.g., a nonclausal one) or exploit more features of OTTER to achieve better
performances. One can also develop special techniques for handling the
transitivity axiom or the seriality axiom (similar to that of [19]).

## References

  * [1] L. Catach, “TABLEAUX: A general theorem prover for modal logics,” J. of Automated Reasoning 7 (1991) 489–510.
  * [2] B.F. Chellas, Modal Logic: An Introduction, Cambridge University Press (1980).
  * [3] S. Demri, “Efficient strategies for automated reasoning in modal logics,” JELIA’94 (Logics in Al), LNAI 838 (1994) 182–197.
  * [4] S. Demri, private communication, Nov. 1996.
  * [5] P. Enjalbert and L. Farinas del Cerro, “Modal resolution in clausal form,” Theor. Comp. Sci. 65 (1989) 1–33.
  * [6] F. Giunchiglia and R. Sebastiani, “Building decision procedures for modal logics from propositional decision procedures – the case study of modal K,” CADE-13 (1996).
  * [7] F. Giunchiglia and R. Sebastiani, “A SAT-based decision procedure for ALC,” KR’96.
  * [8] R. Goré, Cut-free sequent and tableau systems for propositional normal modal logics. PhD thesis, Computer Laboratory, University of Cambridge, England (1992).
  * [9] R. Goré, W. Heinle and A. Heuerding, “Relations Between Propositional Normal Modal Logics: An Overview,” Technical Report TR-ARP-16-95, Automated Reasoning Project, Australian National University (1995).
  * [10] J.Y. Halpern and Y. Moses, “A guide to completeness and complexity for modal logics of knowledge and belief,” Artif. Intel. 54 (1992) 319–379.
  * [11] Z. Manna and A. Pnueli, The Temporal Logic of Reactive and Concurrent Systems: Specification, Springer-Verlag (1991).
  * [12] W. McCune, “OTTER 2.0”, CADE-10, LNAI 449, 663–664.
  * [13] W. McCune, “OTTER 3.0 Reference manual and guide,” Technical Report ANL-94/6, Argonne National Laboratory (1994).
  * [14] W. McCune, “A Davis-Putnam program and its application to finite first-order model search: Quasigroup existence problems,” Technical Report ANL/MCS-TM-194, Argonne National Laboratory (1994).
  * [15] R. Moore, Reasoning about Knowledge and Action, PhD Thesis, MIT, Cambridge, USA (1980).
  * [16] C.G. Morgan, “Methods for automated theorem proving in nonclassical logics,” IEEE Trans. Computers 25 (1976) 852–862.
  * [17] A. Nonnengart, “First-order modal logic theorem proving and functional simulation,” IJCAI-93, 80–85.
  * [18] H.J. Ohlbach, “Translation methods for non-classical logics - an overview,” Bulletin of IGPL 1 (1993) 69–91. Also: Technical Report MPI-I-93-225, Max-Planck-Institut für Informatik, Saarbrücken, Germany.
  * [19] H.J. Ohlbach and C. Weidenbach, “A note on assumptions about Skolem functions,” J. of Automated Reasoning 15 (1995) 267–275.
  * [20] J.K. Slaney, “FINDER: Finite domain enumerator – system description,” Proc. CADE-12 (1994) 798–801.
  * [21] J. Slaney, M. Fujita and M. Stickel, “Automated reasoning and exhaustive search: Quasigroup existence problems,” Computers and Mathematics with Applications 29 (1995) 115–132.
  * [22] L.A. Wallen, Automated Proof Search in Non-Classical Logics, The MIT Press (1990).
  * [23] H. Zhang and M. Stickel, “Implementing the Davis-Putnam algorithm by tries,” Technical Report, University of Iowa (1994).
  * [24] J. Zhang, Model Generation for Many-sorted Equations and Automated Reasoning in Modal Logics, Technical Report ISCAS-LCS-94-04, Institute of Software, Chinese Academy of Sciences, Beijing, China (1994).
  * [25] J. Zhang and H. Zhang, “Generating Models by SEM,” Proc. CADE-13 (1996).