IA - Grupo 9

    A estratégia final do robot é tal que: Circular o mapa em Ss sucessivos de forma a encontrar todas as paredes e todas as ovelhas (falha apenas no caso de que um quadrado seja inacessível). Dirige-se para a primeira ovelha, calcula um caminho e empurra-a até ao curral. Caso se perca a ovelha (devido a paredes ou algo similar que impeça o robot de continuar atrás da ovelha), procura aleatoriamente nos quadrados que a circundam de forma a reencontrá-la, repetindo o processo. Dirigir-se para a outra ovelha: Se no quadrado está uma ovelha, calcula um caminho e empurra-a até ao curral. Caso se perca a ovelha (devido a paredes ou algo similar que impeça o robot de continuar atrás da ovelha), procura aleatoriamente nos quadrados que a circundam de forma a reencontrá-la, repetindo o processo. De forma semelhante, se não houver uma ovelha no quadrado (por se ter movido, por exemplo), procura aleatoriamente nos quadrados que a circundam.         Seg...

Escolha do Algoritmo      De forma a poder encontrar o seu caminho mais facilmente, foi inserido no projeto código que implementa o algoritmo A*.     A escolha do algoritmo deu-se, em parte, graças à visualização neste site , que tornou evidente que este algoritmo se adequava aos objetivos do projeto.     Uma procura na Internet rendeu várias implementações do algoritmo, sendo esta a implementação em que o grupo se baseou. Esta é notável pelas técnicas de Python desconhecidas ao grupo (como os métodos privados que a classe Node possui) que facilitam imenso a implementação do A*. Do código dado pelo site, três partes foram utilizadas: A classe Node , que representa os nós a serem utilizados no algoritmo cujo código em nada foi alterado. A função a_star_search (map,start,end) ,  que implementa a procura. Muito alterada, mas com a estrutura básica (processo lógico) mantida. A função add_to_open ( open , neighbor ) , auxiliar da procura q...

Movimento para uma dada coordenada com paredes e ovelhas no caminho      Nesta sessão continuamos o desenvolvimento da função goTo para que o robot se movimentasse para uma dada casa evitando paredes e ovelhas guardando também a localização das mesmas para que depois da fase de recolha de informação fosse possível acelerar o movimento do robot evitando a necessidade de verificar se existe uma parede antes de cada movimento.     Foi desenvolvida a função localizar que recolhe a informação relativa às paredes numa fase inicial do jogo e direciona o robot para a casa de partida. Mais tarde esta informação será usada para escolher o melhor caminho a seguir para ganhar o jogo.     Esta solução, utilizando o goTo , levou a imensos imprevistos, pelo que o grupo decidiu abandonar esta função goTo , em favor de um algoritmo abordado na aula: A*. A função foi, no entanto, reformulada para goToAdj , que apenas serve para que o robot se direcione para u...

    A hierarquia dos ficheiros utilizados no projeto pode ser resumida do seguinte modo:     Como já mencionado anteriormente, brick.py importa as ferramentas do EV3 Brick utilizado e é, por sua vez, importado por extra.py , action.py e movement.py .     O primeiro destes, extra.py , importa também a livraria random e as variáveis de jogo contidas em movement.py .     O ficheiro movement.py importa a livraria copy , assim como a função spot () definida em action.py .     Estes três ficheiros que importam brick.py em seu turno são utilizados por strategy.py , onde está contido o código de estratégia.     Finalmente, main.py importa apenas strategy.py e consiste apenas numa chamada da função play () que inicia o jogo.       Esta hierarquia pode ser visualizada no seguinte diagrama:     Retângulos simples são ficheiros criados pelo grupo, duplos livrarias utilizadas...

Movimento para uma dada coordenada      Nesta sessão foi desenvolvida uma função que leva o robot a uma casa do tabuleiro. Após testes (sem obstáculos), o bom funcionamento da função foi confirmado e passou-se então à formulação de ideias para  que sejam tidos em conta eventuais paredes ou ovelhas que bloqueiem o caminho.

