# Semantic Sensing and Planning for
Human-Robot Collaboration in Uncertain Environments

Luke Burks, Hunter M. Ray, Jamison McGinley, Sousheel Vunnam, and Nisar Ahmed∗
∗Smead Aerospace Engineering Sciences Department, 429 UCB, University of
Colorado Boulder, Boulder CO 80309, USA.
<EMAIL_ADDRESS>This work is funded by the
Center for Unmanned Aircraft Systems (C-UAS), a National Science Foundation
Industry/University Cooperative Research Center (I/UCRC) under NSF Award No.
CNS-1650468 along with significant contributions from C-UAS industry members.

###### Abstract

Autonomous robots can benefit greatly from human-provided semantic
characterizations of uncertain task environments and states. However, the
development of integrated strategies which let robots model, communicate, and
act on such ‘soft data’ remains challenging. Here, a framework is presented
for active semantic sensing and planning in human-robot teams which addresses
these gaps by formally combining the benefits of online sampling-based POMDP
policies, multi-modal semantic interaction, and Bayesian data fusion. This
approach lets humans opportunistically impose model structure and extend the
range of semantic soft data in uncertain environments by sketching and
labeling arbitrary landmarks across the environment. Dynamic updating of the
environment while searching for a mobile target allows robotic agents to
actively query humans for novel and relevant semantic data, thereby improving
beliefs of unknown environments and target states for improved online
planning. Target search simulations show significant improvements in time and
belief state estimates required for interception versus conventional planning
based solely on robotic sensing. Human subject studies ($n=36$) demonstrate a
average doubling in dynamic target capture rate compared to the lone robot
case, employing reasoning over a range of user characteristics and interaction
modalities. Video of interaction can be found at https://youtu.be/Eh-82ZJ1o4I.

##  I Introduction

Autonomous robotic vehicles will greatly extend human capabilities in domains
such as space exploration [1], disaster response [2], environmental monitoring
[3], infrastructure inspection [4], search and rescue [5], and defense [6].
Yet, the uncertain dynamic nature of these settings, coupled with vehicle
size-weight-power-compute constraints, often necessitates some form of human
oversight to cope with the brittleness of autonomy [7]. This has created
interest in new forms of human-robot interaction that can efficiently leverage
human reasoning to enhance robotic reasoning abilities. Probabilistic
techniques based on semantic language-based human-robot communication have
gained considerable attention for information fusion [8, 9, 10, 11, 12, 13]
and task planning [14, 15, 16, 17, 18, 19, 20]. However, existing approaches
only allow robots to reason about limited kinds of uncertainties, i.e. as long
as task environments and conditions are known a priori, or do not change in
unforeseen ways. These approaches are antithetical to how human teams
communicate with subtle ambiguities to express uncertainty. Constraining the
types of information in turn limits the flexibility and utility of semantic
communication for adapting to new or unknown situations.

Figure 1: Aerial robot searching for ground target with human aiding via
semantic labeling and referencing of environment.

This work examines how robots operating in uncertain environments can use
semantic communication with humans to solve the combined issues of model
augmentation, multi-level information fusion, and replanning under uncertainty
in an online manner. Such problems practically arise, for instance, with time-
sensitive dynamic target search in areas with outdated/poor prior maps, which
lead to uncertain robot and target motion models as well as uncertain human
input models. We present a novel framework for integrated active semantic
sensing and planning in human-robot teams that formally combines aspects of
online partially observable Markov decision process (POMDP) planning, sketch
and language-based semantic human-robot interfaces, and model-based Bayesian
data fusion.

As shown in Fig. 1, our approach features three key technical innovations.
Firstly, humans act as ‘ad hoc sensors’ that push multi-level semantic data to
robots via structured language, enabling robots to update task models and
beliefs with information outside their nominal sensing range. Secondly, humans
can use real-time sketch interfaces to update semantic language dictionaries
grounded in uncertain environments, thus dynamically extending the range and
flexibility of their observations. Finally, robots actively query humans for
specific semantic data at multiple task model levels to improve online
performance, while also non-myopically planning to act with imperfect human
sensors. These features effectively enable online ‘reprogramming’ of uncertain
POMDPs together with human-robot sensor fusion to support online replanning in
complex, dynamic environments. The remainder of the paper is organized as
follows; Sec. II presents motivating dynamic search problems and reviews
methods for planning and semantic data fusion under uncertainty; Sec. III
describes the technical details of our framework; Sec. IV presents target
search simulation results with simulated human sketch and structured language
observations; Sec V presents results of human subject experiments; and Sec. VI
concludes the paper.

##  II Motivating Problems and Background

We focus on dynamic target search problems in which a robot must intercept a
moving target as quickly as possible through an uncertain environment. Figure
10 shows a version of this problem for an unmanned aerial system (UAS), which
will be used as an example. Major uncertainties arise in (but are not limited
to): vehicle motion and transition models (due to unknown terrain or wind
fields that are difficult for robots to sense); target models and states (if
targets display different dynamic behaviors); and models of language-based
semantic ‘human sensor’ observations (e.g. Fig. 1), where ‘soft data’ can be
expressed with variable consistency/accuracy [10, 21].

In the example problem, the environment includes map regions with differing
probabilistic state transition models that affect robot and target motion
dynamics. The robot carries a visual sensor, which allows for target proximity
detection with a high probability and subject to false alarms, without
informing about the environment. Finally, the robot can communicate with a
remote human, who can view the robot’s telemetry data, sensing data, and map
information with negligible time delay and generate soft data, but issues no
commands to the robot. The robot plans its own movements to intercept the
target using available models and observations, assuming an initial prior
target state pdf. We next consider how the robot can use semantic soft data to
update knowledge of the uncertain environment and target states as part of an
optimal autonomous planning process.

Figure 2: Example Flowchart

###  II-A Language-based and Sketch-based Semantic Soft Data

The human primarily acts as an auxiliary (and imperfect) semantic information
source that can interface with the robot at any time via either one of two
methods. The first interface allows the human to compose linguistic statements
that are parsed and interpreted as target state observations. As shown in Fig.
1, these are modeled in the structured form ‘Target _is/is not_ _Desc_ _Ref_
’, where the _Desc_ and _Ref_ elements are taken from a defined semantic
codebook, and the _is/is not_ field toggles between positive and negative data
[22]. In prior work [21, 12, 13, 23, 24], probabilistic likelihoods were
developed for all possible statements in a given codebook to support recursive
Bayesian fusion of linguistic human and robot sensor data. Since these works
considered only fully known environments, all relevant semantic references
could be enumerated in advance. However, the environments here are not fully
known in advance, so the codebook is at best only partially defined at mission
start.

