Introdução

O desafio é uma variante muito interessante da pista de corrida do jogo e esses dois desafios:

• Para Vectory! - O Grande Prêmio de Corridas de Vetores
• Programe um carro de corrida

A fonte deste desafio está aqui (em alemão): c't-Racetrack

Esse desafio é especialmente interessante (e diferente dos dois desafios mencionados acima) porque combina um enorme espaço de pesquisa com algumas condições exatas que precisam ser atendidas. Por causa das enormes técnicas de pesquisa exaustivas no espaço de pesquisa, é difícil de usar, devido às condições exatas dos métodos aproximados também não são facilmente utilizáveis. Por causa dessa combinação única (mais a intuição subjacente da física), o problema é fascinante (e tudo relacionado aos carros de corrida é fascinante de qualquer maneira ;-)

Desafio

Dê uma olhada na seguinte pista ( fonte ):

Você precisa começar (120,180)e terminar exatamente em (320,220)("Ziel" em alemão) sem tocar em nenhuma das paredes.

O carro é controlado por vetores de aceleração do formulário (a_x,a_y)- como um exemplo:

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

O primeiro número é a aceleração para o vetor x, o segundo para o vetor y. Eles precisam ser números inteiros porque você só pode usar os pontos inteiros na grade. Além disso, a seguinte condição deve ser atendida:

a_x^2 + a_y^2 <= 100,

o que significa que a aceleração em qualquer direção deve ser menor ou igual a 10.

Para ver como ele funciona, dê uma olhada na seguinte imagem ( fonte ):

Como exemplo: A partir de (120,180)você, acelere 8na direção xe na direção -6y. Para o próximo passo, esta é a sua velocidade na qual você adiciona sua aceleração (10,0)para obter (fisicamente correto) o seu próximo movimento resultante (apontar (146,168). O movimento resultante é o que conta quando se trata de examinar se você tocou uma das paredes. No próximo passo você adiciona novamente o seu próximo vetor de aceleração à sua velocidade atual para obter o próximo movimento e assim por diante. A cada passo, seu carro tem uma posição e uma velocidade. (Na figura ilustrativa acima, as setas azuis são para a velocidade, as setas laranja para aceleração e as setas vermelhas escuras para o movimento resultante.)

Como condição adicional, você deve ter (0,0)velocidade terminal quando estiver no ponto de chegada (320,220).

A saída deve ser uma lista de vetores de aceleração na forma acima mencionada.

O vencedor é quem fornece um programa que encontra uma solução com o menor número de vetores de aceleração.

Desempate
Além disso, seria ótimo se você pudesse mostrar que esta é uma solução ideal e se esta é a única solução ideal ou se existem várias soluções ótimas (e quais são).

Também seria bom se você pudesse fornecer um esboço geral de como seu algoritmo funciona e comentar o código para que possamos entendê-lo.

Eu tenho um programa que verifica se alguma solução é válida e eu darei feedback.

Adendo
Você pode usar qualquer linguagem de programação, mas eu ficaria muito feliz se alguém usasse R porque eu o uso muito no meu trabalho diário e de alguma forma me acostumei :-)

Adendo II
Pela primeira vez, comecei uma recompensa - espero que isso aconteça (ou melhor: pegue o carro dirigindo :-)

Python, 24 etapas (trabalho em andamento)

A idéia era resolver o problema contínuo primeiro, reduzindo bastante o espaço de pesquisa e, em seguida, quantificando o resultado na grade (arredondando para o ponto de grade mais próximo e pesquisando os 8 quadrados ao redor)

Parametrizo o caminho como uma soma de funções trigonométricas (diferentemente dos polinômios, eles não divergem e são mais fáceis de controlar). Também controlo a velocidade diretamente em vez da aceleração, porque é mais fácil impor a condição de contorno simplesmente multiplicando uma função de ponderação que tende a 0 no final.
Minha função objetivo consiste em
: pontuação exponencial para aceleração> 10
; pontuação polinomial para a distância euclidiana entre o último ponto e o alvo;
alta pontuação constante para cada interseção com uma parede, diminuindo em direção às bordas da parede

Para minimizar a pontuação, eu jogo tudo na otimização do Nelder-Mead e espero alguns segundos. O algoritmo sempre consegue chegar ao fim, parando aí e não excedendo a aceleração máxima, mas tem problemas com paredes. O caminho se teleporta pelos cantos e fica preso ali, ou para ao lado de uma parede com o objetivo do outro lado (imagem à esquerda)

Durante os testes, tive sorte e encontrei um caminho que era distorcido de uma maneira promissora (imagem certa) e depois de ajustar os parâmetros um pouco mais, eu poderia usá-lo como um palpite inicial para uma otimização bem-sucedida.

Quantização
Depois de encontrar um caminho paramétrico, era hora de remover os pontos decimais. Observar a vizinhança 3x3 reduz o espaço de pesquisa de aproximadamente 300 ^ N para 9 ^ N, mas ainda é muito grande e chato de implementar. Antes de seguir esse caminho, tentei adicionar um termo "Ajustar à grade" à função objetivo (as partes comentadas). Mais cem etapas de otimização com o objetivo atualizado e simplesmente arredondamento foram suficientes para obter a solução.

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

O número de etapas foi corrigido e não faz parte da otimização, mas como temos uma descrição analítica do caminho (e como a aceleração máxima está bem abaixo de 10), podemos reutilizá-lo como ponto de partida para otimização adicional com um número menor de 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()

A Fazer: GUI que permite desenhar um caminho inicial para obter uma sensação aproximada de direção. Qualquer coisa é melhor do que a amostragem aleatória do espaço 14-dimensional