Computer Science
Computer Science-2021.gz:143305
Computer Science
de481ee1532970e9da4ff3f3d138f93bf34af9ab
Semantic Sensing and Planning for Human-Robot Collaboration in Uncertain Environments

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 humanrobot teams which addresses these gaps by formally combining the benefits of online sampling-based POMDP policies, multimodal 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 languagebased human-robot communication have gained considerable attention for information fusion [8]- [13] and task planning [14]- [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 This work examines how robots operating in uncertain environments can use semantic communication with humans to solve the combined issues of model augmentation, multilevel 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 modelbased 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 nonmyopically 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 arXiv:2110.10324v1 [cs.RO] 20 Oct 2021

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.

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 [12], [13], [21], [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], [16], [26], [27], this work presents a novel use case in the context of multi-level data fusion for planning under uncertainty.

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 (S, A, T , R, Ω, O, γ), where the goal is to find a policy π which maps from a Bayesian posterior distribution, i.e. the belief b = p(s) over the set of states S, to a discrete action a ∈ A. The transition model T is a discrete time probabilistic mapping from one state to the next given an action, p(s |s, a), after which the robot is rewarded according to R(s, a). During policy execution, the robot receives observations o ∈ Ω according to observation likelihood O = p(o|s). For infinite horizon planning problems with discount factor γ ∈ [0, 1), the optimal policy π[b(s)] → a maximizes the expected future discounted reward: The primary challenge arising from casting our motivating problem as a POMDP lies in the ability of the human to modify the models T and O online in an unmodeled adhoc 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 T and O, but require gradual changes to their parameters and static T and O. In the motivating problem, A and 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 T , O and Ω 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 'blackbox' generative model, requiring only the 'current POMDP problem' at time of execution, making them good candidates for solving problems with dynamic model uncertainty.

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.

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].

