Publicado em: 24/07/2014

Dissertação de Mestrado em Inteligência Artificial

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL

INSTITUTO DE INFORMÁTICA

PROGRAMA DE PÓS-GRADUAÇÃO EM COMPUTAÇÃO

———————————————————

DEFESA DE DISSERTAÇÃO DE MESTRADO

Aluno: Ricardo Grunitzki

Orientadora: Profa. Dra. Ana Lucia Cetertich Bazzan

Título: Aprendizado por Reforço Multiagente: Uma Avaliação de Diferentes Mecanismos de

Recompensa para o Problema de Aprendizado de Rotas

Linha de Pesquisa: Inteligência Artificial

Data: 01/08/14

Hora: 14:00h

Local: Prédio 43424 – Auditório Prof. Castilho, Instituto de Informática

Banca Examinadora:

Prof. Dr. Felipe Rech Meneguzzi (PUCRS)

Profa. Dra. Graçaliz Pereira Dimuro (FURG)

Profa. Dra. Ingrid Oliveira de Nunes (UFRGS)

Presidente da Banca: Profa. Dra. Ana Lucia Cetertich Bazzan

Resumo:

Esta dissertação de mestrado apresenta um estudo sobre os efeitos de diferentes funções de recompensa, aplicadas em aprendizado por reforço multiagente, para o problema de roteamento de veículos, em redes de tráfego. São abordadas duas funções de recompensas que diferem no alinhamento do sinal numérico enviado do ambiente ao agente. A primeira função, chamada função individual, é alinhada à utilidade individual do agente (veículo ou motorista) e busca minimizar seu tempo de viagem. Já a segunda função, por sua vez, é a chamada difference rewards, essa é alinhada à utilidade global do sistema e tem por objetivo minimizar o tempo médio de viagem na rede (tempo médio de viagem de todos os motoristas). Ambas as abordagens são aplicadas em dois cenários de roteamento de veículos que diferem em: quantidade de motoristas aprendendo, topologia e, consequentemente, nível de complexidade. As abordagens são comparadas com três técnicas de alocação de tráfego presentes na literatura. Resultados apontam que os métodos baseados em aprendizado por reforço apresentam desempenho superior aos métodos de alocação de rotas. Além disso, o alinhamento da função de recompensa à utilidade global proporciona uma melhora significativa nos resultados quando comparados com a função individual. Porém, para cenários com muitos agentes aprendendo simultaneamente, ambas as abordagens apresentam soluções equivalentes.

Palavras-chave:  Aprendizado por reforço multiagente, função de recompensa, difference rewards, sistemas multiagente

_____________

Divulgação PPGC