Minkowski Operations of Sets
with Application to Robot Localization
Benoit Desrochers,

Luc Jaulin

DGA Tn, Lab-Sticc
Brest, France
benoit.desrochers@ensta-bretagne.org

Ensta Bretagne, Lab-Sticc
Brest, France
luc.jaulin@gmail.com

This papers shows that using separators, which is a pair of two complementary contractors, we can
easily and efficiently solve the localization problem of a robot with sonar measurements in an unstructured environment. We introduce separators associated with the Minkowski sum and the Minkowski
difference in order to facilitate the resolution. A test-case is given in order to illustrate the principle
of the approach.

1

Introduction

Interval analysis [14] is a tool which makes it possible to compute with sets even when nonlinear functions are involved [10] in the definition of the sets. Interval methods are generally used to solve equations
or optimization problems [5] but can also been used to solve set-membership problems where the sets
are represented by subpavings [7]. The efficiency of interval algorithms can be improved by the use of
contractors [2] or (separators [6] which correspond to pairs of contractors).
This paper deals with localization of a robot with sonar rangefinders in a unstructured environment.
This problem is considered as difficult due to the fact that the sonar returns a measurement under the
form of an impact point inside an emission cone. This specific type of measurement makes the problem
partially observable. Moreover, our environment is not represented by geometric features such as segments or disks, but by an image which cannot be translated into equations. Now, as shown by Sliwka
[17], an unstructured map can be cast into a contractor form which allows us to use contractor/separator
algebra.
Here, we propose first to use a separator-based method to perform a reliable simulation necessary
to generate realistic data (see, e.g., [18] for a survey on reliable simulation). Then, once these data
have been generated, we consider the inverse problem, i.e., the robot localization with large-cone sonar
measurements in an unstructured map. This problem has never been considered yet, to our knowledge
at least in an unstructured environment (see e.g., [9, 11, 8, 12, 3] in the case where the map is made
with geometrical features). We will also show the link with Minkowski operations and propose separator
counterparts for these operations.
Section 2 recalls the basic notions on contractors and separators needed to understand our approach.
Section 3 presents the concept of set-to-set transform and shows how our localization problem can be
solved with separators. Section 4 proposes to formulate the Minkowski operations as a specific set-to-set
transform, corresponding to translations. Section 5 illustrates the application of the Minkowski operation
to the problem of localization of a robot in an unstructured environment. Section 6 concludes the paper.
E. Ábrahám and S. Bogomolov (Eds.): 3rd International
Workshop on Symbolic and Numerical Methods for Reachability
Analysis (SNR 2017)
EPTCS 247, 2017, pp. 34–45, doi:10.4204/EPTCS.247.3

B. Desrochers, L. Jaulin

35

Figure 1: Contractor consistent with to the set X

2

Contractors and Separators

This section recalls the basic notions on intervals, contractors and separators that are needed to understand the contribution of this paper. An interval of R is a closed connected set of R. A box [x] of Rn is
the Cartesian product of n intervals.
A contractor C is an operator IRn 7→ IRn such that
C ([x]) ⊂ [x]
[x] ⊂ [y] ⇒ C ([x]) ⊂ C ([y]).

(contractance)
(monotonicity)

(1)

We define the inclusion between two contractors C1 and C2 as follows:
C1 ⊂ C2 ⇔ ∀ [x] ∈ IRn , C1 ([x]) ⊂ C2 ([x]).

(2)

A set X is consistent (See Figure 1) with the contractor C (we will write X ∼ C ) if for all [x], we have
C ([x]) ∩ X = [x] ∩ X.

(3)

Two contractors C and C1 are equivalent (we will write C ∼ C1 ) if we have:
X ∼ C ⇔ X ∼ C1 .

(4)

A contractor C is minimal if for any other contractor C1 , we have the following implication
C ∼ C1 ⇒ C ⊂ C1 .
Example 1. The minimal contractor CX consistent with the set

