DE102008057139A1

DE102008057139A1 - Verfahren und Vorrichtung zur rechnergestützten Auswahl von Landmarken aus einer räumlichen Umgebung zur Lokalisation eines mobilen Objekts und entsprechendes Computerprogrammprodukt

Info

Publication number: DE102008057139A1
Application number: DE102008057139A
Authority: DE
Inventors: Walter Beichl; Wendelin Dr. Feiten; Thomas Dr. Wösch; Georg Von Dr. Wichert
Original assignee: Siemens AG
Current assignee: Siemens AG
Priority date: 2008-04-25
Filing date: 2008-11-13
Publication date: 2009-11-12

Abstract

Die Erfindung betrifft ein Verfahren und Vorrichtung zur rechnergestützten Auswahl von Landmarken (L1, L2, L3) aus einer räumlichen Umgebung zur Lokalisation eines mobilen Objekts (1). Aus einer Gesamtmenge von Landmarken (L1, L2, L3) werden eine oder mehrere Teilmengen gebildet, wobei für jede Teilmenge unter Berücksichtigung einer Anzahl von Konfigurationen (q1, q2) des mobilen Objekts (1), welche jeweils eine Lage des mobilen Objekts (1) in der räumlichen Umgebung darstellen, ein Gütemaß bestimmt wird, welches die Güte einer Schätzung der Lage des mobilen Objekts (1) für die Anzahl von Konfigurationen (q1, q2) basierend auf den Landmarken (L1, L2, L3) der jeweiligen Teilmenge repräsentiert. Falls das Gütemaß für eine Teilmenge ein vorbestimmtes Kriterium in Bezug auf eine hohe Güte der Schätzung der Lage des mobilen Objekts (1) für die Anzahl von Konfigurationen (q1, q2) erfüllt, wird die Teilmenge der Landmarken (L1, L2, L3) ausgewählt. Durch das erfindungsgemäße Verfahren wird automatisiert eine Menge an Landmarken bestimmt, welche sich besonders gut für die Lokalisation eines mobilen Objekts eignen.

Description

