( PDF ) Comportamento social cooperativo na realização de tarefas em ambientes dinâmicos e competitivos

Download PDF

ads:

MINIST

ERIO DA DEFESA

ERCITO BRASILEIRO

SECRETARIA DE CI

ENCIA E TECNOLOGIA

INSTITUTO MILITAR DE ENGENHARIA

CURSO DE MESTRADO EM SISTEMAS E COMPUTAC¸

ALEXANDRE TADEU ROSSINI DA SILVA

COMPORTAMENTO SOCIAL COOPERATIVO NA REALIZAC¸

DE TAREFAS EM AMBIENTES DIN

AMICOS E COMPETITIVOS

Rio de Janeiro

2006

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

INSTITUTO MILITAR DE ENGENHARIA

ALEXANDRE TADEU ROSSINI DA SILVA

COMPORTAMENTO SOCIAL COOPERATIVO NA REALIZAC¸

AO DE

TAREFAS EM AMBIENTES DIN

AMICOS E COMPETITIVOS

Disserta¸c˜ao de Mestrado apresentada ao Curso de

Mestrado em Sistemas e Computa¸c˜ao do Instituto Mili-

tar de Engenharia, como requisito parcial para obten¸c˜ao

do t´ıtulo de Mestre em Sistemas e Computa¸c˜ao.

Orientador: Prof. Paulo Fernando Ferreira Rosa -

Ph.D.

Rio de Janeiro

2006

ads:

c2006

INSTITUTO MILITAR DE ENGENHARIA

Pra¸ca General Tib´urcio, 80-Praia Vermelha

Rio de Janeiro-RJ CEP 22290-270

Este exemplar ´e de propriedade do Instituto Militar de Engenharia, que poder´a inclu´ı-

lo em base de dados, armazenar em computador, microﬁlmar ou adotar qualquer forma

de arquivamento.

E permitida a men¸c˜ao, reprodu¸c˜ao parcial ou integral e a transmiss˜ao entre bibliotecas

deste trabalho, sem modiﬁca¸c˜ao de seu texto, em qualquer meio que esteja ou venha a

ser ﬁxado, para pesquisa acadˆemica, coment´arios e cita¸c˜oes, desde que sem ﬁnalidade

comercial e que seja feita a referˆencia bibliogr´aﬁca completa.

Os conceitos expressos neste trabalho s˜ao de responsabilidade do autor e do orientador.

S568 Silva, Alexandre Tadeu Rossini da

Comportamento Social Cooperativo na Realiza¸c˜ao

de Tarefas em Ambientes Dinˆamicos e Competitivos/

Alexandre Tadeu Rossini da Silva.

– Rio de Janeiro: Instituto Militar de Engenharia, 2006.

172 p.: il., tab.

Disserta¸c˜ao (mestrado) – Instituto Militar de Enge-

nharia – Rio de Janeiro, 2006.

1. Robˆos m´oveis autˆonomos. 2. Robˆos co operativos. I.

T´ıtulo. II. Instituto Militar de Engenharia.

CDD 629.892

INSTITUTO MILITAR DE ENGENHARIA

ALEXANDRE TADEU ROSSINI DA SILVA

COMPORTAMENTO SOCIAL COOPERATIVO NA REALIZAC¸

AO DE

TAREFAS EM AMBIENTES DIN

AMICOS E COMPETITIVOS

Disserta¸c˜ao de Mestrado apresentada ao Curso de Mestrado em Sistemas e Com-

puta¸c˜ao do Instituto Militar de Engenharia, como requisito parcial para obten¸c˜ao do

t´ıtulo de Mestre em Sistemas e Computa¸c˜ao.

Orientador: Prof. Paulo Fernando Ferreira Rosa - Ph.D.

Aprovada em 22 de fevereiro de 2006 pela seguinte Banca Examinadora:

Prof. Paulo Fernando Ferreira Rosa - Ph.D. do IME - Presidente

Prof. Rafael Duarte Coelho dos Santos - Ph.D. do INPE

Prof. Ronaldo Ribeiro Goldschmidt - D.Sc. do IME

Rio de Janeiro

2006

Aos meus pais, Jos´e Gerci e Elisabete.

A minha namorada, Fabiana.

Ao meu irm˜ao, Leonardo.

AGRADECIMENTOS

”A noite abre as ﬂores em segredo e deixa que o

dia receba os agradecimentos.” (Tagore)

Agrade¸co a todas as pessoas que me incentivaram, apoiaram e possibilitaram esta

oportunidade de dar asas `a imagina¸c˜ao e tornar real o mundo de fantasias inspirado na

maior enciclop´edia j´a feita, a pr´opria Terra. Em especial:

Ao meu orientador, Dr. Paulo Fernando Ferreira Rosa, pelo tempo e dedica¸c˜ao gastos

durante as v´arias reuni˜oes realizadas ao longo do desenvolvimento do trabalho, al´em de

acreditar e conﬁar nos caminhos que o nortearam at´e sua conclus˜ao.

Ao meu pai, Jos´e Gerci da Silva, que me socorreu `a medida em que as d´uvidas da

nossa p´atria l´ıngua iam surgindo durante o per´ıodo de gesta¸c˜ao da disserta¸c˜ao.

Aos amigos de curso: Cap. Carlos Alberto Padilha PINHEIRO, Carlos Andr´e Batista

de Carvalho, Cap. Fernando APOLIN

ARIO Pereira, F´abio Silveira Vidal, F´abio Suim

Chagas, Fabr´ıcio Nogueira da Silva, Marco Antonio Firmino de Sousa, Rafael Lima de

Carvalho e Vitor Guerra Rolla.

Ao TC Edison ISHIKAWA por me disponibilizar livre acesso ao LaSiD (Laborat´orio

de Sistemas Distribu´ıdos), fundamental para a ﬁnaliza¸c˜ao do trabalho.

Aos alunos de gradua¸c˜ao do IME: Fernando Martins, Fernando Rocha, Guilherme

Schirmer e Leonardo Louren¸co.

Aos demais colegas do mestrado, que em proveitosas conversas t´ecnicas contribu´ıram

direta ou indiretamente no trabalho.

A todos os mestres e alguns funcion´arios do Departamento de Engenharia de Sistemas

(SE/8) do IME.

Por ﬁm, `a Capes (Coordena¸c˜ao de Aperfei¸coamente de Pessoal de N´ıvel Superior) por

ﬁnanciar parcialmente este trabalho, o tornando vi´avel.

Alexandre Tadeu Rossini da Silva

”Muitos pensam que a pesquisa cient´ıﬁca ´e uma

atividade puramente racional, na qual o objetivismo

l´ogico ´e o ´unico mecanismo capaz de gerar conhe-

cimento. Como resultado, os cientistas s˜ao vistos

como insens´ıveis e limitados, um grupo de pessoas

que corrompe a beleza da Natureza ao analis´a-la ma-

tematicamente. Essa generaliza¸c˜ao, como a maioria

das generaliza¸c˜oes, me parece profundamente injusta,

j´a que ela n˜ao incorpora a motiva¸c˜ao mais impor-

tante do cientista, o seu fasc´ınio pela Natureza e seus

mist´erios. Que outro motivo justiﬁcaria a dedica¸c˜ao

de toda uma vida ao estudo dos fenˆomenos naturais,

sen˜ao uma profunda venera¸c˜ao pela sua beleza? A

ciˆencia vai muito al´em da sua mera pr´atica. Por tr´as

das f´ormulas complicadas, das tabelas de dados ex-

perimentais e da linguagem t´ecnica, encontra-se uma

pessoa tentando transcender as barreiras imediatas

da vida di´aria, guiada por um insaci´avel desejo de

adquirir um n´ıvel mais profundo de conhecimento e

de realiza¸c˜ao pr´opria. Sob esse prisma, o processo

criativo cient´ıﬁco n˜ao ´e assim t˜ao diferente do pro-

cesso criativo das artes, isto ´e, um ve´ıculo de auto-

descoberta que se manifesta ao tentarmos capturar a

nossa essˆencia e lugar no Universo.”

MARCELO GLEISER

SUM

ARIO

LISTA DE ILUSTRAC¸

OES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

LISTA DE TABELAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

LISTA DE ABREVIATURAS E S

IMBOLOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1 INTRODUC¸

AO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.1 Motiva¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.2 Coment´arios Preliminares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3 Organiza¸c˜ao da Disserta¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 REVIS

AO DE LITERATURA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.1 Ve´ıculos Autˆonomos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2 Vis˜ao Computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.3 Coopera¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.4 Teoria dos Jogos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.5 Planejamento de Trajet´orias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.5.1 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.5.2 Decomposi¸c˜ao em c´elulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.5.3 Campo Potencial Artiﬁcial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3 DESCRIC¸

AO DO PROBLEMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.1 Coopera¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2 Tomada de Decis˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.3 Teoria dos Jogos (TJ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.3.1 Tipos de Jogos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.4 Futebol de Robˆos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.4.1 A Federa¸c˜ao RoboCup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.4.2 RoboCup Small Size (f-180) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4 SOLUC¸

AO PROPOSTA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.1 Arquitetura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.2 Aquisi¸c˜ao de Imagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.3 Vis˜ao Computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.3.1 Calibra¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.3.2 Classiﬁca¸c˜ao das Cores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.3.3 Pose dos Objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4.3.4 Identiﬁca¸c˜ao dos Objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.3.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.4 Planejamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

4.4.1 Previs˜ao de Movimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

4.4.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.4.2.1 Objetivo Global . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.4.2.2 Objetivo Local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

4.5 Execu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

4.5.1 Planejamento de Trajet´oria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

4.5.2 Controle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

4.6 Comunica¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.7 Simulador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

5 IMPLEMENTAC¸

AO COMPUTACIONAL . . . . . . . . . . . . . . . . . . . . . . . 112

5.1 Vis˜ao Computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

5.2 Simulador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

6 TESTES E RESULTADOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6.1 Vis˜ao Computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6.2 Simulador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

7 CONSIDERAC¸

OES FINAIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

7.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

8 REFER

ENCIAS BIBLIOGR

AFICAS . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

9 ANEXOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

9.1 ANEXO 1: Regras da RoboCup Small Size League (f-180) . . . . . . . . . . . . . . . . 142

9.2 ANEXO 2: Data Sheet do transmissor RF Keymark TXC1 . . . . . . . . . . . . . . . 168

9.3 ANEXO 3: Data Sheet do receptor RF Keymark RXD1 . . . . . . . . . . . . . . . . . . 171

LISTA DE ILUSTRAC¸

OES

FIG.2.1 Classiﬁca¸c˜ao de ve´ıculos autˆonomos (CAMPION ET. AL., 1996). . . . . . . 23

FIG.2.2 Distribui¸c˜ao de rodas omnidirecionais em robˆos holonˆomicos (ASH-

MORE AND BARNES, 2002). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

FIG.2.3 Rodas omnidirecionais da equipe Cornell Big Red 2002 (esquerda)

e 2003 (direita) (PURWIN AND D’ANDREA, 2003). . . . . . . . . . . . . . . . 24

FIG.2.4 Robˆo da equipe Wingers da Universidade de Buﬀalo na categoria

RoboCup f-180 (UB ROBOTICS, 2006). . . . . . . . . . . . . . . . . . . . . . . . . . . 25

FIG.2.5 Passos fundamentais em processamento de imagens digitais, adap-

tado de (GONZALEZ, 1992). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

FIG.2.6 Exemplos comuns de superf´ıcie na RoboCup f-180, adaptado de

(BRUCE AND VELOSO, 2003). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

FIG.2.7 Compara¸c˜ao do erro posicional e angular de diferentes modelos

(BRUCE AND VELOSO, 2003). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

FIG.2.8 Grafo de visibilidade (LATOMBE, 1991). . . . . . . . . . . . . . . . . . . . . . . . . . . 31

FIG.2.9 Diagrama de Voronoi (LATOMBE, 1991). . . . . . . . . . . . . . . . . . . . . . . . . . . 31

FIG.2.10 Espa¸co livre decomposto de forma exata em um conjunto de c´elulas

poligonais (LATOMBE, 1991). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

FIG.2.11 Decomposi¸c˜ao aproximada em c´elulas (OTTONI E LAGES, 2003). . . . . 33

FIG.2.12 Exemplo de planejamento de trajet´oria utilizando campo potencial

artiﬁcial (PACHECO E COSTA, 2002). . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

FIG.3.1 Dilema dos prisioneiros na forma normal . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

FIG.3.2 Dilema dos prisioneiros na forma estendida . . . . . . . . . . . . . . . . . . . . . . . . . 43

FIG.3.3 RoboCup Simulation League 3D (ROBOCUP, 2006) . . . . . . . . . . . . . . . . . 47

FIG.3.4 RoboCup Small Size Robot League (f-180) (CMU, 2005) . . . . . . . . . . . . . 47

FIG.3.5 RoboCup Middle Size Robot League (f-2000) (CMU, 2005) . . . . . . . . . . . 48

FIG.3.6 RoboCup Four-Legged Robot League . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

FIG.3.7 RoboCup Humanoid League . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

FIG.3.8 Campo de jogo da RoboCup f-180 (ROBOCUP, 2005a). . . . . . . . . . . . . . . 51

FIG.3.9 Dimens˜oes em mil´ımetros do campo de jogo da RoboCup f-180

(ROBOCUP, 2005a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

FIG.4.1 Arquitetura do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

FIG.4.2 Saltos no movimento de um robˆo com diferentes taxas de aquisi¸c˜ao

de imagens (GOMEZ, 2004). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

FIG.4.3 Micro-cˆamera CMOS usada nos experimentos. . . . . . . . . . . . . . . . . . . . . . . 57

FIG.4.4 Modelo n˜ao-linear de um neurˆonio artiﬁcial (HAYKIN, 2001). . . . . . . . . . 58

FIG.4.5 Cubo RGB, adaptado de (SJU, 2005). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

FIG.4.6 Rede neural RBF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

FIG.4.7 Rede neural RBF adaptada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

FIG.4.8 Cone HSV, (NEVES ET. AL., 2004). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

FIG.4.9 Algoritmo de convers˜ao de RGB para HSV. . . . . . . . . . . . . . . . . . . . . . . . . . 62

FIG.4.10 Algoritmo de classiﬁca¸c˜ao por HSV. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

FIG.4.11 Arquitetura de uma rede MLP t´ıpica com uma camada intermedi´aria.

FIG.4.12 Particionamento dos dados de entrada realizado por uma rede RBF

com quatro neurˆonios na camada intermedi´aria (BRAGA ET. AL.,

2000). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

FIG.4.13 Particionamento dos dados de entrada realizado por uma rede MLP

com uma camada intermedi´aria formada por trˆes neurˆonios (BRAGA

ET. AL., 2000). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

FIG.4.14 Algoritmo de classiﬁca¸c˜ao RGB das cores de orienta¸c˜ao. . . . . . . . . . . . . . . 66

FIG.4.15 M´ascara. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

FIG.4.16 Varredura com i pixels no eixo x e j pixels no eixo y. . . . . . . . . . . . . . . . . 68

FIG.4.17 Transforma¸c˜ao em objeto retangular. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

FIG.4.18 Centr´oide da circunferˆencia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

FIG.4.19 Algoritmo do centr´oide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

FIG.4.20 Identiﬁca¸c˜ao dos robˆos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

FIG.4.21 Previs˜ao de posi¸c˜ao futura para a bola. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

FIG.4.22 Previs˜ao de posi¸c˜ao futura para um robˆo advers´ario. . . . . . . . . . . . . . . . . . 76

FIG.4.23 Algoritmo para determinar a estrat´egia global . . . . . . . . . . . . . . . . . . . . . . . 83

FIG.4.24 Supondo que o campo de defesa ´e o lado esquerdo, as ´areas de

atua¸c˜oes das posi¸c˜oes dos jogadores em campo, real¸cada na cor

cinza, s˜ao apresentadas: (a) goleiro; (b) ﬁxo; (c) ala esquerdo; (d)

ala direito; (e) pivˆo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

FIG.4.25 Posi¸c˜oes dos jogadores em campo: (a) goleiro; (b) ﬁxo; (c) ala

esquerdo; (d) ala direito; (e) pivˆo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

FIG.4.26 Algoritmo da a¸c˜ao chutar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

FIG.4.27 Algoritmo da a¸c˜ao caminhar ao gol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

FIG.4.28 Algoritmo da a¸c˜ao interceptar advers´ario. . . . . . . . . . . . . . . . . . . . . . . . . . . 93

FIG.4.29 Algoritmo da a¸c˜ao apoiar ataque. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

FIG.4.30 Algoritmo da a¸c˜ao dar combate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

FIG.4.31 Algoritmo da a¸c˜ao marcar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

FIG.4.32 Algoritmo da a¸c˜ao reposicionar goleiro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

FIG.4.33 Algoritmo da a¸c˜ao reposicionar ﬁxo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

FIG.4.34 Algoritmo da a¸c˜ao reposicionar ala direito. . . . . . . . . . . . . . . . . . . . . . . . . . 96

FIG.4.35 Algoritmo da a¸c˜ao reposicionar ala esquerdo. . . . . . . . . . . . . . . . . . . . . . . . 97

FIG.4.36 Algoritmo da a¸c˜ao reposicionar pivˆo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

FIG.4.37 Hierarquia de coopera¸c˜ao m´axima quando o pivˆo ´e o l´ıder. . . . . . . . . . . . . 99

FIG.4.38 Hierarquia de coopera¸c˜ao m´axima quando o ala direito ´e o l´ıder. . . . . . . 99

FIG.4.39 Hierarquia de coopera¸c˜ao m´axima quando o ala esquerdo ´e o l´ıder. . . . . . 100

FIG.4.40 Hierarquia de coopera¸c˜ao m´axima quando o ﬁxo ´e o l´ıder. . . . . . . . . . . . . 100

FIG.4.41 Exemplo de coopera¸c˜ao ofensiva entre os robˆos da equipe amarela

tendo como l´ıder o ala esquerdo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

FIG.4.42 Hierarquia de coopera¸c˜ao para o exemplo da FIG. 4.41. . . . . . . . . . . . . . . 104

FIG.4.43 Exemplo de coopera¸c˜ao defensiva entre os robˆos da equipe amarela

tendo como l´ıder o ala direito. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

FIG.4.44 Hierarquia de coopera¸c˜ao para o exemplo da FIG. 4.43. . . . . . . . . . . . . . . 104

FIG.4.45 Exemplo de estrat´egia escolhida, com maior recompensa, para co-

opera¸c˜ao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

FIG.4.46 Campo potencial (LATOMBE, 1991) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

FIG.4.47 Transmissor RF Keymark TXC1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

FIG.4.48 Receptor RF Keymark RXD1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

FIG.4.49 Especiﬁca¸c˜oes dos pinos do Transmissor RF Keymark TXC1, adap-

tado de (KEYMARK, 2006a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

FIG.4.50 Especiﬁca¸c˜oes dos pinos do Receptor RF Keymark RXD1, adap-

tado de (KEYMARK, 2006b). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

FIG.5.1 Compara¸c˜ao entre os tempos de execu¸c˜ao do m´etodo do Gradiente

Conjugado (SCHEPKE E CHAR

AO, 2004). . . . . . . . . . . . . . . . . . . . . . . . 113

FIG.5.2 Programa implementado da vis˜ao computacional. . . . . . . . . . . . . . . . . . . . 115

FIG.5.3 Simulador implementado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

FIG.6.1 Fotograﬁa do laborat´orio com o suporte de cˆamera e lˆampadas mon-

tado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

FIG.6.2 Regi˜oes com diferen¸ca de luminosidade utilizadas na calibra¸c˜ao. . . . . . . . 119

FIG.6.3 Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a equipe

amarela, caso 1; onde: (a) ´e a imagem original, (b) imagem proces-

sada e (c) a sobreposi¸c˜ao de (b) em (a) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

FIG.6.4 Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a equipe

amarela, caso 2; onde: (a) ´e a imagem original, (b) imagem proces-

sada e (c) a sobreposi¸c˜ao de (b) em (a) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

FIG.6.5 Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a bola,

caso 1; onde: (a) ´e a imagem original, (b) imagem processada e

FIG.6.6 Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a bola,

caso 2; onde: (a) ´e a imagem original, (b) imagem processada e

FIG.6.7 Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a equipe

azul, caso 1; onde: (a) ´e a imagem original, (b) imagem processada

e (c) a sobreposi¸c˜ao de (b) em (a) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

FIG.6.8 Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a equipe

azul, caso 2; onde: (a) ´e a imagem original, (b) imagem processada

e (c) a sobreposi¸c˜ao de (b) em (a) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

FIG.6.9 Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a equipe

azul, caso 3; onde: (a) ´e a imagem original, (b) imagem processada

e (c) a sobreposi¸c˜ao de (b) em (a) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

FIG.6.10 Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao RBF para a equipe

azul; onde: (a) ´e a imagem original, (b) imagem processada e (c)

o que o algoritmo de identiﬁca¸c˜ao classiﬁca. . . . . . . . . . . . . . . . . . . . . . . . 124

FIG.6.11 Classiﬁca¸c˜ao errada ocasionada pelo m´etodo centr´oide, caso 1; onde:

(a) ´e a imagem original, (b) imagem processada e (c) o que o al-

goritmo de orienta¸c˜ao classiﬁca. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

FIG.6.12 Classiﬁca¸c˜ao errada ocasionada pelo m´etodo centr´oide, caso 2; onde:

(a) ´e a imagem original, (b) imagem processada e (c) o que o al-

goritmo de identiﬁca¸c˜ao classiﬁca. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

FIG.6.13 Amostra utilizada para se determinar o tempo de processamento

de cada jun¸c˜ao de m´etodos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

FIG.6.14 Compara¸c˜ao do tempo de processamento, em milissegundos, dos

m´etodos utilizados nos testes de vis˜ao computacional. . . . . . . . . . . . . . . . 127

FIG.6.15 Exemplo de problema de m´ınimo local do campo potencial artiﬁcial. . . . 129

LISTA DE TABELAS

TAB.3.1 Compara¸c˜ao entre xadrez e futebol de robˆos (ROBOCUP, 2005c) . . . . . . 45

TAB.4.1 Padr˜oes de cores em RGB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

TAB.4.2 Padr˜oes de cores em HSV. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

TAB.4.3 Recompensas do jogo quando a Sociedade A est´a no estado COM

BOLA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

TAB.4.4 Recompensas do jogo quando a So ciedade A est´a no estado SEM

BOLA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

TAB.6.1 Resultados dos testes de identiﬁca¸c˜ao utilizando os m´etodos HSV

e RBF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

TAB.6.2 Resultados dos testes de orienta¸c˜ao utilizando o m´etodo HSV na

identiﬁca¸c˜ao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

TAB.6.3 Resultados dos testes de orienta¸c˜ao utilizando o m´etodo RBF na

identiﬁca¸c˜ao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

LISTA DE ABREVIATURAS E S

IMBOLOS

ABREVIATURAS

CCD - Charge Coupled Device

CMOS - Complementary Metal Oxide Semiconductor

FPS - Frames per second

IA - Inteligˆencia Artiﬁcial

IAD - Inteligˆencia Artiﬁcial Distribu´ıda

MLP - Multilayer Perceptron

RBF - Radial Basis Function

RI - Rob´otica Inteligente

RNA - Rede Neural Artiﬁcial

SMA - Sistemas Multiagentes

STR - Sistema de Tempo Real

TJ - Teoria dos Jogos

RESUMO

Ao longo da disserta¸c˜ao s˜ao apresentados os fundamentos necess´arios para o traba-

lho cooperativo. Nesse sentido, foi feita uma discuss˜ao ﬁlos´oﬁca sobre o comportamento

social, dando ˆenfase nas rela¸c˜oes entre indiv´ıduos e ambiente. Entretanto, para o compor-

tamento social surgir, ´e necess´ario um mecanismo democr´atico, que trate os indiv´ıduos

em igualdade de condi¸c˜ao, j´a que todo indiv´ıduo ´e importante para o ambiente. Con-

tudo, entender o processo de tomada de decis˜ao ´e fundamental para a obten¸c˜ao de bons

resultados. Para isso, a Teoria dos Jogos foi utilizada a ﬁm de compreender o processo de

tomada de decis˜ao em um ambiente dinˆamico, onde duas sociedades de robˆos disputam

um mesmo objetivo. Para a valida¸c˜ao da proposta, a aplica¸c˜ao escolhida foi o futebol

de robˆos (RoboCup Small Size League f-180 com seus parˆametros e suas regras), por ser

um desaﬁo padr˜ao da ´area de rob´otica. Na RoboCup f-180, um computador deve pro-

cessar imagens capturadas por uma cˆamera, localizada acima do campo, e, a partir das

informa¸c˜oes extra´ıdas das imagens, deﬁnir as a¸c˜oes cooperativas a serem executadas pela

equipe.

E importante acrescentar que o futebol de sal˜ao (futsal) foi a principal inspira¸c˜ao

para o desenvolvimento da solu¸c˜ao para a aplica¸c˜ao escolhida. Por ﬁm, foram realizados

testes para validar a solu¸c˜ao.

ABSTRACT

In this work it is presented the relevant research topics for the cooperating robot

work. Thus, a philosophical approach on social behavior was done, with emphasis in the

relations between individuals and environment. However, in order to this social behavior

to appear, is necessary a democratic mechanism, that deals with the individuals in equality

condition, since every each other individual is imp ortant for the environment. In order

to achieve good results it is crucial to understand the decision making process. For

this, the Game Theory is used in order to understand the decision process in a dynamic

environment, where two societies of robots dispute the same objective. For the validation

of the proposal, the chosen application was RoboCup Small Size League (f-180), since this

is standard challenge for the robotics area. In RoboCup f-180, a computer must process

images captured by a camera, located above of the ﬁeld. From the extracted information

of the images, it is necessary to deﬁne the cooperating actions to be executed for the

team. It is important to add that the futsal was the main inspiration for the development

of the solution for the chosen application. Finally, tests had been carried out to validate

our proposal.

1 INTRODUC¸

A coopera¸c˜ao entre robˆos ´e uma ´area de pesquisa que tem atra´ıdo muita aten¸c˜ao

nos ´ultimos anos. As equipes rob´oticas com m´ultiplos robˆos fornecem vantagens sobre

sistemas de um ´unico robˆo. Por exemplo, permitem que uma ´area seja coberta mais

eﬁcientemente e s˜ao mais tolerantes `as falhas individuais dos robˆos. Entretanto, Emery-

Montemerlo et. al. (EMERY-MONTEMERLO ET. AL., 2005) alertam que, ao projetar

uma equipe multi-robˆos, a pergunta chave ´e: como atribuir tarefas individuais aos robˆos,

de forma que ﬁquem melhor coordenados seus comportamentos?

Esta disserta¸c˜ao n˜ao tem a ambi¸c˜ao de responder esse importante questionamento, mas

pretende abordar t´opicos relevantes que devem ser considerados na tentativa de construir

robˆos com comportamentos sociais cooperativos. O objetivo do trabalho ´e capacitar

um conjunto de robˆos para trabalhar em sociedade, realizando tarefas cooperativas em

ambientes semiestruturados e dinˆamicos. A plataforma de teste a ser utilizada ´e o futebol

de robˆos.

1.1 MOTIVAC¸

Em aplica¸c˜oes de sociedades rob´oticas, o comportamento social surge porque um robˆo

faz parte do ambiente e, assim, ´e imp ortante para outro(s) robˆo(s). Nesse sentido, a

constru¸c˜ao de duas sociedades rob´oticas, onde em cada sociedade o comportamento co-

operativo ´e fundamental para sua ”sobrevivˆencia” no ambiente, visto que a competi¸c˜ao

entre as sociedades emerge na disputa de um mesmo objetivo, ´e o que norteia este tra-

balho.

Esse tipo de pesquisa, h´a anos, fascina pesquisadores de diversas ´areas. Tanto ´e

verdade que a Vida Artiﬁcial surgiu na tentativa de recriar fenˆomenos biol´ogicos em

computadores ou outros meios artiﬁciais. A multi-disciplinaridade ´e evidenciada desde

sua cria¸c˜ao, pois surgiu da conﬂuˆencia da IA, rob´otica, teorias biol´ogicas, psicologia, etc.

Assim, a constru¸c˜ao de duas equipes de robˆos ´e motivada para serem utilizadas em

estudos de uma s´erie de experimentos, entre eles os que envolvem robˆos autˆonomos coo-

perativos. Contudo, h´a tamb´em a vontade de montar uma equipe de robˆos do IME para

participar de competi¸c˜oes oﬁciais realizadas por federa¸c˜oes cient´ıﬁcas.

Al´em da quest˜ao l´udica, as competi¸c˜oes cient´ıﬁcas possibilitam acelerar o progresso

cient´ıﬁco no dom´ınio em que esteja inserido. Nas competi¸c˜oes, s˜ao testados conhecimen-

tos em ´areas diversas, como programa¸c˜ao, vis˜ao computacional, integra¸c˜ao de sistemas,

navega¸c˜ao em ambientes dinˆamicos, explora¸c˜ao e monitoramento ambiental, controle de

tr´afego a´ereo e urbano, transmiss˜ao de dados via radiofreq¨uˆencia, an´alise de dispositivos

eletromecˆanicos e microcontrolados, etc.

O futebol de robˆos, problema padr˜ao de investiga¸c˜ao internacional, re´une grande parte

dos desaﬁos presentes em problemas do mundo real a serem resolvidos em tempo real. O

futebol de robˆos ´e baseado em um jogo humano, inspirado na inteligˆencia humana, e com

o prop´osito de fazer robˆos interagirem com humanos, j´a que o objetivo dessas competi¸c˜oes

´e fazer com que robˆos disputem partidas contra equipes de seres humanos. Ent˜ao, nada

mais racional do que observar o ser humano em seu processo decis´orio e comportamental,

para deﬁnir estrat´egias sociais a ﬁm de fazer emergir a coopera¸c˜ao entre os robˆos. A maior

inspira¸c˜ao ´e o pr´oprio futebol de humanos, mais precisamente o futsal, cujas regras tˆem

mais semelhan¸cas com as regras da categoria escolhida para ser explorada nesse trabalho,

do que com as regras do futebol de campo.

As solu¸c˜oes encontradas para o futebol de robˆos podem ser estendidas, possibilitando

o uso da rob´otica em locais de dif´ıcil acesso para humanos, ambiente insalubres e situa¸c˜oes

de risco de vida iminente, incluindo a explora¸c˜ao espacial. Nesse sentido, ´e fundamental

dominar o ciclo de desenvolvimento de projeto, pois se prevˆeem que o pa´ıs que ignorar o

conhecimento da constru¸c˜ao e opera¸c˜ao de robˆos autˆonomos estar´a comprometendo sua

capacidade de competi¸c˜ao no mercado globalizado.

Uma vez montadas as equipes, jogos demonstrativos poder˜ao ser realizados em locais

de aﬂuˆencia de p´ublico, tais como feiras, congressos e escolas, objetivando despertar o

interesse das pessoas para a ciˆencia, em especial para a ´area de tecnologia, uma vez que

os jovens ter˜ao a oportunidade de ver, na pr´atica, a aplica¸c˜ao dos conceitos que antes

ﬁcavam restritos aos livros, desconhecendo suas possibilidades de aplica¸c˜ao.

1.2 COMENT

ARIOS PRELIMINARES

Baseado no princ´ıpio da coopera¸c˜ao, onde se dividem tarefas entre os envolvidos, podendo

ser especializados em determinadas tarefas, as pesquisas de rob´otica costumam ter como

premissa que projetar, construir e usar diversos robˆos simples pode ser mais f´acil do que

projetar, construir e usar um ´unico robˆo complexo. Dependendo da quantidade de robˆos

utilizados, o custo tamb´em poder´a ser otimizado. Complementarmente, um grupo de

robˆos ´e mais ﬂex´ıvel e tolerante a falhas, uma vez que um ou mais robˆos podem falhar

sem afetar a conclus˜ao da tarefa.

A aplica¸c˜ao escolhida para ser investigada, o futebol de robˆos, une a paix˜ao nacional

com a pesquisa cient´ıﬁca. Atualmente, o futebol de robˆos ´e considerado por muitos como

uma paix˜ao tecnol´ogica, aliando a estrat´egia t´atica (inteligˆencia artiﬁcial) com habilidade

t´ecnica (rob´otica) dos jogadores.

E importante acrescentar que durante uma partida de

futebol de robˆos, a interferˆencia humana no sistema de controle dos robˆos ´e proibida, ou

seja, os robˆos s˜ao autˆonomos.

Existem diversas categorias de futebol de robˆos, como tamb´em s˜ao v´arias as enti-

dades que deﬁnem as regras para suas determinadas categorias. As diversas categorias

se dividem em dois grupos: robˆos f´ısicos e robˆos simulados. A categoria escolhida para

ser abordada ´e composta de robˆos f´ısicos e ´e chamada de Small Size League f-180 da

Federa¸c˜ao RoboCup.

Na liga RoboCup Small Size f-180, o jogo ´e disputado por equipes compostas de no

m´aximo 5 robˆos. A percep¸c˜ao visual ´e global e o controle dos robˆos ´e centralizado. Dessa

forma, o sistema de controle dos robˆos (inteligˆencia artiﬁcial) ´e externo, recebe os dados

de uma ou mais cˆameras localizadas acima do campo, processa os dados, determina qual

estrat´egia seguir e, posteriormente, qual comando deve ser executado em cada robˆo. Por

