UC Merced

The computation of navigation strategies plays a significant role in the fields of Computer Animation, Simulation, and Robotics. Its importance spans various applications such as agent navigation, evacuation analysis, and the coordination of largescale multi-agent simulations, ranging from simulated environments to tactical warfare games and robotics. This dissertation focuses on the development of navigation structures specifically designed for strategies that optimize agent flow, take into account formation integrity and preferences during planning and navigation, and provide visualization for a multitude of path choices in face of time-critical situations.This dissertation presents three main contributions. Firstly, a novel approach to multi-agent planning and navigation is presented, utilizing Shortest Path Maps (SPMs). This work demonstrates how querying the SPM vector field leading to the goal can naturally achieve local collision avoidance during multi-agent navigation, provided that all agents are following the same SPM. Furthermore, a two-phase planning and navigation approach for agents in formation is suggested, balancing preferred formations with their respective required clearances, in order to address the impact of high-clearance formations on path length. This is achieved using a novel multi-layer graph representing clearance and formation costs. Additionally, the concept of Corridor Shortest Path Maps (CSPMs) is introduced, providing a vector field to guide agents within the solution corridor, ensuring unobstructed in-formation navigation in cluttered environments and optimizing group motion along lengthwise optimal paths. Secondly, this dissertation introduces the topic of computing and analysing decision boundaries between shortest paths, for optimal decision-making in time-critical scenarios with dynamic regions to be avoided. The proposed approach simulates time-varying avoidance zones, employing SPMs to extract and visualize the boundaries between shortest paths traversing distinct regions. These boundaries offer time dependent guidance for selecting optimal routes based on departure time, delimiting the transition between different classes of optimal paths and illustrating their evolution in response to changing obstacle regions. Finally, this dissertation introduces the concept of controlling dispersion in multiagent path planning and navigation in 3D spaces among obstacles. Given a 3D environment, the proposed method computes collision-free lanes in the 3D environment leading to a shared goal region, taking into account agent clearance and path dispersion. Dispersion is addressed with the application of a max-flow algorithm applied to the 3D medial axis, where graph edges are capacitated based on the volumetric clearance around them, overall determining the number of agents that can occupy each volumetric area of the environment.