Die Erfindung betrifft ein Verfahren und eine Vorrichtung zur rechnergestützten Auswahl von Landmarken aus einer räumlichen Umgebung zur Lokalisation eines mobilen Objekts sowie ein entsprechendes Computerprogrammprodukt.
Zur autonomen Navigation eines mobilen Objekts in einer räumlichen Umgebung ist es erforderlich, dass das Objekt in der räumlichen Umgebung lokalisiert wird. Unter Lokalisation wird dabei die Schätzung der Lage des mobilen Objekts in der räumlichen Umgebung verstanden, wobei die Lage charakterisiert ist durch die Position und Orientierung des mobilen Objekts im Raum. Diese Lage wird häufig auch als Konfiguration des mobilen Objekts bezeichnet.
Zur Schätzung der Konfiguration des mobilen Objekts werden in der Regel sog. Landmarken verwendet, welche geeignete Strukturen in der räumlichen Umgebung sind, wie z. B. Geradenstücke, Ebenenstücke und dergleichen, anhand derer sich ein mobiles Objekt orientieren kann. Während der Navigation des mobilen Objekts wird die Umgebung des Objekts mittels einer Sensoreinrichtung erfasst und aus der erfassten Umgebung werden Landmarken extrahiert. Diese Landmarken werden mit entsprechenden Landmarken aus einer Referenzkarte verglichen, wodurch eine genaue Schätzung der Konfiguration des mobilen Objekts in der Referenzkarte erfolgen kann.
Aus dem Stand der Technik sind verschiedene Verfahren bekannt, wie geeignete Landmarken aus einer mittels einer Sensoreinrichtung erfassten räumlichen Umgebung gewonnen werden können (siehe z. B. Druckschrift [1]). Dabei werden im Wesent lichen alle als Landmarken in Frage kommenden Strukturen aus den Sensordaten extrahiert und in eine Referenzkarte eingetragen. Die Verwendung von allen diesen extrahierten Landmarken im laufenden Betrieb ist in vielen Industrieumgebungen jedoch nicht vertretbar. Es besteht deshalb das Bedürfnis, aus den extrahierten Landmarken nur solche Landmarken in eine Referenzkarte einzutragen, welche für eine spätere genaue Lokalisation des mobilen Objekts auch tatsächlich erforderlich sind. Heutzutage gibt es diesbezüglich nur den Ansatz, die Menge an extrahierten Landmarken manuell einzugrenzen. Dies erfordert erhebliche Arbeitszeit von speziell qualifiziertem Personal.
Der Erfindung liegt die Aufgabe zugrunde ein Verfahren und eine Vorrichtung vorzustellen, das automatisch für die Lokalisation eines mobilen Objekts geeignete auswählt und dabei die Anzahl der Landmarken reduziert.
Diese Aufgabe wird durch die Merkmale des unabhängigen Patentanspruchs 1 oder die Vorrichtung gemäß Patentanspruch 21 oder das Computerprogrammprodukt gemäß Patentanspruch 26 gelöst. Weitere vorteilhafte Ausgestaltungen der Erfindung sind in den abhängigen Ansprüchen wiedergegeben.
Erfindungsgemäß werden eine oder mehrere Teilmengen aus der Gesamtmenge der Landmarken gebildet, wobei für jede Teilmenge unter Berücksichtigung einer Anzahl von Konfigurationen des mobilen Objekts ein Gütemaß bestimmt wird, welches die Güte einer Schätzung der Lage des mobilen Objekts für die Anzahl von Konfigurationen basierend auf den Landmarken der jeweiligen Teilmenge repräsentiert. Erfindungsgemäß wird somit für verschiedene Teilmengen von Landmarken beurteilt, wie gut mit diesen Landmarken die Konfiguration des mobilen Objekts, d. h. dessen Position und Orientierung, in der räumlichen Umgebung geschätzt werden kann. Die Güte kann dabei durch beliebige Parameter repräsentiert werden, beispielsweise durch ein Maß für die statistische Sicherheit der geschätzten Lage des Ob jekts bzw. durch ein Maß für die geschätzte Genauigkeit der Lageschätzung und dergleichen. Je höher die statistische Sicherheit bzw. die Genauigkeit ist, desto besser ist die Güte der Schätzung.
In dem erfindungsgemäßen Verfahren wird ein vorbestimmtes Kriterium im Hinblick auf eine hohe Güte der Schätzung der Lage des Objekts für die Anzahl von Konfigurationen festgelegt. Falls das Gütemaß für eine Teilmenge dieses Kriterium erfüllt, wird die Teilmenge der Landmarken ausgewählt. Die ausgewählte Teilmenge kann dann insbesondere in einer entsprechenden Referenzkarte hinterlegt werden, wobei diese Karte anschließend zur Lokalisation des mobilen Objekts während dessen Navigation verwendet wird.
Die Erfindung beruht auf der Erkenntnis, dass durch die Definition eines geeigneten Gütemaßes in Bezug auf die Lageschätzung eines mobilen Objekts eine für die spätere Lokalisation geeignete Auswahl an Landmarken automatisch aus einer Gesamtmenge von Landmarken extrahiert werden kann. Es kann somit eine große Menge an Landmarken geeignet eingegrenzt werden, ohne dass dazu manuelle Zwischenschritte erforderlich sind.
In einer vorteilhaften Ausgestaltung der Erfindung wird die Umgebung während einer Fahrt des später zu lokalisierenden mobilen Objekts erfasst. Aus dieser räumlichen Umgebung werden Landmarken extrahiert. Aus dem Stand der Technik sind verschiedene Verfahren zur Extraktion solcher Landmarken bekannt. Beispielsweise kann das in der Druckschrift [2] beschriebene Verfahren verwendet werden, bei dem aus einer dreidimensionalen Punktewolke Strukturen in einer horizontalen Ebene extrahiert werden, wobei die Ebene insbesondere etwas unterhalb der Höhe des Daches eines Gebäudes liegt, in dem sich das mobile Objekt bewegt.
In einer vorteilhaften Ausgestaltung der Erfindung ist es auch möglich, dass der Schritt der Extraktion von Landmarken nicht Teil des Verfahrens ist und die extrahierten Landmarken bereits vorliegen. In diesem Fall werden die extrahierten Landmarken zur Durchführung des Verfahrens geeignet bereitgestellt, beispielsweise aus einem entsprechenden Speicher ausgelesen. Durch die extrahierten Landmarken wird eine Gesamtmenge von Landmarken gebildet.
In einer bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens ist das vorbestimmte Kriterium in Bezug auf eine hohe Güte der Schätzung der Lage des mobilen Objekts derart definiert, dass bei der Erfüllung des Kriteriums zumindest die Bedingung erfüllt ist, dass das Gütemaß für die Teilmenge einen vorbestimmten Wert erreicht, der eine ausreichende Güte repräsentiert.
In einer weiteren, besonders bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens werden die Teilmengen aus der Gesamtmenge der Landmarken basierend auf einer Iteration gebildet, wobei in einem aktuellen Iterationsschritt eine oder mehrere neue Teilmengen aus einer im vorhergehenden Iterationsschritt bestimmten Teilmenge gebildet werden, wobei jede neue Teilmenge aus der im vorhergehenden Iterationsschritt bestimmten Teilmenge und zumindest einer zusätzlichen Landmarke aus der Gesamtmenge der Landmarken besteht. Dabei wird aus den neuen Teilmengen diejenige Teilmenge bestimmt, deren Gütemaß die größte Güte der Schätzung der Lage des mobilen Objekts für die Anzahl von Konfigurationen repräsentiert. Durch diese Iteration wird ein einfach zu implementierendes Verfahren zur geeigneten Auswahl der Landmarken geschaffen.
Vorzugsweise wird die obige Iteration dann beendet, wenn das in dem aktuellen Iterationsschritt ermittelte Gütemaß einen vorbestimmten Wert erreicht, der eine ausreichende Güte repräsentiert, und/oder das im aktuellen Iterationsschritt bestimmte Gütemaß die Güte der Schätzung der Lage des mobilen Objekts gegenüber dem vorhergehenden Iterationsschritt nicht ausreichend verbessert.
Wie bereits oben erwähnt, kann das Gütemaß auf verschiedene Arten definiert sein. Vorzugsweise hängt das Gütemaß für eine Teilmenge von den Kovarianzmatrizen der Schätzung der Lage des mobilen Objekts für die jeweilige Konfiguration der Anzahl von Konfigurationen basierend auf den Landmarken der Teilmenge ab. Diese Kovarianzmatrizen können durch geeignete, aus dem Stand der Technik bekannte Verfahren bestimmt werden. Insbesondere ist für jede Landmarke der Gesamtmenge eine geschätzte Lage der Landmarke in der räumlichen Umgebung und eine Kovarianzmatrix dieser geschätzten Lage hinterlegt. Dabei können basierend auf den Kovarianzmatrizen der Landmarken einer Teilmenge mit Hilfe des aus dem Stand der Technik bekannten Kalman-Filters, insbesondere des Extended Kalman-Filters, die Kovarianzmatrizen der Schätzung der Lage des mobilen Objekts für die jeweiligen Konfigurationen der Anzahl von Konfigurationen basierend auf den Landmarken der Teilmenge ermittelt werden.
In einer weiteren, besonders bevorzugten Ausführungsform hängt das Gütemaß von Einzelmaßen ab, welche jeweils die Güte einer Schätzung der Lage des mobilen Objekts für eine einzelne Konfiguration des mobilen Objekts aus der Anzahl von Konfigurationen basierend auf den Landmarken einer Teilmenge repräsentieren. Vorzugsweise wird im Falle, dass das Einzelmaß einer jeweiligen Konfiguration für eine Teilmenge von Landmarken eine vorgegebene Mindestgüte aufweist, die jeweilige Konfiguration aus der Anzahl von Konfigurationen entfernt. Auf diese Weise werden nur Konfigurationen berücksichtigt, welche auch noch zur Verbesserung des Gütemaßes beitragen können. Vorzugsweise wird diese Variante der Erfindung in dem oben beschriebenen iterativen Verfahren eingesetzt.
In einer weiteren Variante des erfindungsgemäßen Verfahrens ist das Einzelmaß einer jeweiligen Konfiguration ein Entropiemaß für die jeweilige Konfiguration. Die Güte des Einzelmaßes ist dabei umso besser, je kleiner die dem Entropiemaß zu Grunde liegende Entropie ist. In der speziellen Beschreibung findet sich eine entsprechende Definition für eine erfindungsgemäß verwendbare Entropie.
In einer weiteren Ausgestaltung des erfindungsgemäßen Verfahrnes hängt das Einzelmaß einer jeweiligen Konfiguration von der Kovarianzmatrix der Schätzung der Lage des mobilen Objekts für die jeweilige Konfiguration ab. Das Einzelmaß kann dabei definiert sein durch das Maximum der Eigenwerte der Kovarianzmatrix der Schätzung der Lage des mobilen Objekts für die jeweilige Konfiguration und/oder als die Norm dieser Kovarianzmatrix.
Aus den Einzelmaßen kann in geeigneter Weise das Gütemaß für die Anzahl von Konfigurationen definiert werden. Das Gütemaß kann beispielsweise ein Extremum (z. B. das Maximum) der Einzelmaße der jeweiligen Konfigurationen aus der Anzahl von Konfigurationen sein bzw. davon abhängen. Ebenso kann das Gütemaß von der Summe der Einzelmaße der jeweiligen Konfigurationen abhängen, insbesondere von einer gewichteten Summe der Einzelmaße, wobei durch entsprechende Gewichte die jeweiligen Konfigurationen in Abhängigkeit von ihrer Wichtigkeit bei der Schätzung der Lage des mobilen Objekts berücksichtigt werden. Das Gütemaß ist beispielsweise der Mittelwert der Einzelmaße der jeweiligen Konfigurationen.
In einer weiteren, bevorzugten Ausführungsform werden die Einzelmaße aufeinander folgend für Konfigurationen entlang einer oder mehrerer Trajektorien einer Bewegung des mobilen Objekts bestimmt, wobei für die Bestimmung eines Einzelmaßes einer Konfiguration die Schätzung der Lage des Objekts für die vorhergehende Konfiguration entlang der jeweiligen Trajektorie verwendet wird. Auf diese Weise wird die Auswahl der Landmarken im Hinblick auf die vom mobilen Objekt aufgabenspezifisch zu durchlaufenden Trajektorien optimiert.
In einer weiteren Ausgestaltung des erfindungsgemäßen Verfahrens kann basierend auf der erfindungsgemäß bestimmten Auswahl der Teilmenge von Landmarken die Lage der Landmarken neu geschätzt werden. Dazu können aus dem Stand der Technik bekannte Verfahren verwendet werden.
In einer weiteren Ausgestaltung des erfindungsgemäßen Verfahrens werden die Landmarken der Gesamtmenge im Hinblick auf ihre Robustheit bei der Extraktion bewertet. Robustheit bedeutet, wie gut und sicher eine Landmarke aus einer erfassten räumlichen Umgebung extrahiert werden kann. Liegen beispielsweise mehrere Landmarken in der räumlichen Umgebung sehr nahe beieinander, ist die Robustheit verringert, da der Fall auftreten kann, dass die eine Landmarke für die andere gehalten wird. Die Robustheit wird dabei derart berücksichtigt, dass Landmarken mit nicht ausreichender Robustheit aus der Gesamtmenge entfernt werden. Es werden somit erfindungsgemäß nur Landmarken ausgewählt, welche auch sicher extrahiert werden können.
Die in dem erfindungsgemäßen Verfahren verwendeten Landmarken können beliebig ausgestaltet sein. Es kann sich dabei beispielsweise um zweidimensionale Geradenstücke oder auch um Ebenenstücke, insbesondere polygonal umrandete Ebenenstücke, handeln.
In einer weiteren, besonders bevorzugten Ausführungsform wird die räumliche Umgebung mit einem schwenkbaren Laserscanner erfasst, wie dies beispielsweise in der oben genannten Druckschrift [2] beschrieben ist.
Neben dem oben beschriebenen Verfahren betrifft die Erfindung ferner eine Vorrichtung zur rechnergestützten Auswahl von Landmarken aus einer räumlichen Umgebung, umfassend eine Sensoreinrichtung und eine Recheneinheit, wobei mittels der Recheneinheit im Betrieb der Vorrichtung aus einer räumlichen Umgebung, welche mit der Sensoreinrichtung während einer Fahrt des mobilen Objekts erfasst wird, Landmarken extrahiert werden und/oder extrahierte Landmarken bereitgestellt werden. Aus der dadurch geschaffenen Gesamtmenge an Landmarken werden mittels der Recheneinheit eine oder mehrere Teilmengen gebildet, wobei für jede Teilmenge unter Berücksichtigung einer Anzahl von Konfigurationen des mobilen Objekts ein Gütemaß bestimmt wird, welches die Güte einer Schätzung der Lage des mobilen Objekts für die Anzahl von Konfigurationen basierend auf den Landmarken der jeweiligen Teilmenge repräsentiert. Falls das Gütemaß für eine Teilmenge ein vorbestimmtes Kriterium im Hinblick auf eine hohe Güte der Schätzung der Lage des mobilen Objekts für die Anzahl von Konfigurationen erfüllt, wird die Teilmenge der Landmarken ausgewählt.
Die obige Vorrichtung ist vorzugsweise derart ausgestaltet, dass jede Variante des oben beschriebenen erfindungsgemäßen Verfahrnes mit der Vorrichtung durchführbar ist.
Die Erfindung betrifft darüber hinaus ein mobiles Objekt, insbesondere einen Roboter, welches die oben beschriebene erfindungsgemäße Vorrichtung umfasst.
Darüber hinaus umfasst die Erfindung ein Computerprogrammprodukt mit einem auf einem maschinenlesbaren Träger gespeicherten Programmcode zur Durchführung jeder Variante des oben beschriebenen erfindungsgemäßen Verfahrens, wenn das Programm auf einem Rechner abläuft.
Ausführungsbeispiele der Erfindung werden nachfolgend anhand der beigefügten 1 beschrieben. Diese Figur zeigt eine Draufsicht auf zwei Konfigurationen eines mobilen Systems und der in diesen Konfigurationen extrahierten Landmarken.
Gemäß den nachfolgend beschriebenen Ausführungsformen des erfindungsgemäßen Verfahrens werden Landmarken aus einer Vielzahl von lokalen Karten geeignet ausgewählt, um danach zur Lokalisation eines mobilen Objekts verwendet werden zu kön nen. Die einzelnen lokalen Karten können mit dem aus dem Stand der Technik bekannten Atlas-Konzept (siehe Dokument [3]) zu einer gesamten Karte zusammengesetzt werden, welche eine Referenzkarte zur Lokalisation bildet. Die in den lokalen Karten vorhandenen Landmarken werden während einer Lernfahrt des mobilen Objekts aufgenommen. Dies erfolgt dadurch, dass mittels einer Sensoreinrichtung auf dem mobilen Objekt die Umgebung des mobilen Objekts während der Fahrt erfasst wird und aus der erfassten Umgebung die Landmarken extrahiert werden.
1 verdeutlicht eine beispielhafte Extraktion von Landmarken basierend auf zwei unterschiedlichen Konfigurationen q1 und q2 eines mobilen Objekts 1. Unter Konfiguration wird dabei die Lage und Orientierung des mobilen Objekts im Raum verstanden. 1 zeigt die zweidimensionale Bewegung des mobilen Objekts in Draufsicht auf eine Bodenebene, wobei das mobile Objekt beispielsweise ein Gabelstapler sein kann, mit dem Güter transportiert werden. Die Bewegung des Objekts erfolgt dabei in einer lokalen zweidimensionalen Karte, welche durch die Achsen x und y beschrieben wird. Auf dem mobilen Objekt befindet sich eine Sensoreinrichtung, deren lokales Koordinatensystem mit 2 bezeichnet ist. Die Sensoreinrichtung ist dabei ein schwenkbarer Laserscanner, mit dem die Umgebung des mobilen Objekts in jeder der Konfigurationen q1 und q2 in einem 180°-Bereich in Bewegungsrichtung des mobilen Objekts erfasst wird. Die Bewegungsrichtung des Objekts ist dabei für die beiden Konfigurationen q1 und q2 durch einen Pfeil P verdeutlicht. Mit dem Laserscanner wird somit ein Winkelbereich von 90° links und rechts von der Bewegungsrichtung P erfasst. Der Laserscanner schwenkt in diesem Bereich eine Scanebene, in der sich ein Laserstrahl hin und her bewegt. Die Scanebene liegt dabei senkrecht zur Blattebene der 1.
In dem Szenario der 1 werden in der Konfiguration q1 des mobilen Objekts 1 die Landmarken L1 und L2 erfasst und extrahiert, wohingegen die Landmarke L3 in dieser Konfiguration nicht sichtbar ist. Die Extraktion der Landmarken erfolgt dabei beispielsweise mit dem Verfahren aus der Druckschrift [2]. In dem Verfahren dieser Druckschrift werden Landmarken beispielsweise in einer Höhenebene im Bereich des Dachs des Gebäudes extrahiert, in dem sich das Objekt bewegt.
Im Folgenden wird eine lokale Karte durch ein lokales zweidimensionales Koordinatensystem beschrieben, dessen x-Achse und y-Achse parallel zum Boden der Umgebung verlaufen, wie dies auch in 1 gezeigt ist. Die lokale Karte besteht somit aus einer Region
und einer Menge von Landmarken L = {l_i|i = 1, ..., n}. Der Gesamtvorrat aller Landmarken aus allen lokalen Karten wird als L_ges = {l_i|i = 1, ..., n} bezeichnet. Bei einer Lernfahrt wird ein geeignetes Verfahren verwendet, um die Konfigurationen des mobilen Objekts während der Landmarkenextraktion zu schätzen. Beispiele für solche geeigneten Verfahren sind Odometrie oder eine Kombination aus Odometrie und Gyroskopie.
Basierend auf der Aufgabe, die das mobile Objekt durchzuführen hat, wird eine Menge T_K ⊂ R × S¹ an Konfigurationen des mobilen Objekts definiert, bezüglich der erfindungsgemäß die Eignung von Landmarken zur Navigation des mobilen Objekts beurteilt wird. Die Aufgabe des mobilen Systems kann z. B. eine Transportaufgabe sein. In diesem Fall besteht die Menge an Konfigurationen T_K aus den Bahnen, entlang derer das mobile Objekt zum Transport fahren soll. Im Falle der Aufgabe der Reinigung eines Bodens, beispielsweise in einem Supermarkt, sind die entsprechenden Konfigurationen auf der gesamten zu reinigenden Fläche verteilt. Eine Konfiguration q ∈ T_K wird im Folgenden auch als Testkonfiguration bezeichnet.
In der hier beschriebenen Ausführungsform des erfindungsgemäßen Verfahrens sind für die aus den Daten der Sensoreinrichtung extrahierten Landmarken auch statistische Eigenschaften dieser Landmarken hinterlegt. Wenn z. B. Geradenstücke g_i in Hesse'scher Normalform mit einem Abstand d_i vom Koordinatenursprung des lokalen Koordinatensystems und einer entsprechenden Orientierung β_i des Normalenvektors extrahiert werden, sind diese statistischen Eigenschaften durch eine gemeinsame Kovarianzmatrix
definiert. Ebenso können die Kovarianzmatrizen
zwischen Konfigurationen des mobilen Objekts und Landmarken sowie Landmarken untereinander geschätzt werden. Die Kovarianzmatrix bzw. die zu Grunde liegende Verteilung für eine Konfiguration q basierend auf einer Landmarke l kann z. B. aus dem (aus Simulation, Messung oder analytisch gewonnenen) Sensormodell p(l|q) des mobilen Objekts über die Formel
hergeleitet werden. Dabei kann für eine Testkonfiguration r die Wahrscheinlichkeitsverteilung der Konfigurationen als die odometrie- und gyroskopbasierte Wahrscheinlichkeitsverteilung aus der Lernfahrt genommen werden, also p(q) = p(g|r).
In der hier beschriebenen Variante des erfindungsgemäßen Verfahrens wird die Wahrscheinlichkeitsverteilung der Konfiguration eines mobilen Objekts aus verschiedenen Teilmengen von Landmarken basierend auf dem Extended Kalman-Filter (EKF) geschätzt. Es wird dabei angenommen, dass sowohl die Konfigurationen des mobilen Objekts als auch die Landmarken normalverteilt sind.
Bei der Initialisierung, d. h. ohne Referenzierung auf Landmarken, wird eine Testkonfiguration q = (x y γ)^T angenommen, welche eine große, aber in der gegebenen Anwendung realistische Kovarianzmatrix Σ_q,{} aufweist. x und y beschreiben dabei die Position des Objekts im lokalen Koordinatensystem und γ die Orientierung des Objekts in diesem Koordinatensystem. Zunächst erfolgt eine Schätzung der Lage des mobilen Objekts unter Berücksichtigung einer einzelnen referenzierten Landmarke l, deren Kovarianzmatrix Σ_d,β = Σ_l bekannt ist. Basierend darauf sind die Parameter der prädizierten Messung z = (d_m, β_m), d. h. die gemessene Position d_m und Orientierung β_m in Hesse'scher Normalform im lokalen Koordinatensystem 2 der Sensoreinrichtung, eine Funktion sowohl der Landmarke als auch der Konfiguration des mobilen Objekts. Das heißt, es gilt: z = (dm, βm) = h(l, q) = h((d, β), (x y γ)T) = = (d – x·cos(γ) – y·sin(γ), β – γ)
Dabei bezeichnet h(l, q) die Beobachtungsfunktion, welche die Position und Orientierung der Landmarke l für die Konfiguration q des mobilen Objekts im lokalen Koordinatensystem 2 der Sensoreinrichtung wiedergibt.
Mit den Jacobischen Matrizen Hl = ∂h∂l und Hq = ∂h∂q wird die Kovarianz der erwarteten Messung approximiert durch Σz = Hq·Σq,{}·HTq + Hl·Σl·HTl und ent sprechend dem hinlänglich bekannten Kalman-Filter-Update wird die Kovarianzmatrix der Schätzung der Konfiguration q nach Berücksichtigung der Landmarke l wie folgt berechnet: Σq,{l} = Σq,{} – HTq ·(Hq·Σq,{}·HTq + Hl·Σl·HTl )–1·Hq
Verallgemeinert ergibt sich aus der Kovarianzmatrix
der Konfiguration q_r, bei der k Landmarken einer Landmarkenmenge L_K zur Schätzung verwendet werden, die Kovarianzmatrix
bei Hinzunahme der k + 1-ten Landmarke zu der Landmarkenmenge durch folgende Gleichung:
Vorteilhafterweise wird bei jeder Landmarke dabei vermerkt, von welchen der Konfigurationen des mobilen Objekts (gemäß der initialen Schätzung der Konfiguration des mobilen Objekts) aus diese entsprechende Landmarke sichtbar ist.
Erfindungsgemäß werden die Landmarken aus der Gesamtheit der Landmarken derart ausgewählt, dass die Schätzung einer Konfiguration des mobilen Objekts, d. h. eine Schätzung seiner Position und Orientierung, aufgrund einer Messung dieser Landmarken durch Sensoren gemäß einem Gütekriterium möglichst gut ist. Zur Definition des Gütekriteriums wird dabei ein Gütemaß verwendet, welches in einer Ausführungsform der Erfindung die „Entropie” bzw. „Information” ist. Die Entropie E(q) einer Zufallsvariable q ist in der hier beschriebenen Ausführungsform gegeben durch E(q) = –∫p(q)·ln(p(q))dq und misst, wie sehr die Wahrscheinlichkeitsmasse auf einen Punkt konzentriert ist. Falls die Zufallsvariable gleichverteilt ist, d. h. wenn alle Zustände der Zufallsvariablen gleich wahrscheinlich sind, ist die Entropie maximal. Ein mögliches Qualitätsmaß μ(q) ist somit gegeben durch die Entropie E(q), d. h. es gilt: μ(q) = E(q). Dieses Maß ist dabei zu minimieren.
In der hier beschriebenen Ausführungsform wird die Konfiguration eines mobilen Objekts als normalverteilt angenommen. In diesem Fall kann als Gütemaß das Maximum der Eigenwerte der Kovarianzmatrix Σ_q bzw. die Norm μ(q) = ∥⁣Σ_q∥⁣ der Kovarianzmatrix einer Konfiguration q verwendet werden, wobei dieses Maximum bzw. die Norm zu minimieren sind. Weitere mögliche Gütemaße sind denkbar, wie z. B. die Vorgabe von Obergrenzen für die Varianz in Translation und Rotation des mobilen Objekts.
In einer bevorzugten Variante sind die Gütemaße so ausgestaltet, dass eine Qualitätsgrenze mit angegeben wird, mit der das Gütemaß begrenzt wird. Hierdurch wird erreicht, dass nicht für eine Konfiguration weiter optimiert wird, welche ohnehin sehr gut geschätzt wird, während für eine andere Konfiguration die Schätzung noch statistisch sehr unsicher ist.
Zur Auswahl einer geeigneten Menge von Landmarken für die durch das mobile Objekt durchzuführende Aufgabe wird modelliert, wie gut eine Konfiguration q des mobilen Objekts unter der Annahme geschätzt werden kann, dass es in einer Testkonfiguration q_r ∈ T_K ist und die Landmarkenmenge L_K aus dem Gesamtvorrat der Landmarken zur Verfügung steht. Es wird somit die Konfiguration
betrachtet. Die einzelnen Maße
werden über die einzelnen Testkonfigurationen hinweg zu einem Gesamtmaß für die Eignung der Menge L_K der Landmarken zur Konfigurationsschätzung zusammengefasst. Es gibt dabei verschiedene Möglichkeiten, dieses Gesamtmaß zu definie ren. Das Gesamtmaß kann als Maximum M_m, als Mittel M_d oder als gewichtetes Mittel M_g der Einzelmaße definiert sein. Wird das Maximum als Gesamtmaß verwendet, lautet dieses wie folgt:
Wird das Mittel als Gesamtmaß verwendet, lautet dieses wie folgt:
Für das gewichtete Mittel wird eine Gewichtsfunktion
verwendet, wobei das gewichtete Mittel folgende Relation erfüllt:
In den vorangegangenen Gleichungen bezeichnet r eine Konfiguration aus der Gesamtmenge an Testkonfigurationen T_K. Mit der obigen Gewichtsfunktion g(r) lässt sich einstellen, welche Priorität die Lokalisierung einer gegebenen Testkonfiguration haben soll. Ebenso lassen sich die obigen Maße
auch spezifisch für jede Testkonfiguration angeben und dann nach den oben gegebenen Regeln zu Gesamtmaßen zusammenfassen. Damit lassen sich unterschiedliche Genau igkeitsanforderungen an verschiedene Testkonfigurationen formulieren, beispielsweise hohe Genauigkeit an einer Docking-Station des mobilen Objekts und geringere Genauigkeit bei einer Bewegung des Objekts auf freier Strecke. Jedes der oben genannten Gesamtmaße kann zur Bewertung der Landmarken in einer Karte verwendet werden. Damit ist eine aufgabengerechte automatische Extraktion einer geeigneten Landmarkenmenge möglich, wobei diese Auswahl im Anschluss bei der Lokalisation des mobilen Objekts eingesetzt wird.
Eine erfindungsgemäß nicht realisierte Variante zur Auswahl von Landmarken besteht darin, dass alle möglichen Teilmengen der Gesamtmenge L_ges von Landmarken nach einem der obigen Maße bewertet und die beste Teilmenge ausgesucht wird. Dieses Verfahren ist jedoch nicht praktikabel, da die Gesamtmenge L_ges selbst sehr groß werden kann und die Anzahl der möglichen Teilmengen mit
unverhältnismäßig groß wird. Daher wird in einer bevorzugten Ausführungsform des erfindungsgemäßen Verfahrens ein inkrementeller Aufbau der Auswahl L_K ⊂ L_ges der Landmarken verwendet. Dabei werden iterativ Landmarken zu der Menge von Landmarken hinzugenommen und basierend auf der jeweils neu entstehenden Landmarkenmenge die Qualität der Schätzung der betrachteten Konfigurationen bestimmt.
In einem ersten Schritt sind in dem iterativen Verfahren keine Landmarken ausgewählt, d. h. die Menge der Landmarken L_K ist leer, es gilt also: L_K = {}. Die Konfigurationen q_r,{} für den ersten Schritt werden mit geringer Information initialisiert, z. B. als gleichverteilt im Falle einer stichprobenbasierten Beschreibung der Verteilung oder mit dem Mittelwert r und einer sehr großen Kovarianz im Falle einer Normalver teilung. Basierend auf dieser Initialisierung wird das Gesamtmaß M berechnet, welches im ersten Schritt als M({}) bezeichnet wird, da es zur Berechnung keine referenzierten Landmarken verwendet. Im nächsten Schritt wird für alle Landmarken l ∈ L_ges das jeweilige Gesamtmaß M({l}) ermittelt und diejenige Landmarke ausgesucht, welche die größte Verbesserung bedeutet. Diese Landmarke lautet l₁ und ergibt sich aus folgender Gleichung:
Verallgemeinert wird somit in dem k + 1-ten Iterationsschritt basierend auf der Landmarkenmenge L_K,k = {l₁, ..., l_k} des k-ten Iterationsschritts die neu zu der Landmarkenmenge hinzukommende Landmarke l_k+1 wie folgt bestimmt:
Die obigen Iterationsschritte werden so lange wiederholt, bis eine vorher gesetzte Grenze für M erreicht wurde oder keine weitere Verbesserung erzielt wird. In einer vorteilhaften Ausführungsform wird dabei während der Iteration für jede Testkonfiguration die Kovarianz
sowie das Maß
gespeichert. In der hier beschriebenen Ausführungsform wurde die Kovarianz
bereits bei der Aufnahme der Landmarken bestimmt und gespeichert, sie kann jedoch auch bei der ersten Iteration bestimmt und dann gespeichert werden.
Die Speicherung aller obiger Kovarianzmatrizen bedeutet einen sehr hohen Speicherplatzbedarf. Dieser Speicherplatzbedarf ist jedoch wirtschaftlich und technisch vertretbar, da die Kovarianzmatrizen nur bei einer entsprechenden Installationsfahrt des mobilen Objekts und nicht während der späteren Lokalisation des mobilen Objekts verwendet werden müssen. Somit kann beispielsweise nur während der Installationsfahrt eine für diese Fahrt vorgesehene Speichererweiterung im mobilen Objekt integriert werden. Durch die Speicherung der Kovarianzmatrizen kann für eine erweitere Landmarkenmenge im k + 1-ten Iterationsschritt, d. h. für L_K,k+1 = L_K,k ∪ {l}, die neue Kovarianzmatrix dieser erweiterten Landmarkenmenge auf einfache Weise durch das bereits oben erwähnte Kalman-Filter-Update wie folgt berechnet werden:
Damit lässt sich leicht der zusätzliche Beitrag einer weiteren Landmarke zur Kovarianz ermitteln und beurteilen, ob die entsprechende Landmarke zur Verbesserung des Qualitätsmaßes beiträgt.
Eine weitere Reduktion der Komplexität des Verfahrens ergibt sich in einer bevorzugten Variante dadurch, dass bei jedem Iterationsschritt nur noch diejenigen Testkonfigurationen betrachtet werden, die zur Verbesserung des Gesamtmaßes noch beitragen können und diejenigen Testkonfiguration weggelassen werden, bei denen das einzelne Maß μ einen individuellen Schwellenwert bereits erreicht hat. Eine solche Testkonfiguration wird dann aus der Menge der Testkonfigurationen gestrichen. In einer weiteren vorteilhaften Ausführungsform wird nach Beendigung der Auswahl der Landmarken ein beliebiges, aus dem Stand der Technik bekanntes Verfahren zur Neuschätzung der Landmarken verwendet. Dadurch kann die Genauigkeit der Lageschätzung der Landmarken und damit der Karte wesentlich verbessert werden.
In einer weiteren Ausführungsform des erfindungsgemäßen Verfahrens werden Landmarken zusätzlich zu ihrem Beitrag zur Lokalisierung auch bezüglich ihrer Robustheit bewertet. Robustheit bedeutet dabei, wie zuverlässig eine Landmarke aus der erfassten Umgebung extrahiert werden kann. Die Robustheit kann beispielsweise bei Landmarken in der Form von horizontalen Geraden durch die minimale Abweichung nach oben und unten definiert werden, innerhalb derer in einzelnen diskreten horizontalen Schnitten auch noch eine Landmarke mit dem gleichen Beitrag bezüglich der Lokalisierung bzw. mit der gleichen Projektion in die Bodenebene liegt. Je größer dieser minimale Abstand ist, desto robuster ist die Landmarke. Dieses Robustheitsmaß wird skaliert und kann geeignet je nach Anwendungsfall in dem obigen Gesamtmaß berücksichtigt werden. Eine Berücksichtigung kann dabei derart stattfinden, dass in der Auswahl der Landmarken nur Landmarken enthalten sein dürfen, welche eine bestimmte Mindestrobustheit aufweisen.
In einer weiteren Ausführungsform des erfindungsgemäßen Verfahrens sind die einzelnen Testkonfigurationen, welche basierend auf den Landmarken geschätzt werden, entlang einer oder mehrerer Testtrajektorien angeordnet. Dabei werden die einzelnen Konfigurationen für eine Landmarkenmenge hintereinander entlang der jeweiligen Trajektorie durchlaufen, wobei für eine Testkonfiguration zur Initialisierung die Schätzung der Konfiguration an der vorherigen Position auf der Trajektorie eingesetzt wird. Auf diese Weise wird die Auswahl der Land marken im Hinblick auf die vom mobilen Objekt aufgabenspezifisch zu durchlaufenden Trajektorien optimiert.
In einer weiteren vorteilhaften Ausführungsform des erfindungsgemäßen Verfahrens werden zusätzlich bzw. anstatt einer Schätzung einer zweidimensionalen Position und Orientierung des mobilen Objekts basierend auf zweidimensionalen Landmarken (wie dies in 1 gezeigt ist) weitere Landmarken ermittelt, die eine Schätzung der Position des mobilen Objekts im dreidimensionalen Raum sowie die Schätzung aller drei Raumwinkel unterstützen.
Literaturverzeichnis

