Antrag auf Gewahrung der Phase IIeines Emmy Noether-Forschungsstipendiumsbei der Deutschen Forschungsgemeinschaft

1 Allgemeine Angaben

Hiermit beantrage ich die Forderung einer Nachwuchsgruppe fur ein Forschungsvorhaben im Rah-

men der Phase II des Emmy Noether-Programms. Dieser Antrag erfolgt ohne vorhergehende Pha-

se I; es handelt sich somit um einen Neuantrag.

1.1 Antragsteller

Name: Oliver Brock, Ph.D.

Dienststellung: Research Associate (Wissenschaftlicher Mitarbeiter)

Geburtsdatum: 3. Juli 1969

Nationalitat: Deutsch

Institution: Robotics Laboratory

Department of Computer Science

Stanford University

Dienstadresse: Gates Building, Room 122

Stanford Univeristy

Stanford, CA 94305

U.S.A.

Telefon: +1 (650) 725-8810

Telefax: +1 (650) 725-1449

Email: oli@cs.stanford.edu

URL: http://robotics.stanford.edu/˜oli

Privatanschrift: 1471 South Van Ness Avenue # B

San Francisco, CA 94110

U.S.A.

Telefon: +1 (415) 642-0893

1

Tabellarischer Lebenslauf siehe Anlage.

1.2 Thema

Echtzeitbewegungsgenerierung fur Roboter mit vielen Freiheitsgraden in dynamischem Umfeld

und unter Berucksichtigung von Aspekten der Bahnplanung und der Bewegungsregelung

1.3 Kennwort

Echtzeitbewegungsgenerierung fur Roboter

1.4 Fachgebiet und Arbeitsrichtung

Informatik, Robotik

1.5 Voraussichtliche Gesamtdauer

Dies ist ein Antrag fur die Phase II des Emmy Noether-Programms. Daher wird eine Gesamtdauer

von vier Jahren beantragt.

1.6 Antrangszeitraum

Es wird die Gewahrung eines Forschungsstipendiums fur die voraussichtliche Gesamtdauer des

Forschungsvorhabens von 48 Monaten beantragt.

1.7 Gewunschter Beginn der Forderung

Als Beginn der Forderung wird der 1. September 2002 erbeten.

1.8 Zusammenfassung des Forschungsvorhabens

Es sollen die algorithmischen Grundlagen fur die Echtzeitgenerierung von Bewegungen fur Ro-

boter mit vielen Freiheitsgraden, wie zum Beispiel humanoide Roboter, gelegt werden. Solche

Methoden sind eine Grundvoraussetzung fur das autonome agieren solcher Maschinen in dynami-

schen und mit Menschen geteilten Umgebungen. Herkommliche Methoden der Bewegungsgene-

rierung erfullen zumeist die Echtzeitanforderungen nicht und ziehen nur Teilaspekte der zu erzeu-

genden Bewegung in Betracht. Im Rahmen dieses Forschungsvorhabens sollen neuartige Echtzeit-

algorithmen entwickelt werden, die eine aufgabengesteuerte Bewegungsgenerierung fur Roboter

2

mit vielen Freiheitsgraden in Echtzeit ermoglichen. Dabei sollen alle fur die Aufgabenerfullung

notwendigen Bewegungsaspekte berucksichtigt werden konnen. Dies beinhaltet unter anderem die

Koordinierung von Mobilitat und Manipulation, die Berucksichtigung von Randbedingungen (Kol-

lisionsvermeidung, Kontakt mit der Umwelt, etc.) und die Integrierung von Optimalitatskriterien.

Die Leistungsfahigkeit der resultierenden Methoden soll durch Simulationen und Experimente mit

humanoiden Robotern uberpruft werden. Weiterhin wird beabsichtigt, Perzeptionsmethoden zu

entwickelt, die wahrend der Bewegungsausfuhrung Veranderungen im gesamten Arbeitsfeld des

Roboters ermitteln, so dass die Bewegung entsprechend der aufgabenbedingten Anforderungen

modifiziert werden kann. Die resultierende Methoden werden es Robotern mit vielen Freiheitsgra-

den ermoglichen, unbeaufsichtigt und eigenstandig vielseitige Aufgaben in dynamischem Umfeld

durchzufuhren.

2 Stand der Forschung, eigene Vorarbeiten

2.1 Stand der Forschung

Gegenwartig kann auf dem Gebiet der Robotik ein starker Trend zu humanoiden Robotern beob-

achtet werden1 (Brooks 1997; Asfour et al. 1999; Bischoff und Graefe 1999; Adams et al. 2000;

Asfour et al. 2000; Bischoff 2000; Dillmann et al. 2000; Honda 2001; Kagami et al. 2001; Kagami

et al. 2001; Kuffner et al. 2001; Shiller et al. 2001). Diese Roboter sollen den Anwendungsbe-

reich von Automatisierungstechnologie uber die Montagestraße hinaus auf die Arbeitsraume von

Menschen erweitern. Humanoide Roboter erscheinen dazu besonders gut geeignet, da ihre an-

tropomorphe Gestalt es ihnen ermoglicht, von Menschen benutzte Werkzeuge zu verwenden und

somit mit Menschen zu kooperieren oder deren Tatigkeiten zu ubernehmen. Durch die Fortbe-

wegung mit Beinen sind sie in der Lage samtliche fur Menschen konstruierte Arbeitsraume zu

erschließen; es sind jedoch auch mobile Manipulatoren mit humanoiden Formen fur diesen Zweck

konzipiert worden (siehe auch Abbildung 1). Um die zur Kooperation und zur Ausfuhrung von

Tatigkeiten erforderlichen vielseitigen und komplexen Bewegungsablaufe berechnen zu konnen,

sind leistungsfahige Algorithmen zur Bahngenerierung erforderlich. Diese konnen als essentielle

Grundlage fur samtliche Anwendungen von Robotern in dynamischem Umfeld angesehen werden.

Bei Anwendungen außerhalb der Montagestraße konnen herkommliche Methoden den gesteigerten1Die DFG hat gemaß dieses Trends den Sonderforschungsbereich Humanoide Roboter (SFB 1846) bewilligt (Dill-

man, R. et al. 2000). Der Schwerpunkt des SFB Humanoide Roboter liegt bei der intelligenten Interaktion zwischenMensch und Maschine und kann deswegen als komplementar zu dem vorliegenden Forschungsvorhaben angesehenwerden.

3

Anforderungen, die sich aus der hohen Anzahl von erforderlichen Freiheitsgraden, den verscharf-

ten Echtzeit- und Sicherheitsanforderungen und den vielseitigen Aufgabenanforderungen ergeben,

nicht gerecht werden.

Abbildung 1: Humanoide Roboter (von links nach rechts): ARMAR von der Universitat Karlsruhe,Asimo von Honda, Cog vom Massachusetts Institute of Technology, HERMES von der Bundes-wehruniversitat Munchen, P3 von Honda und WABIAN RIII von der Waseda Universitat in Tokio.

In der Literatur zur Bewegungsgenerierung fur Roboter wird im Allgemeinen zwischen Bahn-

planung (Latombe 1991) und Bewegungsregelung (Franklin et al. 1994) unterschieden. Dabei

versteht man unter Bahnplanung die Bestimmung einer Bewegung vor dessen Ausfuhrung un-

ter Berucksichtigung globaler Informationen uber die Umwelt. Bewegungsregelung oder Bewe-

gungsausfuhrung hingegen ist die Bestimmung einer Bewegung wahrend dessen Ausfuhrung un-

ter Berucksichtigung von begrenzten, lokalen Informationen, meistens einer genauen Vorgabe fol-

gend. Dabei ist zu beachten, dass die Differenzierung zwischen Planung und Regelung zumeist in

der Aufwendigkeit der Berechnungen begrundet ist und nicht etwa als inharente Eigenschaft der

Problemstellung angesehen werden kann.

2.1.1 Bahnplanung

Bahnplanung dient der Berechnung von kollisionsfreier Bewegung fur Roboter. Es existieren ei-

ne Vielzahl von Methoden zur Bahnplanung (Latombe 1991; Hwang und Ahuja 1992), allerdings

ist die Komplexitat vollstandiger Algorithmen exponentiell in der Anzahl der Freiheitsgrade des

Roboters (Canny 1988). Daher ist Bahnplanung bereits fur einfache Problemstellungen außeror-

dentlich rechenaufwendig. Durch die Einfuhrung probabilistischer – und somit unvollstandiger

oder probabilistisch vollstandiger – Methoden (Kavraki et al. 1996) sind in den letzten Jahren er-

hebliche Fortschritte erzielt worden. So erlauben es einige Methoden, Bewegungen fur realistisch

anmutende Szenarien innerhalb weniger Minuten oder gar im Bereich von Sekunden zu berech-

4

nen (Bohlin und Kavraki 2000; Kuffner und LaValle 2000; Nielsen und Kavraki 2000). Es wur-

den zahlreiche weitere Varianten von probabilistischen Bahnplanungsalgorithmen entwickelt, die

Heuristiken verwenden, um unter bestimmten Bedingungen die Berechnungen zu beschleunigen

(Amato et al. 1998; Vallejo et al. 2001; Song et al. 2001). Die Basisalgorithmen wurden erweitert,

um auch Bewegungen fur elastische Gegenstande (Lamiraux und Kavraki 2001) oder geschlos-

sene kinematische Ketten (LaValle et al. 1999) berechnen zu konnen. Es wurden auch dynami-

sche Randbedingungen in die probabilistische Bewegungsplanung integriert (LaValle und Kuffner

1999; Hsu et al. 2000), wie zum Beispiel das Halten des Gleichgewichts bei humanoiden Robo-

tern (Kuffner et al. 2001). Die Anwendung von probabilistischen Bahnplanungsmethoden auf den

Gebieten der Animation (Kuffner 1998), der Entwicklung von Medikamenten (Finn und Kavraki

1999) und der Untersuchung von Faltungsmechanismen in Proteinen (Song und Amato 2001) hat

gezeigt, dass diese Methoden vielseitiger anwendbar sind, als deterministische Verfahren.

Die mathematischen Prinzipien, auf denen diese Erfolge bei der Bahnplanung basieren, wur-

den eingehend untersucht (Kavraki 1994; Hsu et al. 1997; Hsu et al. 1999; Branicky et al. 2001).

Intuitiv gesehen beruhen sie auf der Tatsache, dass Konfigurationsraumhindernisse (Lozano-Perez

1983) nicht explizit berechnet, sondern nur implizit durch eine reprasentative Stichprobe des kom-

plementaren Raums (Freiraum) reprasentiert werden. Dies bedeutet aber auch, dass es in hochdi-

mensionalen und komplizierten Konfigurationsraumen zunehmend schwer wird, die Verbindungen

der einzelnen Freiraumkomponenten zu bestimmen. Somit kann die Ermittlung einer Bewegung

erheblich erschwert oder sogar verhindert werden. Diess Problem wird als das narrow passage pro-

blem bezeichnet (Hsu et al. 1998) und ist ein Gebiet reger Forschungsarbeit. Seine Auswirkungen

zeigen sich bei der Anwendungen von probabilistischen Bahnplanungsmethoden in hochdimen-

sionalen Konfigurationsraumen: der Rechenaufwand fur die Planung von einfachen Bewegungen

ist hier unverhaltismaßig groß (Kuffner et al. 2001).

Zusammenfassend kann man sagen, dass gegenwartig trotz enormer Fortschritte auf dem Ge-

biet der Bahnplanung durch die Einfuhrung probabilistischer Methoden keine Echtzeitbewegungs-

planung2 auf verlassliche Weise realisierbar ist. Dies gilt insbesondere dann, wenn durch die Ein-

beziehung von Randbedingungen der zu berechnenden Bewegung die Dimensionalitat des Konfi-

gurationsraums uber die Freiheitsgrade des Roboters hinaus erhoht wird.2Unter Echtzeitbewegungsplanung wollen wir hier solche Algorithmen verstehen, die mehr als ein Mal in der

Sekunde eine geplante Bewegung errechnen konnen.

5

2.1.2 Regelungsalgorithmen

Regelungstheorie (Franklin et al. 1994; Franklin et al. 1998) findet in der Robotik vielseitige An-

wendung. In den meisten Fallen werden Roboterbewegungen als zeitabhangige Funktion von Ge-

lenkvariablen beschrieben, die dann mit Hilfe von Regelungsalgorithmen ausgefuhrt werden. Re-

gelungsalgorithmen im operationalen Raum (Khatib 1980; Khatib 1987) ermoglichen eine direkte

Regelung der Variablen, die die auszufuhrende Aufgabe beschreiben und abstrahieren somit von

den kinematischen Eigenschaften des Roboters. Eine Bewegungsbeschreibung durch die Aufgabe

ist insbesondere bei Robotern mit vielen Freiheitsgraden einfacher und effizienter, als Methoden,

die Bewegungen direkt im Konfigurationsraum des Roboters beschreiben. Regelungsalgorithmen

im operationalen Raum konnen auch auf sich verzweigende kinematische Ketten angewendet wer-

den (Russakow et al. 1995), wie zum Beispiel zweiarmigen, humanoiden Robotern. Auch wenn

die Arme gemeinsam ein Objekt ergreifen, konnen sie weiterhin im operationalen Raum geregelt

werden (Williams und Khatib 1993; Chang et al. 2001); gleiches gilt fur mehrere unabhangige Ro-

boter, die gemeinsam einen Gegenstand manipulieren (Khatib et al. 1995; Holmberg und Khatib

2000). Manche Aufgaben, wie zum Beispiel die Reinigung eines Fensters, machen Bewegungen

erforderlich, bei denen der Roboter mit der Umwelt in Beruhrung ist. Es existieren eine Vielzahl

von Regelungsalgorithmen, die dies erlauben (De Schutter und Van Brussel 1988a; De Schutter

und Van Brussel 1988b). Aber auch hier konnen Regelungsalgorithmen im operationalen Raum

vorteilhaft angewandt werden (Featherstone et al. 1999). Kombiniert man die vielseitigen Erwei-

terungen der operationalen Regelung, so lassen sich komplizierte Bewegungsablaufe anhand der

auszufuhrenden Aufgabe auf einfache Weise spezifizieren und ausfuhren (Khatib et al. 1999). Da-

zu mussen lediglich die Freiheitsgrade der Aufgabe beschrieben werden und die Bewegungen der

redundanten Freiheitsgrade werden durch einen operationalen Regelungsalgorithmus bestimmt.

Dennoch gibt Aspekte von Bewegungen, die nicht direkt von der Aufgabe selbst abhangig sind.

Bei einem humanoiden Roboter mussen die Freiheitsgrade der Beine zum Beispiel unabhangig

von einer von den Armen ausgefuhrten Aufgabe so bewegt werden, dass sich der Roboter an den

gewunschten Zielort bewegt. In der Literatur lassen sich verschiedene Ansatze finden, die dies

ermoglichen (Huang et al. 2000; Nishiwaki et al. 2001). Weiterhin muss die Bewegung zwischen

den Beinen und dem Rest des Korpers so abgestimmt sein, damit der Roboter nicht das Gleich-

gewicht verliert. Auch zu diesem Problem wurden erfolgreiche Regelungsmethoden demonstriert

(Kagami et al. 2000; Nakamura und Yamane 2000; Inoue et al. 2000). Diese Algorithmen lassen

sich mit Algorithmen zur operationalen Regelung kombinieren, so dass operationale Regelung als

ausgesprochen vielseitiger Ansatz zur Regelung von Roboterbewegungen betrachtet werden kann.

6

Trotz ihrer vielseitigen Anwendbarkeit konnen Regelungsalgorithmen nicht als alleiniger An-

satz zur Bewegungsgenerierung fur Roboter dienen, da sie nur zur Regelung lokaler Aspekte der

Bewegung verwendet werden konnen. Sie sind nicht dazu geeignet, die zur Aufgabenerfullung

notwendigen globalen Aspekte der Umwelt in die Bewegungsberechnung mit einzubeziehen. Da-

zu sind nach wie vor Bahnplanungsmethoden erforderlich.

2.1.3 Potentialfelder und Bewegungsmodifizierung

Die Bewegungsgenerierung mit Potentialfeldern (Khatib 1986) kann in Abhangigkeit von der ver-

wendeten Potentialfunktion sowohl als Regelungsalgorithmus als auch als Bahnplanung angesehen

werden und wird deshalb hier gesondert betrachtet. Bei diesem Ansatz wird die Bewegung des Ro-

boters anhand von lokalen Großen, den Potentialen, ermittelt; dies ermoglicht eine ausgesprochen

schnelle Berechnung der Bewegung. Werden diese Potentiale ihrerseits nur durch lokale Betrach-

tung des Umfeldes bestimmt, so kann man von einem Regelungsalgorithmus sprechen. Es gibt

allerdings auch global berechnete Potentiale (Barraquand und Latombe 1991), die den Berech-

nungsaufwand der Bahnplanung mit sich bringen. Solche Ansatze bieten sich in niedrigdimensio-

nalen Konfigurationsraumen zur Bewegungsgenerierung an (Brock und Khatib 1999b).

Bewegungsgenerierung basierend auf lokalen Potentialen hat sich in vielen Anwendungen als

leistungsstark und vielseitig erwiesen (Feder und Slotine 1997). Jedoch leiden diese Methoden

unter lokalen Minima (Latombe 1991), die die erfolgreiche Vollendung der Bewegung verhin-

dern konnen. Um dieses Problem zu uberkommen und die gunstigen Eigenschaften der Potential-

