05.03.2021

Mathematische Grundlagen der Kognitiven Robotik, WS2020/21
Heinrich Mellmann, Lea Musiolek, Prof. Verena V. Hafner

# Klausur

Erlaubte Hilfsmittel: bei der Vorlesung bereitgestellte Materialien (Mitschriften, Folien, Übungen) und eigene Notizen.

* Notieren Sie die Lösungen auf eigenem Papier und nicht auf einem Ausdruck der Aufgaben.
* Benutzen Sie für jede Aufgabe ein neues Blatt.
* Versehen Sie jedes Blatt mit Ihrem **Namen, Matrikelnummer und Unterschrift**, sowie der Nummer der jeweiligen Aufgabe.
* Geänderte Antworten müssen deutlich als solche markiert sein. Bitte schreiben Sie leserlich. Punkte können nur für lesbare Antworten vergeben werden.
* Skizzen sind erwünscht und hilfreich. Fassen Sie Ihre Text-Antworten in wenige Sätze.
* Die Klausur besteht aus 8 Aufgaben und 120 zu erreichenden Punkten, dabei entsprechen 100 Punkte 100%. Ab 50 Punkten haben Sie bestanden.
* Die Klausur dauert 120 Minuten.

**Viel Erfolg!**

| Aufgabe | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | $\Sigma$ |
| ------- | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
| Punkte | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 |120|

$$
\newcommand{R}{\mathbb{R}}
\newcommand{sin}{\text{sin}}
\newcommand{cos}{\text{cos}}
$$

<div style="page-break-after: always; break-after: page;"></div>

## Aufgabe 1 (Rotationen, Koordinatensysteme, Transformationen)

Ein zweidimensionaler Fußballroboter hat die Position $p_0\in \mathbb{R}^{2}$ und Rotation $\alpha_0\in[-\pi,\pi)$ auf dem Spielfeld.
Zusätzlich befindet sich auf dem Spielfeld ein Ball auf der Position $b\in\R^2$ in den Koordinaten des Spielfeldes.
Nun fährt der Roboter (aus seiner Sicht) eine Distanz $\rho\in\R$ in $x$-Richtung (vorwärts) und dreht sich **anschließend** um die eigene Achse mit dem Winkel $\beta\in [-\pi,\pi)$. Die neue Position des Roboters auf dem Feld bezeichnen wir mit $p_1\in\R^2$ und seine neue Orientierung mit $\alpha_1\in[-\pi,\pi)$.

---

1. Schreiben Sie die Orientierung $\alpha_0$ des Roboters als Rotationsmatrix $R(\alpha_0)\in \R^{2\times 2}$
2. Bestimmen Sie die Position $b_0\in\R^2$ des Balls in **lokalen kartesischen Koordinaten** des Roboters **vor der Bewegung**
3. Bestimmen Sie die neue Position $p_1$ und Rotation des Roboters als Winkel $\alpha_1$ und als Matrix $R_1=R(\alpha_1)\in \R^{2\times 2}$ nach der Bewegung in Abhängigkeit von $\rho$ und $\beta$
5. Bestimmen Sie die Rotation $R\in \R^{2\times 2}$ und Translation $t\in\R^2$ so, dass für die Position des Balls $b_1\in\R^2$ in **lokalen kartesischen Koordinaten** des Roboters **nach der Bewegung** gilt
$$
b_1 = R\cdot b_0 + t
$$
6. Berechnen Sie die $p_1,\alpha_1,R_1, b_0, b_1$ für konkrete Werte
$$
p_0 = \begin{pmatrix} 3 \\ 2 \end{pmatrix},\;\alpha_0 = -\pi,\quad \rho=2,\;\beta=-\frac{\pi}{2},\quad b = \begin{pmatrix} 1 \\ 3 \end{pmatrix}
$$
8. Stellen Sie die Situation in einer Skizze dar.

**Kommentieren Sie Ihr Vorgehen.**

**Hinweis:**
* die Blickrichtung des Roboters entspricht der $x$-Achse seines Koordinatensystems

<div style="page-break-after: always; break-after: page;"></div>

## Aufgabe 2 (Vorwärtskinematik, Homogene Koordinaten)

