Uso de heurísticas para a aceleração do aprendizado por reforço por Reinaldo Augusto da Costa Bianchi - Versão HTML

ATENÇÃO: Esta é apenas uma visualização em HTML e alguns elementos como links e números de página podem estar incorretos.
Faça o download do livro em PDF, ePub, Kindle para obter uma versão completa.

Reinaldo Augusto da Costa Bianchi

Uso de Heur´ısticas para a Aceleraç˜

ao do

Aprendizado por Reforço

Tese apresentada à Escola Politécnica

da Universidade de S˜ao Paulo para

obtenç˜ao do t´ıtulo de Doutor em

Engenharia.

S˜ao Paulo

2004

Reinaldo Augusto da Costa Bianchi

Uso de Heur´ısticas para a Aceleraç˜

ao do

Aprendizado por Reforço

Tese apresentada à Escola Politécnica

da Universidade de S˜ao Paulo para

obtenç˜ao do t´ıtulo de Doutor em

Engenharia.

Área de concentraç˜ao:

Sistemas Digitais

Orientadora:

Profa. Dra. Anna Helena Reali Costa

S˜ao Paulo

2004

Ficha Catalográfica

Bianchi, Reinaldo Augusto da Costa

Uso de Heur´ısticas para a Aceleraç˜ao do Aprendizado por Reforço

/ Reinaldo Augusto da Costa Bianchi – S˜ao Paulo, 2004.

Ediç˜ao Revisada. 174 p.

Tese (Doutorado)

— Escola Politécnica da Universidade

de S˜ao Paulo.

Departamento de Engenharia de Computaç˜ao

e Sistemas Digitais.

1. Inteligência Artificial. 2. Aprendizado Computacional

3. Robótica Móvel Inteligente. 4. Robôs.

I. Universidade de S˜ao Paulo. Escola Politécnica. Departamento de

Engenharia de Computaç˜ao e Sistemas Digitais II.t

Life can only be understood going backwards, but it must be lived going forwards.

(Kierkegaard)

Agradecimentos

Aos amigos e companheiros do Laboratório de Técnicas Inteligentes da Escola Po-

litécnica da USP: Alexandre Sim˜oes, Fabr´ıcio Barth, Gustavo Lugo, Júlio Kawai,

Jomi Hübner, Lu´ıs Ferreira Filho, Márcio Seixas, Maria das Graças Marietto,

Rafael Pacheco e Valguima Odakura que colaboraram de inúmeras maneiras du-

rante esse per´ıodo. Em especial à Diana Adamatti, Regina Cantele e Valdinei

Freire da Silva pela colaboraç˜ao na finalizaç˜ao deste trabalho.

Aos professores Jaime Sim˜ao Sichman e José Jaime da Cruz da Escola Po-

litécnica da USP, que estavam sempre dispostos a ajudar. Às professoras Leliane

Nunes de Barros do Instituto de Matemática e Estat´ıstica da USP e Lúcia Franco

da Universidade Federal de Itajubá. Ao Professor Renê Pegoraro, da Universi-

dade Estadual Paulista. Aos professores do Centro Universitário da FEI, que

incentivaram este projeto: Márcio Rillo, Jo˜ao Martino, Fabr´ıcio Leonardi, Flávio

Tonidandel, Alessandro La Neve, Aldo Belardi e Devair Arrabaça.

Ao professor Carlos Henrique Costa Ribeiro, do Instituto Tecnológico de Ae-

ronáutica, que acompanhou este trabalho sugerindo melhorias, discutindo o con-

teúdo e indicando os melhores caminhos a seguir.

À minha orientadora, Anna Helena Reali Costa, pela amizade.

À minha fam´ılia, pelo suporte e incentivo constante.

À Mayra.

Resumo

Este trabalho prop˜oe uma nova classe de algoritmos que permite o uso de

heur´ısticas para aceleraç˜ao do aprendizado por reforço. Esta classe de algoritmos,

denominada “Aprendizado Acelerado por Heur´ısticas” ( “Heuristically Accelerated

Learning” – HAL), é formalizada por Processos Markovianos de Decis˜ao, introdu-

zindo uma funç˜ao heur´ıstica H para influenciar o agente na escolha de suas aç˜oes,

durante o aprendizado. A heur´ıstica é usada somente para a escolha da aç˜ao a

ser tomada, n˜ao modificando o funcionamento do algoritmo de aprendizado por

reforço e preservando muitas de suas propriedades.

As heur´ısticas utilizadas nos HALs podem ser definidas a partir de conheci-

mento prévio sobre o dom´ınio ou extra´ıdas, em tempo de execuç˜ao, de ind´ıcios

que existem no próprio processo de aprendizagem. No primeiro caso, a heur´ıstica

é definida a partir de casos previamente aprendidos ou definida ad hoc. No se-

gundo caso s˜ao utilizados métodos automáticos de extraç˜ao da funç˜ao heur´ıstica

H chamados “Heur´ıstica a partir de X” ( “Heuristic from X” ).

Para validar este trabalho s˜ao propostos diversos algoritmos, entre os quais, o

Q–Learning Acelerado por Heur´ısticas” ( Heuristically Accelerated Q–Learning

HAQL), que implementa um HAL estendendo o conhecido algoritmo Q–Learning,

e métodos de extraç˜ao da funç˜ao heur´ıstica que podem ser usados por ele. S˜ao

apresentados experimentos utilizando os algoritmos acelerados por heur´ısticas pa-

ra solucionar problemas em diversos dom´ınios – sendo o mais importante o de

navegaç˜ao robótica – e as heur´ısticas (pré-definidas ou extra´ıdas) que foram usa-

das. Os resultados experimentais permitem concluir que mesmo uma heur´ıstica

muito simples resulta em um aumento significativo do desempenho do algoritmo

de aprendizado de reforço utilizado.

Abstract

This work presents a new class of algorithms that allows the use of heuristics

to speed up Reinforcement Learning (RL) algorithms. This class of algorithms,

called “Heuristically Accelerated Learning” (HAL) is modeled using a convenient

mathematical formalism known as Markov Decision Processes. To model the

