sensor’s field of view, making brute-force search infeasible. A human with
access to the same map and prior knowledge of object locations provides the
robot with a natural language description. For example, given the map in Fig.
7.1, one could say _the red car is behind Jeffrey’s House, around Rene’s
House._ The language is assumed to mention some of the target objects and
their spatial relationships to some of the known landmarks, yet there is no
assumption about how such information is described. To be successful, the
robot must incorporate information from spatial language to efficiently search
for the target object.

This problem can be formulated as the multi-object search (MOS) task Wandzel .
(2019), modeled as an OO-POMDP. The state $s_{i}=(x_{i},y_{i})$ is the
location for target $i$, $1\leq i\leq N$. The robot state
$s_{r}=(x,y,\theta,\mathcal{F})$ consists of the robot’s pose $(x,y,\theta)$
and a set of found targets $\mathcal{F}\subseteq\\{1,\cdots,N\\}$. There are
three types of actions: Move changes the robot pose (possibly stochastically);
Look processes sensory information within the current field-of-view; Find($i$)
marks object $i$ as found. In our implementation of MOS, a Look action is
automatically taken following every Move. Upon taking Find, the robot receives
reward $R_{\text{max}}\gg 0$ if an unfound object is within the field of view,
and $R_{\text{min}}\ll 0$ otherwise. Other actions receive
$R_{\text{step}}<0$. The desired policy accounts for the belief over target
locations while efficiently exploring the map.

Note that in our evaluation, we use a synthetic detector that returns
observations conditioned on the ground truth object locations for belief
update during execution. Our POMDP-based framework can easily make use of a
realistic observation model instead, for example, based on processing visual
data Xiao . (2019); Monsó . (2012). Training vision-based object detectors is
outside the scope of this chapter. Our focus is on spatial language
understanding for planning object search strategies.

In the next section, we introduce SLOOP, with a particular focus on the
observation space and observation model. Then, to apply SLOOP to our problem
setting, we describe our implementation of the spatial language observation
model on 2D city maps, which includes a convolutional network model for FoR
prediction.

Figure 7.2: We consider a spatial language description as an observation
$o_{\mathcal{R}}$, which is a set of $(f,r,\gamma)$ tuples, obtained through
parsing the input language. We propose an observation model that incorporates
the spatial information in $o_{\mathcal{R}}$ into the robot’s belief about
target locations, which benefits subsequent object search performance.

### 7.4 Spatial Language Object-Oriented POMDP (SLOOP)

SLOOP augments an OO-POMDP defined over a given map $\mathcal{M}$ with a
spatial language observation space and a spatial language observation model.
The map $\mathcal{M}$ consists of a discrete set of locations and contains
landmark information (e.g. landmark’s name, location and geometry), such that
$N$ objects exist on the map at possibly unknown locations. Thus, the state
space can be factored into a set of $N$ objects plus the given map
$\mathcal{M}$ and robot state $s=(s_{1},\cdots,s_{N},s_{r},\mathcal{M})$.
SLOOP does not augment the action space, thus the action space of the
underlying OO-POMDP is left unchanged. Because the transition and reward
functions are, by definition, independent of observations, they are also kept
unchanged in SLOOP. Next, we introduce spatial language observations.

#### 7.4.1 Spatial Language Observation

According to Landau Jackendoff (1993), the standard linguistic representation
of an object’s place requires three elements: the object to be located
(_figure_), the reference object (_ground_), and their relationship (_spatial
relation_). We follow this convention and represent spatial information from a
given natural language description in terms of atomic propositions, each
represented as a tuple of the form $(f,r,\gamma)$, where $f$ is the _figure_ ,
$r$ is the _spatial relation_ and $\gamma$ is the _ground_. In our case, $f$
refers to a target object, $\gamma$ refers to a landmark on the map, and $r$
is a predicate that is true if the locations of $f$ and $\gamma$ satisfy the
semantics of the spatial relation. As an example, given spatial language _the
red Honda is behind Belmont, near Hi-Lo_ , two tuples of this form can be
extracted (parentheses indicate role): {(RedCar($f$), behind($r$),
Belmont($\gamma$)), (RedCar($f$), near($r$), HiLo($\gamma$))}.

We define a _spatial language observation_ as a set of $(f,r,\gamma)$ tuples
extracted from a given spatial language. We define the spatial language
observation space to be the space of all possible tuples of such form for a
given map, objects, and a set of spatial relations.

#### 7.4.2 Spatial Language Observation Model

We denote a spatial language observation as $o_{\mathcal{R}}$. Our goal now is
to derive $\Pr(o_{\mathcal{R}}|s^{\prime},a)$, the observation model for
spatial language. We can split $o_{\mathcal{R}}$ into subsets,
$o_{\mathcal{R}}=\cup_{i=1}^{N}o_{\mathcal{R}_{i}}$, where each
$o_{\mathcal{R}_{i}}=\cup_{k=1}^{L}(f_{i},r_{k},\gamma_{k})$,
$L=|o_{\mathcal{R}_{i}}|$ is the set of tuples where the figure is target
object $i$. Since the human describes the target objects with respect to
landmarks on the map, the spatial language is conditionally independent from
the robot state and action given map $\mathcal{M}$ and the target locations
$s_{1},\cdots,s_{N}$. Therefore,

$\displaystyle\Pr(o_{\mathcal{R}}|s^{\prime},a)$
$\displaystyle=\Pr(\cup_{i=1}^{N}o_{\mathcal{R}_{i}}|s_{1}^{\prime},\cdots,s_{N}^{\prime},\mathcal{M})$
(7.1)

We make a simplifying assumption that $o_{\mathcal{R}_{i}}$ is conditionally
independent of all other $o_{\mathcal{R}_{j}}$ and $s_{j}^{\prime}$ ($j\neq
i$) given $s_{i}^{\prime}$ and map $\mathcal{M}$. We make this assumption
because the human observer is capable of producing a language
$o_{\mathcal{R}_{i}}$ to describe target $i$ given just the target location
$s_{i}$ and the map $\mathcal{M}$. Thus,

$\displaystyle\Pr(\cup_{i=1}^{N}o_{\mathcal{R}_{i}}|s_{1}^{\prime},\cdots,s_{N}^{\prime},\mathcal{M})=\prod_{i=1}^{N}\Pr(o_{\mathcal{R}_{i}}|s_{i}^{\prime},\mathcal{M})$
(7.2)

where $\Pr(o_{\mathcal{R}_{i}}|s_{i}^{\prime},\mathcal{M})$ models the spatial
information in the language description for object $i$. For each spatial
relation $r_{j}$ in $o_{\mathcal{R}_{i}}$ whose interpretation depends on the
FoR imposed by the human observer (e.g. _behind_), we introduce a
corresponding random variable $\Psi_{j}$ denoting the FoR vector that
distributes according to the indicator function
$\Pr(\Psi_{j}=\psi_{j})=\mathds{1}(\psi_{j}=\psi_{j}^{*})$, where
$\psi_{j}^{*}$ is the one imposed by the human, unknown to the robot. Then,
our model for $\Pr(o_{\mathcal{R}_{i}}|s_{i}^{\prime},\mathcal{M})$ becomes:

$\displaystyle\Pr(o_{\mathcal{R}_{i}}|s_{i}^{\prime},\mathcal{M})=\prod_{j=1}^{L}\Pr(r_{j}|\gamma_{j},\psi_{j}^{*},f_{i},s_{i}^{\prime},\mathcal{M})$
(7.3)

The step-by-step derivation can be found in the supplementary material. It is
straightforward to extend this model as a mixture model
$\Pr(o_{\mathcal{R}_{i}}|s_{i}^{\prime},\mathcal{M})=\sum_{k=1}^{m}w_{k}\Pr_{k}(o_{\mathcal{R}_{i}}|s_{i}^{\prime},\mathcal{M})$,
$\sum_{k=1}^{m}w_{k}=1$, where multiple interpretations of the spatial
language are used to form separate distributions then combined into a
weighted-sum. This effectively smooths the distribution under individual
interpretations, which improves object search performance in our evaluation
(Figure 7.7),

However, to proceed modeling
$\Pr(r_{j}|\gamma_{j},\psi_{j}^{*},f_{i},s_{i}^{\prime},\mathcal{M})$ in Eq.
(7.3), we notice that it depends on the unknown FoR $\psi_{j}^{*}$. Therefore,
we consider two subproblems instead: The approximation of $\psi_{j}^{*}$ by a
predicted value $\hat{\psi}$ and the modeling of
$\Pr(r_{j}|\gamma_{j},\hat{\psi_{j}},f_{i},s_{i}^{\prime},\mathcal{M})$. Next,
we describe our approach to these two subproblems for object search in city-
scale environments.

#### 7.4.3 Learning to Predict Latent Frame of Reference

Figure 7.3: Frame of Reference Prediction Model Design. In this example taken
from our dataset, the model is predicting the frame of reference for the
preposition _front_. The grayscale image is rendered with color ranging from
blue (black), green (gray) to yellow (white). Green highlights the referenced
landmark, dark blue the streets, blue the surrounding buildings, and yellow
the background.

Here we describe our approach to predict $\psi_{j}^{*}$ corresponding to a
given $(f_{i},r_{j},\gamma_{j})$ tuple, which is critical for correct
resolution of spatial relations. Taking inspiration from the ice cream truck
example where the tourist can infer a potential FoR by looking at the 2D map
of the park, we train a model that predicts the human observer’s imposed FoR
based on the environment context embedded in the map.

We define an FoR in a 2D map as a single vector $\psi_{j}=(x,y,\theta)$
located at $(x,y)$ at an angle $\theta$ with respect to the $+x$ axis of the
map. We use the center-of-mass of the ground as the origin $(x,y)$. We make
this approximation since our data collection shows that when looking at a 2D
map, human observers tend to consider the landmark as a whole without
decomposing it into parts. Therefore, the FoR prediction problem becomes a
regression problem of predicting the angle $\theta$ given a representation of
the environment context.

We design a convolutional neural network, which takes as input a grayscale
image representation of the environment context where the ground in the
spatial relation is highlighted. Surrounding landmarks are also highlighted
with different brightness for streets and buildings (Figure 7.3). The image is
shifted to be egocentric with respect to the referenced landmark, and cropped
into a 28$\times$28 pixel image. The intuition is to have the model focus on
immediate surroundings, as landmarks that are far away tend not to contribute
to inferring the referenced landmark’s properties. The model consists of two
standard convolution modules followed by three fully connected layers. These
convolution modules extract an 800-dimension feature vector, feeding into the
fully connected layers, which eventually output a single value for the FoR
angle. We name this model EGO-CTX for egocentric shift of the contextual
representation.

Regarding the loss function, a direct comparison with the labeled FoR angle is
not desirable. For example, suppose the labeled angle is $0$ (in radians).
Then, a predicted angle of $0.5$ is qualitatively the same as another
predicted angle of $-0.5$ or $2\pi-0.5$. For this reason, we apply the
following treatment to the difference between predicted angle $\theta$ and the
labeled angle $\theta^{*}$. Here, both $\theta$ and $\theta^{*}$ have been
reduced to be between $0$ to $2\pi$:

$\displaystyle\ell(\theta,\theta^{*})=\begin{cases}2\pi-\lvert\theta-\theta^{*}\rvert,&\text{if}\
\lvert\theta-\theta^{*}\rvert>\pi,\\\
\lvert\theta-\theta^{*}\rvert,&\text{otherwise}\\\ \end{cases}$ (7.4)

This ensures that the angular deviation used to compute the loss ranges
between $0$ to $\pi$. The learning objective is to reduce such deviation to
zero. To this end, we minimize the mean-squared error loss
$L(\bm{\theta},\bm{\theta}^{*})=\frac{1}{N}\sum_{i=1}^{N}\left(\ell(\theta_{i},\theta^{*}_{i})\right)^{2}$,
where $\bm{\theta},\bm{\theta}^{*}$ are predicted and annotated angles in the
training set of size $N$. This objective gives greater penalty to angular
deviations farther away from zero.

In our experiments, we combine the data by antonyms and train two models for
each baseline: a front model used to predict FoRs for _front_ and _behind_ ,
and a left model used for _left_ and _right_ 111We do not train a single model
for all four prepositions since _left_ and _right_ often also suggest an
_absolute_ FoR used by the language provider when looking at 2D maps, while
_front_ and _behind_ typically suggest a _relative_ FoR.. We augment the
training data by random rotations for front but not for left.222Again, because
_left_ and _right_ may imply either absolute or relative FoR. We use the Adam
optimizer Kingma Ba (2015) to update the network weights with a fixed learning
rate of $1\times 10^{-5}$. Early stopping based on validation set loss is used
with a patience of 20 epochs Prechelt (1998).

#### 7.4.4 Modeling Spatial Relations

We model
$\Pr(r_{j}|\gamma_{j},\hat{\psi_{j}},f_{i},s_{i}^{\prime},\mathcal{M})$ as a
Gaussian following prior work and evidence from animal behavior Fasola Mataric
(2013); O’Keefe Burgess (1996):

$\displaystyle\begin{split}&\Pr(r_{j}|\gamma_{j},\hat{\psi}_{j},f_{i},s_{i}^{\prime},\mathcal{M})\\\
&\qquad=\lvert
u(s_{i}^{\prime},\gamma_{j},\mathcal{M})\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}v(f_{i},r_{j},\gamma_{j},\hat{\psi}_{j})\rvert\\\
&\qquad\qquad\times\exp\left(-dist(s_{i}^{\prime},\gamma_{j},\mathcal{M})^{2}/2\sigma^{2}\right)\end{split}$
(7.5)

where $\sigma$ controls the steepness of the distribution based on the spatial
relation’s semantics and landmark size, and
$dist(s_{i}^{\prime},\gamma_{j},\mathcal{M})$ is the distance between
$s_{i}^{\prime}$ to the closest position within the ground $\gamma_{j}$ in map
$\mathcal{M}$, and
$u(s_{i}^{\prime},\gamma_{j},\mathcal{M})\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}v(f_{i},r_{j},\gamma_{j},\hat{\psi}_{j})$
is the dot product between $u(s_{i}^{\prime},\gamma_{j},\mathcal{M})$, the
unit vector from $s_{i}^{\prime}$ to the closest position within the ground
$\gamma_{j}$ in map $\mathcal{M}$, and
$v(f_{i},r_{j},\gamma_{j},\hat{\psi}_{j})$, a unit vector in in the direction
that satisfies the semantics of the proposition $(f_{i},r_{j},\gamma_{j})$ by
rotating $\hat{\psi}_{j}$. The dot product is skipped for prepositions that do
not require FoRs (e.g. _near_). We refer to Landau Jackendoff (1993) for a
list of prepositions meaningful in 2D that require FoRs: _above, below, down,
top, under, north, east, south, west, northwest, northeast, southwest,
southeast, front, behind, left, right_.

### 7.5 Data Collection

In this section, we describe our data collection process as well as a pipeline
for spatial information extraction from natural language. We use maps from
OpenStreetMap (OSM), a free and open-source database of the world map with
voluntary landmark contributions OpenStreetMap contributors (2017). We scrape
landmarks in 40,000m2 grid-regions with a resolution of 5m by 5m grid cells in
five different cities leading to a dimension of 41$\times$41 per grid
map333Because of the curvature of the earth, the grid cells and overall region
is not perfectly square, which is why the grid is not perfectly 40x40: Austin,
TX; Cleveland, OH; Denver, CO; Honolulu, HI, and Washington, DC. Geographic
coordinates of OSM landmarks are translated into grid map coordinates.

