sota.tex

\chapter{Erkenntnisse zur Platzierung robotischer Systeme} \label{ch:sota}
Den Anforderungen aus \autoref{sec:anforderungen} ist zu entnehmen, dass die Platzierung robotischer Systeme innerhalb einer Domäne ein fundamentaler Bestandteil zur automatischen Schaffung kollaborative Multi-Roboter Arbeitsräume ist. Die Einhaltung der physikalischen Beschränkungen bezüglich genutzter Roboter ist hierbei unerlässlich, um hinsichtlich ihrer Aufgabe und Position ein zufriedenstellendes Ergebnis zu erzielen. Einen Ansatz zur Erfassung dieser robotischer Grenzen konkretisieren Zacharias et al. \cite{Zacharias2007} und kombiniert diesen in einer späteren Publikationen \cite{Zacharias2009} mit zusätzlichen Aspekten der Kinematik, um einen Algorithmus zu formulieren, welcher sukzessiv die Position eines Roboters hinsichtlich seiner Grenzen bestimmt. Dieses Verfahren ist in die Komponenten  
\emph{Arbeitsraumanalyse}, \emph{Arbeitsrauminvertierung} und \emph{Positionsanalyse} unterteilt, welche somit die Gliederung dieses Kapitels definieren, dessen Inhalt die Auseinandersetzung mit deren Methodiken ist. Die daraus gewonnenen Erkenntnisse werden in der konzeptuellen Ausarbeitung und Implementierung genutzt. \autoref{fig:4} zeigt die Reihenfolge der Komponenten im Algorithmus.