X = x ∈ R2 , (x1 − 2)2 + (x2 − 2.5)2 ∈ [1, 4]

(5)

(6)

can be built using a forward-backward constraint propagation [1] [4]. The contractor CX can be used by
a paver to obtain an outer approximation for X. This is illustrated by Figure 2 (left) where CX removes
parts of the space outside X (painted light-gray). But due to the consistency property (see Equation (3))

36

Minkowski Operations for Localization

4

4

3

3

2

2

1

1

0

0

1

2

3

4

0

0

1

2

3

4

Figure 2: Paving associated to Example 1, Left: paving obtained using the contractor, Right: paving
obtained using the separator. Dark gray boxes belong X (the ring); light gray boxes are outside X. No
conclusion can be given on the white boxes.
CX has no effect on boxes included in X. A box partially included in X can not be eliminated and is
bisected, except if its length is larger than an given value ε. The contractor CX only provides an outer
approximation of X.
If C1 and C2 are two contractors, we define the following operations [2].
(C1 ∩ C2 )([x]) = C1 ([x]) ∩ C2 ([x])

(7)

(C1 ◦ C2 )([x]) = C1 (C2 ([x]))

(9)

(C1 t C2 )([x]) = C1 ([x]) t C2 ([x])

(8)

where t is the union hull defined by
[x] t [y] = [[x] ∪ [y]] .

(10)

In order to characterize an inner and outer approximation of the solution set, we introduce the notion
of separator.

A separator S is a pair of contractors S in , S out such that, for all [x] ∈ IRn , we have
S in ([x]) ∪ S out ([x]) = [x]

(complementarity).

(11)

A set X is consistent with the separator S (we will write X ∼ S ), if
X ∼ S out and X ∼ S in ,

(12)

where X = {x | x ∈
/ X}. This notion of separator is illustrated by Figure 3.
We define the inclusion between two separators S1 and S2 as follows
S1 ⊂ S2 ⇔ S1in ⊂ S2in and S1out ⊂ S2out .

(13)

B. Desrochers, L. Jaulin

37

[x]
X

S in([x])
S out([x])
[x]
Figure 3: Illustration of a separator on two different initial boxes. The outer contractor removes the blue
dashed area and the red dashed area is removed by the inner contractor
A separator S is minimal if

S1 ⊂ S ⇒ S1 = S .

(14)

It is trivial to check that S is minimal implies that the two contractors S in and S out are both minimal.
If we define the following operations

S1 ∩ S2 = S1in ∪ S2in , S1out ∩ S2out
(intersection)
(15)
S1 ∪ S2 = S1in ∩ S2in , S1out ∪ S2out
(union)
then we have [6]


S1 ∼ X1
⇒
S2 ∼ X2



S1 ∩ S2 ∼ X1 ∩ X2
S1 ∪ S2 ∼ X1 ∪ X2

(16)

Other operations on separators such as the complement or the projection can also be considered [6].
Example 2. Consider the set X of Example 1. From the contractor consistent with

/ [1, 4] ,
(17)
X = x ∈ R2 , (x1 − 2)2 + (x2 − 2.5)2 ∈

we can build a separator SX for X. An inner and outer approximation of X obtained by a paver based
on SX is depicted on Figure 2. The dark gray area is inside X and light gray is outside. The minimality
property of the separators can be observed by the fact that all contracted boxes of the subpaving touch
the boundary of X. Therefore, we are now able to quantify the pessimism introduced by the paver.

3

Set-to-set Transform

Notation. Consider a function


f:

Rn × R p −→
Rm
(a, p) −→ f(a, p)

(18)

For a given p ∈ R p , A ⊂ Rn , B ⊂ Rm , Z ⊂ Rn × R p , we shall use the following notations:
f(A, p)
f−1 (B)
pro jp (Z)
Z

