Vizinhança 3k para busca de caminhos em ambientes 3D representados por grids cúbicos

Abstract

Planejamento de rotas é uma importante área de estudo da Inteligência Artificial (IA), visto seu emprego em diversos domínios de aplicação. A execução de jogos e simulações considerando espaço tridimensional (3D) se enquadram nesse contexto apresentando ele vado grau de complexidade. Consequentemente, os algoritmos usados nesse caso também apresentam maior complexidade, visto que há mais aspectos a serem tratados quando comparados a ambientes 2D. Adaptar um algoritmo 2D para ambientes 3D não é uma tarefa trivial. Muitos dos algoritmos que funcionam de forma adequada em ambientes planos, no espaço não oferecem mesmo desempenho. Perante este cenário, foi pensada uma nova abordagem de expansão da vizinhança no processo de busca, visando contri buir para o planejamento de caminhos de forma que a técnica desenvolvida possa compor implementações básicas de tais algoritmos, visando resolver o problema em ambientes 3D. Poucos trabalhos na literatura abordam técnicas de ampliação da vizinhança que pos sibilitem ao algoritmo de busca de caminhos ampliar suas direções de movimento. Essa é uma forma dos algoritmos de busca melhorarem a qualidade das soluções retornadas, promovendo suavização dos caminhos encontrados. Partindo deste princípio, o trabalho apresenta uma nova e extensa expansão de vizinhança para ambientes 3D. A chamada "Vizinhança 3 k " foi desenvolvida com a finalidade de fornecer benefícios próximos aos dos algoritmos any-angle, porém com implementações mais simples. A Vizinhança 3 k pode ser aplicada a qualquer algoritmo que não tenha como característica fundamental uma expansão de vizinhança própria. Porém, por ser uma expansão mais ampla e com plexa, a principal ideia é que seja aplicada a implementações simples, de forma a produzir caminhos de melhor qualidade, resultados próximos aos de implementações complexas. Os resultados dos experimentos, realizados com os algoritmos A*, JPS e Lazy Theta*, demonstraram que o uso da técnica de vizinhança proposta proporcionou suavização dos caminhos retornados pelos algoritmos testados, melhorando a qualidade final dos cami nhos resultantes.

Path planning is an important area of study in Artificial Intelligence (AI) employed in dif ferent application domains. Games and simulations running in three-dimensional space (3D) are in this context presenting an important complexity. Consequently, their algo rithms are also more complex, since there are more aspects to be dealt with compared to 2D environments. Adapting 2D algorithms to 3D environments is not a trivial task. Many of the algorithms that work adequately in flat environments, do not offer the same per formance in 3D spaces. Given this scenario, a new approach of neighborhood expansion in the search process was conceived, aiming to contribute to path planning by composing with basic implementations of such algorithms, aiming to solve the problem in 3D envi ronments. Few works in the literature address neighborhood expansion techniques that allow pathfinding algorithms to expand the possible movement directions. This is a way the algorithms can improve the qualities of the provided solutions, smoothing the result ing paths. Based on this principal, this paper presents a new and extended neighborhood expansion approach for 3D environments. The so-called "3k Neighborhood" was devel oped with the purpose of providing benefits close to those of any-angle algorithms, but with simpler implementations. The "3 k Neighborhood" can be applied to any algorithm that does not have as a fundamental characteristic a particular neighborhood expansion. Nevertheless, because it is a broader and more complex expansion, the main idea is to ap ply it to easy implementations, in order to produce better quality paths, with results close to those of complex implementations. The results of the experiments, performed with the A*, JPS and Lazy Theta* algorithms, demonstrated that the use of the proposed neigh borhood technique provided smoothing to the paths provided by the tested algorithms, improving the quality of the resulting paths.