# MotionSC: Data Set and Network for Real-Time Semantic Mapping in Dynamic
Environments

Joey Wilson1, Jingyu Song1, Yuewei Fu1, Arthur Zhang1
Andrew Capodieci2, Paramsothy Jayakumar3, Kira Barton1, and Maani Ghaffari1
Manuscript received: February 23, 2022; Revised May 20, 2022; Accepted June
20, 2022.This paper was recommended for publication by Editor Cesar Cadena
Lerma upon evaluation of the Associate Editor and Reviewers’ comments. Funding
for M. Ghaffari was in part provided by NSF Award No. 2118818.DISTRIBUTION A.
Approved for public release; distribution unlimited. OPSEC #61521J. Wilson, J.
Song, Y. Fu, A. Zhang, K. Barton, and M. Ghaffari are with the University of
Michigan, Ann Arbor, MI 48109, USA.
{wilsoniv,jingyuso,ywfu,arthurzh,bartonkl,maanigj}
@umich.edu2A. Capodieci is with Neya Systems Division, Applied Research
Associates, Warrendale, PA 15086, USA<EMAIL_ADDRESS>Jayakumar is with the US Army DEVCOM Ground Vehicle Systems Center, Warren, MI
48397, USA<EMAIL_ADDRESS>Object Identifier (DOI):
see top of this page.

###### Abstract

This work addresses a gap in semantic scene completion (SSC) data by creating
a novel outdoor data set with accurate and complete dynamic scenes. Our data
set is formed from randomly sampled views of the world at each time step,
which supervises generalizability to complete scenes without occlusions or
traces. We create SSC baselines from state-of-the-art open source networks and
construct a benchmark real-time dense local semantic mapping algorithm,
MotionSC, by leveraging recent 3D deep learning architectures to enhance SSC
with temporal information. Our network shows that the proposed data set can
quantify and supervise accurate scene completion in the presence of dynamic
objects, which can lead to the development of improved dynamic mapping
algorithms. All software is available at https://github.com/UMich-
CURLY/3DMapping.

###### Index Terms:

Data Sets for Robotic Vision, Deep Learning for Visual Perception, Mapping,
Semantic Scene Understanding.

##  I Introduction

Scene understanding in 3D is a keystone for mobile robotics. Scene
understanding enables a robot to reason the environment and improve decision-
making, internal navigation, path planning, and control execution. While 2D
scene understanding is useful for robots, a 3D understanding ultimately
provides an opportunity for more information, e.g., navigating under obstacles
or understanding their size. Therefore, 3D scene understanding is necessary
for autonomous vehicles [1], as the 2D information cannot support certain
robotic applications due to the lack of depth information.

Scene understanding is generally broken into sub-tasks due to its broad scope,
including object detection, scene categorization, semantic segmentation, depth
estimation, tracking, and prediction [2]. These tasks are easier to conquer on
their own, and have seen significant progress in recent years due to the
development of 3D deep learning networks and rapid improvement of 3D sensors.
The main challenges still facing 3D deep learning include memory and
computation restrictions and working with sparse and unstructured data such as
point clouds [3]. Additionally, these sub-tasks are more straightforward to
produce ground truth labels for than higher-level scene understanding tasks
such as semantic scene completion, where a ground truth map of the world is
nearly impossible to attain in outdoor, dynamic scenes [1].

(a) Ours

(b) Semantic KITTI [4]

Figure 1: Side-by-side comparison of our dynamic scene completion data set
(left) with Semantic KITTI [4] (right) on dynamic scenes from each respective
data set. Moving vehicles, represented in white, leave traces in the KITTI
data set yet are accurately and completely represented in our data set. Using
multiple viewpoints, we reconstruct a dynamic scene without traces and with
minimal occlusions.

Maps provide a unified framework to combine sensor information into a higher
level of scene understanding with interpretable information. They store
structured information which may be re-purposed later in tasks such as
localization and path planning, where algorithms can retrieve locations of
landmarks and driveable surfaces. This can provide benefits including
increased reliability and predictability in diverse fields such as remote
sensing, augmented reality, autonomous vehicles, and even medical devices.
Although some research has proposed mapless navigation [5, 6, 7], maps are
still widely used due to their interpretability and success.

Maps may include multiple layers of information such as traversability,
semantic labels, and dynamic occupancy. Traversability maps generally
construct a binary go-no-go map which may be used by autonomous vehicles for
optimal path planning. Semantic maps include rich semantic labels for each
cell, however generally only function in static scenes [8, 9]. Dynamic
occupancy maps construct binary labels for cells indicating free or occupied,
and extend their domain to scenes with dynamic actors by incorporating scene
dynamics [10, 11, 12]. While learning-based approaches have been attempted in
2D [13, 14], most 3D maps rely on feature engineering which can decrease
performance and efficiency.

Although mapping algorithms are generally hand-crafted, semantic scene
completion (SSC) is a deep learning approach requiring supervision. In SSC,
sensor data from a single scan is used to complete a dense local semantic
scene where completing the occluded portions of the scene may be accomplished
by smoothing. However, the problem constraints leave time information unused.
By adding temporal information, networks could gain insight into occlusions
and dynamics and become more similar to supervised 3D semantic mapping
algorithms.

The main challenges facing 3D semantic scene understanding are the memory and
computation cost of 3D computer vision [3, 15], and the inability to obtain
accurate ground truth data in the presence of dynamic objects and occlusion
[16]. To combat the exponentially increasing cost of 3D computer vision, some
approaches include projecting to 2D views such as bird’s-eye-view (BEV) [13,
17], spherical-front-view (SFV) [18, 19], point pillars [20], or processing
directly in 3D with point operations [21, 22] or sparse convolutions [23, 24].
Some more recent approaches leverage the speed of 2D convolutions while
preserving height information by treating the vertical dimension of an
occupancy grid as the channel [13, 17]. This method maintains a high inference
rate as fast as 100 Hz while achieving high performance in 3D object detection
and SSC.

A final challenge facing 3D maps is the availability of data sets. A complete
scene is difficult to obtain in the real world due to dynamic objects. While
indoor data sets [25, 26, 27, 28, 29] may place multiple sensors throughout
the scene to construct a 3D environment, this is not feasible for outdoor
environments. Furthermore, currently existing synthetic data sets either
contain only indoor environments, provide annotations for the scene only
visible to the ego sensor, or remove dynamic objects altogether [30].
Therefore, mapping algorithms are commonly evaluated indirectly on object
detection or motion prediction tasks. While data sets such as SemanticKITTI
[4] offer outdoor semantically labeled scenes, dynamic objects leave traces in
the constructed map due to the inconsistency of the scene with respect to
time. The lack of a complete outdoor 3D scene makes it impossible to directly
learn or evaluate 3D mapping in dynamic, outdoor environments.

In this paper, we propose to learn a real-time network that infers a dense
ego-centric 3D semantic map by approaching SSC with temporal information. To
quantify performance and supervise learning accurately, we construct a novel
synthetic data set containing realistic outdoor driving scenes with complete
semantic labels of free and occupied space. By randomly sampling multiple
viewpoints of each scene, we ensure minimal occlusions and no traces left by
dynamic objects. Our contributions are as follows.

  1. 1.

Develop a real-time deep neural network for 3D semantic mapping in dynamic
environments.

  2. 2.

Demonstrate improvement over state-of-the-art semantic scene completion
networks quantitatively and qualitatively.

  3. 3.

Create a new data set for semantic scene completion and 3D mapping in dynamic
outdoor environments to address the shortcomings in existing data sets.

  4. 4.

Open source all data and network software for reproducibility and future
developments at https://github.com/UMich-CURLY/3DMapping.

##  II Preliminaries

We first introduce current scene completion data sets, and modern approaches
to the problem of semantic scene completion. We also mention trade-offs in
storage methods of scenes, and introduce the motivation behind our choice in
baselines.

###  II-A Data sets

Current data sets cannot accurately measure scene completion or mapping
performance in dynamic outdoor environments due to occlusions of moving
objects. While an indoor scene may be captured from multiple viewpoints
simultaneously, this is difficult to do in the real world [16]. Instead,
existing data sets sample the ground truth map at time $t$ by aggregating data
from sequential frames. However, this produces traces left behind by dynamic
actors, leading to incorrectly labeled free or occupied space. An example of
traces and occlusions in a modern scene completion data set is shown in Figure
1b, where dynamic vehicles leave behind long white traces and parts of the
scene are completely occluded. Current approaches solve this issue by avoiding
dynamic objects altogether through rejection of dynamic objects during map
generation or post-rejection of dynamic objects after the map is generated
[31]. However, these convoluted methods are due to the unavailability of
accurate dynamic scenes and are not ideal for obtaining a representation of
the true, complete scene.

Existing outdoor scene completion data sets include SemanticKITTI [4] and
SemanticPOSS [32], or virtual data sets SynthCity [30] and more recently
Paris-CARLA-3D [33]. SemanticKITTI provides densely labeled voxelized scenes,
but is susceptible to traces due to aggregating frames temporally, as shown in
Figure 1. While aggregating recent data to form a complete frame may aid with
completeness, it violates the assumption that the data is independently and
identically distributed (i.i.d.), as dynamic objects have moved between
frames. Although traces may be used to evaluate prediction of a vehicle’s
path, they ultimately hinder accurate evaluation as algorithms are penalized
for correctly predicting free space. SemanticPOSS also provides point clouds
and semantic labels in dynamic scenes, yet is still susceptible to occlusions
and traces for the same reason. SynthCity solves the issue of traces by
removing dynamic objects at the cost of dynamic scenes. Finally, Paris-
CARLA-3D provides a mixed synthetic and real data set using a mobile LiDAR
sensor, but is still susceptible to traces for the same reason. Without a
complete ground truth, it is impossible to correctly quantify performance on
outdoor scene completion in dynamic environments, and difficult to supervise
learning which properly handles dynamic objects.

When creating a data set for SSC, there are a plethora of scene
representations to consider, balancing resolution and information with data
compression. Voxel grids are the most popular 3D representation of semantic
scenes, however there exist several other less frequently used methods for
efficiently storing 3D semantic information [1]. Point clouds are an efficient
and direct method for storing scenes, which may be further optimized through
meshes. However, both meshes and point clouds remain difficult representations
for SSC, and few works have attempted this method due to challenging point
generation. Additionally, sampling free space is more difficult as it is
implicitly defined. Structured grids such as voxel grids or occupancy grids
have the benefit of directly encoding semantic and free labels, and may be
directly processed with convolutions. Despite high memory requirements due to
explicitly defining free and occupied regions, their easy usage and
interpretability make grids a frequent option. While grids may be implicitly
encoded using a gradient field such as Signed Distance Function (SDF) or
Truncated Signed Distance Function (TSDF), some SSC networks have found them
to require a large computation time and add little benefit [17, 34, 4]. For
real-time applications, this trade-off is not practical, and as a result voxel
grids are commonly chosen.

###  II-B Semantic Scene Completion

Scene Completion (SC) is a method of inferring the full geometry of a scene
using either 2D or 3D observations. While research historically used
interpolation methods, a subset of SC known as Semantic Scene Completion (SSC)
has become popular due to advances in 3D deep learning networks. SSC differs
from traditional SC by jointly inferring both semantics and geometry of the
whole scene. Furthermore, the SSC task is made more difficult by the sparsity
of the input data and incomplete ground truth, providing weakly guided
supervision.

Semantic scene completion is a similar task to semantic mapping, however it is
generally defined using sensor data from only a single frame. While there
exist some deep learning 3D mapping methods, it is not a common task due to
the lack of accurate outdoor dynamic data to supervise and quantify
performance on [35, 14, 9, 36]. SSC is currently a difficult task with minimal
generalizability to real life due to the lack of accurately labeled dynamic
scenes, as discussed in the previous section.

There are several approaches to SSC which attempt to balance the complexities
of 3D computer vision with a low run-time for practical purposes. 3D computer
vision has become a more tractable problem due to innovative approaches such
as PointNet [21, 22], PointPillars [20], VoxelNet [15], and sparse
convolutions [24, 37]. These networks were able to reduce the memory and
computation consumption of directly processing 3D data through viewing the
problem in different ways. As a result, scene completion may be formulated in
any of these formats through View-Volume networks, Volume networks, Hybrid
networks, and Point-based networks [16].

Volume networks consist of 3D convolution to directly accomplish scene
completion due to high levels of success in semantic segmentation, and the
ability to aggregate contextual information from different levels [38, 39].
This approach is limited by the large memory necessitated by directly
processing 3D data, so is generally attempted with sparse convolutions such as
in JSC3Net [38]. View-Volume networks such as LMSCNet [17] and SSCNet [29] use
2D convolutions in conjunction with 3D convolutions due to the efficiency of
2D convolutions. One method is to view the vertical axis of the 3D scene as a
channel dimension, thus enabling the scene to be processed with 2D
convolutions. This approach has also been taken in other 3D deep learning
tasks with demonstrable success, such as MotionNet [13] in the task of 3D
object detection. A segmentation head then lifts the features from 2D to 3D to
complete semantic segmentation of the 3D scene. Point-based networks operate
directly on points to prevent discretization, but few works have investigated
this avenue [40]. Finally, Hybrid networks combine any of the aforementioned
methods [4, 41, 42, 34, 43].

##  III Method

Our methodology is split into two sections: first we construct a complete
outdoor dynamic data set, and next we train a model from our data set.

(a)

(b)

(c)

(d)

(e)

Figure 2: An illustration of our approach to constructing a 3D dynamic outdoor
driving data set. The ego vehicle is circled in all images, and is filtered
out of the raw data. Top: The left image shows the Bird’s Eye View (BEV) of a
driving frame from our data set, the middle image demonstrates the current
method of semantic scene generation, and the right image contains our method.
Our method is able to accurately label free space without traces through the
use of additional randomly placed sensors. Bottom: Constructed 3D semantic
scene in Cartesian (Left) and Cylindrical (Right) coordinate systems. While we
do not use Cylindrical scenes in our evaluation, ground truth scenes may be
found on our website.

###  III-A Data

We create a new outdoor driving semantic scene completion data set with
accurate and complete scenes, which we call CarlaSC. Our data set is a large
3D synthetic outdoor driving scene completion data set with explicit free
space and semantic labels, without the issues of occlusion and traces in
Semantic KITTI [4]. Ground truth semantic scenes are generated from multiple
randomly placed LiDAR sensors in the CARLA [44] simulator. While multiple
cameras have been used for indoor static scenes, this is the first synthetic
data set to extend the same approach to dynamic scenes. Our data set is
intended to correctly evaluate semantic mapping algorithms in dynamic scenes,
and supervise training of dynamic algorithms. Although multiple view points
may not be easily extended to the real world, we present ideas for how the
static assumption of data collection may be removed to create accurate,
complete scenes in Sections III-A and V.

Our data set consists of 24 scenes in 8 dynamic maps with road users in
various traffic settings. We divide the maps into a train, validation, and
test set where the train set contains the first six maps, the validation set
contains map Town07, and the test set contains map Town10. Each map is used to
create three scenes under low, medium and high traffic conditions, where each
scene contains 3 minutes of data sampled at 10 Hz. Ground truth labels include
point clouds with semantic segmentation and ego-compensated scene flow labels,
ground truth pose and time labels, Bird’s Eye View images, and the complete
semantic scene. Scenes are represented by 3D voxel grids due to explicit
occupancy labels, and ease of use.

Figure 3: Toy illustration of how the semantic measurement for a single voxel
$i$ is obtained. Multiple sensors, shown as eyeglasses, are uniformly
distributed surrounding the ego vehicle and sample points with ground truth
semantic labels from the environment. Occupied points are shown in black, and
free observations obtained from ray tracing are red. In this case, sensors 2
and 3 observe points in cell $i$ with label $k$. However, sensor 1 observes a
point past the cell, resulting in a free space sample in cell $i$ from ray
tracing. Therefore there are two $k$ measurements and one free measurement for
voxel $i$, which is labeled as class $k$ after a majority vote.

We generate synthetic data from the CARLA simulator for its high definition,
ability to generalize to the real world, and realism including autonomous
pedestrians and vehicles, weather patterns, and traffic. Additionally, the
CARLA simulator may be fully synchronized so that we may obtain ground truth
pose and sensor data at every frame. While the CARLA API does not provide
access to the mesh at each frame, we are able to semantically label the local
volume around the ego vehicle by placing multiple sensors around the vehicle.

Ground truth sensor data is obtained from simulated Velodyne 64-E LiDAR
sensors, which are the same type used in KITTI [4]. The ego-sensor is placed
on board the ego vehicle half a meter backwards from the center of the
vehicle, and at the top of the vehicle 1.8 meters above the ground. The sensor
samples at a frequency of 10 Hz with 130,000 points per scan created from 64
channels. The maximum range is 50 meters, and points which sample the ego
vehicle or an invalid label from the simulator are discarded, creating a clean
data set. Uniform noise is added to each point, such that each point is at
most 2 centimeters from its true value.

To create the semantic volume for each frame, we uniformly distribute 20
additional LiDAR sensors surrounding the ego vehicle, then aggregate their
scans to obtain a complete scene. Any voxels without laser or free space
measurements are rendered invalid, and excluded from evaluation. The LiDAR
sensors remain fixed relative to the ego-vehicle for the duration of the
scene, and a new configuration is randomly generated for each driving
sequence. While some data sets construct a ground truth scene in front of the
ego vehicle, we construct a scene completely surrounding the vehicle due to
the nature of LiDAR sensors. By generating point clouds from multiple randomly
placed sensors, we obtain voxelized labels more reflective of the true
distribution, without the presence of traces and with minimal occlusions. We
change the location of sensors between each scene to ensure that the whole
data set is a better representation of the true data distribution, and to
teach supervised networks to generalize to any view. Placing the sensors
randomly assures that our data is i.i.d., which we can show guarantees
convergence by the strong law of large numbers as the number of sensors and
samples increases.

Algorithm 1 Ray Tracing Algorithm

1:Require: semantic point cloud $P_{s}^{t}$, free space step $r$

2:$O_{s}^{t}\leftarrow\varnothing$

3:for $x_{i},y_{i}\in P_{s}^{t}$ do

4: $O_{s}^{t}\leftarrow O_{s}^{t}\cup(x_{i},y_{i})$ $\triangleright$ Occupied
observation

5: $d\leftarrow\lVert x_{i}\rVert-r$

6: $\hat{x}_{i}\leftarrow\frac{x_{i}}{\lVert x_{i}\rVert}$

7: while $d>0$ do $\triangleright$ Iterate towards sensor

8: $O_{s}^{t}\leftarrow O_{s}^{t}\cup(d\cdot\hat{x}_{i},\text{\emph{free}})$
$\triangleright$ Free observation

9: $d\leftarrow d-r$

10: end while

11:end for

12:$O_{s}^{t}\leftarrow T_{0,s}O_{s}^{t}$ $\triangleright$ Transform to ego-
sensor frame

13:Return: sensor observations $O_{s}^{t}$

Let $O^{t}$ indicate the set of observations of the world, $\mathcal{S}$
represent the set of $N$ randomly placed i.i.d. sensors $s$ sampled from a
uniform distribution $U(\cdot)$ surrounding the ego vehicle, and $t$ be the
current time. Then, we can write that:

${\color[rgb]{0,0,0}s\sim U(\begin{bmatrix}X_{min},X_{max}\\\
Y_{min},Y_{max}\\\ Z_{min},Z_{max}\end{bmatrix}),}$ (1)

$p(O^{t})=\int_{\mathcal{S}}{p(O^{t}\mid
s)p(s)}ds\>\approx\>\frac{1}{N}\sum_{i=1}^{N}p(O^{t}\mid s_{i}),$ (2)

where the set of observations is defined as

$O^{t}=\\{O_{s}^{t}\mid\forall\,s\in\mathcal{S}\\}.$ (3)

This shows that our samples are representative of the expected observations,
even in the presence of dynamic objects. Additionally, points from multiple
uniformly distributed sensors may be aggregated into the ground truth scene
without weighting as shown in (3). While multiple viewpoints are difficult to
achieve in the real world, the same approach of gathering i.i.d. samples may
be applied through instance segmentation and reconstruction of non-deformable
dynamic objects, which we have left as future work. An example of the raw data
produced for a single frame is shown in Fig. 2. As can be seen, there are no
traces left by dynamic objects, and a more complete view of the scene is
available, with fewer occlusions.

Figure 4: Proposed MotionSC network. MotionSC is a view-volume scene
completion network which incorporates a Spatio-Temporal Pyramid Network [13]
backbone to incorporate temporal information in real-time. The input to the
network is the past $T$ raw point clouds and corresponding poses, which are
converted to a stack of the past $T\in\mathbb{N}$ binary occupancy grids. For
specific layer details, please see our website.

To label free space in our 3D volume, we ray trace across each LiDAR ray in
fixed distance increments, starting from the endpoint. Sampling in constant
spacing ensures that free samples are also i.i.d.. An algorithm for ray
tracing is shown in Algorithm 1, where the set of all occupied and free
observations $O_{s}^{t}$ for sensor $s$ are computed from the point cloud
$P_{s}^{t}$ observed by sensor $s$ in its frame of reference. Note that each
point contains a geometric position $x\in\mathbb{R}^{3}$ and a semantic label
$y\in\mathbb{N}$. $r$ is a hyper-parameter indicating the sampling distance
between free space labels. Once all observations are computed, they are
transformed to the on-board ego sensor using a transformation matrix where
$s=0$ represents the ego-matrix. Finally, (3) shows how all observations are
combined into one set $O^{t}$, which is used to compute the complete semantic
scene. An illustration of the free space sampling and data aggregation method
is shown in Fig. 3.

One advantage of our method is that it is scalable and open source, so that
multiple resolutions or configurations may be generated. We publish two
versions of the completed scenes on our website, one with the same dimensions
and resolution of Semantic KITTI, and a slightly more coarse version. We
choose the coarse scenes for our evaluations, where each semantically labeled
scene is of the dimension (128, 128, 8), with a dimension of $-25.6$ to $25.6$
meters in the $x$ and $y$ axes, and $-2.0$ to $1.0$ meters in the vertical
axis. We set free space sampling interval $r=1.5\mathop{\mathrm{m}}$ to avoid
saturation of the data set from over-sampling and voxel discretization. For
more information on how to use our data and the specifications, please see our
website.

Remapped Class |  Original Classes
---|---
Other |  Other, Sky, Bridge, Railtrack, Static, Dynamic, Water
Barrier |  Fence, Wall, Guardrail
Poles |  Pole, Traffic Light, Traffic Sign
Road |  Road, Roadline
Ground |  Ground, Terrain
Table I: Remapped classes and the original CARLA classes they contain.

Our data set includes the raw CARLA labels obtained for every point, however
we find that some classes are unobserved or exceedingly difficult to
distinguish from one another by LiDAR sensor. Therefore, we perform evaluation
on a remapped version of the data, where semantic labels are mapped from the
initial CARLA labels to a set of 11, as shown in Table I.

Method |  mIoU |  Accuracy |  Free |  Building |  Barrier |  Other |  Pedestrian |  Pole |  Road |  Ground |  Sidewalk |  Vegetation |  Vehicles
---|---|---|---|---|---|---|---|---|---|---|---|---|---
LMSCNet SS [17] | 42.53 | 94.64 | 97.41 | 25.61 | 3.35 | 11.31 | 33.76 | 43.54 | 85.96 | 21.15 | 52.64 | 39.99 | 53.09
SSCNet Full [29, 17] | 41.91 | 94.11 | 96.02 | 27.04 | 1.82 | 13.65 | 29.69 | 27.02 | 88.45 | 25.89 | 65.36 | 33.29 | 52.78
MotionSC (T=1) | 46.31 | 95.11 | 97.42 | 31.59 | 2.63 | 14.77 | 39.87 | 42.11 | 90.57 | 25.89 | 60.77 | 42.41 | 61.37
MotionSC (T=5) | 45.35 | 95.00 | 97.43 | 29.48 | 2.54 | 17.48 | 41.87 | 43.43 | 90.90 | 22.08 | 58.43 | 35.79 | 59.41
MotionSC (T=10) | 47.01 | 95.15 | 97.44 | 32.29 | 2.35 | 19.82 | 44.06 | 45.47 | 90.19 | 27.35 | 62.48 | 36.92 | 58.80
MotionSC (T=16) | 47.45 | 95.57 | 97.60 | 34.91 | 2.66 | 22.86 | 37.78 | 43.87 | 90.12 | 28.31 | 66.20 | 41.59 | 56.08

Table II: Semantic results on test set of CarlaSC. The network is adjusted to
accommodate smaller dimensions of $T$ by changing the temporal dimension of
the Spatio-Temporal Convolution layer to $1$, effectively creating a fully-
connected layer as the convolution kernel is dimension (1, 1, 1). The base
model with $T=1$ uses 1,967 MB of memory, while MotionSC with a temporal stack
of $T=16$ uses 2,427 MB of memory.

###  III-B MotionSC: Dense Local Mapping

Next, we create a benchmark 3D dynamic semantic mapping neural network on our
data set which we compare to baseline state-of-the-art scene completion
algorithms. The goal of our method, MotionSC, is to create a real-time dense
local semantic mapping algorithm which may run on-board mobile robots in
outdoor, dynamic scenes. Due to the memory and latency constraints of onboard
applications, MotionSC is a view-volume scene completion network which
primarily consists of 2D operations. MotionSC builds upon the real-time
temporal backbone of MotionNet [13] which learns a latent space capable of
reasoning about dynamic objects. A segmentation head then lifts the
dimensionality of the feature space to predict a complete semantic scene. Our
network synthesizes deep learning advancements in semantic scene completion
and object detection to realize a higher level of scene understanding, and
accomplish a new application of semantic mapping in dynamic environments.
MotionSC is novel in that it combines a temporal backbone from object
detection with a view-volume SSC network architecture to jointly track objects
and complete semantic scenes. A diagram of our network may be seen in Fig. 4.

The input to MotionSC is a raw point cloud, which we convert to a 3D binary
occupancy grid. We choose 3D occupancy grids instead of truncated signed
distance function (TSDF) format since TSDF format has been found to require a
greedy computation time with little benefit [17, 4, 34], which makes it
impractical for a real-time dense local mapping algorithm. Input point clouds
are transformed to the current frame using pose information, as we found no
correlation between performance and stack height $T$ if pose information was
discarded. 3D occupancy grids are created for each frame and maintained in a
stack with a maximum depth of $T$ consecutive frames. By leveraging temporal
information, we are able to train the network to reason about dynamic objects
and occlusions. The occupancy grids are a tensor of shape $(C,H,W)$ where the
$H$ and $W$ represent the horizontal axes while $C$ represents the vertical
axis, encoded as a channel dimension similar to a bird’s eye view image.

The temporally stacked occupancy grids are fed to a Spatio-Temporal Pyramid
Network (STPN) [13], which treats the vertical axis as a channel dimension $C$
to process the four dimensional grid in real time using 2D convolutions and
temporal pooling. The STPN is shown in Fig. 4, and is a U-Net [45] structure
composed of two key components: Temporal Pooling (TP) to aggregate information
across frames, and Spatio-Temporal Convolution (STC) to increase feature size
while reducing the temporal and spatial dimensions. The output of the STPN is
a feature vector of shape $(1,C,H,W)$, where temporal information is
implicitly encoded within the channel dimension. TP is a consistent operation
throughout all layers, and applies a max pooling operation over the 4D tensor
across the temporal axis, reducing the $T$ dimension to size 1. STC is a
series of 2D convolutions dimensions to grow the channel size and reduce the
spatial dimension by half, sometimes followed by a 3D convolution over the
$(T,H,W)$ dimensions. For $T<3$, temporal convolution with a width of $3$ may
not be performed, so we resize the filter to shape $(1,1,1)$ which effectively
performs a linear layer operation. Upsampling deeper layers to combine with
shallow layers is done by interpolation over the $(H,W)$ dimensions by a
factor of 2, then concatenating with the next sequential layer and applying 2D
convolutions. For more information on STPN see [13], and on our layer hyper-
parameters see our website.

A segmentation head lifts the dimensionality of the latent tensor from
$(1,C,H,W)$ to $(K,C,H,W)$ in order to assign a semantic label to every 3D
voxel. We use the segmentation head from LMSCNet [17], as LMSCNet is also a
view-volume scene completion network which has achieved high performance. The
segmentation head performs 3D convolutions to lift the feature dimension from
1 to $K$, and learns spatial relations through an Atrous Spatial Pyramid
Pooling (ASPP) block [46, 47]. For inference, a softmax layer is applied to
obtain probabilities per class.

##  IV Results and Discussion

We establish baselines using state-of-the-art open source SSC networks on our
data set, then compare our proposed real-time dynamic semantic mapping
network, MotionSC, to establish a benchmark. We perform a temporal ablation
study to demonstrate that temporal information enhances our network to achieve
semantic and geometric completion results on par or better on both metrics. We
also include a comparison on the real-world Semantic KITTI data set to
demonstrate that our method works successfully on real data.  Finally, we
include a qualitative comparison from images on our test set of each model.

###  IV-A Quantitative Evaluation

We perform a comparison of our method with several state-of-the-art SSC
networks on the test set of our data set, and the real-world Semantic KITTI
[4] data set. We choose to compare our network on our data set with LMSCNet
[17] and SSCNet [29], as they are the best available open-source view-volume
SSC networks at the time. We use the single-state (SS) variation of LMSCNet
and full variation of SSCNet, as they were shown to have the best performance
in [17]. While these networks do not take advantage of temporal information,
they serve as a strong baseline for MotionSC on our data set. To ensure a fair
comparison, we perform an ablation study of the temporal stack height. At
$T=1$, our network reduces to a view-volume SSC model, while at larger stack
sizes it uses past information. As mentioned in Section II-B, there are few
open-source supervised mapping algorithms for dynamic scenes, and as a result
state-of-the-art SSC networks make competitive baselines.

LMSCNet and SSCNet are view-volume networks with low inference times and
memory usage. We imitate each network’s learning parameters and process as
closely as possible and choose the best model according to the mean
intersection over union (mIoU) on the validation set. Models are trained for
24 to 48 hours, and model weights and training data are recorded and are
available open-source for reference. We train the models until convergence is
reached, which we found to be 10 epochs for MotionSC and 20 epochs for the
baselines.

MotionSC is compared with the baselines on the test set of CarlaSC and
Semantic KITTI. Concretely, the input to each algorithm is the past $T$ scans
from the ego-vehicle LiDAR, and the output is a full scene containing a
predicted semantic label for each voxel. Predictions are evaluated at every
ground truth voxel containing laser measurements, including voxels occluded to
the ego vehicle. In line with [4], we compute performance over geometric
completeness and semantic completeness.

Table II shows the results of our model compared to the baselines on the test
set, including an ablation study of the effect of $T$. Comparing MotionSC with
$T=1$ with the baselines, we find that our model achieves both a higher
semantic accuracy and mean intersection over union (mIoU). As the temporal
stack height increases, MotionSC improves at nearly all metrics, most evident
by the mIoU score. A stack height of $T=16$ corresponds to the last 1.6
seconds of information, and could be further increased at the cost of more
memory. A similar pattern emerges when measuring performance on geometric
completeness, shown in Table III. Geometric completeness measures binary
occupancy by mapping all non-free semantic classes to a single label. This
metric indicates that MotionSC gains an advantage in completeness by
leveraging temporal information to mitigate occlusions.

Method | Precision (%) | Recall (%) | IoU (%)
---|---|---|---
SSCNet Full | 85.87 | 93.05 | 80.69
LMSCNet SS | 95.62 | 89.5 | 85.98
MotionSC (T=1) | 93.32 | 92.16 | 86.46
MotionSC (T=5) | 94.76 | 90.57 | 86.25
MotionSC (T=10) | 93.17 | 92.43 | 86.56
MotionSC (T=16) | 94.61 | 91.77 | 87.21
Table III: Geometric Completeness on test set of CarlaSC. MotionSC has a better geometric IoU than the baselines at $T=1$, which is again increased as the temporal stack height grows. Although LMSCNet achieves the best precision, it has lower recall, meaning that it fails to identify a larger portion of the occupied space. Method | Geom. IoU (%) | Sem. mIoU (%) | Latency (ms)
---|---|---|---
SSCNet Full [29] | 49.98 | 16.14 | 2.18
LMSCNet SS [17] | 56.72 | 17.62 | 4.86
MotionSC (T=1) | 56.85 | 18.42 | 5.72
JS3CNet [38] | 56.6 | 23.8 | 166.2
Table IV: Comparison of published methods on test set of Semantic KITTI [4]
over Geometric IoU, Semantic mIoU, and latency metrics. We only compare our
method with T=1 due to the restrictions of the scene completion competition.
Latency is measured on an NVIDIA GeForce RTX 3090 GPU, averaged over one
hundred repetitions.

Finally, we quantitatively evaluate our model on the test set of Semantic
KITTI, shown in Table IV. For this comparison, we use $T=1$ as MotionSC
reduces to a view-volume semantic scene completion network. On Semantic KITTI,
MotionSC again outperforms SSCNet Full and LMSCNet SS, demonstrating that the
performance patterns transfer from our data set to the real world. We include
an additional comparison with the volume network JS3CNet [38]. JS3CNet
achieves greater semantic performance than the baselines and our model,
however it has lower geometric completeness than MotionSC and a slower
inference rate due to costly 3D convolutions. Note that incorporating temporal
information should logically see the same gains in geometric and semantic
completeness, thereby improving MotionSC in real world robotic applications.

###  IV-B Qualitative Evaluation

We compare MotionSC qualitatively with SSCNet Full and LMSCNet SS on the test
set of our data set by generating predictions for each model and comparing the
predictions visually in a side-by-side comparison. We also include
illustrations of MotionSC when $T=1$ and $T=16$ to demonstrate the effect of
temporal information. We choose a scene with an occlusion, as temporal
information allows the network to complete regions which are currently
occluded.

Figure 5: Qualitative comparison of MotionSC at $T=1$ and $T=16$ with SSCNet
and LMSCNet. The left four images show predictions from each network,
visualized from a bird’s eye view. The right image shows the ground truth
bird’s eye view image of the scene for validation. Note that the ego vehicle
is not in the predicted scenes, and is circled in white. In this frame, the
ego vehicle’s view of the road to the left is occluded. LMSCNet, SSCNet, and
MotionSC ($T=1$) are all susceptible to occlusions, and have noise in the
output, although MotionSC has the most complete road. When $T=16$, MotionSC
successfully incorporates past point clouds to complete the road. Videos are
included on our website.

As was shown quantitatively, MotionSC achieves a high level of geometric
completeness and semantic segmentation due to temporal information. In Fig. 5,
a scene from the test set of our data set is depicted, which shows the ego
vehicle driving next to multiple cars. The neighboring vehicle obscures the
view of the nearby street, causing noise in both baselines and MotionSC with
$T=1$. In contrast, MotionSC ($T=16$) is able to complete the scene from past
scans, and accurately forms the road to the left of the scene. MotionSC
($T=1$) still outperforms the baselines, as was demonstrated quantitatively on
both our data set and Semantic KITTI.

Each network is able to generate a complete scene with semantic labels to some
degree. SSCNet creates a smooth scene, although it is unable to complete the
road to the left of the scene due to the occlusion. LMSCNet is most
susceptible to noise due to occlusions, which is evident again in the street
to the left and in individual vehicles. MotionSC in contrast, is able to
generate the most smooth scene of the view-volume networks, with the road and
sidewalk clearly labeled, and minimal occlusions.

##  V Conclusion

This paper addressed a need for semantic scene completion data by creating a
novel outdoor data set with accurate and complete dynamic scenes. The data set
uses the CARLA simulator [44] with similar parameters to the real-life
Semantic KITTI [4] data set to promote generalization in future works. We
trained a real-time dense local semantic mapping algorithm to enhance semantic
scene completion using temporal information. Our network shows that the
proposed data set can quantify and supervise accurate scene completion in the
presence of dynamic objects, encouraging future developments of dynamic
mapping algorithms by the community.

Future work includes improving the MotionSC algorithm to develop a more robust
real-time local semantic mapping algorithm by adding recurrency or
quantifiable uncertainty. Additional direction includes extending the proposed
data construction method to the real world. While multiple sensors may not
directly transfer to the real world, correct dynamic scenes may be formed by
segmenting instances and using partial views to complete each actor, or
importance sampling of point clouds from a multi-agent environment.

## References

  * [1] L. Wang and Y. Huang, “A Survey of 3D Point Cloud and Deep Learning-Based Approaches for Scene Understanding in Autonomous Driving,” _IEEE Trans. Intell. Transp. Syst._ , 2021.
  * [2] J. Janai, F. Guney, A. Behl, and A. Geiger, “Computer Vision for Autonomous Vehicles: Problems, Datasets and State-of-the-Art,” _Foundations and Trends in Computer Graphics and Vision_ , vol. 12, 04 2017.
  * [3] Y. Guo, H. Wang, Q. Hu, H. Liu, L. Liu, and M. Bennamoun, “Deep Learning for 3D Point Clouds: A Survey,” _IEEE Trans. Pattern. Analy. Machine. Intell._ , vol. 43, no. 12, pp. 4338–4364, 2020.
  * [4] J. Behley, M. Garbade, A. Milioto, J. Quenzel, S. Behnke, C. Stachniss, and J. Gall, “SemanticKITTI: A Dataset for Semantic Scene Understanding of LiDAR Sequences,” in _Proc. IEEE Int. Conf. Comput. Vis._ , 2019.
  * [5] S. Casas, A. Sadat, and R. Urtasun, “MP3: A Unified Model to Map, Perceive, Predict and Plan,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2021, pp. 14 403–14 412.
  * [6] F. Codevilla, M. Müller, A. López, V. Koltun, and A. Dosovitskiy, “End-to-End Driving Via Conditional Imitation Learning,” in _Proc. IEEE Int. Conf. Robot. and Automation_. IEEE, 2018 , pp. 4693–4700.
  * [7] H. L. Chiang, A. Faust, M. Fiser, and A. Francis, “Learning Navigation Behaviors End-to-End With AutoRL,” _IEEE Robot. Autom. Letter._ , vol. 4, no. 2, pp. 2007–2014, 2019 .
  * [8] L. Gan, R. Zhang, J. W. Grizzle, R. M. Eustice, and M. Ghaffari, “Bayesian Spatial Kernel Smoothing for Scalable Dense Semantic Mapping,” _IEEE Robot. Autom. Letter._ , vol. 5, no. 2, pp. 790–797, 2020.
  * [9] L. Sun, Z. Yan, A. Zaganidis, C. Zhao, and T. Duckett, “Recurrent-OctoMap: Learning State-Based Map Refinement for Long-Term Semantic Mapping with 3-D-Lidar Data,” _IEEE Robot. Autom. Letter._ , vol. 3, no. 4, pp. 3749–3756, 2018.
  * [10] Y. Min, D.-U. Kim, and H.-L. Choi, “Kernel-Based 3-D Dynamic Occupancy Mapping with Particle Tracking,” in _Proc. IEEE Int. Conf. Robot. and Automation_. IEEE, 2021, pp. 5268–5274.
  * [11] A. Unnikrishnan, J. Wilson, L. Gan, A. Capodieci, P. Jayakumar, K. Barton, and M. Ghaffari, “Dynamic Semantic Occupancy Mapping using 3D Scene Flow and Closed-Form Bayesian Inference,” _arXiv preprint arXiv:2108.03180_ , 2021\.
  * [12] D. Nuss, S. Reuter, M. Thom, T. Yuan, G. Krehl, M. Maile, A. Gern, and K. Dietmayer, “A Random Finite Set Approach for Dynamic Occupancy Grid Maps with Real-Time Application,” _Int. J. Robot. Res._ , vol. 37, no. 8, pp. 841–866, 2018.
  * [13] P. Wu, S. Chen, and D. N. Metaxas, “MotionNet: Joint Perception and Motion Prediction for Autonomous Driving Based on Bird’s Eye View Maps,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2020, pp. 11 382–11 392.
  * [14] E. Amirloo, M. Rohani, E. Banijamali, J. Luo, and P. Poupart, “Self-Supervised Simultaneous Multi-Step Prediction of Road Dynamics and Cost Map,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2021, pp. 8490–8499.
  * [15] Y. Zhou and O. Tuzel, “VoxelNet: End-to-End Learning for Point Cloud Based 3D Object Detection,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2018, pp. 4490–4499.
  * [16] L. Roldao, R. de Charette, and A. Verroust-Blondet, “3D Semantic Scene Completion: a Survey,” _CoRR_ , vol. abs/2103.07466, 2021.
  * [17] L. Roldao, R. De Charette, and A. Verroust-Blondet, “LMSCNet: Lightweight Multiscale 3D Semantic Completion,” _Proc. IEEE Int. Conf. 3D Vis._ , pp. 111–119, 2020.
  * [18] B. Wu, A. Wan, X. Yue, and K. Keutzer, “SqueezeSeg: Convolutional Neural Nets with Recurrent CRF for Real-Time Road-Object Segmentation from 3D LiDAR Point Cloud,” in _Proc. IEEE Int. Conf. Robot. and Automation_. IEEE, 2018, pp. 1887–1893.
  * [19] A. Milioto, I. Vizzo, J. Behley, and C. Stachniss, “RangeNet++: Fast and accurate LiDAR semantic segmentation,” in _Proc. IEEE/RSJ Int. Conf. Intell. Robots and Syst._ IEEE, 2019, pp. 4213–4220.
  * [20] A. H. Lang, S. Vora, H. Caesar, L. Zhou, J. Yang, and O. Beijbom, “PointPillars: Fast Encoders for Object Detection From Point Clouds,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2019, pp. 12 697–12 705.
  * [21] R. Charles, H. Su, M. Kaichun, and L. J. Guibas, “PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2017 , pp. 77–85.
  * [22] C. R. Qi, L. Yi, H. Su, and L. J. Guibas, “PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space,” in _Proc. Advances Neural Inform. Process. Syst. Conf._ , 2017, pp. 1–10.
  * [23] Y. Yan, Y. Mao, and B. Li, “Second: Sparsely Embedded Convolutional Detection,” _Sensors_ , vol. 18, no. 10, p. 3337, 2018.
  * [24] C. Choy, J. Gwak, and S. Savarese, “4D Spatio-Temporal ConvNets: Minkowski Convolutional Neural Networks,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2019 , pp. 3070–3079.
  * [25] N. Silberman, D. Hoiem, P. Kohli, and R. Fergus, “Indoor Segmentation and Support Inference from RGBD Images,” in _Proc. European Conf. Comput. Vis._ , 2012.
  * [26] A. Chang, A. Dai, T. Funkhouser, M. Halber, M. Niebner, M. Savva, S. Song, A. Zeng, and Y. Zhang, “Matterport3D: Learning from RGB-D Data in Indoor Environments,” in _Proc. IEEE Int. Conf. 3D Vis._ , 2017 , pp. 667–676.
  * [27] A. Dai, A. X. Chang, M. Savva, M. Halber, T. Funkhouser, and M. Niessner, “ScanNet: Richly-Annotated 3D Reconstructions of Indoor Scenes,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2017 , pp. 2432–2443.
  * [28] J. Xiao, A. Owens, and A. Torralba, “SUN3D: A Database of Big Spaces Reconstructed Using SfM and Object Labels,” in _Proc. IEEE Int. Conf. Comput. Vis._ , 2013, pp. 1625–1632.
  * [29] S. Song, F. Yu, A. Zeng, A. X. Chang, M. Savva, and T. Funkhouser, “Semantic Scene Completion from a Single Depth Image,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2017 , pp. 190–198.
  * [30] D. Griffiths and J. Boehm, “SynthCity: A Large Scale Synthetic Point Cloud,” _ArXiv preprint_ , pp. 1–6, 2019.
  * [31] H. Lim, S. Hwang, and H. Myung, “ERASOR: Egocentric Ratio of Pseudo Occupancy-Based Dynamic Object Removal for Static 3D Point Cloud Map Building,” _IEEE Robot. Autom. Letter._ , vol. 6, no. 2, pp. 2272–2279, 2021.
  * [32] Y. Pan, B. Gao, J. Mei, S. Geng, C. Li, and H. Zhao, “SemanticPOSS: A Point Cloud Dataset with Large Quantity of Dynamic Instances,” _IEEE Intell. Vehicles. Sympos._ , pp. 687–693, 2020 .
  * [33] J. E. Deschaud, D. Duque, J. P. Richa, S. Velasco-Forero, B. Marcotegui, and F. Goulette, “Paris-CARLA-3D: a Real and Synthetic Outdoor Point Cloud Dataset for Challenging Tasks in 3D Mapping,” _Remote Sensing_ , vol. 13, no. 22, pp. 1–24, 2021.
  * [34] M. Garbade, Y.-T. Chen, J. Sawatzky, and J. Gall, “Two Stream 3D Semantic Scene Completion,” in _IEEE/CVF Conf. Comput. Vis. Pattern Recog. Workshops (CVPRW)_ , 2019, pp. 416–425.
  * [35] Y. Xiang and D. Fox, “DA-RNN: Semantic Mapping with Data Associated Recurrent Neural Networks,” in _Robotics. Sci. Sys._ , vol. 13, 2017.
  * [36] C. Zhao, L. Sun, P. Purkait, T. Duckett, and R. Stolkin, “Dense RGB-D Semantic Mapping with Pixel-Voxel Neural Network,” _Sensors_ , vol. 18, no. 9, 2018.
  * [37] B. Graham, M. Engelcke, and L. van der Maaten, “3D Semantic Segmentation with Submanifold Sparse Convolutional Networks,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2018.
  * [38] X. Yan, J. Gao, J. Li, R. Zhang, Z. Li, R. Huang, and S. Cui, “Sparse Single Sweep LiDAR Point Cloud Segmentation via Learning Contextual Shape Priors from Scene Completion,” in _Proc. AAAI Nat. Conf. Artif. Intell._ , 2021 .
  * [39] J. Zhang, H. Zhao, A. Yao, Y. Chen, L. Zhang, and H. Liao, “Efficient Semantic Scene Completion Network with Spatial Group Convolution,” in _Lec. Notes. Comp. Sci._ , vol. 11216 LNCS, 2018, pp. 749–765.
  * [40] M. Zhong and G. Zeng, “Semantic Point Completion Network for 3D Semantic Scene Completion,” _Front. Artif. Intell. Appl._ , vol. 325, pp. 2824–2831, 2020.
  * [41] Y. Cai, X. Chen, C. Zhang, K. Lin, X. Wang, and H. Li, “Semantic Scene Completion via Integrating Instances and Scene in-the-Loop,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recog._ , 2021 , pp. 324–333.
  * [42] R. Cheng, C. Agia, Y. Ren, X. Li, and L. Bingbing, “S3CNet: A Sparse Semantic Scene Completion Network for LiDAR Point Clouds,” in _Conf. Robot. Learning._ , 2020 .
  * [43] C. Rist, D. Emmerichs, M. Enzweiler, and D. Gavrila, “Semantic Scene Completion using Local Deep Implicit Functions on LiDAR Data,” _IEEE Trans. Pattern. Analy. Machine. Intell._ , pp. 1–1, 2021 .
  * [44] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun, “CARLA: An Open Urban Driving Simulator,” in _Conf. Robot. Learning._ , 2017, pp. 1–16.
  * [45] O. Ronneberger, P. Fischer, and T. Brox, “U-Net: Convolutional Networks for Biomedical Image Segmentation,” _Med. Image. Comp. Comp-Assisted. Interv._ , pp. 234–241, 2015 .
  * [46] L. Chen, G. Papandreou, I. Kokkinos, K. Murphy, and A. L. Yuille, “DeepLab: Semantic Image Segmentation with Deep Convolutional Nets, Atrous Convolution, and Fully Connected CRFs,” _IEEE Trans. Pattern. Analy. Machine. Intell._ , vol. 40, no. 4, pp. 834–848, 2018 .
  * [47] S. Liu, Y. Hu, Y. Zeng, Q. Tang, B. Jin, Y. Han, and X. Li, “See and Think: Disentangling Semantic Scene Completion,” in _Proc. Advances Neural Inform. Process. Syst. Conf._ , 2018.


