Mobile robot navigation in dynamic environments [Elektronische Ressource] / Maren Bennewitz

Maren Bennewitz

Informations

• Publié par: albert-ludwigs-universitat_freiburg
• Publié le: 01 janvier 2004
• Nombre de lectures: 13
• Langue: Deutsch
• Poids de l'ouvrage: 5 Mo

Extrait

Dissertation zur Erlangung des Doktorgrades der Fakultat¨ fur¨
Angewandte Wissenschaften der Albert Ludwigs Universit at¨
Freiburg im Breisgau
Mobile Robot Navigation in
Dynamic Environments
Maren Bennewitz
Betreuer:
Prof. Dr. Wolfram Burgard¨ ¨Dekan der Fakultat fur Angewandte Wissenschaften:
Prof. Dr. Thomas Ottmann
1. Gutachter: Prof. Dr. Wolfram Burgard
2. Prof. Dr. Raja Chatila
Tag der Disputation: 28. Juni 2004Zusammenfassung
Service Roboter, die in von Menschen bevolk¨ erten Umgebungen agieren, sind in
den letzten Jahren immer popularer¨ geworden. Es existieren schon eine Reihe von
¨ ¨ ¨ ¨Systemen, die beispielsweise in Krankenhausern, Burogebauden, Kaufhausern
und Museen eingesetzt werden. Daruber¨ hinaus sind auch verschiedene Mehr
robotersysteme entwickelt worden, da einige Aufgaben von einem Team von Ro
botern schneller und effizienter erledigt werden konnen¨ als von einem einzelnen
Roboter. Dazu gehoren¨ unter anderem Reinigungsarbeiten, Auslieferungsauftrage¨
und das Erkunden von unbekannten Umgebungen.
Immer wenn Teams von mobilen Robotern in der selben Umgebung eingesetzt
werden, mussen¨ ihre Bewegungen koordiniert werden, damit die einzelnen Robo
ter sich nicht gegenseitig behindern. Außerdem sollte ihre gemeinsame Aufgabe
so schnell wie moglich¨ erledigt werden. Um diese Anspruche¨ zu erfullen,¨ wer-
den komplexe Pfadplanungtechniken benotigt.¨ Da der gemeinsame Konfigura
tionsraum der Roboter in der Regel extrem groß ist und exponentiell mit der An
¨ ¨ ¨zahl der Roboter wachst, konnen existierende Pfadplanungtechniken fur einzelne
Roboter nicht unmittelbar auf Mehrrobotersysteme ubertragen¨ werden.
Viele existierende Methoden fur¨ sind entkoppelt“, was be
”
deutet, dass sie zuerst Pfade fur¨ die einzelnen Roboter unabhangig¨ voneinan
der planen. Anschließend uberpr¨ ufen¨ sie, ob sich die Roboter zu nahe kamen,¨
wenn sie sich entlang dieser Pfade bewegten. In solchen Fallen¨ werden die Pfade
neu berechnet, um diese Konflikte zu umgehen. Dabei weisen viele entkoppelte
Methoden den einzelnen Robotern Prioritaten¨ zu. Diese geben an, in welcher
Reihenfolge die Pfade neu berechnet werden. Bei der Berechnung des Pfades
fur¨ einen Roboter werden dabei die Pfade aller Roboter mit hoherer¨ Prioritat¨ als
gegeben und unveranderbar¨ angesehen. Auf diese Weise wird der Suchraum ex
trem eingeschrankt¨ und die Suche nach einer Losung¨ des kombinierten Planungs
problems beschleunigt. Die meisten existierenden entkoppelten Ansatze¨ benutzen
dabei ein festes Prioritatsschema,¨ d.h. eine feste Ordnung der Roboter. Die Rei
henfolge, in der Pfade berechnet werden, hat jedoch einen großen Einfluss darauf,
ob uberhaupt¨ eine Losung¨ fur¨ das kombinierte Pfadplanungsproblem gefunden
werden kann und darauf, wie effizient diese Losung¨ fur¨ das gesamte Mehrroboter
system ist.
Im ersten Teil dieser Dissertation stellen wir einen Ansatz vor, der in dem Raum
aller Prioritatsschemata¨ nach einer Ordnung der Roboter sucht, fur¨ die eine Losung¨
des Pfadplanungsproblems berechnet werden kann. Dabei nutzt unser Verfahren
Einschrankungen¨ (Constraints) zwischen den Prioritaten¨ der Roboter aus, welche
automatisch von der Aufgabenspezifikation abgeleitet werden. Nachdem ein ge
eignetes Prioriatsschema¨ gefunden wurde, versucht unser Verfahren dieses mit hilfe einer Hill Climbing Strategie zu verbessern. Unsere Suchmethode kann urf¨
beliebige entkoppelte Planungsysteme eingesetzt werden. In verschiedenen Expe
rimenten mit einem realen Mehrrobotersystem sowie in Simulationen zeigen wir,
dass unser Verfahren effiziente Losungen¨ auch fur¨ komplizierte Pfadplanungs
probleme finden kann.
Der zweite Teil dieser Dissertation konzentriert sich auf Roboter, die in von Men
schen genutzten Umgebungen eingesetzt werden. Diese Systeme konnen¨ den
Service und ihr Verhalten gegenuber¨ Personen verbessern, wenn sie auf die Ak
tivitaten¨ der umgebenden Menschen reagieren und nicht mit ihnen interferieren.
Im Gegensatz zu einem Mehrrobotersystem sind die zukunftigen¨ Bewegungen
¨von Menschen aber nicht bekannt. Deswegen mussen die Roboter in der Lage
sein, die Menschen mittels ihrer Sensoren wahrzunehmen, zu identifizieren und
ihre Intentionen zu lernen, damit sie bessere Vorhersagen uber¨ das Verhalten der
Menschen machen konnen.¨ In dieser Dissertation stellen wir eine Technik vor,
die typische Bewegungsmuster von Personen aus Sensordaten mithilfe des EM
Algorithmus’ lernt. Wir beschreiben außerdem, wie die gelernten Muster dazu
benutzt werden konnen,¨ um potentielle zukunftige¨ Bewegungen der Personen
vorherzusagen. Anschließend erklaren¨ wir, wie dieses Wissen im Pfadplanung
prozess eines mobilen Roboters berucksichtigt¨ werden kann. Danach fuhren¨ wir
eine Methode ein, die aus den gelernten Verhaltensmustern automatisch Hidden
Markov Modelle (HMMs) ableitet. Diese HMMs konnen¨ von einem mobilen
Roboter benutzt werden, um die Positionen von mehreren Personen vorherzusagen,
auch wenn sie außerhalb seines Sichtfelds sind. Um die HMMs mithilfe von
Kamera und Laserdaten zu aktualisieren, wenden wir Joint Probabilistic Data
Association Filter an. In der Regel wird ein Roboter unsicher uber¨ die Positio
nen von Personen, wenn er sie langere¨ Zeit nicht beobachtet. Deswegen unter-
suchen wir auch, wie entscheidungstheoretisch geeignete Beobachtungsaktionen
bestimmt werden konnen,¨ welche ausgefuhrt¨ werden, wahrend¨ der Roboter seine
sonstigen Aufgaben verrichtet.
Praktische Experimente, die wir mit unserem mobilen Roboter durchgefuhrt¨ haben,
zeigen, dass
unsere Methode typische Bewegungsmuster von Personen lernen kann,
das Navigationsverhalten des Roboters verbessert werden kann, indem er
¨die gelernten Muster benutzt, um Vorhersagen uber die Bewegungen von
Personen zu machen,
die abgeleiteten HMMs eingesetzt werden konnen,¨ um zuverlassig¨ einen
probabilistischen Glauben uber¨ die Positionen von mehreren Personen zu
behalten, auch wenn sie gerade nicht im Sichtfeld des Roboters sind, und unsere Technik effektive Aktionen generiert, welche die Unsicherheit des
Roboters uber¨ die Positionen von Personen stark reduzieren.
Unser Ansatz ist nutzlich¨ fur¨ Serviceroboter verschiedenster Art, da es in vielen
Anwendungen hilfreich ist zu wissen, wo sich die Personen in der Umgebung
aufhalten. Beispielsweise kann ein Roboter personliche¨ Botendienste effizien
ter ausfuhren,¨ wenn er weiß, wo sich die Personen gerade befinden. Fur¨ einen
Putzroboter ist es ebenfalls interessant zu wissen, welche Raume¨ gerade leer sind,
damit er niemanden stort.¨ Daruber¨ hinaus kann ein Haushaltsrobototer sein Ver-
halten verbessern, wenn er weiß, wo eine Person gerade ist oder wo sie hingeht.
Dadurch kann der Roboter sich beispielsweise so bewegen, dass er der Person
nicht im Weg steht und er kann sich strategisch gunstig¨ fur¨ Interaktionen posi
tionieren.
Zusammengefasst prasentieren¨ wir Techniken, welche das Zusammenleben von
Mensch und Roboter sowie deren Interaktion erleichtern.Summary
Service robots which act in environments populated by humans have become
very popular in the last few years. A variety of systems exists which act for exam
ple in hospitals, office buildings, department stores, and museums. Furthermore,
several multi robot systems have been developed for tasks which can be accom
plished more efficiently by a whole team of robots than just by a single robot.
These tasks include surface cleaning, deliveries, and the exploration of unknown
terrain. Whenever teams of mobile robots are operating in the same environment
their motions have to be coordinated in order to avoid congestions or collisions.
At the same time the robots should perform their navigation tasks in a minimum
amount of time. Thus, sophisticated path planning techniques are needed that
fulfill these requirements. Since the joint configuration space of the robots is
typically huge and grows exponentially with the number of robots, existing path
planning methods for single robot systems cannot directly be transferred to multi
robot systems.
Many existing path planning methods for multi robot systems are decoupled,
which means that they first plan paths for the individual robots independently. Af
terward, they check if the robots would get too close to each other if the paths
were executed. In such a case the paths are recomputed to avoid these conflicts.
Many decoupled methods assign priorities to the individual robots. These prior-
ities define an order in which the paths of the robots have to be recomputed. By
computing the path of a robot, the paths of the with higher priority are con
sidered as fixed. This way, the size of the search space is extremely reduced. Most
of the existing prioritized decoupled methods use a fixed priority scheme (order
of the robots). However, the order in which the paths of the robots are recom
puted has a serious influence on whether a solution can