XIP

Ciber 2009

2009-04-08T16:20:00.002Z

Com algumas mudanças interessantes nas regras, foi anunciado o ciber-rato 2009! Vamos participar mas ainda não é claro se eu ou o Francisco podemos estar presentes. Veremos...

Rescaldo da prova

2008-04-10T10:06:00.002Z

Como não tive hipótese de ir à prova, enviei o código para a organização e participei à distância. Pelo que vi pela seca2tv (o que não foi muito) a competição correu bastante bem mas depois do que se passou o ano passado só podia melhorar :) Acabámos por ficar em segundo lugar, o que não é mau tendo em conta o esforço. Parabéns ao El Raton!

Para dizer a verdade, estava à espera de um comportamento um pouco mais regular do XIP... Aparentemente o tempo de prova baixou para 40ms (o que eu não estava à espera) e quando ele chega ao farol calcula um conjunto de caminhos que o tornam mais pesado: ex: da partida aos vários farois + do agente ao farol mais próximo da partida. Os 40ms acabam por não chegar e o xip encarna a personagem da Dory no Finding Nemo.

Vou tentar colocar o binário online brevemente.

De volta ao trabalho

2008-03-27T11:34:00.003Z

Voltei a pegar no código para participar este ano. Comecei por correr umas provas no servidor de 2006, o último que funciona. Não se está a portar muito mal mas descobri um (pequeno) bug na detecção do farol. Nada de extraordinário mas não tive tempo de corrigir.

Ao menos consegui configurar o ambiente e ver umas provazitas. Começa a ser apertado ter isto pronto mas espero que nos próximos dias consiga dar um "avanço" sem ter de fazer uma noitada no último dia.

O objectivo de hoje é alterar a biblioteca de comunicação e a leitura dos sensores para funcionar com o novo modelo sem que isso atafulhe o estado do mundo com lixo. Vamos ver....

Algoritmos de pesquisa de caminhos

2007-12-27T03:46:00.000Z

Existe a possibilidade de descoberta de 3 tipos de caminhos para determinado local.

Caminho mais curto apenas por posições conhecidas
Caminho mais curto
Caminho relativamente curto tentando explorar posições não conhecidas do labirinto

É utilizado o algoritmo A* com a heurística de distância euclidiana e com funções de distancia pesadas entre a distancia percorrida no labirinto, o risco de colisão, o conhecimento da posição, e a rotação necessária.
A implementação deste algoritmo é particularmente eficiente já que a memória dos possíveis nós na arvore de pesquisas está previamente alocada e indexada por posição no labirinto. Foi ainda desenvolvida uma implementação de uma priority queue que, em conjunto com a indexação por posição, utiliza particularidades do funcionamento do algoritmo A* para ter uma maior performance.

Após o cálculo do caminho, é calculada uma optimização sobre o mesmo utilizando o algoritmo de Besenham para procurar segmentos que possam ser melhorados. Isto corrige o facto de o A* ser calculado numa matriz discreta e apenas permitir caminhos múltiplos de 45º.

Decisão de alto-nível

2007-12-27T03:29:00.000Z

O comportamento de alto nível do agente está codificado na máquina de estados descrita na seguinte figura:

(1) Início da prova
(2) Conhece a localização de um farol
(3) Visitou o farol mas existem faróis por visitar
(4) Visitou todos os faróis
(5) Chegou à partida de forma eficiente ; Chegou à partida e não tem tempo de voltar a um farol ; Acabou o tempo de prova
(6) Conhece bem o caminho da posição de partida até ao farol e não o está a fazer de forma eficiente ; Não tem tempo extra para além de ir ao farol e voltar à partida pelo caminho que conhece.
(7) Chegou a um farol ; Não tem tempo de chegar a um farol

O agente começa por procurar farois através da estratégia explicada anteriormente. Caso já conheça um ou mais farois, passa a dirigir-se para o farol conhecido mais próximo precorrendo zonas do mapa que por vezes desconhece. Após ter visitado cada farol dirige-se para o seguinte farol mais próximo e caso não conheça mais nenhum volta para o estado de procura de farois.
Quando todos os farois foram visitados, o agente dirige-se à partida, explorando o caminho.
Caso tenha sido eficiente acende o sinal de fim e dá como terminada a sua prova. Caso não tenha sido eficiente volta a um farol e tenta novamente percorrer o caminho final por sitios conhecidos já que a eficiência com que se percorre este caminho é a parcela mais importante para a pontuação final.
Todos estes passos são condicionados pelo tempo de prova e por isso o algoritmo pondera o passo a dar conforme o tempo disponível para o final.

Os conceitos utilizados no algoritmo são os seguintes:

Conhecimento de um caminho é a razão entre o tempo previsto que o caminho demora a ser percorrido por locais desconhecidos e por locais conhecidos.

Eficiência é a razão entre o tempo óptimo de percorrer um caminho e aquele que o agente realmente demora.

Por vezes, devido a limitações no tempo de processamento, não é possível calcular em todos os ciclos esta informação. Assim, a informação é calculada incrementalmente, e estimativas são usadas desde a última medição exacta.

Existe ainda uma camada de correcção de erros sobre o estado do agente, fazendo com que, no caso de existirem falhas que provoquem a não aplicação de acções e que estas sejam importantes para a alterações de estado, o algoritmo volte ao estado correcto.

Código do conversor de logs para SWF

2007-03-25T19:16:00.000Z

Código está diponível aqui. Precisa de: python, libming, python-ming.

Para executar: python log2swf.py -l logfilename.log

Mais logs em SWF

2007-03-24T01:11:00.000Z

Não mexo mais, fica assim. Podem ver alguns exemplos aqui. Amanhã um post com o link para o código.

Logs em SWF

2007-03-22T14:37:00.000Z

Estou a fazer um conversor de logs para SWF. Podem ver um exemplo aqui.

A mão à palmatória

2007-03-21T16:17:00.000Z

É no que dá falar antes do tempo. Afinal o tempo de ciclo não vai baixar mas sim continuar dentro do mesmo intervalo (50-80ms). Isto vai reduzir bastante a lista de modificações a fazer ao Xip... :) Outra modificação é que as duas primeiras mangas vão ser repetidas 3 vezes; a final pelos vistos não. Acho que tem bastante lógica porque um azar poderia impedir a passagem à final. Talvez tivesse (ainda) mais lógica os pontos das duas melhores provas serem somados (e também fazer o mesmo na final...).

Pode ser que seja este ano que vamos finalmente fazer algumas coisas que têm estado em lista de espera e não temos tido tempo para fazer...

Entre elas:

Utilizar a diferença de posição do estado do labirinto ao longo do tempo para corrigir a posição (Parte do crédito desta ideia vai para o Nuno Lau numa conversa no jantar do micro-rato 2005).
Aproveitar a informação das provas (pelo menos a posição do farol) para o restante da manga (Crédito para o Artur Pereira que fez um pensamento em voz alta no final do concurso do ano passado).

E certamente não entre elas:

As aplicações dos sensores no estado interno do xip serem transaccionais. Deste modo é possível utilizar a informação para reconstruir o estado do mundo com dados mais exactos.
Refazer o código em python.

Detecção de situações de risco de colisão

2007-03-21T14:10:00.000Z

Uma vez que foi tomada a decisão do uso de um estado interno do agente bastante estático existe o risco de variações no labirinto não serem detectadas. O facto da representação do labirinto não ser volátil pode causar alguns problemas quando o erro de posição é elevado ou quando um rato aparece numa posição previamente marcada como espaço aberto (mas tem a vantagem de permitir a correcção de erros e a detecção de objectos móveis no labirinto).

Para evitar que estas variações não afectem o comportamento do agente, especialmente com colisões, foi acrescentado um modo reflexivo para quando as leituras actuais dos sensores contrariam as decisões tomadas pelo alto nível do agente.

Para este modo reflexivo foram usada regras que codificam o conhecimento humano e para isto foi utilizada lógica difusa. A inferência das regras é feita utilizando lógica de Mamdani.

As seguintes regras são utilizadas:

power(power_left,power_right)
SE parede_próxima(sensor_centro_esquerda) ENTÃO power(-0.05,-0.05)
SE parede próxima(sensor_centro_direita) ENTÃO power(-0.05,-0.05)
SE movimento_para__lado(sensor_esquera) E muito(parede_próxima(sensor_esquerda)) ENTÃO power(power_left,-power_right)
SE movimento_para__lado(sensor_direita) E muito(parede_próxima(sensor_direita)) ENTÃO power(-power_left,power_right)

Definições:

muito(X)=verdade(X)²
movimento_para_lado(X)=função_em_rampa(0.0,0.04)
parede_próxima(X)=função_em_rampa(0.2,0.4)

Um bom exemplo do funcionamento deste modo é a manga 2 de 2006 onde é possível ver as colisões que podem acontecer pelo erro de posicionamento e também como o modo reflexivo funciona bem quando existe um rato a bloquear o caminho. Outro bom exemplo é a manga 1 do mesmo ano em que passamos uma tangente ao YAM.

Modo de procura de farois

2007-03-20T17:52:00.000Z

Este é um daqueles casos em que temos uma estratégia simples e que funciona bastante bem.

