Multi-Agent Pathfinding with Obstacle Movement for Realistic Virtual Tactical Simulations on Topographic Terrains

Multi-Agent Pathfinding (MAPF) algorithms represent a powerful tool for modeling realistic tactical movements of troops in military simulation systems. Solving MAPF problems while dealing with topographic terrains involves computing the most cost-effective and safe relief routes for agents with movement constraints. To minimize the overall topographic cost of agents' movement and the need to deviate from other stationary agents, this work considers a MAPF approach that respects real-world agents' movement characteristics, such as the agents' orientation, the limits of the agents' turning angles, and the relief inclinations they can safely navigate. To solve conflicts between agents while navigating uneven terrains, the proposed approach explores the attribution of agents' movement priorities related to the need to execute given missions. Most importantly, other agents without planned movement at the current mission situation, as they are stationary on safe and low-cost routes according to the terrain relief, are minimally displaced to nearby locations to give passage to the mission-critical agents. The MAPF algorithm is evaluated on a comprehensive set of test scenarios, with results analyzed using Generalized Linear Regression models. This analysis provides valuable insights into the MAPF algorithm's effectiveness in virtually modeling organized agent movement behaviors for developing simulation-based training and instruction activities.