00footnotetext: Support of the research of the first author by IGA, project
PřF 2023 010, and of the second author by the Austrian Science Fund (FWF),
project I 4579-N, entitled “The many facets of orthomodularity”, is gratefully
acknowledged.

# Properties and special filters of pseudocomplemented posets

Ivan Chajda and Helmut Länger

###### Abstract

Investigating the structure of pseudocomplemented lattices started ninety
years ago with papers by V. Glivenko, G. Birkhoff and O. Frink and this
structure was essentially developed by G. Grätzer. In recent years, some
special filters in pseudocomplemented and Stone lattices have been studied by
M. Sambasiva Rao. However, in some applications, in particular in non-
classical logics with unsharp logical connectives, pseudocomplemented posets
instead of lattices are used. This motivated us to develop an algebraic theory
of pseudocomplemented posets, i.e. we derive identities and inequalities
holding in such posets and we use them in order to characterize the so-called
Stone posets. Then we adopt several concepts of special filters and we
investigate their properties in pseudocomplemented posets. Moreover, we show
how properties of these filters influence algebraic properties of the
underlying pseudocomplemented posets.

AMS Subject Classification: 06A11, 06A15, 06D15

Keywords: Poset, pseudocomplemented poset, Stone poset, Stone identity,
filter, coherent filter, strongly coherent filter, closed filter, prime
filter, median filter

##  1 Introduction

Apart from V. Glivenko’s early work [11] from 1929, the study of
pseudocomplemented lattices started in 1957 with a solution of problem 70 of
the second edition [2] of G. Birkhoff’s monograph on lattice theory which
provided a characterization of Stone lattices by minimal prime ideals, see
[13]. The idea of a triple was conceived by G .Grätzer in 1961, see e.g. the
monograph [12], as a method for proving O. Frink’s conjecture on the
representation of Stone lattices, see [10]. More on pseudocomplemented and
Stone lattices can be found in [16] and [17].

Recently M. Sambasiva Rao [15] studied so-called median filters in
pseudocomplemented distributive lattices. Other results on filters in
pseudocomplemented posets can be found in [14].

In connection with non-classical logics the natural question arises if the
theory of pseudocomplemented lattices can be extended to posets. (For another
paper on pseudocomplemented posets cf. paper [14] by R. Halaš.) The authors
already published papers treating this topic, see e.g. [4], [7] and [8]. A
characterization of pseudocomplemented posets by triples similar to that for
lattices mentioned above was settled for particular cases by the first author
and R. Halaš in [3]. For relative pseudocomplementation in posets, see also
[5] and [6]. Moreover, a certain generalization of pseudocomplementation in
posets can be found in [9].

The aim of this paper is two-fold.

At first, we collect identities known to be valid in pseudocomplemented and
Stone lattices and establish their counterparts in pseudocomplemented and
Stone posets. It is evident that not all of these identities can be
transferred to posets, but a lot can be settled and proved. Section 3 contains
an algebraic theory of pseudocomplemented and Stone posets which, to the
authors’ knowledge, was not published before.

The second part of the paper (Section 4) is devoted to several special filters
in pseudocomplemented and Stone posets. We investigate relationships between
these filters and connections between such filters and the structure of the
underlying posets.

##  2 Basic concepts

In the following we identify singletons with their unique element, i.e. we
will often write $x$ instead of $\\{x\\}$.

Let $(P,\leq)$ be a poset, $a,b\in P$ and $A,B\subseteq P$. We define

$\displaystyle A\leq B$ $\displaystyle:\Leftrightarrow x\leq y\text{ for all
}xinA\text{ and all }y\in B,$ $\displaystyle L(A)$ $\displaystyle:=\\{x\in
P\mid x\leq A\\},$ $\displaystyle U(A)$ $\displaystyle:=\\{x\in P\mid A\leq
x\\}.$

Instead of $L(\\{a\\})$, $L(\\{a,b\\})$, $L(A\cup\\{b\\})$, $L(A\cup B)$ and
$L\big{(}U(A)\big{)}$ we simply write $L(a)$, $L(a,b)$, $L(A,b)$, $L(A,B)$ and
$LU(A)$, respectively. Analogously we proceed in similar cases. The expression
$a\vee b$ means that the supremum of $a$ and $b$ exists and that it is equal
to $a\vee b$. Dually, $a\wedge b$ means that the infimum of $a$ and $b$ exists
and that it is equal to $a\wedge b$. A poset $(P,\leq,0)$ with bottom element
$0$ is called pseudocomplemented if for every $x\in P$ there exists a greatest
element $x^{*}$ of $P$ satisfying $L(x,x^{*})=0$ which is equivalent to
$x\wedge x^{*}=0$. This element $x^{*}$ is called the pseudocomplement of $x$.
We then write $(P,\leq,{}^{*},0)$. It is easy to see that $1:=0^{*}$ is the
top element of $(P,\leq)$. Hence any pseudocomplemented poset is bounded and
we write $(P,\leq,{}^{*},0,1)$. If $(P,\leq,{}^{*},0,1)$ is a
pseudocomplemented poset and $a,b\in P$ then it is elementary to check that
the following holds:

  1. (i)

$a\leq b$ implies $b^{*}\leq a^{*}$,

  2. (ii)

$a\leq a^{**}$,

  3. (iii)

$a^{***}=a^{*}$,

  4. (iv)

$a\leq b^{*}$ if and only if $L(a,b)=0$ if and only if $b\leq a^{*}$.

An element $a$ of $P$ is called dense if $a^{*}=0$. Let $D$ denote the set of
all dense elements of $P$. Of course, $1\in D$.

######  Lemma 2.1.

