| JP2003322538 | ON-VEHICLE RADIO COMMUNICATION DEVICE |
| JP2011043449 | SATELLITE SIGNAL RECEIVER AND METHOD OF CONTROLLING THE SAME |
| JP07152997 | NAVIGATION SYSTEM |
ANGERMANN, Michael (Am Vogelherd 14, Graefelfing, 82166, DE)
KRACH, Bernhard (Rother Straße 43, Hilpoltstein, 91161, DE)
ROBERTSON, Patrick (Kloiberweg 20, Ammerland, 82541, DE)
ANGERMANN, Michael (Am Vogelherd 14, Graefelfing, 82166, DE)
KRACH, Bernhard (Rother Straße 43, Hilpoltstein, 91161, DE)
| ANP ÜCHE 1. Verfahren zur Erstellung einer Karte bezüglich ortsbezogener Angaben über die Wahrscheinlichkeit der zukünftigen Bewegung einer Person in einem räumlichen Umfeld, wie z.B. Gebäude, Wald, Tunneisystem, öffentlicher Platz wie insbesondere Einkaufszentrum, Flughafen, Bahnhof, wobei bei dem Verfahren mindestens eine Person einen oder mehrere Sensoren wie z.B. Trägheitssensoren, Drehratensensoren, optische Sensoren, für odometrische Messungen (Odometrie) mitführt, und zwar z. B. an einem Schuh, wobei die Odometrie auf Grund von inhärenten Messungenauigkeiten des/der Sensors/Sensoren, wie z.B. Winkelabweichungen, Längenabweichungen fehierbehaftet ist, sich die mindestens eine Person zu Fuß durch das räumliche Umfeld bewegt, aus den Messsignalen des/der Sensors/Sensoren Informationen über die Schrittlängen und/oder Schrittrichtung und/oder Orientierung des Sensors oder der Person ermittelt werden (Odometrie-Informationen Zu genannt) und anhand dieser Odometrie-Informationen eine Karte erstellt wird, und zwar unter Verwendung eines Bayes'schen Schätzers (z.B. Hypothesen- bzw. Particle-Filter, Rao-Blackwellisiertes Particle-Filter, Kaiman-Filter, Monte-Carlo-Hypothesen-Filter, oder Mischformen solcher Filter), dessen Zustandsvariablen-Raum (z.B. Hypothesen- Raum der Hypothesen eines Particle-Filters) sowohl den aktuellen Schritt (Schrittlänge und optional auch Bewegungsrichtungsänderung) der Person U, Odometrie-Fehler E (z. B. Driftparameter bezogen auf die ermittelte Schrittlängen und/oder Schrittrichtung und/oder Orientierung des Sensors oder der Person) als auch die ortsbezogenen Angaben über die Wahrscheinlichkeiten der zukünftigen Bewegung der Person beinhaltet. 2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Karte während der Bewegung der Person durch das Urnfeld oder nach einer Speicherung der Sensor-Messsignale bzw. der ermittelten Odometrie- Informationen zeitverzögert erstellt wird, 3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass die Berechnungen zur Erstellung der Karte entweder auf einem mitgetragenen Endgerät, wie z.B. Mobiltelephon, PDA, tragbarer Rechner oder auf einem Server durchgeführt werden. 4, Verfahren nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass die erstellte Karte entweder zur Positionierung bzw. Wegführung der Person oder zur verbesserten Positionierung bzw. Wegführung anderer Personen verwendet wird. 5, Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass zur Verbesserung der Odometrie-Informationen Messsignale/-daten weiterer Sensoren herangezogen werden, und zwar z.B. Sateliitennavi- gation, Magnetkompass, WLAN Messungen zur Positionierung, Mobilfunkpositionsmessungen, UWB Messungen zur Positionierung und/oder dass Teilbereiche eines Plans des Umfeldes verwendet werden, um den Zustandsraum des Bayes'schen Schätzers zu beschränken, 6. Verfahren nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, dass reelle oder virtuelle Referenzmarken verwendet werden, weiche durch die Person erkannt werden können und deren Vorhandensein und ggf. auch deren Position als weitere Parameter in dem Zustandsraum des Bayes'schen Schätzers aufgenommen werden, und zwar z.B. durch eine in Örtlicher Nähe der Person befindliche Mensch-Maschine-Schnittstelle, wie z.B. Knopf, Taster, Spracheingabe. 7, Verfahren nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, dass das Verfahren mit aus der Robotik bekannten optischen SLAM Verfahren kombiniert wird, indem die visuellen Merkmale, welche mit optischen Sensoren vermessen werden, in die Bestimmung des Zustandsraums des Bayes'schen Schätzers eingehen (z.B. als beitragende Faktoren in der Gewichtsberechnung und/oder "importance sampling" Schritt der Particie eingehen - z.B. als multiplikativer Term in dem Gewicht, wobei jedes Particie nun auch den Zustand jedes beobachteten visuellen Features trägt und dessen Ort und Lage im Raum sowie dessen Genauigkeit der aktuellen Beobachtung der Features und der restlichen Zustände des Particie anpasst und wobei ferner in derselben Art und Weise auch Features von Ultraschall oder Infrarot oder Mikrowellen Sensorsystemen verwendet werden können, die somit als Teil der erstellten Karte aufgefasst und verwendet werden und/oder die Erstellung der Karte auf Basis der Odometrie verbessern). 8. Verfahren nach einem der Ansprüche 1 bis 7, dadurch gekennzeichnet, dass magnetische Sensoren, wie z.B. elektronische Magnetfeldsensoren verwendet werden, indem die jeweilige Stärke und Richtung des örtlichen Magnetfeldes als Feature aufgenommen wird und entsprechend einem visuellen Merkmal in die Berechnungen eingehen. 9. Verfahren nach einem der Ansprüche 1 bis 8, dadurch gekennzeichnet, dass die Person mit mehreren Sensoren versehen ist, um Odometrie- Fehler, wie z.B. die Drift zu reduzieren, wobei sich durch Kombination der Messsignale der mehreren Sensoren, wie z.B. durch Mittelung der Odometrie-Informationen oder durch Mittelung der Rohdaten der Sensoren eine verbesserte Odometrie gewinnen lässt. 10. Verfahren nach einem der Ansprüche 1 bis 9, dadurch gekennzeichnet, dass Sensoren für die Odometrie an anderen Körperstellen angebracht werden als an den Füßen/Schuhen, und dass aus der Pedestrian Dead Reckoning bekannte Verfahren zur Berechnung bzw. Verbesserung der Odometrie angewendet werden. 11. Verfahren nach einem der Ansprüche 1 bis 10, dadurch gekennzeichnet, dass als Darstellung der Wahrscheinlichkeitsdichtefunktion des Bayes'schen Schätzers z.B.folgendes mathematisches Produkt gewählt wird : die bedingte Wahrscheinlichkeitsdichte der aktuellen Odometrie- Fehler E konditioniert auf die Odometrie-Fehler im letzten Zeitschritt, multipliziert mit der bedingten Wahrscheinlichkeitsdichte des aktuellen Schrittvektors U konditioniert auf die aktuellen Odometrie-Informationen Zu und der aktuellen Driftparameter E. 12. Verfahren nach einem der Ansprüche 1 bis 11, dadurch gekennzeichnet, dass als Karte bezüglich ortsbezogener Angaben über die Wahrscheinlichkeit der zukünftigen Bewegung einer Person in einem räumlichen Umfeld Angaben über Übergangswahrscheinlichkeiten über Kanten von räumlich angeordneten Polygonen, wie z.B. Hexagone, Rechtecke, Dreiecke, andere Polygone verwendet werden, wobei bei Umsetzung mittels eines Particle- Filters die Kantenübergänge des Particles bei jedem Polygonübergang für dieses Particle gezählt und in eine Gewichtsberechnung aufgenommen werden. 13. Verfahren nach Anspruch 12, dadurch gekennzeichnet, dass bei der Verwendung von Polygonen die Zähler nur für eine Kante zwischen zwei benachbarten Polygonen aktualisiert und gespeichert werden, und nicht für alle Kanten aller Polygone einzeln, wodurch sich der Speicherbedarf deutlich reduzieren lässt 14. Verfahren nach einem der Ansprüche 1 bis 13, dadurch gekennzeichnet, dass aus der Robotik bekannte visuelle Odometrie , wie z.B. "Lucas- Kanade" oder "Focus of Expansion" Verfahren angewendet wird, wobei mittels optischer Sensoren z.B. die Veränderung der Erscheinung der Umgebung verwendet wird, um die Ortsänderung und Lageänderung der Person zu schätzen. 15. Verfahren nach einem der Ansprüche 1 bis 14, unter Verwendung von Polygon-Repräsentationen z.B. der Karte, wobei das Poiygonraster an die Umgebung angepasst wird, um unterschiedlich dicht aufgebaut zu sein, wobei sich die Polygone überlappen können und/oder mehrere Polygonebenen hierarchisch eingesetzt werden und die Übergangszähler für jede Ebene getrennt berechnet werden und wobei in der Gewichtsberechnung der Hypothesen eines Particle-Fiiters alle Ebenen eingehen z.B, und als Karte dann z.B. sämtliche derart erstellte Ebenen ausgegeben wird. 16. Verfahren nach einem der Ansprüche 1 bis 15, dadurch gekennzeichnet, dass bei der Verwendung von Polygonen für die Karte die Polygone überlappend oder nicht-überlappend und/oder regelmäßig oder unregelmäßig sind und/oder in mehreren Ebenen aufgebaut sind. 17. Verfahren nach einem der Ansprüche 1 bis 16, dadurch gekennzeichnet, dass bei der Verwendung von Polygonen für die Karte statt eines Polygonrasters eine regelmäßige oder unregelmäßige Anordnung von Kreisen oder Ovalen oder anderer geometrischer Formen verwendet wird, wobei anstelle des Zählens eines Kantenübergangs der Winkel über den bei einem Schritt oder Teil des Schrittes die Form verlassen wird, erfasst wird und für diesen Winkel ein Winkeibereichsübergangszähler ausgewertet und aktualisiert wird, wobei bei einem überlappenden Formmuster stets diejenige Form selektiert wird, dessen Mittelpunkt am nächsten zum Particie liegt und analog zur Umsetzung mit Hexagonen die Winkelbereichsübergänge gezählt und in die Gewichtsberechnung aufgenommen werden. 18. Verfahren nach einem der Ansprüche 1 bis 17, dadurch gekennzeichnet, dass nicht nur die Zähler für Kantenübergänge bzw. Winkelbereichsübergänge pro Hexagon oder anderer Strukturen gezählt und ausgewertet werden, sondern für jede Kombination beliebig vieler vorheriger Übergänge. 19. Verfahren nach einem der Ansprüche 1 bis 18, dadurch gekennzeichnet, dass bei der Kartenerstellung bereits erstellte Karten von anderen Nutzern bzw. anderen Läufen einer Person verwendet werden, indem z.B. die "a-priori" Zähler für Kantenübergänge von Polygon Karten auf bereits gemessene Übergangszähier gesetzt werden und/oder es eine Iterative Verarbeitung erfolgt, bei der die Kartenerstellung für einen Odometrie- Datensatz immer wieder neu durchgeführt wird, und zwar unter Verwendung gegenseitig erstellter Karten. Verfahren nach einem der Ansprüche 1 bis 19, dadurch gekennzeichnet, dass die ersteilte Karte drei Raum-Dimensionen abbildet (z. B. können für eine Anwendung in drei Dimensionen säulenartige geometrische Flächen mit polygonartigen Grundrissen und einem flachen oder schrägen Boden und Dach verwendet werden, z.B. wobei analog zur zweidimensionalen Ausführung der Poiygon-Karte die Übergänge durch die dabei definierten Wände bzw. Boden- und Dach-Fläche gezählt und ausgewertet werden, z.B. indem bei zweidimensionaler Karte Übergänge über Linien und bei zweidimensionaler Karte jedoch Übergänge durch Flächen betrachtet werden. |
Die Erfindung betrifft ein Verfahren zur Erstellung einer Karte bezüglich ortsbezogener Angaben über die Wahrscheinlichkeit der zukünftigen Bewegung einer Person, So betrifft die Erfindung insbesondere ein Verfahren zur Erstellung von Wege-Karten und Raumplänen innerhalb und außerhalb von Gebäuden mittels Auswertung von Sensoren welche von Fußgängern getragen werden.
Hintergrund
Die Positionierung von Personen und Gütern wird mittlerweile häufig unter Verwendung der Satellitennavtgation durchgeführt (z.B. GPS), was außerhalb von Gebäuden mittlerweile auch für Fußgänger zu akzeptablen Genauigkeiten führen kann. Innerhalb von Gebäuden, sowie in Gebieten mit starker Abdeckung des sichtbaren Bereichs des Himmels (z.B. Straßenschluchten, Einkaufspassagen, Innenhöfen, Bahnhöfen mit Teilüberdachung) kommt es oft zu starken Störungen durch Abschattung des direkten Signalpfades vom Satelliten oder zu Mehrwegefehlern. Um hierbei Abhilfe zu schaffen, nutzt man im Prinzip zwei Möglichkeiten - die auch kombinierbar sind :
1) Die Verwendung von weiteren Funksystemen zur Positionierung, die auch in Gebäuden empfangbar sind (z.B, Wireless LAN, Mobilfunk, Ultra- Wideband - UWB),
2) Die Verwendung von Sensorik, welche Informationen über die Bewegung des Fußgängers oder eines anderen Körpers geben (z.B. Inertialsensorik, Odometrie bei Robotern, barometrische Höhenmesser, passive und aktive optische Sensoren/Systeme), Die Verbindung verschiedener Systeme, Signale und Sensoren nennt man Sensorfusion; sie ist besonders für dynamische Körper (also z.B. Fußgänger, Roboter) ein geeignetes Verfahren, um die Systeme optimal miteinander zu verbinden. Eine weitere Möglichkeit, die Genauigkeit zu verbessern, ist die Verwendung von Informationen über die Umgebung, wie z.B. Gebäudeplänen. In "Integration of Foot-Mounted Inertial Sensors into a Bayesian Location Estimation Framework", Krach, Bernhard und Robertson, Patrick (2008), in WPNC 2008, 2008-3-27, Hannover, und "Cascaded Estimation Architecture for Integration of Foot-Mounted Inertial Sensors", Krach, Bernhard und Robertson, Patrick (2008), in PLANS 2008, 2008-05-05 - 2008-05-08, Monterey, California, USA, ist gezeigt, dass das Vorwissen über die Gebäudepläne und die alleinige Verwendung einer am Schuh getragenen Inertialsensorik (Inertial Measurement Unit für alle 3 Raumachsen - IMU) zur eindeutigen Positionierung eines Fußgängers im Gebäude geeignet ist. Dieses bekannte Verfahren stellt eine wichtige Grundlage für diese Anmeldung dar und wird im Folgenden genauer erläutert:
Der Fußgänger trägt am Schuh eine IMU, dessen Beschleunigungs- und Drehraten-Signale in einem Extenden Kaiman Filter (EKF) prozessiert werden, um die Lage und Position des Schuhs - und somit der Person - zu schätzen. Um die Problematik des unbegrenzt anwachsenden Fehlers ("Drift") zu begrenzen, verwendet man sogenannte Zero Velocity Updates (ZUPTs), um in den Ruhephasen des Fußes am Boden das EKF auf null Geschwindigkeit zu setzen (sogenannte Pseudomessung). Die Ruhephase des Fußes kann man recht zuverlässig und einfach bestimmen, indem man die Beschleunigungsund Drehraten der IMU auswertet, denn bei jedem Schritt eines Menschen treten charakteristische Muster auf. Die Verwendung des EKF und der ZUPT wurde in dieser Weise von Foxfin eingeführt (stehe Pedestrian Tracking with Shoe-Mounted Inertial Sensors, Eric Foxlin, November/December 2005 Published by the IEEE Computer Society 0272-1716/05 2005 IEEE). Ein Nachteil dieses Verfahrens ist jedoch, dass die durch Drift steigenden Fehler der Orientierung um die Hochachse (engl. : "heading") mittels der ZUPT schlecht observterbar ist, und somit vor allem die Richtung der Person zunehmend ungenauer wird. Dies trifft auch - wenngleich in geringerem Maße - auf die zurückgelegte Weglänge zu. Ferner ist dieses System (alleine verwendet) grundsätzlich nur in der Lage eine relative Positionierung zu ermöglichen (also in Bezug zu einem bekannten Startpunkt). Wie eben beschrieben, konnte gemäß der Veröffentlichungen von Krach und Robertson ein zusätzliches Hypothesen-Filter ( nachfolgend auch mit Particle-Filter bezeichnet) eingesetzt werden, um zusammen mit bekannten Karten die Position im Raum zu bestimmen, indem die "Particle" (auch "Hypothesen" genannt, im Folgenden aber mit "Particle" bezeichnet) nach der gemessenen Schrittschätzung des EFK bewegt werden (was mathematisch dem Ziehen eines neuen Zustandes des Particles aus der Proposal-Funktion des Particle- Filters entspricht), jedoch mit einer jeweils anderen angenommenen Abweichung von Schrittrichtung und Schrittlänge. Die Hypothesen "ergründen" somit alle möglichen Abweichungen der EKF Schrittiängenbestimmung von der tatsächlichen Folge der Schritte der Person. Solche Hypothesen welche sich innerhalb der bekannten Wände und Hindernisse bewegen, werden entweder im "update" oder "prediction" Teil des "Particie-Filter"-(PF-)Algorithmus durch eine hohe Wahrscheinlichkeit "belohnt", und dürfen im nächsten Zeitschritt des PF-Algorithmus weitergeführt werden. Diejenigen Hypothesen, welche "Schritte durch Wände" repräsentieren, werden entweder sofort eliminiert oder mehr oder weniger stark bestraft. Nachteil dieses Verfahrens ist, dass das Wissen über die Wände (Gebäudeplan) bekannt sein muss.
(Gebäude-)Piäne bestehender Gebäude (bzw. Karten bestehender Wege) werden üblicherweise mit Mitteln aus der Vermessungstechnik erstellt, welche teuer und aufwändig sind. Oftmals sind Gebäudepläne aus einer Bau- oder Planungsphase eines Gebäudes in Papierform vorhanden; diese müssten entweder manuell eingescannt (mit anschließender Nachbereitung) oder automatisch eingescannt (digitalisiert) und verarbeitet werden, um beispielsweise Wände zu erkennen. Dieser Prozess ist teuer und fehlerträchtig. Femer erfasst er verschiedene örtliche Gegebenheiten in/an einem Gebäude nicht, welche aber bei der Positionierung nach obigen Verfahren nützlich sein können, weil sie die mögliche Bewegung der Hypothesen einschränken - z.B. Hindernisse wie größere Möbel, Ausstellungsteile, große Pflanzenanordnungen, Absperrungen, temporär oder dauerhaft aufgestellte Stände, Theken, Bestuhlungen, Trennwände etc,
Gebäudepläne und Wegenetze sind auch außerhalb der Anwendung der reinen Positionierung von Wert: In der Simulation, Anpassung und Überprüfung von Fluchtwegen, in der Optimierung und Planung von Gebäuden, Strukturen und Ressourcen (z.B. Optimierung eines Flughafens oder Krankenhauses unter Verwendung des Wissens um räumliche Bewegungen von Menschen und Gütern), bei behördlichen Eingriffen (z. B. in der Terrorbekämpfung, bei Geiselbefreiungen oder verdeckten Ermittlungen) bei Notfällen wie Großbränden, bei Großereignissen (z.B. Analyse der Ströme großer Menschenmassen), bei Wegweisungssystemen, in der Logistik (z.B. Lagerhaltung, Prozessoptimierung) sowie bei elektronischen Assistenten wie elektronischen Wegweisern oder Museumsführern. Solche Pläne sind für eine Vielzahl der aufgezählten Anwendungen besonders dann wertvoll, wenn nicht nur die Wände bekannt sind, sondern auch die tatsächlich von Menschen benutzten Wege - welche z.B. auch von Einrichtungsgegenständen und anderen Hindernissen bestimmt sein können.
Problemstellung
Es wird ein System und Verfahren benötigt, um Gebäudepiäne und/oder Wegenetze insbesondere aus Sicht von Fußgängern zu ermitteln. Eine Anwendung hiervon ist die darauf aufbauende Positionierung und Navigation von Fußgängern in Gebäuden und außerhalb. Das System und Verfahren soll nicht auf Vermessungsinstrumenten angewiesen sein und sich schnell an neue Situationen und Änderungen der Umgebung anpassen. Ferner soll das System und Verfahren in der Lage sein, insbesondere solche Umgebungscharakteristika abzubilden, welche die tatsächliche Bewegung von Fußgängern stark beeinflussen. Idee der Erfindung
Die Erfindung schlägt ein Verfahren zur Erstellung einer Karte bezüglich ortsbezogener Angaben über die Wahrscheinlichkeit der zukünftigen Bewegung einer Person vor, wobei bei dem Verfahren
mindestens eine Person mit einem oder mehreren Sensoren (z.B. Trägheitssensoren, Drehratensensoren, optische Sensoren) für odometrische Messung (Odometrie) versehen wird (z.B. an einem Schuh angebracht), wobei die Odometrie auf Grund von inhärenten Messungenauigkeiten des/der Sensors/Sensoren (z.B.
Winkelabweichungen, Längenabweichungen) fehlerbehaftet ist,
sich die mindestens eine Person zu Fuß durch das räumliche Umfeld bewegt,
- aus den Messsignalen des/der Sensors/Sensoren Informationen über die Schrittlängen und/oder Schrittrichtung und/oder Orientierung des Sensors oder der Person ermittelt werden (Odometrte-Informationen Z genannt) und
anhand dieser Odometrie-Informationen eine Karte erstellt wird, und zwar unter Verwendung eines Bayes'schen Schätzers (z.B. Particle-Filter, ao-Blackwellisiertes Particle-Filter, Kaiman-Filter, Monte-Carlo- Hypothesen-Filter, oder Mischformen solcher Filter), dessen Zustandsvariablen-Raum (z.B. Hypothesen-Raum der Particle eines Particle-Filters) sowohl den aktuellen Schritt (Schrittlänge und optional auch Bewegungsrichtungsänderung) der Person U, Odometrie-Fehler E (z. B. Driftparameter bezogen auf die ermittelte Schrittlängen und/oder Schrittrichtung und/oder Orientierung des Sensors oder der Person) und auch die ortsbezogenen Angaben über die Wahrscheinlichkeiten der zukünftigen Bewegung der Person beinhaltet.
Unter "Particle-Filter" im Sinne der Erfindung wird ein Hypothesen-Filter verstanden, bei dem es sich um ein nummerisches Verfahren handelt, mit dem eine Vielzahl von "Hypothesen" verfolgt werden, um ein dynamisches Schätzproblem näherungsweise zu lösen. Dabei stellt jede Hypothese bzw. jedes "Particle" einen Punkt im zumeist mehrdimensionalen zustandsvariablen Raum dar. Gemäß des sogenannten "Importance Sampling"-Prinzips wird dabei bei jedem Zeitschritt des nummerischen Verfahrens jeder Hypothese bzw. jedem "Particle" ein neuer Wert im zustandsvariablen Raum zugewiesen. Anschließend wird jede Hypothese (Partide) mit einem Gewichtungsfaktor gewichtet und somit bewertet.
Unter "Importance Sampling" wird im Rahmen dieser Erfindung eine nummerische Darstellung der Wahrscheinlichkeitsdichtefunktion P einer zumeist mehrdimensionalen Zustandsvariablen verstanden. Eine konkrete Realisierung dieser Zustandsvariablen entspricht einem Punkt im zustandsvariablen Raum. Beim "Importance Sampling" wird nun aus einer (auch als "Proposal Density" genannten) Wahrscheinlichkeitsdichtefunktion P eine Menge an konkreten Realisierungen einer Proposal-Zufallsvariablen gezogen. Diese "Proposal Density" sollte möglichst große Ähnlichkeiten zur gewünschten Wahrscheiniichkeitsdichtefunktion P aufweisen. Die Menge an somit "gezogenen" konkreten Realisierungen der Proposal-Zufallsvariablen stellt die Approximation zur Wahrscheinlichkeitsdichtefunktion P dar. Dabei wird jeder konkreten Realisierung der Zustandsvariablen ein Gewichtungsfaktor zugewiesen, welcher den Unterschied zwischen der "Proposal Density" und der gewünschten Wahrscheinlichkeitsdichtefunktion P berücksichtigt. Bei einer günstig ausgewählten "Proposal Density" wird es wenige konkrete Realisierungen der Proposal-Zufallsvariablen geben, welche vergleichsweise niedrige Wichtungen aufweisen und somit zwar Speicherbedarf und Rechenbedarf kosten, aber weniger zur genaueren Darstellung der WahrscheinMchkeitsdichtefunktion P beitragen.
Ferner kann vorgesehen sein, dass die Karte während der Bewegung der Person durch das Umfeld oder nach einer Speicherung der Sensor-Messsignale bzw. der ermittelten Odometrie-Informationen zeitverzögert erstellt wird.
Die Berechnungen zur Erstellung der Karte können entweder auf einem mitgetragenen Endgerät (z.B. Mobiltelephon, PDA, tragbarer Rechner) oder auf einem Server durchgeführt werden. Vorteilhafterweise wird die erstellte Karte entweder zur Positionierung bzw. Wegführung der Person oder zur verbesserten Positionierung bzw. Wegführung anderer Personen verwendet.
Zur Verbesserung der Odometrie-Informationen können Messsignale/-daten weiterer Sensoren herangezogen werden, und zwar z.B. Satellitennavigation, Magnetkompass, WLAN Messungen zur Positionierung,
Mobilfunkpositionsmessungen, UWB Messungen zur Positionierung und/oder dass Teilbereiche eines Plans des Umfeldes verwendet werden, um den Zustandsraum des erfindungsgemäß verwendeten Bayes'schen Schätzers zu beschränken.
Eine Weiterbildung des Verfahrens zeichnet sich dadurch aus, dass reelle oder virtuelle Referenzmarken verwendet werden, weiche durch die Person erkannt werden können und deren Vorhandensein und ggf. auch deren Position als weitere Parameter in dem Zustandsraum des Bayes'schen Schätzers aufgenommen werden, und zwar z.B. durch eine in örtlicher Nähe der Person befindliche Mensch-Maschine-Schnittstelle (z.B. Knopf, Taster, Spracheingabe).
Ferner kann das Verfahren mit aus der Robotik bekannten optischen SLAM Verfahren kombiniert werden, indem die visuellen Merkmale, welche mit optischen Sensoren vermessen werden, in die Bestimmung des Zustandsraums des Bayes'schen Schätzers eingehen, und zwar z.B. als beitragende Faktoren in der Gewichtsberechnung und/oder "Importance Sampling" Schritt der Partide eingehen - z.B. als muftiplikativer Term in dem Gewicht, wobei jedes Partide nun auch den Zustand jedes beobachteten visuellen Features trägt und dessen Ort und Lage im Raum sowie dessen Genauigkeit der aktuellen Beobachtung der Features und der restlichen Zustände des Particle anpasst und wobei ferner in derselben Art und Weise auch Features von Ultraschall oder Infrarot oder Mikrowellen Sensorsystemen verwendet werden können, die somit als Teil der erstellten Karte aufgefasst und verwendet werden und/oder die Erstellung der Karte auf Basis der Odometrie verbessern. Ferner können magnetische Sensoren (z.B. elektronische Magnetfeidsensoren) verwendet werden, indem die jeweilige Stärke und Richtung des örtlichen Magnetfeldes als Merkmal aufgenommen wird und entsprechend einem visuellen Merkmal in die Berechnungen eingehen.
Es kann vorgesehen werden, dass die Person mit mehreren Sensoren versehen ist, um Odometrie-Fehler (z.B. die Drift) zu reduzieren, wobei sich durch Kombination der Messsignale der mehreren Sensoren (z.B. Mittelung der Odometrie-Informationen oder Mittelung der Rohdaten der Sensoren) eine verbesserte Odometrie gewinnen Sässt.
Ferner kann vorgesehen sein, dass Sensoren für die Odometrie an anderen Körpersteilen angebracht werden als an den Füßen/Schuhen, und dass aus der Pedestrian Dead Reckoning bekannte Verfahren zur Berechnung bzw. Verbesserung der Odometrie angewendet werden.
Als Proposal Density des Bayes'schen Schätzers (z.B. Partide-Filter) kann folgendes mathematisches Produkt gewählt werden : die bedingte Wahrscheinlichkeitsdichte der aktueiien Odometrie-Fehler E konditioniert auf die Odometrie-Fehler im letzten Zeitschritt, multipliziert mit der bedingten Wahrscheinlichkeitsdichte des aktueiien Schrittvektors U konditioniert auf die aktuellen Odometrie-Informationen Z u und der aktuellen Driftparameter E.
Unter Karte im Sinne dieser Erfindung werden ortsbezogene Angaben über die Wahrscheinlichkeit der zukünftigen Bewegung einer Person in einem räumlichen Umfeld (P-Karte) verstanden. Bei der Erstellung dieser Karten können Angaben über Übergangswahrscheiniichkeiten über Kanten von räumlich angeordneten Polygonen (z.B. Hexagone, Rechtecke, Dreiecke, andere Polygone) verwendet werden, wobei bei Umsetzung mittels eines Particle Filters die Kantenübergänge des Particles bei jedem Polygonübergang für dieses Particle gezählt und in eine Gewichtsberechnung aufgenommen werden. Bei der Verwendung von Polygonen werden die Zähler zweckmäßigerweise nur für eine Kante zwischen zwei benachbarten Polygonen aktualisiert und gespeichert, und nicht für alle Kanten aller Polygone einzeln, wodurch sich der Speicherbedarf deutlich reduzieren iässt.
Vorzugsweise wird die aus der Robotik bekannte visuelle Odornetrie angewendet (z.B. "Lucas-Kanade" oder "Focus of Expansion" Verfahren), wobei mittels optischer Sensoren (z. B. Kamera) die Veränderung der Erscheinung der Umgebung verwendet wird, um die Ortsänderung und Lageänderung der Person zu schätzen.
Bei Verwendung von Polygon-Repräsentationen (z.B. Hexagon) der Karte ist es zweckmäßig, wenn das Polygonraster an die Umgebung angepasst wird, um unterschiedlich dicht aufgebaut zu sein, wobei sich die Polygone überlappen können und/oder mehrere Polygonebenen hierarchisch eingesetzt werden und die Übergangszähler für jede Ebene betrennt berechnet werden und wobei in der Gewichtsberechnung der Particle (eines Particle-Filters) alle Ebenen eingehen (z.B. multiplikativ im Gewicht) und als Karte dann z.B. sämtliche derart erstellte Ebenen ausgegeben wird.
Bei der Verwendung von Polygonen für die Karte können die Polygone überlappend oder nicht-überlappend und/oder regelmäßig oder unregelmäßig sein und/oder in mehreren Ebenen aufgebaut sein.
Bei der Verwendung von Polygonen für die Karte kann statt eines Polygonrasters eine regelmäßige oder unregelmäßige Anordnung von Kreisen oder Ovalen oder anderer geometrischer Formen verwendet werden, wobei anstelle des Zählens eines Kantenübergangs der Winkel über den bei einem Schritt oder Teil des Schrittes die Form verlassen wird, erfasst wird und für diesen Winkel (in geeigneter beliebiger Quantisierung, d.h. WertebereichsAufteilung) ein Winkelbereichsübergangszähler ausgewertet und aktualisiert (analog zu den Kantenzählern bei den Hexagonen im Ausführungsbeispiel) wird, wobei bei einem überlappenden Formmuster stets diejenige Form selektiert wird, dessen Mittelpunkt am nächsten zum Particle liegt und analog zur Umsetzung mit Hexagonen die Winkelbereichsübergänge gezählt und in die Gewichtsberechnung aufgenommen werden.
Zweckmäßigerweise werden nicht nur die Zähler für Kantenübergänge bzw. Winkelbereichsübergänge pro Hexagon oder anderer Strukturen gezählt und ausgewertet, sondern für jede Kombination beliebig vieler vorheriger Übergänge.
Zur Kartenerstellung können bereits erstellte Karten von anderen Nutzern bzw. anderen Läufen einer Person verwendet werden (z.B. können die "a~ priori" Zähler für Kantenübergänge von Polygon Karten auf bereits gemessene Übergangszähler gesetzt werden und/oder es kann eine Iterative Verarbeitung erfolgen, bei der die Kartenersteilung für einen Odometrie-Datensatz immer wieder neu durchgeführt wird, unter Verwendung gegenseitig erstellter Karten) ,
Zweckmäßigerweise bildet die erstellte Karte drei Raum-Dimensionen ab (z.B. können für eine Anwendung in drei Dimensionen säulenartige geometrische Flächen mit polygonartigen Grundrissen und einem flachen oder schrägen Boden und Dach verwendet werden (Höhe dabei z.B. zwischen 0,5 m und 5 m)), wobei analog zur zweidimensionalen Ausführung der Polygon-Karte die Übergänge durch die dabei definierten Wände bzw. Boden- und Dach-Fläche gezählt und ausgewertet werden (bei zweidimensionaler Karte werden Übergänge über Linien betrachtet, bei zweidimensionaler Karte jedoch Übergänge durch Flächen).
Die Erfindung wird nachfolgend anhand eines Ausführungsbeispiels und unter Bezugnahme auf die Zeichnung näher erläutert.
Fig. 1
Dargestellt ist schematisch das dynamische Modell für einen Bayes'schen Schätzer, wobei mit DBN ein dynamisches Bayes'sches Netzwerk, mit Z u die Schrittschätzung (Odometrie-Informatäon), mit E die Odometrie- Fehlerzustände, mit U der tatsächliche Schritt und mit P die "Pose" bezeichnet . i i _ sind und wobei für die Berechnungsdauer (Kartenbestimmungsperiode) zeitinvariant, also für alle Zeitschritte k gleich ist, bezeichnet die ortbezogenen Angaben über die Wahrscheinlichkeit der zukünftigen Bewegung einer Person in einem räumlichen Umfeld.
Fig. 2
Hier sind die Definitionen der "Pose" (Position im Raum) und des Schrittvektors für die nachfolgenden Figuren und Beispiele gezeigt. Mit P k- i ist die (alte) Position im Raum zum Zeitpunkt k-1 und mit P k ist die (neue) Position im Raum zum Zeitpunkt k bezeichnet. U k bezeichnet den Schrittvektor, d.h. die Translation der neuen Position in Bezug auf die alte Position. Der Wert k ist eine ganze Zahl. Sie wird bei jedem Takt um eins erhöht. Dies kann beispielsweise entweder zu regelmäßigen Zeitpunkten geschehen (z.B. jede Sekunde), oder wenn die Odometrie einen neuen Schritt berechnet hat, oder wenn die durch die Odometrie berechnete Schrittlänge eine Mindestiänge überschreitet (in Bezug auf k-1).
Fig. 3
Es werden zwei Beispiele für Odometrie-Berechnungen grafisch dargestellt, wobei jeweils Fußgänger etwa 10 Minuten in einer Büroumgebung liefen. Jeder Punkt stellt die geschätzte Position des Fußes dar, zum Zeitpunkt zu dem der Fuß zum Stehen kam (also ein Schritt berechnet wurde). Die Odometrte-Fehler führen zu einer Abweichung dieser Positionen von den wahren Positionen.
Fig. 4
Diese Figur zeigt schematisch eine Systemübersicht. Der Nutzer kann optional weitere Sensoren wie beispielsweise GPS- oder WLAN-Empfänger, einen elektrischen Kompass, weitere Schrittzähler, eine Kamera o.dgl. mitführen. Eine am Fuß bzw. Schuh montierte IMU kann optional vorgesehen sein, wenn die Odometrie durch andere Sensoren ermöglicht wird. Die Komponenten des Blocks 2b können beliebig im System verteilt sein, nämlich beispielsweise im Nutzergerät und/oder am Schuh und/oder als Recheneinheit im Datennetzwerk. Fig. 5
Diese Figur zeigt schematisch eine Systemübersicht. Der Nutzer kann optional weitere Sensoren wie beispielsweise GPS- oder WLAN-Empfänger, einen elektrischen Kompass, weitere Schrittzähler, eine Kamera o.dgl. mitführen. Eine am Fuß bzw, Schuh montierte IMU kann optional vorgesehen sein, wenn die Odometrie durch andere Sensoren ermöglicht wird. Die Komponenten des Blocks 2a können beliebig im System verteilt sein, nämlich beispielsweise im Nutzergerät und/oder am Schuh und/oder als Recheneinheit im Datennetzwerk.
Fig. 6
In dieser Figur ist eine schematische Darstellung des funktionalen Zusammenhangs zwischen den Blöcken 3, 4 und 14 der Fign. 4 bzw. 5 dargestellt. Die Blöcke 5, 6 und 8 speichern ihre Ergebnisse bei jedem Zeitschritt k im Speicher als Hypothesen-(Particle-)Zustand ab, Die RBPF- Steuerung erfolgt in der Reihenfolge der Blöcke 5, 6, 7, 8 und 9. Dann erfolgt die Neuberechnung des Gewichts aus den Blöcken 7 und 8 sowie gegebenenfalls ein Resampling.
Fig. 7
Diese Figur zeigt eine beispielhafte Definition der Koordinatensysteme, Winkel- und Schritt-Vektoren, wie sie in einem Ausführungsbeispiel der Erfindung verwendet werden können,
Fign. 8 und 9
Diese Figuren zeigen den gesamten Verarbeitungsprozess, und zwar ausgehend von den Rohdaten bis zur Odometrie-Informationsbestimmung und weiter bis zum Ziehen von E und Ι .
Fig. 10
Diese Figur zeigt beispielhaft zwei benachbarte Hexagone, die für die Erstellung der P-Karte verwendet werden können. Fig. 11
Diese Figur zeigt ein Beispiel für eine Hexagon-P-Karte mit Hexagon-Raster und Hexagon-Kanten, wobei hier ein Schritt zu einem der benachbarten Hexagone führt.
Fig. 12
Diese Figur zeigt ein Beispiel für eine Hexagon-P-Karte mit Hexagon-Raster und Hexagon-Kanten, wobei in diesem Beispiel ein Schritt zu einem der übernächsten Hexagone führt.
Fig. 13
Diese Figur zeigt die Darstellung einer Person (teilweise hinter dem Hexagon) in einer räumlichen Umgebung.
Fig. 14
Diese Figur zeigt zwei Beispiele für nach dem erfindungsgemäßen Verfahren erstellte Wegepläne in einem Gebäude.
Die Idee der Erfindung ist das Erlernen einer geeigneten Karte der Umgebung (also eine Art Gebäudeplan oder Wegenetz oder Mischformen), indem Daten von Inertial-Sensoren, welche von einzelnen oder mehreren Fußgängern getragen werden, ausgewertet werden. Dies geschieht erfindungsgemäß unter Verwendung eines Bayes'schen Schätzers, wie zum Beispiel eines Rao- Blackwellisierten Particie-Filters (RBPF). Solche Verfahren sind grundsätzlich aus der Robotik bekannt (siehe Literatur zu SLAM - Simultaneous Lokalization and Mapping), bisher jedoch nur unter Verwendung von Visuellen Sensoren oder Radar/Sonar/Laserranging Sensoren, welche die physikalische Umgebung abtasten oder mittels Bildverarbeitung erkennen und in einem Bayes'schen Filter (z.B. RBPF oder EKF) als Sensorsignal verarbeiten. Nach der Erfindung beruht die Kartenbildung ailetne auf der Schrittschätzung - kann aber durch weitere Sensoren und Informationen verbessert werden.
Ein Beispiel für das zugrunde liegende dynamische Modell für ein Bayes'sches Filter zeigt Fig. 1. Dargestellt ist ein Dynamisches Bayes'sches Netzwerk (DBN), welches die kausalen Zusammenhänge zwischen den beteiligten Zufallsvariablen repräsentiert. Pfeilrichtung bedeuten im bekannten Sinne der DBN als kausale Netzwerke : Wirkungsrichtung der Kausalität (Uk wirkt kausal auf Pk ein, nicht umgekehrt). Die Bedeutung der Variablen wird im nachfolgenden Text erläutert. Dieses DBN ist in dieser Anmeldung dargestellt, weil es in der Fachwelt der Bayes'schen-Schätzalgorithmen zur Verdeutlichung und zur Vermeidung von Unklarheiten üblich ist und weit verbreitet verstanden wird.
Die Schrittschätzung wird im Folgenden als Odometrie bezeichnet: Es können für die Odometrie die von Foxlin in der obigen Veröffentlichung beschriebenen Verfahren eingesetzt werden, aber auch andere, welche nicht unbedingt eine am Schuh befestigte Sensorik erfordern (z.B. Messung an anderen Körperstellen (wie Hüfte, Hosentasche) auch in Kombination mit Magnetkompass; diese werden oft als Pedestrian Dead Reckoning bezeichnet). Dabei wird davon ausgegangen, dass die Odometrie immer mehr oder weniger gute Schätzungen des Schrittvektors (diese Schrittschätzung wird als Z u bezeichnet und in dieser Anmeldung teilweise auch als Odometrie-Information bezeichnet, und ist die Schätzung des tatsächlichen Schrittvektors U) des Fußgängers ermittelt (Schrittschätzung: Raumvektor in 2D oder 3D bezogen auf den letzten Schritt oder äquivalent dazu, insgesamt bezogen auf einen anderen Zeitpunkt als den Startpunkt Siehe auch Fig. 2). Zwei Beispiele für die Verteilung der geschätzten Position gemäß Odometrie-Berechnung finden sich in Fig. 3. Anzumerken ist, dass die Definition eines Schrittes nicht nur eine Ortstranslation des Fußes oder der Person sondern auch eine Veränderung der Raumlage (Orientierung) des Fußen oder der Person umfassen kann. Wenn also ein Mensch einen Schritt tätigt, dann verändert sein Fuß bzw. der darauf befestigter Sensor sowohl seine Position im Raum als auch die Lage (Richtung); ebenso verändert dabei der Körper des Menschen seine Position (in Bezug auf eine Steile am Körper) sowie die räumliche Ausrichtung einer Körperachse (z.B. Schulteriinie oder Beckenausrichtung). Die Translation bzw. Richtungsänderung von Fuß und Person stehen aber in einem engen Verhältnis zueinander. In der zweidimensionalen Welt bestehend aus Koordinaten x und y ist die Richtung immer bezogen auf eine Richtung in der x-y Ebene. Gemäß Fign. 4 und 5 "Systemübersicht Kartenbestimmung" trägt der Nutzer eine z.B. am Fuß/Schuh montierte IMU (1) und/oder weitere Sensoren (3). Ein Posstäonsbestimmungsrechner (2a) führt die Berechnung der Position durch, wie im Folgenden beschrieben.
Gemäß der Erfindung beim beispielhaften Einsatz eines Particle-Filters werden jedem Particie des Particle-Filters (bestehend aus den Komponenten (11), ( 12) und (10)) folgende Zustandsvariablen zugeordnet:
1) Verschiedene geeignete zeitvariabie oder zeitfeste Odornetrie-Fehlerzu- stände E, um die möglichen Fehler wie feste Abweichungen und/oder Drifts der zugrundeliegenden Odometrie abzubilden (z.B. Winkelabweichung des Schrittvektors Z u pro Sekunde, Änderungsrate der Winkelabweichung, Längenabweichungsfaktor, feste Winkelabweichungen), für sowohl den aktuellen als auch den letzten Zeitschritt des Particie-Filter.
2) Ortskoordinaten und ggfs. Orientierung im Raum in einem geeigneten relativen oder absoluten Orts-Koordinatensystem (z.B. WGS-84 oder in Bezug auf eine Gebäudeecke oder relativ bezogen auf einen Startpunkt), für sowohl den aktuellen als auch den letzten Zeitschritt des Particie- Filter. Dabei ergibt sich der aktuelle Schrittvektor U als Änderung der Position und der Orientierung vom letzten zum aktuellen Zeitschritt. Diese Zustandsvariable wird als Pose P bezeichnet und ist in Fig. 2 zusammen mit dem Schrittvektor abgebildet
3) Eine geeignete Repräsentation von ortsbezogener Angaben über die Wahrscheinlichkeit der zukünftigen Bewegung einer Person in einem räumlichen Umfeld - hier als P-Karte bezeichnet. Ausführungsbeispiele werden im Folgenden aufgeführt.
Dem Particie-Filter werden bei jedem Zeitschritt die Odometrie-Informationen (also der sich aus der Einheit (dem Block) 4 der Fign. 4 und 6 Schrittvektor, ggf. mit Information über dessen Zuverlässigkeit (z.B. in Form einer Wahrscheinlichkeitsverteilung oder Varianz) zugeführt. Die Particle werden nun gemäß des bekannten Particle-Filters Algorithmus in zweierlei Weisen behandelt: a) Die Zustandsvariablen werden neu bestimmt - möglicherweise unter Zuhilfenahme eines Zufallsgenerators. Dies ist der bekannte "importance sampling" oder "Proposal Density Drawing" Schritt des Particle-Filters. Dies wird in den Komponenten (5), (6), und (8) der Fig. 6 durchgeführt. b) Jedes Particle wird neu gewichtet. Dies ist der "weight update" Schritt des Particle-Filters. Dies wird in den Komponenten (7), (11) und optional (9) der Fig. 6 durchgeführt.
Wie genau diese beiden Schritte ausgeführt werden, ist zum Teil frei auswählbar und eine Funktion der Beschaffenheit der Unsicherheit der Odometrie und der oben gemäß Ziff. 3) gewählten P-Karten-Darstellung. Hat man die Auswahl der sogenannten "Proposal-Function" getroffen, so ist die im Bayes'schen Sinne optimale "weight update" Berechnung festgelegt. Bekannte Vorgehensweisen werden in der Fachweit z.B. als "likelihood Partide-Filter" oder "transition probability proposal function" bezeichnet.
Die Wahl der P-Karte ist frei. Um nützlich zu sein, sollte sie jedoch einigen mathematischen und praktischen Kriterien standhalten, die im Folgenden aufgeführt sind. Die P-Karte wird aufgefasst als die Wahrscheinlichkeitsdichte einer geeigneten Zufallsvariablen, M, der Karte, wie weiter unten beschrieben ist. Sie sollte so gewählt sein, dass die Komponente (8) (Fign. 4 und 6) die bedingte Wahrscheinlichkeitsdichte zumindest näherungsweise p(M | P_{0: k}) bestimmen kann. Hierbei bedeutet P„{0:k} die ganze Folge der Pose vom Anfang der Messungen {Zeitschritt 0) bis zum aktuellen Zeitschritt k. Insbesondere soll M so gewählt sein, dass p(M | P_{0: k}) mit der Zeit, also mit aufsteigendem k, eine im Wesentlichen zunehmend geringere Entropie im Sinne der bekannten Shannon Entropie aufweist. Ebenso muss die bedingte Wahrscheinlichkeit p(U_k| P_{0 : k-1},M) zumindest näherungsweise bestimmbar sein (Komponente (7) in Fign. 4 und 6). Dieser Term repräsentiert den Einfluss der P-Karte M auf den nächsten Schritt zum Zeitpunkt k, gegeben bei einer bestimmten Pose-Historie bis Zeitpunkt k-1. Vorteilshafterweise kann man aber p(U_k | P_{0 : k- 1}, ) - p(U_k| P_{k-1},M) annähern, also den Einfluss älterer Poses vernachlässigen, wie dies bei den später dargestellten Hexagon P-Karten der Fall ist.
Ein Beispiel für und diese Verteilung ist aber eine Hexagon-P-Karte, M stellt Kanten-Übergangswahrscheinlichkeiten in einem Hexagon-Raster dar. Die Wahrscheinlichkeitsdichte p(M l I PO:k) für Particle i ist in mathematischer Schreibweise eine geeignete Repräsentation einer die Bewegung beeinflussenden Umgebung (P-Karte). M ist demnach eine Zufallsvariable. p(M | ...) folgt einer bekannten Beta-Verteilung. Bei der Neuberechnung von p(M | ...) wird der Übergang der Pose von Zeitpunkt k-1 auf k verwendet und die entsprechenden Zähler der Beta-Verteilung um eins erhöht (siehe auch die Fign. 10, 11 und 12). M wird so gewählt, dass pClVIPo k-i', Μ') berechnet werden kann, also der Einfluss von M auf den nächsten Schritt zum Zeitpunkt k berechnet werden kann, und zwar bei gegebener Pose- Entwicklung von 0 bis Zeitschritt k-1. Für das obige Beispiel für Hexagon-P- Karten gilt:
Ebenso muss das Integral
zumindest näherungsweise bestimmbar sein (z.B. in Komponente (7) der Fign. 4 und 6). Für Particle i zum Zeitpunkt k wird w_k neu berechnet. Die Wahrscheinlichkeitsdichte ist der Einfluss der Zufallsvariabien M auf die Bewegung (Schritt U) zum Zeitpunkt k. Der letzte Term des Integrals ist das Ergebnis von Komponente (8) aus dem letzten Zeitschritt; also die alte P- Karte. Komponente (7) berechnet oder approximiert dieses Integral entweder implizit (d.h. das Integral ist analytisch ausdrückbar) oder durch nummerische oder analytische Integration zur Laufzeit. Die Normaiisierungs-Konstante k_k wird so berechnet, dass die Summe der w„k über alle Particle zu eins summiert. Bei Hexagon-P-Karten ist p(M |„.„) vollständig durch die Kantenzähler und a-priori-Zähler spezifiziert. Das Integral ist dann generell analytisch lösbar. Das Integral muss nicht zur Laufzeit ausgewertet werden, ebenso wenig die Terme im Integral (siehe Fig. 10).
Vorteilhafterweise wählt man M und p(M | P_{0 :k}) so, dass das Integral analytisch bestimmbar ist, wie dies bei den später dargestellten Hexagon P- Karten der Fall ist.
Nach der Berechnung des Gewichts ailer Particle werden in vorteilhafter Weise die Gewichte auf Summe 1 normiert und ein optionaler (in der Fachwelt bekannter) "resampiing" Schritt durchgeführt (dies geschieht z.B. ebenfalls in Komponente ( 11) der Fign. 4 und 6).
Als Ausführungsbeispiel sei hierfür genannt, dass als "Proposal Density" für das Ziehen jedes Particles bei jedem Zeitschritt in vorteilhafter Weise folgendes mathematisches Produkt gewählt werden kann :
Die bedingte Wahrscheinlichkeitsdichte der aktuellen Odometrie-Fehler E konditioniert auf die Odometrie-Fehler im letzten Zeitschritt (z.B. in Komponente (5) der Fign. 4 und 6), multipliziert mit der bedingten Wahrscheinlichkeitsdichte des aktuellen Schrittvektors U konditioniert auf die aktuellen Odometrie-Informationen Ζ υ und der aktuellen Odometrie-Fehler E (z.B. in Komponente (6) der Fign . 4 und 6).
Dabei wird in den Komponenten (5) und (6) wie folgt verfahren : (5) : ziehe ein neues Ej^ aus der Verteilung:
Beispiel für E und diese Verteilung :
E stellt eine zeitvariante Schrittwinkelabweichung ("Bias") und eine zeitliche Änderungsrate der Schrittwinkelabweichung ("Drift") von Z u dar. Beide Zustandsgrößen sind unabhängig und folgen einem "random walk"- Zufallsprozess und stellen somit jeweils einen von zwei multipükativen Faktoren von p(E| ,.,) dar.
(6): Ziehe einen neuen Schrittvektor JJ l k aus der Verteilung:
Neuer Odometrie-Fehlerzustand
für Particle i I
tpunkt k (2D Vektor)
Praktisch bedeutet dies, dass für jedes Particle zuerst ein neuer Odometrie- Fehler-Parametersatz zufällig oder pseudozufällig gezogen wird - konditioniert auf die alten; und dann bezogen auf diesen neuen Odometrie-Fehler- Parametersatz und der aktuellen Odometrie-Informationen ein neuer Schrittvektor zufällig oder pseudozufällig gezogen wird ("Proposai Density Drawing"). Mit dem gewählten neuen Schrittvektor wird die neue Position und Orientierung berechnet und der Systemzustand des Particle wird gespeichert. In der Praxis können als Verteilung, aus der gezogen wird, die Normalverteilung genommen werden, die Varianzen ergeben sich dabei aus den tatsächlichen GüteEigenschaften der Odometrie-Sensoren und können z.B.
experimentell ermittelt werden.
Fig. 7 zeigt das beispielhaft verwendete Koordinatensystem mit Winkeln und Schrittvektoren. Für die verwendete Symbolik gilt:
Odomemtriejnformation: Z u k ={Z r k + n r k ; zr k + nv k } = {(Z a k + if k , Zv k + n ; Z? k + n } Tatsachlicher Schritt U:
Wir bestimmen aus den Rohdaten; TP = Z r k + Rauschvektor « Γ ^; und Richtungsaänd. Rauschen i k U stellt den tatsächlichen x,y-Schrittvektor ; i: dar, (rot); sowie die tatsächliche Orientierungsänd. der Person <p k e Winkelabwelchung zwischen Orientierung der Person und Sensor-Orientierung γ Odometrie Richtungsclrift γ = Ζ^^ ~
Der gesamte Verarbettungsprozess ist in den Fign. 8 und 9 gezeigt. Dabei gilt:
Rauschterme werden zufällig aus einer Mittelwertfreien Normalverteilung gezogen Bestimmung von φ folgt einem„random walk" Prozess, ggfs begrenzt Bestimmung von folgt einem .random walk" Prozess
(Anmerkung: U 1 ist im "Person zero heading" Koordinatensystem; d.h.
bezogen auf die letzte Orientierung der Person zum Zeitpunkt k)
Nun erfolgt in vorteilhafter Art und Weise gemäß der in den Fign. 10, 11 und 12 gezeigten beispielhaften Realisierung mittels Hexagon P-Karten die Berechnung des Gewichts des Particle wie folgt ("weight update", siehe Komponenten (7,9,11) der Fign. 4 und 6) : Neues Gewicht = altes Gewicht mal
Produkt__{j=0 bis Ns-1} (N(h(j), e(j))+a(h(j), e(j))) / (N(h(j)) +
3(h(j))); fails der neue Schritt das Particle aus einem Hexagon herausführt oder:
Neues Gewicht = altes Gewicht mal 0,25; falls der neue Schritt das
Particle nicht aus einem Hexagon herausführt.
Dabei gilt für Fig. 10, dass Ns = 2 ist, da vom Schritt K lediglich zwei Hexagon betroffen sind. Ferner gilt
so, dass Hj aus H h lieber U f c erreicht wird, und j Φ h
Für Ns=2 gilt ferner,
N sind Kantenzähler bzw. die Summe für alle Kanten eines Hexagons. Analog dazu sind alpha die a-prior-Zähler.
In den Fign, 11 und 12 bezeichnen die Ziffern 0, 1, 2, 3, 4, 5 die Kantennummern jeweils eines Hexagons. Gemäß Fig. 11 wird beim Übergang einer Partide-Position von P k _i nach P k der Gewichtsberechnung in Komponente (7) der Zähler der Kante 1 des Hexagons Hl hochgezählt sowie optional der Zähler der Kante 4 des Hexagons H2 hochgezählt. Bei der Gewichtsberechnung in Komponente (7) des Particle wird der Zähler der Kante 1 des Hexagons Hl (bezogen auf den Summenzähler des Hexagons H l) verwendet. Gemäß Fig. 12 wird beim Übergang einer Particle-Position von P k- i nach P k nach der Gewichtsberechnung in Komponente (7) der Zähler der Kante 1 des Hexagons Hl hochgezählt und der Zähler der Kante 2 des Hexagons H2 sowie optional der Zähler der Kante 4 des Hexagons H2 und der Zähler der Kante 5 des Hexagons H3 hochgezählt. Bei der Gewichtsberechnung des Particle wird der Zähler der Kante 1 des Hexagons Hl (bezogen auf den Summenzähler des Hexagons Hl) sowie der Zähler der Kante 2 des Hexagons H2 (bezogen auf den Summenzähler des Hexagons H2) verwendet.
Zum Verständnis sei auf Fig. 13 verwiesen, in der ein einzelnes Hexagon einer Hexagon P-Karte, welches die Wahrscheinlichkeiten der möglichen Bewegungen der Person an diesem Ort darstellt, gezeigt ist. In diesem Beispiel ist die Pfeillänge proportional zur Übergangswahrscheinlichkeit über die jeweilige Hexagon-Kante - es ist eher unwahrscheinlich, dass die Person von hinten gesehen nach links oder hinten laufen wird. Typischerweise wird der Hexagon-Radius ca. 0.25 - 1 Meter gewählt.
Die oben erwähnten Terme N(h(j), e(j)), a(h(j), e(j)), N(h(j)), a(h(j)), und Ns werden in diesem Ausführungsbeispiel - für eine Problemstellung in zwei Raumdimensionen - wie folgt bestimmt bzw. verwendet:
Der 2D Ortsbereich wird in ein regelmäßiges Hexagonraster aufgeteilt (Hexagonradius zum Beispiel 0,5 m).
Der Index h(0) bestimmt eindeutig die x- und y- Position des Mittelpunktes jenes Hexagons, welches das Particle vom letzten Schritt verlassen hat.
Der Index h(Ns) bestimmt eindeutig die x- und y- Position des Mittelpunktes jenes Hexagons, welches das Particle als Folge des letzten Schrittes erreicht hat. Alle Hexagone, welche weiterhin passiert werden (wenn überhaupt), werden in aufsteigender Reihenfolge des Verlassens mit h(j) indiziert, wobei 0<j<Ns. Zum Beispiel ist in Fig. 12 i\is=3 und in dieser Figur ist h(0) gleich Hl, h(l) ist H2 und h(2) ist H3. Für Ns=2 gilt als Beispiel Fig. 10.
In ähnlicher Weise bezeichnet 0<=e(j)<6 die Kante des Hexagons h(j) über welches es verlassen wurde.
Die Zahl N(h(j), e(j)) ist die Anzahl aller vergangenen Ereignisse (für dieses Particle) bei welchem das Hexagon mit Index h(j) über Kante e(j) verlassen wurde, also wie oft der Pfad dieses Particles die entsprechende Kante überschritten hat- Dieser Term wird als Kantenzähler bezeichnet. (h(j), e(j)) ist in diesem Falle der Hexagon P-Karten gleichzeitig die Repräsentation einer die Bewegung beeinflussenden Umgebung wie eingangs beschrieben, Sie wird wie unten erläutert zur Karte umgerechnet.
Die Zahl N(h(j)) ist der Summenzähfer des Hexagons und bezeichnet die Summe von N(h(j), e) für e=0 bis 5.
Die Zahl a(h(j), e(j)) ist eine im Prinzip beliebig wählbare positive Zahl weiche als "a-priori" Zähler interpretiert werden kann (englisch, aus der Bayes'schen Schätztheorie bekannt: "Virtual counts") und Vorwissen über die Passierbarkeit dieses Hexagons über diese Kante enthält.
So ist auch a(h( )) die Summe von a(h(j), e) für e=0 bis 5. Man kann z.B. für a(h(j), e(j)) grundsätzlich einen Wert von ca. 1 ansetzen.
Vorteilhafterweise inkrementiert man N(h(j), e(j)) für ein Particle nicht nur für das verlassene Polygon (z.B. Hexagon), sondern man tut so, als hätte man ebenfalls den Übergang in umgekehrter Reihenfolge getan und inkrementiert auch noch die entsprechende Kante des erreichten Polygons (wie in den Beispielen aus Fign. 11 und 12 gezeigt). Vorteilhafterweise korrigiert man den Bruch im Term für die Gewichtsberechnung um geometrische Ungleichheiten des Polygon-Gitters, da je nach Durchtrittsrichtung des betreffenden Particle beispielsweise durch ein Hexagongitter für eine fixe und gerade Weglänge leicht unterschiedlich viele Kanten durchschritten werden, was sonst zu einer falschen Bevorzugung mancher Richtungen und somit mancher Particle führt, da der Bruch in der Formel für die Gewichtsberechnung immer kleiner als 1 ist. Vorteiihafterweise korrigiert man den Bruch im Term für die Gewichtsberechnung um unterschiedliche Längen des aktuellen Schrittvektors eines Particle, da sonst Particle, welche aus Zufall eher kürzere Schritte repräsentieren, dadurch fälschlicherweise bevorzugt würden, da der Bruch in der Forme! für die Gewichtsberechnung immer kleiner als 1 ist. Dies kann beispielhaft dadurch geschehen, dass der Bruch potenziert um eine Zahl z genommen wird, wobei z die Längen- und/oder Richtungskorrektur umfasst (z.B. lineare Normierung auf die Anzahl der Hexagonübergänge bezogen auf einen eter Wegiänge und bezogen auf eine einheitliche Richtung im Hexagonraster).
Die Bestimmung der Karte selbst geschieht in der Komponente 13b der Fign. 4 und 6 nach Abschluss eines Laufes durch Auswertung der in der Zustandsvariablen gespeicherten ,Repräsentation einer die Bewegung beeinflussende Umgebung (P-Karte oder Karte M, im Folgenden zur Vereinfachung als Karte bezeichnet) eines jeden Particle, im obigen Beispiel z.B. die Zahl N(h, e) oder auch der Bruch (N(h, e)+a(h, e)) / (N(h) + a(h)) für alle Hexagone h und alle Kanten e. Entweder nimmt man die Karte des Particle mit dem größten Gewicht, oder die über alle Particle gewichtet gemittelte Karte oder andere Verfahren, welche in der Particle-Literatur bekannt sind. Bei der gewichteten Mittelung können zum Beispiel die Übergangszähler gewichtet gemittelt werden. Die Karte kann in einer solchen Form direkt bei der Positionierung eines Fußgängers zu einem späteren Zeitpunkt verwendet werden - sie ersetzt im obigen Beispiel dauerhaft oder als "a-priori" Zähler die entsprechenden Werte bei der später durchgeführten Positionierung mit oder ohne Neuberechnung der Karte. Die Karte kann aber auch weiterverarbeitet werden (durch Anwendung beliebiger weiterer Funktionen), z.B. durch Anwendung von Ortsbereichsfiltern oder Kantenerkennungsalgorithmen, um eine graphische Repräsentation der Karte bzw. der Umgebung zu erlangen. Im obigen Ausführungsbetspiel können die aus den Particlen berechneten (gemittelt gewichteten) Kantenübergangszähler verwendet werden, um Wände und Hindernisse zu erkennen (Kanten ohne oder mit nur sehr wenigen Übergängen). Dabei können nichtlineare Funktionen wie z.B. harte Begrenzung, Sigmoid-Funktionen oder Schweliwerte verwendet werden, um unterschiedliche Werte der Kantenübergangszähler unterschiedlich und nichtlinear in die Karte einfließen zu lassen,
Vorteile der Erfindung
Das so beschriebene Verfahren hat die Eigenschaft, dass solche Partide belohnt werden, welche gemäß ihrer Odometrie-Fehler- und Schritthypothesen öfters wieder dieselben Kantenübergänge der Hexagone aufsuchen. Dies tut auch ein Mensch, wenn er sich in einer durch Wände beschränkten Umgebung bewegt: an Türen, in Fluren, an Kreuzungen und bei ähnlichen Hindernissen bzw. Wegmöglichkeiten wählt der Fußgänger einen der physikalisch möglichen Übergänge aus - er läuft nicht durch Wände hindurch. Wenn ein Fußgänger also wiederholt dieselben Gebiete (also z.B. obige Hexagone) aufsucht, dann werden solche Particle (Hypothesen) bevorzugt, welche ebenfalls dieselben Bewegungsmuster repräsentieren. Nach einer Zeit "überleben" nur solche Particle, welche die wirkliche Bewegungshistorie des Fußgängers mehr oder weniger korrekt abbilden - und somit die Karte. Dies ermöglicht es also einer Person, zum Beispiel in ein Gebäude einzutreten - mit zuletzt bekannter Position durch Satellitennavigation (z.B. GPS) - und dann im Gebäude eine Karte aufzubauen, unter der Voraussetzung, dass hinreichend oft (in der Praxis reicht oftmals 1 weiteres Mal) eine Region erneut aufgesucht wird. Die Drift neuerer Sensoren ist derzeit so gut, dass oftmais für einige Minuten auf wenige Meter genau positioniert werden kann, ohne dass der Fußgänger erneut Gebiete betreten hat. In dieser Zeit ist es sehr wahrscheinlich, dass z.B. eine Wegstrecke in umgekehrter Richtung gegangen wurde, oder eine Flurecke mehrmals gleichartig betreten wurde.
Ferner ist das Verfahren in der Lage, nicht nur Wände zu erkennen und zu lernen, sondern auch solche Einflüsse wie Möbel, Trennwände, und andere Hindernisse. Somit ergibt sich eine engere Bindung der Bewegung des Menschen an die Umgebung, was die Positionlerungsgenauigkeit erhöht Ferner kann das Verfahren auch Änderungen der Umgebung erfassen, wie z.B. Änderungen von Innen- und Außenwänden, Umstellung größerer Möbel, neue Trennwände, usw.
In Flg. 14 sind zwei Beispiele von erzeugten Hexagon P-Karten für jeweils unabhängige Läufe eines Menschen in einem Gebäude während jeweils ca. 10 Minuten dargestellt. Während dieser Zeit hat die Person den innenliegenden, umlaufenden Fiur ein paar Mal durchlaufen sowie einige der Räume betreten. Verfahren : In diesem Beispiel war es ein Rao Blackwellisiertes Particle-Filter mit ca. 30000 Particles.
Hintergrundumriss: Tatsächlicher Flurplan - hier nur als Vergleich.
Schwarze Hexagone: Die P-Karte, welche vom Verfahren als die wahrscheinlichste errechnet wurde. Diese P-Karte ist also die P-Karte im Zustand des Particles, welches insgesamt das beste kumulative Gewicht bekommen hat.
Weniger schwarze (graue) Hexagone: Hexagone welche zu etwas weniger wahrscheinlichen, aber dennoch nicht unwahrscheinlichen P-Karten gehören.
Je größer die Löcher in den Hexagonen sind, desto häufiger wurde dieses Hexagon vom besten Particle "besucht",
Weiße Bereiche: Diese wurden durch das beste Particle nicht besucht. Erweiterungen
In der Praxis wird man dieses Verfahren auch mit Daten weiterer Sensoren verbinden, was dessen Zuverlässigkeit weiter erhöhen wird : z.B. Satellitennavigation, Magnetkompass, WLAN Messungen zur Positionierung, Mobilfunkposittonsmessungen, UWB Messungen zur Positionierung (z.B. in Komponente (3) der Fign. 4 und 6). Ebenso wird man bekannte Teilbereich des Gebäudepians verwenden, um die Particle-Bewegung zu beschränken - z.B. die Außenwände. Eine weitere Möglichkeit, dieses Verfahren zu verbessern, ist die Verwendung von ΓΘΘΙ len oder virtuellen Referenzmarken, Eine Referenzmarke ist in dem Zusammenhang dieser Erfindung ein Merkmal der Umgebung, die ein Mensch wiedererkennen kann (z.B. eine bestimmte Tür, eine Ecke eines bestimmten Raums, etc.). Bei einer virtuellen Referenzmarke muss der Ort (im Koordinatensystem des Systems) dieser Referenzmarke nicht bekannt sein.
Das System verwendet diese virtuellen Referenzmarken in folgender Weise : Wenn eine Person zum ersten Mal einer neuen geeigneten Referenzmarke begegnet, dann gibt die Person in einer geeigneten Art und Weise ein Signal an das System. Das kann zum Beispiel so geschehen, dass die Person an einem tragbaren Endgerät (z.B. Mobiltelefon) eine bestimmte Nummer eingibt oder einen bestimmten Knopf drückt. Oder aber die Person bewegt auf einer bestimmten Art und Weise den Fuß auf dem die Sensoren angebracht sind (z B. zweimal leicht gegen den Boden treten, was aus den Sensordaten vom System leicht zu erkennen ist). Die Referenzmarke kann die Person selbst wählen, bzw. sie kann sich entscheiden, an welchen Orten sie eine solche Referenzmarke setzen möchte. Oder aber eine Referenzmarke ist bereits als solche physisch markiert oder dem Fußgänger so beschrieben, dass sie erkennbar ist.
Das Particle-Filter weist nun jedem Particle für diese neue Referenzmarke eine weitere Zustandsvariable zu, bestehend aus diesen Informationen : dem aktuellen Ort des Particle (kopiert aus dessen Zustandsvariable) und dazugehörend optional eine Repräsentation der Ortsgenauigkeit (z.B. Varianzen, Wahrscheinlichkeitsdichtefunktion) sowie eine
Identifikationsnummer. Falls nur eine virtuelle Referenzmarke erlaubt ist oder wenn die explizite Identifikation der Referenzmarke beispielsweise aus der Namensgebung in einer Software-Realisierung hervorgeht, muss keine Identifikationsnummer gespeichert werden. Trifft nun der Fußgänger im weiteren Verlauf erneut auf diese virtuelle Referenzmarke, so wird er erneut dasselbe Signal geben (z. B. dasselbe Bewegungsmuster mit den Füßen oder denselben Knopf/Nummernknopf drücken). Nun werden im obigen Beispiel im "weight update" Schritt die Gewichte mit einem weiteren multiplikativen Faktor bewertet. Dieser Faktor ist eine Funktion (genannt Fl) der aktuellen Ortskoordinate des Particle und der gespeicherten Position der Referenzmarke und dessen bisher bestimmter Ortsgenauigkeit. Diese Funktion kann beliebig gewählt werden, wird aber vorteilhafter so gewählt, dass der Faktor umso größer wird, je näher die beiden Koordinaten zueinander liegen und je höher die aktuelle Ortsgenauigkeit der Referenzmarke ist. Ferner wird die für jedes Particle gespeicherte Position der Referenzmarke und dessen bisher bestimmte Ortsgenauigkeit neu berechnet, indem zum Beispiel die Position aus dem Mittelwert aller beobachteten Positionen genommen wird und die Ortsgenauigkeit die Variation der beobachteten Positionen repräsentiert (z.B. die Varianz; es kann hierzu auch ein Kaiman Filter verwendet werden).
Gibt der Fußgänger kein Signal, so werden trotzdem alle Particle mit Nlv weiteren multiplikativen Faktoren im "weight update" Schritt gewichtet. Hierbei ist Nlv die Anzahl der bisher festgelegten virtuellen Referenzmarken. Diese Faktoren berechnen sich jeweils wie folgt: sie ist ebenso eine Funktion (genannt F2) der aktuellen Ortskoordinate des Particle und der gespeicherten Position und dessen bisher bestimmter Ortsgenauigkeit. Diese Funktion F2 kann beliebig gewählt werden, wird aber vorteilhaft so gewählt, dass der Faktor umso kleiner wird, je näher die beiden Koordinaten zueinander liegen und je höher die aktuelle Ortsgenauigkeit der Referenzmarke ist. Wenn eine Referenzmarke beobachtet wird, dann besteht optional der "weight update" Schritt nicht nur aus einem multiplikativen Faktor bezogen auf diese Referenzmarke, sondern aus diesem Faktor multipliziert mit (Nlv-1) weiteren Faktoren bezogen auf alle (Nlv-1) jetzt unbeobachteten Referenzmarken, so wie beschrieben. Die Form der beiden genannten Funktionen trägt auch der Tatsache Rechnung, dass Fußgänger es insbesondere vergessen, eine Referenzmarke anzumerken, und es auch (seltener) vorkommen kann, dass ein Fußgänger eine Referenzmarke anmerkt, obwohl er nicht in dessen Nähe ist. Das Anpassen der beiden Funktionen Fl und F2 an diese Fehlerquellen geschieht in geeigneter Weise dadurch, dass deren Werte nicht zu klein werden, wenn die jeweils eingehenden Positionen weiter entfernt sind (bei der Funktion Fl) bzw. näher sind (bei F2). In ähnlicher Weise können Fl und F2 so angepasst werden, dass Referenzmarken auch in größerer Umgebung vom Fußgänger angemerkt werden, indem sie im mathematischen Sinne weniger diskriminierend ("scharf") bezüglich der Positionsunterschiede sind.
Im Gegensatz zu den ebenso beschriebenen virtuellen Referenzmarken werden reelle Referenzmarken ähnlich betrachtet und im System verarbeitet. Die Unterschiede sind die, dass die Positionen dieser echten Referenzmarken dem System bekannt sein müssen. Somit entfällt der Schritt der Neuberechnung der Position der Referenzmarke. Ferner arbeitet das System auch von Beginn an mit den Nir reeiien Referenzmarken und es muss nicht gewartet werden, bis sich diese Zahl durch Markieren der Referenzmarken erreicht wird. Natürlich können bei diesem Verfahren reelle und virtuell Referenzmarken verbunden werden: alle entsprechende Faktoren gehen im gewählten obigen Beispiel multiplikativ in die Gewichtsberechnung ein.
Das Verfahren lässt sich auch in geeigneter Art und Weise mit aus der Robotik bekannten optischen SLAM Verfahren verbinden, indem die visuellen "Features", welche mit den optischen Sensoren (siehe Komponente (3) in den Fign. 4 und 6) vermessen werden, ebenso als beitragende Faktoren in der Gewichtsberechnung und/oder "importance sampling" Schritt der Particle eingehen - z.B. als multiplikativer Term in dem Gewicht. Ebenso trägt jedes Particle nun auch den Zustand jedes beobachteten visuellen Features und passt dessen Ort und Lage im Raum sowie dessen Genauigkeit der aktuellen Beobachtung und der restlichen Zustände des Particle an. Es können auch in derselben Art und Weise Features von Ultraschall oder Infrarot oder Mikrowellen Sensorsystemen verwendet werden. Diese "Features" können somit als Teil der erstellten Karte aufgefasst und verwendet werden und/oder die hier beschrieben Erweiterung verbessert die Erstellung der Karte auf Basis der Odometrie.
Das Verfahren lässt sich auch in geeigneter Art und Weise mit magnetischen Sensoren verbinden, indem die jeweilige Stärke und Richtung des örtlichen Magnetfeldes als Feature aufgenommen wird und entsprechend den eben beschriebenen visuellen Features im System eingehen. Das Magnetfeld wird in diesem Fall mit geeigneten elektronischen Magnetfeldsensoren gemessen. Das Verfahren lässt sich auch in geeigneter Art und Weise verbessern, indem an beiden Füßen Sensoren für die Odometrie verwendet werden (also zwei Ausführungen von Komponente (1) vorhanden sind). Ebenso sind mehrere Sensoren an einem Fuß einsetzbar, um die Drift zu reduzieren. Durch geeignete Verbindung der Sensordaten (z.B. Mittelung der Odometrie- Ergebnisse oder Mittelung der Rohdaten der Sensoren) lässt sich eine verbesserte Odometne gewinnen.
Das Verfahren lässt sich auch in geeigneter Art und Weise verbessern und/oder vereinfachen, indem Sensoren für die Odometrie (Komponente (3) in den Fign. 4 und 6) an anderen Körperstellen angebracht werden und aus der Pedestrian Dead Reckoning bekannte Verfahren zur Berechnung bzw. Verbesserung der Odometrie angewendet werden (in Komponente (4) der Fign. 4 und 6). Ebenso kann das Verfahren nur mittels solcher Odometrie durch Schrittdetektion und Schritt!ängen-/Winkel-Schätzung betrieben werden - ohne am Schuh montierte Sensoren (also ist Komponente ( 1) der Fign. 4 und 6 in diesem Fal! optional).
Das Verfahren lässt sich auch in geeigneter Art und Weise vereinfachen, indem bei der Verwendung von Polygon oder Hexagon P-Karten die Zähler nur für eine Kante zwischen zwei Polygonen oder Hexagonen aktualisiert und gespeichert werden, und nicht für alle Kanten aller Hexagone einzeln. Somit lässt sich der Speicherbedarf deutlich reduzieren.
Das Verfahren lässt sich auch in geeigneter Art und Weise verbessern und/oder vereinfachen, indem die aus der Robotik bekannte visuelle Odometrie angewendet wird (z.B. "Lucas-Kanide" oder "Focus of Expansion" Verfahren). Hierbei wird mittels optischer Sensoren (z.B, Kamera (Komponente (3) in den Fign. 4 und 6) die Veränderung der Erscheinung der Umgebung verwendet um die Ortsänderung und Lageänderung der Person zu schätzen.
Das Verfahren lässt sich auch in geeigneter Art und Weise unter Verwendung der Polygon-Repräsentation (Polygon P-Karten) verbessern, indem das PoSygonraster an die Umgebung angepasst wird, um unterschiedlich dicht aufgebaut zu sein. Die Polygone können sich auch überlappen. Ebenfalls können mehrere Polygonebenen hierarchisch eingesetzt werden und die Übergangszähler für jede Ebene getrennt berechnet werden. Ebenso gehen dann in der Gewichtsberechnung der Particle alle Ebenen ein (z. B. multiplikativ im Gewicht).
Als Karte werden dann beispielsweise alle so erstellten Ebenen ausgegeben.
Das Verfahren lässt sich auch in geeigneter Art und Weise umsetzen, indem bei der Verwendung von Hexagon P-Karten statt eines Hexagon-Rasters andere Raster (z. B. Rechtecke, Dreiecke, andere Polygone) eingesetzt werden. Diese können überlappend oder nicht-überlappend und / oder regelmäßig oder unregelmäßig sein und / oder in mehreren Ebenen aufgebaut sein. Analog zum Umsetzung mit Hexagonen werden die Winkelbereichsübergänge gezählt und in die Gewichtsberechnung aufgenommen.
Das Verfahren lässt sich auch in geeigneter Art und Weise umsetzen, indem bei der Verwendung von Hexagon P-Karten statt eines Hexagon-Rasters oder eines anderen Polygonraster eine regelmäßige oder unregelmäßige Anordnung von Kreisen oder Ovalen verwendet wird, Hierbei wird kein Kantenübergang gezählt, sondern es wird der Winkel, über den bei einem Schritt oder Teil des Schrittes der Kreis verlassen wurde, erfasst. Für diesen Winkel (in geeigneter beliebiger Quantisierung, d.h. Wertebereichs-Aufteilung) wird nun der Winkelbereichsübergangszähler ausgewertet und aktualisiert (analog zu den Kantenzählern bei den Hexagonen im Ausführungsbeispiel). Bei einem überlappenden Kreismuster würde man stets den Kreis selektieren, dessen Mittelpunkt am nächsten zum Particle liegt. Analog zum Umsetzung mit Hexagonen werden die Kantenübergänge gezählt und in die Gewichtsberechnung aufgenommen.
Das Verfahren lässt sich auch In geeigneter Art und Weise verbessern, indem nicht nur die Zähler für Kantenübergänge bzw. Winkelbereichsübergänge pro Hexagon oder anderer Strukturen gezählt und ausgewertet werden, sondern für jede Kombination beliebig vieler vorheriger Übergänge. Wenn Nm solcher vorheriger Übergänge berücksichtigt werden, dann spricht man von einem arkov-Prozess Nm-ter Ordnung, und es können die in der Fachwelt bekannten Verfahren zur Berechnung des Markov-Prozesses angewendet werden, wie z.B. die Repräsentation der Markov-Kette als sog. gerichtetes Bayesian Network (welches zur Vereinfachung nur Knoten-Übergänge von jedem Zustandsknoten der Markov-Kette (also z.B. die Kantenübergänge des entsprechend zurückliegenden Hexagons bei Hexagon P-Karten) zum Knoten der Kantenübergänge des aktuellen Hexagons) aufweisen muss, und dem Erlernen dessen Wahrscheinlichkeitstabeilen gemäß dem bekannten Bayes'schem Lernen aus Daten bei bekannter Netzwerk-Struktur. Die Berechnung des Integrals aus Fig. 8 ist auch in diesem Fall vorher analytisch lösbar und entspricht der Lösung eines Bayesian Networks mit einem Zielknoten und Nm unabhängigen Elternknoten.
Das Verfahren lässt sich auch in geeigneter Art und Weise verbessern, indem bei der Kartenerstellung bereits erstellte Karten von anderen Nutzern verwendet werden. So können beispielsweise die "a-priori" Zähler auf bereits gemessene Übergangszähler gesetzt werden.
Das Verfahren lässt sich auch in geeigneter Art und Weise dadurch erweitern, dass die gemessenen Sensorwerte (inklusive der möglicherweise weiter verwendeten Daten anderer Sensoren wie Satellitennavigation, Kompass, etc.) von mehreren Läufen in derselben Umgebung oder in überlappenden Umgebungen bei der Kartenerstellung verknüpft werden. Diese Datensätze können vom selben Läufer aufgenommen werden oder von unterschiedlichen Personen, So wäre es möglich, dass kundige Personen - z.B. in einem Gebäude arbeitende Mitarbeiter eines Unternehmens - eine Zeit lang Sensordaten während ihres Alltages oder bei speziellen Messläufen aufnehmen. Diese Daten können währenddessen oder anschließend elektronisch an eine Recheneinheit (z.B. Server) übertragen werden, und diese Recheneinheit kann daraus eine Karte erstellen. Als Erweiterung hiervon können neu gewonnene Karten bzw. Messungen von bestimmten Gebieten mit bestehenden oder parallel dazu aufgenommenen Karten/Messungen (teil-) überlappender Gebiete verknüpft werden. Diese Verknüpfung lässt sich beispielhaft auf verschiedenen Wegen umsetzen :
1. Durch Verbindung der individuellen Karten, nachdem jede Karte für jeden Lauf erstellt wurde. Die Verbindung lässt sich bei überlappenden Gebieten durch Erkennen von gemeinsamen geometrischen Merkmaien in den Karten durchführen, z.B. mittels Kreuz-Korrelation der Übergangswahrscheinlichkeiten im Suchraum von verschiedenen Rotations-, Translations- und SkaÜerungstransformationen einer der Karten. Die Karten werden hierbei unter Berücksichtigung der Transformation mit der größten Korrelation kombiniert (z.B. Addition der Kantenzähler). Bei der Kombination muss berücksichtigt werden, dass bei einer Rotation die Kanten der Hexagone (oder anderer Poiygone) der Karten gegeneinander verdreht sind. Dieser Winkel muss kein Vielfaches vom Polygongrundwinkei sein (z.B. 60° beim Hexagon). In diesem Fall kann bei der Kombination zwischen den benachbarten beitragenden Kantenwerten interpoliert werden. Ähnlich kann bei einer Skalierung oder Transiation vorgegangen werden, wenn nach diesen Transformationen die Hexagon-Raster nicht übereinander passen - auch hier können die beitragenden Kanten gewichtet gemittelt zusammengeführt werden.
2. Wie eben beschrieben - aber nach einer Zusammenführung von neuen mit bestehenden Karten, wird die entstandene Karte als "a-priori" Zähler für eine erneute Durchführung des SLAM Algorithmus auf die einzelnen Datensätze verwendet. Die dabei entstehenden einzelnen Karten werden dann wieder zusammengeführt. Dieser Prozess kann iterativ für alle oder einzelne beitragende Datensätze wiederholt werden. Bei der Verwendung der "a-priori" Zähler bei der erneuten Berechnung einer Karte aus einem Datensatz X kann das Verfahren dadurch verbessert werden, dass die Zähier aus der Karte, die aus dem Datensatz X in die gemeinsame Karte geflossen waren, aus dieser Karte abgezogen werden, aber nur für die erneute Verarbeitung des Datensatzes X. Dieses zuletzt genannte Prinzip entspricht der bekannten Berücksichtigung von "extrinsischen" und "intrinsischen" Informationen bei der iterativen Dekodierung von Turbo- 3^ "
Codes, welche für die Fehlerkorrektur in der Nachrichtentechnik verwendet werden.
3. Wie eben beschrieben aber mit der Erweiterung, dass bei der Kombination der Zählerwerte keine einfache Addition der Werte aus neuer und bestehender Karte vorgenommen wird, sondern eine beliebige lineare oder nichtlineare Funktion der beitragenden Werte (z.B. gewichtete Addition, Kompression der beitragenden Werte, Kompression des Ergebnisses einer Addition, Anwendung von Schwellenwerten auf die beitragenden Werte oder auf das Ergebnis).
Wie bei der Zusammenführung von Karten beschrieben, kann die errechnete Karte einer beliebigen linearen oder nichtlinearen Funktion unterzogen werden (z.B. Kompression der Zählerwerte oder Wahrscheinlichkeiten, Anwendung von Schwellenwerten).
Eine weitere, noch detailliertere Beschreibung der Erfindung findet sich in den nachfolgend aufgelisteten Artikeln, deren Gegenstände durch Bezugnahme hiermit zum Gegenstand der vorliegenden Anmeldung gemacht werden :
Konferenz GNSS-ION: "Inertial Systems Based Joint Mapping and Positioning for Pedestrian Navigation", Patrick Robertson, Michael Angermann, Bernhard Krach, Mohammed Khider; Sept. 22-25 2009, Savannah, Georgia, USA.
Konferenz UbiComp 2009 : "Simultaneous LocaSization and Mapping for Pedestrians using only Foot-Mounted Inertial Sensors", Patrick Robertson, Michael Angermann, Bernhard Krach, September 30 - October 3, 2009, Orlando, Florida, USA.
Robertson, Patrick; Angermann, Michael; Krach, Bernhard and Khider, Mohammed : SLAM Dance: Inertial-Based Joint Mapping and Positioning for Pedestrian Navigation, InsideGNSS, May 201 (www.tnsidegnss.com).