ﬁm, esse comando ´e enviado atrav´es de radiofreq¨uˆencia aos robˆos.

Os problemas de investiga¸c˜ao contidos no futebol de robˆos cobrem uma ´area mais am-

pla do que aparentam, j´a que o jogo pode ser visto apenas como uma simples brincadeira.

No entanto, o futebol de robˆos constitui um dom´ınio bem mais complexo. Dentre os

problemas nele explorados, podem ser citados a coordena¸c˜ao, coopera¸c˜ao, comunica¸c˜ao

entre m´aquinas, aprendizagem, planejamento em tempo real, decis˜ao estrat´egica, t´atica,

comportamento, vis˜ao, controle, locomo¸c˜ao e sistemas sensoriais.

Para Stone apud Reis (REIS, 2003), os principais perigos das competi¸c˜oes cient´ıﬁcas

est˜ao na obsess˜ao por vencer, especialmente quando prˆemios em dinheiro est˜ao envolvidos,

uma vez que existe um incentivo para manter secretas as t´ecnicas ”vencedoras” de ano

para ano, sem que o seu desenvolvimento permita avan¸car a ciˆencia em geral. No entanto,

na RoboCup, o desaﬁo cient´ıﬁco procura diminuir o risco de se esconder as solu¸c˜oes,

incentivando e premiando a publica¸c˜ao cient´ıﬁca de qualidade. Por exemplo, na categoria

de robˆos simulados, a disponibiliza¸c˜ao do c´odigo fonte de anos anteriores ´e pr´e-requisito

para a inscri¸c˜ao na competi¸c˜ao do ano seguinte.

Para analisar o futebol de robˆos, a Teoria dos Jogos (TJ), que ´e uma teoria matem´atica

que se origina do estudo de jogos, ´e usada em aplica¸c˜oes como uma ferramenta auxili-

adora na compreens˜ao de sistemas complexos. A Teoria dos Jogos estuda, atrav´es de

modelos matem´aticos, a escolha de decis˜oes sob condi¸c˜oes de conﬂito e ajuda a entender

teoricamente o processo de decis˜ao.

1.3 ORGANIZAC¸

AO DA DISSERTAC¸

A disserta¸c˜ao est´a organizada a ﬁm de permitir um maior entendimento do assunto.

No cap´ıtulo 2 ´e feita uma revis˜ao de literatura sobre as id´eias que s˜ao discutidas ao

longo da disserta¸c˜ao. O cap´ıtulo 3 ´e reservado para a descri¸c˜ao do problema, onde ´e

realizada uma discuss˜ao ﬁlos´oﬁca sobre coopera¸c˜ao, apresentando com mais detalhes o

problema, assim como as premissas e condi¸c˜oes para sua execu¸c˜ao. A solu¸c˜ao proposta

´e o tema do cap´ıtulo 4. No cap´ıtulo 4, as solu¸c˜oes e considera¸c˜oes t´ecnicas s˜ao descritas

detalhadamente. Para validar a solu¸c˜ao proposta, o cap´ıtulo 5 descreve os testes realizados

e seus respectivos resultados. Por ﬁm, as considera¸c˜oes ﬁnais da disserta¸c˜ao s˜ao feitas,

bem como perspectivas de sua continua¸c˜ao em trabalhos futuros.

2 REVIS

AO DE LITERATURA

Neste cap´ıtulo, o principal objetivo ´e apresentar subs´ıdios para que se possa relacionar

este a outros trabalhos. Assim, ser˜ao descritos os tipos de ve´ıculos autˆonomos e suas

caracter´ısticas. Posteriormente, o foco ser´a a vis˜ao computacional, onde alguns trabalhos

relacionados ao futebol de robˆos s˜ao apresentados. Em seguida, h´a uma explana¸c˜ao sobre

a coopera¸c˜ao no futebol de robˆos e teoria dos jogos. Por ﬁm, o planejamento de trajet´oria

encerra a revis˜ao de literatura.

2.1 VE

ICULOS AUT

ONOMOS

Ve´ıculos autˆonomos constituem uma classe de sistemas mecˆanicos que possuem trˆes graus

de liberdade, que s˜ao as coordenadas x, y e a orienta¸c˜ao θ, mas s´o podem ser controlados

por duas vari´aveis: a velocidade escalar do centro de massa do ve´ıculo e a velocidade

angular do ve´ıculo em torno do centro instantˆaneo de rota¸c˜ao. Os ve´ıculos costumam

ser classiﬁcados em n˜ao-holonˆomicos (movimentam-se em qualquer dire¸c˜ao no plano com

a necessidade de manobras) e holonˆomicos (movimenta-se em qualquer dire¸c˜ao no plano

sem a necessidade de manobras).

Dentre os ve´ıculos autˆonomos de trˆes rodas, Campion et. al. (CAMPION ET. AL.,

1996) os classiﬁcam em cinco tipos. Vide FIG. 2.1.

• Tipo (0,0) - robˆo com trˆes rodas direcion´aveis descentradas;

• Tipo (1,0) - robˆo com duas rodas ﬁxas no mesmo eixo e uma roda direcion´avel

descentrada;

• Tipo (0,1) - robˆo com uma roda direcion´avel centrada e duas rodas direcion´aveis

descentradas;

• Tipo (1,1) - robˆo com duas rodas ﬁxas no mesmo eixo e uma roda direcion´avel

centrada;

• Tipo (0,2) - robˆo com duas rodas direcion´aveis centradas e uma roda direcion´avel

descentrada.

FIG. 2.1: Classiﬁca¸c˜ao de ve´ıculos autˆonomos (CAMPION ET. AL., 1996).

Figueiredo e Jota (FIGUEIREDO E JOTA, 2004) deﬁnem sistemas n˜ao-holonˆomicos

como sistemas com dimens˜ao ﬁnita, onde algum tipo de restri¸c˜ao ´e imposta a um ou

mais estados do sistema. Assim, sistemas n˜ao-holonˆomicos p odem ser interpretados como

sistemas n˜ao integr´aveis. A abordagem matem´atica a este tipo de problema ´e realizada

atrav´es de ferramentas da geometria diferencial. Apesar dos movimentos serem limitados

em sistemas n˜ao-holonˆomicos, eles podem atingir qualquer conﬁgura¸c˜ao no espa¸co onde

est˜ao deﬁnidos (quando control´aveis e ating´ıveis).

Os ve´ıculos n˜ao-holonˆomicos encontrados no futebol de robˆos possuem duas rodas

motoras, ou seja, associadas a motores e uma ro da livre, do tipo castor, para apoio da

estrutura. Assim, com velocidades iguais nas duas rodas motoras, o robˆo desloca-se em

linha reta; para a direita se a velocidade da roda esquerda for maior do que a da roda

direita e vice-versa. Esse tipo de ve´ıculo ´e chamado de ve´ıculo de tra¸c˜ao diferencial. Para

maiores detalhes sobre robˆos n˜ao-holonˆomicos no futebol de robˆos consultar (INDIVERI,

2001) (JONG-HWAN ET. AL., 1998).

Ao contr´ario dos robˆos n˜ao-holonˆomicos, nos robˆos holonˆomicos a omnidirecionali-

dade de um robˆo prov´em da sua capacidade de movimentar-se em qualquer dire¸c˜ao no

plano, sem a necessidade de rotacionar no pr´oprio eixo. A equipe da Universidade de

Cornell (D’ANDREA, 2005), dos Estados Unidos, introduziu em 2000 a utiliza¸c˜ao de

robˆos holonˆomicos no futebol de robˆos. A movimenta¸c˜ao omnidirecional resulta em maior

facilidade de deslocamento, bem como maior agilidade.

A omnidirecionalidade ´e obtida atrav´es do controle individual das rodas, onde cada

FIG. 2.2: Distribui¸c˜ao de rodas omnidirecionais em robˆos holonˆomicos (ASHMORE AND

BARNES, 2002).

FIG. 2.3: Rodas omnidirecionais da equipe Cornell Big Red 2002 (esquerda) e 2003 (di-

reita) (PURWIN AND D’ANDREA, 2003).

robˆo possui um n´umero de rodas maior ou igual a 3 (FIG. 2.2), e cada uma delas possui

um motor associado. Assim, pela combina¸c˜ao vetorial da for¸ca aplicada por cada roda,

comp˜oe-se um vetor velocidade resultante e uma velocidade angular. Por´em, para pro-

porcionar ao robˆo movimenta¸c˜ao omnidirecional, ´e necess´ario rodas omnidirecionais (com

dois graus de liberdade). Para Ribeiro (RIBEIRO, 2005), rodas omnidirecionais (FIG.

2.3) s˜ao rodas especiais que possuem rolamentos passivos transversais ao eixo de rota¸c˜ao

normal da roda, assim, permitindo que a roda n˜ao ofere¸ca resistˆencia a uma desloca¸c˜ao

na dire¸c˜ao deﬁnida pelo seu eixo de rota¸c˜ao associado a um motor.

Um estudo detalhado sobre os modelos cinem´aticos e dinˆamicos de robˆos do tip o n˜ao-

holonˆomicos ´e apresentado em (HONDA, 2002) e (ROSA E APOLIN

ARIO, 2005). Os

modelos cinem´aticos e dinˆamicos de robˆos n˜ao holonˆomicos s˜ao encontrados em (ASH-

MORE AND BARNES, 2002) e (CARTER ET. AL., 2001).

Atualmente, v´arias equipes da categoria RoboCup f-180 j´a possuem, incorporado

FIG. 2.4: Robˆo da equipe Wingers da Universidade de Buﬀalo na categoria RoboCup

f-180 (UB ROBOTICS, 2006).

ao robˆo, um dispositivo mecˆanico conhecido como ”driblador” (UB ROBOTICS, 2006)

(D’ANDREA, 2005) (MART

INEZ-G

OMEZ ET. AL., 2005). O ”driblador” consiste de

um cilindro girat´orio na qual sua rota¸c˜ao para tr´as permite que o robˆo caminhe com a b ola,

mantendo-a em contato com sua superf´ıcie. Na FIG. 2.4, pode-se observar o ”driblador”

posicionado na frente do robˆo.

Al´em do ”driblador”, os robˆos atuais de v´arias equipes p ossuem dispositivo de chute

e algumas, dispositivo de passe. Note a diferen¸ca: em um dispositivo de chute, n˜ao h´a

tanta preocupa¸c˜ao quanto a for¸ca aplicada `a bola; j´a no passe, a for¸ca deve possuir um

controle diferencial para fazer o dispositivo funcionar com precis˜ao.

E imp ortante frisar

que, cada dispositivo a mais presente nos robˆos acarreta maior custo no desenvolvimento

deles.

Nos ´ultimos anos as principais competi¸c˜oes internacionais foram compostas basica-

mente por equipes de robˆos holonˆomicos. Uma constata¸c˜ao de que esses tipos de robˆo

apresentam-se mais adequados `a aplica¸c˜ao de futebol de robˆos, ´e que os atuais campe˜oes

dos mais importantes campeonatos mundiais s˜ao equipes formadas por robˆos holonˆomicos.

Para o desenvolvimento dos robˆos da equipe do IME, algumas premissas devem ser

obedecidas: i) os robˆos devem ter dimens˜oes e caracter´ısticas f´ısicas de acordo com as

regras da RoboCup f-180 ii) o robˆo deve ser projetado de maneira que possa ser utilizado

em outras aplica¸c˜oes, al´em do futebol de robˆos; iii) as pe¸cas devem ser de f´acil reposi¸c˜ao

e disponibilidade; iv) o custo de montagem e manuten¸c˜ao dos robˆos deve ser baixo.

FIG. 2.5: Passos fundamentais em processamento de imagens digitais, adaptado de (GON-

ZALEZ, 1992).

2.2 VIS

AO COMPUTACIONAL

O objetivo da Vis˜ao Computacional ´e a determina¸c˜ao de caracter´ısticas dos objetos con-

tidos em imagens digitalizadas. No modelo cl´assico de Marr (MARR, 1982), a vis˜ao ´e

dividida em m´odulos de baixo n´ıvel, n´ıvel intermedi´ario e alto n´ıvel.

Nos m´etodos de baixo n´ıvel, h´a pouco conhecimento do conte´udo da imagem. Como

exemplo dos m´etodos de baixo n´ıvel est˜ao os ﬁltros de elimina¸c˜ao de ru´ıdos, detec¸c˜ao

de bordas, melhoramento de contraste etc, que resultam no particionamento da imagem

em partes signiﬁcativas, as quais correspondem `as linhas ou objetos existentes nesta cena.

Nos m´etodos de n´ıvel intermedi´ario ´e feita a an´alise das caracter´ısticas dos objetos a partir

do processamento de baixo n´ıvel, produzindo dados simb´olicos. No pro cessamento de alto

n´ıvel ´e comum a utiliza¸c˜ao de IA.

E onde ocorre a interpreta¸c˜ao ﬁnal da cena, o reconhe-

cimento dos objetos e a an´alise das estruturas relacionais. Assim, ´e necess´ario um modelo

formal de mundo para que as percep¸c˜oes (imagens digitalizadas) sejam comparadas com

esse modelo. Por exemplo, um modelo de um carro pode possuir as descri¸c˜oes das rodas,

portas, etc., e as restri¸c˜oes descrevendo seus relacionamentos (MOLZ ET. AL., 2001).

Gonzalez (GONZALEZ, 1992) divide o processo de processamento de imagens em 4

passos fundamentais a partir da aquisi¸c˜ao da imagem. Vide FIG. 2.5.

Aquisi¸c˜ao de imagens ´e adquirir uma imagem digital a partir do dom´ınio do pro-

blema.

Pr´e-processamento ´e utilizado para melhorar a imagem a ﬁm de maximizar os

resultados do sistema, para isso utilizam-se ﬁltros para remover ru´ıdos, convers˜ao entre

espa¸cos de cores, ajuste de contraste, brilho, etc.

Segmenta¸c˜ao divide uma imagem de entrada em partes ou objetos constituintes.

Representa¸c˜ao ´e a convers˜ao dos dados iniciais em uma estrutura adequada para o

processamento posterior e a descri¸c˜ao procura extrair as caracter´ısticas relevantes para

a diferencia¸c˜ao dos objetos.

Reconhecimento ´e o processo que atribui identiﬁcadores aos objetos e a inter-

preta¸c˜ao atribui um signiﬁcado aos objetos reconhecidos.

Diversas institui¸c˜oes tˆem proposto e implementado sistemas de vis˜ao para o futebol de

robˆos. No entanto, parte desses sistemas baseia-se em hardware especializados com alto

custo de aquisi¸c˜ao. Assim, ´e motivado o desenvolvimento de um software pr´oprio. Al´em

do mais, o desenvolvimento de um sistema de vis˜ao computacional poder´a possibilitar sua

extens˜ao na utiliza¸c˜ao em outros projetos do IME.

As caracter´ısticas desej´aveis para uma solu¸c˜ao no futebol de robˆos ´e pouca com-

puta¸c˜ao (que atenda `as restri¸c˜oes temporais) e acur´acia elevada. Todavia, a rela¸c˜ao

entre computa¸c˜ao e acur´acia tende a ser inversamente proporcional. Nesse contexto,

faz-se necess´ario encontrar uma melhor rela¸c˜ao custo-benef´ıcio entre as vari´aveis supra

citadas. Para isso, ´e preciso levar em considera¸c˜ao a taxa de aquisi¸c˜ao de imagens e,

conseq¨uentemente, a quantidade de quadros processados. Uma maior taxa de aquisi¸c˜ao

de imagens gera menos saltos. Em contrapartida, ´e necess´ario um sistema de baixo custo

computacional.

Algumas equip es de futebol de robˆos j´a est˜ao trabalhando com uma taxa de aquisi¸c˜ao

de aproximadamente 60fps (LOOMIS ET. AL., 2003) (BALL ET. AL., 2004) (MART

INEZ-

OMEZ AND WEITZENFELD, 2004), embora a maioria das equipes possua taxa de

aquisi¸c˜ao de aproximadamente 30fps (ZICKLER, 2005); j´a a Funda¸c˜ao Universidade Fede-

ral do Rio Grande (FURG), atual bicampe˜a brasileira e vice-campe˜a latino-americana da

RoboCup f-180, trabalha com uma taxa de aquisi¸c˜ao de aproximadamente 15fps (COSTA

ET. AL., 2003).

Nesse sentido, trabalhos recentes relacionados ao futebol de robˆos utilizam espa¸cos de

cores distintos para representar a imagem digital e ﬁltros durante o pr´e-processamento

(BALL ET. AL., 2004) (JAMZAD ET. AL., 2001) (MART

INEZ-G

OMEZ AND WEITZEN-

FELD, 2004) (NEVES ET. AL., 2004) (LOOMIS ET. AL., 2003). A grande maioria dos

hardwares (cˆamera e placa de captura) capturam as imagens e trabalham no espa¸co

RGB. Entretanto, como ser´a exposto no cap´ıtulo 4, o espa¸co RGB ´e muito sens´ıvel `as

diferen¸cas de luminosidade do ambiente. Contudo, a possibilidade de sucesso ao utilizar

o espa¸co RGB ´e motivado nesse trabalho, uma vez que deve ser considerado o tempo

de convers˜ao RGB em outros espa¸cos de cores. Quanto aos ﬁltros, muitas vezes eles po-

FIG. 2.6: Exemplos comuns de superf´ıcie na RoboCup f-180, adaptado de (BRUCE AND

VELOSO, 2003).

dem ser desnecess´arios, caso um espa¸co de cor apropriado seja adotado em determinadas

aplica¸c˜oes.

Embora a preocupa¸c˜ao computa¸c˜ao-acur´acia seja importante, ela n˜ao ´e a ´unica. O

sistema de vis˜ao para o futebol de robˆos deve ser de f´acil calibra¸c˜ao, j´a que essa etapa ´e

realizada apenas minutos antes da partida come¸car. Calibra¸c˜ao ´e o ajuste de parˆametros

para que o sistema possa adaptar-se `a ilumina¸c˜ao do ambiente para reconhecer as cores e

localizar objetos.

Em rela¸c˜ao ao que a cˆamera captura do robˆo, a ﬁm de se determinar sua pose

(posi¸c˜ao e orienta¸c˜ao), diversas combina¸c˜oes (aceit´aveis dentro das regras) foram pro-

postas nos ´ultimos anos. No cap´ıtulo 3 ser˜ao expostas as restri¸c˜oes visuais do robˆo. Em

(BRUCE AND VELOSO, 2003) ´e apresentado um estudo sobre identiﬁca¸c˜oes utilizadas

na RoboCup f-180 e os exemplos mais comuns adotados s˜ao o borboleta, simples, linear

e o triangular (FIG. 2.6). Nesse mesmo trabalho, Bruce e Veloso fazem um teste padr˜ao

comparando o erro posicional e angular desses modelos. Vide FIG. 2.7.

O teste padr˜ao estimou com maior exatid˜ao a posi¸c˜ao do modelo Borboleta, seguido

pelo triangular e linear com acur´acia um pouco menor. Para o erro angular, o teste

padr˜ao mostrou o modelo b orboleta com o erro mais baixo novamente, seguido de perto

pelo triangular. Os modelos borboleta e triangular se mostraram mais eﬁcientes, o que

motiva a utiliza¸c˜ao de um deles.

2.3 COOPERAC¸

Projetar robˆos para trabalharem juntos n˜ao ´e uma tarefa trivial. Muitas perguntas re-

manescem na coopera¸c˜ao multi-robˆo. Alguns questionamentos s˜ao feitos por Vail e Veloso

(VAIL AND VELOSO, 2003): Como deve um grupo dos robˆos dividir tarefas entre seus

membros? Uma vez que os pap´eis foram atribu´ıdos aos robˆos, como se posicionarem para

FIG. 2.7: Compara¸c˜ao do erro posicional e angular de diferentes mo delos (BRUCE AND

VELOSO, 2003).

cumprir seus pap´eis sem interferir com seus companheiros de time? O que acontece se um

robˆo falhar ou se o ambiente mudar de modo que um robˆo diferente seja mais apropriado

para a tarefa?

Nos trabalhos em que o dom´ınio da aplica¸c˜ao ´e o futebol de robˆos, ´e comum a id´eia de

se distribuir pap´eis, dinamicamente, entre os membros da equipe (SPAAN AND GROEN,

2002). Este tipo de modelo em um ambiente cooperativo necessita de que todos os mem-

bros tenham caracter´ısticas em comum, n˜ao havendo especializa¸c˜ao entre eles. Adicional-

mente, ´e comum a ado¸c˜ao de objetivos globais e locais em trabalhos rob´oticos cooperativos

(PEREIRA E ROSA, 2001) (ROSA ET. AL., 2004).

Trabalhos recentes relacionados ao futebol de robˆos utilizam m´odulos em s´erie (CAO

ET. AL., 2004) (LIMA ET. AL., 2004) (RUIZ-DEL-SOLAR ET. AL., 2004) (BUCH-

HEIM ET. AL., 2004) (CHALUP ET. AL., 2003). Esse tipo de modelo necessita sempre

processar todos os m´odulos sequencialmente em cada itera¸c˜ao.

Vail e Veloso (VAIL AND VELOSO, 2003) apresentam uma estrutura para a atribui¸c˜ao

de tarefas e coordena¸c˜ao para um grupo dos robˆos em um dom´ınio de futebol de robˆos.

Ainda acrescentam que, embora durante os jogos pode-se claramente observar a coor-

dena¸c˜ao bem sucedida de m´ultiplos robˆos, ´e dif´ıcil quantiﬁcar o valor deste componente

espec´ıﬁco.

2.4 TEORIA DOS JOGOS

A Teoria dos Jogos (TJ) ´e um m´etodo da Teoria da Decis˜ao e desde a publica¸c˜ao de Theory

of Games and Economic Behaviour (VON NEUMANN AND MORGENSTERN, 1944),

lan¸cando os fundamentos desse m´etodo, a Teoria dos Jogos (TJ) vem sendo aplicada em

diversas ´areas.

Shi e Littman (SHI AND LITTMAN, 2002) apresentam em Abstraction methods for

game theoretic poker a TJ utilizada para a tomada de decis˜ao no pˆoquer, tradicional jogo

de cartas. A TJ tamb´em ´e aplicada em muitos outros jogos, por exemplo, xadrez (SHAN-

NON, 1950) (ANANTHARAMAN, 1990), damas (SAMUEL, 1967), go (MULLER, 1993),

gam˜ao, jogos de tabuleiro, entre outros. Entretanto, nesses jogos, geralmente, o tipo de

movimenta¸c˜ao ´e seq¨uencial. J´a no futebol de robˆos, a movimenta¸c˜ao ´e simultˆanea, o que

muda o enfoque de estudo. A TJ tamb´em costuma ser aplicada na pol´ıtica de governo,

na an´alise militar (estrat´egica e t´atica), biologia, etc.

Em sistemas inteligentes, o uso da TJ para direcionar o aprendizado de agentes ´e inte-

ressante (VIDAL, 2003). Contudo, a TJ ainda ´e pouco aplicada ao futebol de robˆos, sendo

esse um jogo. Entretanto, recentemente, em Game Theoretic Control for Robot Teams

(EMERY-MONTEMERLO ET. AL., 2005) a TJ foi adotada para modelar um problema

de Partially observable stochastic games (POSGs), que ´e uma tarefa fortemente acoplada,

para o controle de times rob´oticos. A coopera¸c˜ao entre os robˆos de uma mesma equipe,

no futebol de robˆos, tamb´em ´e uma tarefa fortemente acoplada (descrita posteriormente).

Todavia, Emery-Montemerlo et. al. aplicam a TJ em uma aplica¸c˜ao descentralizada. Em

contrapartida, a categoria do futebol de robˆos adotada para valida¸c˜ao desse trabalho ´e

centralizada. Assim, ´e motivada a utiliza¸c˜ao da TJ para melhor compreender as rela¸c˜oes

existentes e os tipos de jogos envolvidos no futebol de robˆos.

2.5 PLANEJAMENTO DE TRAJET

ORIAS

Para Jensen et. al. (JENSEN ET. AL., 2003), o maior desaﬁo na navega¸c˜ao dos robˆos

est´a em representar o ambiente de forma compacta. Existem v´arios m´etodos para resolver

problemas gerais de planejamento de trajet´orias. Entretanto, os m´etodos s˜ao baseados

em algumas t´ecnicas gerais. As trˆes principais abordagens utilizadas pelas t´ecnicas de

navega¸c˜ao de robˆos m´oveis autˆonomos s˜ao: roadmaps, decomposi¸c˜ao de c´elulas e campo

potencial.

FIG. 2.8: Grafo de visibilidade (LATOMBE, 1991).

FIG. 2.9: Diagrama de Voronoi (LATOMBE, 1991).

2.5.1 ROADMAP

O roadmap consiste em representar a conectividade das informa¸c˜oes ambientais do espa¸co

livre em um grafo. Uma vez constru´ıdo o grafo, o planejamento de trajet´oria ´e calculado

a partir da posi¸c˜ao inicial e ﬁnal do robˆo. O problema dessa abordagem est´a no fato de,

geralmente, os grafos n˜ao fornecerem uma boa forma de representa¸c˜ao das informa¸c˜oes

do ambiente.

Diversos m´etodos com diferentes tipos de roadmaps foram propostos. Por exemplo,

dois m´etodos bastante utilizados s˜ao: grafo de visibilididade (FIG. 2.8) e diagrama de

Voronoi (FIG. 2.9).

E interessante acrescentar que n˜ao ´e comum o uso de roadmaps no

futebol de robˆos.

FIG. 2.10: Espa¸co livre decomposto de forma exata em um conjunto de c´elulas poligonais

(LATOMBE, 1991).

2.5.2 DECOMPOSIC¸

AO EM C

ELULAS

O m´etodo de decomposi¸c˜ao em c´elulas consiste em representar o ambiente por meio de

c´elulas. Um grafo n˜ao-dirigido representa a rela¸c˜ao de adjacˆencia entre as c´elulas. O

v´ertices do grafo s˜ao c´elulas do espa¸co livre do robˆo. A trajet´oria planejada pela decom-

posi¸c˜ao em c´elulas ´e uma seq¨uˆencia de c´elulas.

Dividem-se os m´etodos de decomposi¸c˜ao em c´elulas em exatos e aproximados (OTTONI

E LAGES, 2003). Os m´etodos exatos decomp˜oem o espa¸co em um conjunto de c´elulas no

qual a uni˜ao cobre o espa¸co livre (FIG. 2.10). Os m´etodos aproximados dividem o espa¸co

em um conjunto de c´elulas de forma predeﬁnida cuja uni˜ao est´a estritamente contida no

espa¸co livre (FIG. 2.11).

Para maiores informa¸c˜oes de artigos de futebol de robˆos relaciodos `a decomposi¸c˜ao

em c´elulas, consulte (NEVES ET. AL., 2004) (THOMAS ET. AL., 2003) (BRACHO ET.

AL., 2001).

2.5.3 CAMPO POTENCIAL ARTIFICIAL

Os m´etodos de campos potenciais artiﬁciais s˜ao muito populares entre os pesquisadores

de Rob´otica e s˜ao comumente adotados no futebol de robˆos (NAGASAKA ET. AL., 2001)

(MEYER ET. AL., 2003). O princ´ıpio b´asico do camp o potencial est´a em movimentar

um robˆo sob um campo de for¸cas artiﬁciais geradas pelos obst´aculos e pelo alvo (FIG.

2.12).

FIG. 2.11: Decomposi¸c˜ao aproximada em c´elulas (OTTONI E LAGES, 2003).

FIG. 2.12: Exemplo de planejamento de trajet´oria utilizando campo potencial artiﬁcial

(PACHECO E COSTA, 2002).

O campo potencial pode ser bastante eﬁciente, se comparado a outros m´etodos. No

entanto, o problema mais conhecido da abordagem por campo potencial ´e a possibilidade

de convergˆencia do movimento para regi˜oes em estado de potencial m´ınimo local. Os

m´ınimos locais podem ser constitu´ıdos em diversos formatos. O mais conhecido m´ınimo

local ´e o de formato de U. Contudo, h´a diversas heur´ısticas propostas para solucionar o

problema dos m´ınimos locais e pelo fato do futebol de robˆos ser uma aplica¸c˜ao extrema-

mente dinˆamica, acredita-se que seja adequado o uso do m´etodo de campo potencial

artiﬁcial.

3 DESCRIC¸

AO DO PROBLEMA

Neste cap´ıtulo, para que se melhor compreenda as rela¸c˜oes envolvidas no futebol de

robˆos, ´e descrito o processo social entre humanos, bem como as rela¸c˜oes necess´arias para

que isso ocorra. Em seguida, o problema da tomada de decis˜ao e dos jogos s˜ao apresen-

tados. Posteriormente, o problema do futebol de robˆos ´e exposto.

3.1 COOPERAC¸

”A coopera¸c˜ao entre os homens e o respeito `a vida

far˜ao deste, o melhor dos mundos.”

(Autor Desconhecido)

Nos estudos da IA, focam-se os objetivos na tentativa de construir uma m´aquina

que exiba comportamento inteligente, igual ou superior ao do ser humano. Para isso, ´e

necess´ario compreender como se desenvolve a inteligˆencia humana.

Segundo Piaget apud (BEHAR E COSTA, 1996), a inteligˆencia humana se desenvolve,

desde a sua origem, como processo interpessoal e, a capacidade de agir voluntariamente,

controlando o meio f´ısico. Um ambiente individualista, se comparado `a organiza¸c˜ao co-

operativa (que favorece o estabelecimento de rela¸c˜oes entre os indiv´ıduos), n˜ao propicia

bons resultados em rela¸c˜ao ao n´ıvel de rendimento e produtividade dos sujeitos envolvidos

neste tipo de processo.

Vygotsky apud (FREITAS, 1995) compreende que o sujeito n˜ao se constitui a partir

de fenˆomenos internos e nem se reduz a um mero reﬂexo passivo do meio. Para ele, o

sujeito se constitui na rela¸c˜ao.

Para Skinner (SKINNER, 1979), o comportamento social pode ser deﬁnido como o

comportamento de duas ou mais pessoas em rela¸c˜ao a uma outra ou em conjunto em

rela¸c˜ao ao ambiente comum. Skinner ainda acrescenta que o comportamento social surge

porque um organismo ´e importante para outro como parte de seu ambiente. Por isso, no

trabalho cooperativo existe uma coopera¸c˜ao m´utua entre participantes.

Como foi visto acima, trˆes grandes nomes da psicologia, apesar de divergirem em

diversas ´areas, s˜ao unˆanimes em reconhecer que uma boa organiza¸c˜ao social ´e primordial

para a obten¸c˜ao de resultados favor´aveis. Isso porque o comportamento social est´a nas

rela¸c˜oes entre indiv´ıduos ou entre indiv´ıduos/ambiente.

Diante da necessidade de exprimir comportamento social, ´e preciso entender o processo

de constru¸c˜ao da inteligˆencia coletiva. A base e o objetivo da inteligˆencia coletiva s˜ao o

reconhecimento e o enriquecimento m´utuos dos agentes. A express˜ao ”inteligˆencia cole-

tiva” foi usada originalmente no contexto de sistemas rob´oticos celulares para descrever

a auto-organiza¸c˜ao de agentes mecˆanicos simples atrav´es da intera¸c˜ao com proximidade

dos vizinhos. Bonabeau et. al. (BONABEAU ET. AL., 1999) estenderam essa deﬁni¸c˜ao

incluindo que a inteligˆencia coletiva ´e ”toda a tentativa de projetar algoritmos ou disposi-

tivos resolvendo problemas distribu´ıdos inspirado pelo comportamento coletivo de colˆonias

sociais de inseto e de outras sociedades animais”. A inspira¸c˜ao da inteligˆencia coletiva ´e

biol´ogica e engloba colˆonias de insetos (formigas, cupins, etc), bando de p´assaros, cardume

de peixes e at´e a sociedade humana.

Baseando-se nas id´eias de Piaget, se aplicadas `a rob´otica, diversas tarefas poder˜ao

ser executadas com mais eﬁciˆencia e robustez usando m´ultiplos robˆos (PARKER, 2000).

Por exemplo, Fierro et. al. (FIERRO ET. AL., 2002) trabalharam em dois geradores

de trajet´orias simples derivados da teoria do campo potencial. O primeiro, onde cada

robˆo funciona como seu pr´oprio controlador de trajet´orias, permite que cada robˆo planeje

sua trajet´oria de referˆencia baseado na informa¸c˜ao disp on´ıvel a ele. O segundo esquema

requer informa¸c˜ao compartilhada e permitiu uma forma¸c˜ao r´ıgida do grupo, al´em de os

robˆos poderem negociar os obst´aculos, evitar colis˜oes e manter a forma¸c˜ao.

Para Kube e Bonabeau (KUBE AND BONABEAU, 1998), determinados agentes po-

dem se tornar especializados na realiza¸c˜ao de certas tarefas, tornando o trabalho coope-

rativo ainda mais eﬁciente, al´em de aumentar as possibilidades de novas tarefas. Como

exemplo disso, ´e tra¸cado um paralelo entre formigas e robˆos. No trabalho cooperativo

das formigas, quando uma ´unica formiga encontra um alimento, tenta movˆe-lo sozinha;

quando bem sucedida, a formiga leva o alimento para o formigueiro. Quando mal suce-

dida (ap´os diversas tentativas de reposicionamento mal sucedidas), s˜ao recrutadas mais

formigas. Se, ap´os v´arias tentativas, as formigas forem incapazes de mover o alimento, as

