pengantar

Tantangannya adalah varian yang sangat menarik dari arena pacuan kuda dan dua tantangan itu:

• Untuk Vectory! - Grand Prix Balap Vektor
• Program Mobil Balap

Sumber tantangan ini ada di sini (dalam bahasa Jerman): c't-Racetrack

Tantangan ini sangat menarik (dan berbeda dari dua tantangan di atas) karena menggabungkan ruang pencarian yang besar dengan beberapa kondisi tepat yang harus dipenuhi. Karena ruang pencarian yang luas, teknik pencarian lengkap sulit digunakan, karena kondisi yang tepat, metode perkiraan juga tidak mudah digunakan. Karena kombinasi unik ini (ditambah intuisi yang mendasari dari fisika) masalahnya menarik (dan segala sesuatu sehubungan dengan mobil balap tetap menarik ;-)

Tantangan

Lihatlah arena pacuan kuda ( sumber ) berikut:

Anda harus mulai (120,180)dan menyelesaikan tepat pada (320,220)("Ziel" dalam bahasa Jerman) tanpa menyentuh salah satu dinding.

Mobil dikendalikan oleh vektor percepatan bentuk (a_x,a_y)- sebagai contoh:

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

Angka pertama adalah percepatan untuk vektor-x, yang kedua untuk vektor-y. Mereka harus bilangan bulat karena Anda hanya diperbolehkan menggunakan titik bilangan bulat di grid. Selain itu, kondisi berikut harus dipenuhi:

a_x^2 + a_y^2 <= 100,

yang berarti bahwa akselerasi ke segala arah harus di bawah atau sama dengan 10.

Untuk melihat cara kerjanya lihat gambar berikut ( sumber ):

Sebagai contoh: Mulai dari (120,180)Anda berakselerasi dengan 8arah x dan arah -6y. Untuk langkah selanjutnya ini adalah kecepatan Anda di mana Anda menambahkan akselerasi Anda (10,0)untuk mendapatkan (secara fisik benar) gerakan Anda selanjutnya (ke titik (146,168). Gerakan yang dihasilkan adalah yang terpenting dalam memeriksa apakah Anda menyentuh salah satu dinding. Pada langkah berikutnya Anda kembali menambahkan vektor percepatan berikutnya ke kecepatan Anda saat ini untuk mendapatkan gerakan berikutnya dan seterusnya. Jadi pada setiap langkah mobil Anda memiliki posisi dan kecepatan. (Dalam gambar ilustrasi di atas panah biru adalah untuk kecepatan, panah oranye untuk akselerasi dan panah merah gelap untuk gerakan yang dihasilkan.)

Sebagai kondisi tambahan Anda harus memiliki (0,0)kecepatan terminal ketika Anda berada di titik akhir (320,220).

Keluaran harus berupa daftar vektor percepatan dalam bentuk yang disebutkan di atas.

Pemenangnya adalah orang yang menyediakan program yang menemukan solusi dengan vektor percepatan paling sedikit.

Tiebreak
Selain itu akan lebih bagus jika Anda dapat menunjukkan bahwa ini adalah solusi optimal dan apakah ini satu-satunya solusi optimal atau apakah ada beberapa solusi optimal (dan mana mereka).

Akan lebih baik jika Anda bisa memberikan garis besar umum tentang bagaimana algoritma Anda bekerja dan mengomentari kodenya sehingga kami dapat memahaminya.

Saya memiliki program yang memeriksa apakah solusi yang diberikan valid dan saya akan memberikan umpan balik.

Tambahan
Anda dapat menggunakan bahasa pemrograman apa pun tetapi saya akan sangat senang jika seseorang menggunakan R karena saya sering menggunakannya dalam pekerjaan saya dan entah bagaimana terbiasa dengannya :-)

Tambahan II
Untuk pertama kalinya saya memulai hadiah - semoga ini adalah bola yang bergulir (atau lebih baik: dapatkan mobilnya mengemudi :-)

Python, 24 langkah (sedang berlangsung)

Idenya adalah untuk memecahkan masalah berkelanjutan pertama, sangat mengurangi ruang pencarian, dan kemudian mengukur hasilnya ke grid (dengan hanya membulatkan ke gridpoint terdekat dan mencari 8 kotak di sekitarnya)

Saya parametrize jalan sebagai jumlah fungsi trigonometrik (tidak seperti polinomial, mereka tidak berbeda dan lebih mudah untuk tetap di cek). Saya juga mengontrol kecepatan secara langsung daripada akselerasi, karena lebih mudah untuk menegakkan kondisi batas dengan hanya mengalikan fungsi pembobotan yang cenderung 0 pada akhirnya.
Fungsi obyektif saya terdiri dari
skor -eksponensial untuk akselerasi>
skor 10 -polynomial untuk jarak euclidean antara titik terakhir dan target
- skor konstan tinggi untuk setiap persimpangan dengan dinding, menurun ke arah tepi dinding

Untuk meminimalkan skor, saya membuang semuanya ke dalam optimasi Nelder-Mead dan tunggu beberapa detik. Algoritme selalu berhasil mencapai akhir, berhenti di sana dan tidak melebihi percepatan maksimum, tetapi memiliki masalah dengan dinding. Jalur tersebut dapat diteleportasi melalui sudut-sudut dan terjebak di sana, atau berhenti di sebelah dinding dengan tujuan tepat di seberang (gambar kiri)

Selama pengujian, saya beruntung dan menemukan jalur yang dililit dengan cara yang menjanjikan (gambar kanan) dan setelah mengubah parameter lagi saya bisa menggunakannya sebagai tebakan awal untuk optimasi yang sukses.

Kuantisasi
Setelah menemukan lintasan parametrik, tiba saatnya untuk menghapus titik desimal. Melihat lingkungan 3x3 mengurangi ruang pencarian dari sekitar 300 ^ N menjadi 9 ^ N, tetapi masih terlalu besar dan membosankan untuk diterapkan. Sebelum saya menyusuri jalan ini, saya mencoba menambahkan istilah "Snap to Grid" ke fungsi objektif (bagian komentar). Seratus langkah lagi pengoptimalan dengan tujuan yang diperbarui dan hanya pembulatan sudah cukup untuk mendapatkan solusi.

[(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)]

Jumlah langkah telah diperbaiki dan bukan bagian dari optimasi, tetapi karena kami memiliki deskripsi analitis jalur, (dan karena akselerasi maksimal jauh di bawah 10), kami dapat menggunakannya kembali sebagai titik awal untuk optimasi lebih lanjut dengan jumlah yang lebih kecil dari timesteps

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()

Aktivitas: GUI yang memungkinkan Anda menggambar jalur awal untuk mendapatkan arah yang kasar. Apa pun lebih baik daripada pengambilan sampel acak dari ruang 14 dimensi