# Commonsense Spatial Reasoning for Visually Intelligent Agents

Agnese Chiatti1 Gianluca Bardaro1 Enrico Motta1 Enrico Daga1
1Knowledge Media Institute, The Open University, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

Service robots are expected to reliably make sense of complex, fast-changing
environments. From a cognitive standpoint, they need the appropriate reasoning
capabilities and background knowledge required to exhibit human-like Visual
Intelligence. In particular, our prior work has shown that the ability to
reason about spatial relations between objects in the world is a key
requirement for the development of Visually Intelligent Agents. In this paper,
we present a framework for commonsense spatial reasoning which is tailored to
real-world robotic applications. Differently from prior approaches to
qualitative spatial reasoning, the proposed framework is robust to variations
in the robot’s viewpoint and object orientation. The spatial relations in the
proposed framework are also mapped to the types of commonsense predicates used
to describe typical object configurations in English. In addition, we also
show how this formally-defined framework can be implemented in a concrete
spatial database.

##  1 Introduction

In all cases where it is inconvenient or even dangerous for us to intervene,
there is an incentive to delegate tasks to service robots \- or robot
assistants: e.g., under the extreme conditions imposed by space explorations
(?), in hazardous manufacturing environments (?), or whenever social distance
needs to be maintained (?). Before delegating complex tasks to robots,
however, we need to ensure that they can reliably make sense of the stimuli
coming from their sensors. Autonomous sensemaking remains an open challenge,
because it requires not only to reconcile the high-volume and diverse data
collected from real-world settings (?), but also to actually understand these
data, going beyond mere pattern recognition (?; ?).

From a vision perspective, the problem of robot sensemaking becomes one of
enhancing the Visual Intelligence of service robots, i.e., their ability to
make sense of the environment through their vision system and epistemic
competences (?). Naturally, several epistemic competences are required to
build Visually Intelligent Agents (VIA). For instance, let us consider the
case of HanS, a Health & Safety robot inspector. HanS is expected to
autonomously detect potentially threatening situations, such as the fire
hazard posed by a sweater left to dry on top of an electric heater. To assess
the risk associated with this situation, HanS first needs to recognise the
sweater and the heater in question, i.e., it needs to exhibit robust object
recognition capabilities. It also needs spatial reasoning capabilities, to
infer that the sweater is touching the heater. Moreover, it also needs to know
that sweaters are made of cloth and that a piece of cloth clogging an electric
radiator can catch fire. The list goes on.

In (?), we identified a framework of epistemic requirements, i.e., knowledge
properties and reasoning capabilities which are needed to develop Visually
Intelligent Agents (VIA). To form hypotheses on which epistemic requirements
are more likely to significantly enhance the Visual Intelligence of a robot,
we also mapped these epistemic ingredients to the types of object
classification errors emerging from one of HanS’ scouting routines. This error
analysis highlighted that the majority of misclassifications could in
principle have been avoided, if the robot was capable of considering: (i) the
canonical size of objects, e.g., that mugs are generally smaller than bins, as
well as (ii) the typical Qualitative Spatial Relations (QSR) between objects.
For instance, a fire extinguisher may be mistaken for a bottle due to its
shape. However, the proximity of a fire extinguisher sign is a strong
indication that the observed object is in fact a fire extinguisher. This
element of typicality relates to the broader objective of developing AI
systems which can reason about what is plausible (?), i.e., which exhibit
common sense (?) and Intuitive Physics reasoning abilities (?; ?). Our most
recent findings (?) confirmed that combining state-of-the-art Machine Learning
methods with a component able to reason about object sizes improves the
robot’s object recognition performance. In this paper, we progress this line
of research by characterising commonsense QSR between objects.

The problem of representing spatial relations has been actively researched for
decades, producing many theoretical frameworks for autonomous spatial
reasoning (?). In robotics, semantic mapping (?; ?) and object anchoring
methods (?) have enabled linking the robot sensor data and symbolic knowledge
to the geometric maps modelling its environment. To combine the best of both
worlds, a number of approaches (?; ?; ?) have linked the spatial
representations within semantic maps to the higher-level formal definitions
provided by AI theories. In this paper, we propose a novel spatial reasoning
framework which extends the work in (?; ?), to account for variations in the
robot’s viewpoint and in the relative orientation of objects. Moreover, we
formally map the Qualitative Spatial Relations composing this framework to the
type of linguistic predicates used to describe commonsense spatial relations
in English, which are discussed within seminal theories of spatial cognition
(?; ?). Finally, we show how the proposed framework can be implemented in
state-of-the-art Geographic Information Systems (GIS), to support commonsense
spatial reasoning in real-world robotic scenarios.

##  2 Related work

Broadly speaking, spatial relations can be represented qualitatively - e.g., A
contains B - or quantitatively - e.g., the angle between A and B is $\theta$
(?). Following (?), Qualitative Spatial Relations (QSR) can be further
characterised as (i) metric, i.e., based on the metric distance between
objects (ii) topological, i.e., describing the neighbourhood of objects, and
(iii) directional, i.e., relative to the axis directions in a reference
coordinate system. The interested reader is referred to (?) for a foundational
review of qualitative spatial representations. Compared to quantitative
representations, qualitative representations are more similar to the types of
spatial predicates involved in natural language discourse. As a result,
qualitative spatial representations are easier to interpret and aid Human-
Robot Interaction (?; ?; ?). Moreover, they are more similar to the types of
linguistic predicates available within large-scale, general-purpose Knowledge
Bases (KB), such as those surveyed in (?). Crucially, they are also aligned
with the spatial predicates provided with benchmark image collections for
visual reasoning tasks, such as Visual Genome (?) and SpatialSense (?). Thus,
relying on qualitative representations has the potential to facilitate the
repurposing of these resources in robotic contexts, especially given the
paucity of comprehensive KBs for Visually Intelligent Agents (?).

Extensive efforts have been devoted to mapping the quantitative data collected
through the robot’s sensors to higher-level symbols describing a set of known
object classes and their attributes (?; ?; ?). These efforts have produced
intermediate representational models also known as semantic maps, i.e., maps
that contain, “in addition to spatial information about the environment,
assignments of mapped features to entities of known classes” (?). Further
approaches have been proposed, where the content of semantic maps is also
interpreted with respect to formal theories of qualitative spatial reasoning
(?; ?; ?). In general, spatial relations are expressed between object pairs,
where one of the two objects is considered as a reference, or landmark: e.g.,
bike near house. (?) have used Ring Calculus to represent the closeness of
objects. (?) have relied on ternary point calculus (?) to model directional
relations with respect to both the robot’s location and the location of the
reference object. Thus, the 3D regions occupied by objects are reduced to
point-like objects on the 2D plane. Moreover, (?) assumed that the robot’s
location does not change over time, and is always defined with respect to a
tabletop. Differently from (?), (?) represented directional relations by
comparing the 3D regions occupied by objects, through the halfspace-based
model of (?). However, this model is based on the assumption that the robot’s
viewpoint is always aligned both with the global coordinate system of the map
and with the inherent orientation of the observed objects. Thus, it is not
suitable to model mobile robots making sense of the environment during
navigation. In real-world scenarios, as the robot moves, its viewpoint changes
over time and the objects observed will be oriented differently. Thus, we
propose to combine the robot’s viewpoint and the orientation of the reference
object within a contextualised frame of reference. This contextualised frame
of reference allows us to define a contextualised 3D region, or Contextualised
Bounding Box, which represents the location of the object with respect to both
the robot’s viewpoint and the frame of reference of a landmark. Crucially, the
contextualised frame of reference and Bounding Box can be defined for any
combination of robot and landmark location, thus ensuring that this framework
can scale to many real-world robotic scenarios.

##  3 Proposed Framework

To define a spatial reasoning framework which satisfies the concrete
requirements of robot sensemaking, we extend the formal theory of spatial
reasoning by (?). Moreover, we map the obtained spatial relations to the
commonsense predicates used to describe spatial relations between objects in
English. These predicates are gathered from cognitive theories (?). By making
an explicit link between formal AI theories and informal linguistic
representations, we obtain a framework for commonsense spatial reasoning in
robotic scenarios.

#### Notation

In what follows, we model definitions as First Order Logic (FOL) statements.
We represent logic variables through lowercase letters and constants through
uppercase letters. We also use lowercase initials to denote functions, while
uppercase initials symbolise predicates. For instance, sReg is a function,
whereas Above is a predicate. Unless otherwise stated, free variables are
universally quantified. Finally, we use the standard notation (X, Y, Z) to
denote reference axes, while $x,y,z$ are used to refer to the spatial
coordinates with respect to those axes.

#### Spatial primitives

Our domain of discourse $\mathbb{D}$ is that of spatial objects, i.e.,
physical objects, “which have spatial extensions” (?). From this perspective,
a spatial object is represented in terms of the associated spatial region. In
particular, our spatial primitive is the concept of spatial point. Thus,
spatial regions are represented as sets of spatial points, $p$. Let $P$ be the
set of all spatial points, then, for each spatial object $o\in\mathbb{D}$, we
assume the existence of a function $sReg$ which, given $o$, returns the subset
of $P$ which includes all the points in the spatial region of $o$.

$\displaystyle\textit{SpatialObj}(o)\Rightarrow\textit{sReg}(o)\subseteq P$
(1)
$\displaystyle\textit{SpatialObj}(o)\Rightarrow\textit{sReg}(o)\neq\emptyset$
(2)

In particular, our focus is not on arbitrary collections of spatial points,
but rather on one-piece regions (?), i.e., on sets of internally connected
points:

$\displaystyle\textit{SpatialObj}(o)\Rightarrow\textit{ProperSR}(\textit{sReg}(o))$
(3)

To provide a formal definition of the concept of proper spatial region, we
need first to establish a spatial frame of reference.

#### Spatial Frame of Reference

A spatial object is characterised not only with respect to a spatial region
but also in terms of a reference coordinate system, also known as frame of
reference. A frame of reference consists of an origin point and of a set of
directed axes intersecting at the origin, $O$. In particular, modelling the 3D
space requires three reference axes $X,Y,Z$. Although spatial points and
spatial regions exist independently of the frame of reference, the
interpretation of these spatial primitives only makes sense in the context of
a frame of reference. Once we have defined a reference frame, we can interpret
spatial points as geometrical points, i.e., as coordinate triples in
$\mathbb{R}^{3}$. Let $GP$ be the set of all geometrical points in the
considered space:

