Dem Algorithmus fehlt ein Preprocessing der Umgebung und der Bewegungen der Hindernisse. Die Bewegungen der Hindernisse sind bekannt, aber dies nutzt der Algorithmus nicht aus. Die RAMP-Heuristik in ihrer jetzigen Form wäre ebenso anwendbar auf Hindernisse, die sich abhängig vom Agenten bewegen und diesen evtl. sogar verfolgen würden. In einem Preprocessing könnten die Laufbahnen der Hindernisse analysiert werden und die aggregierten Daten in den Datenfeldern mit einfließen.

Bei der Prioritätsvergabe in der Funktion eval können die Hindernisse dann mit berücksichtigt werden. Ein Beispiel wäre, die Priorität zu verbessern, wenn ein erreichtes Datenfeld häufig von Hindernissen blockiert ist. Damit würden Wege favorisiert werden, die für den Agenten schwer zu finden sind. Weiterhin könnte man die Hindernisse auf Regelmäßigkeiten (Perioden) in ihrer Bewegung untersuchen. Wäre so eine Regelmäßigkeit vorhanden, würden alle Hindernisse zusammen sich nach Ablauf einer Gesamtperiode in der gleichen Konfiguration befinden. Damit hätte man ein Ausschlusskriterium mit dem entschieden werden kann, dass keine Lösung existiert. Wäre z.B. das Ziel innerhalb dieser Periode nicht kollisionsfrei erreichbar, kann eine Lösung ausgeschlossen werden. Gleiches gilt, wenn der Agent innerhalb einer Periode seine initiale Konfiguration nicht ändern kann. Das größte Verbesserungspotential liegt meiner Meinung nach in dem Finden von neuen Bewertungsfaktoren für die Funktion eval und einem Verbessern der Balance bei der Gewichtung der einzelnen Faktoren.

Das Verbessern der Balance kann in einem Postprocessing geschehen, also einem Auswerten der gefundenen Lösung. Am Ende wird ein Wegpunkt zurückgegeben, der zusammen mit seinen Vorfahren die beste gefunden Bewegung von s_A nach z mit k Wegpunkten beschreibt. Im idealen Fall würde die Bewertungsfunktion jeden dieser kWegpunkte eine gute Priorität geben und der Algorithmus wäre nach k Schritten fertig. In der Auswertung würde die Priorität der k Wegpunkte mit der durchschnittlich vergebenen Priorität verglichen werden. Das Ziel sollte es sein zu erkennen, wenn eval eine falsche Entscheidung getroffen hat und warum.

Die Komplexität der Bewegungsplanung hängt im wesentlichen von drei Faktoren ab, der Dimension in der wir uns bewegen, die Bewegungsfreiheit des Agenten und ob die Hindernisse statisch sind oder sich bewegen können und welche Geometrie sie haben. Dabei gibt es zunächst zwei Probleme zu unterscheiden: Die Entscheidung, ob eine Lösung existiert und wenn ja, die Berechnung einer optimalen Lösung. In [2] wird bewiesen, dass die Wegplanung für einen punktförmigen Agenten in einer 2D-Umgebung mit beschränkter Geschwindigkeit NP-schwer ist, selbst wenn die konvexen Hindernisse sich nur mit einer konstanten Geschwindigkeit linear bewegen. In einer 3D-Umgebung mit rotierenden sich nicht linear bewegenden Hindernissen ist das Problem PSPACE-schwer und ohne Geschwindigkeitsbegrenzung noch NP-schwer [4]. Wenn keine Bewegungseinschränkungen für den Agenten vorliegen und die Bewegungen der Hindernisse algebraisch beschrieben werden können, ist das Problem in polynomieller Zeitlösbar [4].

Warum ist die Beschränkung der Bewegungsfreiheit, also der Geschwindigkeit, sogravierend? Mit seiner begrenzten Geschwindigkeit kann sich der Agent nicht bewegen ohne das Zeit vergeht, in der sich dann auch die Hindernisse bewegen. Wenn man die Zeit als dritte Dimension betrachtet, kann der Agent sich mit begrenzter Geschwindigkeit zu keinem Zeitpunkt t an zwei Positionen befinden und t steigt streng monoton mit jeder Bewegung des Agenten. Eine Bewegung ohne voranschreitende Zeit würde ja bedeuten, dass die Hindernisse statisch sind und somit nur eine kollisionsfreie Polylinie zwischen der Position des Agenten p(t) und dem Zielpunkt z zu einem Zeitpunkt t existieren muss. Wir vermuten, dass das in dieser Arbeit behandelte Problem mindestens NP-schwer ist, da es sich mit einem Agenten ohne Radius und mit einer unbegrenzten Beschleunigung dem Bewegungsplanungsproblem in [2}] sehr ähnlich ist. Ob es ausserdem noch PSPACE-schwer ist bleibt ebenso offen, da wir zwar Positionen mit zugehörigen Geschwindigkeiten im 4-dimensionalen Raum darstellen lässt, aber es, wie in [4] gefordert, keine dynamischen rotierenden Hindernisse gibt.

• Zusammenfassung
• Einführung
• Physikalische Grundlagen
• Lösungsansatz RAMP
• Implementierung
• Diskussion

• Page:
•  1 
•  2 
•  3