Search planning for UUV missions involves a complex optimization problem over multiple degrees of freedom. The detection performance of individual searches is governed by the local environment and the sensor settings that determine the rate at which target objects of interest can be identified. This paper addresses some of the computational aspects of collaborative search planning when multiple search agents seek to find hidden objects (i.e. mines) in adverse local operating environments where the detection process is prone to false alarms. For these conditions, we apply a receiver operator characteristic (ROC) analysis to model detection performance and develop a Bayesian risk objective that enumerates the required number of detections for validation as part of the modeling paradigm. In this paper we consider an expanded optimization process whereby ROC operating points are optimized simultaneously for all validation criteria with the best performing combinations selected. Details of its application within a broader search planning context are discussed. An analysis of this optimization process is presented. Numerical results are provided to demonstrate the effectiveness of the approach.
We describe a problem of optimal planning for unmanned vehicles and illustrate two distinct procedures for its solution. The problem under consideration, which we refer to as the search tour problem, involves the determination of multi-stage plans for unmanned vehicles conducting search operations. These types of problems are important in situations where the searcher has varying performance in diﬀerent regions throughout the domain due to environmental complexity. The ability to provide robust planning for unmanned systems under diﬃcult environmental conditions is critical for their use in search operations. The problem we consider consists of searches with variable times for each of the stages, as well as an additional degree of freedom for each stage to select from one of a ﬁnite set of operational conﬁgurations. As each combination of conﬁguration and stage time leads to a diﬀerent performance level, there is a need to determine the optimal conﬁguration of these stages. When the complexity of constraints on total time, as well as resources expended at each stage for a given conﬁguration, are added, the problem becomes one of non-trivial search eﬀort allocation and numerical methods of optimization are required. We show two solution approaches for this numerical optimization problem. The ﬁrst solution technique is to use a mixed-integer linear programming formulation, for which commercially available solvers can ﬁnd optimal solutions in a reasonable amount of time. We use this solution as a baseline and compare against a new inner/outer optimization formulation. This inner/outer optimization compares favorably to the baseline solution, but is also amenable to adaptation as the search operation progresses. Numerical examples illustrate the utility of the approach for unmanned vehicle search planning.
This paper addresses selected computational aspects of collaborative search planning when multiple search agents seek to find hidden objects (i.e. mines) in operating environments where the detection process is prone to false alarms. A Receiver Operator Characteristic (ROC) analysis is applied to construct a Bayesian cost objective function that weighs and combines missed detection and false alarm probabilities. It is shown that for fixed ROC operating points and a validation criterion consisting of a prerequisite number of detection outcomes, an interval exists in the number of conducted search passes over which the risk objective function is supermodular. We show that this property is not retained beyond validation criterion boundaries. We investigate the use of greedy algorithms for distributing search effort and, in particular, examine the double greedy algorithm for its applicability under conditions of varying criteria. Numerical results are provided to demonstrate the effectiveness of the approach.
This paper addresses the planning of multiple collaborative searchers that are seeking to find hidden objects (i.e. mines) in environments where the sensor detection process is prone to false alarms. In such situations it is anticipated that collaboration between searchers that are examining the same sub-regions may be used to mitigate the impact of false alarms. A standard Receiver Operator Characteristic (ROC) analysis is conducted and the mapping between a single search pass ROC curve and an equivalent multiple search pass representation within a cumulative probability space is discussed. This mapping produces an analogous family of ROC curves for an increasing number of search passes using either a first detection or multiple occurrence performance criteria. The migration of ROC operating points is analyzed as additional search passes are included within a search plan and suggests the need to coordinate search effort with operating point selection. The mapping from waiting time event probabilities to a total error performance criterion weighted according to the cumulative probabilities of missed detection and false alarm is developed. Details of its application for threshold optimization within search planning is discussed and numerical results are provided to demonstrate the usefulness of the models in evaluating performance trade-offs.
Particle filters represent the current state of the art in nonlinear, non-Gaussian filtering. They are easy to implement and have been applied in numerous domains. That being said, particle filters can be impractical for problems with state dimensions greater than four, if some other problem specific efficiencies can’t be identified. This “curse of dimensionality” makes particle filters a computationally burdensome approach, and the associated re-sampling makes parallel processing difficult. In the past several years an alternative to particle filters dubbed particle flows has emerged as a (potentially) much more efficient method to solving non-linear, non-Gaussian problems. Particle flow filtering (unlike particle filtering) is a deterministic approach, however, its implementation entails solving an under-determined system of partial differential equations which has infinitely many potential solutions. In this work we apply the filters to angles-only target motion analysis problems in order to quantify the (if any) computational gains over standard particle filtering approaches. In particular we focus on the simplest form of particle flow filter, known as the exact particle flow filter. This form assumes a Gaussian prior and likelihood function of the unknown target states and is then linearized as is standard practice for extended Kalman filters. We implement both particle filters and particle flows and perform numerous numerical experiments for comparison.
When unmanned distributed sensor fields are developed for rapid deployment in hostile areas, the deployment
may consist of multiple sensor types. This occurs because of the variations in expected threats and uncertainties
about the details of the local environmental conditions. As more detailed information is available at deployment,
the quantity and types of sensors are given and fixed, yet the specific pattern for the configuration of their
deployment is still variable. We develop a new optimization approach for planning these configurations for this
resource constrained sensor application. Our approach takes into account the variety of sensors available and
their respective expected performance in the environment, as well as the target uncertainty. Due to the large
dimensionality of the design space for this unmanned sensor planning problem, heuristic-based optimizations will
provide very sub-optimal solutions and gradient-based methods lack a good quality initialization. Instead, we
utilize a robust optimization procedure that combines genetic algorithms with nonlinear programming techniques
to create numerical solutions for determining the optimal spatial distribution of sensing effort for each type of
sensor. We illustrate the effectiveness of the approach on numerical examples, and also illustrate the qualitative
difference in the optimal patterns as a function of the relative numbers of available sensors of each type. We
conclude by using the optimization results to discuss the benefits of interspersing the different sensor types, as
opposed to creating area sub-segmentations for each type.
This paper presents a hybrid approximate dynamic programming (ADP) method for a hybrid dynamic system
(HDS) optimal control problem, that occurs in many complex unmanned systems which are implemented via a
hybrid architecture, regarding robot modes or the complex environment. The HDS considered in this paper is
characterized by a well-known three-layer hybrid framework, which includes a discrete event controller layer, a
discrete-continuous interface layer, and a continuous state layer. The hybrid optimal control problem (HOCP)
is to nd the optimal discrete event decisions and the optimal continuous controls subject to a deterministic
minimization of a scalar function regarding the system state and control over time. Due to the uncertainty
of environment and complexity of the HOCP, the cost-to-go cannot be evaluated before the HDS explores the
entire system state space; as a result, the optimal control, neither continuous nor discrete, is not available ahead
of time. Therefore, ADP is adopted to learn the optimal control while the HDS is exploring the environment,
because of the online advantage of ADP method. Furthermore, ADP can break the curses of dimensionality
which other optimizing methods, such as dynamic programming (DP) and Markov decision process (MDP), are
facing due to the high dimensions of HOCP.
This paper presents a discussion of U.S. naval mine countermeasures (MCM) theory modernization in light of
advances in the areas of autonomy, tactics, and sensor processing. The unifying theme spanning these research areas
concerns the capability for in situ adaptation of processing algorithms, plans, and vehicle behaviors enabled through
run-time situation assessment and performance estimation. Independently, each of these technology developments
impact the MCM Measures of Effectiveness1 [MOE(s)] of time and risk by improving one or more associated
Measures of Performance2 [MOP(s)]; the contribution of this paper is to outline an integrated strategy for realizing
the cumulative benefits of these technology enablers to the United States Navy's minehunting capability. An
introduction to the MCM problem is provided to frame the importance of the foundational research and the
ramifications of the proposed strategy on the MIW community. We then include an overview of current and future
adaptive capability research in the aforementioned areas, highlighting a departure from the existing rigid
assumption-based approaches while identifying anticipated technology acceptance issues. Consequently, the paper
describes an incremental strategy for transitioning from the current minehunting paradigm where tactical decision
aids rely on a priori intelligence and there is little to no in situ adaptation or feedback to a future vision where
unmanned systems3, equipped with a representation of the commander's intent, are afforded the authority and ability
to adapt to environmental perturbations with minimal human-in-the-loop supervision. The discussion concludes with
an articulation of the science and technology issues which the MCM research community must continue to address.
We illustrate an approach for adapting the configuration of surveillance-based distributed sensor fields. By using a robust method of centralized adaptation of the field configuration, the performance of distributed sensor fields can be greatly extended. In this paper, we use the concept of Pareto optimality (that is, the achievement of desired tradeoffs between competing objectives) as a mechanism for describing the intent of the original deployment. We illustrate a computational approach to adaptation of the field configuration, provide numerical examples, and provide an analysis of the stability properties.
The performance of a distributed sensor field that seeks to achieve surveillance coverage against moving targets is
tied to many different constraints and competing objectives. Understanding these tradeoffs is paramount if such
systems are to be efficiently designed and employed. When physically deploying the sensor field, the placement
of sensors in specific patterns can tremendously alter the system's performance relative to these tradeoffs. Given
a robust parameterization of the field configuration, the tradeoffs manifest themselves as boundaries in the space
of achievable parameter combinations under the system's constraints. In this paper, we utilize a numerical
Pareto optimization approach to derive explicit tradeoff surfaces for the problem of a cooperative network of
passive sensor nodes, illustrating the tradeoff between improving field-level search performance and decreasing
false searches. We conclude by discussing the impact of these results on the deployment of sensor fields.
In a sparse sensor network, the sensor detection regions are often not overlapped. The traditional
instantaneous detection scheme is less effective due to the fact that targets may not be detected by any
sensors at certain sampling instances. To detect the moving targets in a sparse sensor network, we have
developed a new system suitable for multiple targets detection and tracking. An optimization based random
field estimation method has been developed to characterize spatially distributed sensor reports without
making any assumptions of their underlying statistical distributions. FBMM (Forward & Backward Mapping
Mitigation) technology is developed to reduce the false detections resulted from the random field estimation.
To further reduce the false detections, the refined random field is clustered using gap statistics. STLD (Spatial
& Temporal Layering Discrimination) method is developed to individual clusters and true sensor detections
are determined based on both spatial and temporal patterns. Simulation results have shown that our system
can effectively detect multiple target tracks in a large surveillance region.