= {b|∃a ∈ A, b = f(a, p)}
= {z = (a, p) |∃b ∈ B, b = f(a, p)}
= {p |∃a, (a, p) ∈ Z}
= {z | z ∈
/ Z}

(19)

38

Minkowski Operations for Localization

Many sets that are defined with quantifiers can be defined in terms of projection, inversion, complement
and composition.
An important problem where these operations occur is the set-to-set transform which is now defined.
Set-to-set transform. Consider the set defined by :
P = {p ∈ R p | f(A, p) ⊂ B}.

(20)

The vector p corresponds to a parameter vector associated to a transformation. A transformation p is
consistent, if after transformation of A, the set A is included inside B. We have
⇔
⇔
⇔
⇔

f(A, p) ⊂ B
∀a ∈ A, f(a, p) ∈ B
¬∃a ∈ A, f(a, p) ∈ B

¬∃a ∈ A, (a, p) ∈ f−1 B

¬∃a, (a, p) ∈ A × R p ∧ (a, p) ∈ f−1 B .

(21)

As a consequence

P = pro jp {(A × R p ) ∩ f−1 B }.

(22)


SP = pro jp {(SA × SR p ) ∩ f−1 SB }.

(23)

Therefore, if we have separators SA , SB for A, B then a separator SP for P can be obtained using
the separator algebra [6]. It is given by

Combining this separator with a paver, we are able to obtain an inner and outer approximation of P.
Example 1: A robot at position (0,0) in inside an environment defined by the map
M = {x ∈ R2 | x1 < 5 or x2 < 3}.

(24)

π
. For a simulation purpose, we want to compute
It emits an ultrasonic sound in the cone with angles π4 ± 24
the distance returned by the sonar. This distance corresponds to the shortest distance inside the emission
cone to the complementary of the map:

d = inf{d | f(S1 , d) ∩ M 6= 0}
/
or equivalently
d = sup{d | f(S1 , d) ⊂ M},

(25)

where S1 is the unit cone defined by
5π 7π
, ]}.
24 24
and f(x, d) = d · x is the scaling function. To solve our problem, we first characterize the set:
S1 = {(x, y) | x2 + y2 < 1 and atan2(y, x) ∈ [

D = {d | f(S1 , d) ⊂ M}

(26)

(27)

which corresponds to a set-to-set transform problem and we get
[0, 6.2988] ⊂ D ⊂ [0, 6.3085].

(28)

B. Desrochers, L. Jaulin

39

The situation is depicted on Figure 4. As a consequence, the true distance d returned by the sensor
satisfies d ∈ [6.2988, 6.3085]
y

6

M
4

2

f6.3 (S1 )
0

S1
0

2

4

6

8

x

Figure 4: The map M is represented by the white space outside the hatched area while the unit pie S1 is
painted in gray. The red pie represents the lower upper bound of D which almost touches the border of
the map.

4

Minkowski sum and difference

Minkowski operations are used in morphological mathematics to perform dilation or inflation of sets. As
it will be shown in Section 4, it can also be used for localization. Efficient algorithms (see e.g., [16]) have
been proposed to perform Minkowski operations with sets represented by subpavings. In this section,
we show Minkowski sum and difference can be see as a set-to-set transform. This will allow us to build
separators for these Minkowski operations.

4.1

Minkowski difference

Given two sets A ⊂ P(Rn ), B ⊂ P(Rn ), the Minkowski difference [15], denoted
B

A = {p | A + p ⊂ B}.

, defined by
(29)

Proposition 1. Given two separator SA and SB for A and B. Define the Minkowski difference of two
separators as

SB SA = pro jp {(SA × SRn ) ∩ f−1 SB }
(30)
where f(p, a) = a + p. The operator SB SA is a separator for B A.
Proof. Computing the Minkowski difference can be seen as a specific set-to-set transform problem
where f(p, a) = a+p , i.e., the transformation corresponds to a translation of vector p. As a consequence
B


A = pro jp {(A × R p ) ∩ f−1 B }.

(31)

A separator can thus be built for B A and a paver is then able to characterize B A.
Example 2: Let A be a rectangle of side’s length of 4 x 2, and B be a disk of radius 5. The resulting
solution set B A is depicted in Figure 5.

40

Minkowski Operations for Localization
y

y5

y5

4

A

B

2

B

3

A

3

1

1

x
-4

-2

2

4

x
-5

-3

-1

1

3

x
5

-5

-3

-1

1

-1

-1

-3

-3

-5

-5

3

5

-2

-4

Figure 5: Minkowski difference of the disk B and the rectangle A

4.2

Minkowski addition

Given two sets A ∈ P(Rn ), B ∈ P(Rn ), the Minkowski sum, denoted by ⊕, is defined by:
A ⊕ B = {a + b, a ∈ A, b ∈ B}.

(32)

Proposition 2. Given two separators SA and SB for A and B. The Minkowski sum of two separators
defined by
SA ⊕ SB = SB −SA
(33)

is a separator for A ⊕ B.
Proof. We have:

A⊕B =
=
=
=
=
=

{p | ∃a ∈ A, ∃b ∈ B, p = a + b}
{p | ∃a ∈ A, ∃b ∈ B, p − a = b}
{p | (p − A) ∩ B 6= 0}
/
{p | (p − A) ∩ B = 0}
/
{p | (p + (−A)) ⊂ B}(see Eq 29)
B −A.

(34)

Thus, a separator for the set A ⊕ B is SB −SA .
Example 3: Consider a triangle A and a square B. The Minkowski addition A⊕B is shown on Figure
6.
A⊕B
A

B

Figure 6: Minkowski sum of a square B and a triangle A computed using set membership algorithm.

B. Desrochers, L. Jaulin

5

41

Localization in an unstructured environment

Consider a robot R at position p = (p1 , p2 ) in an unstructured environment described by the set M. We
assume that the heading θ of R is known with a good accuracy (for instance, by using a compass) and
doesn’t need to be estimated. The robot is equipped several sonars which return the distance between the
robot and the map with respect to the emission cone of the sonar. This section deals with the localization
of the robots using the set-to-set transform. Several authors have already studied this problem using
interval analysis [12, 13, 3] but in an environment made with segments.
Each sensor emits an acoustic wave in its direction αi which propagates inside a cone of half angle
γ corresponding to the aperture of the beam. By measuring the time lag between the emission and the
reception of the wave, reflected by the map, an interval [di ] = [di− , di+ ] contains the true distance di to the
nearest obstacle which lies in the scope of the sensor can be obtained. The situation is depicted in Figure
7a. The area swept by the wave between 0 and di is free of obstacles whereas the map is hit by the wave
at distance di . Define
Si = {(x, y) | x2 + y2 < di− and atan2(y, x) ∈ [αi − γ, αi + γ]}
∆Si = {(x, y) | x2 + y2 ∈ [di ] and atan2(y, x) ∈ [αi − γ, αi + γ]}
The set Si is called the free sector and ∆Si is called the impact pie. These sets are depicted on Figure 7b.

γ

Si

di

∆Si

αi
(p1 , p2 )

(p1 , p2 )

(b) The free sector Si is represented by the dotted area while
the gray pie ∆Si contains the impact point.

(a) Emission cone.

Figure 7: Sensor model used by the robot.
The set of all feasible positions P consistent with [di ] is
/
P(i) = {p ∈ R2 | (p + Si ) ⊂ M and (p + ∆Si ) ∩ M 6= 0}
= (M

(35)

Si ) ∩ (M ⊕ −∆Si ).

With several measurements [di ] the set of all positions consistent with all data is
P=

\

(M

i

Si ) ∩ (M ⊕ −∆Si ).

(36)

42

Minkowski Operations for Localization

Denote by SM ,SSi ,S∆Si separators for M,Si ,∆Si . Then a separator for P is

SP =

\

(SM

i

SSi ) ∩ (SM ⊕ −S∆Si ).

(37)

As an illustration, consider the situation described by Figure 8 (left), where a robot collects 6 sonar
data. The width of the intervals corresponding to the range measurement is ±1m .The first measurement
corresponding to i = 1 is painted green. Figure 8 (right) corresponds to an approximation of the set
M S1 , obtained using a paver with the separator SM SS1 .

80

80

60

60

40

40

20

20

0

0

-20

-20

-40

-40

-60

-60

-80

-80
20

40

60

80

100

120

140

160

180

20

40

60

80

100

120

140

160

180

Figure 8: Left: a robot which collects 6 sonar range measurements. All free sectors Si are included in
the map M (in white) and the impact pies ∆Si , in yellow intersects M. Right: Set of all positions for the
robot consistent with the fact that the free sector S1 is inside M.

Figure 9 (left) corresponds to an approximation of the set M ⊕ −∆S1 , obtained using a paver with
the separator SM ⊕ −S∆S1 . It corresponds to the set of positions for the robot such that the impact pie
∆S1 intersects the outside of the map M. Figure 9 (right) corresponds to the set (M S1 ) ∩ (M ⊕ −∆S1 ),
i.e., it contains the position consistent with both ∆S1 and S1 .

B. Desrochers, L. Jaulin

43

80

80

60

60

40

40

20

20

0

0

-20

-20

-40

-40

-60

-60

-80

-80
20

40

60

80

100

120

140

160

180

20

40

60

80

100

120

140

160

180

Figure 9: Left: Positions for the robot consistent with the impact pie ∆S1 . Right: Positions consistent
with the free sector S1 and the impact pie ∆S1 .

Figure 10 (left) corresponds to an approximation of the set P, obtained using a paver on with the
separator SP . It corresponds to the set of positions for the robot that all six impact pies ∆Si intersect the
outside of the map M and all six free sectors are inside M. A zoom of the solution set is given in Figure
10 (right). The computing time is 127 sec. and 205 boxes have been generated. Note that obtaining an
inner approximation of the solution set was not possible using existing approaches that are not based on
separators.

80

60

-59

40

20

-60

0

-20

-40

-61

-60

99

-80
20

40

60

80

100

120

140

160

100

101

180

Figure 10: Left: Set of positions P for the robot consistent with all six free sectors Si and all impact pies
∆Si . Right: zoom around the solution set P.

44

6

Minkowski Operations for Localization

Conclusion

Separator-based techniques are particularly attractive when solving engineering applications, due to the
fact that they can handle and propagate uncertainties in a context where the equations of the problem
are non-linear and non-convex. Now, the performances of paving methods are extremely sensitive to
the accuracy of the separators but also by the uncertainty generated by the dependency effect induced
by the separator algebra. Indeed, when a separator, associated to the same set, occurs several times in
the separator expression, a pessimism is introduced. It is thus important to factorize subexpression with
separators into a single one which is computed separately by a specific algorithm. Another possibility
is to rewrite the set expression in order to avoid multioccurences. This is what we have done for the
Minkowski sum A ⊕ B and difference A B.
The efficiency of these new operators and their ability to get an inner and outer approximation of the
solution set was illustrated on the problem of the localization of a robot.

References
[1] Frédéric Benhamou, Frédéric Goualard, Laurent Granvilliers & Jean-François Puget (1999): Revising
Hull and Box Consistency. In: Proceedings of the 1999 International Conference on Logic Programming, Massachusetts Institute of Technology, Cambridge, MA, USA, pp. 230–244. Available at http:
//dl.acm.org/citation.cfm?id=341176.341208.
[2] G. Chabert & L. Jaulin (2009): Contractor Programming. Artificial Intelligence 173, pp. 1079–1100,
doi:10.1016/j.artint.2009.03.002.
[3] E. Colle & Galerne (2013): Mobile robot localization by multiangulation using set inversion. Robotics and
Autonomous Systems 61(1), pp. 39–48, doi:10.1016/j.robot.2012.09.006.
[4] V. Drevelle & P. Bonnifait (2012): iGPS: Global Positioning in Urban Canyons with Road Surface Maps.
IEEE Intelligent Transportation Systems Magazine 4(3), pp. 6–18, doi:10.1109/MITS.2012.2203222.
[5] E. R. Hansen (1992): Bounding the solution of interval linear equations. SIAM Journal on Numerical
Analysis 29(5), pp. 1493–1503, doi:10.1137/0729086.
[6] L. Jaulin & B. Desrochers (2014): Introduction to the Algebra of Separators with Application to Path Planning.
Engineering Applications of Artificial Intelligence 33, pp. 141–147,
doi:10.1016/j.engappai.2014.04.010.
[7] L. Jaulin, M. Kieffer, O. Didrit & E. Walter (2001): Applied Interval Analysis, with Examples in Parameter
and State Estimation, Robust Control and Robotics. Springer-Verlag, London, doi:10.1007/978-1-44710249-6.
[8] L. Jaulin, M. Kieffer, E. Walter & D. Meizel (2002): Guaranteed Robust Nonlinear Estimation with Application to Robot Localization. IEEE Transactions on systems, man and cybernetics; Part C Applications and
Reviews 32(4), pp. 374–382, doi:10.1109/TSMCC.2002.806747.
[9] L. Jaulin, E. Walter, O. Lévêque & D. Meizel (2000): Set Inversion for Chi-Algorithms, with Application to Guaranteed Robot Localization. Mathematics and Computers in Simulation 52(3-4), pp. 197–210,
doi:10.1016/S0378-4754(00)00150-6.
[10] R. B. Kearfott & V. Kreinovich, editors (1996): Applications of Interval Computations. Kluwer, Dordrecht,
the Netherlands, doi:10.1007/978-1-4613-3440-8.
[11] Michel Kieffer, Luc Jaulin, Eric Walter & Dominique Meizel (1999): Guaranteed mobile robot tracking
using interval analysis. In: MISC’99, Workshop on Application of Interval Analysis to System and Control,
Girona, Spain, pp. 347–360. Available at https://hal.archives-ouvertes.fr/hal-00844601.

B. Desrochers, L. Jaulin

45

[12] Olivier Leveque, Luc Jaulin, Dominique Meizel & Eric Walter (1997): Vehicle localization from inaccurate
telemetric data: a set inversion approach. In: 5th IFAC Symposium on Robot Control SY.RO.CO.’97, 1,
Nantes, France, pp. 179–186. Available at https://hal.archives-ouvertes.fr/hal-00844041.
[13] D. Meizel, O. Lévêque, L. Jaulin & E. Walter (2002): Initial Localization by Set Inversion. IEEE transactions
on robotics and Automation 18(6), pp. 966–971, doi:10.1109/TRA.2002.805664.
[14] R. E. Moore (1966):
Interval
doi:10.1126/science.158.3799.365.

Analysis.

Prentice-Hall,

Englewood

Cliffs,

NJ,

[15] L. Najman & H. Talbot (Eds) (1000): Mathematical morphology: from theory to applications. ISTE-Wiley,
doi:10.1002/9781118600788.
[16] Kenji Shoji (1991): Quadtree decomposition of binary structuring elements. In: Nonlinear Image Processing
II, Proc. SPIE 1451, doi:10.1117/12.44322.
[17] J. Sliwka, F. Le Bars, O. Reynet & L. Jaulin (2011): Using interval methods in the context of robust localization of underwater robots. In: NAFIPS 2011, El Paso, USA, doi:10.1109/NAFIPS.2011.5751922.
[18] W. Taha & A. Duracz (2015): Acumen: An Open-source Testbed for Cyber-Physical Systems Research. In:
CYCLONE’15, doi:10.1007/978-3-319-47063-4_11.

