Einführung in die Robotik - tams.informatik.uni-hamburg.de · Fakult¨at f ¨ur Mathematik, Informatik und Naturwissenschaften Department Informatik Technische Aspekte Multimodaler

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


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



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



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


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


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



Ein Beispiel der CSG-Darstellung

J. Zhang 327

Universitat Hamburg



Ein Beispiel der BR-Darstellung

J. Zhang 328

Universitat Hamburg



Ein Sweeping-Modell durch Drehung

J. Zhang 329

Universitat Hamburg



Eine Quadtree-Darstellung

J. Zhang 330

Universitat Hamburg


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

Motivation: “Piano-Mover”

J. Zhang 331

Universitat Hamburg



Losung eines Knobelspiels uber einen Computer?

J. Zhang 332

Universitat Hamburg



Motivation: Roboterprogrammierung

J. Zhang 333

Universitat Hamburg



Motivation: Ausrichten eines Greifers

J. Zhang 334

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 335

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 336

Universitat Hamburg



Konfiguration eines starren Korpers

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

J. Zhang 337

Universitat Hamburg



Konfigurationen eines Mehrgelenkarms

J. Zhang 338

Universitat Hamburg



Konfigurationen und Bahn eines Menschen

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

J. Zhang 339

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 340

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 341

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 342

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 343

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 344

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 345

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 346

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 347

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 348

Documents

Einführung in die Robotik - tams.informatik.uni-hamburg.de · Fakult¨at f ¨ur Mathematik, Informatik und Naturwissenschaften Department Informatik Technische Aspekte Multimodaler