To collect a variety of spatial language descriptions from each city, we
randomly generate 30 environment configurations for each city, each with two
target objects. We prompt Amazon Mechanical Turk (AMT) workers to describe the
location of the target objects and specify that the robot knows the map but
does not know target locations. Each configuration is used to obtain language
descriptions from up to eleven different workers. The descriptions are parsed
using our pipeline described next in Sec. 7.5.1. Examples are shown in Fig.
7.4. Screenshots of the survey and statistics of the dataset are provided in
the supplementary material.

The authors annotated FoRs for _front, behind, left_ and _right_ through a
custom annotation tool which displays the AMT worker’s language alongside the
map without targets. We manually infer the FoR used by the AMT worker, similar
to what the robot is tasked to do. This set of annotations are used as data to
train and evaluate our FoR prediction model. Prepositions such as _north,
northeast_ have absolute FoRs with known direction. Others are either
difficult to annotate (e.g. _across_) or have too little samples (e.g. _above_
, _below_).

#### 7.5.1 Spatial Information Extraction from Natural Language

We designed a pipeline to extract spatial relation triplets from the natural
language using the spaCy library Honnibal Montani (2017) for noun phrase (NP)
identification and dependency parsing, as it achieves good performance on
these tasks. Extracted NPs are matched against synonyms of target and landmark
symbols using cosine similarity. All paths from targets to landmarks in the
dependency parse tree are extracted to form the $(f,r,\gamma)$ tuples used as
spatial language observations (Sec. 7.4).

Our spatial language understanding models assume as input language that has
been parsed into $(f,r,\gamma)$ tuples, but is not dependent on this exact
pipeline for doing so. Future work could explore alternative methods for
parsing and entity linking, including approaches optimized for the task of
spatial language resolution. In our end-to-end experiments, we report the task
performance both when using this parsing pipeline and when using manually
annotated $(f,r,\gamma)$ tuples to indicate the influence of parsing on search
performance.

Figure 7.4: Map screenshot shown to AMT workers paired with collected spatial
language descriptions.

### 7.6 Evaluation

#### 7.6.1 Evaluation of Frame of Reference Prediction Model

We test the generalizability of our FoR prediction model (EGO-CTX) by cross-
validation. The model is trained on maps from four cities and tested on the
remaining held-out city for all possible splits. We evaluate the model by the
angular deviation between predicted and annotated FoR angles, in comparison
with three baselines and human performance: The first is a variation (CTX)
that uses a synthetic image with the same kind of contextual representation
yet without egocentric shift. The second is another variation (EGO) that
performs egocentric shift and also crops a $28\times 28$ window, but only
highlights the referenced landmark at the center without contextual
information. The random baseline (Random) predicts the angle at random
uniformly between $[0,2\pi]$. The Human performance is obtained by first
computing the differences between pairs of annotated FoR angles for the same
landmarks (Eq. 7.4), then averaging over all such differences for landmarks
per city. Each pair of FoRs may be annotated by the same or different
annotators. Taking the average gives a sense of the disagreement among the
annotators’ interpretation of spatial relations.

Figure 7.5: FoR prediction results. The solid orange line shows the median,
and the dotted green line shows the mean. The circles are outliers. Lower is
better. Figure 7.6: Visualization of FoR predictions for _front_. Darker
arrows indicate labeled FoR, while brighter arrows are predicted FoR.

The results are shown in Figure 7.5. Each boxplot summarizes the means of
baseline performance in the five cross-validation splits. The results
demonstrate that EGO-CTX shows generalizable behavior close to the human
annotators, especially for front. We observe that our model is able to predict
_front_ FoRs roughly perpendicular to streets against other buildings, while
the baselines often fail to do so (Figure 7.6). The competitive performance of
the neural network baselines in left indicates that for _left_ and _right_ ,
the FoR annotations are often absolute, i.e. independent of the context. Our
model as well as baselines are limited in determining, for example, whether
the speaker refers to the left side of the map (absolute FoR), or the left
side of the street relative to a perceived forward direction (relative FoR).

#### 7.6.2 End-to-End Evaluation

We randomly select 20 spatial descriptions per city. We task the robot to
search for each target object mentioned in every description separately,
resulting in a total of 40 search trials per city, 200 in total. Cross-
validation is employed such that for each city, the robot uses the FoR
prediction model trained on the other four cities. For each step, the robot
can either move or mark an object as detected. The robot can move by rotating
clockwise or counterclockwise for 45 degrees, or move forward by 3 grid cells
(15m). The robot receives observation through an on-board fan-shaped sensor
after every move. The sensor has a field of view with an angle of 45 degrees
and a varying depth of 3, 4, 5 (15m, 20m, 25m). As the field of view becomes
smaller, the search task is expected to be more difficult. The robot receives
$R_{\text{step}}=-10$ step cost for moving and $R_{\max}=+1000$ for correctly
detecting the target, and $R_{\min}=-1000$ if the detection is incorrect. The
rest of the domain setup follows Wandzel . (2019).

_Baselines._ SLOOP uses the spatial language observation model without
mixture, that is, for each object, it computes the observation distribution in
Eq. (7.3) by multiplying the distributions for each spatial relation; With the
same observation distribution, SLOOP (m=2) mixes in one distribution computed
by treating all prepositions as _near_ with weight 0.2; Also with the same
observation distribution, SLOOP (m=4) mixes in three additional distributions:
one ignores FoR-dependent prepositions, one treating all prepositions as
_near_ , one treating all prepositions as _at_ , with weights 0.25, 0.1, 0.05,
respectively. The baseline MOS (keyword) uses a keyword-based model based on
Wandzel . (2019) that assigns a uniform probability over referenced landmarks
in a spatial language but does not incorporate information from spatial
prepositions. Finally, informed and uniform are upper and lower bounds: for
the informed, the agent has an initial belief that has a small Gaussian noise
over the groundtruth location444The noise is necessary for object search,
otherwise the task is trivial.; uniform uses a uniform prior. We also report
the performance with annotated spatial relations and landmarks to show search
performance if the languages are parsed correctly.

For all baselines, we use an online POMDP solver, POMCP Silver Veness (2010)
but with a histogram belief representation to avoid particle depletion. The
number of simulations per planning step is 1000 for all baselines. The
discount factor is set to 0.95. The robot is allowed to search for 200 steps
per search task, since search beyond this point will earn very little
discounted reward and is not efficient.

Figure 7.7: Number of completed search tasks as the maximum search step
increases. Steeper slope indicates greater efficiency and success rate of
search. Figure 7.8: Example object search trial for description “the green
toyota is _behind_ velvet dog” from AMT. The green region shows the
distribution over the object location after interpreting the description. Our
method enables probabilistic interpretation of the spatial language leading to
more efficient search strategy.

_Results._ We evaluate the effectiveness and efficiency of the search by the
amount of search tasks the robot completed (i.e. successfully found the
target) under a given limit of search steps (ranging from 1 to 200). Results
are shown in Figure 7.7. The results show that using spatial language with
SLOOP outperforms the keyword-based approach in MOS. The gain in the
discounted reward is statistically significant over all sensor ranges
comparing SLOOP with MOS (keyword), and for sensor range 3 comparing the
annotated versions. We observe that using mixture models for spatial language
improves search efficiency and success rate over SLOOP. We observe improvement
when the system is given annotated spatial relations. This suggests the
important role of language parsing for spatial language understanding. Figure
7.8 shows a trial comparing SLOOP and MOS (keyword).

spatial | No. | MOS (keyword) | SLOOP | SLOOP (m=4)
---|---|---|---|---
preposition | trials | annodated | annotated | annotated
on | 59 | 200.65 (78.06) | 267.00 (76.45) | 290.05 (70.51)
at | 58 | 179.42 (81.46) | 237.36 (81.03) | 238.24 (80.50)
near | 35 | 97.64 (135.39) | 280.69 (109.00) | 249.35 (113.60)
between | 25 | 21.48 (116.93) | 172.93 (143.77) | 175.59 (136.71)
in | 22 | 302.05 (151.42) | 398.88 (119.32) | 307.45 (141.67)
north | 9 | 222.28 (291.13) | 201.88 (296.49) | 365.14 (246.05)
southeast | 7 | 306.77 (341.43) | 553.82 (174.04) | 549.43 (165.83)
southwest | 7 | -75.67 (205.98) | 1.37 (271.46) | -27.63 (281.89)
east | 6 | 56.57 (337.58) | 290.68 (303.53) | 439.99 (276.85)
northwest | 6 | 385.41 (320.82) | 43.57 (282.88) | -1.82 (256.71)
south | 6 | 79.12 (289.54) | 310.29 (410.04) | 494.26 (161.60)
west | 4 | -160.91 (188.02) | 234.93 (587.57) | 327.13 (245.28)
northeast | 2 | -167.99 (660.76) | 206.42 (138.93) | 213.17 (977.62)
front | 25 | 246.96 (142.45) | 168.91 (150.41) | 160.55 (136.88)
behind | 8 | 128.47 (356.25) | 101.20 (333.38) | 140.92 (333.61)
right | 4 | 19.75 (697.88) | 160.14 (601.54) | 336.00 (725.84)
left | 3 | 247.35 (363.32) | 192.93 (393.75) | 231.75 (330.33)
front (good) | 15 | 255.85 (210.46) | 421.83 (143.65) | 222.67 (264.50)
behind (good) | 6 | 145.26 (489.55) | 207.58 (430.52) | 359.80 (753.15)
front (bad) | 10 | 281.04 (226.47) | -208.92 (11.39) | 93.80 (176.11)
behind (bad) | 2 | 78.11 (3771.84) | -217.95 (23.53) | -77.97 (223.71)
Table 7.1: Mean (95% CI) of discounted cumulative reward for different
prepositions evaluated on language descriptions with annotated spatial
relations. The value with highest mean per row is bolded.

We analyze the performance with respect to different spatial prepositions. We
report results for annotated languages as they reflect the performance
obtained if the prepositions are correctly identified. Results for the
smallest sensor range of 3 is shown in Table 7.1. SLOOP outperforms the
baseline for the majority of prepositions. For prepositions _front_ , _behind_
, _left_ , and _right_ , our investigation shows the performance of SLOOP
polarizes where trials with “good” FoR (i.e. ones in the correct direction
towards the true target location) leads to a much greater performance than the
counterpart (“bad” FoR). Yet, MOS (keyword) is not subject to such
polarization and the target often appears close to the landmark for these
prepositions. We observe that SLOOP (m=4) using mixture is able to
consistently improve the reward for most of the prepositions, indicating the
benefit of modeling multiple interpretations of the spatial language.

No. spatial | No. | MOS (keyword) | SLOOP | SLOOP (m=4)
---|---|---|---|---
prepositions | trials | annotated | annotated | annotated
1 | 100 | 234.32 (72.64) | 320.91 (64.23) | 289.34 (66.42)
2 | 83 | 179.18 (68.60) | 264.08 (62.39) | 286.19 (60.83)
3 | 14 | 26.96 (165.98) | 115.44 (202.42) | 215.30 (200.99)
Table 7.2: Mean (95% CI) of discounted cumulative reward for completed search
tasks as language complexity (number of spatial relations) increases.

Finally, we analyze the relationship between the performance and varying
complexity of the language description, indicated by the number of spatial
relations used to describe the target location. Again, we used annotated
languages for this experiment for the smallest sensor range of 3. Results in
Table 7.2 indicate that understanding spatial language can benefit search
performance, with a wider gain as the number of spatial relations increases.
Again, using mixture model in SLOOP (m=4) improves the performance even more.

#### 7.6.3 Demonstration on AirSim

We implemented SLOOP (m=4) on AirSim S. Shah . (2017), a realistic drone
simulator built on top of Unreal Engine Epic Games (). Similar to our
evaluation in OpenStreetMap, we discretize the map into 41$\times$41 grid
cells. We use the same fan-shaped model of on-board sensor as in
OpenStreetMap. As mentioned in Sec. 7.3, sensor observations are synthetic,
based on the ground-truth state. Additionally, although the underlying
localization and control is continuous, the drone plans discrete navigation
actions (move forward, rotate left 90∘, rotate right 90∘). We annotated
landmarks (houses and streets) in the scene on the 2D grid map. Houses with
heights greater than flight height are subject to collision and results in a
large penalty reward (-1000). Checking for collision in the POMDP model for
this domain helped prevent such behavior during planning. We found that the
FoR prediction model trained on OpenStreetMap generalizes to this domain,
consistently producing reasonable FoR predictions for _front_ and _behind_.
This shows the benefit of using synthetic images of top-down street maps. The
drone is able to plan actions to search back and forth to find the object,
despite given inexact spatial language description. Please refer to the video
demo on our project for the examples shown in Fig. 7.1 and 7.9.

Figure 7.9: Example trial from AirSim demonstration. Given spatial language
description: _The red car is by the side of Main street in front of Zoey’s
House (red), while the green car is within Annie’s House on the right side of
East street (green)._ Left: belief over two target objects (red and green
car). Right: screenshot from AirSim. Video: https://youtu.be/V54RY8v8VmA

#### 7.6.4 Demonstration on Boston Dynamics Spot

We take one step further and demonstrate SLOOP on a physical robot. In
particular, we task a Boston Dynamics Spot robot to find a book in a lab
environment. We developed a 2D MOS-based object search system integrated with
ROS that can interact with Spot through the Spot SDK. This system uses
histogram-based 2D belief, and the object search POMDP model is the same 2D
MOS model used for simulation experiments.555In fact, this system is the
npredecessor to GenMOS for 3D-MOS in Chapter 5, GenMOS is robot-independent
(does not rely on ROS). Object detection was done through projecting
segmentation masks obtained with Mask-RCNN He . (2017) to 2D grid cells using
depth from Spot’s gripper camera. To obtain the same kind of 2D grid map
representation as in simulation experiments, we first use Spot’s built-in
capability to create a 3D point cloud map of the lab and then project it down
to 2D, where points are filtered to separate free space from obstacles. Then,
in order to apply SLOOP for 2D MOS, we build a map of landmarks similar to
OpenStreetMap by driving the robot around the lab, and recording object
detection results projected onto a 2D grid, and then assigning a unique name
to each detected object. Since our FoR prediction model works over synthetic
images, they can be directly applied to this landmark map. The end result is
an interface that allows a person to type in a free-form spatial language with
respect to the landmarks, and the belief gets updated after the system
interprets the spatial language, and the robot goes off to search under the
updated belief; Planning is based on the hierarchical planning algorithm
introduced for COS-POMDP in Chapter 6 that combines local, fine-grained search
actions with navigation subgoals over a topological graph. In Figure 7.10, we
contrast the system’s behavior with and without spatial language. SLOOP
enables the robot to quickly narrow down the search region given _“the book is
in front of the Monitor,”_ whereas the baseline without language results in
searching all over the lab.