O mapa é também representado por uma grelha, neste caso com uma granularidade bastante elevada (2 unidades de labirinto). Cada posição da grelha pode estar classificada como inatingível (Informação retornada pelo algoritmo de pesquisa de caminhos) ou com a probabilidade de ter sido verificado se o farol lá se encontra (uma enumeração com meia duzia de valores). Caso o agente esteja a "olhar" na direcção de uma posição da grelha, dependendo da distância a que desta se encontra, a posição é marcada com o grau adequado de probabilidade de conhecimento da área.

O Xip dirige-se à area sobre a qual tem menor conhecimento e que não tenha sido marcada como inatingível. A distância a se encontra da área do mapa é utilizada como factor de desempate. É simples e funciona bastante bem. Vejam o log da manga 3 de 2006.

Representação do labirinto

2007-03-20T11:12:00.000Z

Como temos alguns textos escritos sobre a abordagem do Xip aos diversos problemas, vamos tentar partilhar esse conhecimento aqui no blog.

O labirinto é representado de forma discreta numa matriz. Esta matriz, com a definição de 0.1 unidades de labirinto, inclui um valor probabilístico da existência de parede assim como o número de amostras da posição. A probabilidade de, de acordo com uma leitura do sensor, existir parede num dado ponto da matriz é calculada usando uma distribuição normal com o desvio padrão do erro do sensor.

Estes cálculos são aplicados a cada ciclo, para cada sensor. Esta computação é bastante pesada e por isso foram feitas algumas optimizações. Antes de a simulação começar, são calculadas e guardadas numa matriz as probabilidades de existência de parede, tendo como origem do referêncial a posição do agente. As probabilidades são calculadas para cada cada valor possível do sensor assim como para cada orientação do agente evitando processamento durante o valioso e limitado tempo de ciclo. Outra optimização que evita percorrer posições da matriz sobre as quais os sensores não têm informação, é copiar os resultados que contêm leituras relevantes para uma lista, evitando deste modo verificar se a informação é válida (e poupar memória).

Para melhorar a qualidade da representação do labirinto são utilizadas técnicas de processamento de imagem. Existe uma melhoria clara quando são utilizadas estas técnicas, tal com é visivel na figura.

Para o processamento de imagem são usadas operações morfológicas de dilatação e erosão. Na dilatação uma posição da matriz que tenha um vizinho que contenha parede também fica com parede. Na erosão, todas as posições da matriz que não estejam completamente rodeadas por parede são assinaladas como não tendo parede. Após aplicar uma sequência destas operações, a representação dos obstáculos fica muito regular.

A operação de erosão é também utilizada para, no caso de o Xip pensar que está rodeado por obstáculos, transformar em zonas desconhecidas as paredes com marcação menos intensa.

Comentários às regras do ciber 2007

2007-03-19T15:59:00.000Z

Este ano as regras do ciber levaram uma volta (ainda não estão publicadas no site mas vão ser baseadas no Ciber-RTSS). De certo modo está mais interessante mas por outro lado vai ser mais difícil para as equipas novas começarem. Adaptar o Xip também não vai ser brincadeira nenhuma! O código é bastante pesado e por isso vamos ter que passar o cálculo de caminhos para uma thread independente. Mesmo assim é possível que as operações necessárias a todos os ciclos sejam lentas; nesse caso vamos ter que cortar na "inteligência" (processamento de imagem, etc).

Resumo das alterações:

Tempo de ciclo mais breve (20ms?)
Beacon e Compass com latência (9 ciclos?)
Dos 7 sensores (4 de parede + ground + compass + beacon) apenas alguns estão disponíveis por ciclo (2?)

Filme do XIP

2007-03-19T15:35:00.000Z

Um filme do XIP a resolver o labirinto da final de 2006 pode ser encontrado aqui!

Binário de 2006 divulgado

2007-03-19T15:34:00.001Z

Binário do XIP2006 foi divulgado e está disponível aqui!

XIP vence Ciber-Rato 2006

2007-03-19T15:33:00.001Z

XIP fica em 1º lugar no Ciber-Rato 2006 e ganha o prémio Acelera.
Mais informação na página da competição.

Editor de labirintos suporta as regras de 2006

2007-03-19T15:31:00.000Z

O editor de labirintos suporta agora as regras de 2006.
Binário e código-fonte disponíveis aqui e aqui respectivamente.

XIP é 4º classificado no Ciber-Rato 2005

2007-03-19T15:27:00.001Z

XIP fica em 4º lugar no Ciber-Rato 2005.
Mais informação na página da competição.

Agora com weblog

2007-03-19T15:15:00.000Z

Agora temos um blog com as novidades e ideias do Xip!