Multi-agent pathfinding com restrições cinemáticas e movimentação de obstáculos em terrenos com elevação

Abstract

Multi-Agent Path Finding (MAPF) algorithms are essential for developing entertainment and serious games. MAPF is a multi-agent navigation problem in which each agent moves from a starting point to a destination in a manner that avoids collisions with other agents. Solving a MAPF problem involves computing the most efficient and cost-effective topographic routes for agents with different movement restrictions. To minimize the topographic cost of agent movement and the need to deviate from other stationary agents on the terrain, the proposed MAPF algorithm searches for topographic paths that respect the agents’ movement orientation and the limits of the turning angles they can execute. In resolving conflicts/collisions between agents, the proposed algorithm explores the agents’ movement priority. In this case, agents that do not have planned movement as they are stationary on the terrain are minimally displaced by the MAPF algorithm to allow for the computation of more direct and higher-quality routes for other agents. The proposed MAPF algorithm is evaluated based on a comprehensive set of scenarios, tests, and results, which are analyzed using generalized linear regression models and various metrics. This analysis provides valuable insights into the algorithm’s performance and effectiveness in different contexts. The proposed algorithm has an experimental character with high execution time and cannot yet be applied to real-time simulations.