Meu EP ainda não está funcionando e estou confusa sobre a função Modify-Cost.
Primeiro, encontro o caminho ótimo inicial, daí vou percorrendo esse caminho até verificar que o custo da célula a para célula b não era o esperado.
A partir daí, devo chamar a Modify-Cost.
Pelo que entendi, c(b,a) é o custo novo encontrado, então, se o b já não estava mais na lista, devo coloca-lo.
Eu entendi errado? Meu robô está passando pela parede.
Ah! Não entendi porque a função devolve get-kmin.
Alguém pode me ajudar?
Professor, se a pergunta "quebrar as regras" do uso do PACA, por favor, me avise.
Outra coisa, alguém sabe se a entrega ficou para amanhã ou para o dia da prova?
Muito obrigada!
Não sei se isso ajuda para o seu caso ou se quebro as regras.
Mas acho que seria necessário atualizar o h(b) também, senão ele continua achando que aquele é o melhor caminho.
c(a,b) é o custo de ir para a vindo de b (Isso me deixou confuso durante um tempo)
No artigo ele faz uso da função auxiliar INSERT(X, Hnew) e ela faz umas verificações para acidionar corretamente as coisas.
quem entra na OPEN list é a parede, depois com com as chamadas da PROCESS-STATE a posição nova do robo acaba entrando na OPEN e o custo é propagado para o resto dos estados.
Também estou com uns problemas com o meu, para um mapa pequeno (8x8) ele rodou sem problemas... para um maior (16x16) ele vai bem, desviando bonitinho, mas uma hora ele seca a OPEN list sem achar o melhor caminho
Para que dia realmente é o EP? cada dia que entro na página da entrega tem uma data difernete :P
Eu fiz a função Insert como está no paper, mas ainda não encontrei o erro.
Quando o custo de a->b é atualizado, a célula da parede (b) é colocada na fila.
Após a execução do modify-cost, na primeira chamada do o process-state, a célula b que é selecionada (pelo menos é isso que acontece aqui).
A minha dúvida é: qual execução da função process-state deve alterar o caminho (alterar backpointers(a)) ?
Não sei se é quando 'a' , 'b' ou algum possível vizinho de 'a' é retirado da fila (faz o papel de X no pseudo código).
Se alguém puder me responder isso, eu agradeço MUITO!
obrigadas
Não sei se mudei demais o algoritmo, mas pra mim no caso de mudar o custo de A para B, eu colocaria o A na fila.
Aí a mudança do backpointer do A aconteceria na primeira execução dele, se possível. Se ele tivesse que voltar no caminho ele atualizaria o backpointer do "pai" dele e colocaria o A de volta na fila.
Bom, acho que é isso. Se falei alguma besteira, alguém corrija.
Faz sentido que o estado 'b' seja a primeira selecionada pela process-state, pois ela tem o menor K, já que seria o próximo estado do caminho ótimo, mas não sei se da para garantir isso.
Quando o estado 'b' é seleciondo pela process-state ela coloca o estado a na OPEN list através da linha L11 e L13, porém ela não muda o backpointer de 'a'. Nesse ponto h(a) = infinito , pois b(a) = b, e k(a) é k(b) + 1
(Na minha implementação eu usei c(x,y) = 1 se vizinhos e c(x,y) = inf se x é parede )
Como k(a) é quase tão baixo quanto k(b) ele tem grandes chances de ser chamado em seguida pela process-state, então o b(a) é alterado na linha L7 pois passa pelo if da linha L4 ( Kold < h(a) )
Então, respondendo a sua pergunta, b(a) é alterado quando 'a' é retirado da fila, mas pode acontecer dele ser modificado novamente, pois algum outro vizinho de a pode entrar na OPEN list.
Muito obrigada!!
Mas não vejo muito sentido em colocar o B, já que o backpointer do A que precisa ser mudado. O custo do B pro b(B) continua o mesmo, e não vai ser necessário mudar.
O único que precisará ser mudado é o A. Os outros que tem o backpointer em B não vão ter seus custos alterados, então não seria necessário mudar.
Como ele estima o custo? Percorrendo o caminho de G até X e somando?
Se for, ele não deveria fazer isso pra todos os caminhos possíveis?
Ou eu tô viajando por completo...?
Como inicialmente o robo não sabe da existência de obstáculos ele imagina o melhor dos mundos (não existem obstáculos) inicialmente o h(G,X) é a distância de norma 1 entre G e X. Conforme o algorítmo vai sendo executado ele vai aperfeiçoando o valor de h(G,X) (através da função INSERT).
A propósito, consegui resolver meu problema do robo louco...
Se alguém estiver usando a HEAP do python para a fila de prioridade das KEYs, cuidado, a função min(lista) não retorna o mesmo elemento que a função heapq.heappop(lista).
Se você quer acessar o menor elemento da heap basta acessar lista[0] :P
O tal mundo perfeito pode ter mais de um caminho, não?
Considerando que o tal custo é 0 quando é possível caminhar entre duas casas vizinhas e "prohibitively large" pros obstáculos, a menos q o robô (X) e o objetivo (G) estejam na mesma linha do labirinto vão existir alguns caminhos possíveis.
Então refaço as minhas perguntas: como escolher a qual dos caminhos possíveis se refere h(G,X). Se isso não fizer sentido, q parte do experimento eu deixei de perceber?
Obrigado!
http://en.wikipedia.org/wiki/D*_search_algorithm#Expansion
explica a parte que eu não tinha entendido.
Valeu!