# Opportunistic Qualitative Planning in Stochastic Systems with Incomplete
Preferences over Reachability Objectives

Abhishek N. Kulkarni∗, and Jie Fu A. Kulkarni (∗ corresponding author) and J.
Fu are with the Dept. of Electrical and Computer Engineering, University of
Florida, Gainesville, Fl 32611 USA<EMAIL_ADDRESS>material
is based upon work supported by the Air Force Office of Scientific Research
under award number FA9550-21-1-0085.

###### Abstract

Preferences play a key role in determining what goals/constraints to satisfy
when not all constraints can be satisfied simultaneously. In this paper, we
study how to synthesize preference satisfying plans in stochastic systems,
modeled as a Markov Decision Process (MDP), given a (possibly incomplete)
combinative preference model over temporally extended goals. We start by
introducing new semantics to interpret preferences over infinite plays of the
stochastic system. Then, we introduce a new notion of _improvement_ to enable
comparison between two prefixes of an infinite play. Based on this, we define
two solution concepts called Safe and Positive Improving (SPI) and Safe and
Almost-Sure Improving (SASI) that enforce improvements with a positive
probability and with probability one, respectively. We construct a model
called an improvement MDP, in which the synthesis of SPI and SASI strategies
that guarantee at least one improvement reduces to computing positive and
almost-sure winning strategies in an MDP. We present an algorithm to
synthesize the SPI and SASI strategies that induce multiple sequential
improvements. We demonstrate the proposed approach using a robot motion
planning problem.

##  I Introduction

With the rise of artificial intelligence, robotics and autonomous systems are
being designed to make complex decisions by reasoning about multiple goals at
the same time. Preference-based planning (PBP) allows the systems to decide
which goals to satisfy when not all of them can be achieved [1]. Even though
PBP has been studied since the early 1950s, most works on preference-based
temporal planning (c.f. [2]) fall into at least one of the following
categories: (a) those which assume that all outcomes are pairwise
comparable—that is, the preference relation is _complete_ [3, 4], (b) those
which study exclusionary preferences—that is, the set of outcomes is mutually
exclusive (see [5] and the references within), (c) those which are interpreted
over finite traces [6]. In this work, we study the PBP problem for the class
of systems in which the preference model is _incomplete_ , _combinative_ (as
opposed to exclusionary) and is interpreted over _infinite plays_ of the
stochastic system.

The motivation to study incomplete, combinative preferences comes from two
well-known facts that the assumption of completeness is strong and, in many
cases, unrealistic [7], and that combinative preferences are more expressive
than exclusionary preferences [8]. In many control applications, preferences
may need to admit incompleteness because of (a) _Inescapability_ : An agent
has to make decisions under time limits but with incomplete information about
preferences because, for example, it lost communication with the server; and
(b) _Incommensurability_ : Some situations, for instance, comparing the
quality of an apple to that of banana, are fundamentally incomparable since
they lack a standard basis to compare. Similarly, the common preferences in
robotics such as “visiting A is preferred to visiting B” are better
interpreted under a combinative model because a path visiting A may pass
through B, which means that the outcomes (sets of plays of the stochastic
model satisfying a certain property) are not mutually exclusive.

Preference-based planning problems over temporal goals have been well-studied
for deterministic planning given both complete and incomplete preferences (see
[2] for a survey). For preference specified over temporal goals, several works
[9, 10, 11] proposed minimum violation planning methods that decide which low-
priority constraints should be violated in a deterministic system. Mehdipour
_et al._ [12] associate weights with Boolean and temporal operators in signal
temporal logic to specify the importance of satisfying the sub-formula and
priority in the timing of satisfaction. This reduces the PBP problem to that
of maximizing the weighted satisfaction in deterministic dynamical systems.
However, the solutions to the PBP problem for deterministic systems cannot be
applied to stochastic systems. This is because, in stochastic systems, even a
deterministic strategy yields a distribution over outcomes. Hence, to
determine a better strategy, we need a comparison of distributions—a task a
deterministic planner cannot do.

Several works have studied the PBP problem for stochastic systems. Lahijanian
and Kwiatkowska [13] considered the problem of revising a given specification
to improve the probability of satisfaction of the specification. They
formulated the problem as a multi-objective MDP problem that trades off
minimizing the cost of revision and maximizing the probability of satisfying
the revised formula. Li _et al._ [14] solve a preference-based probabilistic
planning problem by reducing it to a multi-objective model checking problem.
However, all these works assume the preference relation to be _complete_. To
the best of our knowledge, [15] is the only work that studies the problem of
probabilistic planning with incomplete preferences. The authors introduce the
notion of the value of preference satisfaction for planning within a pre-
defined finite time duration and developed a mixed-integer linear program to
maximize the satisfaction value for a subset of preference relations.

The aforementioned work studied preference-based quantitative planning. In
comparison, this work focuses on qualitative planning in MDPs with preferences
over a set of outcomes, representable by reachability objectives. We first
introduce new semantics to interpret an incomplete, combinative preference
model over infinite plays of a stochastic system. We observe that
uncertainties in the planning environment combined with infinite plays might
give rise to opportunities to _improve_ the outcomes achieved by the agent.
Thus, analogous to the idea of an _improving flip_ [16], we define the notion
of _improvement_ that compares two prefixes of an infinite play to determine
which one is more preferred, based on their different prospects regarding the
set of possible, achievable objectives. Based on whether a strategy exists to
enforce an improvement with a positive probability or with probability one, we
introduce two solution concepts called _safe and positively improving_ and
_safe and almost-surely improving_ which ensure an improvement can be made
with positive probability and with probability one, respectively. The
synthesis of SPI and SASI strategies is through a construction called
_improvement MDP_ and a reduction to that of computing positive and almost-
sure winning strategies for some reachability objectives of the improvement
MDP. In the case of almost-surely improvement, we also provide an algorithm to
determine the maximum number of improvements achievable given any given state.
The correctness of the proposed algorithms is demonstrated through a robot
motion planning example.

##  II Preliminaries

Notation. Given a finite set $X$, the powerset of $X$ is denoted as $\wp(X)$.
The set of all finite (resp., infinite) ordered sequences of elements from $X$
is denoted by $X^{\ast}$ (resp., $X^{\omega}$). The set of all finite ordered
sequences of length $>0$ is denoted by $X^{+}$. We write $\mathcal{D}(X)$ to
denote the set of probability distributions over $X$. The support of a
distribution $D\in\mathcal{D}(X)$ is denoted by $\mbox{Supp}(D)=\\{x\in X\mid
D(x)>0\\}$.

In this paper, we consider a class of decision-making problems in stochastic
systems modeled as a MDP without the reward function. We then introduce a
preference model over the set of infinite plays in the MDP.

######  Definition 1 (MDP).

An MDP is a tuple $M=\langle S,A,T,\iota\rangle,$ where $S$ and $A$ are finite
state and action sets, $\iota\in S$ is an initial state, and $T:S\times
A\rightarrow\mathcal{D}(S)$ is the transition probability function such that
$T(s,a,s^{\prime})$ is the probability of reaching the state $s^{\prime}\in S$
when action $a\in A$ is chosen at the state $s\in S$.

A _play_ in an MDP $M$ is an infinite sequence of states
$\rho=s_{0}s_{1}\ldots\in S^{\omega}$ such that, for every integer $i\geq 0$,
there exists an action $a\in A$ such that $T(s_{i},a,s_{i+1})>0$. We denote
the set of all plays starting from $s\in S$ in the MDP by
$\mathsf{Plays}(M,s)$ and the set of all plays in $M$ is denoted by
$\mathsf{Plays}(M)=\bigcup_{s\in S}\mathsf{Plays}(M,s)$. The set of states
occurring in a play is given by ${\mathsf{Occ}}(\rho)=\\{s\in S\mid\exists
i\geq 0,s_{i}=s\\}$. A prefix of a play $\rho$ is a finite sub-sequence of
states $\nu=s_{0}s_{1}\ldots s_{k}$, $k\geq 0$, whose the length is
$|\nu|=k+1$. The set of all prefixes of a play $\rho$ is denoted by
$\mathsf{Pref}(\rho)$. The set of all prefixes in $M$ is denoted by
$\mathsf{PrefPlays}(M)=\cup_{\rho\in\mathsf{Plays}(M)}\mathsf{Pref}(\rho)$.
Given a prefix $\nu=s_{0}s_{1}\ldots s_{k}\in\mathsf{PrefPlays}(M)$, the
sequence of states $s_{k+1}s_{k+2}\ldots\in S^{\omega}$ is called a suffix of
$\nu$ if the play $\nu\rho^{\prime}=s_{0}s_{1}\ldots
s_{k}s_{k+1}s_{k+2}\ldots$ is an element of $\mathsf{Plays}(M)$.

In this MDP, we consider reachability objectives for the agent. Given a set
$F\subseteq S$, a reachability objective is characterized by the set
$\mathsf{Reach}(F)=\\{\rho\in\mathsf{Plays}(M)\mid{\mathsf{Occ}}(\rho)\cap
F\neq\emptyset\\}$, which contains all the plays in $M$ starting at the state
$s\in S$ that visit $F$. Any play $\rho\in\mathsf{Plays}(M)$ that satisfies a
reachability objective $\mathsf{Reach}(F)$ has a _good prefix_
$\nu\in\mathsf{Pref}(\rho)$ such that the last state of $\nu$ is in $F$ [17].

A finite-memory (resp., memoryless), non-deterministic strategy in the MDP is
a mapping $\pi:S^{+}\rightarrow\wp(A)$ (resp., $\pi:S\rightarrow\wp(A)$) from
a prefix to a subset of actions that can be taken from that prefix. The set of
all finite-memory, nondeterministic strategies is denoted $\Pi$. Given a
prefix $\nu=s_{0}\ldots s_{k}\in\mathsf{PrefPlays}(M)$, a suffix
$\rho=s_{k+1}s_{k+2}\ldots\in S^{\omega}$ is _consistent_ with $\pi$, if for
all $i\geq 0$, there exists an action $a\in\pi(s_{0}\ldots s_{k}\ldots
s_{k+i})$ such that $T(s_{i},a,s_{i+1})>0$. Given an MDP $M$, a prefix
$\nu\in\mathsf{PrefPlays}(M)$ and a strategy $\pi$, the _cone_ is defined as
the set of consistent suffixes of $\nu$ w.r.t. $\pi$, that is

$\mathsf{Cone}(M,\nu,\pi)=\\{\rho\in S^{\omega}\mid\nu\rho\text{ is consistent
with }\pi\\}.$

Given a prefix ${\nu}\in\mathsf{PrefPlays}(M)$ and a reachability objective
$\mathsf{Reach}(F)$, a (finite-memory/memoryless) strategy
$\pi^{\mathsf{PWin}(F)}$ is said to be positive winning if
$\mathsf{Cone}(M,{\nu},\pi)\cap\mathsf{Reach}(F)\neq\emptyset$. Similarly, a
(finite-memory/memoryless) strategy $\pi^{\mathsf{ASWin}(F)}$ is said to be
almost-sure winning if $\mathsf{Cone}(M,\nu,\pi)\subseteq\mathsf{Reach}(F)$.

The set of _states_ in the MDP $M$, starting from which the agent has an
almost-sure (resp. positive) winning strategy to satisfy a reachability
objective $F\in\mathbb{F}$ is called the almost-sure (resp., positive) winning
region and is denoted by $\mathsf{ASWin}(F)$ (resp., $\mathsf{PWin}(F)$). The
almost-sure and positive winning strategies in the product MDP are known to be
memoryless. The almost-sure winning region and strategies can be synthesized
in polynomial time and linear time, respectively [18].

