Einführung

Die Herausforderung ist eine sehr interessante Variante der Rennstrecke und dieser beiden Herausforderungen:

• Zum Vectory! - Der Vector Racing Grand Prix
• Programmieren Sie einen Rennwagen

Quelle dieser Herausforderung ist hier: c't-Racetrack

Diese Herausforderung ist besonders interessant (und unterscheidet sich von den beiden oben genannten Herausforderungen), da sie einen riesigen Suchraum mit einigen genauen Bedingungen kombiniert, die erfüllt werden müssen. Aufgrund des riesigen Suchraums sind erschöpfende Suchtechniken schwer zu verwenden, da aufgrund der genauen Bedingungen auch ungefähre Methoden nicht einfach zu verwenden sind. Aufgrund dieser einzigartigen Kombination (plus der zugrunde liegenden Intuition aus der Physik) ist das Problem faszinierend (und alles im Zusammenhang mit Rennwagen ist sowieso faszinierend ;-)

Herausforderung

Schauen Sie sich folgende Rennstrecke an ( Quelle ):

Sie müssen (120,180)genau bei beginnen und enden, (320,220)ohne eine der Wände zu berühren.

Das Auto wird durch Beschleunigungsvektoren der Form gesteuert (a_x,a_y)- als Beispiel:

(8,-6)
(10,0)
(1,9)

Die erste Zahl ist die Beschleunigung für den x-Vektor, die zweite für den y-Vektor. Sie müssen Ganzzahlen sein, da Sie nur die Ganzzahlpunkte im Raster verwenden dürfen. Zusätzlich muss folgende Bedingung erfüllt sein:

a_x^2 + a_y^2 <= 100,

Dies bedeutet, dass die Beschleunigung in jede Richtung unter oder gleich sein muss 10.

Um zu sehen, wie es funktioniert, schauen Sie sich das folgende Bild ( Quelle ) an:

Als Beispiel: Ausgehend von (120,180)Ihnen beschleunigen Sie 8in x-Richtung und -6in y-Richtung. Für den nächsten Schritt ist dies Ihre Geschwindigkeit, bei der Sie Ihre Beschleunigung hinzufügen (10,0), um Ihre nächste resultierende Bewegung (zum Zeigen) (physisch korrekt) zu erhalten (146,168). Die resultierende Bewegung ist entscheidend, wenn Sie prüfen möchten, ob Sie eine der Wände berührt haben. Im nächsten Schritt Sie addieren erneut Ihren nächsten Beschleunigungsvektor zu Ihrer aktuellen Geschwindigkeit, um die nächste Bewegung usw. zu erhalten. Bei jedem Schritt hat Ihr Auto eine Position und eine Geschwindigkeit. (In der Abbildung oben sind die blauen Pfeile für die Geschwindigkeit die orangefarbenen Pfeile für die Beschleunigung und die dunkelroten Pfeile für die resultierende Bewegung.)

Als zusätzliche Bedingung müssen Sie die (0,0)Endgeschwindigkeit haben, wenn Sie sich am Endpunkt befinden (320,220).

Die Ausgabe muss eine Liste von Beschleunigungsvektoren in der oben genannten Form sein.

Der Gewinner ist derjenige, der ein Programm bereitstellt, das eine Lösung mit den wenigsten Beschleunigungsvektoren findet.

Tiebreaker
Zusätzlich wäre es großartig, wenn Sie zeigen könnten, dass dies eine optimale Lösung ist und ob dies die einzig optimale Lösung ist oder ob es mehrere optimale Lösungen gibt (und welche es sind).

Es wäre auch gut, wenn Sie einen allgemeinen Überblick über die Funktionsweise Ihres Algorithmus geben und den Code kommentieren könnten, damit wir ihn verstehen können.

Ich habe ein Programm, das prüft, ob eine bestimmte Lösung gültig ist, und ich werde Feedback geben.

Nachtrag
Sie können jede Programmiersprache verwenden, aber ich würde mich besonders freuen, wenn jemand R verwendet, weil ich es in meiner täglichen Arbeit häufig benutze und mich irgendwie daran gewöhnt habe :-)

Nachtrag II
Zum ersten Mal habe ich ein Kopfgeld gestartet - hoffentlich bringt das den Ball ins Rollen (oder besser: bringt das Auto zum Fahren :-)

Python, 24 Schritte (in Arbeit)

