Extraction of probabilistic route information representations from human-robot dialogs [Elektronische Ressource] / Andrea M. Bauer

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2010
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

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