##  III Preference Model

######  Definition 2.

A preference model is a tuple $\langle U,\succeq\rangle$, where $U$ is a
countable set of outcomes and $\succeq$ is a reflexive and transitive binary
relation on $U$.

Given $u_{1},u_{2}\in U$, we write $u_{1}\succeq u_{2}$ if $u_{1}$ is _weakly
preferred to_ (i.e., is at least as good as) $u_{2}$; and $u_{1}\sim u_{2}$ if
$u_{1}\succeq u_{2}$ and $u_{2}\succeq u_{1}$, that is, $u_{1}$ and $u_{2}$
are _indifferent_. We write $u_{1}\succ u_{2}$ to mean that $u_{1}$ is
_strictly preferred_ to $u_{2}$, i.e., $u_{1}\succeq u_{2}$ and
$u_{2}\not\succeq u_{1}$. We write $u_{1}\nparallel u_{2}$ if $u_{1}$ and
$u_{2}$ are _incomparable_. Since Def. 3 allows outcomes to be incomparable,
it models _incomplete_ preferences [19].

We consider planning objectives specified as preferences over reachability
objectives.

######  Definition 3.

A preference model over reachability objectives in an MDP $M$ is a tuple
$\langle\mathbb{F},\trianglerighteq\rangle$, where
$\mathbb{F}=\\{\mathsf{Reach}(F_{1}),\mathsf{Reach}(F_{2}),\ldots,\mathsf{Reach}(F_{n})\\}$
is a set of reachability objectives such that $F_{1},\ldots,F_{n}$ are subsets
of $S$.

Intuitively, a preference
$\mathsf{Reach}(F_{1})\trianglerighteq\mathsf{Reach}(F_{2})$ means that any
play in $\mathsf{Reach}(F_{1})$ is weakly preferred to any play in
$\mathsf{Reach}(F_{2})$. The strict preference ($\triangleright$),
indifference and incomparability are understood similarly.

The model $\langle\mathbb{F},\trianglerighteq\rangle$ is a combinative
preference model, as opposed to exclusionary one. This is because we do not
assert the exclusivity condition
$\mathsf{Reach}(F_{1})\cap\mathsf{Reach}(F_{2})=\emptyset$. This allows us to
represent a preference such as “Visiting A and B is preferred to visiting A,”
where the less preferred outcome must be satisfied first in order to satisfy
the more preferred outcome. In literature, it is common to study exclusionary
preference models (see [2, 4] and the references within) because of their
simplicity [5]. However, we focus on planning with combinative preferences
since they are more expressive than the exclusionary ones [8]. That is, every
exclusionary preference model can be transformed into a combinative one, but
the opposite is not true.

When a combinative preference model is interpreted over infinite plays, the
agent needs a way to compare the sets of reachability objectives satisfied by
two plays. For instance, in the example from previous paragraph, to compare a
play that visits A and B with a play that visits only A, the agent must
compare the sets $\\{\mathsf{Reach}(F_{B}),\mathsf{Reach}(F_{A})\\}$ with
$\\{\mathsf{Reach}(F_{A})\\}$. Since visiting A and B is more preferred than
visiting A, first play is preferred over the second. However, if the
preference was “visiting A is preferred over visiting B”, then the two plays
would be indifferent since both visit the more preferred objective. In this
case, the less preferred objective of visiting B does not influence the
comparison of the sets. To formalize this notion, we define notion of most-
preferred outcomes.

Given a non-empty subset $\mathbb{X}\subseteq\mathbb{F}$, let
$\mathsf{MP}(\mathbb{X})\triangleq\\{R\in\mathbb{X}\mid\nexists
R^{\prime}\in\mathbb{X}:R^{\prime}\triangleright R\\}$ denote the set of most-
preferred outcomes in $\mathbb{X}$.

######  Definition 4.

Given a preference model $\langle\mathbb{F},\trianglerighteq\rangle$ and a
play $\rho\in\mathsf{Plays}(M)$, the set of most-preferred outcomes satisfied
by $\rho$ is given by
$\mathsf{MP}(\rho)\triangleq\mathsf{MP}(\\{\mathsf{Reach}(F)\in\mathbb{F}\mid\exists\nu\in\mathsf{Pref}(\rho):\nu\text{
is a good prefix for }\mathsf{Reach}(F)\\})$.

By definition, there is no outcome included in $\mathsf{MP}(\rho)$ that is
preferred to any other outcome in $\mathsf{MP}(\rho)$. Thus, we have the
following result.

######  Lemma 1.

For any play $\rho\in\mathsf{Plays}(M)$, every pair of outcomes in
$\mathsf{MP}(\rho)$ is incomparable to each other.

Now, we formally define the interpretation of
$\langle\mathbb{F},\trianglerighteq\rangle$ in terms of the preference
relation it induces on $\mathsf{Plays}(M)$.

######  Definition 5.

Let $\langle\mathsf{Plays}(M),\succeq\rangle$ be the preference model induced
by $\langle\mathbb{F},\trianglerighteq\rangle$. Then, for any
$\rho_{1},\rho_{2}\in\mathsf{Plays}(M)$, we have

  * •

$\rho_{1}\succ\rho_{2}$ if and only if there exist a pair of outcomes
$R\in\mathsf{MP}(\rho_{1})$ and $R^{\prime}\in\mathsf{MP}(\rho_{2})$ such that
$R\triangleright R^{\prime}$, and there does not exist a pair of outcomes
$R\in\mathsf{MP}(\rho_{1})$ and $R^{\prime}\in\mathsf{MP}(\rho_{2})$ such that
$R^{\prime}\triangleright R$.

  * •

$\rho_{1}\sim\rho_{2}$ if and only if
$\mathsf{MP}(\rho_{1})=\mathsf{MP}(\rho_{2})$.

  * •

$\rho_{1}\nparallel\rho_{2}$, otherwise.

##  IV Solution Concept

In preference-based planning, the agent is to choose its next action given a
finite prefix ${\nu}\in\mathsf{PrefPlays}(M)$ in order to satisfy the given
preference relation on a set of outcomes. A naïve approach to this problem is
to follow the strategy to satisfy a most-preferred outcome from the set of
almost-surely achievable outcomes given $\nu$. However, this is not sufficient
as illustrated by the following example.

######  Example 1.

Consider the toy MDP shown in the Fig. 1. To clarify, the exact probabilities
are omitted. The transitions are understood as follows: Given action $a$ at
state $s_{0}$, it is possible to reach both $s_{5}$ and $s_{1}$ with positive
probabilities. Given the three sets
$F_{1}=\\{s_{1},s_{5}\\},F_{2}=\\{s_{2},s_{4}\\}$ and $F_{3}=\\{s_{3}\\}$, let
$\langle\mathbb{F},\trianglerighteq\rangle$ be the preference model such that
$\mathbb{F}=\\{\mathsf{Reach}(F_{1}),\mathsf{Reach}(F_{2}),\mathsf{Reach}(F_{3})\\}$
and $\mathsf{Reach}(F_{2})\triangleright\mathsf{Reach}(F_{1})$ and
$\mathsf{Reach}(F_{3})\triangleright\mathsf{Reach}(F_{1})$. Consider the state
$s_{0}$ at which the agent is to choose its next action. From $s_{0}$, the
agent can visit $F_{1}$ almost surely by choosing the action $a$. It, however,
does not have an almost sure winning strategy to visit either $F_{2}$ or
$F_{3}$, individually. But, by choosing action $b$ at $s_{0}$, the agent will
almost surely visit either $F_{2}$ or $F_{3}$ and, thereby, achieve an outcome
strictly better than $F_{1}$.

$s_{5}$$s_{0}$$s_{4}$$s_{1}$$s_{2}$$s_{3}$$a$$b$$b,c$$c$$a$$a$ Figure 1: Toy
example to illustrate the limitation of almost-sure winning solution concept
for preference-based planning. The states with no outgoing transitions are
sink states.

The example highlights that almost-sure winning solution concept is not
suitable for preference-based planning because it reasons about exactly one
outcome at a time. As a result, the agent cannot reason about opportunities to
achieve a better outcome that may become available to due to stochasticity in
the environment.

In the sequel, we introduce two new solution concepts for probabilistic
planning under incomplete preferences interpreted over infinite plays. Our
solution concepts are based upon the notion of an _improvement_ that
generalizes the idea of _improving flip_ [16] which is defined for
propositional preferences. An improving flip compares two outcomes
representable as propositional logic formulas to determine which is more
preferred. Analogously, an improvement compares two prefixes of a play to
determine which one can yield a more preferred outcome with probability one.

Given a prefix $\nu$, let
$\mathsf{Outcomes}(\nu)=\\{\mathsf{Reach}(F)\in\mathbb{F}\mid\exists\pi\in\Pi,\forall\rho\in\mathsf{Cone}(M,\nu,\pi):\rho\in\mathsf{Reach}(F)\\}$
be the set of outcomes, each of which can be achieved almost-surely under some
strategy. Note that different outcomes may require different policies to
achieve them.

######  Definition 6.

Given a play $\rho\in\mathsf{Plays}(M)$ and two of its prefixes
$\nu,\nu^{\prime}\in\mathsf{Pref}(\rho)$ such that $|\nu^{\prime}|>|\nu|$,
$\nu^{\prime}$ is said to be an _improvement_ of $\nu$ if there exists a pair
of outcomes $R\in\mathsf{MP}(\mathsf{Outcomes}(\nu))$ and
$R^{\prime}\in\mathsf{MP}(\mathsf{Outcomes}(\nu^{\prime}))$ such that
$R^{\prime}\triangleright R$. And, $\nu^{\prime}$ is said to be a _weakening_
of $\nu$ if there exists a pair of outcomes
$R\in\mathsf{MP}(\mathsf{Outcomes}(\nu))$ and
$R^{\prime}\in\mathsf{MP}(\mathsf{Outcomes}(\nu^{\prime}))$ such that
$R\triangleright R^{\prime}$.

Given a prefix $s_{0}s_{1}\ldots s_{k}\in\mathsf{PrefPlays}(M)$, the
transition from $s_{k-1}$ to $s_{k}$ is said to be an _improving transition_
if the prefix $s_{0}s_{1}\ldots s_{k-1}s_{k}$ is an improvement over
$s_{0}s_{1}\ldots s_{k-1}$. A play that contains an improving transition is
called an _improving play_. It is noted that a prefix $\nu^{\prime}$ can
simultaneously be an improvement and a weakening of a prefix $\nu$.

Next, we define the two solution concepts that, while avoiding any weakening,
induce improvements either with positive probability or with probability one.

######  Definition 7 (SPI/SASI Strategy).

Given a prefix $\nu=s_{0}s_{1}\ldots s_{k}\in\mathsf{PrefPlays}(M)$, a
strategy $\pi:S^{+}\rightarrow 2^{A}$ is said to be _safe and positively
(resp., safe and almost-surely) improving_ for $\nu$ if the following
conditions hold:

  1. 1.

(Safety) For all $\rho\in\mathsf{Cone}(M,\nu,\pi)$, the play $\nu\rho$
satisfies that $s_{0}s_{1}\ldots s_{j}$ is not a weakening of
$s_{0}s_{1}\ldots s_{k}$ for any integer $j>k$.

  2. 2.

(Improvement) There exists (resp., for any) $\rho\in\mathsf{Cone}(M,\nu,\pi)$,
the play $\nu\rho$ satisfies the condition that there exists an integer $j>k$
such that $s_{0}s_{1}\ldots s_{j}$ is an improvement over $s_{0}s_{1}\ldots
s_{k}$.

We now state our problem statement.

######  Problem 1.

Given an MDP $M$ and a preference model
$\langle\mathbb{F},\trianglerighteq\rangle$, design an algorithm to synthesize
an SPI and a SASI strategy.

##  V Opportunistic Qualitative Planning with Incomplete Preferences