Aprofundando os sentidos do robot      Um dos "problemas" antes tidos consistia na redundância de verificações de paredes, i.e., enquanto não encontrava as seis paredes o robot continuaria a verificar paredes a não ser que soubesse que há uma parede. Isto significava que o robot verificava até as casas em que já havia passado.     Para resolver isto, foi criado um array parelelo ao das paredes que grava os movimento válidos. Isto reduziu imenso o tempo gasto no movimento do robot e agilizou a aquisição de informação do tabuleiro.     Caso sejam encontradas todas as paredes, o array deverá ser apagado (tendo em conta que, sem ser as ovelhas, que são móveis, e o curral, que é constante, nada senão as paredes deverá impedir o movimento do robot).   Aperfeiçoando o movimento     Uma pequena particularidade foi notada no movimento do robot: os motores não resistiam a movimento que lhes fosse aplicado. Isto quer dizer que, ao m...

Uma nova estratégia      Antes de qualquer estratégia mais complexa ser implementada, será útil mapear todo o tabuleiro. Para este efeito, foi escrito código que permita ao robot percorrer todo o tabuleiro com os objetivos de encontrar todas as seis paredes e as duas ovelhas, voltando de seguida à casa inicial.      O âmbito por de trás de tal código assenta na utilidade que esta informação terá, independentemente de qualquer tipo de estratégia que seja concebida eventualmente.   A dicionalmente...     Além de hipotecar novos modos de jogo, o grupo afinou o movimento do robot, nomeadamente a maneira como vira e deteta margens. No que toca à heurística, foi proposto que fosse implementada uma forma de guardar as casas entre onde não há paredes de forma a acelerar o seu movimento durante o mapeamento inicial do tabuleiro. Em teoria, não é difícil: apenas será necessário criar um array paralelo ao das paredes que funcionará da mesma maneira...

Considerações iniciais      Antes do adiamento do prazo final, o docente da UC apontou que a estratégia levada a cabo pelo grupo era demasiado simples: falharia em muitos casos e naqueles em que não falhava imediatamente poderia entrar em ciclos infinitos.      Com isto em conta, descartámos dita estratégia com a salvaguarda de mais duas semanas para conceber uma que obtivesse resultados mais satisfatórios. Reorganização do código      Com isto em mente, o código foi reformulado: Python não é a melhor linguagem para se recorrer ao uso de classes, o uso recorrente da palavra "self" e a falta de encapsulamento ou polimorfismo são motivos notáveis.      Para começar, foram eliminadas as classes. Métodos como "move" ou "spot" (para movimento e deteção) agora não precisam de ser chamados recorrendo a uma instância da classe "dog", que previamente os contia.      No entanto, de modo a poder ser organizado o código, fo...

Heurística   Tabuleiro           Tendo como referência que o robot começa no canto inferior esquerdo e o curral se localiza no canto superior direito, o pastor começa virado para a direita. Internamente, a classe que o representa, em Python, possui três atributos: localização (a sua coordenada), frente (a coordenada à sua frente) e direção (o seu sentido).   Paredes            O código desenvolvido permite guardar a localização das paredes. Para poder localizar todas as paredes, a cada movimento o robot verifica a existência de uma parede para o local onde se pretende movimentar. Caso todas as paredes tenham sido encontradas, esta verificação deixa de ser feita. As paredes são guardadas na classe do tabuleiro, tal que este possui método para adicionar paredes. As paredes são representadas como um par de coordenadas.     Estratégia       Primeiramente, o grupo focou-se numa estratégia...