feldmethode mit einer garantierten Bewegungsvollendung zu kombinieren, wurde ein Ansatz zur

Bewegungsmodifizierung von bereits ermittelten Bewegungen konzipiert (elastische Bander oder

elastic bands) (Quinlan 1994). Hier wirken Potentiale auf die gesamte Bahn des Roboters und mo-

difizieren sie zwecks Kollisionsvermeidung. Da auch diese Methoden von der Dimensionalitat des

Konfigurationsraums abhangig sind, geht in hochdimensionalen Konfigurationsraumen die Echt-

zeitfahigkeit verloren. Bei Robotern mit wenigen Freiheitsgraden stellen die elastischen Bander ein

sehr leistungsfahigen Ansatz zur Bewegungsausfuhrung dar, der sowohl auf holonome als auch auf

nicht-holonome Roboter (Khatib 1996) angewendet werden kann.

Ausgehend von derselben Idee, namlich Potentialfelder auf eine Bahn in ihrer Gesamtheit an-

zuwenden, wurden auch Verfahren zur Bahnplanung entwickelt, die sehr positive Ergebnisse er-

zielen. Die BB-Methode (Baginski 1998) kann fur viele fur viele Anwendungen eine Bewegung in

Echtzeit errechnen und ubertrifft dabei in vielerlei Hinsicht probabilistische Methoden zur Bahn-

planung, basiert aber auf Heuristiken, die das Problem von lokalen Minima aufweisen und in be-

stimmten Situationen versagen konnen.

7

2.1.4 Bilderkennung

Bilderkennung (Nalwa 1993; Trucco und Verri 1998) hat die Rekonstruktion von dreidimensiona-

len Szeneninhalten anhand von zweidimensionalen Projektionen dieser Szene zum Ziel. Dies kann

beispielsweise durch die Analyse von Bildpaaren verschiedener, unterschiedlich platzierter Kame-

ras erfolgen oder durch Bewegung relativ zu einer einzelnen Kamera mit anschließender Analyse

der entstehenden Bildsequenz. Durch eigens zu diesem Zweck konzipierte Systeme konnen diese

Berechnungen in Echtzeit ausgefuhrt werden (Kanade et al. 1995). Es ist sogar moglich, zusatz-

lich zur Form, auch die Bewegungen von Gegenstanden anhand von Bildsequenzen zu bestimmen

(Tomasi und Kanade 1992). Um dies zu erreichen, werden eine Vielzahl von Algorithmen, wie

zum Beispiel zur Bildsegmentierung, verwendet, die in der Literatur ausgiebig untersucht wurden

(Forsyth und Ponce 2000). Einen sehr vielversprechender Ansatz zur Rekonstruktion von Sze-

neninhalten stellen so genannte shape from silhouette-Algorithmen dar (Laurentini 1994; Small

2001). Hier werden Szeneninhalte mithilfe von Bildern mehrerer Kameras, die den selben Raum

von unterschiedlichen Standpunkten uberblicken, berechnet.

Shape from silhouette-Methoden eigenen sich besonders gut zur Erfassung einer raumlich aus-

gedehnten Szene (Neumann et al. 1993; Small 2001). So wurden Raume zur zeitbasierten Digita-

lisierung von Szenen mit bis zu funfzig Kameras ausgestattet (Kanade und Vedula 1998). Diese

Idee vorantreibend wird vorgeschlagen, ganze Hauser (Shafer et al. 1998) oder Buroraume (Ras-

kar et al. 1998) mit derartiger Technologie auszustatten, um intelligente Wohn- und Arbeitsraume

zu erschaffen. Dabei wird an Anwendungen gedacht, die Personen erkennen, deren Bewegung

durch eine Reihe von Raumen verfolgen und Arbeitsvorgange oder den Genuss von multimedia-

ler Unterhaltung erleichtern oder unterstutzen. Die Implementierung dieser Ideen beschrankt sich

zum gegenwartigen Zeitpunkt auf einzelne Raume und die Umlenkung von Videosignalen auf den

der Person am nachsten gelegenen Bildschirm. Es ist ein erheblicher Aufwand an Rechenzeit und

zweckgebundenen Geraten erforderlich, um dies zu ermoglichen (Krumm et al. 2000).

2.1.5 Zusammenfassung

Sowohl auf dem Gebiet der Bahnplanung als auch auf dem Gebiet der Regelungsalgorithmen exi-

stieren leistungsfahige Methoden fur spezifische Bewegungsgenerierungsprobleme. Jedoch erfor-

dern realistische Anwendungen außerhalb der Montagestraße eine integrierte Losung der spezi-

fischen Teilprobleme, die von bisherigen Ansatzen nicht geleistet werden kann. So werden zum

Beispiel die Bewegungen von Basis und Roboterarm bei einem mobilen Roboter zumeist getrennt

betrachtet, was eine erhebliche Einschrankung der Anwendbarkeit und Flexibilitat mit sich bringt.

8

Ebenso verhalt es sich bei dem Zusammenspiel von Wahrnehmung und Bewegungsgenerierung.

Es wurden vielseitige Methoden zur Szenenrekonstruktion entwickelt, die nicht notwendigerweise

zur Anbindung an Bewegungsgenerierungsmethoden geeignet sind. Die Bemuhungen, die zu einer

integrierten Losung der hier erwahnten Problemstellung erforderlich sind, erfordern die Entwick-

lung neuartiger Ansatze auf den Gebieten der Bahnplanung, der Bewegungsgenerierung und der

Bilderkennung.

2.2 Eigene Vorarbeiten

2.2.1 Integrierung von Bewegungsaspekten

In den Abschnitten 2.1.1 und 2.1.2 wurde erlautert, dass Bahnplanung dazu benutzt wird, global

kollisonsfreie Bewegungen zu generieren, wahrend Regelungsalgorithmen dazu verwendet wer-

den, messbare lokale Großen nach vorgegebenen Kriterien zu regeln. Das eigenstandige Handeln

von Robotern in dynamischen Umgebungen erfordert sowohl global kollisonsfreie Bewegung als

auch die Regelung anderer Bewegungsaspekte. Die Vorarbeiten auf dem Gebiet der Bewegungsge-

nerierung beruhen auf der Idee, Bahnplanungs- und Bewegungsregelungsmethoden in einem alle

Bewegungsaspekte umfassenden Ansatz zur Bewegungsgenerierung zu vereinen. Dabei wurden

wesentliche Grundlagen fur das Gelingen des beantragten Forschungsvorhabens gelegt. So wurde

eine neuartige Methode zur Bahnplanung entwickelt, die die Abhangigkeit der Berechnungszeit

von der Dimensionalitat des Konfigurationsraums, wie sie bei herkommlichen Bahnplanungsme-

thoden gegeben ist, im Wesentlichen uberkommen konnte. Zudem wurde ein innovativer Ansatz

zur Echtzeitbewegungsmodifizierung demonstriert, der auf einfachste Weise die Regelung beliebi-

ger weiterer Bewegungsaspekte ermoglicht.

2.2.2 Bahnplanung

Um zur Erfullung einer Aufgabe eine optimale oder nahezu optimale Bewegung zu bestimmen,

wird meist die gesamte Umwelt in Betracht gezogen. Diese muss im Konfigurationsraum re-

prasentiert sein, damit eine kollisonsfreie Bewegung ermittelt werden kann. Bei den allermeisten

Planungsaufgaben ist es jedoch weder erforderlich, die Algorithmen auf gesamte Umwelt anzu-

wenden, noch ist es notwendig, fur alle Freiheitsgrade des Roboters eine genaue Trajektorie zu

bestimmen. Die Methodik der dekompositionsbasierten Bahnplanung (decomposition-based mo-

tion planning) (Brock und Kavraki 2000; Brock und Kavraki 2001) hingegen plant nur explizit

fur die Freiheitsgrade der zu erfullenden Aufgabe. Dies ist besonders fur hochredundante Mani-

pulatoren von Bedeutung, weil hier die Spezifizierung samtlicher Freiheitsgrade unter Umstanden

9

gar nicht moglich ist. Aufgrund der damit verbunden Vereinfachung des Planungsproblems kann

dekompositionsbasierte Bahnplanung in hochdimensionalen Konfigurationsraumen und dynami-

schen Umgebungen in Echtzeit ausgefuhrt werden. Die Leistungsfahigkeit der vorgeschagenen

Verfahren wurde anhand von Simulationen uberpruft (Brock und Kavraki 2001). Im Folgenden

wird diese Methode naher erlautert.

Bei der Ausfuhrung einer Bewegung durchstreift ein Roboter ein bestimmtes Volumen im Ar-

beitsraum. Dieses Volumen kann als Reprasentation der Bewegung angesehen werden, die im Kon-

figurationsraum einer eindimensionalen Kurve entsprache. Vergroßert man allerdings das Volumen

in alle Richtungen entsprechend des benachbarten Freiraums, so umfasst diese vergroßerte Volu-

men eine Vielzahl von Trajektorien, von denen eine Teilmenge zur ursprunglichen Bewegung ho-

motopisch ist. Dabei sind alle Trajektorien nur implizit reprasentiert: es ist lediglich bekannt, dass

sich das wahrend Bewegung durchlaufene Arbeitsraumvolumen innerhalb des vergroßerten Volu-

mens befindet, nicht aber wie sich die Gelenkvariablen in Abhangigkeit der Zeit verandern. Diese

implizite Reprasentation ist der Schussel zur Effizienz dieser Algorithmen und ermoglicht gleich-

zeitig eine nahtlose Integrierung mit Regelungsalgorithmen, die zusatzliche Aspekte der Bahnpla-

nung steuern konnen.

Anstatt also eine im Konfigurationsraum beschriebene Bewegung zu ermitteln, bestimmt de-

kompositionsbasierte Bahnplanung ein Arbeitsraumvolumen, genannt Tunnel, welches das Volu-

men umfasst, das vom Roboter wahrend einer Bewegung durchlaufen wird. Raumliche Berechnun-

gen, die von den geometrischen Eigenschaften des Roboters abhangig sind, dienen als Kriterium,

ob der Tunnel auch tatsachlich das gesamte von einer Bewegung durchlaufene Volumen enthalt.

Diese Kriterien konnen zur inkrementellen Berechnung des Arbeitsraumvolumens verwendet wer-

den. Da der Arbeitsraum von konstanter Dimensionalitat ist, sind die Berechnungen unabhangig

von der Anzahl der Freiheitsgrade des Roboters. Durch die inkrementelle Berechnung des Arbeits-

raumvolumens ist es, ebenso wie bei von numerischen Navigationsfunktionen (Barraquand und

Latombe 1991; Rimon und Koditschek 1992), nicht notwendigerweise erforderlich, das gesamte

Umfeld bei der Bahnplanung in Betracht zu ziehen.

Bei dekompositonsbasierter Bahnplanung handelt es sich um einen unvollstandigen Planungs-

algorithmus. Zur Untersuchung der theoretischen Eigenschaften dieser Methode wurden die Kri-

terien der δ-Schwierigkeit von Bahnplanungsproblemen und δ-Vollstandigkeit von Bahnplanungs-

methoden eingefuhrt (Brock und Kavraki 2000). Sie ermoglichen diese Probleme daraufhin zu

bewerten, ob dekompostionsbasierte Bahnplanung erfolgversprechend angewendet werden kann.

Nahezu alle Planungsprobleme in fur Menschen konstruierten Umgebungen erfullen die Kriterien

fur δ-Schwierigkeit; deshalb kann diese Planungsmethode in den meisten realistischen Situationen

10

Anwendung finden. Sollte die Planung mit einem dekompositionsbasierten Planer erfolglos ver-

laufen, so kann man auf einen probabilistisch vollstandigen oder gar einen vollstandigen Planer

zuruckgreifen.

Der Name “dekompositionsbasierte Bahnplanung” leitet sich aus der Tatsache ab, dass das ur-

sprungliche Planungsproblem in zwei Teilprobleme dekomponiert wird: einerseits die Ermittlung

des Arbeitsraumvolumens, welches gemaß der raumlichen Kriterien eine gewunschte Bewegung

enthalt, und andererseits die konkrete Bestimmung der Trajektorie. Letzteres kann sehr einfach

mit Hilfe von Potentialfeldern und Regelungsalgorithmen in Echtzeit und wahrend der Bewegungs-

ausfuhrung bestimmt werden. Auf diese Weise wird die Bewegegungssuche im hochdimensionalen

Konfigurationsraum vermieden. Regelungsalgorithmen werden verwendet, um auf reaktive Weise

in einem kleinen Teilgebiet des Suchraums die eigentliche Trajektorie zu bestimmen. Diese De-

komposition erlaubt eine nahtlose Anknupfung der Bahnplanung an die Bewegungsmodifizierung,

wie weitergehend in Abschnitt 2.2.3 erlautert wird.

2.2.3 Bewegungsmodifizierung

Die meisten Algorithmen zur Bahnplanung fur Roboter ziehen die gesamte Umwelt in Betracht,

um eine kollisionsfreie Bahn zu bestimmen. Wenn ein sich bewegendes Hindernis wahrend der

Ausfuhrung der geplanten Bewegung einen Abschnitt der geplanten Bahn ungultig macht, ist aus

Effizienzgrunden vorteilhaft, nur den ungultig gewordenen Abschnitt neu zu berechnen. Anstatt

eine neue Bahn zu planen, wird die existierende inkrementell in den Abschnitten modifiziert, in

denen Anderungen in der Umwelt dies erforderlich machen. Im Rahmen der Vorarbeiten wurde

die Methode der elastischen Streifen (elastic strip framework) entwickelt, die dieses fur Roboter

mit beliebig vielen Freiheitsgraden ermoglicht (Brock und Khatib 1998; Brock und Khatib 2000;

Khatib et al. 1999).

Ein elastic strip reprasentiert neben einer Trajektorie auch den Freiraum, der sie umgibt. Die

Trajektorie ist verschiedenen Potentialfeldern ausgesetzt. Hindernisse in der Umwelt erzeugen ein

Potential, welches die Trajektorie in sicherer Entfernung halt. Zusatzlich bewirken interne Krafte

eine Kontraktion der Trajektorie. So ergibt sich der Anschein eines elastic strip oder Gummiban-

des: ausgehend von einer beliebigen Bewegung im Arbeitsraum konnen sich annahernde Hinder-

nisse eine Modifizierung der Bewegung bewirken. Sollten die Hindernisse sich wieder entfernen,

nimmt die Trajektorie aufgrund der internen Krafte wieder seine ursprungliche Form an. So wird

die zuvor geplante Bahn inkrementell modifiziert, um kollisionsfreie Bewegung zu ermoglichen.

Anhand des Freiraums kann bestimmt werden, ob eine Modifizierung kollisionsbehaftet ist; in ei-

nem solchen Fall wird sie verworfen und es muss gegebenenfalls eine neue Bahn geplant werden.

11

Elastic strips unterscheiden sich von bisherigen Methoden zur Bewegungsmodifizierung da-

durch, dass die aufwendige Suche nach einer Bewegung im Konfigurationsraum des Roboters

durch eine einfache Projektion von Entfernungsmessungen in den kinematischen Raum ersetzt

wird. Damit ist die Komplexitat der Berechnungen nicht mehr von der Dimensionalitat des Robo-

ters abhangig, sondern von seinen geometrischen Eigenschaften. Dies ermoglicht die Anwendung

von Bewegungsmodifizierung bei Robotern mit beliebig vielen Freiheitsgraden, also gerade dort,

wo Bahnplanung eine besonders komplexe Operation darstellt. Somit ist es prinzipiell moglich,

hochredundante Roboter selbstandig in dynamischen Umgebungen agieren zu lassen, ohne durch

langwierige Bahnplanungsberechnungen limitiert zu sein.

Eine ganz entscheidende Eigenschaft der elastic strips im Bezug auf des hier beschriebene For-

schungsvorhaben ist die Tatsache, dass sie die Miteinbeziehung von beliebigen Optimierungskrite-

rien in die Modifizierung der Bewegung erlauben. Somit sollte es moglich sein, die verschiedensten

erforderlichen Randbedingungen einer Bewegung wahrend der Modifizierung zu gewahrleisten.

Durch die Wahl von geeigneten Regelungsalgorithmen kann sogar sichergestellt werden, dass die

Modifizierung der Bewegung die Ausfuhrung der Aufgabe nicht beeinflusst. Dies ist naturlich nur

dann moglichen, wenn ausschließlich Freiheitsgrade zur Veranderung der Bewegung verwendet

werden, die im Bezug auf die Aufgabe redundant sind. Da sowohl elastic strips als auch dekompo-

sitionsbasierte Bahnplanung fundamental auf einer Darstellung des eine Trajektorie umgebenden

Freiraums beruhen, lassen sich diese beiden Methoden auf ganz naturliche Weise integrieren. Die

Bahnplanung ermittelt eine global optimale Bewegung, die wahrend ihrer Ausfuhrung als elastic

strip reprasentiert wird und somit Echtzeitmodifizierung unter Berucksichtigung der Aufgabe und

unter Einbezug gegebener Randbedingungen erlaubt.

Die Vorarbeiten umfassen eine experimentelle Demonstration der elastic strips mit dem Stan-