HALs a heuristic function H that influences the choice of the actions by the

agent during its learning is defined. As the heuristic is used only when choosing

the action to be taken, the RL algorithm operation is not modified and many

proprieties of the RL algorithms are preserved.

The heuristic used in the HALs can be defined from previous knowledge about

the domain or be extracted from clues that exist in the learning process itself. In

the first case, the heuristic is defined from previously learned cases or is defined

ad hoc. In the second case, automatic methods for the extraction of the heuristic

function H called “Heuristic from X” are used.

A new algorithm called Heuristically Accelerated Q–Learning is proposed,

among others, to validate this work. It implements a HAL by extending the

well-known RL algorithm Q–Learning. Experiments that use the heuristically

accelerated algorithms to solve problems in a number of domains – including

robotic navigation – are presented. The experimental results allow to conclude

that even a very simple heuristic results in a significant performance increase in

the used reinforcement learning algorithm.

Sumário

Lista de Figuras

Lista de Tabelas

Lista de Abreviaturas

Lista de S´ımbolos

1 Introduç˜

ao

1

1.1 Dom´ınio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2 Objetivos e contribuiç˜oes . . . . . . . . . . . . . . . . . . . . . . .

3

1.3 Histórico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.4 Organizaç˜ao do trabalho . . . . . . . . . . . . . . . . . . . . . . .

6

2 Aprendizado por Reforço

8

2.1 O Problema do Aprendizado . . . . . . . . . . . . . . . . . . . . .

8

2.2 Processos Markovianos de Decis˜ao . . . . . . . . . . . . . . . . . .

9

2.3 MDPs e Programaç˜ao Dinâmica . . . . . . . . . . . . . . . . . . .

11

2.4 Q–Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.5 O método das Diferenças Temporais – TD-Learning . . . . . . . .

17

2.6 SARSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.7 Jogos de Markov e o Minimax–Q . . . . . . . . . . . . . . . . . .

21

2.8 Processos Markovianos de Decis˜ao Generalizados e o Q–Learning

Generalizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

2.9 Discuss˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3 Aceleraç˜

ao do aprendizado por reforço

28

3.1 Aceleraç˜ao por Generalizaç˜ao . . . . . . . . . . . . . . . . . . . .

29

3.1.1

Generalizaç˜ao Temporal . . . . . . . . . . . . . . . . . . .

29

3.1.2

Generalizaç˜ao Espacial . . . . . . . . . . . . . . . . . . . .

30

3.2 Aceleraç˜ao por Abstraç˜ao . . . . . . . . . . . . . . . . . . . . . .

32

3.2.1

Abstraç˜ao Temporal . . . . . . . . . . . . . . . . . . . . .

32

3.2.2

Abstraç˜ao Espacial . . . . . . . . . . . . . . . . . . . . . .

32

3.3 Aceleraç˜ao por Distribuiç˜ao . . . . . . . . . . . . . . . . . . . . .

37

3.3.1

Q–Learning Distribu´ıdo . . . . . . . . . . . . . . . . . . .

40

3.3.2

Dyna–Q Multiagente . . . . . . . . . . . . . . . . . . . . .

42

3.3.3

Otimizaç˜ao por Colônia de Formigas . . . . . . . . . . . .

44

3.4 Aceleraç˜ao Baseada em Casos . . . . . . . . . . . . . . . . . . . .

49

3.5 Discuss˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

4 Uso de heur´ısticas para aceleraç˜

ao do aprendizado por reforço

56

4.1 Introduç˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

4.2 A funç˜ao heur´ıstica H . . . . . . . . . . . . . . . . . . . . . . . .

60

4.3 “Aprendizado Acelerado por Heur´ısticas” como uma busca informada 67

4.4 Os métodos “Heur´ıstica a partir de X” . . . . . . . . . . . . . . .

69

4.4.1

Extraç˜ao da Estrutura . . . . . . . . . . . . . . . . . . . .

71

4.4.2

Construç˜ao da Heur´ıstica . . . . . . . . . . . . . . . . . . .

72

4.5 O algoritmo Q–Learning Acelerado por Heur´ısticas . . . . . . . .

73

4.6 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

78

5 Experimentos no dom´ınio de navegaç˜

ao rob´

otica

79

5.1 O dom´ınio dos robôs móveis . . . . . . . . . . . . . . . . . . . . .

79

5.2 Uso de métodos “Heur´ıstica a partir de X” em tempo de execuç˜ao

80

5.2.1

Extraç˜ao de estrutura . . . . . . . . . . . . . . . . . . . .

81

5.2.2

Construç˜ao da heur´ıstica . . . . . . . . . . . . . . . . . . .

85

5.2.3

Discuss˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

5.3 Experimentos com o algoritmo HAQL . . . . . . . . . . . . . . . .

88

5.3.1

Navegaç˜ao robótica em ambiente desconhecido . . . . . . .

89

5.3.2

Navegaç˜ao robótica em ambiente pouco modificado . . . .

93

5.3.3

Navegaç˜ao robótica com reposicionamento da meta . . . . 100

5.3.4

Discuss˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

5.4 Simulaç˜ao de um robô real utilizando o ambiente Saphira . . . . . 104

5.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

6 Utilizaç˜

ao de heur´ısticas a priori para aceleraç˜

ao do aprendizado116

6.1 O problema do Carro na Montanha utilizando HA–SARSA( λ) . . 116

6.2 O problema do Pêndulo Invertido utilizando HATD( λ) . . . . . . 128

6.3 O problema do Caixeiro Viajante utilizando HADQL . . . . . . . 131

6.4 Futebol de Robôs utilizando HA–Minimax– Q . . . . . . . . . . . . 135

6.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

7 Conclus˜

ao e trabalhos futuros

143

Anexos

148

A

Estudo da convergˆ

encia da pol´ıtica e da funç˜

ao valor

148

B

Estudo da relaç˜

ao entre a qualidade da heur´ıstica e a evoluç˜

ao

do aprendizado

152

C

Evoluç˜

ao das visitas em um ambiente de grandes dimens˜

oes

155

D

Evoluç˜

ao da funç˜

ao valor

161

Referˆ

encias Bibliogr´

aficas

166

Índice Remissivo

174

Apˆ

endices

i

I

Resumo sobre estat´ıstica

i

I.1

O teste t de Student . . . . . . . . . . . . . . . . . . . . . . . . .

i

I.2

Erros médios . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

Lista de Figuras

2.1 Ciclo Percepç˜ao-Aç˜ao. . . . . . . . . . . . . . . . . . . . . . . . .

9

3.1 Exemplo de camadas de telhas em um CMAC para um problema

unidimensional. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.2 Exemplo das camadas de telhas em um CMAC. . . . . . . . . . .

34

3.3 Um exemplo de espaço de estados discretizado (esquerda) e a

árvore-kd correspondente (MUNOS; MOORE, 2002, pg. 295). . . .

36

3.4 Refinamentos sucessivos de um espaço discretizado. (MUNOS;

MOORE, 2002, pg. 300). . . . . . . . . . . . . . . . . . . . . . . .

37

3.5 O espaço discretizado utilizando o critério da variância para o

problema do carro na montanha (MUNOS; MOORE, 2002, pg. 302). 37

3.6 O grafo que identifica uma sub-tarefa (esquerda) e os valores da

funç˜ao que é a soluç˜ao para a sub-tarefa (direita) (DRUMMOND,

2002). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

3.7 Sala com paredes proposta por Drummond (2002), onde o quadrado marca a meta a atingir. . . . . . . . . . . . . . . . . . . . . . . . .

51

3.8 A funç˜ao valor obtida utilizando Q–Learning apresenta grandes

descontinuidades (área escura) e o grafo constru´ıdo para a sala

superior esquerda (DRUMMOND, 2002, p. 62). . . . . . . . . . . .

51

3.9 Um ambiente com duas salas (DRUMMOND, 2002, p. 66). . . . .

52

3.10 A funç˜ao valor para o ambiente da figura 3.9 (DRUMMOND, 2002,

p. 67). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.11 O gradiente da funç˜ao valor da figura 3.10, o pol´ıgono extra´ıdo

e o grafo constru´ıdo (à esquerda). A expans˜ao da serpente até a

acomodaç˜ao (à direita) (DRUMMOND, 2002, p. 71). . . . . . . . .

53

3.12 Representaç˜oes gráficas de uma soluç˜ao mostrando as sub-tarefas

do problema da figura 3.7 (DRUMMOND, 2002, p. 63). . . . . . .

54

3.13 A extraç˜ao e reutilizaç˜ao de uma funç˜ao armazenada na base de

casos. A funç˜ao é rotacionada e ampliada para encaixar na nova

sub-tarefa (DRUMMOND, 2002, p. 64). . . . . . . . . . . . . . . .

54

4.1 Estando no estado S e desejando ir para o estado Sd, o valor de

H( s, a 1) da aç˜ao que leva à Sd = 0 , 21 enquanto para as outras

aç˜oes é nulo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

4.2 Se mover de s 1 diretamente para s 3 fizer parte da pol´ıtica ótima,

ent˜ao H é admiss´ıvel quando H( s 1 , a 3) ≥ H( s 1 , a 2). . . . . . . . .

68

4.3 Esquema geral dos métodos “Heur´ıstica a partir de X”. . . . . . .

71

4.4 O estado s 1 possui ambos os valores, máximo e m´ınimo, para a

funç˜ao valor-aç˜ao Q (a execuç˜ao da aç˜ao a 2 em qualquer estado

sempre recebe o reforço negativo m´ınimo e a execuç˜ao da aç˜ao a 1

em s 1 recebe o reforço máximo). . . . . . . . . . . . . . . . . . . .

77

5.1 Sala com paredes (representadas pelas linhas escuras) discretizada

em uma grade de posiç˜oes (representados pelas linhas mais suaves). 80

5.2 Pol´ıtica ótima para um robô móvel em um ambiente com 25 x 25

posiç˜oes e algumas paredes. Setas duplas significam que, em uma

mesma posiç˜ao, n˜ao faz diferença qual das duas aç˜oes a tomar. . .

81

5.3 Estruturas geradas por quatro métodos de extraç˜ao de estrutura

ao final do centésimo episódio de treinamento. . . . . . . . . . . .

83

5.4 A imagem da tabela V ( st) e o seu gradiente ao final do centésimo

episódio de treinamento (células mais claras indicam maiores valores). 84

5.5 A imagem da tabela V ( st), o seu gradiente e o mapa criado ao

final do centésimo episódio de treinamento para um ambiente com

paredes delgadas. . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5.6 Heur´ısticas constru´ıdas utilizando o método “Heur´ıstica a partir

de X” a partir das estruturas geradas pelos métodos de extraç˜ao

de estrutura, apresentadas na figura 5.3 . . . . . . . . . . . . . . .

87

5.7 Salas com paredes (representadas pelas linhas claras) usadas por

Drummond (2002), onde a meta a atingir se encontra em um dos

cantos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

90

5.8 Resultado para a aceleraç˜ao em um ambiente desconhecido, ao final

do décimo episódio, utilizando “Heur´ıstica a partir de Exploraç˜ao”,

com barras de erro (inferior em monolog). . . . . . . . . . . . . .

91

5.9 Resultado do teste t de Student para um ambiente desconhecido

(inferior em monolog). . . . . . . . . . . . . . . . . . . . . . . . .

92

5.10 O ambiente usado para definir a heur´ıstica (a) e o ambiente onde

ela é utilizada (b). . . . . . . . . . . . . . . . . . . . . . . . . . .

94

5.11 A heur´ıstica gerada para o ambiente da figura 5.10-a. . . . . . . .

96

5.12 A pol´ıtica ótima para o ambiente da figura 5.10-b. . . . . . . . . .

97

5.13 Resultado para a aceleraç˜ao em um ambiente modificado, ao final

do décimo episódio, utilizando “Heur´ıstica a partir de Exploraç˜ao”

(inferior com barras de erro). . . . . . . . . . . . . . . . . . . . . .

98

5.14 Resultado do teste t de Student para aceleraç˜ao na 10. a iteraç˜ao,