A. Formal Problem Statement
The problem described above is formally cast as a POMDP, specified by the 7-tuple {S, A, T , R, Ω, O, γ}. 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 ∈ S = 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 1:k h , o 1:k r , a 1:k−1 ), which is the updated Bayesian posterior pdf given all observations made by the robot o 1:k h and the human o 1:k h through time k. Both s r and b(s t ) are displayed over a terrain map, which dictates transition model T = p(s |s, a) at each point space according to hazards and open areas. Action space A is a combination of movement action made by the robot which affect its state A m and query actions which pull information from the human A q . The human can provide sketches 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 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 Ω = p(o|s, a q ) for a given query action a q . The observation set O is split into robotic detection observations O r = {N oDetection, Detection, Capture} and human answers to action queries O h = {Y es, N o, N ull}, accounting for the possibility of the human not answering. Each sketch creates an enlarged query action space A q such that A q ⊂ A q , 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, A q = A q ∪ [Relation × 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 priorp(s |s, a), ∀s, which need not be reflective of the true transition model p(s |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 δ, such thatp t+1 (s |s, a) =p t (s |s, a) and E[∆s](a) = δ i . Finally, the reward function R is stated as a piece-wise function incentivizing capture of the target and slightly penalizing human queries such that for some distance threshold τ , A POMDP policy π solved for this problem is one which maximizes sum of expected future discounted reward of actions E[ ∞ t=0 γ t R t (s, a)].

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 (ξ), such that, for all human observations o h at all times, p(o h = N one|s) = ξ. This leads to an additional observation o h = N one ∈ Ω h . We also assume the human has a static a priori known accuracy η, such that, for all human observations o h at all times,p(o h = j|s) = p(o h = j|s) · η, where probability is redistributed to the "inaccurate" observations, The notationp(o|s) andp(s |s, a) denote models used during online execution, in contrast to the nominal distributions p(o|s) and p(s |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 ∼ p(o|s), o ∈ Ω, human responses to robotic queries a ∈ A q can be modeled as o h ∼ p(o h |s, a q ), a q ∈ A q , o h ∈ Ω h . These additional query actions can be introduced into 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, A = A m + 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, A = A m × 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, 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",

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, 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 nonmyopically 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.

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 [12], [13], [21], [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], [16], [26], [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.

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 δ 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 ∈ {V }, where {V } ⊂ {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 in a procedure inspired by the Ramer-Douglas-Peucker algorithm.

Algorithm 1 Sequential Convex Hull Reduction
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 predefine 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.
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 North South East West Near 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 = "The Target is relation of label." The area inside the sketch h i is now modelled as subject to any modifying meta data δ i provided by the human. In this work, where such information is provided, the δ acts only as an assumed transition functionp(s |s, a) modifier such that for a sketch made at time (t):p where the ∈ 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 α(s) is pre-initialized, then updated to store meta data: 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 δ 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 δ 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 Ω are modified alongside the transition function T , introducing the newly minted sketch h i ∈ H and its corresponding softmax function in the manner prescribed in Section 5.3. The observation set O remains the same in this work, but through the modified Ω = p(o ∈ O|s, a) observations corresponding to the new actions in A q can now occur. As per Section 5.3, the availability ξ and accuracy η parameters of the human collaborator are static across any model revisions, and their effect is folded into changes to Ω 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.

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, 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 T and 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 where 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 vectors. 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 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.

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 p k+1 (s |s, a) = p k (s |s, a), ∀k (13) p k+1 (s |s, a) =p k (s |s, a).
wherep k (s |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 |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,p k (s |s, a) = p k (s |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 T , we assume the underlying model isn't changing, while the robot's understanding of it might, i.e. p k+1 (s |s, a) = p k (s |s, a) (14) p k+1 (s |s, a) ? =p k (s |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. The Partially Observable Monte Carlo Planning (POMCP) algorithm proposed in [32] is particularly promising due to its use of generative 'forward' models and online anytime 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 A or 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 (α) noted in the previous subsection or the semantic observations included with each sketch (described in more detail below), readily adapt to more general problems.

H. Predictive Tree Planning
Implementation of an online POMDP solver such as POMCP in a time-limited system raises an additional com- s ∼ p k (s |s, am) (unknown state) 6: or ∼p k (or|s) (robot sensor observation) if New Human Sketch ( ) then end if 17: until Scenario End plication, 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.
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.
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 ∈ 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 which is the observation probability distribution for the current belief and action. In order to spend ∆t(a k ) time planning during the execution of a k , |Ω| plans can be pursued, each allocated ∆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 [π(o k+1 = 0), π(o k+1 = 1), ..., π(o k+1 = N ), and received the observation o k+1 = 1, the policy π(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

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
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. 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: 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 m s , with Σ r a = 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 m s , Σ t a = 5 while on the road and 5 m s , Σ t a = 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: and observation likelihood model with a 98% accuracy: As HARPS takes place on a larger scale environment, with state space S comprising a 1000m x 1000m area, the capture distance threshold τ 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 τ = 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.  Figure 12a 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.

A. Human vs Nonhuman
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.

B. Predictive Tree Search vs Blind Dynamics Updates
In Figure 12b, 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.

C. Human Accuracy
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.

D. Human Availability
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.

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 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.

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.
1) 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 ≤ x ≤ 1.
• 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. 2) 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.

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). 1) 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.
2) User Type: The tested subject compromised a wide range of interaction styles and consistencies. Figure 24 shows  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.
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.
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.
3) Subjective Metrics: Figure 26a 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 26b, 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. 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   : 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. 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).

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  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 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.
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 multilevel active semantic sensing and planning in human-robot teams in unknown dynamic environments. Our solution extends online POMDP planning frameworks to incorporate Fig. 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. 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.
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 {X , r, σ, λ, ψ}. The centroid 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 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 σ, 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: Where | X v| denotes the magnitude of the vector from the centroid to X to the vertex v. The number of vertices N v is distributed according to a shifted Poisson Distribution, with mean λ. The distribution is shifted uniformly upward by three, with support on R ∈ [3, ∞], ensuring that sketches are at a minimum triangles.
For a given N v , the requirement that the angles of a convex polygon sum to 2π radians reveals a nominal angular distance between each point of∆θ = 2π Nv radians. To capture the irregularity of a sketched polygon, the angular noise parameter ψ is used, such that∆θ and ψ specify a Gaussian distribution on angular distance. For a vertex v, the angular distance to the next vertex is drawn as The process for drawing vertices from the distribution specified by the 5-tuple {X , r, σ, λ, ψ} is summarized in Algorithm 3. Using PSEUD, sketches can be drawn from the distribution of sketches carrying the same parameterization, allowing angles i ∼ N (∆θ, ψ) 10: end for 11: angles = Normalize(angles,2π) 12: θ = angles 0 #Starting angle 13: for i ∈ N v do 14: 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.

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 freeform 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 = Y es), 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 π 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 θ made by state (s) with the horizontal, generating labels (l), 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 ∈ 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.
p(c, l) = s∈S p(c|s)p(l ∈ L(s)|s)ds (27) While the label term p(l ∈ 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 ∈ S to carry out the summation: p(c, l) = 1 J J j=1 p(c|s j )p(l ∈ L(s j )|s j ) 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), p(s|l) = 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), p(l|s) = c p(l|c)p(c|s) Again, in this instance p(c|l) corresponds to p(class = c|a q = l, o h = Y es), 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 θ 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. 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'.

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 [24], [25], [44] 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 sketchbased 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 p(N ear, Bearing|s) = p(N ear|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": p(F ar, N ear|s) = p(F ar|s)(1 − p(N ear|s)) (32) In this way, Eq. 31 can be generalized, with the assumption of range-bearing independence intact, to: 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.