Figure 7.10: Demonstration of SLOOP on Spot, given the spatial language _“the
book is in front of the Monitor.”_ The total time used for “with spatial
language” includes the time to initially type in the language, while the
baseline without language proceeds to search right off the bat. Nevertheless,
SLOOP quickly narrows down the search space and the robot successfully finds
the book.

### 7.7 Summary

This chapter first presents a formalism for integrating spatial language into
the POMDP belief state as an observation, then a convolutional neural network
for FoR prediction shown to generalize well to new cities. Simulation
experiments show that our system significantly improves object search
efficiency and effectiveness in city-scale domains through understanding
spatial language. For future work, we plan to investigate compositionality in
spatial language for partially observable domains.

### 7.8 Appendix

#### 7.8.1 Derivation of Spatial Language Observation Model

Here we provide the derivation for Eq. (7.3). Using the definition of
$o_{\mathcal{R}_{i}}$,

$\displaystyle\Pr(o_{\mathcal{R}_{i}}|s_{i}^{\prime},\mathcal{M})$
$\displaystyle=\Pr(f_{i},r_{1},\gamma_{1},\cdots,r_{L},\gamma_{L}|s_{i}^{\prime},\mathcal{M})$
(7.6)
$\displaystyle=\Pr(r_{1},\cdots,r_{L}|\gamma_{1},\cdots,\gamma_{L},f_{i},s_{i}^{\prime},\mathcal{M})\times\Pr(\gamma_{1},\cdots,\gamma_{L},f_{i}|s_{i}^{\prime},\mathcal{M})$
(7.7)
$\displaystyle=\frac{1}{Z}\prod_{j=1}^{L}\Pr(r_{j}|\gamma_{j},f_{i},s_{i}^{\prime},\mathcal{M})$
(7.8)

The first term in (7.7) is factored by individual spatial relations, because
each $r_{j}$ is a predicate that, by definition, involves only the figure
$f_{i}$ and the ground $\gamma_{j}$, therefore it is conditionally independent
of all other relations and grounds given $f_{i}$, its location
$s_{i}^{\prime}$, and the landmark $\gamma_{j}$ and its features contained in
$\mathcal{M}$. Because the robot has no prior knowledge regarding the human
observer’s language use,666In general, the human observer may produce spatial
language that mentions arbitrary landmarks and figures whether they make sense
or not. the second term in (7.7) is uniform with probability $1/Z$ where $Z$
is the constant size of the support for $\gamma_{1},\cdots,\gamma_{L},f_{i}$.
This constant can be canceled out during POMDP belief update upon receiving
the spatial language observation, using the belief update formula in Section
2.2.2. We omit this constant in Eq. (7.3).

For predicates such as _behind_ , its truth value depends on the relative FoR
imposed by the human observer who knows the target location. Denote the FoR
vector corresponding to $r_{j}$ as a random variable $\Psi_{j}$ that
distributes according to the indicator function
$\Pr(\Psi_{j}=\psi_{j})=\mathbbm{1}(\psi_{j}=\psi_{j}^{*})$, where
$\psi_{j}^{*}$ is the one imposed by the human. Then regarding
$\Pr(r_{j}|\gamma_{j},f_{i},s_{i}^{\prime},\mathcal{M})$, we can sum out
$\Psi_{j}$:

$\displaystyle\Pr(r_{j}|\gamma_{j},f_{i},s_{i}^{\prime},\mathcal{M})$
$\displaystyle=\frac{\sum_{\psi_{j}}\Pr(r_{j},\gamma_{j},f_{i},s_{i}^{\prime},\mathcal{M}|\psi_{j})\Pr(\psi_{j})}{\Pr(\gamma_{j},f_{i},s_{i}^{\prime},\mathcal{M})}$
(7.9) Since the distribution for $\Psi_{j}$ is an indicator function,
$\displaystyle=\frac{\Pr(r_{j},\gamma_{j},f_{i},s_{i}^{\prime},\mathcal{M}|\psi_{j}^{*})}{\Pr(\gamma_{j},f_{i},s_{i}^{\prime},\mathcal{M})}$
(7.10) By the law of total probability,
$\displaystyle=\frac{\Pr(r_{j}|\gamma_{j},\psi_{j}^{*},f_{i},s_{i}^{\prime},\mathcal{M})\Pr(\gamma_{j},f_{i}|s_{i}^{\prime},\mathcal{M},\psi_{j}^{*})\Pr(s_{i}^{\prime},\mathcal{M}|\psi_{j}^{*})}{\Pr(\gamma_{j},f_{i}|s_{i}^{\prime},\mathcal{M})\Pr(s_{i}^{\prime},\mathcal{M})}$
(7.11) Using the fact that $s_{i}^{\prime},\mathcal{M}$ is independent of
$\psi_{j}^{*}$,
$\displaystyle=\frac{\Pr(r_{j}|\gamma_{j},\psi_{j}^{*},f_{i},s_{i}^{\prime},\mathcal{M})\Pr(\gamma_{j},f_{i}|s_{i}^{\prime},\mathcal{M},\psi_{j}^{*})\Pr(s_{i}^{\prime},\mathcal{M})}{\Pr(\gamma_{j},f_{i}|s_{i}^{\prime},\mathcal{M})\Pr(s_{i}^{\prime},\mathcal{M})}$
(7.12) Canceling out $\Pr(s_{i}^{\prime},\mathcal{M})$,
$\displaystyle=\frac{\Pr(r_{j}|\gamma_{j},\psi_{j}^{*},f_{i},s_{i}^{\prime},\mathcal{M})\Pr(\gamma_{j},f_{i}|s_{i}^{\prime},\mathcal{M},\psi_{j}^{*})}{\Pr(\gamma_{j},f_{i}|s_{i}^{\prime},\mathcal{M})}$
(7.13) Similar to (7.7)-(7.8),
$\Pr(\gamma_{j},f_{i}|s_{i}^{\prime},\mathcal{M},\psi_{j}^{*})$ and
$\Pr(\gamma_{j},f_{i}|s_{i}^{\prime},\mathcal{M})$ are uniform with the same
support. Canceling them out,
$\displaystyle=\Pr(r_{j}|\gamma_{j},\psi_{j}^{*},f_{i},s_{i}^{\prime},\mathcal{M})$
(7.14)

#### 7.8.2 Data Collection Details

##### Amazon Mechanical Turk Questionnaire

As described in Section 7.5, we collect a variety of spatial language
descriptions from five cities. We randomly generate 10 unique configurations
of two object locations for every pair of object symbols from {RedBike,
RedCar, RedCar}. Each configuration is used to obtain language descriptions
from up to eleven different workers. By showing a picture of the objects
placed on the map screenshot, we prompt AMT workers to describe the location
of the target objects. We first show an example task as shown in Fig 7.11
(top). Then we prompt them with the actual task and a text box to submit their
response, as shown in Fig 7.11 (bottom). Note that we specify that the robot
does not know where the target objects are, but that it knows the buildings,
streets and other landmarks available on the map. We encourage them to use the
information available on the map in their description.

Figure 7.11: AMT Questionnaire Screenshot. Top: an example task shown to the
AMT workers prior to the actual task that doesn’t vary from prompt to prompt.
Bottom: the actual task shown to the AMT workers. The objects and the
locations change in every prompt and are all unique.

#### 7.8.3 Distribution of Collected Predicates

Each description is parsed using our pipeline described in Section 7.5.1.
1,521 out of 1,650 gathered descriptions were successfully parsed; meaning at
least one spatial relation was extracted from the sentence. The distribution
of all spatial predicates are shown in Fig 7.12. Note that we include the word
“is” on the list since it often appears in “is in” or “is at”, yet the parser
sometimes skip the word after it due to an artifact. We excluded language
descriptions parsed with such artifact from the ones used in the end-to-end
object search evaluation.

Figure 7.12: Distribution of collected parsable predicates sorted from most frequent to least. Spatial preposition | # of FoR annotations
---|---
front | 121
behind | 54
left | 51
right | 47
Table 7.3: Number of FoR annotations per spatial relation.

#### 7.8.4 FoR Annotation

To collect the FoR annotation, we create our custom annotation tool. The FoR
consists of a front (purple) and right (green) vector that show how the
speaker considers the direction of the ground according to their given spatial
description. The interface (Fig 7.13) works as follows: (1) The annotator
first clicks the “Annotate” button. (2) The interface prompts the annotator
the language phrase corresponding to a spatial relation to be annotated (e.g.
“RedBike is in front of EmpireApartments”), which is composed using the parsed
$(f,r,\gamma)$ tuple. (3) to annotate an FoR, the annotator clicks on the map
as the origin of the FoR, and then clicks on another point on the map as the
end point of the _front_ vector. The vector for _right_ is automatically
computed to be 90 degrees clockwise with respect to the _front_ vector. (4)
After annotating one FoR, the annotator clicks “Next” to move on, and the
process starts over again from step (2). In total we have 273 FoR annotations.
Table 7.3 shows the amount of annotation per spatial relation. You can
download the dataset by visiting the website linked in the footnote on the
first page.

Figure 7.13: The FoR annotator GUI interface. The FoR consists of a front
(purple) and right (green) vector. The target objects are not shown, and the
annotator only has access to the spatial language description, and the map
image. This mimics the situation faced by the robot in our task.

## Chapter 8 Dialogue Object Search: Preliminary Work

Figure 8.1: The motivating scenario for dialogue object search. Imagine one
person is searching for a file at home. Not knowing where it could be, he
calls a family member who knows more. Then, he is able to verbally engage in
the dialogue over the phone while performing search physically. We view
dialogue object search as one route towards realizing such ability to decide
what to say and how to act simultaneously, fundamental for future
collaborative robots.

### 8.1 Motivation

We envision robots that can collaborate and communicate seamlessly with
humans. It is necessary for such robots to decide both what to say and how to
act, while interacting with humans. To this end, we introduce a new task,
_dialogue object search_ : A robot is tasked to search for a target object
(e.g. fork) in a human environment (e.g., kitchen), while engaging in a “video
call” with a remote human who has additional but inexact knowledge about the
target’s location. That is, the robot conducts speech-based dialogue with the
human, while sharing the image from its mounted camera. This task is
challenging at multiple levels, from data collection, algorithm and system
development, to evaluation. Despite these challenges, we believe such a task
blocks the path towards more intelligent and collaborative robots. In this
extended abstract, we motivate and introduce the dialogue object search task
and analyze examples collected from a pilot study. We then discuss our next
steps and conclude with several challenges on which we hope to receive
feedback.

Humans can act in the physical world (such as walking, looking, or opening a
cabinet) while having a conversation with others. As robots enter homes and
care centers, we envision them to have such capability as well when
collaborating and communicating with humans. To achieve this, robots must
decide both what to say and how to act towards a goal. This involves combining
task-oriented dialogue systems with decision making under uncertainty for
embodied agents. Traditionally, dialogue systems have involved users
interacting with a virtual agent for tasks such as technical support
Mouromtsev . (2015), personal assistance (e.g., Siri) and booking reservations
Wen . (2017); Wei . (2018). While recent works have proposed datasets that
combine dialogue and dynamic, embodied decision making de Vries . (2018);
Thomason . (2020), the investigated problems over these datasets are limited
to prediction tasks that bypass the challenges of evaluating a conversational
embodied agent. For example, the Navigation from Dialog History Task Thomason
. (2020) asks the agent to predict the next navigation action, given a history
of dialogue and past navigation actions. The tourist localization task de
Vries . (2018) asks the system to predict a location given a language
description.

Our goal is to enable robots to naturally engage in a dialogue with a human
while completing a task autonomously. We believe a task that captures the
sequential nature of both the dialogue and physical decision making is
necessary for in-depth study towards this goal. We choose to focus on object
search, a useful and widely-studied problem Aydemir . (2013); Kollar Roy
(2009); Zheng . (2021b, 2021a)

### 8.2 Contributions

The main contribution is we introduce a new task called _dialogue object
search_. From the pilot study (Sec. 8.4), we observed that participants
produced language and behavior that are more natural using speech, because
text-based dialogue requires users to decide whether to type or act at every
step. Additionally, we summarize the set of intent types that are observed to
succinctly capture the intents behind the unstructured utterances in the
dialogue object search task.

### 8.3 Dialogue Object Search

A robot is tasked to search for a target object in a human environment (e.g.,
kitchen) while engaging in an audio dialogue with a remote human assistant,
who possesses inexact prior knowledge about the target object’s location. In
our pilot study, this is given in the form of a 2D scatter plot (Fig.
LABEL:fig:timeline). The robot has a mounted RGB-D camera, and shares its view
with the human assistant. We assume the robot and the human assistant have
access to two different sequences of RGB-D images of the scene, which
represent their prior experiences of living in that environment. Target
objects are excluded from these images. The robot must decide what to say and
how to act, in order to efficiently find the target object while naturally
interacting and collaborating with the human assistant.

Our inspiration for the above setting comes from the following scenario
between two people living together (family or friends). One person is
searching for something, such as a document or a key, but not sure where it
is. They decide to video call the other home member who is currently out of
the house but may have a better idea. They then engage in a dialogue while the
first person conducts the search for the target object. We envision that in
the future, this could happen between a home assistant robot and a human user.

### 8.4 Pilot Study

To investigate the above task, we first attempted to understand how a human
would behave if they are in the robot’s position. We designed and conducted a
pilot study among three pairs of people (authors’ lab members) using AI2-THOR
Kolve . (2017) as the simulated home environments. In this study, we designate
two roles according to the above problem setting. The _Assistant_ is the
person assisting in the process as the robot searches for a given target
object. The _Controller_ is the person who is taking on the role of the robot.
Due to the pandemic, we used Zoom to record the audio and create transcripts
of the dialogue. We implemented a web-based data collection tool where the
_Controller_ controls the agent in AI2-THOR through the web interface, and the
_Assistant_ has access to a 2D scatter plot of a subset of objects in the
scene (Fig. LABEL:fig:timeline). Each pair of participants are assigned three
object search trials in one environment. They have 90 seconds to explore the
environment (with target objects removed) and 180 seconds to complete each
trial. In addition to dialogue audio and transcripts, we collected data about
the scene per view, the action executed, and the agent’s groundtruth pose as
provided by the AI2-THOR framework. We considered a discrete action space of
{_MoveAhead_(0.25m), _RotateLeft_(45$\degree$), _RotateRight_(45$\degree$),
_LookUp_(30$\degree$), _LookDown_(30$\degree$), _Open_ , _Close_}.111We first
experimented with a rotation angle of 90$\degree$ following Gordon . (2018);
X. Ye Yang (2021), but experienced sudden jumps that are unnatural as felt by
the participants. Therefore, we switch to 45$\degree$, also used by some
existing works Wortsman . (2019); Qiu . (2020).

Despite the small scale of our pilot dataset, we observed some interesting
behaviors shared between trials. For example, at the beginning of the object
search trials the _Assistant_ would specify the target object and the
_Controller_ would confirm. Additionally, as the task progresses, both roles
would describe behaviors, beliefs about the environment and location of
objects, and visual observations. We codified these into a set of preliminary
intent types; some examples are given in the figure above. Using this pilot
dataset, we have started to explore the development of an autonomous agent
(_Controller_), both modular and end-to-end that can plan actions for this
task.