trabalhadoras especializadas, com mand´ıbulas grandes, podem ser recrutadas para cort´a-

lo em partes menores. Diante disso, as solu¸c˜oes n˜ao s˜ao pr´e-deﬁnidas, mas emergem para,

por exemplo, encontrar uma trajet´oria para o sistema e seu ambiente, de modo que os

estados do sistema e do ambiente constituam a solu¸c˜ao do problema.

Para modelar o comportamento social cooperativo ´e primordial entender seu funciona-

mento. L´evy (L

EVY, 2003) n˜ao vˆe a inteligˆencia coletiva como um conceito exclusiva-

mente cognitivo. Para ele a inteligˆencia deve ser compreendida no sentido de ”trabal-

har em comum acordo”. Trata-se de uma abordagem de car´ater bem geral da vida em

sociedade e de seu poss´ıvel futuro. Nesse contexto, (DE-FARIAS, 2005) diz que o com-

portamento ´e uma situa¸c˜ao na qual a emiss˜ao e/ou o refor¸co do comportamento de um

organismo depende, ao menos parcialmente, do comportamento de outro(s) indiv´ıduo(s).

No entanto os organismos, muitas vezes, podem optar por um trabalho individual.

Desta forma, nas intera¸c˜oes sociais que se destinam `a execu¸c˜ao de tarefas, rela¸c˜oes

cooperativas e competitivas entre os indiv´ıduos s˜ao observadas. As rela¸c˜oes cooperativas

s˜ao caracterizadas pelo ”refor¸co m´utuo”, de modo que todos os indiv´ıduos recebem re-

for¸cos se o desempenho do grupo atingir um crit´erio espec´ıﬁco. Os refor¸cos podem ser

liberados de forma eq¨uitativa ou n˜ao-eq¨uitativa entre os membros do grupo. Em rela¸c˜oes

competitivas, a distribui¸c˜ao de refor¸cos ´e desigual e excludente, dependendo do desem-

penho relativo dos indiv´ıduos, isto ´e, a libera¸c˜ao de refor¸cos para um indiv´ıduo limita ou

mesmo anula a obten¸c˜ao de refor¸cos pelos demais indiv´ıduos.

Quando necess´ario, os robˆos devem ser coordenados para a execu¸c˜ao de tarefas co-

operativas. Durante a coopera¸c˜ao, as a¸c˜oes de cada robˆo necessitam ser especiﬁcadas

levando em considera¸c˜ao as propriedades e habilidades deles, as caracter´ısticas da tarefa,

caracter´ısticas do ambiente, etc.

O comportamento dos robˆos ´e determinado de acordo com as diferentes tarefas. As

tarefas fortemente acopladas s˜ao aquelas que n˜ao podem ser executadas por um ´unico

robˆo; desta forma, requer um grupo de robˆos trabalhando cooperativamente para realiz´a-

la. Por outro lado, as tarefas fracamente acopladas podem ser realizadas por um ´unico

robˆo (PARKER ET. AL., 2004); no entanto, muitas vezes quanto mais robˆos auxiliam

cooperativamente na execu¸c˜ao desse tipo de tarefa, o desempenho aumenta.

Muito embora a so ciedade de seres humanos tenha um objetivo comum, os indiv´ıduos

podem possuir objetivos individuais distintos. Por exemplo, em uma na¸c˜ao, cujos mem-

bros, ainda que n˜ao necessariamente com a mesma origem, l´ıngua, religi˜ao ou ra¸ca, respei-

tam institui¸c˜oes (leis, constitui¸c˜ao, governo). Assim, os robˆos, cada qual com sua pr´opria

caracter´ıstica (objetivo local), para trabalhar de forma cooperativa (objetivo global) s˜ao

levados a ”reﬂetir” sobre o ”pensamento” dos outros. Surge, ent˜ao, a necessidade de

modelar conceitos de democracia no sistema.

Para (L

EVY, 2003) o ideal da democracia n˜ao ´e a elei¸c˜ao de representantes, mas

a maior participa¸c˜ao dos indiv´ıuos da sociedade. O voto ´e um processo de regula¸c˜ao

social que possui apenas efeitos quantitativos, ocultando poss´ıveis nuances de opini˜oes

(solu¸c˜oes). As pesquisas de opini˜ao funcionam, por alto, seguindo os mesmos princ´ıpios

da vota¸c˜ao: o entrevistado deve responder isoladamente ”sim” ou ”n˜ao” a quest˜oes sim-

plistas postas por outros, e suas respostas s´o tˆem efeito estat´ıstico. Um dispositivo de

democracia direta permitiria a cada indiv´ıduo contribuir de maneira cont´ınua para a ela-

bora¸c˜ao e o aperfei¸coamento de solu¸c˜ao para problemas comuns. Os cidad˜aos desenhariam

juntos uma paisagem qualitativamente t˜ao variada quanto quisessem, sem ﬁcar limitados

de sa´ıda, como acontece em um sistema de vota¸c˜ao. Com isso, cada um teria uma identi-

dade e um papel absolutamente singulares e diferentes dos de outros cidad˜aos, conservando

a possibilidade de concordar com os que, sobre este ou aquele assunto, em determinado

momento, possuem posi¸c˜oes pr´oximas ou complementares. Mas quando se trata de comu-

nidades, a no¸c˜ao de tempo real n˜ao tem a mesma escala que os tratamentos da informa¸c˜ao.

Os grupos aprendem mais lentamente que os indiv´ıduos. O aprendizado coletivo demora

tamb´em porque p˜oe em jogo intera¸c˜oes e negocia¸c˜oes entre seres autˆonomos, capazes de

dizer n˜ao, cada um dos quais situados no centro de um mundo. O que inviabiliza a

democracia direta em ambientes competitivos de tempo real.

Contudo, dar coletividade no sentido de comportamento social cooperativo, quando

necess´ario, de forma democr´atica em tempo real ´e o que est´a em jogo.

3.2 TOMADA DE DECIS

”

E f´acil decidir o que fazer.

O dif´ıcil ´e decidir o que n˜ao fazer.”

(Michael Dell)

Qual ´e o processo l´ogico que faz com que um ser racional manifeste preferˆencia por

algo entre dois ou mais objetos? Ou ainda por algu´em entre duas ou mais pessoas?

Costuma-se classiﬁcar em trˆes tip os de escolhas (B

ERNI, 2004). A primeira escolha

ocorre eminentemente de forma individual. O segundo tipo de escolha n˜ao dependente

unicamente da a¸c˜ao individual, uma vez que h´a outro ser envolvido no processo decis´orio.

Tamb´em ´e comumente chamada de escolha interativa. O terceiro tipo de escolha s˜ao as

intera¸c˜oes sociais mais amplas do que dois indiv´ıduos. O presente trabalho se interessa

na investiga¸c˜ao do segundo e terceiro tipo de escolhas.

Na escolha interativa e nas intera¸c˜oes sociais, um jogador necessita compreender as

raz˜oes do comportamento de terceiros para deﬁnir seu pr´oprio comportamento. Para se

tomar uma decis˜ao, ´e necess´ario levantar informa¸c˜oes, process´a-las e s´o ent˜ao decidir o

que fazer. As t´ecnicas decis´orias variam desde o simples ”vou fazer o que der na telha”,

passando pela chamada aritm´etica da prudˆencia, chegando, nos dias que correm, at´e os

mais variados usos da IA (B

ERNI, 2004).

Atualmente, a teoria da decis˜ao ´e um ramo bem estabelecido do conhecimento humano,

sendo que a TJ ´e apenas uma das formas poss´ıveis de se estudar o processo decis´orio.

3.3 TEORIA DOS JOGOS (TJ)

”Podemos ser mais astutos que o outro, nunca,

por´em, mais que todos os outros.”

(Duque De La Rochefoucauld)

A TJ estuda problemas de intera¸c˜ao estrat´egica entre agentes, buscando formalizar

matematicamente o processo de racioc´ınio das a¸c˜oes dos jogadores (agentes) que reconhe-

cem sua intera¸c˜ao m´utua. Isso signiﬁca que na TJ existem regras preestabelecidas para

apresentar e estudar um jogo, o que ´e fundamental para a compreens˜ao da teoria.

Jogos s˜ao situa¸c˜oes que envolvem intera¸c˜oes entre jogadores (agentes racionais), que

tˆem autonomia para tomar decis˜oes, comportando-se estrategicamente.

Um agente ´e simplesmente algo que age (a palavra agente vem do latino agere, que sig-

niﬁca fazer). No entanto, espera-se que um agente computacional tenha outros atributos

que possam distingui-lo de meros ”programas”, tais como operar sob controle autˆonomo,

perceber seu ambiente, persistir por per´ıodo de tempo prolongado, adaptar-se a mudan¸cas

e ser capaz de assumir metas de outros. Um agente racional ´e aquele que age para al-

can¸car o melhor resultado ou, quando h´a incerteza, o melhor resultado esperado (RUSSEL

E NORVIG, 2004).

A TJ trata qualquer ambiente multiagente como um jogo, desde que as a¸c˜oes de cada

agente sobre os outros seja relevante, sem se preocupar se os agentes s˜ao cooperativos ou

competitivos.

SMA ´e uma sub-´area da IAD com forte car´ater interdisciplinar (psicologia social,

computa¸c˜ao, sociologia, ﬁlosoﬁa, l´ogica matem´atica). Em um ambiente multiagente, as

a¸c˜oes de outros agentes devem ser considerados por um dado agente a ﬁm de analisar

como essas a¸c˜oes afetam seu pr´oprio bem-estar. Por´em, os outros agentes, atrav´es da sua

imprevisibilidade, podem introduzir um leque muito grande de estrat´egias poss´ıveis no

processo de resolu¸c˜ao de problemas do agente.

3.3.1 TIPOS DE JOGOS

Faz-se necess´ario conhecer os v´arios tipos de jogos e quais s˜ao os elementos fundamentais

que devem fazer parte deles, para que ent˜ao seja poss´ıvel analis´a-los com mais eﬁciˆencia.

Uma modelagem inadequada pode levar a recomenda¸c˜oes equivocadas sobre que estrat´egia

adotar para obter os melhores resultados. Bˆerni (B

ERNI, 2004) classiﬁca os jogos em:

• Jogos de Estrat´egia - jogos onde a a¸c˜ao ´e necess´aria ser planejada estrategicamente.

• Jogos de Azar - jogos onde o puro acaso inﬂuencia o resultado.

Os jogos de estrat´egias, foco deste trabalho, s˜ao classiﬁcados em:

• Soma Zero - signiﬁca que a recompensa que um jogador ganha ´e exatamente o que o

outro perde. Havendo empate, nenhum ganha e nem mesmo perde. Assim, a soma

dos resultados ´e zero.

• Soma N˜ao-Zero - os jogadores podem sair ganhando ou perdendo, ou seja, a soma

pode ser positiva ou negativa. S˜ao exatamente nesses jogos que podem surgir a

coopera¸c˜ao, visto que a rivalidade n˜ao ´e direta.

Diante dos jogos de Soma N˜ao-Zero, aparece uma nova classiﬁca¸c˜ao:

• Jogos Cooperativos - os jogadores s˜ao estimulados a adotar a¸c˜oes que retornam boas

recompensas a todos os envolvidos.

• Jogos N˜ao-Cooperativos - a postura n˜ao cooperativa procura a¸c˜oes que reduzam as

recompensas dos demais envolvidos (competi¸c˜ao).

Em rela¸c˜ao `a quantidade de intera¸c˜oes, os jogos podem ser:

• Est´aticos - quando h´a apenas uma ocasi˜ao de intera¸c˜ao estrat´egica entre os jo-

gadores.

• Dinˆamicos - quando a intera¸c˜ao estrat´egica acontece mais de uma vez.

A ordem de movimenta¸c˜ao ´e classiﬁcada como segue:

• Simultˆanea - as escolhas devem ser realizadas ao mesmo tempo entre os jogadores,

ignorando as decis˜oes dos demais no momento em que toma sua pr´opria decis˜ao.

N˜ao h´a preocupa¸c˜ao com conseq¨uˆencias futuras das escolhas.

• Seq¨uencial - h´a uma ordem predeterminada de movimenta¸c˜ao entre os jogadores.

Quanto ao conte´udo informacional, os jogos podem ser:

• Completos - os jogadores possuem toda a informa¸c˜ao relevante para deﬁnir sua a¸c˜ao.

• Incompletos - as caracter´ısticas dos jogadores n˜ao s˜ao de conhecimento comum,

tendo conseq¨uˆencias sobre as recompensas dos jogadores.

As informa¸c˜oes (completas ou incompletas) s˜ao divididas em:

• Perfeita - os jogadores sabem todo o hist´orico do jogo antes de deﬁnir sua a¸c˜ao.

• Imperfeita - os jogadores n˜ao conhecem o hist´orico do jogo antes de deﬁnir sua a¸c˜ao.

No entanto, diferentes processos de intera¸c˜ao demandam diferentes representa¸c˜oes.

Segundo Bˆerni (B

ERNI, 2004), quaisquer jogos podem ser representados por dois modelos

b´asicos, s˜ao eles: Forma Normal e Forma Estendida.

A forma mais simples e comum de representar um jogo simultˆaneo ´e pela forma normal.

A forma normal fornece os resultados de todas as combina¸c˜oes poss´ıveis de a¸c˜oes dos

jogadores, bem como as recompensas em fun¸c˜ao de suas escolhas e das escolhas dos

demais jogadores. A forma normal ´e constitu´ıda por uma tabela. As linhas da tabela

representam as poss´ıveis a¸c˜oes do jogador A e as colunas as poss´ıveis a¸c˜oes do jogador B.

A interse¸c˜ao linha/colunas informa o ganho resultante das respectivas a¸c˜oes dos jogadores

A e B.

Com a modelagem de um jogo na forma normal, cada jogador ignora a decis˜ao do

outro, ao tomar sua decis˜ao. Diante disso, para (FIANI, 2004), nada indica que os dois

jogadores consideram poss´ıveis desdobramentos no tempo de suas decis˜oes; eles parecem

considerar apenas as conseq¨uˆencias imediatas.

FIG. 3.1: Dilema dos prisioneiros na forma normal

Um jogo cl´assico utilizado na TJ ´e o Dilema dos Prisioneiro, criado por William

Poundstone (Universidade Princeton) recriado por John H. Kagel e Alvin E. Roth (Cor-

pora¸c˜ao Rand) e enﬁm aperfei¸coado por Albert W. Tucker (Universidade de Stanford)

(TUCKER, 1980). O enunciado do problema do Dilema dos Prisioneiros diz que supondo-

se a ocorrˆencia de um crime, dois suspeitos foram detidos com algumas evidˆencias circuns-

tanciais, mas nenhuma prova cabal. A pol´ıcia os coloca em celas separadas, incomunic´aveis

e a cada um dos suspeitos a pol´ıcia faz a seguinte proposta: se ele confessar o roub o e

o outro suspeito n˜ao confessar, ele ser´a solto em raz˜ao de sua coopera¸c˜ao com a pol´ıcia,

enquanto seu parceiro amargar´a 5 anos de pris˜ao; se, ao contr´ario, ele n˜ao confessar, mas

o outro suspeito o ﬁzer, ser´a a vez dele enfrentar 5 anos de pris˜ao, enquanto seu parceiro

ser´a solto; se ambos confessarem, a coopera¸c˜ao individual perde o valor como den´uncia

do comparsa e ambos enfrentam uma pena de 3 anos de pris˜ao; por ﬁm, se nenhum dos

dois confessar, ambos ﬁcam 1 ano retido. A ﬁgura FIG. 3.1 ´e a representa¸c˜ao normal para

o Dilema dos Prisioneiros.

Sabendo que os jogos simultˆaneos n˜ao fornecem informa¸c˜oes sobre eventuais desdobra-

mentos futuros das escolhas dos jogadores, os jogos seq¨uenciais se desenvolvem em etapas

sucessivas alternando as a¸c˜oes dos jogadores. Entretanto, existem casos em que as esco-

lhas dos jogadores devem ser embasadas nas a¸c˜oes passadas dos demais jogadores. Nesse

tipo de intera¸c˜ao, as escolhas presentes exigem considerar os desdobramentos futuros, j´a

que a retalia¸c˜ao poder´a ser feita por outros jogadores nas pr´oximas etapas. Esses s˜ao os

jogos seq¨uenciais e a forma estendida consegue representar essas caracter´ısticas a ﬁm de

serem analisadas pela TJ. A ﬁgura FIG. 3.2 ´e a representa¸c˜ao do Dilema dos Prisioneiros

na forma estendida.

O Dilema dos Prisioneiros ´e t˜ao importante que at´e os quadrantes foram batizados

ERNI, 2004). O primeiro quadrante (recompensa de 3 anos de pris˜ao para cada jogador)

agora se chama de quadrante da rivalidade universal, uma vez que ambos cooperam com

FIG. 3.2: Dilema dos prisioneiros na forma estendida

a pol´ıcia e n˜ao entre si. No segundo quadrante (recompensas de 0 e 5, respectivamente

para A e B) batizado de caroneiro, A pega carona nas boas inten¸c˜oes de B. No terceiro

quadrante (A recebe pena de 5 anos de cadeia e B apenas 1) A faz o papel de trouxa, uma

vez que B foi o caroneiro. Por ﬁm, o quarto (A e B pegam 1 ano de pena) ´e o quadrante

da coopera¸c˜ao universal, j´a que nenhum confessa o crime e a pol´ıcia apenas pode detˆe-los

pelo menor dos crimes.

E importante ressaltar que a representa¸c˜ao e, principalmente, a solu¸c˜ao dos jogos ´e

mais complicada quando envolve a intera¸c˜ao de mais de dois jogadores. No escopo desse

trabalho, existem dois jogos: entre as equipes (sociedade de agentes) e entre os agentes

de uma sociedade.

3.4 FUTEBOL DE ROB

”(Existem) Diversas formas de fazer o gol e um

milh˜ao de formas de n˜ao fazer.”

(Steve Krug)

Para os experimentos do trabalho, a aplica¸c˜ao escolhida foi o futebol de robˆos RoboCup

Small Size League f-180, com seus parˆametros e suas regras (anexos) (ROBOCUP, 2005a),

por ser um problema padr˜ao de investiga¸c˜ao internacional estimulante do ponto de vista

cient´ıﬁco, que coloca um vasto conjunto de problemas aos investigadores da ´area e ao

mesmo tempo desperta grande interesse no p´ublico em geral, reﬂetindo tamb´em nos

meios de comunica¸c˜ao. O futebol de robˆos ´e uma iniciativa internacional da ´area da

Rob´otica promovida pela comunidade cient´ıﬁca. A id´eia de robˆos jogarem futebol foi men-

cionada pela primeira vez pelo professor Alan Mackworth (University of British Columbia,

Canad´a) em um artigo intitulado ”On Seeing Robots” apresentado no VI-92, em 1992

(ROBOCUP, 2005b), e mais tarde publicado no livro ”Computer Vision: System, The-

ory, and Applications” (MACKWORTH, 1993). O futebol de robˆos inclui ligas que se

dividem em ligas de robˆos reais (utilizando entidades f´ısicas) e liga de simula¸c˜ao. As

competi¸c˜oes entre robˆos autˆonomos apresentam-se como um laborat´orio de capacita¸c˜ao

de robˆos para a realiza¸c˜ao autˆonoma de tarefas e para a forma¸c˜ao de sociedades artiﬁciais,

visando a realiza¸c˜ao de tarefas cooperativas.

No intuito de promover a investiga¸c˜ao na ´area de rob´otica, o futebol de robˆos foi

lan¸cado como objetivo de longo prazo. ”No ano de 2050, uma equipe de robˆos autˆonomos

human´oides, ser´a capaz de vencer a equipe campe˜a do mundo de futebol, num encontro

disputado de acordo com as regras da FIFA” (KITANO, 1997).

Fica claro desde o in´ıcio que o projeto ´e ambicioso e ´e um dos grandes desaﬁos

cient´ıﬁcos atuais.

E estimulante ter um desaﬁo bem deﬁnido de longo prazo dessa pro-

por¸c˜ao a ser investigado por toda uma comunidade. N˜ao se pode deixar de lembrar um

exemplo marcante, que ´e o projeto Apollo da NASA (National Aeronautics and Space

Administration), reiterando aqui as palavras do ent˜ao presidente dos Estados Unidos da

Am´erica, John Fitzgerald Kennedy, quando lan¸cou o desaﬁo. ”Creio que esta na¸c˜ao deve

se comprometer a enviar um homem `a Lua, antes do ﬁm deste decˆenio, e fazˆe-lo regressar

s˜ao e salvo `a Terra. Nenhum projeto espacial deste per´ıodo deve ser mais impressionante

para a Humanidade ou mais importante para a explora¸c˜ao do espa¸co, a longo prazo”

(KENNEDY, 1961).

Antes do futebol de robˆos, os pesquisadores de IA j´a haviam adotado um outro

desaﬁo, investigado nas ´ultimas 4 d´ecadas. O desaﬁo b´asico era de construir um pro-

grama/computador capaz de vencer o campe˜ao mundial de xadrez utilizando as regras

oﬁciais da Federa¸c˜ao Internacional de Xadrez. A padroniza¸c˜ao de problemas ´e importante,

uma vez que metodologias distintas podem ser comparadas, al´em de incentivar a pesquisa

em IA e RI. Desde a ado¸c˜ao do xadrez como problema padr˜ao na d´ecada de 1950, diversos

algoritmos, arquiteturas e metodologias foram propostas. Um marco importante na IA

ocorreu em maio de 1997, quando o computador desenvolvido pela IBM e apelidado de

Deep Blue (DEEP BLUE, 1997) derrotou o campe˜ao mundial de xadrez humano, o russo

Gary Kasparov. Ap´os esse marco, o futebol de robˆos se tornou o desaﬁo padr˜ao.

A principal diferen¸ca entre os problemas do xadrez e do futebol de robˆos ´e que o

segundo consiste em um controle distribu´ıdo, onde v´arios agentes tˆem de agir autonoma-

mente e coordenar-se a ﬁm de cooperar para atingir um objetivo comum. O problema

se torna cr´ıtico, uma vez que o ambiente ´e dinˆamico e a mudan¸ca de estado ´e em tempo

real. Um STR (sistema de tempo real) ´e um sistema computacional que deve reagir

a est´ımulos oriundos do seu ambiente em prazos espec´ıﬁcos de natureza temporal. As

diferen¸cas principais entre o dom´ınio do Xadrez e o RoboCup podem ser visualizadas na

TAB. 3.1 (ROBOCUP, 2005c):

TAB. 3.1: Compara¸c˜ao entre xadrez e futebol de robˆos (ROBOCUP, 2005c)

Quando a internacionaliza¸c˜ao da id´eia do Futebol de Robˆos emergiu, n˜ao haviam regras

a ﬁm de garantir compatibilidade das equipes. Para suprir essa lacuna, pesquisadores

sul-coreanos fundaram a FIRA (Federation of International Robot-soccer Association)

em 1997 (FIRA, 2005a). Paralelamente `a inciativa da FIRA, a empresa japonesa Sony

incentivou o surgimento de competi¸c˜oes de Futebol de Robˆos em escolas e universidades,

o que resultou na cria¸c˜ao de uma outra federa¸c˜ao denominada RoboCup.

3.4.1 A FEDERAC¸

AO ROBOCUP

A federa¸c˜ao RoboCup (RoboCup Federation), originalmente chamada de Robot World

Cup Initiative, ´e uma associa¸c˜ao internacional que tem como principal objetivo a pesquisa,

utilizando a competi¸c˜ao entre equipes de robˆos. Basicamente, ´e uma tentativa de promover

a IA e a RI. Desde que o futebol de robˆos foi adotado como um problema padr˜ao, grandes

esfor¸cos est˜ao concentrados e integrados. A competi¸c˜ao ´e somente uma parte da atividade

da RoboCup. As atividades atuais da RoboCup consistem em (ROBOCUP, 2005d):

• Conferˆencias T´ecnicas

• Conferˆencias e Competi¸c˜oes Internacionais da RoboCup

• Programas de Desaﬁos RoboCup

• Programas de Educa¸c˜ao

• Desenvolvimento de infra-estrutura

Para esta ﬁnalidade, a Rob oCup escolheu usar o futebol de robˆos, e desde ent˜ao orga-

niza a Copa do Mundo de Futebol de Robˆos e conferˆencias, onde os investigadores podem

avaliar o progresso da pesquisa. Atualmente, RoboCup tem trˆes dom´ınios principais

(ROBOCUP, 2005d):

• RoboCupSoccer divide-se em sete categorias:

– Simulation League (2D e 3D), FIG. 3.3;

– Small Size Robot League (f-180), FIG. 3.4;

– Middle Size Robot League (f-2000), FIG. 3.5;

– Four-Legged Robot League, FIG. 3.6;

– Humanoid League, FIG. 3.7;

– E-League;

– RoboCup Commentator Exhibition.

• RoboCupRescue objetiva a investiga¸c˜ao em miss˜oes de salvamento e resgate em

grandes cat´astrofes. Divide-se em duas categorias:

– Rescue Simulation;

– League Rescue Robot League.

• RoboCupJunior foi criada a ﬁm de estimular jovens a participarem da RoboCup.

Divide-se em trˆes categorias:

– Soccer Challenge;

– Dance Challenge;

– Rescue Challenge.

FIG. 3.3: RoboCup Simulation League 3D (ROBOCUP, 2006)

FIG. 3.4: RoboCup Small Size Robot League (f-180) (CMU, 2005)

FIG. 3.5: RoboCup Middle Size Robot League (f-2000) (CMU, 2005)

FIG. 3.6: RoboCup Four-Legged Robot League

FIG. 3.7: RoboCup Humanoid League

3.4.2 ROBOCUP SMALL SIZE (F-180)

A liga de robˆos pequenos (small-size) ´e tamb´em conhecida como a liga f-180. De acordo

com suas regras (ROBOCUP, 2005a), as equipes devem ser compostas por at´e 5 robˆos,

sendo 1 deles o goleiro. Cada robˆo deve estar nitidamente numerado para que o ´arbitro

os possa identiﬁcar durante a partida. O goleiro deve ser designado antes do in´ıcio do

jogo. Durante o jogo, nenhuma interferˆencia humana com o sistema de controle dos robˆos

´e permitida.

O nome small-size se deve `as dimens˜oes pr´e-determinadas dos robˆos. Para a categoria

f-180, os robˆos devem caber em um cilindro de no m´aximo 180mm de diˆametro. Um

robˆo n˜ao deve possuir qualquer artefato que seja perigoso, tanto para um outro robˆo

quanto para seres humanos. Essa caracter´ıstica remete `as famosas Trˆes Leis da Rob´otica

elaboradas pelo escritor ﬁccionista russo Isaac Asimov em seu livro que teve recente

adapta¸c˜ao cinematogr´aﬁca ”Eu, Robˆo” (ASIMOV, 1996). S˜ao elas:

• 1

lei: um robˆo n˜ao pode fazer mal a um ser humano e nem, p or ina¸c˜ao, permitir

que algum mal lhe aconte¸ca;

• 2

lei: um robˆo deve obedecer `as ordens dos seres humanos, exceto quando estas

contrariarem a primeira lei;

• 3

lei: um robˆo deve proteger a sua integridade f´ısica, desde que com isto n˜ao

contrarie as duas primeiras leis

As regras da RoboCup f-180 permitem a utiliza¸c˜ao de vis˜ao global e controle centra-

lizado dos robˆos. O sistema de controle dos robˆos geralmente ´e externo, recebe os dados

da cˆamera localizada acima do campo, processa os dados, determina qual comando deve

ser executado em cada robˆo e envia este comando atrav´es de radiofreq¨uˆencia aos robˆos.

Os robˆos devem possuir marcas pr´oprias no topo de forma a serem identiﬁcados pelo

sistema de vis˜ao global. Antes de um jogo, a cada uma das duas equipes ´e atribu´ıda uma

cor de identiﬁca¸c˜ao (amarela ou azul). Cada equipe deve usar um marcador circular da

cor atribu´ıda no alto dos robˆos. O centro do marcador deve ﬁcar situado no centro visual

do robˆo e o marcador deve ter 50mm de diˆametro. Os robˆos podem ainda usar a colora¸c˜ao

preta e branca sem limita¸c˜ao e tamb´em marcadores cor-de-rosa claro, ciano e verde claro.

Se uma equipe estiver usando o sistema global de vis˜ao, cada robˆo dessa equipe deve

ter uma altura m´axima de 150mm. Nos demais casos, um robˆo pode ter a altura m´axima

de 225mm. O campo de jogo tem as dimens˜oes de 4900mm p or 3400mm. A superf´ıcie

de jogo deve ser da cor verde, podendo ser de feltro ou carpete. O assoalho abaixo do

feltro/carpete deve ser nivelado, liso e r´ıgido. A superf´ıcie do campo continua 300mm

al´em das linhas limites em todos os lados. Na borda da superf´ıcie, uma parede branca

impedir´a que os robˆos funcionem fora do campo.

Todas as linhas que marcam o campo de jogo s˜ao brancas com largura de 10mm. O

campo do jogo ´e dividido em duas metades por uma linha que possui a marca central do

campo (sa´ıda de bola) indicada no ponto m´edio dessa linha. Um c´ırculo com diˆametro de

1000mm ´e desenhado em torno da marca central do campo. Uma ´area de defesa ´e deﬁnida

em cada extremidade do campo por um arco semicircular ´e desenhado no campo do jogo

com seu centro no ponto m´edio entre as traves e um raio de 500mm. A ´area delimitada

por este arco at´e a linha do gol ´e a ´area de defesa. Dentro de cada ´area de defesa, uma

marca de penalidade ´e feita a 450mm do ponto m´edio entre as traves e eq¨uidistante a eles.

A marca ´e um c´ırculo de 10mm de diˆametro.

As traves consistem de duas paredes laterais com 180mm de comprimento e 150mm

de altura juntadas na parte traseira por uma parede de 700mm de comprimento e 150mm

altura. As paredes s˜ao pintadas de azul em um lado do campo e de amarelo no extremo

oposto do campo (para vis˜ao local). O assoalho dentro da trave ´e o mesmo que o do

campo de jogo. As paredes tˆem a mesma espessura que a linha de marca¸c˜ao. As ﬁguras

FIG. 3.8: Campo de jogo da RoboCup f-180 (ROBOCUP, 2005a).

FIG. 3.9: Dimens˜oes em mil´ımetros do campo de jogo da RoboCup f-180 (ROBOCUP,

2005a).

FIG. 3.8 e FIG. 3.9 ilustram o campo de jogo da RoboCup f-180.

A bola padronizada ´e de golfe, com cor de identiﬁca¸c˜ao laranja, aproximadamente 46g

de massa e 43mm de diˆametro. Por ﬁm, um jogador de linha, n˜ao pode invadir a ´area do

goleiro da sua equipe.

4 SOLUC¸

AO PROPOSTA

A inspira¸c˜ao cooperativa proveniente do esquema t´atico e de movimenta¸c˜ao, adv´em

principalmente de observa¸c˜oes realizadas no futsal. Antigamente, conhecido como futebol

de sal˜ao, o futsal ´e um esporte disputado por duas equipes compostas de 5 jogadores

cada, sendo um deles o goleiro. As equipes possuem como objetivo marcar gols. Para

isso, os jogadores se p osicionam em regi˜oes diferentes do campo, a ﬁm de explorar melhor

o ambiente (trabalho cooperativo). A partida ´e vencida pela equipe que marcar o maior

n´umero de gols durante um per´ıodo de tempo predeterminado.

Fica claro que a quantidade de jogadores em uma equipe de futsal ´e a m´axima per-

mitida na RoboCup f-180 e exatamente a mesma quantidade de robˆos projetados neste

trabalho. Em contrapartida, no futebol de campo uma equip e deve ter 11 jogadores,

sendo um deles o goleiro, o que diferencia completamente a distribui¸c˜ao espacial, com-

portamental e t´atica dos jogadores. O comportamento cooperativo dos jogadores de uma

equipe ´e fundamental para obter bons resultados; a forma como isso acontece no futsal ´e

o que motiva a solu¸c˜ao aqui proposta para o futebol de robˆos.

4.1 ARQUITETURA

A modelagem aqui proposta utiliza arquitetura modular e ﬂex´ıvel, fazendo com que o

robˆo possa ser utilizado em outras aplica¸c˜oes. Vide FIG. 4.1. A arquitetura do sistema

proposto ´e seq¨uencial, por´em n˜ao ´e necess´aria a realiza¸c˜ao de todos os passos (em s´erie)

a cada itera¸c˜ao.

Isso foi constatado na analogia com seres humanos, onde os humanos observam o

ambiente, colhem dados, e somente depois realizam um planejamento, determinando a

a¸c˜ao a ser executada. Considerando que um sistema rob´otico recebe 30 imagens por

segundo do sensor de vis˜ao, com base nessa informa¸c˜ao, implica-se que o sistema deve

responder em aproximadamente 33ms a cada itera¸c˜ao. Assim, foi incorporado um gatilho