ford Assistant Mobile Manipulator, einer Plattform zur mobilen Manipulation (Brock und Khatib

1999a) und verschiedenen humanoiden Robotern (Brock et al. 2002) (siehe auch Abbildungen 2,

3 und 4. Im Rahmen dieser Experimente wurde eine Methode zur Zeitparametrisierung der Bewe-

gung entwickelt, die trotz der Veranderungen der Trajektorie die dynamischen Limitationen des

Manipulators nicht verletzt (Brock 2000). Zudem wurde auch gezeigt, wie elastische Streifen zur

unabhangigen Bewegungskoordination von mehreren Robotern, die denselben Arbeitsraum teilen,

verwendet werden konnen (Brock und Khatib 1999c).

2.2.4 Bilderkennung

Roboter konnen sich nur dann auf sichere Weise in dynamischen Umgebungen fortbewegen, wenn

sie in der Lage sind, die Bewegungen von Hindernissen zu erkennen und darauf zu reagieren. In

12

a) c)

b) d)

Abbildung 2: Diese Abbildungen illustrieren die Echtzeitbewegungsmodifizierung mit elasticstrips unter Beibehaltung der globalen Eigenschaften der Bahn und unter Einbezug samtlicherFreiheitsgrade. Abbildung a) zeigt die ursprunglich geradlinige Trajektorie einer mobilen Platt-form, die wahrend der Bewegungsausfuhrng aufgrund der Bewegung von zwei mobilen Roboternzur Kollisionsvermeidung modifiziert werden musste. Die entsprechende Trajektorie des Greifersist in Abbildung b) zu sehen. Es wird ersichtlich, dass aufgrund der Kollisionsvermeidung die Tra-jektorie des Greifers von der durch die Aufgabe vorgegebenen geradlinigen Bewegung abweicht.Abbildungen c) und d) zeigen das gleiche Experiment. Bei der Bewegungsmodifizierung wurdenjedoch die Randbedingungen der Aufgabe berucksichtigt. Als Resultat bewegt sich der Greifertrotz der weitlaufigen Bewegung der Basis auf einer geraden Linie. Dieses Experiment, welchesauch auf einem realen Roboter durchgefuhrt wurde, demonstriert die Leistungsfahigkeit und Viel-seitigkeit des elastic strip framework.

13

Abbildung 3: Das in Abbildung 2 gezeigte Experiment wurde auch auf einer realen Plattformdurchgefuhrt. Es ist zu sehen, wie die durch einen elastic strip in Echtzeit gesteuerte Roboter mitder Basis einem Hindernis ausweicht, wahrend der Greifer sich entlang einer geraden Linie bewegt.Elastic strips erlaube auf diese Art die konsistente Integrierung von Aufgabe und Kollisionsver-meidung.

den vorhergehenden Abschnitten wurden diejenigen Vorarbeiten erlautert, die Robotern die Reak-

tion auf sich bewegende Hindernisse ermoglichen. Hier soll nun auf die Vorarbeiten eingegangen

werden, die sich auf die Wahrnehmung dieser Hindernisse beziehen. Im Gegensatz zu herkomm-

lichen Anwendungen von Bilderkennung, bei denen die Rekonstruktion von Szeneninhalten im

Mittelpunkt der Bemuhungen steht, stellt sich hier ein viel einfacheres Problem: die Unterschei-

dung zwischen Freiraum und Hindernis. Wahrend der Vorarbeiten wurden theoretische Ansatze

entwickelt, die von dieser Vereinfachung des Problems Gebrauch machen (Brock 2000). Das Ziel

ist es, auf einfache und wartungsfreie Weise den gesamtem Arbeitsraum zu uberwachen, weil nur

dann die Kollisionsfreiheit der Bahn gewahrleistet werden kann. Da nicht davon auszugehen ist,

dass der Roboter zu jedem Zeitpunkt den gesamten Arbeitsraum uberblicken kann, wird davon

abgesehen, sich lediglich auf roboterbasierte Sensoren zu verlassen. Bei der gegebenen Problem-

stellung erscheint es vielversprechender, sich auf die in Abschnitt 2.1.4 erwahnte Entwicklung der

intelligenten Arbeitsraume zu berufen und auch Sensoren, die sich nicht auf dem Roboter befinden,

zu verwenden.

Der im Rahmen der Vorarbeiten vorgeschlagene Ansatz erfordert folglich auch eine Vielzahl

von Kameras, die derartig im Arbeitsraum angebracht werden, dass jeder zu uberwachende Ab-

schnitt sich im Blickfeld von mindestens zwei Kameras befindet. Um das Korrespondenzproblem,

welches bei vielen Szenenrekonstruktionsalgorithmen eine große Herausforderung darstellt, zu

umgehen, sieht der Ansatz die Segmentierung eines Bildes unabhangig von denen der anderen Ka-

14

a) b)

Abbildung 4: Bei diesem Experiment wurde das elastic strip framework auf einen humanoidenRoboter mit 34 Freiheitsgraden angewandt. Auch bei derartig komplexen kinematischen Mecha-nismen erfolgt die Bewegungsmodifizierung in Echtzeit. In dem Experiment senkt sich ein Balkenauf die vorgesehene Bahn des Roboters. Abbildung a) zeigt die modifizierte Bewegung ohne Einbe-ziehung von Randbedingungen. Um das Umfallen des Roboters zu gewahrleisten wurden einfacheKorperhaltungsrandbedingungen in die Modifizierung einbezogen; die sich ergebende Bewegungist in Abbildung b) gezeigt.

meras vor. Das Resultat der Segmentierung von allen Kameras kann dann verwendet werden, um

Volumina im Arbeitsraum zu bestimmen, die Hindernisse enthalten. Dabei wird nicht die genaue

Form der Hindernisse ermittelt, sondern lediglich eine Annaherung. Dieser Ansatz zur Extrahie-

rung von Objektbewegungen aus der Bildsequenz mehrerer Kameras ist im Rahmen der Vorarbei-

ten nicht experimentell uberpruft worden, kann jedoch anhand ahnlicher Ansatze in der Literatur

als vielversprechend eingestuft werden (Small 2001).

2.2.5 Simulationsumgebung

Im Rahmen der Vorarbeiten wurde ein vielseitiger, leistungsfahiger und einfach erweiterbarer

Simulator fur Experimente auf dem Gebiet der Bewegungsplanung entwickelt, der zur Validie-

rung der hier vorgestellten Bewegungsgenerierungsmethoden verwandt wurde und auch bei der

Durchfuhrung dieses Forschungsvorhabens Verwendung finden soll.

2.2.6 Weitere Informationen

Weitere Information und insbesondere erlauternde Animationen und Videoaufzeichungen zu den

hier aufgefuhrten Vorarbeiten auf dem Gebiet der Bewegungsplanung und Bewegungsausfuhrung

sind unter folgendem URL zu finden: http://robotics.stanford.edu/˜oli.

15

3 Ziele und Arbeitsprogramm

3.1 Ziele

In den Jahrzehnten hat sich der Anwendungsbereich von Robotertechnologie im Alltagsleben trotz

erheblicher wissenschaftlicher Fortschritte kaum ausgeweitet. Nach wie vor sind die erfolgreichs-

ten Anwendungen hoch spezialisierte Maschinen, die einen sich wiederholenden Arbeitsablauf

mit großer Genauigkeit und Geschwindigkeit ausfuhren. Das Ziel des vorliegenden Forschungs-

vorhabens ist es, durch die Bereitstellung von neuartigen Bewegungsgenerierungsmethoden die

Erweiterung des Anwendungsbereiches von Robotern zu ermoglichen. Dazu sollen Bewegungs-

generierungsmethoden entwickelt werden, die hochredundante Roboter befahigen, eigenstandig

und in mit Menschen geteilten Umgebungen komplexe, nicht repetitive Aufgaben durchzufuhren.

Die Leistungsfahigkeit solcher Methoden ist in erheblichem Maße von der Fahigkeit abhangig,

Veranderung in der Umwelt wahrzunehmen. Deshalb sollen Aspekte der Perzeption in das For-

schungsvorhaben miteinbezogen werden. Diese Fahigkeiten konnen als notwendige und funda-

mentale Grundlage fur samtliche Anwendungen von komplexen Robotersystemen angesehen wer-

den, die hohe Flexibilitat und Sicherheit erfordern. Solche Anwendungsgebiete reichen vom Haus-

halt uber das Gesundheitswesen bis hin zu interplanetaren Erkundungsmissionen. Die zum Gelin-

gen des Vorhabens zu erreichenden Teilziele sind im Folgenden kurz erlautert.

3.1.1 Bahnplanung

Das Ziel dieses Forschungsvorhabens ist die Entwicklung der algorithmischen Grundlagen zur

Bewergungsgenerierung fur Roboter zum Einsatz in fur Menschen geschaffenen und mit Men-

schen geteilten Umgebungen. Daher sollen Bahnplanungsmethoden fur hochredundante Roboter

entwickelt werden, die den Anforderungen und Bedingungen dieser Umgebungen Rechnung tra-

gen. Dabei muss insbesondere die Fortbewegung auf Beinen in die Planung miteinbezogen werden.

Folglich muss die Bahnplanung unter Berucksichtigung von Schrittfolgen vorgenommen werden.

Die angestrebten Planungsmethoden lassen das Um-, Uber- oder Begehen von Hindernissen zu, um

beispielsweise das Besteigen von Treppen und das Uberschreiten von niedrigen Hindernissen zu

ermoglichen. Neben der Fortbewegung muss eine geplante Bewegung auch verschiedene Teilauf-

gaben reprasentieren konnen. Solche Teilaufgaben umfassen zum Beispiel das Greifen eines Ge-

genstandes, die Bewegung im Kontakt mit der Umwelt, Randbedingungen fur die Bewegung, wie

beim Halten eines Wasserglases, und die aus diesen Teilaufgaben resultierenden Wechselwirkun-

gen mit der globalen Bewegung des Roboters. Weiterhin ist in dynamischen Umgebungen damit zu

16

rechnen, dass eine zuvor geplante Bahn wahrend der Ausfuhrung durch die Bewegung eines Hin-

dernisses ungultig wird. Deshalb wird bei der Zielsetzung besonders Wert auf die Echtzeitaspekte

der Bahnplanung gelegt. Es sollen also alle Aspekte der Bewegung (Aufgabe, Kollisionsvermei-

dung in Echtzeit, Randbedinungen der Fortbewegungsmethode, etc.) gleichzeitig berucksichtigt

werden, anstatt sequentiall oder getrennt zu betrachten, wie es bei bisherigen Verfahren ublich ist.

3.1.2 Integrierung von Randbedingungen bei der Bewegungsgenerierung

Bewegungen, die zur Erfullung komplexer Aufgaben dienen sollen, konnen mit einer Vielzahl von

Randbedingungen behaftet sein. Das Ziel bei der Entwicklung von Algorithmen zur Bewegungs-

generierung ist es, die Erfullung dieser Randbedingungen bei der Bahnplanung und bei der Be-

wegungsmodifizerung zu gewahrleisten. Dabei sollen die folgenden Arten von Randbedingungen

behandelt werden:

Aufgabe: Die auszufuhrende Aufgabe kann eine Vielzahl von Randbedingungen mit sich bringen:

das Halten eines Wasserglases beschrankt beispielsweise zwei Rotationsachsen, das Wischen

eines Fensters zwei Rotationsachsen und eine Translationsrichtung.

Nicht-holonome Randbedingungen: Durch kinematischen Eigenschaften des Roboters konnen

bestimmte Bewegungsrichtungen in gewissen Konfigurationen unmoglich sein.

Schrittfolge: Je nach den kinematischen und dynamischen Eigenschaften des Roboters existieren

Beschrankungen bezuglich der Schrittlange, Steighohe, Kurvenradius usw.

Haltung: Bei hochredundanten Robotern werden nur in seltenen Fallen alle Freiheitsgrade benotigt,

um eine gegebene Bewegung durchzufuhren. Die redundanten Freiheitsgrade konnen dazu

verwendet werden, bestimmte andere Randbedinungen zu erfullen, ohne die Durchfuhrung

der Aufgabe zu unterbrechen. Die drei folgenden Randbedinungen konnen als Spezialfall

einer Haltungsrandbedingung gelten.

Kollisionsvermeidung: Kollisionen konnen durch die Regelung von redundanten Freiheitsgra-

den vermieden werden. Sollte es unmoglich sein, die Kollisionsfreiheit bei der Ausfuhrung

einer Aufgabe zu gewahrleisten, so kann die Aufgabe auch unterbrochen werden, so dass

samtliche Freiheitsgrade zur Kollisionsvermeidung verwendet werden konnen.

Kraftregelung: Bei der Bewegungsmodifizierung einer Bewegung im Kontakt mit einem Hin-

dernis muss den gewunschten Kraften und Drehmomenten am Greifer Rechnung getragen

17

werden. Ebenso muss die Fahigkeit bestehen, das bestehende Weltmodell gemaß der am

Kraftsensor gemessenen Daten zu modifizieren.

Gleichgewicht: Die generierten Roboterbewegungen mussen unter Einwirken von Gravitation

physikalisch durchfuhrbar sein.

Optimierung: Die Verfahren sollen die Berucksichtigung beliebiger Optimalitatskriterien bei der

Bewegungsgenerierung erlauben. Diese konnen zum Beispiel dazu verwendet werden, den

Kraftaufwand der Bewegung zu minimieren oder eine Bewegung moglichst naturlich er-

scheinen zu lassen.

3.1.3 Sensorische Wahrnehmung der Umgebung

Um die Bewegungsgenerierungsmethoden sinnvoll einsetzen zu konnen soll ein Verfahren ent-

wickelt werden, welches mittels geeigneter Sensoren die Klassifizierung des gesamten Arbeits-

raums in Freiraum und Hindernisse vornimmt. Dabei wird kein Wert darauf gelegt, die prazi-

se Form der Hindernisse zu rekonstruieren oder sogar die Trajektorie ihrer Bewegungen zu be-

stimmen. Von fundamentaler Bedeutung ist die Verarbeitungsgeschwindigkeit der Bilddaten, die

schnell genug erfolgen muss, um Bewegungsmodifizierung sinnvoll zu ermoglichen. Zugleich wer-

den Sensorsysteme und Verarbeitungsalgorithmen bevorzugt, die Robustheit bei der Hindernis-

erkennung gewahrleisten konnen.

3.1.4 Bewertung der Ergebnisse

Da das vorliegende Forschungsvorhaben darauf abzielt, Robotern das selbstandige agieren in alltagli-

chen Umgebungen zu ermoglichen, sollen die Ergebnisse gemaß den Anforderungen solcher Um-

felder bewertet werden. Die maßgeblichen Eigenschaften im Bezug auf die Teilprojekte sind hier

kurz erlautert; sie sollen bei der Durchfuhrung des Forschungsvorhaben als Kriterien zur Bewer-

tung der Ergebnisse dienen.

Aufgrund der temporalen Varianz der Umwelt stellt die Echtzeitfahigkeit eine herausragen-

de Anforderung in allen Teilprojekten dar. Die spezifischen Kriterien sind in Abschnitt 3.2.1 fur

die Teilprojekte naher erlautert (siehe auch Abbildung 5 auf Seite 21). Die dort aufgefuhrten

Ausfuhrungsfrequenzen stellen das vorrangige Kriterium zu Beurteilung der Echtzeitfahigkeit dar.

Die Algorithmen zur Bahnplanung sollen gemaß ihrer charakterisierbaren Vollstandigkeit be-

urteilt werden. Die zur Erlangung der Echtzeitfahigkeit notwendigen Abstriche (im Vergleich zur

18

determinisitschen Vollstandigkeit von klassischen Bahnplanungsalgorithmen) mussen zur Fahig-

keit der Bewegungsplanung fur komplexe Aufgaben in einem ausgewogenen Verhaltnis stehen. Zur

Bewertung der Ergebnisse konnen Vergleiche zwischen den Fahigkeiten und dem Berechnungsauf-

wand der entwickelten Methoden und denen von probabilitischen Algorithmen gezogen werden.

Letztere sollen bezuglich der Vielseitigkeit der zu generierenden Aufgaben ubertroffen werden;

dies ist im Arbeitsprogramm (siehe Abschnitt 3.2) unter Bahnplanung und der Integrierung von

Randbedinungen weiter ausgefuhrt. Zum Leistungsvergleich sollen realistische und dynamische

Innenraumszenen, wie zum Beispiel Buroumgebungen, herangezogen werden.

Bei der Integrierung von Randbedinungen und der damit erlangten Verknupfung von globalen

und lokalen Aspekten der Bewegungen erfolgt eine Bewertung der Ergebnisse uber das Ausmaß

der Integration. Ziel ist es, die durch bestimmte Bewegungsaspekte erlangten Fahigkeiten trotz der

Integration zu bewahren. Daruber hinaus sollen etwaig entstehende Konflikte zwischen verschie-

denen Randbedinungen automatisch und sinnvoll aufgelost werden. Zur Bewertung der verschie-

denen Bewegungsfahigkeiten dient der Stand der Forschung auf dem jeweiligen Gebiet, wie zum

Beispiel der Kraftregelung, als Maßstab.

Die Bewertung der Algorithmen zur Wahrnehmung beruht neben der Echtzeitfahigkeit auf

der Genauigkeit der Klassifizierung des Arbeitsraums in Freiraum und Hindernisse. Dabei gilt

es false negatives so gut wie moglich zu vermeiden. Die Haufigkeit von false positives soll die

Bewegungsfahigkeit des Roboters nicht einschranken; sie konnen jedoch ausserhalb der vorge-

sehenen Bahn durchaus in Kauf genommen werden. Ein weiteres Kriterium ist die Anfalligkeit

