Smart Shep3rd (2)

Concluimos que a função capaz de conduzir as ovelhas ao curral tem o seguinte funcionamento:

É de funcionamento recursivo sendo que na analise das barreiras, caso não esteja numa situação de vitória toma em conta dois movimentos em frente, ou seja as barreiras a uma e a duas casas de distância, conhecidas já na função de reconhecimento.

Com base nas barreiras adjacentes toma então a decisão com base num conjunto de possíveis movimentos.

De modo ao robô não entrar num loop infinito foi definido que caso não haja um conjunto de passos adequado ou caso sejam alcançados 100 passos o processo de procura do caminho termina, devolvendo um indicador de insucesso.

Antes de iniciar o seu movimento, o robô analisa as 4 posições em redor de cada ovelha escolhendo para cada ovelha a melhor posição inicial para conduzi-la. Com base no número de passos para levar cada ovelha e levada primeiro a que serão necessários menos passos e por fim a que serão necessários mais passos.

Um dos casos de insucesso encontrado foi o seguinte:

Chegou-se à conclusão durante a apresentação que a resolução deste caso passava pelo recurso à aleatoriedade da ovelha até uma posição conveniente.

Encontrou-se também um caso em que as ovelhas conseguiam entrar no curral apenas num sentido (contra ponteiros do relógio):

Semelhante a este caso há um que só permite a entrada das ovelhas no sentido do ponteiro do relógio.

Na última fase as principais alterações foram então o planeamento do caminho para condução das ovelhas no momento inicial e a correção do andamento do robô que por vezes era feito com 4 movimentos quando só podia dar 2. Foram também analisadas com mais atenção as situações em que seria preferencial gritar, elaborando-se esquemas das principais:

Como exemplo de funcionamento do robô tomou-se o seguinte exemplo:

Pesquisa Cega - Demos

Para que o robô tenha conhecimento do território do jogo de modo a ganhar há a necessidade de se fazer um estudo ao pavimento de jogo.

Para a pesquisa cega não se teve em conta nenhum algoritmo de pesquisa na integra abordado nas aulas teóricas.

O objetivo do robô nesta fase é tentar pesquisar todos os cacifos de uma linha, tenho em conta o eixo horizontal.

De modo a registar todos os casos mais complexos que se pode encontrar, ao nível da disposição das barreiras, fez-se algumas gravações ainda na fase de correções de código (por isso tem-se uma ovelha a não ser vista, mas como se vê no vídeo anterior isso já está 100% funcional).

Smart Shep3rd

Junção da função go_to com a codificação de um possível caminho, levando a ovelha da sua posição até ao curral através do toque.

De forma a levar as ovelhas até ao curral, baseado na posição primeiramente suposta como ideal para o robô, é preenchido um array (de capacidade máxima de 100 passos) com os movimentos ideais (gritar, tocar, andar para a frente, virar à direita, virar à esquerda e andar para trás).

Foram definidas como prioridades quando ao posicionamento do robô sempre que possível posicionar-se por baixo da ovelha, em seguida à sua esquerda, depois à direita e por fim em cima. Tomou-se como prioritário o toque em vez do grito de modo a minimizar a interação com outras ovelhas, tendo que anteceder os movimentos por dois passos.

Demo GoTo

Abordada uma nova metodologia tem-se aqui o funcionamento da função GoTo, cujo objetivo é encaminhar o robô até a ovelha colocando-o numa posição favorável.

POSIÇÃO INICIAL: (0,5)
POSIÇÃO OBJETIVO: (5,1)

v2 (melhor qualidade):

Função para levar as ovelhas

Foi considerado que a melhor maneira de dirigir as ovelhas até ao curral seria analisar jogada a jogada reagindo perante o ambiente. De acordo com a posição do robô (já ao pé da ovelha) é pensado para onde se deslocará a ovelha sendo que o robô a segue da forma mais pertinente.

Função goTo - Metodologia

Parte/Função integrante do projeto. Tem apenas uma premissa: a função é chamada com as coordenadas desejadas e o robô dirige-se para tal coordenada, respeitando as regras do jogo. Segue um esquema com uma possível configuração e respetivas respostas.

Pesquisa Cega - Metodologia

Após falhar as duas iniciais soluções para a pesquisa cega, na seguinte imagem exemplifica-se a nova metodologia que se pretende abordar.

Última fase de entrega

DATA DE TRABALHO: 13 de Janeiro de 2016 até 18 de Janeiro de 2016

Inicialmente consideramos que o estudo completo ao pavimento, memorizando onde estão as barreiras e as ovelhas, seria uma abordagem ineficiente, no entanto, numa nova abordagem ao problema notamos que não seria possível o robô pensar racionalmente se não conhecia os futuros obstáculos que ao encaminhar a ovelha esta podia encontrar.

Como primeira abordagem decidimos que trataríamos os quadrados do pavimento como nós de uma árvore e de acordo com esta árvore decidimos de entre os algoritmos de pesquisa abordados na aula que faria a pesquisa da melhor forma.

1ª SOLUÇÃO: Busca em profundidade

Esta solução demonstrou várias limitações então descartamos.

2ª SOLUÇÃO: Busca em largura

Esta solução garantia que todos os nós fossem visitados, no entanto, passá-la para linhas de código em que dependendo da posição e direção os movimentos e a pesquisa aos nós filhos eram diferentes. Quando se implementou esta solução a abordagem não foi realmente a prevista e no fundo a pesquisa cega não tinha em conta a busca em largura mas sim a busca em profundidade com iterações.

Devido ao extenso código os erros tornaram-se quase impossíveis de se corrigir, mas conseguiu-se fazer com que percorresse funcionalmente até a iteração 4.

CONCLUSÃO: Nenhuma das soluções revelou-se eficiente pois deixava nós filhos por pesquisar.

ESTRATEGIA DE TRANSPORTE DAS OVELHAS ATÉ AO CURRAL:

A estratégia optada foi localizar a ovelha compreender se na posição da ovelha tem-se barreiras e de acordo com isso definir a melhor posição para "berrar" para a ovelha. Encaminhar o robô até esta posição e a partir daqui leva-la até as extremidades da matriz que contêm o curral e a partir daí leva-la até ao curral.

RESULTADOS OBTIDOS:

A solução da pesquisa cega não foi implementada de modo a se conseguir todos os níveis sem limitações ou pelo menos com o mínimo de limitações. A estrategia de transporte das ovelhas até ao curral possui algumas limitações como atropelo de ovelhas; caso berre para uma ovelha e nos arredores tenha-se uma ovelha o jogo dá-se como perdido; entre outras que poderiam surgir em outras fases de testes.

Bem agora resta definir uma solução para o estudo do terreno ótima e mais simples de converter em código. Melhorar todas as limitações inerentes a estratégia de jogo no que toca a levar as ovelhas para o curral.