em um ambiente modificado. . . . . . . . . . . . . . . . . . . . . .

99

5.15 Resultado do aprendizado quando a meta é reposicionada no 5000. o

episódio, utilizando “Heur´ıstica a partir de Exploraç˜ao” no HAQL

(em escala monolog na parte superior e ampliado na inferior). . . 101

5.16 Resultado do aprendizado quando a meta é reposicionada no 5000. o

episódio, utilizando “Heur´ıstica a partir de Exploraç˜ao” no HAQL.

Com barras de erro (inferior em monolog). . . . . . . . . . . . . . 102

5.17 Resultado do teste t de Student para reposicionamento da meta

(inferior em monolog). . . . . . . . . . . . . . . . . . . . . . . . . 103

5.18 A plataforma Saphira 8.0. A figura superior apresenta a tela do

aplicativo (com a posiç˜ao do robô no plano de referência) e a infe-

rior, o monitor do simulador (apresentando a posiç˜ao real do robô). 107

5.19 Localizaç˜ao Monte Carlo: os pontos vermelhos indicam a posiç˜ao

das part´ıculas, cada uma definindo uma posiç˜ao provável do robô.

A incerteza na posiç˜ao do robô é menor na imagem superior do

que nas inferiores. . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

5.20 O robô atravessando uma parede – no plano de referência – devido

ao erro de localizaç˜ao. . . . . . . . . . . . . . . . . . . . . . . . . 110

5.21 Número de visitas (branco indica um número maior de visitas) e

o esboço do mapa criado utilizando o método “Estrutura a partir

de Exploraç˜ao” para o ambiente Saphira. . . . . . . . . . . . . . . 111

5.22 A heur´ıstica criada a partir do esboço do mapa apresentado na

figura 5.21. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

5.23 Resultado do uso da aceleraç˜ao no quinto episódio usando o algo-

ritmo HAQL no ambiente de simulaç˜ao Saphira. . . . . . . . . . . 113

5.24 Caminhos percorridos pelo robô utilizando o Q–Learning (superior)

e o HAQL (inferior) no ambiente de simulaç˜ao Saphira 8.0. . . . . 114

6.1 Descriç˜ao do problema do Carro na Montanha. . . . . . . . . . . . 117

6.2 Tabela da funç˜ao valor para o problema do Carro na Montanha

(superior em 3D, inferior em curvas de n´ıvel). . . . . . . . . . . . 118

6.3 Número de passos necessários para atingir a meta para os algorit-

mos Q–Learning, SARSA( λ), HAQL e HAS( λ) para o problema

do Carro na Montanha (inferior em monolog). . . . . . . . . . . . 122

6.4 O reforço recebido para os algoritmos SARSA( λ), HAQL e HAS( λ)

para o problema do Carro na Montanha (inferior com barras de

erros). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

6.5 Caminhos realizados no espaço de estados pelos algoritmos SARSA( λ)

(superior) e HAS( λ) (inferior) para o problema do Carro na Mon-

tanha. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

6.6 Caminhos finais realizados no espaço de estados para o problema

do Carro na Montanha. . . . . . . . . . . . . . . . . . . . . . . . . 125

6.7 Comparaç˜ao para o uso de vários valores de heur´ıstica no HAS( λ)

para o problema do Carro na Montanha (Número de passos na

figura superior e reforço recebido na inferior). . . . . . . . . . . . 126

6.8 Comparaç˜ao entre algoritmos SARSA( λ) e HAS( λ) para o problema

do Carro na Montanha. A figura superior mostra o resultado com

barras de erros e a inferior mostra o resultado do teste t de Student.127

6.9 O problema do Pêndulo Invertido. . . . . . . . . . . . . . . . . . . 128

6.10 Comparaç˜ao entre os algoritmos DQL, ACO e HADQL para o

Problema do Caixeiro Viajante kroA100 (inferior com barras de

erros). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

6.11 O ambiente proposto por Littman (1994). A figura mostra a

posiç˜ao inicial dos agentes. . . . . . . . . . . . . . . . . . . . . . . 137

6.12 A heur´ıstica utilizada para o ambiente da figura 6.11. As setas

indicam a aç˜ao a tomar. . . . . . . . . . . . . . . . . . . . . . . . 137

6.13 Resultados do saldo de gols para os algoritmos Minimax– Q e HAMMQ

contra um jogador com movimentaç˜ao aleatória para o Futebol de

Robôs de Littman (com barras de erro na figura inferior). . . . . . 139

6.14 Resultados do saldo de gols para os algoritmos Minimax– Q e HAMMQ

contra um agente utilizando o Minimax– Q (com barras de erro na

figura inferior). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

6.15 Resultados do teste t de Student entre os algoritmos Minimax–

Q e HAMMQ, treinando contra um agente com movimentaç˜ao

aleatória (superior) e contra agente utilizando o Minimax– Q (in-

ferior). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

A.1 Evoluç˜ao da diferença da funç˜ao valor e do valor calculado a partir

da pol´ıtica utilizando Programaç˜ao Dinâmica. Gráfico Normalizado.149

A.2 A convergência da pol´ıtica mais provável para a sala ao lado direito

da figura 5.2. O eixo x mostra o episódio de treinamento e o y, a

aç˜ao tomada (N, S, E, W). . . . . . . . . . . . . . . . . . . . . . . 151

B.1 Resultado do uso da aceleraç˜ao com a heur´ıstica correta no centésimo

episódio usando o algoritmo HAQL. . . . . . . . . . . . . . . . . . 153

B.2 Resultado do uso da aceleraç˜ao com uma heur´ıstica errada no

centésimo episódio usando o algoritmo HAQL. . . . . . . . . . . . 154

C.1 Planta do 2. o andar da mans˜ao de Bailicroft (SUMMERS, 2001),

onde a área em preto corresponde às paredes e a em branco, ao

espaço por onde o robô pode se mover. . . . . . . . . . . . . . . . 156

C.2 Visitas a novos estados (ampliado na figura inferior). . . . . . . . 157

