-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathohne_lcs_analysis.tex
336 lines (255 loc) · 27.9 KB
/
ohne_lcs_analysis.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
\chapter{Analysen und Experimente}\label{lcs_analysis:cha}
\begin{minipage}{0.4\textwidth}
\begin{flushleft} \large
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.6\textwidth}
\begin{flushright} \tiny
\emph{An inventor is a man who asks 'Why?' of the universe and lets nothing stand between the answer and his mind.} \\
John Galt\\
~\\
~\\
\end{flushright}
\end{minipage}
In diesem Kapitel werden Tests der in Kapitel~\ref{lcs_variants:cha} und Kapitel~\ref{base_agent_types:sec} vorgestellten Algorithmen gesammelt dargestellt und analysiert. Ziel des Kapitels ist es, die bisher gemachten Aussagen, die nicht durch die Literatur abgedeckt sind, anhand empirischer Tests zu beweisen.\\
Zu Beginn werden in Kapitel~\ref{analysis_sans_lcs:cha} anfängliche Tests durchgeführt, bei denen ausschließlich die grundsätzlichen Algorithmen (Agent mit zufälliger Bewegung, Agent mit einfacher Heuristik und Agent mit intelligenter Heuristik) aus Kapitel~\ref{base_agent_types:sec} betrachtet werden. Außerdem werden dort die in Kapitel~\ref{torus_konfigurationen:sec} vorgestellten Szenarien beleuchtet.\\
Alle drei Punkte werden zusammen mit Kapitel~\ref{cha:parameter}, in dem die XCS Parameter beschrieben und analysiert werden, als Vorbereitung für eine Analyse der XCS Varianten in Kapitel~\ref{lcs_analysis:cha} dienen. Damit können gezielt die erfolgversprechenden Konfigurationen getestet werden. Insbesondere werden die drei Heuristiken auch dazu dienen, untere und obere Grenzen zu setzen. Erreicht eine XCS Variante nicht die Qualität des Algorithmus mit zufälliger Bewegung dann ist jegliche "`Optimierung"' an den Parametern wenig hilfreich, denn man kann nicht unterscheiden, ob die Verbesserung von z.B. Lernen oder von zufälligerem Verhalten rührt.\\
Anzumerken ist außerdem, dass mit "`XCS"' die XCS Variante aus Kapitel~\ref{standardxcs:sec} mit den allgemeinen Anpassungen aus Kapitel~\ref{allgemeine_anpassungen:sec} und den Parametereinstellungen aus Kapitel~\ref{cha:parameter} gemeint ist. Vereinzelt wird in diesem Kapitel auch von "`Qualitätsdifferenz"' die Rede sein. Hierbei ist die Differenz zur Qualität des Algorithmus mit zufälliger Bewegung gemeint. Zweck der Benutzung der Differenz ist, leichter die Lerneffekte zwischen verschiedenen Szenarien darzustellen. Hinzuweisen ist inbesondere noch auf Kapitel~\ref{statistiken:sec}, dort werden die einzelnen Statistiken erklärt, die hier aufgeführt werden.\\
Insgesamt kann dieses Kapitel allerdings nur einen kleinen Einblick geben. Die Anzahl der Parameterkombinationen sind sehr groß und können hier nur auszugsweise dargestellt werden.\\
\section{Erste Analyse der Agenten ohne XCS}\label{analysis_sans_lcs:cha}
In diesem Abschnitt werden erste Analysen bezüglich der verwendeten Szenarien anhand des Algorithmus zufälliger Bewegung (siehe Kapitel~\ref{randomized_movement:sec}), des Algorithmus mit einfacher Heuristik (siehe Kapitel~\ref{simple_heuristik:sec}) und des Algorithmus mit intelligenter Heuristik (siehe Kapitel~\ref{intelligent_heuristik:sec}) angefertigt. Insbesondere sollen hier aus den vorgestellten Szenarien solche gewählt werden, in welchen
\begin{itemize}
\item die einfache und die intelligente Heuristiken eine Qualität im Mittelfeld erreichen,
\item die Berechnungszeit möglichst gering ist,
\item der Anteil der Sprünge des Zielobjekts möglichst gering ist,
\item der Anteil der blockierten Bewegungen der Agenten möglichst gering ist,
\item ein signifikanter Unterschied zwischen der einfachen und intelligenten Heuristik besteht und
\item der zufällige Algorithmus eine möglichst niedrige Qualität erreicht.
\end{itemize}
Die Ergebnisse aus der Analyse dienen als Grundlage für die vergleichende Betrachtung der Agenten mit XCS Algorithmen in Kapitel~\ref{lcs_analysis:cha}. Insbesondere werden sie Anhaltspunkte dafür geben, welche Szenarien welche Eigenschaften der Algorithmen testen.\\
\subsection{Zielobjekt mit zufälligem Sprung (leeres Szenario)}\label{zielobjekt_analyse_zufall_sprung:sec}
Springt das Zielobjekt in jedem Schritt auf ein zufälliges Feld (siehe Kapitel~\ref{goal_zufaelliger_sprung:sec}), dann fehlt die Relation zwischen der Position in diesem Schritt zur Position im letzten Schritt. Für die Agenten besteht also keine Möglichkeit, Sensordaten über das Zielobjekt auszunutzen, um einen Vorteil im nächsten Schritt zu erlangen. Die Untersuchungen im Folgenden zeigen, dass sich mit dieser Form der Bewegung des Zielobjekts die Qualität des jeweiligen Algorithmus (fast) nur durch die Abdeckung des Torus durch die Agenten bestimmt ist.\\
Betrachtet man das Szenario ohne Hindernisse gibt sich ein klares Bild (siehe Tabelle~\ref{table:empty_total_random}), die intelligente Heuristik ist etwas besser als der des zufälligen Agenten und der einfachen Heuristik. Ein möglichst weiträumiges Verteilen auf dem Torus führt zum Erfolg. Dies zeigt sich auch in einem hohen Wert der Abdeckung, denn genau das wird mit dem völlig zufällig springenden Agenten getestet. Ebenfalls ist die Zahl der blockierten Bewegungen deutlich niedriger, was sich auch mit der Haltung des Abstands erklären lässt.\\
Die einfache Heuristik schneidet dagegen etwas schlechter als eine zufällige Bewegung ab. Zwar ist die Zahl der blockierten Bewegungen geringer, was sich dadurch erklären lässt, dass die einfache Heuristik zumindest an einem Punkt eine Sichtbarkeitsprüfung für die Richtung durchführt, in der sie sich bewegen möchte (nämlich wenn das Zielobjekt in Sicht ist), andererseits ist die Abdeckung etwas geringer. Ursache dafür ist wahrscheinlich, dass, wenn mehrere Agenten das Zielobjekt in Sichtweite haben, alle sich auf das Zielobjekt bewegen. Dadurch wird die zufällige Verteilung der Agenten auf dem Spielfeld gestört, was letztlich zu einer niedrigeren Abdeckung des Torus führt.\\
Bezüglich der Anzahl der Agenten ergeben sich keine Besonderheiten, die Verhältnisse zwischen den Qualitäten bleibt ähnlich. Nur mit steigender Agentenzahl steigt die Zahl der blockierten Bewegungen (aufgrund größerer Anzahl von blockierten Feldern), während die Abdeckung sinkt (aufgrund sich überlappender Überwachungsreichweiten).\\
\begin{table}[ht]
\caption{Zufällige Sprünge des Zielobjekts im leeren Szenario ohne Hindernisse}
\centering
\begin{tabular}{c c c c c}
\hline\hline
Algorithmus & Agentenzahl & Blockierte Bewegungen & Abdeckung & Qualität \\ [0.5ex]
\hline
Zufällige Bewegung & 8 & 2,82\% & 73,78\% & 32,36\% \\
Einfache Heuristik & 8 & 2,79\% & 73,22\% & 32,10\% \\
Intelligente Heuristik & 8 & 0,64\% & 81,26\% & 35,91\% \\ [1ex]
\hline
Zufällige Bewegung & 12 & 4,32\% & 69,55\% & 44,75\% \\
Einfache Heuristik & 12 & 4,19\% & 68,88\% & 43,86\% \\
Intelligente Heuristik & 12 & 1,49\% & 77,60\% & 49,49\% \\ [1ex]
\hline
Zufällige Bewegung & 16 & 5,82\% & 64,28\% & 54,55\% \\
Einfache Heuristik & 16 & 5,66\% & 63,65\% & 53,99\% \\
Intelligente Heuristik & 16 & 2,85\% & 71,44\% & 60,73\% \\ [1ex]
\hline
\end{tabular}
\label{table:empty_total_random}
\end{table}
\subsection{Zielobjekt mit zufälligem Sprung (Säulenszenario)}
Für das Zielobjekt treffen hier dieselben Überlegungen, wie auch schon in Kapitel~\ref{zielobjekt_analyse_zufall_sprung:sec} erwähnt, zu. Auch ergeben sich im Säulenszenario (siehe Tabelle~\ref{table:pillar_total_random}) erwartungsgemäß ähnliche Werte wie im Fall des leeren Szenarios ohne Hindernisse (siehe Tabelle~\ref{table:empty_total_random}). Durch geringere Sicht und höhere Zahl an blockierten Bewegungen ergibt sich jeweils eine geringere Abdeckung und auch jeweils eine geringere Qualität. Auch hier ergeben sich keine Besonderheiten bezüglich der Agenten.\\
Um die Anzahl blockierter Bewegungen gering zu halten, sich überlappende Überwachungsreichweiten zu vermeiden und die Szenarien möglichst schwer zu halten (d.h. niedrige Qualität des Algorithmus mit zufälliger Bewegung) werden die Tests sich im Folgenden deshalb auf den Fall mit {\bf 8 Agenten} beschränken.\\
\begin{table}[ht]
\caption{Zufällige Sprünge des Zielobjekts in einem Säulenszenario}
\centering
\begin{tabular}{c c c c c}
\hline\hline
Algorithmus & Agentenzahl & Blockierte Bewegungen & Abdeckung & Qualität \\ [0.5ex]
\hline
Zufällige Bewegung & 8 & 4,45\% & 72,11\% & 32,13\% \\
Einfache Heuristik & 8 & 4,08\% & 71,70\% & 31,99\% \\
Intelligente Heuristik & 8 & 2,34\% & 79,61\% & 35,29\% \\ [1ex]
\hline
Zufällige Bewegung & 12 & 5,93\% & 67,72\% & 44,44\% \\
Einfache Heuristik & 12 & 5,67\% & 67,23\% & 43,81\% \\
Intelligente Heuristik & 12 & 3,62\% & 75,86\% & 49,34\% \\ [1ex]
\hline
Zufällige Bewegung & 16 & 7,62\% & 62,53\% & 54,26\% \\
Einfache Heuristik & 16 & 7,23\% & 62,00\% & 53,58\% \\
Intelligente Heuristik & 16 & 5,18\% & 69,91\% & 60,43\% \\ [1ex]
\hline
\end{tabular}
\label{table:pillar_total_random}
\end{table}
\subsection{Zielobjekt mit zufälligem Sprung (Zufällig verteilte Hindernisse)}
Auch hier gelten wieder dieselben Überlegungen für das Zielobjekt, die in Kapitel~\ref{zielobjekt_analyse_zufall_sprung:sec} gemacht wurden. Und auch für alle Einstellungen von \(\lambda_{h}\) und \(\lambda_{p}\) (siehe Kapitel~\ref{random_scenario_definition:sec}) stellt sich ebenfalls ein eindeutiges Bild dar (siehe Tabelle~\ref{table:full_total_random}). So liegt die intelligente Heuristik liegt wieder vorne, gefolgt wieder von der einfachen Heuristik und der zufälligen Bewegung. Im Fall mit vielen Hindernissen (\(\lambda_{h} = 0,2\)) liegt die einfache Heuristik trotz höherer Abdeckung hinter der zufälligen Bewegung. Dies ist wohl auf einen Zufall zurückzuführen, ändert man den \emph{random seed} Wert oder erhöht man die Anzahl der Experimente von 10 auf 30 ergibt sich wieder die oben genannte Reihenfolge.\\
\begin{table}[ht]
\caption{Zufällige Sprünge des Zielobjekts in einem Szenario mit Hindernissen}
\centering
\begin{tabular}{c c c c c c}
\hline\hline
Algorithmus & \(\lambda_{h}\) & \(\lambda_{p}\) & Blockierte Bewegungen & Abdeckung & Qualität \\ [0.5ex]
\hline
Zufällige Bewegung & 0,2 & 0,99 & 12,44\% & 62,50\% & 34,54\% \\
Einfache Heuristik & 0,2 & 0,99 & 10,04\% & 63,02\% & 34,48\% \\
Intelligente Heuristik & 0,2 & 0,99 & 12,71\% & 68,22\% & 37,89\% \\ [1ex]
\hline
Zufällige Bewegung & 0,1 & 0,99 & 7,58\% & 68,33\% & 32,81\% \\
Einfache Heuristik & 0,1 & 0,99 & 6,15\% & 68,49\% & 33,36\% \\
Intelligente Heuristik & 0,1 & 0,99 & 6,50\% & 74,81\% & 36,29\% \\ [1ex]
\hline
Zufällige Bewegung & 0,1 & 0,5 & 10,12\% & 66,01\% & 32,03\% \\
Einfache Heuristik & 0,1 & 0,5 & 8,57\% & 66,52\% & 32,38\% \\
Intelligente Heuristik & 0,1 & 0,5 & 9,29\% & 72,63\% & 35,12\% \\ [1ex]
\hline
\end{tabular}
\label{table:full_total_random}
\end{table}
Kommt das Zielobjekt in Sicht, so weist der Agent mit einfacher Heuristik eine geringere Zahl an blockierten Bewegungen als der Agent mit zufälliger Bewegung auf. Das kann man damit begründen, dass er davon ausgehen kann, dass sich in dieser Richtung wahrscheinlich kein Hindernis befindet, da die Sicht nicht blockiert ist. Im Gegensatz dazu beachtet der Agent mit zufälliger Bewegung Hindernisse überhaupt nicht, läuft erwartungsgemäß öfters gegen solche und bleibt deswegen wiederholt stehen. Wie die Ergebnisse zeigen ist der Unterschied zwischen beiden Agenten ist besonders hoch in Szenarien mit größerem Anteil an Hindernissen.\\
Im Vergleich zur einfachen Heuristik und im Gegensatz zum Säulenszenario scheint insbesondere die intelligente Heuristik Probleme mit den Hindernissen zu haben (viele blockierte Bewegungen). Da Hindernisse in der Heuristik nicht beachtet werden, bewirkt die Strategie der maximalen Ausbreitung der Agenten wahrscheinlich ein "`Drücken"' dieser Agenten gegen die Hindernisse, da sich von anderen Agenten wegbewegt wird anstatt zufällig zu laufen.\\
Schließlich ist zu sehen, dass die Agenten in einem Szenario mit höherem Verknüpfungsfaktor (der Fall mit \(\lambda_{h} = 0,1\) und \(\lambda_{p} = 0,99\) im Vergleich zum Fall mit \(\lambda_{h} = 0,1\) und \(\lambda_{p} = 0,5\)) besser abschneiden. Dies liegt daran, dass Szenarien mit hohem Verknüpfungsfaktor bedeuten, dass viele Hindernisse zusammenhängend einen großen Block bilden und somit dem Szenario ohne Hindernisse ähnlich sind, da es eher größere zusammenhängende Flächen gibt.\\
Insgesamt ist zu sagen, dass es diese Form der Bewegung des Zielobjekts genau die Eigenschaft der intelligenten Heuristik testet, sich auf dem Feld zu verbreiten. Abbildung~\ref{abdeckung_heuristic:fig} stellt dies nochmal grafisch dar, das Verhältnis zwischen Abdeckung und Qualität verhält sich in jedem der weiter oben betrachteten Szenarien (jeweils für den Fall mit 8 Agenten) gleich.\\
\begin{figure}[htbp]
\centerline{
\includegraphics{abdeckung_heuristic.eps}
}
\caption[Zusammenhang zwischen der Abdeckung und der Qualität eines Algorithmus]{Zusammenhang zwischen der Abdeckung und der Qualität eines Algorithmus, getestet in verschiedenen Szenarien}
\label{abdeckung_heuristic:fig}
\end{figure}
Da die Agenten mit einfacher Heuristik sich gegenüber den sich zufällig bewegenden Agenten nicht durchsetzen konnte, könnte der Test mit einem Zielobjekt mit zufälligem Sprung dazu dienen, diese Eigenschaften auch bei lernenden Agenten zu testen. Da das Zielobjekt dort jedoch häufig durch Sprung in die Sichtweite eines Agenten für diesen zufällige Ereignisse auslöst, ist zu erwarten, dass dadurch das Lernen stark gestört wird.\\
\subsection{Zielobjekt mit zufälliger Bewegung bzw. einfacher Richtungsänderung}\label{vergleich_zuf_einfach:sec}
Als einfachster Test eines sich bewegenden Agenten ist die zufällige Bewegung (siehe Kapitel~\ref{random_neighbor:sec}). Nun wird untersucht, ob dieser Art der Bewegung für die Tests sinnvoll ist oder ob eine andere Form der Bewegung für das Zielobjekt im Rahmen der Tests günstiger erscheint.\\
Am nächsten kommt der Bewegungstyp mit einfacher Richtungsänderung (siehe Kapitel~\ref{direction_change:sec}). Gemeinsam haben beide Bewegungstypen, dass der jetzige Ort des Zielobjekts maximal zwei Felder (die maximale Geschwindigkeit des Zielobjekts in den Tests) vom Ort der vorangegangenen Zeiteinheit entfernt ist. Im Gegensatz zum zuvor besprochenen zufälligen Sprung ist hier das lokale Einfangen eher von Relevanz. Der Ort, an dem sich das Zielobjekt im nächsten Schritt befinden wird, ist zumindest von der aktuellen Position abhängig, wenn das Zielobjekt auch schneller sein, kann als andere Agenten. Hingegen unterscheiden sie sich eindeutig im Bewegungsmuster des Zielobjekts. Dieses kehrt mit zufälliger Bewegung nach 2 Schritten mit Wahrscheinlichkeit von \(\frac{1}{4}\) auf das ursprüngliche Feld zurück.\\
Außerdem bezieht der Bewegungstyp mit einfacher Richtungsänderung Hindernisse in die Entscheidung über die nächste Aktion mit ein. Dies führt ebenfalls zu einer deutlich geringeren Anzahl von blockierten Bewegungen. Wie die Anzahl der Sprünge des Zielagenten in Tabellen~\ref{table:neighbor_change_random} und ~\ref{table:neighbor_change_pillar} zeigen, ist es den Agenten beim Zielobjekt mit zufälliger Bewegung deutlich öfters gelungen, ihn in seiner Bewegung zu blockieren. Wie auch an der Qualität abzulesen ergibt sich dadurch ein deutlich leichteres Szenario für beide Heuristiken, während es kaum Unterschiede in der Qualität bei der zufälligen Bewegung der Agenten ergibt.\\
Da die Differenz der Qualität zwischen der einfachen und intelligenten Heuristik beim {\bf Zielobjekt mit einfacher Richtungsänderung} größer, der Anteil der Sprünge des Zielobjekts kleiner, der Anteil der blockierten Bewegungen der Agenten kleiner und das Problem für den Algorithmus mit zufälliger Bewegung schwieriger ist, soll im Weiteren das Zielobjekt mit zufälliger Bewegung nicht mehr verwendet werden.\\
In den Tabellen bezieht sich der Eintrag "`Sprünge"' auf den Anteil vom Zielobjekt durchgeführter Sprünge, "`Blockiert"' auf den Anteil blockierter Bewegungen des Agenten und "`Zufällig bewegend"' bzw. "`Einfache Richtungsänderung"' auf das Zielobjekt.\\
\begin{table}[ht]
\caption{Vergleich von Zielobjekt mit zufälliger Bewegung und einfacher Richtungsänderung (zufälliges Szenario mit $\lambda_{h} = 0,1$, $\lambda_{p} = 0,99$)}
\centering
\begin{tabular}{c c c c c}
\hline\hline
Algorithmus & Sprünge & Blockiert & Abdeckung & Qualität \\ [1ex]
\hline
Zufällig bewegend\\ [1ex]
\hline
Zufällige Bewegung & 0,01\% & 7,49\% & 66,63\% & 33,96\% \\
Einfache Heuristik & 0,41\% & 11,51\% & 59,72\% & 79,99\% \\
Intelligente Heuristik & 0,36\% & 10,76\% & 65,87\% & 81,50\% \\ [1ex]
\hline
Einfache Richtungsänderung \\ [1ex]
\hline
Zufällige Bewegung & 0,00\% & 7,54\% & 68,31\% & 31,66\% \\
Einfache Heuristik & 0,06\% & 8,68\% & 62,31\% & 57,95\% \\
Intelligente Heuristik & 0,08\% & 8,57\% & 68,28\% & 61,72\% \\ [1ex]
\hline
\end{tabular}
\label{table:neighbor_change_random}
\end{table}
\begin{table}[ht]
\caption{Vergleich von Zielobjekt mit zufälliger Bewegung und einfacher Richtungsänderung (Säulenszenario)}
\centering
\begin{tabular}{c c c c c}
\hline\hline
Algorithmus & Sprünge & Blockiert & Abdeckung & Qualität \\ [1ex]
\hline
Zufällig bewegend\\ [1ex]
\hline
Zufällige Bewegung & 0,00\% & 4,34\% & 72,27\% & 31,80\% \\
Einfache Heuristik & 0,07\% & 8,77\% & 62,87\% & 78,34\% \\
Intelligente Heuristik & 0,04\% & 6,40\% & 69,98\% & 80,54\% \\ [1ex]
\hline
Einfache Richtungsänderung \\ [1ex]
\hline
Zufällige Bewegung & 0,00\% & 4,30\% & 72,28\% & 29,17\% \\
Einfache Heuristik & 0,01\% & 6,29\% & 65,80\% & 56,19\% \\
Intelligente Heuristik & 0,01\% & 4,58\% & 72,44\% & 60,41\% \\ [1ex]
\hline
\end{tabular}
\label{table:neighbor_change_pillar}
\end{table}
Vergleicht man die Ergebnisse für {\bf das Säulenzenario} aus Tabelle~\ref{table:neighbor_change_pillar} mit den Ergebnissen für das leere Szenario aus Tabelle~\ref{table:neighbor_change_no_obstacles} ergeben sich kaum Unterschiede. Das leere Szenario soll im Folgenden also nicht weiter für Tests herangezogen werden.\\
\begin{table}[ht]
\caption{Vergleich von Zielobjekt mit zufälliger Bewegung und einfacher Richtungsänderung (leeres Szenario ohne Hindernisse)}
\centering
\begin{tabular}{c c c c c}
\hline\hline
Algorithmus & Sprünge & Blockiert & Abdeckung & Qualität \\ [1ex]
\hline
Zufällig bewegend\\ [1ex]
\hline
Zufällige Bewegung & 0,00\% & 2,71\% & 73,85\% & 32,57\% \\
Einfache Heuristik & 0,06\% & 11,51\% & 63,65\% & 79,97\% \\
Intelligente Heuristik & 0,02\% & 4,71\% & 71,15\% & 81,59\% \\ [1ex]
\hline
Einfache Richtungsänderung \\ [1ex]
\hline
Zufällige Bewegung & 0,00\% & 2,75\% & 73,81\% & 30,99\% \\
Einfache Heuristik & 0,01\% & 4,98\% & 66,61\% & 58,38\% \\
Intelligente Heuristik & 0,01\% & 2,93\% & 73,37\% & 62,48\% \\ [1ex]
\hline
\end{tabular}
\label{table:neighbor_change_no_obstacles}
\end{table}
\section{Auswirkung der Geschwindigkeit des Zielobjekts}\label{zielgeschwindigkeiten_analyse:sec}
Lässt keine der beiden Parteien, Agenten und das Zielobjekt, Sensordaten über die jeweils andere Partei in die Entscheidung über die nächste Aktion mit einfließen, so spielt das Verhältnis der Geschwindigkeiten beider Parteien langfristig keine Rolle (sofern beide eine Geschwindigkeit größer 0 besitzen). Dies hat man im letzten Kapitel~\ref{vergleich_zuf_einfach:sec} daran gesehen, dass bei Agenten mit zufälliger Bewegung sich beim Vergleich zwischen beiden Bewegungstypen kaum Unterschiede in der Qualität auftreten, während dies bei der einfachen und intelligenten Heuristik der Fall war. Im Folgenden werden nun also die Fälle untersucht, bei denen mindestens einer der Parteien die andere Partei mit in die Überlegung miteinbezieht.\\
\subsection{Zielobjekt mit einfacher Richtungsänderung}\label{speed_single_direction:sec}
In Abbildung~\ref{speed_random_goal_heuristik:fig} sind die Testergebnisse für einen Test auf dem Säulenszenario dargestellt, bei dem sich das Zielobjekt mit einfacher Richtungsänderung bewegt. Es ist keine Korrelation zwischen der Geschwindigkeit und der Qualität des Algorithmus mit zufälliger Bewegung festzustellen, nur bei Geschwindigkeit \(0,0\) scheint es ein deutlich besseres Ergebnis zu geben. Das lässt sich aber durch die Anfangskonfiguration erklären, beim Säulenszenario startet das Zielobjekt in der Mitte mit maximalem Abstand zu den Hindernissen, ist also immer optimal in Sicht.\\
Da ein sich zufällig bewegender Agent nichts über die Umwelt wissen muss, stellt dessen erreichte Qualität also eine Untergrenze dar, ein Agent muss mehr als diesen Wert erreichen, damit man sagen kann, dass er etwas gelernt hat.\\
Bei den Testergebnissen für die einfache und die intelligente Heuristik sind dagegen folgende drei Punkte anzumerken:\\
\begin{itemize}
\item Es existiert eine Korrelation zwischen Qualität und Geschwindigkeit,
\item es gibt einen Knick bei Geschwindigkeit \(1,0\) und
\item es ist ein fast stetiger Anstieg der Differenz zwischen der einfachen und der intelligenten Heuristik zu verzeichnen.
\end{itemize}
Der Knick lässt sich dadurch erklären, dass es dem Zielobjekt oberhalb dieser Geschwindigkeit möglich ist, eventuelle Verfolger abzuschütteln. Der Anstieg der Differenz lässt sich dadurch erklären, dass die Abdeckung des Gebiets eine immer größere Rolle spielt, als die Verfolgung des Zielobjekts.\\
Da die Heuristiken das obere Limit angeben und so gebaut sind, dass sie sich immer für die jeweilige in ihren Augen beste Aktion entscheiden, wohingegen die auf XCS basierenden Varianten dies beispielsweise mit der Auswahlart \emph{tournament selection} mit $p = 0,84$ in bestenfalls 84\% der Fälle tun (siehe Kapitel~\ref{tournament_factor_test:sec}). Es ist deshalb anzunehmen, dass in Verbindung mit XCS auch niedrigere Geschwindigkeiten betrachtet werden können, ohne Agenten zu erhalten, die ausschließlich auf Verfolgung aus sind.\\
Im Szenario mit zufällig verteilten Hindernissen (siehe Abbildung~\ref{speed_random_goal_heuristik2:fig}) gelten obige Punkte nur eingeschränkt, insbesondere ist der Knick schwierig auszumachen.\\
\begin{figure}[htbp]
\centerline{
\includegraphics{speed_random_goal_heuristik.eps}
}
\caption[Auswirkung der Zielgeschwindigkeit (Zielobjekt mit einfacher Richtungsänderung, Säulenszenario) auf Agenten mit bestimmten Heuristiken]{Auswirkung der Zielgeschwindigkeit auf Agenten mit bestimmten Heuristiken (Zielobjekt mit einfacher Richtungsänderung, Säulenszenario)}
\label{speed_random_goal_heuristik:fig}
\end{figure}
\begin{figure}[htbp]
\centerline{
\includegraphics{speed_random_goal_heuristik2.eps}
}
\caption[Auswirkung der Zielgeschwindigkeit (Zielobjekt mit einfacher Richtungsänderung, Szenario mit zufällig verteilten Hindernissen) auf Agenten mit bestimmten Heuristiken]{Auswirkung der Zielgeschwindigkeit auf Agenten mit bestimmten Heuristiken (Zielobjekt mit einfacher Richtungsänderung, Szenario mit zufällig verteilten Hindernissen, $\lambda_{h}=0,2$, $\lambda_{p}=0,99$)}
\label{speed_random_goal_heuristik2:fig}
\end{figure}
\subsection{Zielobjekt mit intelligenter Bewegung}\label{zielagent_analyse_intelligent:sec}
In Abbildung~\ref{speed_intelligent_goal:fig} und Abbildung~\ref{speed_intelligent_goal_obst2:fig} werden im Säulenszenario bzw. Szenario mit zufällig verteilten Hindernissen wieder die Heuristiken bei unterschiedlichen Geschwindigkeiten des Zielobjekts verglichen. Beim Säulenszenario ist wieder der Knick wie beim Fall mit Zielobjekt mit einfacher Richtungsänderung (siehe Kapitel~\ref{speed_single_direction:sec}) zu beobachten.\\
Anzumerken ist hier, dass bei Agenten mit zufälliger Bewegung ein stetiger Abfall der Qualität zu verzeichnen ist, das Zielobjekt einem sich zufällig bewegenden Agenten also mit steigender Geschwindigkeit immer etwas besser ausweichen kann.\\
\begin{figure}[htbp]
\centerline{
\includegraphics{speed_intelligent_goal.eps}
}
\caption[Auswirkung der Zielgeschwindigkeit (intelligentes Zielobjekt, Säulenszenario) auf Agenten mit Heuristiken]{Auswirkung der Zielgeschwindigkeit (intelligentes Zielobjekt, Säulenszenario) auf Agenten mit Heuristik}
\label{speed_intelligent_goal:fig}
\end{figure}
\begin{figure}[htbp]
\centerline{
\includegraphics{speed_intelligent_goal_obst2.eps}
}
\caption[Auswirkung der Zielgeschwindigkeit (intelligentes Zielobjekt, Szenario mit zufällig verteilten Hindernissen, $\lambda_{h}=0,2$, $\lambda_{p}=0,99$) auf Agenten mit Heuristik]{Auswirkung der Zielgeschwindigkeit (intelligentes Zielobjekt, Szenario mit zufällig verteilten Hindernissen, $\lambda_{h}=0,2$, $\lambda_{p}=0,99$) auf Agenten mit Heuristik}
\label{speed_intelligent_goal_obst2:fig}
\end{figure}
Aufgrund der hohen Qualität bei niedrigen Geschwindigkeiten und aufgrund des höheren Bedarfs an Kollaboration, sollen in Tests in dieser Arbeit, soweit nicht anders angegeben, nur Zielobjekte mit einer {\bf Geschwindigkeit 2} getestet werden. Insbesondere vermeidet dies ein einfaches, stetiges Verfolgen des Zielobjekts.\\
\section{Heuristiken im schwierigen Szenario}\label{test_schwieriges_szenario:sec}
Für verschiedene Anzahl von Schritten sind für die drei Agententypen in Abbildung~\ref{steps_direction_difficult_heuristics:fig} die jeweiligen Qualitäten aufgeführt. Wie man beim Vergleich zwischen zufälliger Bewegung und einfacher Heuristik sehen kann, ist es nicht nur entscheidend, in den letzten Bereich am rechten Rand des Szenarios vorzudringen, sondern auch, dort den Agenten zu verfolgen und in diesem Bereich zu bleiben. Deutlich zeigen sich hier die Vorzüge der intelligenten Heuristik, durch das Bestreben, Agenten auszuweichen, hat es dieser Algorithmus leichter, durch die Öffnungen in von Agenten unbesetzte Bereiche vorzudringen.\\
Der Unterschied zwischen einfacher und intelligenter Heuristik zeigt auch, dass in diesem Szenario ein deutlich größeres Lernpotential, was die Einbeziehung von wahrgenommenen Agentenpositionen betrifft, für Agenten besteht. Wie später in Kapitel~\ref{xcs_difficult_scenario:sec} gezeigt wird, können in diesem Szenario unter anderem deshalb auf XCS basierte Agenten ihre Vorteile besonders gut ausspielen und erreichen sogar bessere Ergebnisse als die intelligente Heuristik sofern sie genug Zeit zum Lernen erhalten.\\
\begin{figure}[htbp]
\centerline{
\includegraphics{steps_direction_difficult_heuristics.eps}
}
\caption[Auswirkung der Anzahl der Schritte (schwieriges Szenario, ohne Richtungsänderung) auf Qualität von Agenten mit Heuristik]{Auswirkung der Anzahl der Schritte (schwieriges Szenario, ohne Richtungsänderung) auf Qualität von Agenten mit Heuristik}
\label{steps_direction_difficult_heuristics:fig}
\end{figure}
\section{Zusammenfassung der Tests mit Heuristiken}
Folgende Ergebnisse konnten in diesem Kapitel gewonnen werden:
\begin{itemize}
\item Um die Anzahl blockierter Bewegungen gering zu halten, sich überlappende Überwachungsreichweiten zu vermeiden und die Szenarien möglichst schwer zu halten wird sich im Folgenden auf den Fall mit 8 Agenten beschränkt.\\
\item Kapitel~\ref{vergleich_zuf_einfach:sec} hat gezeigt, dass die einfachste Implementierung eines Zielobjekts, das Zielobjekt mit zufälliger Bewegung, eher nicht für Tests benutzt werden sollte. Die Einfachheit des Algorithmus rechtfertigt nicht die höhere Zahl der Sprünge und blockierten Bewegungen. In weiteren Tests werden deswegen immer nur Zielobjekte mit einfacher Richtungsänderung getestet.\\
\item Bei der Analyse der Geschwindigkeit des Zielobjekts in Kapitel~\ref{zielgeschwindigkeiten_analyse:sec} ergab sich bei einer Geschwindigkeit von 1 ein Knick, ab dem kollaboratives Verhalten gegenüber sturem Verfolgen an Bedeutung gewann. Für weitere Tests wird deshalb eine Geschwindigkeit von 2 verwendet.\\
\item Beim Test des schwierigen Szenarien in Kapitel~\ref{test_schwieriges_szenario:sec} wurde zum einen festgestellt, dass ein einfaches Verfolgen des Zielobjekts nicht zum Ziel führen kann. Agenten mit intelligenter Heuristik konnten trotzdem Erfolge zeigen, da sie sich gegenseitig auf frei Felder durch die Öffnungen hindurch drängen.\\
\item Der Vergleich von Agenten intelligenten Heuristik mit Agenten mit zufälliger Bewegung Aufschluss darüber geben, wieviel und welche Aspekte ein Agent in einem solchen Szenario überhaupt lernen kann. Große Unterschiede zwischen intelligenter und einfacher Heuristik weisen beispielsweise darauf hin, dass die Verteilung auf dem Torus wichtiger ist, als das Hinterherlaufen. Dies sieht man insbesondere am Extrembeispiel des Zielobjekts mit zufälligem Sprung in Kapitel~\ref{zielobjekt_analyse_zufall_sprung:sec}.\\
\end{itemize}