Titel

Verfahren zum Ausdünnen eines SLAM-Graphen, Verfahren zum Betrieb eines mobilen Geräts und mobiles Gerät

Die vorliegende Erfindung betrifft ein Verfahren zum Ausdünnen eines SLAM- Graphen, der zum Betreiben eines mobilen Geräts wie z.B. eines Haushaltsrobo ters, verwendet wird, ein Verfahren zum Betreiben eines mobilen Geräts, eine Recheneinheit und ein Computerprogramm zu dessen Durchführung sowie ein mobiles Gerät.

Hintergrund der Erfindung

Mobile Geräte wie z.B. Saug- oder Wischroboter oder andere Haushaltsroboter bewegen sich typischerweise in einer zu bearbeitenden Umgebung wie z.B. einer Wohnung. Eines der grundlegenden Probleme eines solchen oder auch anderen mobilen Geräts besteht darin, sich zu orientieren, also zu wissen, wie die Umge bung aussieht und wo es sich (absolut) befindet. Dafür ist das mobile Gerät z.B. mit verschiedenen Sensoren ausgerüstet, wie z.B. Ultraschall-Sensoren, Kame ras oder Lidar-Sensoren, mit deren Hilfe die Umgebung z.B. zwei- oder dreidi mensional erfasst wird. Dies ermöglicht es dem mobilen Gerät, sich lokal zu be wegen, Hindernisse rechtzeitig zu erkennen und zu umfahren.

Wenn darüber hinaus die absolute Position des mobilen Geräts bekannt ist, z.B. aus zusätzlichen GPS-Sensoren, kann eine Karte aufgebaut werden. Dabei misst das mobile Gerät die relative Position möglicher Hindernisse zu ihm und kann mit seiner bekannten Position dann die absolute Position der Hindernisse bestim men, die anschließend in die Karte eingetragen werden. Dies funktioniert aller dings nur bei extern zur Verfügung gestellten Positionsinformation. Als SLAM ("Simultaneous Localization and Mapping", in etwa: Simultane Positi onsbestimmung und Kartierung) wird ein Verfahren in der Robotik bezeichnet, bei dem ein mobiles Gerät wie ein Roboter gleichzeitig eine Karte seiner Umge bung erstellen und seine räumliche Lage innerhalb dieser Karte schätzen kann oder muss. Es dient damit dem Erkennen von Hindernissen und unterstützt somit die autonome Navigation.

Offenbarung der Erfindung

Erfindungsgemäß werden ein Verfahren zum Ausdünnen eines SLAM-Graphen, ein Verfahren zum Betreiben eines mobilen Geräts, eine Recheneinheit und ein Computerprogramm zu dessen Durchführung sowie ein mobiles Gerät mit den Merkmalen der unabhängigen Patentansprüche vorgeschlagen. Vorteilhafte Aus gestaltungen sind Gegenstand der Unteransprüche sowie der nachfolgenden Be schreibung.

Die Erfindung beschäftigt sich mit dem Thema SLAM sowie dessen Anwendung bei mobilen Geräten. Ein typisches Beispiel für ein mobiles Gerät ist ein Haus haltsroboter wie z.B. ein Saug- und/oder Wischroboter. Ebenso wird SLAM aber auch bei anderen Arten von Robotern, auch bei Drohnen sowie Fahrzeugen, wenn diese z.B. zumindest teilweise automatisiert fahren, verwendet. Bei SLAM wiederum gibt es verschiedene Ansätze, Karten und Positionen darzustellen. Ein Ansatz, der auch im Rahmen der vorliegenden Erfindung verwendet wird, ist sog. graphbasiertes SLAM ("graph-based SLAM"). Hier wird die Karte anhand eines Graphen, nachfolgend auch als SLAM-Graph bezeichnet, dargestellt, der eine Vielzahl an Knoten und eine Vielzahl an Kanten aufweist, wobei eine Kante in der Regel jeweils zwei Knoten verbindet. Die Endpunkte der Kante liegen damit auf den Knoten. Grundsätzlich kann es aber auch Kanten geben, die nur mit einem oder auch mit mehr als zwei Knoten verbunden sind. Sobald ein solcher Graph erstellt ist, kann die Karte berechnet werden, indem die räumliche Konfiguration der Knoten gefunden wird, die größtenteils mit den durch die Kanten modellierten Messungen übereinstimmt. Die Knoten entsprechen dabei jeweils Posen (Position und Orientierung) des mo bilen Geräts, die Kanten entsprechen Verbindungen dazwischen. Dabei gibt es verschiedene Arten von Kanten. Eine Kante kann aus Beobachtungen der Umge bung gewonnen werden, z.B. durch Bestimmung der Richtung, in der ein identifi ziertes Hindernis liegt. Eine Kante kann aber auch aus einer (tatsächlichen) Be wegung des mobilen Geräts gewonnen werden, z.B. durch Odometrie. Nach ei ner bestimmten Strecke, die sich das mobile Gerät bewegt hat, kann dann z.B. ein neuer Knoten ergänzt werden, wobei gleichzeitig Umgebungsinformationen erfasst und gespeichert werden. Eine solche Kante soll nachfolgend auch als Be wegungskante bezeichnet werden. Wenn das mobile Gerät nach längerem Auf enthalt in zuvor unbekannter Umgebung wieder eine bekannte Umgebung (in der schon einmal Umgebungsinformationen erfasst wurden) erreicht, kann versucht werden, die früheren mit den aktuellen Umgebungsinformationen derselben Um gebung zu verknüpfen ("matchen"). Dabei gibt es zwei Knoten bzw. Orte, bei de nen Umgebungsinformationen erfasst werden. Wenn das Verknüpfen (oder An gleichen) erfolgreich ist, kann eine Kante zwischen diesen beiden Knoten gebil det werden. Eine solche Kannte wird nachfolgend auch als Loop-Closure-Kante bezeichnet, da damit sozusagen eine Schleife geschlossen wird.

Das mobile Gerät wird dabei so betrieben, dass Umgebungsinformation erhalten werden, z.B. durch ein Steuergerät des mobilen Geräts, die insbesondere mittels eines oder mehrerer Sensoren wie z.B. Videokameras, Radar-Sensoren, Lidar- Sensoren, Laser-Entfernungsmesser, Ultraschallsensoren, Inertialsensoren und/oder Odometern erfasst werden. Diese Umgebungsinformationen umfassen damit also z.B. Video- bzw. Kameradaten, Entfernungsangaben zu Hindernissen oder zurückgelegte Strecken. Basierend auf diesen Umgebungsinformationen sowie einem aktuellen SLAM-Graphen bzw. einer entsprechenden Karte und z.B. durch Anwendung eines geeigneten SLAM-Algorithmus wird eine aktuelle Pose bzw. Position und/oder Orientierung des mobilen Geräts bestimmt.