ao sistema que aciona o planejamento estrat´egico concorrentemente `a vis˜ao no per´ıodo

T = t segundos. Com isso, possuindo um sistema de vis˜ao robusto, com baixo custo

computacional, pode-se obter imagens da cˆamera e process´a-las com maior freq¨uˆencia,

ao inv´es de deixar ﬁxada a aquisi¸c˜ao de imagens a partir do custo computacional do

FIG. 4.1: Arquitetura do sistema

planejamento estrat´egico e de execu¸c˜ao. A seguir s˜ao descritos os m´odulos do sistema:

A Aquisi¸c˜ao de Imagem ´e feita atrav´es de uma placa digitalizadora ligada a uma

cˆamera, na qual se obt´em as imagens atrav´es de um driver.

A Vis˜ao ´e dividida em 4 (trˆes) sub-m´odulos: i) na calibra¸c˜ao o maior problema de um

sistema de vis˜ao computacional (para o futebol de robˆos) ´e que as cores n˜ao permanecem

iguais em todas as partes do campo; para isso ´e necess´aria a calibra¸c˜ao, realizada oﬄine; ii)

na classiﬁca¸c˜ao de cores somente um n´umero limitado de cores ´e utilizado para identiﬁcar

os objetos e eles devem ser classiﬁcadas por equipe, atribuindo cor diferente para cada

uma delas (azul ou amarelo), e uma cor para a bola (laranjado); iii) a pose dos objetos

consiste em analisar uma imagem obtida na Aquisi¸c˜ao de Imagem e extrair informa¸c˜ao

de posi¸c˜ao e orienta¸c˜ao dos objetos; iv) na identiﬁca¸c˜ao dos objetos, atribui-se um r´otulo

de identiﬁca¸c˜ao a cada objeto.

Planejamento ´e a deﬁni¸c˜ao de ”o que fazer” para realizar a tarefa.

E a etapa que d´a

comportamento para o indiv´ıduo. Divide-se em 2 (dois) sub-m´odulos: i) na previs˜ao de

movimentos o robˆo infere as posi¸c˜oes futuras de todos os objetos m´oveis n˜ao pertencentes

`a sua sociedade, servindo de suporte para a Estrat´egia; ii) estrat´egia ´e o planejamento

das a¸c˜oes futuras. Baseado numa cuidadosa an´alise da posi¸c˜ao dos robˆos, ´e deﬁnido o

objetivo global e em seguida o robˆo deﬁne sua estrat´egia social (objetivo local), podendo

ser cooperativa ou individualista, amarrada ao objetivo global.

A Execu¸c˜ao informa aos robˆos ”como fazer” para executar a tarefa deﬁnida no plane-

jamento.

E realizada a partir de 2 (dois) sub-m´odulos: i) no planejamento de trajet´oria,

dado um robˆo e a descri¸c˜ao de um ambiente, planeja-se uma trajet´oria que seja livre de

colis˜ao; ii) controle s˜ao os comandos que dever˜ao ser enviados ao robˆo para que possa

prover a trajet´oria planejada.

A Comunica¸c˜ao monta os pacotes com os comandos que ser˜ao enviados ao robˆo

atrav´es de radiofreq¨uˆencia conectada a uma interface do computador.

4.2 AQUISIC¸

AO DE IMAGEM

Para Gonzalez (GONZALEZ, 1992), dois elementos s˜ao necess´arios para a aquisi¸c˜ao de

imagens digitais: um dispositivo f´ısico que seja sens´ıvel a uma banda do espectro de energia

eletromagn´etica (raios X, ultravioleta, vis´ıvel ou banda infravermelha) e que pro duza um

sinal el´etrico de sa´ıda proporcional a um n´ıvel de energia percebida; o segundo, chamado

digitalizador, ´e um dispositivo para a convers˜ao da sa´ıda el´etrica de um dispositivo de

sensoreamento f´ısico para a forma digital. O sensor pode ser uma cˆamera (monocrom´atica

ou colorida) que produz uma imagem inteira do dom´ınio do problema a cada

Uma imagem digitalizada ´e um conjunto de valores num´ericos. A resolu¸c˜ao de uma

imagem ´e uma medida b´asica da quantidade de informa¸c˜ao vis´ıvel. A resolu¸c˜ao costuma

ser descrita em termos de h x v, onde h ´e a resolu¸c˜ao horizontal e v a resolu¸c˜ao vertical.

Gomez (GOMEZ, 2004) apresenta o quociente de aspecto, podendo ser 4:3 ou 16:9. Um

quociente de aspecto de 4:3 signiﬁca que sua resolu¸c˜ao vertical ´e

, por exemplo, de

640 =

640

∗ 3 = 480. Assim, cada imagem sendo composta por elementos individuais

conhecidos como pixels (picture elements), tem-se 640x480 pixels e a imagem possui um

total de 640 ∗ 480 = 307.200 pixels.

E importante frisar que quanto maior forem os valores h e v, mais detalhes ser˜ao repre-

sentados em sua forma digital. Entretanto, mais lento ser´a o processamento da imagem.

A quantidade de pixels em uma imagem ´e inversamente proporcional ao tempo de seu

processamento. Encontrar um equil´ıbrio entre detalhamento e tempo de processamento ´e

fundamental para a aplica¸c˜ao.

Gomez (GOMEZ, 2004) acrescenta que a velocidade de processamento das imagens

FIG. 4.2: Saltos no movimento de um robˆo com diferentes taxas de aquisi¸c˜ao de imagens

(GOMEZ, 2004).

no futebol de robˆos ´e um aspecto a ser considerado, j´a que ´e necess´ario manter uma taxa

de processamento suﬁcientemente alta para captar os movimentos dos objetos sem saltos

consider´aveis; assim, durante a movimenta¸c˜ao de um objeto, ´e importante se obter uma

maior quantidade de imagens para ter mais amostras de posi¸c˜oes ocorridas durante a

trajet´oria de um robˆo. Como exemplo, a FIG. 4.2 ilustra diferentes taxas de aquisi¸c˜ao de

imagens.

A cˆamera usada nesse trabalho ´e uma micro-cˆamera CMOS (Complementary Metal

Oxide Semiconductor) com 1 lux e dimens˜oes de 14 x 14mm. Contudo, uma imagem

gerada por chips CMOS ´e tradicionalmente inferior `a correspondente imagem gerada

por chips CCD (Charge Coupled Device). Al´em disso, cˆameras CCD apresentam melhor

resolu¸c˜ao nos tons e luminosidade em rela¸c˜ao ao CMOS. No entanto, o uso de uma cˆamera

CMOS nos testes se justiﬁca pela possibilidade de avaliar o desempenho do sistema em

condi¸c˜oes desfavor´aveis e tamb´em devido `a sua disponibilidade. A placa de captura de

v´ıdeo adotada ´e uma PixelView PlayTV ULTRA PRO capaz de capturar at´e 30 fps com

resolu¸c˜ao m´axima de 720x576 pixels e sistema de cores NTSC M/PAL M/PAL N, adotada

em fun¸c˜ao de seu baixo custo monet´ario de aquisi¸c˜ao.

Para maiores informa¸c˜oes sobre o uso de cˆamera no futebol de robˆos, consultar ”The

Hardware Design Of A Smart Camera For The Robot Soccer Environment” (WILLS,

1999).

FIG. 4.3: Micro-cˆamera CMOS usada nos experimentos.

4.3 VIS

AO COMPUTACIONAL

A Vis˜ao Computacional ´e um conjunto de m´etodos e t´ecnicas capazes de processar e

interpretar imagens. Em termos computacionais, a interpreta¸c˜ao de imagens ´e entendida

como sendo a transforma¸c˜ao da representa¸c˜ao digital de imagem em uma outra estrutura

de dados descrita semanticamente em um contexto qualquer.

Na aplica¸c˜ao do presente trabalho, percorrem-se as imagens capturadas por uma

cˆamera a ﬁm de se identiﬁcar todos os objetos (robˆos e bola), suas respectivas posi¸c˜oes e

as orienta¸c˜oes dos robˆos da equipe controlada. Para isso, ´e necess´ario, antes da partida

come¸car, que um processo de calibra¸c˜ao das cores seja realizado.

Entretanto, ´e necess´ario deﬁnir a superf´ıcie dos robˆos, ou seja, o que ser´a visto pela

cˆamera e conseq¨uentemente processado pela vis˜ao computacional. De acordo com as

regras da RoboCup f-180, ´e obrigat´oria uma circunferˆencia no centro visual do objeto nas

cores amarelo ou azul, que identiﬁcam cada equipe. Isso ´e imut´avel. A circunferˆencia,

al´em de ser obrigat´oria no centro visual dos robˆos, ´e amplamente utilizada no futebol de

robˆos por ser uma forma geom´etrica com facilidades na determina¸c˜ao do seu centr´oide.

Contudo, as demais marca¸c˜oes e a forma em que estar˜ao dispostas s˜ao deﬁnidas por cada

equipe.

Nesse trabalho, a assinatura visual dos robˆos utilizado ´e o triangular. Decidiu-se adot´a-

lo, uma vez que, como visto na revis˜ao de literatura (BRUCE AND VELOSO, 2003), seu

erro ´e baixo e muito pr´oximo do modelo b orboleta. Entretanto, no modelo triangular o

custo computacional ´e menor do que no borboleta.

Por ﬁm, o sistema de vis˜ao deve ser capaz de aceitar uma luminosidade n˜ao uniforme

no campo e, se for o caso, corrigir distor¸c˜oes provocadas pela lente da cˆamera, tendo ao

FIG. 4.4: Modelo n˜ao-linear de um neurˆonio artiﬁcial (HAYKIN, 2001).

mesmo tempo uma boa performance em tempo de execu¸c˜ao, n˜ao prejudicando os demais

m´odulos que comp˜oem o sistema como um todo (NEVES ET. AL., 2004).

4.3.1 CALIBRAC¸

A calibra¸c˜ao ocorre porque uma mesma cor pode variar de acordo com a ilumina¸c˜ao em

diferentes partes do campo de jogo. Esse processo necessita de um professor externo que

ensine, atrav´es de amostras, quais padr˜oes de cores devem ser classiﬁcados com seus res-

pectivos r´otulos (azul e amarelo para as equipes; alaranjado para a bola; ciano, verde

claro e cor-de-rosa claro para as orienta¸c˜oes). Tal processo ´e denominado como apren-

dizado supervisionado e situa-se no campo de aprendizado de m´aquina.

E chamado de

aprendizado supervisionado porque a entrada e a sa´ıda desejada s˜ao fornecidas por um

professor (supervisor) externo.

Haykin (HAYKIN, 2001) diz que aprender ´e equivalente a encontrar uma superf´ıcie, em

um espa¸co multidimensional, que forne¸ca o melhor ajuste para os dados de treinamento,

com o crit´erio de ”melhor ajuste” sendo medido em um sentido estat´ıstico. Tal ponto

de vista ´e a motiva¸c˜ao por tr´as das redes neurais artiﬁciais (RNAs) ou redes neuronais

artiﬁciais.

Goldschmidt e Passos (GOLDSCHMIDT E PASSOS, 2005) acrescentam que, redes

neurais artiﬁciais s˜ao modelos matem´aticos inspirados nos princ´ıpios de funcionamento dos

neurˆonios biol´ogicos e na estrutura do c´erebro. Esses modelos tˆem capacidade de adquirir,

armazenar e utilizar conhecimento experimental e buscam simular computacionalmente

habilidades humanas, tais como aprendizado, generaliza¸c˜ao, associa¸c˜ao e abstra¸c˜ao.

Nas RNAs, n´os (denominados neurˆonios) s˜ao interligados formando uma rede. Haykin

(HAYKIN, 2001) descreve neurˆonio como uma unidade de processamento de informa¸c˜ao

que ´e fundamental para a opera¸c˜ao de uma RNA. A FIG. 4.4 mostra o modelo de um

neurˆonio, que forma a base para o projeto de redes neurais (artiﬁciais). Na FIG. 4.4

identiﬁcam-se trˆes elementos b´asicos do modelo neuronal:

• Um conjunto de sinapses ou elos de conex˜ao, cada uma caracterizada por um peso;

• Um somador para somar os sinais de entrada, ponderadas pelas respectivas sinapses

do neurˆonio;

• Uma fun¸c˜ao de ativa¸c˜ao para restringir a amplitude da sa´ıda de um neurˆonio.

A inspira¸c˜ao original das RNAs vem das estruturas cerebrais. Entretanto, atualmente,

grande parte dos pesquisadores da ´area concorda que RNA difere das estruturas cerebrais.

Uma RNA ´e uma cole¸c˜ao maci¸camente paralela de unidades de processamento, onde as

interliga¸c˜oes formam a inteligˆencia da rede. As principais aplica¸c˜oes das RNAs s˜ao:

• Aproxima¸c˜ao de fun¸c˜oes;

• Previs˜ao de s´eries temporais;

• Classiﬁca¸c˜ao;

• Reconhecimento de Padr˜oes.

A necessidade da calibra¸c˜ao est´a, exatamente, na necessidade de ensinar ao sistema

os padr˜oes de cores que dever˜ao ser reconhecidos. Como supra-citado, as redes neurais,

de acordo com suas caracter´ısticas, s˜ao muito adotadas em aplica¸c˜oes desse tipo.

A estrutura da rede RBF (Radial Basis Function) ´e do tipo de m´ultiplas camadas.

Esse tipo de rede pode ser usada em problemas de aproxima¸c˜ao de fun¸c˜oes, predi¸c˜ao e

classiﬁca¸c˜ao. A rede neural RBF, por trabalhar com fun¸c˜oes de base radial nos neurˆonios

da camada intermedi´aria, faz com que os neurˆonios acab em funcionando como raios de

similaridade. Assim, quando uma amostra de cor n˜ao for classiﬁcada em algum neurˆonio,

signiﬁca que o padr˜ao pertencente a essa amostra ´e desconhecido pela rede, isto ´e, n˜ao

FIG. 4.5: Cubo RGB, adaptado de (SJU, 2005).

foi treinado. Cada camada de uma rede RBF desempenha um papel espec´ıﬁco em seu

comportamento. Segundo Haykin (HAYKIN, 2001), a camada de entrada ´e constitu´ıda

por n´os de fonte (unidades sensoriais) que conectam a rede ao seu ambiente. Na segunda

camada, a ´unica camada oculta da rede, os n´os utilizam fun¸c˜oes de bases radiais, agru-

pando os dados de entrada em clusters. A camada de sa´ıda ´e linear, fornecendo a resposta

da rede ao padr˜ao (sinal) de ativa¸c˜ao aplicado `a camada de entrada. Portanto, a camada

oculta funciona como raios de similaridades e atende `a tarefa de classiﬁca¸c˜ao dos objetos,

uma vez que outras cores, presentes no corpo do robˆo, e n˜ao utilizadas nos treinamentos

ser˜ao encontradas e n˜ao dever˜ao ser classiﬁcadas. Nesse sentido, as cores ensinadas pelo

supervisor ser˜ao utilizadas como conjunto de treinamento em uma RNA de Base Radial

(RBF).

Em rela¸c˜ao `a arquitetura da rede RBF aqui adotada, essa possui 3 entradas, que s˜ao

as representa¸c˜oes das cores no cubo RGB (lado R, comprimento G e altura B), vide FIG.

4.5. De acordo com Gonzalez (GONZALEZ, 1992), o homem enxerga todas as cores como

combina¸c˜oes vari´aveis das trˆes chamadas cores prim´arias: vermelho (R, do inglˆes ”red”),

verde (G, do inglˆes ”green”) e azul (B, do inglˆes ”blue”).

E exatamente no padr˜ao de

cores RGB que as imagens s˜ao capturadas na grande maioria das placas de capturas de

v´ıdeo, incluindo a placa de captura usada nos testes desta disserta¸c˜ao. A camada de sa´ıda

de uma rede RBF ´e comp osta de neurˆonios com fun¸c˜ao de transferˆencia linear (FIG. 4.6).

Entretanto, no intuito de simpliﬁcar a rede RBF e reduzir seu tempo de processamento,

j´a que se trata de um Sistema de Tempo Real (STR), a camada de sa´ıda da rede foi

eliminada, sendo inclu´ıdo, em cada neurˆonio da camada intermedi´aria, um r´otulo que o

associa `a classe ensinada pelo professor, de acordo com suas amostras (FIG. 4.7).

FIG. 4.6: Rede neural RBF.

FIG. 4.7: Rede neural RBF adaptada.

E importante frisar que, no treinamento da rede RBF, apenas as cores da equipes

(controlada e advers´aria) e da bola s˜ao apresentadas `a rede. Assim, as outras cores vistas

pela cˆamera como o verde do campo, o branco das marca¸c˜oes do campo, o preto ou

branco do corpo do robˆo, e as cores de orienta¸c˜ao n˜ao s˜ao ensinadas; pois de acordo com

o algoritmo adotado n˜ao ´e necess´ario o conhecimento desses padr˜oes.

Entretanto, numa RNA, por ser uma rede maci¸camente paralela de unidades de proces-

samento, seu processamento pode n˜ao responder dentro das restri¸c˜oes temporais do sis-

tema. Por isso, foi motivado o uso de outro m´etodo a ﬁm de comparar o desempenho

da RNA RBF. O problema ´e que, de acordo com (NEVES ET. AL., 2004), no espa¸co de

cores RGB, pequenas varia¸c˜oes na luminosidade do campo causam grandes varia¸c˜oes nos

valores R, G e B dos pontos de cada quadro.

Na tentativa de reduzir as nuances provocadas por uma ilumina¸c˜ao heterogˆenea, a

convers˜ao de RGB em outros modelos de representa¸c˜ao de cores ´e comum. Os modelos

de cores mais freq¨uentemente usados para processamento de imagens s˜ao o RGB, YUV

(MART

INEZ-G

OMEZ AND WEITZENFELD, 2004), HSI (LOOMIS ET. AL., 2003) e o

FIG. 4.8: Cone HSV, (NEVES ET. AL., 2004).

FIG. 4.9: Algoritmo de convers˜ao de RGB para HSV.

HSV (NEVES ET. AL., 2004).

Todavia, no espa¸co de cores HSV (FIG. 4.8), onde o H (hue) ´e o matiz, que ´e um ˆangulo

dentre 0 e 359

; S (saturation) ´e um intervalo de zero a 1 de satura¸c˜ao, e V (value) um

valor com o mesmo intervalo da satura¸c˜ao; o matiz de cada cor independe da luminosidade

existente (GONZALEZ, 1992). Assim optou-se pela convers˜ao de RGB para o formato

HSV (FIG. 4.9). Entretanto, os intervalos de S e V adotados aqui neste trabalho s˜ao

de 0 a 255, isso porque, de acordo com o algoritmo de convers˜ao de RGB-HSV, para se

determinar os valores de S e V ´e necess´ario trabalhar com o valor m´aximo da cor RGB.

Assim, ganha-se o tempo de convers˜ao do valor de RGB para o intervalo real de 0 (zero)

a 1. A calibra¸c˜ao dos padr˜oes de cores no formato HSV ´e feita atrav´es da indica¸c˜ao dos

maiores e menores valores de cada canal no seu respectivo padr˜ao de cores. O algoritmo

de classiﬁca¸c˜ao da cores utilizando o espa¸co de cor HSV ´e apresentado em FIG. 4.10.

Em rela¸c˜ao `as cores de orienta¸c˜ao (cor-de-rosa claro, verde claro e ciano), uma outra

rede neural foi utilizada: RNA Multilayer Perceptron (MLP). A arquitetura de uma rede

MLP ´e apresentada na FIG. 4.11. Braga et. al. (BRAGA ET. AL., 2000) descrevem que

FIG. 4.10: Algoritmo de classiﬁca¸c˜ao por HSV.

tanto as redes RBF quanto as redes MLP s˜ao aproximadores universais de fun¸c˜oes, por-

tanto s˜ao redes teoricamente equivalentes. No entanto, existem diferen¸cas entre esses dois

modelos. A primeira diferen¸ca diz resp eito `a parti¸c˜ao do espa¸co de padr˜oes de entrada re-

alizada pela camada intermedi´aria de cada rede. Cada neurˆonio da camada intermedi´aria

de uma rede RBF deﬁne uma hiperelips´oide no espa¸co de padr˜oes de entrada. Assim, uma

rede RBF constr´oi aproximadores locais, isto ´e, apenas as regi˜oes do espa¸co de entrada

que apresentam dados de treinamento ter˜ao respostas da rede. A resp osta de uma fun¸c˜ao

radial (por exemplo a fun¸c˜ao gaussiana) diminui conforme os padr˜oes (pontos do espa¸co

de entrada) se distanciem do centro da fun¸c˜ao radial. A FIG. 4.12 ilustra a parti¸c˜ao dos

dados de entrada realizada por uma rede RBF com quatro neurˆonios na camada inter-

medi´aria. As redes MLP, por outro lado, particionam o espa¸co de entrada atrav´es de

hiperplanos, como pode ser visto na FIG. 4.13 no caso de uma rede com apenas uma

camada intermedi´aria de trˆes neurˆonios.

Braga et. al. (BRAGA ET. AL., 2000) acrescentam ainda uma outra diferen¸ca entre

as redes MLP e RBF: enquanto nas redes MLP o valor de ativa¸c˜ao de uma unidade n

(j -´esimo neurˆonio) da camada interna ´e uma fun¸c˜ao do produto escalar entre o vetor de

entrada e o vetor de pesos da unidade EQ. 4.1, na rede RBF o valor de ativa¸c˜ao ´e dado

em fun¸c˜ao da distˆancia euclidiana entre o vetor de entrada e o vetor centro da unidade

EQ. 4.2.



i=1

+ b

(4.1)

FIG. 4.11: Arquitetura de uma rede MLP t´ıpica com uma camada intermedi´aria.

FIG. 4.12: Particionamento dos dados de entrada realizado por uma rede RBF com quatro

neurˆonios na camada intermedi´aria (BRAGA ET. AL., 2000).

FIG. 4.13: Particionamento dos dados de entrada realizado por uma rede MLP com uma

camada intermedi´aria formada por trˆes neurˆonios (BRAGA ET. AL., 2000).



i=0

σ(||x − µ

||) (4.2)

onde, y

se refere ao sinal funcional que aparece na sa´ıda do neurˆonio j ; m ´e o n´umero

total de entradas aplicadas ao neurˆonio j ; b

´e o bias, e, de acordo com Haykin (HAYKIN,

2001), ele tem o efeito de aumentar ou diminuir a entrada l´ıquida da fun¸c˜ao de ativa¸c˜ao;

as fun¸c˜oes radiais possuem ainda o centro µ e o raio σ.

A rede MLP ´e comumente usada para aplica¸c˜oes de classiﬁca¸c˜ao e aproxima¸c˜ao. Na

tarefa de classiﬁcar as cores de orienta¸c˜ao tem-se como garantia a n˜ao apari¸c˜ao de outros

padr˜oes de cores al´em dos treinados, j´a que a ´area a ser percorrida no robˆo ´e bem deﬁnida.

Assim, as redes MLP, por terem como caracter´ıstica separar as classes em hiperplanos, re-

solve o problema mesmo havendo diferen¸cas de ilumina¸c˜ao no campo. Na rede MLP usada

como classiﬁcador, costuma-se usar sa´ıda maximamente esparsa, onde cada neurˆonio da

camada de sa´ıda corresponde a um padr˜ao a ser reconhecido. Quando n˜ao se utiliza sa´ıda

maximamente esparsa, a classiﬁca¸c˜ao ocorre pela combina¸c˜ao de ativa¸c˜ao dos neurˆonios.

A MLP se justiﬁca diante da RBF, pois, nessa ´ultima, `a medida em que aumenta a he-

terogeneidade da ilumina¸c˜ao, aumenta a quantidade de neurˆonios para representar cada

padr˜ao de cor, aumentando o custo computacional. O algoritmo de treinamento da RNA

MLP implementado foi a Regra Delta (HAYKIN, 2001).

Contudo, para a tarefa de classiﬁca¸c˜ao das cores de orienta¸c˜ao, deve-se ter em mente

que, p or se tratar de um STR, a rede MLP pode n˜ao responder dentro dos limites tem-

porais do. No cap´ıtulo 5 ser˜ao detalhados os resultados do uso da rede MLP.

FIG. 4.14: Algoritmo de classiﬁca¸c˜ao RGB das cores de orienta¸c˜ao.

Por´em, havendo um algoritmo capaz de classiﬁcar eﬁcientemente pelo espa¸co RGB as

cores envolvidas no processo de determinar a orienta¸c˜ao dos robˆos (ciano, verde claro,

cor-de-rosa claro e preto), evita-se a necessidade de convers˜ao para outros espa¸cos de

representa¸c˜ao de cores j´a que a placa de captura obt´em as imagens no espa¸co RGB. O

que reduz o o tempo de processamento do algoritmo.

No entanto, trabalhar com distˆancia no espa¸co RGB com a ﬁnalidade de classiﬁcar as

cores de orienta¸c˜ao n˜ao apresenta bons resultados. Isso ocorre porque a partir de um ´unico

padr˜ao para cada cor, as cores variam muito, j´a que esse modelo de cores ´e muito sens´ıvel

`a varia¸c˜ao de ilumina¸c˜ao e, assim, come¸ca a se confundir os padr˜oes. Todavia, durante

observa¸c˜oes, constatou-se que nas amostras, cada padr˜ao segue uma l´ogica, apesar da

diferen¸ca de ilumina¸c˜ao. Portanto, a partir dessas regras conseguiu-se classiﬁcar as cores

de orienta¸c˜ao mesmo com ilumina¸c˜ao heterogˆenea no campo. O algoritmo implementado

para a tarefa de classiﬁca¸c˜ao ´e apresentado na FIG. 4.14, onde erroCiano, erroRosa e

erroVerde s˜ao vari´aveis de sensibilidade.

Por ﬁm, tamb´em foi adotado o espa¸co de cor HSV para as cores de orienta¸c˜ao a ﬁm de

compar´a-lo, atrav´es de testes (cap´ıtulo 6), em rela¸c˜ao ao erro e tempo de processamento

da RNA MLP e do modelo RGB. A calibra¸c˜ao dos padr˜oes de cores da orienta¸c˜ao em HSV

ocorre da mesma forma que as cores de identiﬁca¸c˜ao dos objetos. As TAB. 4.1 e TAB. 4.2

apresentam os valores dos padr˜oes de cores nos diferentes canais, respectivamente RGB e

HSV.

TAB. 4.1: Padr˜oes de cores em RGB.

TAB. 4.2: Padr˜oes de cores em HSV.

4.3.2 CLASSIFICAC¸

AO DAS CORES

A classiﬁca¸c˜ao das cores ´e a etapa onde os objetos s˜ao identiﬁcados e classiﬁcados como

sendo time controlado, bola ou advers´ario. O algoritmo se inicia utilizando a subtra¸c˜ao

de imagens.

A subtra¸c˜ao de imagens pode ser utilizada como t´ecnica de remo¸c˜ao de padr˜oes n˜ao

desejados presentes na imagem. Existe uma aplica¸c˜ao cl´assica da subtra¸c˜ao de imagens

para realce na ´area de imagens m´edicas chamada radiograﬁa em modo m´ascara. Nesse

caso h(x,y), a m´ascara ´e uma imagem de raios X de uma regi˜ao do corpo do paciente

capturada atrav´es de um intensiﬁcador e cˆamera de TV (em vez de um ﬁlme de raios

X tradicional) localizada em oposi¸c˜ao a uma fonte de raios X. A imagem f(x,y) ´e uma

amostra de uma s´erie de imagens de TV similares, da mesma regi˜ao anatˆomica, mas

adquirida ap´os a inje¸c˜ao de um corante na corrente sang¨u´ınea. O efeito resultante da

subtra¸c˜ao da m´ascara de cada amostra do ﬂuxo das imagens da cˆamara de TV ´e que

apenas as ´areas que s˜ao distintas entre f(x,y) e h(x,y) aparecem na imagem de sa´ıda

como detalhe real¸cado. Como as imagens podem ser capturadas em taxa de v´ıdeo, esse

procedimento essencialmente fornece um ﬁlme mostrando a propaga¸c˜ao do corante atrav´es

das art´erias (GONZALEZ, 1992).

A diferen¸ca entre duas imagens f(x,y) e h(x,y), expressa pela equa¸c˜ao EQ. 4.3, ´e obtida

atrav´es do cˆomputo da diferen¸ca entre todos os pares de pixels correspondentes de f e h.

g(x,y) = |f(x,y) - h(x,y)| (4.3)

No futebol de robˆos, a m´ascara h(x,y) ´e o campo de jogo sem a presen¸ca de qualquer

objeto nele (FIG. 4.15) e f(x,y) s˜ao as amostras capturadas pela cˆamera de v´ıdeo posi-

FIG. 4.15: M´ascara.

FIG. 4.16: Varredura com i pixels no eixo x e j pixels no eixo y.

cionada acima do centro do campo com um taxa de captura deﬁnida, experimentalmente,

de acordo com a velocidade de processamento dela e tamb´em dos demais algoritmos do

sistema.

Contudo, para diminuir o custo computacional, ao inv´es de percorrer cada pixel da

imagem, percorre-se i pixels no eixo x e j pixels no eixo y. Vide ﬁgura FIG. 4.16. Assim,

a EQ. 4.4 determina a porcentagem do total de pixels da imagem que ser´a percorrida,

onde width ´e a amplitude de pixels no eixo x e height a amplitude de pixels no eixo y.

p = 100 *

width

∗

height

width ∗ height

(4.4)

Lembrando que na subtra¸c˜ao de imagens n˜ao se percorre cada pixel da imagem (FIG.

FIG. 4.17: Transforma¸c˜ao em objeto retangular.

4.16.b), tem-se:

(x, y) =



1 se g(x, y) > θ

0 caso contr´ario

(4.5)

onde θ ´e um limiar. Note que m

(x, y) ´e uma matriz bin´aria utilizada como vari´avel

auxiliar para separar os objetos e ´e atribu´ıdo o valor 1 nas coordenadas espaciais (x,y)

apenas se existir uma diferen¸ca apreci´avel entre os n´ıveis de RGB das duas imagens,

determinado pelo limiar θ. A matriz bin´aria ´e alocada com width/i elementos no eixo x

e height/j elementos no eixo y. Todas as posi¸c˜oes da matriz bin´aria s˜ao iniciadas com o

valor 0 (zero).

Finalizada a etapa de subtra¸c˜ao de imagens, a matriz bin´aria est´a com todos os objetos

real¸cados do fundo. O problema ´e que quando objetos est˜ao pr´oximos no espa¸co, eles s˜ao

unidos. Para solucionar esse problema, quando g(x, y) > θ veriﬁca-se atrav´es de um

m´etodo de classiﬁca¸c˜ao se a cor do pixel equivalente `aquele ponto ´e time controlado,

advers´ario, bola ou desconhecido. Sendo o pixel classiﬁcado, s´o ent˜ao se atribui o valor 1

na posi¸c˜ao da matriz bin´aria equivalente `a g(x, y). Note que agora, por causa do corpo

do robˆo vis´ıvel pela cˆamera (cor desconhecida), os objetos n˜ao mais se unir˜ao, real¸cando

apenas as cores de identiﬁca¸c˜ao, isto ´e, os objetos ser˜ao, nesse momento, apenas as cores

de identiﬁca¸c˜ao.

Ent˜ao, os objetos s˜ao transformados em retˆangulos atrav´es dos pontos extremos do

objeto nos eixos x e y (FIG. 4.17). Para eliminar os ru´ıdos, veriﬁca-se os tamanhos dos

objetos. Os objetos com tamanhos improv´aveis s˜ao eliminados. Dos objetos que restaram,

se determina o centro de massa de cada um e o ponto que representa o centr´oide do

retˆangulo (EQ. 4.6) de cada objeto na matriz bin´aria ´e transformado para a escala da

imagem e sua respectiva cor de identiﬁca¸c˜ao (cor da equipe ou da bola) ´e apresentada ao

algoritmo de classiﬁca¸c˜ao de cor de identiﬁca¸c˜ao (RNA RBF ou classiﬁca¸c˜ao no espa¸co

FIG. 4.18: Centr´oide da circunferˆencia.

HSV).

centro

= (x

inicio

+ x

final

)/2 y

centro

= (y

inicio

+ y

final

)/2 (4.6)

4.3.3 POSE DOS OBJETOS

O objetivo deste m´odulo ´e determinar a pose (posi¸c˜ao e orienta¸c˜ao) dos objetos, sendo

que as orienta¸c˜oes em quest˜ao s˜ao somente quanto aos robˆos do time controlado.

A primeira fase desta etapa ´e determinar o centr´oide da circunferˆencia dos objetos a

partir dos pontos determinados na Classiﬁca¸c˜ao das Cores. Inicia-se tra¸cando uma corda

na circunferˆencia em rela¸c˜ao ao eixo x do sistema de coordenadas da cˆamera. No ponto

m´edio da corda tra¸cada no eixo x ´e tra¸cada outra corda, agora em rela¸c˜ao ao eixo y do

sistema de coordenadas da cˆamera. O ponto m´edio ´e o centr´oide da circunferˆencia. Vide

FIG. 4.18.

Entretanto, para tra¸car as cordas a ﬁm de se determinar o seu centro de massa, ´e

necess´ario que o algoritmo conhe¸ca o padr˜ao de cor da circunferˆencia. Tanto a rede RBF

quanto a classiﬁca¸c˜ao por HSV j´a foram calibradas para classiﬁcar os padr˜oes de cores

das equipe e da bola. Assim, esses m´etodos podem ser adotados para determinar o centro

de massa das circunferˆencias que identiﬁcam as equipes e a bola. Contudo, na rede RBF

pode haver mais de um neurˆonio com o mesmo r´otulo, ou seja, representando um mesmo

padr˜ao de cor. Assim, a propaga¸c˜ao da rede est´a relacionada `a quantidade de neurˆonios