Our approach to synthesize SPI and SASI strategies distinguishes between
_opportunistic_ states, i.e., the states from which an improvement could be
made, and _non-opportunistic_ states. We now introduce a new model called _an
improvement MDP_ to synthesize the SPI and SASI strategies.

To facilitate the definition, we slightly abuse the notation and let
$\mathsf{MP}(s)\triangleq\mathsf{MP}(\\{\mathsf{Reach}(F)\in\mathbb{F}\mid
s\in\mathsf{ASWin}(F)\\})$ be the set of outcomes almost-surely achievable
from state $s$ in $M$.

######  Definition 8 (Improvement MDP).

Given an MDP $M=\langle S,A,T,s_{0}\rangle$ and a preference model
$\langle\mathbb{F},\trianglerighteq\rangle$, an _improvement MDP_ is the
tuple,

$\mathcal{M}=\langle V,A,\Delta,v_{0},\mathcal{F}\rangle,$

where $V=S\times\\{0,1\\}$ is the set of states, $A$ is the same set of
actions as $M$, $v_{0}=(s_{0},0)$ is the initial state, and
$\mathcal{F}=\\{(s,1)\mid s\in S\\}$ is a set of final states. The transition
function $\Delta:V\times A\rightarrow\mathcal{D}(V)$ is defined as follows:
For any states $v=(s,m),v^{\prime}=(s^{\prime},m^{\prime})\in V$ and for any
action $a\in A$, $\Delta(v,a,v^{\prime})>0$ holds if and only if the following
conditions hold:

  1. 1.

$T(s,a,s^{\prime})>0$.

  2. 2.

(Safety) For all pairs of outcomes $R\in\mathsf{MP}(s)$ and
$R^{\prime}\in\mathsf{MP}(s^{\prime})$, we have $R\not\triangleright
R^{\prime}$.

  3. 3.

(Improvement) If there exists a pair $R\in\mathsf{MP}(s)$ and
$R^{\prime}\in\mathsf{MP}(s^{\prime})$ such that $R^{\prime}\triangleright R$,
then $m^{\prime}=1$ else $m^{\prime}=0$.

Every play $\rho=s_{0}s_{1}\ldots\in\mathsf{Plays}(M)$ induces a play
$\varrho=v_{0}v_{1}\ldots$ in $\mathcal{M}$ such that for all $i=0,1,\ldots$,
$v_{i}=(s_{i},m_{i})$ where $m_{i}\in\\{0,1\\}$ represents a memory element
that captures whether the transition from $s_{i-1}$ to $s_{i}$ is improving.
The following proposition highlights important features of the improvement
MDP. Before that we note the following fact to prove Proposition 1.

######  Lemma 2.

For every prefix $\nu=s_{0}s_{1}\ldots s_{k}\in\mathsf{PrefPlays}(M)$, it
holds that $\mathsf{Outcomes}(\nu)=\mathsf{Outcomes}(s_{k})$ and thus
$\mathsf{MP}(\mathsf{Outcomes}(\nu))=\mathsf{MP}(\mathsf{Outcomes}(s_{k}))$.

The proof follows from the fact that memoryless strategies are sufficient to
ensure the satisfaction of reachability objectives in MDPs [20]. In other
words, if an outcome is almost-surely achievable given a prefix
$\nu=s_{0}s_{1}\ldots s_{k}$, then it is almost-surely achievable given
$s_{k}$.

For convenience, we will write
$\mathsf{MP}(s)=\mathsf{MP}(\mathsf{Outcomes}(s))$ to denote the set of most
preferred outcomes satsfiable/achievable with some strategy from a state $s\in
S$.

######  Proposition 1.

For any play $\varrho=v_{0}v_{1}\ldots\in\mathsf{Plays}(\mathcal{M})$ such
that $v_{i}=(s_{i},m_{i})$ for all $i=0,1\ldots$, the following statements
hold.

  1. 1.

(Safety). For every prefix $v_{0}v_{1}\ldots
v_{j}\in\mathsf{PrefPlays}(\varrho)$, $s_{0}s_{1}\ldots s_{j}$ is not a
weakening of $s_{0}s_{1}\ldots s_{i}$ for any $0\leq i<j$.

  2. 2.

(Improvement). For every integer $k>0$ such that $s_{k}\in\mathcal{F}$, the
prefix $s_{0}s_{1}\ldots s_{k}$ is an improvement of $s_{0}s_{1}\ldots
s_{k-1}$.

###### Proof (Sketch).

For statement (1) to hold, it must be the case that $R\not\triangleright
R^{\prime}$ holds for all pairs of outcomes $R\in\mathsf{MP}(s_{i})$ and
$R^{\prime}\in\mathsf{MP}(s_{j})$. This is true because of Lma. 2 and the fact
that every transition from $v_{i}$ to $v_{i+1}$, $j<i\leq k$, that violates
the condition is disabled by Def. 8.

To see why statement (2) holds, consider an integer $k>0$ such that
$v_{k}\in\mathcal{F}$. Then, by construction, there exists a pair
$R\in\mathsf{MP}(s_{k-1})$ and $R^{\prime}\in\mathsf{MP}(s_{k})$ such that
$R^{\prime}\triangleright R$. ∎

In words, the improvement MDP guarantees by construction that no play in
$\mathsf{Plays}(\mathcal{M})$ violates the safety condition of Def. 7.
Moreover, it helps identify the opportunistic states as the ones that have an
outgoing transition into $\mathcal{F}$.

######  Corollary 1.

A play $\varrho\in\mathsf{Plays}(\mathcal{M})$ is improving if and only if
${\mathsf{Occ}}(\varrho)\cap\mathcal{F}\neq\emptyset$.

As a result, the problem of determining whether an improvement is possible
from a state $v\in V$ reduces to checking whether a state in $\mathcal{F}$ can
be reached from $v$ with a positive probability (in case of SPI strategy) or
with probability one (in case of SASI strategy).

######  Theorem 1.

The following statements hold:

  1. 1.

The positive winning strategy $\pi^{\mathsf{PWin}(\mathcal{F})}$ in
$\mathcal{M}$ to visit $\mathcal{F}$ is an SPI strategy.

  2. 2.

The almost-sure winning strategy $\pi^{\mathsf{ASWin}(\mathcal{F})}$ in
$\mathcal{M}$ to visit $\mathcal{F}$ is a SASI strategy.

The proof follows from the fact that there exists a (resp., every) play
$\rho\in\mathsf{Cone}(\mathcal{M},v_{0},\pi)$ induced by any positive (resp.,
almost-sure) winning strategy $\pi$ visits $\mathcal{F}$ with positive
probability (resp., probability one) [21]. Therefore, Thm. 1 establishes that
by following $\pi^{\mathsf{PWin}(\mathcal{F})}$ (resp.,
$\pi^{\mathsf{ASWin}(\mathcal{F})}$), the agent is ensured to make an
improvement with a positive probability (resp., with probability one).

Algorithm 1 Level set for constructing SASI strategy

1:Improvement MDP, $\mathcal{M}=\langle\rangle$.

2:Level set, $\mathcal{W}$.

3:$i\leftarrow 0$

4:$R_{i}\leftarrow\mathcal{F}$

5:while $R_{i}$ is not empty do

6: $W_{i+1}\leftarrow\mathsf{ASWin}(R_{i})$

7: $R_{i+1}\leftarrow\\{(s,1)\in\mathcal{F}\mid(s,0)\in W_{i+1}\\}$

8: if $i=0$ then

9: Add $V\setminus W_{i+1}$ to level $0$ in $\mathcal{W}$.

10: Add $W_{i+1}$ to level $i+1$ in $\mathcal{W}$.

11: $i\leftarrow i+1$

12:return $\mathcal{W}$

The SPI and SASI strategies from Thm. 1 guarantee that at least one
improvement will occur with positive probability or with probability one.
Next, we present Alg. 1, using which we can determine the maximum number of
improvements that can _almost-surely_ be made from a given state in
$\mathcal{M}$. The algorithm to determine the maximum number of improvements
possible from a given state in $\mathcal{M}$ with _a positive probability_ and
its properties are similar to Alg. 1.

First, note the following properties of the improvement MDP which follow from
the construction of MDP.

######  Proposition 2.

Consider two states $(s,0),(s,1)\in V$, it holds that for any action $a\in A$,
we have $\mbox{Supp}(\Delta((s,0),a))=\mbox{Supp}(\Delta((s,1),a))$.

The proof is straightforward because given $(s,0),(s,1)$, for any action $a\in
A$, if a transition from $s$ to $s^{\prime}$ given $a$ is improving, then
$\Delta((s,0),a,(s^{\prime},1))>0$ and $\Delta((s,1),a,(s^{\prime},1))>0$.
Else, $\Delta((s,0),a,(s^{\prime},0))>0$ and
$\Delta((s,1),a,(s^{\prime},0))>0$.

######  Corollary 2.

The final states $\mathcal{F}$ can be visited _again_ from a state $(s,1)\in
V$ with a positive probability (resp., with probability one) if and only if
$\mathcal{F}$ can be visited from $(s,0)$ with a positive probability (resp.,
with probability one).

###### Proof.

Let $\pi$ be a positive winning strategy to visit $\mathcal{F}$ from $(s,0)$.
Let $Y=\mbox{Supp}(\Delta((s,0),a))$ for some $a\in\pi((s,0))$. By the
property of a positive winning strategy, a state in $\mathcal{F}$ is reached
with positive probability by following $\pi$ from any state in $Y$. By
Proposition 2, $Y=\mbox{Supp}(\Delta((s,1),a))$. Therefore, by choosing $a$ at
$(s,1)$ and then following $\pi$, a state in $\mathcal{F}$ is visited with
positive probability from $(s,1)$. The proof for almost-sure winning is
similar. ∎

Intuitively, Alg. 1 constructs a set $\mathcal{W}$ of level sets such that
from any state that appears at $k$-th level in $\mathcal{W}$, at least $k$
visits to $\mathcal{F}$ are guaranteed and, thereby, at least $k$ improvements
can be made.

For this purpose, it iteratively computes the almost-sure winning region to
visit the states in $R_{i}\subseteq\mathcal{F}$, from which $\mathcal{F}$ can
be visited at least $i$ times. We denote by $W_{i}$ the $i$-th level set. The
level-$0$ of $\mathcal{W}$ contains the states
$V\setminus\mathsf{ASWin}(\mathcal{F})$ from which $\mathcal{F}$ cannot be
visited again with probability one. That is, $0$-visits to $\mathcal{F}$ are
guaranteed from any state in level-$0$ of $\mathcal{W}$. Every state in
level-$1$ of $\mathcal{W}$ is almost-surely winning to visit $\mathcal{F}$.
Hence, at least one visit to $\mathcal{F}$ is guaranteed. Now, consider the
subset $R_{1}=\\{(s,1)\in\mathcal{F}\mid(s,0)\in W_{1}\\}$ of final states
$\mathcal{F}$. By Corollary 2, because $(s,0)\in
W_{1}=\mathsf{ASWin}(\mathcal{F})$, there exists a strategy from every state
in $R_{1}$ to visit $\mathcal{F}$ with probability one. Therefore, from any
state $(s,0)\in W_{2}=\mathsf{ASWin}(R_{1})$ at least two improvements are
guaranteed—first, when visiting $(s^{\prime},1)\in R_{1}$ and, second, when
visiting $R_{0}=\mathcal{F}$ by following the almost-sure winning strategy at
$(s^{\prime},1)$. Repeating a similar argument, it follows that at least
$k$-visits are guaranteed almost-surely from states at $k$-th level in
$\mathcal{W}$.

The largest integer $k\geq 0$ such that the state $(s,0)\in V$ appears at
$k$-th level of $\mathcal{W}$ is called the rank of the states $(s,0)$ and
$(s,1)$, denoted as
$\mathop{\mathrm{rank}}(s,0)=\mathop{\mathrm{rank}}(s,1)=k$.

######  Proposition 3.

From any state $v=(s,m)\in V$, $m\in\\{0,1\\}$, there exists a strategy to
visit $\mathcal{F}$ at least $\mathop{\mathrm{rank}}(v)$-many times.