Betrachten Sie einen planaren (2D) Roboterarm mit **zwei** Rotationsgelenken, die über die Winkelparameter $\gamma_1, \gamma_2 \in [-\pi, \pi)$ angesteuert werden, und Längen der Segmente $l_1, l_2 \in \R$. Die Segmente verbinden die Gelenke so, dass die kinematische Kette die Form $\gamma_1 - l_1 - \gamma_2 - l_2$ hat. Am Ende des Segmentes $l_2$ befindet sich der Greifer. Das Gelenk $\gamma_1$ ist auf einem Roboter auf der Position $p\in\R^2$ (im Koordinatensystem des Roboters) angebracht.

---

1. Bestimmen Sie die Koordinatentransformation $T(\gamma_1, \gamma_2)\in\mathbb{R}^{3\times3}$ aus dem **Koordinatensystem des Endeffektors** in das **Koordinatensystem des Roboters** in der Schreibweise der *homogenen Koordinaten* in Abhängigkeit von den Winkelparametern.

2. Bestimmen Sie die Position $q\in\R^2$ des Greifers in den **Roboter-Koordinaten** für konkrete Werte
$$
l_1 = 3,\; l_2 = 2,\quad \gamma_1 = \frac{\pi}{4},\; \gamma_2 = -\frac{\pi}{4},\quad p=\begin{pmatrix} 1 \\ 1 \end{pmatrix}
$$

3. Skizzieren Sie den Roboterarm für diesen konkreten Fall

**Kommentieren Sie Ihr Vorgehen und die Zwischenschritte.**

**Hinweis:**
* $\sin(\frac{\pi}{4})=\cos(\frac{\pi}{4})=\frac{1}{\sqrt{2}}$

<div style="page-break-after: always; break-after: page;"></div>

## Aufgabe 3 (Interpolation)

Ein Roboter hat die Aufgabe, eine Box mit einer bestimmten Ausrichtung anzufahren, um sie zu greifen und zu transportieren. Der **zweidimensionale** Pfad des Roboters wird durch die Funktion
$$
\begin{align}
f:[0,1]&\rightarrow \R^2 \\
t &\mapsto f(t) = \begin{pmatrix}
f_x(t) \\
f_y(t)
\end{pmatrix}
\end{align}
$$
beschrieben, die dem Parameter $t\in[0,1]$ eine Position $f(t)\in\R^2$ des Pfades zuordnet. Die Ausrichtung des Roboters ist durch die **Ableitung**
$$
Df(t) = \begin{pmatrix}
f_x'(t) \\
f_y'(t)
\end{pmatrix}
$$
festgelegt. Der Pfad zu der Box wird jeweils durch ein kubisches Polynom für beide Dimensionen modelliert
$$
f(t) = \begin{pmatrix}
f_x(t) \\
f_y(t)
\end{pmatrix}= \begin{pmatrix}
a_x\cdot t^3 + b_x\cdot t^2 + c_x\cdot t + d_x \\
a_y\cdot t^3 + b_y\cdot t^2 + c_y\cdot t + d_y
\end{pmatrix}
$$
Für die Position und die Ausrichtung am Anfang gilt
$$
f(0) =\begin{pmatrix}
0 \\
0
\end{pmatrix},\quad Df(0) = \begin{pmatrix}
0 \\
1
\end{pmatrix}
$$
Für die Endposition und die Ausrichtung am Ende des Pfades soll gelten
$$
f(1) =\begin{pmatrix}
1 \\
1
\end{pmatrix},
\quad Df(1) = \begin{pmatrix}
1 \\
0
\end{pmatrix}
$$

---
1. Schreiben Sie das Problem als lineares Gleichungssystem und bestimmen Sie die Koeffizienten der Funktion $f$.

2. Erstellen Sie eine Skizze, die die Situation und den Pfad veranschaulicht.

**Kommentieren Sie Ihr Vorgehen und die Zwischenschritte.**

<div style="page-break-after: always; break-after: page;"></div>

## Aufgabe 4 (Wahrscheinlichkeiten, Bayes Filter)