Die Idee war, zuerst das kontinuierliche Problem zu lösen, den Suchraum erheblich zu verkleinern und dann das Ergebnis im Raster zu quantisieren (indem nur auf den nächsten Rasterpunkt gerundet und die umliegenden 8 Quadrate durchsucht werden).

Ich parametrisiere den Pfad als Summe trigonometrischer Funktionen (im Gegensatz zu Polynomen divergieren sie nicht und sind leichter in Schach zu halten). Ich steuere auch die Geschwindigkeit direkt anstelle der Beschleunigung, da es einfacher ist, die Randbedingung durch einfaches Multiplizieren einer Gewichtungsfunktion zu erzwingen, die am Ende gegen 0 tendiert.
Meine Zielfunktion besteht aus einer
exponentiellen Bewertung für Beschleunigung> 10 - einer
Polynombewertung für den euklidischen Abstand zwischen dem letzten Punkt und dem Ziel
- einer hohen konstanten Bewertung für jeden Schnittpunkt mit einer Wand, die zu den Rändern der Wand hin abnimmt

Um die Punktzahl zu minimieren, werfe ich alles in die Nelder-Mead-Optimierung und warte einige Sekunden. Dem Algorithmus gelingt es immer, bis zum Ende zu gelangen, dort anzuhalten und die maximale Beschleunigung nicht zu überschreiten, aber er hat Probleme mit Wänden. Der Pfad teleportiert sich entweder durch Ecken und bleibt dort stecken oder hält neben einer Wand mit dem Ziel direkt gegenüber (linkes Bild).

Während des Testens hatte ich Glück und fand einen Pfad, der auf vielversprechende Weise gekrümmt war (rechtes Bild). Nachdem ich die Parameter noch weiter angepasst hatte, konnte ich ihn als erste Vermutung für eine erfolgreiche Optimierung verwenden.

Quantisierung
Nachdem ein parametrischer Pfad gefunden wurde, war es Zeit, die Dezimalstellen zu entfernen. Wenn Sie sich die 3x3-Nachbarschaft ansehen, wird der Suchraum von ungefähr 300 ^ N auf 9 ^ N reduziert, aber es ist immer noch zu groß und langweilig, um ihn zu implementieren. Bevor ich diesen Weg ging, habe ich versucht, der Zielfunktion (den kommentierten Teilen) einen Begriff "Am Raster ausrichten" hinzuzufügen. Hundert weitere Optimierungsschritte mit dem aktualisierten Ziel und einer einfachen Rundung reichten aus, um die Lösung zu erhalten.

[(9, -1), (4, 0), (1, 1), (2, 2), (-1, 2), (-3, 4), (-3, 3), (-2 , 3), (-2, 2), (-1, 1), (0, 0), (1, -2), (2, -3), (2, -2), (3, -5 ), (2, -4), (1, -5), (-2, -3), (-2, -4), (-3, -9), (-4, -4), (- 5, 8), (-4, 8), (5, 8)]

Die Anzahl der Schritte wurde festgelegt und ist nicht Teil der Optimierung. Da wir jedoch eine analytische Beschreibung des Pfades haben (und die maximale Beschleunigung deutlich unter 10 liegt), können wir sie als Ausgangspunkt für die weitere Optimierung mit einer geringeren Anzahl von Schritten wiederverwenden Zeitschritte

from numpy import *
from scipy.optimize import fmin
import matplotlib.pyplot as plt
from matplotlib.collections import LineCollection as LC

walls = array([[[0,0],[500,0]],   # [[x0,y0],[x1,y1]]
        [[500,0],[500,400]],
        [[500,400],[0,400]],
        [[0,400],[0,0]],

        [[200,200],[100,200]],
        [[100,200],[100,100]],
        [[100,100],[200,100]],

        [[250,300],[250,200]],

        [[300,300],[300,100]],
        [[300,200],[400,200]],
        [[300,100],[400,100]],

        [[100,180],[120, 200]], #debug walls
        [[100,120],[120, 100]],
        [[300,220],[320, 200]],
        #[[320,100],[300, 120]],
])

start = array([120,180])
goal = array([320,220])

###################################
# Boring stuff below, scroll down #
###################################
def weightedintersection2D(L1, L2):
    # http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
    p = L1[0]
    q = L2[0]
    r = L1[1]-L1[0]
    s = L2[1]-L2[0]
    d = cross(r,s)
    if d==0: # parallel
        if cross(q-p,r)==0: return 1 # overlap
    else:
        t = cross(q-p,s)*1.0/d
        u = cross(q-p,r)*1.0/d
        if 0<=t<=1 and 0<=u<=1: return 1-0*abs(t-.5)-1*abs(u-.5) # intersect at p+tr=q+us
    return 0

