sota.tex

\chapter{Erkenntnisse zur Platzierung robotischer Systeme} \label{ch:sota}
Den dargelegten Grundlagen beziehungsweise dessen Abschnitt zur Formulierung der 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. in deren wissenschaftlichen Arbeit und kombiniert diesen in folgenden Publikationen mit zusätzlichen Aspekten der Kinematik, um einen Algorithmus zu formulieren, welcher sukzessiv die Position eines Roboters hinsichtlich seiner Grenzen bestimmt \cite{Zacharias2009}. 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. beschreiben in ihrer Publikation die Analyse des Arbeitsraums eines robotischen Systems als Ausgangspunkt zur Berechnung dessen optimaler Positionierung hinsichtlich einer zuvor definierten Aufgabe \cite{Vahrenkamp2013}. Dazu dokumentieren Zacharias et al. in ihrer wissenschaftlichen Arbeit einen Ansatz, dessen Inhalt es ist, durch wiederholtes Anwenden kinematischer Algorithmen $f_{kin}$, gezeigt in \autoref{eq:7}, das unmittelbare Umfeld des Roboters zu erfassen und dieses Anhand einer Metrik zu charakterisieren. 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. Alle Transformation $\in T$ zuzüglich der Information über dessen Erreichbarkeit bilden die \emph{reachability map (RM)}, welche persistiert wird \autoref{eq:8}. 

\begin{equation}\label{eq:7}
f_{kin}:T \to [0 | 1]
\end{equation}

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


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

\label{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. Das Kreuzprodukt dieser Mengen beschreibt alle Endeffektor Posen $\in T$ als Grundlage anschließender kinematischer Berechnungen $f_{kin}$. \autoref{eq:9} visualisiert diese Mengen.

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

\begin{equation}
\label{eq:10}
^{0}T_{Endeff}:= \{(v,R) | v \in P_{total},  R \in OR_{total} \} \in T
\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_{+}$, welches 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} 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 oder anderweitigen Abhängigkeit, mit Ausnahme des festen Intervalls $[-q,q]$, unterliegen.

\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_{+}$ das Umfeld des Roboters in ein reguläres Gitter der Grenzen $[-q,q]$ unterteilt. Der daraus resultierende diskretisierte Würfel stellt eine gleichmäßige Verteilung der Vektoren $^{0}v$ im Abstand $a$ innerhalb des Intervalls $[-q,q]$ dar, welcher in \autoref{fig:PT} anhand roter Marker illustriert ist. Wie \autoref{eq:12} 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}
Die Menge $^{0}OR_{total}$ beschreibt alle möglichen Orientierungen, die für jeden Vektor generiert und operiert 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 aus \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 $^{0}s$ $\overline{sp}$ \cite{SphericalCoordinates}. \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 eindeutig bestimmen.

\begin{equation}
\label{eq:15}
\vert S^{2} \vert = n
\end{equation}

\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:15} durch $n$ gegeben.

\subsection{Arbeitsraumcharakterisierung}
\autoref{eq:18} formuliert die Metrik $D_{Reach}$ zur Klassifizierung der Erreichbarkeit eines Vektors $^{0}v_{Endeff}$. Hierzu erfolgt eine Gegenüberstellung der Menge $OR_{v}$ aller Orientierungen $R$ zu einem Vektor $v$, 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 operierten Orientierungen für $^{0}v_{Endeff}$ \cite{Porges2015}. 

\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}:v & \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 $RM$ 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}
Inhalt dieses Abschnittes ist 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}a \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}a$, welche der Roboter operieren muss, skalieren die Menge aller Basen $P_{Base}$ um $n$. Dabei ist die Verteilung der Vektoren $^{0}p_{Base} \in P_{Base}$ unregelmäßig, beispielsweise gruppieren sie aufeinander oder sind vernachlässigbar voneinander distanziert. Eine Methode, innerhalb dieser enormen Datenmenge eine optimale Position zur Operation der Aufgaben zu entnehmen, ist die Voxelisierung. Dieses Verfahren, ähnlich der kubischen Diskretisierung, erzeugt einen Hyperwürfel innerhalb eines festen Intervalls $[-q, q] \in \R$, welcher aus $k \in \N$ disjunkten Voxeln besteht, dessen Zentren jeweils um eine Auflösung $u \in \R_{+}$ distanziert sind. Jeder Voxel enthält eine disjunkte Teilmenge $TP_{0} ...TP_{k-1}\subset P_{Base}$ der Basispositionen, die abstrahiert voneinander betrachtet werden. Diese Abbildung der Vektoren $^{0}p_{Base}$ auf Voxel implementiert eine Abtastung, wobei die Wertigkeit eines Voxels durch sein Zentrum und dessen Inhalt repräsentiert wird. Gleichermaßen dezimiert diese Darstellung das Lösungsspektrum der Aufgabenabhängigen Kardinalität von $P_{Base}$ auf die Anzahl aller Voxel $k$.

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

\subsection{Charakterisierung eines Voxels}
Nun erfolgt die Eruierung des Algorithmus von Makhal et al. \cite{Makhal2018}, welcher alle $k$ Voxel charakterisiert und anhand der enthaltenen Vektoren $^{0}p_{Base}$ 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}^{average}$ eines Voxels und dem Verhältnis von dessen Mächtigkeit zum maximalen Voxel $TP_{max}$ ergibt. 

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


$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. Die Metrik $D_{voxel}$ bewertet demnach ein Voxel anhand dessen Inhalts und Mächtigkeit, wobei die Voxel mit der maximalen Wertigkeit 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}^{average}:TP & \to [0,1] \\
D_{voxel}^{average}(TP)&= \frac{\displaystyle\sum_{i=0}^{\vert TP \vert } D_{Reach}(p_{i})}{\vert TP \vert}
\end{split}
\end{equation}