Einführung in die Robotik · Bahnplanung darin, eine kollisionsfreie Bahn zwischen zwei Kon gurationen zu bestimmen.\ Ein vollst andiger Bahnplaner soll immer einen zul assigen Plan

$Page 1: Einführung in die Robotik · Bahnplanung darin, eine kollisionsfreie Bahn zwischen zwei Kon gurationen zu bestimmen.\ Ein vollst andiger Bahnplaner soll immer einen zul assigen Plan$
Universitat Hamburg

MIN-FakultatDepartment Informatik

- Einfuhrung in die Robotik

Einfuhrung in die Robotik

Jianwei [email protected]

Universitat HamburgFakultat fur Mathematik, Informatik und NaturwissenschaftenDepartment Informatik

Technische Aspekte Multimodaler Systeme

26. Juni 2012

J. Zhang 296

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung Einfuhrung in die Robotik

Gliederung

Allgemeine InformationenEinfuhrungKoordinaten eines ManipulatorsKinematik-GleichungenInverse Kinematik von ManipulatorenDifferentielle Bewegungen mit homogenen TransformationenJacobi-Matrix eines ManipulatorsAufgabenbeschreibungRobotergrammierung auf drei EbenenTrajektoriegenerierungTrajektoriengenerierungEinfuhrung in RCCLDynamik

J. Zhang 297

Universitat Hamburg



Gliederung (cont.)

RoboterregelungProgrammierung auf Aufgabenebene und Bahnplanung

Grundlage zur Programmierung auf AufgabenebeneObjekt-DarstellungMotivation der BahnplanungBewegungsplanungKonfiguration eines ArtefaktesPlanung geometrischer BahnenSichtbarkeitsgraphTangentengraphVoronoi-DiagrammHeuristische Suche

Programmierung auf Aufgabenebene und Bahnplanung

J. Zhang 298

Universitat Hamburg



Gliederung (cont.)

Programmierung auf Aufgabenebene und BahnplanungArchitekturen sensorbasierter intelligenter SystemeAus- und Ruckblick

J. Zhang 299

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Grundlage zur Programmierung auf Aufgabenebene Einfuhrung in die Robotik

Grundlage zur Programmierung auf Aufgabenebene

Ziel: die Aufgaben-Spezifikation mit symbolisch beschriebenen Zustandenzu ermoglichen,wobei: die Planung der notwendigen Bewegung dem Robotersystem zuuberlassen.Bezuglich der Roboterbewegung soll es lediglich notig sein, einemRoboter zu befehlen, wohin er sich bewegen soll, anstatt zu spezifizieren,wie er sich genau bewegen soll.Ein zentrales Problem der Programmierung auf Aufgabenebene:

KollisionsvermeidungEin Hauptlosungsansatz:

geometrische Bahnplanung - kollisionsfreie Bewegungen zu planen fur die

bekannten Manipulator- und Hindernisse-Modelle im Arbeitsraum.

J. Zhang 300

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Objekt-Darstellung Einfuhrung in die Robotik

Objekt-Darstellung

von Robotern, Umwelt und Konfigurationsraumen

I Approximierte Verfahren: Bounding-Box, Konvexe-Hulle, Kugel undEllipse

I “Constructive Solide Geometry”(CSG)

I “Boundary Representation” (BR)

I “Sweep Representation”

I Zellen-Darstellung:

I Gitter-Modell (“Spatial Occupancy Enuermation”)I Hierarchische Darstellung: Vierer-Baum (“quadtree”),

Achter-Baum (“octree”)

J. Zhang 301

Universitat Hamburg



Ein Beispiel der CSG-Darstellung

J. Zhang 302

Universitat Hamburg



Ein Beispiel der BR-Darstellung

J. Zhang 303

Universitat Hamburg



Ein Sweeping-Modell durch Drehung

J. Zhang 304

Universitat Hamburg



Eine Quadtree-Darstellung

J. Zhang 305

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Motivation der Bahnplanung Einfuhrung in die Robotik

Motivation: “Piano-Mover”

J. Zhang 306

Universitat Hamburg



Losung eines Knobelspiels uber einen Computer?

J. Zhang 307

Universitat Hamburg



Motivation: Roboterprogrammierung

J. Zhang 308

Universitat Hamburg



Motivation: Ausrichten eines Greifers

J. Zhang 309

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Bewegungsplanung Einfuhrung in die Robotik

Bewegungsplanung

Aufgaben umfassen:

I geometrische Bahnen

I Trajektorien (die Positions-, Geschwindigkeits- undBeschleunigungsfunktionen in Bezug auf die Zeit)

I Befehlsreihenfolge bei sensorbasierten Bewegungen

Ziele sind z.B.:

I kollisionsfreie Bewegung zum Ziel

I autonome Montage eines Aggregates

I Raumkognition

J. Zhang 310

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Konfiguration eines Artefaktes Einfuhrung in die Robotik

Konfiguration eines Artefaktes

Artefakt: ein virtueller oder realer Korper, der seinen Ort und/oderseine Form zeitlich verandern kann.

I Eine Konfiguration eines Artefaktes: eine Menge unabhangigerParameter, welche die Positionen aller seiner Punkte bezuglicheines Referenzkoordinatensystems spezifizieren.

I Darstellbar durch einen geometrischen Zustandsvektor.

I Die Anzahl der Parameter fur die Spezifikation einerKonfiguration: Freiheitsgrade.

J. Zhang 311

Universitat Hamburg



Konfiguration eines starren Korpers

Die Konfiguration des Objektes: (x , y , θ)In einem 3D Arbeitsraum: (x , y , z , α, β, γ)

J. Zhang 312

Universitat Hamburg



Konfigurationen eines Mehrgelenkarms

J. Zhang 313

Universitat Hamburg



Konfigurationen und Bahn eines Menschen

Eine Bahn: eine stetige Kurve, die zwei Konfigurationen verbindetτ : s ∈ [0, 1], τ(s) ∈ Konfigurationsraum

J. Zhang 314

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Planung geometrischer Bahnen Einfuhrung in die Robotik

Planung geometrischer Bahnen: Definition

Definition des Basisproblems (generalized mover’s problem):

”Werden eine begrenzte Anzahl m von statischen

Hindernissen und ein Artefakt mit d Freiheitsgradenvorgegeben, dann besteht die Aufgabe der geometrischenBahnplanung darin, eine kollisionsfreie Bahn zwischen zweiKonfigurationen zu bestimmen.“

Ein vollstandiger Bahnplaner soll immer einen zulassigen Planliefern, wenn ein solcher existiert, und ansonsten eine Aussage uberdie Nichtexistenz einer Bahn treffen.

J. Zhang 315

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Planung geometrischer Bahnen Einfuhrung in die Robotik

Planung geometrischer Bahnen: Ein- und Ausgabe

Bekannt seien:

I vollstandig a priori modellierte Geometrie des Artefaktes sowieder Hindernisse

I Kinematik des Artefaktes (eines starren bzw.formveranderlichen Korpers)

I Start- und Zielkonfiguration

Zu berechnen sei:

I eine Reihenfolge von stetigen Verbindungen kollisionsfreierKonfigurationen des Artefaktes von der Start- zurZielkonfiguration.

J. Zhang 316

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Sichtbarkeitsgraph Einfuhrung in die Robotik

Sichtbarkeitsgraph

Der Sichtbarkeitsgraph wird durch Verbindung der sichtbarenEckpunkte der Hindernisse konstruiert, wobei die Sichtbarkeitzweier Eckpunkte bedeutet, daß die Verbindungsgerade der beidenPunkte kein Hindernis schneidet.

(Nilsson 69)

Komplexitat: O(m2) (m: Anzahl der Eckpunkte derHindernispolygone)J. Zhang 317

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Tangentengraph Einfuhrung in die Robotik

Tangentengraph

Der T-Graph wurde als Teilgraph des Sichtbarkeitsgraph eneingefuhrt. Dabei wurde bewiesen, daß jede kurzeste Routezwischen Start und Ziel eine Teilmenge der T-Graph-Kanten ist.Die Haupteigenschaft des T-Graphen gegenuber demSichtbarkeitsgraphen liegt darin, daß die fur d ie Routenplanungnicht benotigten Kanten eliminiert werden konnen.

Komplexitat: O(m2) (m: Anzahl der Eckpunkte derHindernispolygone)

J. Zhang 318

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Voronoi-Diagramm Einfuhrung in die Robotik

Voronoi-Diagramm

Komplexitat: Knoten: O(m) (m: Anzahl der Eckpunkte dervieleckigen Hindernisse), Erstellungszeit: O(m log m)

J. Zhang 319

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Heuristische Suche Einfuhrung in die Robotik

Heuristische Suche

Fur die Routensuche im einem Graphen wird der A∗-Algorithmusverwendet.Man sucht ausgehend von dem Knoten s, in dem der Startpunktliegt, eine Route zu jenem Knoten z, in dem der Zielpunkt liegt.Der A∗-Algorithmus benutzt eine heuristische Kostenfunktion f ,die jeder Route vom Startknoten zu einem Knoten q einen Wertzuordnet, der die Gesamtkosten der Route vom Start- zumZielknoten uber diesen Knoten q abschatzt.Dabei laßt sich f als additive Verknupfung zweier Funktionen gund h wahlen, wobei g die bekannten Kosten der Route vomStartknoten zu q angibt und h die geschatzten Kosten derkurzesten Route von q zum Zielknoten angibt.

J. Zhang 320

Universitat Hamburg



Heuristische Suche

Wenn h so gewahlt wird, daß die wahren Kosten nicht uberschatztwerden, dann wird der Suchalgorithmus als A∗ bezeichnet. Es wirdgarantiert, daß die kurzeste existierende Route mit demA∗-Algorithmus gefunden werden kann.Um nicht nur die kurzeste, sondern auch die glatteste Route zufinden, beinhalten die Kosten einer Route außer der euklidischenLange auch einen Faktor fur Richtungsanderungen. g and h sindexakt folgendermaßen definiert:

I g= euklidische Lange der Route vom Start s zu q+ Gewichtsfaktor * Krummungsmaß;

I h =euklidische Lange der Route von q zum Zielpunkt+ Gewichtsfaktor * (das geschatzte Krummungsmaß)

J. Zhang 321

Universitat Hamburg



Heuristische Suche

Alle moglichen Kandidatenrouten von s nach q werden in eineOffen-Liste eingefugt.Jedesmal wird eine Kandidatenroute aus der Offen-Listeherausgeschoben, deren f -Wert minimal ist.Diese Kandidaten route wird dann mit allen freien Nachbarknotenexpandiert, und die neue f Funktion wird dazu ausgewertet.Dies geschieht so lange, bis der Zielknoten erreicht ist – eine Routewird gefunden, oder wenn die Offen-Liste leer ist – dann es gibtkeine Route von s nach z.

J. Zhang 322

Universitat Hamburg


Programmierung auf Aufgabenebene und Bahnplanung - Untere und obere Schranke der Bahnplanungsalgorithmen Einfuhrung in die Robotik

Untere und obere Schranke der Bahnplanungsalgorithmen

I Die erste untere Schranke: PSPACE-hart, d.h. mindestens soschwer wie ein NP-Problem – im ungunstigsten Fall eineexponentielle Rechenzeit fur jeden Algorithmus zur Losung desProblems (Reif 79).

I Die erste obere Schranke: zweifach exponentielleZeitkomplexitat mit dem Freiheitsgrad d (Schwartz und Sharir87).

I Die zweite obere Schranke: einfach exponentielle Rechenzeitmit dem Silhouetten-Verfahren (Canny 88).

J. Zhang 323

Documents

Einführung in die Robotik · Bahnplanung darin, eine kollisionsfreie Bahn zwischen zwei Kon gurationen zu bestimmen.\ Ein vollst andiger Bahnplaner soll immer einen zul assigen Plan