Die Joint Compatibility Branch and Bound (JCBB) ist ein Datenassoziationsalgorithmus, der in der simultanen Lokalisierung und Kartierung (SLAM) und im Bereich der Computer Vision verwendet wird, um beobachtete Merkmale mit einer bekannten Karte oder einem Modell abzugleichen. Er wurde 2001 von José Neira und Juan D. Tardós in ihrem Artikel „Data Association in Stochastic Mapping Using Joint Compatibility" eingeführt. Der Algorithmus befasst sich mit dem Problem, zu bestimmen, welche Sensormessungen zu welchen Landmarken oder Kartmerkmalen gehören, ein entscheidender Schritt für eine genaue Zustandsschätzung in der mobilen Robotik.
Im Gegensatz zu einfacheren Nearest-Neighbor-Ansätzen, die einzelne Merkmalsübereinstimmungen unabhängig bewerten, bewertet JCBB die gemeinsame Kompatibilität einer Menge von Übereinstimmungen, indem er die statistischen Korrelationen zwischen allen Merkmalen der Menge berücksichtigt. Dieser gemeinsame Test ist robuster gegen Fehlanpassungen, insbesondere in Umgebungen mit sich wiederholenden oder mehrdeutigen Merkmalen. Der Algorithmus durchsucht den Raum möglicher Übereinstimmungsmengen mithilfe einer Branch-and-Bound-Strategie, die systematisch Zweige abschneidet, die nicht zu einer besseren Lösung führen können, und so sicherstellt, dass die gefundene Menge die größte ist, die gemeinsam kompatibel ist.
Algorithmusübersicht
JCBB arbeitet mit einer Menge vorhergesagter Merkmale (aus der aktuellen Karte) und einer Menge beobachteter Merkmale (aus Sensordaten). Jede Beobachtung kann höchstens einem vorhergesagten Merkmal zugeordnet werden, und jedes vorhergesagte Merkmal kann höchstens mit einer Beobachtung übereinstimmen. Das Ziel ist es, die Menge mit der maximalen Kardinalität der Übereinstimmungen zu finden, sodass der gemeinsame Innovationsvektor (die Differenz zwischen beobachteten und vorhergesagten Messungen) innerhalb eines Chi-Quadrat-Schwellenwerts liegt, wobei die vollständige Kovarianzmatrix berücksichtigt wird.
Die Branch-and-Bound-Suche baut einen Baum auf, wobei jeder Knoten eine partielle Zuordnung von Beobachtungen zu Merkmalen darstellt. Bei jedem Schritt eröffnet der Algorithmus den Knoten, indem er die nächste unzugewiesene Beobachtung betrachtet und deren Kompatibilität mit jedem verbleibenden Merkmal testet, sowohl einzeln als auch gemeinsam mit den bereits zugeordneten Übereinstimmungen. Wenn der gemeinsame Kompatibilitätstest fehlschlägt, wird dieser Zweig abgetobt. Die Suche wird fortgerbt, bis alle Knoten untersucht sind, und die beste (größte) Menge wird zurückgegeben. Zur Effizienzsteigerung verwendet der Algorithmus eine heuristische Reihenfolge der Beobachtungen, typischerweise nach ihrer individuellen Kompatibilität, um früh gute Lösungen zu finden und aggressiver zu beschneiden.
Test der gemeinsamen Kompatibilität
Der Kern der JCBB ist der Test der gemeinsamen Kompatibilität. Gegeben einer Menge von Übereinstimmungen berechnet der Test den gemeinsamen Innovationsvektor und seine Kovarianzmatrix. Die Mahalanobis-Distanz dieses Vektors wird mit einem Chi-Quadrat-Schwellenwert verglichen, dessen Freiheitsgrade der Dimension des Innovationsvektors entsprechen. Ist die Distanz unter dem Schwellenwert, gilt die Menge als gemeinsam kompatibel. Dieser Test hat mehr Aussagekraft als die einzelnen Tests, da er die Korrelationen zwischen den Merkmalen erfasst, die aus der Positionunsicherheit des Roboters und der Kovarianz der Karte resultieren. Beispielsweise könnten zwei Merkmale, die einzeln mit verschiedenen Kartenpunkten kompatibel sind, gemeinsam inkompatibel sein, wenn die relative Geometrie zwischen ihnen nicht zur Karte passt.
Anwendungen und Erweiterungen
JCBB wird häufig in SLAM-Systemen verwendet, insbesondere in der Innen- und Außenrobotik. Er wird oft als Vordaten-Modul vor der Optimierung oder Filterung eingesetzt. Der Algorithmus wurde auch für den Einsatz im visuellen SLAM angepasst, wo Merkmale als in Kamerabildern erkannte Keypoints dienen, sowie in der Registrierung von 3D-Punktwolken (englisch: Wechsel von point-cloud-registration in point cloud registration? Nein - gemäß Anweisung Registrierung von 3D-Punktwolken; aber ich habe es als direkte Textherkunft behandelt und in Zielsprache übersetzt. Da es keinen bestehenden Artikel gibt, lasse ich es als echten Text.) Erweiterungen umfassen die Kombination von JCBB mit Random Sample Consensus (RANSAC) für die anfängliche Positionsschätzung und die Verwendung in einer hierarchischen Rahmentruktur für große Karten. In der Praxis kann JCBB für große Anzahlen von Merkmalen rechenintensiv sein, daher wurden Varianten zur Reduktion des Suchraums vorgeschlagen, wie die Verwendung eines Kompatiblitätsgraphen und Algorithmen für das maximale Cliquen-Problem, die bezüglich der Lösung äquivalent zu JCBB sind, aber schneller sein können.
Beziehung zu anderen Methoden
JCBB wird oft mit anderen Datenassoziationsmethoden verglichen, wie der Methode individual compatibility nearest neighbor (ICNN), die schnell, aber anfällig für Fehler ist, und mit mehr Fragenbasierten Methoden, die das Maximum Clique-Problem lösen. Der Branch-and-Ansatz garantiert das Finden der global optimalen Lösung unter dem Kriterium der gemeinsamen Kompatibilität, wohaltl-Wert kannne eine lokal suboptimale Mengen ergeben. Allerdings erkauft man sich diese Optik durch höhere Rechenkomplexität, was damit JCBB für Offline-Verarbeitung oder Umgebungen mit einer moderaten Anzahl von Features geeignet macht. In modernen SLAM-Systemen wird JCBB manchmal durch Methoden ersetzt, die auf Maschinelles Lernen oder Tiefes Lernen basieren, aber es bleibt ein Grundalgorithmus in diesem Bereich.
Siehe auch
- Künstliche Intelligenz
- Maschinelles Lernen
- Neuronales Netzwerk
- Residuales Netzwerk
- [[data-augmentation|Datenverbesserung]? (Hmm,
data-augmentationist – siehe Regeln; Slugs bleiben, Übersetzung folgt.)
Referenzen
- Neira, J., & Tardós, J. D. (2001). Data association in stochastic mapping using joint compatibility. IEEE Transactions on Robotics and Automation, 17(6), 890-897.