Constraint based world modeling for multi agent systems in dynamic environments [Elektronische Ressource] / von Daniel Göhring

Dipl.-Inf. Daniel Göhring

Sujets

• Informatik

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2009
• Nombre de lectures: 11
• Langue: English
• Poids de l'ouvrage: 8 Mo

Extrait

Constraint Based World Modeling for Multi Agent
Systems in Dynamic Environments
DISSERTATION
zurErlangungdesakademischenGrades
Dr.rer.nat.
imFachInformatik
eingereichtander
Mathematisch-NaturwissenschaftlichenFakultätII
Humboldt-UniversitätzuBerlin
von
Dipl.-Inf. Daniel Göhring
06.Juni1978
PräsidentderHumboldt-UniversitätzuBerlin:
Prof.Dr.ChristophMarkschies
DekanderMathematisch-NaturwissenschaftlichenFakultätII:
Prof.Dr.PeterFrensch
Gutachter:
1. Prof.Dr.Hans-DieterBurkhard
2. Prof.Dr.UweSchwiegelshohn
3. Prof.RickMiddleton
eingereicht am: 14.April2009
Tag der mündlichen Prüfung: 10.November2009For my parents.Abstract
Mobile autonomous robotics is a very young and complex field of research. Only
in recent decades have robots become able to explore, to move, navigate and to
interact with their environment.
Since the world is uncertain and since robots can only gain partial information
about it, probabilistic navigation algorithms have become very popular whenever
a robot has to localize itself or surrounding objects. Furthermore, cooperative ex-
ploration and localization approaches have become very relevant lately, as robots
begin to act not just alone but in groups. Within this thesis a new approach using
the concept of spatial percept-relations for cooperative environment modeling is
presented and evaluated. As a second contribution, constraint based localization
techniques will be introduced for having a robot or a group of robots efficiently
localized and to model their environment.
vZusammenfassung
Die mobile Robotik stellt ein sehr junges und komplexes Forschungsfelder unserer
Zeit dar. Innerhalb der letzten Jahrzehnte wurde es Robotern möglich, sich inner-
halb ihrer Umgebung zu bewegen, zu navigieren und mit ihrer Umwelt zu intera-
gieren.
Aufgrund der Tatsache, dass die Welt von Unsicherheit geprägt ist und ein Ro-
boter immer nur partielle Information über sie erhalten kann, wurden probabilis-
tische Navigationsverfahren entwickelt, mit denen sich Roboter lokalisieren und
Objekte ihrer Umgebung modellieren können. Weiterhin wurden in letzter Zeit
Verfahren untersucht, die die kooperative Exploration der Umgebung durch eine
Gruppe von Robotern zum Ziel haben. In der vorliegenden Arbeit wird ein neuarti-
ges Konzept, welches sich Perzeptrelationen für die kooperative Umweltmodellie-
rung zu Nutze macht, vorgestellt und evaluiert. Einen zweiten Beitrag der Arbeit
stellen constraintbasierte Lokalisierungstechniken dar, die es einem oder mehreren
Robotern auf effiziente Art und Weise ermöglichen, sich zu lokalisieren und ihre
Umwelt zu modellieren.
viiContents
1 Introduction 3
1.1 Perception, Uncertainty and Robustness . . . . . . . . . . . . . . . . . . . 3
1.2 Multi-Agent Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Thesis Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Preliminaries 7
2.1 Basics of Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Normal Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Important Terms for Object Modeling . . . . . . . . . . . . . . . . . . . . 12
2.3.1 State Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.2 Further Modeling Terms . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Bayes Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Bayesian Filtering Techniques 19
3.1 The Kalman Filter and its Extensions . . . . . . . . . . . . . . . . . . . . . 19
3.1.1 Extended Kalman Filter . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.2 Unscented Filter . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.3 Transform Linearization . . . . . . . . . . . . . . . . . 25
3.1.4 Information Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Multi-Hypotheses Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Grid-Based Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4 Topological Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.5 Monte-Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.5.1 Properties of MCL . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.5.2 Adaptive Particle Filtering . . . . . . . . . . . . . . . . . . . . . . . 34
3.6 Distribution Function Measures . . . . . . . . . . . . . . . . . . . . . . . . 38
3.7 General Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Spatial Relationships of Visual Sensory Data 41
4.1 Sensory Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Reference Systems for World Modeling . . . . . . . . . . . . . . . . . . . 42
4.2.1 Egocentric World Modeling . . . . . . . . . . . . . . . . . . . . . . 43
4.2.2 Allocentric Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3 Shareable Sensory Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 Object Modeling Using Percept-Relations . . . . . . . . . . . . . . . . . . 45
ixInhaltsverzeichnis
4.4.1 Information Gain by Single Percepts . . . . . . . . . . . . . . . . . 46
4.4.2 Gain from Percept-Relations . . . . . . . . . . . . . . 47
4.5 Ambiguous Landmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.6 Monte-Carlo Localization - Implementation . . . . . . . . . . . . . . . . . 51
4.6.1 Multi Agent Modeling . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.6.2 Self-Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.7 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5 Cooperative Dynamics Modeling and Communication 63
5.1 Modeling of Dynamics Using Percept-Relations . . . . . . . . . . . . . . 63
5.1.1 Friction Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.1.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.2 Dynamics and Time Components . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.1 Synchronization of Communication . . . . . . . . . . . . . . . . . 70
5.2.2 Handling Communication Delays . . . . . . . . . . . . . . . . . . 71
5.2.3 Future Prediction, History Revision . . . . . . . . . . . . . . . . . 72
5.3 Distributed Calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6 Theory of Constraint Based Modeling 77
6.1 Fundamentals of Constraint Satisfaction Problems . . . . . . . . . . . . . 78
6.2 Generating Constraints from Sensory Data . . . . . . . . . . . . . . . . . 79
6.2.1 Distance Based Constraints . . . . . . . . . . . . . . . . . . . . . . 79
6.2.2 Bearing Based . . . . . . . . . . . . . . . . . . . . . . . 79
6.3 Ambiguous Sensory Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.4 Constraint Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.5 Quality Measures for Constraint Sets . . . . . . . . . . . . . . . . . . . . . 86
6.5.1 Inconsistency Measure . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.5.2 Ambiguity Measures . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.6 Optimal Constraint Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.7 Handling Inconsistencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.7.1 Greedy Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.7.2 Sensory Data Clustering . . . . . . . . . . . . . . . . . . . . . . . . 92
6.7.3 Model Resetting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.7.4 Constraint border enlargement. . . . . . . . . . . . . . . . . . . . . 94
6.7.5 Weighted Soft-Cuts and Intra-Constraint Merges . . . . . . . . . . 94
6.8 Position Estimate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7 Constraint Based Localization 99
7.1 Constraint Generation from Percepts . . . . . . . . . . . . . . . . . . . . . 99
7.2 Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
x