[1] Thrun, S., Burgard, W. und Fox, D., Probabilistic Robotics. 2005. Seiten 312 bis 322, MIT Press, Cambridge
[2] WO 2007/096240 A1
[3] Bosse, M., Newman, P., Leonard, J., Soika, M., Teller, S., An Atlas Framework for Scalable Mapping. Seiten 1899 bis 1906, Proceedings of the 2003 IEEE International Conference an Robotics & Automation, Taipai, Taiwan, September 2003

Claims

Verfahren zur rechnergestützten Auswahl von Landmarken (L1, L2, L3) aus einer räumlichen Umgebung zur Lokalisation eines mobilen Objekts (1), bei dem: – eine oder mehrere Teilmengen aus einer Gesamtmenge von Landmarken (L1, L2, L3) gebildet werden, wobei für jede Teilmenge unter Berücksichtigung einer Anzahl von Konfigurationen (q1, q2) des mobilen Objekts (1), welche jeweils eine Lage des mobilen Objekts (1) in der räumlichen Umgebung darstellen, ein Gütemaß bestimmt wird, welches die Güte einer Schätzung der Lage des mobilen Objekts (1) für die Anzahl von Konfigurationen (q1, q2) basierend auf den Landmarken (L1, L2, L3) der jeweiligen Teilmenge repräsentiert; – falls das Gütemaß für eine Teilmenge ein vorbestimmtes Kriterium in Bezug auf eine hohe Güte der Schätzung der Lage des mobilen Objekts (1) für die Anzahl von Konfigurationen (q1, q2) erfüllt, die Teilmenge der Landmarken (L1, L2, L3) ausgewählt wird.
Verfahren nach Anspruch 1, wobei die Gesamtmenge von Landmarken aus einer räumlichen Umgebung extrahiert wird, die während einer Fahrt des später zu lokalisierenden Objekts erfasst wird.
Verfahren nach Anspruch 1 und 2, wobei die Gesamtmenge von Landmarken bereitgestellt wird.
Verfahren nach mindestens einem der vorliegenden Ansprüche, bei dem bei Erfüllung des vorbestimmen Kriteriums zumindest die Bedingung erfüllt ist, dass das Gütemaß für die Teilmenge einen vorbestimmten Wert erreicht, der eine ausreichende Güte repräsentiert.
Verfahren nach mindestens einem der vorhergehenden Ansprüche, bei dem die Teilmengen aus der Gesamtmenge der Landmar ken (L1, L2, L3) basierend auf einer Iteration gebildet werden, wobei in einem aktuellen Iterationsschritt eine oder mehrere neue Teilmengen aus einer im vorhergehenden Iterationsschritt bestimmten Teilmenge gebildet werden, wobei jede neue Teilmenge aus der im vorhergehenden Iterationsschritt bestimmten Teilmenge und zumindest einer zusätzlichen Landmarke (L1, L2, L3) aus der Gesamtmenge der Landmarken (L1, L2, L3) besteht und aus den neuen Teilmengen diejenige Teilmenge bestimmt wird, deren Gütemaß die größte Güte der Schätzung der Lage des mobilen Objekts (1) für die Anzahl von Konfigurationen (q1, q2) repräsentiert.
Verfahren nach Anspruch 5, bei dem die Iteration beendet wird, wenn das im aktuellen Iterationsschritt ermittelte Gütemaß einen vorbestimmten Wert erreicht, der eine ausreichende Güte repräsentiert, und/oder das im aktuellen Iterationsschritt bestimmte Gütemaß die Güte der Schätzung der Lage des mobilen Objekts (1) gegenüber dem vorhergehenden Iterationsschritt nicht ausreichend verbessert.
Verfahren nach einem mindestens der vorhergehenden Ansprüche, bei dem das Gütemaß für eine Teilmenge von Kovarianzmatrizen der Schätzung der Lage des mobilen Objekts (1) für die jeweiligen Konfigurationen (q1, q2) der Anzahl von Konfigurationen (q1, q2) basierend auf den Landmarken (L1, L2, L3) der Teilmenge abhängt.
Verfahren nach Anspruch 7, bei dem für jede Landmarke (L1, L2, L3) der Gesamtmenge eine geschätzte Lage der Landmarke (L1, L2, L3) in der räumlichen Umgebung und eine Kovarianzmatrix der geschätzten Lage hinterlegt ist, wobei basierend auf den Kovarianzmatrizen der Landmarken (L1, L2, L3) einer Teilmenge mit Hilfe des Kalman-Filters die Kovarianzmatrizen der Schätzung der Lage des mobilen Objekts (1) für die jeweiligen Konfigurationen (q1, q2) der Anzahl von Konfigurationen (q1, q2) basierend auf den Landmarken (L1, L2, L3) der Teilmenge ermittelt werden.
Verfahren nach mindestens einem der vorhergehenden Ansprüche, bei dem das Gütemaß von Einzelmaßen abhängt, welche jeweils die Güte einer Schätzung der Lage des mobilen Objekts (1) für eine einzelne Konfiguration (q1, q2) des mobilen Objekts (1) aus der Anzahl von Konfigurationen (q1, q2) basierend auf den Landmarken (L1, L2, L3) einer Teilmenge repräsentieren.
Verfahren nach Anspruch 9, bei dem im Falle, dass das Einzelmaß einer jeweiligen Konfiguration (q1, q2) für eine Teilmenge von Landmarken (L1, L2, L3) eine vorgegebene Mindestgüte aufweist, die jeweilige Konfiguration (q1, q2) aus der Anzahl von Konfigurationen (q1, q2) entfernt.
Verfahren nach Anspruch 9 oder 10, bei dem das Einzelmaß einer jeweiligen Konfiguration (q1, q2) ein Entropiemaß für die jeweilige Konfiguration (q1, q2) ist.
Verfahren nach einem der Ansprüche 9 bis 11, wenn abhängig von Anspruch 5, bei dem das Einzelmaß einer jeweiligen Konfiguration (q1, q2) von der Kovarianzmatrix der Schätzung der Lage des mobilen Objekts (1) für die jeweilige Konfiguration (q1, q2) abhängt.
Verfahren nach Anspruch 12, bei dem das Einzelmaß das Maximum der Eigenwerte der Kovarianzmatrix der Schätzung der Lage des mobilen Objekts (1) für die jeweilige Konfiguration (q1, q2) und/oder die Norm dieser Kovarianzmatrix ist.
Verfahren nach einem der Ansprüche 9 bis 13, bei dem das Gütemaß von einem Extremum der Einzelmaße der jeweiligen Konfigurationen (q1, q2) aus der Anzahl von Konfigurationen (q1, q2) abhängt.
Verfahren nach einem der Ansprüche 9 bis 14, bei dem das Gütemaß von der Summe der Einzelmaße der jeweiligen Konfigu rationen (q1, q2) aus der Anzahl von Konfigurationen (q1, q2) abhängt, insbesondere von einer gewichteten Summe der Einzelmaße.
Verfahren nach einem der Ansprüche 9 bis 15, bei dem die Einzelmaße aufeinander folgend für Konfigurationen (q1, q2) entlang einer oder mehrerer Trajektorien einer Bewegung des mobilen Objekts (1) bestimmt werden, wobei für die Bestimmung eines Einzelmaßes einer Konfiguration (q1, q2) die Schätzung der Lage des mobilen Objekts (1) für die vorhergehende Konfiguration entlang der jeweiligen Trajektorie verwendet wird.
Verfahren nach mindestens einem der vorhergehenden Ansprüche, bei dem basierend auf der ausgewählten Teilmenge von Landmarken (L1, L2, L3) die Lagen der Landmarken (L1, L2, L3) neu geschätzt werden.
Verfahren nach mindestens einem der vorhergehenden Ansprüche, bei dem die Landmarken (L1, L2, L3) der Gesamtmenge im Hinblick auf ihre Robustheit bei der Extraktion bewertet werden, wobei Landmarken mit nicht ausreichender Robustheit aus der Gesamtmenge entfernt werden.
Verfahren nach mindestens einem der vorhergehenden Ansprüche, bei dem die Landmarken (3) Geradenstücke und/oder Ebenenstücke, insbesondere polygonal umrandete Ebenenstücke, sind.
Verfahren nach mindestens einem der vorhergehenden Ansprüche, bei dem die räumliche Umgebung mit einem schwenkbaren Laserscanner (2) erfasst wird.
Vorrichtung zur rechnergestützten Auswahl von Landmarken (L1, L2, L3) aus einer räumlichen Umgebung zur Lokalisation eines mobilen Objekts (1), umfassend eine Sensoreinrichtung und eine Recheneinheit, wobei mittels der Recheneinheit im Betrieb der Vorrichtung: – eine oder mehrere Teilmengen aus einer Gesamtmenge von Landmarken (L1, L2, L3) gebildet werden, wobei für jede Teilmenge unter Berücksichtigung einer Anzahl von Konfigurationen (q1, q2) des mobilen Objekts (1), welche jeweils eine Lage des mobilen Objekts (1) in der räumlichen Umgebung darstellen, ein Gütemaß bestimmt wird, welches die Güte einer Schätzung der Lage des mobilen Objekts (1) für die Anzahl von Konfigurationen (q1, q2) basierend auf den Landmarken (L1, L2, L3) der jeweiligen Teilmenge repräsentiert; – falls das Gütemaß für eine Teilmenge ein vorbestimmtes Kriterium in Bezug auf eine hohe Güte der Schätzung der Lage des mobilen Objekts (1) für die Anzahl von Konfigurationen (q1, q2) erfüllt, die jeweilige Teilmenge der Landmarken (L1, L2, L3) ausgewählt wird.
Vorrichtung nach Anspruch 21, wobei die Recheneinheit im Betrieb einer Vorrichtung die Gesamtmenge von Landmarken aus einer räumlichen Umgebung extrahiert wird, die während einer Fahrt des später zu lokalisierenden Objekts erfasst wird.
Vorrichtung nach Anspruch 21 und/oder 22, wobei die Recheneinheit im Betrieb der Vorrichtung die Gesamtmenge von Landmarken bereitstellt.
Vorrichtung nach Anspruch 21, welche derart ausgestaltet ist, dass mit der Vorrichtung ein Verfahren nach einem der Ansprüche 2 bis 18 durchführbar ist.
Mobiles Objekt, insbesondere Roboter, umfassend eine Vorrichtung nach Anspruch 21 oder 22.
Computerprogrammprodukt mit einem auf einem maschinenlesbaren Träger gespeicherten Programmcode zur Durchführung eines Verfahrens nach einem der Ansprüche 1 bis 20, wenn das Programm auf einem Rechner abläuft.