A unified distributed system architecture for goal-based interaction with smart environments [Elektronische Ressource] / Thomas Heider

A unified distributed system architecture for goal-based interaction with smart environments [Elektronische Ressource] / Thomas Heider

English
214 Pages
Read
Download
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

A Uni ed Distributed System Architecture forGoal-based Interaction with Smart EnvironmentsDipl.-Ing. Thomas HeiderRostock, April 22, 2009Dissertation zur Erlangung des akademischen GradesDoktor-Ingenieur (Dr.-Ing.)der Fakultät für Informatik und Elektrotechnik der Universität RostockPrincipal AdviserProf. Dr. Thomas Kirste, Universität RostockExternal ReviewersProf. Dr. Birgitta König-Ries, Universität JenaProf. Dr. Klaus Schmid, Universität HildesheimDay of Defense:July 24, 2009iiAbstractThe vision of Ambient Intelligence is based on the ubiquity of information technology, thepresence of computation, communication, and sensorial capabilities in an unlimited abun-dance of everyday appliances and environments.It is now a signi cant challenge to let ambient intelligence effortlessly emerge from the de-vices that surround the user in his environment. Future ambient intelligent infrastructures(e.g., Smart Environments) must be able to con gure themselves from the available com-ponents in order to be effective in the real world. They require software technologies thatenable ad-hoc ensembles of devices to spontaneously form a coherent group of cooperatingcomponents. This is speci cally a challenge, if the individual components are heterogeneousin nature and have to engage in complex activity sequences in order to achieve a user goal.Typical examples of such ensembles are smart environments.

Subjects

Informations

Published by
Published 01 January 2009
Reads 17
Language English
Document size 9 MB
Report a problem