C.3 Mapa criado a partir da exploraç˜ao. . . . . . . . . . . . . . . . . . 158

C.4 Resultado para a aceleraç˜ao no 20. o episódio utilizando “Heur´ıstica

a partir de Exploraç˜ao” com barras de erro (em monolog), para o

ambiente Bailicroft. . . . . . . . . . . . . . . . . . . . . . . . . . . 159

C.5 Resultado do teste t de Student para a aceleraç˜ao no 20. o episódio

no ambiente Bailicroft. . . . . . . . . . . . . . . . . . . . . . . . . 160

D.1 Evoluç˜ao da raiz do erro quadrático médio (RMSE) entre a funç˜ao

valor do algoritmo ( Q–Learning ou HAQL) e o valor V ∗, em relaç˜ao

ao total de passos (ampliado na figura inferior). . . . . . . . . . . 162

D.2 Funç˜ao valor gerada pelo Q–Learning (superior) e pelo HAQL (in-

ferior) ao final do 20 × 108 passo, utilizando o reforço positivo igual

a 10 ao atingir a meta. . . . . . . . . . . . . . . . . . . . . . . . . 163

D.3 Evoluç˜ao da raiz do erro quadrático médio (RMSE) entre a funç˜ao

valor do HAQL e o V ∗, para diversos valores de recompensa rece-

bida ao atingir a meta no final de um episódio. . . . . . . . . . . . 165

Lista de Tabelas

2.1 O algoritmo de Iteraç˜ao de Valor (BERTSEKAS, 1987). . . . . . .

13

2.2 O algoritmo de Iteraç˜ao de Pol´ıtica (BERTSEKAS, 1987, p. 199). .

14

2.3 O algoritmo Q–Learning (WATKINS, 1989). . . . . . . . . . . . .

18

2.4 O algoritmo Genérico T D( λ) (SUTTON; BARTO, 1998). . . . . .

21

2.5 O algoritmo Minimax– Q (LITTMAN, 1994). . . . . . . . . . . . .

23

2.6 Alguns modelos de MDPs Generalizados e suas especificaç˜oes (SZEPES-

V ´

ARI; LITTMAN, 1996, Teorema 3). . . . . . . . . . . . . . . . . .

25

3.1 O algoritmo QS (RIBEIRO, 1998, p. 53). . . . . . . . . . . . . . .

31

3.2 O algoritmo Q–Learning Distribu´ıdo (ROMERO; MORALES, 2000). 41

3.3 O algoritmo Ant Colony System (DORIGO; GAMBARDELLA, 1997). 48

4.1 As três hipóteses estudadas. . . . . . . . . . . . . . . . . . . . . .

58

4.2 O meta-algoritmo “Aprendizado Acelerado por Heur´ısticas” . . .

59

4.3 O algoritmo HAQL. . . . . . . . . . . . . . . . . . . . . . . . . . .

77

5.1 Resultado do teste t de Student para aceleraç˜ao no quinto episódio

usando o algoritmo HAQL no ambiente de simulaç˜ao Saphira. . . 112

6.1 A soluç˜ao com o menor número de passos, o tempo médio para

encontrá-la e o maior reforço recebido para o problema do Carro

na Montanha. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

6.2 Resultados para o problema do Pêndulo Invertido utilizando os

algoritmos TD( λ) e HATD( λ).

. . . . . . . . . . . . . . . . . . . 130

6.3 Melhor resultado encontrado pelos algoritmos DQL, ACO e HADQL

após 1000 iteraç˜oes. . . . . . . . . . . . . . . . . . . . . . . . . . . 133

6.4 Média dos resultados encontrados pelos algoritmos DQL, ACO e

HADQL após 1000 iteraç˜oes. . . . . . . . . . . . . . . . . . . . . . 133

6.5 Tempo médio (em segundos) para encontrar a melhor soluç˜ao para

os algoritmos DQL, ACO e HADQL, limitados a 1000 iteraç˜oes. . 133

6.6 Média do saldo cumulativo de gols e do número de vitórias para

todos os jogos realizados. . . . . . . . . . . . . . . . . . . . . . . . 142

D.1 Erros entre a funç˜ao valor gerada pelo HAQL e a funç˜ao valor

ótima V ∗, em relaç˜ao ao reforço recebido ao atingir a meta, ao

final do 20 × 108 passo. . . . . . . . . . . . . . . . . . . . . . . . . 164

Lista de Abreviaturas

ACO Ant Colony Optimization – Otimizaç˜ao por Colônia de Formigas

ACS Ant Colony System – Sistema de Colônia de Formigas

AR Aprendizado por Reforço

DQL Distributed Q–Learning Q–Learning Distribu´ıdo

HAL Heuristically Accelerated Learning – Aprendizado Acelerado por Heur´ısticas

HAQL Heuristically Accelerated Q–Learning Q–Learning Acelerado por Heur´ısticas

IA Inteligência Artificial

IAD Inteligência Artificial Distribu´ıda

ML Machine Learning – Aprendizado de Máquina

MDP Markov Decision Process – Processos de Decis˜ao Markovianos

PD Programaç˜ao Dinâmica

POMDP Partially Observable Markov Decision Process – Processos de Decis˜ao

Markovianos Parcialmente Observáveis

RNA Redes Neurais Artificiais

SMA Sistemas Multiagentes

TSP Travelling Salesman Problem – Problema do Caixeiro Viajante

VC Vis˜ao Computacional

Lista de S´ımbolos

α Taxa de aprendizagem

γ Fator de desconto para os reforços futuros

S Conjunto finito de estados

A Conjunto finito de aç˜oes

T Funç˜ao de Transiç˜ao de Estado

R Funç˜ao de Recompensa

H Funç˜ao Heur´ıstica

π Uma pol´ıtica

π∗ A pol´ıtica ótima

Q Funç˜ao Valor–Aç˜ao

ˆ

Q Uma estimativa da Funç˜ao Valor–Aç˜ao

Q∗ A Funç˜ao Valor–Aç˜ao ótima

V Funç˜ao Valor

ˆ

V Uma estimativa da Funç˜ao Valor

V ∗ A Funç˜ao Valor ótima