Basierend darauf können dann Steuerungsanweisungen zum Betreiben des mo bilen Geräts bestimmt bzw. erzeugt werden, die dann durch das mobile Gerät umgesetzt werden können, oder zunächst dorthin übermittelt werden können (falls die Berechnungen außerhalb des mobilen Geräts erfolgen, z.B. auf einem gerätefremden Rechensystem, z.B. in einer sog. Cloud). Die Steuerungsanwei sungen können z.B. im Rahmen eines Steuerungsalgorithmus bestimmt werden. Dies wiederholt sich immer wieder, z.B. alle 50 cm. Auf diese Weise kann das mobile Gerät z.B. seine Arbeit wie Saugen verrichten, ebenso aber auch die Karte immer weiter verbessern.

Durch ständiges Hinzufügen von Knoten und Kanten zum SLAM-Graphen wird dieser allerdings immer größer, d.h. die Datenmenge wird größer und sämtliche Berechnungen, die auf dem SLAM-Graphen basieren, benötigen mehr Rechen leistung und/oder mehr Zeit.

Eine Lösung für dieses Problem ist, den SLAM-Graphen auszudünnen, d.h. Kno ten und/oder Kanten daraus zu entfernen und so die Datenmenge zu reduzieren. Dies führt allerdings zu einem anderen Problem: die Genauigkeit der durch den SLAM-Graphen dargestellten Karte kann mitunter deutlich reduziert werden bzw. deren Informationsgehalt kann schwinden. Vor diesem Hintergrund wird eine Möglichkeit vorschlagen, einen SLAM-Graphen auszudünnen, sodass dessen Größe reduziert wird, die Genauigkeit allerdings möglichst gut erhalten bleibt.

Hierzu wird der SLAM-Graph (z.B. als Datensatz, in dem also die Knoten und Kanten und ggf. weitere Informationen enthalten sind) erhalten, z.B. direkt in ei ner Recheneinheit oder einem Steuergerät des mobilen Geräts oder auch in ei ner externen Recheneinheit. Dann werden Knoten aus dem SLAM-Graphen ent fernt, um einen aktualisierten SLAM-Graphen (also z.B. einen aktualisierten Da tensatz), zu erhalten; dieser wird ausgegeben, z.B. an eine entsprechende Ein heit im mobilen Geräten oder dort im Steuergerät. Dabei umfasst das Entfernen eines Knotens jeweils das Bestimmen desjenigen der Vielzahl an Knoten, dessen skaleninvariante Dichte an weiteren Knoten um diesen Knoten am höchsten ist, und dann das Entfernen des auf diese Weise bestimmten Knotens, dessen Dichte am höchsten ist, aus dem SLAM-Graphen.

Um die Anzahl der Knoten innerhalb des SLAM-Graphen zu begrenzen, ist es in der Regel nötig, die Knoten im Laufe der Zeit gewissenhaft zu entfernen. Im All gemeinen kommen hierfür zumindest zwei Strategien in Betracht. Eine Strategie ist, einen oder mehrere Knoten auszuwählen und zu entfernen (auch als "Margi- nalisieren" bezeichnet). Eine andere Strategie ist, zwei oder mehr Knoten auszu wählen und sie zu einem zu verschmelzen. Im Fall von auf Lidar-Sensoren basie rendem SLAM hat die zweite Strategie z.B. den Nachteil, dass die Lidar-Scans (Umgebungsinformationen) fusioniert werden müssen und die Position des neuen Knotens nicht mit der Position übereinstimmt, an der die Lidar-Scans ur sprünglich aufgenommen wurden. Somit ist es nicht mehr möglich, eine Nachver folgung von Lidar-Strahlen im Raum (die zu den Umgebungsinformationen ge führt haben) auf einfache Weise durchzuführen, was für bestimmte Algorithmen wichtig ist. Außerdem müssen alle weiteren Informationen, die mit den beteiligten Knoten verknüpft sein können, ebenfalls fusioniert werden. Schließlich ist der fu sionierte Knoten nicht zwangsläufig Teil der ursprünglichen Trajektorie und könnte sich z.B. auf unpassierbarem Bereich (z.B. in einem Hindernis) befinden. Aus diesen Gründen bietet es sich an, die erste Strategie zu verwenden.

Hier sind dann die Knoten zum Entfernen zu bestimmen. Im Allgemeinen könnte die gleichzeitige Entfernung mehrerer Knoten in Betracht gezogen werden und ein kombinierter Effekt dieser Operation analysiert werden. Dies ist jedoch schwierig zu analysieren, sodass das Entfernen einzelner Knoten bevorzugt ist. Als zu entfernender Knoten sollte ein Knoten ausgewählt werden, der für die Ge samtabbildungsqualität (d.h. für die Qualität der Darstellung der Karte durch den SLAM-Graphen) von geringer Bedeutung ist und dessen Entfernung die zukünf tige Leistung des SLAM-Algorithmus so wenig wie möglich beeinträchtigt. Um die Bedeutung eines Knotens zu quantifizieren, können geometrische oder informati onstheoretische Maße verwendet werden.

Informationstheoretische Maße versuchen, die in jedem Knoten enthaltenen In formationen oder die Informationen des zugehörigen Laser-Scans (bzw. allge mein der erfassten Umgebungsinformationen) zu quantifizieren. Vorteilhaft ist, den Knoten so zu entfernen, dass der Informationsverlust minimiert wird. Das Hauptproblem bei diesem Ansatz besteht allerdings darin, dass die tatsächlichen Informationen innerhalb eines Scans kaum zu quantifizieren sind. Die Informatio nen können basierend auf den Besetzungswahrscheinlichkeiten von Zellen in ei ner probabilistischen Gitterkarte berechnet werden. Wie sich gezeigt hat, tendiert jedoch dieser Ansatz dazu, Scans mit hohem Rauschen, falschen Messungen oder schlechter Ausrichtung als hochinformativ zu betrachten, da sie die Wahr scheinlichkeiten innerhalb der Rasterkarte stärker beeinflussen als gut ausgerich tete Scans mit geringem Rauschen, die gut mit anderen Scans der Umgebung übereinstimmen. Außerdem ist die Berechnung der Informationen sehr aufwän dig, da alle Punkte in Scans innerhalb des Bereichs des aktuellen Knotens das Ergebnis beeinflussen. Dies kann insbesondere bei Lidar-Sensoren mit großer Reichweite und hoher Auflösung problematisch sein.