e n˜ao `a quantidade de padr˜oes de cores, o que aumenta seu custo computacional. J´a na

classiﬁca¸c˜ao por HSV ´e necess´ario converter o espa¸co de cores RGB para HSV, o que pode

ser desnecess´ario, elevando tamb´em o custo computacional. Outro complicador, ´e que

ser´a necess´ario tamb´em determinar o centr´oide das marcas de orienta¸c˜ao. Sendo assim,

deve-se considerar os algoritmos utilizados para os classiﬁcar. Nesse sentido, motivou-

se a elabora¸c˜ao de um algoritmo gen´erico capaz de se determinar o centr´oide usando

o espa¸co de cores RGB. Para isso, a equa¸c˜ao EQ. 4.7 (onde r, g e b, pixels vizinhos,

s˜ao comparados ao ponto anterior j´a devidamente classiﬁcado) ´e apresentada a ﬁm de se

veriﬁcar se os pontos vizinhos (na corda) e se o desvio ´e menor que um valor toler´avel

de erro, determinado experimentalmente. Adicionalmente, a corda ´e tra¸cada veriﬁcando

a cor pixel a pixel na imagem. O algoritmo implementado para determinar o centro de

massa da circunferˆencia ´e apresentado na FIG. 4.19.

desvio =

|r − r

ant

| + |g − g

ant

| + |b − b

ant

(4.7)

Uma vez determinado o centro de massa dos objetos, as posi¸c˜oes de todos os objetos, j´a

com suas respectivas classiﬁca¸c˜oes (equipe controlada, advers´ario e bola), s˜ao conhecidas.

A segunda fase consiste em determinar as orienta¸c˜oes dos robˆos da equipe controlada. N˜ao

se est´a interessado em encontrar a orienta¸c˜ao dos robˆos advers´arios, j´a que se desconhece

as marca¸c˜oes visuais do advers´ario. No entanto, uma estima¸c˜ao sobre a orienta¸c˜ao da

bola e dos robˆos advers´arios ser´a feita durante o m´odulo Planejamento.

Tendo, a priori, o conhecimento de que as marcas de orienta¸c˜ao dispostas eq¨uidistantes

em rela¸c˜ao ao centro de massa do robˆo e possuem o mesmo diˆametro, conclui-se que

possuem uma distˆancia (d) em rela¸c˜ao ao centr´oide do robˆo igual para todas as marcas.

Assim, percorre-se radialmente a partir do centro de massa do robˆo d pixels.

A classiﬁca¸c˜ao das cores ´e feita utilizando a RNA MLP, classiﬁca¸c˜ao no espa¸co de

cores RGB e no espa¸co HSV. Na MLP, a rede classiﬁca a amostra no padr˜ao em que

ela estiver com a menor distˆancia. Isso se torna poss´ıvel uma vez que as cores contidas

na superf´ıcie dos robˆos s˜ao conhecidas e bem deﬁnidas. A classiﬁca¸c˜ao por RGB utiliza

as regras apresentadas em FIG. 4.14 e com as vari´aveis de sensibiliza¸c˜ao devidamente

calibradas para classiﬁc´a-las. Para que a classiﬁca¸c˜ao por RGB funcione, ´e necess´ario

que a ´area visual dos robˆos obede¸ca `as regras de classiﬁca¸c˜ao da FIG. 4.14, ou seja, que

durante a impress˜ao dos r´otulos as cores ciano, rosa claro e verde claro sejam alteradas.

Dessa forma, o verde claro deve contar obrigatoriamente um valor maior na coordenada

G, o ciano na coordenada B e o rosa claro na coordenada R.

E importante frisar que

essa altera¸c˜ao no padr˜ao de cor n˜ao ´e proibido pelas regras da RoboCup f-180, j´a que

nas regras apenas cita que as cores a serem usadas devem ser ciano, rosa claro e verde

FIG. 4.19: Algoritmo do centr´oide.

claro. O algoritmo de classiﬁca¸c˜ao por HSV ´e igual ao usado na classiﬁca¸c˜ao das cores de

identiﬁca¸c˜ao.

Assim, sempre que se encontrar uma marca de orienta¸c˜ao (cores ciano, verde claro e

cor-de-rosa claro), a fun¸c˜ao que determina o centr´oide da circunferˆencia (descrito anteri-

ormente) ´e requisitada para determinar com maior precis˜ao o ˆangulo de cada marca em

rela¸c˜ao ao centro de massa do robˆo. Note que, ao contr´ario da RNA MLP, na classiﬁca¸c˜ao

por RGB, a cor do corpo do robˆo ´e desnecess´aria, assim como na classiﬁca¸c˜ao por HSV.

Uma vez classiﬁcadas as marcas de orienta¸c˜ao com seus respectivos centr´oides, as poses

dos objetos relevantes est˜ao determinadas.

4.3.4 IDENTIFICAC¸

AO DOS OBJETOS

A identiﬁca¸c˜ao dos robˆos da equipe controlada ´e realizada a partir da combina¸c˜ao de

cores presentes nas marcas de identiﬁca¸c˜ao. Isso faz-se necess´ario uma vez que, de acordo

com a regras, os robˆos podem ser punidos, algumas vezes acarretando a interven¸c˜ao do

´arbitro (humano) na partida. Com isso, o ´arbitro pode, se necess´ario, pegar nos robˆos

o que comprometeria todo o sistema de identiﬁca¸c˜ao caso o r´otulo de todos os robˆos de

uma mesma equipe fosse iguais e, assim, necessariamente ter que utilizar m´etodos de

estima¸c˜ao de movimento para rastre´a-los. Na ﬁgura FIG. 4.20, as combina¸c˜ao utilizadas

para os robˆos da equipe controlada ´e apresentada.

Para a identiﬁca¸c˜ao dos robˆos da equipe advers´aria ´e necess´ario estimar o movimentos

dos robˆos a ﬁm de ”segui-los”, uma vez que n˜ao se conhece suas marca¸c˜oes de identi-

ﬁca¸c˜ao. A estima¸c˜ao de movimento ´e calculada a partir das posi¸c˜oes dos robˆos advers´arios

extra´ıdos da imagem capturada pela cˆamera no instante de tempo t e pelas posi¸c˜oes obti-

das na imagem do tempo t − 1. A partir desses dois pontos, estima-se para todos os robˆos

as posi¸c˜oes no tempo t + 1. As equa¸c˜oes EQ. 4.8 e EQ. 4.9 determinam a estima¸c˜ao de

movimento de um robˆo.

t+1

= x

+ (x

− x

t−1

) (4.8)

t+1

= y

+ (y

− y

t−1

) (4.9)

Uma vez determinada a estima¸c˜ao da posi¸c˜ao de cada robˆo, associa-se a ela um iden-

tiﬁcador num´erico. Na pr´oxima itera¸c˜ao, calcula-se a distˆancia euclidiana de cada robˆo

em rela¸c˜ao aos pontos determinados na estima¸c˜ao de movimento. Em ordem crescente

de distˆancia, identiﬁcam-se os robˆos de acordo com os identiﬁcadores do tempo t. Por

FIG. 4.20: Identiﬁca¸c˜ao dos robˆos.

exemplo, um mesmo robˆo pode estar mais pr´oximo de dois pontos do que os demais robˆos.

No entanto, ele ser´a identiﬁcado apenas com o identiﬁcador do ponto mais pr´oximo em

rela¸c˜ao `a posi¸c˜ao atual do robˆo. Assim, sucessivamente esse processo se repete at´e que

todos os robˆos tenham um identiﬁcador associado.

4.3.5 RESUMO

O algoritmo de vis˜ao computacional se divide em duas etapas que s˜ao apresentadas,

resumidamente abaixo:

• Na etapa oﬄine, um professor ´e necess´ario para realizar os seguintes passos:

– Apresentar amostras das cores das equipe e da bola;

– Apresentar os valores das vari´aveis de sensibiliza¸c˜ao (RGB) ou ainda as amostras

das cores das marcas de orienta¸c˜ao (HSV e RNA MLP) e, se for o caso, do

corpo do robˆo da equipe controlada (RNA MLP);

– Determinar a distˆancia d de uma marca de orienta¸c˜ao em rela¸c˜ao ao centro de

massa do robˆo.

• Etapa online:

– Capturar imagem da cˆamera;

– Percorrer a imagem capturada em intervalos i no eixo x e j no eixo y utilizando

a subtra¸c˜ao de imagens;

– Se o resultado da subtra¸c˜ao for maior que L ent˜ao

∗ Se a cor do pixel ´e de identiﬁca¸c˜ao de objeto (azul, amarelo ou laranjado)

ent˜ao

· Marcar posi¸c˜ao equivalente em uma matriz bin´aria;

– Eliminar objetos improv´aveis (ru´ıdos);

– Retangularizar objetos da matriz bin´aria;

– Determinar o centro de massa dos objetos retangularizados;

– Classiﬁcar a cor que identiﬁca o objeto;

– Determinar as posi¸c˜oes dos objetos (centr´oide da circunferˆencia);

– Percorrer radialmente com d pixels de distˆancia em rela¸c˜ao ao centro de massa

do robˆos da equipe controlada;

∗ Se a cor do pixel for classiﬁcada como de orienta¸c˜ao, ent˜ao

· Determinar o seu centro de massa;

– Determinar as orienta¸c˜oes dos robˆos da equipe controlada;

– Identiﬁcar os robˆos da equipe controlada (combina¸c˜ao de cores);

– Identiﬁcar os robˆos advers´arios (estima¸c˜ao de movimento).

4.4 PLANEJAMENTO

Aplicar com eﬁc´acia as informa¸c˜oes provenientes da vis˜ao na tentativa de explorar condi¸c˜oes

favor´aveis ´e o que rege o planejamento estrat´egico. Para isso, neste trabalho, o planeja-

mento ´e divido em trˆes partes, s˜ao elas: previs˜ao de movimento, objetivo global e objetivo

local.

4.4.1 PREVIS

AO DE MOVIMENTO

Para auxiliar o planejamento estrat´egico, ´e adotado um algoritmo de previs˜ao da posi¸c˜ao

futura dos objetos n˜ao pertencentes `a equipe controlada (robˆos advers´arios e bola).

FIG. 4.21: Previs˜ao de posi¸c˜ao futura para a bola.

FIG. 4.22: Previs˜ao de posi¸c˜ao futura para um robˆo advers´ario.

Foi deﬁnido, para a aplica¸c˜ao de futebol de robˆos, que o c´alculo da previs˜ao de posi¸c˜ao

futura da bola e dos robˆos advers´arios ´e feito atrav´es de 2 pontos observados em instantes

pr´oximos de tempo (t e t − i). Vide FIG. 4.21 e FIG. 4.22 respectivamente. A n˜ao

utiliza¸c˜ao de um polinˆomio na previs˜ao justiﬁca-se uma vez que n˜ao h´a garantias de que

a previs˜ao se concretize em um jogo e tamb´em porque o custo computacional ´e maior, o

que pode prejudicar as restri¸c˜oes temporais do sistema.

Tendo em vista que os 2 pontos escolhidos (t e t-i) est˜ao pr´oximos no tempo e, con-

seq¨uentemente, pr´oximos no espa¸co, optou-se por adotar uma reta, pois ela obt´em re-

sultados satisfat´orios para a aplica¸c˜ao com baixo custo computacional. Vale acrescentar

ainda que encontrar a posi¸c˜ao futura, al´em dos pontos, necessita-se da velocidade dos

objetos, que ´e calculado atrav´es da distˆancia em pixels dos pontos em rela¸c˜ao ao tempo.

4.4.2 OBJETIVOS

Uma vez calculada a previs˜ao de movimento, passa-se ao planejamento estrat´egico, que

´e a fase mais importante no comportamento social dos robˆos. Durante o planejamento,

os objetivos globais e locais s˜ao analisados a ﬁm de se determinar o comportamento

cooperativo dos robˆos.

Contudo, entender os tipos de jogos envolvidos ´e fundamental para deﬁnir boas es-

trat´egias como solu¸c˜ao do problema. Existem 2 jogos envolvidos na aplica¸c˜ao de futebol

de robˆos: jogo das equipes (objetivo global) e o jogo entre os jogadores de uma mesma

equipe (objetivos locais).

4.4.2.1 OBJETIVO GLOBAL

N˜ao basta somente reconhecer que os jogadores se envolvem em processos de intera¸c˜ao

estrat´egica, mas ´e necess´ario tamb´em modelar esses processos e analis´a-los, procurando

determinar as poss´ıveis conseq¨uˆencias dessas intera¸c˜oes. Assim, ´e primordial entender o

jogo em quest˜ao.

O objetivo do jogo das equipes ´e fazer com que um determinado jogador (equipe)

consiga fazer mais gols do que levar. Desse modo, os resultados prefer´ıveis, por ordem

decrescente, s˜ao:

• Ganhar;

• Empatar;

• Perder.

No jogo que envolve as equipes existem 2 jogadores: a equip e controlada e a equipe

advers´aria. Cada jogador tem um certo n´umero de a¸c˜oes dispon´ıveis e essas a¸c˜oes formam

o seu conjunto de a¸c˜oes. Um jogador e suas a¸c˜oes s˜ao representadas por meio de sub´ındices.

Cada jogador ´e identiﬁcado por um sub´ındice j, onde j = 1, 2, o conjunto de a¸c˜oes do

j-´esimo jogador lista todas as a¸c˜oes dispon´ıveis para aquele jogador e ser´a representado

da seguinte forma: C

= {c

}. O que signiﬁca que o conjunto de a¸c˜oes C

tem como seus

elementos todas as a¸c˜oes dispon´ıveis para o jogador j.

Inicialmente, devem-se deﬁnir os poss´ıveis estados de ambas as equipes. Nesse caso,

a cada tipo de estado emerge uma variante do jogo das equipes, j´a que os objetivos

passam a ser distintos. Nesse sentido, mesmo entendendo que podem haver outros estados

(dependendo do ponto de vista de quem o analisa), interpretou-se que esses outros estados

n˜ao s˜ao nada mais do que varia¸c˜oes de dois estados b´asicos que as equipes podem assumir:

• COM BOLA - onde o objetivo ´e fazer gol;

• SEM BOLA - o objetivo ´e n˜ao tomar gol.

Os parˆametros utilizados para se determinar o estado de uma equipe s˜ao:

• Distˆancia euclidiana dos robˆos em rela¸c˜ao `a bola;

• Velocidade dos robˆos;

• Velocidade da bola.

Contudo, conhecer o conjunto de a¸c˜oes de cada jogador (equipe) ´e um passo essen-

cial na an´alise de um processo de intera¸c˜ao estrat´egica. As possibilidades de intera¸c˜ao

estrat´egica dependem do conjunto de a¸c˜oes que est˜ao disp on´ıveis para os jogadores. As

estrat´egias (todas as escolhas que um jogador pode fazer em um dado momento do jogo)

dos times no jogo das equipes s˜ao:

• ATACAR;

• DEFENDER.

O jogador 1 ser´a identiﬁcado como sendo da equipe controlada e o jogador 2 como

equipe advers´aria. Assim, o conjunto de a¸c˜oes para os jogadores s˜ao apresentadas como

= {atacar, defender}, C

= {atacar, defender}.

Para a TJ, uma estrat´egia s

´e a ado¸c˜ao pelo jogador j de uma a¸c˜ao ou um plano de

a¸c˜oes pertencentes ao seu conjunto de a¸c˜oes C

em todos os momentos em que ele dever´a

decidir o que fazer.

Conjunto de estrat´egias ´e formado por todas as estrat´egias que cada jogador disp˜oe.

De forma gen´erica, s

´e a i-´esima estrat´egia do jogador j, o conjunto de estrat´egias do

jogador j ´e dado por S

= {s

Dessa forma, representa-se o conjunto de estrat´egias por meio de um conjunto or-

denado, em que cada elemento ´e uma estrat´egia para cada um dos n jogadores, S =

, s

, ..., s

) onde j = 1, ..., n.

Assim, sabendo que o jogo das equipes ´e composto por 2 jogadores, s

´e uma dada

estrat´egia do jogador equipe controlada e s

´e uma dada estrat´egia do jogador equipe

advers´aria. O conjunto de estrat´egias dos jogadores 1 e 2 ´e apresentado a seguir:

= (AT ACAR, AT ACAR) S

= (AT ACAR, AT ACAR)

= (AT ACAR, DEF ENDER) S

= (AT ACAR, DEF ENDER)

= (DEF ENDER, AT ACAR) S

= (DEF ENDER, AT ACAR)

= (DEF ENDER, DEF ENDER) S

= (DEF ENDER, DEF ENDER)

Entretanto, cada combina¸c˜ao de estrat´egia produz recompensas diferentes para os jo-

gadores. A fun¸c˜ao de recompensa de um jogador j ´e representada por U

, s

, ..., s

A fun¸c˜ao de recompensa denota que a recompensa que o jogador j recebe quando o jo-

gador 1 adota a estrat´egia s

, o jogador 2 adota a estrat´egia s

etc., at´e o n-´esimo jogador,

incluindo a ado¸c˜ao da estrat´egia s

pelo jogador j. Assim, monta-se de acordo com a TAB.

4.3 as fun¸c˜oes de recompensas para o jogo das equipes (a explica¸c˜ao sobre as os valores

das recompensas ´e apresentada adiante):

(AT ACAR, AT ACAR) = 3 U

(AT ACAR, AT ACAR) = 0

(AT ACAR, DEF ENDER) = 2 U

(DEF ENDER, ATACAR) = 1

(DEF ENDER, ATACAR) = 1 U

(AT ACAR, DEF ENDER) = 2

(DEF ENDER, DEF ENDER) = 0 U

(DEF ENDER, DEF ENDER) = 0

De posse do conjunto de a¸c˜oes dos respectivos jogadores e de acordo com os tipos de

jogos, apresentado no cap´ıtulo 3, o jogo das equipes ´e classiﬁcado a seguir:

• Jogo de estrat´egia - h´a a necessidade de planejar estrategicamente as a¸c˜oes a serem

adotadas durante o jogo.

• Soma-zero - a vit´oria de uma equipe (+1) implica na derrota da outra (-1) ou em

caso de empate nenhuma equipe sai ganhando ou perdendo (0).

• Dinˆamico - a intera¸c˜ao estrat´egica acontece mais de uma vez.

• Movimenta¸c˜ao simultˆanea - as decis˜oes estrat´egicas ocorrem simultaneamente, para

os jogadores.

• Informa¸c˜ao completa - cada jogador conhece os objetivos dos demais jogadores e

qual a importˆancia relativa que os demais jogadores concedem aos seus objetivos,

assim, as recompensas dos jogadores s˜ao de conhecimento comum.

• Informa¸c˜ao imperfeita - n˜ao h´a conhecimento do hist´orico do jogo.

Por se tratar de um jogo de soma-zero, a competi¸c˜ao ´e direta e por isso a coopera¸c˜ao

n˜ao existe. Desta forma, no objetivo global da equipe a democracia tamb´em inexiste. No

futebol de humanos, as estrat´egias s˜ao pr´e-deﬁnidas por um treinador. Analogamente,

no futebol de robˆos as estrat´egias das equipes (objetivo global) devem ser determinadas

previamente. Para isso, ´e realizada a an´alise dos poss´ıveis estados das equipes assumirem:

COM BOLA (quando um robˆo da sociedade controlada est´a mais pr´oximo da bola do

que qualquer outro robˆo da sociedade rival no instante t+i); e SEM BOLA (quanto um

robˆo da sociedade rival est´a mais pr´oximo da bola do que qualquer robˆo da sociedade

controlada no instante t+i). Em ambos os estados, o jogador pode ATACAR (tentar se

posicionar no campo do advers´ario) ou DEFENDER (tentar se manter na sua faixa do

campo). A combina¸c˜ao das estrat´egias das equipes gera recompensas diferentes. Assim,

estabeleceu-se os valores 0,1,2,3 para as recompensas das estrat´egias.

Ao avaliar a melhor estrat´egia, cada jogador deve considerar todas as a¸c˜oes que estejam

dispon´ıveis para ele e para os demais jogadores. O m´etodo mais simples de an´alise e

determina¸c˜ao dos resultados de um jogo simultˆaneo de informa¸c˜ao completa ´e atrav´es

da elimina¸c˜ao iterativa de estrat´egias estritamente ou fortemente dominadas (FIANI,

2004). Uma estrat´egia ´e estritamente dominada para o jogador j se houver uma estrat´egia

alternativa que conduza o jogador a um retorno maior, quaisquer que sejam as escolhas

dos outros jogadores. As estrat´egias dos demais jogadores s˜ao representadas como s

−j

(o sub´ındice -j signiﬁca que est´a se tratando das estrat´egias de todos os jogadores que

n˜ao j). Seja Π

a fun¸c˜ao de recompensa do jogador j, que especiﬁca uma recompensa

para o jogador j em rela¸c˜ao `as estrat´egias que ele e os outros jogadores adotam. Se um

jogador possui uma estrat´egia estritamente ou fortemente dominada, sendo ele racional,

´e de se esperar que ele nunca a utilize. Nesse sentido, se uma dada estrat´egia do jogador

j, denominada s



, ´e fortemente dominante para esse jogador, tem-se a EQ. 4.10.

Π(s



, s

−j

) > Π(s

, s

−j

), para todo s

e todo s

−j

(4.10)

Essa desigualdade representa o fato de que a recompensa proporcionada por s



jogador j ´e estritamente superior `as recompensas proporcionadas por qualquer outra es-

trat´egia que j possa adotar, quaisquer que sejam as estrat´egias adotadas pelos demais

jogadores, ou seja, uma estrat´egia ´e estritamente dominante para o jogador j se for aquela

que maximiza os seus retornos, quaisquer que sejam as escolhas dos outros jogadores

Lembrando que o jogo das equipes por ser um jogo de movimenta¸c˜ao simultˆanea ´e

melhor visualizado pela forma normal (deﬁnida no cap´ıtulo 3), a TAB. 4.3 apresenta as

recompensas do jogo quando a equipe A est´a no estado COM BOLA. Caso A e B decidam

ATACAR, ser´a a melhor situa¸c˜ao poss´ıvel para A e a pior para B, pois A est´a com a posse

de bola no campo de defesa do advers´ario, enquanto B vai ATACAR, no campo de defesa

de A. Desta forma, as recompensas para A e B ser˜ao 3 e 0 respectivamente.

TAB. 4.3: Recompensas do jogo quando a Sociedade A est´a no estado COM BOLA

Se A e B se postarem a ﬁm de DEFENDER, o jogo n˜ao vai se desenvolver e assim

estagnar, o que n˜ao interessa a nenhuma das equipes. Para essa situa¸c˜ao, as recompensas

s˜ao 0 e 0.

Quando A decide ATACAR e B DEFENDER, A ainda estar´a em vantagem, mas B

estar´a em situa¸c˜ao melhor do que se fosse ATACAR, j´a que no estado DEFENDER ele

tenta resistir ao ATAQUE de A. Conseq¨uentemente a recompensa de A n˜ao ser´a igual ao

caso onde B decidiu atacar. Assim, as recompensas de A e B s˜ao 2 e 1 respectivamente.

O ´ultimo caso, ´e quando A decide DEFENDER e B decide ATACAR, pressionando

A. Essa situa¸c˜ao ´e mais perigosa para A do que para B, pois B est´a pressionando A, que

est´a com a bola em seu campo. Se A perder a bola, h´a uma grande probabilidade de

tomar um gol e se A conseguir ATACAR, B ainda ter´a tempo de se defender. Assim, as

recompensas nessa situa¸c˜ao para A e B s˜ao 1 e 2 respectivamente.

Na TAB. 4.3 pode ser observado que a estrat´egia ATACAR ´e dominante em rela¸c˜ao

`a estrat´egia DEFENDER (EQ. 4.11), uma vez que se a sociedade B decidir ATACAR,

´e melhor para A ir ATACAR e se B decidir se DEFENDER, tamb´em ´e melhor para A

ATACAR. Assim, independente da estrat´egia adotada por B, ´e sempre melhor para A

ATACAR.

Π(s



, s

−1

) > Π(s

, s

−1

)

Π(AT ACAR, ATACAR) = 3 > Π(DEF ENDER, ATACAR) = 1

Π(AT ACAR, DEF ENDER) = 2 > Π(DEF ENDER, DEF ENDER) = 0 (4.11)

A TAB. 4.4 apresenta as recompensas do jogo quando a sociedade A est´a no estado

SEM BOLA. A matriz de recompensa ´e montada similarmente `a matriz do estado COM

BOLA. Nesse estado, n˜ao h´a estrat´egia dominante para A (EQ. 4.12), por´em, o Equil´ıbrio

de Nash diz que cada jogador deve dar a melhor resposta `a a¸c˜ao que ele espera que venha a

ser adotada pelo outro. Como j´a visto, a sociedade B sendo um agente racional e estando

no estado COM BOLA, ela ´e incentivada a ATACAR. Com isso, o Equil´ıbrio de Nash do

jogo das equipes ´e (DEFENDER,ATACAR), na vis˜ao da equipe que est´a SEM BOLA.

Contudo, se ap´os um certo per´ıodo de observa¸c˜ao (deﬁnido experimentalmente) a equipe

B n˜ao ATACAR, A deve ATACAR, alterando, assim, as recompensas de A e B.

Π(AT ACAR, ATACAR) = 0 < Π(DEF ENDER, ATACAR) = 1

Π(AT ACAR, DEF ENDER) = 2 > Π(DEF ENDER, DEF ENDER) = 0 (4.12)

TAB. 4.4: Recompensas do jogo quando a Sociedade A est´a no estado SEM BOLA

Diante das an´alises feitas atrav´es da TJ se extraem as regras determinantes do objetivo

global do sistema. Como as regras s˜ao informa¸c˜oes conhecidas previamente, os robˆos,

quando estiverem em competi¸c˜ao, ter˜ao esse conhecimento comum e atrav´es dele o objetivo

local dever´a ser determinado. As regras s˜ao apresentadas na FIG. 4.23.

No entanto, a partir da deﬁni¸c˜ao do estado da equipe, uma estrat´egia entre duas a¸c˜oes

´e deﬁnida, podendo ser ATACAR ou DEFENDER. Mas o que os robˆos entendem por

ATACAR ou DEFENDER?

Como j´a havia sido antecipado na introdu¸c˜ao, o futsal de humanos ´e o jogo que mais

inspirou esse trabalho. Sendo assim, deve-se compreendˆe-lo melhor. Em futsal, a es-

quematiza¸c˜ao de jogo ´e fator preponderante em uma equipe, pois sem essa atividade, n˜ao

FIG. 4.23: Algoritmo para determinar a estrat´egia global

se ter´a uma equipe e sim um grupo de elementos que estar˜ao praticando um esporte sem

um objetivo espec´ıﬁco. T´atica nada mais ´e do que a teoria (t´ecnica) colocada em pr´atica

na quadra de jogo (SOFUTSAL!, 2005).

Basicamente, essas estrat´egias, ATACAR e DEFENDER, deﬁnem um esquema t´atico

que os robˆos dever˜ao assumir socialmente. Existem v´arios esquemas poss´ıveis no futsal

como 3-1, 2-2, 1-2-1, 4-0, todos da mais alta importˆancia desde que sejam bem aplicados

(FUTSAL BRASIL, 2005). Para entender a numera¸c˜ao expressa na nomenclatura dos

esquema t´aticos, precisa-se saber que isso corresponde `a quantidade de jogadores em cada

posi¸c˜ao, iniciando pela defesa. Por exemplo: no 4-0, s˜ao 4 jogadores de defesa e nenhum

jogador de ataque; no 1-2-1, 1 jogador defende, 2 ﬁcam no meio e 1 no ataque. Cada uma

dessas t´aticas deﬁnem o que cada jogador deve fazer no decorrer do jogo.

De acordo com as caracter´ısticas dos robˆos projetados, deﬁniu-se adotar duas t´aticas,

uma para ATACAR e outra para DEFENDER. Para a equipe ATACAR, sabendo que

n˜ao h´a dispositivo de passe nos robˆos projetados neste trabalho, apenas de chute, a t´atica

adota ´e a 2-2. Nesse esquema t´atico, o posicionamento dos robˆos s˜ao: 2 em defesa (um

ala e o ﬁxo) e 2 em ataque (um ala e o pivˆo). Apesar de n˜ao haver dispositivo de passe,

´e interessante 1 jogador apoiar ofensivamente o que est´a com a bola, pois a bola pode,

por exemplo, em um chute sobrar pr´oxima ao gol. Esse robˆo ”apoiador” tamb´em pode

cooperar diretamente com o que est´a com a bola.

A t´atica deﬁnida para se DEFENDER ´e o esquema 3-1, onde 3 robˆos defendem (os alas

e o ﬁxo) e apenas 1 robˆo se posiciona ofensivamente (pivˆo). No esquema 3-1 as posi¸c˜oes

de cada jogador s˜ao pr´e-determinadas, onde cada qual desenvolver´a a sua fun¸c˜ao, mas

nunca ﬁcando restrito a um posicionamento ﬁxo.

E um esquema onde a equipe, em

determinados momentos da partida, o utilizar´a para evitar o crescimento do advers´ario

e conseq¨uentemente a marca¸c˜ao de gols por parte dele. Complementarmente, oferece

a possibilidade do contra-ataque (SOFUTSAL!, 2005).

E interessante complementar que

outras t´aticas podem ser assumidas, levando em considera¸c˜ao apenas a mudan¸ca de fun¸c˜ao

de cada jogador em rela¸c˜ao a ela.

4.4.2.2 OBJETIVO LOCAL

Enquanto a fun¸c˜ao do objetivo global ´e determinar a estrat´egia da equipe, o objetivo local

serve para determinar a a¸c˜ao e a pose do objetivo de cada robˆo da equipe controlada.

O jogo entre jogadores de uma mesma equipe ´e uma tarefa fortemente acoplada. Isso

porque um ´unico robˆo n˜ao ´e capaz de atacar, defender e, sozinho, criar condi¸c˜oes favor´aveis

durante o jogo, mesmo porque, de acordo com as regras da RoboCup f-180, uma equipe

deve possuir no m´aximo 5 robˆos, sendo um o goleiro, o que n˜ao torna poss´ıvel solucionar

o problema com apenas um robˆo.

De acordo com os tipos de jogos, apresentados no cap´ıtulo 3, o jogo entre jogadores

de uma mesma equipe ´e classiﬁcado como:

• Jogo de estrat´egia;

• Soma n˜ao-zero;

• Cooperativo;

• Dinˆamico;

• Movimenta¸c˜ao seq¨uencial;

• Informa¸c˜ao completa;

• Informa¸c˜ao imperfeita;

Assim, pode-se notar que esse jogo difere em rela¸c˜ao ao jogo das equipes por ser um

jogo de soma n˜ao-zero.

E exatamente nesses jogos que a coopera¸c˜ao pode emergir. Se

os jogadores podem estabelecer compromissos e esses compromissos possuem garantias

efetivas, diz-se que o jogo ´e cooperativo.

A principal diferen¸ca da ab ordagem utilizada neste trabalho est´a, de acordo com

observa¸c˜oes feitas, no fato de que apesar de o jogo ser de movimenta¸c˜ao simultˆanea,

acredita-se que a tomada de decis˜ao ´e seq¨uencial. Entretanto, diversos trabalhos tratam

esse jogo como simultˆaneo (BOWLING AND VELOSO, 2003) (IKENOUE ET. AL., 2002)

(MARTINEZ AND BRENA, 2005) (TAKAHASHI ET. AL., 2005). A tomada de decis˜ao

seq¨uencial foi constatada em partidas de futsal, onde cada jogador revˆe sua estrat´egia de

acordo com a possibilidade de contribui¸c˜ao cooperativa na jogada. Por exemplo, o robˆo

com maior inﬂuˆencia na jogada s´o considera as estrat´egias dos robˆos que podem contribuir

consigo. Os robˆos que cooperam com o robˆo mais inﬂuente analisa as estrat´egias dos

robˆos que podem cooperar com ele e assim por diante. Entende-se por maior inﬂuˆencia

na jogada, sendo o robˆo que est´a com a bola, caso a equipe esteja com a bola, ou o jogador

com maiores condi¸c˜oes de roubar a b ola da equip e advers´aria ou impedir um ataque. A

informa¸c˜ao de jogo simultˆaneo, que adv´em da TJ, ´e muito importante e demonstra a

necessidade de entender o jogo em quest˜ao. Isso muda a forma de enxergar o problema,

reﬂetindo, por conseq¨uˆencia, na sua resolu¸c˜ao.

As posi¸c˜oes t´aticas a serem desempenhadas pelos robˆos independem do esquema t´atico

adotado pela equipe. Diversos autores tentam deﬁnir as posi¸c˜oes dos jogadores no futsal.

Todavia, adotou-se as deﬁni¸c˜oes de Voser (VOSER, 2001) por serem amplamente aceitas:

• Goleiro - respons´avel por defender e impedir que a bola ultrapasse a linha de gol;

• Fixo - sua fun¸c˜ao b´asica ´e defensiva, este jogador tamb´em deve ter um bom senso

de cobertura;

• Alas (direito e esquerdo) - s˜ao os respons´aveis pela constru¸c˜ao das jogadas e tˆem a

tarefa de marcar e atacar;

• Pivˆo - Quando acionado exerce as a¸c˜oes de ﬁnaliza¸c˜ao e de abrir espa¸cos na ´area

advers´aria para a penetra¸c˜ao de seus companheiros.

Vistas as posi¸c˜oes dos jogadores e suas respectivas fun¸c˜oes, transferindo-se do futsal

para o futebol de robˆos, as ´areas de atua¸c˜ao de cada robˆo s˜ao apresentadas na FIG. 4.24.

No entanto, a t´atica de jogo p ode e deve variar durante o transcorrer da partida de

futsal. A troca de posi¸c˜oes entre os jogadores, conhecida como rota¸c˜ao, ´e uma das maiores

caracter´ısticas do futsal. A rota¸c˜ao ocorre primeiramente para tentar abrir espa¸co a ﬁm

FIG. 4.24: Supondo que o campo de defesa ´e o lado esquerdo, as ´areas de atua¸c˜oes das

posi¸c˜oes dos jogadores em campo, real¸cada na cor cinza, s˜ao apresentadas: (a) goleiro;

(b) ﬁxo; (c) ala esquerdo; (d) ala direito; (e) pivˆo.

de penetrar no campo do advers´ario e tamb´em para dar maiores condi¸c˜oes ofensivas e

defensivas a uma equipe.

A FIG. 4.25 ´e uma seq¨uˆencia de imagens capturadas da partida disputada entre Brasil

e Espanha, v´alida pela semi-ﬁnal da Copa do Mundo de Futsal Fifa, ocorrida em 2004

e transmitida pelo canal de televis˜ao espanhol EuroSport. Na ﬁgura, pode-se constatar

diversas rota¸c˜oes. A seq¨uˆencia das imagens inicia-se (a) com o jogador identiﬁcado como

1 com a bola e na posi¸c˜ao de ﬁxo, o 2 como ala esquerdo, o 3 como ala direito e o 4 como

pivˆo. Observe que todos os jogadores sempre olham para o jogador com maior inﬂuˆencia

na jogada (nessa imagem o jogador 1 por estar com a bola) na espera de que ele tome sua

decis˜ao para, enﬁm, os demais reverem suas estrat´egias.

Na pr´oxima imagem (b), o jogador 1 passa a bola para o jogador 3. Ao receber (c), o

jogador 3 come¸ca a se movimentar para o centro do campo de jogo e imediatamente ao

observar isso, o jogador 1 que est´a no centro, parte para o ataque a ﬁm de liberar o espa¸co

que o jogador 3 procura (d) e ainda o jogador 4 parte para ocupar a antiga posi¸c˜ao do

jogador 3. Repare agora (e) que houve a troca de posi¸c˜oes, onde o jogador 3 passou a ser

o ﬁxo, o jogador 1 o pivˆo e o jogador 4 o ala esquerdo.

Na seq¨uˆencia, o jogador 3 passa a bola para o jogador 2 e parte para o ataque (f). No

entanto, na seq¨uˆencia (g) o jogador 2 n˜ao se posicionou ocupando o espa¸co deixado pelo

jogador 3 e esse jogador revˆe sua decis˜ao e volta a ocupar sua antiga posi¸c˜ao. O jogador 2

ent˜ao passa a bola para o jogador 4 e parte para o ataque (h). Nesse momento o jogador 3

volta para ocupar a regi˜ao antes ocupada pela 2 (i). Note novamente a rota¸c˜ao (j), agora

o jogador 2 ´e o pivˆo, o jogador 3 o ﬁxo e os jogadores 1 e 4 os alas esquerdo e direito,

respectivamente.

Seguindo (k), o jogador 4 passa a bola para o jogador 1 e parte para o ataque (l).

Continuando, o jogador 1 passa a bola para o jogador 3 (m) e novamente h´a a troca de

posi¸c˜oes (n). O jogador 1 se torna o ﬁxo, o 2 ala esquerdo, 3 ala direito e o 4 pivˆo (o).

O jogador 4 se reposiciona (voltando), o jogador 3 passa a bola para o 2 e se reposiciona

para ocupar o espa¸co do 4 (p), ocorrendo troca de posi¸c˜ao entre eles (q). Por ﬁm, o

jogador 3, agora pivˆo, est´a livre e aguarda a decis˜ao do jogador 2, se este vai passar a

bola, caminhar ao gol ou chut´a-la (r).

Como visto na FIG. 4.25, o futsal ´e um jogo dinˆamico, assim como o futebol de robˆos.

No entanto, devido `as restri¸c˜oes f´ısicas dos robˆos, as caracter´ısticas de comportamento do

