Gegeben sind die Winkel zwischen den Katzenaugen. Die Reihenfolge ist richtig, denn der Laserstrahl rotiert eine einzige volle Umdrehung gegen den Uhrzeigersinn. Es koennen jedoch Katzenaugen uebersehen worden sein. Eventuell ist eine Vermutung ueber die Fahrzeugposition und Richtung gegeben, doch dazu an passender Stelle spaeter mehr. Zunaechst gehe ich davon aus, dass keine Vermutung gegeben ist. Weiterhin sind die Positionen der Katzenaugen gegeben (in der selben Reihenfolge, wie sie auch vom Laserstrahl ueberstrichen werden)
Gesucht sind die Position des EYCar und seine Richtung.
Zunaechst stellt der Algorithmus fest, dass er beispielsweise 6 Winkel gemessen hat, jedoch 8 Katzenaugen im Raum sind. 2 Winkel fehlen also. (fehlt ein Auge werden die beiden anliegenden Winkel summiert und der EYCar misst nur die Summe der beiden. Es gilt, dies zu erkennen.)
Im Moment hat der Algorithmus also 6 Winkel, und 8 Katzenaugen. Er weiss nicht welcher Winkel wo anliegt, und er weiss auch nicht, welche Katzenaugen er uebersehen hat. Einzig die Reihenfolge Winkel zu Auge ist korrekt. Nun wird jedes Katzenauge testweise einmal geloescht und der Algorithmus ruft sich selbst rekursiv auf.
insgesamt 8 mal testet also der Algorithmus folgende Situation: Ich habe 6 Winkel und 7 Katzenaugen. Nach wie vor sieht der Algorithmus, dass er ein Katzenauge zu viel hat, und loescht wiederum jedes einmal und ruft sich jeweils selbst rekursiv auf (Es wird kompliziert ;)
insgesamt 7 mal testet also der Algorithmus folgende Situation: Ich habe 6 Winkel und 6 Katzenaugen. Dies sieht doch nun schon ganz ordentlich aus. Ja genau, die jetzige Ueberlegung macht der Algorithmus 8*7=42 mal. Jedesmal mit 2 anderen ausgelassenen Augen. Es gilt jetzt zu testen, ob die ausgelassenen Augen die richtigen sind. Aber halt! Noch ein weiteres Problem tut sich jetzt auf. Welcher der 6 Winkel gehoert zu dem ersten Katzenauge ??? (nur die Reihenfolge ist bekannt! aber wir wissen nicht, welcher der 6 Winkel zum ersten Auge gehoert !)
Auch fuer diesen Fall habe ich mich entschlossen die Brute Force (brutale Gewalt) Methode anzuwenden und einfach alle 6 Moeglichkeiten durchzutesten und damit jeweils den Kern des Algorithmus zu fuettern.
Der Kern des Algorithmus. Er wird nun in unserer Beispielsituation 8*7*6=336 mal aufgerufen und hat nun die Aufgabe von den 336 moeglichen eindeutigen Zuordnungen von Winkel zu Auge, die richtige herauszusuchen. Die Vorstellungskraft wird nun etwas gefoerdert. Male einen Raum von oben auf ein Papier. Zeichne 6 Katzenaugen ein (die 2 anderen haben wir ja eleminiert). Zeichne den EYCar irgendwo in die Mitte des Papiers. Zeichne nun die Winkel zwischen den Augen ein. Wir glauben im Moment zu wissen, welcher Winkel zu welchen 2 Augen gehoert. Mit nur 2 Augen und dem Winkel laesst sich nun ein Kreis (Fasskreis) einzeichnen, auf dem sich der EYCar theoretisch ueberall befinden koennte. Dies macht nun der Algorithmus mit allen Winkeln und allen Katzenaugen. THEORETISCH, wenn wir die richtigen Katzenaugen ausgelassen haben, schneiden sich alle Kreise in EINEM Punkt, der Position des EYCar. Dummerweise ist dies Aufgrund von Messungenauigkeiten NIEMALS der Fall! Der Algorithmus berechnet nun fuer alle Kreise einen Naeherungsweisen Schnittpunkt und versieht diesen mit einer Qualitaet. (Diesen Unteralgorithmus moechte ich hier nicht erklaeren). Das Ergebnis ist zum Beispiel: EYCar befindet sich an der Position (10.092|40.2345) und diese Position hat eine Qualitaet von 200. Je groesser die Qualitaet, desto unschaerfer ist der Schnittpunkt. Also auch wenn sich die Kreise aeusserst schlecht schneiden, oder gar mehrere unterschiedliche Schnittpunktmaxima (bei speziellen unguenstigen geometrischen Konstellationen) vorhanden sind, berechnet der Unteralgorithmuss trotzdem einen Schnittpunkt, nur hat der eine schlechte Qualitaet, zum Beispiel 20000. Theoretisch muesste der richtige Punkt eine Qualitaet von 0 haben, aber die Messfehler lassen dies NIEMALS zu. OK, zusammengefasst errechnet der "Kern des Algorithmus" also aus einer fiktiven Zuweisung von Winkeln zu Augen eine Position und eine Qualitaet derselben. All die falschen der 336 fiktiven Zuweisungen erhalten auf diese Weise eine schlechtere Qualitaet als die richtige Zuweisung.
Sind alle 336 Moeglichkeiten durchgerechnet, wird diejenige Position mit der kleinsten (also besten) Qualitaet als die richtige angesehen. Wir wissen nun also definitiv, WO der EYCar steht, auch wissen wir, welcher Winkel zu welchem Katzenauge gehoert, und da wir nun wissen, welcher Winkel zu welchem Auge gehoert, und auch die Koordinaten der Augen kennen, und auch wissen, welchen Winkel der Laserstrahl im Zeitpunkt der Beleuchtung jedes Auges RELATIV ZUM FAHRZEUG hatte, koennen wir daraus den absoluten Winkel des EYCar berechnen, ich moechte auch hierauf nicht naeher eingehen.
nun kommt aber noch die Anfangs erwaehnte Vermutungsposition ins Spiel. Wenn der EYCar eine neue Position anfaehrt, dann glaubt er ja am Ende exact da zu sein, wo er sein will. Lediglich der Schlupf an den Raedern und aehnliche Ungenauigkeiten halten ihn von seinem Ziel etwas fern. Die vermutete Position ist also diejenige Position, die der EYCar angefahren hat und demzufolge glaubt dort zu sein.
Unter mannigfaltigen nicht begreifbaren geometrisch aeusserst unguenstigen Konstellationen, in denen auch noch die falschen Katzenaugen abgedeckt wurden kommt der Algorithmus zu falschen Loesungen, die aber ansich richtiger sind, als die richtigen Loesungen (Dies ist leider derart komplex dass ich es nicht vernuenftig hier niederschreiben kann). Hier kommt nun die vermutete Position ins Spiel. Ist die Abweichung der errechneten Position zur vermuteten Position zu gross, wird die errechnete Position unter den Tisch gekehrt, OBWOHL sie per Rechnung richtiger als die eigentlich richtige Position ist. die vermutete Position hilft also mit, die Richtige der 336 Loesungen zu finden.
Unter ganz extrem extrem unguenstigen Konstellationen kann der Algorithmus nur derart schlechte Ergebnisse errechnen, dass er sich geschlagen gibt. In diesen seltenen Faellen hilft nur noch der manuelle Eingriff. Ein Beispiel:
Wir haben 8 Katzenaugen, aber nur 2 Winkel, also 6 verdeckte Augen. Daraus ergeben sich 8*7*6*5*4*3*2*2=80640 moegliche Zuweisungen von Winkel zu Auge. Erstens rechnet der Algorithmus wirklich lange an der Loesung herum, man muss mehrere Sekunden warten, und zweitens gibt es hier derart viele wirklich gute aber falsche Loesungen, dass auch die vermutete Position nicht mehr weiterhilft, der Algorithmus gibt sich geschlagen.
Das perverse an dem Verfahren ist, dass man es immer nur teilweise begreifen kann. Von Nachrechnen kann sowieso keine Rede sein, denn wenn ein Computer mehrere Sekunden rechnet, so kann man als Mensch lieber gleich in Pension gehen. Sonderfaelle zu behandeln ist auch eigentlich nicht moeglich. Aber ein boeses Problem moechte ich noch erwaehnen. Daraus leiten sich auch verschiedene Strategien fuer die guenstige Anordnung der Augen im Raum ab, jedoch sei gesagt, dass von Beweisen hier keine Rede sein kann. Man kann immer nur Vermuten.
Angenommen du ordnest 5 Katzenaugen exakt auf einem Kreis an. Der EYCar steht irgendwo in der Mitte. Woher soll er nun wissen, welcher Winkel zu welchem Auge gehoert ? Alle 5 Moeglichkeiten liefern EXAKT ein Ergebnis mit gleicher Qualitaet aber unterschiedlicher Koordinate. Der Algorithmus wird einfach die erste Loesung verwenden (da alle gleichgut sind), aber die Wahrscheinlichkeit, dass diese falsch ist ist fuenf zu eins.
Zusammengefasst muss ich sagen, dass ich selber erstaunt bin, dass mein Algorithmus tatsaechlich die Position mit erstaunlicher Genauigkeit messen kann (manchmal wenige Millimeter). Dies jedoch nur, wenn keine Augen verdeckt sind. Ist jedoch dieser unguenstige Fall eingetreten werden die Ergebnisse schlechter. Noch erstaunlicher war es fuer mich, dass er tatsaechlich auf dem Bildschirm die uebersehenen Katzenaugen zeigte, und dies auch noch richtig war.
Ich bin eigentlich von diesem Verfahren der Vermessung des Raumes nicht sehr ueberzeugt. Es haette nur einen Sinn, wenn der Laser einige hundert Umdrehungen pro Sekunde machen wuerde und staendig den Raum vermessen wuerde. Dann naemlich waehren die Aenderungen von Messung zu Messung so gering, dass man sofort erkennt, wenn jemand ein Auge zudeckt. Ausserdem ist die Positionsaenderung von Messung zu Messung derart gering, dass man sehr viele falsche Loesungen von vornerein ausschliessen kann
Ich wuerde das System gerne dahingehend abwandeln, dass der Laserstrahl andauern den Raum vermisst. Dann jedoch wird das Problem voll in den EYCar integriert, die Zeiten zur Funkuebertragung kann ich dann nicht mehr tolerieren, der EYCar muss selber rechnen (Seither rechnet der stationaere Rechner). Ausserdem wird die Sache dann ploetzlich derart komplex dass ich es unter umstaenden nicht mehr packe. Das Risiko und der Aufwand sind mir zu gross. Daher wird nur im Stillstand vermessen, mit allen Unannehmlichkeiten, die mir dadurch geboten werden, aber eine Herausforderung waere es allemal, die Hardware dafuer ist bereits vorhanden...