Algoritmos Genéticos na Evolução do Aprendizado

1

Algoritmos Genéticos na Evolução do Aprendizado

Objetivo

Avaliar o desempenho de Algoritmos Genéticos no controle de navegação de um robô.

2

Descrição do Problema

• Fazer com que o robô aprenda a chegar a um objetivo((xxff, , yyff),), a partir de uma posição inicial ((xxii, , yyii),), não colidindo com os obstáculos exis tentes.

• O robô deve aprender a chegar a diferentes objetivos, partindo de diferentes posições iniciais em diferentes mundos.

(xi, yi)

(xf, yf)

Ambiente de Simulação“Khepera Simulator”

• Simula um robô (sensores + motores) e mundos com obstáculos.

• Permite a implementação de algoritmos de controle para o robô, utilizando-se a linguagem C ou C++.

• Dispõe de uma biblioteca de funções, possibilitando direcionar e visualizar seus respectivos movimentos e resultados.

3

Interface do Simulador Khepera

8 Sensores:

0 ≤≤≤≤ Si≤≤≤≤ 1023

Variáveis do Robô

2 Motores com velocidades:

-10 ≤≤≤≤ M1≤≤≤≤ 10

-10 ≤≤≤≤ M2≤≤≤≤ 10

4

Modelagem do Algoritmo Genético

• Modelagem do Problema• Representação do Cromossoma• Função de Avaliação• Criação da População Inicial• Conjunto de Parâmetros

Modelagem do Problema

• Controle (objetivo X obstáculos)• Leitura dos Sensores• Senso de Direção• Velocidade

5

Modelo de Controle

• Cada estado do robô (sensores)(sensores) define uma atitude (velocidade dos motores)(velocidade dos motores)

• Situações possíveis:– Robô livre:

• objetivo: à frente, à esquerda, à direita e atrás

– Obstáculos detectados:• à esquerda • à direita • atrás

Modelagem da Leitura dos Sensores

Sesq

Satrás

Sdir

S3S1S2 S4

S5

S6S7

Sesq = ( S0 + S1 + S2 ) / 3 Sdir = ( S3 + S4 +S5 ) / 3 Satrás = ( S6 + S7 ) / 2

Se S xxx < limiar (900)

então obstáculo não detectado

S0

6

Modelagem do Senso de Direção

A diferença de Â2 por Â1 indica se o objetivo está à frente, à esquerda, à direita, ou atrás do “Khepera”, e por conseguinte, define a sua direção

Posição angular do robô em relação ao mundo

xf,yf)

Exemplo: Â1 = 90o

Â2 = arctan[(y -yf) / (xf - x)]( x,y)

Modelagem do Senso de Direção (Cont.)

Â2 - Â1 3π/4 π/4

Objetivo à esquerda

Objetivo atrás Objetivo à f rente

Objetivo à direita

-3π/4 - π/4

1a Modelagem do Senso de Direção