c.q.d.

1

1

Introduç˜

ao

Um dos objetivos da Inteligência Artificial (IA) é a construç˜ao de agentes

autônomos inteligentes capazes de realizar tarefas complexas de forma racional,

atuando em ambientes complexos do mundo real. N˜ao s˜ao necessárias muitas

consideraç˜oes para concluir que qualquer sistema autônomo deve possuir capa-

cidades de aprendizado que possibilitem a sua adaptaç˜ao a eventos imprevistos,

que surgem devido à falta de conhecimento prévio sobre ambientes complexos, a

adaptaç˜ao a mudanças no ambiente de atuaç˜ao e a melhoria do desempenho do

agente ao longo do tempo.

Aprendi-

Mitchell (1997) define o Aprendizado de Máquina ( Machine Learning – ML)

zado de

como o campo da IA cujo interesse é a construç˜ao de programas de computado-

Máquina

res que se aperfeiçoam automaticamente com a experiência. O aprendizado de

máquina tem sido usado com sucesso em quase todas as áreas do conhecimento

que utilizam computadores, como classificaç˜ao e reconhecimento de padr˜oes, con-

trole, jogos, entre outros. Uma definiç˜ao genérica para um agente autônomo que

aprende é dada por Russell e Norvig (2004, p. 613):

“Um agente aprendiz é aquele que pode melhorar seu comportamento através

do estudo diligente de suas próprias experiências”.

O aprendizado de máquina pode ser classificado pela maneira na qual o agente

interage com o ambiente em que atua para construir seu conhecimento em três

classes: supervisionado, n˜ao supervisionado ou por reforço.

O aprendizado supervisionado envolve a existência de um supervisor que in-

forma ao agente qu˜ao bem ele está atuando. De maneira geral, isto ocorre quando

o resultado de uma aç˜ao pode ser validada de alguma maneira. Usualmente é

apresentado ao agente um conjunto de treinamento, com os valores de entradas

(o estado do ambiente e a aç˜ao do agente) e os resultados esperados. Com base

1.1 Dom´ınio

2

na diferença entre os resultados obtidos e os esperados, o agente pode verificar e

corrigir o seu funcionamento.

Quando um agente n˜ao possui informaç˜oes sobre os resultados esperados para

as suas aç˜oes, o aprendizado é dito n˜ao supervisionado. Neste caso, o agente pode

aprender relaç˜oes entre os dados que ele percebe, agrupando conjuntos de dados

similares ou prevendo resultados futuros com base em aç˜oes passadas, sem a ajuda

de um supervisor.

No aprendizado por reforço (AR), um agente pode aprender a atuar de ma-

neira bem sucedida em um ambiente previamente desconhecido utilizando a ex-

perimentaç˜ao direta, por meio de tentativa e erro. Neste caso, o agente recebe

uma avaliaç˜ao incompleta sobre sua atuaç˜ao (o chamado reforço). Este trabalho

tem seu foco no aprendizado por reforço, que é o assunto do próximo cap´ıtulo.

1.1

Dom´ınio

O principal dom´ınio estudado neste trabalho é o dos agentes robóticos inteligentes

que atuam de maneira eficiente e autônoma em ambientes finitos e Markovianos.

Segundo Costa (2003), este dom´ınio é uma área de pesquisa fascinante por diver-

sas raz˜oes:

É uma área de pesquisa multidisciplinar, envolvendo disciplinas como: Bio-

logia, Ciência da Computaç˜ao, Ciências Cognitivas, Engenharias, Filosofia,

F´ısica, Matemática, Psicologia e Sociologia.

É uma área com um amplo espectro de aplicaç˜oes comerciais: navegaç˜ao

de ve´ıculos autônomos, transporte de objetos, manipulaç˜ao de objetos em

lugares insalubres ou pouco acess´ıveis, vigilância e limpeza de grandes área,

busca e resgate de pessoas em situaç˜ao de perigo, aplicaç˜oes em agricultura,

como colheita e semeadura autônoma, tratamento da terra, entre outras.

E pelo fato dos “robôs móveis serem, atualmente, a melhor aproximaç˜ao de

máquinas que imitam e emulam seres vivos. Assim, a Robótica Móvel In-

teligente contribui grandemente em pesquisas em vida artificial, motivadas

pela quest˜ao de o que seria vida e como entendê-la” (COSTA, 2003, p. 12).

1.2 Objetivos e contribuiç˜oes

3

Neste dom´ınio, o número de interaç˜oes necessárias para um agente apren-

der, geralmente, é muito grande. Quanto maior e mais complexo o ambiente, o

número de aç˜oes ou a quantidade de agentes, maior é a capacidade computacional

necessária para resolver um problema.

Além dos agentes robóticos inteligentes, outros dom´ınios, cujos resultados

também se aplicam à robótica, s˜ao estudados neste trabalho. Entre estes dom´ınios

est˜ao o do Pêndulo Invertido e o do Carro na Montanha.

Para que um robô móvel possa aprender a atingir metas espec´ıficas em ambi-

entes com exigências de atuaç˜ao em tempo real, é necessário aumentar o desem-

penho do aprendizado por reforço. Assim, torna-se de grande interesse propostas

de métodos que permitam a aceleraç˜ao do AR.

1.2

Objetivos e contribuiç˜

oes

Objetivo

O objetivo deste trabalho é propor uma classe de algoritmos que permite o uso de

heur´ısticas para aceleraç˜ao do aprendizado por reforço. Esta classe de algoritmos,

denominada “Aprendizado Acelerado por Heur´ısticas” ( “Heuristically Accelerated

Learning” – HAL), é formalizada utilizando o modelo de Processos Markovianos

de Decis˜ao.

As heur´ısticas utilizadas nos HALs podem ser definidas a partir de conheci-

mento prévio sobre o dom´ınio ou extra´ıdas, em tempo de execuç˜ao, de ind´ıcios

que existem no próprio processo de aprendizagem. No primeiro caso, a heur´ıstica

é definida a partir de casos previamente aprendidos ou definida ad hoc. Dessa

forma, a heur´ıstica é uma maneira de generalizaç˜ao do conhecimento que se tem