\begin{figure}[h!]
\centering
	\begin{tikzpicture} [start chain,node distance=1.6cm, auto, >=stealth']
		\node[rounded corners, draw=black,  thick, minimum height=3em, align=center, on chain] (RM) {Arbeitsraumanalyse};
		\node[rounded corners, draw=black,  thick, minimum height=3em, align=center, on chain, join=by {->}, right = of RM] (IRM) {Arbeitsrauminversion};
		\node[rounded corners, draw=black,  thick, minimum height=3em, align=center, on chain, join=by {->}, right = of IRM] (Base) {Positionsanalyse};
	\end{tikzpicture}
	\caption{Darstellung des Algorithmus zur sukzessiven Ermittlung einer Roboterposition. Die Kommunikation zwischen den Etappen erfolgt mittels Persistenz der Teilergebnisse.
} \label{fig:4}
\end{figure}

\section{Arbeitsraumanalyse}
Vahrenkamp et al. \cite{Vahrenkamp2013} beschreiben in ihrer Publikation die Analyse des Arbeitsraums eines robotischen Systems als Ausgangspunkt zur Berechnung dessen optimaler Positionierung hinsichtlich einer zuvor definierten Aufgabe. Dazu dokumentieren Zacharias et al. in ihrer wissenschaftlichen Arbeit einen Ansatz, dessen Inhalt es ist, durch wiederholtes Anwenden kinematischer Algorithmen das unmittelbare Umfeld des Roboters zu erfassen und dieses Anhand einer Metrik zu charakterisieren. \autoref{eq:7} definiert diese Berechnungen diskret durch die Funktion $f_{kin}$. 

\begin{equation}\label{eq:7}
	\begin{split}
	f_{kin}&: T \to \{0 , 1\} \\
	f_{kin}(^{0}T_{Endeff})&= 
	\begin{cases*}
      1 & gdw. die Pose erreichbar ist \\
      0 & sonst
   \end{cases*}
	\end{split}
\end{equation}

Den Berechnungen liegt eine feste Menge generierter Endeffektor-Posen $T \subset SE(3)$ in Form der Transformationen $^{0}T_{Endeff}  \in T$ relativ zum $Frame_{0}$ zugrunde und ihr Resultat ist bezogen auf die Terminierung ein Wahrheitswert. Alle Transformation zuzüglich der Information über dessen Erreichbarkeit bilden die \emph{reachability map (RM)}, welche in \autoref{eq:8} notiert ist. 



\begin{equation}\label{eq:8}
RM:= \{(t , f_{kin}(t)) | t \in T \}
\end{equation}

\begin{figure}[h!]
\ffigbox[\FBwidth]%
  {\begin{subfloatrow}%
    \ffigbox[\FBwidth]%
      {\fbox{\includegraphics[width=0.47\textwidth, height = 5.5cm]{images/P_total.png}}}%
      {\caption{Menge aller Positionen $\protect P_{total}$}\label{fig:PT}}%
    \ffigbox[\FBwidth]%
      {\fbox{\includegraphics[width=0.47\textwidth, height =5.5cm]{images/OR_total.png}}}%
      {\caption{Menge aller Orientierungen $\protect OR_{total}$} \label{fig:OR}}
  \end{subfloatrow}}%
  {\caption{ Darstellung der Mengen $\protect P_{total}$ und $\protect OR_{total}$. Ein roter Marker repräsentiert den Vektoren, den der Endeffektor einnimmt. Ein grüner Pfeil zeigt in die Richtung des Endeffektors.}
\label{fig:5}}%
\end{figure}


\autoref{eq:10} zeigt, dass ein Paar aus einem Vektor $^{0}v \in \R^{3}$ und einer Rotation $^{0}R \in SO(3)$ die Transformation $^{0}T_{Endeff}$ als Pose des Endeffektors bildet. Daraus ist abzuleiten, dass die Zusammenstellung einer Menge $P_{total}$ aus $^{0}v$ und die Generierung dessen zugehöriger Rotationen $^{0}R$, welche die Menge aller Orientierungen $OR_{total}$ definiert, abstrahiert erfolgt. \autoref{eq:9} beschreibt $T$ als das Kreuzprodukt dieser Mengen.

\begin{equation}
\label{eq:10}
^{0}T_{Endeff}:= \{(v,R) | v \in P_{total},  R \in OR_{total} \} \in T
\end{equation}

\begin{equation}
\label{eq:9}
T:= \{ P_{total} \times OR_{total} \} 
\end{equation}

\subsection{Menge aller Positionen}
Dieser Abschnitt umfasst Methodiken zur Population der Menge $^{0}P_{total}$. Die Wahl der Vektoren $^{0}v \in ^{0}P_{total}$ erfordert das Bestimmen eines Intervalls $[-q,q] : q \in \R_{+}$ für jede Dimension anlog zu den in \autoref{fig:panda} gezeigten Perspektiven, welche den tatsächlichen Arbeitsraum des robotischen Systems überschätzt. Anschließend erfolgt ein Algorithmus zur Generierung der Elemente $^{0}x, ^{0}y, ^{0}z  \in [-q,q]$, die den Vektor $^{0}v$ definieren. Dieser Sachverhalt ist in \autoref{eq:11} vereinfacht dargestellt.

\begin{equation}
\label{eq:11}
P_{total}:= \{(x, y, z)^{T} | q \in \R_{+}; x, y ,z \in [-q,q] \}
\end{equation}

\subsubsection{Positionen durch Zufallsverfahren}
Dieses Verfahren bestimmt die Verteilung der Vektoren $^{0}v$, welche keiner räumlichen Abhängigkeit, mit Ausnahme der festen Intervalle $[-q,q]$, unterliegen. Die Komponenten eines Vektors werden demzufolge durch Zufallsverfahren generiert. Die Initialisierung erfolgt durch Angabe der $n \in \N_{>0}$ zu generierenden Vektoren, wodurch die Kardinalität von $^{0}P_{total}$ durch die Zahl $n$ bestimmt ist. 

\begin{equation}
\label{eq:kadi}
\vert ^{0}P_{total} \vert = n
\end{equation}

\subsubsection{Positionen durch kubische Diskretisierung} 
Die kubische Diskretisierung des Arbeitsraums robotischer Systeme stellt ein Verfahren zur Bestimmung der Vektoren $^{0}v$ dar, welche durch Angabe einer festen Auflösung $ a \in \R_{+}$ pro Dimension das Umfeld des Roboters in ein reguläres Gitter der Grenzen $[-q,q]$ unterteilt. Dem \autoref{sec:diskretisierung} ist zu entnehmen, dass die resultierende Menge $^{0}P_{total}$ durch die gleichmäßige Verteilung der Vektoren $^{0}v$ im Abstand $a$ innerhalb des Intervalls $[-q,q]$ einen Würfel approximiert, welcher in \autoref{fig:PT} anhand roter Marker illustriert ist. Wie \autoref{eq:12} vereinfacht zeigt, ist die Kardinalität der Menge $^{0}P_{total}$ implizit durch das Intervall $[-q,q]$ und der Auflösung $a$ gegeben.

\begin{equation}
\label{eq:12}
\vert ^{0}P_{total} \vert = (\frac{2 \times q}{a})^{3}
\end{equation}

\subsection{Menge aller Orientierungen}
\label{sec:ORS}
Die Menge $^{0}OR_{total}$ beschreibt alle möglichen Orientierungen, die für jeden Vektor generiert werden. Ein grundlegendes Verfahren hierzu ist die sphärische Diskretisierung, welche die Approximation einer Sphäre durch Vektoren $^{0}s \in \R^{3}$ um ein Zentrum $^{0}p \in \R^{3}$ mit festem Abstand $r \in \R_{+}$, beschreibt und in \autoref{fig:OR} durch den Ursprung eines Grünen Pfeils angedeutet ist. Ziel dieses Prozesses ist die Entwicklung aller Orientierungen für einen Vektor $^{0}p$ aus den sphärischen Polarkoordinaten , die $^{0}s \in S^{2}$ auf der erzeugten Sphäre definieren. Die Menge $S^{2}$ aller Vektoren auf einer Sphäre ist in \autoref{eq:13} formuliert. Hierzu beschreiben Azimut $\theta \in [ \, 0,2 \pi \,)$ und Colatitude $\phi \in [ \, 0,\pi \,]$ den Winkel auf der XY Ebene des kartesischen Koordinatensystems bzw. den Winkel zwischen Z Achse und der Strecke zwischen Zentrum und Koordinate $\overline{sp}$ \footnote{\url{https://mathworld.wolfram.com/SphericalCoordinates.html}}. \autoref{fig:6} veranschaulicht die genannten Winkel der sphärischen Polarkoordinaten im kartesischen Koordinatensystem als Referenz farblich. Bezogen auf die Orientierung eines Körpers, können die Polarwinkel als Gier und Nick Winkel eines Objektes interpretiert werden, welche die \autoref{fig:1} illustriert. Der zusätzlichen Roll Winkel $Roll \in [ \, 0,2 \pi \,)$ komplettiert die Rotation des Endeffektors und somit die Menge $OR_{total}$. Die Kardinalität der Menge $^{0}OR_{total}$ ist durch die Menge aller sphärischen Vektoren $^{0}s \in S^{2}$ und zusätzlicher Betrachtung der $Roll$ Winkel bestimmt, was der \autoref{eq:14} zu entnehmen ist.

\begin{figure}[h!]
\centering
	\begin{tikzpicture}
		\def\r{3}
		\node[circle, fill, inner sep=1 , label=left:${p}$]	at (0,0)	(origin)	{};
		\node[inner sep=0.7, label=left:${ps}$] at (\r/3,\r/2)	(s)	{};
		\node[]	at (-\r/5, -\r/3)	(x)	{x};
		\node[]	at (\r, 0) (y)	{y};
		\node[]	at (0, \r)	(z)	{z};
	
	
		\draw [-stealth]	(origin) -- (s);
		\draw [-stealth]	(origin) -- (x);
		\draw [-stealth]	(origin) -- (y);
		\draw [-stealth]	(origin) -- (z);
	
		\draw[dashed] (origin) -- (\r/3, -\r/5) node (phi) {} -- (s);
	
		\draw (origin) circle (\r-0.2);
		\draw[dashed] (origin) ellipse (\r-0.2 and 2.8/3);
	
		% Angles
		\pic [draw = blue,fill=blue!50,fill opacity=.5, text=orange] {angle = x--origin--phi};
		\pic [draw = orange,fill=orange!50,fill opacity=.5, text=orange] {angle = s--origin--z};
	\end{tikzpicture}
	\caption{Visualisierung der Winkel Azimut (blau) $\protect \theta$ und Colatitude (orange) $\protect \phi$, dabei ist $\protect \overline{sp}$ die Strecke zwischen Zentrum p und einer Koordinate $\protect s \in S^{2}$ auf der Sphäre.}\label{fig:6}
\end{figure}

\begin{equation}
\label{eq:13}
S^{2} := \{s \in \R^{3} | \vert \overline{sp} \vert = r\} 
\end{equation}

\begin{equation}
\label{eq:14}
\vert ^{0}OR_{total} \vert = \vert S^{2} \vert \times \vert Roll \vert
\end{equation}

\subsubsection{Orientierungen durch Zufallsverfahren}
Sphärische Diskretisierungen, deren Verteilung bezüglich dessen Vektoren $s$ keinem Schema folgen oder an räumliche Parameter gebunden sind, verteilen diese nach Pseudozufallsverfahren. Die Anzahl der zu verteilenden Vektoren ist durch eine Zahl $n \in \N$ gekennzeichnet und stellt die Initialisierung des Verfahrens da. Die Kardinalität von $S^{2}$ lässt sich daher analog zur \autoref{eq:kadi} eindeutig bestimmen.


\subsubsection{ungleichmäßige sphärische Diskretisierung}
Das Abtasten der Winkelintervalle von $\theta$ und $\phi$ hinsichtlich fester Auflösungen $p, q \in \R_{+}$ generiert ein sphärisches Gitter, indem die sphärischen Vektoren $^{0}s$ nicht äquidistant und demzufolge ungleichmäßig verteilt sind. Die Kardinalität von $ S^{2}$ dieses Verfahrens ist anhand der gewählten Auflösungen $p, q$ und der Winkelintervalle nach \autoref{eq:16} berechenbar.

\begin{equation}
\label{eq:16}
\vert S^{2} \vert = \frac{2 \times \pi}{p} \times \frac{\pi}{q}
\end{equation}

\subsubsection{gleichmäßige sphärische Diskretisierung}
Die äquidistante Verteilung einer festen Zahl $n \in \N$ Vektoren auf einer Sphäre ist ein mathematisches Problem, dessen Lösung eine umfassende Bedeutung für Forschungsfelder der Biologie, Chemie und Physik aufweist. Beispielsweise basieren das Tammes Problem oder hard-spheres Problem auf dieser Problemstellung, bezogen auf der Modellierung fluider Partikel \cite{Saff1997}. Algorithmen zu diesem Kontext approximieren dieses Ziel, wobei die Distanzen auf der Sphäre  minimalen Abweichungen unterliegen und in Spezialfällen die Anforderung einer äquidistanten Verteilung erfüllen. Die Kardinalität $\vert S^{2} \vert$ ist analog zu \autoref{eq:kadi} durch $n$ gegeben.

\subsection{Arbeitsraumcharakterisierung}
\autoref{eq:18} formuliert die Erreichbarkeitsmetrik $D_{Reach}$ zur Bewertung der Erreichbarkeit eines Vektors $^{0}v_{Endeff}$ durch den Endeffektor. Hierzu erfolgt eine Gegenüberstellung der Menge $OR_{v}$ aller Orientierungen $R$, die der Endeffektor für den Vektor $^{0}v_{Endeff}$ während der Berechnungen erfolgreich einnehmen kann, gegenüber der Menge $OR_{total}$ aller generierten und bearbeiteten Orientierungen für $^{0}v_{Endeff}$ \cite{Porges2015}. Demnach impliziert ein geringer Wert $D_{Reach}$ für einen Vektor, dass dieser vom Koordinatenursprung des Frames $Frame_{0}$ weniger erreichbar ist als ein Vektor mit höherer Bewertung.  

\begin{equation}
\label{eq:17}
OR_{v} := \{R | ((v, R),f _{kin}) \in RM  \land f_{kin}((v, R)) = 1 \} \subset  OR_{total}
\end{equation}

\begin{equation}
\label{eq:18}
\begin{split}
D_{Reach}:P_{total} & \to [0,1] \\
D_{Reach}(v) &= \frac{\vert OR_{v} \vert}{\vert OR_{total} \vert}
\end{split}
\end{equation}

\section{Arbeitsrauminversion}
Der invertierte Arbeitsraum beschreibt nach Vahrenkamp et al. alle Posen relativ zum Endeffektor, sphärisch um den Ursprung des $Frame_{0}$ verteilt, von denen aus das robotische System den Ursprung Frames erreicht \cite{Vahrenkamp2013}. Dazu beschreibt dieser Prozess die Invertierung aller persistierten Transformationen $^{0}T_{Endeff}$ der $reachability map$ und Portierung der zugehörigen Metrik $D_{Reach}(^{0}v_{Endeff})$. Die resultierende Menge enthält nach \autoref{eq:5} Transformationen der Form $^{Endeff}T_{0}$, welche dessen Basispose beschreiben. Diese Informationen werden als \emph{inverse reachability map (IRM)} persistiert, welche durch die \autoref{eq:19} definiert ist. 

\begin{equation}
\label{eq:19}
IRM := \{((v,R)^{-1}, D_{Reach}(v)) | ((v,R),d) \in RM \}
\end{equation}

\section{Positionsanalyse}
\label{sec:positioning}
Dieser Abschnitt dokumentiert die Analyse aller potentiellen Basispositionen $P_{Base}$ eines robotischen Systems, welche sich nach \autoref{eq:20} aus der Matrix Multiplikation mit dem invertierten Arbeitsraum IRM und Posen spezifischer Aufgaben $^{0}t \in A$ ergeben. Die Metrik wird dabei nach der Kalkulation auf $P_{Base}$ abgebildet und beschreibt die Zuverlässigkeit dieser Posen \cite{Makhal2018}. Komplexe Aufgaben mit der Anzahl $n \in \N : n > 2$ Posen $^{0}t$, welche der Roboter operieren muss, skalieren die Menge aller Basen $P_{Base}$ um $n$. Dem \autoref{sec:partitionierung} ist das Verfahren der Voxelisierung zu entnehmen, welches diese enormen Datenmenge räumlich in separate Volumen teilt. Das Resultat dieser Abtastung ist eine Menge aus $k \in \N$ disjunkten Voxeln $V$, dessen Zentren jeweils um eine Auflösung $u \in \R_{+}$ distanziert sind und den Zeigern auf alle Basispositionen, die sich räumlich innerhalb eines Voxels befinden. Demnach erfolgt eine Spaltung der Basispositionen $P_{Base}$ in disjunkte Teilmenge $TP_{0} ...TP_{k-1}\subset P_{Base}$, die abstrahiert voneinander betrachtet werden können. Da jeder Vektor $^{0}p_{Base} \in P_{Base}$ auf seine Bewertung zeigt, ist der Wert eines Voxels implizit durch die disjunkte Teilmenge gegeben, in die Menge der Basispositionen $P_{Base}$ teilt. Gleichermaßen reduziert diese Darstellung das Lösungsspektrum von der aufgabenabhängigen Kardinalität von $P_{Base}$ auf die Anzahl aller Voxel $k$.

 
\begin{equation}
\label{eq:20}
\begin{split}
P_{Base} &:= \{(t \times T, d) | (T, d) \in IRM , t \subset A \} \\
\vert P_{Base} \vert &= \vert A \vert \times \vert IRM \vert 
\end{split}
\end{equation}

\subsection{Charakterisierung eines Voxels}
Makhal et al. \cite{Makhal2018} beschreibt einen Algorithmus, welcher alle $k$ Voxel charakterisiert und anhand deren Vektoren $^{0}p_{Base} \in TP$ bestimmt, welches Voxel sich bevorzugt für die Platzierung des robotischen Systems eignet. Dies erfolgt durch eine weitere Metrik $D_{voxel}$ in \autoref{eq:22}, die sich aus dem arithmetischen Mittel  $D_{Reach}^{mittel}$ eines Voxels und dem Verhältnis von dessen Kardinalität zum maximalen Voxel $TP_{max}$ ergibt. $TP_{max}$ ist das Resultat einer Iteration über alle $k$ Voxel, welche im Anschluss an die Voxelisierung erfolgt. Demnach lässt ein Voxel mit hoher Kardinalität darauf schließen, dass Posen verschiedener Aufgaben von ihm erreichbar sind.

\begin{equation}
\label{eq:22}
\begin{split}
D_{voxel}:V & \to [0,1] \\
D_{voxel}(TP) &= D_{voxel}^{mittel}(TP) \times \frac{\vert TP \vert}{\vert TP_{max} \vert}
\end{split}
\end{equation}


Die Metrik $D_{voxel}$ bewertet demnach ein Voxel anhand dessen Inhalts und Kardinalität, wobei ein Voxel mir maximaler Bewertung eine valide Position des robotischen Systems für alle $n = \vert A \vert$ Posen der Aufgabe darstellt.

\begin{equation}
\begin{split}
\label{eq:21}
D_{voxel}^{mittel}:V & \to [0,1] \\
D_{voxel}^{mittel}(TP)&= \frac{\displaystyle\sum_{i=0}^{\vert TP \vert } D_{Reach}(p_{i})}{\vert TP \vert}
\end{split}
\end{equation}

\section{Verwandte wissenschaftliche Arbeiten}
Forstenhausler et al. \cite{Forstenhausler} dokumentieren in deren Publikation eine Methodik zur Kalkulation der Basisposition eines robotisch Systems anhand einer Aufgabe, ohne den schematisch illustrierten Algorithmus in \autoref{fig:4} zu nutzen. Der betrachtete Ansatz basiert auf der Spaltung des Arbeitsraums in verschiedene Dimensionen, ähnlich der in \autoref{fig:panda} dargestellten Perspektiven. Diese definieren einen sphärischen Körper um den Roboter, welche seinen welcher den Arbeitsraum anhand der Distanz charakterisiert. Eigenkollisionen treten häufiger auf, je näher die definierte Aufgabe an der Basis des robotischen Systems ist. Diese Erkenntnis wird durch eine zweite Sphäre integriert, die diesen fehleranfälligen Bereich aus dem tatsächlich Arbeitsraum entfernt. Sofern eine Aufgabe definiert ist, werden diese Sphären auf die Aufgabenpositionen projiziert. Die Kalkulation der Roboterbasis erfolgt anhand eines Algorithmus, welcher den Arbeitsraum des Roboters verschiebt, bis die Ausgabenpositionen in der vom Arbeitsraum definierten Sphäre liegen. \par
Tao et al. \cite{Tao} zeigt in seiner wissenschaftlichen Arbeit einen ähnlichen Ansatz, welcher den Arbeitsraum eins Roboters analog zu \autoref{Forstenhausler} anhand von Sphären beschreibt. In seinem Beispiel besteht der