Let $(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset and $a,b\in P$. Then
the following holds:

  1. (i)

$U(a^{*},b^{*})=1$ implies $L(a,b)=0$,

  2. (ii)

$\big{(}L(a,b)\big{)}^{*}\subseteq U(a^{*},b^{*})$,

  3. (iii)

$\big{(}U(a,b)\big{)}^{*}\subseteq L(a^{*},b^{*})$,

  4. (iv)

$U(a,a^{*})\subseteq D$.

###### Proof.

  1. (i)

If $c\in L(a,b)$ then $c^{*}\in U(a^{*},b^{*})=1$ and hence $c\leq c^{**}=0$
which implies $c=0$.

  2. (ii)

and (iii) follow from the fact that ∗ is antitone.

  3. (iv)

If $b\in U(a,a^{*})$ then $b^{*}\in L(a^{*},a^{**})=0$.

∎

We define

$\displaystyle A\leq_{1}B$ $\displaystyle:\Leftrightarrow\text{ for every
}a\in A\text{ there exists some }b\in B\text{ with }a\leq b,$ $\displaystyle
A\leq_{2}B$ $\displaystyle:\Leftrightarrow\text{ for every }b\in B\text{ there
exists some }a\in A\text{ with }a\leq b,$ $\displaystyle A=_{1}B$
$\displaystyle:\Leftrightarrow A\leq_{1}B\text{ and }B\leq_{1}A,$
$\displaystyle A=_{2}B$ $\displaystyle:\Leftrightarrow A\leq_{2}B\text{ and
}B\leq_{2}A,$ $\displaystyle A^{*}$ $\displaystyle:=\\{a^{*}\mid a\in A\\}.$

It is easy to see that

$\displaystyle A\leq B$ $\displaystyle\text{ implies }B^{*}\leq A^{*},$
$\displaystyle A\leq_{1}B$ $\displaystyle\text{ implies }B^{*}\leq_{2}A^{*},$
$\displaystyle A\leq_{2}B$ $\displaystyle\text{ implies }B^{*}\leq_{1}A^{*},$
$\displaystyle A=_{1}B$ $\displaystyle\text{ implies }A^{*}=_{2}B^{*},$
$\displaystyle A=_{2}B$ $\displaystyle\text{ implies }A^{*}=_{1}B^{*}.$

In the sequel $\operatorname{Max}A$ and $\operatorname{Min}A$ denotes the set
of all maximal and minimal elements of $A$, respectively. Let
$\mathbf{P}=(P,\leq)$ be a poset. $\mathbf{P}$ is said to satisfy the
Ascending Chain Condition (ACC, for short) if it has no infinite ascending
chains and it is said to satisfy the Descending Chain Condition (DCC, for
short) if it has no infinite descending chains. In particular, every finite
poset satisfies both the ACC and DCC. Note that if $\mathbf{P}$ satisfies the
ACC then every non-empty subset $A$ of $P$ has at least one maximal element,
i.e. the set $\operatorname{Max}A$ is non-empty, and if $\mathbf{P}$ satisfies
the DCC then every non-empty subset $A$ of $P$ has at least one minimal
element, i.e. the set $\operatorname{Min}A$ is non-empty. If $\mathbf{P}$
satisfies the ACC and $A\subseteq B$ then $A\leq_{1}\operatorname{Max}B$. If
$\mathbf{P}$ satisfies the DCC and $A\subseteq B$ then
$\operatorname{Min}B\leq_{2}A$. It is evident that the sets
$\operatorname{Max}A$ and $\operatorname{Min}A$ are antichains in
$\mathbf{P}$.

######  Example 2.2.

The poset visualized in Figure 1

$0$$a$$b$$c$$d$$1$Fig. 1Pseudocomplemented poset

is pseudocomplemented, but not a lattice. We have

$\begin{array}[]{l|rrrrrr}x&0&a&b&c&d&1\\\ \hline\cr x^{*}&1&b&a&0&0&0\\\
\hline\cr x^{**}&0&a&b&1&1&1\end{array}$

and $D=\\{c,d,1\\}$.

######  Example 2.3.

The poset depicted in Figure 2

$0$$a$$b$$c$$d$$e$$f$$1$Fig. 2Pseudocomplemented poset

is pseudocomplemented, but not a lattice. We have

$\begin{array}[]{l|rrrrrrrr}x&0&a&b&c&d&e&f&1\\\ \hline\cr
x^{*}&1&f&c&f&0&0&c&0\\\ \hline\cr x^{**}&0&c&f&c&1&1&f&1\end{array}$

and $D=\\{d,e,1\\}$.

######  Remark 2.4.

As mentioned above, the sets $\operatorname{Max}L(x,y)$ and
$\operatorname{Min}U(x,y)$ are antichains for all $x,y\in P$. However, if a
subset $A$ is an antichain then $A^{*}$ need not be an antichain. For example,
the set $\\{c,d\\}$ in the poset visualized in Fig. 2 is an antichain but
$\\{c,d\\}^{*}=\\{c^{*},d^{*}\\}=\\{0,f\\}$ is not an antichain. Even the set
$\big{(}\operatorname{Max}L(x,y)\big{)}^{*}$ need not be an antichain, see the
following example.

######  Example 2.5.

The poset depicted in Figure 3

$0$$a$$b$$c$$d$$e$$f$$g$$1$Fig. 3Pseudocomplemented poset

is pseudocomplemented, but not a lattice. We have

$\begin{array}[]{l|rrrrrrrrr}x&0&a&b&c&d&e&f&g&1\\\ \hline\cr
x^{*}&1&d&e&0&e&d&0&0&0\\\ \hline\cr x^{**}&0&e&d&1&d&e&1&1&1\end{array}$

and $D=\\{c,f,g,1\\}$. We have

$\big{(}\operatorname{Max}L(f,g)\big{)}^{*}=(\\{c,d\\})^{*}=\\{c^{*},d^{*}\\}=\\{0,e\\}$

which is not an antichain.

If $(P,\leq)$ is a poset and $A$ a subset of $P$ and if $L(x^{*},y)\neq 0$ and
$L(x,y^{*})\neq 0$ for all $x,y\in A$ with $x\neq y$ then both $A$ and $A^{*}$
are antichains, for instance if there would exist $a,b\in A$ with $a<b$ then
$L(a,b^{*})\subseteq L(b,b^{*})=0$ and hence we would obtain $L(a,b^{*})=0$, a
contradiction. The other cases can be treated analogously.

######  Remark 2.6.

Let $\mathbf{P}=(P,\leq)$ be a poset, $A$ an antichain of $\mathbf{P}$ and
$B\subseteq P$ and assume $A=_{1}B$. Then $A\subseteq B$. This can be seen as
follows: Assume $a\in A$. Since $A\leq_{1}B$ there exists some $b\in B$ with
$a\leq b$. Since $B\leq_{1}A$ there exists some $c\in A$ with $b\leq c$.
Because of transitivity we have $a\leq c$. Since $A$ is an antichain of
$\mathbf{P}$ we conclude $a=c$ and hence $a=b\in B$. This shows $A\subseteq
B$. In a similar way one can prove that $A\subseteq B$ provided $A=_{2}B$
instead of $A=_{1}B$. If both $A$ and $B$ are antichains of $\mathbf{P}$ and
either $A=_{1}B$ or $A=_{2}B$, we obtain $A=B$. If $A=_{2}B$ then $A=1$ if and
only if $B=1$. This can be seen as follows: Assume $A=1$. Then $B=_{2}1$.
Because of $B\leq_{2}1$ we have $B\neq\emptyset$. On the other hand,
$1\leq_{2}B$ implies $B=1$. The converse implication follows by symmetry.

##  3 Properties of pseudocomplements in bounded posets

In this section we present identities and inequalities holding in
pseudocomplemented posets and compare these identities and inequalities with
the corresponding identities holding in pseudocomplemented lattices.

We start with a list of several important properties of bounded
pseudocomplemented posets.

######  Theorem 3.1.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset. If
$\mathbf{P}$ satisfies the ACC then the following holds:

  1. (i)

$\operatorname{Max}L(x^{*},y^{*})\approx_{1}\big{(}\operatorname{Max}L(x^{*},y^{*})\big{)}^{**}$,

  2. (ii)

$\operatorname{Max}L\Big{(}x,\big{(}\operatorname{Max}L(x^{*},y)\big{)}^{*}\Big{)}\approx
x$,

  3. (iii)

$\operatorname{Max}L(x,y)\leq_{1}\operatorname{Max}L(x^{**},y)\leq_{1}\operatorname{Max}L(x^{**},y^{**})$
for all $x,y\in P$,

  4. (iv)

$\operatorname{Max}L(x,y)\leq_{1}\operatorname{Max}L(x,y^{**})\leq_{1}\operatorname{Max}L(x^{**},y^{**})$
for all $x,y\in P$,

  5. (v)

$\big{(}\operatorname{Max}L(x,y)\big{)}^{**}\leq_{1}\operatorname{Max}L(x^{**},y^{**})$
for all $x,y\in P$.

If $\mathbf{P}$ satisfies the DCC then the following holds:

  1. (vi)

$\operatorname{Min}U(x,y)\leq_{2}\operatorname{Min}U(x^{**},y)\leq_{2}\operatorname{Min}U(x^{**},y^{**})$
for all $x,y\in P$,

  2. (vii)

$\operatorname{Min}U(x,y)\leq_{2}\operatorname{Min}U(x,y^{**})\leq_{2}\operatorname{Min}U(x^{**},y^{**})$
for all $x,y\in P$,

  3. (viii)

$\operatorname{Min}U(x^{**},y^{**})\leq_{2}\big{(}\operatorname{Min}U(x,y)\big{)}^{**}$
for all $x,y\in P$.

If $\mathbf{P}$ satisfies both the ACC and the DCC then the following holds:

  1. (ix)

$\big{(}\operatorname{Min}U(x,y)\big{)}^{*}\approx_{1}\operatorname{Max}L(x^{*},y^{*})$,

  2. (x)

$\operatorname{Min}U(x^{*},y^{*})\leq_{2}\big{(}\operatorname{Max}L(x,y)\big{)}^{*}$
for all $x,y\in P$.

###### Proof.

Let $a,b\in P$.

  1. (i)

$\operatorname{Max}L(a^{*},b^{*})\leq a^{*}$ implies

$\big{(}\operatorname{Max}L(a^{*},b^{*})\big{)}^{**}\leq a^{***}=a^{*}.$

Analogously, $\big{(}\operatorname{Max}L(a^{*},b^{*})\big{)}^{**}\leq b^{*}$.
Hence $\big{(}\operatorname{Max}L(a^{*},b^{*})\big{)}^{**}\subseteq
L(a^{*},b^{*})$ whence
$\big{(}\operatorname{Max}L(a^{*},b^{*})\big{)}^{**}\leq_{1}\operatorname{Max}L(a^{*},b^{*})$.
If $c\in\operatorname{Max}L(a^{*},b^{*})$ then $c\leq
c^{**}\in\big{(}\operatorname{Max}L(a^{*},b^{*})\big{)}^{**}$. This shows
$\operatorname{Max}L(a^{*},b^{*})\leq_{1}\big{(}\operatorname{Max}L(a^{*},b^{*})\big{)}^{**}$.

  2. (ii)

We have $\operatorname{Max}L(a^{*},b)\leq a^{*}$ and hence $a\leq
a^{**}\leq\big{(}\operatorname{Max}L(a^{*},b)\big{)}^{*}$ whence

$L\Big{(}a,\big{(}\operatorname{Max}L(a^{*},b)\big{)}^{*}\Big{)}=L(a).$

  3. (iii)

This follows from $L(a,b)\subseteq L(a^{**},b)\subseteq L(a^{**},b^{**})$.

  4. (iv)

This follows from $L(a,b)\subseteq L(a,b^{**})\subseteq L(a^{**},b^{**})$.

  5. (v)

From (ii) and (i) we obtain
$\big{(}\operatorname{Max}L(a,b)\big{)}^{**}\leq_{1}\big{(}\operatorname{Max}L(a^{**},b^{**})\big{)}^{**}=_{1}\operatorname{Max}L(a^{**},b^{**})$.

  6. (vi)

This follows from $U(a^{**},b^{**})\subseteq U(a^{**},b)\subseteq U(a,b)$.

  7. (vii)

This follows from $U(a^{**},b^{**})\subseteq U(a,b^{**})\subseteq U(a,b)$.

  8. (viii)

We have
$\operatorname{Min}U(a^{**},b^{**})\leq_{2}\big{(}\operatorname{Max}L(a^{*},b^{*})\big{)}^{*}=_{2}\big{(}\operatorname{Min}U(a,b)\big{)}^{**}$
according to (vii) and (vi).

  9. (ix)

Since $a,b\leq\operatorname{Min}U(a,b)$ we have
$\big{(}\operatorname{Min}U(a,b)\big{)}^{*}\leq a^{*},b^{*}$ and hence
$\big{(}\operatorname{Min}U(a,b)\big{)}^{*}\subseteq L(a^{*},b^{*})$ whence
$\big{(}\operatorname{Min}U(a,b)\big{)}^{*}\leq_{1}\operatorname{Max}L(a^{*},b^{*})$.
Conversely, let $c\in\operatorname{Max}L(a^{*},b^{*})$. Then $c\leq
a^{*},b^{*}$ and hence $a,b\leq c^{*}$, i.e. $c^{*}\in U(a,b)$. Therefore
there exists some $d\in\operatorname{Min}U(a,b)$ with $d\leq c^{*}$. Now
$c\leq d^{*}\in\big{(}\operatorname{Min}U(a,b)\big{)}^{*}$ showing
$\operatorname{Max}L(a^{*},b^{*})\leq_{1}\big{(}\operatorname{Min}U(a,b)\big{)}^{*}$.

  10. (x)

Let $c\in\big{(}\operatorname{Max}L(a,b)\big{)}^{*}$. Then there exists some
$d\in\operatorname{Max}L(a,b)$ with $d^{*}=c$. Because of $d\leq a,b$ we have
$a^{*},b^{*}\leq d^{*}$, i.e. $d^{*}\in U(a^{*},b^{*})$. Hence there exists
some $e\in\operatorname{Min}U(a^{*},b^{*})$ with $e\leq d^{*}$. Therefore
$e\leq c$.

∎

The following result is in fact a corollary of Theorem 3.1.

######  Corollary 3.2.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset satisfying
the ACC and assume

  1. (1)

$\big{(}\operatorname{Max}L(x,y)\big{)}^{*}\leq_{2}\big{(}\operatorname{Max}L(x^{**},y^{**})\big{)}^{*}$
for all $x,y\in P$.

Then $\mathbf{P}$ satisfies the identities

  1. (i)

$\big{(}\operatorname{Max}L(x,y)\big{)}^{*}\approx_{2}\big{(}\operatorname{Max}L(x^{**},y^{**})\big{)}^{*}$,

  2. (ii)

$\big{(}\operatorname{Max}L(x,y)\big{)}^{**}\approx_{1}\operatorname{Max}L(x^{**},y^{**})$,

  3. (iii)

$\big{(}\operatorname{Max}L(x,y)\big{)}^{*}\approx_{2}\big{(}\operatorname{Max}L(x^{**},y)\big{)}^{*}\approx_{2}\big{(}\operatorname{Max}L(x,y^{**})\big{)}^{*}$.

###### Proof.

  1. (i)

We have

$\big{(}\operatorname{Max}L(a,b)\big{)}^{*}\leq_{2}\big{(}\operatorname{Max}L(a^{**},b^{**})\big{)}^{*}\leq_{2}\big{(}\operatorname{Max}L(a,b)\big{)}^{*}$

according to the assumption and to (iii) of Theorem 3.1.

  2. (ii)

We have

$\big{(}\operatorname{Max}L(a,b)\big{)}^{**}=_{1}\big{(}\operatorname{Max}L(a^{**},b^{**})\big{)}^{**}=_{1}\operatorname{Max}L(a^{**},b^{**})$

according to (i) and to (i) of Theorem 3.1.

  3. (iii)

We have

$L(a,b)\subseteq L(a^{**},b)\subseteq L(a^{**},b^{**})$

and hence

$\operatorname{Max}L(a,b)\leq_{1}\operatorname{Max}L(a^{**},b)\leq_{1}\operatorname{Max}L(a^{**},b^{**})$

whence

$\big{(}\operatorname{Max}L(a,b)\big{)}^{*}=_{2}\big{(}\operatorname{Max}L(a^{**},b^{**})\big{)}^{*}\leq_{2}\big{(}\operatorname{Max}L(a^{**},b)\big{)}^{*}\leq_{2}\big{(}\operatorname{Max}L(a,b)\big{)}^{*}$

according to (i). The assertion
$\big{(}\operatorname{Max}L(a,b)\big{)}^{*}=_{2}\big{(}\operatorname{Max}L(a,b^{**})\big{)}^{*}$
follows by symmetry.

∎

The assumed inequality (1) is natural since it is satisfied in the case where
the poset is a lattice (see Theorem 3.10). However, it is not satisfied in the
poset from Fig. 2 since

$\displaystyle\big{(}\operatorname{Max}L(d,e)\big{)}^{*}$
$\displaystyle=(\operatorname{Max}\\{0,a,b\\})^{*}=\\{a,b\\}^{*}=\\{c,f\\}\not\leq_{2}0=1^{*}=$
$\displaystyle=(\operatorname{Max}\\{0,a,b,c,d,e,f,1\\})^{*}=\big{(}\operatorname{Max}L(1,1)\big{)}^{*}=\big{(}\operatorname{Max}L(d^{**},e^{**})\big{)}^{*}.$

In the sequel we will often deal with Stone posets. We define

######  Definition 3.3.

A Stone poset is a pseudocomplemented poset $(P,\leq,{}^{*},0,1)$ satisfying
both the ACC and the DCC as well as

$\big{(}\operatorname{Max}L(x^{*},y^{*})\big{)}^{*}\leq_{2}\operatorname{Min}U(x^{**},y^{**})\text{
for all }x,y\in P.$

Stone posets can be characterized by identities, see the following result.

######  Theorem 3.4.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset satisfying
both the ACC and the DCC. Then the following are equivalent:

  1. (i)

$\mathbf{P}$ is a Stone poset,

  2. (ii)

$\mathbf{P}$ satisfies the identity
$\big{(}\operatorname{Max}L(x^{*},y^{*})\big{)}^{*}\approx_{2}\operatorname{Min}U(x^{**},y^{**})$,

  3. (iii)

$\mathbf{P}$ satisfies the identity
$\big{(}\operatorname{Min}U(x,y)\big{)}^{**}\approx_{2}\operatorname{Min}U(x^{**},y^{**})$.

###### Proof.

(i) $\Leftrightarrow$ (ii):
This follows from (x) of Theorem 3.1.
(ii) $\Leftrightarrow$ (iii):
According to (ix) of Theorem 3.1 we have
$\big{(}\operatorname{Min}U(x,y)\big{)}^{**}\approx_{2}\big{(}\operatorname{Max}L(x^{*},y^{*})\big{)}^{*}$.
∎

Assertion (iii) of Theorem 3.4 implies that $\mathbf{P}$ satisfies the
identities

$\displaystyle\big{(}\operatorname{Min}U(x^{*},y^{*})\big{)}^{**}$
$\displaystyle\approx_{2}\operatorname{Min}U(x^{***},y^{***})\approx\operatorname{Min}U(x^{*},y^{*}),$
$\displaystyle\big{(}\operatorname{Min}U(x,y)\big{)}^{*}$
$\displaystyle\approx\big{(}\operatorname{Min}U(x,y)\big{)}^{***}\approx_{1}\big{(}\operatorname{Min}U(x^{**},y^{**})\big{)}^{*}.$

######  Corollary 3.5.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset satisfying
the ACC and the DCC as well as the identity

  1. (2)

$\big{(}\operatorname{Min}U(x^{**},y^{**})\big{)}^{**}\approx_{2}\operatorname{Min}U(x^{**},y^{**})$.

Then $\mathbf{P}$ is a Stone poset.

###### Proof.

By (ix) of Theorem 3.1, $\mathbf{P}$ satisfies the identity

$\big{(}\operatorname{Min}U(x,y)\big{)}^{*}\approx_{1}\operatorname{Max}L(x^{*},y^{*})$

and hence also the identity

$\big{(}\operatorname{Min}U(x,y)\big{)}^{**}\approx_{2}\big{(}\operatorname{Max}L(x^{*},y^{*})\big{)}^{*}.$

Replacing $x$ by $x^{**}$ and $y$ by $y^{**}$ we obtain the identities

$\big{(}\operatorname{Min}U(x^{**},y^{**})\big{)}^{**}\approx_{2}\big{(}\operatorname{Max}L(x^{***},y^{***})\big{)}^{*}=_{1}\big{(}\operatorname{Max}L(x^{*},y^{*})\big{)}^{*}.$

Applying identity (2) we get the identity

$\operatorname{Min}U(x^{**},y^{**})\approx_{2}\big{(}\operatorname{Max}L(x^{*},y^{*})\big{)}^{*}$

which by (ii) of Theorem 3.4 is equivalent to $\mathbf{P}$ being a Stone
poset. ∎

Recall the following well-known concept. A Stone lattice is a distributive
pseudocomplemented lattice $(L,\vee,\wedge,{}^{*},0,1)$ satisfying the
identity $x^{*}\vee x^{**}\approx 1$.

In order to justify the name Stone posets for the posets defined in Definition
3.3 we prove that such posets satisfy the identity $U(x^{*},x^{**})\approx 1$
which is equivalent to $x^{*}\vee x^{**}\approx 1$. Hence such posets satisfy
the same identity as Stone lattices.

######  Lemma 3.6.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a Stone poset. Then $\mathbf{P}$
satisfies the identity

  1. (3)

$U(x^{*},x^{**})\approx 1$.

###### Proof.

According to Theorem 3.4 we have

$\operatorname{Min}U(x^{*},x^{**})\approx\operatorname{Min}U(x^{***},x^{**})\approx_{2}\big{(}\operatorname{Max}L(x^{**},x^{*}\big{)}^{*}\approx(\operatorname{Max}0)^{*}\approx
0^{*}\approx 1.$

Since both $\operatorname{Min}U(x^{*},x^{**})$ and $\\{1\\}$ are antichains we
obtain $\operatorname{Min}U(x^{*},x^{**})\approx 1$, i.e.
$U(x^{*},x^{**})\approx 1$. ∎

Identity (3) is called the Stone identity.

######  Remark 3.7.

Let us recall that a distributive lattice is a Stone lattice if and only if it
satisfies the identity

  1. (4)

$(x^{*}\wedge y^{*})^{*}\approx x^{**}\vee y^{**}$

(see Theorem 3.11). Since a pseudocomplemented poset satisfying both the ACC
and the DCC is a Stone poset if and only if it satisfies the identity

$\big{(}\operatorname{Max}L(x^{*},y^{*})\big{)}^{*}\approx_{2}\operatorname{Min}U(x^{**},y^{**}),$

which is nothing else than identity (4) translated to posets, we need not
assume distributivity within the definition of a Stone poset.

######  Example 3.8.

The posets depicted in Figure 4

$0$$a$$b$$c$$d$$e$$1$(a)Fig. 4Non-lattice Stone
posets$0$$a$$b$$c$$d$$e$$f$$g$$h$$i$$j$$1$(b)

are non-lattice Stone posets. For the poset in Fig. 4 (a) we have

$\begin{array}[]{l|rrrrrrr}x&0&a&b&c&d&e&1\\\ \hline\cr x^{*}&1&0&0&0&0&0&0\\\
\hline\cr x^{**}&0&1&1&1&1&1&1\end{array}$

and hence $D=\\{a,b,c,d,e,1\\}$. For the poset in Fig. 4 (b) we have

$\begin{array}[]{l|rrrrrrrrrrrr}x&0&a&b&c&d&e&f&g&h&i&j&1\\\ \hline\cr
x^{*}&1&j&i&h&g&f&e&d&c&b&a&0\\\ \hline\cr
x^{**}&0&a&b&c&d&e&f&g&h&i&j&1\end{array}$

and therefore it satisfies the identity $x^{**}\approx x$ and $D=\\{1\\}$.
Moreover, both posets satisfy inequality (1).

######  Remark 3.9.

Recall that a poset is called distributive if it satisfies the identity

$L\big{(}U(x,y),z\big{)}\approx LU\big{(}L(x,z),L(y,z)\big{)}.$

The Stone identity and distributivity are independent identities. Namely, the
poset from Fig. 1 is distributive but $U(a^{*},a^{**})=U(a,b)=\\{c,d,1\\}\neq
1$. On the other hand, the poset in Fig. 2 satisfies the Stone identity but it
is not distributive since

$\displaystyle L\big{(}U(c,d),e\big{)}$
$\displaystyle=L(e,1)=L(e)\neq\\{0,a,b\\}=L(d,e,1)=LU(0,a,b)=$
$\displaystyle=LU\big{(}L(c,e),L(d,e)\big{)}.$

One can compare our previous results with well-known properties of
pseudocomplemented lattices as found in [10] – [12], see the following two
theorems.

######  Theorem 3.10.

Every pseudocomplemented lattice satisfies the following identities:

  * •

$(x\wedge y)^{*}\approx(x^{**}\wedge y)^{*}\approx(x\wedge
y^{**})^{*}\approx(x^{**}\wedge y^{**})^{*}$,

  * •

$(x\wedge y)^{**}\approx x^{**}\wedge y^{**}$,

  * •

$x\wedge(x^{*}\wedge y)^{*}\approx x$,

  * •

$(x\vee y)^{*}\approx x^{*}\wedge y^{*}$.

The next result is well-known, see e.g. [12].

######  Theorem 3.11.

If $\mathbf{L}=(L,\vee,\wedge,{}^{*},0,1)$ is a distributive
pseudocomplemented lattice then the following are equivalent:

  1. (i)

$\mathbf{L}$ is a Stone lattice,

  2. (ii)

$\mathbf{L}$ satisfies the identity $(x^{*}\wedge y^{*})^{*}\approx x^{**}\vee
y^{**}$,

  3. (iii)

$\mathbf{L}$ satisfies the identity $(x\vee y)^{**}\approx x^{**}\vee y^{**}$.

Our assumption in Definition 3.3, namely
$\big{(}\operatorname{Max}L(x^{*},y^{*})\big{)}^{*}\leq_{2}\operatorname{Min}U(x^{**},y^{**})$
for all $x,y\in P$, is quite natural since if the poset in question is a
lattice, then it gets $(x^{*}\wedge y^{*})^{*}\leq x^{**}\vee y^{**}$ for all
$x,y\in P$ which is automatically satisfied in every Stone lattice as follows
from (ii) of Theorem 3.11.

######  Remark 3.12.

Assertion (iii) of Theorem 3.11 implies that $\mathbf{L}$ satisfies the
identities

$\displaystyle(x^{*}\vee y^{*})^{**}$ $\displaystyle\approx x^{***}\vee
y^{***}\approx x^{*}\vee y^{*},$ $\displaystyle(x\vee y)^{*}$
$\displaystyle\approx(x\vee y)^{***}\approx(x^{**}\vee y^{**})^{*}$

(see e.g. [12])

##  4 Filters

The concept of a filter of a poset was already introduced in [3]. Recall that
a non-empty subset of a poset $\mathbf{P}=(P,\leq)$ is called a filter of
$\mathbf{P}$ if

  * •

$a\in F$, $b\in P$ and $a\leq b$ together imply $b\in F$,

  * •

$a,b\in F$ implies $L(a,b)\cap F\neq\emptyset$.

The filter $F$ is called proper if $F\neq P$. For every $x\in P$ the set
$F_{x}:=\\{y\in P\mid x\leq y\\}$ is a filter of $\mathbf{P}$, the so-called
principal filter of $\mathbf{P}$ generated by $x$. In case $\mathbf{P}$
satisfies the DCC every filter of $\mathbf{P}$ is principal. This can be seen
as follows. Assume $\mathbf{P}$ to satisfy the DCC and let $F$ be a filter of
$\mathbf{P}$ and $a\in F$. Because of the DCC there exists some minimal
element $b$ of $F$ with $b\leq a$. Assume that $b$ is not the smallest element
of $F$. Then there exists some $c\in F$ with $b\not\leq c$. Since $F$ is a
filter of $\mathbf{P}$ there exists some $d\in L(b,c)\cap F$. Now $d=b$ would
imply $b\leq c$, a contradiction. This shows $d<b$ contradicting the
minimality of $b$. In particular, every filter of a finite pseudocomplemented
poset as well as of a Stone poset is principal.

######  Example 4.1.

All filters of the poset from Fig. 1 are given by:

$\displaystyle F_{0}$ $\displaystyle=\\{0,a,b,c,d,1\\},$ $\displaystyle F_{a}$
$\displaystyle=\\{a,c,d,1\\},$ $\displaystyle F_{b}$
$\displaystyle=\\{b,c,d,1\\},$ $\displaystyle F_{c}$
$\displaystyle=\\{c,1\\},$ $\displaystyle F_{d}$ $\displaystyle=\\{d,1\\},$
$\displaystyle F_{1}$ $\displaystyle=\\{1\\}.$

Hence the poset of all filters of a poset $\mathbf{P}$ satisfying the DCC
ordered by set inclusion is dually isomorphic to $\mathbf{P}$ and hence it is
lattice-ordered if and only if $\mathbf{P}$ has this property.

Let us note that e.g. the subset $D=\\{c,d,1\\}$ of $P$ from Fig. 1 is not a
filter of $\mathbf{P}$ since $c,d\in D$, but $L(c,d)\cap D=\emptyset$.

######  Lemma 4.2.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset, $F$ a
proper filter of $\mathbf{P}$ and $a\in P$. Then the following holds:

  1. (i)

$\\{a,a^{*}\\}\not\subseteq F$,

  2. (ii)

if $a^{*}\in F$ and $b\in\overline{a}$ then $\overline{b}\not\subseteq F$.

###### Proof.

  1. (i)

The inclusion $\\{a,a^{*}\\}\subseteq F$ would imply $\\{0\\}\cap
F=L(a,a^{*})\cap F\neq\emptyset$ and hence $0\in F$, i.e. $F=P$ contradicting
the fact that $F$ is proper.

  2. (ii)

Assume $a^{*}\in F$ and $b\in\overline{a}$. Since $F$ is proper, we conclude
$a\not\in F$ by (i). Now $b\in\overline{a}$ implies $a\in\overline{b}$.
Together we have $a\in\overline{b}\setminus F$ showing
$\overline{b}\not\subseteq F$.

∎

Next we generalize two concepts introduced by M. Sambasiva Rao in [15] to
pseudocomplemented posets.

Let $(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset and $A,B\subseteq P$.
We define

$\displaystyle\overline{A}$ $\displaystyle:=\\{x\in P\mid
U(x^{**},y^{**})=1\text{ for all }y\in A\\},$ $\displaystyle A^{D}$
$\displaystyle:=\\{x\in P\mid U(x,y)\subseteq D\text{ for all }y\in A\\}.$

######  Lemma 4.3.

Let $(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset and $A\subseteq P$.
Then $\overline{\emptyset}=\emptyset^{D}=P$ and $\overline{P}=P^{D}=D$.

###### Proof.

Let $a\in P$. Then the following are equivalent: $a\in\overline{P}$;
$U(a^{**},x^{**})=1$ for all $x\in P$; $U(a^{**},0^{**})=1$; $U(a^{**},0)=1$;
$U(a^{**})=1$; $a^{**}=1$; $a^{*}=0$; $a\in D$. This proves $\overline{P}=D$.
Moreover, the following are equivalent: $a\in P^{D}$; $U(a,x)\subseteq D$ for
all $x\in P$; $U(a,0)\subseteq D$; $U(a)\subseteq D$; $a\in D$. This shows
$P^{D}=D$. The rest of the proof is trivial. ∎

######  Lemma 4.4.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset, $a\in P$
and $A\subseteq P$. Then the following holds:

  1. (i)

$\overline{A}\subseteq A^{D}$,

  2. (ii)

if $\mathbf{P}$ is a Stone poset then $\overline{A}=A^{D}$ and hence $a^{*}\in
a^{D}$.

###### Proof.

Observe that $\overline{A}=\bigcap\limits_{x\in A}\overline{x}$ and
$A^{D}=\bigcap\limits_{x\in A}x^{D}$.

  1. (i)

Let $b\in\overline{a}$. Then $U(a^{**},b^{**})=1$. Let $c\in U(a,b)$. Then
$c^{**}\in U(a^{**},b^{**})=1$ and hence $c^{*}=0$, i.e. $c\in D$. This shows
$U(a,b)\subseteq D$ which means $b\in a^{D}$. We have proved
$\overline{a}\subseteq a^{D}$.

  2. (ii)

Assume $\mathbf{P}$ to be a Stone poset. According to (i),
$\overline{a}\subseteq a^{D}$. Now let $b\in a^{D}$. Then $U(a,b)\subseteq D$
and hence $\operatorname{Min}U(a,b)\subseteq D$ whence
$\big{(}\operatorname{Min}U(a,b)\big{)}^{*}=0$, i.e.
$\big{(}\operatorname{Min}U(a,b)\big{)}^{**}=1$. Due to Theorem 3.4 (iii) and
Remark 2.6 the last statement is equivalent to
$\operatorname{Min}U(a^{**},b^{**})=1$ which means the same as
$U(a^{**},b^{**})=1$, i.e. $b\in\overline{a}$. This shows
$a^{D}\subseteq\overline{a}$ and hence $\overline{a}=a^{D}$. According to
Lemma 3.6 we have $U(a^{***},a^{**})=U(a^{*},a^{**})=1$ and hence
$a^{*}\in\overline{a}\subseteq a^{D}$ by (i).

∎

######  Remark 4.5.

The pair $(A\mapsto\overline{A},A\mapsto\overline{A})$ of mappings is the
Galois-correspondence between $(2^{P},\subseteq)$ and $(2^{P},\subseteq)$
induced by the binary relation $\\{(x,y)\in P^{2}\mid U(x^{**},y^{**})=1\\}$
on $P$. Hence $A\mapsto\overline{\overline{A}}$ is a closure operator on
$(2^{P},\subseteq)$ and therefore the set $\\{\overline{A}\mid A\subseteq
P\\}$ of all subsets of $P$ closed under this closure operator forms a closure
system of $P$, i.e. it is closed under arbitrary intersections. This means
that the closed subsets of $P$ form a complete lattice with respect to set
inclusion with smallest element $\overline{P}=D$ and greatest element
$\overline{\emptyset}=P$ and we have the following properties for
$A,B\subseteq P$:

$\displaystyle A$ $\displaystyle\subseteq B\text{ implies
}\overline{B}\subseteq\overline{A},$ $\displaystyle A$
$\displaystyle\subseteq\overline{\overline{A}},$
$\displaystyle\overline{\overline{\overline{A}}}$
$\displaystyle=\overline{A},$ $\displaystyle A$
$\displaystyle\subseteq\overline{B}\text{ if and only if
}B\subseteq\overline{A}.$

Analogously, the pair $(A\mapsto A^{D},A\mapsto A^{D})$ is the Galois-
correspondence between $(2^{P},\subseteq)$ and $(2^{P},\subseteq)$ induced by
the binary relation $\\{(x,y)\in P^{2}\mid U(x,y)\subseteq D\\}$ on $P$. Hence
the set $\\{A^{D}\mid A\subseteq P\\}$ of all subsets of $P$ closed under the
closure operator $A\mapsto A^{DD}$ forms a complete lattice with respect to
set inclusion and we have analogous results as before.

Note that $\overline{A}$ as well as $A^{D}$ are order filters in $(P,\leq)$
and that for $a\in P$ we have $\overline{F_{a}}=\overline{a}$ as well as
$(F_{a})^{D}=a^{D}$.

The following result shows how the property of being a Stone poset influences
the properties of filters and, conversely, which properties of filters imply
the Stone identity.

######  Theorem 4.6.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset satisfying
both the ACC and the DCC. Consider the following statements:

  1. (i)

$\mathbf{P}$ is a Stone poset,

  2. (ii)

$\overline{F}=F^{D}$ for every filter $F$ of $\mathbf{P}$,

  3. (iii)

for each filters $F,G$ of $\mathbf{P}$ we have $F\cap G\subseteq D$ if and
only if $F\subseteq\overline{G}$,

  4. (iv)

$\overline{\overline{x}}=\overline{x^{*}}$ for all $x\in P$,

  5. (v)

$\overline{\overline{x}}\subseteq\overline{x^{*}}$ for all $x\in P$,

  6. (vi)

$\mathbf{P}$ satisfies the Stone identity $U(x^{*},x^{**})\approx 1$.

Then (i) $\Rightarrow$ (ii) $\Leftrightarrow$ (iii) $\Rightarrow$ (iv)
$\Rightarrow$ (v) $\Leftrightarrow$ (vi).

###### Proof.

Let $a,b,c\in P$. Since $\mathbf{P}$ satisfies the DCC, every filter of
$\mathbf{P}$ is principal. Moreover, $\overline{F_{a}}=\overline{a}$ and
$(F_{a})^{D}=a^{D}$.
(i) $\Rightarrow$ (ii):
This follows from Lemma 4.4.
(ii) $\Leftrightarrow$ (iii)
This follows from the fact that the statements

$F_{a}\cap F_{b}\subseteq D;U(a,b)\subseteq D;a\in b^{D}$

are equivalent and that the statements

$F_{a}\subseteq\overline{F_{b}};F_{a}\subseteq\overline{b};a\in\overline{b}$

are equivalent.
(ii) $\Rightarrow$ (iv):
Since $a,a^{*}\leq U(a,a^{*})$ we have $\big{(}U(a,a^{*})\big{)}^{*}\leq
a^{*},a^{**}$ and hence $\big{(}U(a,a^{*})\big{)}^{*}=0$ which implies
$U(a,a^{*})\subseteq D$, i.e. $a^{*}\in a^{D}=\overline{a}$ by (iii) from
which we conclude $\overline{\overline{a}}\subseteq\overline{a^{*}}$.
Conversely, assume $b\in\overline{a^{*}}$ and $c\in\overline{a}$. Then
$U(a^{**},c^{**})=1$ and hence $L(a^{*},c^{*})=0$ according to Lemma 2.1. This
shows $c^{*}\leq a^{**}$. Since $b\in\overline{a^{*}}$ we have
$U(a^{***},b^{**})=1$ and hence $L(a^{**},b^{*})=0$ again by Lemma 2.1.
Because of $c^{*}\leq a^{**}$ we obtain $L(b^{*},c^{*})=0$. According to Lemma
2.1 we conclude $\big{(}U(b,c)\big{)}^{*}\subseteq L(b^{*},c^{*})=0$ and hence
$\big{(}U(b,c)\big{)}^{*}=0$, i.e. $U(b,c)\subseteq D$ which means $b\in
c^{D}=\overline{c}$ by (iii). Thus we have proved $b\in\overline{x}$ for all
$x\in\overline{a}$ showing $b\in\overline{\overline{a}}$. Therefore
$\overline{a^{*}}\subseteq\overline{\overline{a}}$. Together we obtain
$\overline{\overline{a}}=\overline{a^{*}}$.
(iv) $\Rightarrow$ (v):
This is clear.
(v) $\Leftrightarrow$ (vi):
The following are equivalent: $U(a^{*},a^{**})=1$; $a\in\overline{a^{*}}$;
$\overline{\overline{a}}\subseteq\overline{a^{*}}$. ∎

Now we generalize a further concept (concerning filters) from [15] to
pseudocomplemented posets as follows.

######  Definition 4.7.

We call a filter $F$ of a pseudocomplemented poset $(P,\leq,{}^{*},0,1)$
coherent if $x\in F$, $y\in P$ and $\overline{x}=\overline{y}$ together imply
$y\in F$.

######  Lemma 4.8.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a Stone poset and $F$ a filter of
$\mathbf{P}$ and assume that for every $x\in P$, $x^{**}\in F$ implies $x\in
F$. Then $F$ is coherent.

###### Proof.

Let $a,b,c\in P$. Since $\mathbf{P}$ satisfies the DCC, $F$ is principal as
pointed out at the beginning of Section 4. Assume $b\in F_{a}$ and
$\overline{b}=\overline{c}$. Since $\mathbf{P}$ is a Stone poset we have
$U(a^{*},a^{**})=1$ and hence $U(a^{***},b^{**})=U(a^{*},b^{**})=1$ which
shows $a^{*}\in\overline{b}=\overline{c}$. Therefore
$U(a^{*},c^{**})=U(a^{***},c^{**})=1$ whence $L(a,c^{*})=0$ according to Lemma
2.1 showing $a\leq c^{**}$, i.e. $c^{**}\in F_{a}$ which implies $c\in F_{a}$
according to our assumption. ∎

For every pseudocomplemented poset $(P,\leq,{}^{*},0,1)$ we define an operator
$\pi$ as follows:

$\pi(A):=\\{x\in P\mid\text{for all }y\in P\text{ there exists some
}(z,u)\in\overline{x}\times A\text{ with }y\in\operatorname{Min}U(z,u)\\}$

for all $A\subseteq P$. We use this operator for introducing the next concept.

######  Definition 4.9.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset and $F$ a
filter of $\mathbf{P}$. Then $F$ is called

  * •

strongly coherent if $\pi(F)=F$,

  * •

closed if $\overline{\overline{F}}=F$.

######  Lemma 4.10.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset and $F$ a
filter of $\mathbf{P}$ and assume $F$ to be either strongly coherent or
closed. Then $F$ is coherent.

###### Proof.

Let $a\in F$ and $b\in P$ and suppose $\overline{a}=\overline{b}$. First
assume $F$ to be strongly coherent. Then $a\in\pi(F)$. This means that for
every $c\in P$ there exists some $(d,e)\in\overline{a}\times F$ with
$c\in\operatorname{Min}U(d,e)$. Since $\overline{a}=\overline{b}$ we have that
for every $c\in P$ there exists some $(d,e)\in\overline{b}\times F$ with
$c\in\operatorname{Min}U(d,e)$. This shows $b\in\pi(F)=F$. Hence $F$ is
coherent. If $F$ is closed then
$b\in\overline{\overline{b}}=\overline{\overline{a}}\subseteq\overline{\overline{F}}=F$
proving $F$ to be coherent. ∎

The next types of filters are defined as follows.

######  Definition 4.11.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset and $F$ a
filter of $\mathbf{P}$. Then $F$ is called

  * •

prime if it is proper and if $x,y\in P$ and $U(x,y)\subseteq F$ together imply
$\\{x,y\\}\cap F\neq\emptyset$,

  * •

a $D$-filter if $D\subseteq F$,

  * •

maximal if it is proper and if for every proper filter $G$ of $\mathbf{P}$,
$F\subseteq G$ implies $F=G$.

######  Theorem 4.12.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset and $F$ a
prime filter of $\mathbf{P}$. Consider the following statements:

  1. (i)

$F$ is a $D$-filter,

  2. (ii)

for any $x\in P$, $x\in F$ if and only if $x^{*}\not\in F$,

  3. (iii)

for any $x\in P$, $x\in F$ if and only if $x^{**}\in F$,

  4. (iv)

$x\in F$, $y\in P$ and $x^{*}=y^{*}$ together imply $y\in F$,

  5. (v)

$\overline{x}\subseteq F$ for all $x\in P\setminus F$.

Then (i) $\Leftrightarrow$ (ii) $\Leftrightarrow$ (iii) $\Leftrightarrow$ (iv)
$\Rightarrow$ (v).

###### Proof.

Let $a,b\in P$.
(i) $\Rightarrow$ (ii):
Because of Lemma 2.1 (iv) we have $U(a,a^{*})\subseteq D\subseteq F$. Since
$F$ is prime this implies $\\{a,a^{*}\\}\cap F\neq\emptyset$. On the other
hand, $\\{a,a^{*}\\}\subseteq F$ is not possible because of Lemma 4.2.
(ii) $\Rightarrow$ (iii):
If $a\in F$ then $a^{**}\in F$ because of $a\leq a^{**}$. Conversely, if
$a^{**}\in F$ then $a^{*}\notin F$ because of Lemma 4.2 which implies $a\in F$
according to (ii).
(iii) $\Rightarrow$ (iv):
If $a\in F$ and $a^{*}=b^{*}$ then $b^{**}=a^{**}\in F$ because of (iii) and
hence $b\in F$ again according to (iii).
(iv) $\Rightarrow$ (i):
If $a\in D$ then $1\in F$ and $1^{*}=0=a^{*}$ from which we conclude $a\in F$
by (iv).
(i) $\Rightarrow$ (v):
Assume $a\in P\setminus F$ and $b\in\overline{a}$. Then $b\in a^{D}$ according
to Lemma 4.4 whence $U(a,b)\subseteq D\subseteq F$. Since $a\not\in F$ and $F$
is prime, we conclude $b\in F$. ∎

We can use Theorem 4.12 and Lemma 4.2 to prove the following result.

######  Proposition 4.13.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset and $F$ a
filter of $\mathbf{P}$. Then any of the following statements implies the next
one:

  1. (i)

$F$ is a prime $D$-filter of $\mathbf{P}$,

  2. (ii)

$x\in P\setminus F$ implies $x^{*}\in F$,

  3. (iii)

$F$ is a maximal filter of $\mathbf{P}$.

###### Proof.

(i) $\Rightarrow$ (ii):
This follows from Theorem 4.12.
(ii) $\Rightarrow$ (iii):
Assume that (ii) holds and (iii) does not hold. Then there exists some proper
filter $G$ of $\mathbf{P}$ strictly including $F$. Choose $a\in G\setminus F$.
Since $a\in P\setminus F$ we conclude $a^{*}\in F$ by (ii). But then
$a,a^{*}\in G$ contradicting the fact that $G$ is proper (see Lemma 4.2). ∎

Hence every prime $D$-filter of a pseudocomplemented poset is maximal.

The last kind of filters generalized from Sambasiva Rao’s paper [15] to
pseudocomplemented posets is defined as follows.

######  Definition 4.14.

A filter $F$ of a pseudocomplemented poset $\mathbf{P}=(P,\leq,{}^{*},0,1)$ is
called a median filter of $\mathbf{P}$ if $\overline{x}\not\subseteq F$ for
all $x\in F$.

We can characterize median filters as follows.

######  Proposition 4.15.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset and $F$ a
prime $D$-filter of $\mathbf{P}$. Then the following are equivalent:

  1. (i)

$F$ is median,

  2. (ii)

for all $x\in P$, $x\in F$ if and only if $\overline{x}\not\subseteq F$,

  3. (iii)

for all $x\in P$, $x^{**}\in F$ implies $\overline{x}\not\subseteq F$.

###### Proof.

Let $a\in P$.
(i) $\Rightarrow$ (ii):
If $a\in F$ then $\overline{a}\not\subseteq F$ because of (i), and if
$a\not\in F$ then $\overline{a}\subseteq F$ according to Lemma LABEL:lem5.
(ii) $\Rightarrow$ (iii):
Assume $a^{**}\in F$. Then $a\in F$ according to Theorem 4.12. By (ii) this
implies $\overline{a}\not\subseteq F$.
(iii) $\Rightarrow$ (i):
Assume $a\in F$. Since $a\leq a^{**}$ and $F$ is a filter of $\mathbf{P}$ we
have $a^{**}\in F$. According to (iii) this implies $\overline{a}\not\subseteq
F$. ∎

Finally, we show some properties of median $D$-filters.

######  Theorem 4.16.

Let $\mathbf{P}=(P,\leq,{}^{*},0,1)$ be a pseudocomplemented poset and $F$ a
median $D$-filter of $\mathbf{P}$. Then the following holds:

  1. (i)

If $F$ is prime then for all $x\in P$, $x\in F$ if and only if
$\overline{\overline{x}}\subseteq F$,

  2. (ii)

$F$ is coherent.

###### Proof.

Let $a\in F$. Since $F$ is median there exists some $c\in\overline{a}\setminus
F$.

  1. (i)

Assume $F$ to be prime. Let $b\in\overline{\overline{a}}$. Then
$c\in\overline{a}\subseteq\overline{b}$. Since $c\in P\setminus F$ we have
$\overline{c}\subseteq F$ according to Theorem 4.12. Hence
$b\in\overline{\overline{b}}\subseteq\overline{c}\subseteq F$. This shows
$\overline{\overline{a}}\subseteq F$. That for $x\in P$,
$\overline{\overline{x}}\subseteq F$ implies $x\in F$ follows from
$x\in\overline{\overline{x}}$.

  2. (ii)

Let $b\in P$ and assume $\overline{a}=\overline{b}$. Then
$c\in\overline{a}=\overline{b}\subseteq b^{D}$ according to Lemma 4.4. This
implies $U(b,c)\subseteq D\subseteq F$. Since $F$ is prime and $c\not\in F$ we
conclude $b\in F$.

∎

## References

  * [1] R. Balbes and A. Horn, Stone lattices. Duke Math. J. 37 (1970), 537–545.
  * [2] G. Birkhoff, Lattice Theory. AMS Colloq. Publ. 25, AMS, New York 1948.
  * [3] I. Chajda and R. Halaš, Characterizing triplets for modular pseudocomplemented ordered sets. Math. Slovaca 50 (2000), 513–524.
  * [4] I. Chajda, R. Halaš and J. Kühr, Semilattice Structures. Heldermann, Lemgo 2007. ISBN 978-3-88538-230-0.
  * [5] I. Chajda and H. Länger, Relatively pseudocomplemented posets. Math. Bohem. 143 (2018), 89–97.
  * [6] I. Chajda and H. Länger, Algebraic aspects of relatively pseudocomplemented posets. Order 37 (2020), 1–29.
  * [7] I. Chajda and H. Länger, Algebras describing pseudocomplemented, relatively pseudocomplemented and sectionally pseudocomplemented posets. Symmetry 13 (2021), 753 (17 pp.).
  * [8] I. Chajda and H. Länger, Algebraic structures formalizing the logic with unsharp implication and negation. Logic J. IGPL (2023) (13pp.).
  * [9] I. Chajda, H. Länger and J. Paseka, Sectionally pseudocomplemented posets. Order 38 (2021), 527–546.
  * [10] O. Frink, Pseudo-complements in semi-lattices. Duke Math. J. 29 (1962), 505–514.
  * [11] V. Glivenko, Sur quelques points de la logique de M. Brouwer. Bulletin Acad. Bruxelles 15 (1929), 183–188.
  * [12] G. Grätzer, Lattice Theory: Foundation. Birkhäuse/Springer, Basel 2011. ISBN 978-3-0348-0017-4.
  * [13] G. Grätzer and E. T. Schmidt, On a problem of M. H. Stone. Acta Math. Acad. Sci. Hungar. 8 (1957), 455–460.
  * [14] R. Halaš, Pseudocomplemented ordered sets. Arch. Math. (Brno) 29 (1993), 153–160.
  * [15] M. Sambasiva Rao, Median filters of pseudo-complemented distributive lattices. Discuss. Math. General Algebra Appl. (to appear).
  * [16] T. P. Speed, On Stone lattices. J. Austral. Math. Soc. 9 (1969), 297–307.
  * [17] G. Szász, Introduction to Lattice Theory. Academic Press, New York 1963.

Authors’ addresses:

Ivan Chajda
Palacký University Olomouc
Faculty of Science
Department of Algebra and Geometry
17\. listopadu 12
771 46 Olomouc
Czech Republic
<EMAIL_ADDRESS>
Helmut Länger
TU Wien
Faculty of Mathematics and Geoinformation
Institute of Discrete Mathematics and Geometry
Wiedner Hauptstraße 8-10
1040 Vienna
Austria, and
Palacký University Olomouc
Faculty of Science
Department of Algebra and Geometry
17\. listopadu 12
771 46 Olomouc
Czech Republic
<EMAIL_ADDRESS>


# Bayesian Simultaneous Localization and Multi-Lane Tracking Using Onboard
Sensors and a SD Map
††thanks: This work was partially supported by the Wallenberg AI, Autonomous
Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg
Foundation.

Yuxuan Xia†⋆, Erik Stenborg†, Junsheng Fu†, and Gustaf Hendeby⋆
†Zenseact, Gothenburg, Sweden
⋆Department of Electrical Engineering, Linköping University, Linköping, Sweden
Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

High-definition map with accurate lane-level information is crucial for
autonomous driving, but the creation of these maps is a resource-intensive
process. To this end, we present a cost-effective solution to create lane-
level roadmaps using only the global navigation satellite system (GNSS) and a
camera on customer vehicles. Our proposed solution utilizes a prior standard-
definition (SD) map, GNSS measurements, visual odometry, and lane marking edge
detection points, to simultaneously estimate the vehicle’s 6D pose, its
position within a SD map, and also the 3D geometry of traffic lines. This is
achieved using a Bayesian simultaneous localization and multi-object tracking
filter, where the estimation of traffic lines is formulated as a multiple
extended object tracking problem, solved using a trajectory Poisson multi-
Bernoulli mixture (TPMBM) filter. In TPMBM filtering, traffic lines are
modeled using B-spline trajectories, and each trajectory is parameterized by a
sequence of control points. The proposed solution has been evaluated using
experimental data collected by a test vehicle driving on highway. Preliminary
results show that the traffic line estimates, overlaid on the satellite image,
generally align with the lane markings up to some lateral offsets.

###### Index Terms:

Autonomous driving, lane-level mapping, multi-lane tracking, simultaneous
localization and mapping, B-spline.

##  I Introduction

High-definition (HD) maps with detailed lane-level information are an enabling
factor for autonomous driving, providing the necessary precision, safety, and
efficiency in localization, navigation, and decision-making processes [1].
However, the creation of HD maps is an expensive and resource-intensive
process, which typically involves using vehicles equipped with high-precision
equipment, such as lidar, to continuously collect and process the data. An
appealing, cost-effective alternative is to instead use onboard sensors
available in massive customer vehicles, such as the global navigation
satellite system (GNSS) and camera, to jointly create large-scale, lane-level
geometric maps. This approach is known as crowdsourced mapping [2], whereby
multiple sources of low-fidelity data are aggregated to create high-fidelity
maps.

In this paper, we focus on the problem of creating lane-level geometric maps,
which are built upon standard-definition (SD) maps with low geometric
fidelity, using single-antenna GNSS measurements and mono camera data
collected from a single vehicle traversal. This can serve as a solid
foundation for the follow-up map change detection, update, and merging tasks.
In particular, we aim to estimate the 3D geometry of traffic lines using lane
marking edge detection points obtained from a computer vision algorithm. Since
the accurate estimation of traffic line geometries relies on the precise
vehicle pose, which could hardly be obtained using only GNSS, the vehicle’s
pose and the traffic line geometries need to be simultaneously estimated. To
this end, we propose an effective solution that leverages a prior SD map, GNSS
measurements, visual odometry, and lane marking edge detection points to
simultaneously estimate the vehicle’s 6D pose, its position within a SD map,
and the 3D geometry of traffic lines.

Our proposed solution is achieved using a Bayesian simultaneous localization
and multi-object tracking (SLAMOT) filter, where the estimation of traffic
lines is formulated as a multiple extended object tracking (EOT) problem. Note
that, although traffic lines remain in fact static, in most cases they can
only be partially observed by the camera due to its limited field-of-view.
Thus, a dynamic model for the traffic lines is needed to make predictions of
their unseen geometries before each measurement update. The multiple EOT
problem is addressed using a trajectory Poisson multi-Bernoulli mixture
(TPMBM) filter, which is a state-of-the-art method for tracking objects that
may generate multiple detections per sensor scan [3, 4].

In Bayesian filtering, the state of each traffic line is modeled as a uniform
B-spline trajectory, parameterized by a sequence of control points. Compared
with models based on polylines or clothoids, B-splines can offer greater
flexibility and smoothness, making them well-suited for modeling traffic lines
with varying curvature [5]. The B-spline trajectory representations also
integrate smoothly with the sets of trajectories framework [6], and a
Bernoulli object spawning model can be easily incorporated to handle lane
splitting [7]. Furthermore, by leveraging the road orientation information
provided by the SD map in the lane marking measurement model, we can achieve
recursive B-spline estimation [8] under Gaussian approximations using a linear
Kalman filter.

###  I-A Related Work

In many existing works, e.g., [9, 10, 11, 12], the problem of lane-level map
generation using only onboard sensors is typically addressed using graph-based
optimization, whose performance can be highly dependent on the quality of data
associations of lane marking detection points. However, the data association
problem in these works is only addressed using simple heuristics, such as the
nearest neighbor approach, which may lead to inaccurate estimates in some
challenging cases, e.g., when the vehicle is moving on roads with multiple
parallel dashed lane markings. In contrast, our proposed solution uses a
Bayesian SLAMOT filter, which can handle the data association problem in a
principled way by leveraging data association techniques developed for
multiple EOT.

Multi-lane estimation has also been formulated as a multiple EOT problem in
[13] with polyline lane shape modeling and in [14] with Gaussian process lane
shape modeling. However, these works only consider multi-lane estimation on a
frame-by-frame basis, and they do not provide continuous, multi-lane estimates
over time, and thus cannot generate lane-level maps. The modeling of each
traffic line as a spline trajectory is also considered in [15, 16] using
Catmull-Rom splines. Compared to B-splines, Catmull-Rom splines do not
guarantee curvature continuity, which means that the transition between
segments may not be smooth.

###  I-B Contributions

Our proposed method stands out from the existing works by providing a fully
Bayesian solution to generate lane-level maps using onboard sensors.
Importantly, the multi-trajectory posterior density captures the uncertainties
in both the number of traffic lines and their geometries, which are important
for fusing the maps generated from multiple vehicle traversals.

The main contributions of this paper are as follows:

  1. 1.

We present a TPMBM-based SLAMOT filter and apply it to the problem of
simultaneous localization and multi-lane tracking using onboard sensors and a
SD map.

  2. 2.

We integrate recursive B-spline estimation into the extended object TPMBM
filter to estimate the 3D geometry of traffic lines using lane marking
detection points.

  3. 3.

The efficacy of proposed solution has been verified using real-world data.

The rest of the paper is organized as follows. In Section II, we describe the
system model. We present the problem formulation in Section III and the TPMBM-
based SLAMOT filter in Section IV. In Section V, we present the experimental
results. Finally, we conclude the paper in Section VI.

##  II System Model

In this section, we introduce the system modeling, which includes the SD map,
the state representations of vehicle and traffic lines, as well as their
dynamic and measurement models. We assume that the vision data has already
been transformed from the camera coordinate to the vehicle coordinate. States
and measurements in the vehicle coordinate are denoted with a superscript $l$,
and, if not otherwise specified, they are given in an East-North-Up coordinate
relative to a local origin.

We use $k\in\mathbb{N}_{0}$ to denote discrete time steps, and the time
instant at time step $k$ is $t_{k}$, with uniform time interval
$\tau=t_{k+1}-t_{k}$. The cardinality of a set $\mathbf{x}$ is denoted
$|\mathbf{x}|$. We use $\uplus$ to denote the union of sets that are mutually
disjoint and $\otimes$ to denote the Kronecker product. In addition, we use
$\delta_{x}[\cdot]$ and $\delta_{x}(\cdot)$ to represent the Kronecker delta
and the Dirac delta functions, respectively, centered at $x$.

###  II-A SD Map

The SD map can be represented as a directed graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of
nodes and $\mathcal{E}$ is the set of edges. Each node $v_{i}\in\mathcal{V}$
is associated with a 2D position $[x_{i},y_{i}]^{T}\in\mathbb{R}^{2}$, and
each edge $e_{i,j}\in\mathcal{E}$, with start and end nodes $v_{i}$ and
$v_{j}$, represents a street segment with direction from $v_{i}$ to $v_{j}$.
Each edge $e_{i,j}$ is described by its length $l_{e_{i,j}}$ and its
orientation $\phi_{e_{i,j}}$ via
$l_{e_{i,j}}=\|(x_{j}-x_{i},y_{j}-y_{i})\|_{2}$ and
$\phi_{e_{i,j}}={\displaystyle\arctan}\left(\frac{y_{j}-y_{i}}{x_{j}-x_{i}}\right)$.
As in [17], all the street segments are assumed to be one-way, and two-way
streets are converted to two one-way streets.

###  II-B Vehicle State

The vehicle’s 6D pose
$p_{k}=[x_{k},y_{k},z_{k},\alpha_{k},\beta_{k},\gamma_{k}]^{T}$ at time step
$k$ consists of its 3D position $[x_{k},y_{k},z_{k}]^{T}\in\mathbb{R}^{3}$,
and its yaw $\alpha_{k}$, pitch $\beta_{k}$, and roll $\gamma_{k}$. The
position of the vehicle $q_{k}=[e_{k},d_{k}]^{T}$ within a SD map is defined
by the street segment $e_{k}\in\mathcal{E}$ that the vehicle is moving on and
the distance $d_{k}$ from the start node of $e_{k}$. The inclusion of $d_{k}$
to the vehicle’s state representation may seem redundant, but as we shall see
later, it is helpful for modeling the transition of $e_{k}$. Also note that,
as the geometrical information provided by SD map may be inaccurate, the
distance $d_{k}$ may differ from the actual distance between the vehicle’s
position (projected onto $e_{k}$) and the start node of $e_{k}$. The complete
vehicle state $o_{k}=[p_{k}^{T},q_{k}^{T}]^{T}$ at time step $k$ is then 8D,
and it consists of the vehicle’s global 6D pose $p_{k}$ and its location
$q_{k}$ within a SD map $\mathcal{G}$.

####  II-B1 Vehicle Measurement Model

In this work, we assume that the GNSS only measures111The GNSS operates at a
lower frequency than the camera. We assume that the GNSS data has been
interpolated to be synchronized with the vision data. It is also possible to
directly work with low-frequency GNSS data by considering continuous-discrete
particle filtering. the vehicle’s 3D position, and the measurement at time
step $k$ is denoted as $\zeta_{k}$. Assuming that the measurement noise is
zero-mean Gaussian, the measurement model of GNSS is given by

$\ell_{k}(\zeta_{k}|p_{k})=\mathcal{N}\left(\zeta_{k};[x_{k},y_{k},z_{k}]^{T},\Omega_{k}\right),$
(1)

where $\Omega_{k}$ is the measurement noise covariance.

In addition to GNSS, the SD map $\mathcal{G}$ can also be regarded as a
measurement source, in the sense that the vehicle’s yaw $\alpha_{k}$ should
not diverge too much from the orientation of the street segment $e_{k}$ that
the vehicle is moving on. This measurement likelihood is specified by a von
Mises distribution [18]

$\ell_{k}(\mathcal{G}|o_{k})=\mathcal{VM}(\phi_{e_{k}}|\alpha_{k},\kappa),$
(2)

where $\mathcal{VM}(\cdot|\mu,\kappa)$ denotes a von Mises distribution with
mean $\mu$ and concentration parameter $\kappa$.

####  II-B2 Vehicle Motion Model

In this work, we assume that the vehicle motion estimates obtained from the
visual odometry can be used as control input222Vehicle odometry from wheel
encoders is used if visual odometry is not available, e.g., when the light
condition is poor., and that the SD map does not impose any constraints on the
vehicle’s motion. The vehicle state transition density can then be factorized
as

$g_{k+1}\left(p_{k+1},q_{k+1}|p_{k},q_{k},u^{l}_{k+1},\mathcal{G}\right)\\\
=g^{p}_{k+1}\left(p_{k+1}|p_{k},u^{l}_{k+1}\right)g^{q}_{k+1}(q_{k+1}|p_{k+1},q_{k},\mathcal{G}),$
(3)

where $u^{l}_{k+1}$ represents the control input in the vehicle coordinate at
time step $k+1$, and it can be transformed to the global coordinate $u_{k+1}$
using the vehicle’s pose $p_{k}$. Assuming that the process noise is zero-mean
Gaussian, the transition density of the vehicle’s pose at time step $k+1$ is
given by

$g^{p}_{k+1}\left(p_{k+1}|p_{k},u^{l}_{k+1}\right)=\mathcal{N}(p_{k+1};p_{k}+u_{k+1},Q_{k+1}),$
(4)

where $Q_{k+1}$ is the motion noise covariance.

The transition density $g^{q}_{k+1}(\cdot|p_{k+1},q_{k},\mathcal{G})$ of the
vehicle’s position within a SD map needs to consider the following two cases
depending on the distance the vehicle has moved on the street segment: 1) the
vehicle stays on the same street segment, and 2) the vehicle moves to a new
street segment. In the first case, we have $e_{k+1}=e_{k}$, and the vehicle’s
predicted distance to the start node of $e_{k}$ is modeled as
$d_{k+1}=d_{k}+\epsilon_{k+1}+\sigma_{k+1}$, where $\epsilon_{k+1}$ is the
vehicle’s moved distance along the street segment $e_{k}$, given by

$\epsilon_{k+1}=\cos(\phi_{e_{k}})(x_{k+1}-x_{k})+\sin(\phi_{e_{k}})(y_{k+1}-y_{k}),$
(5)

and $\sigma_{k+1}$ is a zero-mean Gaussian noise. Then for
$d_{k}+\epsilon_{k+1}\leq l_{e_{k}}$, we have

$g^{q}_{k+1}(q_{k+1}|p_{k+1},q_{k},\mathcal{G})=\delta_{e_{k}}[e_{k+1}]\mathcal{N}(d_{k+1};d_{k}+\epsilon_{k+1},\sigma_{k+1}).$
(6)

In the second case, we have $e_{k+1}\in N(e_{k})$, where $N(e_{k})$ is the set
of street segments to which $e_{k}$ connects. Following [18], we assume that
the difference between the orientation of the new street segment $e_{k+1}$ and
the vehicle’s predicted yaw $\alpha_{k+1}$ follows a zero-mean von Mises
distribution. That is, for each $e\in N(e_{k})$,

$P(e_{k+1}=e)\propto\mathcal{VM}(\phi_{e}|\alpha_{k+1},\kappa).$ (7)

After moving to $e_{k+1}$, the vehicle’s distance $d_{k+1}$ to the start node
of $e_{k+1}$ needs to have $l_{e_{k}}$ subtracted, and it is modeled as
$d_{k+1}=d_{k}+\epsilon_{k+1}-l_{e_{k}}+\sigma_{k+1}$ [17]. Then for
$d_{k}+\epsilon_{k+1}>l_{e_{k}}$, $e\in N(e_{k})$, we have

$g^{q}_{k+1}(q_{k+1}|p_{k+1},q_{k},\mathcal{G})\\\
=P(e_{k+1}=e)\mathcal{N}(d_{k+1};d_{k}+\epsilon_{k+1}-l_{e_{k}},\sigma_{k+1}).$
(8)

###  II-C Traffic Line State

A traffic line is modeled as a B-spline with uniform knots. A B-spline of
degree $d$ has minimum $d+1$ control points and continuous time derivatives up
to the $(d-1)$-th order. In this work, we consider 3D quadratic B-splines with
$d=2$, which we find sufficient for modeling lane geometry.

A B-spline trajectory can be parameterized by $C=(\varepsilon,c^{1:\nu})$,
where $\varepsilon$ is the initial time step of the trajectory $C$, $\nu\geq
3$ is its length, and $c^{1:\nu}=(c^{1},\dots,c^{\nu})$, with
$c^{i}\in\mathbb{R}^{3}$, denotes a finite sequence of control points. In the
sequence $c^{1:\nu}$, the first three control points $c^{1:3}$ correspond to
time instant $t^{c}_{\varepsilon}=t_{\varepsilon}$, and the rests $c^{4:\nu}$
are at time instants $t^{c}_{\varepsilon+3},\dots,t^{c}_{\varepsilon+\nu-1}$,
with uniform interval $\tau^{c}\geq\tau$. Note that different from the
trajectory representation in [6], here each trajectory has minimum length 3,
and the time interval $\tau^{c}$ for placing the control points can be larger
than the measurement sampling interval $\tau$ [8].

The trajectory in continuous time can be obtained by interpolating the control
points using the B-spline basis function. Specifically, given
$C=(\varepsilon,c^{1:\nu})$, the position of a point on the trajectory at an
arbitrary time instant
$\varsigma\in[t^{c}_{\varepsilon+i-1},t^{c}_{\varepsilon+i}),i\in\\{1,\dots,\nu-2\\}$,
is determined by the subsequence of control points $c^{i:i+2}$, according to

$\displaystyle c^{\varsigma}$
$\displaystyle=\begin{bmatrix}c^{i},c^{i+1},c^{i+2}\end{bmatrix}\cdot\Sigma\cdot\iota(\varsigma,t^{c}_{\varepsilon+i-1}),$
(9a) $\displaystyle\iota(\varsigma,t^{c}_{\varepsilon+i-1})$
$\displaystyle=\begin{bmatrix}1,\frac{\varsigma-t^{c}_{\varepsilon+i-1}}{\tau^{c}},\left(\frac{\varsigma-t^{c}_{\varepsilon+i-1}}{\tau^{c}}\right)^{2}\end{bmatrix}^{T},$
(9b) $\displaystyle\Sigma$ $\displaystyle=\frac{1}{2}\begin{bmatrix}1&-2&1\\\
1&2&-2\\\ 0&0&1\end{bmatrix}.$ (9c)

where $\Sigma$ is the basis function matrix for quadratic B-splines.

We consider B-spline trajectories up to the current time step $k$. Trajectory
$C=(\varepsilon,c^{1:\nu})$ is considered alive at time step $k$ if and only
if the latest measurement time instant $t_{k}$ satisfies that
$t_{k}\in[t^{c}_{\varepsilon+\nu-3},t^{c}_{\varepsilon+\nu-2})$, i.e.,
$\nu-\lfloor\frac{\tau(k-\varepsilon)}{\tau^{c}}\rfloor=3$. In the rest of the
paper, we use the notation
$\lfloor\frac{\tau(k-\varepsilon)}{\tau^{c}}\rfloor\triangleq\Xi^{\tau,\tau^{c}}_{k,\varepsilon}$
for brevity, where $\Xi^{\tau,\tau^{c}}_{k,\varepsilon}+3$ represents the
maximum length of trajectory $C=(\varepsilon,c^{1:\nu})$ at time step $k$.
Then, the space of a single trajectory up to time step $k$ can be defined as
$T_{(k)}=\uplus_{(\varepsilon,\nu)\in
I_{(k)}}\\{\varepsilon\\}\times\mathbb{R}^{3\nu}$, where
$I_{(k)}=\\{(\varepsilon,\nu):0\leq\varepsilon\leq k\text{ and }3\leq\nu\leq
3+\Xi^{\tau,\tau^{c}}_{k,\varepsilon}\\}$. The set of all trajectories that
have existed up to time step $k$ is denoted as $\mathbf{C}_{k}$. Definitions
of integrals and densities of single trajectories and sets of trajectories can
be found in [6].

####  II-C1 Multi-Lane Measurement Model

From (9), we can see that, for an alive trajectory $C=(\varepsilon,c^{1:\nu})$
at time step $k$, its interpolation at time step $k$ is determined by its
latest three control points $c^{\nu-2:\nu}$. This means that the detections of
$C$ at time step $k$ only depend on $c^{\nu-2:\nu}$ (and the vehicle state).

A single B-spline trajectory $C=(\varepsilon,c^{1:\nu})$ at time step $k$ is
detected with probability

$P_{k}^{D}(C,p_{k})=\begin{cases}P_{k}^{D}\left(c^{\nu-2:\nu},p_{k}\right),&\nu-\Xi^{\tau,\tau^{c}}_{k,\varepsilon}=3,\\\
0,&\text{otherwise},\end{cases}$ (10)

and generates an independent set $\mathbf{w}^{L,l}_{k}\in\mathbb{R}^{3}$ of
lane marking edge detection points in the vehicle coordinate, or is
misdetected with probability $1-P_{k}^{D}(C,p_{k})$. For a detection point
$w^{l}_{k}$, it can be transformed to the global coordinate
$w_{k}\in\mathbf{w}^{L}_{k}$ using the vehicle’s pose $p_{k}$, and the
dependence of $w_{k}$ on $p_{k}$ is made implicit in the following
expressions.

We assume that each individual lane marking edge detection point $w_{k}$
originates from a measurement source $\varpi_{k}$, corrupted by a zero-mean
Gaussian noise with covariance $\Omega_{k}^{w_{k}}$. Each measurement source
$\varpi_{k}$ is considered uniformly distributed along the two lane marking
edges. This modeling assumption allows us to rewrite the single measurement
likelihood as

$\ell_{k}\left(w_{k}|\varepsilon,c^{\nu-2:\nu}\right)=\int\mathcal{N}\left(w_{k};\varpi_{k},\Omega_{k}^{w_{k}}\right)\mathcal{U}\left(\varpi_{k}|\varepsilon,c^{\nu-2:\nu}\right)d\varpi_{k}.$
(11)

To enable the tractable computation of (11), we further approximate the
uniform distribution $\mathcal{U}(\varpi_{k}|\varepsilon,c^{\nu-2:\nu})$ as a
Gaussian
$\mathcal{N}(\varpi_{k};h(\varepsilon,c^{\nu-2:\nu}),\Omega_{k}^{\varpi})$,
which yields

$\ell_{k}\left(w_{k}|\varepsilon,c^{\nu-2:\nu}\right)=\mathcal{N}\left(w_{k};h\left(\varepsilon,c^{\nu-2:\nu}\right),\Omega_{k}^{w_{k}}+\Omega_{k}^{\varpi}\right).$
(12)

In Gaussian distribution
$\mathcal{N}(\varpi_{k};h(\varepsilon,c^{\nu-2:\nu}),\Omega_{k}^{\varpi})$,
the mean $h(\varepsilon,c^{\nu-2:\nu})$ is the interpolated point on
trajectory $C$ at time step $k$, and it can be computed using (9), which gives

$h(\varepsilon,c^{\nu-2:\nu})=\left(\Sigma\cdot\iota(t_{k},t^{c}_{\varepsilon+\nu-3})\right)^{T}\otimes
I_{3}c^{\nu-2:\nu},$ (13)

where $I_{3}$ is an identity matrix. The covariance matrix
$\Omega_{k}^{\varpi}$ can be factorized as [19]

$\Omega_{k}^{\varpi}=R_{k}^{\varpi}\text{diag}\left([l_{x},l_{y},0]/2\right)\cdot\Lambda\cdot\text{diag}\left([l_{x},l_{y},0]/2\right){R_{k}^{\varpi}}^{T},$
(14)

where $R_{k}^{\varpi}$ is a 3D rotation matrix that aligns the measurement
source $\varpi_{k}$ with the orientation of the lane marking, and $\Lambda$ is
a diagonal matrix, which can be set to $\Lambda=I_{3}/4$ to match the Gaussian
distribution to a uniform distribution [19]. The factorization (14) is
motivated by the fact that each observed lane marking within a certain
distance of the vehicle can be approximated as a very thin rectangle with
length $l_{x}$ and width $l_{y}$. The length $l_{x}$ setting should consider
the trade-off between detection range and approximation error due to road
curvature, whereas the width $l_{y}$ can be determined by lane marking type.

The rotation matrix $R_{k}^{\varpi}$ in (14) depends on the orientation of the
(observed) lane marking at time step $k$, which can be approximately obtained
by computing the tangent vector of the velocity of trajectory $C$ (the first
derivative of (9) with respect to time) at time step $k$. However, in this
case the measurement noise covariance $\Omega_{k}^{\varpi}$ would become
state-dependent, resulting in a (highly) nonlinear measurement model [20].

To compute $R_{k}^{\varpi}$ in a simple yet effective way, we assume that the
yaw of the B-spline trajectory evaluated at the interpolated point
$h(\varepsilon,c^{\nu-2:\nu})$ is given by the orientation $\phi_{e^{\prime}}$
of the street segment $e^{\prime}$ that $h(\varepsilon,c^{\nu-2:\nu})$ is on,
and that the pitch and roll of the B-spline trajectory evaluated at
$h(\varepsilon,c^{\nu-2:\nu})$ align with the vehicle’s. Under these
assumptions, we have that

$R_{k}^{\varpi}=R(\phi_{e^{\prime}},\beta_{k},\gamma_{k}),$ (15)

where $R(\cdot)$ is a 3D rotation matrix determined by yaw, pitch, and roll.
This assumption is reasonable for typical cases where the lane markings are in
parallel with the street segment and the street segments are flat within a
short range of distance. To find $e^{\prime}$, we first compute the distance
$\epsilon^{\prime}$ between the vehicle’s position and the interpolated point
$h(\varepsilon,c^{\nu-2:\nu})$ projected on the street segment $e_{k}$ that
the vehicle is currently moving on, similar to (5). If
$d_{k}+\epsilon^{\prime}\leq l_{e_{k}}$, we have $e^{\prime}=e_{k}$.
Otherwise, we find the street segment $e\in N(e_{k})$ that maximizes (7) and
check if $d_{k}+\epsilon^{\prime}-l_{e_{k}}\leq l_{e}$. This process is
repeated until we find $e^{\prime}$. In addition to the detection points
generated by lane markings, we assume that the lane marking detector can also
report clutter detection points. The set $\mathbf{w}_{k}^{C,l}$ of clutter
detection points is modeled as a Poisson point process (PPP) with Poisson
clutter rate $\lambda^{C}_{k}$. The set of all detection points at time step
$k$ is denoted as $\mathbf{w}^{l}_{k}$.

####  II-C2 Multi-Lane Dynamic Model

Given the set of all trajectories $\mathbf{C}_{k}$ at time step $k$, each
$C=(\varepsilon,c^{1:\nu})\in\mathbf{C}_{k}$ survives to time step $k+1$,
i.e., remains in the set $\mathbf{C}_{k+1}$, with probability one, and its
transition density is given by

$g_{k+1}\left(\varepsilon_{+},c_{+}^{1:\nu_{+}}|C\right)=\delta_{\varepsilon}[\varepsilon_{+}]\\\
\times\begin{cases}\delta_{\nu}[\nu_{+}]\delta_{c^{1:\nu}}\left(c_{+}^{1:\nu_{+}}\right),&\begin{aligned}
&\nu<3+\Xi^{\tau,\tau^{c}}_{k,\varepsilon}\text{or},\\\
&\nu=3+\Xi^{\tau,\tau^{c}}_{k,\varepsilon}\text{and}\\\
&t_{k+1}<t^{c}_{\varepsilon+\nu-2},\end{aligned}\\\ \begin{aligned}
&\delta_{\nu}[\nu_{+}]\delta_{c^{1:\nu}}\left(c_{+}^{1:\nu_{+}}\right)\\\
&\times\left(1-P^{S}_{1}(c^{\nu})\right),\end{aligned}&\begin{aligned}
&\nu=3+\Xi^{\tau,\tau^{c}}_{k,\varepsilon}\text{and}\\\ &t_{k+1}\geq
t^{c}_{\varepsilon+\nu-2}\text{ and}\\\ &t_{k+1}\geq
t^{c}_{\varepsilon_{+}+\nu_{+}-2},\end{aligned}\\\ \begin{aligned}
&\delta_{\nu+1}[\nu_{+}]\delta_{c^{1:\nu}}\left(c_{+}^{1:\nu_{+}-1}\right)\\\
&\times
P^{S}_{1}(c^{\nu})g\left(c_{+}^{\nu_{+}}|c^{\nu-1:\nu}\right),\end{aligned}&\begin{aligned}
&\nu=3+\Xi^{\tau,\tau^{c}}_{k,\varepsilon}\text{and}\\\ &t_{k+1}\geq
t^{c}_{\varepsilon+\nu-2}\text{ and}\\\
&t_{k+1}<t^{c}_{\varepsilon_{+}+\nu_{+}-2}.\end{aligned}\end{cases}$ (16)

From (16), we can see that if trajectory $C$ is not alive at time step $k$, or
if it is alive at time step $k$ but the time instant $t_{k+1}$ is smaller than
$t^{c}_{\varepsilon+\nu-2}$, then trajectory $C$ remains unaltered with
probability one. If trajectory $C$ is alive at time step $k$ and the time
instant $t_{k+1}$ is no smaller than $t^{c}_{\varepsilon+\nu-2}$, then with
probability $1-P^{S}_{1}(c^{\nu})$, trajectory $C$ remains unaltered, and with
probability $P^{S}_{1}(c^{\nu})$, it is extended by appending one control
point with a transition density $g(c_{+}^{\nu_{+}}|c^{\nu-1:\nu})$.

The state of the new control point $c^{\nu_{+}}$ in
$g(c_{+}^{\nu_{+}}|c^{\nu-1:\nu})$ is determined by the state of the latest
two control points $c^{\nu-1:\nu}$ by preserving the velocity at time instant
$t^{c}_{\varepsilon+\nu-2}$, which gives $c_{+}^{\nu_{+}}=2c^{\nu}-c^{\nu-1}$.
Assuming that the motion process noise is zero-mean Gaussian, the transition
density is

$g\left(c_{+}^{\nu_{+}}|c^{\nu-1:\nu}\right)=\mathcal{N}\left(c_{+}^{\nu_{+}};\begin{bmatrix}-I_{3}&2I_{3}\end{bmatrix}c^{\nu-1:\nu},Q_{k+1}^{c}\right),$
(17)

where $Q^{c}_{k+1}$ is the motion noise covariance.

The set of trajectories $\mathbf{C}_{k+1}$ at time step $k+1$ is the union of
surviving trajectories, newborn trajectories, and trajectories spawned from
existing trajectories. The set of newborn trajectories appears independently
with a PPP with intensity

$\lambda^{B}_{k+1}(\varepsilon,c^{1:\nu}|p_{k+1})=\delta_{k+1}[\varepsilon]\delta_{3}[\nu]\lambda^{B}_{k+1}(c^{1:3}|p_{k+1}),$
(18)

where the Poisson intensity $\lambda^{B}_{k+1}(c^{1:3}|p_{k+1})$ depends on
the camera’s field-of-view. To model lane splitting, we assume that each
trajectory $C=(\varepsilon,c^{1:\nu})\in\mathbf{C}_{k}$ alive at time step $k$
may spawn a new trajectory with probability $P^{S}_{2}(c^{\nu})$. The set of
trajectories spawned from trajectory $C$, where
$\nu-\Xi^{\tau,\tau^{c}}_{k,\varepsilon}=3$, at time step $k+1$ is then a
Bernoulli process with density

$\displaystyle g_{k+1}^{S}\left(\mathbf{C}_{+}|C\right)$
$\displaystyle=\begin{cases}P^{S}_{2}(c^{\nu})\delta_{k+1}[\varepsilon_{+}]\delta_{3}[\nu_{+}]&\\\
~{}~{}\times\delta_{c^{\nu-1:\nu}}\left(c_{+}^{1:\nu_{+}-1}\right)&\\\
~{}~{}\times
g\left(c_{+}^{\nu_{+}}|c^{\nu-1:\nu}\right),&\mathbf{C}_{+}=\left\\{\left(\varepsilon_{+},c_{+}^{1:\nu_{+}}\right)\right\\},\\\
1-P^{S}_{2}(c^{\nu}),&\mathbf{C}_{+}=\emptyset,\\\
0,&\text{otherwise}.\end{cases}$ (19)

##  III Problem Formulation

With the system model introduced in Section II in place, we can now formulate
the problem of simultaneous localization and multi-lane tracking. The
objective is to recursively compute the joint posterior distribution of the
vehicle trajectory $o_{0:k}$ and the set $\mathbf{C}_{k}$ of all B-spline
trajectories given the SD map $\mathcal{G}$ and the measurements
$\mathbf{w}^{l}_{1:k}$ and visual odometry $u^{l}_{1:k}$ up to and including
time step $k$. The joint posterior distribution can be factorized as the
product of the posterior distribution
$f(o_{0:k}|\zeta_{1:k},u^{l}_{1:k},\mathcal{G})$ of the vehicle trajectory and
the posterior distribution
$f(\mathbf{C}_{k}|o_{0:k},\mathbf{w}^{l}_{1:k},\mathcal{G})$ of the set of all
trajectories conditioned on the vehicle trajectory, i.e.,

$\displaystyle
f\left(o_{0:k},\mathbf{C}_{k}|\zeta_{1:k},u^{l}_{1:k},\mathbf{w}^{l}_{1:k},\mathcal{G}\right)$
$\displaystyle=f\left(o_{0:k}|\zeta_{1:k},u^{l}_{1:k},\mathbf{w}^{l}_{1:k},\mathcal{G}\right)f\left(\mathbf{C}_{k}|o_{0:k},\mathbf{w}^{l}_{1:k},\mathcal{G}\right).$
(20)

The computation of each posterior density involves a prediction step and an
update step. For the vehicle motion model in Section II-B2, the predicted
density of vehicle trajectory at time step $k$ is

$\displaystyle
f\left(o_{0:k}|\zeta_{1:k-1},u^{l}_{1:k},\mathbf{w}^{l}_{1:k-1},\mathcal{G}\right)=g_{k}\left(o_{k}|o_{k-1},u^{l}_{k},\mathcal{G}\right)$
$\displaystyle\times
f\left(o_{0:k-1}|\zeta_{1:k-1},u^{l}_{1:k-1},\mathbf{w}^{l}_{1:k-1},\mathcal{G}\right).$
(21)

The predicted density of the set of all B-spline trajectories at time step $k$
is

$\displaystyle
f\left(\mathbf{C}_{k}|o_{0:k},\mathbf{w}^{l}_{1:k-1},\mathcal{G}\right)=$
$\displaystyle\int
g_{k}\left(\mathbf{C}_{k}|\mathbf{C}_{k-1}\right)f\left(\mathbf{C}_{k-1}|o_{0:k},\mathbf{w}^{l}_{1:k-1},\mathcal{G}\right)\delta\mathbf{C}_{k-1},$
(22)

where $g_{k}(\mathbf{C}_{k}|\mathbf{C}_{k-1})$ is the transition density of
the set of all trajectories for the multi-lane dynamic model in Section II-C2,
and the set integral $\int f(\mathbf{X})\delta\mathbf{X}$ is defined in [6].

The predicted density of the set of all B-spline trajectories at time step $k$
is then updated using the multi-lane measurement model
$\ell_{k}(\mathbf{w}_{k}^{l}|\mathbf{C}_{k},o_{k},\mathcal{G})$ in Section
II-C1, which gives

$\displaystyle
f\left(\mathbf{C}_{k}|o_{0:k},\mathbf{w}^{l}_{1:k},\mathcal{G}\right)$
$\displaystyle=\frac{f\left(\mathbf{C}_{k}|o_{0:k},\mathbf{w}^{l}_{1:k-1},\mathcal{G}\right)\ell_{k}\left(\mathbf{w}_{k}^{l}|\mathbf{C}_{k},o_{k},\mathcal{G}\right)}{\ell_{k}\left(\mathbf{w}_{k}^{l}|o_{0:k},\mathbf{w}_{1:k-1}^{l},\mathcal{G}\right)},$
(23)

where
$\ell_{k}(\mathbf{w}_{k}^{l}|o_{0:k},\mathbf{w}_{1:k-1}^{l},\mathcal{G})$ is a
normalizing factor. Lastly, the predicted density of the vehicle trajectory at
time step $k$ is updated using the measurement model in Section II-B1, which
gives

$\displaystyle
f\left(o_{0:k}|\zeta_{1:k},u^{l}_{1:k},\mathbf{w}^{l}_{1:k},\mathcal{G}\right)=f\left(o_{0:k}|\zeta_{1:k-1},u^{l}_{1:k},\mathbf{w}^{l}_{1:k-1},\mathcal{G}\right)$
$\displaystyle~{}~{}~{}\times\ell_{k}\left(\zeta_{k},\mathcal{G}|o_{k}\right)\ell_{k}\left(\mathbf{w}_{k}^{l}|o_{0:k},\mathbf{w}_{1:k-1}^{l},\mathcal{G}\right)$
$\displaystyle~{}~{}~{}~{}/\ell_{k}\left(\zeta_{k},\mathbf{w}^{l}_{k},\mathcal{G}|\zeta_{1:k-1},\mathbf{w}^{l}_{1:k-1}\right),$
(24)

where
$\ell_{k}(\zeta_{k},\mathbf{w}^{l}_{k},\mathcal{G}|\zeta_{1:k-1},\mathbf{w}^{l}_{1:k-1})$
is a normalizing factor.

In the next section, we will describe how to perform these prediction and
update steps in a computationally tractable way. For notational simplicity, we
will drop the explicit dependence in the predicted and posterior densities and
use the shorthand notations, with $k^{\prime}\in\\{k-1,k\\}$,

$\displaystyle
f\left(o_{0:k}|\zeta_{1:k^{\prime}},u^{l}_{1:k},\mathbf{w}^{l}_{1:k^{\prime}},\mathcal{G}\right)$
$\displaystyle=f_{k|k^{\prime}}\left(o_{0:k}\right),$ (25a) $\displaystyle
f\left(\mathbf{C}_{k}|o_{0:k},\mathbf{w}^{l}_{1:k^{\prime}},\mathcal{G}\right)$
$\displaystyle=f_{k|k^{\prime}}\left(\mathbf{C}_{k}|o_{0:k}\right).$ (25b)

##  IV TPMBM-based Simultaneous Localization and Multi-Lane Tracking

The main challenge in computing (III) lies in the multi-lane update step
(III), which involves the dependence on the vehicle trajectory $o_{0:k}$, and
the normalizing factor in (III) needs to be explicitly computed for updating
the vehicle trajectory in (III). To address this challenge, we adopt a
particle representation of the vehicle trajectory [21, 22]:

$f_{k|k^{\prime}}\left(o_{0:k}\right)=\sum_{n=1}^{N_{p}}\omega_{k|k^{\prime}}^{n}\delta_{o_{0:k}^{n}}\left(o_{0:k}\right),$
(26)

where $N_{p}$ is the number of particles and $\omega_{k|k^{\prime}}^{n}$ is
the weight of particle $o_{0:k}^{n}$, with $\omega_{k|k^{\prime}}^{n}\geq 0$
and $\sum_{n=1}^{N_{p}}\omega_{k|k^{\prime}}^{n}=1$.

With this particle representation, the multi-lane prediction (III) and update
step (III) boil down to computing the predicted and posterior density of the
set $\mathbf{C}_{k}$ of all trajectories for each particle $o_{0:k}^{n}$. In
particular, given the multi-lane measurement and dynamic models in Section
II-C1 and II-C2, the density $f_{k|k^{\prime}}(\mathbf{C}_{k}|o^{n}_{0:k})$ is
of the form TPMBM with [4],

$\displaystyle f_{k|k^{\prime}}(\mathbf{C}_{k}|o^{n}_{0:k})$
$\displaystyle=\sum_{\mathbf{X}\uplus\mathbf{Y}=\mathbf{C}_{k}}f^{p}_{k|k^{\prime}}(\mathbf{X}|o^{n}_{0:k})f^{mbm}_{k|k^{\prime}}(\mathbf{Y}|o^{n}_{0:k}),$
(27) $\displaystyle f^{p}_{k|k^{\prime}}(\mathbf{C}_{k}|o^{n}_{0:k})$
$\displaystyle=e^{-\int\lambda_{k|k^{\prime}}(C|o^{n}_{0:k})dC}\prod_{C\in\mathbf{C}_{k}}\lambda_{k|k^{\prime}}(C|o^{n}_{0:k}),$
(28) $\displaystyle f^{mbm}_{k|k^{\prime}}(\mathbf{C}_{k}|o^{n}_{0:k})$
$\displaystyle=\sum_{a\in\mathcal{A}^{n}_{k|k^{\prime}}}\omega^{a}_{k|k^{\prime}}\sum_{\uplus_{l=1}^{I^{n}_{k|k^{\prime}}}\mathbf{C}^{l}=\mathbf{C}_{k}}\prod_{i=1}^{I^{n}_{k|k^{\prime}}}f^{i,a^{i}}_{k|k^{\prime}}\left(\mathbf{C}^{i}|o^{n}_{0:k}\right).$
(29)

The TPMBM in (27) is the union of two independent sets: a trajectory PPP with
density (28) that represents undetected trajectories that are hypothesized to
exist but have never been detected, and a trajectory multi-Bernoulli mixture
with density (29) that represents trajectories that have been detected at some
point up to time step $k$. The intensity of the trajectory PPP is
$\lambda_{k|k^{\prime}}(\cdot)$. Each received measurement generates a
Bernoulli component, and the number of Bernoulli components is
$I^{n}_{k|k^{\prime}}$. A global hypothesis is
$a=(a^{1},\dots,a^{I^{n}_{k|k^{\prime}}})\in\mathcal{A}^{n}_{k|k^{\prime}}$,
where $a^{i}\in\\{1,\dots,h^{i}_{k|k^{\prime}}\\}$ is the index to the local
hypothesis for the $i$-th Bernoulli and $h^{i}_{k|k^{\prime}}$ is its number
of local hypotheses.

We refer to the $j$-th measurement $w_{k}^{l,j}$ using the pair $(k,j)$, and
the set of all such measurement pairs up to (and including) time step $k$ is
denoted by $\mathcal{M}_{k}$. Then, a local hypothesis $a^{i}$ for the $i$-th
Bernoulli component has a set of measurement pairs denoted as
$\mathcal{M}_{k}^{i,a^{i}}\subseteq\mathcal{M}_{k}$. The set
$\mathcal{A}^{n}_{k|k^{\prime}}$ of global hypotheses satisfies [4],

$\mathcal{A}^{n}_{k|k^{\prime}}=\left\\{\left(a^{1},\dots,a^{I^{n}_{k|k^{\prime}}}\right):a^{i}\in\left\\{1,\dots,h^{i}_{k|k^{\prime}}\right\\}\forall
i,\right.\\\
\left.\uplus_{i=1}^{I^{n}_{k|k^{\prime}}}\mathcal{M}_{k^{\prime}}^{i,a^{i}}=\mathcal{M}_{k^{\prime}}\right\\}.$
(30)

Global hypothesis $a$ has weight
$\omega^{a}_{k|k^{\prime}}\propto\prod_{i=1}^{I^{n}_{k|k^{\prime}}}\omega^{i,a^{i}}_{k|k^{\prime}}$,
where $\omega_{k|k^{\prime}}^{i,a^{i}}$ is the weight of local hypothesis
$a^{i}$ for the $i$-th Bernoulli component, and it should satisfy that
$\sum_{a\in\mathcal{A}^{n}_{k|k^{\prime}}}\omega_{k|k^{\prime}}^{a}=1$. The
density of the $i$-th Bernoulli component with local hypothesis $a^{i}$ is
$f^{i,a^{i}}_{k|k^{\prime}}(\cdot|o_{0:k}^{n})$, parameterized by a
probability of existence $r^{i,a^{i}}_{k|k^{\prime}}$ and a single trajectory
density $p^{i,a^{i}}_{k|k^{\prime}}(\cdot|o_{0:k}^{n})$.

We proceed to describe the prediction (III), (III) and update (III), (III)
steps with the particle representation of the vehicle trajectory (26) and the
TPMBM density representation of the set of all trajectories conditioned on
each particle (27). Due to page limits, we refer the readers to [4, 7] for the
explicit expressions of the TPMBM prediction and update equations.

###  IV-A Vehicle State Prediction

Given a trajectory particle $o_{0:k-1}^{n}$, we first draw a sample of the
vehicle pose at time step $k$ via $p^{n}_{k}\sim
g_{k}(p_{k}|p^{n}_{k-1},u^{l}_{k})$, and then we draw a sample of the
vehicle’s position within the SD map at time step $k$ via $q_{k}^{n}\sim
g_{k}(q_{k}|p^{n}_{k},q^{n}_{k-1},\mathcal{G})$. Lastly, the sampled vehicle
state $o^{n}_{k}$ is appended to $o_{0:k-1}^{n}$ to obtain the updated
particle $o_{0:k}^{n}$. Since we directly draw samples from the vehicle motion
transition density, the particle weights remain unchanged.

###  IV-B Multi-Lane Prediction

Given a TPMBM posterior density at time step $k-1$ and the multi-lane dynamic
model in Section II-C2 without spawning, the predicted density would also be a
TPMBM [4]. However, due to the dependencies between each alive and its spawned
trajectory, the predicted density is no longer a TPMBM in its closed
form333For the standard dynamic and measurement models with multi-Bernoulli
spawning, the posterior is a TPMBM density on the set of tree trajectories
without approximations [7]. This modeling is not used in this work.. As in
[7], we approximate the predicted density as a TPMBM by discarding these
dependencies. In addition, we assume that the PPP represents alive
trajectories without spawning, and that each trajectory Bernoulli component
has a deterministic start time. These approximations would considerably
simplify the implementation of the multi-lane prediction step. Note that the
TPMBM filter in [7] considers the sets of tree trajectories, which contain the
genealogy information of each trajectory. However, in multi-lane tracking the
genealogy information is not needed, and we only consider the traditional sets
of trajectories formulation for notational simplicity [6].

The prediction of PPP and existing Bernoulli components are the same as their
predictions in the TPMBM filter without spawning [4, Prop. 1]. For a spawned
Bernoulli component, its probability of existence is jointly determined by the
spawning probability $P^{S}_{2}(\cdot)$, the probability of existence and the
probability of being alive at time step $k$ of its parent trajectory. After
the prediction step, the number of Bernoulli components (27) becomes
$I^{n}_{k|k-1}=2I^{n}_{k-1|k-1}$.

###  IV-C Multi-Lane Update

Given a TPMBM predicted density at time step $k$ and the multi-lane
measurement model in Section II-C1, the posterior density at time step $k$ is
also a TPMBM (27) [4, Prop. 2]. The complete TPMBM update consists of five
steps:

  1. 1.

The update of the PPP for undetected trajectories that remain undetected.

  2. 2.

The update of the PPP for undetected trajectories that are detected for the
first time. In this step, each received measurement generates a unique
Bernoulli component, such that
$I^{n}_{k|k}=I^{n}_{k|k-1}+|\mathbf{w}_{k}^{l}|$.

  3. 3.

The update of local hypotheses corresponding to misdetection of existing
Bernoulli components.

  4. 4.

The update of local hypotheses corresponding to measurement update of existing
Bernoulli components.

  5. 5.

The update of global hypotheses.

The main challenge lies in the update of global hypotheses. Each global
hypothesis corresponds to a unique partition of $\mathcal{M}_{k}$, and the
number of global hypotheses is given by the Bell number of $|\mathcal{M}_{k}|$
[23]. Thus, it is computationally intractable to enumerate all the global
hypotheses. To address this challenge, we can only consider global hypotheses
with high likelihoods, using approaches that combine clustering and 2D
assignments [23] or sampling-based methods [24].

###  IV-D Vehicle State Update

Computing the particle weight $\omega^{n}_{k|k}$ requires the computation of
$\ell_{k}(\mathbf{w}_{k}^{l}|o^{n}_{0:k},\mathbf{w}_{1:k-1}^{l},\mathcal{G})$,
which is the normalizing factor in computing the TPMBM posterior density (III)
at time step $k$. It can be observed that this normalizing factor is the same
as the normalizing factor in computing the normalized global hypothesis weight
[21], i.e.,

$\ell_{k}(\mathbf{w}_{k}^{l}|o^{n}_{0:k},\mathbf{w}_{1:k-1}^{l},\mathcal{G})=\sum_{a\in\mathcal{A}^{n}_{k|k}}\prod_{i=1}^{I^{n}_{k|k}}\omega^{i,a^{i}}_{k|k}.$
(31)

The updated particle weight is then given by

$\omega^{n}_{k|k}\propto\omega^{n}_{k|k-1}\ell_{k}\left(\zeta_{k}|o_{k}\right)\ell_{k}\left(\mathcal{G}|o_{k}\right)\sum_{a\in\mathcal{A}^{n}_{k|k}}\prod_{i=1}^{I^{n}_{k|k}}\omega^{i,a^{i}}_{k|k}.$
(32)

To avoid particle degeneracy, we resample the particles if the number of
effective particles is below $N_{p}/4$.

##  V Experimental Results

In this section, we present the experimental results of our proposed solution
for simultaneous localization and multi-lane tracking using onboard sensors
and a SD map on real-world data. The data was collected by a test vehicle
during a single traversal on a highway in Gothenburg, Sweden.

The vision data was obtained using a forward-facing, mono camera, operating at
15 Hz. Both the visual odometry and the lane marking edge detections were
extracted from the camera images using Zenseact’s in-house developed computer
vision algorithms. The GNSS measurements were obtained using a single-antenna
GPS receiver, operating at 1 Hz; the SD map is from the open-source
OpenStreetMap.

To evaluate the localization performance of our proposed solution, the vehicle
pose estimates reported by a high-precision localization system from Oxford
Technical Solutions (OxTS) are used as ground truth. Due to the lack of the
ground truth HD map, we evaluate the multi-lane estimation performance by
overlaying the estimated traffic lines on the Google Earth satellite image.

The parameter setting used in the SLAMOT filter is specified as follows. In
the vehicle measurement model, the GNSS measurement noise covariance
$\Omega_{k}$ is a diagonal matrix. The standard deviation of the latitudinal
and longitudinal errors are provided by the GNSS, and we set the standard
deviation of the altitude error to 3 m. The concentration parameter $\kappa$
in the von Mises distribution is set to 8. In the vehicle motion model, the
motion noise covariance $Q_{k}$ is a diagonal matrix with the standard
deviation of the position error set to 0.05 m and orientation error set to
$0.1^{\circ}$. The standard deviation $\sigma_{k}$ of motion noise of $d_{k}$
is set to $0.2\epsilon_{k}$, where $\epsilon_{k}$ is defined in (5). For
B-spline trajectory state modeling, the time interval for placing the control
points is $\tau^{c}=5\tau=1/3\,\text{s}$.

We consider lane marking detection points that are within 16 m distance of the
vehicle and set $l_{x}=3\,\text{m}$ and $l_{y}=0.05\,\text{m}$ in the
covariance matrix (14) that represents the lane extent. In addition to the 3D
positional information, each lane marking edge detection point also contains
the instance segmentation information provided by the lane marking edge
detector. In this work, we have utilized the lane marking type information,
such as solid or dashed, and the clustering information, i.e., to which lane
marking cluster it belongs. Each traffic line is detected with probability
$P^{D}_{k}=0.95$ except for the following special case. If a traffic line was
associated to a dashed lane marking detection point at time step $k-1$ and is
not detected at time step $k$, then its detection probability will be lowered
to $P^{D}_{k}=0.5$ until it is detected again. This setting helps to connect
multiple dashed lane markings into a single traffic line. In addition, by
using the clustering information, the extended object data association problem
reduces to the point object data association problem. Each individual
detection point $w_{k}$ also has its own $\Omega_{k}^{w_{k}}$ provided by the
lane marking detector. The clutter detections have uniform Poisson intensity
$10^{-3}$.

In the multi-lane dynamic model, the survival probability is $P^{S}_{1}=0.99$
and the spawning probability is $P^{S}_{2}=10^{-5}$. The motion noise
covariance in the state transition density (17) is
$Q^{c}_{k}=0.36\tau^{c}I_{3}$. The Poisson birth intensity (18) is a single
Gaussian defined in the vehicle coordinate, with weight $10^{-5}$, mean
$[6,0,-0.5,11,0,-0.5,16,0,-0.5]^{T}$, and covariance
$\text{diag}(100,400,4,100,400,4,100,400,4)$. The weight at time step $0$ is
set to $10^{-3}$.

The TPMBM update uses Murty’s algorithm [25] to find the $M=\lceil
500\omega^{a}_{k|k}\rceil$-best global hypotheses for global hypothesis $a$
with weight $\omega^{a}_{k|k}$. The maximum number of global hypothesis is
$500$, and we prune global hypotheses with weight smaller than $10^{-3}$. We
also prune Bernoulli components with existence probability smaller than
$10^{-5}$ and Gaussian components in the Poisson intensity with weight smaller
than $10^{-5}$. In addition, we consider $L$-scan implementation with $L=3$
[26], where control points before the last three time instants are considered
independent and remain unchanged with new measurements. Furthermore, Bernoulli
components with probability of being alive at the current time step smaller
than $10^{-5}$ are considered dead, and they are no longer predicted or
updated.

To report the traffic line estimates, we first find the TPMBM posterior
density conditioned on the particle with the highest weight, and then we find
the multi-Bernoulli component with the highest weight and its Bernoulli
components with existence probability one. For each Bernoulli component, we
extract the sequence of B-spline control points with the most likely length.
Finally, we interpolate the control points to obtain continuous traffic line
estimates. The vehicle pose estimate at each time step is obtained by taking
the sample mean instead of choosing the particle with the highest weight at
the last time step due to particle history degeneracy.

In the experiment, we use $N_{p}=1000$ particles, initialized only using
information provided by the GNSS measurement. The multi-lane estimation
performance is evaluated by overlaying the estimated traffic lines on the
Google Earth satellite image; screenshots are provided in Fig. 1. It can be
observed from the results that the estimated traffic lines are continuous and
smooth, and that they align well with the lane markings in the satellite image
up to a lateral offset. This offset mainly depends on the lateral localization
accuracy of the vehicle as in most cases, the offset between the estimated
traffic lines and the lane markings matches the offset between the OxTS and
the estimated vehicle trajectories. Lane splittings are also well estimated,
with the only exception being at the bottom-left of Fig. 1, where a newborn
traffic line is estimated to be spawned from an existing one.

The root-mean-square localization error in the $x$, $y$, and $z$ directions
are 0.97 m, 1.10 m, and 2.06 m, respectively. The improvement with respect to
using only visual odometry and GNSS is about 11%. Since lane marking
detections can only provide accurate relative lateral information and GNSS
measurement is of low accuracy, it is difficult to accurately localize the
vehicle and track the lanes without using detections that have good
longitudinal information, such as traffic signs/lights. Nevertheless, our
proposed solution can provide a reasonable estimate of traffic lines with
respect to the vehicle trajectory.

Figure 1: OxTS vehicle trajectory (blue), estimated vehicle trajectory (red),
estimated traffic lines (green) overlaid with Google Earth satellite image.
The top figure illustrates the best traffic line estimation performance,
followed by the bottom figure and the mid-figure.

##  VI Conclusion and Future Work

In this paper, we have proposed an effective solution for simultaneous
localization and multi-lane tracking using onboard sensors and a SD map. The
proposed solution is based on a TPMBM-based SLAMOT filter, where the
estimation of traffic lines, in the form of B-spline trajectories, using lane
marking detection points is formulated as a multiple extended object tracking
problem. The efficacy of the proposed solution has been demonstrated on real-
world data.

In the future, we plan to work on the batch formulation of the SLAMOT problem
such that smoothed vehicle trajectory and traffic line estimates could be
obtained by exploiting full information of the data. The mapping of static
landmarks, such as traffic signs and traffic lights, can also be incorporated
into the solution to further improve the localization accuracy, and hence also
the multi-lane estimation performance.

## References

  * [1] G. Elghazaly, R. Frank, S. Harvey, and S. Safko, “High-definition maps: Comprehensive survey, challenges and future perspectives,” _IEEE Open Journal of Intelligent Transportation Systems_ , 2023.
  * [2] J. Zhou, Y. Guo, Y. Bian, Y. Huang, and B. Li, “Lane information extraction for high definition maps using crowdsourced data,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 24, no. 7, pp. 7780–7790, 2023.
  * [3] Y. Xia, K. Granström, L. Svensson, Á. F. García-Fernández, and J. L. Williams, “Extended target Poisson multi-Bernoulli mixture trackers based on sets of trajectories,” in _22th International Conference on Information Fusion_. IEEE, 2019, pp. 1–8.
  * [4] Y. Xia, Á. F. García-Fernández, F. Meyer, J. L. Williams, K. Granström, and L. Svensson, “Trajectory PMB filters for extended object tracking using belief propagation,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 59, no. 6, pp. 9312–9331, 2023.
  * [5] K. Berntorp, M. Greiff, S. Di Cairano, and P. Miraldo, “Bayesian sensor fusion for joint vehicle localization and road mapping using onboard sensors,” in _26th International Conference on Information Fusion (FUSION)_. IEEE, 2023, pp. 1–8.
  * [6] Á. F. García-Fernández, L. Svensson, and M. R. Morelande, “Multiple target tracking based on sets of trajectories,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 56, no. 3, pp. 1685–1707, 2019.
  * [7] Á. F. García-Fernández and L. Svensson, “Tracking multiple spawning targets using Poisson multi-Bernoulli mixtures on sets of tree trajectories,” _IEEE Transactions on Signal Processing_ , vol. 70, pp. 1987–1999, 2022.
  * [8] K. Li, “On embedding B-splines in recursive state estimation,” _arXiv preprint arXiv:2307.00637_ , 2023.
  * [9] A. Abramov, C. Bayer, C. Heller, and C. Loy, “Multi-lane perception using feature fusion based on GraphSLAM,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2016, pp. 3108–3115.
  * [10] C. Kim, S. Cho, M. Sunwoo, and K. Jo, “Crowd-sourced mapping of new feature layer for high-definition map,” _Sensors_ , vol. 18, no. 12, p. 4172, 2018.
  * [11] M. Liebner, D. Jain, J. Schauseil, D. Pannen, and A. Hackelöer, “Crowdsourced HD map patches based on road model inference and graph-based SLAM,” in _IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2019, pp. 1211–1218.
  * [12] P. Cudrano, B. Gallazzi, M. Frosi, S. Mentasti, and M. Matteucci, “Clothoid-based lane-level high-definition maps: Unifying sensing and control models,” _IEEE Vehicular Technology Magazine_ , vol. 17, no. 4, pp. 47–56, 2022.
  * [13] C. Lundquist, U. Orguner, and F. Gustafsson, “Extended target tracking using polynomials with applications to road-map estimation,” _IEEE Transactions on Signal Processing_ , vol. 59, no. 1, pp. 15–26, 2010.
  * [14] B. Akbari and H. Zhu, “Tracking dependent extended targets using multi-output spatiotemporal Gaussian processes,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 10, pp. 18 301–18 314, 2022.
  * [15] K. Zhao, M. Meuter, C. Nunn, D. Müller, S. Müller-Schneiders, and J. Pauli, “A novel multi-lane detection and tracking system,” in _IEEE Intelligent Vehicles Symposium_. IEEE, 2012, pp. 1084–1089.
  * [16] Z. Qiao, Z. Yu, H. Yin, and S. Shen, “Online monocular lane mapping using Catmull-Rom spline,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2023, pp. 7179–7186.
  * [17] M. A. Brubaker, A. Geiger, and R. Urtasun, “Map-based probabilistic visual self-localization,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 38, no. 4, pp. 652–665, 2015.
  * [18] P. Merriaux, Y. Dupuis, P. Vasseur, and X. Savatier, “Fast and robust vehicle positioning on graph-based representation of drivable maps,” in _IEEE International Conference on Robotics and Automation_. IEEE, 2015, pp. 2787–2793.
  * [19] S. Yang and M. Baum, “Tracking the orientation and axes lengths of an elliptical extended object,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 18, pp. 4720–4729, 2019.
  * [20] D. Spinello and D. J. Stilwell, “Nonlinear estimation with state-dependent Gaussian observation noise,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 6, pp. 1358–1366, 2010.
  * [21] H. Kim, K. Granström, L. Svensson, S. Kim, and H. Wymeersch, “PMBM-based SLAM filters in 5G mmwave vehicular networks,” _IEEE Transactions on Vehicular Technology_ , vol. 71, no. 8, pp. 8646–8661, 2022.
  * [22] M. Montemerlo, S. Thrun, D. Koller, B. Wegbreit _et al._ , “FastSLAM: A factored solution to the simultaneous localization and mapping problem,” _Aaai/iaai_ , vol. 593598, 2002.
  * [23] K. Granström, M. Fatemi, and L. Svensson, “Poisson multi-Bernoulli mixture conjugate prior for multiple extended target filtering,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 56, no. 1, pp. 208–225, 2020.
  * [24] K. Granström, L. Svensson, S. Reuter, Y. Xia, and M. Fatemi, “Likelihood-based data association for extended object tracking using sampling methods,” _IEEE Transactions on Intelligent Vehicles_ , vol. 3, no. 1, pp. 30–45, 2018.
  * [25] D. F. Crouse, “On implementing 2D rectangular assignment algorithms,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 52, no. 4, pp. 1679–1696, 2016.
  * [26] Á. F. García-Fernández and L. Svensson, “Trajectory PHD and CPHD filters,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 22, pp. 5702–5714, 2019.