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