The Multi-Objective Shortest-Path (MOS) problem finds a set of Pareto-optimal solutions from a start node to a destination node in a multi-attribute graph.The literature explores multi-objective A*-style algorithmic approaches to solving the NP-hard MOS problem.These approaches use consistent heuristics to compute an exact set of solutions for the goal node.A generalized MOS algorithm maintains a "frontier" of partial paths at each node and performs ordered processing to ensure that Pareto-optimal paths are generated to reach the goal node.The algorithm becomes computationally intractable at a higher number of objectives due to a rapid increase in the search space for non-dominated paths and the significant increase in Pareto-optimal solutions.While prior works have focused on algorithmic methods to reduce the complexity, we tackle this challenge by exploiting parallelism to accelerate the MOS problem.The key insight is that MOS algorithms rely on the ordered execution of partial paths to maintain high work efficiency.The proposed parallel algorithm (OPMOS) unlocks ordered parallelism and efficiently exploits the concurrent execution of multiple paths in MOS.Experimental evaluation using the NVIDIA GH200 Superchip's 72-core Arm-based CPU shows the performance scaling potential of OPMOS on work efficiency and parallelism using a real-world application to ship routing.

Planning ship routes that take into account meteorological and oceanographic conditions is a salient problem for both commercial and Naval applications. The A* algorithm is a very common method for finding the minimum cost path in a graph. Finding appropriate heuristics for a cost function is critical to the computational efficiency and memory requirements of the A* algorithm. We propose heuristic evaluation functions (HEFs) based on the minimum, mean, median, and mode of the cost function values over the reachable nodes given time constraints. Only the HEF based on the minimum is admissible, but we show that the other heuristics are able to find near-optimal solutions in substantially shorter times than the Dijkstra's algorithm, which does not use a heuristic. We evaluate these heuristics over many scenarios and show that overall the HEF based on the mean value performs the best. This HEF can be used in time-critical applications where an occasional loss of optimality is sacrificed for faster run time, such as real-time planning and control, or as part of a multi-objective shortest path algorithm for planning and execution.

This work formalizes the Route Planning Problem (RPP), wherein a set of distributed assets (e.g., ships, submarines, unmanned systems) simultaneously plan routes to optimize a team goal (e.g., find the location of an unknown threat or object in minimum time and/or fuel consumption) while ensuring that the planned routes satisfy certain constraints (e.g., avoiding collisions and obstacles). This problem becomes overwhelmingly complex for multiple distributed assets as the search space grows exponentially to design such plans. The RPP is formalized as a Team Discrete Markov Decision Process (TDMDP) and we propose a Multi-agent Multi-objective Reinforcement Learning (MaMoRL) framework for solving it. We investigate challenges in deploying the solution in real-world settings and study approximation opportunities. We experimentally demonstrate MaMoRL's effectiveness on multiple real-world and synthetic grids, as well as for transfer learning. MaMoRL is deployed for use by the Naval Research Laboratory - Marine Meteorology Division (NRL-MMD), Monterey, CA.

Routing in uncertain environments is challenging as it involves a number of contextual elements, such as different environmental conditions (forecast realizations with varying spatial and temporal uncertainty), changes in mission goals while en route, and asset status. In this paper, we use an approximate dynamic programming method with Q-factors to determine a cost-to-go approximation by treating the weather forecast realization information as a stochastic state. These types of algorithms take a large amount of offline computation time to determine the cost-to-go approximation, but once obtained, the online route recommendation is nearly instantaneous and several orders of magnitude faster than previously proposed ship routing algorithms. The proposed algorithm is robust to the uncertainty present in the weather forecasts. We compare this algorithm to a well-known shortest path algorithm and apply the approach to a real-world shipping tragedy using weather forecast realizations available prior to the event.