Planejamento baseado em casos para pathfinding enganoso em terrenos com topografia
Fecha
2024-04-30Primeiro coorientador
Bordini, Rafael Heitor
Primeiro membro da banca
Emmendorfer, Leonardo Ramos
Segundo membro da banca
Freitas, Edison Pignaton de
Metadatos
Mostrar el registro completo del ítemResumen
Planos enganosos de movimentação são fundamentais para Sistemas de Simulação Baseados
em Agentes (Agent-Based Simulation Systems (ABSS) que buscam ser realistas
na modelagem e resolução de problemas adversariais do mundo real. Diferentes situações
onde forças opostas são modeladas em ABSS requerem o planejamento de ações
de movimentação com aspectos enganosos. Neste caso, agentes simulados possuem as
capacidades de computar e utilizar caminhos que podem enganar os adversários de seus
reais objetivos. Porém, construir e avaliar planos enganosos é uma atividade complexa
para muitos usuários. Mesmo diante deste problema, a literatura de Inteligência Artificial
(IA) mostra que existe uma carência de técnicas que apoiem a criação de memórias reusáveis
contendo experiências concretas de planejamento de movimentação enganosos.
Neste contexto, o objetivo deste trabalho é investigar o desenvolvimento de ABSS que permitam
usuários especificar e testar planos de movimentação enganosos em cenários de
terrenos com topografia. Baseado em técnicas de Raciocínio Baseado em Casos (CBR)
ajustadas para as necessidades de solução de problemas neste domínio de aplicação,
o trabalho projeta, implementa e testa o framework Case-Based Planning for Deceptive
Pathfinding - CBPDP, o qual é capaz de reter, recuperar e reusar planejamentos de movimentação
enganosos para grupos de agentes. O trabalho implementa uma API de desenvolvimento
de software para apoiar a construção de ABSS. Explorando um sistema de
simulação implementado para validar esta API, o trabalho aborda o desafio de planejar rotas
enganosas em terrenos topográficos onde os custos de caminhos no relevo do terreno
e outros fatores de caminhos enganosos são analisados. O trabalho explora estratégias
enganosas alternativas que são ajustadas para analisar os custos topográficos do terreno,
não apenas para determinar o quão enganosos são os nodos do terreno computados pelos
algoritmos de pathfinding, mas também para obter caminhos enganosos com baixos
custos. Além do algoritmo A , o algoritmo Theta é usado na busca por rotas enganosas
mais suavizadas e realistas, os quais podem melhor modelar as rotas usadas por agentes
terrestres do mundo real. O trabalho analisa caminhos topográficos enganosos calculados
de acordo com as noções de Último Ponto Enganoso (LDP) e Último Ponto Enganoso
Topográfico (LDPT ), as quais permitem obter caminhos topográficos enganosos computados
em terrenos com relevos pronunciados. Resultados experimentais com os métodos
propostos são analisados estatisticamente de acordo com diferentes métricas de análise
de algoritmos de pathfinding, mostrando que as estratégias enganosas computadas com
o emprego do algoritmo A retornam caminhos topográficos com maior número de nodos
enganosos (maior densidade de engano) em tempos de execução reduzidos. Além disso,
as estratégias de computação de caminhos enganosos computadas com o apoio do algoritmo Theta e LDPT permitem obter caminhos que apresentam um trade-off relevante de
número de nodos enganosos e qualidade do caminho topográfico. Resultados experimentais
apoiados por técnicas de validação cruzada e testes de resolução de novos problemas
demonstrar a efetividade do framework de CBPDP em recuperar casos relevantes aos problemas
de movimentação enganosos apresentados ao sistema.
Colecciones
El ítem tiene asociados los siguientes ficheros de licencia: