Organic Computing — A Paradigm Shift for Complex Systems (eBook)

Preface 6
Acknowledgement 8
Contents 10
Review Team 15
Projects 19
Contributors 22
Chapter 1: Theoretical Foundations 30
Chapter 1.1: Adaptivity and Self-organisation in Organic Computing Systems 33
1 Introduction 34
2 State of the Art 36
3 Is It Self-organising or Not? 38
4 System Description 40
5 Robustness and Adaptivity 43
6 System Classification 46
6.1 Classical Feedback Control Loop System 47
6.2 Configuration Space 48
6.3 Limitations of Adaptivity 50
6.4 Learning 51
6.5 Degree of Autonomy 52
6.6 Self-organising Systems 54
7 Architectures for Controlled Self-organisation 56
7.1 Architectural Options 57
7.2 Control Possibilities of OC Systems 58
7.3 Roadmap to Ideal OC Systems 59
8 Conclusion 60
9 Outlook 61
References 62
Chapter 1.2: Quantitative Emergence 66
1 Introduction 66
2 The Measurement of Order 67
3 Observation Model 68
4 Emergence 69
5 Discussion 70
5.1 Limitations 70
5.2 Redundancy and Emergence 71
5.3 Pragmatic Information 72
6 Observer/Controller Architecture 74
7 Experimental Results 75
7.1 Experimental Environment 75
7.2 Results 75
7.3 Prediction 77
8 Conclusion and Outlook 78
References 79
Chapter 1.3: Divergence Measures as a Generalised Approach to Quantitative Emergence 80
1 Introduction 80
2 State of the Art 81
3 Techniques for Emergence Detection and Measurement 82
3.1 Discrete Entropy Difference 82
3.2 Divergence-Based Emergence Measures 83
3.3 Approximations of Divergence-Based Emergence Measures 84
4 Experimental Results 87
4.1 From Chaos To Order 87
4.2 Concept Drift 88
4.3 Novelty 90
5 Conclusion and Outlook 90
References 92
Chapter 1.4: Emergent Control 94
1 Introduction 94
2 Feedback Control and Emergent Control 95
2.1 Feedback Control 95
2.2 Emergent Control 96
3 Examples 97
3.1 EC and FC Result in the Same Macro-behaviour 97
3.2 Emergent Control of the Number of Clusters 99
4 How to Construct Macro-to-Micro Feed-Forward Controller? 101
5 Quantitative Comparison of the Performance of Emergent Control vs. Feedback Control 101
6 Discussion, Conclusion, and Outlook 102
References 104
Chapter 1.5: Constraining Self-organisation Through Corridors of Correct Behaviour: The Restore Invariant Approach 106
1 Introduction 106
2 The Restore Invariant Approach 107
2.1 A Formal View on the Restore Invariant Approach 108
2.2 Behavioural Guarantees 110
Verification of the Functional System 110
Verification of Self-x Mechanisms by Verified Result Checking 111
3 Example Scenario 112
4 Defining Corridors of Correct Behaviour 113
5 Decentralised Restoration of Invariants 114
5.1 Coalitions for Local Reconfiguration 114
5.2 Coalition Formation Strategy 115
5.3 Strategy for Local Variable Violation 116
5.4 Strategy for Complete Breakdown of an Agent 117
5.5 Discussion 118
6 Summary and Outlook 119
References 119
Chapter 1.6: Ant Inspired Methods for Organic Computing 121
1 Introduction 121
2 Spatial Organisation of Work and Response-Threshold Models 124
Results and Discussion 125
Effect of Demand Distribution 125
Demand Redistribution as a Third Task 126
3 Learning from House-Hunting Ants: Collective Decision-Making in Organic Computing Systems 127
3.1 Model of the Organic Computing System 128
3.2 Results and Discussion 130
4 Sorting Networks of Router Agents 131
Results and Discussion 132
5 Summary 133
References 134
Chapter 1.7: Organic Computing: Metaphor or Model? 136
1 Introduction 136
2 Evolutionary Robotics as a Precursor of Organic Computing 137
3 The Evolutionary and the Engineering Paradigm 138
4 Methodological Reconstruction I: Is Evolution Design? 140
5 Methodological Reconstruction II: Is Evolution Optimisation? 143
6 Overcoming Evolutionary Robotics: Organic Computing 145
7 Self-x Properties and the Order of Descriptions 147
8 Conclusion: OC as a New Model-Theoretical Perspective 148
References 149
Chapter 2: Methods and Tools 151
Chapter 2.1: Model-Driven Development of Self-organising Control Applications 154
1 Introduction 154
2 Model-Driven Development 155
2.1 Computational Model 157
2.2 Model Transformation 158
3 Self-stabilising and Self-organising Algorithm Toolbox 159
3.1 Self-stabilising and Self-organising Algorithm Stack 160
3.2 Adaptive and Self-optimising Network Algorithms 162
Adaptive Overlay Topologies 162
Adaptive Routing 162
3.3 Composite Event Detection 164
4 Conclusions 165
References 166
Chapter 2.2: How to Design and Implement Self-organising Resource-Flow Systems 168
1 Introduction 168
2 Self-organising Resource-Flow Systems 169
3 Software Engineering Guideline 171
4 Functional and Reconfiguration Behaviour 173
4.1 An O/C Architecture with Base Agents and Reconfiguration Agents 174
Base Agent 175
Reconfiguration Agent 178
4.2 Functional Behaviour in Self-organising Resource-Flow Systems 178
5 ODP Runtime Environment 180
5.1 Architecture and Behaviour 180
5.2 Code Transformation and Extension Points 181
5.3 Plug-in Mechanism for Reconfiguration Algorithms 182
6 Conclusion and Future Work 183
References 183
Chapter 2.3: Monitoring and Self-awareness for Heterogeneous, Adaptive Computing Systems 185
1 Introduction and Motivation 185
2 Related Work 186
3 Monitoring for Heterogeneous, Adaptive Computing Systems 188
3.1 Overall Structure 188
3.2 Event Coding and Event Space 189
3.3 Associative Counter Array 190
3.4 High-Level Monitoring 191
4 State Classification and Self-awareness 191
4.1 Rule Layout and Online Derivation of Evaluation Rules 191
4.2 State Evaluation and Classification 192
4.3 Update of Rules at Runtime 193
5 Evaluation and Results 194
5.1 Prototypical Hardware Implementation 194
5.2 Self-awareness 195
Initial Classification 195
Rule-Update at Runtime 196
6 Conclusion and Outlook 197
References 198
Chapter 2.4: Generic Emergent Computing in Chip Architectures 200
1 Introduction 200
2 Related Work 201
3 Application-Specific Architectures for Marching Pixels Algorithms 202
3.1 Implementation of the Flooding Algorithm on FPGAs and ASICs 204
4 The Architecture of ParCA 205
4.1 System Overview 205
4.2 PE Architecture 207
4.3 Types of Double Buffering 210
4.4 Simulation Environment 211
5 Results and Layout 211
6 Conclusion and Outlook 212
References 212
Chapter 2.5: Multi-objective Intrinsic Evolution of Embedded Systems 214
1 Evolvable Hardware-An Introduction 214
2 Models and Algorithms 215
2.1 Cartesian Genetic Programs 215
2.2 Modular CGP 216
2.3 Multi-objective Optimisation Using CGP 217
2.4 Challenges of CGP 218
3 Development and Simulation Tools 218
4 Applications 220
4.1 Flexible EHW Pattern Matching Architectures 220
4.2 Optimising Caches: A High-Performance EHW Application 223
5 Conclusion 225
References 226
Chapter 2.6: Organisation-Oriented Chemical Programming 228
1 Introduction 228
2 Chemical Reaction Networks, Chemical Organisation Theory, and Movement between Organisations 229
3 Examples 231
3.1 A Chemical XOR-Reaction Network, Organisations, and Dynamics 231
3.2 Maximal Independent Set Problem-A Chemical Algorithm and a Small Example 233
General Algorithm 233
Small Example 235
4 Design Principles 236
4.1 Design Principles Derived from Heuristics 236
4.2 Design by Evolution 237
4.3 Design by Exploration 238
5 Conclusion 239
References 239
Chapter 2.7: Hovering Data Clouds for Organic Computing 242
1 Introduction 242
2 Related Work 243
3 Concept 244
4 Data Aggregation 246
API provided by every sensor: 247
API provided by the transport layer: 247
5 Data Dissemination-AutoCast 248
6 Evaluation 250
6.1 Data Aggregation 251
6.2 AutoCast 252
7 Conclusion and Future Work 254
References 254
Chapter 3: Learning 256
Chapter 3.1: Aspects of Learning in OC Systems 258
1 Introduction 258
2 State of the Art 260
3 Online Learning Using XCS 262
3.1 XCS with Rule Combining (XCS-RC) 262
3.2 Comparison of XCS and XCS-RC 263
4 Optimisation 265
4.1 The Role-Based Imitation Algorithm (RBI) 265
4.2 Optimisation in Dynamic Fitness Landscapes 268
Parameter Settings and Experimental Results 269
5 Conclusion 270
References 271
Chapter 3.2: Combining Software and Hardware LCS for Lightweight On-chip Learning 273
1 Introduction 273
2 Related Work 274
3 XCS and LCT 275
4 Methodology 275
5 Experimental Setup 277
6 Results 278
6.1 Multiplexer 278
6.2 Task Allocation 280
6.3 Component Parameterisation 282
7 Conclusions 283
References 284
Chapter 3.3: Collaborative Learning by Knowledge Exchange 286
1 Introduction 286
2 Overview of Methodological Foundations 287
2.1 Layered Architecture of an Organic Agent 287
2.2 Knowledge Representation and Off-line-Training 288
2.3 Novelty and Obsoleteness Detection and Reaction 290
2.4 Knowledge Extraction and Integration or Fusion 292
2.5 Interestingness Assessment 292
3 Experiments 293
4 Conclusion 297
References 298
Chapter 3.4: A Framework for Controlled Self-optimisation in Modular System Architectures 300
1 Introduction 300
1.1 Background 300
1.2 Desired Properties of Safe Self-optimisation 301
2 State of the Art 302
3 Framework for Controlled Self-optimisation 304
3.1 Overview 304
3.2 Directed Self-learning 306
3.3 Neuro-fuzzy Elements 308
3.4 DSL and the SILKE Approach 308
3.5 Self-optimisation and Uncertainties 310
4 Discussion 311
5 Conclusion and Outlook 311
References 312
Chapter 3.5: Increasing Learning Speed by Imitation in Multi-robot Societies 314
1 Introduction 314
2 Related Work 315
3 ESLAS-An Imitation Supporting Architecture 316
3.1 Motivation Layer 316
3.2 Strategy Layer 317
3.3 Skill Layer 317
4 Enabling Robots to Learn by Imitation 317
4.1 Deciding Whom and When to Imitate 318
4.2 Interpreting Observed Behaviour 319
4.3 Incorporating the Extracted Knowledge 321
5 Results by Simulation 322
6 Conclusion 325
References 326
Chapter 3.6: Learning to Look at Humans 327
1 Introduction 327
2 Learning Upper Body Models 328
3 Meta-model Construction 330
4 Matching Considerations 331
5 Experimental Results 334
6 Conclusion and Further Work 335
References 338
Chapter 4: Architectures 341
Chapter 4.1: Observation and Control of Organic Systems 343
1 Introduction 343
2 Generic Observer/Controller Architecture 344
2.1 System Under Observation and Control 345
2.2 Observer 346
2.3 Controller 347
3 Design Variants of the Observer/Controller Architecture 348
4 Application Survey 349
4.1 Central Observer/Controller 350
Elevator Control 350
Organic Computing in Off-highway Machines 350
Cleaning Robots 351
4.2 Distributed Observer/Controller Components 351
Organic Network Control 352
Organic Traffic Control 352
4.3 Multi-levelled Observer/Controller Components 353
MeRegioMobil 353
5 Conclusion 354
References 354
Chapter 4.2: Organic Computing Middleware for Ubiquitous Environments 357
1 Introduction 357
2 Related Work 358
3 Initial OCµ Architecture 359
3.1 Middleware Components 360
3.2 Messaging 362
3.3 Monitoring 362
3.4 Self-X Services 363
3.5 Shortcomings 364
4 The Refined Architecture 364
4.1 Monitor 365
4.2 Analyse 365
4.3 Plan 366
4.4 Execute 367
5 Summary and Outlook 367
References 368
Chapter 4.3: DodOrg-A Self-adaptive Organic Many-core Architecture 370
1 Introduction 370
2 Organic Hardware 372
2.1 Communication Infrastructure 373
2.2 Power Management 374
2.3 Low-Level Monitoring 375
2.4 Hardware Prototype 376
3 Organic Monitoring 376
4 Organic Middleware 378
5 Organic Thermal Management 379
6 Conclusion 382
References 383
Chapter 4.4: The Artificial Hormone System-An Organic Middleware for Self-organising Real-Time Task Allocation 386
1 Introduction 386
2 The Basic Principle of the Artificial Hormone System 388
2.1 Different Kinds of Hormones 389
2.2 Constraints of the Artificial Hormone System 391
3 Stability Analysis of the AHS 392
3.1 AHS Stability Without Accelerators 392
3.2 AHS Stability with Equal Suppressors, Accelerators and Eager Values 393
3.3 AHS Stability with Varying Hormones 393
3.4 AHS Stability with Additional Local Suppressors and Accelerators 393
4 AHS Implementation 394
5 Test Scenario and Results 395
6 Related Work 399
7 Conclusion 400
References 400
Chapter 4.5: ORCA: An Organic Robot Control Architecture 402
1 Background 402
2 Organic Robot Control Architecture 403
3 Health Signal Principles 406
3.1 Health Signals 406
3.2 Health Signal Generation 407
3.3 Health Signal Fusion 409
3.4 Health Signal Processing 410
4 Discussion 412
5 Conclusion and Outlook 413
References 414
Chapter 4.6: The EPOC Architecture-Enabling Evolution Under Hard Constraints 416
1 Introduction 416
2 Architectural Approach 417
3 Layered Contracting Architecture 417
4 Domain Separation 418
4.1 Model Domain 420
4.2 Execution Domain 421
5 Observer/Controller Loops 423
5.1 Model Domain O/C-Loop 423
Observer-Model Analysis 423
Controller-Model Optimisation 424
5.2 Execution Domain O/C-Loop 424
Monitoring Timing Aspects 425
Monitoring Memory Access Patterns 425
5.3 Long-Term Evolution and Quick Reflexes 426
6 Conclusion 427
References 427
Chapter 4.7: Autonomic System on Chip Platform 430
1 Introduction 430
2 Autonomic SoC Architecture 432
3 Autonomic SoC Architectural Building Blocks 434
3.1 Autonomic Processor Core 434
3.2 AE Evaluator Architecture 436
3.3 Autonomic Element Interconnect 439
4 ASoC Evaluation 440
5 Conclusion 440
References 442
Chapter 5: Applications 443
Chapter 5.1: Organic Traffic Control 446
1 Introduction 446
2 Adaptive Learning Intersections 448
2.1 State of the Art 448
2.2 An Observer/Controller Architecture for Signal Control 449
Observing the Traffic 449
Controlling the Signalisation 450
Experimental Results 451
3 Self-organised Coordination 452
3.1 State of the Art 453
3.2 Traffic-Responsive Decentralised Coordination 453
Decentralised Progressive Signal Systems 453
Experimental Results 454
3.3 Limitations of Decentralised Control 455
Regional Manager 455
Experimental Results 457
4 Self-organised Routing 457
4.1 State of the Art 458
4.2 Self-organised Routing 458
Distance Vector Routing for Road Networks 458
Experimental Results 459
5 Conclusion 460
References 460
Chapter 5.2: Methods for Improving the Flow of Traffic 462
1 Introduction 462
1.1 Traffic 462
1.2 Computing Methodologies in Traffic and Telematics 463
1.3 Our Approach 464
2 Traffic Models 465
2.1 Single-Lane Traffic 465
2.2 Multi-lane Traffic 465
2.3 Our Extensions to Krauß's Lane-Change Model 466
2.4 Other Models 466
3 Simulation 467
4 Improving the Flow of Highway Traffic 468
5 AutoNomos Strategy Results 469
5.1 Single Lane 469
5.2 Multiple Lanes 471
6 Urban Traffic 472
6.1 Traffic Collapse in an Urban Scenario 472
6.2 Flow Over Successive Traffic Lights 473
6.3 Rerouting and Recovery 474
References 474
Chapter 5.3: Applying ASoC to Multi-core Applications for Workload Management 476
1 Introduction 476
2 System Overview 477
2.1 Functional Layer 478
2.2 Application Software 479
2.3 Autonomic Layer 480
Monitors 480
Actuators 480
Evaluator 481
3 Results 482
3.1 Comparison of Autonomic and Static Systems 483
3.2 Comparison of Autonomic and DVFS Systems 484
3.3 Area Overheads 485
4 Conclusion 486
References 486
Chapter 5.4: Efficient Adaptive Communication from Resource-Restricted Transmitters 488
1 Introduction 488
2 A Protocol for Distributed Adaptive Transmit Beamforming in Wireless Sensor Networks 489
2.1 Experimental Verification of the Protocol 490
2.2 Environmental Impacts on the Performance of the Protocol 491
Impact of Noise and Interference 492
Impact of the Network Size 494
2.3 Impact of Node Mobility 494
2.4 Adaptive Protocols for Distributed Adaptive Beamforming in Wireless Sensor Networks 495
2.5 Proposal of Two Adaptive Protocols 495
An Evolutionary Learning Approach 496
A Metropolis Learning Approach 497
3 Detection of Environmental Conditions in Wireless Sensor Networks 498
3.1 System 498
3.2 Features and Classification 498
3.3 Experiment 499
Results 499
4 Conclusion 500
References 501
Chapter 5.5: OrganicBus: Organic Self-organising Bus-Based Communication Systems 503
1 Introduction 503
2 Model and Problem Definition 504
2.1 Types of Streams 506
Hard Real-Time Streams 506
Soft Real-Time Streams 506
Bandwidth Streams 506
2.2 Objectives of the Organic Communication System 507
3 Hard Real-Time Streams 507
4 Soft Real-Time Streams 508
4.1 DynOAA 509
4.2 Results 510
5 Bandwidth Streams 510
5.1 Medium Access Game 511
5.2 Enhanced Priority-Based Medium Access Game 512
5.3 Penalty Learning Algorithm (PLA) 512
5.4 Results 513
6 Conclusion and Future Work 514
References 515
Chapter 5.6: OC Principles in Wireless Sensor Networks 516
1 Introduction 516
2 Self-organisation in Wireless Sensor Networks 517
2.1 Role Assignment and Adaptive Role Change 517
2.2 Clustering Schemes 519
3 Self-healing in Wireless Sensor Networks 520
3.1 Impaired Node Detection 521
3.2 Preventive Role Changing 522
3.3 Cluster-Based Rehabilitation 522
4 Robust Scale-Free Routing 525
5 Conclusion and Outlook 528
References 528
Chapter 5.7: Application of the Organic Robot Control Architecture ORCA to the Six-Legged Walking Robot OSCAR 530
1 Introduction 530
2 Six-Legged Walking Robot OSCAR 531
3 Robot Control Architecture ORCA 532
4 Implementation of ORCA on OSCAR 533
4.1 Distributed Leg Control and Self-Organising Gait Patterns 533
4.2 Adaptive Walking by Reflexes and Active Compliance 535
4.3 Reaction to Anomalies 536
Weak Anomalies 536
Medium Anomalies 537
Strong Anomalies 537
4.4 Local Fault Masking by Means of Adaptive Filters 537
4.5 Self-reconfiguration in Case of Amputated Legs 538
4.6 Primitive Reactive Behaviours 539
4.7 Path Planning Based on Health Signals 540
5 Conclusions and Outlook 541
References 542
Chapter 5.8: Energy-Awareness in Self-organising Robotic Exploration Teams 544
1 Introduction 544
1.1 Contents of the Article 545
1.2 Related Work 547
1.3 Notation 548
2 Energy Spent for Measurements 549
3 Energy Spent for Motion 550
4 Energy Spent for Motion and Measurements 553
5 Conclusion and Outlook 554
References 555
Chapter 5.9: A Fast Hierarchical Learning Approach for Autonomous Robots 557
1 Introduction 557
2 Overview of the ESLAS Architecture 558
2.1 Motivation Layer 559
2.2 Strategy Layer 560
2.3 Skill Layer 560
3 Ensuring Feasibility by State Abstraction 561
3.1 Transition Heuristic 562
3.2 Experience Heuristic 562
3.3 Failure Heuristic 562
3.4 Simplification Heuristic 563
3.5 Reward Heuristic 563
4 Learning Skills at the Lowest Level 564
5 Exploration vs. Exploitation 566
6 Discussion 567
7 Conclusion and Future Work 568
References 569
Chapter 5.10: Emergent Computing with Marching Pixels for Real-Time Smart Camera Applications 571
1 Introduction 571
2 Related Work 573
3 The Principle of Marching Pixels Algorithms 574
3.1 The Basic Procedures of Marching Pixels Algorithms 574
3.2 The Local Calculation Tasks of Marching Pixels 575
3.3 Example 577
3.4 Flooding as an Example of a MP Algorithm 578
3.5 Limits of Flooding and Further MP Algorithms 581
4 Outlook and Summary 582
References 583
Chapter 6: Status and Outlook 585
Chapter 6.1.1: OC Techniques Applied to Solve Reliability Problems in Future 1000-Core Processors 586
References 587
Chapter 6.1.2: Dynamic Classification for Embedded Real-Time Systems 589
References 590
Chapter 6.1.3: On the Future of Chemistry-Inspired Computing 592
References 593
Chapter 6.1.4: Agent-Based Thermal Management for Multi-core Architectures 595
References 596
Chapter 6.1.5: Trust Management-Handling Uncertainties in Embedded Systems 597
References 598
Chapter 6.1.6: OC-Trust: Towards Trustworthy Organic Computing Systems 600
References 601
Chapter 6.1.7: Emergence in Action 603
1 Cyber-physical Systems 603
2 Actions 603
3 Run-Time System 604
References 604
Chapter 6.1.8: Organic Computing in Off-highway Machines 606
References 608
Chapter 6.1.9: Decentralised Energy Management for Smart Homes 609
References 610
Chapter 6.1.10: Self-organising Distributed Smart Camera Systems 612
References 613
Chapter 6.1.11: Organic Network Control 614
References 615
Chapter 6.2: Organic Computing: Quo vadis? 617
1 Design Time to Runtime 617
2 Cautious Configuration Space Design 619
3 Self-organisation is not Magic 620
4 Overhead and Complexity 620
5 Runtime Learning (Sandboxing) 622
6 OC Devices Can Be Interpreted as Cognitive and Self-optimising Systems 623
7 Definition of Emergence Leads to Analysis of Distribution Functions 623
8 No Decentralisation at Any Cost! 624
9 Human-Centric OC 625
10 Social OC 625
11 Technical Applications? 627
12 Organisational Sciences 627
13 Conclusion 628
References 628