As mentioned in the introduction, we experimented with both speech-based
dialogue and text-based dialogue, using the recording and chat features of
Zoom. With speech, participants typically engage in frequent back-and-forth,
as the _Controller_ controls the agent. Such exchanges involve discussing, for
example, the scene and possible target locations. Participants report that
when using text, the _Controller_ must decide between controlling the agent in
AI2-THOR versus typing in the chat. Consequently, they would try to search for
the object themselves without interacting with the _Assistant_ , who, as a
result, finds it difficult to tell if their input is being considered by the
_Controller_. This suggests collecting dialogue data through text is unnatural
and misaligned with our goal.

### 8.5 Discussion & Next Steps

Though truthful to the task, our pilot data collection procedure is currently
not scalable. We plan to implement a system that can be deployed on the
crowdsourcing platform Amazon Mechanical Turk (AMT), to pair up Turkers to
participate in the task entirely through their web browsers for accessibility.
AMT a powerful platform, yet not designed for multi-user tasks. Due to audio
communication and running AI2-THOR servers, we face a more difficult situation
than Das . (2017) who had to implemented a live chatbot on AMT. We also need
solutions to scalable and accurate transcription of the collected audio as
well as intent labling. We seek suggestions for strategies to collect such
data at scale. In terms of evaluation, we believe both experiment with
simulated assistants and real human assistants are necessary. For the
simulated assistant, we are considering an oracle agent that communicates
using template-based language. The goal of this simulated agent is to
facilitate efficient and repeatable evaluations during algorithm development
for the embodied dialogue agent, which could be a long-term effort.
Ultimately, the agent should be deployed to perform the task with real human
subjects. We plan to consider objective metrics for both object search
performance (e.g., success rate and discounted total return and dialogue
quality Venkatesh . (2018), and, eventually, subjective metrics such as
naturalness Hung . (2009). We believe finding solutions to scalable speech-
based dialogue data collection for embodied tasks and plausible evaluation
protocol are daunting, yet unavoidable challenges towards future collaborative
robots.

THIS IS THE END OF THIS CHAPTER.

## Chapter 9 Conclusion

This thesis was motivated by the practical challenges for object search and
the goal of making object search an off-the-shelf ability for robots. It
argues for using POMDP to model object search and exploiting structure in the
human world and human-robot interaction to achieve practical and effective
object search systems.

We have provided a few examples in supporting this argument: octrees for 3D
multi-object search, spatial correlations for searching for hard-to-detect
objects, and structure in spatial language for searching with a hint. We were
able to demonstrate our proposed algorithms in realistic simulators and on
real robots. Notably, we built GenMOS, the first robot-independent,
environment agnostic system for object search in 3D, and integrated it with
three different robots in different environments. As a preliminary work, we
also identified patterns in the intents behind utterances for dialogue object
search.

We have also proposed taxonomies for three main aspects of object search
studies: problem settings, solution methods, and the systems and applied them
in the literature review of more than 125 papers related to object search.

###### Future Work

Chapter 3 has provided a generic POMDP model for object search, which has been
the parent model for all the POMDP models we developed for specific problems.
However, the problems studied in this thesis are still basic in the sense that
they have involved static target objects and no environment interaction.
Achieving generalized object search beyond the basic setting is the big open
problem and ultimate pursuit in this field. Additionally, it is beneficial to
study ways to learn models of the environment which can be used for object
search planning. This is likely more useful for search involving environment
interactions.

If the question is whether a generic POMDP for object search model in Chapter
3 is extensible to handle the additional challenges, there is both potential
to explore and foreseeable hurdles to worry. In terms of potential, the
transition function in the POMDP can be easily extended to consider motion of
target objects. Besides, the high-level Look action can be extended to be an
abstraction over not only navigation-based search actions, but also
manipulation-based, which all serve the purpose of perceiving some part of the
environment. However, trouble arises as the consequences of manipulation to
the environment may become intractable to model. For example, suppose that a
book might be underneath a bed. In this case, a good way to search underneath
the bed is not to bend over and look, but to find a tool, such as a stick, to
sweep underneath the bed. A robot that can reason at this level faces the
challenge of considering consequences of sweeping in the environment. How to
make a robot that can perform search while being aware of the consequence of
its own actions to the environment? This is a valuable direction of future
work.

THIS IS THE END OF THIS CHAPTER.

## Appendix A The pomdp_py library

In this appendix, we present pomdp_py, a general purpose Partially Observable
Markov Decision Process (POMDP) library written in Python and Cython. Existing
POMDP libraries often hinder accessibility and efficient prototyping due to
the underlying programming language or interfaces, and require extra
complexity in software toolchain to integrate with robotics systems. pomdp_py
features simple and comprehensive interfaces capable of describing large
discrete or continuous (PO)MDP problems. Here, we summarize the design
principles and describe in detail the programming model and interfaces in
pomdp_py. We also describe intuitive integration of this library with ROS
(Robot Operating System), which enabled our torso-actuated robot to perform
object search in 3D. Finally, we note directions to improve and extend this
library for POMDP planning and beyond.

### 1 Introduction

Partially Observable Markov Decision Processes (POMDP) are a sequential
decision-making framework suitable to model many robotics problems, from
localization and mapping Ocaña . (2005) to human-robot interaction Whitney .
(2017). Early efforts in developing tools for POMDPs attempt to separate
solvers from domain description by creating specialized file formats to
specify POMDPs Cassandr (2003); APPL (2009), which are not designed for large
and complex problems. Among libraries under active development, Approximate
POMDP Planning Toolkit (APPL) Somani . (2013) and AI-Toolbox Bargiacchi (2014)
are implemented in C++ and contain numerous solvers. However, the learning
curve for these libraries is steep as C++ is less accessible to current
researchers in general compared to Python Virtanen . (2020). POMDPs.jl Egorov
. (2017) is a POMDP library with a suite of solvers and domains, written in
Julia. Though promising, Julia has yet to achieve a wide recognition and
creates language barrier for many researchers. POMDPy Emami . (2015) is
implemented purely in Python. Yet with an original focus on POMCP
implementation, it assumes a blackbox world model in its POMDP interface,
limiting its extensibility. Finally, a promising toolchain is to use
Relational Dynamic Influence Diagram Language (RDDL) Sanner (2010) to describe
factored POMDPs and solve them via ROSPlan Cashmore . (2015), recently
demonstrated for object fetching Canal . (2019). Nevertheless, using this set
of tools adds overhead of using a classical fluent-based planning paradigm,
which is not required to describe and solve POMDPs in general.

This leads to our belief that there lacks a POMDP library with simple
interfaces that brings together both accessibility and performance. We address
this demand by presenting pomdp_py, a framework to build and solve POMDP
problems written in Python and Cython Behnel . (2011). It features simple and
comprehensive interfaces to describe POMDP or MDP problems, and can be
integrated with ROS Quigley . (2009) intuitively through rospy. In the rest of
this appendix, we first review POMDPs, then illustrate the design principles
and key features of pomdp_py, including integration with ROS. Finally, we note
directions to improve and extend this library, in hope of cultivating an open-
source community for POMDP-related research and development. The documentation
of pomdp_py is available at: https://h2r.github.io/pomdp-py/html/. Tutorials
on example domains can be found in the documentation. This library is
currently actively developed as we continue our POMDP-related research.

### 2 POMDPs

POMDPs Kaelbling . (1998) model sequential decision making problems where the
agent must act under partial observability of the environment state. Refer to
Background (Section 2.2.2, page 2.2.2) for a formal introduction of POMDPs.

Solvers. Most recent POMDP solvers are _anytime algorithms_ Zilberstein
(1996); Ross . (2008), due to the intractable computation required to solve
POMDPs exactly Madani . (1999). There are currently two major camps of anytime
solvers, point-based methods Kurniawati . (2008); Shani . (2013) which
approximates the belief space by a set of reachable $\alpha$-vectors, and
Monte-Carlo tree search-based methods Silver Veness (2010); Somani . (2013)
that explores a subset of future action-observation sequences.

Currently, pomdp_py contains an implementation of POMCP and PO-UCT Silver
Veness (2010), as well as a naive exact value iteration algorithm without
pruning Kaelbling . (1998). The interfaces of the library support
implementation of other algorithms; We hope to cultivate a community to
implement more solvers or create bridges between pomdp_py and other libraries.

Belief representation The partial observability of environment state implies
that the agent has to maintain a posterior distribution over possible states
Thrun . (2005). The agent should update this belief distribution through new
actions and observations. A tabular belief representation requires nested
iterations over the state space to update the belief, which is computationally
intractable in large domains. Particle belief representation is a simple and
scalable belief representation which is updated through matching simulated and
real observations exactly Silver Veness (2010). Different schemes of weighted
particles have been proposed to handle large or continuous observation spaces
where exact matching results in particle depletion Sunberg Kochenderfer
(20181); Garg . (2019).

pomdp_py does not commit to any specific belief representation. It provides
implementations for basic belief representations and update algorithms,
including tabular, particles, and multi-variate Gaussians, but more
importantly allows the user to create their own new or problem-specific
representation, according to the interface of a generative probability
distribution.

### 3 Design Philosphy

Our goal is to design a framework that allows simple and intuitive ways of
defining POMDPs at scale for both discrete and continuous domains, as well as
solving them either through planning or through reinforcement learning. In
addition, we implement this framework in Python and Cython to improve
accessibility and prototyping efficiency without losing orders of magnitude in
performance Behnel . (2011); Smith (2015). We summarize the design principles
behind pomdp_py below:

  * •

Fundamentally, we view the POMDP scenario as the interaction between an
_agent_ and the _environment_ , through a few important generative probability
distributions ($\pi$, $T,O,R$ or blackbox model $G$).

  * •

The agent and the environment may carry different models to support learning,
since for real-world problems especially in robotics, the agent generally does
not know the true transition or reward models underlying the environment, and
only acts based on a simplified or estimated model.

  * •

The POMDP domain could be very large or continuous, thus explicit enumeration
of elements in the spaces should be optional.

  * •

The representation of belief distribution is decided by the user and can be
customized, as long as it follows the interface of a generative distribution.

  * •

Models can be reused across different POMDP problems. Extensions of the POMDP
framework to, for example, decentralized POMDPs, should also be possible by
building upon existing interfaces.

### 4 Programming Model and Features

The basis of pomdp_py is a set of simple interfaces that collectively form a
framework for building and solving POMDPs.

When defining a POMDP, one first defines the _domain_ by implementing the
State, Action, Observation interfaces. The only required functions for each
interface are __eq__ and __hash__. For example, the interface for State is
simply111Note that the code snippets here are modified or shortened slightly
for display purposes. Please refer to the code on github:
https://github.com/h2r/pomdp-py/:

    class State:
       def __eq__(self, other):
           raise NotImplementedError
       def __hash__(self):
           raise NotImplementedError

Next, one defines the _models_ by implementing the interfaces TransitionModel,
ObservationModel, etc. Note that one may define a different transition and
reward model for the agent than the environment (e.g. for learning). One also
defines a PolicyModel which (1) determines the action space at a given history
or state, and (2) samples an action from this space according to some
probability distribution. Implementing these models involves implementing the
probability, sample and argmax functions. For example, the interface for
ObservationModel, modeling $O(s^{\prime},a,o)=\Pr(o|s^{\prime},a)$, is:

    class ObservationModel:
       def probability(self, observation, next_state, action):
           """Returns the probability Pr(o|s’,a)."""
           raise NotImplementedError
       def sample(self, next_state, action):
           """Returns a sample o ~ Pr(o|s’,a)."""
           raise NotImplementedError
       def argmax(self, next_state, action):
           """Returns o* = argmax_o Pr(o|s’,a)."""
           raise NotImplementedError
       def get_all_observations(self, *args, **kwargs):
           """Returns a set of all possible
           observations, if feasible."""
           raise NotImplementedError

It is up to the user to choose which subset of these functions to implement,
depending on the domain. These interfaces aim to remind users the essence of
models in POMDPs.

Figure A.1: (1) Core Interfaces in the pomdp_py framework; (2) POMDP control
flow implemented through interaction between the core interfaces.

To instantiate a POMDP, one provides parameters for the models, the initial
state of the environment, and the initial belief of the agent. For the Tiger
problem222https://h2r.github.io/pomdp-py/html/examples.tiger.html Kaelbling .
(1998), for example,

     s0 = random.choice(list(TigerProblem.STATES))
     b0 = pomdp_py.Histogram({State("tiger-left"): 0.5,
             State("tiger-right"): 0.5})
     tiger_problem = TigerProblem(..., s0, b0)

Here, TigerProblem is a POMDP whose constructor takes care of initializing the
Agent and Environment objects, and is instantiated by parameters (omitted),
initial state and belief. Note that it is entirely optional to explicitly
define a problem class such as TigerProblem in order to program the POMDP
control flow, discussed below.

To solve a POMDP with pomdp_py, here is the control flow one should implement
that contains the basic steps:

  1. 1.

Create a planner (Planner), i.e. a POMDP solver.

  2. 2.

Agent plans an action $a\in\mathcal{A}$ through the planner.

  3. 3.

Environment state transitions $s_{t}\rightarrow s_{t+1}$ according to its
transition model.

  4. 4.

Agent receives an observation $o_{t}$ and reward $r_{t}$ from the environment.

  5. 5.

Agent updates history and belief. $h_{t},b_{t}\rightarrow h_{t+1},b_{t+1}$,
where $h_{t+1}=h_{t}(a_{t},o_{t})$.

  6. 6.

Unless _termination condition_ is true, repeat steps 2-5.

The Planner interface is as follows. The planner may be updated given a real
action and a real observation, which is necessary for MCTS-based solvers.

    class Planner:
        def plan(self, agent):
            """The agent carries the information:
            Bt, ht, O,T,R/G, pi, needed for planning"""
            raise NotImplementedError
        def update(self, agent, action, observation):
            """Updates the planner based on real action
            and observation. Updates the agent belief
            accordingly if necessary. """
            pass

Code Organization. In a more complicated problem such as the Light-Dark domain
Platt Jr . (2010) or Multi-Object Search with fan-shaped sensors Wandzel .
(2019), it may be tricky to organize the code base and be consistent across
different problems. Below we provide a recommendation of the package structure
to use pomdp_py to guide the development and facilitate code sharing:

     - domain/
        - state.py        // State
        - action.py       // Action
        - observation.py  // Observation
        - ...
     - models/
        - transition_model.py   // TransitionModel
        - observation_model.py  // ObservationModel
        - reward_model.py       // RewardModel
        - policy_model.py       // PolicyModel
        - ...
    - agent/
        - agent.py  // Agent
        - ...
    - env/
        - env.py  // Environment
        - ...
     - problem.py  // POMDP

The recommendation is to separate code for domain, models, agent and
environment, and have simple generic filenames. As in the above tree, files
such as state.py or transition_model.py are self-evident in their role. The
problem.py file is where the specific implementation of the POMDP class is
defined, and where the logic of control flow is implemented. Refer to the
Multi-Object Search example in the documentation for more
detail333https://h2r.github.io/pomdp-py/html/examples.mos.html.

Object-Oriented POMDPs. OO-POMDP Wandzel . (2019) is a particular kind of
factored POMDP that factors the state and observation spaces into a set of $n$
objects. For instance, $\Pr(s^{\prime}|s,a)=\prod_{i}\Pr(s^{\prime}_{i}|s,a)$,
$i\in\\{1,\cdots,n\\}$. The belief space is also factored, which allows the
belief space to grow linearly instead of exponentially as the number of
objects increases. Each object is of a certain class and has a set of
attributes. The values of these attributes constitute the state of an object.
In pomdp_py, we provide interfaces to implement OO-POMDPs, which serves as an
example of extending the basic POMDP framework to create another class of
model. These interfaces include OOState, OOBelief, OOTransitionModel, etc.

Integration with ROS. ROS Quigley . (2009) is an open-source system that
builds a network connecting computing stations and robots, where _nodes_
interact with one another through publishing messages or making service
requests. It is typical to separate nodes that manage resources and controls
the robot from nodes that runs sophisticated algorithms. This is the case of
pomdp_py as well. The POMDP-related computations can be done on a node that
implements the POMDP control flow (see the six steps above). Inside this node,
when an action is selected by the Planner (step 1), the node can publish a
message to the nodes for robot control so that the robot can execute the
action (step 2). The environment state automatically updates in the real world
as a result of that action (step 3), and the node receives the sensor
measurements or other forms of observations through subscribed topics (step
4), and performs belief update (step 5). This process is repeated until
termination condition is met (step 6). ROS provides a package rospy which
eases the integration of the POMDP control flow with the robot system.

### 5 Summary

We present a POMDP library, named pomdp_py, that brings together accessibility
to programmers through Python as well as performance through Cython, with an
intuitive design and straightforward integration with ROS. The programming
model is designed to encourage organized development and code sharing within a
community, and it has potential to support research besides POMDP planning,
including reinforcement learning, transfer learning, and multi-agent systems.

## REFERENCES

## References

  * Abel . (2021) abel2021expressivityAbel, D., Dabney, W., Harutyunyan, A., Ho, MK., Littman, M., Precup, D. Singh, S.  2021\.  On the expressivity of markov reward On the expressivity of markov reward.  Advances in Neural Information Processing Systems347799–7812.
  * J. Ahn . (2022) ahn2022coordinationAhn, J., Kim, C. Nam, C.  2022\.  Coordination of two robotic manipulators for object retrieval in clutter Coordination of two robotic manipulators for object retrieval in clutter.  2022 International Conference on Robotics and Automation (ICRA) 2022 international conference on robotics and automation (icra) ( 1039–1045).
  * M. Ahn . (2022) ahn2022canAhn, M., Brohan, A., Brown, N., Chebotar, Y., Cortes, O., David, B.others  2022\.  Do as i can, not as i say: Grounding language in robotic affordances Do as i can, not as i say: Grounding language in robotic affordances.  arXiv preprint arXiv:2204.01691.
  * Anderson . (2018) anderson2018evaluationAnderson, P., Chang, A., Chaplot, DS., Dosovitskiy, A., Gupta, S., Koltun, V.others  2018\.  On evaluation of embodied navigation agents On evaluation of embodied navigation agents.  arXiv preprint arXiv:1807.06757.
  * Andreopoulos . (2010) andreopoulos2010activeAndreopoulos, A., Hasler, S., Wersing, H., Janssen, H., Tsotsos, JK. Korner, E.  2010\.  Active 3D object localization using a humanoid robot Active 3d object localization using a humanoid robot.  IEEE Transactions on Robotics27147–64.
  * APPL (2009) pomdpxformatAPPL, P.  2009\.  PomdpX File Format (version 1.0). Pomdpx file format (version 1.0).  https://bigbird.comp.nus.edu.sg/pmwiki/farm/appl/index.php?n=Main.PomdpXDocumentation.
  * Arulkumaran . (2017) arulkumaran2017deepArulkumaran, K., Deisenroth, MP., Brundage, M. Bharath, AA.  2017\.  Deep reinforcement learning: A brief survey Deep reinforcement learning: A brief survey.  IEEE Signal Processing Magazine34626–38.
  * Åström (1965) aastrom1965optimalÅström, KJ.  1965\.  Optimal control of Markov processes with incomplete state information Optimal control of markov processes with incomplete state information.  Journal of mathematical analysis and applications101174–205.
  * Atanasov . (2014) atanasov2014nonmyopicAtanasov, N., Sankaran, B., Le Ny, J., Pappas, GJ. Daniilidis, K.  2014\.  Nonmyopic view planning for active object classification and pose estimation Nonmyopic view planning for active object classification and pose estimation.  IEEE Transactions on Robotics3051078–1090.
  * Auer . (2002) auer2002finiteAuer, P., Cesa-Bianchi, N. Fischer, P.  2002\.  Finite-time analysis of the multiarmed bandit problem Finite-time analysis of the multiarmed bandit problem.  Machine learning472-3235–256.
  * Aydemir . (2013) aydemir2013activeAydemir, A., Pronobis, A., Göbelbecker, M. Jensfelt, P.  2013\.  Active visual object search in unknown environments using uncertain semantics Active visual object search in unknown environments using uncertain semantics.  IEEE Transactions on Robotics294986–1002.
  * Aydemir . (2011) aydemir2011searchAydemir, A., Sjöö, K., Folkesson, J., Pronobis, A. Jensfelt, P.  2011\.  Search in the real world: Active visual object search based on spatial relations Search in the real world: Active visual object search based on spatial relations.  2011 IEEE International Conference on Robotics and Automation 2011 ieee international conference on robotics and automation ( 2818–2824).
  * Bai . (2016) bai2016markovianBai, A., Srivastava, S. Russell, SJ.  2016\.  Markovian State and Action Abstractions for MDPs via Hierarchical MCTS. Markovian state and action abstractions for MDPs via hierarchical MCTS.  IJCAI. Ijcai.
  * Bargiacchi (2014) aitoolboxBargiacchi, E.  2014\.  AI-Toolbox: A C++ framework for MDPs and POMDPs with Python bindings. Ai-toolbox: A c++ framework for mdps and pomdps with python bindings.  https://github.com/Svalorzen/AI-Toolbox.
  * Batra . (2020) batra2020objectnavBatra, D., Gokaslan, A., Kembhavi, A., Maksymets, O., Mottaghi, R., Savva, M.Wijmans, E.  2020\.  Objectnav revisited: On evaluation of embodied agents navigating to objects Objectnav revisited: On evaluation of embodied agents navigating to objects.  arXiv preprint arXiv:2006.13171.
  * Battistuzzi . (2021) battistuzzi2021ethicalBattistuzzi, L., Recchiuto, CT. Sgorbissa, A.  2021\.  Ethical concerns in rescue robotics: a scoping review Ethical concerns in rescue robotics: a scoping review.  Ethics and Information Technology234863–875.
  * Baxter . (2007) baxter2007multiBaxter, JL., Burke, E., Garibaldi, JM. Norman, M.  2007\.  Multi-robot search and rescue: A potential field based approach Multi-robot search and rescue: A potential field based approach.  Autonomous robots and agents Autonomous robots and agents ( 9–16).  Springer.
  * Behnel . (2011) behnel2011cythonBehnel, S., Bradshaw, R., Citro, C., Dalcin, L., Seljebotn, DS. Smith, K.  2011\.  Cython: The best of both worlds Cython: The best of both worlds.  Computing in Science & Engineering13231–39.
  * Bejjani . (2021) bejjani2021occlusionBejjani, W., Agboh, WC., Dogar, MR. Leonetti, M.  2021\.  Occlusion-aware search for object retrieval in clutter Occlusion-aware search for object retrieval in clutter.  2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2021 ieee/rsj international conference on intelligent robots and systems (iros) ( 4678–4685).
  * Bekkerman Tabrikian (2006) bekkerman2006targetBekkerman, I. Tabrikian, J.  2006\.  Target detection and localization using MIMO radars and sonars Target detection and localization using MIMO radars and sonars.  IEEE Transactions on Signal Processing54103873–3883.
  * Bisk . (2018) bisk2018learningBisk, Y., Shih, K., Choi, Y. Marcu, D.  2018\.  Learning interpretable spatial operations in a rich 3D blocks world Learning interpretable spatial operations in a rich 3D blocks world.  Proceedings of the AAAI Conference on Artificial Intelligence. Proceedings of the aaai conference on artificial intelligence.
  * Bisk . (2016) bisk2016naturalBisk, Y., Yuret, D. Marcu, D.  2016\.  Natural language communication with robots Natural language communication with robots.  Proc. of NAACL. Proc. of naacl.
  * Blukis, Brukhim . (2018) Blukis:18droneBlukis, V., Brukhim, N., Bennett, A., Knepper, RA. Artzi, Y.  2018\.  Following High-level Navigation Instructions on a Simulated Quadcopter with Imitation Learning Following high-level navigation instructions on a simulated quadcopter with imitation learning.  Proceedings of the Robotics: Science and Systems Conference. Proceedings of the robotics: Science and systems conference.
  * Blukis . (2020) Blukis2020:fewshot-droneBlukis, V., Knepper, RA. Artzi, Y.  2020\.  Few-shot Object Grounding and Mapping for Natural Language Robot Instruction Following Few-shot object grounding and mapping for natural language robot instruction following.  Proceedings of the Conference on Robot Learning. Proceedings of the conference on robot learning.
  * Blukis, Misra . (2018) blukis2018mappingBlukis, V., Misra, D., Knepper, RA. Artzi, Y.  2018\.  Mapping navigation instructions to continuous control actions with position-visitation prediction Mapping navigation instructions to continuous control actions with position-visitation prediction.  Conference on Robot Learning. Conference on robot learning.
  * Blukis . (2019) blukis2019learningBlukis, V., Terme, Y., Niklasson, E., Knepper, RA. Artzi, Y.  2019\.  Learning to Map Natural Language Instructions to Physical Quadcopter Control using Simulated Flight Learning to map natural language instructions to physical quadcopter control using simulated flight.  Conference on Robot Learning (CoRL). Conference on robot learning (corl).
  * Bono . (2022) bono2022swarmBono, A., D’Alfonso, L., Fedele, G. Gazi, V.  2022\.  A Swarm Model for Target Capturing in a Polygonal Strip A swarm model for target capturing in a polygonal strip.  2022 8th International Conference on Control, Decision and Information Technologies (CoDIT) 2022 8th international conference on control, decision and information technologies (codit) ( 1, 297–302).
  * Boston Dynamics Spot (2019) bdspotBoston Dynamics Spot. Boston Dynamics Spot.  2019\.  https://www.bostondynamics.com/products/spot.  Accessed: 2019
  * Bourque (2019) BOURQUE201945Bourque, FA.  2019\.  Solving the moving target search problem using indistinguishable searchers Solving the moving target search problem using indistinguishable searchers.  European Journal of Operational Research275145-52.  https://www.sciencedirect.com/science/article/pii/S0377221718309317 https://doi.org/10.1016/j.ejor.2018.11.006
  * Bowling . (2022) bowling2022settlingBowling, M., Martin, JD., Abel, D. Dabney, W.  2022\.  Settling the Reward Hypothesis Settling the reward hypothesis.  arXiv preprint arXiv:2212.10420.
  * Briney (2004) briney2004stateBriney, C.  2004\.  State of the industry State of the industry.  Global Cosmetic Industry17226.
  * Browne . (2012) browne2012surveyBrowne, CB., Powley, E., Whitehouse, D., Lucas, SM., Cowling, PI., Rohlfshagen, P.Colton, S.  2012\.  A survey of monte carlo tree search methods A survey of monte carlo tree search methods.  IEEE Transactions on Computational Intelligence and AI in games411–43.
  * Caicedo Lazebnik (2015) caicedo2015activeCaicedo, JC. Lazebnik, S.  2015\.  Active object localization with deep reinforcement learning Active object localization with deep reinforcement learning.  Proceedings of the IEEE international conference on computer vision Proceedings of the ieee international conference on computer vision ( 2488–2496).
  * Canal . (2019) canal2019probabilisticCanal, G., Cashmore, M., Krivić, S., Alenyà, G., Magazzeni, D. Torras, C.  2019\.  Probabilistic Planning for Robotics with ROSPlan Probabilistic planning for robotics with rosplan.  Annual Conference Towards Autonomous Robotic Systems Annual conference towards autonomous robotic systems ( 236–250).
  * Cashmore . (2015) cashmore2015rosplanCashmore, M., Fox, M., Long, D., Magazzeni, D., Ridder, B., Carrera, A.Carreras, M.  2015\.  Rosplan: Planning in the robot operating system Rosplan: Planning in the robot operating system.  Twenty-Fifth International Conference on Automated Planning and Scheduling. Twenty-fifth international conference on automated planning and scheduling.
  * Cassandr (2003) pomdpfileformatCassandr, AR.  2003\.  POMDP File Format. Pomdp file format.  http://www.pomdp.org/code/pomdp-file-spec.html.
  * Cassandra . (1994) cassandra1994actingCassandra, AR., Kaelbling, LP. Littman, ML.  1994\.  Acting optimally in partially observable stochastic domains Acting optimally in partially observable stochastic domains.  Aaai Aaai ( 94, 1023–1028).
  * Chang . (2020) chang2020semanticChang, M., Gupta, A. Gupta, S.  2020\.  Semantic visual navigation by watching youtube videos Semantic visual navigation by watching youtube videos.  Advances in Neural Information Processing Systems334283–4294.
  * Chaplot . (2020) chaplot2020objectChaplot, DS., Gandhi, D., Gupta, A. Salakhutdinov, R.  2020\.  Object Goal Navigation using Goal-Oriented Semantic Exploration Object goal navigation using goal-oriented semantic exploration.  Neural Information Processing Systems. Neural information processing systems.
  * CP. Chen . (2013) chen2013localChen, CP., Li, H., Wei, Y., Xia, T. Tang, YY.  2013\.  A local contrast method for small infrared target detection A local contrast method for small infrared target detection.  IEEE transactions on geoscience and remote sensing521574–581.
  * K. Chen . (2019) Savarese-RSS-19Chen, K., de Vicente, JP., Sepulveda, G., Xia, F., Soto, A., Vazquez, M. Savarese, S.  2019June.  A Behavioral Approach to Visual Navigation with Graph Localization Networks A behavioral approach to visual navigation with graph localization networks.  Proceedings of Robotics: Science and Systems. Proceedings of robotics: Science and systems.  FreiburgimBreisgau, Germany.  10.15607/RSS.2019.XV.010
  * X. Chen Lee (2013) chen2013visualChen, X. Lee, S.  2013\.  Visual search of an object in cluttered environments for robotic errand service Visual search of an object in cluttered environments for robotic errand service.  2013 IEEE International Conference on Systems, Man, and Cybernetics 2013 ieee international conference on systems, man, and cybernetics ( 4060–4065).
  * Chitta (2016) chitta2016moveitChitta, S.  2016\.  MoveIt!: an introduction Moveit!: an introduction.  Robot Operating System (ROS) Robot operating system (ros) ( 3–27).  Springer.
  * Chowdhery . (2022) chowdhery2022palmChowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A.others  2022\.  Palm: Scaling language modeling with pathways Palm: Scaling language modeling with pathways.  arXiv preprint arXiv:2204.02311.
  * Chung . (2011) chung2011searchChung, TH., Hollinger, GA. Isler, V.  2011\.  Search and pursuit-evasion in mobile robotics Search and pursuit-evasion in mobile robotics.  Autonomous robots314299–316.
  * Czyzowicz . (2016) czyzowicz2016searchCzyzowicz, J., Georgiou, K., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J. Shende, S.  2016\.  Search on a line by byzantine robots Search on a line by byzantine robots.  arXiv preprint arXiv:1611.08209.
  * Dadgar . (2016) dadgar2016psoDadgar, M., Jafari, S. Hamzeh, A.  2016\.  A PSO-based multi-robot cooperation method for target searching in unknown environments A pso-based multi-robot cooperation method for target searching in unknown environments.  Neurocomputing17762–74.
  * Dames (2020) dames2020distributedDames, PM.  2020\.  Distributed multi-target search and tracking using the PHD filter Distributed multi-target search and tracking using the phd filter.  Autonomous robots443673–689.
  * Danielczuk . (2019) danielczuk2019mechanicalDanielczuk, M., Kurenkov, A., Balakrishna, A., Matl, M., Wang, D., Martín-Martín, R.Goldberg, K.  2019\.  Mechanical search: Multi-step retrieval of a target object occluded by clutter Mechanical search: Multi-step retrieval of a target object occluded by clutter.  2019 International Conference on Robotics and Automation (ICRA) 2019 International Conference on Robotics and Automation (ICRA) ( 1614–1621).
  * Das . (2017) das2017visualDas, A., Kottur, S., Gupta, K., Singh, A., Yadav, D., Moura, JM.Batra, D.  2017\.  Visual dialog Visual dialog.  Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Proceedings of the ieee conference on computer vision and pattern recognition ( 326–335).
  * Deitke . (2020) deitke2020robothorDeitke, M., Han, W., Herrasti, A., Kembhavi, A., Kolve, E., Mottaghi, R.others  2020\.  Robothor: An open simulation-to-real embodied ai platform Robothor: An open simulation-to-real embodied ai platform.  Proceedings of the IEEE/CVF conference on computer vision and pattern recognition Proceedings of the ieee/cvf conference on computer vision and pattern recognition ( 3164–3174).
  * Deitke . (2022) deitke2022procthorDeitke, M., VanderBilt, E., Herrasti, A., Weihs, L., Salvador, J., Ehsani, K.others  2022\.  ProcTHOR: Large-Scale Embodied AI Using Procedural Generation ProcTHOR: Large-Scale Embodied AI Using Procedural Generation.  Conference on Neural Information Processing Systems (NeurIPS). Conference on neural information processing systems (NeurIPS).
  * Delmerico . (2018) delmerico2018comparisonDelmerico, J., Isler, S., Sabzevari, R. Scaramuzza, D.  2018\.  A comparison of volumetric information gain metrics for active 3D object reconstruction A comparison of volumetric information gain metrics for active 3d object reconstruction.  Autonomous Robots422197–208.
  * de Vries . (2018) de2018talkde Vries, H., Shuster, K., Batra, D., Parikh, D., Weston, J. Kiela, D.  2018\.  Talk the walk: Navigating new york city through grounded dialogue Talk the walk: Navigating new york city through grounded dialogue.  arXiv preprint arXiv:1807.03367.
  * Ding Castañón (2018) ding2018movingDing, H. Castañón, D.  2018\.  Moving Object Search with Multiple Agents Moving object search with multiple agents.  2018 IEEE Conference on Decision and Control (CDC) 2018 IEEE Conference on Decision and Control (CDC) ( 5746–5752).
  * Diuk . (2008) diuk2008objectDiuk, C., Cohen, A. Littman, ML.  2008\.  An object-oriented representation for efficient reinforcement learning An object-oriented representation for efficient reinforcement learning.  Proceedings of the 25th international conference on Machine learning Proceedings of the 25th international conference on machine learning ( 240–247).
  * Dobbie (1974) dobbie1974twoDobbie, JM.  1974\.  A two-cell model of search for a moving target A two-cell model of search for a moving target.  Operations Research22179–92.
  * Dogan Zengin (2006) dogan2006unmannedDogan, A. Zengin, U.  2006\.  Unmanned aerial vehicle dynamic-target pursuit by using probabilistic threat exposure map Unmanned aerial vehicle dynamic-target pursuit by using probabilistic threat exposure map.  Journal of guidance, control, and dynamics294944–954.
  * Dogar . (2014) dogar2014objectDogar, MR., Koval, MC., Tallavajhula, A. Srinivasa, SS.  2014\.  Object search by manipulation Object search by manipulation.  Autonomous Robots.
  * Doumanoglou . (2016) doumanoglou2016recoveringDoumanoglou, A., Kouskouridas, R., Malassiotis, S. Kim, TK.  2016\.  Recovering 6D object pose and predicting next-best-view in the crowd Recovering 6d object pose and predicting next-best-view in the crowd.  Proceedings of the IEEE conference on computer vision and pattern recognition Proceedings of the ieee conference on computer vision and pattern recognition ( 3583–3592).
  * Druon . (2020) druon2020visualDruon, R., Yoshiyasu, Y., Kanezaki, A. Watt, A.  2020\.  Visual object search by learning spatial context Visual object search by learning spatial context.  IEEE Robotics and Automation Letters521279–1286.
  * Du . (2021) du2021visionDu, G., Wang, K., Lian, S. Zhao, K.  2021\.  Vision-based robotic grasping from object localization, object pose estimation to grasp estimation for parallel grippers: a review Vision-based robotic grasping from object localization, object pose estimation to grasp estimation for parallel grippers: a review.  Artificial Intelligence Review5431677–1734.
  * Duncan Humphreys (1989) duncan1989visualDuncan, J. Humphreys, GW.  1989\.  Visual search and stimulus similarity. Visual search and stimulus similarity.  Psychological review963433.
  * Eaton Zadeh (1962) eaton1962optimalEaton, JH. Zadeh, L.  1962\.  Optimal pursuit strategies in discrete-state probabilistic systems Optimal pursuit strategies in discrete-state probabilistic systems.
  * Ebert . (2022) ebert2022hybridEbert, JT., Berlinger, F., Haghighat, B. Nagpal, R.  2022\.  A Hybrid PSO Algorithm for Multi-robot Target Search and Decision Awareness A hybrid PSO algorithm for multi-robot target search and decision awareness.  2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2022 ieee/rsj international conference on intelligent robots and systems (iros) ( 11520–11527).
  * Eckstein (2011) eckstein2011visualEckstein, MP.  2011\.  Visual search: A retrospective Visual search: A retrospective.  Journal of vision11514–14.
  * Egorov . (2017) egorov2017pomdpsEgorov, M., Sunberg, ZN., Balaban, E., Wheeler, TA., Gupta, JK. Kochenderfer, MJ.  2017\.  POMDPs. jl: A framework for sequential decision making under uncertainty Pomdps. jl: A framework for sequential decision making under uncertainty.  The Journal of Machine Learning Research181831–835.
  * Eismann . (2009) eismann2009automatedEismann, MT., Stocker, AD. Nasrabadi, NM.  2009\.  Automated hyperspectral cueing for civilian search and rescue Automated hyperspectral cueing for civilian search and rescue.  Proceedings of the IEEE9761031–1055.
  * Elfring . (2013) elfring2013activeElfring, J., Jansen, S., Molengraft, Rvd. Steinbuch, M.  2013\.  Active object search exploiting probabilistic object–object relations Active object search exploiting probabilistic object–object relations.  Robot Soccer World Cup Robot soccer world cup ( 13–24).
  * Emami . (2015) emami2015pomdpyEmami, P., Hamlet, AJ. Crane, C.  2015\.  POMDPy: An Extensible Framework for Implementing POMDPs in Python Pomdpy: An extensible framework for implementing pomdps in python.
  * Epic Games () unrealengineEpic Games.  .  Unreal Engine. Unreal Engine.  https://www.unrealengine.com
  * Erickson (1964) erickson1964visualErickson, RA.  1964\.  Visual search for targets: Laboratory experiments Visual search for targets: Laboratory experiments .  NAVAL ORDNANCE TEST STATION CHINA LAKE CA.
  * Fasola Mataric (2013) fasola2013irosFasola, J. Mataric, MJ.  2013\.  Using semantic fields to model dynamic spatial relations in a robot architecture for natural language instruction of service robots Using semantic fields to model dynamic spatial relations in a robot architecture for natural language instruction of service robots.  IEEE/RSJ International Conference on Intelligent Robots and Systems Ieee/rsj international conference on intelligent robots and systems ( 143–150).
  * Fasola Matarić (2013) Fasola2013UsingSSFasola, J. Matarić, MJ.  2013\.  Using spatial semantic and pragmatic fields to interpret natural language pick-and-place instructions for a mobile service robot Using spatial semantic and pragmatic fields to interpret natural language pick-and-place instructions for a mobile service robot.  International Conference on Social Robotics International conference on social robotics ( 501–510).
  * Fidan . (2013) fidan2013adaptiveFidan, B., Dasgupta, S. Anderson, BD.  2013\.  Adaptive range-measurement-based target pursuit Adaptive range-measurement-based target pursuit.  International Journal of Adaptive Control and Signal Processing271-266–81.
  * Gan . (2020) gan2020threedworldGan, C., Schwartz, J., Alter, S., Schrimpf, M., Traer, J., De Freitas, J.others  2020\.  Threedworld: A platform for interactive multi-modal physical simulation Threedworld: A platform for interactive multi-modal physical simulation.  arXiv preprint arXiv:2007.04954.
  * Garg . (2019) garg2019despotGarg, NP., Hsu, D. Lee, WS.  2019\.  DESPOT-$\alpha$: Online POMDP Planning With Large State And Observation Spaces DESPOT-$\alpha$: Online POMDP planning with large state and observation spaces.  Robotics: Science and Systems. Robotics: Science and systems.
  * Garvey (1976) garvey1976Garvey, TD.  1976\.  Perceptual strategies for purposive vision Perceptual strategies for purposive vision.  Thesis Ph.D. Stanford University.
  * Gelenbe Cao (1998) gelenbe1998autonomousGelenbe, E. Cao, Y.  1998\.  Autonomous search for mines Autonomous search for mines.  European Journal of Operational Research1082319–333.
  * Gervet . (2022) gervet2022navigatingGervet, T., Chintala, S., Batra, D., Malik, J. Chaplot, DS.  2022\.  Navigating to Objects in the Real World Navigating to objects in the real world.  arXiv preprint arXiv:2212.00922.
  * Giuliari . (2021) giuliari2021pomp++Giuliari, F., Castellini, A., Berra, R., Del Bue, A., Farinelli, A., Cristani, M.Wang, Y.  2021\.  POMP++: Pomcp-based Active Visual Search in unknown indoor environments Pomp++: Pomcp-based active visual search in unknown indoor environments.  2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2021 ieee/rsj international conference on intelligent robots and systems (iros) ( 1523–1530).
  * Goldsmith Robinett (1998) goldsmith1998collectiveGoldsmith, SY. Robinett, R.  1998\.  Collective search by mobile robots using alpha-beta coordination Collective search by mobile robots using alpha-beta coordination.  International Workshop on Collective Robotics International workshop on collective robotics ( 135–146).
  * Gordon . (2018) gordon2018iqaGordon, D., Kembhavi, A., Rastegari, M., Redmon, J., Fox, D. Farhadi, A.  2018\.  Iqa: Visual question answering in interactive environments Iqa: Visual question answering in interactive environments.  Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Proceedings of the ieee conference on computer vision and pattern recognition ( 4089–4098).
  * gPRC Documentation () grpcgPRC Documentation. gPRC documentation.  .  https://grpc.io/docs/.  Accessed: 2022
  * Grisetti . (2007) grisetti2007improvedGrisetti, G., Stachniss, C. Burgard, W.  2007\.  Improved techniques for grid mapping with rao-blackwellized particle filters Improved techniques for grid mapping with rao-blackwellized particle filters.  IEEE transactions on Robotics23134–46.
  * Gupta . (2017) gupta2017cognitiveGupta, S., Davidson, J., Levine, S., Sukthankar, R. Malik, J.  2017\.  Cognitive mapping and planning for visual navigation Cognitive mapping and planning for visual navigation.  Proceedings of the IEEE conference on computer vision and pattern recognition Proceedings of the ieee conference on computer vision and pattern recognition ( 2616–2625).
  * Harbers . (2017) harbers2017exploringHarbers, M., de Greeff, J., Kruijff-Korbayová, I., Neerincx, MA. Hindriks, KV.  2017\.  Exploring the ethical landscape of robot-assisted search and rescue Exploring the ethical landscape of robot-assisted search and rescue.  A World with Robots A world with robots ( 93–107).  Springer.
  * Hayward Tarr (1995) hayward1995spatialHayward, WG. Tarr, MJ.  1995\.  Spatial language and spatial representation Spatial language and spatial representation.  Cognition55139–84.
  * He . (2017) he2017maskHe, K., Gkioxari, G., Dollár, P. Girshick, R.  2017\.  Mask r-cnn Mask r-cnn.  Proceedings of the IEEE international conference on computer vision Proceedings of the ieee international conference on computer vision ( 2961–2969).
  * Hemachandra . (2015) hemachandra2015learningHemachandra, S., Duvallet, F., Howard, TM., Roy, N., Stentz, A. Walter, MR.  2015\.  Learning models for following natural language directions in unknown environments Learning models for following natural language directions in unknown environments.  IEEE International Conference on Robotics and Automation (ICRA) Ieee international conference on robotics and automation (icra) ( 5608–5615).
  * Hereford Siebold (2010) hereford2010bioHereford, JM. Siebold, MA.  2010\.  Bio-inspired search strategies for robot swarms Bio-inspired search strategies for robot swarms.  Swarm robotics, from biology to robotics1–27.
  * Hernandez . (2021) hernandez2021searchingHernandez, AC., Durner, M., Gomez, C., Grixa, I., Teikmanis, O., Marton, ZC. Barber, R.  2021\.  Searching for objects in human living environments based on relevant inferred and mined priors Searching for objects in human living environments based on relevant inferred and mined priors.  2021 European Conference on Mobile Robots (ECMR) 2021 european conference on mobile robots (ecmr) ( 1–7).
  * Hess . (2016) hess2016realHess, W., Kohler, D., Rapp, H. Andor, D.  2016\.  Real-time loop closure in 2D LIDAR SLAM Real-time loop closure in 2d lidar slam.  2016 IEEE international conference on robotics and automation (ICRA) 2016 ieee international conference on robotics and automation (icra) ( 1271–1278).
  * Ho . (1965) ho1965differentialHo, Y., Bryson, A. Baron, S.  1965\.  Differential games and optimal pursuit-evasion strategies Differential games and optimal pursuit-evasion strategies.  IEEE Transactions on Automatic Control104385–389.
  * Hollinger . (2009) hollinger2009efficientHollinger, G., Singh, S., Djugash, J. Kehagias, A.  2009\.  Efficient multi-robot search for a moving target Efficient multi-robot search for a moving target.  The International Journal of Robotics Research282201–219.
  * Holzherr . (2021) holzherr2021efficientHolzherr, L., Förster, J., Breyer, M., Nieto, J., Siegwart, R. Chung, JJ.  2021\.  Efficient Multi-scale POMDPs for Robotic Object Search and Delivery Efficient multi-scale POMDPs for robotic object search and delivery.  2021 IEEE International Conference on Robotics and Automation (ICRA) 2021 ieee international conference on robotics and automation (icra) ( 6585–6591).
  * Honnibal Montani (2017) spaCy2Honnibal, M. Montani, I.  2017\.  spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing. spaCy 2: Natural language understanding with Bloom embeddings, convolutional neural networks and incremental parsing.  To appear
  * Hornung . (2013) hornung2013octomapHornung, A., Wurm, KM., Bennewitz, M., Stachniss, C. Burgard, W.  2013\.  OctoMap: An efficient probabilistic 3D mapping framework based on octrees Octomap: An efficient probabilistic 3d mapping framework based on octrees.  Autonomous robots343189–206.
  * Huang . (2022) huang2022mechanicalHuang, H., Danielczuk, M., Kim, CM., Fu, L., Tam, Z., Ichnowski, J.Goldberg, K.  2022\.  Mechanical Search on Shelves using a Novel “Bluction” Tool Mechanical search on shelves using a novel “bluction” tool.  2022 International Conference on Robotics and Automation (ICRA) 2022 international conference on robotics and automation (icra) ( 6158–6164).
  * Huang . (2021) huang2021mechanicalHuang, H., Dominguez-Kuhne, M., Satish, V., Danielczuk, M., Sanders, K., Ichnowski, J.Goldberg, K.  2021\.  Mechanical search on shelves using lateral access x-ray Mechanical search on shelves using lateral access x-ray.  2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) ( 2045–2052).
  * Hung . (2009) hung2009towardsHung, V., Elvir, M., Gonzalez, A. DeMara, R.  2009\.  Towards a method for evaluating naturalness in conversational dialog systems Towards a method for evaluating naturalness in conversational dialog systems.  2009 IEEE international conference on systems, man and cybernetics 2009 ieee international conference on systems, man and cybernetics ( 1236–1241).
  * Idrees . (2020) idrees2020robomemIdrees, I., Reiss, SP. Tellex, S.  2020\.  Robomem: Giving long term memory to robots Robomem: Giving long term memory to robots.  arXiv preprint arXiv:2003.10553.
  * Isaza . (2008) isaza2008coverIsaza, AIA., Lu, J., Bulitko, V. Greiner, R.  2008\.  A cover-based approach to multi-agent moving target pursuit A cover-based approach to multi-agent moving target pursuit.  Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment Proceedings of the aaai conference on artificial intelligence and interactive digital entertainment ( 4, 54–59).
  * Ishida Korf (1991) ishida1991movingIshida, T. Korf, RE.  1991\.  Moving Target Search. Moving target search.  IJCAI Ijcai ( 91, 204–210).
  * Izquierdo-Cordova . (2016) izquierdo2016searchingIzquierdo-Cordova, R., Morales, EF., Sucar, LE. Murrieta-Cid, R.  2016\.  Searching objects in known environments: Empowering simple heuristic strategies Searching objects in known environments: Empowering simple heuristic strategies.  Robot World Cup Robot world cup ( 380–391).
  * Jain . (2019) sotp2019aclJain, V., Magalhaes, G., Ku, A., Vaswani, A., Ie, E. Baldridge, J.  2019\.  Stay on the Path: Instruction Fidelity in Vision-and-Language Navigation Stay on the Path: Instruction Fidelity in Vision-and-Language Navigation.  Proc. of ACL. Proc. of acl.
  * Janner . (2018) janner2018representationJanner, M., Narasimhan, K. Barzilay, R.  2018\.  Representation learning for grounded spatial reasoning Representation learning for grounded spatial reasoning.  Transactions of the Association for Computational Linguistics649–61.
  * Jocher . (2020) glenn_jocher_2020_4154370Jocher, G., Stoken, A., Borovec, J., NanoCode012, ChristopherSTAN, Changyu, L.Rai, P.  202010\.  ultralytics/yolov5: v3.1 - Bug Fixes and Performance Improvements. ultralytics/yolov5: v3.1 - Bug Fixes and Performance Improvements.  Zenodo.  https://doi.org/10.5281/zenodo.4154370 10.5281/zenodo.4154370
  * Joho . (2011) joho2011learningJoho, D., Senk, M. Burgard, W.  2011\.  Learning search heuristics for finding objects in structured environments Learning search heuristics for finding objects in structured environments.  Robotics and Autonomous Systems595319–328.
  * Kaelbling . (1998) kaelbling1998planningKaelbling, LP., Littman, ML. Cassandra, AR.  1998\.  Planning and acting in partially observable stochastic domains Planning and acting in partially observable stochastic domains.  Artificial intelligence1011-299–134.
  * Kam . (2015) kam2015rvizKam, HR., Lee, SH., Park, T. Kim, CH.  2015\.  Rviz: a toolkit for real domain data visualization Rviz: a toolkit for real domain data visualization.  Telecommunication Systems602337–345.
  * Kingma Ba (2015) kingma2014adamKingma, DP. Ba, J.  2015\.  Adam: A method for stochastic optimization Adam: A method for stochastic optimization.  International Conference on Learning Representations. International conference on learning representations.
  * Kinova MOVO (2017) movoKinova MOVO. Kinova MOVO.  2017\.  https://kinovarobotics.github.io/kinova-movo/Concepts/c_movo_hardware_overview.html.  Accessed: 2017
  * Kochenderfer (2015) kochenderfer2015decisionKochenderfer, MJ.  2015\.  Decision making under uncertainty: theory and application Decision making under uncertainty: theory and application.  MIT press.
  * Kocsis Szepesvári (2006) kocsis2006banditKocsis, L. Szepesvári, C.  2006\.  Bandit based Monte-Carlo planning Bandit based Monte-Carlo planning.  European Conference on Machine Learning. European Conference on Machine Learning.
  * Kollar Roy (2009) kollar2009utilizingKollar, T. Roy, N.  2009\.  Utilizing object-object and object-scene context when planning to find things Utilizing object-object and object-scene context when planning to find things.  IEEE International Conference on Robotics and Automation IEEE International Conference on Robotics and Automation ( 2168–2173).
  * Kollar . (2010) Kollar2010TowardUNInstructionFollowingKollar, T., Tellex, S., Roy, D. Roy, N.  2010\.  Toward understanding natural language directions Toward understanding natural language directions.  2010 5th ACM/IEEE International Conference on Human-Robot Interaction (HRI). 2010 5th acm/ieee international conference on human-robot interaction (hri).
  * Kolve . (2017) kolve2017ai2Kolve, E., Mottaghi, R., Han, W., VanderBilt, E., Weihs, L., Herrasti, A.Farhadi, A.  2017\.  AI2-THOR: An Interactive 3D Environment for Visual AI AI2-THOR: An Interactive 3D Environment for Visual AI.  arXiv preprint arXiv:1712.05474.
  * Koopman (1956) koopman1956theoryKoopman, BO.  1956\.  The theory of search. II. Target detection The theory of search. II. Target detection.  Operations research45503–531.
  * Kulich . (2015) kulich2015comparisonKulich, M., Juchelka, T. Přeučil, L.  2015\.  Comparison of exploration strategies for multi-robot search Comparison of exploration strategies for multi-robot search.  Acta Polytechnica553162–168.
  * Kurenkov . (2020) kurenkov2020visuomotorKurenkov, A., Taglic, J., Kulkarni, R., Dominguez-Kuhne, M., Garg, A., Martín-Martín, R. Savarese, S.  2020\.  Visuomotor mechanical search: Learning to retrieve target objects in clutter Visuomotor mechanical search: Learning to retrieve target objects in clutter.  2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) ( 8408–8414).
  * Kurniawati (2022) kurniawati2022partiallyKurniawati, H.  2022\.  Partially Observable Markov Decision Processes and Robotics Partially observable markov decision processes and robotics.  Annual Review of Control, Robotics, and Autonomous Systems5.
  * Kurniawati . (2008) kurniawati2008sarsopKurniawati, H., Hsu, D. Lee, WS.  2008\.  Sarsop: Efficient point-based pomdp planning by approximating optimally reachable belief spaces. Sarsop: Efficient point-based pomdp planning by approximating optimally reachable belief spaces.  Robotics: Science and systems Robotics: Science and systems ( 2008).
  * Landau Jackendoff (1993) landau1993whatwhereLandau, B. Jackendoff, R.  1993\.  “What” and “where” in spatial language and spatial cognition “what” and “where” in spatial language and spatial cognition.  Behavioral and Brain Sciences16217-238.  10.1017/S0140525X00029733
  * Lauri . (2022) lauri2022partiallyLauri, M., Hsu, D. Pajarinen, J.  2022\.  Partially Observable Markov Decision Processes in Robotics: A Survey Partially observable markov decision processes in robotics: A survey.  IEEE Transactions on Robotics.
  * JK. Li . (2016) li2016actLi, JK., Hsu, D. Lee, WS.  2016\.  Act to see and see to act: POMDP planning for objects search in clutter Act to see and see to act: POMDP planning for objects search in clutter.  2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
  * L. Li . (2006) li2006towardsLi, L., Walsh, TJ. Littman, ML.  2006\.  Towards a Unified Theory of State Abstraction for MDPs. Towards a unified theory of state abstraction for MDPs.  ISAIM. Isaim.
  * Y. Li . (2022) li2022remoteLi, Y., Ma, Y., Huo, X. Wu, X.  2022\.  Remote object navigation for service robots using hierarchical knowledge graph in human-centered environments Remote object navigation for service robots using hierarchical knowledge graph in human-centered environments.  Intelligent Service Robotics154459–473.
  * Liang . (2021) liang2021sscnavLiang, Y., Chen, B. Song, S.  2021\.  Sscnav: Confidence-aware semantic scene completion for visual semantic navigation Sscnav: Confidence-aware semantic scene completion for visual semantic navigation.  2021 IEEE International Conference on Robotics and Automation (ICRA) 2021 IEEE International Conference on Robotics and Automation (ICRA) ( 13194–13200).
  * TY. Lin . (2014) lin2014microsoftLin, TY., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D.Zitnick, CL.  2014\.  Microsoft COCO: Common objects in context Microsoft COCO: Common objects in context.  European Conference on Computer Vision European Conference on Computer Vision ( 740–755).
  * YC. Lin . (2015) lin2015planningLin, YC., Wei, ST., Yang, SA. Fu, LC.  2015\.  Planning on searching occluded target object with a mobile robot manipulator Planning on searching occluded target object with a mobile robot manipulator.  2015 IEEE International Conference on Robotics and Automation (ICRA) 2015 IEEE International Conference on Robotics and Automation (ICRA) ( 3110–3115).
  * Littman (1996) littman1996algorithmsLittman, ML.  1996\.  Algorithms for sequential decision-making Algorithms for sequential decision-making.  Brown University.
  * Littman (2009) littman2009tutorialLittman, ML.  2009\.  A tutorial on partially observable Markov decision processes A tutorial on partially observable markov decision processes.  Journal of Mathematical Psychology533119–125.
  * MY. Liu . (2012) liu2012fastLiu, MY., Tuzel, O., Veeraraghavan, A., Taguchi, Y., Marks, TK. Chellappa, R.  2012\.  Fast object localization and pose estimation in heavy clutter for robotic bin picking Fast object localization and pose estimation in heavy clutter for robotic bin picking.  The International Journal of Robotics Research318951–973.
  * W. Liu . (2021) liu2021learningLiu, W., Bansal, D., Daruna, AA. Chernova, S.  2021\.  Learning Instance-Level N-Ary Semantic Knowledge At Scale For Robots Operating in Everyday Environments. Learning instance-level n-ary semantic knowledge at scale for robots operating in everyday environments.  Robotics: Science and Systems. Robotics: Science and systems.
  * Loghmani . (2018) loghmani2018towardsLoghmani, MR., Patten, T. Vincze, M.  2018\.  Towards socially assistive robots for elderly: An end-to-end object search framework Towards socially assistive robots for elderly: An end-to-end object search framework.  2018 IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops). 2018 ieee international conference on pervasive computing and communications workshops (percom workshops).
  * Lorbach . (2014) lorbach2014priorLorbach, M., Höfer, S. Brock, O.  2014\.  Prior-assisted propagation of spatial information for object search Prior-assisted propagation of spatial information for object search.  2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2014 ieee/rsj international conference on intelligent robots and systems.
  * Lu . (2018) lu2018targetLu, Y., Wang, Z., Tang, Z. Javidi, T.  2018\.  Target localization with drones using mobile cnns Target localization with drones using mobile cnns.  2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2018 ieee/rsj international conference on intelligent robots and systems (iros) ( 2566–2573).
  * Luo . (2019) luo2019endLuo, W., Sun, P., Zhong, F., Liu, W., Zhang, T. Wang, Y.  2019\.  End-to-end active object tracking and its real-world deployment via reinforcement learning End-to-end active object tracking and its real-world deployment via reinforcement learning.  IEEE transactions on pattern analysis and machine intelligence4261317–1332.
  * Macenski . (2022) ros2Macenski, S., Foote, T., Gerkey, B., Lalancette, C. Woodall, W.  2022\.  Robot Operating System 2: Design, architecture, and uses in the wild Robot operating system 2: Design, architecture, and uses in the wild.  Science Robotics766eabm6074.  https://www.science.org/doi/abs/10.1126/scirobotics.abm6074 10.1126/scirobotics.abm6074
  * Macenski . (2020) macenski2020marathonMacenski, S., Martín, F., White, R. Clavero, JG.  2020\.  The marathon 2: A navigation system The marathon 2: A navigation system.  2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2020 IEEE/RSJ international conference on intelligent robots and systems (iros) ( 2718–2725).
  * Madani . (1999) madani1999undecidabilityMadani, O., Hanks, S. Condon, A.  1999\.  On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems On the undecidability of probabilistic planning and infinite-horizon partially observable markov decision problems.  AAAI/IAAI Aaai/iaai ( 541–548).
  * Majid . (2004) majid2004canMajid, A., Bowerman, M., Kita, S., Haun, DB. Levinson, SC.  2004\.  Can language restructure cognition? The case for space Can language restructure cognition? The case for space.  Trends in cognitive sciences83108–114.
  * Mangel (1981) mangel1981searchMangel, M.  1981\.  Search for a randomly moving object Search for a randomly moving object.  SIAM Journal on Applied Mathematics402327–338.
  * Marjovi . (2009) marjovi2009multiMarjovi, A., Nunes, JG., Marques, L. De Almeida, A.  2009\.  Multi-robot exploration and fire searching Multi-robot exploration and fire searching.  2009 IEEE/RSJ International Conference on Intelligent Robots and Systems 2009 ieee/rsj international conference on intelligent robots and systems ( 1929–1934).
  * Mayo . (2021) mayo2021visualMayo, B., Hazan, T. Tal, A.  2021\.  Visual Navigation with Spatial Attention Visual navigation with spatial attention.  Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Proceedings of the ieee/cvf conference on computer vision and pattern recognition ( 16898–16907).
  * Merkel (2014) merkel2014dockerMerkel, D.  2014\.  Docker: lightweight linux containers for consistent development and deployment Docker: lightweight linux containers for consistent development and deployment.  Linux journal20142392.
  * Moldovan De Raedt (2014) moldovan2014occludedMoldovan, B. De Raedt, L.  2014\.  Occluded object search by relational affordances Occluded object search by relational affordances.  2014 IEEE International Conference on Robotics and Automation (ICRA) 2014 ieee international conference on robotics and automation (icra) ( 169–174).
  * Monsó . (2012) monso2012pomdpMonsó, P., Alenyà, G. Torras, C.  2012\.  Pomdp approach to robotized clothes separation Pomdp approach to robotized clothes separation.  2012 IEEE/RSJ International Conference on Intelligent Robots and Systems 2012 ieee/rsj international conference on intelligent robots and systems ( 1324–1329).
  * Montemerlo . (2003) montemerlo2003perspectivesMontemerlo, M., Roy, N. Thrun, S.  2003\.  Perspectives on standardization in mobile robot programming: The Carnegie Mellon navigation (CARMEN) toolkit Perspectives on standardization in mobile robot programming: The carnegie mellon navigation (carmen) toolkit.  Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No. 03CH37453) Proceedings 2003 ieee/rsj international conference on intelligent robots and systems (iros 2003)(cat. no. 03ch37453) ( 3, 2436–2441).
  * Mouromtsev . (2015) mouromtsev2015spokenMouromtsev, D., Kovriguina, L., Emelyanov, Y., Pavlov, D. Shipilo, A.  2015\.  From spoken language to ontology-driven dialogue management From spoken language to ontology-driven dialogue management.  International Conference on Text, Speech, and Dialogue International conference on text, speech, and dialogue ( 542–550).
  * Mousavi . (2016) mousavi2016deepMousavi, SS., Schukat, M. Howley, E.  2016\.  Deep reinforcement learning: an overview Deep reinforcement learning: an overview.  Proceedings of SAI Intelligent Systems Conference Proceedings of sai intelligent systems conference ( 426–440).
  * Mousavian . (2019) mousavian2019visualMousavian, A., Toshev, A., Fišer, M., Košecká, J., Wahid, A. Davidson, J.  2019\.  Visual representations for semantic target driven navigation Visual representations for semantic target driven navigation.  2019 International Conference on Robotics and Automation (ICRA) 2019 international conference on robotics and automation (icra) ( 8846–8852).
  * Mukherjee . (2011) mukherjee2011symbolicMukherjee, K., Gupta, S., Ray, A. Phoha, S.  2011\.  Symbolic analysis of sonar data for underwater target detection Symbolic analysis of sonar data for underwater target detection.  IEEE Journal of Oceanic Engineering362219–230.
  * Nam . (2019) nam2019planningNam, C., Lee, J., Cho, Y., Lee, J., Kim, DH. Kim, C.  2019\.  Planning for target retrieval using a robotic manipulator in cluttered and occluded environments Planning for target retrieval using a robotic manipulator in cluttered and occluded environments.  arXiv preprint arXiv:1907.03956.
  * Nguyen . (2022) nguyen2022affordanceNguyen, T., Gopalan, N., Patel, R., Corsaro, M., Pavlick, E. Tellex, S.  2022\.  Affordance-based robot object retrieval Affordance-based robot object retrieval.  Autonomous Robots46183–98.
  * Nie . (2016) nie2016searchingNie, X., Wong, LL. Kaelbling, LP.  2016\.  Searching for physical objects in partially known environments Searching for physical objects in partially known environments.  2016 IEEE International Conference on Robotics and Automation (ICRA). 2016 ieee international conference on robotics and automation (icra).
  * Nomatsu . (2015) nomatsu2015developmentNomatsu, M., Suganuma, Y., Yui, Y. Uchimura, Y.  2015\.  Development of an autonomous mobile robot with self-localization and searching target in a real environment Development of an autonomous mobile robot with self-localization and searching target in a real environment.  Journal of Robotics and Mechatronics274356–364.
  * Novkovic . (2019) novkovic2019objectNovkovic, T., Pautrat, R., Furrer, F., Breyer, M., Siegwart, R. Nieto, J.  2019\.  Object Finding in Cluttered Scenes Using Interactive Perception Object finding in cluttered scenes using interactive perception.  arXiv preprint arXiv:1911.07482.
  * Ocaña . (2005) ocana2005indoorOcaña, M., Bergasa, LM., Sotelo, M. Flores, R.  2005\.  Indoor robot navigation using a POMDP based on WiFi and ultrasound observations Indoor robot navigation using a pomdp based on wifi and ultrasound observations.  2005 IEEE/RSJ International Conference on Intelligent Robots and Systems 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems ( 2592–2597).
  * O’Keefe Burgess (1996) o1996geometricO’Keefe, J. Burgess, N.  1996\.  Geometric determinants of the place fields of hippocampal neurons Geometric determinants of the place fields of hippocampal neurons.  Nature381425–428.
  * OpenStreetMap contributors (2017) OpenStreetMapOpenStreetMap contributors.  2017\.  Planet dump retrieved from https://planet.osm.org . Planet dump retrieved from https://planet.osm.org .
  * O’rourke . (1987) o1987artO’rourke, J. .  1987\.  Art gallery theorems and algorithms Art gallery theorems and algorithms ( 57).  Oxford University Press Oxford.
  * Papadimitriou Tsitsiklis (1987) papadimitriou1987complexityPapadimitriou, CH. Tsitsiklis, JN.  1987\.  The complexity of Markov decision processes The complexity of markov decision processes.  Mathematics of operations research123441–450.
  * Park . (2019) park2019deepsdfPark, JJ., Florence, P., Straub, J., Newcombe, R. Lovegrove, S.  2019\.  Deepsdf: Learning continuous signed distance functions for shape representation Deepsdf: Learning continuous signed distance functions for shape representation.  Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Proceedings of the ieee conference on computer vision and pattern recognition ( 165–174).
  * Patki . (2020) patki2020languagePatki, S., Fahnestock, E., Howard, TM. Walter, MR.  2020\.  Language-guided semantic mapping and mobile manipulation in partially observable environments Language-guided semantic mapping and mobile manipulation in partially observable environments.  Conference on Robot Learning. Conference on robot learning.
  * Pineau . (2003) pineau2003pointPineau, J., Gordon, G., Thrun, S. .  2003\.  Point-based value iteration: An anytime algorithm for POMDPs Point-based value iteration: An anytime algorithm for pomdps.  IJCAI Ijcai ( 3, 1025–1032).
  * Platt Jr . (2010) platt2010beliefPlatt Jr, R., Tedrake, R., Kaelbling, L. Lozano-Perez, T.  2010\.  Belief space planning assuming maximum likelihood observations Belief space planning assuming maximum likelihood observations.
  * Pollock (1970) pollock1970simplePollock, SM.  1970\.  A simple model of search for a moving target A simple model of search for a moving target.  Operations Research185883–903.
  * Prechelt (1998) prechelt1998earlyPrechelt, L.  1998\.  Early stopping-but when? Early stopping-but when?  Neural Networks: Tricks of the trade Neural networks: Tricks of the trade ( 55–69).  Springer.
  * Qiu . (2020) qiu2020learningQiu, Y., Pal, A. Christensen, HI.  2020\.  Learning hierarchical relationships for object-goal navigation Learning hierarchical relationships for object-goal navigation.  2020 Conference on Robot Learning (CoRL). 2020 conference on robot learning (corl).
  * Quigley . (2009) quigley2009rosQuigley, M., Conley, K., Gerkey, B., Faust, J., Foote, T., Leibs, J.Ng, AY.  2009\.  ROS: an open-source Robot Operating System Ros: an open-source robot operating system.  ICRA workshop on open source software Icra workshop on open source software ( 3, 5).
  * Rad Lepetit (2017) rad2017bb8Rad, M. Lepetit, V.  2017\.  Bb8: A scalable, accurate, robust to partial occlusion method for predicting the 3d poses of challenging objects without using depth Bb8: A scalable, accurate, robust to partial occlusion method for predicting the 3d poses of challenging objects without using depth.  Proceedings of the IEEE international conference on computer vision Proceedings of the ieee international conference on computer vision ( 3828–3836).
  * Radford . (2021) radford2021learningRadford, A., Kim, JW., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S.others  2021\.  Learning transferable visual models from natural language supervision Learning transferable visual models from natural language supervision.  International Conference on Machine Learning International conference on machine learning ( 8748–8763).
  * Radmard Croft (2017) radmard2017activeRadmard, S. Croft, EA.  2017\.  Active target search for high dimensional robotic systems Active target search for high dimensional robotic systems.  Autonomous Robots411163–180.
  * Ramakrishnan . (2021) ramakrishnan2021habitatRamakrishnan, SK., Gokaslan, A., Wijmans, E., Maksymets, O., Clegg, A., Turner, J.others  2021\.  Habitat-matterport 3D dataset (HM3D): 1000 large-scale 3D environments for embodied AI Habitat-matterport 3d dataset (hm3d): 1000 large-scale 3d environments for embodied ai.  arXiv preprint arXiv:2109.08238.
  * Rasouli (2015) rasouli2015attentionRasouli, A.  2015\.  Attention and sensor planning in autonomous robotic visual search Attention and sensor planning in autonomous robotic visual search.
  * Redmon . (2016) redmon2016youRedmon, J., Divvala, S., Girshick, R. Farhadi, A.  2016\.  You only look once: Unified, real-time object detection You only look once: Unified, real-time object detection.  Proceedings of the IEEE conference on computer vision and pattern recognition. Proceedings of the ieee conference on computer vision and pattern recognition.
  * Rizk . (2019) rizk2019cooperativeRizk, Y., Awad, M. Tunstel, EW.  2019\.  Cooperative heterogeneous multi-robot systems: A survey Cooperative heterogeneous multi-robot systems: A survey.  ACM Computing Surveys (CSUR)5221–31.
  * Robin Lacroix (2016) robin2016multiRobin, C. Lacroix, S.  2016\.  Multi-robot target detection and tracking: taxonomy and survey Multi-robot target detection and tracking: taxonomy and survey.  Autonomous Robots404729–760.
  * Ross . (2008) ross2008onlineRoss, S., Pineau, J., Paquet, S. Chaib-Draa, B.  2008\.  Online planning algorithms for POMDPs Online planning algorithms for POMDPs.  Journal of Artificial Intelligence Research32663–704.
  * M. Roy . (2021) dls2021Roy, M., Zheng, K., Liu, Jason Tellex, S.  2021\.  Dialogue Object Search Dialogue Object Search.  RSS Workshop on Robotics for People (R4P): Perspectives on Interaction, Learning and Safety. RSS Workshop on Robotics for People (R4P): Perspectives on Interaction, Learning and Safety.  https://arxiv.org/pdf/2107.10653.pdf Extended Abstract
  * N. Roy . (2005) roy2005findingRoy, N., Gordon, G. Thrun, S.  2005\.  Finding approximate POMDP solutions through belief compression Finding approximate pomdp solutions through belief compression.  Journal of artificial intelligence research231–40.
  * Rybski . (2002) rybski2002mindartRybski, PE., Larson, AC., Metcalf, H., Skyllingstad, D., Veeraraghavan, H. Gini, ML.  2002\.  MinDART: A Multi-Robot Search and Retrieval System. Mindart: A multi-robot search and retrieval system.  AAAI Mobile Robot Competition Aaai mobile robot competition ( 83–91).
  * Sadeghi . (2020) sadeghi2020optimalSadeghi, M., Behnia, F. Amiri, R.  2020\.  Optimal sensor placement for 2-D range-only target localization in constrained sensor geometry Optimal sensor placement for 2-d range-only target localization in constrained sensor geometry.  IEEE Transactions on Signal Processing682316–2327.
  * Saidi . (2007) saidi2007onlineSaidi, F., Stasse, O., Yokoi, K. Kanehiro, F.  2007\.  Online object search with a humanoid robot Online object search with a humanoid robot.  2007 IEEE/RSJ International Conference on Intelligent Robots and Systems 2007 ieee/rsj international conference on intelligent robots and systems ( 1677–1682).
  * Sanner (2010) sanner2010relationalSanner, S.  2010\.  Relational dynamic influence diagram language (rddl): Language description Relational dynamic influence diagram language (rddl): Language description.  Unpublished ms. Australian National University32.
  * Sarmiento . (2003) sarmiento2003efficientSarmiento, A., Murrieta, R. Hutchinson, SA.  2003\.  An efficient strategy for rapidly finding an object in a polygonal world An efficient strategy for rapidly finding an object in a polygonal world.  Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No. 03CH37453). Proceedings 2003 ieee/rsj international conference on intelligent robots and systems (iros 2003)(cat. no. 03ch37453).
  * Sarmiento . (2004) sarmiento2004multiSarmiento, A., Murrieta-Cid, R. Hutchinson, S.  2004\.  A multi-robot strategy for rapidly searching a polygonal environment A multi-robot strategy for rapidly searching a polygonal environment.  Ibero-American Conference on Artificial Intelligence Ibero-american conference on artificial intelligence ( 484–493).
  * Schmalstieg . (2022) schmalstieg2022learningSchmalstieg, F., Honerkamp, D., Welschehold, T. Valada, A.  2022\.  Learning Long-Horizon Robot Exploration Strategies for Multi-Object Search in Continuous Action Spaces Learning long-horizon robot exploration strategies for multi-object search in continuous action spaces.  arXiv preprint arXiv:2205.11384.
  * Schmid . (2019) schmid2019exploreSchmid, JF., Lauri, M. Frintrop, S.  2019\.  Explore, approach, and terminate: Evaluating subtasks in active visual object search based on deep reinforcement learning Explore, approach, and terminate: Evaluating subtasks in active visual object search based on deep reinforcement learning.  2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2019 ieee/rsj international conference on intelligent robots and systems (iros) ( 5008–5013).
  * D. Shah . (2022) shah2022roboticShah, D., Osinski, B., Ichter, B. Levine, S.  2022\.  Robotic Navigation with Large Pre-Trained Models of Language, Vision, and Action Robotic Navigation with Large Pre-Trained Models of Language, Vision, and Action..  https://arxiv.org/abs/2207.04429
  * S. Shah . (2017) airsim2017fsrShah, S., Dey, D., Lovett, C. Kapoor, A.  2017\.  AirSim: High-Fidelity Visual and Physical Simulation for Autonomous Vehicles Airsim: High-fidelity visual and physical simulation for autonomous vehicles.  Field and Service Robotics. Field and service robotics.
  * Shani . (2013) shani2013surveyShani, G., Pineau, J. Kaplow, R.  2013\.  A survey of point-based POMDP solvers A survey of point-based POMDP solvers.  Autonomous Agents and Multi-Agent Systems.
  * Shapiro (2003) shapiro2003monteShapiro, A.  2003\.  Monte Carlo sampling methods Monte Carlo sampling methods.  Handbooks in operations research and management science10353–425.
  * Sharkey Sharkey (2011) sharkey201117Sharkey, N. Sharkey, A.  2011\.  17 the rights and wrongs of robot care 17 the rights and wrongs of robot care.  Robot ethics: The ethical and social implications of robotics267.
  * P. Sharma . (2022) sharma2022skillSharma, P., Torralba, A. Andreas, J.  2022\.  Skill Induction and Planning with Latent Language Skill induction and planning with latent language.  Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) Proceedings of the 60th annual meeting of the association for computational linguistics (volume 1: Long papers) ( 1713–1726).