Projekt: Optimaler Weg durch Landschaft

ich hab langeweile und will mal ein projekt beginnen. ich will ein programm schreiben, welches den effizientesten weg durch eine gebirgslandschaft findet.

mein ansatz: das gebirge ist eine Funktion $\phi: \mathbb{R}^2 \rightarrow \mathbb{R}, (x, y) \mapsto \phi(x, y)$ (und später ist das Gebirge vllt. noch zeitabhängig). bergangehen soll natürlich "anstrengend" sein und daher irgendwie bestraft werden, es soll also besser sein, durch täler und pässe zu gehen.

mein ansatz ist ein optimierungsproblem auf einem weglängen-funktional (variationsrechnung), also suche ich quasi die kleinste gewichtete weglänge vom weg $\gamma(t) = (x(t), y(t), z(t) = \phi(x(t), y(t))^\intercal$ , die ich dann gedenke, so zu modellieren:

$S(\gamma) = \int\limits\_a^b \phi(x(t), y(t)) \sqrt{\dot x^2(t) + \dot y^2(t) + \dot\phi^2(x(t), y(t))}dt =: \int\limits\_a^b L(x, \dot x, y, \dot y) dt$

den optimalen Weg erhalte ich dann aus $\delta S(\gamma_o) = 0$ mit den Euler-Lagrange-Gleichungen:

\begin{align} \frac{\partial L}{\partial x} = \frac{d}{dt}\frac{\partial L}{\partial \dot x}\\ \frac{\partial L}{\partial y} = \frac{d}{dt}\frac{\partial L}{\partial \dot y}

das ist dann also so ein i.A. nichtlineares gewöhnliches differentialgleichungssystem, was ich dann (hoffentlich) numerisch lösen kann, um den besten weg (x(t), y(t)) zu bekommen.

ist das vorgehen sinnvoll? kann man das auch effizient genug implementieren, um es in echtzeit ablaufen zu lassen? würde ich dieses dgl-system dann mit runge-kutta lösen?

Euler-Lagrange-Gleichungen:

\begin{align} \frac{\partial L}{\partial x} = \frac{d}{dt}\frac{\partial L}{\partial \dot x}\\ \frac{\partial L}{\partial y} = \frac{d}{dt}\frac{\partial L}{\partial \dot y} \end{align}

Daniel E.

Bei so einem Problem könnte das -- je nach Problemdimension -- schon funktionieren. Wenn man dann aber anfängt, stückweise Randbedingungen in das Problem dazuzunehmen, wird das so immer unhandlicher und die Verfahren funktionieren meiner Erfahrung nach dann nicht mehr gut.

Es wird dann oft besser, auf direkte Verfahren umzusteigen, also -- banal gesagt -- x und y vorneweg zu diskretisieren und dann "nur noch" mit nichtlinearen Optimierern die Kostenfunktion anzugreifen.

Der Teufel ist da immer im Detail. Google mal nach nonlinear optimal control oder so. Wenn Du über die Uni an das Buch von Betts rankommst, das hat mir damals sehr geholfen, als ich mit so ähnlichen Problemen rumgespielt habe.

Ich hoffe, es klappt.

Gregor

Daniel E. schrieb:

Es wird dann oft besser, auf direkte Verfahren umzusteigen, also -- banal gesagt -- x und y vorneweg zu diskretisieren und dann "nur noch" mit nichtlinearen Optimierern die Kostenfunktion anzugreifen.

Warum nicht einfach den A* Algorithmus nutzen? Übersehe ich hier ein Problem?

Daniel E. schrieb:

Wenn man dann aber anfängt, stückweise Randbedingungen in das Problem dazuzunehmen, wird das so immer unhandlicher und die Verfahren funktionieren meiner Erfahrung nach dann nicht mehr gut.

Wie meinst du das? So wie ich das sehe, sind meine Randbedingungen durch Start- und Zielpunkt meines Weges bestimmt, meine Zwangsbedingung ist $z(x, y) = \phi(x, y)$ . Meinst du, dass die EL-Gln. zu steif sein könnten, als dass man sie numerisch gut lösen könnte?

Ich sehe gerade, dass ich auch anders gewichten muss, wenn ich Wege bergan bestrafen will, Wege bergab aber eher egal sein sollen. Vermutlich eher wie $|\frac{partial \phi(x, y, z)}{\partial z}|$ .

Daniel E. schrieb:

Es wird dann oft besser, auf direkte Verfahren umzusteigen, also -- banal gesagt -- x und y vorneweg zu diskretisieren und dann "nur noch" mit nichtlinearen Optimierern die Kostenfunktion anzugreifen.

Hm, ich sehe schon. Gregor sagt ja auch, "nimm lieber A*", also irgendwas bekanntes. Aber vielleicht werde ich es trotzdem mal ausprobieren, nur um zu sehen, ob es geht. Den Buch-Tipp werde ich mir mal beherzigen.

Eine konzeptionelle Schwierigkeit sehe ich noch bei den Diff.-Gln. Wenn ich die ELG mal für irgendein "leichtes" Gebirge wie z = x + y aufschreibe, dann sind die allesamt ziemlich groß, hässlich und insbesondere implizit (also so wie $\dot y = f(\dot y, y, ...)$ .
Gibt es irgendwelche numerische Verfahren, die sich auf so implizite Probleme fokussieren?

Projekt0r schrieb:

Daniel E. schrieb:

Wenn man dann aber anfängt, stückweise Randbedingungen in das Problem dazuzunehmen, wird das so immer unhandlicher und die Verfahren funktionieren meiner Erfahrung nach dann nicht mehr gut.

Wie meinst du das? So wie ich das sehe, sind meine Randbedingungen durch Start- und Zielpunkt meines Weges bestimmt, meine Zwangsbedingung ist $z(x, y) = \phi(x, y)$ . Meinst du, dass die EL-Gln. zu steif sein könnten, als dass man sie numerisch gut lösen könnte?

Wenn das das einzigen bleiben und deine Kosten nicht allzu abgefahren aussehen, dann könnte das schon ausreichen.
Schlechter wirds, wenn Du Bereiche in deiner Karte hast, die Du nicht durchqueren kannst, bspw. ein See oder eine Schlucht oder sich deine Systemdynamik ändert (weil Du nun nicht mehr wanderst, sondern ein Teilstück mit dem Zug fährst. Welches Teilstück ist dafür optimal?). Du hast Dann neue (Un-)Gleichheitsbedingungen g(x,y,t)>=0 oder schlimmeres im Problem.

Im Prinzip sollte dich das nicht aufhalten, dafür gibt es auch Ansätze und auch analytische Resultate, indem man sich systematisch die Aktivierungsbedingungen durchgeht, das als Bestrafungsterm in die Kosten aufnimmt, Eckbedingungen auswertet oder was weiß ich. Das macht es aber zunehmend schwerer, das Problem zu skalieren und es in Echtzeit zu lösen.

Gregor: Ich dachte jetzt erst mal daran, x und y über die Zeit zu diskretisieren, also p(t1), p(t2), ... p(tn) zu konstruieren, aber jedes p(ti) kann immer noch aus R^n sein.
Natürlich kann man auch noch räumlich diskretisieren, einen Graphen mit Übergangskosten konstruieren und den dann lösen. Im dynamischen Fall ist das aber oft nicht mehr so intuitiv, weil die Kosten zwischen Knoten k(i) und k(i+1) nicht nur von Ort sondern auch von der Zeit abhängen, wie lange man dafür braucht. Dann nimmt man gerne einen allgemeinen dynamischen Programmieransatz her. Wenn man das Problem richtig hindreht, bekommt man das oft ganz gut in Echtzeit implementiert.

C14

Projekt0r schrieb:

... den optimalen Weg erhalte ich dann aus $\delta S(\gamma_o) = 0$ mit den Euler-Lagrange-Gleichungen ...

Und was für Anfangsbedingungen nimmst du für die Lösung der Euler-Lagrange-Gleichungen?
Wenn du zu einem vorgegebenen Endpunkt kommen willst, bringt dir diese Formulierung denke ich nicht viel.

otze

Gregor schrieb:

Daniel E. schrieb:

Es wird dann oft besser, auf direkte Verfahren umzusteigen, also -- banal gesagt -- x und y vorneweg zu diskretisieren und dann "nur noch" mit nichtlinearen Optimierern die Kostenfunktion anzugreifen.

Warum nicht einfach den A* Algorithmus nutzen? Übersehe ich hier ein Problem?

Nen Dijkstra auf einer diskretisierten Lanschaft würde ich da schon noch sehen, aber ich weiß nicht, ob man für den A* eine entsprechende Heuristik findet. Der Raum ist ja nicht euklidisch.

//Edit okay hab mich schon selbst wiederlegt, natürlich geht das...