Navegação Topológica para Futebol Robótico Gonçalo Neto [email protected] Trabalho Final de Curso 627/2001/L Hugo Costelha [email protected] Fevereiro

Navegação Topológica para Futebol Robótico

Gonçalo [email protected]

Trabalho Final de Curso627/2001/L

Hugo [email protected]

Fevereiro de 2003

Licenciatura em Engenharia Electrotécnica e de Computadores

2 Gonçalo Neto e Hugo Costelha, 2003

Sumário

MOTIVAÇÃO Mapa Topológico Localização e Navegação Resultados Finais Conclusões e Trabalho Futuro


Motivação

Navegação métrica Necessita de um modelo geométrico do mundo. Pressupõe uma exactidão na informação dos sensores. Permite uma navegação mais precisa.

Navegação topológica Permite uma especificação qualitativa dos objectivos de navegação. Utiliza um mapa adaptável e de fácil definição. Não se adequa a aplicações de grande precisão.

Solução ideal Conciliar ambos os modelos de navegação.

Métrica: navegação local, mais precisa. Topológica: navegação global, mais abrangente.


Sumário

Motivação

MAPA TOPOLÓGICO Localização e Navegação Resultados Finais Conclusões e Trabalho Futuro


xy

12

3

4

5

6 7

8

xy

12

3

4

5

6 7

8

Posturas de Treino


Análise de Componentes Principais

Extracção de imagens principais

vectores próprios da matriz de covariância das imagens de treino:

R = X XT

Representação comprimida das imagens.

Desprezam-se as componentes de menor importância - menores valores próprios.

x2

x1


Redução de Recursos Necessários

Decomposição de R muito dispendiosa! No entanto… Os valores próprios (diferentes de zero) de R = X XT são

iguais aos de A = XT X. Os vectores próprios de R podem ser obtidos dos de A e das

imagens de treino (centradas na origem).

vR = (A)-½ X vA

Ainda é necessário armazenar todas as imagens de treino. Mas…

Apenas são necessários os vectores próprios de R mais significativos.

Pode utilizar-se um procedimento iterativo no seu cálculo.


Erro Quadrático de Reconstrução

Conjunto de Treino

Conjunto de Teste

Número de Valores Próprios

Err

o Q

uadr

átic

o M

édio

(P

erce

ntag

em)

10

20

30

40

50

60

70

80

90

00 10 20 30

40

50

60

Conjunto de TesteConjunto de Treino

Próprios Valoresos Todos

osConsiderad não Próprios ValoresTr

Próprios Valoresos Todos

Quadrático ErroTe

av


Construção do Mapa Topológico

O mapa deve ser útil à aplicação em questão.

Pode ser representado como um grafo direccionado em que:

Nós: correspondem aos locais do mapa. Transições: forma de viajar entre locais do mapa.

No futebol robótico, poder-se-á ter: Nós: zonas do campo (meio campo, grandes áreas). Transições: movimentos elementares (virar à esquerda, ir

em frente).


FYG

NYGR

NYGL

NOG3

FBG

NOG4NOG2NOG1

NBGR

NBGL

mfgr

mfgrDescrição do Mapa Topológico

rr: rodar à direita. rl: rodar à esquerda. mfgr: seguir em frente, com baliza do

lado direito. mfgl: seguir em frente, com baliza do

lado esquerdo. mb: seguir para trás.

FYG

NYGR

NYGL

rr rl

mfgr

NOG3

FBG

NOG4NOG2NOG1

NBGR

NBGLmfgl

mfgr

rl rr

rlrr

rlrr

rl

rl

rr

rr

rl rr

rr rl rl rr

rrrl

mb

mb

mb

mfgl

mb

mb

mb

mfgr

mfgl

mfgr

mfgl

NBGL: baliza azul, perto e à esquerda.

NBGR: baliza azul, perto e à direita. FBG: baliza azul, longe. NYGL: baliza amarela, perto e à

esquerda. NYGR: ver a baliza amarela, perto e à

direita. FYG: baliza amarela, longe. NOG: sem baliza.


Sumário

Motivação Mapa Topológico

LOCALIZAÇÃO E NAVEGAÇÃO Resultados Finais Conclusões e Trabalho Futuro


Localização no Mapa

Passo essencial para uma boa navegação (topológica ou métrica).

No caso topológico, equivale a identificar o nó do grafo em que o robot se encontra.

Pode ser formulada como um problema de classificação.

Projecção da imagem a classificar no espaço principal. Comparação com as projecções das imagens de treino. Utilização do método dos k-vizinhos mais próximos para

localizar o robot num nó/classe. Podem ser utilizadas várias métricas.


Localização: Imagens Simuladas

X e variável

Y = 1.1 (m)

0

180