futsal provenientes da capacidade de passar a bola ser˜ao ignoradas, uma vez que os robˆos

FIG. 4.25: Posi¸c˜oes dos jogadores em campo: (a) goleiro; (b) ﬁxo; (c) ala esquerdo; (d)

ala direito; (e) pivˆo.

projetados neste trabalho n˜ao possuem dispositivo de passe.

Desta forma, a distribui¸c˜ao dinˆamica de posi¸c˜ao entre os jogadores, ou seja, a rota¸c˜ao

do futsal ser´a inserida no contexto do futebol de robˆos sem considerar passes. Comple-

mentarmente, a troca de posi¸c˜oes ocorrer´a apenas entre posi¸c˜oes com interse¸c˜ao em suas

´areas de atua¸c˜ao. Com isso, a rota¸c˜ao aqui possibilita ao ﬁxo tornar-se ala (direito ou

esquerdo) e vice-versa, bem como ao pivˆo ser ala (direito ou esquerdo) e a qualquer um

dos alas ser pivˆo ou ainda a troca de posi¸c˜oes entre os alas. Por´em, pela deﬁni¸c˜ao da

´area de atua¸c˜ao de cada posi¸c˜ao, n˜ao h´a troca entre o ﬁxo e o pivˆo, uma vez que n˜ao h´a

interse¸c˜ao em suas ´areas de atua¸c˜ao. Para o ﬁxo se tornar pivˆo, primeiramente ele deve

trocar de posi¸c˜ao com um dos alas. Note ainda que o goleiro nunca troca de posi¸c˜ao.

Uma vez deﬁnido o esquema t´atico da equipe, cada robˆo exerce uma fun¸c˜ao distinta de

acordo com sua posi¸c˜ao. Para isso, deﬁniram-se 3 estados poss´ıveis de um robˆo assumir

independente do estado da equipe. S˜ao eles:

• L´ıder;

• Coopera¸c˜ao;

• Individual.

Deﬁnidos os estados dos robˆos, torna-se necess´ario estabelecer as a¸c˜oes que cada jo-

gador poder´a executar. Toda a¸c˜ao possui um algoritmo associado. As a¸c˜oes poss´ıveis com

a equipe no estado COM BOLA (esquema t´atico 2-2) s˜ao:

• Chutar (l´ıder) - apenas o l´ıder;

• Caminhar ao gol (l´ıder) - apenas o l´ıder, exceto o goleiro.

• Interceptar advers´ario (coopera¸c˜ao) - qualquer robˆo, exceto o goleiro;

• Apoiar ataque (coopera¸c˜ao) - apenas os alas e o pivˆo;

• Reposicionar (individual) - qualquer robˆo.

No entanto, quando a equipe est´a no estado SEM BOLA, as a¸c˜oes dos jogadores n˜ao

s˜ao as mesmas do estado COM BOLA. Assim, as poss´ıveis a¸c˜oes para o estado SEM

BOLA (esquema t´atico 3-1) s˜ao:

• Dar combate (l´ıder) - somente o l´ıder, sempre no advers´ario que est´a com a bola;

• Marcar robˆo (coopera¸c˜ao) - somente os alas (direito e esquerdo), sempre no ad-

vers´ario no seu campo de defesa mais pr´oximo ao gol e a ele;

• Reposicionar (individual) - qualquer robˆo dentro de sua ´area de atua¸c˜ao.

De acordo com o que foi visto at´e o momento e respeitando as ´areas de atua¸c˜ao, ´e

poss´ıvel deﬁnir as caracter´ısticas de cada posi¸c˜ao na estrat´egia aqui adotada no futebol

de robˆos:

• O goleiro somente se reposiciona. Assim, nunca troca de posi¸c˜ao e nem coopera.

• O ﬁxo se reposiciona quando a equipe estiver sem a bola e algum ala puder dar

combate, sen˜ao o ﬁxo deve dar combate. Quando a equipe est´a com a bola, o ﬁxo

se reposiciona e intercepta o advers´ario, se houver condi¸c˜oes para isso.

• Os alas atacam e defendem. Se sua equipe estiver com a bola e o pivˆo for o l´ıder, um

ala ap´oia o ataque do pivˆo, sen˜ao, se um dos alas for o l´ıder, o l´ıder caminha para

gol enquanto o outro ala se reposiciona ou intercepta um advers´ario. Se a equipe

n˜ao estiver com a bola, os alas podem dar combate, marcar ou se reposicionar.

• O pivˆo pode caminhar para gol, apoiar ataque (quando um ala for o l´ıder), in-

terceptar advers´ario e se reposicionar se a sua equipe estiver com a posse de bola.

A equipe n˜ao estando com a bola, o pivˆo pode dar combate (se for o l´ıder) e se

reposicionar.

Para que a TJ possa ser utilizada, ´e preciso atribuir valores de recompensas paras as

a¸c˜oes. No estado global COM BOLA, as recompensas s˜ao:

• Chutar = 20

• Caminhar para o gol = 15

• Interceptar advers´ario = 10

• Apoiar ataque = 5

• Reposicionar = 1

De acordo com os valores atribu´ıdos, nota-se claramente uma ordem de preferˆencia

na execu¸c˜ao das a¸c˜oes. O que implica numa meta-estrat´egia. Assim, no estado COM

FIG. 4.26: Algoritmo da a¸c˜ao chutar.

BOLA, o l´ıder ´e estimulado a chutar para o gol advers´ario, sempre que houver condi¸c˜oes

para isso; n˜ao havendo, ele deve caminhar para o gol. Aos robˆos com possibilidade de

coopera¸c˜ao, ´e prefer´ıvel a eles interceptarem trajet´orias de advers´ario (se poss´ıvel) do que

apoiar ataque. Por ﬁm, a um robˆo n˜ao sendo l´ıder e n˜ao podendo cooperar, resta apenas

se reposicionar. A recompensas das a¸c˜oes no estado global SEM BOLA s˜ao:

• Dar combate = 10

• Marcar robˆo = 5

• Reposicionar = 1

Agora, faz-se necess´ario associar cada a¸c˜ao a um algoritmo que a possa executar.

Os algoritmos das a¸c˜oes chutar (FIG. 4.26), caminhar para o gol (FIG. 4.27), interceptar

advers´ario (FIG. 4.28), apoiar ataque (FIG. 4.29), dar combate (FIG. 4.30), marcar (FIG.

4.31), reposicionar goleiro (FIG. 4.32), reposicionar ﬁxo (FIG. 4.33), reposicionar ala

direito (FIG. 4.34), reposicionar ala esquerdo (FIG. 4.35) e reposicionar pivˆo (FIG. 4.36)

s˜ao descritos.

Diante das explana¸c˜oes feitas a respeito de cada posi¸c˜ao, ´e necess´ario deﬁnir uma

forma de representar as poss´ıveis coopera¸c˜oes existentes em cada instante do jogo. Para

isso, uma estrutura chamada de hierarquia de coopera¸c˜ao ´e deﬁnida.

A forma de se representar a hierarquia de coopera¸c˜ao ´e atrav´es de ´arvore. Pela deﬁni¸c˜ao

cl´assica, ´arvore ´e uma estrutura de dados que possui rela¸c˜ao hier´arquica entre seus ele-

mentos.

Arvore tamb´em costuma ser deﬁnida como um conjunto ﬁnito de um ou mais n´os,

onde um deles ´e denominado raiz e os demais, recursivamente, formam uma sub-´arvore.

FIG. 4.27: Algoritmo da a¸c˜ao caminhar ao gol.

FIG. 4.28: Algoritmo da a¸c˜ao interceptar advers´ario.

FIG. 4.29: Algoritmo da a¸c˜ao apoiar ataque.

FIG. 4.30: Algoritmo da a¸c˜ao dar combate.

FIG. 4.31: Algoritmo da a¸c˜ao marcar.

FIG. 4.32: Algoritmo da a¸c˜ao reposicionar goleiro.

FIG. 4.33: Algoritmo da a¸c˜ao reposicionar ﬁxo.

FIG. 4.34: Algoritmo da a¸c˜ao reposicionar ala direito.

FIG. 4.35: Algoritmo da a¸c˜ao reposicionar ala esquerdo.

FIG. 4.36: Algoritmo da a¸c˜ao reposicionar pivˆo.

Na hierarquia de co opera¸c˜ao, menor profundidade na ´arvore signiﬁca maior representa-

tividade na jogada e uma maior profundidade, menor representatividade. Assim, a maior

profundidade poss´ıvel da ´arvore ´e igual a 4 (lembrando que o goleiro n˜ao coopera).

Na hierarquia de coopera¸c˜ao os v´ertices s˜ao formados pelas posi¸c˜oes; as arestas repre-

sentam a a¸c˜ao que o n´o ﬁlho pode realizar em coopera¸c˜ao com o pai. Assim, cada aresta

possui um peso associado a ela. Antes de montar a hierarquia de coopera¸c˜ao dos robˆos ´e

preciso frisar que o pivˆo s´o co opera com os alas; um ala coopera com o outro ala, o ﬁxo

e o pivˆo; o ﬁxo coopera somente com os alas. Assim, sabendo que a raiz da hierarquia de

coopera¸c˜ao ´e sempre o l´ıder, tem-se:

• O pivˆo pode ter como ﬁlhos na hierarquia os dois alas;

• Um ala pode ter como ﬁlhos o pivˆo, o outro ala e o ﬁxo;

• O ﬁxo pode ter como ﬁlhos somente os alas.

Note que a representa¸c˜ao por forma de ´arvore ´e similar `a representa¸c˜ao na forma

estendida da TJ. Assim, em cada aresta da ´arvore s˜ao atribu´ıdas as recompensas das

a¸c˜oes multiplicadas por um valor que determina a representatividade (profundidade na

´arvore) na jogada e que ser˜ao analisados pela TJ. A solu¸c˜ao que gerar maior recompensa

´e a escolhida.

E importante salientar que, se um robˆo aparecer na ´arvore, ´e porque ele

contribui socialmente. Sendo assim, n˜ao h´a redu¸c˜ao nas recompensas acumuladas at´e seu

pai. As ´arvores que representam toda a hierarquia de coopera¸c˜ao poss´ıvel tendo como l´ıder

o pivˆo (P), o ala direito (AD), o ala esquerdo (AE) e o ﬁxo (F) s˜ao apresentadas nas ﬁguras

FIG. 4.37, FIG. 4.38, FIG. 4.39 e FIG. 4.40, respectivamente. Complementarmente, ´e

importante ressaltar que quando um robˆo n˜ao est´a inserido na hierarquia de coopera¸c˜ao,

ele est´a no estado INDIVIDUAL (reposicionamento).

Entretanto, diante do que foi exposto at´e o momento, para emergir a coopera¸c˜ao, ´e

necess´ario co ordenar socialmente a forma de se distribuir as diferentes a¸c˜oes aos robˆos.

Assim, s˜ao apresentados, resumidamente, abaixo, os passos que determinam os objetivos

locais para os robˆos.

a) Eleger o l´ıder;

b) Deﬁnir posi¸c˜oes t´aticas dos robˆos;

c) Fazer rota¸c˜ao, se for o caso;

FIG. 4.37: Hierarquia de coopera¸c˜ao m´axima quando o pivˆo ´e o l´ıder.

FIG. 4.38: Hierarquia de coopera¸c˜ao m´axima quando o ala direito ´e o l´ıder.

FIG. 4.39: Hierarquia de coopera¸c˜ao m´axima quando o ala esquerdo ´e o l´ıder.

FIG. 4.40: Hierarquia de coopera¸c˜ao m´axima quando o ﬁxo ´e o l´ıder.

100

d) Montar rede de coopera¸c˜ao;

e) Determinar o plano de a¸c˜oes.

Ao eleger o l´ıder, os parˆametros usados para deﬁni-lo s˜ao os mesmos adotados para

determinar o estado da equipe (objetivo global), s´o que aqui se leva em considera¸c˜ao

apenas os robˆos da equipe controlada. Assim, essa informa¸c˜ao, sobre quem ´e o l´ıder, ´e

determinada no algoritmo de objetivo global, n˜ao sendo necess´ario recalcul´a-la. Al´em de

eleger o l´ıder, os demais robˆos da equipe est˜ao hierarquizados em rela¸c˜ao de importˆancia

no instante de tempo atual do jogo.

Para deﬁnir as posi¸c˜oes t´aticas dos robˆos, atribui-se, dinamicamente, aos robˆos

as posi¸c˜oes t´aticas. Na primeira, e somente na primeira, itera¸c˜ao da partida ´e executado

o algoritmo que deﬁne qual dos robˆos da equipe controlada ´e o goleiro; uma vez deﬁnido,

ele ser´a o goleiro at´e o ﬁnal da partida. Na primeira e nas demais itera¸c˜oes do sistema,

cada posi¸c˜ao t´atica ´e deﬁnida inicialmente para o ﬁxo e o pivˆo (n˜ao importando a ordem)

e, posteriormente, para o ala direita e ala esquerdo (sem ordem deﬁnida). S˜ao deixados

por ´ultimo os alas porque, para deﬁni-los, o algoritmo depende da deﬁni¸c˜ao pr´evia do

ﬁxo e do pivˆo. Adicionalmente, o robˆo que for deﬁnido em uma posi¸c˜ao n˜ao ser´a mais

utilizado nos algoritmos de atribui¸c˜ao de posi¸c˜ao.

Para deﬁnir qual robˆo ´e o ﬁxo no instante de tempo t, calcula-se a distˆancia dos

robˆos que ainda n˜ao tˆem posi¸c˜ao t´atica deﬁnida em rela¸c˜ao ao seu gol. O robˆo com menor

distˆancia ´e o ﬁxo. Para o pivˆo, o algoritmo ´e semelhante, s´o que ao inv´es de ser a distˆancia

em rela¸c˜ao ao seu gol, ´e em rela¸c˜ao ao gol advers´ario. Dentre os dois robˆos que sobraram,

o robˆo que estiver mais a esquerda do campo, de acordo com a vis˜ao de sua equipe, ´e o ala

esquerdo e o robˆo que restou ´e o ala direito. A ordem de deﬁni¸c˜ao dos alas n˜ao importa,

lembrando apenas de relacionar o lado do campo com o ala que se est´a deﬁnindo.

No algoritmo de rota¸c˜ao, excetuando o goleiro por n˜ao poder trocar de posi¸c˜ao, todos

os robˆos da equipe controlada s˜ao utilizados para veriﬁcar se a sua posi¸c˜ao espacial atual

corresponde `a sua posi¸c˜ao t´atica, deﬁnida no passo 2. Caso a posi¸c˜ao espacial de algum

deles n˜ao corresponda `a posi¸c˜ao t´atica, diz-se que ele est´a ”fora de posi¸c˜ao” e, assim,

faz-se a troca de posi¸c˜oes t´aticas para concretizar a rota¸c˜ao. Para isso, o robˆo que est´a

”fora de posi¸c˜ao” troca de posi¸c˜ao t´atica com o robˆo com menor inﬂuˆencia na jogada, no

instante de tempo atual (deﬁnido no passo 1).

E importante lembrar, mais uma vez, que

a troca s´o ocorre entre posi¸c˜oes em que h´a interse¸c˜ao na sua ´area de atua¸c˜ao.

101

O objetivo global est´a diretamente relacionado com a forma de montar a rede de

coopera¸c˜ao. Se o objetivo global for ATACAR, as a¸c˜oes que devem estar presentes na

hierarquia de coopera¸c˜ao s˜ao apenas a¸c˜oes de ataque. Em contrapartida, se o objetivo

global for DEFENDER, as a¸c˜oes da rede de coopera¸c˜ao devem ser a¸c˜oes de defesa.

O primeiro passo para montar a hierarquia de coopera¸c˜ao ´e deﬁnir a raiz. A raiz ´e

sempre o l´ıder da equipe, independente do objetivo global. Assim, a partir do l´ıder, sabe-

se quais s˜ao seus poss´ıveis ﬁlhos. Entretanto, ´e necess´ario veriﬁcar quais dos poss´ıveis

ﬁlhos do l´ıder podem cooperar com ele. Sabendo-se que as a¸c˜oes de coopera¸c˜ao s˜ao

INTERCEPTAR ADVERS

ARIO, APOIAR ATAQUE e MARCAR, as formas pelas quais

cada robˆo pode cooperar variam. Assim, para cada tipo de a¸c˜ao cooperativa, h´a uma

veriﬁca¸c˜ao diferente em rela¸c˜ao ao esquema t´atico adotado.

Nesse trabalho, como j´a mencionado, se adota o esquema t´atico 2-2 para atacar e o

esquema 3-1 para defender. Desse modo, ´e descrita, abaixo, a forma de montar a ´arvore

de coopera¸c˜ao para os esquemas t´aticos citados.

Para o esquema t´atico 2-2 em fun¸c˜ao ofensiva, ap´os a inser¸c˜ao da raiz, somente um

ﬁlho do l´ıder (profundidade 2 da ´arvore) pode executar a fun¸c˜ao APOIAR ATAQUE.

Se o l´ıder for um ala, somente o pivˆo pode apoi´a-lo no ataque. Sen˜ao, se o l´ıder for o

pivˆo, somente o ala mais pr´oximo do gol advers´ario pode apoiar o ataque. Entretanto,

a a¸c˜ao INTERCEPTAR ADVERS

ARIO ´e priorit´aria (maior recompensa) em rela¸c˜ao `a

APOIAR ATAQUE. Aos demais ﬁlhos resta apenas a possibilidade de INTERCEPTAR

ADVERS

ARIO. Contudo, para um robˆo interceptar a trajet´oria de um advers´ario em

rela¸c˜ao `a trajet´oria de seu pai na hierarquia de coopera¸c˜ao, calcula-se a distˆancia desse

robˆo e de todos os advers´arios em rela¸c˜ao a seu pai. Se o robˆo estiver mais pr´oximo

de seu pai do que n advers´arios, signiﬁca que esse robˆo pode interceptar a trajet´oria de

n advers´arios. Entretanto, deve-se escolher apenas um advers´ario. A escolha de qual

advers´ario deve ser interceptado pelo robˆo ´e feita pela menor distˆancia do advers´ario em

rela¸c˜ao ao seu pai. Caso haja 2 ou mais robˆos da equipe controlada podendo interceptar

o mesmo advers´ario, tem preferˆencia aquele que est´a em sua ´area de atua¸c˜ao. Se mesmo

assim 2 ou mais robˆos puderem interceptar o advers´ario, ent˜ao o robˆo mais pr´oximo do seu

pai deve executar essa a¸c˜ao, isso por haver mais garantias de que ela se concretize. Note

que a partir da profundidade 3 da ´arvore os robˆos apenas podem interceptar advers´ario.

Por exemplo, a FIG. 4.41 ilustra uma situa¸c˜ao interessante de estrat´egia de ataque

tendo como l´ıder o ala esquerdo. Assim, seus poss´ıveis ﬁlhos (pela interse¸c˜ao das ´area de

102

FIG. 4.41: Exemplo de coopera¸c˜ao ofensiva entre os robˆos da equipe amarela tendo como

l´ıder o ala esquerdo.

atua¸c˜ao) s˜ao o ﬁxo, o ala direito e o pivˆo. Contudo, a melhor solu¸c˜ao ´e do ﬁxo cooperar

com o ala direito e n˜ao com o ala esquerdo. Na FIG. 4.42 est´a a hierarquia de coopera¸c˜ao

com a solu¸c˜ao para o exemplo da FIG. 4.41.

Para o esquema t´atico 3-1 em fun¸c˜ao defensiva (sem bola), a ´unica forma de coopera¸c˜ao

´e atrav´es da a¸c˜ao MARCAR.

E importante frisar que o pivˆo n˜ao marca advers´ario algum,

isto por uma quest˜ao simples: espera-se que ele seja marcado, j´a que est´a no campo

advers´ario. Na solu¸c˜ao, o ﬁxo tamb´em n˜ao marca, isso a ﬁm de proteger melhor o gol,

uma vez que ”chutes” de longa distˆancia podem ocorrer. Assim, somente os alas marcam

e, para isso, algum advers´ario deve estar no seu campo de defesa. Nesse contexto, se o

pivˆo for l´ıder e houver um ou mais advers´arios no campo de defesa da equipe controlada,

os robˆos mais pr´oximos do gol devem ser marcados pelos alas mais pr´oximos a eles. Dessa

forma, pode acontecer de algum robˆo advers´ario ﬁcar sem marca¸c˜ao.

E um risco a ser

corrido, j´a que o pivˆo e o ﬁxo n˜ao marcam. Note que as a¸c˜oes de coopera¸c˜ao se sobrep˜oem

`as ´areas de atua¸c˜ao das posi¸c˜oes por considerar priorit´aria esse tipo de a¸c˜ao.

Supondo a situa¸c˜ao da FIG. 4.43, a coopera¸c˜ao defensiva ´e deﬁnida a partir do l´ıder,

ala direito. Assim, a FIG. 4.44 ´e a solu¸c˜ao para a situa¸c˜ao ilustrada.

Uma vez montada a hierarquia de coopera¸c˜ao, basta determinar o plano de a¸c˜oes.

Para determinar as a¸c˜oes executadas por cada robˆo, deve percorrer a hierarquia de co-

103

FIG. 4.42: Hierarquia de coopera¸c˜ao para o exemplo da FIG. 4.41.

FIG. 4.43: Exemplo de coopera¸c˜ao defensiva entre os robˆos da equipe amarela tendo como

l´ıder o ala direito.

FIG. 4.44: Hierarquia de coopera¸c˜ao para o exemplo da FIG. 4.43.

104

FIG. 4.45: Exemplo de estrat´egia escolhida, com maior recompensa, para coopera¸c˜ao.

opera¸c˜ao a ﬁm de encontrar a coopera¸c˜ao que gera a maior recompensa, sem repeti¸c˜ao

de posi¸c˜oes. Por exemplo, supondo a hierarquia de coopera¸c˜ao da FIG. 4.45, a melhor

solu¸c˜ao ´e apresentada em destaque. Os robˆos que n˜ao est˜ao presentes na solu¸c˜ao extra´ıda

da hierarquia de coopera¸c˜ao executar˜ao o trabalho individual (reposicionamento).

4.5 EXECUC¸

Resumidamente o problema da execu¸c˜ao consiste em conduzir o robˆo de sua posi¸c˜ao

corrente a uma posi¸c˜ao objetivo. A execu¸c˜ao est´a dividida em dois m´odulos: planejamento

de trajet´oria e controle.

4.5.1 PLANEJAMENTO DE TRAJET

ORIA

O planejamento de trajet´oria baseia-se na teoria do Campo Potencial Artiﬁcial (KHATIB,

1986), que tem como princ´ıpio fundamental a movimenta¸c˜ao do robˆo sob um campo de

for¸cas artiﬁciais, geradas pelos obst´aculos e pelo alvo. O potencial, seu gradiente, deve

ser cont´ınuo. Os obst´aculos (outros robˆos) e o alvo (determinado no objetivo local),

lembrando que cada robˆo p ossui seu alvo, geram campos de repuls˜ao e de atra¸c˜ao, respec-

tivamente, obtendo um movimento (seguindo o gradiente) atrav´es do qual os obst´aculos

s˜ao evitados e espera-se que o robˆo atinja seu objetivo (FIG. 4.46). Essas for¸cas s˜ao

oriundas de uma fun¸c˜ao chamada de potencial artiﬁcial.

105

FIG. 4.46: Campo potencial (LATOMBE, 1991)

Basicamente, um robˆo no espa¸co F ´e tratado como sendo uma part´ıcula sob inﬂuˆencia

de um campo potencial artiﬁcial U. O campo potencial U ´e constru´ıdo no intuito de re-

presentar a estrutura espacial do ambiente. Contudo, cada a¸c˜ao descrita no objetivo local

do planejamento estrat´egico possui crit´erios diferentes para inserir campos de repuls˜ao no

ambiente representado. Note que, sendo o alvo dinˆamico, n˜ao ´e necess´ario que a bola,

nem o gol, sejam campos de atra¸c˜ao, uma vez que a posi¸c˜ao do robˆo no instante t + i j´a

foi deﬁnida no planejamento estrat´egico; assim, a bola e o gol tornam-se campos neutros.

Adicionalmente, todos os robˆos de linha ”enxergam” a ´area do goleiro de sua equipe como

campo de repuls˜ao, evitando que o robˆo entre na ´area e, por conseq¨uˆencia, ocasione pe-

nalidade m´axima. Os campos potenciais de repuls˜ao gerados em cada a¸c˜ao s˜ao descritos

abaixo.

Chutar - N˜ao h´a campos de repuls˜ao nesta a¸c˜ao.

Caminhar para o gol - Durante a aproxima¸c˜ao da bola somente os robˆos advers´arios

s˜ao campos potenciais de repuls˜ao e isso ocorre porque as demais a¸c˜oes no estado COM

BOLA ”enxergam” o l´ıder como campo de repuls˜ao. Se o robˆo ainda n˜ao estiver alinhado

com o objetivo e com distˆancia maior que L (limiar de aproxima¸c˜ao) da bola, a bola ´e

106

vista, tamb´em, como campo de repuls˜ao. A bola ´e um campo potencial de repuls˜ao com

a ﬁnalidade de o robˆo contorn´a-la para poder lev´a-la at´e o gol advers´ario. Se o robˆo

estiver alinhado com a bola e a uma distˆancia menor que L, n˜ao h´a campos potenciais de

repuls˜ao em seu ambiente.

Interceptar advers´ario - Somente os robˆos de sua equipe s˜ao vistos como campos

potenciais de repuls˜ao. Se o robˆo, que executa essa a¸c˜ao, enxergasse os robˆos advers´arios

como campos de repuls˜ao, n˜ao haveria intercepta¸c˜ao.

Apoiar ataque - Todos os robˆos s˜ao vistos como campos de repuls˜ao.

Dar combate - Em seu ambiente, excetuando o l´ıder da equipe advers´aria, todos

os demais advers´arios s˜ao campos potenciais de repuls˜ao. O l´ıder advers´ario n˜ao ´e visto

como campo de repuls˜ao por causa da necessidade de aproximar o robˆo que executa essa

a¸c˜ao dele.

Marcar - Enxerga todos os robˆos como campo de repuls˜ao.

Reposicionar goleiro - N˜ao h´a campos potenciais de repuls˜ao em seu ambiente.

Reposicionar ﬁxo - Apenas os robˆos da sua equipe s˜ao vistos como campos de

repuls˜ao.

Reposicionar alas - Apenas os robˆos da sua equipe s˜ao vistos como campos de

repuls˜ao.

Reposicionar pivˆo - Apenas os robˆos da sua equipe s˜ao vistos como camp os de

repuls˜ao.

A fun¸c˜ao potencial, U : F → R, deve atrair o robˆo para a posi¸c˜ao ﬁnal e repelir

o robˆo para longe dos obst´aculos. Um potencial de atra¸c˜ao U

atr

deve estar associado a

uma posi¸c˜ao x, que representa o objetivo, e um potencial de repuls˜ao U

rep

induzido pelo

obst´aculo que deve repelir o robˆo para longe dele, associado a sua posi¸c˜ao x. O campo

repulsivo n˜ao deve afetar o movimento do robˆo quando este estiver a uma distˆancia muito

grande. O potencial total ´e dado por:

U(x) = U

atr

(x) + U

rep

(x) (4.13)

A for¸ca resultante f ´e dada por:

f = f

atr

+ f

rep

(4.14)

em que:

atr

= −  U

atr

(x) (4.15)

107

rep

= −  U

rep

(x) (4.16)

onde f

atr

´e uma for¸ca de atra¸c˜ao que guia o robˆo at´e o objetivo e f

rep

´e uma for¸ca

repulsiva produzida pela superf´ıcie do obst´aculo.

A equa¸c˜ao que expressa o campo potencial de atra¸c˜ao ´e deﬁnido por:

atr

(x) =

k(x − x

atr

)

(x − x

atr

) (4.17)

onde k ´e uma constante. A for¸ca exercida sobre o robˆo ´e:

atr

(x) = −  U

atr

(x) = −k(x − x

atr

) (4.18)

Dessa forma, prop orcional `a distˆancia do robˆo `a posi¸c˜ao do objetivo. O potencial

repulsivo ´e deﬁnido por:

rep

(x) =



−

)

se d < d

0 se d ≥ d

(4.19)

onde d ´e a distˆancia entre o robˆo e o obst´aculo, d

´e a distˆancia m´axima de inﬂuˆencia

do obst´aculo e k uma constante de ganho. A for¸ca repulsiva induzida por este campo ´e:

rep

(x) =



−

)

se d < d

0 se d ≥ d

(4.20)

onde

´e o vetor unit´ario segundo o qual a for¸ca ´e aplicada.

De forma geral, para n obst´aculos, a for¸ca total gerada pelos obst´aculos f

rep

expressa

por:

rep



i=1

rep

(4.21)

A for¸ca resultante dos campos de atra¸c˜ao e repuls˜ao ´e:

f = f

atr

+ f

rep

(4.22)

Por ﬁm, a for¸ca resultante f deve ser aplicada no controle do robˆo.

4.5.2 CONTROLE

Um bom controle de velocidade dos motores ´e primordial para executar com precis˜ao a

