The Multi-Objective Shortest Path (MOS) problem finds a set of unique Pareto-optimal paths from a source to a destination in a multi-attribute graph. This NP-hard problem exhibits exponential complexity growth with increasing objectives, rendering exact solutions computationally intractable. This paper presents MPMOS, the first GPU-accelerated architecture for exact MOS computation, addressing three key challenges: irregular label processing, unpredictable memory requirements that exceed static limits, and maintaining correctness under massive parallelism. Our contributions include: (1) concurrent extraction and processing of lexicographically ordered labels, (2) work-aware label distribution, (3) label-level vectorization with objective-aware dominance and pruning checks, (4) smart compaction to eliminate fragmentation in data structures, and (5) dynamic memory allocation enabling scalability to an increasing number of objectives. Experimental evaluation on NVIDIA GH200 across real-world maritime vessel routing and road network graphs shows MPMOS achieves an order of magnitude geometric mean speedup over a CPU parallel MOS, and two orders of magnitude over a state-of-the-art sequential MOS algorithm with exact Pareto-optimality maintained. The dynamic memory allocator enables GPU acceleration for exact multi-objective optimization at unprecedented computational scales.

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.

Anti-submarine warfare (ASW) missions are the linchpin of maritime operations involving effective allocation and path planning of scarce assets to search for, detect, classify, track, and prosecute hostile submarines within a dynamic and uncertain mission environment. Motivated by the need to assist ASW commanders to make better decisions within an evolving mission context, we investigate a moving target search problem with multiple searchers and develop a context-driven decision support tool for the ASW mission planning problem. Given the spatial probability distribution of a target submarine, sensor detection probability surfaces from meteorological and oceanographic products, and the risk to the fleet as a function of distance of the target from the fleet, we model and formulate the ASW asset allocation and search path planning problem using a hidden Markov modeling framework. We propose a two phase approach to solve this NP-hard problem. In phase I, we partition the geographic area, satisfying contiguity constraints, into search regions using an evolutionary algorithm (EA) coupled with a Voronoi tessellation approach, and allocate the assets to partitioned search areas using the auction algorithm. In phase II, we construct a dynamic search plan for each asset over the search interval using EA. We evaluate our approach via a hypothetical ASW scenario to monitor an enemy submarine in a geographic region via multiple assets. We compare our results to various search path planning strategies that, using the context-driven decision support tool developed here, revise the search regions at periodic intervals given a fixed total search time.

This paper validates two approximate dynamic programming approaches on a maritime interdiction problem involving the allocation of multiple heterogeneous assets over a large area of responsibility to interdict multiple drug smugglers using heterogeneous types of transportation on the sea with varying contraband weights. The asset allocation is based on a probability of activity surface, which represents spatio-temporal target activity obtained by integrating intelligence data on drug smuggler whereabouts/waypoints for contraband transportation, behavior models, and meteorological and oceanographic information. We validate the proposed architectural and algorithmic concepts via several realistic mission scenarios. We conduct sensitivity analyses to quantify the robustness and proactivity of our approach, as well as to measure the value of information used in the allocation process. The contributions of this paper have been transitioned to and are currently being tested by Joint Interagency Task Force-South, an organization tasked with providing the initial line of defense against drug trafficking in the East Pacific and Caribbean Oceans.

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.

This paper presents a mixed-initiative tool for multiobjective planning and asset routing (TMPLAR) in dynamic and uncertain environments. TMPLAR is built upon multiobjective dynamic programming algorithms to route assets in a timely fashion, while considering fuel efficiency, voyage time, distance, and adherence to real world constraints (asset vehicle limits, navigator-specified deadlines, etc.). TMPLAR has the potential to be applied in a variety of contexts, including ship, helicopter, or unmanned aerial vehicle routing. The tool provides recommended schedules, consisting of waypoints, associated arrival and departure times, asset speed and bearing, that are optimized with respect to several objectives. The ship navigation is exacerbated by the need to address multiple conflicting objectives, spatial and temporal uncertainty associated with the weather, multiple constraints on asset operation, and the added capability of waiting at a waypoint with the intent to avoid bad weather, conduct opportunistic training drills, or both. The key algorithmic contribution is a multiobjective shortest path algorithm for networks with stochastic nonconvex edge costs and the following problem features: 1) time windows on nodes; 2) ability to choose vessel speed to next node subject to (minimum and/or maximum) speed constraints; 3) ability to select the power plant configuration at each node; and 4) ability to wait at a node. The algorithm is demonstrated on six real world routing scenarios by comparing its performance against an existing operational routing algorithm.

Counter-smuggling operations constitute a high priority national security mission since drug-trafficking not only involves many criminals, but can also be a source of financing for many illicit activities such as narco-terrorism and arms trafficking. The counter-smuggling mission involves surveillance operations (to search, detect, track and identify potential threats) and interdiction operations (to intercept, investigate and potentially apprehend suspects). Potential smuggling activity is represented in the form of color-coded heat maps built using intelligence and meteorological and oceanographic information, which are interpreted in the form of probability of activity (PoA) surfaces. The PoA surfaces constitute the “sufficient statistics” for the asset allocation and scheduling processes. However, in the case of disconnected, intermittent, and low-bandwidth environments, the problem of allocating resources becomes very challenging as PoA information is unavailable or is not up to date. In this paper, we propose to utilize flow (historic PoA)-based surfaces, which provide cues on where the smugglers may have traversed in the past. Using the flow surfaces, we allocate the surveillance and interdiction assets to best thwart potential smuggling activities. We further evaluate the quality of our solution in terms of the number of targets interdicted and the amount of contraband seized.

Anti-Submarine Warfare (ASW) involves effective allocation and path planning of ASW platforms to search for, detect, classify, track and prosecute hostile submarines within an evolving environment. As the environmental context evolves rapidly, continuously collected Meteorological and Oceanographic (METOC) data is used for assessing the impact of the current and forecasted environment on individual sensors and weapon platforms, as well as on tactics in the form of performance surfaces, which is presented to the commanders in making go/no-go decisions. However, due to the overwhelming amount of METOC information, it is very challenging for the commanders to interpret and analyze the data for generating plans or evaluating courses of action in a timely manner. In this paper, motivated by the need to assist ASW commanders in making proactive decisions in an evolving environmental context, we present a decision support tool for modeling and incorporating the appropriate METOC information from multiple sources and further utilizing it to determine the search regions and optimal trajectories to search for and track the enemy submarines in a timely manner.

Motivated by the Navy's interest in decision support tools that augment planning activities within a maritime operations center (MOC), we have developed a multilevel resource allocation model that is capable of interacting with human planners to dynamically allocate hierarchically-organized assets to process interdependent tasks in order to accomplish mission objectives. The planning problem is formulated as a mixed-integer nonlinear programming (MINLP) problem of minimizing the overall difference between the human-specified desired task accuracy performance criteria and the expected performance outcomes, the latter being based on how well the assigned resources match the required resources, subject to a number of real-world planning constraints. To solve the resulting large-scale MINLP problem, we propose two methods: 1) a Lagrangian relaxation method that solves the multilevel asset allocation problem with a measure of sub-optimality in terms of an approximate duality gap and 2) a dynamic list planning heuristic algorithm that provides high-quality sub-optimal solutions rapidly (less than 10 s for the scenarios considered here). Finally, we verify our methods using realistic MOC planning scenarios, provide a comparative evaluation of the performance measures of the two proposed methods, and investigate the value of information via human-in-the-loop experiments.