Projecto académico - Filtro de partículas com NXT

As nossas criações: MOCs, MODs, técnicas de construção.
Responder
Ricardo T
Hero Member
Hero Member
Mensagens: 1226
Registado: 27 jul 2006, 01:37
Localização: Queluz

Projecto académico - Filtro de partículas com NXT

Mensagem por Ricardo T » 15 jun 2010, 20:13

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
Última edição por Ricardo T em 15 jun 2010, 20:17, editado 1 vez no total.
Ricardo Oliveira

Avatar do Utilizador
BionicDroid
Hero Member
Hero Member
Mensagens: 2087
Registado: 20 jun 2006, 04:39
Localização: Porto

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por BionicDroid » 15 jun 2010, 21:05

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?
Carlos Ribeiro

Ricardo T
Hero Member
Hero Member
Mensagens: 1226
Registado: 27 jul 2006, 01:37
Localização: Queluz

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por Ricardo T » 15 jun 2010, 21:26

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! :-)
Ricardo Oliveira

Avatar do Utilizador
Conchas
Direcção
Direcção
Mensagens: 15195
Registado: 26 jan 2007, 15:20
Localização: Feijó (Almada)
Contacto:

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por Conchas » 15 jun 2010, 22:39

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 é!?
FCorreia
We are working to build a better :plug:
LEGO Fan, a lifelong experience - Play Well (Leg Godt)

Oeiras :brincka: 2020    22-25.Fev

Mortymore
Hero Member
Hero Member
Mensagens: 1141
Registado: 10 nov 2008, 15:40
Contacto:

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por Mortymore » 15 jun 2010, 23:25

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

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

Abraço

Ricardo T
Hero Member
Hero Member
Mensagens: 1226
Registado: 27 jul 2006, 01:37
Localização: Queluz

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por Ricardo T » 15 jun 2010, 23:35

É 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!
Ricardo Oliveira

Mortymore
Hero Member
Hero Member
Mensagens: 1141
Registado: 10 nov 2008, 15:40
Contacto:

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por Mortymore » 15 jun 2010, 23:44

Zero!

Nunca tinha visto, mas já tive encontros imediatos com Matlab, estatísitica, entre outras coisas lindas do estilo  :whistle: 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.  ;D  ;D  ;D

Abraço

Ricardo T
Hero Member
Hero Member
Mensagens: 1226
Registado: 27 jul 2006, 01:37
Localização: Queluz

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por Ricardo T » 15 jun 2010, 23:48

[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).
Ricardo Oliveira

Ricardo T
Hero Member
Hero Member
Mensagens: 1226
Registado: 27 jul 2006, 01:37
Localização: Queluz

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por Ricardo T » 17 jun 2010, 12:12

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
Ricardo Oliveira

Avatar do Utilizador
BionicDroid
Hero Member
Hero Member
Mensagens: 2087
Registado: 20 jun 2006, 04:39
Localização: Porto

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por BionicDroid » 17 jun 2010, 20:39

[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  :fixe:
Carlos Ribeiro

Ricardo T
Hero Member
Hero Member
Mensagens: 1226
Registado: 27 jul 2006, 01:37
Localização: Queluz

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por Ricardo T » 18 jun 2010, 11:09

Claro! É a nova moda! :D

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

Abraço,
Ricardo
Ricardo Oliveira

Avatar do Utilizador
The Player Nº1
Hero Member
Hero Member
Mensagens: 893
Registado: 22 dez 2009, 18:29
Localização: Lisboa

Re: Projecto académico - Filtro de partículas com NXT

Mensagem por The Player Nº1 » 03 jul 2010, 14:58

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
Imagem

Responder