trajet´oria planejada.

O sistema adotado ´e de malha aberta, ou seja, sem realimenta¸c˜ao de odometria (deslo-

camento do ve´ıculo) e encoder (rota¸c˜ao de cada motor). A ausˆencia desses dispositivos

transdutores fez-se necess´aria porque elevaria o custo de produ¸c˜ao de cada robˆo.

108

4.6 COMUNICAC¸

Um bom sistema de comunica¸c˜ao ´e muito importante para um controle de tempo real no

futebol de robˆos. A comunica¸c˜ao utilizada ´e unidirecional (apenas o computador envia

dados e somente os robˆos recebem). A comunica¸c˜ao bidirecional n˜ao costuma ser utilizada

em aplica¸c˜oes que possuam vis˜ao global. O computador externo envia em broadcast (todos

os robˆos recebem os dados e interpretam apenas o bloco que lhe diz respeito) ou por

endere¸camento direto (pacotes enviados para cada robˆo) por radiofreq¨uˆencia, atrav´es de

uma freq¨uˆencia previamente estabelecida, e os robˆos, com receptores sintonizados na

mesma freq¨uˆencia de transmiss˜ao, recebem os sinais e os interpreta. Essa pol´ıtica de

comunica¸c˜ao ´e conhecida como protocolo.

A principal vantagem de se utilizar protocolo por endere¸camento direto ´e a possibili-

dade de fazer um controle de prioridade entre os robˆos durante o jogo. Assim, supondo

que a equipe advers´aria esteja com a bola caminhando livremente para o gol da equipe

controlada, o goleiro poderia ser elevado para prioridade m´axima enquanto o pivˆo seria

de prioridade m´ınima. Por´em, o intervalo de tempo em que os robˆos recebem um pacote

de dados ´e incerto e pode resultar em deﬁciˆencia no controle.

Na comunica¸c˜ao, utilizando proto colos broadcast (mais comum no futebol de robˆos),

cada robˆo possui um endere¸co que corresponde a qual bloco de dados ser´a processado do

pacote recebido. Com isso, nenhum robˆo ﬁca ocioso e o intervalo de tempo no recebimento

dos pacotes ´e constante.

Martins et. al. (MARTINS ET. AL., 2005) alertam que para aplica¸c˜oes de controle

de robˆos, seja numa partida de futebol ou mesmo um robˆo m´ovel em outra aplica¸c˜ao,

o protocolo de comunica¸c˜ao deve ser otimizado para que sua estrutura seja suﬁciente

para conter apenas informa¸c˜oes relevantes a serem passadas aos robˆos. Esse protocolo

deve, ainda, ser conﬁ´avel, ou seja, capaz de separar dados bons de dados corrompidos,

mostrando ter bom controle da informa¸c˜ao e tratamento de erros.

Para o projeto dos robˆos foram adquiridos transmissores Keymark TXC1 FIG. 4.47 e

receptores Keymark RXD1 FIG. 4.47 em freq¨uˆencias 315/433.92MHz.

Nas FIG. 4.49 e FIG. 4.50 est˜ao as especiﬁca¸c˜oes do transmissor e receptor, respecti-

vamente. Para mais informa¸c˜oes do transmissor e do receptor, consultar respectivamente

os seus data sheets (KEYMARK, 2006a) e (KEYMARK, 2006b).

109

FIG. 4.47: Transmissor RF Keymark TXC1.

FIG. 4.48: Receptor RF Keymark RXD1.

FIG. 4.49: Esp eciﬁca¸c˜oes dos pinos do Transmissor RF Keymark TXC1, adaptado de

(KEYMARK, 2006a).

110

FIG. 4.50: Especiﬁca¸c˜oes dos pinos do Receptor RF Keymark RXD1, adaptado de (KEY-

MARK, 2006b).

4.7 SIMULADOR

Os simuladores oﬁciais existentes, tanto da FIRA Simuro Sot (FIRA, 2005b) quanto da

RoboCup Simulation 2D e 3D (ROBOCUP, 2005e), simulam jogadores human´oides. Nesse

sentido, h´a a necessidade de se implementar um simulador, n˜ao no intuito de substituir ou

melhorar os simuladores existentes, mas para simular robˆos com as caracter´ısticas f´ısicas

da equipe do IME.

Visto que, de acordo com a arquitetura proposta, o sistema se constitui de m´odulos,

tem-se como justiﬁcativa, para implementar o simulador e testar o funcionamento do

algoritmo, a ausˆencia de ru´ıdos na determina¸c˜ao exata da posi¸c˜ao e orienta¸c˜ao dos robˆos, o

que no mundo f´ısico sabe-se que, atualmente, as condi¸c˜oes de ilumina¸c˜ao e as deformidades

provocadas pela lente da cˆamera afetam a precis˜ao dos dados. Portanto, se o m´odulo

de Vis˜ao n˜ao estiver funcionando corretamente, dados distorcidos ser˜ao enviados para o

m´odulo Estrat´egia que, por sua vez, vai aparentar estar incorreto, assim tamb´em reﬂetindo

na Execu¸c˜ao e Comunica¸c˜ao, ou seja, o erro ´e acumulativo. Assim, ﬁca muito dif´ıcil

detectar qual m´odulo ´e o gerador do erro. No entanto, com a tecnologia atual, a precis˜ao

dos dados alcan¸cada com um Simulador n˜ao pode ser atingida por algum sistema que

interage com o mundo f´ısico. Sendo assim, um comportamento inconsistente do robˆo

signiﬁca que o erro est´a sendo originado no pr´oprio programa em teste.

Al´em das justiﬁcativas supra-citadas, adicionam-se a elas o elevado tempo de espera

no recarregamento de baterias utilizados nos robˆos f´ısicos, o desgaste natural do hardware,

al´em de os robˆos f´ısicos (incluindo sua fase de projeto) demorarem muito mais tempo para

entrar em opera¸c˜ao se comparados a um sistema de simula¸c˜ao.

111

5 IMPLEMENTAC¸

AO COMPUTACIONAL

Para validar os algoritmos apresentados no cap´ıtulo 4, foram implementados, computa-

cionalmente, dois programas de computador. O primeiro ´e o software de vis˜ao computa-

cional, que processa imagens capturadas do ambiente de jogo, gerando dados num´ericos

que s˜ao utilizados para gerar o comportamento social. O segundo ´e o simulador, j´a apre-

sentado. Tanto no programa de vis˜ao quanto no simulador, o paradigma de programa¸c˜ao

de orienta¸c˜ao a objetos foi adotado.

A orienta¸c˜ao a objetos ´e um paradigma de programa¸c˜ao que surgiu para promover

o entendimento do mundo real. Nesse sentido, um objeto ´e uma entidade que tem uma

identidade. Assim, a programa¸c˜ao orientada a objetos torna a implementa¸c˜ao mais sim-

ples. No entanto, as linguagens que permitem o desenvolvimento de solu¸c˜oes, utilizando o

paradigma de orienta¸c˜ao a objetos, possuem diferen¸cas entre si. Dentre essas diferen¸cas, o

desempenho de execu¸c˜ao do c´odigo fonte da programa¸c˜ao ´e o principal fator aqui procu-

rado. Dentre as linguagens de programa¸c˜ao orientada a objetos, as linguagens Java e

C++ s˜ao as mais utilizadas.

Em (SCHEPKE E CHAR

AO, 2004), Schepke e Char˜ao apresentam uma compara¸c˜ao

entre as linguagens Java e C++ para a resolu¸c˜ao de uma mesma aplica¸c˜ao: a equa¸c˜ao de

Laplace atrav´es do m´etodo iterativo do Gradiente Conjugado. Tal compara¸c˜ao contribui,

principalmente, para ressaltar as vantagens e desvantagens dessas linguagens no contexto

da computa¸c˜ao cient´ıﬁca de alto desempenho. Para ﬁns de compara¸c˜ao, foram gerados

trˆes c´odigos execut´aveis: C++, Java Bytecode e Java Compilado para c´odigo nativo. O

gr´aﬁco FIG. 5.1 representa o resultado da compara¸c˜ao.

Em vista dos resultados apresentados na FIG. 5.1, nota-se claramente que a linguagem

C++ se apresenta como a melhor op¸c˜ao para um STR que exige ser executado de forma

r´apida e eﬁciente. Tanto na implementa¸c˜ao da vis˜ao computacional quanto na imple-

menta¸c˜ao do simulador, a linguagem de programa¸c˜ao C++ foi a adotada.

A linguagem C foi desenvolvida por Dennis Ritchie no in´ıcio dos anos 70 e com a

ﬁlosoﬁa de mantˆe-la r´apida, conﬁar no programador e n˜ao impedir que o programador

fa¸ca o que necessita ser feito. Desde ent˜ao, a linguagem C tornou-se amplamente utilizada.

A linguagem C++ foi criada por Bjarne Stroupstrup no in´ıcio dos anos 80, tendo como

112

FIG. 5.1: Compara¸c˜ao entre os tempos de execu¸c˜ao do m´etodo do Gradiente Conjugado

(SCHEPKE E CHAR

AO, 2004).

principal objetivo estender a linguagem C.

Lee e Tepfenhart (LEE E TEPFENHART, 2001) descrevem as principais capacidades

t´ecnicas da linguagem C++:

• Um programa C++ pode ser r´apido, pois ele n˜ao incorre nos gastos em tempo de

execu¸c˜ao do tipo ”veriﬁca¸c˜ao e coleta de lixo” encontrados na maioria das linguagens

”orientadas a objeto puras”;

• Um casamento entre a linguagem Assembly, de baixo n´ıvel, e constru¸c˜oes orientadas

a objetos de alto n´ıvel. O desenvolvedor poder´a escrever c´odigo no n´ıvel apropriado

para modelar a solu¸c˜ao particular e, ainda, manter detalhes de implementa¸c˜ao em

n´ıvel da m´aquina;

• C++ ´e uma linguagem de multiparadigmas que proporciona ao desenvolvedor uma

gama de op¸c˜oes relativas ao desenho e codiﬁca¸c˜ao de uma solu¸c˜ao. Em resumo,

pode-se considerar a linguagem C++ como alternativa de linguagem orientada a

objetos de um desenvolvedor proﬁssional a linguagens ”orientadas a objeto puras”,

tais como Smalltalk, Objective C, Eiﬀel, etc. A linguagem conﬁa no programador

e n˜ao impede que ele estenda para suportar mecanismos abstratos proveitosos e

tamb´em utilize t´ecnicas n˜ao-orientadas a objeto quanto apropriado. Al´em do mais,

ela ´e uma extens˜ao de uma linguagem de programa¸c˜ao que tem sido utilizada para

escrever um grande n´umero de aplica¸c˜oes numa ampla faixa de m´aquinas.

113

Dentre as interfaces de desenvolvimento que utilizam a linguagem C++, escolheu-se

utilizar a interface de desenvolvimento Borland C++ Builder 4.0 Standard Edition, para

o sistema operacional Microsoft Windows, por sua disponibilidade e ser uma ferramenta

visual de programa¸c˜ao. Al´em disso, com o Borland C++ Builder h´a facilidades em migrar

as aplica¸c˜oes desenvolvidas nele para o Borland Kylix para Linux, desde que utilize os

mesmos componentes na aplica¸c˜ao. A id´eia de desenvolver solu¸c˜oes em diferentes sistemas

operacionais ´e interessante, uma vez que se pode comparar o desempenho das aplica¸c˜oes

neles, possibilitando a escolha do sistema operacional mais adequado.

5.1 VIS

AO COMPUTACIONAL

A ﬁgura FIG. 5.2 apresenta o software de vis˜ao computacional implementado. Na parte

superior, encontram-se as vari´aveis que devem ser ajustadas durante a calibra¸c˜ao. Em

identiﬁca¸c˜ao, est˜ao presentes as op¸c˜oes de escolha entre os m´etodos de classiﬁca¸c˜ao por

HSV e rede neural RBF. J´a na orienta¸c˜ao, os m´etodos dispon´ıveis s˜ao por RGB, HSV e

rede neural MLP. Na guia RGB e HSV est˜ao as vari´aveis utilizadas nesses m´etodos, citadas

no cap´ıtulo 4. Na parte inferior, o endere¸co da imagem m´ascara da subtra¸c˜ao de imagens e

a imagem capturada do ambiente.

A direita, o bot˜ao Raio calcula, a partir de amostras, a

distˆancia entre as marcas de orienta¸c˜ao em rela¸c˜ao ao centro do robˆo; o bot˜ao RBF treina

a rede neural RBF; o bot˜ao MLP treina a rede neural MLP; o bot˜ao Processar inicia o

processamento da vis˜ao computacional; os bot˜oes Identiﬁca¸c˜ao e Orienta¸c˜ao s˜ao utilizados

durante a fase oﬄine para visualizar os resultados da calibra¸c˜ao; o bot˜ao Subtra¸c˜ao exibe

apenas a parte real¸cada pelo m´etodo da subtra¸c˜ao de imagens; e o bot˜ao Salvar tem a

fun¸c˜ao de salvar a imagem resultante do processamento, exibida abaixo dos bot˜oes. Ao

centro do programa, encontra-se a imagem capturada do ambiente.

5.2 SIMULADOR

No simulador, toda a parte de estrat´egia descrita durante o trabalho foi implementada.

Quanto `a movimenta¸c˜ao, somente robˆos holonˆomicos foram utilizados. O simulador ´e

apresentado na FIG. 5.3.

Na ´area central do simulador encontra-se o campo de jogo, local onde ´e simulada,

visualmente, uma partida entre duas equipes (cada uma com sua respectiva cor). Abaixo

do campo est´a o placar da partida.

A esquerda as informa¸c˜oes das equipes em rela¸c˜ao `a

114

FIG. 5.2: Programa implementado da vis˜ao computacional.

FIG. 5.3: Simulador implementado.

115

posse de bola, que implica na estrat´egia global de uma equipe, e as posi¸c˜oes dos robˆos no

campo no instante atual. No lado direito, informa¸c˜oes sobre o ambiente de trabalho.

116

6 TESTES E RESULTADOS

Os testes foram realizados com o intuito de quantiﬁcar a eﬁciˆencia da solu¸c˜ao descrita

ao longo da disserta¸c˜ao. Para os testes, foi utilizada uma m´aquina PC Intel Pentium 4 HT

(32 bits) com freq¨uˆencia de 3.0GHz e 512MB de mem´oria RAM. O sistema operacional

utilizado foi o Microsoft Windows XP Professional. Assim, os testes realizados e os

resultados s˜ao apresentados a seguir.

6.1 VIS

AO COMPUTACIONAL

Para que se pudesse realizar os testes de vis˜ao, foi necess´ario montar uma estrutura que

desse sup orte a isso. Nesse sentido, foi necess´aria uma cˆamera localizada acima do centro

do campo de jogo e lˆampadas para iluminar a superf´ıcie uniformemente. Para isso, foi

adquirida uma tenda do tipo Gazebo para que, aproveitando sua estrutura, pudesse ser

ﬁxada a cˆamera e as lˆampadas. Entretanto, a altura da cˆamera pode variar de acordo com

a necessidade de ajustes. Assim, a altura da cˆamera estaria limitada devido `as restri¸c˜oes da

tenda gazebo. Entretanto, a ﬁm de possibilitar posicionamentos da cˆamera em diferentes

alturas, decidiu-se aproveitar apenas a parte superior da tenda gazebo e prendˆe-la ao teto

com roldanas. A FIG. 6.1 ´e uma fotograﬁa do laborat´orio com a estrutura montada.

Foram utilizadas 4 lˆampadas ﬂuorescentes de 40w para iluminar o campo de jogo, esse

um feltro da cor verde.

Contudo, ap´os a montagem da estrutura f´ısica apareceram problemas inerentes `a vis˜ao

computacional. A proximidade do reator eletrˆonico das lˆampadas em rela¸c˜ao `a cˆamera

provocou ru´ıdos na aquisi¸c˜ao de imagens. Assim, foi necess´ario posicionar os reatores

distantes da cˆamera. Entretanto, ru´ıdos continuaram presentes no processo de aquisi¸c˜ao

de imagens. Dessa vez, ocasionado pelo longo cabo que liga a cˆamera ao computador.

Contudo, foi necess´ario adquirir cabo e conectores de qualidade superior.

Uma vez montada a estrutura, pˆode-se iniciar os testes do sistema de vis˜ao computa-

cional. Devido `as dimens˜oes reduzidas do laborat´orio, foi necess´ario diminuir a escala do

campo de jogo. Na mesma propor¸c˜ao, a ´area dos robˆos foi diminu´ıda, com o intuito de

proporcionar maior ﬁdelidade nos testes. Todavia, pela diﬁculdade de reduzir o tamanho

117

FIG. 6.1: Fotograﬁa do laborat´orio com o suporte de cˆamera e lˆampadas montado.

da bola, ela continuou nas dimens˜oes oﬁciais. No entanto, a cˆamera CMOS, dispon´ıvel

para teste, n˜ao conseguiu captar o ambiente em condi¸c˜oes adequadas de ilumina¸c˜ao para

o processamento. N˜ao foi investigada se a baixa luminosidade capturada no ambiente

foi ocasionada pelas lˆampadas, j´a que foi necess´ario posicionar a cˆamera distante do

campo para que ele fosse enquadrado; nem foi veriﬁcada se a cˆamera era adequada para

essa aplica¸c˜ao. A solu¸c˜ao encontrada foi aproximar a cˆamera e, conseq¨uentemente, as

lˆampadas do campo. Contudo, a escala dos robˆos em rela¸c˜ao ao campo ﬁcou maior, o que

n˜ao obedece `as regras da RoboCup f-180. Fica aqui a sugest˜ao para que, em trabalhos

futuros, seja veriﬁcado o uso de outras cˆameras e tipos de lˆampadas.

Os testes que s˜ao descritos a seguir foram realizados com a ﬁnalidade de comparar os

resultados e tempo de processamento do m´etodos HSV e RBF para a identiﬁca¸c˜ao dos

objetos e RGB, HSV e MLP para a orienta¸c˜ao. Quanto ao erros angulares e espaciais, um

estudo detalhado sobre calibra¸c˜ao deve ser feito, o que foge do escopo dessa disserta¸c˜ao.

Para os testes, foram adquiridas 83 amostras da equipe amarela, 120 da equipe azul e 89

da bola. Todas as imagens foram capturadas na resolu¸c˜ao de 640x480 pixels. A calibra¸c˜ao

118

FIG. 6.2: Regi˜oes com diferen¸ca de luminosidade utilizadas na calibra¸c˜ao.

foi realizada a partir de imagens de cada um dos grupos (equipe amarela, equipe azul e

bola) capazes de exprimir a diversidade de ilumina¸c˜ao e, conseq¨uentemente, varia¸c˜ao de

cor no ambiente. A FIG. 6.2 ilustra as nove regi˜oes, de onde foi retirada 1 amostra de

cada, para a calibra¸c˜ao.

Durante a calibra¸c˜ao, constatou-se que a cor de identiﬁca¸c˜ao azul foi mais dif´ıcil de

calibrar do que as cores amarela e alaranjada. A maior diﬁculdade de calibra¸c˜ao da cor

azul se deve, principalmente, ao fato de o ambiente capturado pela cˆamera estar escuro,

ocasionando a confus˜ao da cor azul com a preta (corpo do robˆo) e, `as vezes, um mau

funcionamento da subtra¸c˜ao de imagens (verde escuro do campo na m´ascara). Vale ainda

acrescentar que, devido `a falta de bola de golfe na cor laranja, foi adquirida uma bola de

golfe branca e pintada com spray de tinta na cor alaranjada. Por´em, a bola ﬁcou com

tonalidade de cor mais clara que a oﬁcial, o que possibilita a confus˜ao na identiﬁca¸c˜ao com

a cor amarela de acordo com a varia¸c˜ao de ilumina¸c˜ao. Adicionalmente, foi observado

que, para a identiﬁca¸c˜ao dos objetos, o m´etodo RBF ´e mais f´acil e r´apido de se calibrar,

devido `a capacidade de generaliza¸c˜ao das RNAs, do que o m´etodo HSV.

Quanto `a calibra¸c˜ao das cores de orienta¸c˜ao, n˜ao houve diﬁculdades em calibrar nos

trˆes m´etodos. O m´etodo RGB ´e o de mais simples calibra¸c˜ao, devido `as suas regras

(descritas no cap´ıtulo 4). Para o m´etodo MLP, poucas amostras conseguem representar

bem o ambiente, devendo apenas se atentar nas regi˜oes de transi¸c˜ao de cores (limite entre

cores). O m´etodo HSV necessita de um pouco mais de cuidado durante sua calibra¸c˜ao,

119

uma vez que h´a interse¸c˜ao nas cores entre as coordenadas desse espa¸co de cor.

Todavia, apesar de tantos problemas, os resultados foram animadores. Em todos

os testes foram utilizadas a mesmas conﬁgura¸c˜oes no programa de vis˜ao computacional:

percorre-se cada imagem em i = 4 pixels no eixo xe j = 4 no eixo y; distˆancia do raio

das marcas de orienta¸c˜ao em rela¸c˜ao ao centro de massa de 11,3 pixels; na subtra¸c˜ao de

imagens, θ = 27; no algoritmo de centr´oide, o erro da identiﬁca¸c˜ao igual a 18 e orienta¸c˜ao

30. Para a classiﬁca¸c˜ao em HSV foi:

• Azul - H

min

= 223, H

max

= 332, S

min

= 51, S

max

= 207, V

min

= 59eV

max

= 182;

• Amarelo - H

min

= 28, H

max

= 94, S

min

= 39, S

max

= 151, V

min

= 198eV

max

= 255;

• Laranja - H

min

= 13, H

max

= 69, S

min

= 141, S

max

= 217, V

min

= 214eV

max

= 255;

• Ciano - H

min

= 22, H

max

= 224, S

min

= 16, S

max

= 141, V

min

= 140eV

max

= 255;

• Rosa - H

min

= 0, H

max

= 358, S

min

= 20, S

max

= 155, V

min

= 127eV

max

= 255;

• Verde - H

min

= 51, H

max

= 148, S

min

= 41, S

max

= 158, V

min

= 67eV

max

= 205;

Note que os valores da conﬁgura¸c˜ao HSV difere da tabela de cores apresentada no

cap´ıtulo 4, isso ocorre porque foi necess´ario modiﬁcar os padr˜oes de cores para que o

m´etodo RGB funcionasse (descrito no cap´ıtulo 4). Para o m´etodo de classiﬁca¸c˜ao por

RGB, os valores de erroCiano, erroRosa e erroVerde utilizados nos testes s˜ao respec-

tivamente 120, 170 e 80. A RNA RBF adotada para a identiﬁca¸c˜ao possuiu, em sua

arquitetura, 14 neurˆonios, sendo 5 para classiﬁcar a cor amarela, 5 para a cor azul e 4

para a cor laranja.

Na TAB. 6.1 s˜ao apresentados os resultados dos testes para a tarefa de identiﬁca¸c˜ao

dos objetos. Os valores de porcentagem est˜ao aproximados.

TAB. 6.1: Resultados dos testes de identiﬁca¸c˜ao utilizando os m´etodos HSV e RBF.

Nos testes realizados, a identiﬁca¸c˜ao utilizando a RNA RBF foi mais eﬁciente para

a classiﬁca¸c˜ao da bola e da equipe amarela. No geral os resultados foram pr´oximos.

120

FIG. 6.3: Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a equipe amarela,

caso 1; onde: (a) ´e a imagem original, (b) imagem processada e (c) a sobreposi¸c˜ao de (b)

em (a)

FIG. 6.4: Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a equipe amarela,

caso 2; onde: (a) ´e a imagem original, (b) imagem processada e (c) a sobreposi¸c˜ao de (b)

em (a)

Entretanto, o m´etodo HSV classiﬁcou uma vez erradamente a equipe amarela como bola

(FIG. 6.3) mas, ainda na ﬁgura, em (c), repare que a maior parte da cor amarela est´a sendo

classiﬁcada corretamente. O outro caso em que o m´etodo HSV classiﬁcou errado a equipe

amarela est´a relatado na FIG. 6.4. Note na FIG. 6.4, em (c), que a cor de orienta¸c˜ao

ciano foi classiﬁcada como sendo da equipe azul, dando a impress˜ao de haver dois objetos

sobrepostos. Os problemas da classiﬁca¸c˜ao em HSV da bola s˜ao apresentados nas ﬁguras

FIG. 6.5 e FIG. 6.6, que s˜ao o mesmo caso da FIG. 6.3. Ainda no m´etodo de classiﬁca¸c˜ao

por HSV, os erros foram ocasionados por causa da subtra¸c˜ao de imagens; repare em (c)

nas FIG. 6.7 e FIG. 6.8, onde o preto ´e o que se real¸ca na subtra¸c˜ao, que apenas uma

pequena parte da cor de identiﬁca¸c˜ao est´a destacada. Na FIG. 6.9, ainda na classiﬁca¸c˜ao

por HSV, o erro foi ocasionado porque a cor rosa de orienta¸c˜ao foi confundida com a cor

azul de identiﬁca¸c˜ao, dando a impress˜ao de haver dois objetos sobrepostos. No entanto,

acredita-se que em melhores condi¸c˜oes de execu¸c˜ao do teste, o resultado da identiﬁca¸c˜ao

melhore.

121

FIG. 6.5: Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a bola, caso 1; onde:

(a) ´e a imagem original, (b) imagem processada e (c) a sobreposi¸c˜ao de (b) em (a)

FIG. 6.6: Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a bola, caso 2; onde:

(a) ´e a imagem original, (b) imagem processada e (c) a sobreposi¸c˜ao de (b) em (a)

FIG. 6.7: Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a equipe azul, caso

1; onde: (a) ´e a imagem original, (b) imagem processada e (c) a sobreposi¸c˜ao de (b) em

(a)

122

FIG. 6.8: Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a equipe azul, caso

2; onde: (a) ´e a imagem original, (b) imagem processada e (c) a sobreposi¸c˜ao de (b) em

(a)

FIG. 6.9: Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao HSV para a equipe azul, caso

3; onde: (a) ´e a imagem original, (b) imagem processada e (c) a sobreposi¸c˜ao de (b) em

(a)

123

FIG. 6.10: Classiﬁca¸c˜ao errada no m´etodo de identiﬁca¸c˜ao RBF para a equipe azul; onde:

(a) ´e a imagem original, (b) imagem processada e (c) o que o algoritmo de identiﬁca¸c˜ao

classiﬁca.

Os erros de classiﬁca¸c˜ao do m´etodo RBF est˜ao relacionados `as amostras utilizadas na

calibra¸c˜ao: a exemplo disso, a FIG. 6.10 ´e apresentada. Os outros dois erros resultantes

da classiﬁca¸c˜ao da RNA RBF s˜ao os mesmos provocados nas ﬁguras FIG. 6.7 e FIG. 6.8.

Para os testes de orienta¸c˜ao, as amostras que foram identiﬁcadas com sucesso no HSV e

no RBF foram processadas, utilizando os m´etodos RGB, HSV e MLP; as demais amostras

(7 do modelo HSV e 3 da RNA RBF) foram descartadas. A RNA MLP usada nos testes

possui em sua arquitetura 5 neurˆonios na camada oculta e, conforme descrito no cap´ıtulo 4,

4 neurˆonios na camada de sa´ıda. As tabelas TAB. 6.2 e TAB. 6.3 apresentam os resultados

dos testes de orienta¸c˜ao utilizando, respectivamente, HSV e RBF na identiﬁca¸c˜ao.

TAB. 6.2: Resultados dos testes de orienta¸c˜ao utilizando o m´etodo HSV na identiﬁca¸c˜ao.

TAB. 6.3: Resultados dos testes de orienta¸c˜ao utilizando o m´etodo RBF na identiﬁca¸c˜ao.

Os resultados apresentados pela RNA MLP foram superiores aos resultados dos outros

dois m´etodos. Isso s´o vem comprovar a capacidade de generaliza¸c˜ao das RNAs. Todavia,

124

FIG. 6.11: Classiﬁca¸c˜ao errada ocasionada pelo m´etodo centr´oide, caso 1; onde: (a) ´e a

imagem original, (b) imagem processada e (c) o que o algoritmo de orienta¸c˜ao classiﬁca.

FIG. 6.12: Classiﬁca¸c˜ao errada ocasionada pelo m´etodo centr´oide, caso 2; onde: (a) ´e a

imagem original, (b) imagem processada e (c) o que o algoritmo de identiﬁca¸c˜ao classiﬁca.

o m´etodo HSV apresentou resultados pr´oximos aos do MLP. J´a o m´etodo RGB mostrou-se

pouco conﬁ´avel, mesmo as superf´ıcies visuais dos robˆos sendo impressas de forma a ajudar

a classiﬁca¸c˜ao por RGB, a varia¸c˜ao de ilumina¸c˜ao no ambiente s´o comprovou o que havia

sido discutido durante a disserta¸c˜ao, a sensibilidade `a luz desse espa¸co de cor.

Quanto ao algoritmo centr´oide apresentado no cap´ıtulo 4, seu desempenho foi compro-

metido por causa da baixa ilumina¸c˜ao capturada no ambiente, lembrando que o algoritmo

centr´oide adotado trabalha com o espa¸co de cores RGB. Isso foi constatado porque os re-

sultados da equipe azul (por causa da confus˜ao com a cor preta) ﬁcaram abaixo dos da

equipe amarela, onde n˜ao havia confus˜ao. Al´em disso, o m´etodo centr´oide fez com que

as amostras, que seriam classiﬁcadas corretamente, fossem classiﬁcadas erroneamente na

equipe azul (vide exemplo em FIG. 6.11). A exemplo disso, a ﬁgura FIG. 6.12 ´e apresen-

tada. Note na FIG. 6.12, em (c), que o algoritmo centr´oide posicionou o centro de massa

das cores de identiﬁca¸c˜ao fora da ´area reconhecida.

Por ﬁm, ´e apresentado na FIG. 6.14 o tempo de processamento da jun¸c˜ao de cada

m´etodo. Para registrar o tempo de processamento da jun¸c˜ao dos m´etodos, a amostra

utilizada nesse teste est´a na FIG. 6.13. Foi adotada uma amostra com a quantidade

125

FIG. 6.13: Amostra utilizada para se determinar o tempo de processamento de cada

jun¸c˜ao de m´etodos.

m´axima de objetos p oss´ıveis para se registrar o pior caso de processamento. Em rela¸c˜ao

`a identiﬁca¸c˜ao, a velocidade de processamento do HSV ´e bem superior `a RNA RBF e os

seus resultados s˜ao semelhantes. Na orienta¸c˜ao, os trˆes modelos apresentam velocidade

de computa¸c˜ao baixa.

6.2 SIMULADOR

Os algoritmos propostos foram suﬁcientes para a equipe apresentar comportamento co-

operativo. Embora durante as simula¸c˜oes pode-se observar a coordena¸c˜ao ocorrer nos

m´ultiplos robˆos, ´e dif´ıcil de quantiﬁcar o valor deste componente espec´ıﬁco. Conclus˜ao

a que Vail e Veloso (VAIL AND VELOSO, 2003) tamb´em chegaram. Assim, uma forma

de tentar quantiﬁcar a solu¸c˜ao, ´e coloc´a-la em confronto direto com outras solu¸c˜oes,

atrav´es das competi¸c˜oes. Mesmo nas competi¸c˜oes, torna-se dif´ıcil encontrar um crit´erio

para quantiﬁcar a solu¸c˜ao. Isso porque tanto as solu¸c˜oes de hardware quanto as solu¸c˜oes

de software s˜ao distintas. Dessa forma, supondo que uma equipe possua uma excelente

solu¸c˜ao de software e uma solu¸c˜ao de hardware inferior, essa equipe pode perder em um

confronto direto de uma outra equipe com ´otima solu¸c˜ao de hardware e uma solu¸c˜ao de

software inferior. O contr´ario tamb´em ´e v´alido.

Mas o que torna uma solu¸c˜ao melhor do que a outra?

E uma pergunta complicada

de se responder. Nesse sentido, vale lembrar o famoso caso do torneio onde programas de

126

FIG. 6.14: Compara¸c˜ao do tempo de processamento, em milissegundos, dos m´etodos

utilizados nos testes de vis˜ao computacional.

computadores disputavam o dilema dos prisioneiros (descrito no cap´ıtulo 3). Participaram

da competi¸c˜ao proﬁssionais de diversas ´areas, apresentando solu¸c˜oes com diferentes graus

de complexidade. Algumas das solu¸c˜oes utilizavam a TJ para induzir o outro jogador a

cooperar, pegando carona em suas boas inten¸c˜oes. Nesse torneio, a estrat´egia vencedora

foi o programa tit-for-tat (olho por olho) (AXELROD AND HAMILTON, 1981).

Resumidamente, a estrat´egia tit-for-tat consiste em inicialmente (na primeira itera¸c˜ao)

cooperar com o oponente e, a partir da´ı, durante as pr´oximas itera¸c˜oes, repetir a a¸c˜ao

deste na jogada anterior, qualquer que seja ela. Sendo assim, o programa ´e muito sim-

