Künstliche Intelligenz für den längsten Trail durch den Churer Fürstenwald
Einleitung: Wie kann die Suche nach dem längsten Pfad im Fürstenwald als Optimierungsproblem gelöst werden? Um die Güte der Lösung und die Performance Unterschiede zu messen wurden verschiedene Experimente (Konstruktionsheuristiken, Metaheuristiken, Regeln, Parameter) durchgeführt. Dazu kam OptaPlanner als Optimierungsengine zum Einsatz. Die Open Source Routing Machine (ORSM) wurde verwendet um die Wegdistanzen zu berechnen. Anschliessend wurde eine Webseite mit React und Redux entwickelt um die Ergebnisse darzustellen.
Vorgehen: Das untersuchte Gebiet ist ein Teil des Fürstenwaldes bei Chur. Dieses wurde in drei Teilgebiete unterteilt. Das kleinste diente einem Proof-of-Work, das Mittlere diente der Optimierung der Parameter und Heuristiken. Im grössten Gebiet sollte der längste Pfad gefunden werden. Ergänzend zum bestehenden Kartenmaterial in OSRM wurden neue Wege kartografiert.
Fazit: Unsere Experimente haben ergeben, dass es abhängig von den Wegen schwer oder unmöglich ist eine Lösung zu finden. Begründet wird dies durch die von uns definierte Regel, dass jede einzelne Weggabelung besucht werden muss. Hierbei liegt die Schwierigkeit, dass es für eine solche Suche mindestens einen Hamiltonkreis gibt. Trotzdem wurden für das kleinste und mittlere Teilgebiet der (wahrscheinlich) längste Trail gefunden. Im dritten Teilgebiet konnten wir auch nach mehreren Experimenten mit verschiedenen Parametern und Heuristiken kein Resultat finden. Ein Longest Path Problem lässt sich unter bestimmten Voraussetzungen als Optimierungsproblem lösen.
Rico Good
