PLUG

Boa tarde a todos,

Aqui fica um projecto que desenvolvi para uma cadeira. Aliei os conhecimentos que adquiri e o nosso querido LEGO para implementar o chamado MCL - Monte Carlo Localization. É um exemplo da aplicação de um filtro de partículas.

Basicamente, este projecto envolve demonstrar um algoritmo existente para a localização de robôs móveis. O robô conjuga a informação fornecida aos motores, que executam o movimento do mesmo, e a informação dos sensores que observam o "mundo exterior" reforçando assim a estimativa da sua posição.

Neste caso o robô usa um sensor de ultra-sons e uma bússola que retorna o ângulo de 0 a 359º.

Para quem quiser perceber um pouco melhor do que se trata:
- http://pt.wikipedia.org/wiki/M%C3%A9todo_de_Monte_Carlo - Método de Monte Carlo, utilizado em muitos problemas de estatística.
- http://en.wikipedia.org/wiki/Monte_Carlo_localization - O algoritmo em si (inglês)

O vídeo:


Um agradecimento especial ao Conchas que, mais uma vez, me facultou peças precisas, os sensores da HiTechnic. :-)

Deu-me bastante gozo conciliar o hobby ao dever! :-)

Espero que gostem!


Abraço,
Ricardo Oliveira

Projecto interessante Ricardo, uma pergunta, os quadrados negros do layout da aplicação são desenhados por ti de forma a se enquadrarem com o espaço físico, certo? ou é a aplicação que determina essa área através da leitura de áreas percorridas previamente?

O mapa é conhecido pelo robô. Tive de o introduzir no programa. Ele apenas estima a posição dentro do mapa.

Existem depois outras técnicas para reconhecimento do ambiente envolvente. Este algoritmo apenas trata da localização! :-)

Bem, não me parece nada fácil de perceber só com as leituras da Wikipedia...

Afinal o que são aquelas bolinhas azuis todas e como aparecem?

Pelo que vejo fizeram também uma aplicação para o PC. O robot comunica por BT, não é!?

Suponho que cada ponto azul seja a localização provável de uma partícula, e a zona que aglomerar mais pontos azuis será zona onde com maior probabilidade se encontrará a partícula que procuramos, assinalada pela tal bola que oscila entre verde e vermelho no Matlab, e que deverá coincidir com a posição real do robot no cenário, se os calculos estiverem a correr bem.
O tracinho que se vê na tal bolinha que oscila entre verde e vermelho, deverá pretender indicar o sentido de orientação do robot.
Deduzo também que a oscilação entre verde e vermelho da bolinha que representa o robot no PC, possa estar relacionado com algum grau de probabilidade ou com alguma validação.

Gostaria realmente que o Grande Mestre explicasse melhor isto, como se eu até nem fosse muito burro. 

Parabéns pelo excelente trabalho e pela criatividade ao envolver LEGO e a aproveitar as suas potencialidades para umas "brincadeiras" sérias.     

Abraço

É exactamente isso tudo o que disseste! :-)

As partículas a azul representam probabilidades da posição do robô (x, y e orientação teta - o tal tracinho).

A combinação espacial delas e o peso de cada uma define a distribuição de probabilidade do estado (posição) do robô.
O peso é atribuido em função da observação dos sensores.

Com base nestas distribuição discretizada, assume-se uma posição. Essa posição é a bola grande a vermelho ou a verde. Ficará verde, quando o factor de certeza (que está indicado no canto inferior direito da aplicação do MATLAB) subir acima de 0.06 (estipulado por mim, por observação). Este valor é o inverso da variância da distância destas partículas à média.

Esta média é uma média pesada, conciliando a posição das partículas e o seu peso.

Assumo que já viste isto em algum lado, ou não?

Abraço!

Zero!

Nunca tinha visto, mas já tive encontros imediatos com Matlab, estatísitica, entre outras coisas lindas do estilo  que me permitiram deduzir o que disse, fosse lá qual fosse a probabilidade de Poisson (a probabilidade dos casos raros, para quem não sabe) de eu poder estar certo.
É que um louco nunca tem vergonha de expor o que lhe passa pela cabeça.     

Abraço

[quote="Conchas"]
Bem, não me parece nada fácil de perceber só com as leituras da Wikipedia...

Afinal o que são aquelas bolinhas azuis todas e como aparecem?

Pelo que vejo fizeram também uma aplicação para o PC. O robot comunica por BT, não é!?
[/quote]

A ideia do algoritmo é discretizar uma distribuição de probabilidade apenas nos pontos em que essa probabilidade é mais alta, uma vez que representar "por completo" a distribuição seria muito pesado computacionalmente.


Sim! Utilizei o MATLAB para a interface gráfica e para processar o algoritmo. O NXT através dos tacometros dos motores, vai actualizando a posição do robô no seu referêncial local. De tempos a tempos, o MATLAB pede essa informação ao NXT por bluetooth e actualiza no referêncial de cada particula, a posição global.

Nesse instante, é feito um "reset" a posição no referencial local do robô.

Este é o primeiro passo do algorítmo, a predicção. Num segundo passo, a informação dos sensores é recolhida e confrontada com cada partícula. A crença em cada partícula depende então destas medidas, atribuindo-lhes um peso.

No fim do algoritmo determinamos a posição conforme nos convir melhor.
As partículas com maior peso sobrevivem, desaparecendo as de menor peso. Criam-se novas partículas para substituir as que morreram, no lugar das mais fortes (são replicadas, portanto).

Aqui fica o relatório, em Português, do projecto! :-)

http://dl.dropbox.com/u/2616967/MCL%20- ... 0Final.pdf

Se alguém tiver curiosidade, força nisso.

Abraço,
Ricardo

[quote="Ricardo T"]
Aqui fica o relatório, em Português, do projecto! :-)
http://dl.dropbox.com/u/2616967/MCL%20- ... 0Final.pdf
Se alguém tiver curiosidade, força nisso.
Abraço,
Ricardo
[/quote]
Heheheh, tambem uso Dropbox 

Claro! É a nova moda!

Tava nomeado para o programa do ano, o ano passado acho eu.

Abraço,
Ricardo

Grande projecto!
Já vi que também és do IST. Eu sou do pólo do tagus.
Grande trabalho que tiveste. Muitos parabéns.
Cumps