Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Manual engineering and evolution of emergent algorithms for agents on two-dimensional grids [Elektronische Ressource] = Manuelle Entwicklung und Evolution emergenter Algorithmen für Agenten auf zweidimensionalen Gittern / vorgelegt von Marcus Komann

De
239 pages
Manual Engineering and Evolution of Emergent Algorithms for Agents on Two-dimensional Grids Manuelle Entwicklung und Evolution emergenter Algorithmen für Agenten auf zweidimensionalen Gittern Der Technischen Fakultät der Universität Erlangen-Nürnberg zur Erlangung des Grades D O K T O R - I N G E N I E U R vorgelegt von Marcus Komann Erlangen – 2011 Als Dissertation genehmigt von der Technischen Fakultät der Universität Erlangen-Nürnberg Tag der Einreichung: 19.07.2010 Tag der Promotion: 22.12.2010 Dekan: Prof. Dr.-Ing. Reinhard German Berichterstatter: Prof. Dr.-Ing. Dietmar Fey Prof. Dr.-Ing. Rolf Hoffmann Manual Engineering and Evolution of EmergentAlgorithms for Agents on Two-dimensional GridsManuelle Entwicklung und Evolutionemergenter Algorithmen fur Agenten aufzweidimensionalen GitternMarcus KomannAbstract. In this thesis, the problem of detecting the attributes of multipleobjects in binary images in realtime is solved. It is a common problem in in-dustrial machine vision. For the solution, the usage of emergent algorithms ona smart camera with a ne-grained massively-parallel processor is proposed.Combining both is promising since such processors can exploit the abilitiesof emergent algorithms. Therefore, so-called Marching Pixels are introduced.
Voir plus Voir moins






Manual Engineering and Evolution of Emergent Algorithms
for Agents on Two-dimensional Grids


Manuelle Entwicklung und Evolution emergenter
Algorithmen für Agenten auf zweidimensionalen Gittern











Der Technischen Fakultät der
Universität Erlangen-Nürnberg
zur Erlangung des Grades

D O K T O R - I N G E N I E U R

vorgelegt von


Marcus Komann










Erlangen – 2011


























Als Dissertation genehmigt von
der Technischen Fakultät der
Universität Erlangen-Nürnberg