$\displaystyle GP=\\{p|p=(x,y,z)\in\mathbb{R}^{3}\\}$ (4)

The identified frame of reference also has an associated granularity, i.e., an
infinitesimally small constant $D>0$ in $\mathbb{R}$, which defines the
minimum distance for two geometrical points to be considered as distinct
entities. Two geometrical points are then said to be adjacent iff their
geometrical distance is equal to $D$. To compute the distance between two
geometrical points, they have to be in the same frame of reference. Let
$d(gp,gp^{\prime})$ be a function which returns a real number indicating the
geometric distance between points $gp$ and $gp^{\prime}$. Then:

$\displaystyle\textit{Adj}(gp,gp^{\prime})\Leftrightarrow d(gp,gp^{\prime})=D$
(5)

The definition of proper spatial region then follows from the defined notion
of adjacency:

$\displaystyle\textit{ProperSR}(sr)\Leftrightarrow\forall gp[gp\in
sr\Rightarrow\textit{Conn}(gp,sr)]$ (6)
$\textit{Conn}(gp,sr)\Leftrightarrow\forall gp^{\prime}[gp^{\prime}\in
sr\wedge\\\ gp^{\prime}\neq gp]\Rightarrow\textit{ConnP}(gp,gp^{\prime})$ (7)
$\textit{ConnP}(gp_{1},gp_{2})\Leftrightarrow\textit{Adj}(gp_{1},gp_{2})\vee\\\
\exists
gp_{3}[\textit{Adj}(gp_{1},gp_{3})\wedge\textit{ConnP}(gp_{3},gp_{2})]$ (8)

In our model, we assume that the global spatial region, $GP$, is a fully-
connected set of points. Moreover, we assume that spatial regions can be
approximated through 3D boxes111In the case of large regions of negligible
thickness, such as floors, walls and ceilings, the spatial region reduces to a
2D surface.. This simplifying assumption is consistent with standard practice
in the literature (?; ?). Bounding boxes can have an arbitrary orientation
around the Z axis aligned with gravity, but their base is always parallel to
the XY plane. In particular, we consider the minimum bounding box which best
approximates the real volume occupied by an object and which is aligned with
its natural orientation (?). Let $b$ be a set of geometrical points which
contains the spatial region of $o$:

$\displaystyle\textit{BoundBox}(b,o)\Leftrightarrow\textit{sReg}(o)\subseteq
b\wedge b\subseteq GP$ (9)
$\textit{MinBoundBox}(b,o)\Leftrightarrow\textit{BoundBox}(b,o)\wedge\\\
\neg\exists b^{\prime}[\textit{BoundBox}(b^{\prime},o)\wedge b^{\prime}\subset
b]$ (10)

In this scenario, the environment navigated by a robot can also be modelled as
a spatial region including an arbitrary number of objects, i.e., as a global
spatial region. Consequently, the outer region of a spatial region, $sr$, is:

$\displaystyle\textit{outReg}(sr)=\\{gp|gp\in GP\wedge gp\notin sr\\}$ (11)

The frame of reference of the global region, $F_{g}$, is extrinsic, i.e.,
based on a reference point which is external to both an object and an
observer. $F_{g}$ remains fixed as the robot navigates the environment.
Conversely, the robot’s frame of reference, $F_{r}$, changes as the robot
moves. Thus, it is deitic, relative to the observer’s position. Consequently,
the location of objects at each point in time can be interpreted differently,
based on which frame of reference is considered. Within the formal spatial
reasoning frameworks of (?; ?), all the spatial relations between objects are
defined according to the same pre-defined frame of reference, whether it is an
extrinsic, deitic or intrinsic one, i.e., inherent to a specific object.

Differently from the latter relations, linguistic spatial predicates
implicitly refer both to (i) the location of whichever object is considered as
reference, and to (ii) the observer’s point of view (?). Similarly, a robot
would conclude that “A is on the left of B” based not only on the location of
objects A and B within $F_{g}$, but also on $F_{r}$. From a different
standpoint, A might appear on the right of B, for instance, or in front of it.
To model such cases, we introduce the notion of robot’s viewpoint,
$F_{r^{\prime}}$. Let $C_{o}$ be the centroid of the spatial region
representing object $o$. Then, $F_{r^{\prime}}$ is obtained by rotating
$F_{r}$ along $Z_{r}$, by an angle $\alpha$. Specifically, $\alpha$ is the
angle between $X_{r}$ and the imaginary line connecting the origin of $F_{r}$
with $C_{o}$. Let $F_{o}$ of origin $C_{o}$ and axes $X_{o},Y_{o},Z_{o}$ be
the intrinsic frame of reference of $o$, i.e., the frame of reference which is
aligned with the orientation of $o$. Then, the contextualised frame of
reference of the object, $F_{c}$, is the frame of reference of origin $C_{o}$
whose axes have the same orientation of the axes defining the robot’s
viewpoint, $F_{r^{\prime}}$ (Figure 1).

Based on $F_{c}$, we can construct a Contextualised Bounding Box (CBB), which
is obtained by aligning the minimum bounding box with $F_{c}$. Let
$\textit{rotZ}(b,\theta)$ be a function which returns the spatial region,
$sr$, obtained by rotating an input bounding box along $Z$ by an angle
$\theta$. Given a frame of reference $F_{c}$, then $\textit{yaw}(sr,F_{c})$
returns the angle between the intrinsic frame of reference of $sr$ and
$F_{c}$, along $Z$. Then, given $\pi/2$:

$\textit{IsCBB}(\textit{rotZ}(b,\theta),o)\Leftrightarrow\textit{MinBoundBox}(b,o)\wedge\\\
\exists\theta[\textit{mod}(\textit{yaw}(\textit{rotZ}(b,\theta),F_{c}),\pi/2)=0\wedge\neg\exists\theta^{\prime}\\\
[\textit{mod}(\textit{yaw}(\textit{rotZ}(b,\theta^{\prime}),F_{c}),\pi/2)=0\wedge\theta^{\prime}<\theta]]$
(12)

Namely, to construct CBB, we select the minimum angle $\theta$ so that the
value returned by the yaw function is divisible by $\pi/2$, i.e., the
remainder of their division, mod, is zero. There are always four possible
alignments of a bounding box, $b$, for which mod is zero. Thus, by selecting
the minimum angle among these four, we apply the transformation which is least
disruptive of the natural orientation of the object. Thanks to these newly-
defined spatial concepts, we can now map the metric, topological and
directional relations in (?; ?) to commonsense predicates expressed in natural
language.

Figure 1: The robot’s viewpoint, $F_{r^{\prime}}$, consists of an origin and
three axes $X_{r^{\prime}}$ (in red), $Y_{r^{\prime}}$ (in green) and
$Z_{r^{\prime}}$ (in blue). $F_{r^{\prime}}$ may not coincide with the frame
of reference characterising the global map, $F_{g}$, nor with the intrinsic
frame of reference of a certain object, $F_{o}$. As shown on the left-hand
side of the Figure, a spatial object is first modelled as the minimum 3D box
bounding the object. Then, $F_{r^{\prime}}$ is translated to the object’s
centroid to define a contextualised frame of reference $F_{c}$. Moreover, a
Contextualised Bounding Box (highlighted in blue) is generated, i.e., the
bounding box which requires the minimum rotation along the $Z$ axis to align
the minimum bounding box with $F_{c}$.

#### Metric spatial relations

Given two spatial objects $o_{1},o_{2}$ and two geometrical points
$gp_{1},gp_{2}$ where $gp_{1}\in o_{1}$ and $gp_{2}\in o_{2}$, we define the
distance between two geometrical points as the their Euclidean distance:

$\displaystyle
d(gp_{1},gp_{2})=\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}+(z_{1}-z_{2})^{2}}$

(13)

Then, the distance between two spatial objects is defined as the global
minimum of the pointwise distance function, $d$:

$[\textit{distance}(o_{1},o_{2})=d(gp_{1},gp_{2})]\Leftrightarrow gp_{1}\in
o_{1}\wedge gp_{2}\in o_{2}\wedge\\\ \forall gp_{3},gp_{4}[gp_{3}\in
o_{1}\wedge gp_{4}\in o_{2}]\Rightarrow d(gp_{3},gp_{4})>\\\ d(gp_{1},gp_{2})$
(14)

A distance threshold, $T$, can be then introduced, to represent closeness
between objects. That is, for a $T$ greater than or equal to the frame
granularity $D$ defined earlier:

$\displaystyle\textit{IsClose}(o_{1},o_{2})\Leftrightarrow\textit{distance}(o_{1},o_{2})\leq
T$ (15)

In particular, if the minimum distance between two objects equals $D$, then
the two objects touch:

$\displaystyle\textit{Touches}(o_{1},o_{2})\Leftrightarrow\textit{distance}(o_{1},o_{2})=D$
(16)

#### Topological spatial relations

Topological relations are spatial relations which are invariant under a
topological isomorphism, i.e., a function $f:X\to Y$ which preserves
neighbourhood relationships while mapping $X$ to $Y$. Although several
different qualitative representations of topological relations have been
proposed (?), here we focus on a subset of topological relations, namely on
the intersection and containment relations. As shown in the remainder of this
Section, this minimal subset of relations, combined with metric and
directional relations, is sufficient to cover all the commonsense spatial
relations required in the scenario of interest. First, based on our prior
definitions, two spatial regions, $sr,sr^{\prime}$ intersect iff they have at
least one geometrical point in common:

$\displaystyle\textit{Int}(sr,sr^{\prime})\Leftrightarrow\exists gp[gp\in
sr\wedge gp\in sr^{\prime}]$ (17)

We also define the spatial region representing the intersection between two
objects (i.e., the intersection between the associated spatial regions) as
follows:

$\displaystyle\textit{inter}(o1,o2)=\\{gp|gp\in\textit{sReg}(o1)\wedge
gp\in\textit{sReg}(o2)\\}$

(18)

Then, a special case of the intersection relation is the case where one
spatial region completely contains the other:

$\displaystyle\textit{ComplCont}(sr,sr^{\prime})\Leftrightarrow\forall
gp[gp\in sr^{\prime}\Rightarrow gp\in sr]$ (19)