Vorzugsweise werden daher geometrische Methoden zum Entfernen von Knoten verwendet. Die Grundidee besteht darin, die Dichte der Knoten zu betrachten und insbesondere über die gesamte Karte hinweg unter einem bestimmten Schwellwert zu halten, d.h. es werden Knoten an Orten (in der Umgebung) ent fernt, an denen sich viele Knoten in einem kleinen Bereich ansammeln. Zu die sem Zweck wird ein neuartiges Dichtemaß vorgeschlagen, das nachfolgend als skaleninvariante Dichte bezeichnet werden soll.

Eine Dichte für einen Knoten kann als eine Anzahl an weiteren Knoten innerhalb eines bestimmten Bereichs um diesen Knoten, z.B. innerhalb eines bestimmten Radius um diesen Knoten definiert werden.

Für v _lr ...,v _n e M ² , wobei v _t v _j für i j, kann für einen Radius r > 0 eine sol che Dichte für einen Knoten v _t wie folgt definiert werden: wobei ||. || die Euklidische Norm angibt. Dies entspricht damit der Anzahl (#) an Knoten innerhalb eines Kreises mit Radius r um den Knoten v aber ohne die sen Knoten selbst.

Diese Dichte hängt allerdings stark vom gewählten Wert für den Radius ab, z.B. könnte eine hohe Anzahl an weiteren Knoten knapp außerhalb des gewählten Radius liegen. Damit würde die eigentliche Dichte für diesen Knoten stark unter bestimmt. Dies wird mittels einer skaleninvarianten Dichte adressiert. Diese gibt z.B. für ei nen Knoten ein Maß für über verschiedene Radien bestimmte einfache Dichten (wie oben) an. Dies kann z.B. durch eine Integration der oben genannten (einfa chen) Dichte über alle r erfolgen. Die skaleninvariante Dichte d(vi ) für den Kno ten v _t ergibt sich dann durch:

Diese skaleninvariante Dichte hängt nun nicht mehr von der Wahl eines be stimmten Werts für den Radius ab und vermeidet so etwaige falsche Bestimmun gen von Dichten für Knoten. Das Integral stellt gewissermaßen einen Mittelwert über eine hohe bzw. unendliche Zahl möglicher Radien dar. Es lässt sich zudem zeigen, dass (zumindest für die vorliegenden Erfordernisse) diese Darstellung äquivalent ist zu folgender Darstellung:

Damit lässt sich die skaleninvariante Dichte deutlich schneller und einfacher Be rechnen. Zudem kann diese Summendarstellung trunkiert werden auf z.B. eine bestimmte Anzahl an nächstbenachbarten weiteren Knoten zu einem bestimmten Knoten.

Vorzugsweise werden dabei so viele Knoten auf diese Weise entfernt, bis die skaleninvariante Dichte bei allen Knoten unterhalb eines bestimmten Schwell werts, einem Dichteschwellwert liegt. Alternativ oder zusätzlich ist es bevorzugt, wenn so viele Knoten entfernt werden, bis eine Anzahl an Knoten im SLAM- Graphen unterhalb eines bestimmten Schwellwerts, eines Knotenschwellwerts liegt. In diesem Fall ist es allerdings zweckmäßig, wenn dieser Knotenschwell wert in Abhängigkeit von einer geometrischen Größe einer durch den SLAM- Graphen repräsentierten Umgebung vorgegeben wird, z.B. proportional hierzu ist. So kann die gewünschte Anzahl an verbleibenden Knoten bei doppelt so gro ßer Fläche der Umgebung auch doppelt so groß sein. Die durchschnittliche Dichte an Knoten hängt dann nicht von der Größe der Umgebung ab. Denkbar ist aber auch, dass beide Varianten kombiniert werden, d.h. dass beide Schwell werte unterschritten werden müssen.

Vorteilhaft ist es zudem, wenn eine vorbestimmte Anzahl an zuletzt zum SLAM- Graphen hinzugefügten Knoten beim Entfernen von Knoten nicht berücksichtigt wird. Diese Knoten werden dann z.B. bereits beim Bestimmen des Knotens mit der höchsten skaleninvarianten Dichte nicht berücksichtigt, und dann entspre chend auch nicht entfernt. Bei der Bestimmung der skaleninvarianten Dichte für andere Knoten sollten diese zuletzt hinzugefügten Knoten allerdings berücksich tigt werden; andernfalls würde z.B. die gewünschte maximale Gesamtzahl an Knoten nicht erreicht. Auf diese Weise kann die Robustheit des Verfahrens ge steigert werden.

Das Entfernen eines Knotens führt dazu, dass diejenigen Kanten, die an dem entfernten Knoten endeten, nicht mehr definiert sind. Der Graph kodiert im Grunde eine gemeinsame Wahrscheinlichkeitsverteilung von Zufallsvariablen, die durch alle Knoten repräsentiert werden. Somit entspricht das Entfernen eines Knotens der Marginalisierung bzw. dem Entfernen einer Zufallsvariable. Vorzugs weise umfasst das Entfernen eines Knotens aus dem SLAM-Graphen daher je weils zusätzlich ein Verknüpfen derjenigen Endpunkte von Kanten, die durch den entfernten Knoten definiert waren, mit jeweils einem anderen Knoten. Mit ande ren Worten werden also die Knoten die über Kanten mit dem entfernten Knoten verbunden waren, neu verbunden.

Zum Lösen dieses Problems kann eine sog. «-Gruppen-Bedingung (auch Vary constraint") zwischen allen dem entfernten Knoten benachbarten Knoten definiert werden. Diese benachbarten Knoten könnten dann z.B. paarweise mit Kanten verbunden werden (die bisherigen Kanten würden dann entfernt), was jedoch zu einer hohen Anzahl an Kanten führt und unerwünscht ist, wenn die Datenmenge reduziert werden soll. Wie sich gezeigt hat, besteht ein Problem beim Umgang mit den Kanten des entfernten Knotens darin, dass dabei falsche Loop-Closure- Kanten entstehen können, die also nichts mit der Wirklichkeit und der tatsächli chen Bewegung des mobilen Geräts zu tun haben. Viele Algorithmen können zwar mit einer geringen Anzahl an solchen falschen Loop-Closure-Kanten umge hen, eine zu hohe Anzahl ist allerdings schwierig zu handhaben. Wie sich gezeigt hat, besteht ein Problem auch darin, dass solche falsche Loop-Closure-Kanten bei deren Bewertung zum Informationsgehalt durch einen Algorithmus keine hö here Unsicherheit aufweisen als echte Loop-Closure-Kanten.

Wenn bei obigem Beispiel mit dem paarweisen Verbinden der benachbarten Knoten z.B. zuvor eine von n Kanten des entfernten Knotens falsch war, ergeben sich durch das paarweise Verbinden n (n - l)/2 neue Kanten, wovon nA falsch sind. Das Verhältnis falscher zu echter Kanten wird damit von Mn auf 2 In erhöht. Wenn dort, wo eine neue Kante zwischen zwei benachbarten Knoten erzeugt wird, schon eine (echte) Kante vorhanden war, würde diese ersetzt oder mit einer neuen Kante fusioniert, was zu einem noch schlechteren Verhältnis führt.

Wie sich gezeigt hat, sind Kanten, die durch Bewegung des mobilen Geräts ent stehen, die erwähnten Bewegungskanten, deutlich zuverlässiger bzw. genauer als Loop-Closure-Kanten, selbst, wenn beide Kanten die gleiche Unsicherheit aufweisen. Während z.B. die Odometrie für Bewegungskanten zwar über die Zeit etwas abdriften kann, sind solche Kanten im Unterschied zu Loop-Closure-Kan- ten in der Regel nicht durch Ausreißer mit großem Fehler beeinflusst. Vor diesem Hintergrund ist es bevorzugt, beim Umgang mit den an einem entfernten Knoten endenden Kanten auf (verlässlichere) Bewegungskanten bzw. eine Bewegungs kette (also eine Kette von Bewegungskanten) abzustellen als auf Loop-Closure- Kanten bzw. Schleifenschlüsse.

Eine Möglichkeit wäre auch, einen solchen benachbarten Knoten auszuwählen und alle Kanten (bzw. Endpunkte der Kanten), die an dem entfernten Knoten en deten, mit diesem ausgewählten Knoten zu verbinden. Dabei könnte z.B. eine Summe der Länge der dadurch entstehenden bzw. veränderten Kanten minimiert werden. Hierbei würde aber die Zuverlässigkeit von Bewegungskanten bzw. Be wegungsketten nicht berücksichtigt. Demgegenüber werden, wie erwähnt, die Kanten, die an dem entfernten Knoten endeten, zwar weiterhin jeweils mit einem anderen Knoten verknüpft, sodass sie dort enden, nicht jedoch (zumindest nicht notwendigerweise) alle mit demselben Knoten.

Vielmehr wird derjenige der dem entfernten Knoten benachbarten Knoten, an dem eine Kante nun enden soll, bevorzugt dadurch ausgewählt, dass der unver bundene Endpunkt der Kante vor oder zurück entlang einer Bewegungskette be wegt wird, bis ein anderer Knoten erreicht wird. Die Bewegungskette gibt die (zeitliche) Abfolge von Knoten an, entlang derer sich das mobile Gerät bewegt hat. Für jeden Knoten gibt es damit auf der Bewegungskette einen zeitlich davor und einen zeitlich danach erzeugten Knoten. Ausgehend von dem entfernten Knoten werden also z.B. der zeitlich davor und der zeitlich danach erzeugte Kno ten gesucht und der unverbundene Endpunkt der Kante wird mit einem der bei den Knoten verknüpft. Zweckmäßigerweise wird derjenigen der beiden Knoten gewählt, bei dem die dadurch entstehende Kante am kürzesten ist, d.h. bei der die Länge am geringsten ist, d.h. geringer als bei anderen theoretisch möglichen Kanten. Auf diese Weise werden die verlässlichen Bewegungskanten bzw. Be wegungsketten berücksichtigt. Bei diesem Vorgehen gibt es auch zwei Kanten, die selbst Teil der Bewegungskette sind (es handelt sich also um Bewegungs kanten). Diese beiden Kanten werden durch eine neue Kante zwischen ihren ver bliebenen Knoten ersetzt.

Bei diesem Vorgehen, d.h. dem Verknüpfen von Endpunkten von Kanten mit neuen Knoten, handelt es sich letztlich um das Verketten von Kanten. Hierfür gibt es typischerweise drei verschiedene Möglichkeiten. Zwei Kanten können ver knüpft werden, sie können kombiniert werden, und eine Kante kann invertiert werden. Zwei Kanten (einmal von Knoten a nach Knoten b und einmal von Kno ten b nach Knoten c) werden z.B. verknüpft, indem eine neue Kante von Knoten a nach Knoten c anstelle der beiden vorigen erzeugt wird. Knoten b ist dabei der entfernte Knoten. Dies kann mit den beiden Kanten gemacht werden, die Teil der Bewegungskette sind, wie vorstehend erwähnt. Beim Kombinieren von zwei Kan ten werden z.B. deren Bedingungen ("constraints") durch Multiplizieren deren beider Gauß-Verteilungen kombiniert. Jede Kante hat eine gewisse Unsicherheit, die z.B. über eine Gauß-Verteilung modelliert werden kann bzw. modelliert ist. Die Gauß-Verteilung beschreibt dabei die Wahrscheinlichkeitsverteilung des Feh lers der Kante. Der Fehler ist dabei in der Regel der Unterschied zwischen der relativen Pose, die in der Kante gespeichert ist, und der relativen Pose der Kno ten, welche die Kante verbindet. Das Invertieren einer Kante kann z.B. über eine Lie-Algebra erfolgen.

Näheres zu diesen drei Möglichkeiten und deren Anwendung wird z.B. in "E. Eade, P. Fong, and M. E. Munich, "Monocular graph SLAM with complexity re- duction,” in Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, 2010, pp. 3017-3024." beschrieben. Bei diesem Vorgehen wird die Anzahl falscher Loop- Closure-Kanten im Wesentlichen nicht verändert, da keine Loop-Closure-Kanten neu erzeugt oder gelöscht werden; stattdessen wird nur der eine Knoten der Kante geändert. Allerdings kann es durch Kombination von Kanten passieren, dass mehrere Kanten zusammenfallen. Bei obigem Beispiel wird die Anzahl der Kanten von n auf nA reduziert, das Verhältnis falscher zu echten Kanten dann von Mn auf 1/(«-1), also nur geringfügig erhöht, nicht aber verdoppelt.

Beim Kombinieren zweier Kanten kann es Vorkommen, dass diese sich wider sprechen. Dies kann z.B. durch Betrachtung der relativen Pose für beide Kanten (eine relative Pose einer Kante entspricht einer Differenz der Posen der Knoten an den Endpunkten der Kante) oder durch eine Mahalonobis-Distanz bestimmt oder herausgefunden werden. Wenn von den beiden Kanten eine eine Loop-Clo- sure-Kante und eine eine Bewegungs-Kante ist, wird die Loop-Closure-Kante entfernt. Wenn beide Kanten Loop-Closure-Kanten sind, werden beide entfernt. Dies ist insofern von Vorteil, als das Verlieren einer echten bzw. richtigen Loop- Closure-Kante in der Regel besser ist als das Erzeugen einer falschen Loop-Clo- sure-Kante.

Wenngleich mit dem Entfernen von Knoten auch zugehörige Kanten aus dem SLAM-Graphen entfernt werden können, ist es bevorzugt, unabhängig von einem Entfernen eines Knotens, Kanten aus dem SLAM-Graphen zu entfernen. Dies ist insbesondere in Bereichen zweckmäßig, in denen die Knoten nicht besonders dicht verteilt sind. Auch werden beim Entfernen von Knoten ggf. neue Kanten er- zeugt, die auf diese Weise entfernt werden können. Grundsätzlich können Kan ten damit aber auch ohne jegliche Entfernung von Knoten entfernt werden (ent weder, weil dies gar nicht erst angewendet wird, oder weil z.B. die Dichte nir gends über dem Schwellwert liegt) wodurch ebenfalls die Größe des SLAM- Graphen bzw. dessen Datenmenge reduziert werden kann, zumal die in den Kanten enthaltenen Informationen entfernt werden.

Das Entfernen einer Kante umfasst dabei jeweils das Bestimmen desjenigen der Vielzahl an Knoten, an dem die meisten Kanten enden; damit können Kanten entfernt werden, wo deren Dichte hoch ist. Von den an diesem Knoten endenden Kanten ist dann anhand eines Kriteriums die zu entfernende Kante auszuwählen. Eine Möglichkeit ist, diejenige Kante mit dem geringsten Residuum oder dem ge ringsten Chi-Quadrat-Fehler zu entfernen. Dann würden aber Kanten mit großem Fehler behalten, welche meistens Kanten mit starkem Rauschen oder falsche Loop-Closure-Kanten sind. Ein großer Fehler kann bedeuten, dass die Kante falsch ist, er kann aber auch bedeuten, dass das derzeitige Optimum der Gra phoptimierung stark vom wahren Optimum abweicht. Wird die Kante dann ent fernt, so geht ggf. Information verloren, mit deren Hilfe das „wahre“ Optimum hätte gefunden werden können.

Zweckmäßig ist es demgegenüber, wenn aus den Kanten, die an dem bestimm ten Knoten enden, diejenige Kante bestimmt wird, die die größte Kovarianz oder die geringste Information aufweist; dann wird die auf diese Weise bestimmte Kante, also diejenige mit der geringsten Kovarianz bzw. Information, entfernt. Die Kovarianz oder Information einer Kante oder ein Maß hierfür kann z.B. anhand der Spur oder der Determinante der zugehörigen Matrix (Kovarianz-Matrix oder Informations-Matrix) der Kante bestimmt werden. Bevorzugt ist dabei die Ver wendung der Information aufgrund der etwas einfacheren Berechnung.

Zweckmäßigerweise werden (nur) so viele Kanten aus dem SLAM-Graphen, un abhängig von einem Entfernen eines Knotens, entfernt, bis eine Anzahl an Kan ten, die an demselben Knoten enden, bei allen Knoten unterhalb eines Schwell werts, eines sog. Kantenschwellwerts liegt. Auf diese Weise werden nicht zu viele Kanten entfernt und es wird eine gleichmäßige Verteilung erreicht. Das Entfernen von Kanten birgt grundsätzlich die Gefahr, dass auch für den SLAM-Graphen bzw. die Karte wichtige Kanten entfernt werden, z.B. solche, die wichtige globale Loop-Closure-Kanten sind; es könnte sogar der gesamte SLAM- Graph aufgetrennt werden. Insofern ist es zweckmäßig, wenn eine Kante nur dann entfernt wird (insbesondere beim Entfernen von Kanten unabhängig vom Entfernen von Knoten), wenn ein Faktor, der ein Verhältnis einer Länge eines kürzesten die Kante nicht enthaltenden Pfades zwischen den zwei Knoten, an denen die Kante endet, und einer Länge der Kante angibt, unterhalb eines Schwellwerts, eines sog. Faktorschwellwerts liegt. Während eine Kante die kür zeste Verbindung (einen Pfad) zwischen zwei Knoten angibt (die Länge der Kante), ergibt sich für einen Pfad zwischen diesen zwei Knoten nach Entfernen der Kante zwangsläufig ein längerer Weg, der z.B. über einen oder mehrere wei tere Knoten und entsprechenden Kanten führt. Wenn dieser neue Pfad dann sehr viel länger als die entfernte Kante ist, deutet dies darauf hin, dass die entfernte Kante eine wichtige Kante bzw. Verbindung ist. Vor diesem Hintergrund kann ein solcher Faktorschwellwert (der zwangsläufig größer als eins ist und z.B. zwi schen zwei und fünf liegen kann) eingeführt werden, der aber nicht zu groß ge wählt werden sollte.

Unabhängig davon ist es bevorzugt, wenn eine Kante nur dann entfernt wird (ins besondere beim Entfernen von Kanten unabhängig vom Entfernen von Knoten), wenn es sich um eine Loop-Closure-Kante handelt. Damit werden die Bewe gungskanten grundsätzlich nicht entfernt; wie schon erwähnt, sind diese in aller Regel sehr verlässlich. Die Bewegungskanten werden insbesondere zwar beim Bestimmen der Anzahl an Kanten pro Knoten mitgezählt, sie werden allerdings nicht entfernt.

Insgesamt kann mit dem vorgeschlagenen Vorgehen ein SLAM-Graph beson ders schnell und effizient ausgedünnt werden, sodass dessen Größe (Daten menge) nicht zu groß wird. Beispielsweise kann das Ausdünnen regelmäßig, z.B. nach jedem neuen Hinzufügen von Umgebungsinformationen an einem Ort (Kno ten) oder auch nach mehreren Malen hiervon erfolgen. Im Wesentlichen bleibt die Größe des SLAM-Graphen bzw. dessen Datenmenge damit konstant, und zwar unabhängig von derzeitdauer, über welche hinweg Daten zum SLAM- Graphen hinzugefügt werden. Dies erlaubt ein lebenslanges SLAM. Während die Geschwindigkeit, mit der ein SLAM-Algorithmus einen solchen SLAM-Graphen verarbeitet, hoch bleibt, wird die Genauigkeit des SLAM-Graphen bzw. der ent sprechenden Karte kaum reduziert.

Weiterhin betrifft die Erfindung den Betrieb eines mobilen Geräts, insbesondere eines Roboters, wobei Umgebungsinformation, die insbesondere mittels eines oder mehrerer Sensoren erfasst werden, erhalten werden, und eine aktuelle Po sition und/oder Orientierung (z.B. Pose) des mobilen Geräts basierend auf einem aktuellen SLAM-Graphen (bzw. entsprechenden Daten, die diesen SLAM- Graphen repräsentieren) bzw. einer entsprechenden Karte und den Umgebungs informationen bestimmt wird, z.B. durch Anwendung eines geeigneten SLAM- Algorithmus. Dann werden Steuerungsanweisungen zum Betreiben des mobilen Geräts basierend auf der aktuellen Position und/oder Orientierung bestimmt und durch das mobile Gerät umgesetzt.

Hierbei kann nun als der aktuelle SLAM-Graph ein früherer SLAM-Graph verwen det werden, der gemäß vorstehendem Vorgehen ausgedünnt bzw. aktualisiert worden ist, z.B. nach dem vorhergehenden Erhalt von Umgebungsinformationen. Ebenso kann der aktuelle SLAM-Graph dann auch unter Verwendung der Umge bungsinformation erweitert und dann gemäß vorstehendem Vorgehen ausge dünnt werden, und zwar zur späteren Verwendung als aktueller SLAM-Graph.

Eine erfindungsgemäße Recheneinheit, z.B. ein Steuergeräteines Roboters, ist, insbesondere programmtechnisch, dazu eingerichtet, ein erfindungsgemäßes Verfahren durchzuführen.

Die Erfindung betrifft außerdem ein mobiles Gerät mit einer solchen Rechenein heit (z.B. als Steuergerät) sowie einem oder mehreren der eingangs genannten Sensoren. Das mobile Gerät ist bevorzugt als Roboter, insbesondere als Haus haltsroboter, z.B. Saug- und/oder Wischroboter, Boden- oder Straßenreinigungs gerät oder Rasenmähroboter, als ein zumindest teilweise automatisiertes Fahr zeug, oder als eine Drohne ausgebildet. Auch die Implementierung eines erfindungsgemäßen Verfahrens in Form eines Computerprogramms oder Computerprogrammprodukts mit Programmcode zur Durchführung aller Verfahrensschritte ist vorteilhaft, da dies besonders geringe Kosten verursacht, insbesondere wenn ein ausführendes Steuergerät noch für weitere Aufgaben genutzt wird und daher ohnehin vorhanden ist. Schließlich ist ein maschinenlesbares Speichermedium vorgesehen mit einem darauf gespei cherten Computerprogramm wie oben beschrieben. Geeignete Speichermedien bzw. Datenträger zur Bereitstellung des Computerprogramms sind insbesondere magnetische, optische und elektrische Speicher, wie z.B. Festplatten, Flash- Speicher, EEPROMs, DVDs u.a.m. Auch ein Download eines Programms über Computernetze (Internet, Intranet usw.) ist möglich. Ein solcher Download kann dabei drahtgebunden bzw. kabelgebunden oder drahtlos (z.B. über ein WLAN- Netz, eine 3G-, 4G-, 5G- oder6G-Verbindung, etc.) erfolgen.

Weitere Vorteile und Ausgestaltungen der Erfindung ergeben sich aus der Be schreibung und der beiliegenden Zeichnung.

Die Erfindung ist anhand eines Ausführungsbeispiels in der Zeichnung schema tisch dargestellt und wird im Folgenden unter Bezugnahme auf die Zeichnung be schrieben.

Kurze Beschreibung der Zeichnungen

Figur 1a zeigt schematisch ein erfindungsgemäßes mobiles Gerät in einer be vorzugten Ausführungsform in einer Umgebung.

Figur 1 b zeigt schematisch einen Ablauf eines erfindungsgemäßen Verfahrens in einerweiteren bevorzugten Ausführungsform.

Figur 1c zeigt schematisch einen Ablauf eines erfindungsgemäßen Verfahrens in einerweiteren bevorzugten Ausführungsform. Figuren 2a und 2b zeigen eine Umgebung mit SLAM-Graph ohne und mit Aus dünnung gemäß einem erfindungsgemäßen Verfahren in bevorzugter Ausführungsform.

Figuren 3a bis 3c zeigen eine Umgebung mit SLAM-Graph ohne Ausdünnung, mit nicht erfindungsgemäßer Ausdünnung und mit Ausdünnung gemäß einem erfindungsgemäßen Verfahren in bevorzugter Ausführungsform.

Figuren 4a, 4b und 5a, 5b zeigen Zeitdauern von Scans und eine Anzahl an Kno ten bei verschiedenen Umgebungen bei Anwendung eines erfindungs gemäßen Verfahrens in bevorzugter Ausführungsform.

Ausführungsform(en) der Erfindung

In Figur 1a ist schematisch ein erfindungsgemäßes mobiles Gerät 100 in einer bevorzugten Ausführungsform in einer Umgebung 200, z.B. einem Raum, darge stellt. Bei dem mobilen Gerät 100 kann es sich beispielhaft um einen Staubsau gerroboter mit Rädern 120, einer als Steuergerät ausgebildeten Recheneinheit 110 sowie einem Lidar-Sensor 130 mit einem Blickfeld 132 handeln. Zur besse ren Veranschaulichung ist das Blickfeld 132 hier relativ klein gewählt; in der Pra xis kann das Blickfeld aber auch bis zu 360° betragen (z.B. aber zumindest min destens 180° oder mindestens 270° betragen); bei 360° ist das vorgeschlagene Verfahren sogar besonders effizient. Der Staubsaugerroboter 100 befindet sich auf einem Untergrund des Raums 200, der z.B. durch Wände begrenzt wird und zwei Hindernisse 202 aufweist.

Außerdem ist beispielhaft ein SLAM-Graph 210 mit einigen Knoten 220 und Kan ten 230, die jeweils zwei Knoten verbinden, gezeigt. Ein Knoten 220 repräsentiert jeweils einen Ort, an dem der Staubsaugerroboter Umgebungsinformationen er fasst, z.B. mittels des Lidar-Sensors 130, sowie die zugehörige Pose. Die Kanten 230 stellen hier Bewegungskanten dar, die sich durch Abfahren des Weges zwi schen zwei Knoten ergeben und z.B. über Odometrie erfasst werden. In Figur 1b ist schematisch ein Ablauf eines erfindungsgemäßen Verfahrens in einer weiteren bevorzugten Ausführungsform dargestellt, und zwar zum Ausdün nen eines SLAM-Graphen, der zum Betreiben des mobilen Geräts verwendet wird. Hierbei wird in einem Schritt 150 der SLAM-Graph erhalten, z.B. als Daten satz. Dieser umfasst die Knoten mit Posen und zugehörigen Umgebungsinforma tionen und die Kanten zwischen den Knoten. Die Kanten können neben Bewe gungskanten auch schon Loop-Closure-Kanten umfassen.

In einem Schritt 152 werden dann Knoten aus dem SLAM-Graphen entfernt. Da nach könnten, in einem Schritt 154, Kanten aus dem SLAM-Graphen entfernt werden, und zwar unabhängig vom Entfernen von Knoten.

Anschließend wird, in einem Schritt 156, ein aktualisierter SLAM-Graph ausgege ben, z.B. wieder als Datensatz. Gegenüber dem zuvor erhaltenen SLAM- Graphen fehlen dort dann die entfernten Knoten und die entfernten Kanten, und es sind ggf. einige andere oder neue Kanten hinzugefügt, wie es sich beim Ent fernen von Knoten ergeben kann. Der auf diese Weise erhaltene aktualisierte SLAM-Graph kann dann zum Betreiben des mobilen Geräts verwendet werden, wie später in Bezug auf Figur 1c näher erläutert werden soll. Beispielsweise kann das Ausdünnen in einer externen Recheneinheit erfolgen, sodass der SLAM- Graph dort vom mobilen Gerät erhalten und danach aktualisiert wieder dorthin übermittelt wird. Ebenso kann dies aber in einer internen Recheneinheit, z.B. ei ner Steuereinheit des mobilen Geräts erfolgen. Dann wird der Graph z.B. von ei ner internen Speichereinheit erhalten bzw. dorthin übermittelt.

Der Schritt 152, das Entfernen von Knoten, kann das Entfernen eines oder meh rere Knoten umfassen. Das Entfernen eines Knotens umfasst dabei ebenfalls wieder mehrere Schritte. In einem Schritt 160 wird zunächst aus allen Knoten derjenige bestimmt, dessen skaleninvariante Dichte an weiteren Knoten um die sen Knoten am höchsten ist. Gemäß Schritt 162 wird dieser dabei bestimmte Knoten dann aus dem SLAM-Graphen entfernt.

Nach dem Entfernen des Knotens werden, in einem Schritt 164, die nun unver bundenen Endpunkte von Loop-Closure-Kanten, die an dem entfernten Knoten endeten, mit jeweils einem anderen Knoten verknüpft. Dabei wird der neue Kno ten für jeden Endpunkt jeweils dadurch ausgewählt, dass der unverbundene End punkt vor oder zurück entlang einer Bewegungskette bewegt wird, wobei die Auswahl in Abhängigkeit von der Länge der neu entstehenden Kante erfolgt. Die zwei Bewegungskanten, die durch den entfernten Knoten definiert waren, kön nen, wie erwähnt, z.B. kombiniert werden. So wird z.B. aus zwei Bewegungskan ten von a nach b und von b nach c dann eine Kante von a nach c.

Die Schritte 160, 162 und 164 werden solange wiederholt, d.h. es werden so lange bzw. so viele Knoten aus dem SLAM-Graphen entfernt, bis die skaleninva riante Dichte bei allen Knoten unterhalb eines Dichteschwellwerts liegt. Dies kann z.B. bei Schritt 160 festgestellt werden, indem der Knoten mit der höchsten skaleninvarianten Dichte bestimmt wird. Ebenso kann dies - im Sinne eines Ab bruchkriteriums - so lange wiederholt werden, bis die (gesamte) Anzahl an Kno ten im SLAM-Graphen unterhalb eines Knotenschwellwerts liegt, wobei der Kno tenschwellwert in Abhängigkeit von einer geometrischen Größe der durch den SLAM-Graphen repräsentierten Umgebung vorgegeben wird.

Der Schritt 154, das Entfernen von Kanten aus dem SLAM-Graphen unabhängig vom Entfernen von Knoten, umfasst für das Entfernen einer Kante zunächst, in Schritt 170, das Bestimmen desjenigen der Vielzahl an Knoten, an dem die meis ten Kanten enden. In Schritt 172 wird aus diesen Kanten dann diejenige Kante bestimmt, die die größte Kovarianz aufweist oder die geringste Information zum Graphen beiträgt. Diese wird in Schritt 174 dann entfernt. Dies kann insbeson dere nur dann erfolgen, wenn es sich um eine Loop-Closure-Kante handelt.

Die Schritte 170, 172 und 174 werden solange wiederholt, d.h. es werden so lange bzw. so viele Kanten aus dem SLAM-Graphen entfernt, bis die Anzahl an Kanten, die ein Knoten begrenzt, bei allen Knoten unterhalb eines Kanten schwellwerts liegt.

In Figur 1c ist schematisch ein Ablauf eines erfindungsgemäßen Verfahrens in einer weiteren bevorzugten Ausführungsform dargestellt, und zwar das Betreiben des mobilen Geräts. Hierzu werden zunächst, in Schritt 180, Umgebungsinforma tion erhalten, die mittels eines oder mehrerer Sensoren erfasst werden, z.B. mit tels des Lidar-Sensors gemäß Figur 1a. Es handelt sich damit um Sensordaten.

In Schritt 182 werden diese Umgebungsinformationen dann einem SLAM- Algorithmus zugeführt, um, in Schritt 184, unter Berücksichtigung aktueller Odo- metrie-lnformationen eine aktuelle Position und/oder Orientierung des mobilen Geräts basierend auf einem aktuellen SLAM-Graphen bzw. entsprechenden Da ten und den Umgebungsinformationen zu bestimmen.

In Schritt 186 werden dann basierend auf der aktuellen Position und/oder Orien tierung Steuerungsanweisungen zum Betreiben des mobilen Geräts bestimmt, also z.B. ob sich der Staubsaugerroboter drehen soll, wenn ja, wie stark und wie schnell und wie weit er fahren soll. In Schritt 188 werden diese Steuerungsanwei sungen durch das mobile Gerät umgesetzt.

Wie erwähnt, werden in Schritt 182 Umgebungsinformationen einem SLAM- Algorithmus zugeführt. Dabei kann ein aktueller SLAM-Graph unter Verwendung dieser Umgebungsinformation erweitert werden, d.h. es werden z.B. ein neuer Knoten und eine neue Kante hinzugefügt. Die diesen erweiterten SLAM-Graphen repräsentierende Daten werden wie in Bezug auf Figur 1b mit dem Schritt 150 z.B. einer ausführenden Recheneinheit zugeführt und dort erhalten, und dann mit den Schritten 152, 154 inkl. der Schritte 160, 162, 164 und 170, 172, 174 ausge dünnt. Mit Schritt 156 werden die so aktualisierten Daten wieder dem SLAM- Algorithmus zur nächsten Verwendung zugeführt.

In den Figuren 2a und 2b ist jeweils eine Umgebung 200 (ähnlich wie in Figur 1a) dargestellt, jedoch jeweils mit einem deutlich detaillierten SLAM-Graphen mit Knoten 220 und Kanten 230. In Figur 2a ist ein SLAM-Graph 210 dargestellt, wie er z.B. im Rahmen des Betriebs eines mobilen Geräts ohne Ausdünnung mit der Zeit erhalten wird, d.h. wenn ständig neue Knoten und Kanten hinzukommen, ohne dass welche entfernt werden. In Figur 2b hingegen ist für dieselbe (realitätsgetreue) Umgebung ein ausge dünnter SLAM-Graph 212 gezeigt, bei dem aus dem SLAM-Graphen 210 Knoten und Kanten gemäß einem erfindungsgemäßen Verfahren in bevorzugter Ausfüh rungsform, wie z.B. vorstehend beschrieben, entfernt wurden. Dabei ist deutlich Zusehen, dass die Dichte von Knoten reduziert und die Knoten insbesondere sehr gleichmäßig verteilt sind.

In Figuren 3a bis 3c ist jeweils eine Umgebung mit SLAM-Graph ohne Ausdün nung (Figur 3a), mit nicht erfindungsgemäßer Ausdünnung (Figur 3b) und mit Ausdünnung gemäß einem erfindungsgemäßen Verfahren in bevorzugter Aus führungsform (Figur 3c) gezeigt.

Bei der Umgebung handelt es sich beispielhaft und zur einfacheren Erläuterung, siehe hierzu Figur 3a, um ein Gitter mit regelmäßig angeordneten Knoten (in Form einer Matrix), wobei die Kanten jeweils senkrecht und waagrecht zwei ne beneinanderliegende Knoten verbinden. Vorliegend verlaufen die Bewegungs kanten 234 mäanderförmig mit langen vertikalen Geraden. Die zusätzlichen hori zontalen Kanten 232 sind Loop-Closure-Kanten.

In der oberen Darstellung sind die Knoten und Kanten gezeigt, in der unteren Darstellung hingegen sind nur die Knoten mit angedeuteter Dichte zu sehen. Diese ist zunächst relativ gleichmäßig aber auch sehr hoch (außer an den Rän dern).

In Figur 3b sind nun Knoten 220 und Kanten 232, 234 zu sehen, wenn die zu ent fernenden Knoten beispielsweise basierend auf einer einfachen Dichte (mit fes tem Radius) bestimmt werden. Dabei ist zu sehen, dass die nach dem Entfernen verbleibenden Knoten relativ ungleich verteilt sind.

In Figur 3c sind nun Knoten 220 und Kanten 232, 234 zu sehen, wenn die zu ent fernenden Knoten basierend auf der im Rahmen der vorliegenden Erfindung vor geschlagenen skaleninvarianten Dichte bestimmt werden. Dabei ist zu sehen, dass die nach dem Entfernen verbleibenden Knoten deutlich gleichmäßiger ver teilt sind, als dies z.B. bei Figur 3b der Fall ist. Dies zeigt, dass die Verwendung der skaleninvarianten Dichte einen deutlich genaueren SLAM-Graphen liefert.

In den Figuren 4a und 4b sind Zeitdauern t von Scans über der Nummer s des Scans und Anzahl # an Knoten über der Nummer k eines Aufzeichnungsvor gangs eines Scans bei einer bestimmten Umgebung gezeigt. Scans werden typi scherweise mit einer bestimmten Frequenz, z.B. 10 Hz, vorgenommen. Jeder dieser Scans ist in Figur 4a enthalten. Ein Scan umfasst dabei das Erfassen von Umgebungsinformationen z.B. mittels Lidar-Sensors, die gezeigte Zeitdauer ebenfalls dessen Verarbeitung inkl. Einträgen von Knoten und Optimieren des SLAM-Graphen.

Allerdings werden in der Regel nicht alle diese Scans auch verwendet, um einen Knoten oder eine Information in den SLAM-Graphen einzutragen; dies erfolgt z.B. nur in gewissen zeitlichen oder örtlichen Abständen. Dadurch ist die Anzahl der Nummern k in Figur 4b geringer als die Anzahl der Nummern s in Figur 4a. Bei der Anzahl # an Knoten über der Nummer k eines Aufzeichnungsvorgangs ist bereits umfasst, dass auch wieder Knoten entfernt werden (dies kann z.B. zwi schen zwei Aufzeichnungsvorgängen erfolgt sein). Dies ist bei Anwendung eines erfindungsgemäßen Verfahrens in bevorzugten Ausführungsformen (V2, V3) zum Betreiben eines Geräts inkl. Ausdünnen des SLAM-Graphen im Vergleich zu ei ner Referenz (V1) gezeigt.

Die Linien V1 zeigen dabei jeweils die Referenz, bei der keine Ausdünnung vor genommen wird, die Linien V2 zeigen die Anwendung eines erfindungsgemäßen Verfahrens in bevorzugter Ausführungsform, bei der relativ wenig bzw. sparsam Knoten und Kanten entfernt werden, und die Linien V3 zeigen die Anwendung eines erfindungsgemäßen Verfahrens in bevorzugter Ausführungsform, bei der relativ viele bzw. aggressiv Knoten und Kanten entfernt werden. Dabei ist in Fig. 4a zu sehen, dass die Zeit, die für einen Scan nötig ist, bei der Referenz zunehmend ansteigt, während bei Anwendung der Erfindung der An stieg deutlich geringer ist, insbesondere bei Entfernung vieler Knoten und Kan ten.

Die Anzahl an Knoten in Fig. 4b nimmt bei der Referenz linear zu, bei Anwen dung der Erfindung hingegen deutlich weniger, insbesondere bei Entfernen vieler Knoten und Kanten, und geht insbesondere auch langsam in Sättigung. Anzumerken ist, dass die Unregelmäßigkeiten in den Linien (Nullpunkte) durch eine Relokalisierung nach einem neuen Kartendurchlauf entstanden sind und da her in der Praxis keinen Einfluss haben.

In den Figuren 5a und 5b ist der gleiche Vergleich für eine andere, und zwar grö- ßere Umgebung gezeigt; dort ist der Einfluss der Erfindung noch deutlich stärker sichtbar.