Uma Contribuição a Solução do Problema dos k-Servos Usando Aprendizagem por Reforço

Neste trabalho e proposto um novo algoritmo online para o resolver o Problema dos k-Servos (PKS). O desempenho desta solucao e comparado com o de outros algoritmos existentes na literatura, a saber, os algoritmos Harmonic e Work Function, que mostraram ser competitivos, tornando-os parâmetros de comparacao significativos. Um algoritmo que apresente desempenho eficiente em relacao aos mesmos tende a ser competitivo tambem, devendo, obviamente, se provar o referido fato. Tal prova, entretanto, foge aos objetivos do presente trabalho. O algoritmo apresentado para a solucao do PKS e baseado em tecnicas de aprendizagem por reforco. Para tanto, o problema foi modelado como um processo de decisao em multiplas etapas, ao qual e aplicado o algoritmo Q-Learning, um dos metodos de solucao mais populares para o estabelecimento de politicas otimas neste tipo de problema de decisao. Entretanto, deve-se observar que a dimensao da estrutura de armazenamento utilizada pela aprendizagem por reforco para se obter a politica otima cresce em funcao do numero de estados e de acoes, que por sua vez e proporcional ao numero n de nos e k de servos. Ao se analisar esse crescimento (matematicamente, ) percebe-se que o mesmo ocorre de maneira exponencial, limitando a aplicacao do metodo a problemas de menor porte, onde o numero de nos e de servos e reduzido. Este problema, denominado maldicao da dimensionalidade, foi introduzido por Belmann e implica na impossibilidade de execucao de um algoritmo para certas instâncias de um problema pelo esgotamento de recursos computacionais para obtencao de sua saida. De modo a evitar que a solucao proposta, baseada exclusivamente na aprendizagem por reforco, seja restrita a aplicacoes de menor porte, propoe-se uma solucao alternativa para problemas mais realistas, que envolvam um numero maior de nos e de servos. Esta solucao alternativa e hierarquizada e utiliza dois metodos de solucao do PKS: a aprendizagem por reforco, aplicada a um numero reduzido de nos obtidos a partir de um processo de agregacao, e um metodo guloso, aplicado aos subconjuntos de nos resultantes do processo de agregacao, onde o criterio de escolha do agendamento dos servos e baseado na menor distância ao local de demanda