Algorithms for Visualization and Simulation of Optimal Navigation
Abstract
This project proposes to investigate new GPU-based algorithms for computing global and optimal navigation information in given environments, with the goal to introduce optimal metrics in multi-agent simulations and to develop new tools for visualization and analysis of navigation strategies and characteristics in given environments. Because global navigation is strongly related to path planning, this project will develop new techniques for computing, representing, and visualizing globally optimal shortest paths in varied situations. The starting point for this project is the computation of Shortest Path Maps (SPMs), which are well-known spatial decompositions that encode all the shortest paths in the plane relative to a source point in the environment. This project will rely on the recent approach introduced by the PIÕs group for computing SPMs with GPU shader programming. The approach is capable of successfully generating SPMs of unprecedented complexity and taking into account a number of extensions. This project will expand the approach in order to achieve new types of optimal path maps which will enable the computation of novel path planning queries with optimality guarantees. The optimal path maps that will be produced will also lead to new ways of representing global navigation information in multi-agent simulations. The result will be simulations based on well-defined metrics and thus more reliable and informative to be used in support to strategic movement or space design decisions. The particular topic of navigation analysis in open or closed spaces is important for a number of applications, from design of facilities optimized for navigation of people or vehicles, to movement strategy evaluation such as designing and validating infiltration or evacuation plans. This project will provide new critical capabilities to such applications. In a tactical scenario, confidence on the optimality of the computed metrics with respect to a given problem definition will lead to accurate situational awareness and ultimately to improved support for decision taking. In conjunction with real-time multi-agent simulations the proposed techniques will lead to powerful tools grounded on optimal metrics in support to a number of applications. Overall the proposed work has three main objectives: 1) to develop novel methods based on GPU programming for computing new types of path planning queries with optimality guarantees, 2) to globally visualize optimal navigation information and strategies in given environments, and 3) to apply the developed methods for achieving new multi-agent simulations relying on the selection of optimal paths and thus producing simulation results grounded on well-defined metrics.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 11, 2018
- Source ID
- W911NF1710463
Entities
People
- Marcelo Kallmann
Organizations
- Army Contracting Command
- United States Army
- University of California