acerca de um dom´ınio. No segundo caso s˜ao utilizados métodos automáticos de

extraç˜ao da funç˜ao heur´ıstica H.

As principais contribuiç˜oes deste trabalho s˜ao:

Contribuiç˜

oes

A formalizaç˜ao da classe de algoritmos de “Aprendizado Acelerado por

Heur´ısticas” com a introduç˜ao de uma funç˜ao heur´ıstica H que influen-

cia a escolha das aç˜oes e é atualizada durante o processo de aprendizado,

preservando, no entanto, muitas das propriedades dos algoritmos de AR.

A proposta de métodos automáticos de extraç˜ao da funç˜ao heur´ıstica H,

1.3 Histórico

4

a partir do dom´ınio do problema ou do próprio processo de aprendizagem,

chamados “Heur´ıstica a partir de X” ( “Heuristic from X” ). De maneira ge-

ral estes métodos funcionam em dois estágios: o primeiro retira da estima-

tiva da funç˜ao valor informaç˜oes sobre a estrutura do dom´ınio e o segundo

encontra a heur´ıstica para a pol´ıtica usando as informaç˜oes extra´ıdas. Es-

tes estágios foram denominados de Extraç˜ao de Estrutura e Construç˜ao da

Heur´ıstica, respectivamente.

Outras contribuiç˜oes relevantes s˜ao:

A comparaç˜ao do uso da funç˜ao heur´ıstica H pelos HALs com o uso de

heur´ısticas em algoritmos de busca informada.

A verificaç˜ao de que as informaç˜oes existentes no dom´ınio ou em estágios

iniciais do aprendizado permitem definir a funç˜ao heur´ıstica H. Entre os

ind´ıcios existentes no processo de aprendizagem, os mais relevantes s˜ao a

funç˜ao valor em um determinado instante, a pol´ıtica do sistema em um

determinado instante e o caminho pelo espaço de estados que o agente

pode explorar.

A proposta do algoritmo “Q–Learning Acelerado por Heur´ısticas” ( Heuris-

tically Accelerated Q–Learning – HAQL), que implementa um HAL esten-

dendo o conhecido algoritmo Q–Learning de Watkins (1989).

O teste do algoritmo Heuristically Accelerated Q–Learning em diversos

dom´ınios, incluindo o dos robôs móveis autônomos e o problema do Carro

nas Montanha.

A implementaç˜ao e o teste de algoritmos acelerados por heur´ısticas baseados

em algoritmos bem conhecidos na literatura de aprendizado por reforço co-

mo o SARSA( λ), o TD( λ) e o Minimax– Q, atuando em diferentes dom´ınios

e mostrando a generalidade dos HALs.

1.3

Histórico

Este trabalho teve in´ıcio como uma pesquisa sobre o aprendizado em Sistemas

Multiagentes, com o objetivo de estender a arquitetura de controle distribu´ıda

1.3 Histórico

5

proposta pelo autor em seu mestrado (BIANCHI, 1998).

Esta arquitetura, chamada ViBRA, utiliza uma abordagem multiagentes para

integrar percepç˜ao, planejamento, reaç˜ao e execuç˜ao para resolver problemas onde

manipuladores robóticos realizam tarefas de montagens visualmente guiadas.

A arquitetura ViBRA é definida como uma sociedade dinâmica de agentes

autônomos, cada qual responsável por um comportamento espec´ıfico. Os agen-

tes comunicam-se através de uma rede descentralizada e totalmente conectada e

s˜ao organizados segundo uma estrutura de autoridade e regras de comportamen-

to. Esta arquitetura combina atividades de planejamento reativas (como evitar

colis˜oes) e deliberativas (como realizar uma montagem), atuando em ambientes

complexos de montagem utilizando manipuladores robóticos (COSTA; BARROS;

BIANCHI, 1998).

Uma das restriç˜oes na arquitetura ViBRA foi o uso de uma estrutura de

autoridade predefinida e fixa. Uma vez estabelecido que um agente tem pre-

cedência sobre outro, o sistema se comporta sempre da mesma maneira, n˜ao se

preocupando com quest˜oes de eficiência.

Para solucionar este problema, Costa e Bianchi (2000) estenderam a arqui-

tetura ViBRA utilizando aprendizado por reforço para aprender a coordenar as

aç˜oes dos diversos agentes, com o objetivo de minimizar o tempo de execuç˜ao

de uma tarefa de montagem. Para tanto, foi introduzido um agente de controle

com capacidades de aprendizado na sociedade de agentes autônomos, permitindo

a substituiç˜ao da estrutura de autoridade fixa por uma dinâmica.

Nesta nova arquitetura, denominada L–ViBRA, o agente de controle utiliza

o algoritmo Q–Learning para, com base em informaç˜oes recebidas pelo sistema

de percepç˜ao, criar um plano de montagem otimizado. O uso do Q–Learning na

arquitetura L–ViBRA resultou em um sistema capaz de criar o plano de monta-

gem otimizado desejado, mas que n˜ao era rápido suficiente na produç˜ao destes

planos.

Para acelerar o aprendizado, o algoritmo de aprendizado utilizado no agen-

te de controle foi substitu´ıdo por uma adaptaç˜ao do algoritmo de Inteligência

de Enxame ( Swarm Intelligence) chamado Ant Colony System (DORIGO; GAM-

BARDELLA, 1997). Esta nova arquitetura, denominada Ant–ViBRA, mostrou-se

1.4 Organizaç˜ao do trabalho

6

eficiente na produç˜ao dos planos de montagem necessários, reduzindo o tempo de

aprendizado (BIANCHI; COSTA, 2002a; BIANCHI; COSTA, 2002b).

Apesar do aprendizado em sistemas multiagentes n˜ao ser o foco principal

deste trabalho, durante estes estudos surgiram as principais quest˜oes que este

trabalho pretende investigar:

Como acelerar o aprendizado por reforço?

Como utilizar as informaç˜oes existentes no próprio processo de aprendizado

para acelerar o aprendizado?

Como utilizar informaç˜oes conhecidas a priori acerca de um problema para