A Uni ed Distributed System Architecture for
Goal-based Interaction with Smart Environments
Dipl.-Ing. Thomas Heider
Rostock, April 22, 2009
Dissertation zur Erlangung des akademischen Grades
Doktor-Ingenieur (Dr.-Ing.)
der Fakultät für Informatik und Elektrotechnik der Universität RostockPrincipal Adviser
Prof. Dr. Thomas Kirste, Universität Rostock
External Reviewers
Prof. Dr. Birgitta König-Ries, Universität Jena
Prof. Dr. Klaus Schmid, Universität Hildesheim
Day of Defense:
July 24, 2009
iiAbstract
The vision of Ambient Intelligence is based on the ubiquity of information technology, the
presence of computation, communication, and sensorial capabilities in an unlimited abun-
dance of everyday appliances and environments.
It is now a signi cant challenge to let ambient intelligence effortlessly emerge from the de-
vices that surround the user in his environment. Future ambient intelligent infrastructures
(e.g., Smart Environments) must be able to con gure themselves from the available com-
ponents in order to be effective in the real world. They require software technologies that
enable ad-hoc ensembles of devices to spontaneously form a coherent group of cooperating
components. This is speci cally a challenge, if the individual components are heterogeneous
in nature and have to engage in complex activity sequences in order to achieve a user goal.
Typical examples of such ensembles are smart environments.
It will be argued that enabling an ensemble of devices to spontaneously and coherently act
on behalf of the user, requires software technologies that support unsupervised spontaneous
cooperation. This thesis will illustrate why a goal based approach is reasonable and how
explicit goals can be used to nd device spanning strategies that assist the user.
In order to solve the challenges noted above, an overall concept and architecture based
on goal based interaction will be illustrated. Furthermore different concepts of cooperation
strategies will be introduced and nally an evaluation will prove the validity of the approach.
iiiivKurzfassung
Die Vision von Ambient Intelligence basiert auf ubiquitären Informationstechnologien in
Alltagsgeräten und Umgebungen, wobei Rechnerkapazität, Kommunikation und sensorische
Fähigkeiten in einer unlimitierten Form vorhanden sind.
Eine der zentralen Herausforderungen ist es dafür zu sorgen, dass Ambient Intelligence aus
den Geräten die den Nutzer umgeben mühelos enstehen kann. Zukünftige Ambient Intel-
ligence Infrastrukturen (z.B. Intelligente Umgebungen) müssen in der Lage sein, sich aus
den vorhandenen Komponenten selbst zu kon gurieren, um in der realen Welt effektiv zu
sein. Dies erfordert Softwaretechnologien, die es einem ad-hoc Ensemble von Geräten er-
möglichen, spontan eine Gruppe von kooperierenden Komponenten zu bilden. Dies ist
besonders deshalb eine Herausforderung, da die individuellen sehr heterogen
sind und sich an komplexen Aktivitäts-Sequenzen beteiligen müssen, um die Nutzerziele zu
erreichen. Ein typisches Beispiel für solche Ensembles sind sogenannte Smart Environments.
Um Geräte-Ensembles zu befähigen, spontan und kohärent im Interesse des Nutzers zu
agieren, werden Technologien benötigt die unüberwachte spontane Kooperation unterstützen.
Die Dissertation wird darstellen, warum ein zielbasierter Ansatz erfolgversprechend ist, und
wie explizite Ziele verwendet werden können, um systemübergreifende Strategien zu gener-
ieren.
Um die zuvor erwähnten Herausforderungen zu lösen, wird ein Gesamtkonzept und eine
Architektur vorgestellt, die auf zielbasierter Interaktion basiert. Weiterhin werden ver-
schiedene Konzepte zur Generierung von Kooperationsstrategien erläutert. Eine abschließen-
de Evaluierung zeigt die Gültigkeit des Ansatzes.
vviContents
1 Introduction 1
1.1 Thematic Context & Motivation . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Ambient Intelligent Environments . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Application Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 User Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Building AmI Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.1 Some Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.2 System Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.1 Paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.2 Architectural Integration . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.3 Operational . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.4 Proof of Realizability & Usefulness . . . . . . . . . . . . . . . . . . . 19
1.4.5 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Contribution & Results of the Thesis . . . . . . . . . . . . . . . . . . . . . . 19
1.6 Chronology of the presented work . . . . . . . . . . . . . . . . . . . . . . . 20
1.7 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 Goal-based Interaction 23
2.1 The Application Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Function-based vs. Goal-based . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Dynamic Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4 Explicit Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.1 Goals in Smart Environments . . . . . . . . . . . . . . . . . . . . . . 28
2.4.2 Goal classi cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4.3 Goal Example: Direct Goals . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.4 Goal Indirect Goals . . . . . . . . . . . . . . . . . . . . . . 34
2.5 Goal-based Interaction – Conclusion . . . . . . . . . . . . . . . . . . . . . . 35
2.5.1 Intention Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.2 Strategy Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
viiCONTENTS
2.6 GbI and Computer-based Assistance . . . . . . . . . . . . . . . . . . . . . . 36
2.6.1 The Mental Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.7 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3 Related Work – Smart Environments 43
3.1 Device cooperation / user assistance in smart environments . . . . . . . . . . 43
3.1.1 Custom-tailored by the designer . . . . . . . . . . . . . . . . . . . . . 43
3.1.2 Device cooperation by Plan Recognition . . . . . . . . . . . . . . . . 46
3.1.3 Learning by observing the user . . . . . . . . . . . . . . . . . . . . . 47
3.1.4 Device cooperation by Matchmaking . . . . . . . . . . . . . . . . . . 49
3.1.5 Device – Projects focusing on middleware . . . . . . . . 51
3.1.6 Strategies for cooperation from other research areas . . . . . . . . . . 52
3.2 Software infrastructures for distributed systems . . . . . . . . . . . . . . . . 54
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3.1 Verdict on operational integration . . . . . . . . . . . . . . . . . . . . 57
3.3.2 Verdict on architectonic . . . . . . . . . . . . . . . . . . . 57
4 Architecture Framework 59
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2 Middleware challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3 TheEmbassi architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3.1 The Multi-Modal-Interaction (MMI) levels . . . . . . . . . . . . . . . 64
4.3.2 The assistance levels . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3.3 Additional notes on the generic architecture . . . . . . . . . . . . . . 65
4.4 The middleware modelSoda-Pop . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4.1 Component types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4.2 Channels & systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4.3 Subscriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.4.4 Message handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.5 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.6 Summary and outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.6.1 What has been achieved so far . . . . . . . . . . . . . . . . . . . . . . 74
4.6.2 Additional considerations . . . . . . . . . . . . . . . . . . . . . . . . 75
4.6.3 Enhancement ofSoda-Pop with an agent selection algorithm . . . . . 76
4.7 Ensemble Communication Framework –ECo . . . . . . . . . . . . . . . . . 77
viii5 AI Planning as Source of the Assistance Strategy 81
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2 Architecture overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3 Planning as assistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.3.1 Concrete example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.4 Why Planning as Inference? . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.4.1 Reasoning Methods in AI . . . . . . . . . . . . . . . . . . . . . . . . 85
5.4.2 Planning vs. Service Matching . . . . . . . . . . . . . . . . . . . . . . 86
5.5 The planning domain model . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.5.1 Representing Plans . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.5.2 Choosing a planning language . . . . . . . . . . . . . . . . . . . . . . 89
5.5.3 PDDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.5.4 Choosing a Planning System . . . . . . . . . . . . . . . . . . . . . . . 98
5.5.5 What about HTN planning? . . . . . . . . . . . . . . . . . . . . . . . 99
5.6 The Scheduling Coordination Algorithm . . . . . . . . . . . . . . . . . . . . 100
5.7 The joint ontology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.8 Prototype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.8.1 System extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.8.2 Operating sequence example . . . . . . . . . . . . . . . . . . . . . . . 106
5.9 Limits of the AI planning approach as assistance method . . . . . . . . . . . 106
5.10 Distributed vs. Centralized Strategy Generation . . . . . . . . . . . . . . . . 107
5.11 Chapter summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6 Optimization as Source of the Assistance Strategy 111
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.2 Smart Meeting Rooms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.3 Managing Multi-Display Environments . . . . . . . . . . . . . . . . . . . . . 113
6.4 The Need for Automatic Display Mapping . . . . . . . . . . . . . . . . . . . 115
6.4.1 User Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.5 De ning Optimal Display Mapping . . . . . . . . . . . . . . . . . . . . . . . 116
6.5.1 q – Spatial Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118s
6.5.2 q – Temporal Continuity . . . . . . . . . . . . . . . . . . . . . . . . 121t
6.5.3 q – Semantic Proximity . . . . . . . . . . . . . . . . . . . . . . . . . 121p
6.5.4 Discussion ofq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.5.5 Usingq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.6 Distributed Optimization in ad-hoc Ensembles . . . . . . . . . . . . . . . . . 123
6.6.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.6.2 The Search Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.6.3 The Display Mapping Problem as a Special Case of the Quadratic
Assignment Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
ixCONTENTS
6.6.4 Distributed Optimization – The Approach . . . . . . . . . . . . . . . 129
6.6.5 GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.6.6 Distributing GRASP (DGRASP) . . . . . . . . . . . . . . . . . . . . . 131
6.6.7 Running DGRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.7 Evaluation of . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.7.1 Environment Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.7.2 Section Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.8 Combining DGRASP and Planning . . . . . . . . . . . . . . . . . . . . . . . 142
6.8.1 Goal Re nement - Goal Deliberation . . . . . . . . . . . . . . . . . . 142
6.8.2 Soda-Pop’s Selection Mechanism . . . . . . . . . . . . . . . . . . . . 143
6.9 Evaluation ofq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.9.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
6.9.2 Calibration Experiment . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.9.3 Evaluation – Setup . . . . . . . . . . . . . . . . . . . . . 148
6.9.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.9.5 Section Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
6.10 Excursus: Goal function as Benchmark: . . . . . . . . . . . . . . . . . . . . . 158
6.11 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
7 Conclusion 161
7.1 Final example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
7.2 Summary of the results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.3 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7.4 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
A AI Planning Documents i
A.1 Example operator le . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
A.2 Environment Ontology extract . . . . . . . . . . . . . . . . . . . . . . . . . . iii
A.3 Dynamic Strategy Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
B Test rooms for optimization algorithms ix
x