fur Fehlklassifizierungen aufgrund von Okklusionen. Wiederum gilt es, eine Kollision unter allen

Umstanden zu vermeiden, ohne jedoch dem Bewegungsfreiraum zu weitreichende Beschrankun-

gen aufzuerlegen.

3.1.5 Weiterfuhrende Forschungsarbeiten

Die Befahigung von komplexen Robotersystemen in dynamischem Umfeld eigenstandig, robust

und sicher agieren zu konnen, ermoglicht eine drastische Erweiterung des Anwendungsgebietes

fur Roboter. Folglich lassen sich im Anschluss an das beantragte Forschungsvorhaben durch die

zu entwickelnden Methoden – neben der Weiterentwicklung der resultierenden Methoden – auch

eine Vielzahl von weiteren Arbeitsfeldern erschließen. Dazu zahlen zum Beispiel die Bereitstel-

lung von Leistungsfahigen Schnittstellen zur Aufgabendefinition und Roboterprogrammierung, die

mulitmodale Kommunikation zwischen Roboter und Mensch zur Assistenz und Kooperation, die

Ausstattung von Robotersystemen mit aufgabenspezifischen Fahigkeiten (skills) oder die Integrie-

rung von Aufgabenplanung und logischem Schließen zur Durchfuhrung komplexer Tatigkeiten

19

und zur Reaktion auf das Versagen bei der Durchfuhrung von von Teilaspekten einer Aufgabe.

Auch auf dem Gebiet der Bilderkennung und der intelligenten Arbeitsraume (smart spaces) er-

geben sich weitreichende Moglichkeiten der fortfuhrenden Forschungsaktivitat. Das beantragte

Forschungsvorhaben kann also als Fundament fur weitreichende wissenschaftliche Arbeiten ange-

sehen werden.

3.2 Arbeitsprogramm

3.2.1 Ubersicht

Ein erfolgreicher Abschluss des vorliegenden Forschungsvorhabens erfordert neben der Erfullung

der in Abschnitt 3.1 aufgefuhrten Teilziele auch das koordinierte Zusammenspiel der resultieren-

den algorithmischen Komponenten. Abbildung 5 zeigt einen schematischen Uberblick der ange-

strebten Regelungsarchitektur zur Bewegungsgenerierung. Sie besteht aus vier voneinander abhangi-

gen Regelungsschleifen mit unterschiedlichen Aufgaben und Anforderungen. Bei den folgenden

Erlauterungen ist der Bezug auf Abbildung 5 hilfreich.

Die Aufgabe der ersten Regelungsschleife ist die moglichst exakte Ausfuhrung einer Bewe-

gung, die als zeitvariable Funktion der Gelenkvariablen im Konfigurationsraum gegeben ist. Es ist

wunschenswert die Regelungsschleife mit einer Frequenz von mindestens 1000 Hz zu durchlaufen.

Die dazu erforderlichen Algorithmen sind in der Literatur zu finden (Franklin et al. 1994; Franklin

et al. 1998). Eine weitere Regelungsschleife, jedoch im operationalen Raum, umschließt die erste

Schleife. Ausfuhrungsfrequenzen zwischen 200 und 600 Hz genugen den Anforderungen einer ro-

busten Aufgabenausfuhrung. In dieser Regelungsschleife wird die Ausfuhrung der Aufgabe, wie

beispielsweise die Bewegung des Greifers ohne Orientierungsanderung, sichergestellt. Auch hier

handelt es sich um Regelungsalgorithmen, die in der Literatur bereits eingehend untersucht wurden

(Khatib 1987; Russakow et al. 1995).

In der außersten Schleife der Regelungsarchitektur wird zunachst das Modell der Umwelt durch

Wahrnehmung den wirklichen Gegebenheiten angeglichen. Dieses Weltmodell dient wiederum der

Bahnplanung. Eine realistische Anforderung bezuglich der Planungsfrequenz sind 1 bis 2 Hz. Zur

Realisierung dieser Regelungsschleife sind Arbeiten auf dem Gebiet der Wahrnehmung und der

Bahnplanung, gemaß der in Abschnitt 3.1 dargelegten Ziele erforderlich.

Die Beschreibung des lokalen Freiraums um die bestimmte Bahn herum leitet sich aus dem

Modell der Umwelt ab. Die Integrierung der in Abschnitt 3.1.2 aufgefuhrten Randbedingungen

erfolgt unter Einbezug dieses Freiraums und verwirklicht somit die Integrierung von Bahnplanung

und Regelungsalgorithmen. Diese Regelungsschleife stellt den Hauptunterschied zu herkommli-

20

Lokaler Freiraum

Aufgabe

>1000Hz

200−600Hz

5−10Hz

<2Hz

OperationelleKontrolle

Kontrolle

Bahnplanung

RandbedingungenIntegrierung von

Roboter

UmweltWahrnehmung

Weltmodell

Gelenke

Abbildung 5: Architektur zur Bewegungsgenerierung: Reprasentationen der Umwelt sind als ab-gerundete Rechtecke dargestellt. Im untersten Teil der Abbildung befindet sich die Umwelt, ein-schließlich des Roboters; die zu entwickelnden Algorithmen operieren respektive auf einem Welt-modell, einer Darstellung des lokalen Freiraums in unmittelbarer Umgebung der Trajektorie, einerReprasentation der gegenwartig auszufuhrenden Aufgabe und schließlich auf der Messung derGelenkwinkel. Diesen vier Reprasentationen der Umwelt sind funf algorithmische Komponentengegenubergestellt. Neben der Bahnplanung, der Integrierung von Randbedingungen und der Wahr-nehmung, die den Schwerpunkt dieses Forschungsvorhabens ausmachen und als Rechtecke darge-stellt sind, werden auch eine operationale und eine Gelenkraumregelungskomponente benotigt, diedurch unterbrochene Linien unterschieden werden. Die Funktionweise der Regelungsschleifen istim Text erlautert. Man beachte, dass Pfeile nicht den vollstandigen Datenfluss angeben, sondernzur Veranschaulichung der Regelungsschleifen dienen.

21

chen Regelungsarchitekturen dar. Sie ermoglicht die Generierung von global zielgerichteter Bah-

nen unter Berucksichtigung einer Vielzahl von Bewegungsaspekten. Aus der Anforderung, die

Integrierung etwa funf bis zehn Mal in der Sekunde durchzufuhren, ergibt sich, dass die zur Wahr-

nehmung vorgesehenen Methoden dazu in der Lage sein mussen, das Weltmodell bis zu zehn Mal

in der Sekunde zu akutalisieren.

Aus Abbildung 5 wird auch ersichtlich, warum die Wahrnehmung einen wichtigen Bestandteil

des beantragten Forschungsvorhaben ausmacht. Erst durch eine Aktualisierung des Weltmodells

konnen die beiden außeren Regelungsschleifen geschlossen werden. Dies ist fur die Generierung,

Modifizierung und Ausfuhrung von Roboterbewegungen in dynamischem Umfeld unerlasslich.

Das hier dargestellte Gesamtbild der Regelungsarchitektur macht die Forschungsarbeit in drei

Teilbereichen erforderlich, namlich der Bahnplanung, der Integrierung von Randbedingungen bei

der Generierung und Modifizierung von Bewegungen und der sensorischen Wahrnehmung der

Umwelt. In den folgenden Abschnitten werden die Arbeitsprogramme dieser Teilprojekte naher

erlautert.

3.2.2 Bahnplanung

Dieses Teilprojekt soll auf dem Gebiet der Bahnplanung die Moglichkeit untersuchen, mit Hilfe

von geometrischen Kriterien ein Volumen im Freiraum zu bestimmen, innerhalb dessen eine kol-

lisionsfreie Bahn existiert, die die gestellte Planungsaufgabe erfullt. Dieser Ansatz unterscheidet

sich von der herkommlichen Bahnplanung darin, dass anstatt ein Bahn explizit als Kurve im Kon-

figurationsraum zu bestimmen (Latombe 1991), eine Vielzahl von homotopischen Bahnen implizit

durch die Berechnung eines kollisionsfreies Arbeitsraumvolumen ermittelt werden. Das Ergebnis

einer Planungsoperation ist also nicht eine konkrete Trajektorie, sondern ein Arbeitsraumvolumen,

mittels dessen Regelungsalgorithmen wahrend der Bewegungsausfuhrung in Echtzeit eine Bahn

bestimmt. Folglich ist die Anwendung dieses Ansatzes nur in der in Abbildung 5 dargestellten

oder einer ahnlich strukturierten Regelungsarchitektur sinnvoll. Trotz positiver erster Ergebnis-

se mit diesem Ansatz (Brock und Kavraki 2000), ist im Rahmen dieses Teilprojekts erhebliche

Grundlagenarbeit zu diesem Thema erforderlich.

Modellierung der Umwelt: Aufgrund der Vielseitigkeit der vorgesehenen Aufgaben, die mit der

zu entwickelnden Regelungsarchitektur ausfuhrbar sein sollen, mussen die Anforderungen an ein

Weltmodell erweitert werden. In den meisten Ansatzen zur Bahnplanung wird ein Weltmodell zur

Kollisionserkennung oder Entfernungsberechnung verwendet (Latombe 1991). Modelle zur Be-

rechnung und Erhaltung von Randbedingungen, die sich aus Kontakt zwischen zwei Gegenstanden

22

ergeben, werden im Allgemeinen nur bei der Montageplanung berucksichtigt (Liu und Popplestone

1994). Damit auch fur solche Aufgaben, die eine Beruhrung der Umwelt erfordern, eine Bahn er-

mittelt werden kann, muss das Weltmodell Ubergange zwischen kollisionsfreien Konfigurationen

und solchen in Kontakt erlauben. Dazu ist die Entwicklung so genannter “transparenter” Hinder-

nisse als Bestandteil des Weltmodells geplant (Brock 2000). Solche Hindernisse konnen selektiv

von der Entfernungs- oder Kollisionsberechnung ausgeschlossen werden, wenn gewahrleistet ist,

dass der Kontakt und somit die Kollision zwischen dem Manipulator und dem manipulierten Ge-

genstand durch Regelungsalgorithmen gesteuert wird (Khatib 1987; Featherstone et al. 1999). Die

Einbettung solcher Regelungsalgorithmen in die Regelungsarchitektur ist in Abschnitt 3.2.3 naher

beschrieben.

Geometrische Kriterien fur den Freiraum: Dekompositionsbasierte Bahnplanung basiert sehr

stark auf der Fahigkeit Freiraum im Arbeitsraum zu berechnen, zu bewerten und zu reprasen-

tieren. Dabei soll die Berechnung durch ein Bewertungskriterium gesteuert werden, welches die

Durchfuhrbarkeit einer Bewegung gemaß der gegebenen kinematischen Eigenschaften des Robo-

ters uberprufen kann. Auf diese Art und Weise kann dann inkrementell ein so genannter Tunnel von

Freiraum (Brock und Kavraki 2001) ermittelt werden, der implizit die gesuchte Bahn enthalt. Dabei

muss zwischen der Reprasentation des Tunnels selbst und der des bereits in Betracht gezogenen

Teil des Arbeitsraums unterschieden werden. In den drei Teilbereichen Berechnung, Bewertung

und Reprasentation des Freiraums ist der großte Arbeitsaufwand des Teilprojekts Bahnplanung zu

erwarten.

Bei der Berechnung des Freiraums konnen zwei verschiedene Ansatze verfolgt werden. Ein

Ansatz bezieht die aus der Aufgabe und den kinematischen Eigenschaften resultierenden Rand-

bedingungen umgehend in die Freiraumberechnung mit ein. Als Konsequenz waren die zur Er-

mittlung des kinematisch konsistenten Freiraums erforderlichen Algorithmen relativ aufwendig,

jedoch lassen sich in diesem Fall die Ergebnisse der Vorarbeiten uber elastische Streifen (Brock

und Khatib 2000) direkt anwenden. Ein weiterer Ansatz bestimmt das Volumen des Freiraums

unabhangig von Randbedingungen. Die daraus resultierende, gegenuber des Weltmodells stark

vereinfachte Darstellung des Freiraums kann dann dazu verwendet werden, die Berechnung des

Tunnels unter Einbezug der Randbedingungen durchzufuhren. Dabei kann in Bereichen mit viel

Freiraum auf die Berechnung einiger Randbedingungen verzichtet werden, wenn diese auf triviale

Weise erfullbar sind. Dies bringt insbesondere in fur Menschen konzipierten Arbeitraumen eine

Beschleunigung der Berechnungen mit sich. Beide Verfahren sollten einen Berechnungsaufwand

aufweisen, der proportional zur Komplexitat der lokalen Umgebung ist und zudem nicht darauf

23

ausgelegt sein, den Freiraum in der gesamten Umwelt bestimmen, sondern sich auf solche Gegen-

den beschranken, die zur Losungsermittlung relevant sind (Brock und Kavraki 2001).

In jedem Fall sollte die Berechnung mittels eines inkrementellen Kriteriums erfolgen, da so

komplexe Berechnungen von inverser Kinematik durch einfache, reaktive Regelungsalgorithmen

ersetzt werden konnen. Anstatt eine Suche in einem hochdimensionalen Raum durchzufuhren,

werden Informationen aus dem Arbeitsraum in den Konfigurationsraum des Roboters projiziert.

An diesem Punkt verschmelzen Bahnplanungs- und Regelungsalgorithmen. Bei den Algorithmen

zur Einhaltung der Randbedingungen handelt es sich um Regelungsalgorithmen, die in Abschnitt

3.2.3 eingehend beschrieben werden.

In Abhangigkeit der gewahlten Methode zur Berechnung des Freiraums wird eine angemesse-

ne Reprasentation des bereits untersuchten Freiraumvolumens benotigt, mit Hilfe derer die mehr-

fache Berechnung von Arbeitraumabschnitten vermieden werden kann. Aus der Fahigkeit jeden

Abschnitt nur endlich oft zu untersuchen, ergibt sich, dass die Freiraumberechnung gleichzeitig

dazu benutzt werden kann, eine Navigationsfunktion (Koditschek 1987) zu berechnen, die frei von

lokalen Minima ist.

Sollte die Berechnung des Freiraums die Randbedingungen mit einbeziehen, wurde sich auch

die Reprasentation des bereits untersuchten Freiraums erschweren, da es die Geometrie des Ro-

boters berucksichtigt werden muss. Dies konnte durch die Vereinigung von Arbeitsraum- und

Konfigurationsraumkomponenten erfolgen. Es sind zum Beispiel probabilistische Methoden zur

Freiraumberechnung denkbar, die die Stichprobendichte den lokalen Eigenschaften des Freiraums

anpassen. Diese Methoden konnten als Weiterentwicklung von Arbeiten auf dem Gebiet der pro-

babilistischen Bahnplanung angesehen werden (LaValle 1998; Bohlin und Kavraki 2000; Nielsen

und Kavraki 2000; Foskey et al. 2001). Trotz der zu erwartenden Komplexitat der Reprasentati-

on selbst, erscheint dieser hybride Ansatz aus Arbeitsraum- und Konfigurationsraumkomponenten

sehr vielversprechend.

Bei einer Freiraumberechnung ohne Einbezug der Randbedingungen lassen sich wesentlich

einfachere Methoden anwenden; ein Beispiel fur eine solche Methode ist in den Vorarbeiten zu

finden (Brock und Kavraki 2001). Diese Vereinfachung ist jedoch gegen den erhohten Aufwand

bei der Bestimmung einer gultigen Trajektorie abzuwagen. Diese wurde bei dem zuvor erwahnten

Ansatz automatisch ermittelt werden.

Vollstandigkeit: Da es sich bei dekompositionsbasierter Bahnplanung um einen unvollstandigen

Ansatz handelt, ist eine Charakterisierung der Anwendbarkeit dieser Planungsmethode von großem

Interesse. Mit der Einfuhrung der Konzepte von δ-Schwierigkeit und δ-Vollstandigkeit (Brock und

24

Kavraki 2001) sind bereits aussagekraftige Mechanismen fur diese Untersuchung bereitgestellt.

Diese lassen jedoch die kinematischen Eigenschaften des Manipulators außer Acht und beziehen

sich deswegen nicht auf strukturelle lokale Minima, welche insbesondere bei hochredundanten

Manipulatoren eine wichtige Rolle spielen konnen. Ein manipulatorabhanigens Kriterium sollte

entwickelt werden, da von ihm eine differenzierte Klassifizierung von Planungsproblemen erwartet

werden kann.

Neben den theoretischen Aspekten dieser Fragestellung ist es wunschenswert, Kriterien des

Scheiterns zu ermitteln, die solche Situationen erkennen und klassifizieren, in denen mittels der

vorgeschlagenen Bahnplanungsmethoden die Erfullung der Aufgabe nicht moglich ist. In einem

solchen Fall konnen weitere Planungsmethoden in den Prozess der Bahngenerierung eingebunden

werden. Wird zum Beispiel ein strukturelles lokales Minimum erkannt, konnen spezielle Metho-

den angewendet werden, um aus diesem Minimum zu entkommen (McLean und Cameron 1996).

Idealerweise wurde zu jedem Kriterium des Scheiterns eine adaquate Losungsstrategie entwickelt

werden. Weiterhin soll untersucht werden, ob negative Kriterien existieren, die aufgrund von Ar-

beitsraumberechnungen die Existenz einer Bahn unmittelbar ausschließen konnen (Basch et al.

2001).

Integrierung mit anderen Bahnplanungsmethoden: Die Integrierbarkeit von dekompositions-