###### Proof.

We prove this by constructing the strategy that achieves
$\mathop{\mathrm{rank}}(v)$ improvements: First, if
$\mathop{\mathrm{rank}}(v)=k$, then by construction it is in
$\mathsf{ASWin}(R_{k-1})$. Following the almost-sure winning strategy a state
in $R_{k-1}$ can be reached with probability one and thus the first
improvement is made. Upon reaching a state, say $(s^{\prime},1)$, in
$R_{k-1}$, one identify $(s^{\prime},0)\in W_{k-1}$. Because
$W_{k-1}=\mathsf{ASWin}(R_{k-2})$, an almost-sure winning strategy exists to
reach $R_{k-2}$ and hence the second improvement. Repeating the similar steps,
eventually $R_{0}$ will be reached after the $k$-th improvement. ∎

######  Corollary 3.

From any state $v=(s,m)\in V$ at most $\mathop{\mathrm{rank}}(v)$-many visits
to $\mathcal{F}$ are almost-surely guaranteed.

###### Proof (Sketch).

By contradiction. Let $\mathop{\mathrm{rank}}(v)=k$. Suppose that $k+1$ visits
are possible from $v$. Then, following the argument in the proof of
Proposition 3, on making $k$-th visit to $\mathcal{F}$, the resulting state
must still be in $W_{1}$ so that $k+1$-th visit to $\mathcal{F}$ could be
made. By definition, this means that the state from which $k$-th visit is made
is also contained in $W_{2}$. Using a similar argument repeatedly, it must be
the case that $v\in W_{k+1}$, which means that
$\mathop{\mathrm{rank}}(v)=k+1$—a contradiction. ∎

Complexity. Alg. 1 runs in polynomial time with respect to the size of
$\mathcal{M}$ since the while loop can run no more than $|V|$ times and the
complexity of $\mathsf{ASWin}$ is quadratic in the size of $\mathcal{M}$ [18].

##  VI Example: Robot Motion Planning

We illustrate our approach using a motion planning problem for a robot in a
$5\times 5$ gridworld as shown in Figure 2. The gridworld environment consists
of seven regions: $\\{A:(0,0),B:(2,0),C:(4,0),D:(2,4),E:(4,4),F:(1,2)\\}$ from
which the robot must pick up an item. There is a charging station at cell
$(4,2)$. Each cell denoted using the convention (row, col). The robot can
choose among four actions N, S, E, W to deterministically move north, east,
south and west by one cell. The actions E, W are disabled in the cells $(4,2)$
and $(2,2)$. The cells $(1,1),(3,1),(1,3),(3,3)$ are slippery, that is,
whenever the robot moves into any of these cells, say $(1,1)$, it may non-
deterministically end up in either the same cell $(1,1)$, or the cell north to
it $(2,1)$, or south to it $(0,1)$. In any cell, if applying an action results
in a cell that is outside the gridworld or contains an obstacle, the robot
returns to the same cell. The robot has limited battery of $5$ units, which it
may recharge by visiting the charging station. The robot spends $1$ unit to
execute each action.

At the beginning, only the items at $A,B$ and $C$ are available for pickup.
That is, if the robot visits the charging station or regions $D,E,F$, then
neither its battery will be recharged nor will it be able to pickup items
$D,E,F$. When the robot picks up an item at $A$ or $B$, the charging station
and the items at $D,E$ become available. When the robot picks up an item at
$C$, the charging station and the items at $E,F$ become available. The
following preference about picking up the items is given to the robot:
$D\triangleright A,E\triangleright A,D\triangleright B,E\triangleright
B,E\triangleright C,F\triangleright C$. By default, picking up any item is
preferred to not picking up any item.

Figure 2: A gridworld example in which the black arrows with no-entry symbol
denotes the disabled actions from that state and green arrows show the random
outcomes on entering the cell.

Note that the preference model given to the robot is incomplete as well as
combinative. It is incomplete because picking up items $A,B,C$ are mutually
incomparable outcomes. Similarly, picking up items $D,E,F$ are mutually
incomparable. It is combinative because, for instance, any play in which robot
picks up an item from $D$ or $E$ is considered preferred to a play in which
robot only picks an item from $A$ or $B$, even though to pick an item from $D$
or $E$ an item from $A$ or $B$ must be picked first.

We implemented the example in Python 3.9 on a Windows 10 machine with a core
i$7$, 2.80GHz CPU and a 32GB memory. We discuss few noteworthy observations
next. The MDP for this case has $3600$ states and $18496$ transitions, whereas
the improvement MDP has $7200$ states and $35524$ transitions.

Consider the initial state $s_{0}=(2,2,8,(1,1,1,0,0,0,0))$ in which the robot
is at cell $(2,2)$ with $8$ units of battery. The fourth component of the
state denotes which items are available for pickup with the last element of
the tuple reserved for availability of the charging station. In this state,
the robot does not have an almost-sure winning strategy to visit any of $A,B$
or $C$. This is because to visit, say $A$, the robot must visit the slippery
cell $(1,1)$. But whenever $(1,1)$ is visited, the robot may reach $(2,1)$
with a positive probability. Hence,
$\mathsf{MP}(\mathsf{Outcomes}(s_{0}))=\emptyset$.

When under the SASI concept, the rank of the state $(s_{0},1)$ is $2$
indicating that two improvements are almost-surely guaranteed. This is
understood by observing the SASI strategy which chooses action N at
$(s_{0},0)$ to reach $s_{1}=(3,2,7,(1,1,1,0,0,0,0))$. At $(s_{1},0)$ the
strategy selects W and visits either $B$ or $C$ with probability one. Since a
pickup from $B$ and $C$ are incomparable, both actions N and S are deemed
valid under SASI strategy at $(3,1,6,(1,1,1,0,0,0,0))$. On visiting either $B$
or $C$, the SASI strategy follows the almost-sure winning strategy to visit
either $D$ or $E$ to make a second improvement. Since visiting the cell
$(3,3)$ may result in returning back to the cell $(3,2)$ with a positive
probability, the robot can recharge itself until a successful visit to $E$ or
$D$ is made.

The SASI strategy at $(s_{0},0)$ does not select S because a second
improvement cannot be guaranteed with probability one after visiting $A$ since
the robot may remain at the cell $(0,1)$ until its battery runs out. However,
we observe that the SPI strategy at $(s_{0},0)$ allows selection of both
actions N, S at $(s_{0},0)$ since in both cases two improvements are possible
with positive probability.

We conclude with Table I, which shows the number of states from which the
robot has an SPI and SASI strategies to make at least $1$ or $2$ improvements,
since the maximum number of improvements possible under given preference model
is $2$. It is noted that the states from which a SASI strategy exists are a
subset of states from which a SPI strategy exists.

| SASI | SPI
---|---|---
Rank-$1$ | 768 | 926
Rank-$2$ | 98 | 167
TABLE I: Number of states from which the robot has SPI and SASI strategies to
make at least $1$ or at least $2$ improvements.

##  VII Conclusion

In this paper, we introduced two solution concepts, namely SPI and SASI to
solve a preference-based planning problem given a combinative, incomplete
preference model over infinite plays of a stochastic system. In the
improvement MDP, we showed that the synthesis of SPI and SASI strategies
reduces to that of computing positive and almost-sure winning strategies.
Finally, we designed an algorithm using which we can synthesize a strategy
that induces the maximum number of improvements under the SASI concept.
Building on this work, there are a number of future directions: 1) it is
possible to consider a preference over temporal objectives that encompass more
general properties such as safety, recurrence, and liveness; 2) it remains
open as how to connect qualitative reasoning with quantitative planning with
such preference specifications.

## References

  * [1] R. Hastie and R. M. Dawes, _Rational choice in an uncertain world: The psychology of judgment and decision making_. Sage, 2010.
  * [2] J. A. Baier and S. A. McIlraith, “Planning with Preferences,” _AI Magazine_ , vol. 29, no. 4, p. 25, 2008.
  * [3] T. C. Son and E. Pontelli, “Planning with preferences using logic programming,” _Theory and Practice of Logic Programming_ , vol. 6, no. 5, pp. 559–607, 2006.
  * [4] M. Bienvenu, C. Fritz, and S. A. McIlraith, “Specifying and computing preferred plans,” _Artificial Intelligence_ , vol. 175, no. 7-8, pp. 1308–1345, 2011.
  * [5] S. O. Hansson and T. Grüne-Yanoff, “Preferences”, the stanford encyclopedia of philosophy (spring 2022 edition).” [Online]. Available: https://plato.stanford.edu/archives/spr2022/entries/preferences/
  * [6] H. Rahmani, A. N. Kulkarni, and J. Fu, “Probabilistic planning with partially ordered preferences over temporal goals,” _arXiv preprint arXiv:2209.12267_ , 2022.
  * [7] R. J. Aumann, “Utility theory without the completeness axiom,” _Econometrica: Journal of the Econometric Society_ , pp. 445–462, 1962.
  * [8] S. O. Hansson, _The structure of values and norms_. Cambridge University Press, 2001.
  * [9] J. Tumova, G. C. Hall, S. Karaman, E. Frazzoli, and D. Rus, “Least-violating control strategy synthesis with safety rules,” in _Proceedings of the 16th international conference on Hybrid systems: computation and control_. ACM, 2013, pp. 1–10.
  * [10] T. Wongpiromsarn, K. Slutsky, E. Frazzoli, and U. Topcu, “Minimum-violation planning for autonomous systems: Theoretical and practical considerations,” in _2021 American Control Conference_ , 2021, submitted.
  * [11] H. Rahmani and J. M. O’Kane, “What to do when you can’t do it all: Temporal logic planning with soft temporal logic constraints,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 6619–6626.
  * [12] N. Mehdipour, C.-I. Vasile, and C. Belta, “Specifying User Preferences Using Weighted Signal Temporal Logic,” _IEEE Control Systems Letters_ , vol. 5, no. 6, pp. 2006–2011, Dec. 2021.
  * [13] M. Lahijanian and M. Kwiatkowska, “Specification revision for Markov decision processes with optimal trade-off,” in _Proc. 55th Conference on Decision and Control (CDC’16)_ , 2016, pp. 7411–7418.
  * [14] M. Li, A. Turrini, E. M. Hahn, Z. She, and L. Zhang, “Probabilistic preference planning problem for markov decision processes,” _IEEE transactions on software engineering_ , 2020.
  * [15] J. Fu, “Probabilistic planning with preferences over temporal goals,” in _2021 American Control Conference (ACC)_. IEEE, 2021, pp. 4854–4859.
  * [16] G. R. Santhanam, S. Basu, and V. Honavar, “Representing and Reasoning with Qualitative Preferences: Tools and Applications,” _Synthesis Lectures on Artificial Intelligence and Machine Learning_ , vol. 10, no. 1, pp. 1–154, Jan. 2016, zSCC: 0000006 Publisher: Morgan & Claypool Publishers. [Online]. Available: https://www.morganclaypool.com/doi/10.2200/S00689ED1V01Y201512AIM031
  * [17] O. Kupferman and M. Y. Vardi, “Model checking of safety properties,” _Formal methods in system design_ , vol. 19, no. 3, pp. 291–314, 2001.
  * [18] C. Baier and J.-P. Katoen, _Principles of model checking_. MIT press, 2008.
  * [19] D. Bouyssou, D. Dubois, and M. Pirlot, _Concepts & Methods of Decision-Making_. John Wiley & Sons Inc., 2009.
  * [20] L. de Alfaro and R. Majumdar, “Quantitative solution of omega-regular games,” in _Proceedings of the thirty-third annual ACM symposium on Theory of computing_ , 2001, pp. 675–683.
  * [21] K. Chatterjee and T. A. Henzinger, “A survey of stochastic $\omega$-regular games,” _Journal of Computer and System Sciences_ , vol. 78, no. 2, pp. 394–413, 2012.

  *[MDP]: Markov Decision Process
  *[SPI]: Safe and Positive Improving
  *[SASI]: Safe and Almost-Sure Improving
  *[ MDP]: Markov Decision Process