360

-5 0 5

x

NBGLNBGRFBGNYGLNYGRFYGNOG

x

y


Localização: Imagens Reais

X, Y e variáveis

NBGLNBGRFBGNYGLNYGRFYGNOG

x

y-4 4-1-3 31-2 20

1

-1

-2

2

0


Geração de Caminhos

Utilização de algoritmos de procura, aplicados ao grafo. Grafos Grandes:

definir uma heurística. utilizar A*.

Grafos Pequenos (caso do futebol robótico): procura simples, pelo que não será muito vantajoso o uso de

uma heurística. reduzir A* a procura de custo uniforme ou procura em

largura.


Seguimento de Caminhos

Idealmente, corresponderia à execução sequencial das transições que definem o caminho gerado.

Contudo…

Ambiente muito dinâmico e sujeito a alterações bruscas. Algumas transições apresentam percentagens de falha

superiores a 50%.

É necessário um mecanismo de detecção de falhas e geração de novos caminhos.


Sumário

Motivação Mapa Topológico Localização e Navegação

RESULTADOS FINAIS Conclusões e Trabalho Futuro


Resultados Finais

Vídeo 1 As regiões de fronteira

entre os nós situam-se na zona do meio campo.

Vídeo 2 As regiões de fronteira

entre os nós situam-se na zona entre o meio campo e a grande área.




Sumário

Motivação Mapa Topológico Localização e Navegação Resultados Finais

CONCLUSÕES E TRABALHO FUTURO


Conclusões

Apresenta resultados promissores na navegação entre locais do mapa.

Permite uma aprendizagem expedita das características relevantes do mundo, adaptando-se facilmente a diferentes ambientes.

Demonstra flexibilidade face a diferentes mapas topológicos.

Possibilita a utilização de linguagens qualitativas de especificação de objectivos.

Pressupõe a utilização de mecanismos de controlo de falhas.


Trabalho Futuro

RoboCup Challenge 4 – Play with an arbitrary FIFA ball

É apresentada uma bola ao robot durante 60 segundos. O robot deverá procurar a bola no campo e marcar golo. O teste é feito com 3 bolas diferentes.

Solução: Análise de Componentes Principais para guardar informação

a priori acerca da bola. Navegação Topológica para conduzir o robot à bola. Comportamentos implementados na arquitectura actual do

projecto SocRob para condução da bola até à baliza.


Obrigado pela vossa atenção!!!

Gonçalo [email protected]

Hugo [email protected]

http://b52.ist.utl.pt/costelha/socrob/index.htm



Anexos


Simulador da Câmara

Permite: Acelerar o processo de desenvolvimento. Tornar o desenvolvimento flexível e independente dos robots. Obter resultados de um modo bastante rápido.

Implementado em VRML (Virtual Reality Modelling Language). Independente da plataforma (Linux vs Windows©). Interacção com Matlab© e JAVA™. Possibilidade de variação das condições do ambiente e uso de

texturas.


Imagens: Reais vs Simuladas

Imagem simulada Imagem real


___________


Modelo de Discretização

Tipo de discretização: Uniforme:

Mais flexível. Não necessita de conhecimento a priori. Permite a definição de vários mapas topológicos.

Não uniforme: Mais precisa. Orientada a uma aplicação específica.

Compromisso no número de imagens: Reduzido: pode não representar o campo correctamente. Elevado: pode tornar-se computacionalmente impraticável.

No caso actual: Discretização Uniforme. Intervalos de Discretização: x=1m ; y=1m ; =45º


___________


Associação das Imagens aos Nós

Feita com base em características geométricas, definidas pelos próprios nós.

Utiliza a grelha de discretização já mencionada.

Permite, assim: Variação do local do mapa associado a cada nó (variando

as imagens). Definição de vários mapas, utilizando a mesma grelha de

discretização.


Associação das Imagens aos Nós

FYG

NYGR

NYGL

rr rl

mfgr

NOG3

FBG

NOG4NOG2NOG1

NBGR

NBGLmfgl

mfgr

rl rr

rlrr

rlrr

rl

rl

rr

rr

rl rr

rr rl rl rr

rrrl

mb

mb

mb

mfgl

mb

mb

mb

mfgr

mfgl

mfgr

mfgl


__________


Comparação de Parametrizações

K Métrica Tempo Médio de Classificação (s)

1 Euclidiana 0.129

1 Ponderada 0.153

5 Euclidiana 0.141

5 Ponderada 0.169

10 Euclidiana 0.160

10 Ponderada 0.183


__________


Percentagem de Falhas

Documents

Navegação Topológica para Futebol Robótico Gonçalo Neto [email protected] Trabalho Final de Curso 627/2001/L Hugo Costelha [email protected] Fevereiro