basierter Planung und anderen Methoden soll aus zwei Grunden untersucht werden: Dekomposi-

tionsbasierte Verfahren konnen mehrere Male innerhalb einer Sekunde ausgefuhrt werden. Aller-

dings ist aufgrund der δ-Vollstandigkeit ist trotz eines Versagens der Methode die Existenz einer

gultigen Bahn nicht auszuschließen. In einem solchen Fall kann ein probabilistisch vollstandiges

oder deterministisch vollstandiges Planungsverfahren eingesetzt werden, um in bestimmten Ar-

beitsraumabschnitten eine gultige Bahn zu ermitteln. Es wird also eine Verbindung zwischen den

Ansatzen hergestellt, um dekomposionsbasierte Planung bei komplizierten Teilproblemen zu un-

terstutzen. Da jedoch der Rechenaufwand von dekompositionsbasierten im Verhaltnis zu herkomm-

lichen Bahnplanungsansatzen so verschwindend gering ist, ist auch die umgekehrte Situation denk-

bar. So konnen rechenaufwendige Verfahren durch den Einsatz dekompositionsbasierter Verfahren

Informationen uber die Schwierigkeit der Planung in verschiedenen Regionen des Arbeitsraums

sammeln und den Rechenaufwand entsprechend anpassen. Es sollen Moglichkeiten untersucht

werden, diese Verbindungen herzustellen. Dabei ist es einerseits wichtig zu ermitteln, wie pro-

babilistische oder vollstandige Planungsmethoden einfach auf Teilabschnitte des Konfigurations-

raums angewendet werden konnen, die einem schwierigen Arbeitsraumabschnitt entsprechen (Fos-

key et al. 2001); anderseits sollen Ansatze entwickelt werden, um durch dekompositionsbasierte

25

Bahnplanungsmethoden ermittelte Arbeitsrauminformationen in die Berechnungen von konfigura-

tionsraumbasierten Verfahren einzubinden.

Alternative Ansatze: Die hier vorgeschlagene Methode zur Bahnplanung unterscheidet sich

fundamental von bisherigen Ansatzen in der Literatur. Aufgrund des daraus resultierenden Mangels

an inhaltlich verwandter Forschungsarbeit sollen zu Beginn des Forschungsvorhabens zur Sicher-

stellung des Erfolgs auch andere Verfahren zur Bahnplanung in die Untersuchungen einbezogen

werden. Da die vorgesehene Regelungsarchitektur (siehe Abbildung 5) von keinem spezifischen

Bahnplaner abhangig ist, hat ein Paradigmenwechsel in diesem Bereich, abgesehen von einem

erheblich gesteigerten Berechnungaufwand, keine fundamentalen Auswirkungen. Eine herkomm-

liche Methode zur Bahnplanung kann einfach in die Architektur eingebunden werden, indem nach

der Ermittlung der Bahn auch der die Bahn umgebende Freiraum ermittelt wird.

Als mogliche Alternativverfahren werden die lazy probabilistic roadmaps (Bohlin und Kavraki

2000) und die BB-Methode (Baginski 1998) in Betracht gezogen. Bei ersterem handelt es sich um

ein probabilistisches Verfahren, welches erfolgreich auf Probleme mit vielen Freiheitsgraden ange-

wandt wurde. Eine Erweiterung des Verfahrens ware erforderlich, um die hier behandelten Rand-

bedingung in den Planungsprozess mit einzubeziehen. Das zweite Verfahren, die BB-Methode, ist

ein inharent unvollstandiges Verfahren, bei dem die Planung aufgrund von lokalen Minima schei-

tern kann; es wurde bereits auf mobile Manipulatoren angewendet, konnte allerdings fur relative

einfache Problemstellungen Bewegungen nicht in Echtzeit generieren. Hybride Planungsmethoden

(Foskey et al. 2001), die aus arbeitsraumbasierten Methoden und einem dieser Alternativverfahren

bestehen, stellen einen weiteren Ansatz dar.

3.2.3 Integrierung von Randbedingungen bei der Modifizierung von Bewegungen

Im Rahmen dieses Teilprojekts sollen reaktive Regelungsalgorithmen entwickelt werden, die fur

hochredundante Roboter eine Echtzeitintegrierung von Randbedingungen vornehmen. Eine Kopp-

lung mit dem in Abschnitt 3.2.2 beschriebenen Verfahren zur Bahnplanung gemaß der vorgesehe-

nen Regelungsarchitektur erlaubt dann die Ausfuhrung von kollisionsfreien, mit Randbedingungen

behafteten Bewegungen fur Roboter mit vielen Freiheitsgraden in dynamischen Umgebungen.

Reprasentation der Bahn: Herkommliche Bahnplanungsmethoden reprasentieren die Bahn fur

einen Manipulator als Sequenz diskreter Roboterkonfiguraionen. Die Konfigurationen sind so ge-

wahlt, dass eine einfach zu ermittelnde, kollisionsfreie Bewegung zwischen ihnen existiert. Da bei

26

der hier vorgeschlangenen Regelungsarchitektur Bahnplanung und Regelungsalgorithmen in en-

ger Verbindung miteinander stehen und zusatzlich verschiedenste Randbedingungen berucksich-

tigt werden sollen, muss eine umfassendere Darstellung einer Bewegung entwickelt werden. Es ist

erforderlich, solche Konfigurationen zu kennzeichnen, die einem kritischen Ereignis beim Bewe-

gungsablauf entsprechen. Ein Beispiel sind Konfigurationen, bei denen ein Bein angehoben oder

aufgesetzt wird. Solche Konfigurationen signalisieren eine Veranderung in den Randbedingungen.

Zusatzlich sind sie mit bestimmten Beschrankungen, wie Schrittlange oder Steighohe behaftet,

deren Einhaltung von den Regelungsalgorithmen entlang der gesamten Trajektorie gewahrleistet

werden muss. Des Weiteren konnen ich die auszufuhrende Aufgabe und die sich daraus erwach-

senden Bewegungsbeschrankungen wahrend einer Bewegung andern. Nach dem Ergreifen eines

Wasserglases, zum Beispiel, gelten andere Randbedingungen, als zuvor. Dies muss als Teil der

Bewegung in Abhangikeit von anderen Ereignissen darstellbar sein. Der Ansatz von kritischen

Konfigurationen (Brock 2000) verspricht auch hier zur Erweiterung der Bahnreprasentation verall-

gemeinert werden zu konnen.

Da die meisten Randbedingungen durch inkrementelle Annaherung eingehalten werden, kann

es vorkommen, dass einige von ihnen zeitweise nicht erfullt sind. Die Reprasentation der Bahn

muss solche Abschnitte als inkonsistent Ausweisen konnen. Die Zeitparametrisierung bei der Be-

wegungsausfuhrung sollte dann so ermittelt werden, dass diese Abschnitte erst nach Wiederher-

stellung aller Randbedingungen durchlaufen werden.

Integrierung von verschiedenen Randbedingungen: Bei redundanten Robotern ist das Verhalt-

nis zwischen Kraften und Drehmomenten im Arbeitsraum und im Konfigurationsraum durch

Γ = JT (q)F+[

I − JT (q)JT (q)]

Γ0 (1)

gegeben (Khatib 1993); dabei bezeichnet Γ den Vektor die Krafte und Drehmomente im Konfi-

gurationsraum, J die Funktionalmatrix (Jacobian) in Bezug zur auszufuhrenden Aufgabe, q den

Vektor der Gelenkvariablen, F den Vektor der aufgabendefinierenden Krafte und Drehmomente

im Arbeitsraum, J die dynamisch konsistente, generalisierte inverse Matrix (Khatib 1995) zu J ,

und Γ0 einen weiteren Vektor von Gelenkkraften und Gelenkdrehmomenten. Die Große Γ0 wird

in den Nullraum N T (J) = I − JT (q)JT (q) von J projiziert und beeinflusst somit lediglich die

bezuglich der Aufgabe redundanten Freiheitsgrade. Auf diese Weise lassen sich die durch F re-

prasentierte Aufgabe und weitere unter Γ0 zusammengefasste Randbedingungen integrieren. Dies

gilt solange, bis der zur Erhaltung der Randbedingungen erforderliche Vektor Γ0 annahernd or-

thogonal zum Nullraum von J ist. In einem solchen Fall nahert sich der Betrag seiner Projektion

27

in den Nullraum∥

∥N T (J)Γ0∥

∥ dem Nullvektor an: die Randbedingungen konnen nicht mehr in-

nerhalb des Nullraums der Aufgabe erfullt werden. Damit auch unten solchen Bedingungen ein

vorhersehbares und regelbares Verhalten des Manipulators gesichert ist, muss der Integrierungsan-

satz um das Ein- und Ausblenden und die Prioritisierung von Randbedingungen erweitert werden.

Dies kann erreicht werden, indem zwischen dem durch Gleichung 1 und dem durch Γ = J T (q)F

beschriebenen operationalen Regelungsverfahren gewechselt wird. Bei dem Ubergang wird die

Aufgabenerfullung temporar aufgegeben, da sie nicht mit der Erfullung der Randbedingungen ver-

traglich ist. Es sollen Kriterien entwickelt werden, die diesen Wechsel so steuern, dass sich stabiles

und aufgabenorientiertes Verhalten ergibt. Ein moglicher Ansatz regelt den Wechsel in Abhangig-

keit des Verhaltnisses von ‖Γ0‖ zu ‖N T (J)Γ0‖ (Brock et al. 2002). Weitere denkbare Verfahren

geben die Randbedinungen stufenweise auf, um die Einhaltung moglichst vieler konsistenter Rand-

bedingungen zu ermoglichen. Dazu muss analysiert werden, wie sich bestimmte Randbedinungen

untereinander beeinflussen.

Randbedingungen - generelles Vorgehen: Mit Hilfe des oben beschriebenen Ansatzes konnen

eine unbeschrankte Anzahl von Randbedingungen durch die Spezifizierung von Γ0 in die Bewe-

gungsregelung miteinbezogen werden. Fur Randbedingungen Ri, die sich ausschließlich auf eine

einzelne Konfiguration des Manipulators beziehen, ergibt sich Γ0 =∑

iΓRi . Die Drehmoments-

und Kraftvektoren ΓRi sind durch den Gradienten der mit den Randbedingungen assoziierten

Potentialfunktionen VRi bestimmt: ΓRi = −∇VRi . Es ist also lediglich notwendig, die mit der

Randbedingung Ri assoziierte Potentialfunktion VRi zu ermitteln. Aufgrund der Echtzeitanforde-

rung muss der Gradient dieser Funktion sehr schnell ermittelbar sein. Randbedingungen, die Be-

schrankungen auf das Verhaltnis zwischen zwei verschiedenen Konfigurationen mit sich bringen,

mussen getrennt behandelt werden. Notwendige Modifikationen der beteiligten Konfigurationen

werden jedoch wiederum durch obigen Ansatz in die Bewegungsgenerierung integriert. Im Fol-

genden sind die bei diesem Forschungsvorhaben einbezogenen Randbedingungen und die zur ihrer

Behandlung notwendigen Arbeitsschritte erlautert.

Randbedingungen der Aufgabe: Die Aufgabe fließt in die Integrierung von Randbedingungen

gemaß Gleichung 1 durch die Definition von F und J ein. Neben der oben beschriebenen Bahn-

reprasentation und den zuvor erwahnten Kriterien zur Ein- und Ausblendung der Aufgabe werden

keine zusatzlichen Verfahren benotigt. Der zu betreibende Aufwand beschrankt sich auf die Inte-

grierung existierender Verfahren.

28

Nicht-holonome Randbedingungen: Nicht-holonome Randbedingungen werden am haufigsten

bei der Mobilitat eines Manipulators angetroffen. Sie beziehen sich somit auf das Verhaltnis zwi-

schen raumlich aufeinanderfolgenden Konfigurationen. Bei holonomer Bewegung konnen an dem

Manipulator wirkende Krafte zur Bewegungsmodifizierung einfach in den Konfigurationsraum

projiziert werden. Um Bewegungsmodifizierung auch bei der nicht-holonomen Fortbewegung zu

ermoglichen, mussen Methoden entwickelt werden, die nur mit den Randbedingungen vertragli-

che Modifizierung vornehmen. Solche Methoden wurden fur lenkbare Wagen bereits entwickelt

(Khatib und Jaouni 1996) und konnen integriert werden. Die Koordinierungsfahigkeit von nicht-

holonomen und aufgabenbedingten Randbedingungen konnen bei der Bewegungsgenerierung durch

Optimalitatsfunktionen ausgedruckt werden. Bei gehender Fortbewegung mussen jedoch zusatzli-

che Aspekte in Betracht gezogen werden. So findet zum Beispiel eine diskrete Veranderung von

Schrittmustern statt, wenn die Bahn so stark gebogen ist, dass ein Ubergang von geradem Lau-

fen auf seitliches Schreiten erfolgen muss. Nicht-holonome Randbedingungen fur Fortbewegung

mit Beinen konnen also den Wechsel von Bewegungsmodi hervorrufen. Es ist nicht gewiss, ob

im Rahmen der Untersuchungen hierzu generelle Verfahren entwickelt werden konnen oder ob die

nicht-holonomen Beschrankungen der verschieden Fortbewegungsarten getrennt behandelt werden

sollen.

Randbedingungen der Schrittfolge: Innerhalb eines gegebenen, durch Beine charakterisierten

Bewegungsmodus mussen bestimmte Beschrankungen bezuglich der Schrittfolge und Schrittlange

eingehalten werden. Hierzu ist geplant den Ansatz der internen Krafte beim elastische Streifen

(Brock 2000) zu erweitern, um die Anwendung auf kritische Konfigurationen entlang der Bahn

zu ermoglichen. Diese sollen die Einhaltung der aus der Fortbewegungsmethode erwachsenden

Randbedingungen gewahrleisten.

Randbedingungen der Haltung: Randbedingungen bezuglich der Haltung des Roboters konnen

dazu dienen, die Bewegung des Roboters nach asthetischen oder optimierenden Gesichtspunkten

zu beeinflussen. Zu ersterem ist es hinreichend, ein entsprechendes Potential gemaß der bevor-

zugten Gelenkpositionen zu ermitteln. Fur letzteres konnen die verschiedensten Kriterien ermittelt

werden, deren Entwicklung jedoch nicht in die ausgefuhrten Arbeiten einfließen soll. Das For-

schungsvorhaben beschrankt sich auf die Entwicklung von Methoden zur Integrierung beliebiger

Haltungspotentialfunktionen, auf das Vermeiden von Gelenkbeschrankungen (joint limits) und von

Eigenkollisionen des Roboters. Geeignete Potentiale fur verschiedene Haltungsvorgaben konnen

aus anderen Arbeiten ubernommen werden (Sentis 2001).

29

Randbedingungen der Kollisionvermeidung: Die Methoden zur Kollisionsvermeidung mit der

Umwelt konnen aus den Vorarbeiten ubernommen werden (Brock 2000).

Randbedingungen durch Kontakt: Die durch Kontakt mit der Umwelt entstehenden Randbe-

dingungen konnen direkt entsprechende Regelungsalgorithmen (Khatib 1987; Featherstone et al.

1999) eingehalten werden. Neben der oben beschriebenen Bahnrereprasentation und er Erweite-

rung des Weltmodells werden keine zusatzlichen Verfahren benotigt. Der zu betreibende Aufwand

beschrankt sich auf die Integrierung existierender Verfahren. Dabei ist anzumerken, dass die Rege-

lungsalgorithmen, die den Ubergang zwischen Bewegung im Freiraum und Bewegung im Kontakt

steuern nicht Gegenstand des Forschungsvorhabens sind. Es wird die vereinfachende Annahme ge-

macht, dass sowohl im Manipulator, als auch in der Umwelt Flexibilitaten vorhanden sind, die es

erlauben, die damit verbunden Problemstellungen zu ignorieren. Auf dem Gebiet der Bewegungs-

planung fur den Ubergang von zwischen Kontakt und Freiraum mussen das Weltmodell und die

Reprasentation der Bewegung wie oben ausgefuhrt erweitert werden.

Randbedingungen der Erhaltung des Gleichgewichts: Die Erhaltung des Gleichgewichts nimmt

eine besondere Rolle unter den Randbedinungen ein, da die Einhaltung zu jedem Zeitpunkt abso-

lut notwendig ist.3 Es existieren verschieden Ansatze, um die Stabilitat bei gehender Fortbewe-

gung zu berechnen, wie zum Beispiel die Methode des zero moment point (ZMP) (Vukobratovic

et al. 1970). Es soll versucht werden, eine dieser Methoden mit dem operationalen Regelungsan-

satz zu vereinen. Die Regelung im operationalen Raum geht jedoch bei Bewegungen des Greifers

von beliebig großen, zulassigen Reaktionskraften an der Basis des Roboters aus. Diese Annahme

ist nur bei einem stationaren, verankerten Roboter zulassig. Demzufolge mussen Methoden ent-

wickelt werden, die eine programmatische Beschrankung dieser Reaktionskrafte zulassen. Dies

muss durch eine konservative Regelung des Gleichgewichts erfolgen und sollte mit einer Sonder-

stellung dieser Regelung in Bezug auf andere Randbedingungen verbunden sein.

3.2.4 Sensorische Wahrnehmung der Umwelt

Es soll ein Verfahren zur Echtzeiterkennung von Hindernissen im einem weitlaufigen Arbeits-