ples. Entretanto, a grande surpresa veio quando, ap´os os resultados serem divulgados `a

comunidade participante do certame, o torneio se repetiu e o tit-for-tat voltou a vencer.

Mas, dessa vez, alguns dos participantes utilizaram programas para explorar o tit-for-tat.

O exemplo do tit-for-tat mostra que uma solu¸c˜ao simples pode obter melhores resul-

tados do que solu¸c˜oes com alto grau de complexidade. Mesmo assim, n˜ao h´a garantia de

que o tit-for-tat ´e a melhor solu¸c˜ao. No entanto, era uma competi¸c˜ao somente de software

e o problema ´e, teoricamente, menos complexo do que futebol de robˆos.

Embora o comportamento social possa ser observado nas simula¸c˜oes, em alguns mo-

mentos o jogo pareceu estar truncado. Isso foi provocado porque os robˆos, n˜ao possuindo

dispositivo de passe, necessitam carregar a bola at´e uma distˆancia em que possa ”chutar”

para o gol advers´ario. Contudo, o advers´ario, atrav´es da a¸c˜ao DAR COMBATE, tenta

impedir que o robˆo com a posse de bola consiga evoluir espacialmente. Assim, a inser¸c˜ao

de dispositivo de passe possibilita novas movimenta¸c˜oes e menos tempo carregando a bola,

o que pode ajudar a diminuir o truncamento do jogo.

127

Com o truncamento do jogo, houve oscila¸c˜oes no estado do objetivo global das equipes.

Isso ocorre porque quando um robˆo carrega a bola, n˜ao havendo o dispositivo ”driblador”

nele, a bola tende a escapar de sua superf´ıcie e, com isso, o advers´ario que est´a dando com-

bate passa a ﬁcar com uma distˆancia da bola menor do que tinha o que antes caminhava

para o gol. Diz-se antes porque, nesse momento, o estado global das equipes inverteu, j´a

que o estado global ´e deﬁnido utilizando a distˆancia dos robˆos em rela¸c˜ao `a b ola. Esse

processo se repete in´umeras vezes, tornando os movimentos de todos os robˆos oscilat´orios.

Por exemplo, um robˆo pode oscilar entre apoiar ataque (COM BOLA) e se reposicionar

(SEM BOLA); entre outras situa¸c˜oes. Com o objetivo de resolver as oscila¸c˜oes no estado

global das equipes, a inser¸c˜ao de um novo estado global pode ser interessante, o estado

EM DISPUTA.

A utiliza¸c˜ao de segmento de reta para fazer a previs˜ao de movimento dos advers´arios e

da bola funcionou bem, fazendo com que os robˆos da equipe controlada sempre conseguis-

sem atingir a bola e realizar a movimenta¸c˜ao a partir da previs˜ao dos robˆos advers´arios.

Entretanto, problemas de m´ınimos locais provocados pelo m´etodo de campo potencial

artiﬁcial foram identiﬁcados.

Na FIG. 6.15 est´a ilustrada uma situa¸c˜ao de m´ınimo local. Repare que a bola est´a

gerando um campo potencial de repuls˜ao (´area em cinza) para o robˆo l´ıder da equipe

controlada, assim como a ´area de atua¸c˜ao do goleiro de sua equipe. Repare ainda que

para o robˆo atingir o objetivo (identiﬁcado com um X ), de acordo com a teoria do campo

potencial artiﬁcial, ele deveria passar entre a bola e a ´area do goleiro, no entanto, n˜ao

h´a espa¸co suﬁciente para isso. Mas, supondo que o advers´ario v´a em dire¸c˜ao `a bola a

ﬁm de fazer o gol, o robˆo que estava em m´ınimo local, vai sair dessa situa¸c˜ao, j´a que sua

a¸c˜ao vai se modiﬁcada para DAR COMBATE.

E uma situa¸c˜ao indesejada, uma vez que

de uma situa¸c˜ao de vantagem, a equipe passar´a para uma de desvantagem. Por´em, se

por algum motivo a equipe advers´aria estiver parada, o jogo vai estagnar, necessitando

da interven¸c˜ao do ´arbitro humano.

Pela falta de aleatoriedade no sistema, a solu¸c˜ao ´e determin´ıstica, ou seja, a partir de

uma mesma raiz, o resultado ser´a sempre o mesmo. Dessa forma, torna a movimenta¸c˜ao

da equipe previs´ıvel, podendo o advers´ario explorar essa situa¸c˜ao.

Por ﬁm, ´e apresentado o tempo m´edio aproximado de processamento extra´ıdo nas

itera¸c˜oes do simulador. Para o m´odulo de Planejamento, onde ocorrem os c´alculos de

Previs˜ao de Movimento, Objetivo Global e Objetivo Local, o tempo de processamento ´e

128

FIG. 6.15: Exemplo de problema de m´ınimo local do campo potencial artiﬁcial.

de aproximadamente 0.09ms. Para o Planejamento de Trajet´oria, o tempo aproximado

de pro cessamento ´e de 0.05ms. Em ambos os casos, o tempo de processamento superou

as expectativas mais otimistas dos que estiveram envolvidos no trabalho.

129

7 CONSIDERAC¸

OES FINAIS

O futebol de robˆos ´e um desaﬁo padr˜ao internacional, onde pesquisadores de diversas

´areas desenvolvem solu¸c˜oes. O grande desaﬁo do futebol de robˆos est´a focado at´e o ano

de 2050, onde se prevˆe que uma equipe de robˆos vencer´a a equipe campe˜a mundial de

futebol de humanos, seguindo regras internacionais da FIFA.

Durante a disserta¸c˜ao foram apresentados os fundamentos necess´arios para o trabalho

cooperativo. Nesse sentido, foi feita uma discuss˜ao ﬁlos´oﬁca sobre o comportamento

social, dando ˆenfase nas rela¸c˜oes entre indiv´ıduos e ambiente. Entretanto, para o compor-

tamento social surgir, ´e necess´ario uma mecanismo democr´atico, que trate os indiv´ıduos

em igualdade de condi¸c˜ao, j´a que todo indiv´ıduo ´e importante para o ambiente. Todavia,

a democracia direta, que teoricamente propicia a cada indiv´ıduo contribuir de maneira

cont´ınua para a elabora¸c˜ao e o aperfei¸coamento das solu¸c˜oes, ´e um pro cesso muito lento

e invi´avel em um STR. Assim, foi adotado um processo de regula¸c˜ao social, que veriﬁca

as condi¸c˜oes de contribui¸c˜ao social de cada indiv´ıduo. Nesse sentido, foi montada uma

hierarquia de contribui¸c˜ao social dos indiv´ıduos, denominada hierarquia de coopera¸c˜ao.

Atrav´es da hierarquia de coopera¸c˜ao cada indiv´ıduo planeja sua a¸c˜ao em rela¸c˜ao `a sua

posi¸c˜ao na hierarquia. O uso da hierarquia de coopera¸c˜ao possibilitou o uso coordenado

de a¸c˜oes individuais em benef´ıcio social.

Contudo, entender o processo de tomada de decis˜ao ´e fundamental para bons resulta-

dos. Foram constatados dois tipos de jogos: jogo das equipes (objetivo global), rela¸c˜ao de

competi¸c˜ao entre os jogadores; e jogo entre os jogadores de uma mesma equipe (objetivo

local), rela¸c˜ao de coopera¸c˜ao entre os jogadores. Assim, a TJ possibilitou compreender

melhor os tipos de jogos envolvidos no futebol de robˆos. Constatou-se que, no jogo entre

os jogadores de uma mesma equipe, apesar de ser um jogo de movimenta¸c˜ao simultˆanea, a

tomada de decis˜ao pode ser seq¨uencial. Essa abordagem possibilitou uma vis˜ao diferente

da coopera¸c˜ao no futebol de robˆos.

O futsal foi preponderante na formula¸c˜ao de estrat´egias sociais aplicadas na solu¸c˜ao da

aplica¸c˜ao descrita nesta disserta¸c˜ao. Tanto o esquema t´atico, quanto as posi¸c˜oes espaciais

e seus tipos de rela¸c˜oes foram deﬁnidas a partir do futsal.

Para que os robˆos fossem capazes de interagir com o ambiente, uma arquitetura mo-

130

dular e ﬂex´ıvel foi proposta para a aplica¸c˜ao de futebol de robˆos. Nessa arquitetura,

cada m´odulo do sistema ´e respons´avel por uma tarefa. Os m´odulos apresentados s˜ao:

aquisi¸c˜ao de imagem, vis˜ao, planejamento, execu¸c˜ao e comunica¸c˜ao. Os m´odulos do sis-

tema podem apresentar sub-m´odulos e assim sucessivamente.

E importante ressaltar que

a altera¸c˜ao dos algoritmos de um m´odulo n˜ao implica na altera¸c˜ao dos demais m´odulos,

aﬁrma¸c˜ao v´alida tamb´em para os sub-m´odulos recursivamente. Por exemplo, a altera¸c˜ao

do algoritmo de uma a¸c˜ao do objetivo local implicar´a em nenhuma altera¸c˜ao no restante

do sistema, o que facilita a amplia¸c˜ao da solu¸c˜ao.

Ao longo da disserta¸c˜ao foram discutidas em detalhes as solu¸c˜oes de software. Na

vis˜ao computacional, a jun¸c˜ao de 2 m´etodos de identiﬁca¸c˜ao de objetos com 3 m´etodos

de orienta¸c˜ao resultou em 6 m´etodos diferentes. Foram apresentados os testes e seus

respectivos resultados no cap´ıtulo 6. Apesar das diﬁculdades operacionais encontradas,

2 m´etodos apresentaram resultados bastante interessantes: HSV na identiﬁca¸c˜ao junta-

mente com HSV e MLP na orienta¸c˜ao. Contudo, vale observar que em nenhum m´etodo

foram utilizados ﬁltros para melhorar as imagens e as RNA trabalharam com espa¸co de

cor RGB.

Para os testes de comportamento social, um simulador foi implementado. No simu-

lador, duas equipes iguais foram postas em campo de jogo. No testes foram observadas as

rela¸c˜oes sociais em execu¸c˜ao. Contudo, ´e muito dif´ıcil quantiﬁcar a solu¸c˜ao implementada.

7.1 TRABALHOS FUTUROS

O presente trabalho defendeu a coopera¸c˜ao no futebol de robˆos atrav´es de hierarquia e os

testes serviram para validar a solu¸c˜ao. Contudo, na solu¸c˜ao apresentada n˜ao foi utilizado

algum m´etodo de aprendizado, a ﬁm de explorar inteligentemente diferentes situa¸c˜oes de

jogo. Assim, sugere-se a implementa¸c˜ao de m´etodos de aprendizado por refor¸co, onde a TJ

funcionaria como o cr´ıtico para refor¸car boas solu¸c˜oes. Al´em do aprendizado por refor¸co,

´e interessante a implementa¸c˜ao de um sistema de Minera¸c˜ao de Dados (Data Mining)

para extrair informa¸c˜oes e regras de como agir no decorrer da partida com diferentes

equipes. Por exemplo, qual esquema t´atico adotar em diferentes situa¸c˜oes de jogo para

obter melhores resultados.

A pr´oxima etapa do trabalho ´e implementar ﬁsicamente os robˆos para que se possa,

atrav´es de competi¸c˜oes, avaliar e aperfei¸coar a solu¸c˜ao apresentada nesta disserta¸c˜ao. A

incorpora¸c˜ao de novos esquemas t´aticos e novas a¸c˜oes aos robˆos, assim como melhorar os

131

algoritmos das a¸c˜oes aqui apresentadas, ´e motivada. Por´em, faz-se necess´ario incorporar

heur´ısticas no planejamento de trajet´oria a ﬁm de se evitar os m´ınimos locais gerados no

m´etodo de campo potencial artiﬁcial.

Posteriormente, pretende-se expandir a forma de comportamento social, descrita na

disserta¸c˜ao, para 11 jogadores por equipe, com a ﬁnalidade de utiliz´a-la na RoboCup

Simulation League 2D e 3D. Quanto a outras competi¸c˜oes, o simulador implementado

permite o desenvolvimento de solu¸c˜oes de linguagem natural para a RoboCup Commen-

tator Exhibition, na qual a competi¸c˜ao ocorre na narra¸c˜ao dos jogos.

Por ﬁm, vislumbra-se a utiliza¸c˜ao da hierarquia de coopera¸c˜ao em outras aplica¸c˜oes

com caracter´ısticas semelhantes ao do futebol de robˆos.

132

8 REFER

ENCIAS BIBLIOGR

AFICAS

ANANTHARAMAN, T. A Statistical Study of Selective Min-Max Search in

Computer Chess. PhD thesis, Carnegie-Mellon University, Pittsburgh, PA, May

1990.

ASHMORE, M. and BARNES, N. Omni-drive robot motion on curved paths:

The fastest path between two points is not a straight-line. In AI 2002: Ad-

vances in artiﬁcial intelligence. 15th Australian joint conference on artiﬁcial intelligence,

Canberra, Australia, December 2-6, 2002. Proceedings. Berlin: Springer. Lect. Notes

Comput. Sci. 2557, 225-236 (2002). MSC 2000.

ASIMOV, I. I, Robot. Doubleday, Garden City, NY, 1950.

AXELROD, R. and HAMILTON, W. D. The evolution of cooperation. Science 211,

p.1390-1396, 1981.

BALL, D., WYETH, G. and NUSKE, S. A Global Vision System for a Robot Soccer

Team. Proceedings of the 2004 Australasian Conference on Robotics and Automation

(ACRA), Canberra, Australia.

BEHAR, P. A. e COSTA, A. C. R. Computa¸c˜ao Cooperativa no Processo de

Constru¸c˜ao Coletiva de Conhecimentos. In III Congresso Ibero-Americano de

Inform´atica Educativa, Barranquilla: 1996.

ERNI, D. A. Teoria dos Jogos: Jogos de Estrat´egia, Estrat´egia Decis´oria,

Teoria da Decis˜ao. Rio de Janeiro: Reichmann and Aﬀonso Ed., 2004.

BONABEAU, E., DORIGO, M. e THERAULAZ, G. Swarm Intelligence: From Nat-

ural to Artiﬁcial Systems. Oxford University Press, New York, 1999.

BOWLING, M. and VELOSO, M. Simultaneous adversarial multirobot learning. In

Proceedings of the Eighteenth International Joint Conference on Artiﬁcial Intelligence,

August 2003.

BRACHO, M., CASTRO, M. and MORENO, J. A. A Robotic Architecture for

RoboCup. In Conferencia de la Asociaci´on Espa˜nola para la Inteligencia Artiﬁcial,

CAEPIA-TTIA 2001.

BRAGA, A. P., LUDERMIR, T. B. e CARVALHO, A. C. P. L. F. Redes Neurais

Artiﬁcias: Teoria e Aplica¸c˜oes. Rio de Janeiro: LTC, 2000.

BRUCE, J. and VELOSO, M. Fast and Accurate Vision-Based Pattern Detec-

tion and Identiﬁcation. In Proceedings of ICRA’03, the 2003 IEEE International

Conference on Robotics and Automation, Taiwan, May 2003.

133

BUCHHEIM, T., KINDERMANN, G., LAFRENZ, R., RAJAIE, H., SCHANZ, M.,

SCHREIBER, F., ZWEIGLE, O. and LEVI, P. Team Description Paper 2004

CoPS Stuttgart. IPVS, University of Stuttgart, Stuttgart: 2004.

CAMPION, G., D’ANDREA NOVEL, B. and BASTIN, G. Structural properties and

classiﬁcation of kinematic and dynamic models of wheeled mobile robots. In

IEEE Trans. Robotics Automation, 12(1):47-62, 1996.

CAO, Q., CHEN, W., HUANG, Y., WANG, J., JIA, J., LUO, Z., ZHANG, Z., PAN, L.,

QIAN, Z., FU, Z., SUN, Y., MIAO, S., CHEN, X., ZHANG, F., YU, L. and ZHANG,

Y. JiaoLong2004 Team Description . In Research Institute of Robotics, Shanghai

Jiao Tong University, Shangai: 2004.

CARTER, B., GOOD, M., DOROHOFF, M., LEW, J., WILLIAMS II, R. L. and GAL-

LINA, P. Mechanical design and modeling of an omni-directional robocup

player. In Proceedings RoboCup 2001 International Symposium, Seattle, WA, August

2001..

CHALUP, S. K., COLEMAN, O. J., FREESTON, M. N., MIDDLETON, R. H., MURCH,

C. L., QUINLAN, M. J., SEYSENER, C. J., SHANKS, G. D. The NUbots’ Team

Description for 2003. School of Electrical Engineering and Computer Science, The

University of Newcastle, Newcastle: 2003.

CARNEGIE MELLON UNIVERSITY Carnegie Mellon Robot Soccer Images. In

http://www.cs.cmu.edu/ robosoccer/image-gallery, acessado em 01 de novembro de

2005.

COSTA, R. M., TADDEI, L., NEVES, R. S. e BOTELHO, S. S. DA C. Vis˜ao Global

de Futebol de Robˆos para Equipe FurgBol. In Cricte, Univale, 2003.

D’ANDREA, R. The Cornell RoboCup Soccer Team: 1999 - 2003. In B. Levine

and D. Hristu, editors, Handb ook of Networked and Embedded Control Systems.

Birkhauser, 2005.

DE-FARIAS, A. K. C. R. Comportamento Social: Coopera¸c˜ao, Competi¸c˜ao e

Trabalho Individual. In An´alise do Comportamento - Pesquisa, Teoria e Aplica¸c˜ao,

Artmed, Porto Alegre: 2005.

DEEP BLUE In http://www.research.ibm.com/deepblue, acessado em 25 de outubro de

2005.

EMERY-MONTEMERLO, R. , GORDON, G., SCHNEIDER, F. e THRUN, S. Game

Theoretic Control for Robot Teams. In ICRA, 2005.

FIANI, R. Teoria dos Jogos para Cursos de Administra¸c˜ao e Economia. Rio de

Janeiro: Elsevier 2002.

FIERRO, R., SONG, P., DAS, A. K. e KUMAR, V. Cooperative control of robot

formations. In Cooperative Control and Optimization, R. Murphey and P. Pardalos,

Eds. Dordrecht, The Netherlands: Kluwer, 2002.

134

FIGUEIREDO, L. C. e JOTA, F. G Introdu¸c˜ao ao controle de sistemas n˜ao-

holonˆomicos. In Sba Controle e Automa¸c˜ao, July/Sept. 2004, vol.15, no.3, p.243-268.

ISSN 0103-1759, 2004.

FEDERATION OF INTERNATIONAL ROBOT-SOCCER ASSOCIATION About

FIRA: Overview. In http://www.ﬁra.net/about/overview.html, acessado em 02 de

novembro de 2005a.

FEDERATION OF INTERNATIONAL ROBOT-SOCCER ASSOCIATION SimuroSot

Overview. In http://www.ﬁra.net/soccer/simurosot/overview.html, acessado em 04

de novembro de 2005b.

FREITAS, M. T. A. Vygotsky e Bakhtin - Psicologia e Educa¸c˜ao: Um Intertexto.

Atica, 1995.

FUTSAL BRASIL Movimenta¸c˜ao de Quadra: da teoria `a pr´atica.

http://www.futsalbrasil.com.br/artigos/artigo.php?cd artigo=34, acessado em 14 de

novembro de 2005.

GOLDSCHMIDT, R. e PASSOS, E. Data Mining: Um Guia Pr´atico. Rio de Janeiro:

Elsevier, 2005.

GOMEZ, L. A. M. Sistema de visi´on para el equipo de robots aut´onomos del

ITAM. Tesis que para obtener el t´ıtulo de ingeniero en computaci´on, 2004.

GONZALEZ, R. C. e WOODS, R. C. Digital Image Processing. Reading, MA: Ad-

disonWesley, 1992.

HAYKIN, S. Redes Neurais: princ´ıpios e pr´atica. trad. Paulo MArtins Engel, 2.ed.,

Porto Alegre: Bookman, 2001.

HIBINO, S., KODAMA, Y., NAGASAKA, Y., TAKAHASHI, T., MURAKAMI, K. and

NARUSE, T. Fast Image Processing and Flexible Path Generation System

for RoboCup Small Size League. RoboCup2002, pp.53-64, 2002.

HONDA, V. A. Desenvolvimento de um ve´ıculo microcontrolado por malha

fechada. Disserta¸c˜ao de mestrado - Engenharia Mecˆanica - UFF, 2002.

IKENOUE, S., ASADA, M. and HOSODA, K. Cooperative behavior acquisition by

asynchronous policy renewal that enables simultaneous learning in multia-

gent environment. Proceedings of the 2002 IEEE/RSJ Intl. Conference on Intelligent

Robots and Systems, pp.2728-2734, 2002.

INDIVERI, G. On the motion control of a nonholonomic soccer playing robot.

In RoboCup-2001: The Fifth International Symposium, Co-located with IJCAI-01,

Seattle, USA, 2-10 August 2001.

JAMZAD, M., SADJAD, B. S., MIRROKNI, V. S., KAZEMI, M., CHITSAZ, H., HEY-

DARNOORI, A., HAJIAGHAI, M. T. and CHINIFOROOSHAN, E. A fast vision

system for middle size robots in RoboCup. RobCup Symposium, Seattle-2001.

135

JENSEN, R. M., VELOSO, M. M. and BRYANT, R. E. Guided symbolic universal

planning. In Proceedings of the 13th International Conference on Automated Planning

and Scheduling ICAPS-03, pages 123–132, 2003.

JONG-HWAN, K., KWANG-CHOON, K., YONG-JAE, K. and VADAKKEPAT, P. Path

Planning and Role Selection Mechanism for Soccer Robots. In ICRA 1998:

3216-3221.

KEYMARK Products. In http://www.keymark.com.tw/download/TXC1.pdf, acessado

em 2 de fevereiro de 2006a.

KEYMARK Products. In http://www.keymark.com.tw/download/RXD1.pdf, acessado

em 2 de fevereiro de 2006b.

KHATIB, O. Real-Time Obstacle Avoidance for Manipulators and Mobile Ro-

bots. In International Journal of Robotic Research, v. 5, n. 1, p. 90-98, 1986.

KENNEDY, J. F. Urgent National Needs. In Congressional Record - House (25 de

Maio de 1961), 1961.

KITANO, H. RoboCup: The Robot World Cup Initiative. In Proceedings of the

1st International Conference on Autonomous Agent (Agents’ 97), Marina del Ray, The

ACM Press, 1997.

KUBE, R. C. and BONABEAU, E. Cooperative transport by ants and robots. In

Robotics and autonomous systems, vol. 30, pp. 85-101.

LATOMBE, J. C. Robot Motion Planning. Kluwer Academic Publishers, Boston,

1991.

LEE, R. C. e TEPFENHART, W. M. UML e C++: Guia Pr´atico de Desenvolvi-

mento Orientado a Objeto. Makron Books, 2001.

EVY, P. A Inteligˆencia Coletiva. Por Uma Antropologia do Ciberespa¸co. 4

Edi¸c˜ao, Loyola, S˜ao Paulo: 2003.

LIMA, P., CUST

ODIO, L., PINHEIRO, P., COSTELHA, H., NETO, G., PIRES, V.,

ARROZ, M. and VECHT, B. ISocRob 2004: Team Description Paper. Instituto

de Sistemas e Rob´otica, Instituto Superior T´ecnico, Lisboa: 2004.

LOOMIS, J. G., PALMER, J. D. and PANDIT, P. Performance Development of a

Real-Time Vision System. Master’s thesis, Cornell University, New York1: 2003.

MACKWORTH, A. K. On Seeing Robots. In Computer Vision: Systems, Theory, and

Applications, pages 1–13. Singapore: World Scientiﬁc Press, 1993.

MARR, D. Vision: A Computational Investigation into the Human Represen-

tation and Processing of Visual Information. W.H. Freeman, 1982..

136

MARTINEZ-GOMEZ, L. A. and WEITZENFELD, A. Simultaneous Planning: A

Real-Time Planning Method. Research on Computer Science, Vol. 13, Advances in

Computer Science in Mexico, A. Gelbukh and H. Calvo (Eds.), pp 3-12, ISSN 1665-9899,

2005.

MART

INEZ-G

OMEZ, L. A., MONEO, F., SOTELO, D. and WEITZENFELD, A. Eagle

Knights Small Size League Team Description Paper. In Proc. RoboCup 2005,

Osaka, Japan, July 13-19, 2005.

MART

INEZ-G

OMEZ, L. A. and WEITZENFELD, A. Real Time Vision System for

a Small Size League Team. In 1st IEEE Latin American Robotics Symposium,

Mexico City: 2004.

MARTINS, M. F., TONIDANDEL, F. e BIANCHI, R. A. C. Um protocolo conﬁ´avel

e ﬂex´ıvel de comunica¸c˜ao para futebol de robˆos. In LARC 2005 Latin American

Robotics Competition, S˜ao Lu´ıs: 2005.

MEYER, J., ADOLPH, R., SEPHAN, D., DANIEL, A., SEEKAMP, M., WEINERT,

V. and VISSER, U. Decision-making and Tactical Behavior with Potential

Fields. In RoboCup 2002: Robot Soccer World Cup VI. Volume 2752 of Lecture Notes

in Artiﬁcial Intelligence, Springer, 2003.

MOLZ, R. F., ENGEL, P. M. e MORAES, F. G. Uma Metodologia para o Desen-

volvimento de Aplica¸c˜oes de Vis˜ao Computacional utilizando um projeto

conjunto de Hardware e Software. In Tese de doutorado, Instituto de Inform´atica,

UFRGS, 2001.

MULLER, M. Game theories and computer Go. Go and Computer Science Workshop

(GCSW’93), INRIA, Sophia-Antipolis, 1993.

NAGASAKA, Y., MURAKAMI, K., NARUSE, T., TAKAHASHI, T. and MORI, Y. Po-

tential Field Approach to Short Term Action Planning in RoboCup F180

League. In RoboCup 2000: Robot Soccer World Cup IV table of contents, 345-350,

2001.

NEVES, R. S., TADDEI, L., BANDEIRA, I. e BOTELHO, S. S. C. Vis˜ao Computa-

cional e Estrat´egias de Controle Aplicadas ao Futebol de Robˆos. In MPU

2004, Rio Grande: 2004.

OTTONI, G. DE L. e LAGES, W. F. Navega¸c˜ao de robˆos m´oveis em ambientes

desconhecidos utilizando sonares de ultra-som. Sba Controle e Automa¸c˜ao, 2003,

vol.14, no.4, p.402-411. ISSN 0103-1759.

PACHECO, R. N. e COSTA, A. H. R. Navega¸c˜ao de Robˆos M´oveis Utilizando o

M´etodo de Campos Potenciais. In Workshop de Computa¸c˜ao WORKCOMP’2002.

Milton T. S. Sakude and Cec´ılia de A. Castro Cesar (eds.). Instituto Tecnol´ogico de

Aeron´autica - ITA, S˜ao Jos´e dos Campos, SP, 2002, Pgs. 125-130.

137

PARKER, L. E., KANNAN, B., TANG, F. and BAILEY, M. Tightly-Coupled Nav-

igation Assistance in Heterogeneous Multi-Robot Teams. In Proceedings of

IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sept.

2004.

PARKER, L. E. Current state of the art in distributed autonomous mobile

robotics. In Parker, L. E., Bekey, G., and Barhen, J., editors, Distributed Autonomous

Robotic Systems, volume 4, pages 3–12. Springer, Tokio, 2000.

PEREIRA, P. R. DA C. e ROSA, P. F. F. Coopera¸c˜ao entre Robˆos para Reconhe-

cimento de Ambientes Desestruturados. In Disserta¸c˜ao de Mestrado apresentada

ao programa de p´os-gradua¸c˜ao em Sistemas e Computa¸c˜ao/IME, 2001.

PURWIN, O. and D’ANDREA, R. Cornell Big Red 2003. Bonarini A., Browning

B., Yoshida K. (Eds), Robocup 2003: Robot Soccer World Cup VII, Lecture Notes in

Artiﬁcial Intelligence, Springer, Berlin, 2003.

REIS, L. P. Coordena¸c˜ao em Sistemas Multi-Agentes: Aplica¸c˜oes na Gest˜ao

Universit´aria e Futebol Rob´otico. Tese de PhD, FEUP, julho de 2003.

RIBEIRO, M. I. Uma Viagem ao Mundo dos Robots. 3

ciclo de col´oquios Despertar

para a Ciˆencia, Lisboa, 2005.

ROBOCUP RoboCup: Regulations and Rules. In

http://www.robocup.org/regulations/4.html, acessado em 1 de maio de 2005a.

ROBOCUP A brief History of RoboCup. In

http://www.robocup.org/overview/23.html, acessado em 25 de outubro de 2005b.

ROBOCUP RoboCup Objective. In http://www.robocup.org/overview/22.html, aces-

sado em 25 de outubro de 2005c.

ROBOCUP What is RoboCup. In http://www.robocup.org/overview/21.html, aces-

sado em 25 de outubro de 2005d.

ROBOCUP About RoboCup Simulation League Competition 2005. In

http://staﬀ.science.uva.nl/∼jellekok/robocup/rc05, acessado em 04 de novembro de

2005e.

ROBOCUP Osaka 2005 Highlights. In

http://www.robocup.org/games/05Osaka/images/index.htm, acessado em 31 de

janeiro de 2006.

ROSA, P. F. F., PEREIRA, P. R. C. e JUSTEL, C. M. Heuristics for exploring

unstructured environments with a cooperating robot team. In WorldW-

CETEC2004 - World Congress on Engineering and Technology Education, 2004, Santos

- S˜ao Paulo. WorldWCETEC2004 - World Congress on Engineering and Technology

Education. USA : IEEE - Education Society, 2004. v. 1. p. 380-384..

138

ROSA, P. F. F. e APOLIN

ARIO, F. M´ultiplos robˆos autˆonomos em uma estrutura

cooperativa. 18th International Congress of Mechanical Engineering, Ouro Preto,

2005.

RUIZ-DEL-SOLAR, J., VALLEJOS, P., ZAGAL, J. C., LASTRA, R., CASTRO, G.,

GORTARIS, C., SARMIENTO, I. and MONTERO, P. UChile1 2004 Team De-

scription Paper. Department of Electrical Engineering, Universidad de Chile, Santi-

ago: 2004.

RUSSEL, S. e NORVIG, P. Inteligˆencia Artiﬁcial. Editora Campus, 2004.

SAMUEL, A. Some studies in machine learning using the game of checkers -

recent progress. IBM Journal of research and development, 11:601– 617, 1967.

SCHEPKE, C. e CHAR

AO, A. S. Compara¸c˜ao entre Java e C++ na Computa¸c˜ao

Num´erica. Foz do Igua¸cu: Quinto Workshop em Sistemas Computacionais de Alto

Desempenho, 2004.

SHANNON, C. Programming a computer for playing chess. Philosophical Magazine,

41(4):256–275, 1950.

SHI, J. and LITTMAN, M. L. Abstraction metho ds for game theoretic poker.

Computers and Games, pages 333-345, 2000.

SAINT JOHN´S UNIVERSITY Color Depth and Color Spaces. In

http://www.csbsju.edu/itservices/teaching/c space/colors.htm, acessado em 14 de no-

vembro de 2005.

SKINNER, B. F. Ciˆencia e Comportamento Humano. In 1

Edi¸c˜ao, Martins Fontes,

S˜ao Paulo: 1979.

SOFUTSAL! T´atica de Jogo. In http://www.sofutsal.com/novo sofutsal/taticas.htm,

acessado em 14 de novembro de 2005.

SPAAN, M. T. J. and GROEN, F. C. A. Team Coordination among Robotic Soccer

Players. In: RoboCup 2002: 409-416.

TAKAHASHI, Y., EDAZAWA, E., NOMA, K. and ASADA, M. Simultaneous Learn-

ing to Acquire Competitive Behaviors in Multi-Agent System based on a

Modular Learning System. Proceedings of the 2005 IEEE/RSJ International Con-

ference on Intelligent Robots and Systems, pp.153-159, 2005.

THOMAS, J., BLAIR, A. and BARNES, N. Towards an eﬃcient optimal trajec-

tory planner for multiple mobile robots. Proceedings of the 2003 International

Conference on Intelligent Robots and Systems, 2291-2296.

TUCKER, A. W. On Jargon: The Prisoner’s Dilemma. UMAP Journal 1, 101, 1980.

UB ROBOTICS An undergraduate club of the University at Buﬀalo. In

http://www.eng.buﬀalo.edu/ubr/rcmedia.php, acessado em 30 de janeiro de 2006.

139

VAIL, D. and VELOSO, M. Dynamic Multi-Robot Coordination. In Multi-Robot

Systems, Kluwer, 2003.

VIDAL, J. M. Learning in Multiagent Systems: An Introduction from a Game-

Theoretic Perspective. CoRR cs.MA/0308030, (2003).

VON NEUMANN, J. and MORGENSTERN, O. Theory of Games and Economic

Behaviour. Princeton University Press, 1944.

VOSER, R. C. Futsal: Princ´ıpios T´ecnicos e T´aticos. Rio de Janeiro, Editora Sprint,

2001.

WILLS, P. The Hardware Design Of A Smart Camera For The Robot Soccer

Environment. Bachelor’s Thesis, School of Engineering - The University of Queens-

land, 2001.

ZICKLER, S., LICITRA, M. Rob oCup SSL 2005 Team Description: Wingers.

2005.

140

9 ANEXOS

141

9.1 ANEXO 1: REGRAS DA ROBOCUP SMALL SIZE LEAGUE (F-180)

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

9.2 ANEXO 2: DATA SHEET DO TRANSMISSOR RF KEYMARK TXC1

168

169

170

9.3 ANEXO 3: DATA SHEET DO RECEPTOR RF KEYMARK RXD1

171

172

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 