variante_com.tex

\section{DSXCS Variante mit Kommunikation}\label{communication:cha}

Wann immer ein \emph{base reward} Wert an einen Agenten verteilt wird, kann es sinnvoll sein, diesen Wert an andere Agenten weiterzugeben. Dies wurde z.B. in einem ähnlichen Szenario in~\cite{1102281} festgestellt, bei dem zwei auf XCS basierende Agenten gegen bis zu zwei anderen (zufälligen) Agenten eine vereinfachte Form des Fußballs spielen. Dabei erhielt bei Erreichen des Ziels (Beförderung des Balls aus dem Spielfeld) der Agent, der den Ball zuletzt berührt hat, den vollen \emph{reward} Wert und der andere Agent \(90\%\) dieses Werts.\\

Hier werden nun zwei Formen der Weitergabe des \emph{reward} Werts vorgestellt, zum einen die Kommunikationsvariante in der alle Agenten ihre \emph{reward} Werte teilen (siehe Kapitel~\ref{einfache_gruppe_kommunikation:sec}) und zum anderen eine Kommunikationsvariante bei der der \emph{reward} Wert anhand ähnlicher in den \emph{classifier sets} gespeicherter Verhaltensweisen verteilt wird (siehe Kapitel~\ref{egoistic_relation:sec}. Zuvor wird auf die Kommunikationsrestriktionen in Kapitel~\ref{com_reichweite:sec} und die Behandlung externer Ereignisse in Kapitel~\ref{externe_ereignisse:sec} eingegangen.\\

Wie später ausführlich in Kapitel~\ref{bewertung_komm:sec} dargestellt wird, blieb dieser Ansatz erfolgreich. Über mögliche Gründe wird dort diskutiert.\\


\subsection{Kommunikationsreichweite}\label{com_reichweite:sec}

Geht man davon aus, dass die Kommunikationsreichweite zumindest ausreichend groß ist um nahe Agenten zu kontaktieren, so kann man argumentieren, dass man dadurch ein Kommunikationsnetzwerk aufbauen kann, in dem jeder Agent jeden anderen Agenten - mit einer gewissen Zeitverzögerung - erreichen kann. Bei ausreichender Agentenzahl relativ zur freien Fläche fallen dadurch wahrscheinlich nur vereinzelte Agenten aus dem Netz, abhängig vom Szenario. Stehen die Agenten nicht indirekt andauernd miteinander in Kontakt (mit anderen Agenten als Proxy), sondern muss die Information zum Teil durch aktive Bewegungen der Agenten transportiert werden, tritt eine Zeitverzögerung auf. Auch kann die benötigte Bandbreite die verfügbare übersteigen, was ebenfalls zusätzliche Zeit benötigen kann. Der Einfachheit halber wird deshalb angenommen, dass zwar globale Kommunikation zur Verfügung steht, jedoch diese u.U. zeitverzögert stattfindet und wir nur geringe Mengen an Information weitergeben können. In diesem Falle soll ein Agent in jedem Schritt maximal lediglich einen Aktualisierungsfaktor (siehe Kapitel~\ref{aktualisierungsfaktor:sec}) und einen \emph{reward} Wert an alle anderen Agenten weitergeben können. Da dieser Algorithmus auf dem DSXCS Algorithmus aufbaut, sollen hier auch Ereignisse auftreten können und immer eine ganze Reihe von \emph{action set} Listen bewertet werden. Somit muss außerdem noch ein Start- und Endzeitpunkt übermittelt werden. Dies wäre beispielsweise bei einem neutralen Ereignis \(\frac{maxStackSize}{2}\) und \emph{maxStackSize} oder bei einem positiven Ereignis mit 5 Schritten seit dem letzten Ereignis 0 als Startzeitpunkt und 4 als Endzeitpunkt.\\


\subsection{Externe Ereignisse}\label{externe_ereignisse:sec}

Jeder ermittelte \emph{reward} Wert kann an alle anderen Agenten weitergegeben werden. Wie ein solches sogenanntes "`externes Ereignis"' dann von diesen Agenten aufgefasst wird, hängt von der jeweiligen Kommunikationsvariante ab. Diese werden in den folgenden Kapitel besprochen.\\

Durch eine gemeinsame Schnittstelle erhält jeder Agent den \emph{reward} Wert zusammen mit dem Aktualisierungsfaktor. Dabei ergibt sich das Problem, dass sich \emph{reward} überschneiden können, da jeder \emph{reward} Wert sich rückwirkend auf die vergangenen \emph{action set} Listen auswirken kann. Auch können mehrere externe \emph{reward} Werte eintreffen, als auch ein eigener positiver lokaler \emph{reward} Wert aufgetreten sein. Würden die \emph{reward} Werte nach ihrer Eingangsreihenfolge abgearbeitet werden, kann es passieren, dass dieselbe \emph{action set} Liste sowohl mit einem hohen als auch einem niedrigen \emph{reward} Wert aktualisiert wird. Da das globale Ziel ist, das Zielobjekt durch \emph{irgendeinen} Agenten zu überwachen, ist es in jedem einzelnen Zeitschritt nur relevant, dass ein \emph{einzelner} Agent einen hohen \emph{reward} Wert produziert bzw. weitergibt um die eigene Aktion als zielführend zu bewerten. Dies wird für die Entwicklung der Funktion, die für die Verarbeitung in Kapitel~\ref{zeitgleiche_ereignisse:sec} verantwortlich ist, maßgeblich sein.\\

Befindet sich das Ziel beispielsweise gerade in Überwachungsreichweite mehrerer Agenten und verliert ein anderer Agent das Ziel aus der Sicht, sollte der Agent (und alle anderen Agenten), der das Ziel in Sicht hat, deswegen nicht bestraft werden, da das globale Ziel ja weiterhin erfüllt wurde. Ein gespeicherter höherer \emph{reward} Wert soll also einen gespeicherten niedrigeren \emph{reward} Wert verdrängen.\\


\subsection{Einzelne Kommunikationsgruppe}\label{einfache_gruppe_kommunikation:sec}

Mit dieser Variante wird der Aktualisierungsfaktor fest auf \(1,0\) gesetzt und es werden alle \emph{reward} Werte in gleicher Weise weitergegeben. Dadurch wird zwischen den Agenten nicht diskriminiert, was letztlich bedeutet, dass zwar zum einen diejenigen Agenten korrekt mit einem externen \emph{reward} Wert belohnt werden, die sich zielführend verhalten, aber zum anderen eben auch diejenigen, die es nicht tun. Deren \emph{classifier} werden somit zu einem gewissen Grad zufällig bewertet, denn es fehlt die Verbindung zwischen \emph{classifier}, Handlung und der Bewertung. Idee der Variante ist, dass durch die Zusammenschaltung der \emph{reward} Werte eine Art großes gemeinsames Sensorsystem entsteht.\\


\subsection{Egoistische Kommunikationsgruppe}\label{egoistic_relation:sec}

Die Idee für diese Art der Gruppenbildung ist, dass unterschiedliche Agenten unterschiedlich stark am Erfolg der anderen Agenten beteiligt sind. Ohne Kommunikation wird jeder Agent versuchen, selbst das Zielobjekt möglichst in die eigene Überwachungsreichweite zu bekommen, anstatt die Arbeit mit anderen Agenten zu teilen, also z.B. das Gebiet des Torus möglichst großräumig abzudecken, wie es der in Kapitel~\ref{intelligent_heuristik:sec} vorgestellte Agent mit intelligenter Heuristik in mehreren Tests u.a. in Kapitel~\ref{zielagent_analyse_intelligent:sec} demonstriert hat.\\

Diese Variante berechnet erst einmal für jeden Agenten einen "`Egoismusfaktor"', indem grob die Wahrscheinlichkeit ermittelt wird, dass ein Agent, wenn sich ein anderer Agent in Sicht befindet, sich in diese Richtung bewegt. "`\emph{Egoismus}"'-Faktor, weil ein großer Faktor bedeutet, dass der Agent eher einen kleinen Abstand zu anderen Agenten bevorzugt, also wahrscheinlich eher auf eigene Faust versuchen wird, das Zielobjekt in Sicht zu bekommen, anstatt ein möglichst großes Gebiet abzudecken.\\

Auf Basis dieses Faktors kann man dann eine Ähnlichkeit zwischen verschiedenen Agenten hinsichtlich des Verhaltens gegenüber anderen Agenten und damit den Aktualisierungsfaktor bestimmen. Die Hypothese hier ist, dass Agenten mit ähnlichem Egoismusfaktor auch eine ähnliche \emph{classifier set} Liste besitzen. Besitzen mehrere Agenten eine ähnliche Liste, so bilden sie eine mehr oder weniger homogene Gruppe, die sich gegenseitig \emph{reward} Werte mit hohem Aktualisierungsfaktor senden, während Agenten mit anderem Egoismusfaktor leer ausgehen.\\

Der Vorteil gegenüber Verfahren, die die \emph{classifier set} Listen direkt vergleichen, liegt darin, dass der Kommunikationsaufwand hier nur minimal ist. Neben dem \emph{reward} Wert muss lediglich der Egoismusfaktor übertragen und pro Zeitschritt nur einmal berechnet werden.\\

\begin{figure}[htbp]
\centerline{	
\includegraphics{corrected_reward.eps}
}
\caption[Beispielhafte Kombinierung interner und externer \emph{reward} Werte]{Beispielhafte Darstellung der Kombinierung interner und externer \emph{reward} Werte}
\label{corrected_reward:fig}
\end{figure}

Die Berechnung des Faktors ist in Programm~\ref{egoistic_relationship:pro} dargestellt. Bei der Berechnung des Aktualisierungsfaktors bietet es sich (wie oben beschrieben) nun an, entweder den eigenen Egoismusfaktor direkt zu verwenden, oder die Differenz des eigenen Egoismusfaktors mit des Faktors des Agenten, der das externe Ereignis ausgelöst hat. In beiden Fällen wird der Wert von \(1,0\) abgezogen. Der Egoismusfaktor selbst bestimmen sich aus dem (mit jeweils dem Produkt aus den jeweiligen \emph{fitness} und \emph{reward predicton} Werten gewichtet) Anteil aller \emph{classifier}, die sich auf andere Agenten zu bewegen, sofern sie in Sicht sind. Somit ist der daraus berechnete Aktualisierungsfaktor umso größer, je ähnlicher die Agenten in ihrem Abstandsverhalten gegenüber anderen Agenten sind bzw. je eher der Agent anderen Agenten ausweicht.\\