def sinsum(coeff, tt):
    '''input: list of length 2(2k+1), 
    first half for X-movement, second for Y-movement.
    Of each, the first k elements are sin-coefficients
    the next k+1 elements are cos-coefficients'''
    N = len(coeff)/2
    XS = [0]+list(coeff[:N][:N/2])
    XC =     coeff[:N][N/2:]
    YS = [0]+list(coeff[N:][:N/2])
    YC =     coeff[N:][N/2:]
    VX = sum([XS[i]*sin(tt*ww[i]) + XC[i]*cos(tt*ww[i]) for i in range(N/2+1)], 0)
    VY = sum([YS[i]*sin(tt*ww[i]) + YC[i]*cos(tt*ww[i]) for i in range(N/2+1)], 0)
    return VX*weightfunc, VY*weightfunc

def makepath(vx, vy):
    # turn coordinates into line segments, to check for intersections
    xx = cumsum(vx)+start[0]
    yy = cumsum(vy)+start[1]
    path = []
    for i in range(1,len(xx)):
        path.append([[xx[i-1], yy[i-1]],[xx[i], yy[i]]])
    return path

def checkpath(path):
    intersections = 0
    for line1 in path[:-1]: # last two elements are equal, and thus wrongly intersect each wall
        for line2 in walls:
            intersections += weightedintersection2D(array(line1), array(line2))
    return intersections

def eval_score(coeff):
    # tweak everything for better convergence
    vx, vy = sinsum(coeff, tt)
    path = makepath(vx, vy)
    score_int = checkpath(path)
    dist = hypot(*(path[-1][1]-goal))
    score_pos = abs(dist)**3
    acc = hypot(diff(vx), diff(vy))
    score_acc = sum(exp(clip(3*(acc-10), -10,20)))
    #score_snap = sum(abs(diff(vx)-diff(vx).round())) + sum(abs(diff(vy)-diff(vy).round()))
    print score_int, score_pos, score_acc#, score_snap
    return score_int*100 + score_pos*.5 + score_acc #+ score_snap

######################################
# Boring stuff above, scroll to here #
######################################
Nw = 4 # <3: paths not squiggly enough, >6: too many dimensions, slow
ww = [1*pi*k for k in range(Nw)]
Nt = 30 # find a solution with tis many steps
tt = linspace(0,1,Nt)
weightfunc = tanh(tt*30)*tanh(30*(1-tt)) # makes sure end velocity is 0

guess = random.random(4*Nw-2)*10-5
guess = array([ 5.72255365, -0.02720178,  8.09631272,  1.88852287, -2.28175362,
        2.915817  ,  8.29529905,  8.46535503,  5.32069444, -1.7422171 ,
       -3.87486437,  1.35836498, -1.28681144,  2.20784655])  # this is a good start...
array([ 10.50877078,  -0.1177561 ,   4.63897574,  -0.79066986,
         3.08680958,  -0.66848585,   4.34140494,   6.80129358,
         5.13853914,  -7.02747384,  -1.80208349,   1.91870184,
        -4.21784737,   0.17727804]) # ...and it returns this solution      

optimsettings = dict(
    xtol = 1e-6,
    ftol = 1e-6,
    disp = 1,
    maxiter = 1000, # better restart if not even close after 300
    full_output = 1,
    retall = 1)

plt.ion()
plt.axes().add_collection(LC(walls))
plt.xlim(-10,510)
plt.ylim(-10,410)
path = makepath(*sinsum(guess, tt))
plt.axes().add_collection(LC(path, color='red'))
plt.plot(*start, marker='o')
plt.plot(*goal, marker='o')
plt.show()

optres = fmin(eval_score, guess, **optimsettings)
optcoeff = optres[0]    

#for c in optres[-1][::optimsettings['maxiter']/10]:
for c in array(optres[-1])[logspace(1,log10(optimsettings['maxiter']-1), 10).astype(int)]:
    vx, vy = sinsum(c, tt)
    path = makepath(vx,vy)
    plt.axes().add_collection(LC(path, color='green'))
    plt.show()

Zu erledigen: GUI, mit der Sie einen ersten Pfad zeichnen können, um einen groben Orientierungssinn zu erhalten. Alles ist besser als eine zufällige Stichprobe aus dem 14-dimensionalen Raum