Warum wird Reinforcement Learning so selten bei der Pfadfindung eingesetzt?

Der ehrwürdige theoretische Algorithmus A * für Graphen mit kürzestem Pfad und nachfolgende Verbesserungen (z. B. Hierarchical Annotated A *) ist eindeutig die Technik der Wahl für die Pfadfindung in der Spieleentwicklung.

Stattdessen scheint mir RL ein natürlicheres Paradigma zu sein, um einen Charakter in einem Spielfeld zu bewegen.

Dabei ist mir kein einziger Spieleentwickler bekannt, der eine auf Reinforcement Learning basierende Pathfinding-Engine implementiert hat. (Ich schließe daraus nicht, dass die Anwendung von RL bei der Pfadfindung 0 ist, nur dass sie im Verhältnis zu A * und Freunden sehr klein ist.)

Was auch immer der Grund sein mag, es liegt nicht daran, dass diese Entwickler RL nicht kennen, wie die Tatsache belegt, dass RL häufig an anderer Stelle in der Spiel-Engine verwendet wird.

Diese Frage ist kein Vorwand, um eine Stellungnahme zu RL bei der Pfadfindung abzugeben. in der Tat gehe ich davon aus, dass die stillschweigende Präferenz für A * et al. über RL ist richtig - aber diese Präferenz ist nicht offensichtlich für mich und ich bin sehr gespannt auf den Grund dafür, insbesondere von jedem, der versucht hat, RL für die Wegfindung zu verwenden.

Ich würde mir vorstellen, dass dies daran liegt, dass die Aussicht auf die Verwendung von RL in der Regel wie eine echte A * -Heuristik aussieht, da Sie nur aus Spielzeugproblemen eine nützliche Verallgemeinerung der Politik erhalten und die Belohnungsfunktion verdächtig aussieht Überarbeitete, ineffiziente Methode, um Ergebnisse zu erzielen, die allenfalls mit A * identisch sind, aber wahrscheinlich nicht annähernd so gut sind.

Das mag RL gegenüber unfair sein, und wenn ja, würde ich gerne wissen, warum, aber ich sehe nichts, was darauf hindeutet.

Viele von uns erinnern sich auch daran, wie die Wegfindung in Spielen vor der weit verbreiteten Einführung von A * war, und sind nicht bereit, den Spielern etwas Ähnliches zuzufügen oder die Marktfolgen davon zu tragen.

Ohne viel über RL zu wissen, werde ich versuchen, Ihre Frage mit anderen Fragen zu beantworten:

Können Sie mit RL feststellen, ob es möglich ist, Punkt A von Punkt B aus zu erreichen?

Kann RL reproduzierbares / konsistentes / testbares Navigationsverhalten garantieren?

Wie vergleichen sich Arbeitsspeicher- und CPU-Laufzeitanforderungen mit A *? Wie viel können Sie im Vergleich zu beispielsweise Navigationsnetzen vorberechnen?

Wie kann RL in einer Umgebung mit dynamischen Kollisionen gerecht werden?

Wie viel schwieriger ist es, RL richtig zu verstehen und umzusetzen, beispielsweise im Vergleich zu Lenkverhalten?

Gibt es gute Middleware-Anbieter für RL?

Vielleicht können Ihnen diese Fragen bei Ihrer Antwort helfen.

Ich bin verwirrt von dem Vorschlag, dass RL "ein natürlicheres Paradigma" ist. Ich verstehe nicht, wie Reinforcement Learning der Problemdomäne annähernd so sauber oder genau zuzuordnen ist wie Graph Search. Normalerweise möchten Sie nicht, dass ein Agent etwas lernt - Sie haben angenommen, dass er die Route bereits kennt. Stattdessen möchten Sie, dass sie die direkteste verfügbare Route auswählen und verwenden, und die Diagrammsuche erleichtert dies auf nahezu optimale Weise. Wenn Sie RL offline verwenden, um die beste Richtung zu berechnen, die an einem bestimmten Knoten für ein bestimmtes Ziel eingeschlagen werden kann, würde dies im Großen und Ganzen A * entsprechen, außer dass Sie erheblich mehr Speicher * benötigen und die Entwickler sehr vorsichtig vorgehen Stellen Sie sicher, dass alle Knoten während des Trainings ausreichend erforscht wurden. Und dieses Training wird nur einen Wert ergeben, den wir mit der Pythagoras-Gleichung bereits sehr gut annähern können, da wir im Voraus wissen, dass der Graph den euklidischen Abstandsregeln folgt. (Dies ist natürlich nicht für alle Situationen der Fall, in denen Graphensuche und / oder Verstärkung eingesetzt werden können.)

(In Bezug auf das Speicherproblem: Wenn Sie 1000 mögliche quantisierte Positionen auf einer Karte hatten, sind das 1000 Knoten plus 1000 * M Kanten (wobei M die durchschnittliche Anzahl von Knoten ist, die von jedem anderen Knoten aus erreichbar sind.) Dies plus die Heuristik ist ausreichend für A * zum Bedienen. Zum Erlernen des Funktionierens der Verstärkung, zumindest so, wie ich es mir vorstelle, würden Sie außerdem 1000 Einträge für jede dieser 1000 * M-Kanten benötigen, um den Belohnungswert für das Folgen dieser Kante für eine der 1000 zu erzielen Mögliche Ziele: Das sind viele Daten - und jedes einzelne muss einigermaßen genau sein, um Schleifen, Umwege oder Sackgassen zu vermeiden.

Pathfinding ist ein relativ "gelöstes" Problem, RL nicht.

Mit A * können Entwickler Heuristiken schnell erstellen und im Laufe der Zeit verbessern. RL (ich spreche von Q-Learning, wenn ich mich hier auf RL beziehe) benötigt Zeit, um die besten Lernraten und Abzinsungsfaktoren zu berechnen (Zeit, die es wert ist, für andere Aspekte des Spiels aufgewendet zu werden).

Es kommt wirklich auf die Art des Spiels an. Wenn alles im Spiel statisch ist, ist es effizienter, die A * -Suche zu verwenden. Wenn sich jedoch andere menschliche Spieler im selben Gebiet bewegen, ist ein Fehlschlagen der A * -Suche garantiert. Eine * Suche hat keine Ahnung, wohin andere Spieler steuern. Andererseits kann RL das Verhalten anderer Spieler modellieren und einen besseren Weg finden, der die Bewegung anderer Spieler berücksichtigt.