raum entwickelt werden. Dieses dient, der Regelungsarchitektur entsprechend, zur Ruckkopplung

von Veranderungen in der Umwelt an Bahnplanung und Bewegungsmodifizierung. Daher ist es

von großer Bedeutung die Perzeptionsalgorithmen so zu konzipieren, dass die Frequenz der Rege-

lungsschleife fur die Integrierung von Randbedingungen eingehalten wird. Dabei ist eine genaue3Bisher gibt es keinen humanoiden Roboter, der das Aufstehen nach einem Sturz beherrscht.

30

Rekonstruktion der wahrgenommenen Gegenstande nicht erforderlich, es soll lediglich eine Un-

terscheidung von Freiraum und Hindernis ermittelt werden. Eine weitere Anforderung ist die Ein-

fachheit der Kalibrierungsverfahren und die Robustheit der Algorithmen gegen Ungenauigkeiten

in der Wahrnehmung. Eine sinnvolle Ruckkopplung kann nur dann erfolgen, wenn der gesamte

Arbeitsraum uberwacht wird. Insofern ist es unter Umstanden erforderlich, eine große Anzahl von

Sensoren in mehreren abgetrennten Raumen zu installieren. Dies ist nur dann realistisch, wenn die

Kalibrierung außerst einfach durchzufuhren ist. Da es in von Menschen benutzten Arbeitsraumen

zu der Veranderung der Orientierung oder Position eines Sensors kommen kann, sollten die zu

entwickelnden Algorithmen die Kalibrierung auch wahrend des Betriebs erlauben.

Die Grundidee des zu entwickelnden Verfahrens beruht auf shape from silhouette-Methoden:

Ein Objekt wird von mehreren Kameras erfasst. Durch Segmentierung wird sein Abbild in den

Bildsequenzen der verschieden Kameras vom Hintergrund getrennt. Projiziert man die sich daraus

ergebenden Teile der Abbilder durch die optischen Zentren zuruck in den Raum, so ergeben sich

Volumen in Form von verallgemeinerten Kegeln mit Scheitel im jeweiligen optischen Zentrum.

Das beobachtete Objekt befindet sich innerhalb der Schnittmenge samtlicher projizierter Kegel,

der so genannten visual hull. Dabei wird die Ausdehnung des Hindernisses uberschatzt, was jedoch

zur Kollisionsvermeidung akzeptabel ist. Bei diesem Teilprojekt liegt der Schwerpunkt darin, ein

außerst effizientes und robustes Verfahren zu entwickeln, welches in die gewahlte Regelungsarchi-

tektur vervollstandigt.

Wahl des Segmentierungsverfahrens: Die Wahl des Segmentierungsverfahrens hat entschei-

denden Einfluss auf die Echtzeitfahigkeit der Wahrnehmung. Da in der Literatur ist eine Vielzahl

von Ansatzen zu finden sind (Nalwa 1993; Forsyth und Ponce 2000), sollen im Rahmen dieses

Forschungsvorhabens keine neuartigen Verfahren entwickelt werden. Es konnen zum Beispiel die

Grauton- oder Farbeigenschaften des Bildes zur Segmentierung verwendet werden (Prewitt 1970;

Beveridge et al. 1989). Andere Verfahren partitionieren das Bild aufgrund bestimmter Eigenschaf-

ten und fassen dann Gegenden mit ahnlichen Eigenschaften zusammen (Horowitz und Pavlidis

1987) oder segmentieren das Bild durch die Bestimmung des optischen Flusses (Irani et al. 1994;

Barron et al. 1994). Es lassen sich zudem zahlreiche weitere Ansatze und weiterfuhrende Arbeiten

finden (Nalwa 1993; Trucco und Verri 1998). Auch zur dynamischen Aktualisierung einer Segmen-

tierung sind Verfahren entwickelt worden (Kass et al. 1988; Blake et al. 1993). Ein entscheidender

Vorteil des vorgeschlagenen Verfahrens ist, dass keine Tiefeninformation zur Bildinterpretation

verwendet werden muss, wie es zum Beispiel bei Stereopsis der Fall ist. Stereopsis macht ei-

nerseits Stereokameras erforderlich, deren Kalibrierung sehr aufwendig sein kann. Des Weiteren

31

musste bei diesen Methoden das sehr rechenintensive und oft unrobuste Korrespondenzproblem

(Tomasi und Manduchi 1998) gelost werden. Daher erscheinen bild- und bewegungsbasierte Ver-

fahren fur den gewahlten Ansatz vielversprechender.

Wahl der Sensoren: Die Wahl der Sensoren ist von der Wahl des Segmentierungsverfahrens

abhangig. Es sollen jedoch keine aktiven Sensoren, so wie Radar, Laser oder strukturierte Lichtpro-

jektion in Kombination mit Kameras verwendet werden. Nur durch passive Sensoren ist gewahr-

leistet, dass die mit Menschen geteilten Arbeitsraume nicht beeinflusst werden. Da bild- und bewe-

gungsfeldbasierte Verfahren zur Segmentierung verwendet werden sollen, erscheint die Wahl von

digitalen Farbkameras als angebracht.

Kalibrierung der Kameras: Die zu entwickelnde Kalibrierungsmethode soll die extrinsischen

Parameter der Kameras ermitteln; die intrinsischen Kenngroßen sollen als bekannt angenommen

werden.4 Generell erfolgt die Kalibrierung von Kameras durch die Losung von Projektionsglei-

chungen, die bekannte Punkte im Arbeitsraum zu ihren Abbildern in Verhaltnis setzen und die

Kameraparameter als Variablen enthalten. In der Literatur ist erlautert, wie die geometrischen und

algebraischen Randbedingungen, die fur von mehreren Blickpunkten aus betrachtete Szenenmerk-

male gelten, auf die Parameter der Kameras ruckschließen lassen (Forsyth und Ponce 2000).

Es sollen Verfahren entwickelt werden, welche die Genauigkeit der Kalibrierung mit der An-

zahl der sich zwischen mehreren Sensoren uberschneidenden Beobachtungen erhohen. Da nicht

notwendigerweise alle Sensoren identische Teile eines Raumes wahrnehmen konnen, sollen die

Randbedingungen auch transitiv verbreitbar sein. Uberschneidet sich das Blickfeld von Sensoren

A und B, die durch eine Beobachtung kalibriert wurden, so sollten die Algorithmen in der La-

ge sein, mit Hilfe einer gemeinsamen Beobachtung von Sensoren B und C einen inkrementellen

Abgleich der Kenngroßen durchzufuhren. Es wird weiterhin beabsichtigt, diese Algorithmen so

zu erweitern, dass die plotzlichen Veranderungen der extrinsischen Parameter einer Kamera, wie

zum Beispiel durch menschlichen Eingriff, erkannt und korrigiert werden. Die Auswirkungen auf

die Hinderniserkennung sind dabei durch die Redundanz der Sensoren zu minimieren. Auf diese

Weise wird gewissermaßen eine kontinuierliche Kalibrierung der Kameras erreicht.4Bei der experimentellen Verifizierung des zu entwickelnden Ansatzes, mussen die Kameras naturlich auch gemaß

der intrinsischen Parameter geeicht werden; dies erfolgt jedoch nur einmalig und durch wohlbekannte Methoden. Da-her sind intrinsische Kenngroßen nicht Gegenstand des Forschungsvorhabens. Der Ansatz des beschriebenen Wahr-nehmungsverfahrens lasst zudem eine Robustheit gegen die Ungenauigkeit von intrinsischen Kenngroßen erwarten.

32

Schnittmengenbestimmung: Um die Erkennung von Hindernissen zu erlauben, soll die Schnitt-

menge mehrerer durch Segementierung ermittelten generalisierten Kegel errechnet werden. Die

Kegel sind durch das optische Zentrum der jeweiligen Kamera und eine Bildregion definiert. Es

muss eine Darstellung dieser Kegel ermittelt werden, die die Schnittmengenberechnung auf ein-

fache Weise zulasst. In der Literatur werden hierzu zumeist volumetrische Reprasentationen des

Raums verwendet (Szeliski 1990). Diese Methoden sind sehr rechenintensiv. Im Rahmen des For-

schungsprojekts soll der Versuch unternommen werden, robuste geometrische Verfahren zu ent-

wickeln, die eine visuelle Hulle (Matusik 2001) ermitteln. Dabei kann auf ein breites Spektrum

geometrischen Algorithmen zuruckgegriffen werden (Goodman und O’Rourke 1997). Da die Re-

prasentation der Hindernisse hauptsachlich zur Entfernungsberechnung im Weltmodell verwendet

wird, sollte dem Gesichtspunkt der raumlichen Koharenz, die von vielen Entfernungsberechnungs-

methoden zur Beschleunigung der Entfernungsermittlung verwendet wird (Lin 1993; Ong und

Gilbert 1997), besondere Aufmerksamkeit gewidmet werden. Dazu ist es erforderlich, die Berech-

nungen in aufeinander folgenden Zeitabschnitten miteinander in Bezug setzen zu konnen.

Die Berechnung der Schnittmenge kann auch von Modellen der wahrgenommenen Gegenstande

unterstutzt werden. Es soll insbesondere im Zusammenhang mit Okklusionen (siehe nachster Ab-

schnitt) und Kalibrierung untersucht werden, ob modellbasierte Ansatze die Verlasslichkeit der

Verfahren erhohen.

Okklusion: Der Blick einer Kamera auf ein bestimmtes Objekt kann durch andere Gegenstande

verdeckt werden. In einer solchen Situation sollte naturlich das verdeckte Hindernis weiterhin im

Weltmodell angezeigt und nach Moglichkeit auch dessen Position aktualisiert werden. Es ist be-

absichtigt Methoden zu entwickelt, die dieses Problem losen oder dessen Effekt zu minimieren.

Am einfachsten ware dies durch eine sehr hohe Anzahl von Kameras zu losen. Solange ein Objekt

vollstandig von mindestens zwei Sensoren erfasst werden kann, deren optische Achsen in einem

angemessenen Winkel angeordnet sind, mussen etwaige Okklusionen anderer Kameras nicht not-

wendigerweise in Betracht gezogen werden. Sollte aber ein Objekt von nur einer Kamera, nur von

Kameras mit nahezu parallelen optischen Achsen oder von einer oder mehreren Kameras nur un-

vollstandig erfasst werden, so ist die Fahigkeit zur Ermittlung des Ausmaßes des Gegenstandes

beeintrachtigt. Bei teilweiser Okklusion kann versucht werden, das durch den Gegenstand verur-

sachte Bildsegment des Kamerabildes aufgrund von vergangenen Messungen zu vervollstandigen.

In einem konservativeren Ansatz kann eine obere Schranke fur die Ausmaße des Hindernisses

aus vergangenen Messungen ermittelt werden. Die Folgen einer vollstandigen Okklusion oder par-

alleler optischer Achsen zu beschranken ist weitaus schwieriger. Es sollen Methoden entwickelt

33

werden, die die Auswirkungen von Okklusionen minimieren. Diese konnen zusatzliche Sensoren

des Roboters (siehe nachster Abschnitt) in die Berechnungen einbeziehen, spezielle Konturbestim-

mungsverfahren bei der Ermittlung der Silhouette verwenden (Kass et al. 1988) oder ein Modell

des wahrgenommenen Gegenstandes erstellen.

Einbeziehung von Sensoren des Roboters: Eine sehr interessante Moglichkeit sowohl die Ge-

nauigkeit der Schnittmengenbestimmung zu erhohen als auch die Auswirkungen von Okklusionen

zu verringern ist die Einbeziehung von Sensoren des Roboters. Es soll untersucht werden, wie un-

ter Berucksichtigung der gegenwartigen Position und auszufuhrenden Aufgabe des Roboters eine

moglichst gunstige Position und Orientierung fur die robotermontierte Kamera ermittelt werden

kann. Dabei ist darauf zu achten, dass die Position und Orientierung des Roboters ausreichend

genau bekannt ist. Dies kann durch Relokalisierung anhand von Robotersensoren oder der im Ar-

beitsraum installierten Kameras erfolgen.

Platzierung und Anzahl der Sensoren: Zur akkuraten Schnittmengenbestimmung und zur Ver-

meidung von Okklusionen sind die Anzahl und Platzierung der Kameras von ausschlaggeben-

der Bedeutung. Aufgrund der moglichen Vielfaltigkeit und Variabilitat von Arbeitsumgebungen

erscheint es sehr schwierig, allgemeinene Verfahren zur Bestimmung dieser Parameter zu ent-

wickeln. Solche Verfahren sollen nicht Gegenstand der Untersuchungen sein. Eine interessan-

te Fragestellung ist jedoch auch, welche der vielen Kamerabilder in Betracht gezogen werden

mussen, um Rechenzeit und Genauigkeit der Hindernisbestimmung gegeneinander abzuwagen.

Dieser Aspekt soll im Rahmen der Echtzeitanforderung der Regelungsarchitektur untersucht wer-

den.

3.2.5 Experimentelle Verifizierung

Fur die Teilprojekte 3.2.2 zur Bahnplanung und 3.2.3 zur Integration von Randbedingungen soll

wahrend der Entwicklung die im Rahmen der Vorarbeiten entwickelte Simulationsplattform zur

Verifizierung der entwickelten Verfahren verwendet werden. Die Verfahren zur Wahrnehmung

werden ausschließlich experimentell erprobt. In einem ersten Integrationsschritt werden dann die

Wahrnehmungsalgorithmen mit der Simulationsumgebung gekoppelt. Erst wenn diese Tests er-

folgreich abgeschlossen worden sind, wird erwogen, die gesamte Regelungsschleife auf einen

wirklichen Roboter anzuwenden.

Fur die experimentelle Verifikation der gesamten Regelungsarchitektur (siehe Abbildung 5 auf

Seite 21) werden hochentwickelte Robotersysteme benotigt. Insbesondere kann die Leistungsfahig-

34

keit nur auf Plattformen mit sehr vielen Freiheitsgraden uberpruft werden. Zudem ist es erforder-

lich, die Fahigkeit der Manipulation mit zweibeiniger Fortbewegung zu kombinieren. Folglich

wird ein humanoider Roboter mit Beinen fur die Versuche benotigt. Zum gegenwartigen Zeitpunkt

existieren keine solchen Systeme in Deutschland. An der Stanford Univerisitat wird jedoch in-

nerhalb des kommenden Jahres ein Asimo Roboter von Honda (siehe Abbildung 1 auf Seite 4)

zu Experimentierzwecken zur Verfugung stehen. Daher wird es vorgezogen, die abschließenden

experimentellen Arbeiten am Ende des Forderungszeitraums mit allen Projektteilnehmern dort

durchzufuhren (siehe auch Abschnitt 4.4 uber Reisemittel auf Seite 38). Aufgrund der Vertraut-

heit des Antragstellers mit dieser Arbeitsumgebung, ist eine schnellstmogliche Abwicklung der

Experimente gewahrleistet.

Zur Vorbereitung dieser Reise sind vorlaufige Experimente mit den an der aufnehmenden Insti-

tution vorhandenen Roboterplattformen vorgesehen. Des weiteren sollen im Rahmen eines engen

Kontakts mit dem Robotiklabor an der Stanford Universitat vorbereitende Experimente via Inter-

net durchgefuhrt werden. Eine kontinuerliche Kooperation mit Stanford ermoglicht zudem den

Wissenstransfer mit einem der fuhrenden Robotiklabore auf diesem Forschungsgebiet.

3.2.6 Zeitplan

Der Zeitplan fur das Forschungsvorhaben ist in Tabelle 1 zusammengefasst. Die Bezeichnung der

Arbeitsschritte beziehen sich auf die entsprechenden Paragraphen in den Abschnitten 3.2.1 - 3.2.4

der Beschreibung des Arbeitsprogramms. Zeitliche Uberschneidungen entsprechen inhaltlichen

Abhangigkeiten der Arbeitsschritte. Die Teilprojekte werden von jeweils einem Mitarbeiter der

Forschungsgruppe getragen.

3.3 Untersuchungen am Menschen

Es sind keine Untersuchungen am Menschen vorgesehen.

3.4 Tierversuche

Es sind keine Tierversuche vorgesehen.

3.5 Gentechnologische Experimente

Es sind keine gentechnologischen Experimente vorgesehen.

35

Zei

tpla

n

Jahr

1Ja

hr2

Jahr

3Ja

hr4

Bahnplanung

Mod

ellie

rung

der

Um

wel

tU

nter

such

ung

der

Vol

lsta

ndig

keit

Integrierung und experimentelle Verifizierung

Geo

met

risc

heK

rite

rien

Inte

grie

rung

mit

Wah

rneh

mun

g

Fre

irau

mre

pras

enta

tion

Ver

bind

ung

mit

ande

ren

Met

hode

n

Alte

rnat

ive

Ans

atze

Inte

grie

rung

Ges

amta

rchi

tekt

ur

Randbedinungen

Rep

rase

ntat

ion

der

Bah

n

Inte

grie

rung

Hal

tung

Bew

egun

gin

Kon

takt

Gle

ichg

ewic

htS

chri

ttfol

ge

Nic

htho

lono

me

Ran

dbed

inun

gen

Nic

htho

lono

me

Ran

dbed

inun

gen

Inte

grie

rung

Ges

amta

rchi

tekt

ur

Wahrnehmung

Seg

men

tieru

ngO

kklu

sion

Kal

ibri

erun

gIn

krem

ente

lleK

alib

rier

ung

Sch

nittm

enge

nbes

timm

ung

Ein

bezi

ehun

gR

obot

erse

nsor

en

Bes

chra

nkun

gde

rer

wog

enen

Sen

sore

nIn

tegr

ieru

ngG

esam

tarc

hite

ktur

Tabelle 1: Zeitplan fur das Forschungsvorhaben.

36

4 Beantragte Mittel

4.1 Personalkosten

Zur Durchfuhrung der Forschungsarbeiten werden eine gemaß BAT Ia vergutete Stelle fur den An-

tragsteller und zwei gemaß BAT IIa vergutete Stellen fur wissenschaftliche Mitarbeiter fur jeweils

vier Jahre beantragt. Der Antragsteller strebt im Rahmen dieses Forschungsprojekts die Habilita-

tion an und den wissenschaftlichen Mitarbeitern soll die Dissertation ermoglicht werden.

4.2 Wissenschaftliche Gerate

Aufgrund der Echtzeitanforderungen ist die Leistungsfahigkeit der verwendeten Rechner von her-

ausragender Wichtigkeit. Die Regelungsarchitektur soll aus Effizienzgrunden von dem Wahrneh-

mungssystem entkoppelt werden. Daher wird der Erwerb von zwei leistungsfahigen Mehrprozes-

sorsystemen beantragt.

Die bereits entwickelte Simulationsumgebung basiert auf einer vielseitigen Grafikbibliothek.

