Monte Carlo continuous action space solver for chance constrained Markov decision processes (2024)
- Authors:
- Autor USP: SOUZA, GUSTAVO DE MOURA - ICMC
- Unidade: ICMC
- Sigla do Departamento: SSC
- DOI: 10.11606/D.55.2024.tde-23042025-131038
- Subjects: AERONAVES NÃO TRIPULADAS; MÉTODO DE MONTE CARLO; MÉTODOS PROBABILÍSTICOS; COMPUTAÇÃO EVOLUTIVA
- Keywords: Aprendizado por reforço; Árvore de busca de Monte Carlo; Chance constraint; Limitante de risco; Monte Carlo tree search; Path planning; Planejamento de rotas; Reinforcement learning; Restrições de probabilidade; Risk bounding
- Language: Inglês
- Abstract: O uso de Veículos Aéreos Não Tripulados (VANTs) expande constantemente em vários domínios, desde aplicações militares até monitoramento ambiental e planejamento urbano. O planejamento de rotas para VANTs, especialmente em ambientes complexos e dinâmicos, apresenta desafios relevantes, particularmente quando se consideram incertezas e restrições de risco. Esta dissertação foca no desenvolvimento de um algoritmo de planejamento de rotas utilizando Árvores de Busca de Monte Carlo (Monte Carlo Tree Search - MCTS) que aborda problemas de roteamento com restrições de probabilidade em espaços de ação contínuos. Pesquisas anteriores em planejamento de rotas para VANTs exploraram métodos determinísticos e probabilísticos. Este estudo é desenvolvido com base nos métodos probabilísticos, visando aproveitar os pontos fortes do MCTS em lidar com incertezas e fornecer uma solução de planejamento de rotas flexível. O algoritmo Vulcan foi adaptado para um espaço de ação contínuo resultando no desenvolvimento do algoritmo Nashor. Ele incorpora modificações, incluindo avaliação contínua da viabilidade em cada transição de estado, para garantir um planejamento de rotas sem violar riscos. As configurações experimentais incluíram simulações em um ambiente virtual customizado denominado Itomori, criado dentro do framework Gymnasium, facilitando o teste do algoritmo sob várias condições, incluindo diferentes níveis de incerteza do GPS e densidades de obstáculos. Dados foram coletados de diversasexecuções de simulação, configurações de mapas e técnicas de discretização, como Partições Hierárquicas, além de avaliações do desempenho do algoritmo sob diferentes restrições de risco. Experimentos demonstraram que as técnicas de discretização foram suficientes para que o Nashor pudesse encontrar soluções para todos os mapas testados, incluindo os mais difíceis. O desempenho do algoritmo é influenciado pelo nível de risco, mostrando que, enquanto níveis impraticavelmente altos de incerteza tornam encontrar uma solução difícil, Nashor ainda conseguiu identificar rotas viáveis em cenários de incerteza realistas. Além disso, o desenvolvimento do ambiente de simulação Itomori oferece uma plataforma versátil para pesquisas futuras, permitindo o teste de novos algoritmos de planejamento de rotas sob uma variedade de condições. Este trabalho contribui com novos estudos em MCTS e discretização e também abre caminhos para avanços adicionais em simulações envolvendo risco, ao facilitar a comunicação do ambiente com novos algoritmos.
- Imprenta:
- Publisher place: São Carlos
- Date published: 2024
- Data da defesa: 09.12.2024
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
SOUZA, Gustavo de Moura. Monte Carlo continuous action space solver for chance constrained Markov decision processes. 2024. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2024. Disponível em: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-23042025-131038/. Acesso em: 25 maio 2025. -
APA
Souza, G. de M. (2024). Monte Carlo continuous action space solver for chance constrained Markov decision processes (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/55/55134/tde-23042025-131038/ -
NLM
Souza G de M. Monte Carlo continuous action space solver for chance constrained Markov decision processes [Internet]. 2024 ;[citado 2025 maio 25 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-23042025-131038/ -
Vancouver
Souza G de M. Monte Carlo continuous action space solver for chance constrained Markov decision processes [Internet]. 2024 ;[citado 2025 maio 25 ] Available from: https://www.teses.usp.br/teses/disponiveis/55/55134/tde-23042025-131038/
Informações sobre o DOI: 10.11606/D.55.2024.tde-23042025-131038 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
