#  SOCRATES: Text-based Human Search and Approach using a Robot Dog

Jeongeun Park1, Jefferson Silveria2, Matthew Pan2 and Sungjoon Choi 1
1Jeongeun Park and Sungjoon Choi are with the Department of Artificial
Intelligence, Korea University, Seoul, Korea {baro0906,sungjoon-
<EMAIL_ADDRESS>Jefferson Silveria and Matthew Pan are with the Department
of Electrical and Computer Engineering, Queens University, Kingston, Canada
<EMAIL_ADDRESS>
###### Abstract

In this paper, we propose a SOCratic model for Robots Approaching humans based
on TExt System (SOCRATES) focusing on the human search and approach based on
free-form textual description; the robot first searches for the target user,
then the robot proceeds to approach in a human-friendly manner. In particular,
textual descriptions are composed of appearance (e.g., wearing white shirts
with black hair) and location clues (e.g., is a student who works with
robots). We initially present a Human Search Socratic Model that connects
large pre-trained models in the language domain to solve the downstream task,
which is searching for the target person based on textual descriptions. Then,
we propose a hybrid learning-based framework for generating target-cordial
robotic motion to approach a person, consisting of a learning-from-
demonstration module and a knowledge distillation module. We validate the
proposed searching module via simulation using a virtual mobile robot as well
as through real-world experiments involving participants and the Boston
Dynamics Spot robot. Furthermore, we analyze the properties of the proposed
approaching framework with human participants based on the Robotic Social
Attributes Scale (RoSAS) [1].

##  I Introduction

In recent years, the coexistence of humans and robots has become increasingly
common in daily life. Assistive robots are widely used in everyday commercial
tasks within human environments such as delivering luggage at the airport or
transporting packages such as food within an office. To ensure efficient
human-robot interactions on such tasks, the ability for robots to interact
with humans based on natural language and intuitive motions appears to be an
important feature. In this paper, we propose a SOCratic model for Robots
Approaching humans based on TExt System (SOCRATES) which focuses on the
problem of human search and approach. In this system, the target person is
described via a free-form textual description; the robot first searches for a
target person, then proceeds to approach in a human-friendly manner.

Recent success on large pre-trained models, e.g., GPT [2], CLIP [3], has
opened a new paradigm for robots to understand human languages, such as
instruction following [4, 5], vision language-based navigation [6, 7], and
zero-shot object search [8, 9, 10, 11]. In this paper, we aim to build a
robotic system that searches and approaches a target person based on a textual
description of their appearance (e.g., person with black hair wearing a white
shirt) and location clues (e.g., is a student who works with robots). Our task
is similar to zero-shot object search [8, 9, 10, 11], which aims to search for
objects based on descriptions provided in free-form text, but differs in that
our goal is to search for target people rather than objects. Because our
objective is to enable robots to search for people, we must also focus on
correctly identifying them based on free-form user-entered text, as well as
having a robot competently and appropriately interact with targets.

Building on the success of large pre-trained models, Zeng et al. [12] proposed
a modular framework called Socratic Model (SM). This framework leverages pre-
trained models, which allows for an efficient and effective task-specific
performance without fine-tuning on downstream task data. The SM framework
formulates downstream tasks in a shared language domain between the pre-
trained models and tackles the problem by building bridges among models from
different modalities to facilitate communication. This approach has the
advantage of leveraging pre-trained models trained on a large external
database, which can avoid the need for task-specific data to train a single
model. Inspired by the success of the SM framework, we propose to apply this
approach to the task of human search and approach. Our hypothesis is that the
capabilities of large pre-trained models can be effectively leveraged to solve
this task.

To this end, we propose a SOCratic model for Robots Approaching humans based
on TExt System (SOCRATES), tackling the problem of human search and approach
where the target is given as a textual description. SOCRATES consists of two
serial modules: search and approach. The search module of SOCRATES, also
referred to as a Human Search Socratic Model, connects large pre-trained
models on a shared language domain to solve search downstream tasks without
fine-tuning. In particular, it is composed of a Large Language Model (LLM),
Vision and Language Model (VLM), and a waypoint generator. The LLM infers the
searching prior based on the location clue of the target person, the VLM
localizes the human with an appearance description, and the waypoint generator
estimates the next waypoints for the robot to take based on the prior
knowledge by LLM. The approach module is used after the search phase: the
robot has to approach the target user in a comfortable and cordial manner,
without being deemed threatening. To perform these functions, we propose a
hybrid learning-based framework to estimate the cost function of the approach
motion, composed of a learning from demonstration (LfD) step and knowledge
distillation step from the large-language model.

The main contributions of the paper are as follows:

  1. 1.

We propose SOCRATES, which efficiently searches and approaches a target person
where its description is given as free-form text.

  2. 2.

We present a Human Search Socratic Model, combining pre-trained models in the
language domain to search for people based on textual descriptions.

  3. 3.

We propose a hybrid learning-based framework to generate a target-friendly
approach motion composed of the learning from demonstrations (LfD) module and
the knowledge distillation module from large language models.

##  II Related Work

In this section, we provide existing work related to applying the SM to
searching for objects and humans and approaching a person in a socially
acceptable way. Socratic Model (SM) [12] is a framework that enables composing
pre-trained models to ”talk to each other” so that the knowledge learned from
a set of surrogate tasks can be applied to a new downstream target task. Zeng
et al. [12] proposed various applications of SM, including robotic perception
and planning, open-ended reasoning on egocentric video, and multimodal
assistive dialogue. SM has been widely used in robotics to solve language-
based problems such as task and motion planning or visual navigation. Huang et
al. [13] proposed Inner Monologue for instruction-based task and motion
planning, chaining Large-Language-Model (LLM) together with Vision-Language
Models (VLM), robotic skills, affordance models, and human feedback in a
shared language prompt. Shah et al. [7] proposed LM-Nav for vision-language
navigation tasks, which executes language instructions in a self-supervised
manner, combining three different pre-trained models (i.e., LLM, VLM, and
Vision-Language-Navigation).

There have been recent attempts to search for an object described through
free-form text, referred to as zero-shot object goal navigation [8, 9, 10,
11]. Gadre et al. [8] has proposed a framework called ’CLIP on the Wheels’,
which leverages Gradient-weighted Class Activation Mapping (Grad-CAM) [14] of
CLIP [3] for localizing novel target objects and frontier based explorations
[15] for exploration. Majumdar et al. [10] proposed the method for this task,
projecting navigation goals into a common semantic embedding space using CLIP
[3] to guide the agent to understand the image goal in language form. While
some work has trained whole uni-model networks for text-based object search in
simulated environments [10, 9], their lack of application in real-world
settings serves as a limitation. Our task is similar to zero-shot object goal
navigation as it is also based on text inputs; however, it differs in the fact
that it requires adapting to the changing characteristics of the target
person, as well as processing longer descriptions.

Approaching humans in a user-friendly manner is another key component in human
search and approach. Several papers [16, 17, 18] have covered the socially
aware navigation problem with learning-based frameworks, as it is difficult to
model complex social interactions explicitly. Ahn et al. [16] presented the
method to comfortably approach a user by considering each user’s personal
comfort field, measured by existing theories in anthropology, and learning
personalized comfort fields from users. Konar et al. [17] proposed a sampling-
based approximation to enable model-free inverse reinforcement learning for
socially compliant navigations. In this paper, we contain a method based on a
non-parametric inverse-reinforcement learning framework, this learning-based
method has its strength in robustly learning the reward function with a small
amount of noisy expert data.

##  III Human Search Socratic Model

In this paper, we propose SOCRATES, which tackles the problem of text-based
human search and approach. The problem is separated into search and approach
phases. Here, we present the Human Search Socratic Model, which connects pre-
trained models from different modalities to shared language domains as a
method to solve the downstream task of searching for a target person based on
textual descriptions.

The Human Search Socratic Model is composed of three key components: a large-
language model, a vision-language model, and a waypoint generator. The large-
language model [2] takes the description of a target person and estimates the
search prior, whereas the vision-language model [19] processes images and
descriptions to localize the target person. Lastly, the waypoint generator
commands the robotic actions with the search prior and the detection results.
An overview of the Socratic-based searching model is shown in Figure 1.

Figure 1: Overview of the proposed Human Search Socratic Model, red: input,
blue: output Figure 2: Input of the system.

###  III-A Problem Formulation

In this framework, we tackle the problem of robotic human search based on
textural descriptions $t$. Such descriptions are composed of appearance
$t_{1}$ and location clues $t_{2}$ (e.g., wearing a white shirt with black
hair and is a student who works with robots). We assume that an annotated map
and the location of the robot are accessible. The annotated map consists of
area categories $\\{a_{i}\\}_{i=1}^{K}$ and the label of each area $a_{i}$. An
example of the annotated map and the GUI used for textual description input of
target people are illustrated in Figure 2. The output of the Human Search
Socratic Model is a waypoint $\mathbf{p}=(x,y,z,\theta)$, which directs the
robot to a search location.

###  III-B General Procedure

Using large-language models, we estimate the search prior by computing the
likelihood of the target person to occur in label $a_{i}$ of the annotated map
shown in Figure 2-(a). Based on this search prior, the waypoint generator
calculates the cost of each label and generates the waypoint whose label has
the lowest cost. Then, the waypoint generator conducts a local search of the
area belonging to the chosen label using the detection results from the
vision-language model. As the ambiguity between language and vision is
inevitable, there is a possibility of obtaining multiple answers (potential
target detections). As such, the system asks for user feedback on whether a
detected person fitting the textual description provided is the target person.
If not, the system continues the local search. When the waypoint generator
finishes the local search, the system recalculates the cost of the map’s
label, moves to the next label, and starts another local search. The following
subsections explain the details of each process.

###  III-C Large Language Model

We leverage a large language model, i.e., GPT3 [2], in order to provide a
search clue to the robot. We gain commonsense knowledge of where the target
person may be located on the annotated map. This knowledge guides the robot to
search for the areas that have a high likelihood of the target person’s
placing. The prompt given to GPT3 is as follows:

The lab is composed of [floorplan categories ($\\{a_{i},\cdots,a_{K}\\}$)]. X
is a [location clue ($t_{2}$)] but not always. Where can I find X in the lab?

We denote a set of $M$ generated sentences $\\{s_{i}\\}_{i=1}^{M}$ as follows:

$\\{s_{i}\\}_{i=1}^{M}=f_{1}(t_{2},a_{1},\cdots,a_{K})$ (1)

where $f_{1}$ is GPT3.

###  III-D Vision-Language Model

For the successful localization of the target person based on the description
of appearance $t_{1}$, we utilize the vision-language model. In particular, we
leverage PNP-VQA: a specific vision-question answering model proposed in [19].
The input of the vision-language model is an image $I$ and a question, where
the question is prompted as follows:

Is a person [appearance ($t_{1}$)]?

As the vision-question-answering model provides an answer to a question, we
process the answer (yes or no) as a binary label. Additionally, we leverage
the Grad-CAM [14] of the VLM to localize the target person. Following the same
approach in PNP-VQA [19], we compute the relevance between the text and image
features to obtain an activation map. Based on un-normalized Grad-CAM on the
text and image similarity, we obtain the bounding box
$\mathbf{b}=\\{x_{1},y_{1},x_{2},y_{2}\\}$ of the image on the area where the
Grad-CAM score is higher than the threshold.

###  III-E Waypoint Generator

The waypoint generator operates in two phases; the global search phase and the
local search phase. The first phase determines which label of the annotated
map to visit. The second module generates waypoints to search for the target
person in the specific annotated area.

#### Global Search

In the global search phase, the module estimates the likelihood of occurrence
of the target person in the specific label based on the prior knowledge in
Section III-C. It then generates the waypoint to reach an area belonging to a
specific label. The first step is to measure the occurrence score of label
$a_{i}$ in the annotated map. We calculate the score with maximum word
similarity [20] between each word from the generated sentence in equation 1
and the label name. The occurrence score becomes the average of each score
calculated by generated sentences from $\\{s_{i}\\}_{i=1}^{M}$.

$p(a_{i}|t_{2})=\frac{1}{M}\sum_{k=1}^{M}\max_{l}\ell(w(a_{i}),w(s_{k}^{l}))$
(2)

where $s_{k}^{l}$ is a $l$-th word in sentence $s_{k}$, $\ell$ is a cosine
similarity and $w$ is a word to vector embedding [20]. Based on the occurrence
score, we compute the cost of visiting label $a_{i}$ for each label in the
annotated map. The cost function is as follows:

$c_{l}(a_{i})=||(\mathbf{p}_{r}-\mathbf{p}_{a_{i}})||_{2}+w_{e}(1-p(a_{i}|t_{2}))$
(3)

where $\mathbf{p}_{r}$ is a current robot pose, $\mathbf{p}_{a_{i}}$ is the
closest reachable position in the annotated area where its label is $a_{i}$,
and $w_{e}$ is a weight of the occurrence score. Then the robot navigates to
$\mathbf{p}_{a_{i}}$ that has the lowest cost among unvisited labels.

#### Local Search

In the local search phase, the robot aims to search for a target person in the
area that is annotated as the chosen label. After navigating to the area
chosen as described in the global search phase, the robot conducts the local
search. As detection based on language description is less reliable and also
dependent on the specific viewpoint, we adopt an indirect search approach. The
robot searches for general humans first, obtains better viewpoints, and then
detects the target based on the language description. We leverage the YOLOV5
[21] model pre-trained on the MS-COCO [22] dataset to detect general humans.
With an indirect search approach, we can prevent missing or false detection
due to poor viewpoints and reduce the amount of feedback asked back to the
user.

The steps of the local indirect search are as follows. The robot first detects
the general person, if any person is detected, the robot approaches or moves
back to keep a 5m distance and centers the human to obtain a proper image.
Then the vision-language model detects the person based on the description. If
a potential target is detected, the system asks for user feedback. If no
general person or text-based person is detected, the robot conducts frontier-
based exploration [15] based on the map. We also use the history of the
visited waypoints $\\{\mathbf{p}_{i}\\}_{i=1}^{n}$ to eject the waypoint that
has already been visited. The robot visits the waypoint if the minimum
$l2$-norm between past waypoints and the target waypoint is smaller than a
certain threshold. With this indirect search approach, we were able to reduce
the missing or false detection due to inappropriate viewpoints, hence reducing
the amount of feedback asked back to the user.

##  IV Hybrid Learning-based Human Approach

Figure 3: Overview of Proposed hybrid learning-based approach

In this section, we propose a hybrid learning-based framework for generating a
cordial approach motion to a target person. Target-friendly approach motions
are an essential part of the human search and approach task since the robot
has to move to a reachable position within the range of the target person
without appearing threatening or distracting him/her. The proposed hybrid
learning-based framework consists of two different modules: learning from
demonstration (LfD) and knowledge distillation. Both modules estimate the
reward function of the state space for a confiding approach trajectory and are
combined to a final reward function. Next, the path planner conducts cost-
aware planning based on the estimated reward function and sends actions
(velocity commands) to the robot. The overview of the proposed hybrid
learning-based framework is shown in Figure 3.

###  IV-A Problem Formulation

The objective of the human approach is to generate a target-friendly approach
motion. The inputs are estimated human pose $\mathbf{p}_{h}$, robot pose
$\mathbf{p}_{r}$, captions $\\{\mathbf{c}_{i}\\}_{i=1}^{N}$, and gaze
parameter $g$ which identifies whether the person is looking at the robot or
not. The proposed framework first estimates the reward function $R$ of the
state space, in which the frame of the reward function is defined as the robot
pose frame with respect to the human pose frame. We define the state space as
a combination of the two-dimensional robot poses relative to the human pose,
gaze parameter, and the robot’s speed;
$\mathbf{x}=\\{x_{r}^{h},y_{r}^{h},\theta_{r}^{h},g,v\\}$111We arranged as
$x_{r}^{h}\in\\{-6,-5.5,\cdots,6\\}$, $y_{r}^{h}\in\\{-3,-2.5,\cdots,3\\}$
$\theta_{r}^{h}\in\\{-\pi,-3/4\pi,\cdots,3/4\pi\\}$ $v\in\\{0.15,0.4,0.65\\}$
with a total of $14976$ points and $7488$ inducing points.. With the reward
function $R$, the path planner plans the trajectory and controls the robot by
velocity $(v_{x},v_{y},v_{\theta})$ commands. We assume the local egocentric
map is accessible for cost-aware planning without collision.

###  IV-B Input Processing

The inputs of the human approach system are the pose of the robot relative to
the pose of the person, gaze parameter, and image captions. As the detection
result in section III-D can only estimate its position with depth information,
we utilize a pre-trained human face mesh estimation network proposed in [23]
to estimate the orientation of a target person. The mesh detection is
conducted on a cropped image of the target’s head based on the detection
result. If the absolute orientation of the human face is less than 40 degrees,
the gaze parameter becomes $1$; otherwise, $0$. Furthermore, to process the
image in the format of the input of the language model, i.e., text, we
estimate the caption by the image-captioning branch (BLIP [24]) of PNP-VQA
[19].

###  IV-C Learning from Demonstration

As it is hard to explicitly model complex social behaviour for the robot to
create appropriate and non-threatening approaching motions, we adopt a
learning from demonstration (LfD) paradigm. In particular, we leverage the
Kernel Density Matching Reward Learning [25] (KDMRL) framework to estimate the
reward function of the approaching motion. It optimizes the reward function
that matches the state-action distribution of expert demonstrations.

In the density matching reward estimation framework, we assume that the
demonstrations are sampled from stationary state distribution
$\mu(\mathbf{x})$. Following the objective of the inverse reinforcement
learning formulation, the objective of density matching reward learning (DMRL)
is to maximize the dot product of the density of the state space $\hat{\mu}$
and the reward $R$ subject to $||R||_{2}\leq 1$. Then, the problem can be
relaxed by solving the following optimization problem:

$\underset{R}{\text{maximize}}\ \tilde{V}(R)=\sum_{\forall\mathbf{x}\in
U}\hat{\mu}(\mathbf{x})\tilde{R}(\mathbf{x})-\frac{\lambda}{2}||\tilde{R}||^{2}_{\mathcal{H}}$
(4)

where $\tilde{R}$ is a optimization subject, $\mathbf{x}$ is a state,
$\lambda$ is a smoothness parameter,
$U=\\{\mathbf{x}_{i}^{U}\\}_{i=1}^{N_{U}}$ is a set of $N_{U}$ inducing
points, and $||\tilde{R}||^{2}_{\mathcal{H}}$ is the squared Hilbert norm.
Then the reward function with inducing points is as follows:

$\tilde{R}(\mathbf{x})=\sum_{i=1}^{N_{U}}\alpha_{i}k(\mathbf{x},\mathbf{x}_{i}^{U})$
(5)

where $\mathbf{x}\in\mathcal{X}$, $\mathcal{X}$ is the state space,
$\mathcal{U}\subset\mathcal{X}$ is a set of pre-defined inducing points,
$\alpha\in\mathbb{R}^{N_{U}}$ is a parameter determining the shape of the
reward function, and $k(\cdot,\cdot)$ is a positive semi-definite kernel
function. Kernel density estimation is used to estimate the probability
density function of $\mu$,

$\hat{\mu}(\mathbf{x})=\frac{1}{Z}\sum_{k=1}^{N_{D}}\cos(\frac{\pi}{2}(1-\gamma_{k}))k_{\mu}(\mathbf{x},\mathbf{x}_{k}^{D})$
(6)

where $N_{D}$ is the number of training samples and $\mathbf{x}_{k}^{D}$ is
the $k$-th training data, $\gamma_{k}$ is a leverage value, and
$k_{\mu}(\cdot,\mathbf{x}^{D})$ is a kernel function whose integral is one.
The leverage value $\gamma_{k}=\delta^{T-t}$ indicates the weight of $k$-th
data with $\delta\in[0,1]$, $T$ and $t$ is the length and time-step of the
trajectory of the data and $Z$ is a normalization constant.

With equation 6, 5, and norm regularization
$\frac{\beta}{2}||\alpha||_{2}^{2}$, we can formulate equation 4 as matrix
form as follows

$\max_{a}\tilde{V}=\frac{1}{Z}\alpha^{T}K_{U}K_{D}\mathbf{g}-\frac{\lambda}{2}\alpha^{T}K_{U}\alpha-\frac{\beta}{2}\alpha^{T}\alpha$
(7)

where $[K_{U}]_{ij}=k(\mathbf{x}_{i}^{U},\mathbf{x}_{j}^{U})$,
$[K_{D}]_{ij}=k_{\mu}(\mathbf{x}_{i}^{U},\mathbf{x}_{j}^{D})$, and
$\mathbf{g}=\\{\cos(\frac{\pi}{2}(1-\gamma_{k}))\\}_{k=1}^{N_{D}}$ is a vector
of leverage values. The analytic solution of equation 7 with respect to
$\alpha$ is as follows:

$\hat{\alpha}=\frac{1}{Z}(\beta K_{U}+\lambda I)^{-1}K_{U}K_{D}\mathbf{g}$ (8)

###  IV-D Knowledge Distillation

Furthermore, we distillate the knowledge from the Large-Language model [2] to
generate the approaching motion of the robot. We extract commonsense knowledge
from GPT3 [2] to estimate the reward function. With gaze parameter $g$ and
captions $\\{\mathbf{c_{i}}\\}_{c=1}^{N}$, we make prompt for GPT3 as follows:

[caption ($\mathbf{c_{i}}$)] and the robot is [([$g=1$)/ not ($g=0$)] looking
at a person. What is the trajectory for the robots to gently approach a
person?

We generate sentences with GPT3, $\\{s^{t}_{i}\\}_{i=1}^{n\cdot N}$, $n$ times
for each $N$ captions. Then, we extract the keywords222straight, 45, side,
behind, curve, front, curved for the position, slow, slowly for velocity, and
not for negative sign. that are relevant to the trajectory, i.e., words
related to the position, velocity, and negative sign. The keywords extraction
function is denoted as $f_{k}(s^{t}_{i})$ and extracted keyword as
$\\{w^{l}_{i}\\}_{l=1}^{L}=f_{k}(s^{t}_{i})$.

To generate a trajectory based on a set of keywords, we set a word-to-
trajectory function $f_{d}(w)$ for generating a partial path based on the
word. The detail of the function is explained in the supplementary materials.
Based on this function $f_{d}(w)$, we generate an estimated trajectory by
iterating over the extracted keyword and stacking the partial path from the
word. Next, we transfer the generated trajectories to the reward function; the
procedure of estimating the reward function is shown in algorithm 1. Following
reward estimation, we smooth the reward function with the radial basis kernel
function $k_{r}(\cdot,\cdot)$. The knowledge-distillation-based reward
function becomes $R=k_{r}(\mathbf{x},\mathbf{x})\cdot R$.

Algorithm 1 Reward Estimation for Knowledge Distillation Based Human Approach

$R=[0]_{s}$ where $s$ is a dimension of the state space

for i = 0 to $n\cdot N$ do

$\\{w^{l}_{i}\\}_{l=1}^{L}=f_{k}(s^{t}_{i})$, $x=0$, $y=0$

for $l$ = $L$ to $0$ do

$\\{d\mathbf{x}^{j},d\mathbf{y}^{j}\\}_{j=1}^{N_{L}}=f_{d}(w^{l}_{i})$ //
extract keyword

$v=0.15$ if {$\text{'slow', 'slowly'}\in\\{w^{l}_{i}\\}_{l=1}^{L}$} otherwise
$v=0.6$ // set velocity

for j = 0 to $N_{L}$ do

$\theta=\arctan(d\mathbf{y}^{j}[-1],d\mathbf{x}^{j}[-1])$

$R(x+d\mathbf{x}^{j},y+d\mathbf{y}^{j},[\theta]_{d},\cdot,[v]_{d})+=1$

// update reward function

$x\leftarrow x+d\mathbf{x}^{j}[-1]$, $y\leftarrow y+d\mathbf{y}^{j}[-1]$

// update last position

end for

end for

end for

$R\leftarrow R/(N\cdot n)$

###  IV-E Path Planner

In the path planning step, the main goal is to generate paths based on the
reward function for any initial configuration of the robot. To achieve this,
we apply the FMT* path planning algorithm [26] made available in the Open
Motion Planning Library (OMPL) [27] in an environment where the cost of each
state is a function of the rewards obtained through the hybrid learning-based
reward estimation.

With reward functions from the learning-based framework $R_{I}$ and knowledge
distillation-based reward function $R_{L}$, we estimate the combined reward
function by weighted summation of the two parts,
$R_{T}=w_{r}R_{I}+(1-w_{r})R_{L}$ such that $R_{T}\in[0,1]$. In this system,
we set $w_{r}=0.2$. The resulting function is converted into a cost $1-R_{T}$
that is used by FMT* to penalize undesirable states. We set the cost function
to take into account the reward $R_{T}$ and the path length of the arriving
state. The cost function is as follows:

$c_{m}(\mathbf{\bar{x}}_{1},\mathbf{\bar{x}}_{2})=\zeta(1-R_{T}(\mathbf{\bar{x}}_{2}))\textrm{dist}(\mathbf{\bar{x}}_{1},\mathbf{\bar{x}}_{2}),$
(9)
$\textrm{dist}(\mathbf{\bar{x}}_{1},\mathbf{\bar{x}}_{2})=w_{p}||\mathbf{q}_{2}-\mathbf{q}_{1}||+w_{o}|\theta_{2}-\theta_{1}|,$
(10)

where $\mathbf{\bar{x}}_{i}=\\{\mathbf{q},\theta\\}$ is the $i$-th
configuration of the robot such that $\mathbf{q}\in\mathbb{R}^{2}$ and
$\theta\in SO(2)$. The weights $w_{p}$ and $w_{o}$ are used in the distance
function to give more or less importance to each component of the state.
$\zeta$ is a parameter that is used to fine-tune whether the solution
converges towards the shortest path or to one that closely matches the reward
function according to its magnitude.

##  V Experiments

In this section, we analyze the properties of the proposed method and discuss
the experimental results. We validate our search module in the real world with
human participants while also conducting an additional experiment on simulated
environments. In addition, we conduct human-subject pilot studies on the
proposed approaching motion of our system. The details of hyperparameters and
the environments are explained in the supplementary materials.

Figure 4: Robot settings and Environmental settings for Search Evaluation. Figure 5: Illustration of the Experimental Results. (a) shows the exemplary demonstrations of the proposed search module. The circles represent waypoints. (b) shows how the trajectories vary between methods. Circles represent waypoints and the circles with hashes represent the viewpoint that contained the target detection, where the red line denotes false detection and the blue line denotes true detection. Method | SPF $\uparrow$ | SPL $\uparrow$ | SR $\uparrow$ | # FD $\downarrow$
---|---|---|---|---
CoW [8] | 0.214 | 0.314 | 0.4 | 0.8
CoW [8] $+$ Indir. | 0.247 | 0.295 | 0.6 | 0.3
Knowledge Prior [28] | 0.55 | 0.636 | 0.9 | 0.8
SOCRATES(Ours) | 0.597 | 0.647 | 1.0 | 0.2
TABLE I: Result of Search Module on Real-world Environment.

###  V-A Real-world Search Experiments

In this section, we will discuss the experimental results of the proposed
Human Search Socratic Model in the real-world environment. We use a Spot robot
mounted with a Luxonis OAK-D-Pro camera [29] as shown in Figure 4-(a). The
real-world environment setting is a robotics lab environment shown in Figure
4-(b), Five different annotations of the floorplan are used to distinguish
locations in the lab. We conducted our real-world experiments using ten
different locations, with five different people and two unique initial
positions for each person. The performance of the system is evaluated using
three metrics: success rate (SR), success rate per path length (SPL), and the
number of false detections (# FD). SR and SPL are widely used in the
evaluation of visual search tasks, as reported in previous studies such as
[30]. The # FD metric is the average number of false detections, equivalent to
the number of false feedback from the users. Success is defined as the robot
successfully localizing the target person within a 5 m radius and receiving
positive feedback from the users. A trial is marked as a failure if the system
does not meet the success criteria, in total path length less than 30 m and #
FD less than five.

We compare the proposed system with three different approaches: CoW, CoW +
Indir, and Knowledge prior. CoW [8] leverage direct search without prior
knowledge, adapting only the distance term in equation 3, and replacing the
Grad-CAM [14] of CLIP [3] with BLIP [24]. In addition, we compared the
proposed method with CoW [8] with indirect search (CoW + Indir.). Knowledge
Prior is the method that solely utilizes the vision-language model without
general ’human’ detection, which resembles previous work [28, 31]. If the
target is detected, it approaches within 5m of the target and requests user
feedback; otherwise, the robot explores based on FBE [15]

The performance of the proposed search module is reported in Table I. The
system proposed in this work has the best performance on the SPL metric with a
gap of $0.137$. While the direct search has the highest success rate, the gap
of $0.1$ is not significant. In addition, the direct search has more false
detections compared to the indirect search, with a gap of $0.6$. As the
proposed method obtains a human-centered and well-scaled image, this property
leads to a decrease in the number of false detection and an increase in SPL.
Compared to methodologies without prior knowledge for searching, methods that
utilize prior knowledge have a significantly higher SPL metric, with an
average $0.23$ gap. As such, we would like to posit that prior knowledge plays
an essential role in the efficient search by robots.

Figure 5-(a) and (b) shows the trajectory of the robot. Figure 5-(a)
illustrates three different demonstrations of the proposed searching method.
The robot estimates the area where the target person is likely to be located
first and then performs a local search within the likely area. For example, in
Figure 5-(a)-(2), the robot infers, according to Section III-C that the target
person (a student that works on VR headsets) is likely to be located in the
lower-floor student cubicle area or upper-floor open-space where the VR
headsets are stored. The robot searches for the target within the lower-floor
cubicles first, as it is closer to its current position, and then moves to the
upper-floor space when the target is not detected. Figure 5-(b) shows the
trajectory with different methods. With prior knowledge, the robot searches
the upper-floor open-space first and then moves to the workspace with robots.
On the other hand, without prior knowledge, the robot searches in the order of
open-space area, sofa, and offices, leading to failure. Although the proposed
indirect search does not show a significant gap in path length with direct
search, the indirect search asks for less feedback from the user. Furthermore,
Figure 6 shows the example of the system detecting the target person based on
their appearance.

Figure 6: Detection Results

###  V-B Simulation Search Experiments

To show the expansion of the proposed method to various scenes other than the
lab, we evaluate the system in two more simulation environments, i.e., a house
and an office. We utilized a virtual Pioneer3AT robot mounted with an RGB-D
camera and Lidar within the Gazebo simulator. We ran 24 experiments, two
different initial positions for each person, with four different people in the
house setting and eight in the office setting. We assume all people are static
in the simulation environment. The comparison methods and metrics used are the
same as Section V-A. When the total path length is more than $15$ or the
number of false detection is larger than three, we deem the trial as a
failure.

Method | SPF $\uparrow$ | SPL $\uparrow$ | SR $\uparrow$ | # FD $\downarrow$
---|---|---|---|---
CoW [8] | 0.304 | 0.379 | 0.423 | 0.69
CoW [8] $+$ Indir. | 0.352 | 0.50 | 0.625 | 0.66
Knowledge Prior [28] | 0.460 | 0.615 | 0.833 | 0.375
SOCRATES(Ours) | 0.564 | 0.709 | 0.956 | 0.260
TABLE II: Result of Search Module on Simulation Environment.

The proposed method outperforms the compared method in all of the metrics. The
number of false detection is higher with a $0.08$ gap compared to the direct
search method. In addition, the result shows $0.041$ higher SPL on indirect
search compared to direct search. The method with prior knowledge increases
the performance, $0.32$ in SPL and $0.178$ in SR. The success rate of indirect
search is higher than direct search on the simulational result, but the gap of
$0.041$ is minor. Unlike real-world experiments, the number of false detection
increases when we do not adapt the prior knowledge. Since the simulation
environment is more crowded and contains more overlapping clothes, the longer
path length leads to more false detections.

###  V-C Real-world Approach Experiments

Figure 7: The illustration of data collection for the Learning-from-Demonstration module and the resulting reward function. The arrow heading indicates the orientation of the robot and the size indicates the speed. We only plot the reward that has a maximum reward on corresponding orientation and speed. Figure 8: Illustration of the Experimental Results on approach phase. Method | Competence $\uparrow$ | Warmth $\uparrow$ | Discomfort $\downarrow$
---|---|---|---
Baseline | 4.41 (1.08) | 3.34 (1.23) | 3.23 (1.23)
KD | 3.96 (0.82) | 3.28 (1.03) | 3.59 (1.08)
LfD | 4.14 (1.01) | 3.28 (1.29) | 3.30 (1.54)
Ours |  4.56 (1.28) |  3.63 (1.28) |  2.96 (1.28)
TABLE III: RoSAS Scale results in the total pool

Method | Competence $\uparrow$ | Warmth $\uparrow$ | Discomfort $\downarrow$
---|---|---|---
| Exp | IExp | Exp | IExp | Exp | IExp
Baseline | 4.30 | 4.58 | 3.11 | 3.58 | 3.35 | 3.12
KD | 3.94 | 4.14 | 3.17 | 3.02 | 3.41 | 3.36
LfD | 4.24 | 3.99 | 3.63 | 2.94 | 3.25 | 3.36
Ours | 4.71 | 4.41 | 3.80 | 3.46 | 2.98 | 2.90

TABLE IV: RoSAS Scale results depending on the group. Figure 9: Average rate
of the RoSAS attributes from different groups with 95% confidence bound.

In this section, we conduct a real-world human subject pilot study to analyze
the properties of the proposed approach module with the SPOT robot in Figure
4-(a). The robot approaches the person from 5 m away to closer than 0.6 m,
which is inside the reachable space for the target person. We evaluate the
proposed method based on the Robotic Social Attribute Scale (RoSAS) [1]. We
compare the proposed approaching motion with three different methods of
approach generation: learning from demonstration (LfD), knowledge distillation
(KD), and a baseline condition (having the robot directly move toward the
target person based on position control). The LfD-based approach only
leverages the reward function described in Section IV-C, and the KD-based
approach solely adapts the reward function shown in Section IV-D.

We recruited 16 people (gender: M=10, F=6, ages: 21-47) to participate in the
approach experiments. We divided the participants into two groups: an
experienced group containing those who have worked with robots previously
(n=8) and an inexperienced group (n=8). The participants were asked to rate
the robot’s approach motion using 18 word descriptors as part of the RoSAS
inventory, which measures user perceptions of the robot’s behaviour along the
dimensions of competence, warmth, and discomfort. Each participant reported
how applicable each keyword described their perception of the robot under
different robot conditions on 7-point Likert scale that ranged from 1 (not at
all) to 7 (very much so). Each participant evaluated eight different
trajectories balanced using a Latin square design: four trajectories with
gazing at the robot and four trajectories without gazing at the robot.

Before the experiment, we collected data using the Spot robot’s joystick
controller to create the LfD module described in Section IV-C, consisting of
18 expert demonstrations from 4 different people. We carefully collected data
from experts with feedback from the target person, such as if the person felt
safe or threatened according to the motion. The estimated reward function from
the LfD is shown in Figure 7. The estimated reward increases when the robot
gets closer to a target person, where the coordinate and the angle of the
target person are fixed as $(0,0,0)$. On the learned reward function with gaze
condition, the robot approaches from the front of the person, and the robot
obtains a larger reward by heading to the target person at a decreasing speed.
Under the no-gaze condition, the robot approaches from the back, and the
reward function contains a higher value for heading diagonally to a target
person.

Figure 8 shows the robotic motion of the proposed method and how the
trajectories vary between different approaching methods. In Figure 8-(1), when
the target person is facing the robot, the robot moves sideways in a short
distance and goes straight to the person at a decreasing speed. When the
target person is not looking at the robot, as shown in Figure 8-(2), it turns
toward the direction in which the person is looking and then moves laterally
to the target. Figure 8-(3) and 8-(4) illustrate the trajectories from
different methods conditioned on the gaze parameter. The limitation of the
knowledge distillation (KD) framework is that the robot does not slow down
near the human. As the LfD-based reward function is trained from various
complex expert demonstrations, it models diverse directions to approach
motion, leading to frequent changes in heading directions. The proposed method
tends to slowly approach from the forward direction with a slightly turning
sideway on gaze condition. In no-gaze condition, the robot slowly approaches
from sideways with lateral movement. We believe that the proposed hybrid
learning-based approach has the benefit of smoothing the LfD-based
trajectories, reducing the number of abrupt changes in the heading of the
robot.

We have conducted human-subject pilot studies using the RoSAS. To analyze our
results, we conducted a two-way repeated-measures MANOVA on the RoSAS results
obtained from the real-world approach experiment. As we have recruited limited
subjects in this pilot, this study is not sufficiently powered to assess the
effect; the results should be interpreted with caution. We observe that the
approaching motion significantly affects the participants on the warmth
dimension of the RoSAS ($F(7)=1.297$, $p=0.047$, $\eta^{2}=0.132$ with
$\alpha=0.05$). No other RoSAS dimension exhibits any significant results.
Post hoc pairwise comparisons with Bonferroni correction were not able to
detect any significant effects, likely due to a large number of contrasts
(seven) as well as reduced statistical power.

Table III reports the mean and standard deviation of each rating with
different methods. The proposed method outperforms the other methods with a
gap of $0.15$, $0.19$, and $0.27$, respectively, to each attribute. With
curved motion and decrement in speed, the participants observed motion to be
more competent and warm with less discomfort compared to straight and fast-
approaching motion. Furthermore, we measure the difference between the robot-
experienced group and the robot-inexperienced group in Table IV. Exp denotes
the robot-experienced group, while IExp. denotes the robot-inexperienced
group. The experienced group preferred the proposed method compared to the
other method with a gap of $0.48$ while the in-experienced group preferred the
baseline approach with a minor gap of $0.01$. Figure 9 reports the mean of
each rating with different methods on gaze conditions. From the survey
comments, two out of six people commented the lateral motion from the proposed
method made it hard for the inexperienced group to predict the direction of
the robot, while the experienced group observed that the motion was more dog-
like. As such, we would like to carefully hypothesize that the expertise of
the robot influences the preference of the motion of the robot when the person
is not gazing at it.

###  V-D Limitations

Although the human-subject studies of the approaching motion did not appear to
show significant effects, we would like to state that the user had a large
variance in their perspectives. As the data of the learning from demonstration
framework is collected from robot-experienced experts, the proposed method
adapts the preferences of the experts more than the non-expert group. We
believe that the proposed method can be further improved by considering the
preference of the user. In addition, we have observed that the system fails on
ambiguous commands or images during the search phase.

##  VI Conclusion

In this paper, we have introduced SOCRATES, which tackles the problem of human
search and approach based on textual descriptions. We proposed the Human
Search Socratic Model, which connects pre-trained models (e.g., large-language
models and vision-language models) by sharing the language domain for solving
the human search task. We evaluated the efficiency of the proposed search
module in both real-world and simulation environments. The proposed method
that its strength in performing a shorter path length with a small number of
feedback from the user. Furthermore, we have presented a hybrid learning-based
framework for generating the robotic motion to approach a person in a socially
aware manner. We conducted pilot studies with human participants to analyze
the properties of the proposed approach module to measure the user rate of
three attributes. We observed that the proposed method participants
outperformed the baseline approach method in all three attributes due to the
slow and lateral movement of the proposed method. We believe that the proposed
method can be further improved by considering the preferences of the user.

## References

  * [1] Colleen M. Carpinella, Alisa B. Wyman, Michael A. Perez, and Steven J. Stroessner.  The robotic social attributes scale (rosas): Development and validation.  In Proc. of the 2017 12th ACM/IEEE International Conference on Human-Robot Interaction (HRI, pages 254–262, 2017.
  * [2] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  In Proc. of the Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 1877–1901, 2020.
  * [3] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In Proc. of the International Conference on Machine Learning (ICML), pages 8748–8763. PMLR, 2021.
  * [4] Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, et al.  Do as i can, not as i say: Grounding language in robotic affordances.  arXiv preprint arXiv:2204.01691, 2022.
  * [5] Eric Jang, Alex Irpan, Mohi Khansari, Daniel Kappler, Frederik Ebert, Corey Lynch, Sergey Levine, and Chelsea Finn.  Bc-z: Zero-shot task generalization with robotic imitation learning.  In Proc. of the Conference on Robot Learning (CoRL), pages 991–1002. PMLR, 2022.
  * [6] Fengda Zhu, Yi Zhu, Xiaojun Chang, and Xiaodan Liang.  Vision-language navigation with self-supervised auxiliary reasoning tasks.  In Proc. of the Conference on Computer Vision and Pattern Recognition (CVPR), pages 10012–10022, 2020.
  * [7] Dhruv Shah, Blazej Osinski, Brian Ichter, and Sergey Levine.  Lm-nav: Robotic navigation with large pre-trained models of language, vision, and action.  In Proc. of the Conference on Robot Learning (CoRL), 2022.
  * [8] Samir Yitzhak Gadre, Mitchell Wortsman, Gabriel Ilharco, Ludwig Schmidt, and Shuran Song.  Clip on wheels: Zero-shot object navigation as object localization and exploration.  arXiv preprint arXiv:2203.10421, 2022.
  * [9] Apoorv Khandelwal, Luca Weihs, Roozbeh Mottaghi, and Aniruddha Kembhavi.  Simple but effective: Clip embeddings for embodied ai.  In Proc. of the Conference on Computer Vision and Pattern Recognition (CVPR), pages 14829–14838, 2022.
  * [10] Arjun Majumdar, Gunjan Aggarwal, Bhavika Devnani, Judy Hoffman, and Dhruv Batra.  Zson: Zero-shot object-goal navigation using multimodal goal embeddings.  arXiv preprint arXiv:2206.12403, 2022.
  * [11] Jeongeun Park, Taerim Yoon, Jejoon Hong, Youngjae Yu, Matthew Pan, and Sungjoon Choi.  Zero-shot active visual search (zavis): Intelligent object search for robotic assistants.  In Proc. of the IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023.
  * [12] Andy Zeng, Adrian Wong, Stefan Welker, Krzysztof Choromanski, Federico Tombari, Aveek Purohit, Michael Ryoo, Vikas Sindhwani, Johnny Lee, Vincent Vanhoucke, et al.  Socratic models: Composing zero-shot multimodal reasoning with language.  In Proc. of the International Conference on Learning Representations (ICLR), 2022.
  * [13] Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al.  Inner monologue: Embodied reasoning through planning with language models.  In Proc. of the Conference on Robot Learning (CoRL), 2022.
  * [14] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In Proc. of the IEEE international conference on computer vision (ICCV), pages 618–626, 2017.
  * [15] Brian Yamauchi.  Frontier-based exploration using multiple robots.  In Proc. of the International conference on Autonomous agents, pages 47–53, 1998.
  * [16] Hyemin Ahn, Yoonseon Oh, Sungjoon Choi, Claire J Tomlin, and Songhwai Oh.  Online learning to approach a person with no regret.  IEEE Robotics and Automation Letters, 3(1):52–59, 2017.
  * [17] Abhisek Konar, Bobak H Baghi, and Gregory Dudek.  Learning goal conditioned socially compliant navigation from demonstration using risk-based features.  IEEE Robotics and Automation Letters, 6(2):651–658, 2021.
  * [18] Yuying Chen, Congcong Liu, Bertram E Shi, and Ming Liu.  Robot navigation in crowds by graph convolutional networks with attention learned from human gaze.  IEEE Robotics and Automation Letters, 5(2):2754–2761, 2020.
  * [19] Anthony Meng Huat Tiong, Junnan Li, Boyang Li, Silvio Savarese, and Steven CH Hoi.  Plug-and-play vqa: Zero-shot vqa by conjoining large pretrained models with zero training.  In Proc. of the Empirical Methods in Natural Language Processing (EMNLP), 2022.
  * [20] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  In Proc. of the International Conference on Learning Representations (ICLR), 2013.
  * [21] Glenn Jocher.  ultralytics/yolov5: v3.1 - Bug Fixes and Performance Improvements.  https://github.com/ultralytics/yolov5, October 2020.
  * [22] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In Proc. of the European conference on computer vision (ECCV), pages 740–755. Springer, 2014.
  * [23] Camillo Lugaresi, Jiuqiang Tang, Hadon Nash, Chris McClanahan, Esha Uboweja, Michael Hays, Fan Zhang, Chuo-Ling Chang, Ming Guang Yong, Juhyun Lee, et al.  Mediapipe: A framework for building perception pipelines.  arXiv preprint arXiv:1906.08172, 2019.
  * [24] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  In Proc. of the International Conference on Machine Learning (ICML)), 2022.
  * [25] Sungjoon Choi, Kyungjae Lee, Andy Park, and Songhwai Oh.  Density matching reward learning.  arXiv preprint arXiv:1608.03694, 2016.
  * [26] Lucas Janson, Edward Schmerling, Ashley Clark, and Marco Pavone.  Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions.  The International journal of robotics research, 34(7):883–921, 2015\.
  * [27] Ioan A. Şucan, Mark Moll, and Lydia E. Kavraki.  The Open Motion Planning Library.  IEEE Robotics & Automation Magazine, 19(4):72–82, December 2012\.  https://ompl.kavrakilab.org.
  * [28] Ying Zhang, Guohui Tian, Jiaxing Lu, Mengyang Zhang, and Senyan Zhang.  Efficient dynamic object search in home environment by mobile robot: A priori knowledge-based approach.  IEEE Transactions on Vehicular Technology, 68(10):9466–9477, 2019\.
  * [29] OpenCV Luxonis (n.d.).  Opencv ai kit, July 2021.
  * [30] Peter Anderson, Angel Chang, Devendra Singh Chaplot, Alexey Dosovitskiy, Saurabh Gupta, Vladlen Koltun, Jana Kosecka, Jitendra Malik, Roozbeh Mottaghi, Manolis Savva, et al.  On evaluation of embodied navigation agents.  arXiv preprint arXiv:1807.06757, 2018.
  * [31] Thomas Kollar and Nicholas Roy.  Utilizing object-object and object-scene context when planning to find things.  In 2009 IEEE International Conference on Robotics and Automation, pages 2168–2173, 2009.
  * [32] Matthias Minderer, Alexey Gritsenko, Austin Stone, Maxim Neumann, Dirk Weissenborn, Alexey Dosovitskiy, Aravindh Mahendran, Anurag Arnab, Mostafa Dehghani, Zhuoran Shen, et al.  Simple open-vocabulary object detection with vision transformers.  In Proc. of the European Conference on Computer Vision (ECCV), 2022\.
  * [33] Assaf J Zeevi and Ronny Meir.  Density estimation through convex combinations of densities: approximation and estimation bounds.  Neural Networks, 10(1):99–109, 1997.
  * [34] Jonathan Ho and Stefano Ermon.  Generative adversarial imitation learning.  Advances in neural information processing systems, 29, 2016.
  * [35] Walter R Gilks, Sylvia Richardson, and David Spiegelhalter.  Markov chain Monte Carlo in practice.  CRC press, 1995.
  * [36] David Pollard.  Asymptopia.  Manuscript, Yale University, Dept. of Statist., New Haven, Connecticut, 2000.
  * [37] P Alfeld.  Understanding mathematics. utah: Departemen of mathematics, 2014.

## Appendix

###  VI-A Failure Cases

We observe that the system may fail when presented with ambiguous or noisy
inputs. In the vision system, localizing a person using grad-CAM may fail in
the presence of multiple people in one scene that corresponds to the prompt.
Additionally, the system may be susceptible to failures in certain lighting
conditions or when the person’s clothing color is similar to the background
color. Moreover, because the environment is dynamic, occlusion by other people
in the scene can also lead to search failure. The failure cases are
illustrated in Figure 10.

Figure 10: Failure Cases on Vision

In addition, ambiguous location clues can also cause system failures, for
example, the term ”teacher” may refer to either a student teaching assistant
or a professor. Furthermore, queries that are out-of-distribution, such as
”faculty members” who usually stay at a place not annotated, tend to result in
incorrect predictions. The search prior on the ambiguous commands are
illustrated in Table V

Location Clue |  (1) |  (2) |  (3) |  (4) |  (5)
---|---|---|---|---|---
teacher |  0.694 |  0.931 |  0.1 |  0.986 |  0.93
teaching assistant |  0.95 |  0.84 |  0.3 |  1.0 |  1.0
faculty member |  0.55 |  0.9 |  0 |  0.99 |  0.95
faculty member and having lunch |  0.4 |  0.95 |  0 |  0.93 |  0.80
student who is walking near chairs |  0.95 |  0.52 |  0.10 |  0.94 |  0.60
cleaning staff |  0.58 |  0.55 |  0.15 |  0.93 |  0.84
intern |  0.95 |  0.73 |  0.15 |  1.0 |  1.0
undergraduate intern |  0.9 |  0.58 |  0.1 |  0.98 |  0.93
TABLE V: Search prior with ambiguous commands. (1) Desk for students (2)
Office for professors (3) Sofa (4) Open space desk (5) Workspace with robots

###  VI-B Various Prompts

We have conducted additional experiments on Language clarifying the
generalizability of our system to more complex queries. The prompt used in LLM
is simply a set of the categorical names, e.g., desk, sofa, office, workspace,
etc, of the annotated map, which does not explicitly include information about
which user belongs to that area. However, the location clue from the input
sentence, e.g., a student who researches AI, does not explicitly express the
location of the target person. The possible location of the target person
cannot be easily determined by simple heuristics, and we leveraged the
commonsense knowledge of the large language model to address this challenge.
We tested both the vision-language model and the large-language model on the
complex queries. The illustrations of the results are shown in Figure 11 and
Table VI respectively.

Figure 11: Various Prompts on Vision Location Clue |  (1) |  (2) |  (3) |  (4) |  (5) |  (6)
---|---|---|---|---|---|---
student from mechanical engineering department |  1.0 |  0.35 |  0.15 |  0.25 |  0.7 |  0.5
student from the computer science department |  1.0 |  0.0 |  0.0 |  0.0 |  0.6 |  0.35
assistant professor |  0.6 |  0.05 |  0.05 |  0.97 |  0.6 |  0.15
professor |  0.14 |  0.05 |  0.05 |  0.98 |  0.1 |  0.05
student working on the paper |  1.0 |  0.25 |  0.14 |  0.15 |  0.75 |  0.45
visiting research students to do experiments |  1.0 |  0.15 |  0.50 |  0.31 |  0.9 |  0.65
TABLE VI: Search prior with complex commands. (1) Desk for students (2)Machine
shop (3) Sofa (4) Professor Office (5) Open space desk (6) Workspace with
robots

###  VI-C Word Based Path Generation Function

The algorithm for generating the reward function based on knowledge
distillation is mentioned in Section IV-D. To generate a trajectory based on a
set of keywords $\\{w^{l}_{i}\\}_{l=1}^{L}=f_{k}(s^{t}_{i})$, we set a word-
to-trajectory function $f_{d}(w)$ for generating a partial path based on the
word. The word-to-trajectory function function $f_{d}(w)$ is as follows:

$f_{d}(w)=\begin{cases}\\{(0,\ell\cos(\theta_{r}^{h})),(0,\ell\sin(\theta_{r}^{h}))\\},&\text{if
}w=\text{straight}\\\ \\{(0,\ell\cos(\pi/4)\text{sgn}(x_{r}^{h})),\\\
(0,\ell\sin(\pi/4)\text{sgn}(x_{r}^{h}))\\},\\\
\\{(0,\ell\cos(\pi/4)\text{sgn}(x_{r}^{h})),\\\
(0,\ell\sin(-\pi/4)\text{sgn}(x_{r}^{h}))\\}&\text{if }w=\text{45}\\\
\\{(0,\ell\cos(\pi/2),(0,\ell\sin(\pi/2))\\},\\\
\\{(0,\ell\cos(\pi/2),(0,\ell\sin(-\pi/2))\\}&\text{if }w=\text{side}\\\
\\{\\{\ell/2+\ell\cos(\theta)\\}_{\theta=0}^{\pi}\text{sgn}(x_{r}^{h}),\\\
\\{\ell/2+\ell\sin(\theta)\\}_{\theta=0}^{\pi}\text{sgn}(x_{r}^{h})\\},\\\
\\{\\{\ell/2+\ell\cos(\theta)\\}_{\theta=-\pi}^{0}\text{sgn}(x_{r}^{h}),\\\
\\{\ell/2+\ell\sin(\theta)\\}_{\theta=-\pi}^{0}\text{sgn}(x_{r}^{h})\\},)\\}&\text{if
}w=\text{curved or curve}\\\ \\{(0,\ell)),(0)\\},&\text{if }w=\text{front}\\\
\\{(0,-\ell)),(0)\\},&\text{if }w=\text{behind}\\\ \end{cases}$ (11)

where $\ell$ is a step variable. We set the step variable on the experiments
as $\ell=0.2$.

###  VI-D Function for Determining the Visit of Waypoint

On the local search phase of the waypoint generator on Section III-E, we
utilize the history of waypoints to guide the robot to visit waypoints that
have not been previously visited. The equation to determine the robot to visit
the waypoint is as follows:

$go(\mathbf{p}_{r})=\begin{cases}1,&\text{if
}\min_{i}||\mathbf{p}_{r}-\mathbf{p}_{i}||_{2}>t_{g}\\\
0,&\text{otherwise}\end{cases}$ (12)

where $t_{g}$ is a distance threshold to determine whether the robot has
visited the waypoint or not.

###  VI-E Experimental Setup

In the search phase, we experimented on a 2-floor lab environment with 40
experiments in total, and the details are shown in URL section 4. In addition,
in the approach phase, we had 16 participants with each evaluating 8
trajectories, which leads to 128 experiments in total.

Environment | # Q | Trials | # A | Methods | Total
---|---|---|---|---|---
Real-world Lab (2-floors) | 5 | 2 | 5 | 4 | 40
Simulation Household | 4 | 2 | 3 | 4 | 32
Simulation Office | 8 | 2 | 3 | 4 | 64
Total | 17 |  |  |  | 168
TABLE VII: Search Experiment Setup. # Q denotes the number of input queries.
Trials denote different initial positions, # A denotes the number of
categories in annotated map. Methods denote the number of compared methods.

###  VI-F Hyperparameters

We set the number of generation $M$ for prior knowledge on equation 1 as $20$,
and the weight of prior knowledge $w_{e}$ on equation 3 as $30$. In addition,
we set the threshold for the detection $t_{c}$ as $0.5$. Finally, we choose
the threshold of the visitence of the waypoint $t_{g}$ as $2$.

For the KDMRL framework on Section IV-C, we set hyperparamters as follows:
$\beta=0.2$, $Z=200$, $\delta=0.8$, $\lambda=0.01$. We set the weight for the
combined reward function as $w_{r}=0.2$. We leveraged the radial basis kernel
function with $\sigma$ as $1.0,0.5,1.0$ for
$k(\cdot,\cdot),k_{\mu}(\cdot,\cdot),k_{r}(\cdot,\cdot)$ respectively. On the
path planning module, we set $w_{p}=1,w_{o}=0.5,\zeta=1.5$ on equations 9 and
10.

###  VI-G Prompts of the Search Experiments

Table VIII shows the prompts used in search experiments.

Appearance ($t_{1}$) | Location Clue ($t_{2}$)
---|---
Real-World
wearing a white shirt with black hair | student that works with robots
wearing a black shirt with black hair | student that works with robots
wearing a black shirt with a hat | professor
wearing a red knit with black hair | student that works on VR
wearing a white shirt with black hair | student that works on AI
Simulation
wearing a white shirt with black hair | dad and cooking for dinner
wearing a blue shirt with white hair | mom and cooking for dinner
wearing a striped shirt with black hair | kids and preparing for bed
wearing a striped shirt with brown hair | grandma and watching TV
wearing a yellow shirt with brown hair | employee and doing office work
wearing a green shirt with black hair | employee and taking a rest
wearing a purple shirt with black hair | employer and doing a meeting
wearing a yellow shirt with blonde hair | employee and doing office work
wearing a red shirt with brown hair | employee and doing office work
wearing a purple shirt with brown hair | employee and doing a meeting
wearing a orange shirt with blonde hair | employee and doing office work
wearing a blue shirt with gray hair | staff and taking a rest
TABLE VIII: Prompts of the experimental environment

###  VI-H Vision-Language Detection

Following the text-based localization of the image in Section III-D, we
localize the target person based on un-normalized Grad-CAM on the text and
image similarity. We obtain the bounding box
$\mathbf{b}=\\{x_{1},y_{1},x_{2},y_{2}\\}$ of the image with threshold $t_{c}$
as follows:

$x_{1},y_{1}=\arg\min_{x,y}L^{\text{text}}_{\text{Grad-CAM}}(x,y)>t_{c}$ (13)

$x_{2},y_{2}=\arg\max_{x,y}L^{\text{text}}_{\text{Grad-CAM}}(x,y)>t_{c}$ (14)

###  VI-I Other Vision Model (OWL-ViT)

For the vision-language model, we had two objectives; localizing the target
person and obtaining a textual description of the scene. As we used a laptop
with limited computational power to control the Spot robot, we could not use
both the detection model and captioning model on one GPU. We have also tested
the proposed method on the Open-Vocabulary detection model, in particular,
owl-vit [32]. The results are shown in Figure 12.

Figure 12: Results with Owl-Vit

###  VI-J Theoretical Analysis of KDMRL

In this section, we present a bound on the sample complexity of the DMRL
mentioned in Section IV-C. Following the objective of the inverse
reinforcement learning formulation, the objective of density matching reward
learning (DMRL) is as follows:

$\begin{split}\underset{R}{\text{maximize}}\ &V(R)=<\hat{\mu},R>\\\
\text{subject to}\ &||R||_{2}\leq 1\end{split}$ (15)

where $\hat{\mu}$ is an estimated density of the state space.

Suppose that we have access to the true stationary state-action density
$\bar{\mu}(s,a)$ and estimate the reward $\bar{R}(s,a)$ from (15), i.e.,
$\bar{R}=\arg\max_{||R||_{2}\leq 1}\langle\bar{\mu},R\rangle$. We define the
value of $\bar{R}$ with respect to the true state-action density
$\bar{\mu}(s,a)$ as an optimal value
$\bar{V}=\langle\bar{\mu},\bar{R}\rangle$. In other words, the optimal value
$\bar{V}$ is an expectation of reward $\bar{R}$ with respect to the true
state-action density $\bar{\mu}$, i.e.,

$\bar{V}=\langle\bar{\mu},\bar{R}\rangle.$ (16)

Similarly, we define an estimated value $\hat{V}$ as an expectation of an
estimated reward $\hat{R}$ computed from solving (15) with estimated density
$\hat{\mu}$ with respect to the true state action density $\bar{\mu}(s,a)$,
i.e.,

$\hat{V}=\langle\bar{\mu},\hat{R}\rangle.$ (17)

As estimating the true density $\bar{\mu}(s,a)$ is practically infeasible, as
such it requires an infinite number of samples, we give a probabilistic bound
on the absolute difference between $\bar{V}$ and $\hat{V}$, i.e.,
$|\bar{V}-\hat{V}|$ as a function of the number of trajectories (sample
complexity). We show the sample complexity on the absolute difference between
the best value $\bar{V}$ and the optimized value, $\hat{V}$, with $n$ samples.
As $|\bar{V}-\hat{V}|=|\langle\bar{\mu},\,\bar{R}-\hat{R}\rangle|$, minimizing
this quantity can be interpreted as minimizing the difference between the
estimated reward $\hat{R}$ and the true reward $\bar{R}$ when projected by the
true state-action density $\bar{\mu}$.

We first introduce assumptions for the remaining theorem. Note that assumption
1 to 7 are illustrated in [33], but we depict the assumptions here for
completeness of the theorem. Assumption 8 is newly added.

###### Assumption 1

The random variables $\\{x_{i}\\}_{i}^{N}$ are sampled independent and
identically distributed according to $f(x)$.

###### Assumption 2

The density estimator function $f_{n}^{\theta}$ is piecewise continuous for
each parameter $\theta$.

###### Assumption 3

(a) $E[\log f(x)]$ exists and $|\log f_{n}^{\theta}(x)|\leq
m(x)~{}\forall\theta\in\Theta$ for some $m(x)$ where $m(x)$ is an integrable
function with respect to $f$. (b) $E[\log(f/f_{n}^{\theta})]$ has a unique
minimum.

###### Assumption 4

$\frac{\partial\log f_{n}^{\theta}(x)}{\partial\theta}$ is integrable with
respect to $x$ and continuously differentiable.

###### Assumption 5

$|\frac{\partial^{2}\log
f_{n}^{\theta}(x)}{\partial\theta_{i}\partial\theta_{j}}|$ and
$|\frac{\partial f_{n}^{\theta}(x)}{\partial\theta_{i}}\frac{\partial
f_{n}^{\theta}(x)}{\partial\theta_{j}}|$ is dominated by functions integrable
with respect to $f$ $\forall x\in\mathcal{X},~{}\theta\in\Theta$.

###### Assumption 6

(a) $\theta^{*}$ is interior to $\Theta$. (b) $B(\theta^{*})$ is nonsingular.
(c) $\theta^{*}$ is a regular point of $A(\theta)$.

###### Assumption 7

The convex model $f_{n}^{\theta}=\mathcal{G}_{n}$ obeys $\eta$ positivity
requirement.

###### Assumption 8

The target density function
$f\in\\{\sum_{i=1}^{\infty}\alpha_{i}\phi_{\rho}(\cdot;\theta_{i})\\}$ where
$\phi_{\rho}(\cdot;\theta_{i})$ is a basis density function.

The followings are the main results of this analysis.

###### Theorem 1

Let $\hat{R}$ be computed from
$\hat{R}=\underset{R}{\mathrm{arg\max}\langle\hat{\mu},R\rangle}\ \text{s.t.}\
\|R\|_{2}\leq 1$ and $\bar{R}$ be computed from
$\bar{R}=\underset{R}{\mathrm{arg\max}\langle\bar{\mu},R\rangle}\ \text{s.t.}\
\|R\|_{2}\leq 1$, where $\hat{\mu}$ and $\bar{\mu}$ are estimated and true
densities, respectively. Then

$|\langle\bar{\mu},\hat{R}\rangle-\langle\bar{\mu},\bar{R}\rangle|\leq
3(R_{max}-R_{min})d_{var}(\bar{\mu},\hat{\mu})$

where $d_{var}(\cdot,\cdot)$ is the variational distance333 The variational
distance between two probability distributions, $P$ and $Q$, is defined as
$d_{var}(P,Q)=\frac{1}{2}\sum_{x\in\mathcal{X}}|P(x)-Q(x)|$. It is also known
that $d_{var}(P,Q)=\sum_{x\in\mathcal{X}:P(x)>Q(x)}|P(x)-Q(x)|$.  between two
probability distributions.

###### Theorem 2

Suppose Assumption 1–8 hold. Let $n$ and $N$ be the number of samples and the
number of basis functions for kernel density estimation, respectively. Then,
for any $\delta\geq 0$ and $n$ and $N$ be sufficiently large, we have

$|\langle\bar{\mu},\hat{R}\rangle-\langle\bar{\mu},\bar{R}\rangle|\leq
3\sqrt{2}(R_{max}-R_{min})\sqrt{O\left(\frac{1}{n}\right)+O\left(\frac{nd}{N}(1+\frac{1}{\sqrt{\delta}})\right)}$
(18)

with probability at least $(1-\delta)$.

The main intuition behind the DMRL is that IRL can be viewed as a dual problem
of finding a reward function that matches the state-action distribution [34].
The domain of our interest is the product space of states and actions,
$\mathcal{S}\times\mathcal{A}$, and for the notational simplicity, we will
denote this space as $\mathcal{X}=\mathcal{S}\times\mathcal{A}$. Before
proving Theorem 1 and 2, we first introduce useful lemmas.

###### Lemma 1

[35] Let $P$ and $Q$ be probability distributions over $\mathcal{X}$ and $f$
be a bounded function on $\mathcal{X}$. Then,

$|\langle P,f\rangle-\langle Q,f\rangle|\leq(\sup f-\inf f)d_{var}(P,Q).$

###### Lemma 2

[36] Suppose $P$ and $Q$ are probability distributions. Then,

$d_{var}(P,\,Q)\leq\sqrt{2}d_{\mathcal{H}}(P,\,Q),$

where $d_{\mathcal{H}}(\cdot)$ is the Hellinger distance444 The Hellinger
distance between two probability distributions $P$ and $Q$ is defined as
$d^{2}_{\mathcal{H}}(P,Q)=\frac{1}{2}\sum_{x\in\mathcal{X}}(\sqrt{P(x)}-\sqrt{Q(x)})^{2}$
.

###### Lemma 3

[37] Suppose $\|\cdot\|$ is a proper norm defined on index set $\mathcal{X}$.
Then, for any $a,b\in\mathcal{X}$,

$|\|a\|-\|b\||\leq\|a-b\|.$

We also introduce a theorem from [33], which is used to prove Theorem 2.

###### Theorem 3

Suppose Assumption 1–8 hold. Let $n$ and $N$ be the number of samples and
basis functions for kernel density estimation, respectively, and
$\hat{f}_{n,N}$ be the estimated density function from kernel density
estimation with $n$ samples and $N$ basis functions. Then, for any $\delta\geq
0$ and $n$ and $N$ sufficiently large, we have

$d^{2}_{\mathcal{H}}(f,\hat{f}_{n,N})\leq
O\left(\frac{1}{n}\right)+O\left(\frac{nd}{N}(1+\frac{1}{\sqrt{\delta}})\right),$

where $d^{2}_{\mathcal{H}}(\cdot)$ is a squared Hellinger distance between two
probability distributions.

With that Lemma 1, 2, 3 and Theorem 3, we can prove Theorem 1 and Theorem 2.

###### Proof:

(Theorem 1) Let $\bar{\mu}$ and $\hat{\mu}$ be the true and estimated density
functions, respectively, and $\bar{R}$ and $\hat{R}$ be the reward functions
estimated by DMRL with $\bar{\mu}$ and $\hat{\mu}$, respectively. The absolute
difference between the optimal value $\bar{V}$ and the estimated value
$\hat{V}$ can be expressed as:

$\displaystyle|\langle\bar{\mu},\hat{R}\rangle-\langle\bar{\mu},\bar{R}\rangle|$
$\displaystyle=|\langle\bar{\mu},\hat{R}\rangle-\langle\bar{\mu},\bar{R}\rangle+\langle\hat{\mu},\hat{R}\rangle-\langle\hat{\mu},\hat{R}\rangle|$
$\displaystyle\leq|\langle\bar{\mu},\hat{R}\rangle-\langle\hat{\mu},\hat{R}\rangle|+|\langle\bar{\mu},\bar{R}\rangle-\langle\hat{\mu},\hat{R}\rangle|$
$\displaystyle\leq(R_{max}-R_{min})d_{var}(\bar{\mu},\,\hat{\mu})+|\langle\bar{\mu},\,\bar{R}\rangle-\langle\hat{\mu},\,\hat{R}\rangle|,$

where we used the triangular inequality and Lemma 1.

$|\langle\bar{\mu},\,\bar{R}\rangle-\langle\hat{\mu},\,\hat{R}\rangle|$ can be
further bounded by

$\displaystyle|\langle\bar{\mu},\bar{R}\rangle-\langle\hat{\mu},\hat{R}\rangle|$
$\displaystyle=\left|\max_{\|R\|\leq
1}{\langle\bar{\mu},R\rangle}-\max_{\|R\|\leq
1}{\langle\hat{\mu},R\rangle}\right|$ $\displaystyle\leq\max_{\|R\|\leq
1}{\langle\bar{\mu}-\hat{\mu},R\rangle}$
$\displaystyle\leq(R_{max}-R_{min})\sum_{x\in\mathcal{X}}|\mu(x)-\hat{\mu}(x)|$
$\displaystyle=2(R_{max}-R_{min})d_{var}(\bar{\mu},\hat{\mu}),$

where we used the definition of optimal and estimated values, Lemma 3 for a
dual norm, the definition of an inner product, and the definition of
$d_{var}(\cdot)$. ∎

###### Proof:

(Theorem 2) Combining the aforementioned two inequalities and Lemma 2, we get

$\displaystyle|\langle\bar{\mu},\hat{R}\rangle-\langle\bar{\mu},\bar{R}\rangle|$
$\displaystyle\leq 3(R_{max}-R_{min})d_{var}(\bar{\mu},\,\hat{\mu})$
$\displaystyle\leq
3\sqrt{2}(R_{max}-R_{min})\sqrt{O\left(\frac{1}{n}\right)+O\left(\frac{nd}{N}(1+\frac{1}{\sqrt{\delta}})\right)}.$

∎


* [Bod12] Manuel Bodirsky.  Complexity classification in infinite-domain constraint satisfaction.  Mémoire d’habilitation à diriger des recherches, Université Diderot – Paris 7. Available at arXiv:1201.0856v8, 2012.
  * [Bod21] Manuel Bodirsky.  Complexity of Infinite-Domain Constraint Satisfaction.  Lecture Notes in Logic (52). Cambridge University Press, 2021.  doi:10.1017/9781107337534.
  * [BP15] Manuel Bodirsky and Michael Pinsker.  Schaefer’s theorem for graphs.  Journal of the ACM, 62(3):52 pages (article number 19), 2015.  A conference version appeared in the Proceedings of STOC 2011, pages 655-664.  doi:10.1145/2764899.
  * [BPP15] Manuel Bodirsky, Michael Pinsker, and András Pongrácz.  The 42 reducts of the random ordered graph.  Proceedings of the LMS, 111(3):591–632, 2015.  Preprint available from arXiv:1309.2165.  doi:10.1112/plms/pdv037.
  * [BPR20] Manuel Bodirsky, Wied Pakusa, and Jakub Rydval.  Temporal constraint satisfaction problems in fixed-point logic.  In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors, LICS ’20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020, pages 237–251. ACM, 2020.  doi:10.1145/3373718.3394750.
  * [BS01] Franz Baader and Klaus U. Schulz.  Combining constraint solving.  H. Comon, C. March, and R. Treinen, editors, Constraints in Computational Logics, 2001.
  * [BW12] Manuel Bodirsky and Michał Wrona.  Equivalence constraint satisfaction problems.  In Proceedings of Computer Science Logic, volume 16 of LIPICS, pages 122–136. Dagstuhl Publishing, September 2012.  doi:10.4230/LIPIcs.CSL.2012.122.
  * [Cam90] Peter J. Cameron.  Oligomorphic permutation groups.  Cambridge University Press, Cambridge, 1990.
  * [Ghi04] Silvio Ghilardi.  Model-theoretic methods in combined constraint satisfiability.  Journal of Automated Reasoning, 33(3):221–249, 2004.  doi:10.1007/s10817-004-6241-5.
  * [GM77] Zvi Galil and Nimrod Megiddo.  Cyclic ordering is NP-complete.  Theoretical Computer Science, 5(2):179–182, 1977.
  * [Hod97] Wilfrid Hodges.  A shorter model theory.  Cambridge University Press, Cambridge, 1997.
  * [KG07] Sava Krstić and Amit Goel.  Architecting solvers for sat modulo theories: Nelson-oppen with dpll.  In Proceedings of the 6th International Symposium on Frontiers of Combining Systems, FroCoS ’07, pages 1–27, Berlin, Heidelberg, 2007. Springer-Verlag.  doi:10.1007/978-3-540-74621-8_1.
  * [KP18] Michael Kompatscher and Trung Van Pham.  A complexity dichotomy for poset constraint satisfaction.  IfCoLog Journal of Logics and their Applications (FLAP), 5(8):1663–1696, 2018.
  * [KPT05] Alexander Kechris, Vladimir Pestov, and Stevo Todorčević.  Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups.  Geometric and Functional Analysis, 15(1):106–189, 2005.
  * [LP15] Julie Linman and Michael Pinsker.  Permutations on the random permutation.  Electronic Journal of Combinatorics, 22(2):1–22, 2015.
  * [MSS04] Rolf H. Möhring, Martin Skutella, and Frederik Stork.  Scheduling with and/or precedence constraints.  SIAM Journal on Computing, 33(2):393–415, 2004.
  * [NB95] Bernhard Nebel and Hans-Jürgen Bürckert.  Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra.  Journal of the ACM, 42(1):43–66, 1995.
  * [NO79] Greg Nelson and Derek C. Oppen.  Simplification by cooperating decision procedures.  ACM Transactions on Programming Languages and Systems, 1(2):245–257, 10 1979.  doi:10.1145/357073.357079.
  * [Opa79] Jaroslav Opatrny.  Total ordering problem.  SIAM Journal on Computing, 8(1):111–114, 1979.
  * [Opp80] Derek C. Oppen.  Complexity, convexity and combinations of theories.  Theoretical Computer Science, 12(3):291 – 302, 1980.  doi:10.1016/0304-3975(80)90059-6.
  * [Pos41] Emil L. Post.  The two-valued iterative systems of mathematical logic, volume 5.  Princeton University Press, Princeton, 1941.
  * [Rin96] Christophe Ringeissen.  Cooperation of Decision Procedures for the Satisfiability Problem, pages 121–139.  Springer Netherlands, Dordrecht, 1996.  doi:10.1007/978-94-009-0349-4_6.
  * [Sch00] Klaus U. Schulz.  Why combined decision problems are often intractable.  In Frontiers of Combining Systems, pages 217–244, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg.
  * [TR03] Cesare Tinelli and Christophe Ringeissen.  Unions of non-disjoint theories and combinations of satisfiability procedures.  Theoretical Computer Science, 290(1):291 – 353, 2003.  doi:10.1016/S0304-3975(01)00332-2.
  * [VKvB89] Marc Vilain, Henry Kautz, and Peter van Beek.  Constraint propagation algorithms for temporal reasoning: A revised report.  Reading in Qualitative Reasoning about Physical Systems, pages 373–381, 1989.