UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE CENTRO DE TECNOLOGIA – CT CENTRO DE CIÊNCIAS EXATAS E DA TERRA – CCET PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA E ENGENHARIA DE PETRÓLEO - PPGCEP TESE DE DOUTORADO Uma Abordagem Utilizando Aprendizagem por Reforço Hierárquica e Computação Paralela para o Problema dos K-Servos. Mademerson Leandro da Costa Orientador: Prof. Dr. Adrião Duarte Dória Neto Natal/RN, Junho de 2017 Universidade Federal do Rio Grande do Norte - UFRN Sistema de Bibliotecas - SISBI Catalogação de Publicação na Fonte. UFRN - Biblioteca Central Zila Mamede Costa, Mademerson Leandro da. Uma abordagem utilizando aprendizagem por reforço hierárquica e computação paralela para o problema dos K-Servos / Mademerson Leandro da Costa. - 2017. 79 f.: il. Tese (doutorado) - Universidade Federal do Rio Grande do Norte, Centro de Ciências Exatas e da Terra, Programa de Pós- graduação em Ciência e Engenharia de Petróleo. Natal, RN, 2017. Orientador: Prof. Dr. Adrião Duarte Dória Neto. Coorientador: Prof. Dr. Jorge Dantas de Melo. 1. Computação paralela - Tese. 2. Aprendizagem por Reforço Hierárquica - Tese. 3. Problemas de Otimização em Espaços Métricos - Tese. I. Dória Neto, Adrião Duarte. II. Melo, Jorge Dantas de. III. Título. RN/UF/BCZM CDU 004.42 Uma Abordagem Utilizando Aprendizagem por Reforço Hierárquica e Computação Paralela para o Problema dos K-Servos. Mademerson Leandro da Costa Natal/RN, Junho de 2017 COSTA, Mademerson Leandro - Uma Abordagem Utilizando Aprendizagem por Reforço Hierárquica e Computação Paralela para o Problema dos K-Servos. Tese de Doutorado, UFRN, Programa de Pós-Graduação em Ciência e Engenharia de Petróleo. Área de Concentração: Pesquisa e Desenvolvimento em Ciência e Engenharia de Petróleo. Linha de Pesquisa: Automação na Indústria de Petróleo e Gás Natural, Natal – RN, Brasil. Orientador: Prof. Dr. Adrião Duarte Dória Neto Co-orientador: Prof. Dr. Jorge Dantas de Melo Resumo Um sistema de tarefas em espaços métricos é um modelo abstrato para uma classe de problemas de otimização online, incluindo o problema de paginação de memória, listas de acesso, problemas na indústria do petróleo como o gerenciamento de sondas de produção terrestre (workover rigs) e de logística na produção de petróleo offshore, o problema dos K- Servos, dentre outros. A utilização da aprendizagem por reforço na solução destes problemas, embora tenha se mostrado eficiente, está restrita a uma classe simples de problemas, devido à maldição da dimensionalidade inerente ao método. Neste trabalho, apresenta-se uma solução que utiliza a aprendizagem por reforço, baseada em técnicas de decomposição hierárquica e computação paralela para solução de problemas de otimização em espaços métricos, com o objetivo de estender a aplicabilidade do método a problemas complexos na indústria petrolífera, contornando a restrição da sua utilização a problemas teóricos de menor porte. A dimensão da estrutura de armazenamento utilizada pela aprendizagem por reforço para se obter a política ótima cresce em função do número de estados e de ações, sendo diretamente proporcional ao número n de nós e k de servos, fazendo com que o crescimento da complexidade do problema se dê de maneira exponencial (𝐶𝑘 𝑛 ≅ 𝑂(𝑛𝑘)). Para contorná-lo, o problema foi modelado com um processo de decisão em múltiplas etapas onde inicialmente utilizamos o algoritmo k-means como método de agrupamento visando decompor o problema em subproblemas de menor dimensão. Em seguida foi aplicado o algoritmo Q-learning nos subgrupos buscando-se atingir a melhor política de deslocamento dos servos. Nesta etapa, foram utilizadas técnicas de computação paralela para que os processos de aprendizado e armazenamento nos subgrupos fossem executados de forma paralela. Desta forma, a dimensão do problema e o tempo total de execução do algoritmo foram reduzidos, viabilizando a aplicação do método proposto às grandes instâncias. A abordagem proposta apresentou melhores resultados quando comparada com a aprendizagem por reforço clássica e o método guloso. Além de ter atingido ganhos de speedup e eficiência na avaliação das métricas de desempenho paralelo. Palavras-chave: Aprendizagem por Reforço Hierárquica, Problemas de Otimização em Espaços Métricos, Computação Paralela. ABSTRACT A metrical task system is an abstract model for a class of online optimization problems, including paging, access lists, industry oil problems such as the management of workover rigs and logistics in the production of offshore oil, the problem of K-Servos, among others. The use of reinforcement learning to solving these problems, although proved to be efective, is restricted to a simple class of problems due to the curse of dimensionality inherent to the method. This work presents a solution that uses reinforcement learning based on hierarchical decomposition techniques and parallel computing to solve optimization problems in metric spaces. The use of these techniques allowed to extend the applicability of the method to more complex problems, bypassing the restriction of its use to smaller problems. As the size of the storage structure used by reinforcement learning to obtain the optimal policy grows as a function of the number of states and actions, which in turn is proportional to the number n of nodes and k of servers, it is noticed that their growth is given exponentially (𝐶𝑘 𝑛 ≅ 𝑂(𝑛𝑘)). To circumvent this, the problem was modeled with a multi-step decision process where we initially used the k-means algorithm as a grouping method to decompose the problem into smaller subproblems. Then, the Q- learning algorithm was applied in the subgroups, aiming at achieving the best server displacement policy. In this step, the learning and storage processes in the subgroups were executed in parallel. In this way, the problem dimension and the total execution time of the algorithm were reduced, making possible the application of the proposed method to the large instances. The proposed approach presented better results when compared to the classical reinforcement learning and the greedy method. In addition to achieving speedup and efficiency gains in the evaluation of parallel performance metrics. Keywords— Metrical Task Systems, The K-Server Problem, Curse of Dimensionality, Hierarchical Reinforcement Learning, Q-Learning Algorithm, Parallel Computing. "Que a tua sabedoria não seja humilhação para o teu próximo." (Omar Khayyám), "Pois o Senhor é quem dá sabedoria; de sua boca procedem o conhecimento e o discernimento." (Provérbios 2:6) Dedico esse trabalho aos meus filhos Anna Beatriz e Pedro, meu melhor legado para este mundo. Agradecimentos Agradecer é manifestar gratidão a quem esteve ao nosso lado em momentos difíceis. É recompensar através de gestos ou palavras a todos que nos levantaram em nossos tropeços. É reconhecer que qualquer jornada será mais amena com alguém nos apoiando. Aqui gostaria de agradecer a todos que de maneira direta, ou indireta, contribuíram na execução deste trabalho: À Deus por me conceder a força necessária para me reerguer nos inúmeros momentos difíceis e permitir concluir esse trabalho. Aos meus pais Manoel Leandro de Lima (in memoriam) e Maria da Penha Leandro da Costa, por transmitirem os melhores ensinamentos que eu poderia receber. À Simone Almeida Gavilan, por ser a primeira a acreditar na realização deste trabalho e por todo apoio dedicado durante esta jornada. Aos meus orientadores, Adrião Duarte Dória Neto e Jorge Dantas de Melo, pela confiança em mim depositada, pelas orientações e por todos os ensinamentos transmitidos ao longo desse período. Ao meu irmão Manoel Leandro de Lima Júnior, pelas contribuições e por todo apoio transmitido. À Universidade do Estado do Rio Grande do Norte pelo investimento na minha capacitação docente. Ao meu chefe imediato professor Ênio Virgílio de Oliveira Matias pela presteza e compreensão dedicados. Aos colegas do Departamento de Matemática e Estatística, DME-FANAT/UERN, por todo apoio durante minha liberação das atividades acadêmicas. A todos os colegas do Laboratório de Sistemas Inteligentes, pelas inúmeras contribuições e sugestões que certamente foram imprescindíveis ao sucesso deste trabalho. A todos os meus familiares que torceram e oraram para a conclusão com êxito desse trabalho. Sumário Lista de Figuras ii Lista de Algoritmos iii Lista de Tabelas iv Lista de Símbolos e Abreviaturas v Sumário Introdução ............................................................................................................................................... 1 1.1 Motivação ...................................................................................................................................... 3 1.2 Objetivos ................................................................................................................................. 3 1.3 Estado da arte ............................................................................................................................... 4 1.4 Organização do trabalho ............................................................................................................... 8 Sistemas de tarefas em espaços métricos - MTS .................................................................................... 9 2.1 Computação online e análise competitiva .................................................................................... 9 2.2 Sistemas de tarefas em espaços métricos .................................................................................. 10 2.3 O Problema dos K-Servos ............................................................................................................ 12 2.4 Modelagem do PKS ao Roteamento de Sondas de Produção Terrestre ..................................... 12 2.5 Considerações ............................................................................................................................. 13 Aprendizagem por reforço – Q-learning ............................................................................................... 14 3.1 Aprendizagem por reforço (AR) .................................................................................................. 14 3.2 Q-learning .................................................................................................................................... 17 3.3 Maldição do dimensionamento .................................................................................................. 18 3.4 Considerações ............................................................................................................................. 19 Aprendizagem por reforço hierárquica ................................................................................................. 20 4.1 Aspectos teóricos da aprendizagem por reforço hierárquica ..................................................... 20 4.2 Processos de Decisão Semi-Markovianos (PDSM) ...................................................................... 22 4.3 Algoritmos de aprendizagem por reforço hierárquica ................................................................ 23 4.3.1 Q-Learning Semi-Markoviano .............................................................................................. 23 4.3.2 Q-Learning Semi-Markoviano Hierárquico ........................................................................... 25 4.3.3 MAXQ-Q ............................................................................................................................... 26 4.3.4 Q-Learning com Hierarquia de Máquinas Abstratas ............................................................ 28 4.4 Outras técnicas para aceleração do aprendizado ....................................................................... 29 4.5 Considerações ............................................................................................................................. 30 Computação Paralela ............................................................................................................................ 31 5.1 Fundamentos sobre Processamento Paralelo............................................................................. 31 5.2 Arquiteturas de computador ...................................................................................................... 36 5.2.1 Arquitetura von Neumann ................................................................................................... 36 5.2.2 Arquitetura SIMD ................................................................................................................. 37 5.2.3 Arquitetura MIMD ................................................................................................................ 39 5.2.4 Organização da Memória Compartilhada (Shared Memory) ............................................... 40 5.2.5 Organização da Passagem de Mensagem (Message Passing) .............................................. 42 5.3 Paralelismo versus Desempenho ................................................................................................ 43 5.3.1 Origens da perda de desempenho ....................................................................................... 43 5.4 Dependência ............................................................................................................................... 45 5.5 Granularidade.............................................................................................................................. 46 5.6 Speedup ....................................................................................................................................... 46 5.7 Eficiência ..................................................................................................................................... 46 5.8 Dimensionando o tamanho do problema ................................................................................... 47 5.9 Considerações ............................................................................................................................. 47 Aplicação da aprendizagem por reforço ao PKS ................................................................................... 48 6.1 Considerações iniciais ................................................................................................................. 48 6.2 Modelagem para problemas de menor porte............................................................................. 49 6.3 Modelagem para problemas de maior porte .............................................................................. 51 6.4 Considerações ............................................................................................................................. 57 Análise da solução proposta ................................................................................................................. 58 7.1 Análise de desempenho dos algoritmos propostos .................................................................... 59 7.2 Complexidade da solução ........................................................................................................... 60 7.3 Análise comparativa – Q-Learning, Hierárquico paralelizado e Guloso. ..................................... 60 7.4 Aplicação do Método Hierárquico Paralelizado ao Problema de Sondas de Produção Terrestre. ........................................................................................................................................................... 69 7.4 Considerações ............................................................................................................................. 72 Considerações finais .............................................................................................................................. 73 8.1 Conclusão .................................................................................................................................... 73 8.2 Perspectivas de trabalhos futuros ............................................................................................... 74 8.3 Trabalhos publicados .................................................................................................................. 74 Referências Bibliográficas ..................................................................................................................... 75 Lista de Figuras Figura 3.1: Sistema de aprendizagem por reforço......................................................................14 Figura 5.1: Representação de um algoritmo para o cálculo de uma soma em sequência...................................................................................................................................34 Figura 5.2: Representação de um algoritmo para o cálculo de uma soma em paralelo...............35 Figura 5.3: Dois esquemas de SIMD.........................................................................................38 Figura 5.4: Arquitetura memória compartilhada versus message passing.................................39 Figura 6.1: Diagrama de backup do algoritmo Q-Learning.......................................................50 Figura 6.3: Problema com 10 nós e 2 servos..............................................................................54 Figura 6.4: Problema após a divisão em grupos e seleção dos nós-centro..................................54 Figura 6.5: Exemplo com os 2 servos localizados em nós-centro distintos e uma demanda em um outro nó-centro....................................................................................................................56 Figura 6.6: Exemplo com os 2 servos localizados em nós-centro distintos e com a demanda em um nó, que não é nó-centro, num grupo distinto ao dos servos...................................................56 Figura 6.7: Exemplo com os 2 servos localizados em grupos distintos e uma demanda num nó que pertence ao grupo de um deles.............................................................................................56 Figura 6.8: Exemplo com os 2 servos e a demanda localizados em um mesmo grupo................57 Figura 6.9: Exemplo com 2 servos localizados em grupos distintos, um deles está num nó-centro e o outro não, e surge uma demanda em um nó que não é centro e que pertence a um grupo que é distinto ao dos 2 servos............................................................................................................57 Figura 7.1: Tempo Total de execução do algoritmo sequencial versus paralelo com seis core............................................................................................................................................65 Figura 7.2: Tempo Total de execução do algoritmo Q-learning sequencial versus paralelo com seis core.....................................................................................................................................66 Figura 7.3: Speedup do algoritmo proposto com o número de agrupamentos variando de um a seis.............................................................................................................................................67 Figura 7.4: Eficiência do algoritmo proposto com o número de agrupamentos variando de um a seis..........................................................................................................................................68 Figura 7.4.1: Tempo total de execução, em segundos, para os métodos Q-Learning, Hierárquico paralelizado e o guloso para as várias instâncias de poços........................................................70 Lista de Algoritmos Algoritmo 3.1 Descrição do algoritmo Q-Learning..................................................................18 Algoritmo 4.1 SMDP Q-learning..............................................................................................24 Algoritmo 4.2 HSMQ-learning.................................................................................................25 Algoritmo 4.3 MAXQ-Q learning.............................................................................................27 Algoritmo 4.3 HAMQ-learning................................................................................................28 Algoritmo 6.1: Método Hierárquico Paralelo............................................................................53 Lista de Tabelas Tabela 7.1: Resultados experimentais da comparação entre o algoritmo Q-learning, aprendizagem por reforço hierárquica paralelizada e guloso (60 nós, 2 servos e 6 grupamentos).............................................................................................................................62 Tabela 7.2: Resultados experimentais da comparação entre o algoritmo Q-learning, aprendizagem por reforço hierárquica paralelizada e guloso (90 nós, 2 servos e 6 grupamentos).............................................................................................................................63 Tabela 7.3: Resultados experimentais da comparação entre o algoritmo Q-learning, aprendizagem por reforço hierárquica paralelizada e guloso (120 nós, 2 servos e 6 grupamentos).............................................................................................................................63 Tabela 7.4: Resultados experimentais da comparação entre o algoritmo Q-learning, aprendizagem por reforço hierárquica paralelizada e guloso (150 nós, 2 servos e 6 grupamentos).............................................................................................................................64 Tabela 7.5: Comparativo entre o tempo total de execução sequencial e paralelo......................................................................................................................................64 Tabela 7.6: Comparativo entre o tempo total de execução do Q-learning sequencial e paralelo com seis agrupamentos.............................................................................................................65 Tabela 7.7: Tempo de execução, em segundos, do algoritmo proposto com o número de agrupamentos variando de um a seis..........................................................................................66 Tabela 7.8: Speedup do algoritmo proposto com o número de agrupamentos variando de um a seis.............................................................................................................................................67 Tabela 7.9: Eficiência do algoritmo proposto com o número de agrupamentos variando de um a seis..........................................................................................................................................68 Tabela 7.10 Resumo do comparativo entre o Q-Learning, Hierárquico paralelizado e o guloso para as várias instâncias de poços..............................................................................................69 Tabela 7.11: Tempo total de execução, em segundos, para os métodos Q-Learning, Hierárquico paralelizado e o guloso para as várias instâncias de poços.........................................................70 Tabela 7.12: Comparativo entre os métodos Q-Learning, Hierárquico paralelizado e o guloso para a instância de 100 poços.....................................................................................................71 Tabela 7.13: Comparativo entre os métodos Q-Learning, Hierárquico paralelizado e o guloso para a instância de 125 poços.....................................................................................................71 Tabela 7.14: Comparativo entre os métodos Q-Learning, Hierárquico paralelizado e o guloso para a instância de 150 poços....................................................................................................71 Tabela 7.15: Comparativo entre os métodos Q-Learning, Hierárquico paralelizado e o guloso para a instância de 175 poços.....................................................................................................72 Tabela 7.16: Comparativo entre os métodos Q-Learning, Hierárquico paralelizado e o guloso para a instância de 200 poços.....................................................................................................72 Lista de Símbolos e Abreviaturas MTS – Metrical Task Systems AR – Aprendizagem por Reforço PKS – Problema dos K-Servos GPU – Graphic Processing Units CUDA – Compute Unified Device Architecture PSO – Particle Swarm Optimization GA – Genetic Algorithm HRL – Hierarchical Reinforcement Learning CBRMs – Conditional Restricted Boltzmann Machines MDP – Markov Decision Process CAC – Call Admission Control VNS – Variable Neighborhood Search PCVS – Problema do Caixeiro Viajante Simétrico SPT – Sondas de Produção Terrestre PDM – Processo de Decisão Markoviano PDSM – Processo de Decisão Semi-Markovianos SMDP Q-Learning - Q-Learning Semi-Markoviano HSMQ-Learning – Q-Learning Semi-Markoviano Hierárquico HAMQ – Q-Learning com Hierarquia de Máquinas Abstratas RNA – Redes Neurais Artificiais CPU – Unidade Central de Processamento ALU – Unidade Lógica e Aritmética SISD – single-instruction single-data streams SIMD – single-instruction multiple-data streams MISD – multiple-instruction single-data streams MIMD – multiple-instruction multiple-data streams SMP – Symmetric multiprocessing UMA – Uniform Memory Access NUMA – Nonuniform Memory Access COMA – Cache-Only Memory Architecture 1 1 Capítulo 1 Introdução Um Sistema de Tarefas em Espaços Métricos (MTS – Metrical Task Systems)1 é um modelo abstrato para problemas de computação online (Borodin; El-Yaniv, 1998). Foi formulado por Borodin, Linial e Saks (Borodin et al., 1992), e serve como abstração para uma série de problemas, incluindo o problema de paginação de memória (Albers, 1996), listas de acesso (Borodin; El-Yaniv, 1998) e o problema dos K-Servos (Manasse et al., 1988), dentre outros. De maneira informal, o MTS modela problemas onde uma sequência de tarefas necessita ser realizada, existindo mais de uma maneira de executar cada tarefa. A decisão de realizar uma tarefa em particular tem impacto na eficiência tanto no que se refere ao modo como a mesma é realizada quanto no estado do sistema após o seu término, o qual pode afetar o custo das tarefas subsequentes. Normalmente, as decisões de como realizar uma tarefa são tomadas sem qualquer conhecimento acerca de quais serão as tarefas apresentadas ao sistema. Assim, o MTS é comumente considerado como um problema de computação online (Borodin; El-Yaniv, 1998). Esses problemas podem ser caracterizados como segue: dada uma sequência de solicitações σ = {σ1, σ2, . . . , σm}, um algoritmo A deve atender cada uma dessas solicitações de maneira online, ou seja, sem o conhecimento prévio das solicitações subsequentes. Desde que o atendimento das solicitações implica em custos, o objetivo a ser alcançado, geralmente, é a minimização desses custos. Tal problema pode ser visto como um processo de decisão em múltiplas etapas, onde a cada instante ti (i = 1,2, . . . , m) considerado, uma decisão deve ser tomada sobre como atender à solicitação σi. Esse processo é também markoviano, uma vez que a decisão a ser tomada no instante ti depende apenas das informações disponíveis nesse instante. De maneira geral, a solução de problemas de decisão markovianos pode ser obtida de maneira eficiente a partir da utilização da Aprendizagem por Reforço (AR) (Sutton; Barto, 1998), desde que satisfeitas as hipóteses de aplicabilidade do método. A aprendizagem por reforço tem analogia com modelos inspirados na observação de fenômenos do comportamento animal, especificamente aqueles ligados à aprendizagem baseada em recompensas e punições. Consiste num tema multidisciplinar, envolvendo 1 Os termos sistema de tarefas em espaços métricos e problemas de otimização em espaços métricos são utilizados como sinônimos neste trabalho, sendo utilizado para ambos, indistintamente, a abreviatura MTS. 2 disciplinas como biologia, ciências da computação, ciências cognitivas, engenharia, filosofia, física, matemática, psicologia e sociologia (Sutton; Barto, 1998). O processo de aprendizagem é baseado em iterações entre um agente e o seu ambiente, tentando otimizar a escolha das ações de acordo com algum critério de recompensa. Neste trabalho, considera-se que o ambiente evolui dinamicamente em tempo discreto, de acordo com a equação: 𝑠𝑡+1 = 𝑓(𝑠𝑡, 𝑎𝑡, 𝜔𝑡) (1.1) onde 𝑠𝑡 ∈ 𝑆 é o conjunto finito de estados, 𝑎𝑡 ∈ 𝐴(𝑠𝑡) é o conjunto finito de ações associadas a cada estado e 𝜔𝑡 ∈ Ω é o conjunto finito de perturbações, amostrados de forma independente a partir de uma dada distribuição. A cada passo de tempo, o agente observa o estado st do ambiente e seleciona uma ação at apropriada. A execução de uma ação produz uma mudança no estado do ambiente para um novo estado st+1, e uma avaliação desta ação, na forma de punição ou recompensa, denotada por rt+1(st, at), é apresentada ao agente pelo ambiente. O processo de aprendizagem tem por finalidade orientar o agente a tomar as ações que venham a maximizar ou minimizar as recompensas ou punições recebidas. Deve-se levar em conta que uma ação tomada em um dado instante t tem influência não apenas sobre a avaliação imediata, mas também sobre todas as outras ações (avaliações) que serão efetuadas a partir de então. O problema a ser resolvido pode ser estabelecido da seguinte forma: dado um estado inicial s = s0, qual deve ser a política π(st) empregada na escolha das ações at (t = 0, 1, . . .), tal que o retorno obtido 𝑅(𝑠, 𝜋) = ∑ 𝛾𝑡𝑟(𝑠𝑡, 𝜋(𝑠𝑡)) ∞ 𝑡=0 seja ótimo em determinado sentido, dado que γ é um fator de desconto (0 ≤ γ ≤ 1) utilizado para garantir que R(s, π) seja finito. Na solução deste problema, associa-se uma função de valor V(s) a cada estado (ou Q(s,a) par estado-ação), que fornece uma estimativa de 𝑅(𝑠, 𝜋), permitindo assim avaliar a política baseado em resultados da programação dinâmica (Bellman, 1957), pode-se desenvolver algoritmos para a estimação da função de valor ótima e, consequentemente, da política ótima a ser empregada. 3 1.1 Motivação A utilização da aprendizagem por reforço na solução de problemas de pequena dimensão tem aberto boas perspectivas de aplicabilidade do método. Entretanto, como todos os métodos inspirados na teoria da programação dinâmica desenvolvida nos anos 50 por Richard Bellman (Bellman, 1957), ela sofre do problema do maldição da dimensionalidade (do inglês, curse of dimensionality), o que impede uma aplicação efetiva a problemas mais realistas, uma vez que torna-se necessário armazenar os valores de V(s) para cada estado 𝑠 ∈ 𝑆, o que é impossível se o número de estados é elevado. Nos últimos anos, vários artigos foram publicados abordando métodos que buscam soluções para contornar essa dificuldade, onde destacam-se os trabalhos sobre programação dinâmica aproximada ((Liang; Li; Wei, 2014), (Li; Jayaweera, 2014), (Střelec; Berka, 2013), (Kariotoglou et al., 2013) e (Huang; Ma, 2011)), programação dinâmica em tempo real (Rocha Vianna; Sanner; Nunes de Barros, 2014) e métodos hierárquicos ((Djurdjevic; Huber, 2013), (Yu et al., 2011) e (Yan; Liu; Hu, 2010)). Estes métodos visam melhorar a eficiência dos algoritmos de aprendizagem por reforço e possibilitar a sua aplicação a uma ampla gama de problemas reais. Estas técnicas embora tenham obtidos resultados satisfatórios para algumas aplicações, falham categoricamente em outras, não sendo eficientes para todos os casos. O fato de ainda não ter sido encontrada uma solução de âmbito global tem ocasionado a busca por novas alternativas. A aplicação efetiva do algoritmo Q-Learning associado às técnicas de decomposição hierárquica e computação paralela visam cobrir uma lacuna deixado por outros algoritmos. Por permitirem a modelagem de inúmeros problemas uma solução aplicável às grandes instâncias de MTS constitui objeto de interesse para vários segmentos, entre eles problemas na indústria petrolífera cujas reduções nos custos operacionais representam objeto de grande interesse comercial. Sendo estes portanto, fatores de motivação para execução deste trabalho. 1.2 Objetivos Neste trabalho propomos uma solução alternativa para problemas de MTS utilizando a aprendizagem por reforço baseada em técnicas de decomposição hierárquica processada de forma paralela. O objetivo é estender a aplicabilidade do método a problemas de grande dimensão, contornando a restrição de seu uso em problemas de menor porte. Para verificar o desempenho da solução proposta, será feita uma análise comparativa entre os desempenhos das 4 abordagens clássica (baseada no algoritmo Q-Learning), do método de aprendizagem por reforço hierárquica paralelizada e do algoritmo guloso em um problema específico de MTS, a saber, o problema dos K-Servos – PKS (Manasse et al. 1988). Serão analisados aspectos ligados à qualidade da solução hierárquica paralelizada obtida quando comparada com a aprendizagem por reforço clássica, e suas possíveis limitações, além da associação entre a teoria sobre aprendizagem por reforço hierárquica encontrada na literatura e a solução proposta neste trabalho, correlacionando as técnicas formais que garantem a convergência para o ótimo com as que estão sendo propostas neste texto. A partir do cálculo das principais métricas de desempenho paralelo, speedup e eficiência, desejamos avaliar a escalabilidade do método proposto em aplicações de maior complexidade. A adequabilidade do método a ser apresentado em uma aplicação de MTS específica vislumbraria a aprendizagem por reforço como um método eficaz de solução para qualquer problema de otimização em espaços métricos, já que a mesma pode ser facilmente estendida para outras aplicações de MTS. Especificamente, aos problemas de gerenciamento de sondas de produção terrestre (workover rigs) e de logística na produção de petróleo offshore. 1.3 Estado da arte Embora os métodos baseados no princípio da programação dinâmica sejam eficientes para controle de políticas ótimas em processos de decisão em múltiplas etapas, seu uso não pode ser estendido a problemas mais complexos devido à maldição da dimensionalidade. A maldição da dimensionalidade é um termo cunhado por Bellman (1961) para se referir ao aumento exponencial no espaço de estados com o incremento de cada dimensão ou variável que descreve o problema. Muitos problemas podem ser estruturados de forma hierárquica, o que lhes permite ser dividido em sub-problemas. Os sub-problemas, sendo menores, muitas vezes são resolvidos mais facilmente. As soluções para os sub-problemas são combinados para fornecer a solução para o problema maior original. Neste trabalho associa-se ao método de aprendizagem por reforço hierárquica técnicas de computação paralela. Diante do esforço computacional necessário ao treinamento destes algoritmos a computação paralela apresenta-se como uma proposta interesante na busca de soluções para problemas de alta complexidade. Desta forma, determinados trabalhos vêm sendo desenvolvidos com o intuito de contornar esse problema. Xie et al. (2016) apresenta um algoritmo hierarquico para maximizar a vida útil de baterias em determinadas condições de utilização. O algoritmo baseia-se em uma combinação de técnicas de programação dinâmica e apredizagem por reforço. Foi aplicado o algoritmo Q-learning para 5 obter as curvas de investimento em energia de arrefecimento e degradação da capacidade de geração de energia pela bateria. Os resultados obtidos mostraram que o algoritmo proposto atingiu uma melhoria na vida útil da bateria em até duas vezes, resultando numa carga de trabalho adicional de 80% antes da bateria descarregar. Yu et al. (2016) apresenta um trabalho de controle de múltiplos peixes robóticos biométricos em um ambiente aquático amplamente dinâmico através de um sistema híbrido centralizado. Para isso foi proposta uma arquitetura baseada em comportamento hierarquico conjuntamente com aprendizagem por reforço fuzzy para realizar a coordenação do nado dos múltiplos robôs. O método foi testado num jogo de polo aquático entre duas equipes com dois robôs cada. O planejamento dos movimentos e controle do rastreamento de trajetórias são dois problemas fundamentais para manobrar robôs com rodas de forma autônoma num ambiente desordenado. Para resolver esse problema Feng et al. (2015) utiliza duas abordagens inteligentes integradas. Inicialmente, uma aboradagem baseada em aprendizagem por reforço hierarquica integrada com transferência de conhecimento é proposta para planejar as tarefas de movimentos no referido ambiente, a transferência de conhecimento é empregada para acelerar o processo de aprendizagem. Então, a trajetória gerada é monitorada por um controlador, os parâmetros de inferência dos sistema são atualizados de forma online pelo algoritmo de aprendizagem do gradiente descendente. O desempenho do uso da abordagem inteligente proposta para controlar o robô no referido ambiente foi validada através de simulação. Uma implementação realizada a partir da análise e aplicação adequada das principais práticas de otimização de desempenho em plataformas GPU (Graphic Processing Units) CUDA (Compute Unified Device Architecture) foi aplicada por (Silva; Bastos Filho, 2015) para o algortimo Otimização por Enxames de Partículas (Particle Swarm Optimization, PSO). Várias confirgurações paralelas foram testadas e os experimentos mostraram um desempenho muito superior da configuração paralela quando comparada com a serial. A detecção de defeitos periódicos durante a produção de materiais web é uma tarefa de grande importância. Com o objetivo de reduzi-los e manter a qualidade do produto um sistema para detecção de falhas busca ser otimizado. Isto é realizado pela procura dos valores ótimos para cada uma de seus parâmetros de configuração. Uma vez que o espaço de busca formado por estes parâmetros é muito grande, ele pode não ser explorado exaustivamente. Para contornar esse problema Bulnes et al (2015) utiliza o algoritmo genético (Genetic Algorithm, GA) paralelo. Conseguindo com isso reduzir consideravelmente o tempo para se encontrar uma solução aceitável. Em (Liang; Li; Wei, 2014) a programação dinâmica aproximada foi aplicada na modelagem em multiestágios de um processo de otimização de uma operação a longo prazo numa estação de armazenamento de energia por bombeamento hidráulico. Sendo para isso 6 utilizado o método de aproximação da função valor que mostrou ser adequado ao problema e com características de otimização estáveis. A abordagem em múltiplos estágios permitiu reduzir a escala do problema e melhorar a velocidade da solução, mostrando que o método proposto é adequado para solução de problemas de decisão otimizados em grande escala. No trabalho de (Li; Jayaweera, 2014) o conceito de casa inteligente com capacidade de tomar decisões de forma instantânea e distribuída foi expandido às unidades consumidoras em geral, sendo utilizada a programação dinâmica aproximada baseada no Q-learning que apresentou muito mais flexibilidade e adaptabilidade quando comparado com outros métodos, como o guloso ou a estratégia de decisão randômica. O gerenciamento de micro redes de energia representam um problema de otimização na qual tarefas discretas e contínuas devem ser resolvidas. Um algoritmo baseado na técnica de programação dinâmica aproximada e várias arquiteturas alternativas de aproximação foram apresentadas por Střelec e Berka (2013). Kariotoglou et al. (2013) descreve um método que aplica a programação dinâmica aproximada ao problema da acessibilidade estocástica em estados infinitos e controle de espaços. Os autores abordam o problema de atingir-evitar (reach-avoid problem) e a aproximação da função valor em uma combinação linear de funções de base radial, conseguido avanços computacionais em sua solução que não podem ser resolvidos por métodos genéricos devido a maldição da dimensionalidade. Simulações numéricas do problema indicam que os controles de políticas vêm como resultado da aproximação da função valor atingindo desempenho próximo do ótimo. Djurdjevic e Huber (2013) apresentam uma abordagem de aprendizagem inovadora para a Aprendizagem por Reforço Hierárquica (Hierarchical Reinforcement Learning - HRL) baseada nas Máquinas de Boltzmann Restritamente Condicionais (Conditional Restricted Boltzmann Machines - CRBMs). O modelo proposto fornece meios uniformes para aprender simultaneamente políticas e características associadas a estados abstratos, permitindo aprender e executar habilidades hierárquicas dentro de uma estrutura de rede consistente e uniforme. Neste modelo, a aprendizagem é executada incrementalmente a partir de características fundamentais básicas para políticas abstratas complexas baseadas em estados latentes e retornos extraídos automaticamente. A modelagem do mundo e do agente dinâmico através de uma hierarquia incremental com mais estados abstratos e políticas, permitiu a aceleração da aprendizagem de vários modos. (Yan; Liu; Hu, 2010) propõem um algoritmo que utiliza a HRL baseada numa função de retorno heurística, aplicando-a a plataforma experimental de Tetris2. Os resultados experimentais mostram que este método pôde superar o enorme espaço de estados 2 O jogo de Tetris foi desenvolvido por Alexey Pathitov em 1985. Como o jogo exige uma enorme estrutura de estados-espaços, ele pode ser usado como uma plataforma típica de aprendizagem por reforço para resolver problemas de grande escala em espaços discretos. 7 do ambiente, isto é, o problema da "maldição da dimensionalidade". Ao adicionar o retorno heurístico a convergência lenta do problema foi melhorada, influenciando no resultado geral do experimento. Em seu estudo, Yu et al. (2013) apresentam uma abordagem melhorada HRL para tratar da maldição da dimensionalidade na otimização dinâmica de um sistema interconectado de energia. O problema foi modelado como um processo de decisão de Markov. A aplicação do algoritmo Q-learning hierárquico em um modelo de rede de energia no sudeste da China mostra que o método proposto pode reduzir o tempo de convergência no processo de pré- aprendizagem, diminuir o custo de regulagem e melhorar o desempenho do sistema quando comparado com a HRL convencional, GA e métodos de engenharia. Outros métodos que buscam contornar a maldição da dimensionalidade podem ser encontrados em Yu et al. (Yu et al., 2012) que propôs um método de determinação de uma nova rota dinâmica, em que o valor da função Q da programação dinâmica e o algoritmo SARSA são combinadas para calcular o tempo ótimo aproximado de cada seção para os destinos nas redes rodoviárias. Os resultados da simulação mostraram que o método proposto pode reduzir o congestionamento do tráfego e melhorar a eficiência do sistema de tráfego efetivamente comparado com o método convencional na rede de estradas do mundo real. Chen et al. (Chen et al., 2012) propõem um processo de decisão Markoviano (Markov Decision Process - MDP) sub-ótimo baseado em um esquema CAC (Call Admission Control) para um sistema de telecomunicações heterogêneos com múltiplas classes de prioridade por serviços, concebido com base em uma redução da dimensão da estrutura em duas fases para diminuir substancialmente a complexidade computacional total da ordem de O(C12) para a ordem de O(C4), onde C denota a capacidade do sistema. A proposta de um esquema MDP baseado em CAC é avaliada por meio de um simulador de eventos, e os resultados são comparados entre dois sistemas diferentes sob diferentes níveis de tráfego. Inserida no contexto de metaheurística a busca reativa surgiu de modo a integrar o aprendizado de máquina dentro das buscas heurísticas para resolver problemas de otimização complexos (Santos et al., 2014). Esses problemas surgem principalmente da modelagem de situações do mundo real nas quais a construção detalhada de um modelo torna-se impossível devido a sua alta complexidade e, por outro lado, sua simplificação pode causar a perda de informações relevantes que poderiam comprometer a qualidade do problema. Santos et al. (2014) utilizam uma abordagem baseada na integração que a busca reativa propõe entre o aprendizado de máquina e metaheurísticas, sendo inserida a AR, mais especificamente o algoritmo Q-learning com um comportamento reativo para selecionar quais busca locais são mais apropriadas em um dado momento da busca, sucedendo outra busca local que não pode 8 melhorar a solução atual na metaheurística VNS (Variable Neighborhood Search). Para sua validação é proposto uma implementação reativa usando a Aprendizagem por Reforço para auto ajustar o algoritmo implementado, aplicado ao Problema do Caixeiro Viajante Simétrico (PCVS). 1.4 Organização do trabalho Este trabalho está organizado da seguinte forma: no Capítulo 2 são apresentados a definição e os principais conceitos de problemas de MTS, contextualizando-o a partir da noção de computação online e análise competitiva. Comenta-se, ainda no Capítulo 2, o problema dos k- servos, o qual será utilizado para verificar o desempenho da solução proposta. No Capítulo 3 são apresentadas noções básicas sobre a aprendizagem por reforço clássica, bem como um de seus métodos de solução mais importantes, a saber, o algoritmo Q-Learning, sendo este o método utilizado neste trabalho. No Capítulo 4 apresenta-se uma visão geral sobre aprendizagem por reforço hierárquica, destacando a estrutura teórica da abordagem, bem como alguns dos principais algoritmos que usam esta técnica. No Capítulo 5 é apresentada uma visão geral sobre computação paralela, conceitos básicos e as principais arquiteturas utilizadas. No capítulo 6 é apresentada a solução proposta para contornar o problema do dimensionamento, baseada em técnicas de aprendizagem por reforço hierárquica e computação paralela, que é aplicada na solução de um MTS específico, a saber, o problema dos k-servos. No Capítulo 7 é apresentada uma análise da solução proposta, situando a mesma dentro da estrutura teórica da aprendizagem por reforço hierárquica apresentada no Capítulo 4, assim como uma comparação entre os desempenhos das soluções baseadas na abordagem hierárquica, no Q-Learning e no método hierárquico paralelizado. As considerações finais encontram-se no Capítulo 8. 9 Capítulo 2 Sistemas de tarefas em espaços métricos - MTS Apresentar-se-á neste capítulo a noção geral de Metrical Task Systems (MTS), contextualizando-o a partir das definições de computação online e análise competitiva. Essa teoria foi extraída principalmente a partir dos estudos de Borodin e El-Yaniv (Borodin; El- Yaniv, 1998). Este modelo foi formulado por Borodin et al. (1992) e serve para modelar problemas como o de paginação de memória (Albers, 1996), listas de acesso (Borodin; El- Yaniv, 1998) e o problema dos k-servos (Manasse et al., 1988), dentre outros. Explora-se ainda o Problema dos K-Servos (PKS), um problema específico dentre os da categoria de MTS, que será utilizado para verificar o desempenho da solução hierárquica paralela proposta neste trabalho. 2.1 Computação online e análise competitiva Em problemas de computação online um algoritmo deve decidir qual ação tomar para uma entrada específica sem o conhecimento das entradas futuras. Por exemplo, como uma chamada telefônica deve ser roteada? Qual página deve ser removida da memória cache quando uma requisição nova chega e todas as páginas da memória cache estão ocupadas? Qual sonda de completação de poços de petróleo deverá ser deslocada de modo que nenhum poço de produção de petróleo fique inoperante e o custo de deslocamento seja o menor possível? A sequência de decisões tomadas pelo algoritmo tem impacto na qualidade total do mesmo. Cada uma destas decisões são tomadas baseadas em eventos passados sem a informação precisa dos eventos futuros. Formalmente, muitos problemas de computação online podem ser descritos como a seguir. Uma sequência de requisições σ = σ(1), σ(2), . . . , σ(m) é apresentada ao algoritmo online A. O algoritmo A deve servir uma sequência de requisições online, isto é, sem o conhecimento prévio das solicitações futuras. Mais precisamente, ao servir a requisição σ(t), 1 ≤ t ≤ m, o algoritmo não tem qualquer conhecimento das requisições σ(t') com t’ > t. Como atender as solicitações implica em custos, o objetivo é atender toda a sequência de requisições de forma que o custo seja o menor possível. Essa configuração também pode ser considerada como um 10 jogo requisição-resposta: um adversário gera pedidos, e um algoritmo online deve servi-los um de cada vez (Albers, 1996). Na análise competitiva, um algoritmo online A é comparado a um algoritmo ótimo offline. Um algoritmo ótimo offline tem conhecimento antecipado da sequência completa de requisições e pode serví-lo a um custo mínimo. Esta metodologia para a análise da tomada de decisão online tornou-se uma abordagem padrão em ciência da computação (Borodin; El-Yaniv, 1998). Dada uma sequência de requisições σ, seja 𝐶𝐴(𝜎) o custo incorrido em A e seja 𝐶𝑂𝑃𝑇(𝜎) o custo pago por um algoritmo ótimo offline OPT. O algoritmo A é dito ser c-competitivo se existe uma constante α de modo que 𝐶𝐴(𝜎) ≤ 𝑐. 𝐶𝑂𝑃𝑇(𝜎) + 𝛼 Para toda a sequência de requisições σ. Aqui nós assumimos que A é um algoritmo determinístico3. O fator c é também chamadado de taxa de competitividade de A. 2.2 Sistemas de tarefas em espaços métricos Aplicações da teoria geral dos MTS para um problema online particular produzem resultados fracos. Entretanto, é natural que um modelo geral abstraia características especiais de configurações particulares que devem ser exploradas de modo a obter melhores resultados. Descreveremos a seguir um modelo abstrato para problemas de computação online, denominado Sistema de Tarefas em Espaços Métricos (Metrical Task Systems – MTS) (Borodin; El-Yaniv, 1998). Formalmente, um espaço métrico M é um par (S, d) onde S é um conjunto de pontos e d : S × S → R+ é uma função de distância métrica que satisfaz: 1. d(i, j) > 0, ∀ i ≠ j, i, j ∈ S; (Positividade) 2. d(i, i) = 0, ∀ 𝑖 ∈ 𝑆; (Reflexividade) 3. d(i, j) + d(j, k) ≥ d(i, k), ∀ 𝑖, j, k ∈ S; (Desigualdade triangular) 4. d(i, j) = d(j, i), ∀ 𝑖, j ∈ 𝑆; (Simetria) Para compreender como um espaço métrico pode ser usado em problemas online abstratos, é só considerar S como sendo um conjunto de todas as possíveis configurações (estados) que podem ser ocupadas por um jogador online4 (Borodin; El-Yaniv, 1998), enquanto d representa 3 Algoritmos Determinísticos: dada uma determinada entrada, o algoritmo apresenta sempre a mesma saída. 4 Um jogador online roda um algoritmo online com entradas fornecidas por um adversário que roda um offline. 11 uma função custo de transição entre pontos de S. Um tarefa r é definida como um vetor de custos, r = {r (1), r (2), . . . , r (N)}, onde para cada i, 𝑟(𝑖) ∈ ℝ+ ∪ {∞} é o custo de processar a tarefa r no estado5 i. Um sistema de tarefas em espaços métricos (MTS) é um par (M, R) onde M é um espaço métrico e R é um conjunto de tarefas disponíveis. Quando não há restrições sobre o conjunto de tarefas disponíveis (ou seja, qualquer vetor de custo é permitido), um sistema de tarefa é simplesmente um espaço métrico. Consideremos um jogador (ou um algoritmo) ao qual é dado um estado inicial s0 e uma sequência finita de tarefas σ = {r1, r2, . . . , rn}, que devem ser processadas sequencialmente, iniciando no estado s0. Se o jogador está no estado corrente s e chega uma tarefa r, ele, primeiramente, muda para um estado q qualquer (ou permanece no mesmo estado), incorrendo num custo de transição d(s, q). Em seguida, o jogador deve processar a tarefa no estado q, incorrendo num custo de processamento r (q). O objetivo de um algoritmo que resolve um MTS é determinar o estado no qual processará cada tarefa, balanceando o custo dos movimentos do jogador, d(s, q), com o custo, r (q), de processar cada tarefa. O algoritmo ALG[i] ∈ S denota o estado no qual a i-ésima tarefa é processada pelo algoritmo ALG, ou seja, ALG[i] é o estado no qual a tarefa r i é processada. Por convenção, ALG[0] = s0. O custo total do algoritmo ALG para uma sequência σ é a soma do custo dos movimentos entre estados com o custo de processamento das tarefas. Matematicamente (Borodin; El-Yaniv, 1998): 𝐴𝐿𝐺(𝜎) = ∑ 𝑑(𝐴𝐿𝐺[𝑖 − 1], 𝐴𝐿𝐺[𝑖]) + ∑ 𝑟𝑖(𝐴𝐿𝐺[𝑖]) 𝑛 𝑖=1 𝑛 𝑖=1 (2.1) Onde n indica o número de tarefas. A primeira parcela do lado direito da igualdade representa o custo total de transições entre estados para servir o conjunto de tarefas σ e a segunda representa o custo total de processamento de σ. Nesta formulação, o jogador pode, em princípio, processar qualquer tarefa de qualquer estado. Em particular, o jogador pode permanecer no mesmo estado para sempre. No entanto, uma vez que cada vetor de tarefas pode incluir componentes com pesos infinitos, um jogador pode ser impedido de atender a uma solicitação em um determinado estado. 5 Um estado representa uma configuração possível de ser ocupada em um espaço métrico M por um jogador online. Em outras palavras, um estado representa um ponto ou um conjunto de pontos ocupados pelo jogador online em um espaço métrico M. 12 2.3 O Problema dos K-Servos O problema dos K-Servos foi proposto por Manasse et al. (1988) servindo como abstração para um grande número de temas. O modelo e a conjectura dos K-Servos têm servido como um catalisador para o desenvolvimento da análise competitiva (Borodin; El-Yaniv, 1998). O problema dos K-Servos pode ser formulado como a seguir. Seja um inteiro k > 1, e seja M = (S, d) um espaço métrico onde S é um conjunto de pontos com | S | > k e d é uma métrica sobre S. Um algoritmo controla k servos móveis, que estão localizados nos pontos de S. Ao algoritmo é apresentado uma sequência σ = r1, r2, . . ., rn de requisições onde uma requisição ri é um ponto do espaço. Nós dizemos que uma requisição r é servida se um dos servos encontra-se em r. O algoritmo deve servir todas as requisições sequencialmente. Para qualquer sequência de requisição σ e qualquer algoritmo para k-servos ALG, ALG(σ) é definida como a soma da distância total (medida pela métrica d) dos movimentos dos servos feitos por ALG para servir σ. 2.4 Modelagem do PKS ao Roteamento de Sondas de Produção Terrestre Um campo petrolífero é uma área composta por um número abundante de poços produtores de petróleo. No entanto, grande parte destes poços não são surgentes, ou seja, não possuem pressão natural suficiente para que os fluidos atinjam a superfície. Diante disto, a elevação do óleo contido nesses poços é feita de maneira artificial através da utilização de equipamentos que atuarão junto destes realizando o bombeamento contínuo dos seus fluídos. A utilização constante destes equipamentos acarreta falhas, fazendo com que intervenções periódicas de manutenção sejam realizadas. Para executar esse serviço utilizam-se as Sondas de Produção Terrestre (SPT), unidades móveis que realizam serviços de intervenção em equipamentos de elevação artificial de óleo. Devido ao alto custo destes equipamentos e das intervenções, as empresas que atuam neste setor possuem uma frota limitada de SPT em relação ao número de equipamentos de bombeamento dos poços. Uma eventual demora em corrigir falhas nos equipamentos de bombeamento decorrentes da limitação no número de sondas pode acarretar redução na produção do óleo, ocasionando perdas substanciais. Assim, encontrar a melhor rota para a frota de sondas de produção terrestre disponíveis de forma a minimizar o tempo de atendimento das solicitações e os custos correspondentes às perdas decorrentes de poços 13 inativos por falta de manutenção, constitui em tarefa primordial para maximizar a produção total da bacia petrolífera. O PKS pode servir de abstração para várias aplicações em logística na indústria do petróleo, sendo que o problema de roteamento de SPT pode ser delineado como o Problema dos K-Servos Homogêneos online (PKS) (Manasse et al., 1988). Este pode ser formalmente modelado da seguinte maneira: Seja k um conjunto de SPT (servos), localizados em n poços necessariamente distintos da bacia produção petrolífera G, e seja {𝜎1, 𝜎2, … , 𝜎𝑚} uma sequência de solicitações que podem surgir em qualquer um dos poços. Para atender a cada uma dessas solicitações 𝜎𝑖 em dado instante 𝑡𝑖 (i = 1, 2, ..., m), uma das SPT deve ser deslocada de sua posição atual para o poço 𝜎𝑖. Associado a esse deslocamento de um nó i para um nó j, existe um custo de atendimento proporcional à distância percorrida d(i, j). O objetivo em questão é atender a toda a sequência de solicitações, minimizando o custo total, ∑ 𝑑(𝑖, 𝑗)𝑚𝑖=1 . Do ponto de vista da Aprendizagem por Reforço, o problema pode ser modelado como segue: o estado do ambiente é representado por uma configuração possível das k SPT, ou seja, por k-túplas do tipo {SPT1, SPT2, ..., SPTk}. As ações correspondem aos deslocamentos permitidos das SPT em um estado válido. Em cada estado, e considerando o surgimento de uma intervenção 𝜎𝑖 em um dos n poços da bacia petrolífera, um das k SPT será deslocada. Deste modo, tem-se que o número de ações permitidas para atender 𝜎𝑖 é k. Será considerado aqui o surgimento de uma intervenção por vez, deixando a análise de múltiplas intervenções para trabalhos futuros. 2.5 Considerações Neste capítulo foram apresentadas noções de computação online e da análise competitiva. Em seguida, descrevemos um modelo abstrato para problemas de computação online o Metrical Task Systems (MTS) e o Problema do K-Servos. Apresentamos ainda uma modelagem do problema de roteamento de sondas de produção terrestre a partir da conjectura do PKS. 14 Capítulo 3 Aprendizagem por reforço – Q-learning Neste capítulo, busca-se passar ao leitor informações básicas acerca da aprendizagem por reforço, suas características, princípios, elementos e métodos, destacando-se, o algoritmo Q- Learning e o problema da maldição da dimensionalidade. 3.1 Aprendizagem por reforço (AR) A aprendizagem por reforço é um método de aprendizado de máquinas não-supervisionado cujo objetivo é a construção de algoritmos que realizam o aprendizado a partir da interação de um agente com um ambiente, e baseia-se nos conceitos matemáticos de programação dinâmica (Bellman, 1957). Sua utilização é recomendada quando não se dispõe de modelos a priori, ou quando não se consegue obter exemplos apropriados das situações as quais o agente aprendiz irá enfrentar (Lima Júnior; 2009). O agente aprende de maneira autônoma uma política ótima de atuação: aprende ativamente, por experimentação direta, sem ser ensinado por meio de exemplos fornecidos por um supervisor. Um esquema de iteração do agente com o ambiente é representado na figura 3.1 abaixo. Figura 3.1: Sistema de aprendizagem por reforço. Política: a política π é responsável por definir qual ação o agente deverá tomar em cada passo de tempo a partir do mapeamento da representação dos estados para as probabilidades de selecionar cada ação possível. O mapeamento dos estados s e ações a é denotado por πt(s, a), onde at = a se st = s. O objetivo do agente é maximizar o montante total de retornos recebidos ao longo do tempo. 15 O objetivo do agente na aprendizagem por reforço é formalizada através de um sinal, chamado retorno, que é passado do ambiente para o agente. O retorno é apenas um número (rt+1) cujo valor varia passo a passo, logo que uma ação a seja executada e ocorra uma transição do estado st para st+1. Informalmente, o objetivo do agente é maximizar o valor total da recompensa que recebe. Isto significa maximizar não só a recompensa imediata, mas a recompensa acumulada a longo prazo. Uma sequência de retornos recebidos após um passo de tempo t é denotado por rt+1, rt+2, rt+3, ..., onde o que desejamos maximizar é o retorno esperado, Rt, definido como uma função específica da sequência de recompensa. No caso mais simples, o retorno é só uma soma de recompensas: Rt = rt+1 + rt+2 + rt+3 + . . . + rT; Onde T é o passo final No modelo de aprendizagem por reforço utilizado no restante deste trabalho, são apresentadas ao agente percepções de seu ambiente (que representam os estados), aos quais aquele responde com ações, sendo estas realizadas sobre uma sequência de instantes de tempo discretos ti (i = 1, 2, . . . , m). A cada instante de tempo ti, o agente observa o estado 𝑠𝑡𝑖 do ambiente e seleciona uma ação 𝑎𝑡𝑖 específica, o que irá provocar uma alteração no estado do ambiente para 𝑠𝑡𝑖+1. Ao realizar a ação 𝑎𝑡𝑖, uma avaliação desta ação, na forma de punição ou recompensa, é apresentada ao agente pelo ambiente, sendo a mesma denotada por 𝑟𝑡𝑖+1. Deste modo, o agente irá interagir com o seu ambiente em busca de otimizar a escolha de suas ações. 𝑅𝑡 = ∑ 𝑟𝑡+𝑖 ∞ 𝑖=0 (3.1) O ambiente é representado por um conjunto finito de estados S, cujos elementos 𝑠𝑡𝑖 representam os estados tomados no instante de tempo discreto ti. Para cada estado, associa-se um conjunto A(𝑠𝑡𝑖) finito de ações 𝑎𝑡𝑖. Usando a abordagem da aprendizagem por reforço, busca-se garantir a obtenção da melhor política de escolha das ações para o problema abordado. Para garantir a convergência para o ótimo, restrições na estrutura do ambiente são adicionadas. Assume-se que o ambiente opera segundo o modelo de Processos de Decisão Markovianos (PDM), de modo que a decisão a ser tomada em um instante específico depende apenas das informações disponíveis nesse instante. No processo de decisão markoviano, em seu modo estacionário, os resultados de uma ação, em termos de transição de estados e recompensa, obedecem a uma probabilidade de distribuição fixa que depende somente do estado corrente e da ação realizada. A cada instante, portanto, somente uma única ação pode ser executada. 16 A propriedade de Markov permite soluções incrementais, como na programação dinâmica (Bellman, 1957), onde os valores obtidos em um estado 𝑠𝑡𝑖+1 são calculados a partir dos valores obtidos no estado 𝑠𝑡𝑖, de maneira recursiva. Formalmente, um PDM pode ser descrito por uma 4-tupla 〈𝑆, 𝐴, 𝑃, 𝑅〉 onde S é um conjunto finito de estados, A é um conjunto finito de ações, P : S × A × S → [0,1] é a função probabilidade de transição e R : S × A × S → ℝ é valor esperado de retorno: 𝑃𝑠𝑠′ = Pr {𝑠𝑡+1 = 𝑠 ′|𝑠𝑡 = 𝑠, 𝑎𝑡 = 𝑎} (3.2) 𝑅𝑠𝑠′ = 𝐸{𝑟𝑡+1|𝑠𝑡 = 𝑠, 𝑎𝑡 = 𝑎, 𝑠𝑡+1 = 𝑠 ′} (3.3) O termo 𝑃𝑠𝑠′(a) indica a probabilidade de se tomar a ação a no estado s e o próximo estado ser s’. E é o valor esperado do retorno 𝑟𝑡𝑖+1, sempre que o estado s, no instante t, passe para o estado s’, no tempo t + 1, sob a ação a. O sistema evolui dinamicamente de acordo com as suas probabilidades de transição que podem ser conhecidas (existe um modelo para o sistema) ou não. Deste modo, busca-se inicialmente estimar a função de valor estado-ação Q(s,a) associada ao seu respectivo par estado-ação (s,a). Essa função associa a cada par considerado uma estimativa do retorno esperado obtido quando uma ação particular é tomada em um dado estado e uma política π(s,a) é seguida daí em diante. Antes de detalhar o que vem a ser a função de valor estado-ação, apresentar-se-á algumas definições básicas associadas ao problema da aprendizagem por reforço (Sutton; Barto, 1998). Uma política 𝜋𝑡(𝑠, 𝑎) associada ao problema é um mapeamento das representações dos estados em probabilidades (no caso da política estocástica) de seleção de cada uma das ações possíveis, ou seja: 𝜋𝑡(𝑠, 𝑎) = Pr {𝑎𝑡 = 𝑎|𝑠𝑡 = 𝑠} (3.4) O retorno total esperado, que corresponde ao valor esperado de todas as recompensas e/ou punições colhidas pela política empregada, é dado por: 𝑅𝑡 = 𝑟𝑡 + 𝑟𝑡+1 + 𝑟𝑡+2 + 𝑟𝑡+3 + ⋯ + 𝑟𝑇 (3.5) onde rt+i é a recompensa/punição obtida no i-ésimo instante de tempo e T é o horizonte de tempo. No caso de T → ∞, o retorno total esperado é dado por: 𝑅𝑡 = 𝑟𝑡 + 𝛾𝑟𝑡+1 + 𝛾 2𝑟𝑡+2 + 𝛾 3𝑟𝑡+3 + ⋯ = ∑ 𝛾 𝑖𝑟𝑡+𝑖 ∞ 𝑖=0 (3.6) 17 onde γ é o fator de desconto, 0 ≤ γ ≤ 1, utilizado para garantir que 𝑅𝑡 seja finito, dado que cada 𝑟𝑡+𝑖 é finito. Com base nas definições apresentadas, pode-se descrever formalmente o que é uma função de valor estado-ação associada a uma dada política π(s,a) através da equação: 𝑄𝜋(𝑠, 𝑎) = 𝐸𝜋{∑ 𝑅𝑡|𝑠𝑡 = 𝑠, 𝑎𝑡 = 𝑎 ∞ 𝑖=0 } (3.7) A questão central da aprendizagem por reforço pode então ser colocada: • Dada uma política (s,a), qual a melhor forma de estimar 𝑄𝜋(𝑠, 𝑎), ∀𝑠 ∈ 𝑆 e ∀𝑎 ∈ 𝐴(𝑠)? • Conhecendo-se uma resposta afirmativa para a questão anterior, de que forma essa política pode ser modificada, tal que 𝑄𝜋(𝑠, 𝑎) convirja para o ótimo e a política ótima correspondente possa ser obtida? Vários são os resultados encontrados na literatura que apontam uma resposta a estas questões, notadamente aqueles baseados em programação dinâmica (Bellman, 1957), métodos de Monte Carlo (Sutton; Barto, 1998), diferenças temporais (Sutton; Barto, 1998] e o algoritmo Q-Learning (Watkins, 1989). 3.2 Q-learning Neste trabalho optou-se utilizar o algoritmo Q-Learning, desenvolvido por Watkins (Watkins, 1989). Dentre as vantagens desse algoritmo está o fato de ele aproximar diretamente o valor ótimo de Q(s,a), independentemente da política utilizada. Os valores de Q(s,a) são atualizados segundo a equação: 𝑄(𝑠, 𝑎) ← 𝑄(𝑠, 𝑎) + 𝛼[𝑟 + 𝛾. 𝑚𝑎𝑥𝑎′𝑄(𝑠 ′, 𝑎′) − 𝑄(𝑠, 𝑎)] (3.8) onde α é a taxa de aprendizagem. O algoritmo que implementa o Q-Learning está mostrado a seguir: 18 Algoritmo 3.1: Descrição do algoritmo Q-Learning. 1 Inicialize Q(s,a) randomicamente; 2 Para cada episódio; 3 Inicialize s; 4 Repita para cada passo do episódio; 5 Escolha a para s usando a política π; (ε-gulosa, por ex.); 6 Dado a ação a, observe r, s’; 7 𝑄(𝑠, 𝑎) ← 𝑄(𝑠, 𝑎) + 𝛼[𝑟 + 𝛾. 𝑚𝑎𝑥𝑎′𝑄(𝑠 ′, 𝑎′) − 𝑄(𝑠, 𝑎)] 8 s ← s’; 10 até condição de parada estabelecida. Dado que a convergência do algoritmo só é garantida se todos os pares estado-ação forem visitados infinitas vezes, a escolha da política a ser utilizada no Q-Learning deve garantir que todos os pares tenham uma probabilidade não nula de serem visitados. Isto pode ser alcançado utilizando-se uma política ε-gulosa, definida por: 𝜋(𝑠, 𝑎) = { 1 − 𝜖 + 𝜖 |𝐴(𝑠)| , 𝑠𝑒 𝑎 = 𝑎∗ = 𝑎𝑟𝑔𝑚𝑎𝑥𝑎𝑄(𝑠, 𝑎) 𝜖 |𝐴(𝑠)| , 𝑠𝑒 𝑎 ≠ 𝑎∗ (3.9) A política ε-gulosa seleciona a ação aleatória com probabilidade ε, e a ação de maior valor esperado com probabilidade (1- ε). Assim, o controle da gula (aleatoriedade) é estabelecido por ε, enquanto |A(s)| corresponde ao número de ações que podem ser axecutadas a partir de um estado s (Lima Júnior; 2009). As restrições estabelecidas em (3.9) são condições necessárias para que o Q-learning encontre uma política ótima, permitindo que o mesmo explore o espaço de estados do problema. 3.3 Maldição do dimensionamento Apesar de possuir fortes provas matemáticas da convergência de 𝑄(𝑠, 𝑎) para valores ótimos, a aplicação do algoritmo Q-Learning em problemas práticos mostra-se restrita, normalmente abrangendo problemas de pequeno porte. A razão para essa limitação se deve ao fato do Q-Learning ter que visitar cada par estado-ação um número infinito de vezes para que sua política convirja para o ótimo. Sabe-se que a dimensão da estrutura de armazenamento da função Q, que é necessária para se obter a política ótima, cresce em função do número de estados e de ações. Ao se analisar esse crescimento, percebe-se que o mesmo ocorre de maneira 19 exponencial. Este problema, denominado maldição da dimensionalidade, foi introduzido por Belmann (Bellman, 1957) e implica na impossibilidade de execução de um algoritmo para certas instâncias de um problema pelo esgotamento de recursos computacionais para obtenção de sua saída. Infere-se, consequentemente, que para que se possa aplicar a solução baseada no Q- Learning a aplicações que envolvam um número significativo de parâmetros (estados e ações), algum mecanismo deve ser criado para contornar o problema do dimensionamento inerente ao método da aprendizagem por reforço. 3.4 Considerações O objetivo deste capítulo foi apresentar noções básicas acerca da aprendizagem por reforço, notadamente, do algoritmo Q-Learning e da maldição da dimensionalidade inerente ao método. A compreensão do presente capítulo, já que toda a base teórica deste trabalho foi formada a partir deste assunto, é de vital importância para entender a necessidade do uso de métodos hierárquicos e do processamento paralelo, além de permitir uma melhor compreensão da modelagem do problema dos k-Servos segundo a aprendizagem por reforço, assuntos esses que serão abordados nos capítulos seguintes. 20 Capítulo 4 Aprendizagem por reforço hierárquica Este capítulo apresenta a fundamentação teórica da aprendizagem por reforço baseada em técnicas de decomposição hierárquica, denominada aprendizagem por reforço hierárquica6. Apresentar-se-á suas características, princípios e seus principais algoritmos, bem como outros mecanismos para aceleração do aprendizado encontrados na literatura. 4.1 Aspectos teóricos da aprendizagem por reforço hierárquica Dentre os métodos propostos na literatura para acelerar a convergência dos algoritmos de aprendizagem por reforço e permitir sua aplicação a problemas mais realistas, o método baseado em técnicas de decomposição hierárquica, denominado aprendizagem por reforço hierárquica (Hierarchical Reinforcement Learning – HRL), pode ser destacado. Baseia-se no princípio de “dividir-para-conquistar”, onde problemas complexos podem ser resolvidos mais facilmente se divididos em um conjunto de problemas menores. Os problemas menores podem ser resolvidos de maneira mais simples se considerados isoladamente. Por fim, eles são recombinados para formar a solução do problema global (Ryan, 2002). O princípio básico da aprendizagem por reforço hierárquica é acelerar o aprendizado a partir da redução da estrutura de armazenamento da função Q, a qual é utilizada para se obter a política ótima. Isto é obtido a partir da divisão do problema complexo em subproblemas, fazendo com que a dimensão da estrutura de armazenamento da função Q utilizada pela aprendizagem por reforço clássica em cada subproblema seja reduzida proporcionalmente. Como o tempo de aprendizagem e os requisitos de memória são determinados pelo número de pares estado-ação que necessitam ser visitados, a diminuição das quantidades destes pares fazem com que o processo de aprendizagem seja acelerado, em decorrência da redução do tempo de busca no espaço de estados-ações. Isto implica que a convergência da política nestes subproblemas ocorre de forma mais rápida. A redução no número de ações pode ser feita, 6 A aprendizagem por reforço tradicional, baseada no algoritmo Q-Learning, apresentada no capítulo anterior será chamada de clássica. 21 também, com a identificação de ações que sejam comprovadamente inúteis e a sua consequente eliminação do conjunto das ações possíveis. Pode-se utilizar a aprendizagem por reforço para se obter as políticas ótimas tanto para o problema global quanto para seus subproblemas. Não necessariamente o problema global é ótimo mesmo se constituídos de subproblemas ótimos. Embora possa parecer uma contradição ao princípio da otimalidade de Bellman (Bellman, 1957), deve-se ressaltar que as condições de otimalidade são diferentes para cada contexto. A técnica utilizada de dividir problemas complexos em subproblemas faz com que as ações deixem de operar somente de maneira discreta e sequencial (ou seja, a cada passo de tempo). Assim, na aprendizagem por reforço hierárquica, ao invés de se ter, exclusivamente, ações que são requeridas a cada passo de tempo, tem-se uma hierarquia de ações abstratas (princípio da abstração temporal), que operam sobre diversos passos de tempo (Ryan, 2002; Hengst, 2011). Atividades que seguem sua própria política são executadas em um tempo abstrato até atingir um estado terminal, quando então o controle é repassado para a política principal. Estas ações que operam em um tempo abstrato são denominadas de comportamentos (ou ações de múltiplos passos), que por sua vez são compostos por ações que operam a cada passo de tempo e que são denominadas ações primitivas (ou ações de um único passo). Em outras palavras, executar um comportamento resulta em uma sequência de ações primitivas sendo realizadas. Para facilitar a compreensão, considere a execução de um algoritmo, cuja função principal é composta por instruções simples e sub-rotinas, sendo estas compostas por uma série de instruções simples. O algoritmo executará, sequencialmente, as instruções simples até encontrar uma sub-rotina, que assumirá, momentaneamente, o controle do algoritmo. A sub- rotina executará toda a sua sequência de instruções simples, até atingir o seu término, repassando novamente o controle à função principal. Em seguida, a função principal voltará a executar as instruções contidas após a chamada da sub-rotina, até encontrar uma nova sub- rotina, repetindo o processo até finalizar o algoritmo. Neste exemplo, os comportamentos são as sub-rotinas e as ações primitivas as instruções simples. As ações primitivas operam de forma discreta, em instantes de tempo discretos ti (i = 1, 2, . . .), e sequencial, de modo que uma ação 𝑎𝑡+1 no instante t +1 só é executada se a ação at no instante t já tiver sido executada. Por isso, diz-se que as ações primitivas são ações de um único passo, ou seja, a ação é finalizada em um único instante de tempo. Os comportamentos, entretanto, não operam sobre um único instante de tempo. Ao se executar um comportamento, em um instante t, o mesmo irá ser finalizado em um instante t+k, 22 sendo o instante do seu término determinado pelo seu conjunto de ações primitivas. De modo mais detalhado, um comportamento é executado sobre uma sequência discreta de instantes de tempo, t, t+1, t+2, . . . , t+k−1, t+k, de modo que cada instante de tempo corresponde a execução de uma ação primitiva. Por isso se diz que os comportamentos operam em um tempo abstrato ou sobre diversos passos de tempo. Deve-se notar que o processo de decisão markoviano apresentado anteriormente está limitado a ações que operam sobre passos de tempo discretos e sequenciais, não englobando as ações sugeridas pela técnica hierárquica, que operam em um tempo abstrato. Para tanto, faz-se necessário um novo modelo que leve em conta esta restrição. 4.2 Processos de Decisão Semi-Markovianos (PDSM) O Processo de Decisão Semi-Markoviano (PDSM) (Ryan, 2002) é a extensão do modelo tradicional para incluir o conceito de duração, permitindo o uso de ações que operam em um tempo abstrato, ou seja, em múltiplos passos. Processos de decisão Markovianos que incluem ações abstratas são chamados de Problemas de Decisão Semi-Markovianos (Semi Markov Decision Problems - SMDP) (Hengst, 2011). É indicado para modelar qualquer sistema sequencial e discreto no tempo (Ryan, 2002). Formalmente, o PDSM pode ser descrito por uma 4-tupla 〈𝑆, 𝐵, 𝑃, 𝑅〉, onde S é um conjunto finito de estados, B é um conjunto finito de comportamentos (ações abstratas), P : S × B × S → [0,1] é a função probabilidade de transição e R : S × A × S → ℝ é o valor esperado de retorno. 𝑃𝑠,𝑠′,𝑘(𝐵) = Pr {𝑠𝑡+𝑘 = 𝑠 ′|𝑠𝑡 = 𝑠, 𝐵𝑡 = 𝐵} (4.1) 𝑅𝑠,𝑠′,𝑘(𝐵) = 𝐸{∑ 𝛾 𝑖𝑟𝑡+𝑖|𝑠𝑡 = 𝑠, 𝐵𝑡 = 𝐵, 𝑠𝑡+𝑘 = 𝑠 ′}𝑘−1𝑖=0 (4.2) Ambos, P e R devem obedecer à propriedade markoviana, melhor dizendo, eles só podem depender do comportamento executado e do estado em que iniciou. O termo 𝑃𝑠,𝑠′,𝑘(𝐵) indica a probabilidade de se executar o comportamento B no estado s e o próximo estado ser s’ no tempo t+k. E é o valor esperado do retorno ∑ 𝛾𝑖𝑟𝑡+𝑖𝑅𝑡(𝐵) 𝑘−1 𝑖=0 , sempre que o estado s, no instante i, passe para o estado s’, no tempo t +k, sob a execução do comportamento B. Em outras palavras, o valor do retorno Rt ao se executar um comportamento B que iniciou no estado st e termina num estado st+k é equivalente ao acúmulo dos reforços recebidos para cada ação primitiva executada durante a execução de B. Matematicamente: 23 𝑅𝑡(𝐵) = 𝑟𝑡 + 𝛾𝑟𝑡+1 + 𝛾 2𝑟𝑡+2 + 𝛾 3𝑟𝑡+3 + ⋯ + 𝛾 𝑘−1𝑟𝑡+𝑘−1 (4.3) 4.3 Algoritmos de aprendizagem por reforço hierárquica Toda a fundamentação teórica apresentada até então não levou em conta aplicações específicas, tendo sido apresentado, somente, conceitos gerais sobre aprendizagem por reforço hierárquica. Nesta seção, mostra-se, sucintamente, os principais algoritmos de aprendizagem por reforço hierárquica. Todas essas implementações diferem significativamente em alguns aspectos, como por exemplo, na maneira de abordar o problema ou quais elementos da técnica hierárquica enfatizar mais intensamente. Entretanto, todas elas foram desenvolvidas sobre rígida estrutura teórica. São algoritmos de âmbito geral, não se restringindo a uma aplicação específica. Se atendidas as condições de convergência de cada método, os algoritmos alcançarão valores ótimos. 4.3.1 Q-Learning Semi-Markoviano É o algoritmo mais simples dentre todos os hierárquicos. É uma extensão do Q-Learning tradicional (Watkins 1989), mantendo, praticamente, as mesmas características, inclusive a maneira em que a política ótima pode ser aprendida. A principal diferença entre ambos é que o algoritmo baseado na aprendizagem por reforço hierárquica utiliza o conceito de abstração temporal, introduzindo a noção de comportamentos. Para tanto, utiliza o modelo de PDSM em sua estrutura. A sua convergência para valores ótimos, se atendidas certas condições, pode ser mostrada de maneira similar àquela do Q-Learning tradicional. Maiores informações em Bratdke et al. (Bratdke; Duff, 1995). Assim como o Q-learning padrão aprende uma função valor estado-ação, o SMDP Q- learning aprende uma função valor estado-comportamento Q: S × B → R, que é uma aproximação para a função valor estado-comportamento ótima Q*: 𝑄∗(𝑠, 𝐵) = 𝐸{∑ 𝛾𝑖𝑘−1𝑖=0 𝑟𝑡+𝑖 + 𝛾 𝑘𝑉∗(𝑠𝑡+𝑘)|𝜀(𝑠, 𝐵, 𝑡)} (4.4) onde k é a duração do comportamento B, e ε(s, B, t) indica o evento para o comportamento B no estado s no tempo t. A política ótima é definida como a seguir: 𝜋∗(𝑠) = 𝑎𝑟𝑔𝑚𝑎𝑥𝐵∈ℬ𝑄 ∗(𝑠, 𝐵) (4.5) 24 A aproximação Q(s, B) pode aprender via uma regra de atualização análoga a do Q-learning: 𝑄(𝑠𝑡, 𝐵𝑡) 𝛼 ← 𝑅𝑡 + 𝛾 𝑘𝑚𝑎𝑥𝐵∈ℬ𝑄(𝑠𝑡+𝑘, 𝐵) (4.6) onde k é a duração de Bt e Rt é o somatório descontado de todos os valores de reforço recebidos durante a execução do comportamento: 𝑅𝑡 = ∑ 𝛾 𝑖𝑟𝑡+𝑖 𝑘−1 𝑖=0 (4.7) Pode ser demonstrado que o SMDP Q-learning converge para o ótimo sob uma política de comportamento de forma similar ao Q-learning padrão. Algoritmo 4.1 SMDP Q-learning t ← 0 Observe o estado st Enquanto st não é um estado terminal faça Escolha o comportamento Bt ← π(st) de acordo com uma política de exploração Retorno_total ← 0 desconto ← 1 k ← 0 Enquanto Bt ← 0 não tenha terminado faça Execute Bt Observe o retorno r Retorno_total ← Retorno_total + desconto × r desconto ← desconto × γ k ← k + 1 Fim enquanto Observe o estado st+k 𝑄(𝑠𝑡, 𝐵𝑡) 𝛼 ← 𝑅𝑒𝑡𝑜𝑟𝑛𝑜_𝑡𝑜𝑡𝑎𝑙 + 𝑑𝑒𝑠𝑐𝑜𝑛𝑡𝑜 × 𝑚𝑎𝑥𝐵∈ℬ𝑄(𝑠𝑡+𝑘, 𝐵) t ← t + k Fim enquanto Fim 25 4.3.2 Q-Learning Semi-Markoviano Hierárquico O Q-Learning Semi-Markoviano Hierárquico (HSMQ) é um algoritmo de aprendizagem recursivamente ótimo, cuja política é baseada em comportamentos. Trata-se de um aprimoramento do Q-Learning Semi-Markoviano. A regra de atualização do SMDPQ dada pela equação (4.6) é aplicada recursivamente com uma função de retornos local em cada nível da hierarquia. A função Tarefa_Hierarquica no pseudocódigo retorna um conjunto de ações disponíveis que pode ser usada por um comportamento particular em dado estado. Esta hierarquia é codificada pelo treinador baseado no conhecimento de que ações são apropriadas em quais ocasiões. A convergência de sua política para o ótimo pode ser provada de modo similar a do Q-Learning Semi-Markoviano, desde que, obviamente, atendidas as condições requeridas. Algoritmo 4.2 HSMQ-learning Retorna sequência de estados de transição {〈𝑠𝑡, 𝑎𝑡, 𝑠𝑡+1, … 〉} Se at é primitivo então Execute a ação at Observe o próximo estado st+1 Retorne {〈𝑠𝑡, 𝑎𝑡, 𝑠𝑡+1, 𝑎𝑡+1〉} Caso contrário Sequência S ← { } Comportamento B ← at At ← Tarefa_Hierarquica(st, B) Enquanto B não está terminado faça Escolha a ação at ← B.π(st) de At de acordo com uma política de exploração Sequência S’ ← HSMQ(st, at) k ← 0 Retorno_total ← 0 para cada 〈s, a, s'〉 ∈ 𝑆′ faça Retorno_total ← Retorno_total + γkB.r(s, a, s’) k ← k + 1 26 4.3.3 MAXQ-Q O MAXQ-Q é um algoritmo mais sofisticado que os anteriores. Sua política de aprendizado é equivalente ao do HSMQ. Difere, porém, por usar uma decomposição especial da função de valor estado-ação no intuito de aprender mais eficientemente. O MAXQ-Q se baseia na observação que o valor de um comportamento B como parte de um comportamento pai P pode ser divido em duas partes: o retorno esperado enquanto B é executado, e o retorno descontado de continuar executando P após B ter terminado. Isto é: 𝑃. 𝑄(𝑠, 𝐵) = 𝑃. 𝐼(𝑠, 𝐵) + 𝑃. 𝐶(𝑃, 𝑠, 𝐵) (4.8) Onde P.I(s, B) é o retorno descontado total esperado (de acordo com a função de retorno do comportamento dos pais P) que é recebida enquanto executado o comportamento B de estado inicial s e P.C(Bpai, s, Bfilho) é o retorno total esperado de continuar executando o comportamento Bpai após Bfilho estar concluído, descontados adequadamente para levar em conta o tempo gasto em Bfilho (novamente com retornos calculados de acordo com o comportamento P) Além disso a função I(s, B) pode ser recursivamente decomposta em I e C pela regra: 𝑃. 𝐼(𝑠, 𝐵) = 𝑚𝑎𝑥𝑎∈𝐵.𝐴𝑃. 𝑄(𝑠, 𝑎) (4.9) Há várias vantagens nesta decomposição, principalmente no valor em aprendizagem recursivamente ótimo Q. As funções I e C podem cada uma ser representada como determinados estados de abstração que não são aplicados em ambas as partes. Esta explanação fim para cada Observe o próximo estado st+k At+k ← Tarefa_Hierárquica(st+k, B) 𝐵. 𝑄(𝑠𝑡, 𝑎𝑡) 𝛼 ← 𝑅𝑒𝑡𝑜𝑟𝑛𝑜𝑡𝑜𝑡𝑎𝑙 + 𝛾 𝑘𝑚𝑎𝑥𝑎∈𝐴𝑡+𝑘𝐵. 𝑄(𝑠𝑡+𝑘, 𝑎) S ← S + S’ t ← t + k fim enquanto retornar S fim se end 27 é complexa e está fora do escopo desta revisão. Para maiores detalhes e pseudocódigo ver (Dietterich, 2000a) Algoritmo 4.3 MAXQ-Q learning Digite a equação aqui. Seja seq = ∅ a sequência de estados visitados enquanto executar i se i é um estado primitivo Max_no executar i¸ receber r, e observar o estado resultante s’ 𝑉𝑡+1(𝑖, 𝑠) ≔ (1 − 𝛼𝑡(𝑖)). 𝑉𝑡(𝑖, 𝑠) + 𝛼𝑡(𝑖). 𝑟𝑡 Ponha s dento do início de seq caso contrário seja count = 0 enquanto Ti(s) for falso faça escolha uma ação a de acordo com a política de exploração πi(i,s) seja Seq_filho = MAXQ-Q(a, s), onde Seq_filho é a sequência de estados visitados enquanto executamos a ação a observe o estado resultante s’ seja 𝑎∗ = 𝑎𝑟𝑔𝑚𝑎𝑥𝑎′[?̃?𝑡(𝑖, 𝑠 ′, 𝑎′) + 𝑉𝑡(𝑎 ′, 𝑠′)] seja N = comprimento(Seq_filho) para cada s em Seq_filho faça ?̃?𝑡+1(𝑖, 𝑠, 𝑎) ≔ (1 − 𝛼𝑡(𝑖)). ?̃?𝑡(𝑖, 𝑠, 𝑎) + 𝛼𝑡(𝑖). 𝛾 𝑁[?̃?𝑖(𝑠 ′) + ?̃?𝑡(𝑖, 𝑠 ′, 𝑎∗) + 𝑉𝑡(𝑎 ∗, 𝑠)] 𝐶𝑡+1(𝑖, 𝑠, 𝑎) ≔ (1 − 𝛼𝑡(𝑖)). 𝐶𝑡(𝑖, 𝑠, 𝑎) + 𝛼𝑡(𝑖). 𝛾 𝑁[𝐶𝑡(𝑖, 𝑠 ′, 𝑎∗) + 𝑉𝑡(𝑎 ∗, 𝑠′)] N := N – 1 fim // para anexar Seq_filho na parte da frente de seq s := s’ fim // enquanto fim // caso contrário retornar seq fim 28 4.3.4 Q-Learning com Hierarquia de Máquinas Abstratas O Q-Learning com Hierarquia de Máquinas Abstratas (Q-Learning with Hierarchies of Abstract Machines – HAMQ) é um algoritmo de aprendizagem hierarquicamente ótimo que usa um modelo mais elaborado para estruturar o espaço da política. Os comportamentos são implementados como uma hierarquia de máquinas abstratas (Hierarchies of Abstract Machines – HAM), que se assemelha com uma máquina de estados finita, incluindo uma máquina de estados interna. O estado da máquina indica as ações que se podem tomar. Os estados das máquinas determinam as ações a serem tomadas. Ações incluem: 1) executar ações primitivas, 2) chamar outras máquinas como sub-rotinas, 3) fazer escolhas, 4) concluir e retornar o controle de chamada de um comportamento. As transições entre máquinas de estados podem ser determinísticos, estocásticos ou podem depender do estado do ambiente. A aprendizagem acontece somente na escolha de estados. Algoritmo 4.3 HAMQ-learning t ← 0 nó ← nó inicial Retorno_total ← 0 k ← 0 escolha a ← nulo escolha o estado s ← nulo escolha o nó n ← nulo enquanto s não é um estado terminal faça se nó é uma nó de ação então Execute a ação Observe o retorno r Retorno_total ← Retorno_total + γkr k ← k + 1 nó ← próximo_nó Caso contrário nó é um nó de escolha Observe o estado s’ se n ≠ nulo então 𝑄(𝑛, 𝑠, 𝑎) 𝛼 ← 𝑅𝑒𝑡𝑜𝑟𝑛𝑜_𝑡𝑜𝑡𝑎𝑙 + 𝛾𝑘𝑚𝑎𝑥𝑎′∈𝐴𝑄(𝑛ó, 𝑠 ′, 𝑎′) Retrono_total ← 0 k ← 0 fim se n ← nó s ← s’ Escolher a transição a ← π(n, s) de acordo com um política de exploração nó ← a.destino fim enquanto fim 29 No HAMQ os comportamentos são meramente uma conveniência topográfica. Na realidade eles são compilados em uma única máquina abstrata, consistindo de nós de ação e nós de escolha. O algoritmo 4.3 mostra o pseudocódigo para aprendizagem em uma máquina deste tipo. Maiores informações em Parr e Russel (Parr; Russell, 1998). 4.4 Outras técnicas para aceleração do aprendizado Uma maneira de acelerar o aprendizado é melhorando o aproveitamento das experiências, por meio de generalizações temporais, espaciais ou das ações. Na generalização temporal, os resultados de uma experiência são distribuídos para estados executados anteriormente. Uma arquitetura denominada Dyna, que utiliza esta técnica, foi proposta inicialmente por Sutton (Sutton, 1990). O funcionamento deste algoritmo é muito similar ao do Q-Learning. À medida que as ações são executadas, o algoritmo aprende iterativamente o modelo da função de transição entre estados e das recompensas, usando a experiência e o modelo aprendido para ajustar a política. Na generalização espacial (Ribeiro, 1998), os resultados de uma experiência são distribuídos para vários estados, segundo alguma medida de similaridade entre os mesmos. O algoritmo Q-Learning é combinado com o espalhamento espacial na função de valor estado- ação, de tal maneira que durante o aprendizado outros pares estado-ação não envolvidos na experiência também são atualizados. O autor prova que se as garantias de convergência do algoritmo Q-Learning e certas condições da função de espalhamento forem satisfeitas, a política converge para o ótimo Na abstração estrutural, estados são agregados de maneira que o tamanho efetivo (e a complexidade) do problema seja reduzido. É realizada quando existe a necessidade de representar a função valor em domínios cujo espaço de estados é muito grande ou contínuo. O uso de aproximadores de funções como Redes Neurais Artificiais (RNA) para representar a avaliação do custo é um dos procedimentos mais comuns, tendo sido utilizado com sucesso por Tesauro (Tesauro, 1995) no programa TD-Gammon. Finalmente, outras maneiras possíveis de aceleração do aprendizado incluem a abordagem distribuída (Littman; Boyan, 1993) e a utilização de uma base de casos (Drummond, 2002). Na abordagem distribuída, em vez de um único agente, tem-se diversos agentes aprendendo ao mesmo tempo; a utilização de uma base de casos reutiliza conhecimento sobre as soluções já encontradas. 30 4.5 Considerações O objetivo deste capítulo foi fornecer o embasamento teórico da aprendizagem por reforço hierárquica para abordagem de problema reais complexos, utilizada com o fim de superar a maldição da dimensionalidade. Apresentou-se os seus princípios, suas características e principais algoritmos, assim como outros métodos de aceleração do aprendizado encontrados na literatura. Espera-se que essa breve exposição sobre o tema possa ajudar o leitor a compreender mais facilmente o modo como a proposta de solução MTS utilizando a aprendizagem por reforço, tanto no seu modo clássico (para problemas de menor porte) quanto hierárquico (para problemas complexos realistas). 31 Capítulo 5 Computação Paralela Neste capítulo iremos tratar de arquiteturas avançadas de computadores que utilizam paralelismo via múltiplas unidades de processadores. Iremos abordar conceitos e descrever metodologias que comparam aplicações sequenciais e paralelas. Este capítulo está organizado da seguinte forma: na seção 5.1 iremos tratar das noções gerais do processamento paralelo, na seção 5.2 descreveremos as principais arquiteturas paralelas e na seção 5.3 as origens para perda de desempenho. 5.1 Fundamentos sobre Processamento Paralelo Computação paralela consiste num paradigma pelo qual cálculos computacionais podem ser executados mais rápidos, e diante das mudanças significativas nas arquiteturas dos computadores e dos avanços ocorridos nas últimas décadas na tecnologia dos microprocessadores tornou-se uma proposta vantajosa. No entanto, muitos dos programas atuais não são capazes de usufruir destes benefícios pois são escritos assumindo que suas instruções sejam executadas sequencialmente. Pelo fato de que a semântica sequencial embutida em muitas das linguagens de computador produzirem resultados satisfatórios, torna incomum oportunidades para execução em paralelo. Essa mudança tem uma consequência muito importante para os desenvolvedores de software: simplesmente adicionando mais processadores não irá magicamente melhorar o desempenho da maioria dos programas em série, ou seja, programas que foram escritos para rodar em um único processador (Pacheco, 2011). Tais programas não têm conhecimento da existência de múltiplos processadores, e o desempenho de um programa em um sistema com múltiplos processadores será efetivamente o mesmo que o seu desempenho em um único processador. Na realidade, uma das razões pela qual continuamos a escrever programas sequenciais é devido as arquiteturas de computadores explorarem de forma bem sucessida o paralelismo (Lin; Snyder, 2008). A constante melhoria da tecnologia de silício permitiu adicionar várias formas de paralelismo dentro dos projetos de processadores sequenciais, o chamado paralelismo oculto (hidden parallelism). Tal paralelismo, junto com o aumento da velocidade de clock, tem permitido que cada geração 32 subsequente de chip de processadores executem programas mais rápidos, enquanto preservam a ilusão de execução sequencial (Lin; Snyder, 2008). Quando vistos no contexto da rápida taxa de desenvolvimento de microprocessadores, somos tentados a questionar a necessidade de dedicar esforço significativo no sentido de explorar o paralelismo como um meio de acelerar aplicações. Afinal, se levarmos dois anos para desenvolver uma aplicação paralela, durante o qual o hardware subjacente e/ou plataforma de software tornou-se obsoleto, o esforço de desenvolvimento é claramente desperdiçado (Grama et al, 2003). Este aumento sem precedentes fez com que os usuários e desenvolvedores de softwares podessem simplesmente esperar pela próxima geração de microprocessadores, a fim de obter maior desempenho dos programas de aplicação (Pacheco, 2011). Para que possamos atingir aumento de desempenho relevantes, devemos ir além da sequência de instruções dos programas atuais. Precisamos de programas capazes de operar múltiplas instruções simultaneamente. Devendo para isso, desenvolver novas técnicas de programação. Arquitetos de computadores têm buscado incrementar o desempenho das arquiteturas dos seus computadores. Alto desempenho pode ser atingido com circuitos densos rápidos, tecnologia de encapsulamento e paralelismo. Entretanto, esta tendência acabará em breve, pois existem barreiras físicas e de arquitetura que impõem limites à capacidade dos computadores com sistemas de processadores únicos. A Lei de Moore (Gordon Moore, co-fundador da Intel) de que “o número de transistores em um chip dobrará em aproximadamente dois anos” (Snyder; Lin, 2009) diminuiu para um incremento anual de cerca de 20% a partir de meados do ano 2000. A cada ano, mais e mais transistores cabem em um mesmo espaço, mas a sua velocidade de clock não pode ser aumentada sem sobreaquecimento. Devido ao aumento do consumo de energia proporcional ao quadrado do aumento da velocidade dos processadores, essa energia, em sua maioria, é dissipada em forma de calor o qual, em excesso, faz com que o circuito integrado não seja confiável (Assis, 2015). Em vez disso, os fabricantes estão voltando-se para arquiteturas multicore, em que múltiplos processadores (núcleos) compartilham o mesmo chip com caches compartilhados. Chips de multiprocessadores fazem computação mais eficiente, explorando paralelismo: Aproveitamento de vários processadores para trabalhar em uma única tarefa (Herlihy; Shavit, 2008). Segundo Snyder (2009) o advento do primeiro multi-core em 2005/2006 levou a comunidade a uma ampla discussão. As principais observações da discussão foram: 33 • Desenvolvedores de softwares têm desfrutado de forma constante das melhorias de desempenho há décadas, graças aos avanços na tecnologia de silício e projetos de arquitetura; • Programadores, que não necessitavam se preocupar com o desempenho, mudaram suas técnicas e metodologias ao longo dos anos; • Softwares já existentes geralmente não podem explorar chips multi-core diretamente; • Programas que não podem explorar chips multi-core não percebem as melhorias de desempenho agora e não o farão no futuro; • Muitos programadores não sabem como escrever programas paralelos. Podemos concluir que os programas devem mudar e para isso é preciso que os programadores mudem também. Especificamente, se a computação é reescrita de forma paralela e se os programas paralelos são escalonáveis, significa que é possível usar progressivamente mais processadores, então com o avanço da tecnologia de silício mais núcleos serão adicionados aos futuros chips e os programas reescritos manterão a curva de desempenho. Porém, programas paralelos não-escaláveis não irão desfrutar dos benefícios de avanços continuados da tecnologia de silício. Serão apresentadas a seguir estruturas que podem utilizar um grande número de processadores: Supercomputadores: os problemas de interesse dos laboratórios de pesquisas nacionais, os militares a as grandes corporações têm tradicionalmente requerido o uso de supercomputadores, cuja definição seria dos computadores mais rápidos do mundo. Atualmente o topo da lista é dominado por computadores paralelos com milhares de processadores. Na 48º edição da lista top500.org de novembro de 2016 a China e os Estados Unidos despontam na supremacia dos supercomputadores. O Sunway TaihuLight - Sunway MPP, Sunway SW26010 260C 1.45GHz, Sunway NRCPC, da National Supercomputing Center, em Wuxi - China com 10.649.600 cores e 93.014,6 TFlop/s aparece no topo da lista. Clusters: muitas vezes é observado que, independentemente da velocidade com que um único computador está conectando, dois ou mais deles em conjunto produzem um computador mais rápido no sentido de que máquinas combinadas podem executar mais instruções por unidade de tempo. E programas de computador bem elaborados são necessários para explorar essa potência adicional. Os clusters têm se tornado populares desde a década de 1990, pois são relativamente baratos para serem construídos com peças disponíveis no mercado. Os preços baixos os fazem lhes garante uma excelente ralação custo/benefício sobre outras formas de computação de alta qualidade. O mais popular talvez seja o Cluster de Beowulf, um sistema de 34 processamento construído a partir de computadores comuns e de um sistema operacional com código-fonte livre para computação paralela de alto desempenho. Servidores: a expansão da internet e a popularização dos serviços remotos, tais como os de buscas, têm criado amplas instalações de computadores em rede. Em termos do total de instruções executadas por segundos, estes centros representam um amplo recurso computacional. Esses enormes sistemas em rede estão sendo usados para analisar as características de sua carga de trabalho e executar outras computações intensivas de dados, nessas soluções também se aplicam técnicas de programação paralela. Computação em grid: de uma maneira mais generalizada, o conjunto de computadores não precisam estar no mesmo local, nem ser administrado pela mesma organização; os computadores conectados pela internet representam um enorme recurso computacional. A computação em grid busca proporcionar um serviço de computação singular, mesmo que os computadores subjacentes consistam tipicamente de máquinas fisicamente dispersas regidas por várias organizações administrativas. Para exemplificar a diferença entre algoritmos sequenciais e paralelos, iremos comparar algoritmos alternativos para encontrar a soma de uma sequência de números. Embora bastante simples este exemplo é suficiente para ilustrar a diferença entre uma solução sequencial e uma paralela. Dada uma sequência de números {17, 5, 19, 7, 4, 6, 13, 10}, a sua soma em sequencial será como mostrada na figura abaixo: Figura 5.1: Representação de um algoritmo para o cálculo de uma soma em sequência de números. Fonte: Snyder; Lin, 2009. 81 71 58 52 48 41 22 Sequência de números Te m p o 5 19 7 4 6 13 10 17 35 Uma outra maneira, mais paralela de somatório, é adicionar os números da série aos pares produzindo soma intermediárias, Figura 5.2: Representação de um algoritmo para o cálculo de uma soma em paralelo. Fonte: Snyder; Lin, 2009. Podemos ver que as duas soluções requerem o mesmo número de operações e os mesmos números de somas intermediárias, neste caso, não há vantagem entre as duas soluções quando usamos um único processador. Entretanto, com um computador paralelo que têm pelo menos 𝑃 = 𝑛 2 processadores, onde n é o número de elementos de uma série, todos os somatórios em um mesmo nível podem ser calculados simultaneamente, produzindo uma solução em um tempo ℴ(log 𝑛). Esta estratégia produz uma melhoria significante sobre o tempo de um algoritmo sequencial. Sequência de números Te m p o 81 33 48 23 10 26 22 17 5 19 7 4 6 13 10 36 5.2 Arquiteturas de computador 5.2.1 Arquitetura von Neumann A arquitetura "clássica" de von Neumann consiste em memória principal, uma unidade central de processamento (CPU) e uma interligação entre a memória e a CPU (Pacheco, 2011). A memória principal é composta por um conjunto de locações, cada uma capaz de armazenar instruções e dados. Cada locação consiste em um endereço, que é usado para acessar a locação e os seus conteúdos - as instruções ou dados armazenados na locação. A unidade central de processamento é dividida em uma unidade de controle e uma Unidade Lógica e Aritmética (ALU). A unidade de controle é responsável por decidir quais instruções em um programa devem ser executadas, e a ALU é responsável por executar a instrução atual. Os dados da CPU e as informações sobre o estado de execução de um programa são armazenados de forma especial, em armazenadores mais rápidos chamados registros. A unidade de controle tem um registrador especial chamado de contador de programas. Ele armazena o endereço da próxima instrução a ser executada. Instruções e os dados são transferidos entre a CPU e a memória através da interconexão. Esta tem sido, tradicionalmente, um barramento, que consiste de uma coleção de fios paralelos e algum hardware para controlar o acesso aos fios. Uma máquina de von Neumann executa uma única instrução de cada vez, e cada instrução opera apenas partes dos dados. A mais popular taxonomia para arquiteturas de computadores foi definida por Flynn em 1966 (El-Rewini; Abd-El-Barr, 2005). O esquema de classificação de Flynn é baseado na noção de fluxo de informações. São considerados dois tipos de fluxo de informação dentro de um processador: instruções e dados. O fluxo de instruções é definido como uma sequência de instruções executadas pela unidade de processamento. O fluxo de dados é definido como o tráfego de dados trocados entre a memória e a unidade de processamento. De acordo com a classificação de Flynn, os fluxos de instruções e de dados podem ser simples ou múltiplos. A arquitetura de computadores pode ser classificada em quatro categorias distintas: • single-instruction single-data streams (SISD); • single-instruction multiple-data streams (SIMD); • multiple-instruction single-data streams (MISD); e • multiple-instruction multiple-data streams (MIMD). 37 Computadores convencionais com um único processador são classificados como sistemas SISD. Computadores paralelos ou são SIMD ou MIMD. Quando só existe uma unidade de controle e todos os processadores executam a mesma instrução de modo sincronizado, a máquina paralela é classificada como SIMD. Numa máquina MIMD, cada processador tem sua própria unidade de controle e pode executar diferentes instruções de diferentes dados. Na categoria MISD, múltiplos fluxos de instruções operam sobre os mesmos dados. Na prática, não há máquina MISD viável. 5.2.2 Arquitetura SIMD O modelo SIMD de computação paralela consiste de duas partes: um computador habitual baseado no paradigma de von Neumann e um arranjo de processadores. O arranjo de processadores é um conjunto de elementos de processamento sincronizados capazes de realizar simultaneamente a mesma operação de dados. Cada processador é um arranjo que tem uma pequena quantidade de memória local onde os dados distribuídos residem ao mesmo tempo que está a ser processado em paralelo. Na arquitetura SIMD, o paralelismo é explorado através da aplicação de operações simultâneas em um grande conjunto de dados. Este paradigma é mais útil para a resolução de problemas que têm grande quantidade de dados que precisam ser atualizados no atacado. É especialmente poderosa em muitos cálculos numéricos regulares. Existem duas configurações principais que têm sido usados em máquinas SIMD (ver figura 5.3). No primeiro esquema, cada processador tem sua própria memória local. Processadores podem comunicar uns com os outros através da rede de interligação. Se esta rede não fornece conexão direta entre um determinado par de processadores, então este par pode trocar dados através de um processador intermediário. No segundo esquema SIMD, processadores e módulos de memória se comunicam uns com os outros através da rede de interligação. Dois processadores podem transferir dados entre eles através do módulo de memória intermediária ou, eventualmente, através de processadores intermediários. 38 Figura 5.3: Dois esquemas de SIMD. Unidade de controle P1 P2 P3 Pn-1 Pn M1 M2 M3 Mn-1 Mn Rede de interligação Unidade de controle P1 P2 P3 Pn-1 Pn M1 M2 M3 Mn-1 Mn Rede de interligação 39 5.2.3 Arquitetura MIMD Multiple-instruction multiple-data streams (MIMD) são arquiteturas paralelas constituídas de múltiplos processadores e múltiplos módulos de memória conectados via alguma rede de interligação. Eles se dividem em duas grandes categorias: memória compartilhada (memória comum) ou memória distribuída (memória local). A figura 5.4 ilustra a arquitetura geral destas duas categorias. Figura 5.4: Arquitetura memória compartilhada versus passagem de mensagem. M M M M Rede de interligação P P P P Arquitetura MIMD com memória compartilhada ou comum M M M M Rede de interligação P P P P Arquitetura MIMD com memória compartilhada ou local 40 Os processadores trocam informação por meio de sua memória no sistema de memória compartilhada, e trocam informação através de troca de mensagens, no sistema de memória local. Os sistemas de memória compartilhada se comunicam através de um barramento e um controlador de cache de memória. A arquitetura barramento/cache alivia a necessidade de memórias multiportas caras e circuitos de interface, bem como a necessidade de adotar um paradigma de troca de mensagens no desenvolvimento de um software de aplicação. Como o acesso à memória compartilhada é equilibrado, esses sistemas também são chamados de sistemas SMP (Symmetric multiprocessing). Cada processador tem oportunidade igual de leitura/gravação na memória, incluindo velocidades iguais de acesso. Um sistema de memória compartilhada tipicamente combina a memória local e o processador formando um nó da rede de interligação. Não há memória global, então é necessário mover os dados a partir de uma memória local para outra por meio da troca de mensagens. Isso geralmente é feito pelo par de comandos envio/recebimento, que deve ser escrito no programa de aplicação por um programador. Assim, os programadores devem aprender o paradigma de passagem de mensagens, que envolve cópia de dados e lidar com problemas de consistência. 5.2.4 Organização da Memória Compartilhada (Shared Memory) Um modelo de memória compartilhada é aquele em que os processadores se comunicam através de leitura e escrita localizada em uma memória compartilhada que é igualmente acessível por todos os processadores. Cada processador pode ter registros, buffers, caches e bancos de memória locais como recursos adicionais de memória. Uma série de questões básicas deve ser levada em consideração na concepção de um sistema de memória compartilhada. Isto inclui o controle de acesso, sincronização, proteção e segurança. O controle de acesso determina quais os acessos de processos são possíveis para quais recursos. Modelos de controle de acesso fazem a verificação exigida para cada pedido de acesso emitido pelos processadores à memória compartilhada, contra o conteúdo da tabela de controle de acesso. Este último contém sinalizadores que determinam a legalidade de cada tentativa de acesso. Se houver tentativas de acesso aos recursos, então até o acesso desejado ser concluído, todas as tentativas de acessos não permitidas e processos ilegais estarão bloqueados. As requisições provenientes do processo compartilhado podem alterar o conteúdo da tabela de controle de acesso durante a execução. 41 Os sinalizadores do controle de acesso com as regras de sincronização determinam a funcionalidade do sistema. Restrições de sincronização limitam o tempo de acesso de processos compartilhados para recursos compartilhados. Uma sincronização apropriada assegura o correto fluxo de informação e garante a funcionalidade do sistema. A proteção é uma característica do sistema que impede os processos de permitirem o acesso arbitrário a recursos pertencentes a outros processos. Compartilhamento e proteção são incompatíveis; compartilhamento permite o acesso, enquanto que proteção a restringe. O mais simples sistema de memória compartilhada consiste de um módulo de memória que pode ser acessado por dois processadores. Requisições chegam ao módulo de memória através de suas duas portas. Uma unidade de arbitragem dentro do módulo de memória passa requisições através de um controlador de memória. Se o módulo de memória não está ocupado e um único pedido chega, então a unidade de arbitragem passa essa solicitação ao controlador de memória e o pedido é atendido. O módulo é colocado no estado ocupado enquanto o pedido está sendo atendido. Se uma nova requisição chega enquanto a memória está ocupada servindo uma requisição anterior, o processador requerente pode conter a requisição em questão até que a memória se torna livre ou pode repetir a solicitação algum tempo depois. Dependendo da rede de interconexão, um sistema de memória compartilhada leva a sistemas que podem ser classificados como: Uniform Memory Access (UMA), Nonuniform Memory Access (NUMA), e Cache-Only Memory Architecture (COMA). No sistema UMA, uma memória compartilhada é acessível por todos os processadores através de uma rede de interconexão da mesma forma que um único processador acessa a memória. Portanto, todos os processadores têm tempo igual de acesso a qualquer local de memória. A rede de interconexão utilizada em UMA pode ter barramento único, múltiplo barramento, um crossbar, ou memória multiportas. Em um sistema NUMA, cada processador tem parte da memória compartilhada anexada. A memória tem um único espaço de endereço. Portanto, qualquer processador pode acessar qualquer local de memória diretamente através do seu endereço real. No entanto, o tempo de acesso aos módulos depende da distância para o processador. Isto resulta em um tempo de acesso de memória não uniforme. Um certo número de arquiteturas são utilizados para interligar processadores aos módulos de memória em uma NUMA. Similar a NUMA, cada processador tem parte da memória compartilhada na COMA. No entanto, neste caso, a memória partilhada consiste em memória cache. Um sistema COMA exige que os dados sejam migrados para o processador que o solicitou. 42 5.2.5 Organização da Passagem de Mensagem (Message Passing) Um sistema de passagem de mensagem é uma classe de multiprocessadores, em que cada processador tem acesso à sua própria memória local. Ao contrário dos sistemas de memória compartilhada, as comunicações em um sistema de passagem de mensagem são realizadas através do envio e recebimento de operações. Um nó em sistema deste tipo é constituído por um processador e sua memória local. Os nós são tipicamente capazes de armazenar mensagens em buffers (posições de memória temporária onde as mensagens esperam até que possam ser enviadas ou recebidas), e realizar o envio/recebimento de operações ao mesmo tempo em que são processadas. Processadores não compartilham uma memória global e cada processador tem acesso ao seu próprio espaço de endereço. As unidades de processamento de um sistema de passagem de mensagens podem ser conectadas de inúmeras maneiras que variam a partir de estruturas específicas da arquitetura de interconexão à redes geograficamente dispersas. O método de passagem de mensagem é, em princípio, escalável para grandes proporções. Por escalável, entende-se que o número de processadores pode ser aumentado sem diminuição significativa da eficiência da operação. Multiprocessadores de passagem de mensagem empregam uma variedade de redes estáticas em comunicação locais. De relevância têm-se os hipercubos, que receberam atenção especial por muitos anos. O vizinho mais próximo bidimensional e redes tridimensionais de malha têm sido também usados em sistemas de passagem de mensagens. Dois fatores importantes do projeto devem ser considerados na elaboração das redes de interconexão para sistemas de passagem de mensagem. A largura da banda de ligação e a latência da rede. A ligação da banda é definida como o número de bits que podem ser transmitidos por unidade de tempo (bits/s). A latência da rede é definida como o tempo para completar a transferência de mensagens. 43 5.3 Paralelismo versus Desempenho Idealmente, um problema que leva um tempo T para ser executado em um processador simples pode ser executado no tempo T/P em P processadores. No entanto, existem várias razões pelas quais isso não ocorre. Primeiro, há a necessidade de identificar o paralelismo ao menos P vezes. Segundo, a computação paralela tipicamente introduz overhead (processamento ou armazenamento em excesso) que não está presente na computação sequencial. Terceiro, mesmo para programas paralelos bem concebidos, o desafio de atingir a meta T/P se torna mais difícil à medida que P aumenta, porque, por exemplo, a vantagem marginal de paralelismo diminui comparada aos custos de overhead. Mas, para complicar ainda mais, há certos casos em que os P processadores podem produzir menor tempo de execução do que o previsto pela estimativa T/P. Portanto, embora paralelismo e desempenho estejam relacionados, eles não são a mesma coisa. 5.3.1 Origens da perda de desempenho Enquanto nós idealmente esperaríamos que os P processadores poderiam acelerar a computação por um fator de P, há quatro razões básicas pelo qual este pode não ser o caso. Essas causas, que por vezes se sobrepõem, são: 1. Overhead, que não ocorre na computação sequencial; 2. Computação não paralelizável; 3. Processadores ociosos; 4. Contenção de recursos. Todas as outras origens são decorrentes destas quatro. 5.3.1.1 Overhead Qualquer custo que ocorre na solução paralela e não ocorre na solução em série é considerado overhead. Há overhead na inicialização e finalização de threads e processos na execução concorrente. Devido sua alocação de memória e inicialização mais dispendiosas, os processos acarretam um overhead de inicialização maior do que threads. Após o primeiro processo ser inicializado, todos os threads e processos subsequentes inicializados incorrerão em overhead, o que não está presente na computação sequencial. Estes custos representam os overheads do paralelismo. 44 Em geral, reconhecemos quatro fontes de overhead em paralelo. Comunicação A comunicação entre threads e processos é a maior componente de Overhead. Uma vez que na computação sequencial não ocorre comunicação com outro processador, toda comunicação é uma forma de overhead. Sincronização A sincronização é uma forma de overhead que surge quando um thread ou processo deve esperar por um evento em outro thread ou processo. Computação Computações paralelas quase sempre realizam cálculos extras que não são necessários na solução sequencial. Memória Computações paralelas frequentemente incorrem em overhead de memória. Enquanto overhead nem sempre prejudica o desempenho ele pode ser significativo para computações paralelas cujo tamanho é limitado por restrições de memória. 5.3.1.2 Códigos não paralelizáveis Se a computação é inerentemente sequencial - ou seja, não pode ser paralelizável – o uso de mais processadores não melhorará o seu desempenho. A existência de computação não paralelizável é importante porque limita os potenciais benefícios da paralelização. A lei de Amdahl considera que se 1/S de um cálculo é inerentemente sequencial, então o ganho de desempenho máximo é limitado por um fator S. O raciocínio é que o tempo de execução, Tp, de uma computação paralela será a soma do tempo de sua componente sequencial e sua componente paralelizável. Se o cálculo leva em tempo TS para executar sequencialmente, então para P processadores teremos: 𝑇𝑃 = 1 𝑆 × 𝑇𝑆 + (1 − 1 𝑠 ) × 𝑇𝑆 𝑃 (5.1) 45 Imagine um valor de P tão grande que a parte paralelizável leva um tempo insignificante, a melhoria de desempenho máximo é um fator de S. Isto é, a proporção sequencialmente executada em um código de computação determina o seu potencial para a melhoria usando paralelismo. A situação é, na verdade, um pouco pior do que implica a lei de Amdahl. Um problema evidente é que a parte paralelizável da computação pode não ser melhorada para uma extensão ilimitada - ou seja, provavelmente há um limite máximo para o número de processadores que podem ser utilizados utilmente e ainda melhorar o desempenho – assim é improvável o tempo de execução paralela desaparecer. 5.3.1.3 Contenção Contenção é a degradação do desempenho de um sistema causada pela competição por um recurso compartilhado. Poderíamos considerar contenção um caso especial de overhead, mas contenção merece atenção especial, pois seus efeitos podem muitas vezes levar a desaceleração, ou seja, pior desempenho do que teríamos com um único processador. 5.3.1.4 Tempo ocioso Idealmente, todos os processadores estão funcionando todo o tempo, mas isto pode não ser o caso. Um processo ou thread pode não ser capaz de continuar, devido à falta de trabalho porque ele está à espera de algum evento externo como, por exemplo, a chegada de dados de algum outro processo. Assim, o tempo ocioso é muitas vezes consequência de sincronização e comunicação. 5.4 Dependência A dependência é uma relação de ordem entre duas computações. Dependências podem surgir de diferentes maneiras em diferentes contextos. Por exemplo, a dependência pode ocorrer entre dois processos, quando um processo espera chegar uma mensagem a partir de outro processo. Dependência também pode ser definida em termos de leitura e gravação de operações, o que para computações alinhadas correspondem a carregar e armazenar na memória. A dependência de dados é uma ordenação em um par de operações de memória que deve ser preservada de modo a manter a exatidão. Existem três tipos de dependências de dados: • Dependência de fluxo: ler após escrever; • Anti-dependência: escrever após ler; 46 • Dependência de saída: escrever após escrever. Dependências de fluxo também são chamadas de dependências verdadeiras porque representam ordenamentos fundamentais do funcionamento de operações de memória. Por outro lado, anti-dependências e dependências de saída são referidas como dependências falsas porque surgem a partir da reutilização de memória, em vez de partir de uma ordenação fundamental das operações, embora elas possam ser chamadas de "falsas", elas ainda são importantes para nós, porque muitas vezes desejamos reutilizar a memória. 5.5 Granularidade A granularidade do paralelismo é determinada pela frequência de iterações entre threads ou processos, ou seja, a frequência com que dependências cruzam limites de thread ou processos. Aqui, a frequência é medida pelo número de instruções entre interações. Assim, granulometria grossa se refere a threads e processos que só raramente dependem de dados ou eventos em outros segmentos ou processos, enquanto computação de granulometria fina são aquelas que interagem com frequência. 5.6 Speedup Speedup é definido como o tempo de execução de um programa sequencial dividido pelo tempo de execução de um programa em paralelo que calculam o mesmo resultado. Em particular, Speedup = TS/TP, onde TS é o tempo sequencial e TP é o tempo paralelo de execução em P processadores. Um fenômeno curioso que algumas vezes ocorre quando um programa paralelo é executado é um speedup maior que P quando P processadores são utilizados, obtendo-se o que é conhecido como speedup superlinear. 5.7 Eficiência A eficiência é uma medida normalizada do speedup, que indica a eficácia de cada processador usado: Eficiência = Speedup/P. Uma eficiência ideal de 1 indica speedup linear e que todos os processadores são usados em plena capacidade. Devido a fontes de perda de desempenho, a eficiência é tipicamente menor do que 1 e diminui à medida que o número de processadores aumenta. A eficiência é maior do que 1 no caso de speedup superlinear. 47 5.8 Dimensionando o tamanho do problema Ignorando restrições de memória e assumindo speedup perfeito, consideraremos como o paralelismo afeta o tamanho do problema. Para um algoritmo sequencial cujo o tempo de execução é O(nx), nós temos T = cnx. Se nós assumimos que P processadores pode melhorar o tamanho do problema por um fator de m, então para o mesmo tempo de execução, T, nós temos 𝑇 = 𝑐(𝑚𝑛)𝑥 𝑃 = 𝑐𝑛𝑥 (5.2) Resolvendo para m têm-se (mn)x = Pnx mxnx = Pnx m = P(1/x) Assim, para aumentar o tamanho do problema por um fator de 100 para um problema cuja complexidade assintótica é O(n4), nós precisamos de 100.000.000 processadores. Por contraste, para aumentar por um fator de 100 um problema cuja complexidade assintótica é O(n2), nós precisamos de 10.000 processadores; se a complexidade é linear somente 100 processadores são necessários. 5.9 Considerações Neste capítulo foram apresentados os conceitos básicos em computação paralela, as principais arquiteturas utilizadas em computação e as origens para perda de desempenho na computação paralela. 48 Capítulo 6 Aplicação da aprendizagem por reforço ao PKS Neste Capítulo será mostrado como foi feita a modelagem de um problema de otimização em espaço métrico específico, o problema dos K-Servos (PKS). O objetivo é apresentar uma solução baseada na aprendizagem por reforço hierárquica processada de forma paralela para solução de problemas de otimização em espaços métricos, superando o inconveniente do dimensionamento e permitindo sua aplicação a situações complexas. O método a seguir apresentado é de propósito geral, podendo ser aplicado desde problemas de gerenciamento de sondas de produção terrestre e de logística na produção de petróleo offshore, a problemas de otimização variados. Constituindo-se assim, uma das principais contribuições deste trabalho. 6.1 Considerações iniciais Os algoritmos de aprendizagem por reforço hierárquica apresentados anteriormente são de âmbito geral, ou seja, não se restringem a uma aplicação específica. Desde que seja possível a modelagem do problema segundo a estrutura dos algoritmos, eles podem ser utilizados. Do mesmo modo que estes algoritmos, a solução proposta nesta seção também visa ser uma solução de âmbito geral, não sendo sua utilização limitada a um problema particular. Para mostrar isto, será analisada a adequação desta solução para problemas de otimização em espaços métricos (MTS). Como explicado em seções anteriores, o MTS serve como abstração para diversos problemas. Entretanto, para verificar o desempenho da solução será analisada a utilização da aprendizagem por reforço em um problema específico de MTS, o problema dos K-Servos – PKS (Manasse et al. 1988). Sem maiores dificuldades teóricas, a solução poderia ser aplicada a quaisquer problemas de otimização em espaços métricos, sendo opção do autor a escolha do PKS. Se um desempenho satisfatório for obtido para o PKS possivelmente será obtido para os demais problemas de MTS. Na modelagem formal do problema dos K-Servos apresentada anteriormente, os servos podiam estar localizados em quaisquer nós, não necessariamente distintos. Neste trabalho, será considerado que os servos estarão localizados em nós necessariamente distintos, não sendo 49 permitido que dois ou mais servos ocupem o mesmo nó em um mesmo instante de tempo. A restrição de dois ou mais servos ocuparem um mesmo nó no mesmo instante de tempo não significa uma limitação da abordagem da aprendizagem por reforço, sendo considerada somente para a simplificação na manipulação e geração dos estados apresentados. A razão para esta restrição não ser uma limitação da aprendizagem por reforço é simples, como os servos são homogêneos, se dois ou mais deles ocupam um único nó no mesmo instante de tempo, qualquer um deles pode ser deslocado para atender à solicitação. Assim, em termos de escolha de qual servo será deslocado, já que tanto faz deslocar um servo ou outro, pode-se considerar que somente um único servo ocupa este nó neste instante de tempo. Considere um problema com k servos, onde os mesmos podem ocupar mais de um nó ao mesmo tempo (modelo clássico), e seja k’ (k’ ≥ 0) o número de nós ocupados por mais de um servo. Se k’ > 0, o número de servos que podem ser deslocados é igual a k−k’, dado que se mais de um servo ocupa o mesmo nó considera-se que existe somente um único servo neste nó. Se k’ = 0 (nenhum nó está ocupado por mais de um servo), o número de servos que pode ser deslocado é igual a k (o modelo formal e o considerado se tornam equivalentes). Ora, se o modelo para o PKS considerado neste trabalho (onde dois ou mais servos não podem ocupar um mesmo nó no mesmo instante de tempo) possui as mesmas características do formal, e é capaz de solucionar o PKS para k servos, também será capaz de resolvê-lo para k−k’ (k’ ≥ 0) servos. Em outras palavras, a solução usando o modelo considerado engloba a formal. Portanto, a modelagem pode ser estendida, sem dificuldades teóricas, para casos onde diversos servos ocupem o mesmo nó em um dado instante de tempo. 6.2 Modelagem para problemas de menor porte Do ponto de vista da aprendizagem por reforço, o problema pode ser modelado como segue: o estado do ambiente é representado por uma configuração possível dos k servos, ou seja, por k-tuplos do tipo s={no1,no2, . . . ,nok}, onde noi representa o índice do nó em que o servo está localizado. O número total de estados possíveis é dado pela expressão: 𝐶𝑛,𝑘 = 𝑛! 𝑘!(𝑛−𝑘)! (6.1) As ações correspondem aos movimentos permitidos dos servos em um estado válido. Cada ação representa o movimento de um servo de um nó i para um nó j, no intuito de atender a requisição σj. Neste trabalho, só será considerado o atendimento de uma requisição por vez, deixando a análise de múltiplos servos para trabalhos futuros. Em cada estado, e considerando 50 o surgimento de uma demanda σj em um dos n nós em G, um dos k servos será deslocado. Deste modo, o número de ações permitidas na ocasião é igual a k, todas do tipo mover servo localizado no nó i para o nó j, de forma a atender a solicitação σj. Como n demandas podem surgir por estado, o número total de ações possíveis é igual a k · n. A distinção deve ser notada entre os conceitos de ações permitidas e possíveis. Ações permitidas são as k ações que podem ser tomadas quando do surgimento de uma dada requisição, ocasionando o deslocamento de um dos k servos para atender a mesma. Ações possíveis são todas as ações que podem ser tomadas quando ainda não se conhece o nó onde irá surgir a próxima requisição, podendo a mesma, portanto, surgir em qualquer um dos n nós que compõem o grafo G. Consequentemente, qualquer um dos k servos pode ser deslocado para atender uma demanda (que pode surgir em qualquer um dos n nós de G), totalizando k · n ações possíveis. O sinal de reforço corresponde à distância percorrida pelo servo ki localizado no nó i para atender à demanda σj localizada no nó j, representado por d(ki, σj). Pelo exposto, infere-se que para armazenar os valores da função de valor estado-ação Q, uma estrutura de dimensão Cn,k·k·n, onde Cn,k, definido em (6.1), representa o total de estados válidos, e k·n o total de ações possíveis por estado. Logo, a complexidade em espaço do algoritmo é O(k · nk+1). Na solução da equação do Q-Learning, uma questão importante diz respeito ao cálculo do termo maxa’ Q(s’,a’). No caso geral, esse cálculo pode ser visualizado através de um diagrama de backup mostrado na Figura (6.1). Na Figura (6.1), os estados estão representados por quadriláteros. As ações estão representadas por círculos e por um triângulo (ação a). Uma vez conhecidos s e a, tem-se o estado s’. O valor do termo maxa’ Q(s’,a’) é então tomado entre os valores de Q(s’,a’) de todas as k · n ações possíveis de serem tomadas a partir de s’ (estas ações são representadas na figura pelos círculos preenchidos com preto). Observe-se que não existe a necessidade de se conhecer qual a ação que será tomada em s’, mas sim quais são todas as ações possíveis de serem tomadas. Figura (6.1): Diagrama de backup do algoritmo Q-Learning. 51 Para problemas de menor porte, a solução do PKS utilizando a aprendizagem por reforço pode ser obtida através do uso do Q-Learning (Júnior et al. 2005a), utilizando-se as definições de estado, ação e reforço apresentadas nesta seção. Observa-se que o aprendizado pode ser realizado satisfatoriamente, já que a estrutura de armazenamento da função Q é viável para ser processada computacionalmente. 6.3 Modelagem para problemas de maior porte Para se poder utilizar a aprendizagem por reforço em aplicações que envolvam um conjunto mais significativo de estados e ações, devido a maldição da dimensionalidade inerente ao método da aprendizagem por reforço, fez-se necessário a criação de uma solução baseada em técnicas de decomposição hierárquica, apresentadas no Capítulo 4, no algoritmo Q- Learning e em técnicas de computação paralela. A ideia geral é aplicar o Q-Learning a um número reduzido de nós (selecionados seguindo um critério específico) do conjunto de nós do problema e generalizar o aprendizado obtido neste treinamento para outros pares estado-ação não visitados. Quando a generalização não for possível, utiliza-se o critério ε-guloso para selecionar o servo a ser deslocado. A descrição do método hierárquico é a seguinte: • Divida o conjunto de nós em grupamentos de proximidade; • Para cada grupamento formado o Escolha um nó para representar o grupo – nó-centro; o Execute o Q-Learning no conjunto de nós que compõem o grupo; • Execute o Q-Learning nos nós escolhidos no passo anterior – nós-centro; • Se o par estado-ação não foi visitado no passo anterior e a generalização não puder ser feita, utilize o critério ε-guloso para escolher o servo a ser deslocado. De posse do conjunto de grupamentos formados, o próximo passo é selecionar os nós que irão representar cada um destes grupos. Denominou-se os nós selecionados de nós-centro. O critério de escolha destes nós é a média da sua distância em relação aos demais nós que compõem seu grupo. Em outras palavras, o nó selecionado será aquele que possuir, em média, a menor distância em relação a todos os outros nós que compõem seu grupo. Nos primeiros passos do algoritmo hierárquico, o conjunto de n nós do problema foi dividido em x grupamentos de proximidade, e para cada grupamento um nó-centro foi 52 selecionado, totalizando x nós-centro. Cada um destes x grupamentos contém um determinado número de nós, de tal forma que o somatório dos nós que compõem os x grupos é igual a n. A aprendizagem por reforço clássica, que usa o Q-Learning, será aplicada no conjunto de x nós-centro e em cada conjunto dos nós que compõem os x grupamentos, mantendo-se constante o total de k servos. A execução da aprendizagem por reforço, neste conjunto reduzido de nós, mantém as mesmas características da execução no conjunto de n nós do problema. Porém, deve-se observar que os servos e os possíveis locais de demanda estarão localizados somente nos nós selecionados para cada execução. Assim, durante a execução da aprendizagem por reforço no conjunto de x nós-centro, os servos só poderão se deslocar e demandas só poderão surgir nestes nós. Do mesmo modo, durante a execução em um dos x grupamentos de proximidade, os servos e as demandas só estarão localizados nos nós que compõem o grupo. No caso do método de aprendizagem por reforço hierárquica paralelizada, a aprendizagem usando o Q-Learning será executada de forma concorrente no conjunto de x nós- centro e em cada conjunto dos nós que compõem os x grupamentos, mantendo-se constante o total de k servos. Como critério para definir o número de agrupamentos, levou-se em consideração o tamanho do problema e a quantidade de processadores disponíveis. O parâmetro de equilíbrio de carga (τ) possibilita a homogeneidade nos tamanhos dos agrupamentos e o esforço computacional dos processadores. Segundo Ribeiro (1998), garantidos os critérios de convergência do algoritmo Q-Learning e certas condições da função de espalhamento forem satisfeitas, a política convergirá para o ótimo. Desta forma, o algoritmo proposto atende aos critérios de convergência do algoritmo Q-Learning e a abordagem paralela permite tratar problemas complexos de alta dimensão. O algoritmo do método hierárquico paralelo é exposto a seguir: 53 Algoritmo 6.1: Método Hierárquico Paralelo. Encontre x grupamentos utilizando o algoritmo k-means tal que (x_max ≤ τ × x_min); Para cada grupamento x formado (seção paralela) Selecione o nó que será o centro do grupamento em questão; Execute o Q-Learning no conjunto de nós que compõem o grupo; Fim Execute o Q-Learning nos x nós-centro selecionados e com k servos e encontre a política π; Para cada requisição σi Se o par estado-ação foi visitado pelo Q-Learning O servo a ser deslocado será determinado pela política π; Se Se o grupamento da demanda for o mesmo que o de um ou mais servos Selecione os servos que pertencem ao mesmo grupo da demanda; Dentre os servos selecionados, desloque o que estiver mais próximo à demanda; Senão Se o grupamento da demanda for diferente do grupamento dos k servos Se os k servos pertencem ao mesmo grupamento Desloque o servo que estiver mais próximo à demanda; Senão Se os k servos pertencem a grupamentos distintos Considere que cada servo e a demanda estão localizados nos centros dos seus grupamentos; O servo a ser deslocado será determinado pela política π; Senão O servo a ser deslocado será o que estiver mais próximo à demanda; Fim do algoritmo 54 EXEMPLO Os passos do algoritmo poderão ser melhores visualizados com a compreensão do seguinte exemplo. Considere um problema, que será denominado de original, com 10 nós e 2 servos (Figura 6.2). Serão desconsideradas as conexões entre os nós do grafo. Figura 6.3: Problema com 10 nós e 2 servos. O primeiro passo do algoritmo é a divisão do conjunto de nós em grupos utilizando o algoritmo k-means. Em seguida, um nó de cada grupo, segundo critério já apresentado, é selecionado para ser o nó-centro. A visualização do conjunto de nós após os primeiros passos do algoritmo se encontra na Figura 6.4. Agora, tem-se 10 nós, divididos em 3 grupos, com cada grupo tendo o seu nó-centro. Figura 6.4: Problema após a divisão em grupos e seleção dos nós-centro. A aprendizagem por reforço, mantendo-se constante o número de servos (que é igual a 2), será executada: • No conjunto dos 3 nós-centro selecionados; • Em cada um dos 3 conjuntos de nós que compõem os grupamentos formados. A política π correspondente aos pares estado-ação visitados será obtida. Os deslocamentos dos servos e os locais de demanda só ocorrerão: • Quando o Q-Learning for executado nos 3 nós-centro selecionados: os deslocamentos e o surgimento de demandas só ocorrerão em pontos situados nestes nós-centro; • Quando for executado dentro de cada um dos 3 grupamentos formados: os deslocamentos e o surgimento de demandas só ocorrerão em pontos situados nos nós que compõem cada grupamento. 55 A dimensão da estrutura de armazenamentos da função Q do problema original, para 10 nós e 2 servos, é dada pela expressão C10,2 · 10 · 2 = 45 · 10 · 2 = 900. Após a divisão em grupos, a dimensão do problema será dada pelo somatório da dimensão da estrutura decorrente da execução nos nós-centro e dentro de cada um dos grupos. Portanto, é só verificar a quantidade de nós-centro e de nós contidos em cada grupo, e em seguida realizar os cálculos necessários para cada um deles, mantendo-se constante o número de servos, que é 2. No final, tem-se que a dimensão da estrutura será dada pelo somatório dos valores obtidos: • Nós-centro: C3,2 · 3 · 2 = 3 · 3 · 2 = 18; • Grupo A: C3,2 · 3 · 2 = 3 · 3 · 2 = 18; • Grupo B: C4,2 · 4 · 2 = 6 · 4 · 2 = 48; • Grupo C: C3,2 · 3 · 2 = 3 · 3 · 2 = 18. Desta maneira, a dimensão do problema com um número inferior de nós é igual a 18+18+48+18 = 102, sendo este número bem inferior ao do problema original, cuja dimensão obtida foi 900. Deve-se observar que nem todos os pares estado-ação do problema original foram visitados com a utilização da abordagem hierárquica. Quando este par não tiver sido visitado, duas soluções podem ser utilizadas: a generalização do aprendizado ou o método guloso. Quando os servos e as demandas pertencerem a grupos distintos, todos eles, e os mesmos não estiverem nos nós-centrais dos seus respectivos grupos, serão considerados como se estivessem. A partir desta suposição, utiliza-se o conhecimento obtido durante a execução da aprendizagem por reforço e se escolhe o servo a ser deslocado. Esta transposição da posição dos servos ou da requisição faz com que o aprendizado feito na execução da aprendizagem por reforço possa ser utilizado em pares estado-ação que não foram visitados, generalizando para outros estados o conhecimento obtido durante o aprendizado. Esta técnica é denominada de generalização espacial do conhecimento. Quando o par estado-ação não foi visitado pela aprendizagem por reforço e a generalização do conhecimento não puder ser feita, o critério para o deslocamento dos servos será o guloso, ou seja, o servo a ser deslocado será o que estiver mais próximo à demanda. Considere cinco exemplos de possíveis localizações de servos e surgimento de requisições por serviço, considerando o problema original, e a correspondente solução ao se seguir os passos do algoritmo hierárquico: 1. Os 2 servos estão localizados em nós-centro distintos e surge uma demanda em um outro nó-centro: como o par estado-ação já foi apresentado durante a fase de execução do Q- 56 Learning nos nós-centro, o servo deslocado será aquele que possuir o maior valor da política π para o respectivo par estado-ação. Figura 6.5: Exemplo com os 2 servos localizados em nós-centro distintos e uma demanda em um outro nó-centro. 2. Os 2 servos estão localizados em nós-centro distintos e surge uma demanda em um local, que não é nó-centro, num grupo distinto ao dos servos: o algoritmo considerará que a demanda está inserida no nó-central de seu grupo correspondente (ver Figura 6.5), utilizando portanto a técnica da generalização. Com isso, este par estado-ação com a demanda transposta ao nó-centro já foi visitado durante a execução do Q-Learning nos nós-centro, implicando a seleção do servo que apresentar o maior valor para a política π correspondente a este par estado-ação. Obviamente, no cômputo da distância percorrida pelo servo será considerado o deslocamento do mesmo até o local original da demanda, e não ao nó-centro considerado. Figura 6.6: Exemplo com os 2 servos localizados em nós-centro distintos e com a demanda em um nó, que não é nó-centro, num grupo distinto ao dos servos. 3. Os 2 servos estão localizados em grupos distintos e surge uma demanda num nó que pertence ao grupo de um deles: o servo a ser deslocado será aquele que pertencer ao grupo da demanda. Se por acaso fossem 3 servos, e 2 deles pertencessem ao grupo da demanda e 1 não, o deslocado seria aquele que pertencesse ao grupo da demanda e que estivesse mais próximo a mesma (critério guloso), já que esta situação não foi treinada durante o aprendizado e a generalização não pode ser feita. Figura 6.7: Exemplo com os 2 servos localizados em grupos distintos e uma demanda num nó que pertence ao grupo de um deles. 57 4. Os 2 servos e a demanda estão localizados em um mesmo grupo: o servo selecionado será aquele que apresentar o maior valor para a política π correspondente ao par estado- ação, pois esta situação foi treinada durante a execução do Q-Learning dentro de um dos grupamentos (será considerado que o treinamento correspondente à descrição foi feito dentro do grupo A). Figura 6.8: Exemplo com os 2 servos e a demanda localizados em um mesmo grupo. Os 2 servos estão em grupos distintos, um deles está num nó-centro e o outro não, e surge uma demanda em um nó que não é centro e que pertence a um grupo que é distinto ao dos 2 servos: tanto o servo quanto a demanda serão considerados como se estivessem localizados no nó-central do seu grupo (ver Figura 6.8). Este estado transposto já foi visitado durante a execução do Q-Learning nos nós-centro e o servo escolhido será o que apresentar o maior valor para a política π correspondente. Mais uma vez, os deslocamentos serão calculados segundo as posições originais dos servos e da demanda. Figura 6.9: Exemplo com 2 servos localizados em grupos distintos, um deles está num nó-centro e o outro não, e surge uma demanda em um nó que não é centro e que pertence a um grupo que é distinto ao dos 2 servos. 6.4 Considerações A finalidade deste capítulo foi mostrar como foi feito a aplicação da aprendizagem por reforço hierárquica em um problema de otimização em espaço métrico específico, o problema dos K-Servos (PKS). Objetivou-se, neste capítulo, apresentar o modo como foi modelado computacionalmente a solução para o problema em questão, ficando a análise da solução proposta para o capítulo seguinte. 58 Capítulo 7 Análise da solução proposta O objetivo deste Capítulo é fazer a comparação entre a teoria sobre aprendizagem por reforço hierárquica apresentada anteriormente e a solução proposta neste trabalho, correlacionando as técnicas formais encontradas na literatura, que garantem a convergência para o ótimo, com as que estão sendo propostas neste texto. Demonstrou-se que a solução é plausível, e que seus resultados empíricos indicam características de otimalidade. O trabalho desenvolvido objetivou construir uma solução capaz de resolver problemas de otimização em espaços métricos mais complexos em um tempo computacionalmente viável, mesmo que para isso se perca um pouco a qualidade da solução. O uso do método ε-guloso na solução proposta é uma excelente estratégia para a obtenção de soluções satisfatórias em um tempo viável. Trata-se de um método que fornece respostas instantâneas, não necessita de estrutura de armazenamento para fornecer essas respostas e consegue obter, dadas as condições de otimalidade do método7, a convergência para o ótimo em problemas com espaços euclidianos. Analisou-se a complexidade em espaço da solução hierárquica, comparando esta complexidade com a do Q-Learning na solução de MTS. 7 Existem dois elementos que indicam que a estratégia gulosa pode ser utilizada com sucesso: • Propriedade de escolha gulosa: uma solução ótima global pode ser obtida a partir de escolhas locais ótimas. • Subestrutura ótima: se uma solução ótima contém dentro dela soluções ótimas para os subproblemas. 59 7.1 Análise de desempenho dos algoritmos propostos A solução proposta neste trabalho realiza decomposição hierárquica, transformando problemas mais complexos em subproblemas, ao dividir o conjunto de nós em grupos (cada um com seu respectivo nó-centro), e executando a aprendizagem por reforço clássica separadamente em cada um destes grupos. A divisão do conjunto de nós em grupos reduz o número de pares estado-ação processados em cada etapa do algoritmo, o que aumenta a eficiência do processo de aprendizagem, sendo esta uma característica fundamental da teoria da decomposição hierárquica. Como o cálculo da matriz Q para cada grupo e para os nós centrais é feito de forma independente, ou seja, não é necessário aguardar o resultado do cálculo da matriz Q de um grupo para começar o de outra. Podemos realizar o cômputo dessas matrizes de forma paralela e assim diminuir o tempo total gasto no processo. Com o processo de aprendizagem por reforço hierárquico agregado às técnicas de computação paralela, esperamos aplicar o método em problemas práticos de grande porte. Deve-se ressaltar que Ribeiro (Ribeiro, 1998) prova que se as garantias de convergência do Q-Learning e certas condições de espalhamento forem satisfeitas, a política converge para o ótimo. Isto indica que a técnica de divisão em grupos e a do espalhamento do aprendizado a partir de um nó-central propostos podem convergir para o ótimo, já que as garantias de convergência do Q-Learning foram satisfeitas nesta solução. Da mesma forma, o número de pares estado-ação a serem armazenados também foi reduzido com a utilização do método ε-guloso, já que quando o mesmo é utilizado o par estado- ação correspondente não necessita ser armazenado. No que se refere ao princípio da abstração temporal, neste trabalho, considerou-se como comportamento a execução do Q-Learning nos nós-centros e dentro de cada grupamento. Pode- se fazer uma analogia com o apresentado anteriormente sobre comportamentos, onde a função principal seria “realizar o aprendizado” e cada sub-rotina (os comportamentos) seria a execução do Q-Learning dentro de cada conjunto de nós, ou seja, o aprendizado nestes conjuntos. Desta maneira, o problema global pode ser considerado como um PDSM. Entretanto, a execução de cada comportamento obedece as mesmas características da aprendizagem por reforço clássica, ou seja, é baseada no modelo PDM. A estrutura da solução proposta segue idêntica à apresentada na literatura, indicando, mais uma vez, que esta solução pode possuir características de otimalidade. 60 7.2 Complexidade da solução A redução da dimensão da estrutura usada pela aprendizagem por reforço hierárquica para armazenar os valores da função Q ocorrerá proporcionalmente a um fator de redução δ, sendo este valor variável de acordo com a decomposição hierárquica utilizada em cada problema. Matematicamente, 𝐶𝑛 𝛿 ,𝑘. 𝑘. 𝑛 𝛿 , onde: 𝐶𝑛 𝛿 ,𝑘 = ( 𝑛 𝛿 !) 𝑘!( 𝑛 𝛿 −𝑘!) (7.1) De posse destas informações e fazendo-se as manipulações necessárias, obter-se-á 𝑂 = 1 (𝛿)𝑘 . 𝑛𝑘 como complexidade em espaço da aprendizagem por reforço hierárquica. A redução da complexidade em relação à aprendizagem por reforço clássica é da ordem de 1 (𝛿)𝑘 . 7.3 Análise comparativa – Q-Learning, Hierárquico paralelizado e Guloso. Um comparativo entre os algoritmos Q-learning, Harmonic e Work function modelados para o problema dos K-Servos foi abordado por Júnior et al. (2005a), verificando-se um melhor desempenho do Q-learning em relação aos demais algoritmos supra citados para pequenas instâncias. Neste trabalho busca-se verificar o desempenho da solução baseada na aprendizagem por reforço hierárquica em comparação com os algoritmos Q-learning e guloso, visando mostrar a aplicabilidade do método a problemas de maiores dimensões. Para isso, fez- se uma aplicação específica da aprendizagem por reforço em MTS, o problema dos K-Servos. O uso de técnicas de computação paralela visa tão somente a diminuição do tempo gasto na execução do algoritmo, viabilizando seu uso a problemas de grande dimensão. Deve-se ter em mente que o presente estudo pode ser generalizado sem maiores restrições para outros problemas de otimização em espaços métricos (Borodin; El-Yaniv, 1998). Para efetuar o comparativo, testes foram realizados no intuito de observar o desempenho da aprendizagem por reforço hierárquica paralelizada em comparação com os algoritmos Q- learning e guloso. Será apresentado aqui os resultados do comparativo para 60, 90, 120 e 150 nós. Devido ao esforço computacional e o tempo necessário ao treinamento do algoritmo Q- Learning limitou-se o número de nós. No entanto, pode-se facilmente perceber a partir dos resultados apresentados que a abordagem utilizando aprendizagem por reforço hierárquica pode, sem maiores restrições, abordar problemas de alta dimensão. 61 No treinamento dos agrupamento e nós centrais foram geradas sequências de n demandas aleatórias σ = {σ1, σ2, · · · , σn}. Como o Q-learning converge para a solução ótima quando cada par estado-ação for visitado “infinitas” vezes, o valor atribuído a n foi convenientemente grande. Sabe-se que a dimensão da estrutura de armazenamento da função Q necessária para se obter a política ótima Q* cresce exponencialmente em função do número de estados e de ações (maldição da dimensionalidade). A função de valor estado-ação Q converge para a função de valor estado-ação ótima Q*, à medida que os pares estado-ação são visitados e o seu valor é atualizado. Para problemas de maior dimensão não se teria como garantir na prática que todos os estados sejam visitados. Afetando desta forma os pressupostos que garantem a otimalidade do algoritmo Q-Learning. Ao dividir o grafo se consegue melhorar as visitas aos pares estado-ação nos nós centrais e dentro dos agrupamentos. Nesta fase, para melhorar o equilíbrio de carga entre os processadores, utilizou-se na divisão dos agrupamentos pelo k-means um parâmetro de equilíbrio de carga (τ) como critério de divisão dos tamanhos de cada grupo. Assim, a diferença entre o menor e o maior agrupamento não poderia ser maior do que esse parâmetro. Por exemplo, para (τ) igual a 1,5 significa que o maior agrupamento (𝑥𝑚𝑎𝑥) só poderia ser 1,5 vezes maior do que o menor agrupamento (𝑥𝑚𝑖𝑛), (𝑥𝑚𝑎𝑥 ≤ 1,5 × 𝑥𝑚𝑖𝑛). Desta forma a carga de trabalho seria melhor distribuída entre os processadores, diminuindo o tempo ocioso destes. Para comparação entre os métodos foram gerados grafos aleatórios e feitas 100 comparações onde para cada uma destas foi fornecida uma sequência aleatória de 500 solicitações por demandas e em seguida anotado o total de vitórias obtidas por cada método. No caso de empate entre os métodos foi atribuído a pontuação a ambos. Registrou-se o tempo (em segundos), a distância média, o desvio-padrão, o maior e o menor caminho percorrido pelos servos. No caso do Q-learning hierárquico paralelizado adota- se o seguinte critério de convergência: foi calculada a diferença da média da matriz Q a cada 500 episódios de treinamento, quando esta diferença atingir um determinado limiar (ex.: 10-4) a execução é interrompida. Com isso se conseguiu diminuir o número de episódios de treinamento do algoritmo Q- learning, minimizando o esforço computacional e avaliando a convergência do método em cada agrupamento e nós centrais. Na execução do método foram utilizados na aprendizagem por reforço os parâmetros α = 0.85 (taxa de aprendizagem), γ = 0.9 (fator de desconto); no método ε-guloso ε = 0.15 (parâmetro de aleatoriedade). Os códigos forma elaborados em Matlab® e os testes executados em uma CPU equipada com 2 processadores Intel I7 980 contendo 6 núcleos cada (2 threads por núcleo), memória RAM de 16 GB DDR3, 1600 mhz e sistema operacional Ubuntu. 62 Os resultados experimentais para cada tamanho de grafo são mostrados a seguir. O valor do parâmetro de equilíbrio de carga (τ) foi ajustado empiricamente pelo pesquisador. Se dividiu os agrupamentos originais em 6 subgrupos de forma a otimizar o uso dos recursos computacionais disponíveis, já que se dispunha de um computador com seis núcleos. Tabela 7.1: Resultados experimentais da comparação entre o algoritmo Q-learning, aprendizagem por reforço hierárquica paralelizada e guloso. 60 nós, 2 servos e 6 grupamentos Q-learning Q-learning Hierárquico Paralelo Guloso Tempo (s) 1888,00 234,74 * Distância Média 12849,60 11881,53 12913,56 Desvio padrão 253,70 263,78 241,32 Maior caminho 13391,00 12468,00 13613,00 Menor caminho 12151,00 11195,00 12196,00 Vitórias 0 100 0 * O método guloso não necessita de treinamento. Para uma configuração com 60 nós e 2 servos o algoritmo Q-learning necessita de uma estrutura de armazenamento com 212.400 pares estado-ação, sendo que com o método hierárquico com 6 agrupamentos (τ = 2,2) de tamanhos 13, 10, 11, 10, 10, 6 esse número é reduzido para 6.118 pares estado-ação. 63 Tabela 7.2: Resultados experimentais da comparação entre o algoritmo Q-learning, aprendizagem por reforço hierárquica paralelizada e guloso. 90 nós, 2 servos e 6 grupamentos Q-learning Q-learning Hierárquico Paralelo Guloso Tempo (s) 4786,00 897,39 * Distância Média 14921,60 13573,48 13995,01 Desvio padrão 239,76 245,21 270,02 Maior caminho 15617,00 14219,00 14904,00 Menor caminho 14338,00 12974,00 13251,00 Vitórias 0 99 1 * O método guloso não necessita de treinamento. Para uma configuração com 90 nós e 2 servos o algoritmo Q-learning necessita de uma estrutura de armazenamento com 720.900 pares estado-ação, sendo que com o método hierárquico com 6 grupamentos (τ = 1,7) de tamanhos 13, 19, 18, 13, 11, 16 esse número é reduzido para 21.112 pares estado-ação. Tabela 7.3: Resultados experimentais da comparação entre o algoritmo Q-learning, aprendizagem por reforço hierárquica paralelizada e guloso. 120 nós, 2 servos e 6 grupamentos Q-learning Q-learning Hierárquico Paralelo Guloso Tempo (s) 8038,00 1143,38 * Distância Média 15076,79 13790,30 13962,06 Desvio padrão 233,69 223,03 237,07 Maior caminho 15664,00 14506,00 14511,00 Menor caminho 14435,00 13219,00 13283,00 Vitórias 0 89 11 * O método guloso não necessita de treinamento. 64 Para uma configuração com 120 nós e 2 servos o algoritmo Q-learning necessita de uma estrutura de armazenamento com 1.713.600 pares estado-ação, sendo que com o método hierárquico com 6 grupamentos (τ = 1,9) de tamanhos 16, 22, 21, 23, 23, 15 esse número é reduzido para 49.250 pares estado-ação. Tabela 7.4: Resultados experimentais da comparação entre o algoritmo Q-learning, aprendizagem por reforço hierárquica paralelizada e guloso. 150 nós, 2 servos Q-learning Q-learning Hierárquico Paralelo Guloso Tempo (s) 10533,00 2946,68 * Distância Média 15562,18 14263,73 14363,54 Desvio padrão 209,80 199,13 195,81 Maior caminho 16169,00 14791,00 14863,00 Menor caminho 15062,00 13850,00 13980,00 Vitórias 0 72 28 * O método guloso não necessita de treinamento. Tabela 7.5: Comparativo entre o tempo total de execução sequencial e paralelo. Tamanho do Grafo Tempo total Sequencial Paralelo 60 nós 1888 82,880 90 nós 4786 502,593 120 nós 8038 708,349 150 nós 10533 1262,02 65 Figura 7.1: Tempo Total de execução do algoritmo sequencial versus paralelo com seis core. Tabela 7.6: Comparativo entre o tempo total de execução do Q-learning sequencial e paralelo com seis agrupamentos. Tamanho do Grafo Tempo total (s) Sequencial (I) Paralelo(II) 60 nós 4006 9,8 90 nós 8395 21,2 120 nós 15862 126,7 150 nós * 177,25 180 nós * 565,419 210 nós * 2014,02 * Não realizamos os testes para essas instâncias devido ao longo tempo de treinamento. I - Foram executados 600.000 episódios de treinamento para o Q-learning. II - Os grafos foram divididos em 6 (seis) agrupamentos (O computador utilizado dispunha de seis núcleos físicos). 0 2000 4000 6000 8000 10000 12000 60 nós 90 nós 120 nós 150 nós Te m p o ( em s ) Tamanho do Grafo Tempo Total de Execução Sequencial Paralelo 66 Figura 7.2: Tempo Total de execução do algoritmo Q-learning sequencial versus paralelo com seis core. Percebe-se a partir da Figura 7.2 que o tempo de treinamento do algoritmo Q-learning cresce exponencialmente a medida que aumentamos o tamanho do grafo, enquanto o tempo do método paralelo proposto cresce de forma menos acentuada. Além disso, para problemas de maior dimensão temos a possibilidade de trabalhar com arquiteturas de computador com um número maior de cores, viabilizando a execução do método em cenários de maior complexidade. Para avaliarmos a escalabilidade e eficiência do método proposto tomamos grafos com 60, 90, 120, 150, 180, 210 e 240 nós, em seguida os mesmos foram divididos em 6 agrupamentos e o algoritmo hierárquico foi então executado fixando-se o número de processadores de um a seis. Os dados dos experimentos são apresentados na tabela 7.7 a seguir: Nós Núcleos 1 2 3 4 5 6 60 0,00071 0,00070 0,00055 0,00040 0,00035 0,00033 90 0,00129 0,00122 0,00086 0,00075 0,00075 0,00049 120 0,00245 0,00228 0,00153 0,00135 0,00113 0,00093 150 0,00570 0,00323 0,00227 0,00190 0,00188 0,00167 180 0,00836 0,00558 0,00455 0,00424 0,00325 0,00304 210 0,01087 0,00943 0,00802 0,00763 0,00616 0,00385 240 0,01454 0,01307 0,01069 0,00843 0,00571 0,00337 Tabela 7.7: Tempo de execução, em segundos, do algoritmo proposto com o número de agrupamentos variando de um a seis. 0 2000 4000 6000 8000 10000 12000 14000 16000 18000 60 90 120 150 180 210 240 Te m p o ( em s ) Tamanho do Grafo Tempo Total de Execução Q-learning Sequencial HierárquicoParalelo 67 Núcleos Nós Dois Três Quatro Cinco Seis 60 1,0229 1,3101 1,8030 2,0517 2,1902 90 1,0566 1,5029 1,7105 1,7150 2,6232 120 1,0754 1,5997 1,8205 2,1813 2,6274 150 1,7641 2,5079 3,0021 3,0276 3,4140 180 1,4988 1,8357 1,9698 2,5695 2,7505 210 1,1529 1,3560 1,4246 1,7651 2,8251 240 1,1129 1,3600 1,7251 2,5475 4,3148 Tabela 7.8: Speedup do algoritmo proposto com o número de agrupamentos variando de um a seis. Observando a tabela 7.8 acima percebe-se que o speedup aumenta à medida que incrementamos o número de processadores. Destacando-se a configuração para 240 nós na qual foram utilizados seis processadores, onde atingiu-se um speedup de 4,3. Na figura 7.3 a seguir conseguimos avaliar a evolução do desempenho com o aumento do número de processadores. Figura 7.3: Speedup do algoritmo proposto com o número de agrupamentos variando de um a seis. 0 0,5 1 1,5 2 2,5 3 3,5 4 4,5 5 Dois Três Quatro Cinco Seis Sp ee d u p Nº de Processadores 60 90 120 150 180 210 240 68 Núcleos Nós Dois Três Quatro Cinco Seis 60 0,511 0,437 0,451 0,410 0,365 90 0,528 0,501 0,428 0,343 0,437 120 0,538 0,533 0,455 0,436 0,438 150 0,882 0,836 0,751 0,606 0,569 180 0,749 0,612 0,492 0,514 0,458 210 0,576 0,452 0,356 0,353 0,471 240 0,556 0,453 0,431 0,509 0,719 Tabela 7.9: Eficiência do algoritmo proposto com o número de agrupamentos variando de um a seis. O cerne do método proposto é dividir convenientemente o grafo que representa o problema original em agrupamentos e distribuir adequadamente o treinamento dos mesmos de forma equitativa entre os processadores disponíveis. Como o treinamento dos agrupamentos ocorre de forma independente, a abordagem hierárquica permitiu potencializar o uso dos processadores e, consequentemente, tratar problemas de maior dimensão. Na tabela 7.9 podemos observar que a eficiência chegou a 0,882 para 150 nós e 2 processadores, para 240 nós e 6 processadores se atingiu uma eficiência de 0,719. A figura 7.4 mostra que mesmo aumentando o tamanho do problema as taxas de eficiência se apresentaram satisfatórias, indicando a escalabilidade do método proposto. Figura 7.4: Eficiência do algoritmo proposto com o número de agrupamentos variando de um a seis. 0,000 0,100 0,200 0,300 0,400 0,500 0,600 0,700 0,800 0,900 1,000 60 90 120 150 180 210 240 Ef ic iê n ci a Tamanho do Grafo Dois Três Quatro Cinco Seis 69 7.4 Aplicação do Método Hierárquico Paralelizado ao Problema de Sondas de Produção Terrestre. Para aplicação do algoritmo em um problema prático na indústria petrolífera foi utilizado instâncias com 100, 125, 150, 175 e 200 poços de petróleo. Sendo na prática as sondas de manutenção limitadas, como também, devido ao crescimento exponencial da estrutura de armazenamento do método proposto (𝐶𝑘 𝑛 × 𝑘 × 𝑛 ) para um número maior de poços (n) e de sondas de manutenção (k), utilizaremos nos testes duas sondas de manutenção (servos). A configuração original dos poços, que não apresenta grande discrepância nas distâncias entre os poços, favorece as características do método guloso que sempre irá atender a demanda mais próxima. A inteligência artificial utilizada pelo agente da aprendizagem pro reforço tende a se sobressair em condições mais adversar, ou seja, onde as distâncias até a demanda sejam maiores e o treinamento do agente indique as melhores opções de deslocamento. Na prática, essa característica significa tomar decisões acertadas em condições que envolvam maiores riscos de perda (ou ganho). Já que na indústria do petróleo as operações envolvem usualmente milhares de dólares, essa condição significaria a oportunidade de ganhos maiores ao longo do tempo. Assim, provocamos um “distúrbio” na configuração original dos poços. Mantendo a distância máxima entre dois poços mas ampliando a heterogeneidade do conjunto. Os resultados dos testes são apresentados a seguir: Tabela 7.10 Resumo do comparativo entre o Q-Learning, Hierárquico paralelizado e o guloso para as várias instâncias de poços. Nº de poços Tamanho dos agrupamentos Nº de vitórias QL Q-Hier_Par Guloso 100 14 - 14 - 20 - 15 - 22 - 15 0 91 9 125 19 - 26 - 16 - 17 - 21 - 26 0 100 0 150 21 - 30 - 18 - 17 - 37 - 27 0 52 48 175 26 - 28 - 33 - 31 - 22 - 35 0 78 22 200 36 - 41 - 31 - 31 - 29 - 32 0 97 3 70 A tabela 7.10 mostra os desempenhos dos métodos para as várias instâncias de poços. O resultado obtido para o Q-Learning resulta da incapacidade prática de se garantir um treinamento adequado do método para grande instâncias e, consequentemente, sua convergência. Fica evidente que a proposta do parâmetro de equilíbrio de carga (τ) permitiu, não só o esforço computacional homogêneo entre os processadores, como também um treinamento mais eficiente nos agrupamentos. Resultando no maior número de vitórias do método proposto para todas as instâncias. Tabela 7.11: Tempo total de execução, em segundos, para os métodos Q-Learning, Hierárquico paralelizado e o guloso para as várias instâncias de poços. Tempo total de execução (segundos) Nº de poços Q-learning Sequencial Hierárquico Paralelo (6 núcleos) 100 12.337 59,11 125 16.717 219,97 150 20.432 232,83 175 24.731 727,77 200 29.076 1.706,84 Figura 7.4.1 Tempo total de execução, em segundos, para os métodos Q-Learning, Hierárquico paralelizado e o guloso para as várias instâncias de poços. 0 5000 10000 15000 20000 25000 30000 35000 100 125 150 175 200 Te m p o d e ex ec u çã o ( se gu n d o s) Número de poços Q-learning Sequencial Hierárquico Paralelo (6 núcleos) 71 A tabela 7.4.2 e a figura 7.4.1 ressaltam a eficiência da abordagem utilizando o método hierárquico e computação paralela quando comparado com a abordagem clássica sequencial. Tabela 7.12: Comparativo entre os métodos Q-Learning, Hierárquico paralelizado e o guloso para a instância de 100 poços. 100 poços, 2 servos e 6 grupamentos: 14 - 14 - 20 - 15 - 22 – 15 Q-learning Q-learning Hierárquico Paralelo Guloso Tempo (s) 12.337,0 59,11 * Distância Média 93.6573,46 85.0160,49 86.8478,13 Desvio padrão 14.632,28 15.163,56 19.165,73 Maior caminho 976.987,00 882.387,00 917.010,00 Menor caminho 901.531,00 814.713,00 824.754,00 Vitórias 0 91 9 * O método guloso não necessita de treinamento. Tabela 7.13: Comparativo entre os métodos Q-Learning, Hierárquico paralelizado e o guloso para a instância de 125 poços. 125 poços, 2 servos e 6 grupamentos: 19 - 26 - 16 - 17 - 21 - 26 Q-learning Q-learning Hierárquico Paralelo Guloso Tempo (s) 16.717,0 219,97 * Distância Média 1.849.645,06 1.718.874,37 1.767.356,55 Desvio padrão 31.709,49 31.800,11 34.367,86 Maior caminho 1.947.187,00 1.820.615,00 1.852.283,00 Menor caminho 1.750.761,00 1.642.989,00 1.671.321,00 Vitórias 0 100 0 * O método guloso não necessita de treinamento. Tabela 7.14: Comparativo entre os métodos Q-Learning, Hierárquico paralelizado e o guloso para a instância de 150 poços. 150 poços, 2 servos e 6 grupamentos: 21 - 30 - 18 - 17 - 37 - 27 Q-learning Q-learning Hierárquico Paralelo Guloso Tempo (s) 20.432,0 232,83 * Distância Média 1.654.806,56 1.555.931,44 1.558.770,06 Desvio padrão 23.293,30 23.985,38 26.012,27 Maior caminho 1.706.591,00 1.603.289,00 1.634.902,00 Menor caminho 1.597.942,00 1.496.936,00 1.494.245,00 Vitórias 0 52 48 * O método guloso não necessita de treinamento. 72 Tabela 7.15: Comparativo entre os métodos Q-Learning, Hierárquico paralelizado e o guloso para a instância de 175 poços. 175 poços, 2 servos e 6 grupamentos: 26 - 28 - 33 - 31 - 22 - 35 Q-learning Q-learning Hierárquico Paralelo Guloso Tempo (s) 24.731,0 727,77 * Distância Média 2.096.386,36 1.958.206,00 1.977.679,29 Desvio padrão 31.149,03 29.931,22 32.948,97 Maior caminho 2.168.079,00 2.021.396,00 2.056.947,00 Menor caminho 2.020.114,00 1.896.478,00 1.892.335,00 Vitórias 0 78 22 * O método guloso não necessita de treinamento. Tabela 7.16: Comparativo entre os métodos Q-Learning, Hierárquico paralelizado e o guloso para a instância de 200 poços. 200 poços, 2 servos e 6 grupamentos: 36 - 41 - 31 - 31 - 29 - 32 Q-learning Q-learning Hierárquico Paralelo Guloso Tempo (s) 29.076,0 1706,84 * Distância Média 2.036.864,60 1.927.855,05 1.965.630,12 Desvio padrão 37.278,25 41.314,88 36.497,46 Maior caminho 2.137.770,00 2.057.930,00 2.070.240,00 Menor caminho 1.944.878,00 1.806.119,00 1.872.483,00 Vitórias 0 97 3 * O método guloso não necessita de treinamento. 7.4 Considerações Neste Capítulo mostrou-se a associação entre a teoria sobre aprendizagem por reforço hierárquica apresentada e a solução proposta neste trabalho, correlacionando técnicas formais que garantem a convergência para o ótimo com a proposta neste texto. Os resultados empíricos foram muito satisfatórios quando comparados com o método Q-Learning e o guloso, sendo este um forte indício da viabilidade da solução. 73 Capítulo 8 Considerações finais 8.1 Conclusão A solução apresentada neste trabalho de tese, baseada na aprendizagem por reforço hierárquica e em técnicas de computação paralela, vislumbra-se como uma ferramenta eficaz no desenvolvimento de algoritmos para a solução de problemas de otimização em espaços métricos. Para verificar o desempenho da solução foi analisada a utilização da aprendizagem por reforço em um problema específico de MTS, o problema dos K-Servos. Como sem maiores dificuldades teóricas a solução pode ser aplicada a quaisquer problemas de otimização em espaços métricos, o desempenho satisfatório obtido para o PKS poderia ser replicado a outros problemas de MTS. O problema de sondas de produção terrestre (SPT) foi modelado a partir do problema dos K-Servos homogêneos e os resultados obtidos mostraram a eficiência do método proposto para tratar problemas práticos de grande dimensão. O método hierárquico paralelizado obteve resultados satisfatórios em problemas de alta complexidade, já que o critério de subdivisão em agrupamentos permite um melhor treinamento dentro dos mesmos e nos nós centrais, como também, proporciona um equilíbrio de carga no processamento dos dados. Com isso, não só o tempo de treinamento se mostrou escalável como o desempenho do método comparado ao guloso se mostrou superior. Desta forma, vislumbra- se boas perspectivas de uso do método proposto de forma a contornar a maldição da dimensionalidade. Como mostrado por Ribeiro (1998) [16], se as garantias de convergência do algoritmo Q-Learning e certas condições da função de espalhamento forem satisfeitas, a política converge para o ótimo. Isto indica que a técnica de divisão em grupos e a do espalhamento do aprendizado a partir de um nó-central proposta pode convergir para o ótimo, já que as garantias de convergência do Q-Learning foram satisfeitas nesta solução. Já o uso do método ε-guloso na solução proposta decorreu de sua capacidade de obtenção de soluções satisfatórias em um tempo viável. Trata-se de um método que fornece respostas instantâneas, não necessita de estrutura de armazenamento para fornecer essas respostas e consegue obter, dadas as condições de otimalidade do método, a convergência para o ótimo em problemas com espaços euclidianos. 74 Mesmo não garantindo respostas ótimas para todas as instâncias, o método guloso mostrou-se bastante eficiente. 8.2 Perspectivas de trabalhos futuros Os resultados obtidos apontam para a viabilidade de aplicação do método a instâncias ainda maiores e a uma quantidade maior de servos, já que a abordagem hierárquica paralela mostrou-se bastante eficiente. O algoritmo proposto apresenta potencial para utilização em outras abordagens. Podendo se adequar para aplicações em Smart Cities (Cidades Inteligentes), Big Data e em outros problemas da indústria de petróleo. 8.3 Trabalhos publicados M. L. Costa, C. A. A. Padilha, J. D. Melo and A. D. Dória Neto. Uma Abordagem utilizando Redes Neurais Fuzzy ART e Aprendizagem por Reforço para o Problema dos k-servos. Proceedings. 1st BRICS Countries Congress on Computational Intelligence. BRICS-CCI 2013. 8-11 September 2013. Recife (Porto de Galinhas Beach), Brazil. M. L. Costa, J. D. Melo e A. D. Dória Neto. Aprendizagem por Reforço Hierárquica e Computação Paralela Aplicada ao Problema da Dimensionalidade. ANAIS 1º SIMPÓSIO DO PPGCEP – UFRN - PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA E ENGENHARIA DE PETRÓLEO, dezembro de 2015. M. L. Costa, C. A. A. Padilha, J. D. Melo and A. D. Dória Neto. Hierarchical Reinforcement Learning and Parallel Computing Applied to the K-Server Problem. IEEE LATIN AMERICA TRANSACTIONS, VOL. 14, NO. 10, OCTOBER 2016. 75 Referências Bibliográficas Yao, A.C.C. Probabilistic computations: Towards a unified measure of complexity. In Proc. 17th Annual IEEE Symposium on Foundations of Computer Science, pages 222-227, 1977. Albers, Susanne (1996), Competitive on-line algorithms, BRICS Lecture Series LS-96-2, Department of Computer Science, University of Aarhus. Assis, Ítalo Augusto Souza de. Um algoritmo paralelo eficiente de migração reversa no tempo (rtm) 3d com granularidade fina. Dissertação de Mestrado, 2015. Bansal, N., Buchbinder, N. & Naor, J. (2010). Proceedings 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10, Austin TX, USA, January 17-19, 2010). In Charikar, M. (Ed.), Towards the randomized k-server conjecture: A primal-dual approach, (pp. 40-55). SIAM. Bartal, Y. & E. Koutsoupias (2004), On the competitive ratio of the work function algorithm for the k-server problem, em ‘Proceedings of the 23rd ACM Symposium on Theory of Computation’, Vol. 324, ACM Press, pp. 337–345. Bartal, Y. & E. Grove (1991), The harmonic k-server algorithm is competitive, em ‘Proceedings of the 23rd ACM Symposium on Theory of Computation’, Vol. 47, ACM Press, pp. 1–15. Barto, A. G. & S. Mahadevan (2003), Recent advances in hierarchical reinforcement learning, em ‘Discrete-Event Dynamical Systems: Theory and Aplications’, Vol. 13, pp. 341–379. Borodin, A. & R. El-Yaniv (1998), Online Computation and Competitive Analysis, Cambridge University Press, Cambridge, MA. Borodin, A.; Linial, N. and Saks, M. An optimal online algorithm for metrical task systems. Journal of the ACM, 39:745-763, 1992. (Conference version [81]) Bellman, R. (1957), Dynamic Programming, Princeton University Press. Bertsekas, D. P. & J. N. Tsitsiklis (1996), Neuro-dynamic Programming, Athena Scientific, Cambridge, MA. Bratdke, S. J. & M. O. Duff (1995), Reinforcement learning methods for continuous –time markov decision problems, em G.Tesauro, D.Touretzky & T.Leen, eds., ‘Advances in Neural Information in Processing Systems’, Vol. 7, pp. 393–400. Bulnes, F. G.; Usamentiaga, R. ; García, D. F. and Molleda, J. A Parallel Genetic Algorithm for Optimizing an Industrial Inspection System. IEEE LATIN AMERICA TRANSACTIONS, VOL. 11, NO. 6, DECEMBER 2013. Crites, R. H. & A. G Barto (1996), Improving elevator performance using reinforcement learning, em D. S.Touretzky, M. C.Mozer & M. E.Hasselmo, eds., ‘Advances in Neural Information Processing Systems’, MIT Press, Cambridge, MA. 76 Sleator, D.D. and Tarjan, R.R. Amortized efficiency of list up date and paging rules. Communication of the ACM. 28:202-208, 1985. Dietterich, T. G. (2000a), Hierarchical reinforcement learning with the maxq value function decomposition, em ‘Artificial Intelligence’, Vol. 7, pp. 227–303. Drummond, C. (2002), Accelerating reinforcement learning by composing solutions of automatically identified subtasks, em ‘Journal of Artificial Intelligence Research’, Vol. 16, pp. 59–104. Djurdjevic, P.D., Huber, M., Systems, Deep Belief Network for Modeling Hierarchical Reinforcement Learning Policies. Man, and Cybernetics (SMC), 2013 IEEE International Conference on DOI: 10.1109/SMC.2013.424 Publication Year: 2013, Page(s): 2485 - 2491 El-Rewini, H. and Abd-El-Barr, M., Advanced Computer Architecture and Parallel Processing, John Wiley & Sons, Inc., 2005. Koutsoupias, E. The k-server problem. Computer Science Review 3(2): 105-118 (2009). Farias, Daniela Pucci De (2002), The Linear Programming Approach to Approximate Dynamic Programming: Theory and Application, Tese de doutorado, Stanford University. Feng, Y.; Yu, W.; Chen, Y.; Tan, X.; Wang, R.; Madani, K. Option-based motion planning and ANFIS-based tracking control for wheeled robot in cluttered environment. Informatics in Control, Automation and Robotics (ICINCO), 12th International Conference on Year: 2015, Volume: 01. Pages: 287 – 293. Foster, Ian. Designing and Building Parallel Program: Concepts and Tools for Parallel Software Engineering. Addison-Wesley Publishing Co., 1995. Huang, Z. & S.N. Balakrishnan (2000), Robust adaptive critic based neurocontrollers for systems with input uncertainties, em ‘Proceedings of IJCNN’2000’, Como, Italy, pp. B–263. Hesham El-Rewini, Mostafa Abd-El-Barr. ADVANCED COMPUTER ARCHITECTURE AND PARALLEL PROCESSING, 2005 by John Wiley & Sons, Inc. Herlihy, M.; Shavit, N. The Art of Multiprocessor Programming. Elsevier Inc., 2008. Hengst, B. Hierarchical Approaches, 2011. Huang Z., Ma J., Solving the curse of dimensionality utilizing action-dependent heuristic dynamic programming, Computer Science and Automation Engineering (CSAE), 2011 IEEE International Conference on Volume: 2 DOI: 10.1109/CSAE.2011.5952472 Publication Year: 2011 , Page(s): 289 – 292 Júnior, M. L. L., J. D. Melo & A. D. D. Neto (2005a), The k-server problem: A reinforcement learning approach, em ‘Proceedings 2005 IEEE International Joint Conference on Neural Networks’, Vol. 2, pp. 798–802. 77 Kariotoglou, N., Summers, S., Summers, T., Kamgarpour, M., Lygeros, J., Approximate dynamic programming for stochastic reachability, Control Conference (ECC), 2013 European Publication Year: 2013 , Page(s): 584 - 589 Lima Júnior, F. C, Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético. Tese de doutorado, 2009. Littman, M. & J. Boyan (1993), A distributed reinforcement learning scheme for network routing, em J.Alspector, R.Goodman & T. X.Brown, eds., ‘Proceedings of the InternationalWorkshop on Applications of Neural Networks to Telecommunications’, pp. 45– 51. Liang, Z., Li, Y., Wei, H., The operation optimization model of pumped-hydro power storage station based on approximate dynamic programming. Power System Technology (POWERCON), 2014 International Conference on DOI: 10.1109 / POWERCON. 2014. 6993586 Publication Year: 2014 , Page(s): 215 - 220 Li, D., Jayaweera, S.K., Machine-Learning Aided Optimal Customer Decisions for an Interactive Smart Grid, Systems Journal, IEEE Volume: PP , Issue: 99 DOI: 10.1109/JSYST.2014.2334637 Publication Year: 2014 , Page(s): 1 - 12. Manasse, M. S., L. A. McGeoch & D. D. Sleator (1988), Competitive algorithms for online problems, em ‘Proceedings of the twentieth annual ACM symposium on Theory of computing’, ACM Press, pp. 322–333. Neidhoefer, J. C. & K. Krishnakumar (2001), Intelligent control for autonomous aircraft missions, em ‘IEEE Transactions on Systems, Man, and Cybernetics’. Pacheco, Peter S. An Introduction to Parallel Programming. Elsevier Inc., 2011 Parr, R. & S. Russell (1998), Reinforcement Learning with Hierarchy of Machines, Tese de doutorado, Cambridge, MA. Prokhorov, D. (1997), Adaptive Critic Designs and their Application, Tese de doutorado, Texas Tech University. Ribeiro, C. H. C. (1998), Embedding a priori knowledge in reinforcement learning, em ‘Journal of Intelligent and Robotic Systems’, Vol. 21, pp. 51–71. Rocha Vianna, L.G., Sanner, S., Nunes de Barros, L., Continuous Real Time Dynamic Programming for Discrete and Continuous State MDPs. Intelligent Systems (BRACIS), 2014 Brazilian Conference on DOI: 10.1109/BRACIS.2014.34 Publication Year: 2014 , Page(s): 134 - 139 Ryan, M. R. K. (2002), Hierarchical Reinforcement Learning: A Hybrid Approach, Tese de doutorado, University of New South Wales. Santos, J.P.Q; Melo, J.D., Dória Neto, A. D.; Aloise, D.; Reactive Search strategies using Reinforcement Learning, local search algorithms and Variable Neighborhood Search; Expert Systems with Applications, Volume: 41; Publication Year: 2014; page(s): 4939–4949. 78 Schultz, L. J., T. T. Shannon & G. G. Lendaris (2001), Using dhp adaptive critic methods to tune a fuzzy automobile steering controller, em ‘Proceedings of FSA/NAFIPS Conference’. Si, J., A. G. Barto, W. B. Powell & D. Wunsch II (2004), Handbook of Learning and Approximate Dynamic Programming, IEEE Press Series on Computational Intelligence, IEEE Press and Wiley-Interscience. Silva, E. H. M. and Bastos Filho, C. J. A. PSO Efficient Implementation on GPUs Using Low Latency Memory. IEEE LATIN AMERICA TRANSACTIONS, VOL. 13, Nº. 5, MAY 2015. Snyder, L., Lin, C., Principles of Parallel Progamming, Pearson Education, 2009, 1st ed. Sutton, R. S. & A. G. Barto (1998), Reinforcement Learning: An Introduction, The MIT Press, Cambridge, MA. Sutton, R. S. (1990), Integrated architectures for learning, planning and reacting based on approximating dynamic programming, em ‘Proceedings of the 7th International Conference on Machine Learning’. Střelec, M., Berka, J., Microgrid energy management based on approximate dynamic programming, Innovative Smart Grid Technologies Europe (ISGT EUROPE), 2013 4th IEEE/PES DOI: 10.1109/ISGTEurope.2013.6695439 Publication Year: 2013 , Page(s): 1 - 5 Tesauro, G. (1995), Temporal difference learning and td-gammon, em ‘Communications of the ACM’, Vol. 38, pp. 58–67. Xie, Q.; Shin, D.; Chang, N.; Pedram, M. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Volume: 35, Pages: 611 – 622, 2016. Yu, T., Wang, Y.M., Ye, W.J., Zhou, B., Chan, K.W., Stochastic optimal generation command dispatch based on improved hierarchical reinforcement learning approach, Generation, Transmission & Distribution, IET Volume: 5, Issue: 8 DOI: 10.1049/iet-gtd.2010.0600 Publication Year: 2011 , Page(s): 789 – 797 Yan Q., Liu, Q., Hu, D., A hierarchical reinforcement learning algorithm based on heuristic reward function, Advanced Computer Control (ICACC), 2010 2nd International Conference on Volume: 3 DOI: 10.1109/ICACC.2010.5486837 Publication Year: 2010 , Page(s): 371 – 376 Yu, J.; Wang, C.; Xie, G. Coordination of Multiple Robotic Fish With Applications to Underwater Robot Competition. IEEE Transactions on Industrial Electronics. Volume: 63, Pages: 1280 - 1288, 2016. Yao, A C. C. (1977), Probabilistic computations: Towards a unified measure of complexity, In Proceedings of the 18th Annual Symposium on Foundations of computer Science (FOCS), pp. 222–227. Watkins, C. J. C. H. (1989), Learning from Delayed Rewards, Tese de doutorado, King’s College. Zhang, W. & T. G. Dietterich (1995), A reinforcement learning approach to job shop scheduling, em ‘Proceedings of the IJCAI’. 79 Xie, Q.; Shin, D.; Chang, N.; Pedram, M. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Volume: 35, Pages: 611 – 622, 2016. Yu, J.; Wang, C.; Xie, G. Coordination of Multiple Robotic Fish With Applications to Underwater Robot Competition. IEEE Transactions on Industrial Electronics. Volume: 63, Pages: 1280 - 1288, 2016.