Es wird der Erwerb von drei Lizenzen von der Firma TGS (http://www.tgs.com) beantragt. Weitere

Softwarepakete sind an der aufnehmenden Institution vorhanden.

Zur Simulation von physikalisch korrekten Interaktion zwischen verschiedenen Objekten, wie

zum Beispiel bei der Bewegung eines Roboters im Kontakt mit der Umwelt, bietet die Firma

Arachi (http://www.arachi.com) ein Softwarepaket an. Um die aufwendige Entwicklung dieser

Funktionalitat zu umgehen, wird der Erwerb einer Softwarelizenz fur dieses Paket beantragt. Die

Firma Arachi hat einen Rabatt von 50% gegenuber dem Universitatspreises zugesagt.

Fur das Wahrnehmungssystem werden sechs digitale Farbkameras und sechs Framegrabber

benotigt. Ein weiterer Posten wird fur anfallende Kosten bei der Montage des Systems, wie Hal-

ter, Kabel, Verbindungsstecker, etc. beantragt. Es handelt sich um Standardmodelle der unteren

Preisklasse, die durch Gerat mit ahnlichen Merkmalen ersetzt werden konnen.

Da die Dokumentation der Forschungsergebnisse fur ein Forschungsprojekt, welches sich mit

der Bewegung von Robotern befasst, nicht in Form von statischen Bildern erfolgen kann, wird

zudem der Erwerb eines digitalen Camcorders beantragt.

37

2 Multi-Prozessor PCs von Dell�

20.000,–3 Softwarelizensen: MasterSuite von TGS

�12.000,–

1 Softwarelizens: Simulator Softwarebibliothek von Arachi�

6.000,–6 Digitale Farbkameras: Hitachi KP-D580 von CCDDirect

�15.000,–

6 Frame Grabber: Data Translation DT3153 von CCDDirect�

4.000,–Diverse Kabel, Stecker, etc.

�500,–

1 Camcorder: Sony DCR-TRV830-E�

1.100,–Summe 4.2

�58.600,–

4.3 Verbrauchsmaterial

Innerhalb des Projekts entstehen neben den Kosten fur Disketten, Videokassetten, Papier, Folien,

Literatur, Druckertoner und Kopien auch Ausgaben in Zusammenhang mit den Veroffentlichungen.

Fur diese Position werden zusammen�

1000,– pro Jahr veranschlagt, zusammen also�

4000,–.

Summe 4.3�

4.000,–

4.4 Reisen

Die beantragten Reisemittel sollen jedem der Projektteilnehmer im Verlauf des gesamten Vorha-

bens den Besuch von drei internationalen und drei nationalen Kongressen erlauben. Da im Rahmen

dieses Forschungsvorhabens die Habilitation beziehungsweise Promotion erfolgen soll, erscheint

dies angemessen. Es werden�

2.500,– pro Reise ins Ausland und�

1.500,– pro Reise innerhalb

Deutschlands veranschlagt. Dies soll neben den Reise- und Hotelkosten auch die Teilnahmegebuhr

von ungefahr�

600,– umfassen. Es ist nicht vorgesehen, mehr als einen Projektteilnehmer zu ei-

nem gegebenen Kongress zu entsenden. Die Beantragung der Reisemittel fur eine Reise an die

Stanford Universitat ist in Abschnitt 3.2.5 auf Seite 34 begrundet. Eine solche Reise wird mit�

3.000,– pro Person veranschlagt, da sie im Gegensatz zu einer Kongressreise mehrwochig ist.

9 Internationale Kongressreisen�

22.500,–9 Nationale Kongressreisen

�13.500,–

3 Reisen an die Stanford Universitat zur experimentellen Arbeit�

9.000,–Summe 4.4

�45.000,–

4.5 Sonstige Kosten

Es entfallen keine weiteren Kosten.

Summe 4.5�

0,–

38

5 Voraussetzung fur die Durchfuhrung des Vorhabens

5.1 Zusammensetzung der Arbeitsgruppe

Der vorliegende Forschungsantrag soll von dem Antragsteller und zwei Doktoranden durchgefuhrt

werden. Dabei ubernimmt jedes Mitglied der Arbeitsgruppe ein Teilprojekt. Der Antragsteller wird

jedoch an allen Teilprojekten in vollem Umfang beteiligt sein.

5.2 Zusammenarbeit mit anderen Wissenschaftlern

5.2.1 Zusammenarbeit mit Wissenschaftlern an der aufnehmenden Institution

Prof. Georg Farber, Fakultat fur Elektrotechnik und Informationstechnik, Technische Universitat

Munchen

Professor Farber ist Leiter der Robotic Vision Group. Es besteht eine Zusammenarbeit mit

Professor Radig, die sich mit der Erkundung von Arbeitsraumen beschaftigt. Diese Thematik

ist fur das vorgeschlagene Forschungsvorhaben sehr relevant; daher wird auch mit der Ar-

beitsgruppe von Professor Farber eine Zusammenarbeit angestrebt. Zudem wurde in dieser

Arbeitsgruppe die mobile Plattform MARVIN entwickelt, die zur experimentellen Verifizie-

rung der entwickelten Verfahren dienlich sein kann.

Prof. Alois Knoll, Fakultat fur Informatik, Technische Universitat Munchen

In der Arbeitsgruppe von Professor Knoll wurden Bahnplanungsmethoden entwickelt (Bag-

inski 1998; Baumann 2001), die sich fur das Forschungsvorhaben als bedeutungsvoll erwei-

sen konnen. So wird zum Beispiel die BB-Methode als Alternativansatz zur deompositions-

basierten Bahnplanung erwogen. Es wird daher in diesem Bereich eine enge Zusammen-

arbeit angestrebt. Des weiteren bestehen gemeinsame Interessen bei der Integrierung von

Computer Vision und Bewegungsausfuhrung.

Prof. Friedrich Pfeiffer, Fakultat fur Maschinenwesen, Technische Universitat Munchen

Die zweibeinige Laufmaschine Johnnie, die in der Arbeitsgruppe von Professor Pfeiffer kon-

zipiert wurde, konnte zur vorlaufigen experimentellen Uberprufung von Bahnplanungs- und

Bewegungsgenerierungsmethoden verwendet werden. Zudem wird in dieser Arbeitsgruppe

auch Forschung auf dem Gebiet der Kraftkontrolle betrieben; auch hier kann ein produktiver

Austausch von beidseitigem Interesse sein.

Prof. Bernd Radig, Fakultat fur Informatik, Technische Universitat Munchen

39

Professor Radig ist auf dem Gebiet der Bilderkennung tatig. Dabei beschaftigt er sich mit

der Exploration von Innenraumen. Die hier entwickelten Verfahren konnen fur die Bildver-

arbeitungskomponente des Forschungsvorhaben relevant sein. Eine enge Zusammenarbeit

ist daher naheliegend und erwunscht.

Prof. Gunther Schmidt, Fakultat fur Elektrotechnik und Informationstechnik, Technische Uni-

versitat Munchen

Die Forschungsgruppe von Professor Schmidt beschaftigt sich mit humanoidem Laufen.

Von einer Zusammenarbeit verspricht sich der Antragsteller eine Beschleunigung der Bewe-

gungsmodifizerungsmethoden fur Bewegungen, die auf dieser Fortbewegungsart beruhen.

Des weiteren wurde in dieser Arbeitsgruppe die mobile Plattform ROMAN entwickelt, die

zur experimentellen Verifizierung der entwickelten Verfahren dienlich sein kann.

5.2.2 Zusammenarbeit mit Wissenschaftlern an anderen Institutionen

Prof. Rudiger Dillmann, Industrielle Anwendungen von Informatik und Mikrosystemen, Uni-

versitat Karlsruhe

Professor Dillmann ist Sprecher des Sonderforschungsbereichs “Humanoide Roboter, Ler-

nenende und kooperierende multimodale Roboter”. Der Antragsteller ist mit Professor Dill-

mann in Kontakt und aufgrund der inhaltlichen Komplementaritat des Forschungsvorhabens

mit dem Sonderforschungsbereich besteht ein beiderseitiges Interesse an einer Zusammen-

arbeit.

Prof. Gunter Hommel, Prozessdatenverarbeitung und Robotik, Technische Universtiat Berlin

Der Antragsteller unterhalt zu Professor Hommel, dem ehemaligen Betreuer seiner Diplom-

arbeit, einen guten Kontakt. Insbesondere im Bereich der Steuerung nicht-holonomen Fahr-

zeuge besteht ein gemeinsames Interesse, welches eine Zusammenarbeit nahelegt.

Dr. Frieder Lohnert, Forschung und Technologie, DaimlerChrysler

Dr. Lohnert leitet das Advanced Servicing Robot-Projekt, welches in Zusammenarbeit mit

Professor Hommel an der Technischen Universitat Berlin durchgefuhrt wird. Es besteht sein

mehreren Jahren Kontakt, der unter anderem zu einem Vortrag des Antragstellers bei Daim-

lerChrysler in Berlin fuhrte.

40

5.3 Arbeiten im Ausland und Kooperation mit auslandischen Partnern

Yuji Haikawa, Forschungsabteilung Humanoide Roboter, Honda Research, Japan

Honda Research finanziert gegenwartig ein Forschungsprojekt im Robotiklabor von Profes-

sor Khatib an der Stanford Universitat. Im Rahmen eines Besuchs von Herrn Haikawa im

Juli 2001 wurde die Bewegungsgenerierung mit elastic strips demonstriert. Herr Haikawa

hat außerordentliches Interesse an dieser Methode gezeigt. Eine weitergehende Zusammen-

arbeit zwischen Honda und Stanford ist geplant. Der Antragsteller sieht in diesem Zusam-

menhang die Moglichkeit einer direkten Zusammenarbeit mit Herrn Haikawa und seinem

Forschungslabor.

Prof. Lydia Kavraki, Robotics Group, Rice University, Houston, Texas

Die Vorarbeiten zur Bahnplanung wurden in Zusammenarbeit mit Professor Kavraki er-

bracht. Es besteht gegenseitiges Interesse an dem neuartigen Verfahren von dekompositi-

onsbasierter Bahnplanung. Da Professor Kavraki die probabilistische Bahnplanung mitbe-

grundet hat, erhofft sich der Antragsteller einen produktiven Gedankenaustausch.

Prof. Oussama Khatib, Robotics Laboratory, Stanford University, Stanford, Kalifornien

Die Regelungsmethoden im operationalen Raum sind in ihrer ursprunglichen Form von Pro-

fessor Khatib entwickelt wurden. Ein wichtiger Teil des vorliegenden Forschungsprojekts

kann als eine Erweiterung und Weiterentwicklung dieser Methoden angesehen werden. Da-

her ist ein reger Austausch und eine enge Zusammenarbeit sowohl von Seiten des Antragstel-

lers als auch von Seiten Professor Khatibs außerst wunschenswert. Weiterhin ist vorgesehen,

zur experimentellen Demonstration der entwickelten Methoden die an der Stanford Univer-

sitat vorhandene Versuchsplattform zu verwenden (siehe auch Abschnitt 3.2.5 auf Seite 34).

5.4 Apparative Ausstattung

Neben den unter 4.2 beantragten Gerate sind alle benotigten Gerate und die dazugehorige Infra-

struktur an der aufnehmenden Institution vorhanden.

5.5 Laufende Mittel fur Sachausgaben

Es bestehen keine laufenden Mittel fur Sachausgaben.

41

5.6 Sonstige Voraussetzungen

Neben den oben aufgefuhrten gibt es keine weiteren Voraussetzungen.

6 Wirtschaftliche Verwertung

Eine unmittelbare wirtschaftliche Verwertung der Forschungsergebnisse ist nicht geplant.

7 Erklarungen

7.1

Ein Antrag auf Finanzierung dieses Vorhabens wurde bei keiner anderen Stelle eingereicht. Wenn

ich einen solchen Antrag stelle, werde ich die Deutsche Forschungsgemeinschaft unverzuglich

benachrichtigen.

7.2

Der Vertrauensdozent der DFG an der TU Munchen, Herr Prof. Roland Bulirsch, wurde von der

Antragstellung unterrichtet.

8 Unterschrift

Oliver Brock

9 Verzeichnis der Anlagen

1. Anschreiben

2. DFG Vordruck 10.04

3. Tabellarischer Lebenslauf

4. Ausfuhrlicher Lebenslauf

5. Akademische Abschlusszeugnisse (Diplom, Master of Science, Doctor of Philosophy)

42

6. Publikationsverzeichnis

7. Sonderdrucke ausgewahlter Veroffentlichungen in zweifacher Ausfuhrung

8. Kopie der Promotionsschrift in zweifacher Ausfuhrung

9. Befurwortungsschreiben von Professor Oussama Khatib, Stanford Univeristy

10. Befurwortungsschreiben von Professor Alois Knoll, Technische Universitat Munchen

11. Begrundung fur die Wahl der TU Munchen als aufnehmende Institution

12. Zusageschreiben der aufnehmenden Institution (TU Munchen)

43

Literatur

Adams, B., C. Breazeal, R. Brooks, und B. Scassellati (2000). Humanoid robots: A new kind oftool. IEEE Intelligent Systems 15(4), 25–31.

Amato, N., B. Bayazid, L. Dale, C. Jones, und D. Vallejo (1998). OBPRM: An obstacle-basedPRM for 3D workspaces. In Robotics: The Algorithmic Perspective. AK Peters.

Asfour, T., K. Berns, und R. Dillmann (2000). The humanoid robot ARMAR: Design andcontrol. In Proceedings of the International Conference on Humanoid Robots, Cambridge,USA.

Asfour, T., K. Berns, J. Schelling, und R. Dillmann (1999). Programming of manipulation tasksof the humanoid robot ARMAR. In Proceedings of the International Conference on Advan-ced Robotics.

Baginski, B. (1998). Motion Planning for Manipulators with Many Degrees of Freedom – TheBB-Method. Ph. D. thesis, Technische Universitat Munchen.

Barraquand, J. und J.-C. Latombe (1991). Robot motion planning: A distributed representationapproach. International Journal of Robotics Research 10(6), 628–649.

Barron, J. L., D. J. Fleet, und S. Beauchemin (1994). Performance of optical flow techniques.International Journal of Computer Vision 12, 43–77.

Basch, J., L. J. Guibas, D. Shu, und A. T. Nguyen (2001). Disconnection proofs for motion plan-ning. In Proceedings of the International Conference on Robotics and Automation, Seoul,Korea, pp. 1765–1772.

Baumann, A. (2001). Robot Motion Planning in Time-Varying Environments. Ph. D. thesis,Technische Universitat Munchen.

Beveridge, J. R., J. Griffith, R. R. Kohler, A. R. Hanson, und E. M. Riseman (1989). Segmentingimages using localized histograms and region merging. International Journal of ComputerVision 2, 311–347.

Bischoff, R. (2000). Towards the development of ’plug-and-play’ personal robots. In Procee-dings of the International Conference on Humanoid Robots, Cambridge, USA.

Bischoff, R. und V. Graefe (1999). Integrating vision, touch and natural language in the controlof a situation-oriented behavior-based humanoid robot. In Proceedings of the InternationalConference on Systems, Man, and Cybernetics, Volume 2, pp. 999–1004.

Blake, A., R. Curwen, und A. Zissermann (1993). A framework for spatio-temporal control inthe tracking of visual contours. International Journal of Computer Vision 11, 127–145.

Bohlin, R. und L. E. Kavraki (2000). Path planning using lazy PRM. In Proceedings of theInternational Conference on Robotics and Automation, Volume 1, San Francisco, USA, pp.521–528.

Branicky, M. S., S. M. LaValle, K. Olson, und L. Yang (2001). Quasi-randomized path planning.In Proceedings of the International Conference on Robotics and Automation, Seoul, Korea,pp. 1481–1487.

44

Brock, O. (2000). Generating Robot Motion: The Integration of Planning and Execution. Ph.D. thesis, Stanford University, Stanford University, USA.

Brock, O. und L. E. Kavraki (2000). Decomposition-based motion planning: Towards real-timeplanning for robots with many degrees of freedom. Technical Report TR00-367, Rice Uni-versity.

Brock, O. und L. E. Kavraki (2001). Decomposition-based motion planning: A framework forreal-time motion planning in high-dimensional configuration spaces. In Proceedings of theInternational Conference on Robotics and Automation, Seoul, Korea, pp. 1469–1474.

Brock, O. und O. Khatib (1998). Executing motion plans for robots with many degrees of free-dom in dynamic environments. In Proceedings of the International Conference on Roboticsand Automation, Volume 1, Leuven, Belgium, pp. 1–6.

Brock, O. und O. Khatib (1999a). Elastic strips: A framework for integrated planning and exe-cution. In P. Corke und J. Trevelyan (Eds.), Proceedings of the International Symposium onExperimental Robotics, Volume 250 of Lecture Notes in Control and Information Sciences,pp. 328–338. Springer Verlag.

Brock, O. und O. Khatib (1999b). High-speed navigation using the global dynamic windowapproach. In Proceedings of the International Conference on Robotics and Automation, Vo-lume 1, Detroit, USA, pp. 341–346.

Brock, O. und O. Khatib (1999c). Real-time obstacle avoidance and motion coordination in amulti-robot workcell. In Proceedings of the International Symposium on Assembly and TaskPlanning, Porto, Portugal, pp. 274–279.

Brock, O. und O. Khatib (2000). Real-time replanning in high-dimensional configuration spacesusing sets of homotopic paths. In Proceedings of the International Conference on Roboticsand Automation, Volume 1, San Francisco, USA, pp. 550–555.

Brock, O., O. Khatib, und S. Viji (2002). Task-consistent obstacle avoidance and motion beha-vior for mobile manipulation. In Proceedings of the International Conference on Roboticsand Automation, Washington, USA. Submitted.

Brooks, R. (1997). From earwigs to humans. Robotics and Autonomous Systems 20(2-4), 291–304.

Canny, J. F. (1988). The Complexity of Robot Motion Planning. MIT Press.

Chang, K.-S., R. Holmberg, und O. Khatib (2001). The augmented object model: Cooperativemanipluation and parallel mechanism dynamics. In Proceedings of the International Confe-rence on Robotics and Automation, Seoul, Korea, pp. 470–475.

De Schutter, J. und H. Van Brussel (1988a). Compliant robot motion i. a formalism for specify-ing compliant motion tasks. International Journal of Robotics Research 7(4), 3–17.

De Schutter, J. und H. Van Brussel (1988b). Compliant robot motion ii. a control approachbased on external control loops. International Journal of Robotics Research 7(4), 18–33.

Dillman, R. et al. (2000). Humanoide Roboter – Lernende und kooperierende multimodale Ro-boter. Finanzierungsantrage zum SFB 1846.

45

Dillmann, R., T. Asfour, und K. Berns (2000). Design and control of a humaonid 2-arm-system.In Proceedings of the World Automation Congress.

Featherstone, R., S. Sonck, und O. Khatib (1999). A general contact model for dynamically-decoupled force/motion control. In Proceedings of the International Conference on Roboticsand Automation, Detroit, USA, pp. 3281–3286.

Feder, H. J. S. und J.-J. E. Slotine (1997). Real-time path planning using harmonic potentialsin dynamic environments. In Proceedings of the International Conference on Robotics andAutomation, Volume 1, pp. 874–811.

Finn, P. W. und L. E. Kavraki (1999). Computational approaches to drug design. Algorithmi-ca 25, 347–371.

Forsyth, D. und J. Ponce (2000). Computer Vision – A Modern Approach. Unpublished Draft ofBook. http://www.cs.berkeley.edu/˜daf/book3chaps.html.

Foskey, M., M. Garber, M. C. Lin, und D. Manocha (2001). A voronoi-based hybrid motionplanner. In Proceedings of the International Conference on Intelligent Robots and Systems,Volume 1, Mauii, USA, pp. 55–60.

Franklin, G. F., J. D. Powell, und A. Emami-Naeini (1994). Feedback Control of Dynamic Sy-stems (3rd ed.). Addison-Wesley.

Franklin, G. F., J. D. Powell, und M. L. Workman (1998). Digital Control of Dynamic Systems(3rd ed.). Addison-Wesley.

Goodman, J. E. und J. O’Rourke (1997). Handbook of Discrete and Computational Geometry.CRC Press.

Holmberg, B. und O. Khatib (2000). Development of a holonomic mobile robot for mobilemanipulation tasks. International Journal of Robotics Research 19(11), 1066–1074.

Honda (2001, Januar). Honda stellt humanoiden Roboter ASIMO vor. Presseveroffentlichung:http://www.honda.de/np/1199.html.

Horowitz, S. L. und T. Pavlidis (1987). Picture segmentation by a tree traversal algorithm. Jour-nal of the Association for Computing Machinery 23(2), 368–388.

Hsu, D., L. E. Kavraki, J.-C. Latombe, und R. Motwani (1999). Capturing the connectivity ofhigh-dimensional geometric spaces by parallelizable random sampling techniques. In P. M.Pardalos und S. Rajasekaran (Eds.), Advances in Randomized Parallel Computing, pp. 159–182. Kluwer Acedemic Publishers.

Hsu, D., L. E. Kavraki, J.-C. Latombe, R. Motwani, und S. Sorkin (1998). On finding narrowpassages with probabilistic roadmap planners. In Proceedings of the Workshop on the Algo-rithmic Foundations of Robotics, pp. 141–154. A K Peters.

Hsu, D., R. Kindel, J.-C. Latombe, und S. Rock (2000). Randomized kinodynamic motion plan-ning with moving obstacles. In Proceedings of the Workshop on the Algorithmic Foundationsof Robotics, pp. 247–264.

Hsu, D., J.-C. Latombe, und R. Motwani (1997). Path planning in expansive configurationspaces. In Proceedings of the International Conference on Robotics and Automation, Vo-lume 3, pp. 2719–2726.

46

Huang, Q., K. Kaneko, K. Yokoi, S. Kajita, T. Kotoku, N. Koyachi, H. Arai, N. Imamura, K. Ko-moriya, und K. Tanie (2000). Balance control of a biped robot combining off-line patter withreal-time modification. In Proceedings of the International Conference on Robotics and Au-tomation, San Francisco, USA, pp. 3346–3352.

Hwang, Y. K. und N. Ahuja (1992). Gross motion planning - a survey. ACM Computing Sur-veys 24(3), 219–291.

Inoue, K., H. Yoshida, T. Arai, und Y. Mae (2000). Moblie manipulation of humanoids – real-time control based on manipulability and stability. In Proceedings of the International Con-ference on Robotics and Automation, San Francisco, USA.

Irani, M., B. Rousso, und S. Peleg (1994). Computing occluding and transparent motions. In-ternational Journal of Computer Vision 12, 5–16.

Kagami, S., F. Kanehiro, Y. Tamiya, M. Inaba, und H. Inoue (2000). AutoBalancer: An onlinedynamic balance compensation scheme for humanoid robots. In Proceedings of the Work-shop on the Algorithmic Foundations of Robotics, pp. 329–339.

Kagami, S., J. J. Kuffner, K. Nishiwaki, T. Sugihara, T. Michikata, T. Aoyama, M. Inaba, undH. Inoue (2001). Design and implementation of remotely operation interaface for humanoiderobot. In Proceedings of the International Conference on Robotics and Automation, Seoul,Korea, pp. 401–406.

Kagami, S., K. Nishiwaki, T. Sugihara, J. Kuffner, M. Inaba, und H. Inoue (2001). Design andimplementation of software research platform for humanoid robotics: H6. In Proceedings ofthe International Conference on Robotics and Automation, Seoul, Korea, pp. 2431–2436.

Kanade, T., H. Kano, S. Kimuara, A. Yoshida, und K. Oda (1995). Development of a video-ratestereo machine. In Proceedings of the International Conference on Intelligent Robots andSystems, Volume 3, pp. 95–100.

Kanade, T. und H. S. S. Vedula (1998). The 3d room: Digitizing time-varying 3d events by syn-chronized multiple video streams. Technical Report CMU-RI-TR-98-34, Carnegie MellonUniversity.

Kass, M., A. Witkin, und D. Terzonpoulos (1988). Snakes: Active contour models. InternationalJournal of Computer Vision 1(4), 321–331.

Kavraki, L. (1994). Random Networks in Configuration Space for Fast Motion Planning. Ph. D.thesis, Stanford University.

Kavraki, L. E., P. Svestka, J.-C. Latombe, und M. H. Overmars (1996). Probabilistic roadmapsfor path planning in high-dimensional configuration spaces. IEEE Transactions on Roboticsand Automation 12(4), 566–580.

Khatib, M. (1996). Sensor-Based Motion Control for Mobile Robots. Ph. D. thesis, LAAS-CNRS, Toulouse, France.

Khatib, M. und H. Jaouni (1996). Kinematics integrated in non-holonomic autonomous naviga-tion. Technical Report 96346, LAAS.

47

Khatib, O. (1980). Command Dynamique dans l’Espace Operationel des Robots Manipulateursen Presence d’Obstacle. Ph. D. thesis, Ecole Nationale Superieur de l’Aeronautic et del’Espace, Toulouse, France.

Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. Interna-tional Journal of Robotics Research 5(1), 90–98.

Khatib, O. (1987). A unified approach to motion and force control of robot manipulators: Theoperational space formulation. International Journal of Robotics and Automation 3(1), 43–53.

Khatib, O. (1993). The operational space framework. JSME International Journal 36(3), 277–287.

Khatib, O. (1995). Inertial properties in robotics manipulation: An object-level framework. In-ternational Journal of Robotics Research 14(1), 19–36.

Khatib, O., O. Brock, K.-S. Chang, B. Holmberg, und A. Bowling (1999). Dancing with juliet.In Proceedings of the International Conference on Robotics and Automation, Detroit, USA.Video Proceedings.

Khatib, O., K. Yokoi, O. Brock, K.-S. Chang, und A. Casal (1999). Robots in human environ-ments: Basic autonomous capabilities. International Journal of Robotics Research 18(7),684–696.

Khatib, O., K. Yokoi, K.-S. Chang, R. Holmberg, A. Casal, und A. Baader (1995). Force strate-gies for cooperative tasks in multiple mobile manipulation systems. In G. Giralt und G. Hir-zinger (Eds.), Proceedings of the International Symposium of Robotics Research, pp. 333–342. Springer Verlag.

Koditschek, D. E. (1987). Exact robot navigation by means of potential functions: Some to-pological considerations. In Proceedings of the International Conference on Robotics andAutomation, pp. 1–6.

Krumm, J., S. Harris, B. Meyers, B. Brumitt, M. Hale, und S. Shafer (2000). Muli-cameramulti-person tracking for EasyLiving. In Third IEEE International Workshop on Visual Sur-veillance, Dublin, Ireland.

Kuffner, J. J. (1998). Goal-directed navigation for animated characters using real-time pathplanning and control. In Proceedings of Captech’98.

Kuffner, J. J. und S. M. LaValle (2000). RRT-connect: An efficient approach to single-querypath planning. In Proceedings of the International Conference on Robotics and Automation,Volume 2, San Francisco, USA, pp. 995–1001.

Kuffner, J. J., K. Nishiwaki, S. Kagami, M. Inaba, und H. Inoue (2001). Motion planning forhumanoid robots under obstacle and dynamic balance constraints. In Proceedings of theInternational Conference on Robotics and Automation, Seoul, Korea, pp. 692–698.

Lamiraux, F. und L. E. Kavraki (2001). Planning paths for elastic objects under manipulationconstraints. International Journal of Robotics Research 20(3), 188–208.

Latombe, J.-C. (1991). Robot Motion Planning. Boston: Kluwer Academic Publishers.

48

Laurentini, A. (1994). The visual hull concept for silhouette-based image understanding. IEEETransactions on Pattern Analysis and Machine Intelligence 16(2), 150–162.

LaValle, S. M. (1998). Rapidly-exploring random trees: A new tool for path planning. TechnicalReport TR 98-11, Iowa State University.

LaValle, S. M. und J. J. Kuffner (1999). Randomized kinodynamic planning. In Proceedings ofthe International Conference on Robotics and Automation, Detroit, USA.

LaValle, S. M., J. H. Yakey, und L. E. Kavraki (1999). A probabilistic roadmap approach forsytems with closed kinematic chains. In Proceedings of the International Conference onRobotics and Automation, Detroit, USA, pp. 1671–1675.

Lin, M. C. (1993). Efficient Collision Detection for Animation and Robotics. Ph. D. thesis,University of California at Berkeley.

Liu, Y. und R. Popplestone (1994). A group theoretic formalization of surface contact. Interna-tional Journal of Robotics Research 13(2), 148–161.

Lozano-Perez, T. (1983). Spatial planning: A configuration space approach. IEEE Transactionson Computers C-32(2), 108–120.

Matusik, W. (2001). Image-based visual hulls. Master’s thesis, Massachusetts Institute of Tech-nology.

McLean, A. und S. Cameron (1996). The virtual springs method: Path planning and collisionavoidance for redundant manipulators. International Journal of Robotics Research 15(4),300–319.

Nakamura, Y. und K. Yamane (2000). Interactive motion generation of humanoid robots viadynanics filter. In Proceedings of the International Conference on Humanoid Robots, Cam-bridge, USA.

Nalwa, V. S. (1993). A Guided Tour of Computer Vision. Addison Wesley.

Neumann, Ulrich, und H. Fuchs (1993). A vision of telepresence for medical consultation andother applications. In Robotics Research, pp. 565–571. Springer Verlag.

Nielsen, C. L. und L. E. Kavraki (2000). A two level fuzzy PRM for manipulation planning. InProceedings of the International Conference on Intelligent Robots and Systems.

Nishiwaki, K., T. Sugihara, S. Kagami, M. Inaba, und H. Inoue (2001). Online mixture andconnection of basic motions for humanoid walking control by footprint specification. InProceedings of the International Conference on Robotics and Automation, Seoul, Korea,pp. 4110–4115.

Ong, C. J. und E. G. Gilbert (1997). The Gilbert-Johnson-Keerthi distance algorithm: A fastversion for incremental motions. In Proceedings of the International Conference on Roboticsand Automation, Volume 2, pp. 1183–1189.

Prewitt, J. M. S. (1970). Object enhancement and extraction. In B. S. Lipkin und A. Rosenfeld(Eds.), Picture Processing and Psychopictorics, pp. 75–149. Academic Press.

Quinlan, S. (1994). Real-Time Modification of Collision-Free Paths. Ph. D. thesis, StanfordUniversity.

49

Raskar, R., G. Welch, M. Cutts, A. Lake, L. Stesin, und H. Fuchs (1998). The office of thefuture: A unified approach to image-based modeling and spatially immersive displays. InProceedings of SIGRAPH, Orlando, USA, pp. 179–188.

Rimon, E. und D. E. Koditschek (1992). Exact robot navigation using artificial potential fields.IEEE Transactions on Robotics and Automation 8(5), 501–518.

Russakow, J., O. Khatib, und S. M. Rock (1995). Extended operational space formation forserial-to-parallel chain (branching) manipulators. In Proceedings of the International Con-ference on Robotics and Automation, Volume 1, pp. 1056–1061.

Sentis, L. (2001). About the generation of postures in the nullspace. Personliches Gesprach ander Stanford University.

Shafer, S., J. Krumm, B. Brumitt, B. Meyers, M. Czerwinski, und D. Robbins (1998). The newEasyLiving project at Microsoft research. In Joint DARPA/NIST Smart Spaces Workshop,Gaithersburg, USA, pp. 137–130.

Shiller, Z., K. Yamane, und Y. Nakamura (2001). Planning motion patters of human figuresusing a multi-layered grid and the dynamics filter. In Proceedings of the International Con-ference on Robotics and Automation, Seoul, Korea, pp. 1–8.

Small, D. E. (2001, July). Real-time shape-from-silhouette. Master’s thesis, University of NewMexico, USA.

Song, G. und N. M. Amato (2001). A motion planning approach to folding: From paper craft toprotein folding. In Proceedings of the International Conference on Robotics and Automati-on, Seoul, Korea.

Song, G., S. Miller, und N. M. Amato (2001). Customizing PRM roadmaps at query time. InProceedings of the International Conference on Robotics and Automation, Seoul, Korea, pp.1500–1505.

Szeliski, R. (1990). Real-time octree generation from rotating objects. Technical Report CRL90/12, Digital Equipment Corporation.

Tomasi, C. und T. Kanade (1992). Shape and motion from images streams under orthography:a factorization method. International Journal of Computer Vision 9, 137–154.

Tomasi, C. und R. Manduchi (1998). Stereo matching as a nearest-neighbor problem. IEEETransactions on Pattern Analysis and Machine Intelligence 20(3), 333–340.

Trucco, E. und A. Verri (1998). Introductory Techniques for 3-D Computer Vision. PrenticeHall.

Vallejo, D., I. Remmler, und N. M. Amato (2001). An adaptive framework for single shot mo-tion planning: A self-tuning system for rigid and articulated robots. In Proceedings of theInternational Conference on Robotics and Automation, Seoul, Korea, pp. 21–26.

Vukobratovic, M., A. A. Frank, und D. Juricic (1970). On the stability of biped locomotion.IEEE Transactions on Biomedical Engineering 17(1), 25–36.

Williams, D. und O. Khatib (1993). The virtual linkage: A model for internal forces in multi-grasp manipulation. In Proceedings of the International Conference on Robotics and Auto-mation, Volume 1, pp. 1035–1030.

50