This leads to the second interface: since new map information cannot be
obtained from the robot’s sensor to augment the codebook, the human may
instead do this by providing labeled 2D free-form sketches, which each depict
a spatially constrained region on a 2D map display (as in Fig. 1 with ‘Pond’
and ‘Trees’. Building on [25], the codebook is automatically augmented with
the labels of new landmarks/references, so that the corresponding spatial
sketch data can also be used to generate suitable soft data likelihood models
for the linguistic statement interface (see Fig. 1). However, unlike in [25],
human sketches here may also provide direct information about probabilistic
state transition models, to constrain how the robot and target may traverse
certain map areas. While similar 2D sketch interfaces have also been developed
for robotics applications [14, 26, 16, 27], this work presents a novel use
case in the context of multi-level data fusion for planning under uncertainty.

###  II-B Optimal Planning and Sensing under Uncertainty

The robot must autonomously generate its own plans for minimum time target
interception, whether or not any semantic soft data are provided. The presence
of model uncertainties, sensing errors, and process noise makes optimal
planning quite challenging. One family of decision-making algorithms that
accounts for these combined uncertainties are partially observable Markov
decision processes (POMDPs). While POMDPs are impractical to solve exactly for
all but the most simple problems [28], a variety of powerful approximations
can exploit various features of particular problem formulations. A POMDP is
formally specified as a 7-tuple
$(\mathcal{S,A,T,R},\Omega,\mathcal{O,\gamma})$, where the goal is to find a
policy $\pi$ which maps from a Bayesian posterior distribution, i.e. the
belief $b=p(s)$ over the set of states $\mathcal{S}$, to a discrete action
$a\in\mathcal{A}$. The transition model $\mathcal{T}$ is a discrete time
probabilistic mapping from one state to the next given an action,
$p(s^{\prime}|s,a)$, after which the robot is rewarded according to $R(s,a)$.
During policy execution, the robot receives observations $o\in\Omega$
according to observation likelihood $\mathcal{O}=p(o|s)$. For infinite horizon
planning problems with discount factor $\gamma\in[0,1)$, the optimal policy
$\pi[b(s)]\rightarrow a$ maximizes the expected future discounted reward:
$\mathbb{E}[\sum_{k=0}^{\infty}\gamma^{k}R(s_{k},a_{k})]$.

The primary challenge arising from casting our motivating problem as a POMDP
lies in the ability of the human to modify the models $\mathcal{T}$ and
$\mathcal{O}$ online in an unmodeled ad-hoc fashion via the sketch interface.
These modifications can happen rapidly, and might change large swathes of each
model with a single sketch. Bayes-Adaptive POMDPs [29] allow POMDPs to learn
the parameters of $\mathcal{T}$ and $\mathcal{O}$, but require gradual changes
to their parameters and static $\mathcal{T}$ and $\mathcal{O}$. In the
motivating problem, $\mathcal{A}$ and $\mathcal{O}$ change unpredictably with
new sketches. This issue renders “full-width” offline point-based POMDP
planners [30, 31] inapplicable, as they require models of how $\mathcal{T,O}$
and $\Omega$ change.

Online POMDP approaches [32], which eschew the process of pre-solving the
policy prior to execution in favor of interleaving steps of policy execution
and search, have successfully been used to address large observation spaces
[33], continuous state spaces [34], and more recently, dynamic ad-hoc models
[25]. These algorithms make use of a ’black-box’ generative model, requiring
only the ‘current POMDP problem’ at time of execution, making them good
candidates for solving problems with dynamic model uncertainty.

###  II-C Active Semantic Sensing for Planning with Human Collaborators

A major challenge for problems like target localization is that dynamics and
uncertainties can quickly become quite non-linear and non-Gaussian,
particularly given the types of semantic information available for fusion
(e.g. negative information from ‘no detection’ readings [35]). As a result,
typical stovepiped approaches to control/planning and sensing/estimation can
lead to poor performance, since they rely on overly simplistic uncertainty
assumptions. Constraints on human and robot performance also place premiums on
when and how often collaborative data fusion can occur. For example, it is
generally important to balance situational awareness and mental workload for a
human sensor (who might also need to switch between tasks constantly).
Likewise, it is important for the robot to know how and when a human sensor
can be exploited for solving complex planning problems, which would otherwise
be very inefficient to tackle using only its own local sensor data.

One approach to POMDP approximation, the QMDP algorithm [36], attempts to use
a fully observable MDP policy to compute the optimal action in a partially
observed step. As QMDPs are only exactly optimal assuming the state will
indeed become fully observable after a single timestep, they are generally
unsuitable for information gathering dependent problems such as the one
addressed in this work. However, the introduction of the oracular POMDP
(OPOMDP) formulation [37, 38] built on a QMDP policy and enabled the use of a
human sensor to provide “perfect” state information at a fixed cost. Further
work resulted in Human Observation Provider POMDPs (HOP-POMDPs) [39], which
allow the consideration of oracular humans who are not always available to
answer a robotic query. HOP-POMDPs calculate a cost of asking, which is then
weighed against the potential information value, similar to VOI aware planning
in [9]. When augmented with the Learning the Model of Humans as Observation
Providers (LM-HOP) algorithm [10], HOP-POMDPs can estimate both the accuracy
and availability of humans, thus treating them as probabilistic sensors. A
primary drawback to using either OPOMDPs or HOP-POMDPs to address target
tracking problems is that while they both enable a QMDP based policy to
consider information gathering actions, these actions consist of a single
self-localization query. Such formulations ignore the rich information set
available in the motivating problem thanks to the presence of semantically
labeled objects.

###  II-D Planning for Bi-directional Communication

Human-robot communication presents unique challenges in reasoning with respect
to the complex nuances of natural language and human interaction. In order to
perform comparably to an all-human team, robots working with humans benefit
greatly from the ability to comprehend and actively query their teammates to
reason about given commands, aid collaboration, and update their understanding
about the task or environment. Just as an environment may change over the
course of an interaction, the vocabulary used to describe such environment
must also be able to adapt. The method proposed in [15] implements a
probabilistic graphical model to reason over a teammate’s commands. Spatial
distribution clauses are used to infer a location based hierarchy that allows
a robot to reason over a wide range of commands. However, the approach is
limited by a static dictionary that doesn’t allow for the entry of new spatial
or semantic information into the environment.

While predefined interfaces, such as GPS coordinates, could be used to reason
in a precise manner about geographic locations, this type of deterministic
communication is unintuitive and prone to errors. Human teams will often
communicate with inherent ambiguity necessitating follow up questions between
teammates to ensure comprehension. However, reasoning over this type of
nuanced information remains challenging for robots. The method devised in [15]
set up a framework for comprehending what information the user provided,
whereas [40][41][42] consider the problem of if, when, and what to communicate
back to the user in order to resolve ambiguity across an interaction. These
approaches utilize POMDPs to reason about some component of the human’s mental
state in different collaborative tasks. The work presented in [43] shows how a
POMDP can be utilized to refine the robot’s understanding of a human’s object
of interest. However, in each of these cases the user is limited in their
vocabulary. These methods constrain the robot to communicate about a static,
and potentially obsolete environment, especially when applied in a dynamic
target search where new locations become relevant to planning or querying.

In uncertain environments, new spatial information may be presented that, when
reasoned over, can provide critical information to the completion of a task.
The approach described in this work uses a simplified compass based spatial
reference cues (North,South,etc.) coupled with a dynamic dictionary that the
user can update and modify in real time. The inherent uncertainty provided by
these cues enables the user to communicate to the robot teammate in an
intuitive manner. Furthermore, the use of a POMDP to select the nature and
timing of human communication enables reasoning with respect to the Value of
Information theory proposed in [9].

##  III Methodology

###  III-A Formal Problem Statement

The problem described above is formally cast as a POMDP, specified by the
7-tuple $\\{\mathcal{S,A,T,R},\Omega,\mathcal{O},\gamma\\}$. Let the
continuous states of the mobile robot and target in some search environment be
$s_{r}$ and $s_{t}$, respectively. The joint state space is
$[s_{r},s_{t}]^{T}=s\in\mathcal{S}=\mathcal{R}^{N}$. The human sensor has full
knowledge of $s_{r}$ at all times as well the belief
$b(s_{t})=p(s_{t}|o_{h}^{1:k},o_{r}^{1:k},a^{1:k-1})$, which is the updated
Bayesian posterior pdf given all observations made by the robot $o_{h}^{1:k}$
and the human $o_{h}^{1:k}$ through time $k$. Both $s_{r}$ and $b(s_{t})$ are
displayed over a terrain map, which dictates transition model
$\mathcal{T}=p(s^{\prime}|s,a)$ at each point space according to hazards and
open areas. Action space $\mathcal{A}$ is a combination of movement action
made by the robot which affect its state $\mathcal{A}_{m}$ and query actions
which pull information from the human $\mathcal{A}_{q}$. The human can provide
sketches $\mathcal{H}$, which are semantically labeled spatial areas
corresponding to salient features of the space. These labels, along with
problem relevant relational indicators, form the semantic dictionary from with
the query actions $A_{q}$ are drawn. The sketches themselves are defined
geometrically, as a set of vertices forming a convex polytope in
$\mathbb{R}^{N}$. Each sketch also corresponds to a softmax observation model
like those used in [44, 45], which is derived based on the polytopes vertices
[13] and is the observation model $\Omega=p(o|s,a_{q})$ for a given query
action $a_{q}$. The observation set $\mathcal{O}$ is split into robotic
detection observations $\mathcal{O}_{r}=\\{NoDetection,Detection,Capture\\}$
and human answers to action queries $\mathcal{O}_{h}=\\{Yes,No,Null\\}$,
accounting for the possibility of the human not answering. Each sketch creates
an enlarged query action space $\mathcal{A}_{q}^{\prime}$ such that
$\mathcal{A}_{q}\subset\mathcal{A}_{q}^{\prime}$, where each new action is a
possible query to the human regarding the relative location of $s_{t}$ with
respect to the new sketch. For a given sketch labeled $(l)$, with a set of
relevant relational indicators,
$\mathcal{A}_{q}^{\prime}=\mathcal{A}_{q}\cup[Relation\times l]$. Thus the
robot is capable of asking more questions after a sketch due to the expansion
of possible semantic queries. The robot initially holds some prior
$\hat{p}(s^{\prime}|s,a),\ \forall s$, which need not be reflective of the
true transition model $p(s^{\prime}|s,a)$, and which the human can update by
attaching meta information to sketches indicating the relative ease or
difficulty of traversal within a region. In this work, for a given sketch
$h_{i}$, the human may introduce meta information in the form of terrain
multipliers $\delta$, such that
$\hat{p}_{t+1}(s^{\prime}|s,a)\neq\hat{p}_{t}(s^{\prime}|s,a)$ and $E[\Delta
s](a)=\delta_{i}$. Finally, the reward function $\mathcal{R}$ is stated as a
piece-wise function incentivizing capture of the target and slightly
penalizing human queries such that for some distance threshold $\tau$,

$\displaystyle\mathcal{R}=\begin{cases}100&dist(s_{t},s_{r})\leq\tau\\\
0&dist(s_{t},s_{r})>\tau,a_{q}=Null\\\ -1&dist(s_{t},s_{r})>\tau,a_{q}\neq
Null\\\ \end{cases}$ (1)

A POMDP policy $\pi$ solved for this problem is one which maximizes sum of
expected future discounted reward of actions
$E[\sum_{t=0}^{\infty}\gamma^{t}R_{t}(s,a)]$.

###  III-B Human Querying and Data Fusion

The human can act as either: a passive semantic sensor, which volunteers
information without request whenever possible; or as an active semantic
sensor, which can be queried by the robot to provide information on request.
Here we assume the human will respond to queries based on a static a priori
known responsivness value $(\xi)$, such that, for all human observations
$o_{h}$ at all times, $p(o_{h}\neq None|s)=\xi$. This leads to an additional
observation $o_{h}=None\in\Omega_{h}$. We also assume the human has a static a
priori known accuracy $\eta$, such that, for all human observations $o_{h}$ at
all times, $\bar{p}(o_{h}=j|s)=p(o_{h}=j|s)\cdot\eta$, where probability is
redistributed to the “inaccurate” observations,

$\displaystyle\bar{p}(o_{h}=(k\neq j)|s)=$ (2)
$\displaystyle\frac{1}{|\Omega|-1}p(o_{h}=j|s)\cdot\eta\cdot p(o_{h}=(k\neq
j)|s)$

The notation $\bar{p}(o|s)$ and $\bar{p}(s^{\prime}|s,a)$ denote models used
during online execution, in contrast to the nominal distributions $p(o|s)$ and
$p(s^{\prime}|s,a)$. This parameterization of accuracy ignores similarity
between any two observations. While this simplifies implementation and allows
comparative testing of accuracy levels, other models may yield more realistic
results; e.g. linear softmax model parameters [24, 25, 46], can be used to
determine the likelihood of mistaking semantic labels given $s$.

We focus here on humans as active sensors. This requires an explicit
dependency on actions to be included in the observation model, as well as
additional actions which trigger this dependency. Just as POMDP observations
can be typically modeled as $o\sim p(o|s),o\in\Omega$, human responses to
robotic queries $a\in\mathcal{A}_{q}$ can be modeled as $o_{h}\sim
p(o_{h}|s,a_{q}),\ a_{q}\in\mathcal{A}_{q},\ o_{h}\in\Omega_{h}$. These
additional query actions can be introduced into $\mathcal{A}$ in one of two
ways. Casting them as exclusive options, where either movement or a query can
be pursued but not both, minimally expands the action space to the sum of
queries and movements, $\mathcal{A}=\mathcal{A}_{m}+\mathcal{A}_{q}$. But this
can be limiting in situations which benefit from rapid information gathering
about models and states together. Instead, we cast the queries as inclusive
actions, in which every time step permits any combination of movement and
query, $\mathcal{A}=\mathcal{A}_{m}\times\mathcal{A}_{q}$. This can
drastically increase the size of the action space, but allows rapid
information gathering.

The robot’s on-board sensor produces a single categorical observation per time
step $o_{r}$ , which must be fused with $o_{h}$. We assume the robot’s sensor
is independent of the human observations given the state such that,

$\displaystyle
p(s|o_{r},o_{h})=\frac{p(s)p(o_{h},o_{r}|s)}{p(o_{r},o_{h})}\propto
p(s)p(o_{r}|s)p(o_{h}|s)$ (3)

Fig. 3 summarizes the probabilistic dependencies for the POMDPs describing the
Fig. 10 search problems. While all observations are state dependent, some now
depend on actions chosen by the policy. Also, query actions have no effect on
the state, and are pure information gathering actions. In these new POMDPs, a
combined action might be “Move to North, and Ask human if target South of
Lake”, which may return a combined observation of “Target is Far from me, and
human says target is not South of Lake”. So in this case
$a=\\{North,South/Lake\\}$, and $o=\\{Far,No\\}$.

Figure 3: Graphical model for the proposed POMDP

###  III-C Ad-hoc Semantic Modeling

As discussed previously, many existing approaches for augmenting autonomous
robotic reasoning with human-robot semantic dialog only allow robots to reason
about limited kinds of uncertainties, i.e. as long as task environments and
conditions are known a priori, or do not change in unforeseen ways. This in
turn limits the flexibility and utility of semantic communication for adapting
to new or unknown situations.

As shown in Fig. 1, this approach features three key technical innovations.
Firstly, humans are modeled as ‘ad hoc sensors’ that push _multi-level_
semantic data to robots via structured language, enabling robots to update
task models and beliefs with information outside their nominal sensing range.
Such multi-level data can correspond to information regarding updates to the
POMDPs own transition, observation, or reward models, $\mathcal{T,O,R}$, or
semantic information pertaining to previously abstracted or ignored state
information such as modal behavior or intent. Such dynamic modeling was
expressly forbidden by the techniques used in [44, 45], which required a
static, apriori known POMDP 7-tuple, but are now accessible via ad-hoc
semantic sensor models.

Secondly, humans can use real-time sketch interfaces to update semantic
language dictionaries grounded in uncertain environments, thus dynamically
extending the range and flexibility of their observations. Finally, robots
actively query humans for specific semantic data at multiple task model levels
to improve online performance, while also non-myopically planning to act with
imperfect human sensors. These features effectively enable online
‘reprogramming’ of uncertain POMDPs together with human-robot sensor fusion to
support online replanning in complex environments.

###  III-D Language-based and Sketch-based Semantic Soft Data

While addressing scenarios of unknown/dynamic environments the human primarily
acts as an auxiliary and imperfect semantic information source that can
communicate with the robot at any time via either one of two interfaces. The
first interface allows the human to compose linguistic statements that are
parsed and interpreted as target state observations. As shown in Fig. 1, these
are modeled in the structured form ‘Target _is/is not_ _Desc_ _Ref_ ’, where
the _Desc_ and _Ref_ elements are taken from a defined semantic codebook, and
the _is/is not_ field toggles between positive and negative data [22]. In
prior work [21, 12, 13, 23, 24], probabilistic likelihoods were developed for
all possible statements in a given codebook to support recursive Bayesian
fusion of linguistic human and robot sensor data. Since these works only
considered _fully known_ environments, all relevant semantic references could
be enumerated in advance. However, the environments here are not fully known
in advance, so the codebook is at best only partially defined at mission
start.

This leads to the second interface: since new map information cannot be
obtained from the robot’s sensor to augment the codebook , the human may
instead do this by providing labeled 2D free-form sketches, which each depict
a spatially constrained region on a 2D map display (as in Fig. 1 with ‘Pond’
and ‘Trees’). Building on [25], the codebook is automatically augmented with
the labels of new landmarks/references, and the corresponding spatial sketch
data can also be used to generate suitable soft data likelihood models for the
linguistic statement interface (see Fig. 1). However, unlike in [25], human
sketches here may also provide direct information about probabilistic state
transition models, to constrain how the robot and target may traverse certain
map areas. While similar 2D sketch interfaces have also been developed for
robotics applications [14, 26, 16, 27], their use in the context of multi-
level data fusion for planning under uncertainty represents a novel
contribution.

In this work, the model for the human sensor is assumed to be known in
advance. That is, given a sketch $h_{i}$, the autonomy is capable of
interpreting human responses to queries regarding $h_{i}$ according to a
probabilistic likelihood function. Regarding the scope of human soft data in
this work, such assumed models, including those for accuracy and availability,
are further assumed to be static, and are not learned or adapted online.
Furthermore, while the online planning approach in the following sections
could in principle be applied to changing reward functions without
modification, here only changes to the observation and transition functions
are considered. Such changes are taken ‘as is’ by the autonomy, rather than
maintaining a belief over the uncertain model parameters as in previous work
[29].

Finally, the example problems in this work assume the semantic codebook to be
empty at the start of the problem, and built up from scratch by the human
using semantically labeled sketches. However, the techniques for online
planning and sketch processing apply identically in problems for which the
codebook is pre-available yet incomplete. In any case, building the codebook
from scratch implies a slightly more difficult problem due to the potentially
lacking information available at the start of the problem, and thus provides a
more compelling case for human sketch input.

###  III-E Revising POMDP models through Sketching

A sketch, or drawing in the 2D plane, begins as a set of points $\\{P\\}$,
whether with a pen, touchscreen, mouse, or other modality. The set $\\{P\\}$
is tagged by the human with a natural language label $(l)$, and any applicable
meta information $\delta$ as in Section 5.2. The communication of the label
and meta information in this work is accomplished using fillable text boxes
and radio button selection of a pre-selected set of meta data options, but
could also be acquired entirely from natural language through word association
methods such as Word2Vec [47] or other deep learning methods.

From the set $\\{P\\}$, the ordered verticies of a convex hull
$v_{i}\in\\{V\\}$, where $\\{V\\}\subset\\{P\\}$ are obtained using the
Quickhull algorithm. $\\{V\\}$ is progressively reduced using Algorithm 1
until it reaches a predefinied size by repeatedly removing the point
contributing the least deflection angle to the line between its neighbors,
calculated via the Law of Cosines for the vertex pair vectors
$\overrightarrow{v_{i-1}v_{i}}$,

$\displaystyle\Theta(v_{i})=\arccos{\left[\frac{\overrightarrow{v_{i-1}v_{i}}\cdot\overrightarrow{v_{i}v_{i+1}}}{\|\overrightarrow{v_{i-1}v_{i}}\|\|\overrightarrow{v_{i}v_{i+1}}\|}\right]}$
(4)

in a procedure inspired by the Ramer-Douglas-Peucker algorithm.

Algorithm 1 Sequential Convex Hull Reduction

Function: $REDUCE$

Input: Convex Hull $\\{V\\}$, Target Number $N$

if $\\{V\\}==N$ then

return hull

end if

for $v_{i}\in\\{V\\}$ do

$\Theta(v_{i})\leftarrow angle(v_{i-1},v_{i},v_{i+1})$

end for

$\\{V\\}\leftarrow\\{V\\}\setminus argmin_{v}\Theta(v)$

return REDUCE(hull,N)

This heuristic was chosen as a proxy for maximizing the area maintained by the
reduced hull, but in practice other heuristics could also be used. The reduced
set is then used as the basis for softmax model synthesis [13], in which $M$
points define a final sketch $h_{i}$ associated with a softmax function with
$|h_{i}|=M+1$ classes. In general, these are 1 interior classes and $M$
exterior classes, each associated with a relational indicator. These classes
are associated with relational indicators using the methodology described in
Section 5.10.

A limitation of sequential hull reduction is the need to pre-define a set
number of points at which to stop the progressive reduction. Ideally, the
“natural” number of points needed to maximize some criteria could be chosen on
a sketch by sketch basis in a geometric analogue to the Bayesian Information
Criterion (BIC) score for model selection. Note that this approach for convex
hull reduction differs from that used in Geometric SVM classifiers in that
reduces the vertices comprising the boundaries of the hull itself, rather than
reducing the hull area in a feature hyperplane.

Figure 4: Left: Convex hull verticies (red), reduced to 4 points with
sequential hull reduction (green). Right: Softmax function and labels
resulting from reduced points.

An example sketch is shown in Fig. 4, where the initial input consists of 661
points, shown in black, making a roughly rectangular shape. The Quickhull
algorithm is applied to find 21 points, shown in red, defining a convex hull
on the set of points. These points are then used as input to Algorithm 1,
which further reduces the number of points to the 4 points shown in green.
From these 4 points, a softmax model consisting of 5 classes, a “Near” class
and 4 relational indicators, is then synthesized. Semantic observations can
now be constructed using the label $(l)$ given by the human when they made the
sketch in the form, $o=\text{``The Target is $relation$ of $label$."}$ The
area inside the sketch $h_{i}$ is now modelled as subject to any modifying
meta data $\delta_{i}$ provided by the human. In this work, where such
information is provided, the $\delta$ acts only as an assumed transition
function $\hat{p}(s^{\prime}|s,a)$ modifier such that for a sketch made at
time $(t)$:

$\displaystyle\hat{p}_{t}(s^{\prime}|s,a)!=\hat{p}_{t+1}(s^{\prime}|s,a)$ (5)
$\displaystyle E[\Delta s]_{t}(a)=X$ (6) $\displaystyle E[\Delta
s]_{t+1}(a)=\delta_{i}X,\forall s\in h_{i}$ (7)

where the $\in$ operation filters states located within the convex polygon
defined by the vertices of $h_{i}$. This introduces a scaling factor, in which
for any given state simulation in an online POMDP, the transition simulation
must check if the state is contained in any previously drawn sketches.
Alternatively, the transition modification can be stored in either a
continuous function such as a unnormalized Gaussian Mixture, or a discrete
grid as appropriate to limit computational expense. In the experiments in
following sections that explore the use of human meta data to modify
transition functions (specifically Section 5.11.1), the discrete grid approach
is used, wherein a grid of nominal values $\alpha(s)$ is pre-initialized, then
updated to store meta data:

$\displaystyle\alpha(s)=\delta_{i},\forall s\in h_{i}$ (9)

Naturally in problems without specific transition function modification,
Section 5.11.2 and 5.12, such a storage solution is not included. In this
specific work, the human can communicate the appropriate $\delta$ value for a
given sketch as one of a given set of semantic choices to indicate the effect
of the terrain contained within the sketch on the movement speed of any ground
vehicle passing through it. Each choice is assigned a $\delta$ value,
corresponding to multipliers on a vehicles nominal speed. Implementation
details are given in Section 5.11.1.

The query action set $A_{q}$ and observation function $\Omega$ are modified
alongside the transition function $\mathcal{T}$, introducing the newly minted
sketch $h_{i}\in\mathcal{H}$ and its corresponding softmax function in the
manner prescribed in Section 5.3. The observation set $\mathcal{O}$ remains
the same in this work, but through the modified
$\Omega=p(o\in\mathcal{O}|s,a)$ observations corresponding to the new actions
in $A_{q}$ can now occur. As per Section 5.3, the availability $\xi$ and
accuracy $\eta$ parameters of the human collaborator are static across any
model revisions, and their effect is folded into changes to $\Omega$ through
Equations 5.2-5.4. In this way, both parameters are accounted for in planning
through their effect on the observation liklihood.

In principle the human could provide nothing more than the sketched points
$\\{P\\}$, with no meta information or label. The meta data is processed as
available, and any lack of such data can simply be ignored by not updating the
transition function. However, the robot will still need to indicate specific
sketches to the human in queries, potentially requiring it to resort to
referring to “Sketch 1” vs “Sketch 2”. Semantic labeling of sketches
ultimately leads to better understanding on the human’s part of the robots
queries and opens the door to the use of the semantic label to infer
additional meta data using natural language processing techniques.

###  III-F Multi-Level Active Information Gathering

To accommodate stochastic switching dynamics, it is generally convenient to
include mode states $m$ as shown in Fig. 3 (right) for the Road Network
problem, which dictate alterations to the target state transition models,

$\displaystyle\bar{s}=[s,m]^{T},m^{\prime}\sim p(m^{\prime}|m)\ s^{\prime}\sim
p(s^{\prime}|s,a,m^{\prime}).$ (10)

This additional discrete state variable can be easily handled by POMCP and
other Monte Carlo tree search approximations, which rely on generative black
box simulators and support edits to $\mathcal{T}$ and $\mathcal{O}$. Offline
approximations based on switching-mode POMDPs [48] can also accommodate hybrid
dynamics, but require stationary models. Such hybrid model extensions also
open the door to active semantic queries and specific human observations
$o_{h}$ pertaining to $m$, which can greatly enhance the Bayesian belief for
$m$.

With this modification to the generative model, the probability of different
state transition models being in effect can be explicitly represented via
particle approximation as

$\displaystyle P(m=x)=\frac{1}{N}\sum_{n=0}^{N}\textbf{1}(m_{n}=x),$ (11)

where $\textbf{1}(m_{n}=x)$ is an indicator function applied to the mode of
particle ($n$). This allows queries to be constructed in the same way as those
presented in [44], but referring only to the mode segment of the state vector
$\bar{s}$. For instance, in the motivating problem the modes governing the
transition probabilities represent whether or not a target is on a road. Thus,
actions can be taken such as “Ask the human if the target has gone off-road”,
which can improve the robot’s estimated belief of the target’s speed. In this
way, the model changes brought about by queries are anticipated by the solver,
and don’t imply the need to solve a different POMDP. For human responses
modeled as $p(o_{h}|m)$, the belief update equation becomes

$\displaystyle p(s|o_{r},o_{h})=\sum_{m}p(s,m|o_{r},o_{h})$ (12)
$\displaystyle=\sum_{m}p(s|o_{r},o_{h},m)p(m|o_{r},o_{h})=\sum_{m}\frac{p(r|s)p(m|s)p(h|m)}{p(h)p(r)}$

With the mode treated an additional state variable as in Equation 10, this
equation reduces to Equation 3. The bootstrap particle filter used in
Algorithm 1 approximates this belief update through use of weighted particles.

###  III-G Online Planning with Revised Models

Having updated the POMDP with revised transition functions and observation
likelihoods through a human sketch, a POMDP planner can be brought to bear to
produce an optimal policy. However, this newly available information creates
its own issues, as most POMDP solvers make two key assumptions on transition
models. First is that the model is temporally static

$\displaystyle p_{k+1}(s^{\prime}|s,a)=p_{k}(s^{\prime}|s,a),\forall k$ (13)
$\displaystyle\hat{p}_{k+1}(s^{\prime}|s,a)=\hat{p}_{k}(s^{\prime}|s,a).$

where $\hat{p}_{k}(s^{\prime}|s,a)$ is the internal transition function in use
by the robot at time $k$, in contrast to the true underlying (unknown) model
$p_{k}(s^{\prime}|s,a)$. The second is that the model being used by the solver
is identical to the model being used during the execution of the policy,
$\hat{p}_{k}(s^{\prime}|s,a)=p_{k}(s^{\prime}|s,a)$.

The first assumption is particularly important for infinite horizon offline
solvers, where Bellman-backup steps generate approximations of the value
function agnostic of whichever timestep a reward may be achieved on. Finite
horizon offline and online solvers can cope with this limitation [32, 49], but
require that even non-stationary transition models be known for all times
prior to generating a policy. The Adaptive Belief Tree (ABT) [50] online
planner was developed to address changing environmental conditions with regard
to the transition model, but carries no provision for the observation model
alterations necessary in this work.

For $\mathcal{T}$, we assume the underlying model isn’t changing, while the
robot’s understanding of it might, i.e.

$\displaystyle p_{k+1}(s^{\prime}|s,a)=p_{k}(s^{\prime}|s,a)$ (14)
$\displaystyle\hat{p}_{k+1}(s^{\prime}|s,a)\stackrel{{\scriptstyle?}}{{=}}\hat{p}_{k}(s^{\prime}|s,a)$

However, we make no assumption on the nature of this understanding change nor
the timing. For the observation model however, both the true and internal
model change when given a new sketch. All of these model changes imply that
the robot must solve a different but related POMDP after each human sketch.
With this in mind, we next consider viable approximations for solving such
POMDPs.

Algorithm 2 Planning with Human Model Updates

1: $B_{k}=$ Particle_Set(Size = N)

2: $\alpha(s)$ = Discrete_Grid()

3: repeat

4: $[a_{m},a_{q}]$ = POMCP($B$) (Ref. [32])

5: $s\sim p_{k}(s^{\prime}|s,a_{m})$ (unknown state)

6: $o_{r}\sim\bar{p}_{k}(o_{r}|s)$ (robot sensor observation)

7: $o_{h}\sim\bar{p}_{k}(o_{h}|s,a_{q})$ (human query answer)

8: $B_{k+1}=$ Bootstrap_Filter($B_{k},a_{m},a_{q},o_{r},o_{h}$)

9: if New Human Sketch ($\mathcal{h}$) then

10: $\delta$ = $\mathcal{h}.\delta$, (human assigned state modifier)

11: l = $\mathcal{h}.l$, (human assigned label)

12: for $s\in\mathcal{h}$ do

13: $\alpha(s)=\delta$

14: end for

15: $\Omega_{k+1}=\Omega_{k}\cup(l\times[Near,E,W,N,S])$

16: end if

17: until Scenario End

The Partially Observable Monte Carlo Planning (POMCP) algorithm proposed in
[32] is particularly promising due to its use of generative ‘forward’ models
and online any-time characteristics. While the original implementation of
POMCP uses an unweighted particle filter for belief updates, the authors of
[51] note that, for problems with even moderately large $\mathcal{A}$ or
$\mathcal{O}$, a bootstrap particle filter allows for more consistent belief
updates without domain specific particle reinvigoration. This weighted
particle filter approach coincidentally also provides a solution to the
dynamic modeling problem. Each belief update is carried out using the most up-
to-date model, while changes to the model only affect future timesteps. As
model alterations require solving a different POMDP after each sketch, this
approach allows each planning phase to be treated as the start of a brand new
POMDP solution. Our procedure for carrying out POMCP planning while handling
dynamic model updates from a human is detailed in Algorithm 2. Certain aspects
of this procedure, such as our use of a discretized grid to store transition
model modifiers ($\alpha$) noted in the previous subsection or the semantic
observations included with each sketch (described in more detail below),
readily adapt to more general problems.

Figure 5: Sketch Generation and Preparation Pipeline

###  III-H Predictive Tree Planning

Implementation of an online POMDP solver such as POMCP in a time-limited
system raises an additional complication, regardless of human involvement. A
typical offline POMDP solver computes a policy prior to execution and requires
significantly less time to execute actions recommended thereby, as shown in
Figure 6.

Figure 6: Typical Offline POMDP Time Allocation

Online planners like POMCP interweave planning and execution during runtime,
leading to a time allocation structure like the one in Figure 7. This
structure, when implemented directly on a robotic platform, leaves the robot
immobile while planning and non-cognizant while acting. Planning for timestep
$k+1$ cannot take place until the observation at timestep $k$ has been fused
into the belief, as POMCP operates on the current belief as the root node of
its planning tree. If this challenge could be overcome, it would be ideal to
operate according to the structure in Figure 8, where the planning for
timestep $k+1$ takes place during the execution of action $k$. Additionally,
given that POMCP is limited in this work to a maximum decision time, it would
be ideal to allocate exactly as much decision time as action $k$ takes to
execute, as shown in Figure 9. An approach to achieving this structure is
proposed here, known as Predictive Tree Planning.

Figure 7: Typical Online POMDP Time Allocation Figure 8: Simultaneous Planning
and Execution Time Allocation Figure 9: Irregular Action Duration Time
Allocation

If such planning can take place only after receiving an observation, the tree
structure of POMCP can be leveraged to pre-plan by predicting which
observation will be received. For a given action $a_{k}\in A_{k}$ and belief
$b_{k}$, the observation model $p(o|s)$ is used to direct tree samples to
nodes with history $b_{k}a_{k}o$. The weighted proportion of samples in nodes
$[b_{k}a_{k}o^{1},b_{k}a_{k}o_{2},...,b_{k}a_{k}o_{|\Omega|}]$ represents the
distribution $p(o_{k}|b_{k},a_{k})$,

$\displaystyle p(o_{k}=o|b_{k},a_{k})=\sum_{s_{k}\in
b_{k}}w_{s}p(o_{k}=1|s_{k},a_{k})$ (15)

which is the observation probability distribution for the current belief and
action. In order to spend $\Delta t(a_{k})$ time planning during the execution
of $a_{k}$, $|\Omega|$ plans can be pursued, each allocated $\Delta
t(a_{k})p(o_{k}=o|b_{k},a_{k})$ time. That is to say, after carrying out a
belief update assuming a future observation, we generate a POMCP policy using
time in proportion to the probability of receiving said observation. Upon
receiving the true observation at the end of the action execution phase, the
autonomous system can immediately begin executing the action from to the
policy corresponding to that observation. That is, having generated N policies
$[\pi(o_{k+1}=0),\pi(o_{k+1}=1),...,\pi(o_{k+1}=N)$, and received the
observation $o_{k+1}=1$, the policy $\pi(o_{k+1}=1)$ can be used to find
action $a_{k+1}$ without delay.

It must be noted that although this approach works well for all of the example
application problems considered here (as there are only two observations the
drone can receive during a movement action) it faces significant scalability
issues. Creating and choosing between significantly larger numbers of
predictive planning trees reduces the accuracy of the policy approximation
sharply, especially if many observations hold similar likelihoods. This can be
addressed in future work through a likelihood threshold to filter out rare
observations, combined with a heuristic to determine actions when such rare
observations are seen. Alternatively, observations could be collected into
meta-observations when they lead to similar beliefs, echoing the
discretization of observations spaces seen in [52].

###  III-I Observation Model Generation Pipeline

In order to produce data for simulated testing, as well as process human input
data, a single end-to-end pipeline was developed. This pipeline, shown in
Figure 5, is capable of generating sketches from distributions of variables of
interest such as number of sides, regularity, and size. Then the sketches,
whether generated by this automatic method or with a human, are processed in a
Monte-Carlo Auto-labeling to assign semantic labels before a Near Class
composite range model is extracted. The final result, an observation
likelihood specified by a set of softmax models, can then be used in both the
belief update and policy search processes. This allows testing to cover the
full range of possible human inputs in simulated experiments with minimal
human input beyond specified ranges of sketch input parameters, and allows
minimal effort construction of likelihood models in human testing using only
the input sketch. Details on individual elements of the pipeline are given in
Appendix A.

##  IV Simulated HARPS Results

Figure 10: Problem Setup: A UAS tracks a mobile ground target that can deviate
from road. The user has access to live camera views across the environment,
which they use to provide relevant information to help the UAS improve its
search.

The Human-Assisted Robotic Planning and Sensing (HARPS) environment was
developed in Unreal Engine 4 [53] to provide a physics based simulation on
which to test POMDP tracking problems with human input. A drone, controlled
through ROS [54] using the Microsoft Airsim API [55] attempts to localize,
track, and intercept a ground based target within an outdoor environment,
while interacting with the human through the sketch based interface shown in
Figure 11. This PYQT5 based interface inherits robot pull and human push
functionality from the CNR interface in [45], but populates the semantic
dictionary within from user sketches drawn directly on the map. Also similar
to CNR, the human can view the space either through a selection of security
cameras or through the robot’s on-board camera.

Figure 11: HARPS Human Sketch Interface

In order to assess the ability an online POMDP to work together with a human
to complete this task, a simulated human with a variety of parameters
generating sketches and observations using the methods of Section 5.10 was
first tested on a slightly simplified version of the HARPS environment built
in Python 3.5. This allowed for large batch testing to examine the POMDP’s
effectiveness and potential weak points prior to live human subject testing.

In all simulated runs, the drone was given $t_{max}=600s$ maximum flight time,
after which the run was considered a failure. Rather than pose actions as
simple directional objects (“North” and “South”) as in previous experiments,
HARPS used a graph-based POMDP navigation approach, which designated
intersections, or nodes, of the local road network as actions. In principle,
this is no different than designating 4 cardinal direction displacements as
actions, and thus requires minimal changes to the planner. Specifically, the
POMDP was allowed to choose any neighboring node, or neighbors of neighbors,
from its previous action:

$\displaystyle A_{m}^{t}=\cup n_{t+1}\in Neighbors(Neighbors(n^{t}))$ (16)

The use of such an action model opens the door to variable time actions, and
the use of Predictive Tree Planning techniques discussed in Section 5.8. The
robot was allowed to move at an average speed of $15\frac{m}{s}$, with
$\Sigma_{a}^{r}=1$ for all actions, while the target followed the switching
Markov dynamics model in the road network problem of Section 5.12.2, using an
average speed of $20\frac{m}{s},\Sigma_{a}^{t}=5$ while on the road and
$5\frac{m}{s},\Sigma_{a}^{t}=1$ while off-road.

Query actions $A_{q}$ were handled identically to those in 5.11.1, with the
exception that instead of being selected from a pre-drawn set all sketches
were generated in real-time using the PSEUD algorithm.

Rather than the circular detection assumption of Sections 5.11.1 and 5.12.2,
HARPS uses a conical model with a 30 degree viewcone $v_{c}$ for the robot
similar to that used in [45], with observation set:

$\mathcal{O}=\\{None,Detected,Captured\\}$ (17)

and observation likelihood model with a 98% accuracy:

$\displaystyle\Omega(Captured)=p(o=Captured|s)=.98,$ (18)
$\displaystyle\forall s|dist(s_{t},s_{r})\leq\tau\ \&\ s\in v_{c}$
$\displaystyle\Omega(Detected)=p(o=Detected|s)=.98,$ (19)
$\displaystyle\forall s|\tau\leq dist(s_{t},s_{r})\leq 2\tau\ \&\ s\in v_{c}$
$\displaystyle\Omega(None)=p(o=None|s)=.98,$ (20) $\displaystyle\forall
s|2\tau\leq dist(s_{t},s_{r})\ \&\ s\in v_{c}$

As HARPS takes place on a larger scale environment, with state space
$\mathcal{S}$ comprising a 1000m x 1000m area, the capture distance threshold
$\tau$ is set to 75m. However, the restriction of detection and capture to the
area under observation by viewcone $v_{c}$ limits the ability of the robot to
detect targets it is not directly facing as a result of movement actions
$A_{m}$.

The reward function was given a large positive reward of 100 for the capture
of the target within $\tau=75m$, and a small penalty of -1 for asking the
human a question.

All statistical testing in the simplified HARPS environment was conducted
using binomial significance tests on the ratio of successful captures by a
given method when compared to a control.

###  IV-A Human vs Nonhuman

(a) Effect of Human Input in Simulated HARPS Environment

(b) Effect of Predictive Tree Search Input in Simulated HARPS Environment

Figure 12: Performance for Simulated HARPS

Figure 12(a) compares the ability of the drone to intercept the target with
and without human assistance. Each case was tested with N=250 independent
trials, with significance being determined via Binomial Test. It is
particularly important to note that the POMDP is able to locate and intercept
the target in the majority of cases even without human intervention. With or
without the human’s information, the online POMDP is still approximating an
optimal policy for the information it has available. Far from minimizing the
improvement shown in the “Human” case, the significant $(p<0.05)$ discrepancy
with the “Nonhuman” case emphasizes that even an otherwise effective algorithm
can still benefit greatly from the introduction of additional human
information.

Qualitatively, the introduction of human information resulted in similar
behavioral changes as in [45]. For example, in Figure 13, without human input,
either sketches or semantic observations, the robot engages in a broad ranging
patrol behavior, prioritizing well connected nodes in the graph and eventually
capturing the target as it ventured through a high traffic area. However, the
human case of Figure 13 shows a more directed pursuit behavior, wherein the
robot moves quickly towards the target area indicated by the human before
firmly localizing and capturing the target. Note, this example does not imply
all human cases were so direct, nor all non-human cases so wandering. Rather,
it represents general behavior of each approach.

Figure 13: Representative example traces of the robot (green) and target (red)
showcasing Left: Patrol Behavior of Non-Human HARPS Case, and Right: Pursuit
Behavior with Human Information

###  IV-B Predictive Tree Search vs Blind Dynamics Updates

In Figure 12(b), the Predictive Tree Search method is tested against a naive
“blind” real-time planner. Each case was tested with N=100 independent trails,
with significance being determined via Binomial Test. In the blind case,
planning is also carried out during the execution of the previous action, but
using a belief predicated only on the expected dynamics update. This is
opposed to the Predictive method which probabilistically allocates planning
time among multiple possible observations to produce predicted measurement
updates in addition to the dynamics update. Of note, the blindness of the
blind method only applies to a single step, as the full measurement update
still occurs after the end of the current action, so it is at most one step
behind. Here the Predictive Tree Search approach produces significantly
$(p<0.05)$ more captures by drones operating with a battery-dictated 10 minute
search restriction. This may be attributable to the fact that the drone moves
at a slower speed than the target on the road, and therefore timely arrival of
a single positive measurement can have an out-sized effect on the ability of
the drone to capture the target before it escapes the local area.

###  IV-C Human Accuracy

Figure 14: Effect of True Human Accuracy vs Modeled Accuracy in Simulated
HARPS Environment.

After establishing the general effect of a human collaborator on the
effectiveness of the POMDP, specific attributes likely to vary between live
subjects were examined. First, human accuracy was tested, using values in the
set: $[.3,.5,.7,.9,.95]$. That is, for a value of $.7$, the human would
respond to questions correctly 70% of the time, and incorrectly 30% of the
time. These same values were tested as applied to the robot’s model of the
human, allowing the difference between the true and assumed sensor dynamics to
be examined. The full results of these tests, carried out for N=50 independent
trails for each combination of assumed and actual accuracy, are show in Figure
14. In particular, the results with regard to matched assumed and actual
accuracy are displayed in Figure 15 alongside the Binomial significance test
results for each pair-wise comparison. A human operating at 50% accuracy acts
as a random observation generator, and therefore does not produce
significantly more captures than the earlier “Nonhuman” case. The 30% case
allows the human observations to be taken in negative form, still allowing
useful information to be passed along.

The average effects of both assumed and actual accuracy are displayed in
Figure 16. The average true accuracy shows similar results to the match case,
with the averaging over assumptions compressing the range of results, while
the assumed accuracy displays no clearly significant effect. Naturally there
can be limits to such data in marginalized form, as examining the combined
effects in Figure 14 seems to indicate a slight advantage to a more
pessimistic view of the human. That is, the upper-left triangle of results in
which the human is more accurate than assumed performs slightly better on
average than the lower-right.

Figure 15: Effect of Matched Human Accuracy in Simulated HARPS Environment

Figure 16: Average effect of Actual Human Accuracy (left) and Assumed Human
Accuracy (right)

###  IV-D Human Availability

Figure 17: Effect of True Human Availability vs Modeled Availability in
Simulated HARPS Environment

Similar to accuracy, human availability was also tested across the same range
of assumed and true values, with the results aggregated in Figure 17. Given
the same size of N=50, the matched true to assumed results in Figure 18 do not
indicate a strong effect. However, examining the marginal result distributions
in Figure 19, there is a clear positive trend line for true human accuracy,
while the effect of the robot’s assumption of the human’s accuracy is minimal.

Figure 18: Effect of Matched Human Availability in Simulated HARPS Environment

Figure 19: Average effect of Actual Human Availability (top) and Assumed Human
Availability (bottom)

###  IV-E Sketch Rate

Finally, the rate at which a human inserts additional sketch entries into the
robot’s semantic dictionary was examined. Simulated humans drew sketches at a
constant rate drawn from: $[15,30,60,120]$ seconds. For completeness, a trial
was run in which the human was present but drew no sketches and introduced no
new semantic information. As expected, this case of an infinitely long average
sketching rate performed identically to the Nonhuman baseline. As shown in
Figure 20, there exists an optimal rate at which sketches provide a
sufficiently diverse semantic dictionary without over complicating the POMDP
with additional actions to consider. This optimum, which peaked around one
sketch per minute in this scenario, is likely highly problem dependent and
represents a consideration for future implementations of this work. It is
possible that, having established for a particular problem the near-optimal
sketch rate, human collaborators could be coached or trained to adhere to it.

Figure 20: Effect of Sketch Rate in Simulated HARPS Environment

These results taken together showcase the ability of the online POMDP planner
to adapt to the human it is given, rather than requiring a collaborator with
specific training or knowledge. Certainly more accurate and available humans
are of more use, but in no case tested across a range of simulated humans did
the drone do significantly worse than the Nonhuman baseline. This indicates
that in the worst of cases the POMDP is able to mitigate the effects of a poor
human, while maintaining its ability to effectively collaborate with others.

##  V Human Subject Studies

A user study was run to test the effectiveness of the proposed approach using
the same environment presented above. The goal of the study was to evaluate
the performance of the human-robot team with different communication abilities
(active, passive, both active and passive) and compare the difference to a
robot only approach.

The study was devised as a within-subjects experiment, which tested a total of
36 subjects with varying levels of experience with autonomy and UAS. Subjects
were tasked with assisting the drone in capturing the target in each of three
scenarios. They could observe the landscape for the target, or signs of the
target, using seven different camera views distributed across the environment.
Sketches could be added on an accompanying 2D map at any time, which also
displayed the drone’s location and previous path.

In the active only scenario, the subject could volunteer information only when
requested by the robot. For example, the robot could ask Is the target North
of the Farm?, to which the user could respond Yes, No or I don’t know. The
passive only scenario allows the subject to provide information without
request whenever possible. This modality offered the subject the ability to
provide positive or negative information about the target (is/is not),
relative location (Near, Inside, North, South, East, West) and the associated
sketch (The target is inside the mountains). Finally, the active/passive
scenario combined the capabilities in the previous two other scenarios,
allowing bi-directional communication between the robot and subject where the
robot queried the user and the subject provided additional information as they
saw fit. Unlike the work described in previous sections, subjects were unable
to provide observations regarding the target’s mode of travel (walking or
driving), in order to simplify the interaction.

Analysis of the results from the simulated user studies leads us to posit the
six following hypotheses for the human subject studies. Hypotheses 1,2,3 and 4
relate to objective measures whereas H5 and H6 correspond to subjective
measures.

H1: Respectively incremental human input for the three scenarios, from active
only, passive only, and active/passive will improve task performance.

H2: There exists a favorable frequency of human sketch input, such that too
many sketches result in inefficient algorithmic planning and performance and
too few sketches do not provide sufficient localization of the target.

H3: A more effective user, defined as having high levels of accuracy and
availability, will result in improved task performance.

H4: Subjects who had better situational awareness, defined as those who used
more viewpoints over time, will be more accurate.

H5: Subjects will have incrementally higher respective task loads for active
only, passive only, and active/passive scenarios.

H6: Subjects will report higher levels of trust towards the robot with more
interaction, with more accurate subjects reporting higher levels of trust.

H1 investigates the performance of the algorithm in context of the unique
modes available in an interaction. H2, H3 and H4 aim to evaluate the
algorithm’s ability to handle a range of user types. H5 and H6 will provide
insight into the user’s subjective view of the interaction with the robot
across the respective modes.

###  V-A Experimental Procedure

Upon recruitment to the study, subjects were given a briefing regarding the
purpose and scope of the experiment. The experimenter walked subjects through
the interface and showed a brief video of the interaction. Once a subject read
through the IRB approved consent form, they were assigned a subject ID number
and given the opportunity to experiment with the interface before starting the
three trials. For each subject, the scenario ordering and target location was
randomized to account for learning improvements. This proved valuable as
subjects often reported that they gained a better understanding of how to
interact with the robot over the course of the trials. For each scenario,
subjects were given a maximum of 15 minutes (900 seconds) to find the target
with the drone. After each scenario, the subject filled out a questionnaire to
rate their subjective workload and trust observations. Once all three
scenarios had been finished, the subject was paid using an Amazon gift card
and dismissed.

####  V-A1 Objective Measures

The objective measures used in this study can be broken down into metrics for
performance, defined by time to capture (TTC), and user characteristics, which
includes their accuracy, availability, sketch rate, and view rate.

Performance

  * •

Time to Capture: The time to capture is defined as the time taken from the
start of the simulation until the time where the robot came within 75m to the
target. If the drone failed to capture the target, then the TTC is not
reported, and the scenario updates the Capture Ratio for the respective run.

  * •

Capture Ratio: The Capture Ratio equals the number of successful captures
divided by the total number of runs for each category of scenario (n = 36).

User Characteristics

  * •

Accuracy: For each observation provided by the subject, either passively or
actively provided, an accuracy value can be reported using a softmax
approximation as defined in Section III. Equation 21 shows how the total
accuracy is calculated where $p_{o}$ is the softmax derived probability of the
target being in the assigned label and $p_{max}$ is the maximum possible
probability for that specific observation and target location. For comparison,
a heuristic compass approximation is also calculated based on 29 and whose
total value is calculated according to equation 22. In this equation, $p_{o}$
similarly refers to the probability of the target being in the assigned label,
although the definition constrains this value to $0.33\leq x\leq 1$.

$\displaystyle\mathbf{accuracy_{softmax}}$
$\displaystyle=\frac{1}{N}\sum_{o\in O}\frac{p_{o}}{p_{max}}$ (21)
$\displaystyle\mathbf{accuracy_{compass}}$
$\displaystyle=\frac{1}{N}\sum_{o\in O}\begin{cases}1&p_{o}\neq 0\\\
0&p_{o}=0\\\ \end{cases}$ (22)

  * •

Availability: The availability for the subject in each scenario can be
calculated as the total questions answered divided by the total number of
questions asked by the robot.

  * •

Sketch Rate: The sketch rate for each scenario equals the number of sketches
provided by the user divided by the scenario time. If the target was captured,
then the TTC is used as the scenario time, otherwise the duration of the
scenario (15 minutes) is used.

  * •

View Rate: The view rate, or the rate at which a subject looks at different
camera views, equals the total number of camera views divided by the scenario
time.

####  V-A2 Subjective Measures

At the conclusion of each trial, subjects were given questionnaires to assess
their subjective workload, measured by the NASA RTLX survey, and their trust
in the robot, using the Multi-Dimensional Measure of Trust (MDMT) survey.

The NASA Task Load Index (NASA-TLX) has been successfully applied across a
range of domains to gauge user workloads [56]. We used a modified version
known as the Raw TLX (RTLX) to simplify the questionnaires for the user. The
RTLX is the most common modification to the classic TLX survey [57]. It
dispenses with the relative weightings found in the classic TLX survey and
simply takes the average of six questions that were reported on a scale from 0
(very low) to 7 (very high).

The MDMT survey was developed as a novel measurement tool to asses human-robot
trust [58]. It gathers perceived trust across four differentiable dimensions,
Reliable, Capable, Ethical, and Sincere, which are respectively gaged by a
series of four questions. Each dimension can be further categorized into the
broader factors of Capacity Trust and Moral Trust of which we only focused on
Capacity Trust. Each question is evaluated on an 8-point scale from 0 (Not at
All) to 7 (Very) and can be ignored by the user if they deem it irrelevant.
The total reported workload for each trial is calculated as the average of the
answered questions.

###  V-B Results

Participants were recruited from across the University of Colorado Boulder
student body, as well as members of the local community. All 36 subjects were
between the ages of 18-65 and reported 20/20 or correctible to 20/20 vision.
While some subjects were professional UAS operators involved in surveying or
search and rescue capacities, others came from a background with no UAS,
aviation, or operational experience. There was also a range of experience with
decision making algorithms as 42% of subjects reported no subject matter
background and 25% reported high levels of familiarity. 21 of the subjects
reqported their gender as male, 14 as female and one as agender. As a baseline
metric of performance, the simulation was run without an active user ($n=40$).

####  V-B1 Performance

Results for subject performance are shown in Figure 21. The capture ratio for
each of the respective study modes shows a clear increase increase in capture
ratio with increasing levels of human interaction. When no human is present,
the robot captured the target only 47.5% of the time, compared to the active
human (77.8%), passive human (88.9%), and active/passive human (97.2%). Using
a binomial significance test, the user cases are shown to be significant to
$p<0.001$ when compared to the robot only situation. When the target was
captured by the robot, the mean time to capture is slightly higher for the
robot only case and does not have a significant variation across all of the
interaction modes. However, it is important to consider that the mean time to
capture does not account for instances where the robot failed to capture the
target. While the mean time to capture is not statistically significant on its
own, the doubling in capture ratio from the robot only mode to the
active/passive human mode, and incremental improvement across interaction
modes, substantiates hypothesis 1.

(a) Mean time to capture when the robot was captured

(b) Target capture ratio across all testing modalities.

Figure 21: Results for human performance Figure 22: Example of a successful
interaction using the active/passive mode. Figure 23: Example of a poor
interaction using the passive mode.

####  V-B2 User Type

The tested subject compromised a wide range of interaction styles and
consistencies. Figure 24 shows each subject’s performance across all three
scenarios sorted by mean time to capture. Some users, such as subjects 2, 3,4
and 5 showed consistently low mean time to captures. Alternatively other
users, such as subjects 32, 33, and 35 showed repeated failures to capture the
target and a wide standard error across their respective scenarios. There are
other instances, such as subject 1, where the target was captured primarily
through luck on one instance and failed to capture it on other modes of
interaction. These trends are indicative that the method by which the user
interacts with the agent can have a substantial effect in their resulting
performance. Analysis of sketch frequency, user accuracy, availability, and
camera views attempt to quantify the particular variables that influence the
success of each interaction.

Figure 24: Subject specific mean time to capture with associated standard
deviation. Colors tie to subject capture rate with red, yellow, and green
subjects having respectively captured the target 1/3 times, 2/3 times, and 3/3
times.

Users drew anywhere from 1 to a maximum of 14 sketches throughout the
simulation. While some users preferred to draw a series of sketches prior to
searching for the target, others would only draw sketches when the target had
been observed. Unlike the simulated HARPS environment, there was no clear
correlating trend for user performance and the number of sketches that had
been drawn. However, the scenarios with three of the top four highest number
of sketches drawn (14, 13, and 11 sketches), were not able to capture the
target. During these simulations, the robot displayed behaviour that was
characteristic of poor planning, such as repeated routes. Since the action
space grows exponentially with each added sketch, it makes intuitive sense
that significant numbers of sketches leads to inefficient planning. As
subjects were able to capture the target in less than two minutes with as few
as one sketch and as many as nine sketches, there does not prove to be a
favorable number or frequency of sketches that results in optimal performance,
therefore disproving hypothesis 2.

Accuracy for softmax and compass values were calculated according to equations
21 and 22. When accuracies are evaluated for all scenarios, there are no clear
correlations as capture times of 200 seconds maintained a wide range of values
from 0 (completely inaccurate) to 1 (completely accurate). This variance may
be due to users providing helpful information that wasn’t completely accurate
but drew the drone towards where they may have seen to target. A more
effective analysis compares each users’ overall accuracy to their mean TTC for
all three scenarios. These results are shown in Figure 25, which shows a
statistically significant ($p<0.05$) decreasing trend of lower user accuracy
leading to poor performance.

User availability did not show any clear trends when compared to user
performance. The average user availability was 57%, which reflects the fact
that users would answer about every other question. The frequency of questions
asked by the robot varied throughout the simulation. The unpredictable nature
caused some to users comment that it was challenging to notice that a question
was being asked and respond to it in a prompt and accurate manner. Wide
variability existed even for successful users as one subject captured the
target in 188 seconds with an availability of 31%, while another user finished
at 168 seconds with an availability of 80%. This observed contrast in
conjunction with the accuracy trends demonstrates that the quality of
information provided is more valuable than the quantity of observations.
Hypothesis 3 is therefore partially proven in that effective users are
primarily defined by higher accuracy, while availability is not a significant
factor.

Figure 25: Average user accuracy compared to their mean time to capture.
Colors indicate capture ratios of $3/3$, $2/3$, and $1/3$ for green, yellow
and red respectively.

While it was expected that user situational awareness could be captured by the
number of camera views, the trends are inconclusive. Users who observed more
cameras per second performed slightly better than others, however not enough
data is available to prove that this is indicative of a larger trend. There
was also no relationship between the view rate and user accuracy. These
results indicate that hypothesis 4 can be disproved.

####  V-B3 Subjective Metrics

Figure 26(a) shows the total workload across the three different user modes.
The total reported workload across all three conditions demonstrates minor
increases for active (3.2), passive (3.3), and active/passive (3.4)
modalities. Overall, the workload did not seem to be significant with one user
reporting that There was not a lot of workload. Methods of reporting workload
in a consistent manner across different subjects is an ongoing area of study
[57]. These challenges merit the consideration each subject’s relative ranking
of the workload for each mode. Some subjects evaluated workload equally across
scenarios, which resulted in a tie between certain rankings. Evaluating the
relative workload from this perspective in Figure 26(b), the active/passive
condition displays the highest workload for all conditions. Hypothesis 7 can
be partially substantiated by this claim, however only in the fact that the
active/passive condition had the highest level of workload, whereas the
passive and active scenarios displayed relatively equal rankings across
subjects.

(a) Total workload across all scenarios

(b) Each subject’s relative workload ranking across all scenarios

Figure 26: Results for user workload

Figure 27 shows the total trust across the respective user modes. Evaluated
using a Student‘s T-test, there is a statistically significant ($p<0.07$)
difference between the reported trust for the active/passive case versus the
passive case, which had the lowest overall trust. This was unexpected as in
that the active mode had a slightly higher trust in comparison to the passive
mode. In post simulation questionnaires, one subject noted that Having the
drone ask questions and respond according to my answers built trust. This may
be indicative that giving the agent the capability to ask questions provides
the user insight into its understanding of the mission. In evaluating
hypothesis 6, there are no clear trends between user trust and user accuracy.
However, a clear trend developed between user trust and scenario mean time to
capture, with lower time to capture strongly correlating to higher trust
($p<0.01$).

(a) Total robot trust across all scenarios

(b) Correlation between user trust and performance across all scenarios

Figure 27: Results for user trust

###  V-C Discussion

The human subject studies demonstrate that the proposed algorithm maintains
strong performance while reasoning over users that display wide ranges of
accuracies and behaviors. The interaction did not significantly burden the
users and the ability to offer bi-directional communication improved user’s
trust in the robot. Detailed user training may also improve the frustration
felt by several users by clarifying robot intent and behavior.

Calculating the user’s accuracy as a single number disposes of the nuance in
each observation. For example, the interaction in Figure 22 shows the user
providing an objectively incorrect first observation that the target was
inside sketch area1. However, this information compelled the robot to move in
that general direction and follow up questions to the user narrowed the
robot’s belief of the target resulting in a capture. In this interaction, the
user likely confused the proper location of the target on the 2D map, favoring
a prompt coarse observation in the target’s general vicinity.

In a different scenario, the user knowingly provided false information in
order to steer the drone away from the town at the NW corner of the map. Due
to the density of roads in this area, the drone often gravitated in this
direction and user observations were helpful in getting it to explore other
areas. In this case, a negative observation that the target was not in the
town would have been equally helpful. Once out of the town, a subsequently
accurate observation by the user helped the robot catch the target.

Despite these nuances, the significant trend correlating user’s overall
softmax accuracy to performance, in comparison to the cruder compass metric,
validates the implementation of the softmax approximation.

Notably, the algorithm encouraged users to interact with the interface in a
personalized manner. Figure 28 shows how users chose to draw sketches around
notable landmarks, at camera locations, or solely around the perceived target.
Each of these methods resulted in the target being captured, particularly if
the observations provided were followed up from numerous reference points.
Users that failed to perform adequately often did not treat the robot as a
teammate, instead trying to direct the drone to regions that they wanted it to
visit, such as in Figure 23, or giving a standalone observation from a single
reference point. While standalone observations were considered sufficient by
some users, the robot’s ability to ask follow-up questions showed an
improvement in performance and a significant increase in user trust. However,
numerous subjects reported frustration in dealing with the robot as it seemed
to not take their observations into account. The drone displayed complex
behavior, such as not going directly to the area mentioned to cut-off possible
escape locations. Sometimes, this frustration turned to surprise as the target
was subsequently caught, such as when one user noted, I still couldn’t figure
out what the robot was doing sometimes and why it was flying in certain
directions. This made me think it wasn’t as consistent and predictable. It was
quite competent in the end at accomplishing the task. Subjects mentioned that
continued interactions with the robot improved their understanding of
effective interaction methods commenting that, I think the practice from the
previous rounds made it easier to determine what to do this round. In our
study, the subject briefing was left intentionally vague to evaluate the
intuitive nature of the interaction. However, like any collaborative task with
a teammate, joint training would likely improve performance as robot behavior
becomes less opaque.

Figure 28: A collection of user sketches and interactions. In these
interactions user a captured the target in 436s in the passive mode, user b
captured the target in 288s in the active mode, user c captured the target in
575s in the active/passive mode, and user d failed to capture the target in
the active/passive mode likely due to the significant number of sketches
resulting in poor planning.

To improve the collaborative nature of the searching task, future work may
incorporate non-binary observations of the target. For example, instead of
only being offered an option of Is/Is not, a user could express their own
uncertainty with nuanced observations such as probably/probably not. While
these observations would be more challenging for the robot to reason through,
the user may be compelled to provide extra information when they have only a
vague understanding of the target location. Adding degrees of uncertainty to
observations naturally extends the uncertainty enabled through the sketch-
based interface and replicates how humans communicate to each other in dynamic
environments.

##  VI Conclusion

We proposed and demonstrated a novel approach to multi-level active semantic
sensing and planning in human-robot teams in unknown dynamic environments. Our
solution extends online POMDP planning frameworks to incorporate semantic soft
data from a human sensor about the location of a tracked target as well as
relevant terrain information. Such information is propagated from human to
robot through the use of a sketch based, natural language interface. This
approach provides a novel formulation of a POMDP with a “human-in-the-loop”
active sensing model, as well as innovations to the use of soft-data fusion as
applied to higher level modal information. We demonstrated our approach on two
example problems and applied it in a human subject study. The first showcased
the improvements queries to a human can bring to target search problems, while
the second demonstrated that the incorporation of human information even with
regard to higher level mode observations can improve a robot’s target search
ability. Finally, the human subject studies validated the effectiveness of the
algorithm in extracting information from users in a wide range of interaction
styles, and showed that active querying increased user trust in the robot
without adding excessive workload.

Moving forward, research will examine the effect of inaccurate or incomplete
sketches on the part of the human. Pairing the robot with a visual object
detector has potential to allow feedback to ensure that the robot’s perception
of the object or region is consistent with a sketch. Additionally, the human
query framework presented here is readily extensible to allow queries
regarding hybrid-switching mode dynamics, which will be explored in follow up
work. Finally, future implementations of this approach in hardware will enable
more effective and intuitive interaction with autonomous systems.

## References

  * [1] S. McGuire, P. M. Furlong, C. Heckman, S. Julier, D. Szafir, and N. Ahmed, “Failure is not an option: Policy learning for adaptive recovery in space operations,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 3, pp. 1639–1646, 2018.
  * [2] J. Delmerico, S. Mintchev, A. Giusti, B. Gromov, K. Melo, T. Horvat, C. Cadena, M. Hutter, A. Ijspeert, D. Floreano _et al._ , “The current state and future outlook of rescue robotics,” _Journal of Field Robotics_.
  * [3] M. Dunbabin and L. Marques, “Robots for environmental monitoring: Significant advancements and applications,” _IEEE Robotics & Automation Magazine_, vol. 19, no. 1, pp. 24–39, 2012.
  * [4] M. Hutter, R. Diethelm, S. Bachmann, P. Fankhauser, C. Gehring, V. Tsounis, A. Lauber, F. Guenther, M. Bjelonic, L. Isler _et al._ , “Towards a generic solution for inspection of industrial sites,” in _Field and Service Robotics_. Springer, 2018, pp. 575–589.
  * [5] M. Goodrich, B. Morse, C. Engh, J. Cooper, and J. Adams, “Towards using unmanned aerial vehicles (uavs) in wilderness search and rescue: Lessons from field trials,” _Interaction Studies_ , vol. 10, pp. 453–478, 2009.
  * [6] R. A. David and P. Nielsen, “Defense science board summer study on autonomy,” Defense Science Board Washington United States, Tech. Rep., 2016.
  * [7] J. M. Bradshaw, R. R. Hoffman, D. D. Woods, and M. Johnson, “The seven deadly myths of” autonomous systems”,” _IEEE Intelligent Systems_ , vol. 28, no. 3, pp. 54–61, 2013.
  * [8] F. Bourgault, A. Chokshi, J. Wang, D. Shah, J. Schoenberg, R. Iyer, F. Cedano, and M. Campbell, “Scalable bayesian human-robot cooperation in mobile sensor networks,” in _2008 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2008, pp. 2342–2349.
  * [9] T. Kaupp, A. Makarenko, and H. Durrant-Whyte, “Human–robot communication for collaborative decision making—A probabilistic approach,” _Robotics and Autonomous Systems_ , vol. 58, no. 5, pp. 444–456, 2010.
  * [10] S. Rosenthal, M. Veloso, and A. K. Dey, “Learning accuracy and availability of humans who help mobile robots,” in _Twenty-Fifth AAAI Conference on Artificial Intelligence_ , 2011.
  * [11] A. N. Bishop and B. Ristic, “Fusion of spatially referring natural language statements with random set theoretic likelihoods,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 49, no. 2, pp. 932–944, 2013.
  * [12] N. R. Ahmed, E. M. Sample, and M. Campbell, “Bayesian multicategorical soft data fusion for human–robot collaboration,” _IEEE Transactions on Robotics_ , vol. 29, no. 1, pp. 189–206, 2013.
  * [13] N. Sweet and N. Ahmed, “Structured synthesis and compression of semantic human sensor models for Bayesian estimation,” in _2016 American Control Conference (ACC)_. IEEE, 2016, pp. 5479–5485.
  * [14] M. Skubic, C. Bailey, and G. Chronis, “A sketch interface for mobile robots,” in _SMC’03 Conference Proceedings. 2003 IEEE International Conference on Systems, Man and Cybernetics. Conference Theme-System Security and Assurance (Cat. No. 03CH37483)_ , vol. 1. IEEE, 2003, pp. 919–924.
  * [15] S. Tellex, T. Kollar, S. Dickerson, M. R. Walter, A. G. Banerjee, S. Teller, and N. Roy, “Understanding natural language commands for robotic navigation and mobile manipulation,” in _Twenty-Fifth AAAI Conference on Artificial Intelligence_ , 2011.
  * [16] D. Shah, J. Schneider, and M. Campbell, “A sketch interface for robust and natural robot control,” _Proceedings of the IEEE_ , vol. 100, no. 3, pp. 604–622, 2012.
  * [17] C. Matuszek, E. Herbst, L. Zettlemoyer, and D. Fox, “Learning to parse natural language commands to a robot control system,” in _Experimental Robotics_. Springer, 2013, pp. 403–415.
  * [18] T. M. Howard, S. Tellex, and N. Roy, “A natural language planner interface for mobile manipulators,” in _2014 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2014, pp. 6652–6659.
  * [19] F. Duvallet, M. R. Walter, T. Howard, S. Hemachandra, J. Oh, S. Teller, N. Roy, and A. Stentz, “Inferring maps and behaviors from natural language instructions,” in _Experimental Robotics_. Springer, 2016, pp. 373–388.
  * [20] R. Paul, J. Arkin, N. Roy, and T. M Howard, “Efficient grounding of abstract spatial concepts for natural language interaction with robot manipulators,” 2016\.
  * [21] E. Sample, N. Ahmed, and M. Campbell, “An experimental evaluation of bayesian soft human sensor fusion in robotic systems,” in _AIAA Guidance, Navigation, and Control Conference_ , 2012, p. 4542.
  * [22] W. Koch, “On exploiting “negative” sensor evidence for target tracking and sensor data fusion,” _Information Fusion_ , vol. 8, no. 1, pp. 28–39, 2007\.
  * [23] K. G. Lore, N. Sweet, K. Kumar, N. Ahmed, and S. Sarkar, “Deep value of information estimators for collaborative human-machine information gathering,” in _Proceedings of the 7th International Conference on Cyber-Physical Systems (ICCPS 2016)_. IEEE Press, 2016, pp. 3–12.
  * [24] L. Burks, I. Loefgren, L. Barbier, J. Muesing, J. McGinley, S. Vunnam, and N. Ahmed, “Closed-loop Bayesian semantic data fusion for collaborative human-autonomy target search,” in _2018 21st International Conference on Information Fusion (FUSION 2018)_. IEEE, 2018, pp. 2262–2269.
  * [25] L. Burks and N. Ahmed, “Collaborative semantic data fusion with dynamically observable decision processes,” in _2019 22nd International Conference on Information Fusion_. IEEE, 2019.
  * [26] F. Boniardi, B. Behzadian, W. Burgard, and G. D. Tipaldi, “Robot navigation in hand-drawn sketched maps,” in _2015 European conference on mobile robots (ECMR)_. IEEE, 2015, pp. 1–6.
  * [27] N. Ahmed, M. Campbell, D. Casbeer, Y. Cao, and D. Kingston, “Fully bayesian learning and spatial reasoning with flexible human sensor networks,” in _Proceedings of the ACM/IEEE Sixth International Conference on Cyber-Physical Systems_. ACM, 2015, pp. 80–89.
  * [28] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra, “Planning and acting in partially observable stochastic domains,” _Artificial Intelligence_ , vol. 101, no. 1-2, pp. 99–134, 1998.
  * [29] S. Ross, B. Chaib-draa, and J. Pineau, “Bayes-adaptive pomdps,” in _Advances in neural information processing systems_ , 2008, pp. 1225–1232.
  * [30] J. Pineau, G. Gordon, S. Thrun _et al._ , “Point-based value iteration: An anytime algorithm for POMDPs,” in _2003 International Joint Conference on Artificial Intelligence (IJCAI 2003)_ , vol. 3, 2003, pp. 1025–1032.
  * [31] M. T. Spaan and N. Vlassis, “Perseus: Randomized point-based value iteration for POMDPs,” _Journal of Artificial Intelligence Research_ , vol. 24, pp. 195–220, 2005.
  * [32] D. Silver and J. Veness, “Monte-Carlo planning in large POMDPs,” in _Advances in neural information processing systems_ , 2010, pp. 2164–2172.
  * [33] Z. N. Sunberg and M. J. Kochenderfer, “Online algorithms for pomdps with continuous state, action, and observation spaces,” in _Twenty-Eighth International Conference on Automated Planning and Scheduling_ , 2018.
  * [34] A. Goldhoorn, A. Garrell, R. Alquézar, and A. Sanfeliu, “Continuous real time POMCP to find-and-follow people by a humanoid service robot,” in _2014 IEEE-RAS International Conference on Humanoid Robots_. IEEE, 2014, pp. 741–747.
  * [35] W. Koch, “On ‘negative’information in tracking and sensor data fusion: Discussion of selected examples,” in _Proceedings of the Seventh International Conference on Information Fusion_ , vol. 1. IEEE Publ. Piscataway, NJ, 2004, pp. 91–98.
  * [36] M. L. Littman, A. R. Cassandra, and L. P. Kaelbling, “Learning policies for partially observable environments: Scaling up,” in _Machine Learning Proceedings 1995_. Elsevier, 1995, pp. 362–370.
  * [37] N. Armstrong-Crews and M. Veloso, “Oracular partially observable markov decision processes: A very special case,” in _Proceedings 2007 IEEE International Conference on Robotics and Automation_. IEEE, 2007, pp. 2477–2482.
  * [38] ——, “An approximate algorithm for solving oracular pomdps,” in _2008 IEEE International Conference on Robotics and Automation_. IEEE, 2008, pp. 3346–3352.
  * [39] S. Rosenthal and M. Veloso, “Modeling humans as observation providers using pomdps,” in _2011 RO-MAN_. IEEE, 2011, pp. 53–58.
  * [40] V. V. Unhelkar, S. Li, and J. A. Shah, “Semi-supervised learning of decision-making models for human-robot collaboration,” in _Proceedings of the Conference on Robot Learning_ , ser. Proceedings of Machine Learning Research, vol. 100. PMLR, 30 Oct–01 Nov 2020, pp. 192–203. [Online]. Available: http://proceedings.mlr.press/v100/unhelkar20a.html
  * [41] ——, “Decision-making for bidirectional communication in sequential human-robot collaborative tasks,” in _Proceedings of the 2020 ACM/IEEE International Conference on Human-Robot Interaction_. New York, NY, USA: Association for Computing Machinery, 2020, pp. 329––341. [Online]. Available: https://doi.org/10.1145/3319502.3374779
  * [42] S. Nikolaidis, M. Kwon, J. Forlizzi, and S. Srinivasa, “Planning with verbal communication for human-robot collaboration,” _J. Hum.-Robot Interact._ , vol. 7, no. 3, Nov. 2018. [Online]. Available: https://doi-org.colorado.idm.oclc.org/10.1145/3203305
  * [43] E. Rosen, N. Kumar, N. Gopalan, D. Ullman, G. Konidaris, and S. Tellex, “Mixed reality as a bidirectional communication interface for human–robot interaction,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2020, pp. 1–9.
  * [44] L. Burks, I. Loefgren, and N. R. Ahmed, “Optimal continuous state pomdp planning with semantic observations: A variational approach,” _IEEE Transactions on Robotics_ , 2019.
  * [45] L. Burks, N. Ahmed, I. Loefgren, L. Barbier, J. Muesing, J. McGinley, and S. Vunnam, “Collaborative human-autonomy semantic sensing through structured pomdp planning,” _Robotics and Autonomous Systems_ , vol. 140, p. 103753, 2021.
  * [46] N. R. Ahmed, “Data-free/data-sparse softmax parameter estimation with structured class geometries,” _IEEE Signal Processing Letters_ , vol. 25, no. 9, pp. 1408–1412, Sep. 2018.
  * [47] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word representations in vector space,” _arXiv preprint arXiv:1301.3781_ , 2013\.
  * [48] E. Brunskill, L. P. Kaelbling, T. Lozano-Pérez, and N. Roy, “Planning in partially-observable switching-mode continuous domains,” _Annals of Mathematics and Artificial Intelligence_ , vol. 58, no. 3-4, pp. 185–216, 2010\.
  * [49] A. Somani, N. Ye, D. Hsu, and W. S. Lee, “DESPOT: Online POMDP planning with regularization,” in _Advances in neural information processing systems_ , 2013, pp. 1772–1780.
  * [50] H. Kurniawati and V. Yadav, “An online pomdp solver for uncertainty planning in dynamic environment,” in _Robotics Research_. Springer, 2016, pp. 611–629.
  * [51] M. Egorov, Z. N. Sunberg, E. Balaban, T. A. Wheeler, J. K. Gupta, and M. J. Kochenderfer, “POMDPs.jl: A framework for sequential decision making under uncertainty,” _Journal of Machine Learning Research_ , vol. 18, no. 26, pp. 1–5, 2017. [Online]. Available: http://jmlr.org/papers/v18/16-300.html
  * [52] J. M. Porta, N. Vlassis, M. T. Spaan, and P. Poupart, “Point-based value iteration for continuous POMDPs,” _Journal of Machine Learning Research_ , vol. 7, no. Nov, pp. 2329–2367, 2006.
  * [53] Epic Games, “Unreal engine.” [Online]. Available: https://www.unrealengine.com
  * [54] Stanford Artificial Intelligence Laboratory et al., “Robotic operating system.” [Online]. Available: https://www.ros.org
  * [55] S. Shah, D. Dey, C. Lovett, and A. Kapoor, “Airsim: High-fidelity visual and physical simulation for autonomous vehicles,” in _Field and Service Robotics_ , 2017. [Online]. Available: https://arxiv.org/abs/1705.05065
  * [56] S. G. Hart and L. Staveland, “Development of nasa-tlx (task load index): Results of empirical and theoretical research,” _Advances in Psychology_ , vol. 52, pp. 139–183, 1988.
  * [57] S. G. Hard, “Nasa-task load index (nasa-tlx); 20 years later,” in _In Proceedings of the Human Factors and Ergonomics Society Annual Meeting_ , vol. 50. Sage Publications, 2006, pp. 904–908.
  * [58] D. Ullman and B. F. Malle, “Measuring gains and losses in human-robot trust: Evidence for differentiable components of trust,” in _Proceedings of the 14th ACM/IEEE International Conference on Human-Robot Interaction_ , pp. 618–619.

##  Appendix A Appendix Section Name

###  A-A Parameterized Sketch Generation

A distinct drawback of human-robot interaction research is the time associated
with collecting human subject test data. For this work in particular, the
tightly integrated planning and sensing at the core of information gathering
problems further complicates the collection of human data, as the POMDP must
be run in real-time while simultaneously receiving real-time input from a
human. Also, while observations from a given softmax model can be drawn
probabilistically to simulate a human response, the motivating problem
requires the real-time generation of new softmax models from sketches. Thus
gathering large sample sizes becomes extremely time intensive. However, such
sample sizes are highly desirable for the purpose of investigating the value
of online POMDPs in human-robot teams.

This section describes the Parameterized Sketching Emuluator Utilizing vertex
Downsampling (PSEUD), Developed for the purpose of investigating the response
and efficacy online human-interacting POMDPs. PSEUD allows the generation of
convex sketched polygons according to a learnable set of parameters,
effectively drawing a sketch from a distribution of identically parameterized
sketches. In this way, the effect of a human’s sketch input on the POMDP can
be quantified for a broad variety of possible sketching styles and
idiosyncrasies, even those likely to represent rare edge cases in the actual
human population.

A 2D PSEUD sketch is parameterized as the 5-tuple
$\\{\mathcal{X},r,\sigma,\lambda,\psi\\}$. The centroid
$\mathcal{X}=\\{x,y\\}$ and characteristic size $r$ are left as features
dependent on a given landmark around which the sketch is being made.
Specifically, in this work, both $\mathcal{X}$ and $r$ are defined in the 2D
plane corresponding to the target state $s_{t}$, while more generally they are
defined whichever state space plane the sketch is being drawn on. The chosen
landmark might be a choice from a pre-selected set, or generated autonomously
using computer vision object recognition approaches. In either case, $r$
serves as the Gaussian mean distance away from the centroid, with some
standard deviation $\sigma$, such that for a given vertex $v$ in a
hypothetical sketch object $h$ to be simulated the distance of the vertex from
the centroid is drawn from the distribution:

$\displaystyle|\vec{\mathcal{X}v}|\sim\mathcal{N}(r,\sigma)$ (23)

Where $|\vec{\mathcal{X}v}|$ denotes the magnitude of the vector from the
centroid to $\mathcal{X}$ to the vertex $v$. The number of vertices $N_{v}$ is
distributed according to a shifted Poisson Distribution, with mean $\lambda$.
The distribution is shifted uniformly upward by three, with support on
$\mathcal{R}\in[3,\infty]$, ensuring that sketches are at a minimum triangles.

$\displaystyle N_{v}\sim 3+Pois(\lambda)$ (24)

For a given $N_{v}$, the requirement that the angles of a convex polygon sum
to $2\pi$ radians reveals a nominal angular distance between each point of
$\hat{\Delta\theta}=\frac{2\pi}{N_{v}}$ radians. To capture the irregularity
of a sketched polygon, the angular noise parameter $\psi$ is used, such that
$\hat{\Delta\theta}$ and $\psi$ specify a Gaussian distribution on angular
distance. For a vertex $v$, the angular distance to the next vertex is drawn
as

$\displaystyle\Delta\theta\sim\mathcal{N}(\hat{\Delta\theta},\psi)$ (25)

The process for drawing vertices from the distribution specified by the
5-tuple $\\{\mathcal{X},r,\sigma,\lambda,\psi\\}$ is summarized in Algorithm
3.

Algorithm 3 Parameterized Sketching Emulator Utilizing vertex Downsampling

1: Function: $PSEUD$

2: Input: Centroid $\mathcal{X}$, Radius $r$, Sd $\sigma$, Poisson Mean
$\lambda$, Angular Noise $\phi$

3: Vertex Set $\\{V\\}=\emptyset$

4: Magnitude List $\textit{mags}=[]$

5: Angle List $\textit{angles}=[]$

6: $N_{v}\sim 3+Pois(\lambda)$

7: for $i\in N_{v}$ do

8: $\textit{mags}_{i}\sim\mathcal{N}(r,\sigma)$

9: $\textit{angles}_{i}\sim\mathcal{N}(\hat{\Delta\theta},\psi)$

10: end for

11: angles = Normalize(angles,2$\pi$)

12: $\theta=\textit{angles}_{0}$ #Starting angle

13: for $i\in N_{v}$ do

14:
$V_{i}=\mathcal{X}+[\textit{mags}_{i}cos(\theta),\textit{mags}_{i}sin(\theta)]$

15: $\Delta\theta=\textit{angles}_{i}$

16: $\theta+=\Delta\theta$

17: end for

18: return $\\{V\\}$

Using PSEUD, sketches can be drawn from the distribution of sketches carrying
the same parameterization, allowing high fidelity testing of each parameters
effect on POMDP performance. These sketches, represented by their vertices can
then be directly converted into softmax observation models using the
techniques of [13], as described in 5.7.1. For example, both of the sketches
shown in Figure 29 are drawn from a single parameterizied distribution, and
yield similarly structured softmax models.

Figure 29: Two draws from the PSEUD Algorithm for a given centroid {x,y} and
radius $(r)$

###  A-B Monte Carlo Auto-labeling

Once a softmax observation model has been generated, whether by a real human
or through a simulator such as PSEUD, the individual softmax classes can be
mapped onto semantic labels for further human interaction. In the Cops and
Robots experiment of [45], this mapping was largely defined by hand offline to
be 1-to-1, with a particular class label index always corresponding to ‘South’
for instance. This was enabled by assuming that the 2D spatial extent of all
known semantic reference objects could be represented by simple Cartesian-
aligned rectangles, so that softmax parameters for semantic classes describing
4 canonical bearings relative to the reference object needed to be specified.
The use of free-form ad-hoc sketches leaves little room for such restrictions.
For instance, in either of the sketches in Figure 29, it is unclear which of
the classes would receive the exclusive use of the label ‘North’, and indeed
it seems unwieldy to attempt such a hard classification. This suggests that a
soft classification approach could be used, disassociating the semantic labels
from tight correspondence with individual classes.

To start this process, a new set of conditional probabilities are defined as
the probability that a state drawn from softmax class $(c)$ would be
associated with the relational label $(l)$, $p(label=l|class=c)$, and the
probability that a given human observation $o_{h}$ arising from a query action
$a_{q}$ corresponding to semantic label $l$ was referring to the current state
being associated with softmax class $c$, $p(class=c|a_{q}=l,o_{h}=Yes)$, or
more succinctly $p(class=c|label=l)$. That is, given that the human indicated
the state was associated with relational label $(l)$, with what probability
the true state would have been drawn from softmax class $(c)$ The generative
process used to build the POMCP planning tree will rely on
$p(label=l|class=c)$, $p(l|c)$ for short, while updating the target belief
distribution requires $p(class=c|label=l)$, $p(c|l)$. Both conditional
distributions can be derived from the joint probability distribution $p(c,l)$.
In order to find this distribution, first a canonical semantic bearing model
$L$ with overlapping 90 degree increments is assumed. Each semantic label,
corresponding to the 8-point set of cardinal directions, covers an angular
distance of 90 degrees, and overlaps by 45 degrees with the labels on either
side. For instance, a point at $\frac{\pi}{4}$ radians or 45 degrees
counterclockwise above the horizontal in this canonical model can be
accurately labeled ‘North’, ‘NorthEast’, or ‘East’, while a point at 60
degrees counterclockwise above the horizontal can be labeled only ‘North’ or
‘NorthEast’. Such a model can be represented as an overlapping piece-wise
function on the angle $\theta$ made by state $(s)$ with the horizontal,
generating labels $(l)$,

$\displaystyle L(s)=\begin{cases}NorthEast&0\leq\theta\leq 90\\\
North&45\leq\theta\leq 135\\\ NorthWest&90\leq\theta\leq 180\\\
West&135\leq\theta\leq 225\\\ ...\end{cases}$ (26)

Note, the overlapping nature of this function allows for the return of a set
of labels, rather than a single label. This further suggests the possibility
of a softmax representation, which will be explored in future work. Here the
probabilistic representation $p(l\in L(s)|s)$ is used to describe the current
deterministic function to preserve generality.

In order to find the joint probability $p(c,l)$, it is necessary to calculate
the integral of the product of the class and label probability over the state
space.

$\displaystyle p(c,l)=\int_{s\in S}p(c|s)p(l\in L(s)|s)ds$ (27)

While the label term $p(l\in L(s)|s)$ can only take values 0 or 1, as it
describes a deterministic piece-wise function, the integral over the softmax
function $p(c|s)$ is analytically intractable [12]. Therefore, a Monte Carlo
approach is used to approximate the integral, selecting $J$ states
$s\in\mathcal{S}$ to carry out the summation:

$\displaystyle p(c,l)=\frac{1}{J}\sum_{j=1}^{J}p(c|s_{j})p(l\in
L(s_{j})|s_{j})$ (28)

From this joint distribution, both the conditional probabilities $p(c|l)$ and
$p(l|c)$ can be easily obtained. The former is used within the Bayesian belief
update to find $p(s|l)$,

$\displaystyle p(s|l)=\sum_{c}p(s|c)p(c|l)$ (29)

while the later is used to generate semantic labels from belief states during
the planning phase through $p(l|s)$,

$\displaystyle p(l|s)=\sum_{c}p(l|c)p(c|s)$ (30)

Again, in this instance $p(c|l)$ corresponds to
$p(class=c|a_{q}=l,o_{h}=Yes)$, such it serves as a probabilistic mapping from
human information to a set of mathematical objects after a robotic query.

While this approximation approaches the true joint distribution with infinite
samples, it is necessary in practice to choose a finite number of points.
While these would typically be randomly scattered throughout the state space
to avoid sampling bias, the number of points required to achieve an accurate
approximation could be rather high. To limit computational expense, while
preserving the approximation’s accuracy, this work leverages the determinism
and radial symmetry of the piece-wise canonical bearing model $L$ by using a
set of points uniformly distributed on $\theta$ at a constant radius. This
method is illustrated in Figure 30, where the softmax model on the left is
evaluated using the ring of Monte Carlo points on the right.

Figure 30: An irregular softmax model with numbered class labels (left)
The Monte Carlo approximation points used to approximate semantic class labels
(right)

This approximation yields the conditional probability distributions shown in
Figure 31. These distributions, substantially similar to those found using a
dense random sampling method with 10000 points, were found using only a
sampled ring of 360 points. Furthermore, they correspond to intuition
regarding the semantic labels. From model in Figure 30, $p(class|label)$ in
Figure 31 indicates that an observation ‘South’ of the object in question
could only reasonably be associated with class 4, while $p(label|class)$
indicates that states sampled from class 4 would likely be labeled either
‘SouthWest’, ‘South’, or ‘SouthEast’.

Figure 31: Conditional probability tables derived from Monte Carlo Auto-
labeling

###  A-C Composite Range Models

While the Monte Carlo Auto-labeling technique described in the previous
section establishes a probabilistic correspondence between softmax classes and
the type of semantic labels a human would use, the interior class based method
of building softmax models used in [44, 24, 25] is limited in its ability to
express range information. The target can be described as “Inside” the sketch
if it is literally within the bounds of the sketched convex polygon, or as
“Not Inside”, in which case it can be anywhere else in the state space. In
many applications, including the motivating problem for this work, it is
desirable to express when the target is in the general vicinity of the sketch,
when it is “Near” or “Near NorthEast” to a particular landmark. Previous work
[12] constructed such range-bearing softmax models using hand crafted classes
for specific range-bearing combinations (“Near Northeast”), and used an
multimodal softmax (MMS) model summing together a set of classes to express
range only measurements (“Near”).

Here an alternative method is proposed for constructing range labels which is
more applicable to ad-hoc sketch-based softmax models. Here, the range softmax
model is constructed based on the structure of the sketch before being
combined with the sketched bearing model in a product softmax model [13].
Specifically, this section and the following text make use of a single label
“Near” range model, rather than the multiple option range models of previous
work.

The “Near” class is first assumed to hold an identical, yet inflated, shape to
the original interior softmax class, which has conditional probability
$p(Inside|s)$. That is to say, the vertices of the near model are an affine
transform of the original vertices such that the area they encompass is a
scalar multiple $h$ of the previous area. The interior class of these inflated
points can be applied as a product softmax model as shown in 32, under the
assumption that range and bearing are independent, such that

$\displaystyle p(Near,Bearing|s)=p(Near|s)p(Bearing|s)$ (31)

Thus, a point can be evaluated against both models separately to determine the
probability it was drawn from the composite joint range-bearing class label.
This work only considers the use of the “Near” range observation, with
observations outside the range models interior class carrying no explicit
range information. In such a framework, the negative observation “Not Near”
serves as a proxy for the implicit observation “Far”. In principle, rather
than being restricted to binary range information, additional affine
transforms of larger size can be applied to indicate any number of semantic
ranges. However, such models would necessarily overlap and fully contain the
smaller “Near” interior class, such that for some hypothetical “Near/Far”
range model it must be assumed that any observation “Far” is actually the
compound observation “Far and Not Near”:

$\displaystyle p(Far,~{}Near|s)=p(Far|s)(1-p(Near|s))$ (32)

In this way, Eq. 31 can be generalized, with the assumption of range-bearing
independence intact, to:

$\displaystyle p(Range,Bearing|s)=p(Range|s)p(Bearing|s)$ (33)

A cleaner approach to be explored in future work would be the use of softmax
models specified directly in range space, such that “Near” and “Far” could
correspond to 2 different classes within the same function rather than 2
separate functions. However, this approach would neglect the shape information
from the sketch preserved in the affine transform method, a trade-off to be
further explored. The example problems in the following sections are
restricted to the “Near” only range models.

Figure 32: Composite Range and Bearing Softmax Model

##  Appendix B Appendix Section Name