Â2 - Â1 3π/4 π/4 Objetivo à direita Objetivo à direita um pouco um pouco deslocado deslocado Objetivo atrás à f rente Objetivo atrás um pouco á frente um pouco deslocado à esquerda deslocado à esquerda π 0 Objetivo atrás um Objetivo à frente pouco deslocado um pouco deslocad à direita Objetivo Objetivo à direita à direita um `a direita um pouco deslocado pouco deslocado atrás ̀ a f rente -3π/4 -π/4 2a Modelagem do Senso de Direção

7

Modelagem do Senso de Direção (Cont.)

A partir destas entradas para ambas as modelagens do senso de direção, define-se o estado do robô pela regra descrita abaixo:

Se ((Sesq > L) ou (Sdir >L) ou (Satrás > L)) /* L (limiar) ∈ [0,1023] Então Obstáculo detectado Maior (Sesq ,Sdir ,Satrás) Senão Obstáculo não detectado (Robô livre) Direção = Â2 - Â1

Representação do Cromossoma

Cada estado corresponde a uma única atitude (par de velocidades M1 e M2), e cada atitude corresponde a um gene do cromossoma.

Livre Obstáculo

M1, M2 M1, M2 M1, M2 M1, M2 M1, M2 M1, M2 M1, M2 Frente Esquerda Direita Atrás Esquerda Direita Atrás Modelagem do Cromossoma com 7 Genes

Livre Obstáculo

M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 Frente Frente Esq. Esq. Di r. Dir Atrás Atrás Esq. Dir. Atrás Esq. Dir. Frente Atrás Frente Atrás Esq. Dir.

Modelagem do Cromossoma com 11 Genes

8

Avaliação de um Cromossoma

•• F(c) = f(velocidade, direção, objetivo)F(c) = f(velocidade, direção, objetivo)• Velocidade:

– quanto mais veloz, melhor• Direção:

– se o robô está de frente para o objetivo, melhor • Objetivo:

– procura-se sempre se aproximar do objetivo e longe de obstáculos

Velocidade

• A velocidade dos motores está compreendida na faixa de -10 a 10 (valores inteiros)

• O objetivo é que o robô ande com a velocidade máxima nos seus motores

• Se os motores estiverem com valores altos (módulos), é dado uma nota alta a velocidade

9

Direção

• A direção também está relacionada com a velocidade

• Deseja-se que o robô esteja sempre de frente para o seu objetivo

• Se os motores estiverem com valores altos e positivos, é dado uma nota alta a direção

Objetivo

• Leva-se em consideração se com uma certa atitude tomada, o robô se aproxima ou se afasta do objetivo

• A nota dada ao objetivo é proporcional a quanto o robô se aproxima do objetivo e se afasta de obstáculos

10

Função de Avaliação

Seja: - Vi : Velocidade da a titude i; - Di : Direção da atitude i; - Ai : Avaliação da atitude i; - F(ck) : Avaliação do cromossoma k; - TPi : Total de passos executados pela atitude i; - AAit : Avaliação da atitude i no passo (execução) t; - ∆di : Variação da distância (com relação ao objetivo) provocada pela atitude i em um passo; - ∆gi : Variação do ângulo (com relação ao objeto) provocada pela atitude i em um passo; - St : Leitura do maior sensor no passo t; - dmax : Distância máxima que o robô consegue percorre em um passo; - gmax : Ângulo máximo que o robô consegue girar em um passo; - Mmax : Velocidade máxima do motor (igual a 10); - Smax : Leitura máxima do sensor (igual a 1023).

Função de Avaliação - 7 Genes Atitudes 1 2 3 4 5 6 7

M1, M2 M1, M2 M1, M2 M1, M2 M1, M2 M1, M2 M1, M2 F(ck) = Soma (Vi *Di * Ai) onde i (atitude) = [1,7]; 0 ≤≤≤≤ Vi ≤≤≤≤ 1; 0 ≤≤≤≤ Ai ≤≤≤≤ 1 Vi = ( |M1|+|M2| ) / ( 2 * Mmax ) Di = ( 1 + (( M1 + M2 ) / ( 2 * Mmax ))) / 2 Ai = 0 se TPi = 0 Ai = Soma( AAit ) / TPi se TPi ≠ 0, onde t = [1,Tpi] AAit = ∆di / dmax se i = 1 e ∆di < 0 ,senão AAit = 0; AAit = ∆gi / gmax se i = [2,3,4] e ∆gi < 0 ,senão AAit = 0; AAit = 1 - St / Smax se i = [5,6,7].

11

Função de Avaliação - 11 Genes Atitudes

1 2 3 4 5 6 7 8 9 10 11 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2 M1,M2

F(ck) = Soma (Vi *Di * Ai) onde i (atitude) = [1,11]; 0 ≤≤≤≤ Vi ≤≤≤≤ 1; 0 ≤≤≤≤ Ai ≤≤≤≤1 Vi = ( |M1|+|M2| ) / ( 2 * Mmax ) Di = ( 1 + (( M1 + M2 ) / ( 2 * Mmax ))) / 2 Ai = 0 se TPi = 0 Ai = Soma( AAit ) / TPi se Tpi ≠ 0, onde t = [1,Tpi] AAit = ∆di / dmax se i = [1,2] e ∆di < 0 ,senão AAit = 0; AAit = ∆gi / gmax se i = [3,4,5,6,7,8] e ∆gi < 0 ,senão AAit = 0; AAit = 1 - St / Smax se i = [9,10,11].

Criação da População Inicial

• Foram gerados números inteiros aleatórios entre -10 e +10 (velocidades mínima e máxima válidas dos motores)

• O valor 0 (zero) não é gerado

12

Resultados Obtidos

Curvas de DesempenhoCromossoma de 7 Genes

EVOLUÇÃO DE UMA RODADACROM OSSOMA DE 7 GENES

0

0, 5

1

1, 5

2

2, 5

3

3, 5

4

4, 5

NÚMERO DE GERAÇÕES

AVA

LIA

ÇÃO

Se qüênci a1

13


MÉDIA DAS AVALIAÇÕES DE 25 R ODAD AS CR OMOSSOMA DE 7 GENES

SEM ELETISMO A CADA ROD ADA

0

0,5

1

1,5

2

2,5

3

3,5

4

4,5

1 3 5 7 9

11

13

15

17

19

21

23

25

27

29

31

33

35

37

39

41

43

45

47

49


AV

AL

IAÇ

ÃO

Seqüência1


MÉDIA DAS AVALIAÇÕES DE 25 RODADASCROMOSSOMA DE 7 GENES

COM ELITISMO A CADA RODADA

3 ,9

4

4 ,1

4 ,2

4 ,3

4 ,4

4 ,5

4 ,6

4 ,7

4 ,8

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49


AVAL

IAÇÃ

O

Seqüência1

14


EVOLU ÇÃO DE U MA ROD ADACR OMOSSOMA D E 11 GEN ES

0

0,5

1

1,5

2

2,5

3

3,5

4

4,5

5

1 3 5 7 9

11

13

15

17

19

21

23

25

27

29

31

33

35

37

39

41

43

45

47

49

NÚ MER O D E GER AÇÕES

AVA

LIAÇ

ÃO

Seqüência1


MÉDIA DA AVALIAÇÕES DE 25 RODADASCROMOSSOMA DE 11 GENES

SEM ELITISMO A CADA RODADA

0

0,5

1

1,5

2

2,5

3

3,5

4

4,5

5

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49

NÚM ERO DE GERAÇÕES

AVAL

IAÇÃ

O

Seqüênc ia1

15


MÉDIA DAS AVALIAÇÕES DE 25 RODADASC ROMOSSOMA DE 11 GENES

COM ELITISMO A CADA RODADA

5,5

5 ,55

5,6

5 ,65

5,7

5 ,75

5,8

5 ,85

5,9

5 ,95

6

6 ,05

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49


AVAL

IAÇÃO

Seqüência1

Trajetória Percorrida pelo Robô “Khepera” no mundo “la1.world”

SITUAÇÃO 1 CROMOSSOMA DE 7 GENES CROMOSSOMA DE 11 GENES

16





17



Comparação entre osCromossomas de 7 e de 11 Genes

0

100 0

200 0

300 0

400 0

500 0

600 0

1 2 3 4 5

SITUAÇÃO

TOTA

L DE

PAS

SOS

C ROMOSSOM DE 11 GENESC ROMOSSOMA DE 7 GENES

18

Velocidade do Cromossoma de 11 Genes em Relação ao de 7 Genes

1 0,00%

29, 41%

71, 65%

100,00%

20,83%

Sit uação 1

Sit uação 2Sit uação 3

Sit uação 4Sit uação 5


SITUAÇÃO 1

CRO MOSS OMA D E 7 GENES CROM OSSO MA DE 11 GENES

19


SITUAÇÃO 2

CROMOSSOMA DE 7 GENES CROMOSSSOMA DE 11 GENES


SITUAÇÃO 3

CROMOSSOMA DE 7 GENES CROMOSSOMA DE 11 GENES

20

Comparação entre osCromossomas de 7 e de 11 Genes

0

500

1000

1500

2000

2500

3000

3500

4000

4500

1 2 3

SIT UAÇÃO

TOTA

L DE P

ASSO

S

CROM OSSOMA DE 11 GENESCROM OSSOMA DE 7 GENES

Velocidade do Cromossoma de 11 Genes em Relação ao de 7 Genes

84,62%

40,00%

214,29%

Si tuação 1

Si tuação 2Si tuação 3

21

Trajetória Percorrida pelo Robô no mundo “home.world”

SITUAÇÃO 1

CROM OSS OMA D E 7 G EN ES CROMO SSO MA DE 11 GENES


SITUAÇÃO 2


22


SITUAÇÃO 3

CR OMOSSOMA DE 7 GENES CR OMOSSOMA DE 11 GENES


SITUAÇÃO 4

CROMOSSOMA DE 7 GENES CROMOSSOMA DE 1 1 GENES

23

Quadro Comparativo entre osCromossomas de 7 e de 11 Genes

Total de Passos com Cromossoma de 7

Genes Total de passos com Cromossoma de 11

Gen es Situação 1 O robô não consegue chegar ao objetivo 729 Situação 2 1124 618 Situação 3 O robô não consegue chegar ao objetivo O robô não consegue chegar ao objetivo Situação 4 O robô não consegue chegar ao objetivo 1655


SITUAÇÃO 1


24


SITUAÇÃO 2



SITUAÇÃO 3

CROMOS SOMA DE 7 GENES CROMOS SOMA DE 11 GENES

25

Quadro Comparativo entre osCromossomas de 7 e de 11 Genes

Total de Pas sos com Cromossoma de 7Genes

Total de Passos com Cromoss om a de 11Genes

Situação 1 O robô não cons egue chegar ao objet ivo 2537Situação 2 O robô não cons egue chegar ao objet ivo 1518Situação 3 O robô não cons egue chegar ao objet ivo O robô não consegue chegar ao objetivo

Conclusões

• O trabalho demonstrou o potencial de algoritmo genético no problema de evolução do aprendizado

• A eficiência do modelo do cromossoma foi comprovada, pois o robô aprendeu a chegar ao objetivo sem colidir nos obstáculos e em diversos mundos

• Com o cromossoma de 11 genes, o robô obteve melhores resultados do que com o cromossoma de 7 genes:– O robô alcançou o objetivo com menor número de

passos

26

Conclusões (Cont.)

• O robô em certas circunstâncias, alcançou o seu objetivo com um número muito grande de passos, devido ao fato de que, ao se encontrar numa região com muitos obstáculos, ele tenta se livrar dos mesmos, tomando atitudes que o afastam ao invés de aproximá- lo do objetivo

• Em certas situações o robô repetiu a mesma trajetória sem alcançar o seu objetivo. Uma possível solução para esse problema ser ia acrescentar ao modelo um recurso de memória.

Documents

Algoritmos Genéticos na Evolução do Aprendizado