Betrachten Sie einen Roboter, der vor einer Tür steht, die nur im **Zustand** $x_0\in S:=\{o,g\}=\{\text{offen}, \text{geschlossen}\}$ sein kann. Der Roboter ist mit einem **Sensor** ausgestattet, der ihm erlaubt zu ermitteln ob die Tür gerade *offen* oder *geschlossen* ist (zum Beispiel ein Abstandssensor). Der Roboter verfügt ebenfalls über einen **Aktuator** (zum Beispiel einen Arm) mit dem er versuchen kann, die Tür zu öffnen oder zu schließen. Der Sensor und Aktuator sind jedoch nicht sehr zuverlässig und werden probabilistisch modelliert. Im Anfangszustand $x_0$ sind beide Möglichkeiten gleich wahrscheinlich.
$$
p(x_0) = 0.5,\quad x_0\in \{o,g\}
$$

---
1. Der Roboter macht eine Messung $z_0$. Zeigen Sie, dass für den *Belief* $bel(x_0)=p(x_0|z_0)$ gilt
$$
p(o|z_0) + p(g|z_0) = 1
$$

2. Für das Sensormodell $p(z_0|x_0)$ zu der Messung $z_0$ gilt

$$
\begin{align}
&p(z_0|\text{o}) &= 0.8 \\
&p(z_0|\text{g}) &= 0.5
\end{align}
$$

Bestimmen Sie den *Belief* $bel(x_0)=p(x_0|z_0)$ für den Zustand der Tür. Da es nur zwei Zustände gibt, ist der Belief durch zwei Werte definiert
$$
\begin{align}
p(\text{o}|z_0)=?\\
p(\text{g}|z_0)=?\\
\end{align}
$$

3. Der Roboter führt die Aktion $u_1$ aus - (zum Beispiel stößt die Tür mit einem Aktuator im Versuch sie aufzumachen). Der Roboter hat dabei folgendes Zustandsübergangsmodell $p(x_1|u_1, x_0)$ von seinem Aktuator für die Aktion $u_1$

$$
\begin{align}
p(\text{o}|u_1, \text{o}) = 0.8 \\
p(\text{g}|u_1, \text{o}) = 0.2 \\
p(\text{o}|u_1, \text{g}) = 0.5 \\
p(\text{g}|u_1, \text{g}) = 0.5 \\
\end{align}
$$

Bestimmen Sie den *Belief* $bel(x_1)=p(x_1|u_1,z_0)$ für den Zustand der Tür nach der Aktion $u_1$. Da es nur zwei Zustände gibt, besteht der Belief nur aus zwei Werten
$$
\begin{align}
p(\text{o}|u_1,z_0)=?\\
p(\text{g}|u_1,z_0)=?\\
\end{align}
$$

**Hinweise:**

- Wir nehmen an, dass der Ausgangszustand $x_0$ **stochastisch unabhängig** von der Aktion $u_1$ ist.
- Wir nehmen an, dass der Folgezustand $x_1$ **bedingt stochastisch unabhängig** von der Messung $z_0$ ist, wenn der Ausgangszustand $x_0$ bekannt ist.

**Kommentieren Sie Ihr Vorgehen.**

<div style="page-break-after: always; break-after: page;"></div>

## Aufgabe 5 (Partikel-Filter)

1. Beschreiben Sie in eigenen Worten stichpunktartig die Funktionsweise des Partikel-Filters. Gehen Sie dabei insbesondere auf folgende Punkte ein
* In welcher Relation stehen die Begriffe *Partikel-Filter* und *Bayesscher Filter*?
* Nennen Sie die wichtigen Schritte des Algorithmus und beschreiben Sie deren Funktion.
* Was bedeutet *Belief*?
* Wie werden Wahrscheinlichkeitsverteilungen im Partikel-Filter dargestellt?
* Nutzen Sie zum Erklären ein Beispiel.

**Hinweis:** Der Partikelfilter (eng. Particlefilter) ist synonym mit der Sequenziellen Monte-Carlo-Methode.

<div style="page-break-after: always; break-after: page;"></div>

## Aufgabe 6 (Minimierung, Gradientenverfahren)

Betrachten Sie die Funktion $f:\R^2 \rightarrow \R$, definiert durch
$$
f(x,y) := \frac{1}{2}((x+3)^2 + (y-2)^2)
$$
1. Bestimmen Sie den Gradienten $\nabla f(x,y)$

2. Betrachten Sie den Startpunkt $p_0:=(x_0, y_0) = (3,3)$. Bestimmen Sie den Gradienten $\nabla f(x_0,y_0)$.

3. Bestimmen Sie nun ausgehend von $p_0$ die nächsten drei Punkte $p_1,p_2,p_3\in\R^2$, die sich durch die Anwendung des Gradienten-Abstieges mit fester Schrittweite $\alpha = 0.5$ ergeben.

4. Skizzieren Sie die Funktion $f$ als Kontur-Zeichnung und die Punkte $p_1,p_2,p_3$.

5. Beantworten Sie in Kürze folgende Fragen

( a ) Findet das Verfahren immer das globale Minimum?
( b ) Nennen Sie ein Beispiel wofür das Verfahren in der Robotik eingesetzt werden kann.
( c ) Wie kann die Abbruchbedingung formuliert werden?

**Kommentieren Sie Ihr Vorgehen.**

<div style="page-break-after: always; break-after: page;"></div>

## Aufgabe 7 (Künstliche Evolution)

1. Beschreiben Sie stichpunktartig das Grundschema der Evolutionären Algorithmen und benutzen Sie dabei folgende Begriffe
* Selektion
* Population
* Mutation
* Individuum
* Fitness-Funktion
* Crossover

2. Wie kann man mit der bei Genetischen Algorithmen üblichen Binärkodierung trotzdem (annähernd) kontinuierliche Werte darstellen? Geben Sie ein Beispiel für 4 Bit und Werte zwischen -1.0 und 1.0.

3. Kann das **Bergsteigeverfahren** als eine **Evolutionsstrategie** betrachtet werden? Begründen Sie Ihre Antwort.

<div style="page-break-after: always; break-after: page;"></div>

## Aufgabe 8 (Projekt "pick and place")
1. Der Roboter *youBot* aus dem Projekt verfügt über die sogenannten Mecanum-Räder, die ein *omnidirektionales* Fahren ermöglichen. Gegeben seien die Geschwindigkeiten $(x,y,\alpha)\in\R^3$ für die Bewegung in $x$-Richtung, $y$-Richtung und die Rotation um die eigene Achse $\alpha$. Schreiben Sie die Formel für die Funktion $f:\R^3\rightarrow \R^4$, die die entsprechenden Geschwindigkeiten $f(x,y,\alpha) = (\theta_1,\theta_2,\theta_3,\theta_4)\in\R^4$ einzelner Räder bestimmt.
**Hinweis:** die maximal mögliche Geschwindigkeit der Räder muss nicht beachtet werden.
2. Wir betrachten das Anfahren der Box als ein 2D Problem. Der Roboter kennt die eigene **globale** Position $p\in\R^2$ und Rotation $R\in\R^{2\times 2}$, sowie die **globale** Position der Box $b_G\in\R^2$. Bestimmen Sie die Parameter $(x,y,\alpha)$ so, dass der Roboter zur Box fährt und in einem Abstand $d\in\R$ vor der Box anhält. Erstellen Sie eine Skizze.
4. Um die Box dynamisch aus verschiedenen Lagen zu greifen, kann die **inverse Kinematik** genutzt werden. Wir nehmen an, dass die Vorwärtskinematik bekannt ist, das heißt es sind die Position $p(\theta)\in\R^3$ und die Rotation $R(\theta)\in\R^{3\times 3}$ des Greifers in Abhängigkeit von den Gelenkwinkeln des Roboterarms $\theta\in [-\pi,\pi)^5$ gegeben. Sei $p\in\R^3$ die Position der Box in den **Koordinaten des Roboters**. Sei $q\in\R^3$ eine Position in den **Koordinaten des Greifers** an der die beste Greifleistung vorliegt. Formulieren Sie das Minimierungsproblem um die Winkel $\theta^*\in [-\pi,\pi)^5$ so zu bestimmen, dass, wenn diese angesteuert werden, die Position der Box in den **Koordinaten des Greifers** der Position $q$ entspricht.