FenixEdu™

Dissertação

{en_GB=Optimization of Message Ferrying UAV Paths using Monte Carlo Tree Search and Reinforcement Learning} {} EVALUATED

Detalhes: {pt=Hoje em dia, a comunicação é um elemento indispensável para a grande maioria das atividades humanas, sejam estas económicas, sociais, ou outras. Apesar de haverem diversos métodos para o efeito tais como a Internet e os telemóveis, existem casos em que a conexão pode falhar, como em catástrofes naturais ou em aldeias remotas onde não existe infrastrutura de telecomunicações. Nestes casos, é necessário um método alternativo de transporte de mensagens, como por exemplo, o uso de veículos aéreos não tripulados (UAVs). Nesta tese, propõe-se a adaptação de dois grupos de algoritmos, um de planeamento (Procura em Árvore Monte Carlo (MCTS)) e outro de aprendizagem automática (Aprendizagem por Reforço (RL)), para a procura de caminhos eficientes em redes tolerantes a atrasos (DTNs). Esta comunicação vai ser considerada em duas topologias de rede: (1) de todos os nós para um nó comum e (2) de todos os nós para todos os nós. Os resultados mostram que tanto o método baseado em RL como o método baseado em MCTS obtêm melhores resultados quando comparados com soluções baseadas no Problema do Caixeiro Viajante (TSP), para ambas as topologias. O método baseado em RL teve resultados mais consistentes quando comparado com o MCTS, tendo também precisado de menos memória. Para redes maiores ainda serão necessárias otimizações de modo a obter melhorias significantes., en=Nowadays, communication is an indispensable element for the vast majority of human activities, such as economic, social, or other. Although there are several methods for this purpose, such as the Internet and mobile phones, there are situations where the connection may fail, as in natural catastrophes or in remote villages where there is no telecommunications infrastructure. In these cases, an alternative method of message transport is required, such as the use of Unmanned Aerial Vehicles (UAVs). This thesis proposes the adaptation of two groups of algorithms, one of planning (Monte Carlo Tree Search (MCTS)) and another of Machine Learning (Reinforcement Learning (RL)), for the search of efficient paths in Delay Tolerant Networks (DTNs). This communication was considered in two distinct network topologies: (1) from all nodes to a common node and (2) from all nodes to all nodes. The results show that both RL and MCTS methods present some improvements over the Travelling Salesman Problem (TSP), in smaller networks, for both topologies. RL methods proved to have more consistent results and require less memory when comparing to MCTS. For larger networks, some optimizations are still needed in order to obtain significant improvement. }
Keywords: {pt=Rede Tolerante a Atrasos, Procura em Árvore Monte Carlo, Aprendizagem por Reforço, Veículo Aéreo não Tripulado, en=Delay Tolerant Network, Monte Carlo Tree Search, Reinforcement Learning, Unmanned Aerial Vehicle}

Discussão: julho 6, 2020, 9:0