Segundo o enunciado, estas são as regras a seguir:   Regras para o robot Os movimentos são: ←↑→↓. Não estão permitidos ↖↗↘↙. O robot apenas pode-se mover entre 0 a 2 casas de cada vez Começa no cacifo inferior esquerdo. Não sabe onde estão as paredes até as encontrar . Tem que detectar se uma ovelha se encontra num cacifo adjacente ao dele antes de efectuar o movimento (←↑→↓). As paredes não evitam que o robot detete uma ovelha. O robot não pode andar para uma casa em que alguma ovelha está presente. O robot não pode atravessar as paredes. O robot não pode entrar no curral. O robot pode tocar ou gritar por uma parede. Regras para as ovelhas As ovelhas não podem atravessar paredes. Se a ovelha for empurrada para uma parede, esta move-se no sentido horário.   Após a ovelha entrar no curral já não pode sair . Se o robot tocar na ovelha, esta move-se duas casas.   Se o robot gritar para a ovelha, esta move-se uma casa.   As ovelhas não podem cair no curral quando se ...

     Para esta primeira entrega, o robot tem apenas que seguir os requisitos mais essenciais: isto é, rodar e movimentar-se pelo mapa ao obedecer aos limites, não atravessando paredes nem atropelando ovelhas. Para este efeito, o código, escrito em Python, guarda a informação do tabuleiro (localização das ovelhas e do cão pastor) e o robot alterna entre tocar e berrar, isto enquanto roda num sentido aleatória de cada vez que atinge um quadrado para o qual não se pode mover. Abaixo, um vídeo com uma breve demonstração. https://drive.google.com/file/d/13dU43Tn2wxeqE8WDszCIpsISseGpWzZ2/view?usp=sharing  

De modo a avaliar os melhores sensores a utilizar, testámos um a um os disponibilizados pelo kit. O sensor de distância mostrou ser o mais fiável, com os resultados mais consistentes de entre todos os outro https://drive.google.com/file/d/11WHEqzovhIwQGSQ-5NOcdluUglNTvX7q/view?usp=sharing https://drive.google.com/file/d/11cYo99VfxhpJg_FsNY3MNKbr-E8NyASg/view?usp=sharing https://drive.google.com/file/d/11MYJCYQmzJ5w7-o6IrhnVObj6cERsD8S/view?usp=sharing Por outro lado, o sensor de cor revelou-se imprevisível, dependente de tal forma da luminosidade que o seu uso levaria a um gasto de tempo de modo a apenas garantir a sua fiabilidade. https://drive.google.com/file/d/11_5LW6Oc8YojnS5LYkWf-p67vwieocMm/view?usp=sharing   Finalmente, o sensor de toque é relativamente simples e, de tal modo, facilmente integrável no modelo do robot. https://drive.google.com/file/d/1kDhpEsyaCU5wWth6y4zyHv1kNRB7USlK/view?usp=sharing https://drive.google.com/file/d/12H-fgyDu6_pK9WcalNaVNgC9TTInEaD3/view?u...

     Para avaliar que modelo de robot a utilizar, verificámos a documentação do Ev3 no site da Lego. Depois de rapidamente avaliar entre os recomendados, acabámos por testar dois modelos diferentes:      O primeiro modelo é vantajoso devido à sua leveza e simplicidade, mas isto torna-o difícil de modificar, além de que usar apenas um motor o deixa incapaz de rodar.   https://drive.google.com/file/d/10qGpZ0-MRrgxCJ2OhMOUaoZjjTVQ24G0/view?usp=sharing      O segundo modelo porém, mesmo que mais complexo e pesado, não possui estes problemas: por ser maior, é possível adicionar quaisquer próteses que desejemos, além de que lhe é possível rodar sobre si mesmo com facilidade graças ao dois motores que o impulsionam. https://drive.google.com/file/d/10mxFkFaif-hZrzE_KkEGS2_QQaVAwH3e/view?usp=sharing      Tendo tudo isto em conta, foi escolhido o segundo modelo.

      No âmbito da unidade curricular de Inteligência Artificial, foi-nos proposto pelo professor Eduardo Fermé a realização de um trabalho prático que visa pôr em prática os conhecimentos da área.     Este projeto consiste na programação de um robot para que este possa concluir com sucesso um jogo fornecido pelo docente da UC.     Fazem parte deste grupo os alunos que se seguem: Diogo Oliveira Gouveia, n.º 2042818 Paulo Tomás Caires Teles n.º 2087018 Diogo Ornelas, n.º 2101618 Francisco Silva, n.º 2042518 Alberto Ornelas, n.º 2044818       Este blog foi então criado com a finalidade de permitir o acompanhamento do desenvolvimento do projeto pelo professor, servindo, portanto, de ferramenta de avaliação do trabalho realizado para a UC de Inteligência Artificial.     Pode ser consultado aqui o enunciado.