Semantically, $o$ contains $o^{\prime}$ completely iff all the geometrical
points in the spatial region of $o^{\prime}$ are also members of the spatial
region of $o$.

#### Directional spatial relations

Differently from metric and topological relations, directional spatial
relations are interpreted differently based on the considered frame of
reference. (?) have proposed a qualitative representation for directional
relations where the region outside a 3D bounding box is partitioned into six
halfspaces, i.e., one halfspace for each semi-axis of $X,Y,Z$. Because we have
defined a global spatial region containing all geometrical points in the
robot’s environment, these halfspaces are also proper spatial regions, which
can be approximated through 3D bounding boxes. In particular, as in (?), they
can be modelled as 3D extrusions, obtained by multiplying the extent of the
object spatial region by a scaling factor $s\in\mathbb{R}$.

The coordinates of all geometrical points in the minimum bounding box are
bound to a minimum and maximum value, e.g., $x_{min}$ and $x_{max}$. Let
$X_{o}^{+}$ and $X_{o}^{-}$ be the positive and negative semi-axes of $X_{o}$
in $F_{o}$. Then, we define a function, hs, which returns the halfspace of an
input bounding box, given semi-axis, $X_{o}^{+}$, and frame of reference,
$F_{o}$:

$\textit{MinBoundBox}(mb_{1},o_{1})\Rightarrow\textit{hs}(mb_{1},X_{o}^{+},F_{o})=\\\
\begin{split}\\{gp\in\textit{outReg}(mb_{1})|&{}gp=(x,y,z)\textit{ w.r.t
}F_{o},\\\ &x_{max}\leq x\leq x_{max}+x_{max}\cdot s,\\\ &y_{min}\leq y\leq
y_{max},\\\ &z_{min}\leq z\leq z_{max}\\}\end{split}$ (20)

Additional halfspaces can be similarly derived for the other semi-axes in
$F_{o}$, as further documented in the supplementary materials. Once these
halfspaces have been defined, one can test whether a second object $o_{2}$
lies within any of the halfspaces of $o_{1}$. In particular, (?) differentiate
between “relaxed” (_r) and “strict” (_s) spatial operators, based on whether
$o_{2}$ intersects or is completely contained in the halfspaces of $o_{1}$. In
the following, we represent predicates symbolising cardinal directions East,
West, North, South, Above and Below through their capital initial. Given a
$F_{o}$ which coincides with $F_{g}$, the strict and relaxed definitions of
the relation East($o_{2}$,$o_{1}$) are:

$\displaystyle\begin{split}\textit{E\\_s}(o_{2},o_{1},&{}F_{o})\Leftrightarrow\textit{MinBoundBox}(mb_{1},o_{1})\wedge\\\
&\textit{ComplCont}(\textit{hs}(mb_{1},X_{o}^{+},F_{o}),\textit{sReg}(o_{2}))\end{split}$
(21)
$\textit{E\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{MinBoundBox}(mb_{1},o_{1})\wedge\\\
\textit{Int}(\textit{hs}(mb_{1},X_{o}^{+},F_{o}),\textit{sReg}(o_{2}))$ (22)

Based on our prior definitions, we can model directional relations with
respect to a given $F_{o}$ as follows:

$\displaystyle\textit{W\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{Int}(\textit{sReg}(o_{2}),\textit{hs}(mb_{1},X_{o}^{-},F_{o}))$
(23)
$\displaystyle\textit{N\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{Int}(\textit{sReg}(o_{2}),\textit{hs}(mb_{1},Y_{o}^{+},F_{o}))$
(24)
$\displaystyle\textit{S\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{Int}(\textit{sReg}(o_{2}),\textit{hs}(mb_{1},Y_{o}^{-},F_{o}))$
(25)
$\displaystyle\textit{A\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{Int}(\textit{sReg}(o_{2}),\textit{hs}(mb_{1},Z_{o}^{+},F_{o}))$
(26)
$\displaystyle\textit{B\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{Int}(\textit{sReg}(o_{2}),\textit{hs}(mb_{1},Z_{o}^{-},F_{o}))$
(27)

For brevity, we have omitted the predicate
$\textit{MinBoundBox}(mb_{1},o_{1})$ from axioms 23-27. The full definition is
in the supplementary materials.

Figure 2: Halfspaces are generated by extruding the 3D bounding boxes along
the axis direction in the frame of reference. Specifically, the top and bottom
halfspaces, i.e., extruded along the $Z$ axis, are derived from the minimum
oriented bounding box (left-hand side of the Figure). The left, right, front
and bottom halfspaces are instead extruded from the Contextualised Bounding
Box (right-hand side of the Figure).

(?) defined the aforementioned relations under the assumption that $F_{o}$ is
always aligned with $F_{g}$. However, this assumption does not hold in the
case of mobile robot sensemaking. Indeed, the frame of reference of the robot,
$F_{r}$ is mobile, i.e., its origin and orientation change over time.
Moreover, the natural orientation of objects may not be aligned with $F_{g}$.
Thus, to produce a representational model which suits the case of robot
sensemaking, we need to map axioms 22-27 to the contextualised frame of
reference, $F_{c}$, defined earlier. In a typical robotic setting, the robot
always faces towards $X_{r}^{+}$, and $Z_{r}^{+}$ is directed upwards, i.e.,
opposite to the direction of gravity. Then, the orientation of $Y_{r}$ is
given by applying the right hand rule (Figure 1). Based on these premises, all
$Z$ axes always share the same orientation. Namely, the top and bottom
halfspaces of an object do not change with the robot’s reference frame
(Figures 1,2). Therefore, the A_r and B_r predicates based on the minimum
oriented bounding box of an object w.r.t. a given $F_{o}$ can be directly
reused to define the Above and Below relations w.r.t. $F_{c}$:

$\displaystyle\textit{Above}(o_{2},o_{1},F_{c})\Leftrightarrow\textit{A\\_r}(o_{2},o_{1},F_{o})$
(28)
$\displaystyle\textit{Below}(o_{2},o_{1},F_{c})\Leftrightarrow\textit{B\\_r}(o_{2},o_{1},F_{o})$
(29)

Nonetheless, to model relations such as RightOf or LeftOf, we need to account
for the robot’s viewpoint. Thus, we apply the halfspace-based model to the
Contextualised Bounding Box we have defined earlier (see Figure 2). By
definition, CBB is aligned with the contextualised frame of reference,
$F_{c}$, so the front halfspace of CBB, for instance, can be defined w.r.t. a
given $F_{c}$ as follows:

$\textit{IsCBB}(cbb_{1},o_{1})\Rightarrow\textit{hs}(cbb_{1},X_{c}^{-},F_{c})=\\\
\begin{split}\\{gp\in\textit{outReg}(cbb_{1})|gp&{}=(x,y,z)\textit{
w.r.t.}F_{c},\\\ &x^{\prime}_{min}-x^{\prime}_{min}\cdot s\leq x\leq
x^{\prime}_{min},\\\ &y^{\prime}_{min}\leq y\leq y^{\prime}_{max},\\\
&z^{\prime}_{min}\leq z\leq z^{\prime}_{max}\\}\end{split}$ (30)

Capitalising on these spatial constructs, we can define the remaining
directional relations:

$\displaystyle\textit{RightOf}(o_{2},o_{1},F_{c})\Leftrightarrow\textit{Int}(\textit{sr}_{2},\textit{hs}(cbb_{1},Y_{c}^{-},F_{c}))$
(31)
$\displaystyle\textit{LeftOf}(o_{2},o_{1},F_{c})\Leftrightarrow\textit{Int}(\textit{sr}_{2},\textit{hs}(cbb_{1},Y_{c}^{+},F_{c}))$
(32)
$\displaystyle\textit{InFrontOf}(o_{2},o_{1},F_{c})\Leftrightarrow\textit{Int}(\textit{sr}_{2},\textit{hs}(cbb_{1},X_{c}^{-},F_{c}))$
(33)
$\displaystyle\textit{Behind}(o_{2},o_{1},F_{c})\Leftrightarrow\textit{Int}(\textit{sr}_{2},\textit{hs}(cbb_{1},X_{c}^{+},F_{c}))$
(34)

For brevity, in axioms 31-34 we have omitted the predicate
$\textit{IsCBB}(cbb_{1},o_{1})$, which is always valid. The full definition is
given in the supplementary materials. Next, we need to specify how the
qualitative spatial relations we have identified align with commonsense
spatial predicates.

#### Commonsense spatial relations

In English, objects are represented by nouns while the spatial relationships
between objects are mainly represented through prepositions - e.g., on, next
to, behind (?). Spatial relations are also implied by using certain verbs
(e.g., person wears shirt). However, almost invariably, these verbs can be
reduced to a simplified form, followed by a preposition (e.g., person has
shirt on). Hence, the canonical structure of a spatial sentence consists of
three elements: (i) a reference object and (ii) a figure object, both
expressed as noun phrases, as well as (iii) a spatial preposition. The
reference object and the preposition, together, define the spatial region
occupied by the figure object.
As pointed out in (?), a set of reference axes is needed to differentiate the
front, back, top, bottom and sides of an object. Specifically, the object’s
top and bottom are defined as “the regions at the ends of whichever axis is
vertical in the object’s normal orientation” (?). Thus, they are conceptually
equivalent to the notion of top and bottom halfspaces we defined for the
minimum oriented bounding box. Moreover, the object front is defined as the
region at the end of the object’s horizontal axis which also faces the
observer. Conversely, the object back region is located opposite to the
observer along the same axis. Finally, the region at the end of any other
horizontal axis can be called a side. Thus, the four halfspaces we have
defined based on the CBB cover these concepts.
Consequently, the directional relations defined at statements 28-34 are fit to
model the directional predicates in (?). Moreover, the LeftOf and RightOf
relations can be combined so that, given $F_{c}$:

$\displaystyle\begin{split}\textit{Beside}(o_{2},o_{1},F_{c})\Leftrightarrow&{}\textit{RightOf}(o_{2},o_{1},F_{c})\lor\\\
&\textit{LeftOf}(o_{2},o_{1},F_{c})\end{split}$ (35)

An interesting case is that of the “on” preposition. One of the senses of “on”
is semantically related to “above”. However, while “above” typically implies
absence of contact between the two objects, “on” strongly favours a contact
reading (?). Formally, we make this distinction by defining:

$\displaystyle\begin{split}\textit{OnTopOf}(o_{2},o_{1},F_{c})\Leftrightarrow&{}\textit{Above}(o_{2},o_{1},F_{c})\wedge\\\
&\textit{Touches}(o_{2},o_{1})\end{split}$ (36)

Nonetheless, the “on” preposition can also be used to denote that the figure
object is supported by the reference object. For instance, we say that a
“clock is on the wall” although the two objects overlap horizontally. The
phrase “clock on wall” also implies that the wall is adequately stable to
support the clock. Indeed, if two objects differ in terms of size and
mobility, we typically prefer to consider the larger and more stable object as
reference (?). To disambiguate these additional uses of “on”, we define, for a
given $F_{c}$:

$\displaystyle\begin{split}\textit{LeansOn}(&{}o_{2},o_{1},F_{c})\Leftrightarrow\textit{Touches}(o_{2},o_{1})\wedge\\\
&\neg\textit{Above}(o_{2},o_{1},F_{c})\wedge\neg\textit{Below}(o_{2},o_{1},F_{c})\wedge\\\
\exists
o_{3}&[\textit{Touches}(o_{2},o_{3})\wedge\textit{Below}(o_{3},o_{2},F_{c})]\end{split}$
(37)
$\textit{Touches}(o_{2},o_{1})\wedge\neg\textit{Above}(o_{2},o_{1},F_{c})\wedge\\\
\neg\exists
o_{3}\textit{Touches}(o_{3},o_{2})\Rightarrow\textit{AffixedOn}(o_{2},o_{1},F_{c})$
(38)

Namely, whenever $o_{2}$ is supported by a reference object $o_{1}$ along the
horizontal direction, it is typically said to be “leaning against” $o_{1}$:
e.g., a ladder leaning against a wall. Furthermore, if the reference object
$o_{1}$ provides the only support surface for $o_{2}$, $o_{2}$ is typically
said to be AffixedOn $o_{1}$: e.g., a ladder which is affixed on the wall,
above ground. Nonetheless, there may be cases where an object, $o_{2}$, is
physically affixed to a surface, $o_{1}$, even though $o_{1}$ is not the only
surface in contact with $o_{2}$: e.g., a ladder affixed at ground level.
Hence, we used a single logic implication in Statement 37.

Similar considerations apply for the spatial preposition “in”, which is also
polysemous. First, “in” is generally used to imply that one object is “inside”
another, or, based on our prior topological definitions, that one object is
completely contained in the other (axiom 19). However, “in” is also used in
cases where two objects only partially compenetrate each other. For instance,
we would say that “a cat is in the box” even when the cat’s tail is peeping
from the box. To define this notion of partial containment we need first to
define a function, adjSRCard, which, given two spatial regions, sr and sr’,
returns the cardinality of the set of points in sr’ that are adjacent to
points in sr:

$\textit{adjSRCard}(sr,sr^{\prime})=|\\{gp^{\prime}|gp^{\prime}\in\textit{outReg}(sr)\wedge
gp^{\prime}\in sr^{\prime}\wedge\\\ \exists gp[gp\in
sr\wedge\textit{Adj}(gp,gp^{\prime})]\\}|$ (39)

Hence, we can now define partial containment as follows:

$\displaystyle\textit{PartIn}(o_{1},o_{2})\Leftrightarrow\textit{sr}=\textit{inter}(\textit{sReg}(o_{1}),\textit{sReg}(o_{2}))\wedge$
$\displaystyle\textit{adjSRCard}(sr,\textit{sReg}(o_{1}))<\textit{adjSRCard}(sr,\textit{sReg}(o_{2}))]$
(40)

Namely, $o_{1}$ is partially contained in $o_{2}$ iff the number of points in
$o_{1}$ that are adjacent to the intersection region of $o_{1}$ and $o_{2}$ is
strictly smaller than the number of points in $o_{2}$ that are adjacent to the
same intersection region.

Lastly, an object is said to be “near” another object if it is located in a
region “extending up to some critical distance” (?). This notion corresponds
exactly to our definition of predicate IsClose (axiom 15).

##  4 Framework Applicability

In this Section, we assess the applicability of the proposed logic framework
in concrete robotic scenarios. First, we illustrate how the raw sensor data
can be opportunely processed to populate a spatial database (Section 4.1).
Then, in Section 4.2, we evaluate the extent to which state-of-the-art GIS
operators can cover the proposed set of Qualitative Spatial Relations.
Furthermore, we show that, once a set of basic spatial concepts has been
derived through GIS operators, our framework provides a method to combine
these basic spatial concepts to model the commonsense spatial predicates of
(?).

###  4.1 Populating the Spatial Database

Figure 3a shows an example of RGB-Depth (RGB-D) data collected through HanS’
Orbbec Astra Pro monocular camera. At each time frame, $t$, the distance
between the robot’s pose and the surfaces reached by the laser in the depth
sensor is measured. These data are also known as depth images, and can be
converted to collections of 3D geometrical points in the considered frame of
reference, i.e., PointClouds. As in (?), RGB images are autonomously
classified through Machine Learning (ML), i.e., based on the multi-branch
Network of (?). We then project the object regions annotated on RGB images on
the PointCloud representing the observed scene, to obtain a segmented 3D
region for each annotated object. In addition to the annotated object regions,
we extract the planar surfaces representing the wall and floor areas.
Specifically, we use the PCL library (?) to reproduce the RANSAC planar
segmentation algorithm. Then, we differentiate walls from floors based on the
orientation of the plane normal. Because the robot pose at each $t$ is known,
the depth values within each 3D object region can be converted to coordinate
triples in the global frame of reference, $F_{g}$. In sum, we have produced a
semantic map of the robot’s environment.

Figure 3: Example of operational workflow: (a) the PointCloud representing the
observed scene is first segmented and annotated with object categories. Then,
(b) the minimum oriented bounding boxes and CBBs (in blue) are constructed.
Lastly, (c) a set of QSR in figure-reference form is derived. In Figures 3b,
3c we show a subset of the bounding boxes and QSR representing the scene, for
readability.

Consistently with (?), we store the object regions and labels in the semantic
map within a spatial database, implemented in
PostgreSQL222https://www.postgresql.org/. By linking these data to a spatial
database, we can capitalise on the PostGIS engine333https://postgis.net/,
which provides a series of query operators for spatial reasoning over
PostgreSQL databases. In particular, we rely on the SFCGAL
backend444http://www.sfcgal.org/, which extends PostGIS by supporting more
advanced 3D operations. Objects are stored in the PostGIS database using a
minimum oriented polyhedron derived by applying the convex hull algorithm on
the segmented PointCloud. Planar surfaces are instead stored as 2D polygons.
To populate the spatial database, for each 3D solid or 2D polygon, a new
database record is added, which includes: (i) a unique identifier, obtained by
concatenating the data collection timestamp with an incremental digit; (ii)
the robot’s heading and $x,y,z$ coordinates w.r.t. $F_{g}$; (iii) the top-5
object labels and related confidence scores, as predicted through ML; as well
as (iv) a set of Bounding Box representations of the 3D solid, as further
detailed in the next Section.

###  4.2 Coverage Study

The mapping of spatial concepts in our framework to GIS operators is
summarised in Table 1(a). In the following, we also explain the operational
steps applied to obtain the output of each row in Table 1(a).

#### Minimum Oriented Bounding Box

To compute the minimum oriented bounding box, we input the 2D projection of
the solid on the XY plane to the ST_OrientedEnvelope operator. Second, the
ST_ZMin and ST_ZMax functions can be used to find the minimum and maximum
coordinate of the 3D solid with respect to the vertical axis. The absolute
difference between these two coordinates yields the height of the target
bounding box, $h$. Then, the ST_Extrude operator can be used to extrude the 2D
envelope along $Z$ by $h$.

#### Contextualised Bounding Box

The Contextualised Bounding Box, CBB, is obtained by rotating the minimum
oriented bounding box by an angle $\theta$, to align it with $F_{c}$ (axiom
12). This operation can be achieved through the ST_Rotate operator. ST_Rotate
requires, as input, a geometry, a rotation origin and an angle. We use
ST_Angle to compute the angle between the heading of the robot and the
bounding box, i.e., $\theta$. To derive the rotation origin, we can exploit
ST_Centroid. Since ST_Centroid is a 2D operator, it is applied to the minimum
oriented 2D rectangle returned by ST_OrientedEnvelope. Lastly, the
transformation is applied to the line passing through the rotation origin and
parallel to the $Z$ axis.

#### Object Halfspaces

To derive the six object halfspaces, we can rely on the ST_Extrude operator.
As emphasised in Table 1(a), we generate the top and bottom halfspaces by
applying ST_Extrude to the minimum oriented bounding box. However, to account
for the orientation of both the object and the robot, the remaining four
halfspaces are generated by extruding the Contextualised Bounding Box.

Input Geometry/ies | GIS operators applied | Output
---|---|---
Convex Hull |  ST_OrientedEnvelope, | Min Oriented BBox
|  ST_ZMin, ST_ZMax, |
| ST_Extrude |
Min Oriented BBox, |  ST_Rotate, | CBB
Robot heading |  ST_Angle, ST_Centroid |
Min Oriented BBox, $s$ | ST_Extrude | Top/Bottom Halfspaces
CBB, $s$ | ST_Extrude | L/R/Front/Back Halfspaces
Min Oriented BBoxes | ST_Volume | Reference object set
Min Oriented BBoxes | ST_3DDWithin |  IsClose, Touches
Min Oriented BBoxes | ST_3DIntersects | Intersects (Int)
Min Oriented BBoxes | ST_3DIntersection | inter
Min Oriented BBoxes |  ST_3DIntersection, | CompletelyContains
| ST_Volume | (ComplCont)
Min Oriented BBox | ST_3DIntersects | Left/RightOf
Halfspaces |  |  Above, Below
|  |  InFrontOf, Behind
Min Oriented BBoxes |  ST_Scale, ST_Volume | adjSRCard
| ST_Intersection |
(a)

QSR | Follows from
---|---
Beside |  RightOf, LeftOf
OnTopOf |  Touches, Above
LeansOn |  Touches, Above
| Below
AffixedOn |  Touches, Above
Inside | ComplCont
PartIn |  inter, adjSRCard
Near | isClose
(b)

Table 1: (a) Coverage of spatial notions through PostGIS operators. (b) The
basic spatial relations covered by PostGIS are combined to derive more complex
QSR.

#### Identifying the reference objects

Commonsense spatial relations are expressed with respect to a reference object
and are asymmetric (?). For instance, we would say that a plant is on the
floor (figure-reference form), but we would never say that the floor is under
a plant (reference-figure form). Therefore, to extract only the QSR which are
in figure-reference form, we need first to identify the set of reference
objects in each scene. Reference objects are usually the largest and most
stable among the observed objects (?). Hence, by definition, we consider as
reference the objects of large area and negligible thickness, which we have
modelled as 2D planes, i.e., walls and floors. Moreover, the ST_Volume
operator provides a way to measure the size of the 3D bounding boxes. To
compute only QSR which are in figure-reference form, we sort objects by volume
in descending order. Then, we only compute the QSR between one object and the
nearby objects which are smaller than it, if any is found. As a result, in the
example depicted in Figure 3, QSR such as wall behind fire extinguisher1 or
floor under fire extinguisher2 would not be extracted. Thus, this design
choice also reduces the computational load of extracting QSR for all pairwise
combinations of objects.

#### Metric relations

To identify the set of objects which lie nearby a reference object, we can use
the ST_3DDWithin operator. This operator returns true if the minimum 3D
Euclidean distance between two objects is within a specified threshold. Thus,
it is equivalent to our definition of object closeness (axiom 15). Hence, for
all object pairs $o^{\prime}$ and $o$ for which ST_3DDWithin returns true for
a specified $T>0$, the relation IsClose($o,o^{\prime}$) also holds. A special
case is that of the Touches($o,o^{\prime}$) relation, where $T=0$.

#### Topological relations

The intersection relation we have defined at axiom 17 is directly covered by
the ST_3DIntersects operator. Similarly, ST_3DIntersection, is equivalent to
the aforementioned inter function (axiom 18). Neither PostGIS nor SFCGAL
support 3D containment tests. To circumvent this limitation, we derive
containment relations by comparing the volume of objects with the volume of
their intersection region, through ST_Volume. Namely, if the volume of the
intersection region equals the volume of the smaller object, e.g.,
$o^{\prime}$, then ComplCont($o,o^{\prime}$).

#### Directional relations

To derive directional QSR, the ST_3DIntersects operator can be applied to the
object halfspaces constructed earlier. For instance, in Figure 3c, fire
extinguisher2 is on the left of the radiator, because it intersects the left
halfspace of the radiator. Differently from (?), however, the left halfspace
was here defined on a Contextualised Bounding Box, so that the robot’s
viewpoint is also accounted for.

#### Commonsense spatial relations

As shown in Table 1(a), PostGIS ensures a full coverage of the basic building
blocks of our spatial framework. Then, the commonsense relations defined in
Section 3 can be seen as a combination of these building blocks (Table 1(b)).
For instance, having mapped the LeftOf and RightOf relation to GIS operators
(Table 1(a)) we can also conclude whether $o,o^{\prime}$ are Beside one
another (Table 1(b)). In the case of PartIn, we first apply ST_Intersection to
obtain the intersection region of $o,o^{\prime}$, i.e., inter$(o,o^{\prime})$.
Then, to approximate the frontier of points which are adjacent to the
intersection region, we scale inter$(o,o^{\prime})$ by a $D$, via ST_Scale. In
other words, we obtain a region which is infinitesimally larger than the
intersection region. Thus, we can use this region to test, again through
ST_Intersection, which sets of points overlap $o$ and $o^{\prime}$.
Specifically, since we are dealing with geometric regions, the cardinality of
each point set (axiom 39) is given by the region volume, i.e., via ST_Volume.
In sum, the aforementioned operators, also listed in Table 1, cover the logic
functions needed to evaluate PartIn$(o,o^{\prime})$.

Crucially, the introduction of commonsense QSR allows us to disambiguate
polysemous spatial prepositions, such as “in” or “on”. For instance, in Figure
3, both fire extinguishers are generically “on the wall”. However, fire
extinguisher 1, is affixed on the wall, whereas fire extinguisher 2, is also
supported by the floor and thus leans on the wall, i.e., it may or may not be
affixed on the wall. Thus, compared to the “on” preposition, the introduced
QSR more precisely express the intuitive spatial and physics relations at
play.

##  5 Conclusion and Future Work

In this paper, we have identified a framework for commonsense spatial
reasoning which satisfies the concrete requirements of robot sensemaking in
real-world scenarios. Differently from prior approaches to qualitative spatial
reasoning in robotics, this framework is robust to variations in the robot’s
viewpoint and object orientation, thus ensuring scalability to many
application scenarios. As highlighted by our coverage study, the proposed
framework can be fully implemented by capitalising on state-of-the-art GIS
technologies. Moreover, the proposed framework contributes a cognitively-
inspired conceptual layer on top of these basic spatial operators, to model
commonsense spatial predicates. The resulting linguistic predicates facilitate
Human-Robot Interaction, as well as the integration of background spatial
knowledge from external resources. As such, the proposed framework contributes
to the broader objective of developing Visually Intelligent Agents (VIA),
which can reliably assist us with our daily tasks.

Our future efforts will be focused on evaluating the performance impacts of
augmenting ML-based object recognition methods with the proposed commonsense
spatial reasoner. In this context, we will also assess the effects of
combining commonsense spatial reasoning with the other types of reasoners
contributing to the Visual Intelligence of a robot (?): e.g., size-based (?),
motion-based and others.

##  Appendix A Supplementary Materials

###  A.1 Halfspace Definitions

The hs function we introduced at axiom 20 of the paper can be similarly
applied to the other semi-axes in a given $F_{o}$. Specifically, given an
input bounding box, and frame of reference, $F_{o}$:

$\textit{MinBoundBox}(mb_{1},o_{1})\Rightarrow\textit{hs}(mb_{1},X_{o}^{-},F_{o})=\\\
\begin{split}\\{gp\in\textit{outReg}(mb_{1})|&{}gp=(x,y,z)\textit{ w.r.t
}F_{o},\\\ &x_{min}-x_{min}\cdot s\leq x\leq x_{min},\\\ &y_{min}\leq y\leq
y_{max},\\\ &z_{min}\leq z\leq z_{max}\\}\end{split}$ (41)

$\textit{MinBoundBox}(mb_{1},o_{1})\Rightarrow\textit{hs}(mb_{1},Y_{o}^{+},F_{o})=\\\
\begin{split}\\{gp\in\textit{outReg}(mb_{1})|&{}gp=(x,y,z)\textit{ w.r.t
}F_{o},\\\ &x_{min}\leq x\leq x_{max},\\\ &y_{max}\leq y\leq
y_{max}+y_{max}\cdot s,\\\ &z_{min}\leq z\leq z_{max}\\}\end{split}$ (42)

$\textit{MinBoundBox}(mb_{1},o_{1})\Rightarrow\textit{hs}(mb_{1},Y_{o}^{-},F_{o})=\\\
\begin{split}\\{gp\in\textit{outReg}(mb_{1})|&{}gp=(x,y,z)\textit{ w.r.t
}F_{o},\\\ &x_{min}\leq x\leq x_{max},\\\ &y_{min}-y_{min}\cdot s\leq y\leq
y_{min},\\\ &z_{min}\leq z\leq z_{max}\\}\end{split}$ (43)

$\textit{MinBoundBox}(mb_{1},o_{1})\Rightarrow\textit{hs}(mb_{1},Z_{o}^{+},F_{o})=\\\
\begin{split}\\{gp\in\textit{outReg}(mb_{1})|&{}gp=(x,y,z)\textit{ w.r.t
}F_{o},\\\ &x_{min}\leq x\leq x_{max},\\\ &y_{min}\leq y\leq y_{max},\\\
&z_{max}\leq z\leq z_{max}+z_{max}\cdot s\\}\end{split}$ (44)

$\textit{MinBoundBox}(mb_{1},o_{1})\Rightarrow\textit{hs}(mb_{1},Z_{o}^{-},F_{o})=\\\
\begin{split}\\{gp\in\textit{outReg}(mb_{1})|&{}gp=(x,y,z)\textit{ w.r.t
}F_{o},\\\ &x_{min}\leq x\leq x_{max},\\\ &y_{min}\leq y\leq y_{max},\\\
&z_{min}-z_{min}\cdot s\leq z\leq z_{min}\\}\end{split}$ (45)

Similarly, to complete axiom 30 in the main paper, the back, left and right
halfspaces are defined as follows, given $F_{c}$:

$\textit{IsCBB}(cbb_{1},o_{1})\Rightarrow\textit{hs}(cbb_{1},X_{c}^{+},F_{c})=\\\
\begin{split}\\{gp\in\textit{outReg}(cbb_{1})|gp&{}=(x,y,z)\textit{
w.r.t.}F_{c},\\\ &x^{\prime}_{max}\leq x\leq
x^{\prime}_{max}+x^{\prime}_{max}\cdot s,\\\ &y^{\prime}_{min}\leq y\leq
y^{\prime}_{max},\\\ &z^{\prime}_{min}\leq z\leq
z^{\prime}_{max}\\}\end{split}$ (46)

$\textit{IsCBB}(cbb_{1},o_{1})\Rightarrow\textit{hs}(cbb_{1},Y_{c}^{+},F_{c})=\\\
\begin{split}\\{gp\in\textit{outReg}(cbb_{1})|gp&{}=(x,y,z)\textit{
w.r.t.}F_{c},\\\ &x^{\prime}_{min}\leq x\leq x^{\prime}_{max},\\\
&y^{\prime}_{max}\leq y\leq y^{\prime}_{max}+y^{\prime}_{max}\cdot s,\\\
&z^{\prime}_{min}\leq z\leq z^{\prime}_{max}\\}\end{split}$ (47)

$\textit{IsCBB}(cbb_{1},o_{1})\Rightarrow\textit{hs}(cbb_{1},Y_{c}^{-},F_{c})=\\\
\begin{split}\\{gp\in\textit{outReg}(cbb_{1})|gp&{}=(x,y,z)\textit{
w.r.t.}F_{c},\\\ &x^{\prime}_{min}\leq x\leq x^{\prime}_{max},\\\
&y^{\prime}_{min}-y^{\prime}_{min}\cdot s\leq y\leq y^{\prime}_{min},\\\
&z^{\prime}_{min}\leq z\leq z^{\prime}_{max}\\}\end{split}$ (48)

###  A.2 Directional Relations

The extended definitions of axioms 23-27 in the main paper for a given $F_{o}$
are:

$\textit{W\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{MinBoundBox}(mb_{1},o_{1})\wedge\\\
\textit{Int}(\textit{sReg}(o_{2}),\textit{hs}(mb_{1},X_{o}^{-},F_{o}))$ (49)
$\textit{N\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{MinBoundBox}(mb_{1},o_{1})\wedge\\\
\textit{Int}(\textit{sReg}(o_{2}),\textit{hs}(mb_{1},Y_{o}^{+},F_{o}))$ (50)
$\textit{S\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{MinBoundBox}(mb_{1},o_{1})\wedge\\\
\textit{Int}(\textit{sReg}(o_{2}),\textit{hs}(mb_{1},Y_{o}^{-},F_{o}))$ (51)
$\textit{A\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{MinBoundBox}(mb_{1},o_{1})\wedge\\\
\textit{Int}(\textit{sReg}(o_{2}),\textit{hs}(mb_{1},Z_{o}^{+},F_{o}))$ (52)

$\textit{B\\_r}(o_{2},o_{1},F_{o})\Leftrightarrow\textit{MinBoundBox}(mb_{1},o_{1})\wedge\\\
\textit{Int}(\textit{sReg}(o_{2}),\textit{hs}(mb_{1},Z_{o}^{-},F_{o}))$ (53)

Moreover, the full definitions of axioms 31-34 in the main paper, given
$F_{c}$, are:

$\textit{RightOf}(o_{2},o_{1},F_{c})\Leftrightarrow\textit{IsCBB}(cbb_{1},o_{1})\wedge\\\
\textit{Int}(\textit{sr}_{2},\textit{hs}(cbb_{1},Y_{c}^{-},F_{c}))$ (54)

$\textit{LeftOf}(o_{2},o_{1},F_{c})\Leftrightarrow\textit{IsCBB}(cbb_{1},o_{1})\wedge\\\
\textit{Int}(\textit{sr}_{2},\textit{hs}(cbb_{1},Y_{c}^{+},F_{c}))$ (55)

$\textit{InFrontOf}(o_{2},o_{1},F_{c})\Leftrightarrow\textit{IsCBB}(cbb_{1},o_{1})\wedge\\\
\textit{Int}(\textit{sr}_{2},\textit{hs}(cbb_{1},X_{c}^{-},F_{c}))$ (56)

$\textit{Behind}(o_{2},o_{1},F_{c})\Leftrightarrow\textit{IsCBB}(cbb_{1},o_{1})\wedge\\\
\textit{Int}(\textit{sr}_{2},\textit{hs}(cbb_{1},X_{c}^{+},F_{c}))$ (57)

## References

  * Alatise and Hancke 2020 Alatise, M. B., and Hancke, G. P.  2020\.  A review on challenges of autonomous mobile robot and sensor fusion methods.  IEEE Access 8:39830–39846.
  * Borrmann and Rank 2010 Borrmann, A., and Rank, E.  2010\.  Query Support for BIMs using Semantic and Spatial Conditions.  In Handbook of Research on Building Information Modeling and Construction Informatics: Concepts and Technologies. IGI Global.  405–450.
  * Chiatti et al. 2021 Chiatti, A.; Motta, E.; Daga, E.; and Bardaro, G.  2021\.  Fit to measure: Reasoning about sizes for robust object recognition.  In To appear in proceedings of the AAAI2021 Spring Symposium on Combining Machine Learning and Knowledge Engineering (AAAI-MAKE 2021).
  * Chiatti, Motta, and Daga 2020 Chiatti, A.; Motta, E.; and Daga, E.  2020\.  Towards a Framework for Visual Intelligence in Service Robotics: Epistemic Requirements and Gap Analysis.  In Proceedings of KR 2020- Special session on KR & Robotics, 905–916.  IJCAI.
  * Cohn and Renz 2008 Cohn, A. G., and Renz, J.  2008\.  Qualitative Spatial Representation and Reasoning.  In van Harmelen, F.; Lifschitz, V.; and Porter, B., eds., Foundations of Artificial Intelligence, volume 3 of Handbook of Knowledge Representation. Elsevier.  551–596.
  * Coradeschi and Saffiotti 2003 Coradeschi, S., and Saffiotti, A.  2003\.  An introduction to the anchoring problem.  Robotics and autonomous systems 43(2-3):85–96.
  * Davis and Marcus 2015 Davis, E., and Marcus, G.  2015\.  Commonsense reasoning and commonsense knowledge in artificial intelligence.  Communications of the ACM 58(9):92–103.
  * Deeken, Wiemann, and Hertzberg 2018 Deeken, H.; Wiemann, T.; and Hertzberg, J.  2018\.  Grounding semantic maps in spatial databases.  Robotics and Autonomous Systems 105:146–165.
  * Hayes 1988 Hayes, P. J.  1988\.  The Second Naive Physics Manifesto. Formal theories of the common sense world.  Ablex Publishing Corporation.
  * Herskovits 1997 Herskovits, A.  1997\.  Language, Spatial Cognition, and Vision.  In Stock, O., ed., Spatial and Temporal Reasoning. Dordrecht: Springer Netherlands.  155–202.
  * Kostavelis and Gasteratos 2015 Kostavelis, I., and Gasteratos, A.  2015\.  Semantic mapping for mobile robotics tasks: A survey.  Robotics and Autonomous Systems 66:86–103.
  * Krishna et al. 2017 Krishna, R.; Zhu, Y.; Groth, O.; Johnson, J.; and et al.  2017\.  Visual genome: Connecting language and vision using crowdsourced dense image annotations.  International journal of computer vision 123(1):32–73.
  * Kunze et al. 2014 Kunze, L.; Burbridge, C.; Alberti, M.; Thippur, A.; Folkesson, J.; Jensfelt, P.; and Hawes, N.  2014\.  Combining top-down spatial reasoning and bottom-up object class recognition for scene understanding.  In 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2910–2915.
  * Lake et al. 2017 Lake, B. M.; Ullman, T. D.; Tenenbaum, J. B.; and Gershman, S. J.  2017\.  Building machines that learn and think like people.  Behavioral and Brain Sciences 40\.
  * Landau and Jackendoff 1993 Landau, B., and Jackendoff, R.  1993\.  “What” and “where” in spatial language and spatial cognition.  Behavioral and Brain Sciences 16(2):217–238.
  * Levesque 2017 Levesque, H.  2017\.  Common Sense, the Turing Test, and the Quest for Real AI.  The MIT Press.
  * Liu and Wang 2020 Liu, H., and Wang, L.  2020\.  Remote human–robot collaboration: A cyber–physical system application for hazard manufacturing environment.  Journal of manufacturing systems 54:24–34.
  * Moratz and Ragni 2008 Moratz, R., and Ragni, M.  2008\.  Qualitative spatial reasoning about relative point position.  Journal of Visual Languages & Computing 19(1):75–98.
  * Nilsson et al. 2018 Nilsson, P.; Haesaert, S.; Thakker, R.; Otsu, K.; Vasile, C.-I.; Agha-Mohammadi, A.-A.; Murray, R. M.; and Ames, A. D.  2018\.  Toward specification-guided active mars exploration for cooperative robot teams.  Robotics: Science and Systems (RSS).
  * Nüchter and Hertzberg 2008 Nüchter, A., and Hertzberg, J.  2008\.  Towards semantic maps for mobile robots.  Robotics and Autonomous Systems 56(11):915–926.
  * Rusu and Cousins 2011 Rusu, R. B., and Cousins, S.  2011\.  3d is here: Point cloud library (pcl).  In 2011 IEEE International Conference on Robotics and Automation (ICRA), 1–4.  IEEE.
  * Sarthou, Alami, and Clodic 2019 Sarthou, G.; Alami, R.; and Clodic, A.  2019\.  Semantic Spatial Representation: a unique representation of an environment based on an ontology for robotic applications.  In Combined Workshop on Spatial Language Understanding (SpLU) and Grounded Communication for Robotics (RoboNLP)., 12.
  * Sisbot and Connell 2019 Sisbot, E. A., and Connell, J. H.  2019\.  Where is My Stuff? An Interactive System for Spatial Relations.  arXiv:1909.06331 [cs].  arXiv: 1909.06331.
  * Storks, Gao, and Chai 2019 Storks, S.; Gao, Q.; and Chai, J. Y.  2019\.  Recent advances in natural language inference: A survey of benchmarks, resources, and approaches.  arXiv preprint arXiv:1904.01172.
  * Thippur et al. 2015 Thippur, A.; Burbridge, C.; Kunze, L.; Alberti, M.; Folkesson, J.; Jensfelt, P.; and Hawes, N.  2015\.  A comparison of qualitative and metric spatial relation models for scene understanding.  In 29th AAAI Conference and the 27th Innovative Applications of Artificial Intelligence Conference (IAAI), volume 2, 1632–1640.  AI Access Foundation.
  * Thippur, Stork, and Jensfelt 2017 Thippur, A.; Stork, J. A.; and Jensfelt, P.  2017\.  Non-parametric spatial context structure learning for autonomous understanding of human environments.  In 2017 26th IEEE International Symposium on Robot and Human Interactive Communication (RO-MAN), 1317–1324.  ISSN: 1944-9437.
  * Yang et al. 2020 Yang, G.; Lv, H.; Zhang, Z.; Yang, L.; Deng, J.; You, S.; Du, J.; and Yang, H.  2020\.  Keep healthcare workers safe: application of teleoperated robot in isolation ward for covid-19 prevention and control.  Chinese Journal of Mechanical Engineering 33(1):1–4.
  * Yang, Russakovsky, and Deng 2019 Yang, K.; Russakovsky, O.; and Deng, J.  2019\.  SpatialSense: An Adversarially Crowdsourced Benchmark for Spatial Relation Recognition.  In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), 2051–2060.  Seoul, Korea (South): IEEE.
  * Young et al. 2017 Young, J.; Kunze, L.; Basile, V.; Cabrio, E.; Hawes, N.; and Caputo, B.  2017\.  Semantic web-mining and deep vision for lifelong object discovery.  In 2017 IEEE International Conference on Robotics and Automation (ICRA), 2774–2779.  IEEE.
  * Zeng et al. 2018 Zeng, A.; Song, S.; Yu, K.-T.; Donlon, E.; Hogan, F. R.; Bauza, M.; Ma, D.; Taylor, O.; Liu, M.; Romo, E.; et al.  2018\.  Robotic pick-and-place of novel objects in clutter with multi-affordance grasping and cross-domain image matching.  In 2018 IEEE ICRA Conference, 1–8.  IEEE.


* [18] Thierry Denœux.  The cautious rule of combination for belief functions and some extensions.  In 2006 9th International Conference on Information Fusion, pages 1–8. IEEE, 2006.
  * [19] Renu Desai, Vikram Desai, Theresa Libby, and Rajendra P Srivastava.  External auditors' evaluation of the internal audit function: An empirical investigation.  International Journal of Accounting Information Systems, 24:1–14, 2017.
  * [20] Vikram Desai, Robin W Roberts, and Rajendra P Srivastava.  An analytical model for external auditor evaluation of the internal audit function using belief functions.  Available at SSRN 938183, 2006.
  * [21] Sergio M Dias and Newton Vieira.  Reducing the size of concept lattices: The jbos approach.  In Cla, volume 672, pages 80–91, 2010.
  * [22] Gabe Dickey, S Blanke, and L Seaton.  Machine learning in auditing.  The CPA Journal, pages 16–21, 2019.
  * [23] Didier Dubois and Henri Prade.  A set-theoretic view of belief functions logical operations and approximations by fuzzy sets.  International Journal Of General System, 12(3):193–226, 1986.
  * [24] J Michael Dunn, Mai Gehrke, and Alessandra Palmigiano.  Canonical extensions and relational completeness of some substructural logics.  The Journal of Symbolic Logic, 70(3):713–740, 2005.
  * [25] Sebastian Enqvist.  Modelling epistemic actions in interrogative belief revision.  Journal of Logic and Computation, 22(6):1335–1365, 2012.
  * [26] Sabine Frittella, Krishna Manoorkar, Alessandra Palmigiano, Apostolos Tzimoulis, and Nachoem Wijnberg.  Toward a dempster-shafer theory of concepts.  International Journal of Approximate Reasoning, 125:14–25, 2020\.
  * [27] Bernhard Ganter and Rudolf Wille.  Conceptual scaling.  In Applications of combinatorics and graph theory to the biological and social sciences, pages 139–167. Springer, 1989.
  * [28] Bernhard Ganter and Rudolf Wille.  Formal concept analysis: mathematical foundations.  Springer Science & Business Media, 2012.
  * [29] Lei Gao, Theodore J Mock, and Rajendra P Srivastava.  An evidential reasoning approach to fraud risk assessment under dempster-shafer theory: A general framework.  In 2011 44th Hawaii International Conference on System Sciences, pages 1–10. IEEE, 2011.
  * [30] Bruno Gaume, Emmanuel Navarro, and Henri Prade.  Clustering bipartite graphs in terms of approximate formal concepts and sub-contexts.  International Journal of Computational Intelligence Systems, 6(6):1125–1142, 2013.
  * [31] Mai Gehrke and Bjarni Jónsson.  Bounded distributive lattice expansions.  Mathematica Scandinavica, pages 13–45, 2004.
  * [32] Lukas Giriūnas and Jonas Mackevičius.  Evaluation of frauds in public sector.  Entrepreneurship and sustainability issues, 1:143–150, 2014.
  * [33] Robert Goldblatt.  Canonical extensions and ultraproducts of polarities.  Algebra universalis, 79(4):1–28, 2018.
  * [34] Jeroen Antonius Gerardus Groenendijk and Martin Johan Bastiaan Stokhof.  Studies on the Semantics of Questions and the Pragmatics of Answers.  PhD thesis, Univ. Amsterdam, 1984.
  * [35] Jonathan Hayes and Claudio Gutierrez.  Bipartite graphs as intermediate model for rdf.  In International Semantic Web Conference, pages 47–61. Springer, 2004.
  * [36] Anil K Jain and Richard C Dubes.  Algorithms for clustering data.  Prentice-Hall, Inc., 1988.
  * [37] Anil K Jain, M Narasimha Murty, and Patrick J Flynn.  Data clustering: a review.  ACM computing surveys (CSUR), 31(3):264–323, 1999.
  * [38] Edward J Joyce.  Expert judgment in audit program planning.  Journal of Accounting Research, 14:29–60, 1976.
  * [39] Frank Klawonn and Philippe Smets.  The dynamic of belief in the transferable belief model and specialization-generalization matrices.  In Uncertainty in artificial intelligence, pages 130–137. Elsevier, 1992.
  * [40] Julia Kokina and Thomas H Davenport.  The emergence of artificial intelligence: How automation is changing auditing.  Journal of emerging technologies in accounting, 14(1):115–122, 2017\.
  * [41] Sergei O Kuznetsov.  Machine learning and formal concept analysis.  In International Conference on Formal Concept Analysis, pages 287–312. Springer, 2004.
  * [42] Sergei O Kuznetsov.  On stability of a formal concept.  Annals of Mathematics and Artificial Intelligence, 49(1):101–115, 2007.
  * [43] LatViz.  Lattice visualization.  latviz.loria.fr, 2016.
  * [44] Jinhai Li, Changlin Mei, and Yuejin Lv.  Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction.  International Journal of Approximate Reasoning, 54(1):149–165, 2013\.
  * [45] Robert K Merton.  The self-fulfilling prophecy.  The antioch review, 8(2):193–210, 1948.
  * [46] Theodore J Mock, Srinivasan C Ragothaman, and Rajendra P Srivastava.  Using evidential reasoning technology to enhance the audit quality assurance inspection process.  Journal of Emerging Technologies in Accounting, 15(1):29–43, 2018\.
  * [47] David G Myers and Helmut Lamm.  The group polarization phenomenon.  Psychological bulletin, 83(4):602, 1976.
  * [48] Mark EJ Newman.  Scientific collaboration networks. ii. shortest paths, weighted networks, and centrality.  Physical review E, 64(1):016132, 2001.
  * [49] Georgios A Pavlopoulos, Panagiota I Kontou, Athanasia Pavlopoulou, Costas Bouyioukos, Evripides Markou, and Pantelis G Bagos.  Bipartite graphs in systems biology and medicine: a survey of methods and applications.  GigaScience, 7(4):giy014, 2018.
  * [50] Jonas Poelmans, Paul Elzinga, Stijn Viaene, and Guido Dedene.  Formal concept analysis in knowledge discovery: a survey.  In International conference on conceptual structures, pages 139–153. Springer, 2010.
  * [51] Jonas Poelmans, Sergei O Kuznetsov, Dmitry I Ignatov, and Guido Dedene.  Formal concept analysis in knowledge processing: A survey on models and techniques.  Expert systems with applications, 40(16):6601–6623, 2013.
  * [52] Uta Priss.  Formal concept analysis in information science.  Annu. Rev. Inf. Sci. Technol., 40(1):521–543, 2006.
  * [53] Abderrahim El Qadi, Driss Aboutajedine, and Yassine Ennouary.  Formal concept analysis for information retrieval.  arXiv preprint arXiv:1003.1494, 2010.
  * [54] John R. Raphael.  Rethinking the audit: Innovation is transforming how audits are conducted - and even what it means to be an auditor.  Journal of accountancy, 223:28, 2017.
  * [55] Erzsébet Ravasz, Anna Lisa Somera, Dale A Mongru, Zoltán N Oltvai, and A-L Barabási.  Hierarchical organization of modularity in metabolic networks.  science, 297(5586):1551–1555, 2002.
  * [56] Satu Elisa Schaeffer.  Graph clustering.  Computer science review, 1(1):27–64, 2007.
  * [57] Kari Sentz, Scott Ferson, et al.  Combination of evidence in Dempster-Shafer theory, volume 4015.  Citeseer, 2002.
  * [58] Glenn Shafer.  A mathematical theory of evidence.  Princeton university press, 1976.
  * [59] Glenn Shafer and Rajendra Srivastava.  The bayesian and belief-function formalisms: A general perspective for auditing.  Auditing: A Journal of practice and Theory, 9(Supplement):110–148, 1990.
  * [60] Nitin Singh, Kee-hung Lai, Markus Vejvar, and TC Edwin Cheng.  Data-driven auditing: A predictive modeling approach to fraud detection and classification.  Journal of Corporate Accounting & Finance, 30(3):64–82, 2019.
  * [61] Prem Kumar Singh, Aswani Kumar Cherukuri, and Jinhai Li.  Concepts reduction in formal concept analysis with fuzzy setting using shannon entropy.  International Journal of Machine Learning and Cybernetics, 8(1):179–189, 2017.
  * [62] Frano Škopljanac-Mačina and Bruno Blašković.  Formal concept analysis–overview and applications.  Procedia Engineering, 69:1258–1267, 2014.
  * [63] Philippe Smets.  Constructing the pignistic probability function in a context of uncertainty.  In Machine intelligence and pattern recognition, volume 10, pages 29–39. Elsevier, 1990.
  * [64] Philippe Smets.  The application of the matrix calculus to belief functions.  International Journal of Approximate Reasoning, 31(1-2):1–30, 2002\.
  * [65] Philippe Smets.  Decision making in the tbm: the necessity of the pignistic transformation.  International journal of approximate reasoning, 38(2):133–147, 2005\.
  * [66] Rajendra P Srivastava.  Belief functions and audit decisions.  Auditors Report, 17(1):8–12, 1993.
  * [67] Rajendra P Srivastava.  An introduction to evidential reasoning for decision making under uncertainty: Bayesian and belief function perspectives.  International Journal of Accounting Information Systems, 12(2):126–135, 2011.
  * [68] Rajendra P Srivastava and Glenn R Shafer.  Belief-function formulas for audit risk.  Accounting Review, pages 249–283, 1992.
  * [69] Lili Sun, Rajendra P Srivastava, and Theodore J Mock.  An information systems security risk assessment model under the dempster-shafer theory of belief functions.  Journal of Management Information Systems, 22(4):109–142, 2006\.
  * [70] Cass Sunstein.  Republic. com princeton.  Telhami, Shibley: 2010 Arab Public Opinion Poll (conducted by the University of, 2001.
  * [71] Petko Valtchev, Rokia Missaoui, and Robert Godin.  Formal concept analysis for knowledge discovery and data mining: The new challenges.  In International conference on formal concept analysis, pages 352–371. Springer, 2004.
  * [72] Peter Walley.  Statistical Reasoning with Imprecise Probabilities.  Chapman & Hall, 1991.
  * [73] Xiaohong Wang.  Reflections on the application of ai in auditing practice in the context of big data.  In The International Conference on Cyber Security Intelligence and Analytics, pages 1262–1267. Springer, 2019.
  * [74] Philip M Whitman.  Lattices, equivalence relations, and subgroups.  Bulletin of the American Mathematical Society, 52(6):507–522, 1946\.
  * [75] Rudolf Wille and Bernhard Ganter.  Formal concept analysis, 1996.
  * [76] Kuai Xu, Feng Wang, and Lin Gu.  Behavior analysis of internet traffic via bipartite graphs and one-mode projections.  IEEE/ACM Transactions on Networking, 22(3):931–942, 2013.
  * [77] Panpan Xu, Nan Cao, Huamin Qu, and John Stasko.  Interactive visual co-cluster analysis of bipartite graphs.  In 2016 IEEE Pacific Visualization Symposium (PacificVis), pages 32–39. IEEE, 2016.
  * [78] Ronald R Yager.  The entailment principle for dempster—shafer granules.  International Journal of Intelligent Systems, 1(4):247–262, 1986\.
  * [79] Ronald R Yager and Liping Liu.  Classic works of the Dempster-Shafer theory of belief functions, volume 219.  Springer, 2008.
  * [80] Yiyu Yao.  Interval sets and three-way concept analysis in incomplete contexts.  International Journal of Machine Learning and Cybernetics, 8(1):3–20, 2017.
  * [81] Hongyuan Zha, Xiaofeng He, Chris Ding, Horst Simon, and Ming Gu.  Bipartite graph partitioning and data clustering.  In Proceedings of the tenth international conference on Information and knowledge management, pages 25–32, 2001.

## Declaration of interest and disclaimer:

The authors report no conflicts of interest, and declare that they have no
relevant or material financial interests related to the research in this
paper. The authors alone are responsible for the content and writing of the
paper, and the views expressed here are their personal views and do not
necessarily reflect the position of their employer.

##  10 Appendix

######  Proposition 36.

For any set $W$, if $|W|\geq 2$, then $e\in J^{\infty}(\mathrm{E}(W))$ iff $e$
is identified by some partition of the form
$\mathcal{E}_{xy}:=\\{\\{x,y\\}\\}\cup\\{\\{z\\}\mid z\in
W\setminus\\{x,y\\}\\}$ with $x,y\in W$ such that $x\neq y$.

###### Proof.

By construction, any $e$ corresponding to some $\mathcal{E}_{xy}$ as above is
an atom, and hence a completely join-irreducible element of $\mathrm{E}(W)$.
Conversely, let $e$ be a completely join-irreducible element of
$\mathrm{E}(W)$. Then $e\neq\epsilon$, hence some $x,y\in W$ exist such that
$x\neq y$ and $(x,y)\in e$. To show that $e$ is identified by the partition
$\mathcal{E}_{xy}:=\\{\\{x,y\\}\\}\cup\\{\\{z\\}\mid z\in
W\setminus\\{x,y\\}\\}$, we need to show that (a) the $e$-equivalence class
$X$ of $x$ cannot contain three pairwise distinct elements, and (b) for any
$z\in W\setminus\\{x,y\\}$, the $e$-equivalence class $Z$ of $z$ is a
singleton. As to (a), assume for contradiction that $X$ contains three
pairwise distinct elements $x,y,z$. Hence, $X$ is both the union of two
disjoint subsets $X_{1}$ and $X_{2}$ such that $x\in X_{1}$ and $y,z\in X_{2}$
and is the union of two disjoint subsets $Y_{1}$ and $Y_{2}$ such that $y\in
Y_{1}$ and $x,z\in Y_{2}$. Then let $e_{1},e_{2}\in\mathrm{E}(W)$ be
respectively identified by the partitions
$\mathcal{E}_{1}:=\\{\\{X_{1},X_{2}\\}\cup\\{[w]_{e}\mid w\in W\setminus X\\}$
and $\mathcal{E}_{2}:=\\{Y_{1},Y_{2}\\}\cup\\{[w]_{e}\mid w\in W\setminus
X\\}$. By construction, $e=e_{1}\sqcup e_{2}$; however, $e\neq e_{1}$ and
$e\neq e_{2}$, which contradicts the assumption that $e$ is completely join-
irreducible. As to (b), by (a) and the assumptions, $X$ and $Z$ are disjoint
and $X$ contains two distinct elements. If $Z$ contains some $z^{\prime}\in W$
such that $z\neq z^{\prime}$, then $Z$ is the union of two disjoint subsets
$Z_{1}$ and $Z_{2}$ such that $z\in Z_{1}$ and $z^{\prime}\in Z_{2}$. Then let
$e_{1},e_{2}\in\mathrm{E}(W)$ be respectively identified by the partitions
$\mathcal{E}_{1}:=\\{\\{Z_{1},Z_{2}\\}\cup\\{[w]_{e}\mid w\in W\setminus Z\\}$
and $\mathcal{E}_{2}:=\\{\\{x\\},\\{y\\}\\}\cup\\{[w]_{e}\mid w\in W\setminus
X\\}$. By construction, $e=e_{1}\sqcup e_{2}$; however, $e\neq e_{1}$ and
$e\neq e_{2}$, which contradicts the assumption that $e$ is completely join-
irreducible. ∎

###  10.1 A Financial statements network example

The following table is a small database showing different transactions and
financial accounts used to obtain a small financial statements network
considered in examples.

Table 3: A small database with 12 business processes and 6 financial accounts. We use same TID to denote all credit and debit activities relating to a single business process. ID | TID | FA name | Value
---|---|---|---
1 | 1 | revenue | -100
2 | 1 | cost of sales | +100
3 | 2 | revenue | -400
4 | 2 | personal expenses | +400
5 | 3 | other expenses | +125
6 | 3 | cost of sales | +375
7 | 3 | revenue | -500
8 | 4 | tax | -125
9 | 4 | cost of sales | +500
10 | 4 | revenue | -375
11 | 5 | tax | -10
12 | 5 | cost of sales | +200
13 | 5 | revenue | -190
14 | 6 | other expenses | +50
15 | 6 | cost of sales | +450
16 | 6 | inventory | -500
17 | 7 | cost of sales | +400
18 | 7 | revenue | -300
19 | 7 | inventory | -100
20 | 8 | revenue | -150
21 | 8 | cost of sales | +150
22 | 9 | revenue | -250
23 | 9 | cost of sales | +250
24 | 10 | tax | -250
24 | 10 | personal expenses | +250
26 | 11 | revenue | -250
27 | 11 | personal expenses | +175
28 | 11 | other expenses | +75
29 | 12 | revenue | -250
30 | 12 | tax | -50
31 | 12 | personal expenses | +150
32 | 12 | other expenses | +150

The following table gives shows the many valued context obtained by
interpreting the business processes as objects and financial accounts as
features. The value of incidence relation denotes the share of given financial
account in given business process.

Table 4: The formal context obtained from transaction database given in Table LABEL:database_table. $I(a,x)=0$ for any $(a,x)$ pair not present in the table. Business process (a) | Financial account (x) |  Share of value (I(a,x))
---|---|---
1 ($a_{1}$) | revenue ($x_{2}$) | -1
1 ($a_{1}$) | cost of sales ($x_{3}$) | +1
2 ($a_{2}$) | revenue ($x_{2}$) | -1
2 ($a_{2}$) | personal expenses ($x_{4}$) | +1
3 ($a_{3}$) | other expenses ($x_{6}$) | +0.25
3 ($a_{3}$) | cost of sales ($x_{3}$) | +0.75
3 ($a_{3}$) | revenue ($x_{2}$) | -1
4 ($a_{4}$) | tax ($x_{1}$) | -0.25
4 ($a_{4}$) | cost of sales ($x_{3}$) | +1
4 ($a_{4}$) | revenue ($x_{2}$) | -0.75
5 ($a_{5}$) | tax ($x_{1}$) | -0.05
5 ($a_{5}$) | cost of sales ($x_{3}$) | +1
5 ($a_{5}$) | revenue ($x_{2}$) | -0.95
6 ($a_{6}$) | other expenses ($x_{6}$) | +0.1
6 ($a_{6}$) | cost of sales ($x_{3}$) | +0.9
6 ($a_{6}$) | inventory ($x_{5}$) | -1
7 ($a_{7}$) | cost of sales ($x_{3}$) | +1
7 ($a_{7}$) | inventory ($x_{5}$) | -0.25
7 ($a_{7}$) | revenue ($x_{2}$) | -0.75
8 ($a_{8}$) | revenue ($x_{2}$) | -1
8 ($a_{8}$) | cost of sales ($x_{3}$) | +1
9 ($a_{9}$) | revenue ($x_{2}$) | -1
9 ($a_{9}$) | other expenses ($x_{6}$) | +1
10 ($a_{10}$) | tax ($x_{1}$) | -1
10 ($a_{10}$) | personal expenses ($x_{4}$) | +1
11 ($a_{11}$) | revenue($x_{2}$) | -1
11 ($a_{11}$) | personal expenses ($x_{4}$) | +0.7
11 ($a_{11}$) | other expenses ($x_{6}$) | +0.3
12 ($a_{12}$) | revenue($x_{2}$) | -0.83
12 ($a_{12}$) | tax($x_{1}$) | -0.17
12 ($a_{12}$) | personal expenses ($x_{4}$) | +0.5
12 ($a_{12}$) | other expenses ($x_{6}$) | +0.5

###  10.2 B concept lattices obtained in different examples

In this Section, we give the diagrams of various concept lattices arising from
the different examples in Section 8. These concept lattices were drawn with
the help of lattice visualization by LatViz [43, 2, 3, 1].

Figure 4: Concept lattice 1 Figure 5: Concept lattice 2 Figure 6: Concept
lattice 3 Figure 7: Concept lattice 4 Figure 8: Concept lattice 5 Figure 9:
Concept lattice 6 Figure 10: Concept lattice 7 Figure 11: Concept lattice 8
Figure 12: Concept lattice 9 Figure 13: Concept lattice 10