Repositório Digital

A- A A+

Applying bandit algorithms to the route choice problem

.

Applying bandit algorithms to the route choice problem

Mostrar registro completo

Estatísticas

Título Applying bandit algorithms to the route choice problem
Outro título Aplicando algoritmos de bandits ao route choice problem
Autor Oliveira, Thiago Bell Felix de
Orientador Bazzan, Ana Lucia Cetertich
Co-orientador Silva, Bruno Castro da
Data 2017
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Algorítmo
Informatica : Transportes
[en] Bandit algorithms
[en] Q-learning
[en] Reinforcement learning
[en] Route choice
[en] Traffic assignment
Abstract Traffic infrastructure in major cities must be able to handle increasing demand. Building this infrastructure is expensive and not something that is done in a short time frame. Bottlenecks in the network and potential improvements must be identified for further planning and expansion. However, changes to the network are not always beneficial as shown by the Braess paradox. Therefore, it is ever more important to be able to understand the demand of its users and how it affects the network, and predict the effect changes in the network will cause. Traffic demand is normally defined in origin destination studies but this information is incomplete. It shows only the endpoints of trips but not the routes they take. To understand how each link in the network is used, a route allocation must be calculated. The problem of allocation of routes to trips is called the traffic assignment problem. We compare the performance of selected bandit algorithms with that of Q-learning in the context of the traffic assignment problem in a multi-agent reinforcement learning scenario. Specifically, non-stationary bandit algorithms were the main focus due to the nonstationarity of the problem. These algorithms were evaluated in their ability to provide traffic allocations that minimize the average travel time on a traffic network. Through experimentation, we found that bandit algorithms show potential. However, they did not perform better than Q-learning. Further study is required to better ascertain their capabilities for the problem.
Resumo Infraestrutura de tráfego em grandes cidades deve ser capaz de lidar com demanda crescente. Construção de infraestrutura tem altos custos e requer longo tempo de construção. Gargalos e melhorias em potencial em redes de tráfego devem ser identificados para planejamento e expansão. No entanto, mudanças na rede não são sempre benéficas como mostrado pelo paradoxo de Braess. Portanto, é cada vez mais importante entender a demanda dos usuários e como ela afeta a rede, e prever os efeitos que mudanças na rede vão causar. Demanda de tráfego é normalmente definida em estudos de origem e destino mas essa informação é incompleta. Ela mostra apenas o inicio e fim de cada viagem mas não as rotas seguidas. para compreender como cada aresta na rede é usada uma alocação de rotas deve ser calculada. O problema de alocação de rotas a viagens é chamado de Traffic Assignment Problem. Nós comparamos a performance de algoritmos de bandits selecionados com aquela do Q-learning no contexto do Traffic Assignment Problem em um cenário multi-agente com aprendizagem por reforço. Especificamente, algoritmos de bandits não estacionários foram o principal foco devido a não-estacionaridade do problema. Esse algoritmos foram avaliados nas suas habilidades de prover alocações de tráfego que minimizem o tempo médio de viagem. Através de experimentação, foi descoberto que os algoritmos de bandits mostram potencial. No entanto, eles não tem performance melhor que a do Q-learning. Mais estudos são necessários para melhor determinar as capacidades desses algoritmos para o problema.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/168972
Arquivos Descrição Formato
001048296.pdf (374.2Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.