acelerar o aprendizado?

Como reutilizar conhecimentos já aprendidos para acelerar o aprendizado?

Como compartilhar o conhecimento entre diversos agentes para acelerar o

aprendizado?

Como combinar todas estas informaç˜oes com o processo de aprendizado,

sem perder as boas propriedades dos algoritmos de AR?

O restante deste trabalho pretende mostrar que o uso dos algoritmos de

“Aprendizado Acelerado por Heur´ısticas” é uma resposta eficiente e elegante para

estas quest˜oes.

1.4

Organizaç˜

ao do trabalho

Este trabalho está organizado da seguinte maneira: no cap´ıtulo 2 é apresentada

uma vis˜ao geral do aprendizado por reforço, mostrando os modelos utilizados

para formalizar o problema de aprendizado e alguns dos principais algoritmos.

No cap´ıtulo 3 s˜ao resumidas algumas propostas para aumentar o desempe-

nho dos algoritmos de aprendizado por reforço apresentadas nos últimos anos.

No cap´ıtulo 4 é apresentado detalhadamente o “Aprendizado Acelerado por

Heur´ısticas”, os métodos “Heur´ıstica a partir de X” e o algoritmo Heuristically

Accelerated Q–Learning – HAQL, propostos neste trabalho.

1.4 Organizaç˜ao do trabalho

7

No cap´ıtulo 5 s˜ao apresentados alguns dos resultados obtidos para o dom´ınio

dos robôs móveis autônomos utilizando o Heuristically Accelerated Q–Learning.

Por ser um dom´ınio mais difundido, ele foi usado para explorar métodos

“Heur´ıstica a partir de X” que podem ser usados em tempo de execuç˜ao. No

cap´ıtulo 6, s˜ao utilizadas heur´ıstica definidas a priori visando explorar outros algoritmos acelerados por heur´ısticas, atuando em diversos dom´ınios.

Finalmente, no cap´ıtulo 7 é realizada uma discuss˜ao sobre os resultados e

propostas de extens˜oes deste trabalho.

8

2

Aprendizado por Reforço

O objetivo deste cap´ıtulo é apresentar uma vis˜ao geral do Aprendizado por Re-

forço (AR), permitindo a compreens˜ao dos mecanismos básicos utilizados nesta

área de pesquisa.

2.1

O Problema do Aprendizado

O Agente

Para o Aprendizado por Reforço (AR), um agente aprendiz é aquele que, a partir

Aprendiz

da interaç˜ao com o ambiente que o cerca, aprende de maneira autônoma uma

pol´ıtica ótima de atuaç˜ao: aprende ativamente, por experimentaç˜ao direta, sem

ser ensinado por meio de exemplos fornecidos por um supervisor.

Um agente aprendiz interage com o ambiente em intervalos de tempos dis-

cretos em um ciclo de percepç˜ao-aç˜ao (figura 2.1): o agente aprendiz observa,

a cada passo de iteraç˜ao, o estado corrente st do ambiente e escolhe a aç˜ao at

para realizar. Ao executar esta aç˜ao at – que altera o estado do ambiente – o

agente recebe um sinal escalar de reforço rs,a (penalizaç˜ao ou recompensa), que

indica qu˜ao desejável é o estado resultante st+1. O AR permite que o agente

possa determinar, após várias iteraç˜oes, qual a melhor aç˜ao a ser executada em

cada estado, isto é, a melhor pol´ıtica de atuaç˜ao.

Assim, o objetivo do agente aprendiz é aprender uma pol´ıtica ótima de

atuaç˜ao que maximize a quantidade de recompensa recebida ao longo de sua

execuç˜ao, independentemente do estado inicial. Esse problema pode ser modela-

do como um Processo Markoviano de Decis˜ao, descrito a seguir.

2.2 Processos Markovianos de Decis˜ao

9

Ação a t

Agente Aprendiz

Ambiente

Estado s t+1

Reforço r s,a

Figura 2.1: Ciclo Percepç˜ao-Aç˜ao.

2.2

Processos Markovianos de Decis˜

ao

A maneira mais tradicional para formalizar o Aprendizado por Reforço é utili-

zando o conceito de Processo Markoviano de Decis˜ao ( Markov Decision Process

– MDP).

Por ser matematicamente bem estabelecido e fundamentado, este formalismo

facilita o estudo do AR. Por outro lado, assume uma condiç˜ao simplificadora –

conhecida como Condiç˜ao de Markov – que reduz a abrangência das soluç˜oes, mas

que é compensada em grande parte pela facilidade de análise (RIBEIRO, 2002).

A Condiç˜ao de Markov especifica que o estado de um sistema no próximo

instante ( t + 1) é uma funç˜ao que depende somente do que se pode observar

acerca do estado atual e da aç˜ao tomada pelo agente neste estado (descontando

alguma perturbaç˜ao aleatória), isto é, o estado de um sistema independe da sua

história. Pode-se ver que muitos dom´ınios obedecem esta condiç˜ao: problemas de

roteamento, controle de inventário, escalonamento, robótica móvel e problemas

de controle discreto em geral.

Markov

Um Processo Markoviano de Decis˜ao é aquele que obedece à Condiç˜ao de

Decision

Markov e pode ser descrito como um processo estocástico no qual a distribuiç˜ao

Process

futura de uma variável depende somente do seu estado atual. Um MDP é de-

finido formalmente (LITTMAN, 1994; KAELBLING; LITTMAN; MOORE, 1996;

MITCHELL, 1997) pela quádrupla S, A, T , R , onde:

• S: é um conjunto finito de estados do ambiente.

• A: é um conjunto finito de aç˜oes que o agente pode realizar.

2.2 Processos Markovianos de Decis˜ao

10

• T : S × A → Π( S): é a funç˜ao de transiç˜ao de estado, onde Π( S) é uma

distribuiç˜ao de probabilidades sobre o conjunto de estados S. T ( st, at, st+1)

define a probabilidade de realizar a transiç˜ao do estado st para o estado

st+1 quando se executa a aç˜ao at.

• R : S × A →

: é a funç˜ao de recompensa, que especifica a tarefa do