¨ ¨TECHNISCHE UNIVERSITAT MUNCHEN
Lehrstuhl fu¨r Steuerungs- und Regelungstechnik
Extraction of Probabilistic Route
Information Representations from
Human-Robot Dialogs
Andrea M. Bauer
Vollst¨andiger Abdruck der von der Fakult¨at fu¨r Elektrotechnik und Informationstechnik
der Technischen Universit¨at Mu¨nchen zur Erlangung des akademischen Grades eines
Doktor-Ingenieurs
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Dr.-Ing. habil. Gerhard Rigoll
Pru¨fer der Dissertation:
1. TUM Junior Fellow Dr.-Ing. Dirk Wollherr
2. Univ.-Prof. Dr. Manfred Tscheligi
¨Universit¨at Salzburg / Osterreich
Die Dissertation wurde am 21.04.2010 bei der Technischen Universit¨at Mu¨nchen einge-
reicht und durch die Fakult¨at fu¨r Elektrotechnik und Informationstechnik am 26.11.2010
angenommen.Foreword
This thesis is the result of three years of research at the Institute of Automatic Control
Engineering (LSR) of Technische Universit¨at Mu¨nchen. I am grateful to all people who
contributed to my research and supported me during this time.
First of all, I would like to thank my doctoral advisor Dr. Dirk Wollherr for all open
discussions and constructive feedback. I would like to express my gratitude towards Prof.
Martin Buss who trusted in my abilities and provided an inspiring working environment
formyresearch. ForthegreatinterdisciplinarycollaborationIthankDr. AstridWeissand
Prof. Manfred Tscheligi of the ICT&S Center, University of Salzburg. For their advice
on experimental design and statistics I would like to thank my colleague Raphaela Groten
and Stephan Haug from TUMStat. Great thanks go to Prof. Niall Palfreyman for the
thorough proofreading of this thesis.
I enjoyed the pleasant and supportive working environment at the LSR to which all
of my colleagues have contributed. For the great team work, fruitful discussions, and
assistance, I would like to thank the other members of the ACE-team: Klass Klasing,
Georgios Lidoris, Quirin Mu¨hlbauer, Florian Rohrmu¨ller, Stefan Sosnowski, Tingting Xu,
and Tianguang Zhang. Special thanks go to my colleagues Michelle Karg, Markus Rank,
MichaelScheint, UlrichUnterhinninghofen,andTingtingXu, whohavesupportedmewith
their technical knowledge, proofreading of parts of this thesis, encouragement, and most
importantly friendship. I would like to thank all students who contributed to this thesis:
Adrian Garcea, Barbara Gonsior, Raul Heinrich, Lilian Kettner, Taru Laamannen, and
Jens-Nikolas Martens.
Foralwayssupportingme, Iwouldliketothankmymomwhoismytechnicalhero. And
last but not least, I thank my boyfriend Philipp for his love and encouragement.
Munich, April 2010 Andrea Bauer
iiiTo my grandmother Marie Fetterov´a
and my dog Hexi.
ivContents
1 Introduction 1
1.1 Motivation and Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview of Human-Robot Interaction . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Design Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Human-Robot Communication. . . . . . . . . . . . . . . . . . . . . 4
1.2.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Interactive Robots Extracting Spatial Information . . . . . . . . . . 7
1.3 Overview of Spatial Cognition and Computation . . . . . . . . . . . . . . . 7
1.3.1 Spatial Representations in Humans . . . . . . . . . . . . . . . . . . 7
1.3.2 Spatial Representations in Technical Systems . . . . . . . . . . . . 9
1.4 Main Contributions and Outline of the Thesis . . . . . . . . . . . . . . . . 10
2 Identification of Research Questions from an Outdoor Experiment 13
2.1 Problem Description and State of the Art . . . . . . . . . . . . . . . . . . 13
2.2 The Autonomous City Explorer Robot . . . . . . . . . . . . . . . . . . . . 14
2.3 The Autonomous City Explorer Experiment . . . . . . . . . . . . . . . . . 16
2.4 Open Research Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Human-Robot Dialog for Route Information Extraction 21
3.1 Problem Description and State of the Art . . . . . . . . . . . . . . . . . . 21
3.2 Linguistic Principles Relevant to Direction Inquiry . . . . . . . . . . . . . . 23
3.2.1 Dialog Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.2 Deixis Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.3 The Origo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.4 Problems in Interpreting Deictics . . . . . . . . . . . . . . . . . . . 25
3.3 Guidelines for Human-Robot Communication . . . . . . . . . . . . . . . . 26
3.4 Dialog System for Proactive Route Information Extraction . . . . . . . . . 29
3.4.1 System Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4.2 Implementation of the Dialog Guidelines . . . . . . . . . . . . . . . 32
3.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5.1 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
vContents
4 Probabilistic Models of Route Information 43
4.1 Problem Description and State of the Art . . . . . . . . . . . . . . . . . . 43
4.2 Models for Direction and Distance Information . . . . . . . . . . . . . . . . 45
4.2.1 Certainty Value of Direction Information . . . . . . . . . . . . . . . 45
4.2.2 Posterior Probability of Distance Information . . . . . . . . . . . . 48
4.3 Data Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.1 Direction Information. . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.2 Quantitative Distance Information . . . . . . . . . . . . . . . . . . 54
4.3.3 Qualitative Distance Information . . . . . . . . . . . . . . . . . . . 59
4.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5 Simultaneous Reasoning and Mapping 69
5.1 Problem Description and State of the Art . . . . . . . . . . . . . . . . . . 69
5.2 Types of Differences between Route Descriptions . . . . . . . . . . . . . . . 70
5.3 Simultaneous Reasoning and Mapping . . . . . . . . . . . . . . . . . . . . 71
5.3.1 Information Representation by Topological Route Graphs . . . . . . 72
5.3.2 Vector Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.3.3 Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.3.4 Route Similarity Assessment . . . . . . . . . . . . . . . . . . . . . . 77
5.3.5 Inquiry about Conflicting Information . . . . . . . . . . . . . . . . 77
5.3.6 Building and Updating Route Belief. . . . . . . . . . . . . . . . . . 78
5.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6 Conclusion and Outlook 85
6.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.2 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
A The Autonomous City Explorer 89
A.1 Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
A.2 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
B Contextual Dependence of Distance Information 91
B.1 Quantitative Distance Information . . . . . . . . . . . . . . . . . . . . . . 91
B.2 Qualitative Direction Information . . . . . . . . . . . . . . . . . . . . . . . 94
C Questionnaires 97
C.1 Questionnaire for Dialog-System Assessment . . . . . . . . . . . . . . . . . 97
C.2 Questionnaire for Qualitative Distance Assessment. . . . . . . . . . . . . . 99
Bibliography 103
viAbstract
This thesis addresses methods that enable robots to extract missing route knowledge by
asking humans for directions. In a first step an experiment was conducted in which a
robot had to navigate to a designated goal in an unknown urban environment without
any prior map knowledge or GPS, but solely by asking passers-by for directions. While
the experiment was successful, at the same time the results point up further challenges
for extracting route information through human-robot communication. Hence, research
questions are derived that are answered in the remainder of the thesis, namely proactive
extraction of route information from human-robot dialogs, probabilistic representation of
route information, and reasoning about extracted route descriptions. Linguistic principles
relevant to direction-inquiry dialogs are reviewed. Guidelines for human-robot dialogs are
derived from these and implemented in a dialog system. This renders the dialog natu-
ral to humans and facilitates proactive extraction of unambiguous route information. As
route information is usually simplified and distorted, probabilistic models of individual
route information are developed. Certainty values are computed from direction and error
probabilities to assess the reliability of direction information. Quantitative and qualita-
tive distance information is modeled by posterior probability distributions that assess the
accuracy of distance information. Finally, a system is developed that allows robots to
reason about different route descriptions. Route descriptions are represented as graphs
and evaluated for plausibility by pattern matching and route similarity assessment. Rea-
sonable route information is included in the route belief of the robot, while conflicting
information is inquired about if necessary. All methods are evaluated experimentally with
collected data or by human participants. The methods and systems introduced are de-
signed in adaptable ways and can be expanded for extracting and representing other types
of information from human-robot dialogs.
Zusammenfassung
Diese Arbeit besch¨aftigt sich mit Methoden, die es Robotern ermo¨glichen, sich fehlendes
Wegwissen anzueignen indem sie Menschen gezielt nach dem Weg fragen. Zuna¨chst wurde
einExperimentdurchgefu¨hrt,indemeinRoboterseinenWegzueinemvorgegebenenZielin
in einer unbekannten Umgebung ohne vorheriges Kartenwissen oder GPS, sondern allein
durch Wegangaben von Passanten erreichen musste. Dieses Experiment war erfolgreich,
zeigt aber auch auf, welche Herausforderungen fur die Aneignung von Wegwissen durch¨
Mensch-Roboter-Kommunikation noch bestehen. Daraus leiten sich die Forschungsschwer-
punkte dieser Arbeit ab, n¨amlich Extraktion von Weginformationen aus Mensch-Roboter-
Dialogen, probabilistische Repr¨asentation von Weginformationen und das Schlussfolgern
uber gegebene Wegbeschreibungen. Aus linguistischen Erkenntnissen werden Richtlinien¨
fur Mensch-Roboter-Dialoge uber Wegwissen abgeleitet und in einem Dialogsystem im-¨ ¨
plementiert. Dies ermoglicht eine fur den Menschen naturliche Kommunikation und die¨ ¨ ¨
zuverl¨assige Extraktion von inhaltlich eindeutigen Weginformationen. Da Weginformatio-
nen u¨blicherweise Scha¨tzwerte und Vereinfachungen der tats¨achlichen Werte wiedergeben,
werden in einem n¨achsten Schritt probabilistische Modelle fu¨r einzelne Weginformationen
erstellt. Aus Richtungs- und Fehlerwahrscheinlichkeiten werden Zuverlassigkeitswerte fur¨ ¨
viiContents
Richtungsangaben berechnet. Quantitative und qualitative Distanzangaben werden durch
bedingteWahrscheinlichkeitsdichteverteilungenmodelliert,dieAufschlussu¨berdieGenau-
igkeit der einzelnen Angaben liefern. Zuletzt wird ein System vorgestellt, das es Robotern
ermoglicht, verschiedene Wegauskunfte zu vergleichen. Dabei werden die Wegauskunfte¨ ¨ ¨
graphentheoretischreprasentiertunduberPattern-MatchingundWegvektorahnlichkeitauf¨ ¨ ¨
Plausibilitat untersucht. Sinnvolle Weggraphen werden in die Wissensbasis aufgenommen,¨
w¨ahrenddasSystemgegebenenfallsgezieltbeiwiderspru¨chlichenInformationennachfragt.
Alle Methoden werden mit durch Umfragen erhobene Daten oder mit Probanden experi-
mentell evaluiert. Die Vorgestellten Systeme und Verfahren sind modular gehalten und
lassen sich auf Aneignung und Reprasentation allgemeiner Informationen durch Mensch-¨
Roboter-Dialoge erweitern.
viiiNotations
Abbreviations
ACE Autonomous City Explorer
ANOVA analysis of variance
Concl dialog system state: conclusion
Conf dialog system state: confirmation
FSM finite state machine
GivDir dialog system state: give directions
GPS Global Positioning System
GUI graphical user interface
DG dialog guideline
HRI human-robot interaction
Intro dialog system state: introduction
pdf probability density function
SRAM Simultaneous Reasoning and Mapping
s.t. subject to
SSH Spatial Semantic Hierarchy
XML Extensible Markup Language
Conventions
Scalars, Vectors, and Matrices
Scalars are denoted by letters in italic type. Vectors are denoted by bold lower case letters
in italic type, vector x is composed of elements x . Matrices are denoted by bold upperi
th thcase letters in italic type, matrixM is composed of elements M (i row, j column).ij
x, X scalar
x vector
X matrix
TX transposed ofX
x◦y Hadamard product ofx andy
g(·) scalar function
|·| absolute value
k· Euclidean norm
ixNotations
List of Symbols
Roman Symbols
A path in Bi
A vector spanned by path Ai i
a edge in path A as vectori,j i
B belief
B , B belief of human/robotH R
B preliminary beliefprel,i
hb border between ‘here’ and ‘close’c
cb border between ‘close’ and ‘far’f
B RC , C conflicting information in B, R
c certainty valuek
Mc certainty value in a metric graph
k
sensorc confidence value of sensor datak
D (x,y) pattern matching metricM
d length of edgek
Md length of edge in metric graphk
d estimated distanceest
d real distancereal
E edgek
ME edge in metric graphk
TE edge in topological graphk
e(M ) number of edges in Mi,j i,j
Ae relative absolute error of distance estimated
Ae relative absolute error of time estimatet
Ce relative constant error of distance estimated
Ce relative constant error of time estimatet
f frequency of qualitative distance ‘close’c
F cumulative error frequencyE,k
f error frequencyE,k
f frequency of qualitative distance ‘far’f
f frequency of qualitative distance ‘here’h
G route graph
g rational functionrat
g power functionpow
H human participanti
k route segment
l landmark typei
Ml landmark type in metric graphi
M sub-matchi,j
N nodei
O personal reference system of humanH
x