Tag der Einreichung: 19.07.2010
Tag der Promotion: 22.12.2010
Dekan: Prof. Dr.-Ing. Reinhard German
Berichterstatter: Prof. Dr.-Ing. Dietmar Fey
Prof. Dr.-Ing. Rolf Hoffmann Manual Engineering and Evolution of Emergent
Algorithms for Agents on Two-dimensional Grids
Manuelle Entwicklung und Evolution
emergenter Algorithmen fur Agenten auf
zweidimensionalen Gittern
Marcus KomannAbstract. In this thesis, the problem of detecting the attributes of multiple
objects in binary images in realtime is solved. It is a common problem in in-
dustrial machine vision. For the solution, the usage of emergent algorithms on
a smart camera with a ne-grained massively-parallel processor is proposed.
Combining both is promising since such processors can exploit the abilities
of emergent algorithms. Therefore, so-called Marching Pixels are introduced.
These are local agents that traverse the pixel grid of an image in a certain way
in order to accumulate global data about the image objects. At rst, manually
engineered Marching Pixels algorithms for di erent object classes are presented
and compared. Afterwards, their realizations in hardware are shown. These
realizations are able to ful ll the realtime requirements and are small enough
for application in real industrial scenarios. They can further be used to execute
other emergent algorithms that are based on 2-D grids. However, the abso-
lute quality of the manually engineered algorithms is unknown. In the thesis,
emergent agent algorithms for 2-D grids are thus also evolved. First, the ef-
fectiveness of evolution for nding good emergent agent algorithms is shown.
Then, it is argued that improving agent abilities has to be done by cautiously
balancing increased agent amounts and higher agent intelligence. The focus on
the initial machine vision problem is thereby expanded to emergent agents on
2-D grids in general since many complex systems today comprise such entities
and controlling their emergent phenomena is di cult but worthwhile.
Zusammenfassung. In dieser Dissertation wird das Problem der Realzeit-
Ermittlung der Eigenschaften mehrerer Objekte in binaren Bildern gelost. Dies
ist ein verbreitetes Problem der industriellen maschinellen Bildverarbeitung.
Als Losung wird der Einsatz emergenter Algorithmen auf einer intelligenten
Kamera mit massiv-parallelem Prozessor vorgeschlagen. Die Kombination bei-
der ist vielversprechend, weil solche Prozessoren die Leistungsfahigkeit emer-
genter Algorithmen besonders gut ausnutzen konnen. Darum werden so ge-
nannte Marching Pixels vorgestellt. Dies sind lokale Agenten, die das Pixelfeld
eines Bildes auf eine bestimmte Art und Weise ub erlaufen um Informationen
ub er die Objekte im Bild zu sammeln. Zuerst werden von Hand entwickelte
Marching Pixels Algorithmen fur verschiedene Objektklassen prasen tiert und
verglichen. Danach werden ihre Hardware-Realisierungen gezeigt. Diese Reali-
sierungen sind in der Lage Realzeitanforderungen zu erfullen und klein genug
fur den Einsatz in echten industriellen Umgebungen. Daruber hinaus kann
man sie benutzen um andere auf 2-D-Gittern beruhende emergente Algorith-
men auszufuhren. Die absolute Qualitat der von Hand entwickelten
men ist aber unbekannt. In dieser Dissertation werden emergente Agentenalgo-
rithmen daher auch evolviert. Zuerst wird gezeigt, dass Evolution ein e ekti-
ves Verfahren fur die Suche nach emergenten Agentenalgorithmen ist. Danach
wird argumentiert, dass die Verbesserung von Agentenfahigkeiten am besten
durch behutsames Ausbalancieren von hoheren Agentenzahlen und gesteigerter
Agentenintelligenz erreicht wird. Der Fokus auf das Ausgangsproblem der ma-
schinellen Bildverarbeitung wird dabei auf Agenten auf 2-D-Gittern im Allge-
meinen erweitert, da viele komplexe Systeme heutzutage aus solchen Einheiten
bestehen und weil die Kontrolle ihrer emergenten Phanomene schwierig aber
lohnend ist.iii
\The whole is greater than the sum of the parts."
Aristotle, Metaphysics (shortened)iv
Acknowledgment. I would rst like to thank my mentor Dietmar Fey for his
support, his enthusiasm, his e orts, and his ability to always motivate me. Without
him, this thesis would not exist. I further want to mention my colleagues and
students Andreas L., Andreas M., Andreas S., Carsten, Christian, David, Frank,
Marc, Michael, Patrick, and Tobias whose ideas and work have positively in uenced
this thesis. At last, i would like to express my appreciation for the German BAF oG
which allowed me and many other people to study even if their parents could not
a ord it. Education is power. Everyone deserves it.Contents
List of Figures ix
List of Tables xiii
Part 1. Introduction, Basics, and Related Work 1
Chapter I. Introduction 3
1. Fast Machine Vision Needs Smart Cameras and Parallelism 3
2. Emergent Algorithms Exploit Fine-Grained Parallelism 4
3. Two Ways for Finding Emergent Algorithms 5
4. Objectives and Outline 6
Chapter II. Basics and Related Work 11
1. Emergence 12
2. Ant Algorithms 12
3. Cellular Automata 13
4. Evolution 17
5. The Creature’s Exploration Problem 21
6. Image Processing 24
7. Smart Cameras and Fine-grained Massively-parallel Hardware 27
Part 2. Introducing Marching Pixels 33
Chapter III. The Idea of Marching Pixels 35
1. Formal Problem De nition 35
2. What are Marching Pixels? 36
3. Exploiting Emergence in Soft- and Hardware 38
4. The Marching Pixels Lifecycle Phases 38
Chapter IV. Compression of Collected Data - Moments 41
1. Problem De nition 42
2. Updating Relative Positions 42
3. Collecting the Results 44
4. Example 44
5. Correctness of the Computation 45
Part 3. Manually Engineered Emergent Algorithms:
The Marching Pixels Algorithm Toolbox 47
Chapter V. Edge Run 49
1. Concept 49
vvi CONTENTS
2. Speci cation 51
3. Capabilities, Constraints, and Analysis 52
Chapter VI. Reduction Lines 55
1. Concept 55
2. Speci cation 57
3. Capabilities, Constraints, and Analysis 62
Chapter VII. Flooding 67
1. Concept 67
2. Speci cation 68
3. Capabilities, Constraints, and Analysis 71
Chapter VIII. Opposite Flooding 75
1. Concept 75
2. Speci cation 77
3. Capabilities, Constraints, and Analysis 82
Chapter IX. Pearl Chains 85
1. Concept 85
2. Speci cation 87
3. Capabilities, Constraints, and Analysis 90
Chapter X. Discussing the Intermediate Global Signal 95
1. The Time Step when the Global Signal Is Triggered 95
2. A Leader Election Algorithm in Time peri for Arbitrary Objects 98
Part 4. Implementation and Hardware Layer 101
Chapter XI. Hardware for Agents on 2-D Grids and the Observer Processor 103
1. An Array of Massively-Parallel Processor Elements 103
2. Finish And Output of Computation - The Observer Processor 104
Chapter XII. Marching Pixels and Fault Tolerance 107
1. Introduction to Fault Tolerance 107
2. A Pipeline Implementation for Agents on a Grid 108
3. Redundant Bu ers and Error Insertion 110
4. Results and Conclusions 112
Chapter XIII. Implementations of the Marching Pixels Algorithm Toolbox 115
1. Preliminary Remarks 116
2. Reduction Lines 116
3. Flooding 119
4. Pearl Chains 123
5. Without the Intermediate Global Signal 126
6. Generic Programmable Pipeline 127
Part 5. Evolving Emergence 133
Chapter XIV. Comparing Di erent Evolution Approaches for the Search of
Centroid Finding Algorithms 135CONTENTS vii
1. Evolving Rules for Uniform CAs 136
2. Extending the Evolution to Non-Uniform CAs 140
3. A Third Approach: Genetic Programming 142
4. Conclusions - Which Evolutionary Approach Fits Best for Agents on
2-D Grids 149
Chapter XV. The Quality of Evolution in Di cult Problem Spaces 151
1. Introduction to Evolution in Di cult Problem Spaces 151
2. De ning the Diculty of a Problem Space 152
3. Di culty of the CEP Problem Space 153
4. Evolving 6-State-Automata for the CEP 155
5. Test Results of the Evolution 158
6. Summary 159
Chapter XVI. The Relation of Amount of States and Amount of Agents 163
1. Introduction 164
2. Making Agents More or Less Elaborate 165
3. Experimental Setup and Evolutionary Parameters 166
4. Similarities and Di erences to Marching Pixels 168
5. Results for 26 Input Grids 169
6. for 62 175
7. Results for 62 Input Grids with Stigmergic Communication 181
8. Summary 188
Part 6. Conclusions and Outlook 191
Chapter XVII. Conclusions 193
1. Marching Pixels Ful ll Industrial Requirements 193
2. Evolution of Emergent Agents Is Feasible 194
Chapter XVIII. Outlook 197
1. Open Questions 197
2. Promotive Developments 198
Nomenclature 201
Bibliography 203
Appendix A. Evolution Input Grids 209
1. Size of the Grids and Amount of Non-Blocked Cells 210
2. The Five Original Initial Input Grids 211
3. The Remaining 21 Original Input Grids 212
4. The Extension Set of 36 Input Images 217

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin