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
23. Juni 2009
J. Zhang 321
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung Einfuhrung in die Robotik
Gliederung
Allgemeine InformationenEinfuhrungKoordinaten eines ManipulatorsKinematik-GleichungenKinematik-GleichungenInverse Kinematik von ManipulatorenDifferentielle Bewegungen mit homogenen TransformationenJacobi-Matrix eines ManipulatorsAufgabenbeschreibungRobotergrammierung auf drei EbenenTrajektoriegenerierungTrajektoriengenerierungEinfuhrung in RCCL
J. Zhang 322
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung Einfuhrung in die Robotik
Gliederung (cont.)
DynamikRoboterregelungProgrammierung auf Aufgabenebene und Bahnplanung
Grundlage zur Programmierung auf AufgabenebeneObjekt-DarstellungMotivation der BahnplanungBewegungsplanungKonfiguration eines ArtefaktesPlanung geometrischer BahnenSichtbarkeitsgraphTangentengraphVoronoi-Diagramm
Programmierung auf Aufgabenebene und Bahnplanung
J. Zhang 323
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung Einfuhrung in die Robotik
Gliederung (cont.)
Transformation vom Arbeitsraum zum KonfigurationsraumBerechnung der K-Hindernisse von PolygonenBerechnung der K-Hindernisse fur StangenketteReprasentation des Konfigurationsraums durchZerlegungsverfahren
Programmierung auf Aufgabenebene und BahnplanungArchitekturen sensorbasierter intelligenter SystemeAus- und Ruckblick
J. Zhang 324
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 325
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 326
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Objekt-Darstellung Einfuhrung in die Robotik
Ein Beispiel der CSG-Darstellung
J. Zhang 327
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Objekt-Darstellung Einfuhrung in die Robotik
Ein Beispiel der BR-Darstellung
J. Zhang 328
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Objekt-Darstellung Einfuhrung in die Robotik
Ein Sweeping-Modell durch Drehung
J. Zhang 329
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Objekt-Darstellung Einfuhrung in die Robotik
Eine Quadtree-Darstellung
J. Zhang 330
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Motivation der Bahnplanung Einfuhrung in die Robotik
Motivation: “Piano-Mover”
J. Zhang 331
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Motivation der Bahnplanung Einfuhrung in die Robotik
Losung eines Knobelspiels uber einen Computer?
J. Zhang 332
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Motivation der Bahnplanung Einfuhrung in die Robotik
Motivation: Roboterprogrammierung
J. Zhang 333
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Motivation der Bahnplanung Einfuhrung in die Robotik
Motivation: Ausrichten eines Greifers
J. Zhang 334
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 335
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 336
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Konfiguration eines Artefaktes Einfuhrung in die Robotik
Konfiguration eines starren Korpers
Die Konfiguration des Objektes: (x , y , θ)In einem 3D Arbeitsraum: (x , y , z , α, β, γ)
J. Zhang 337
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Konfiguration eines Artefaktes Einfuhrung in die Robotik
Konfigurationen eines Mehrgelenkarms
J. Zhang 338
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Konfiguration eines Artefaktes Einfuhrung in die Robotik
Konfigurationen und Bahn eines Menschen
Eine Bahn: eine stetige Kurve, die zwei Konfigurationen verbindetτ : s ∈ [0, 1], τ(s) ∈ Konfigurationsraum
J. Zhang 339
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 340
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 341
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 342
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 343
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 344
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 345
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Heuristische Suche Einfuhrung in die Robotik
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 346
Universitat Hamburg
MIN-FakultatDepartment Informatik
Programmierung auf Aufgabenebene und Bahnplanung - Heuristische Suche Einfuhrung in die Robotik
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 347
Universitat Hamburg
MIN-FakultatDepartment Informatik
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 348