Controle para Futebol de Robôs
Utilizando Processamento Paralelo
Seminário de Andamento
Mestrando Gabriel G. Detoni
Orientador Prof. Dante Barone
Agenda
•
•
•
•
•
•
Visão Geral
Motivação
Trabalho Desenvolvido
Trabalhos Relacionados
Situação e Resultados
Cronograma
2
Agenda
•
•
•
•
•
•
Visão Geral
Motivação
Trabalho Desenvolvido
Trabalhos Relacionados
Situação e Resultados
Cronograma
3
Contexto
• Robocup
– Small Size League (SSL)
• Processamento paralelo
– Tipos de paralelismo de tarefas: temporal e
espacial
– Modelos de programação: troca de mensagens e
variáveis compartilhadas
4
Agenda
•
•
•
•
•
•
Visão Geral
Motivação
Trabalho Desenvolvido
Trabalhos Relacionados
Situação e Resultados
Cronograma
5
Motivação
• Importância do processamento paralelo na
atualidade.
• Evoluções no futebol de robôs.
• Complexidade da modelagem de sistemas
orientados ao processamento paralelo.
6
Agenda
•
•
•
•
•
Visão Geral
Motivação
Trabalho Desenvolvido
Situação e Resultados
Cronograma
7
Trabalho Desenvolvido
• Utilizar processamento paralelo como uma
forma para habilitar melhorias de
desempenho
• Estabelecer um modelo de programação
eficiente e com suporte a diferentes escalas
• Desenvolver um sistema de controle eficaz
– Validar a hipótese e trazê-la ao mundo de futebol
de robôs
8
Programação voltada ao paralelismo
• Problemas de software paralelos
– Comunicação entre threads (sincronização)
• Troca de mensagens
• Variáveis compartilhadas
– Gargalos de pipeline
• Evitado balanceando-se o processamento de cada
tarefa
– Escalabilidade
9
Modelagem do Sistema de Controle
• Como obter paralelismo evitando ao máximo
os problemas da execução assíncrona?
– Dividindo o sistema em tarefas independentes
– Quando há dependência, balanceando-se as
tarefas para evitar gargalos
– Utilizando um mecanismo de comunicação
eficiente
– Utilizando um modelo de programação escalável
10
Modelagem do Sistema de Controle
• Divisão de tarefas inspirada em campeões da
Robocup 1
1
KRIENGWATTANAKUL, A. Plasma-z 2008 Team Description Paper. Robocup, 2008.
11
Modelagem do Sistema de Controle
• Favorável ao Paralelismo Temporal (pipeline)
– Divisão em níveis balanceados, dependentes uns
dos outros
12
Modelagem do Sistema de Controle
• Favorável ao Paralelismo Temporal (pipeline)
– Divisão em níveis balanceados, dependentes uns
dos outros
13
Modelagem do Sistema de Controle
• Paralelismo Espacial
– Divisão de cada nível em tarefas paralelizáveis
com pouca interdependência
• Jogadas executadas por grupos de jogadores distintos
• Movimentos executados por jogadores individualmente
• Monitoramento do estado do jogo
14
Modelo EC
• Extensão do modelo de programação baseado
em troca de mensagens ou coordenação
• Inspirado em modelos biológicos
– Processamento paralelo distribuído2
– Redes neurais
• Entidades Conexionistas (EC)
• Mensagens são também chamadas estímulos.
2
MCCLELLAND, J. L.; RUMELHART, D. E.; HINTON, G. E. The Parallel Distributed Processing Perspective
15
Modelo EC
• Diagrama de duas entidade e suas conexões
W corresponde à influencia que uma conexão possui no estado de ativação
da entidade.
16
Modelo EC: características da
comunicação
• Blocking Receive
– Executa apenas se houver dados para processar.
• Non-blocking Send
– Envia dados produzidos e continua o processamento das
entradas.
• Garantia de ordem
• Quanto a fairness
– Todas as mensagens enviadas podem ser recebidas porém
para garantir balanceamento da execução das tarefas, o
buffer de entrada é limitado, de forma que mensagens
antigas podem ser descartadas para dar lugar às novas.
17
Modelo EC: rotina de comunicação
• Modelo de dados utiliza tipos complexos.
Mensagem
String: Tipo
Object<Stimulus>: Dados
• Mensagens são enviadas para todos os
receptores vinculados ao transmissor.
• Cada receptor opta por aceitar ou rejeitar uma
mensagem com base em seu tipo (W).
18
Sistema de controle EC
• Algoritmos de execução:
19
Sistema de controle EC
• Topologia de uma Jogada:
20
Plano de Testes
• Speedup e Eficiência do modelo EC
– Execução em computadores com múltiplas CPUs
variando a afinidade do processo.
– Teste em uma maquina com SMT (Hyperthreading)
• Testes funcionais do sistema de controle
baseado em EC
– Validar autonomia do sistema e a eficácia da
execução das jogadas desenvolvidas
21
Agenda
•
•
•
•
•
•
Visão Geral
Motivação
Trabalho Desenvolvido
Trabalhos Relacionados
Situação e Resultados
Cronograma
22
Trabalhos Relacionados
• KITANO, H.; HENDLER, J. (Eds.). Massivelly
Parallel Artificial Intelligence. [S.l.]: AAAI
Press, 1994.
– Conecta o desempenho das maquinas paralelas
disponíveis atualmente e as oportunidades disto
para a Inteligência Artificial concluindo que o
desempenho só é obtido se o sistema for pensado
desde seu projeto para ser executado de forma
paralela.
23
Trabalhos Relacionados
• GUNDOJU, V.; MINOURA, T. Distributed
Observable/Observer: A Distributed RealTime Object-Communication Mechanism.
The First IEEE International Symposium on
Object-Oriented Real-Time Distributed
Computing. 1998. p. 358.
– Propõe um framework com características em
comum com as propostas no modelo EC.
24
Trabalhos Relacionados
• MCCLELLAND, J. L.; RUMELHART, D. E.;
HINTON, G. E. The Parallel Distributed
Processing Perspective. 1983.
– Apresenta um modelo lógico generalizado de um
sistema inteligente com várias semelhanças com a
estrutura que foi desenvolvida para o sistema de
controle de futebol de robôs em questão.
25
Trabalhos Relacionados
• KIELMANN, THILO. Objective Linda: A
Coordination Model for Object-Oriented
Parallel Programming. 1997
– Propõe a implementação do modelo LINDA
orientado a objetos sendo. Um framework que
utiliza um mecanismo implícito de troca de
mensagens.
26
Agenda
•
•
•
•
•
•
Visão Geral
Motivação
Trabalho Desenvolvido
Trabalhos Relacionados
Situação e Resultados
Cronograma
27
Situação e Resultados
• Testes em uma aplicação simplificada
28
Resultados
• Tempo de execução
29
Resultados
• Speedup e eficiência
30
Trabalhos Futuros
• Utilização do modelo EC com topologia
dinâmica e adaptativa.
– Aprendizado
– Técnicas de redes neurais artificiais
• Aplicação do sistema de controle ao time de
robôs da UFRGS.
31
Agenda
•
•
•
•
•
Visão Geral
Motivação
Trabalho Desenvolvido
Situação e Resultados
Cronograma
32
Cronograma
2009
Ação
3 4 5 6 7 8 9
2010
10
11
12
1 2 3 4 5 6
Revisão bibliográfica sobre o estado da arte
em futebol de robôs.
Revisão bibliográfica sobre o padrões
técnicos recomendados para processamento
paralelo de informações.
Desenvolvimento de um simulador de
futebol de robôs.
Planejamento de uma arquitetura e sua
subseqüente aplicação no desenvolvimento
de um time de futebol de robôs.
Coleta de resultados
Reuniões Periódicas com o Prof. Orientador
Seminário de Andamento
Redação e revisão da dissertação
Entregar a dissertação
Defender a dissertação
33
Cronograma
2009
Ação
3 4 5 6 7 8 9
2010
10
11
12
1 2 3 4 5 6
Revisão bibliográfica sobre o estado da arte
em futebol de robôs.
Revisão bibliográfica sobre o padrões
técnicos recomendados para processamento
paralelo de informações.
Desenvolvimento de um simulador de
futebol de robôs.
Planejamento de uma arquitetura e sua
subseqüente aplicação no desenvolvimento
de um time de futebol de robôs.
Coleta de resultados
Reuniões Periódicas com o Prof. Orientador
Seminário de Andamento
Redação e revisão da dissertação
Entregar a dissertação
Defender a dissertação
34
Perguntas e Respostas
35