Search

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Motivated by the need for multiple agents to collaborate in order to solve a distributed resource allocation planning problem, this paper develops a distributed framework that combines each agent's information, expertise, responsibility, and asset ownership with the goal of optimizing a given mission objective. A mission is a collection of interdependent tasks to be executed in a directed/sequential sequence. Each task is modeled by a vector of resource requirements, a processing time, and a start time (release time). Each agent has a subset of tasks for which it is responsible, and owns a set of heterogeneous assets, where each asset is modeled by a vector of resource capabilities that it provides. Multiple agents must collaboratively allocate assets to tasks to maximize an expected mission performance, defined by how well all of the tasks' requirements are satisfied by the allocated asset capabilities. Our agent-based distributed planning framework uses a blackboard communication paradigm to exchange information among agents. The framework contains an intra-agent and an interagent module that support individual and cooperative planning, respectively. The intra-agent module employs an optimization-based $m$ -best asset allocation algorithm to match an agent's own tasks with its locally owned assets. The interagent module coordinates the exchange of information and asset allocations among agents to improve the local plans using an asset pricing mechanism, and includes a means for characterizing an agent's cooperative behavior. [ABSTRACT FROM AUTHOR]