IA - Grupo 9

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...