Discrete search allocation game with false contacts

This paper deals with a two‐person zero‐sum game called a search allocation game, where a searcher and a target participate, taking account of false contacts. The searcher distributes his search effort in a search space in order to detect the target. On the other hand, the target moves to avoid the searcher. As a payoff of the game, we take the cumulative amount of search effort weighted by the target distribution, which can be derived as an approximation of the detection probability of the target. The searcher's strategy is a plan of distributing search effort and the target's is a movement represented by a path or transition probability across the search space. In the search, there are false contacts caused by environmental noises, signal processing noises, or real objects resembling true targets. If they happen, the searcher must take some time for their investigation, which interrupts the search for a while. There have been few researches dealing with search games with false contacts. In this paper, we formulate the game into a mathematical programming problem to obtain its equilibrium point. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Incremental approximation of optimal allocations

This paper concerns the approximation of optimal allocations by δ allocations. δ allocations are obtained by fixing an increment δ of effort and deciding at each step upon a single cell in which to allocate the entire increment. It is shown that δ allocations may be used as a simple method of approximating optimal allocations of effort resulting from constrained separable optimization problems involving a finite number of cells. The results are applied to find δ allocations (called δ plans) which approximate optimal search plans. δ plans have the property that as δ → 0, the mean time to find the target using a δ plan approaches the mean time when using the optimal plan. δ plans have the advantage that. they are easily computed and more easily realized in practice than optimal plans which tend to be difficult to calculate and to call for spreading impractically small amounts of effort over large areas.     

Minimax resource allocation problems with ordering constraints

Resource allocation problems consider the allocation of limited resources among numerous competing activities. We address an allocation problem with multiple knapsack resource constraints. The activities are grouped into disjoint sets. Ordering constraints are imposed on the activities within each set, so that the level of one activity cannot exceed the level of another activity in the same set. The objective function is of the minimax type and each performance function is a nonlinear, strictly decreasing and continuous function of a single variable. Applications for such resource allocation problems are found, for example, in high-tech industries confronted with large-scale and complex production planning problems. We present two algorithms to solve the allocation problem with ordering constraints. The first one uses characterization of the optimal decision variables to apply a search method. The second algorithm solves a sequence of problems, each in the format of the original problem without ordering constraints. Whereas the computational effort of the first algorithm depends on the desired degree of accuracy even for linear performance functions, the effort of the latter algorithm is polynomial for certain classes of performance functions. © 1994 John Wiley & Sons, Inc.     

Optimal search plan minimizing the expected risk of the search for a target with conditionally deterministic motion

This article deals with a search problem for a moving target with a rather simple type of motion called factorable conditionally deterministic. A search plan is characterized by (ϕ, T), the elements of which specify how to search and when to stop the search, respectively. The problem is to find the optimal search plan which minimizes the expected risk (the expected search cost minus the expected reward). We obtain conditions for the optimal search plan, and applying the theorems, we derive the optimal search plan in a closed form for the case in which the target moves straight from a fixed point selecting his course and speed randomly.     

LFM脉冲雷达距离维快速搜索处理算法

针对脉冲雷达近距离目标遮挡问题,从理论上分析了雷达最小作用距离不受限于脉冲宽度.在此基础上,以Chirp脉冲为例,提出了一种适合远近距离全程目标的快速搜索处理算法.该算法只需发射一种宽脉冲波形,而不必根据距离的变化改变脉宽,从而有效缩短了搜索时间,大大提高了搜索效率.仿真结果表明了理论分析的正确性和算法的有效性.     

Total optimality of incrementally optimal allocations

This paper considers the problem of finding optimal solutions to a class of separable constrained extremal problems involving nonlinear functionals. The results are proved for rather general situations, but they may be easily stated for the case of search for a stationary object whose a priori location distribution is given by a density function on R, a subset of Euclidean n-space. The functional to be optimized in this case is the probability of detection and the constraint is on the amount of effort to be used Suppose that a search of the above type is conducted in such a manner as to produce the maximum increase in probability of detection for each increment of effort added to the search. Then under very weak assumptions, it is proven that this search will produce an optimal allocation of the total effort involved. Under some additional assumptions, it is shown that any amount of search effort may be allocated in an optimal fashion.     

A search game taking account of attributes of searching resources

This article deals with a two‐person zero‐sum game called a search allocation game (SAG), in which a searcher and a target participate as players. The searcher distributes his searching resources in a search space to detect the target. The effect of resources lasts a certain period of time and extends to some areas at a distance from the resources' dropped points. On the other hand, the target moves around in the search space to evade the searcher. In the history of search games, there has been little research covering the durability and reachability of searching resources. This article proposes two linear programming formulations to solve the SAG with durable and reachable resources, and at the same time provide an optimal strategy of distributing searching resources for the searcher and an optimal moving strategy for the target. Using examples, we will analyze the influences of two attributes of resources on optimal strategies. © 2007 Wiley Periodicals, Inc. Naval Research Logistics 2008     

双站无源定位最佳配置分析

为了提高双站无源定位精度,在全局坐标系下分析了双站纯方位定位系统的最佳配置形式。首先研究了最小GDOP(Geometric Dilution of Precision)意义下的方位角约束关系及最优夹角,得到双站的最佳配置形式是目标与两传感器间呈一确定夹角的等腰三角形;在此基础上,讨论了夹角对GDOP的影响进而提出有效定位区域的概念,指出只有当目标位于该区域内时双站才能获得较好的定位精度。仿真结果验证了上述关于最佳配置形式及有效定位区域的分析,指出该结论可以应用到基于传感器管理的多站无源定位算法中。     

离散搜索力的最优配置模型及增量搜索计划

目前,离散搜索正越来越普遍地应用于各种搜索实践。为了优化搜索过程,提高离散搜索的效率,应用最优搜索理论,导出了待搜目标服从均匀分布、正态分布时离散搜索力的最优配置模型、目标的踪迹预测方法和最优增量搜索计划的求法,并通过实例作了演示,上述结论和方法为离散搜索力如何实施最优搜索提供了一定的理论依据。     

考虑需求相关的可修复系统备件配置模型

对于一个拥有多台相同设备的可修复系统来说,一种备件的需求以及其对应的备件保障方案将影响着系统的可工作设备数量,从而影响着设备其他备件的需求,故假设备件需求相互独立且与系统自身备件保障方案无关而开展备件配置研究是不合理的.在考虑备件需求相关以及备件的保障方案对备件需求的影响的前提下,利用马尔可夫理论描述了备件需求规律,针对不串件拼修和串件拼修两种情况分别给出了可用度的计算方法,并在此基础上以备件配置费用作为优化目标,以可用度作为约束构建备件优化配置模型,给出了边际分析求解模型的方法.通过案例分析,验证了模型的正确性.     

The discrete search problem and the construction of optimal allocations

Suppose one object is hidden in the k-th of n boxes with probability p(k). The boxes are to be searched sequentially. Associated with the j-th search of box k is a cost c(j,k) and a conditional probability q(j,k) that the first j - 1 searches of box k are unsuccessful while the j-th search is successful given that the object is hidden in box k. The problem is to maximize the probability that we find the object if we are not allowed to offer more than L for the search. We prove the existence of an optimal allocation of the search effort L and state an algorithm for the construction of an optimal allocation. Finally, we discuss some problems concerning the complexity of our problem.     

Multiperiod resource allocation with a smoothing objective

We consider a multiperiod resource allocation problem, where a single resource is allocated over a finite planning horizon of T periods. Resource allocated to one period can be used to satisfy demand of that period or of future periods, but backordering of demand is not allowed. The objective is to allocate the resource as smoothly as possible throughout the planning horizon. We present two models: the first assumes that the allocation decision variables are continuous, whereas the second considers only integer allocations. Applications for such models are found, for example, in subassembly production planning for complex products in a multistage production environment. Efficient algorithms are presented to find optimal allocations for these models at an effort of O(T²). Among all optimal policies for each model, these algorithms find the one that carries the least excess resources throughout the planning horizon. © 1995 John Wiley & Sons, Inc.     

The United States Coast Guard Computer-Assisted Search Planning system (CASP)

This paper provides an overview of the Computer-Assisted Search Planning (CASP) system developed for the United States Coast Guard. The CASP information processing methodology is based upon Monte Carlo simulation to obtain an initial probability distribution for target location and to update this distribution to account for drift due to currents and winds. A multiple scenario approach is employed to generate the initial probability distribution. Bayesian updating is used to reflect negative information obtained from unsuccessful search. The principal output of the CASP system is a sequence of probability “maps” which display the current target location probability distributions throughout the time period of interest. CASP also provides guidance for allocating search effort based upon optimal search theory.     

异步雷达组网协同跟踪动态传感器分配算法

针对异步雷达组网下的协同跟踪问题提出了一种基于异步顺序融合的动态传感器分配算法。该算法对异步雷达的量测值按采样时刻顺序滤波,根据滤波协方差和目标期望协方差的接近程度动态选择下一时刻跟踪的最优传感器集合。仿真分析表明该算法和基于伪量测的异步雷达组网协同跟踪传感器分配算法相比具有较少的计算量和较高的目标跟踪精度。     

Optimal strategies for problems of simultaneous attack against an area defense with impact-point prediction

An area to be defended consists of separated point targets. These targets are subject to an attack in which the offensive weapons are assumed to arrive simultaneously. The defense has area defenders, each of which is capable of intercepting any attacker'. Furthermore, the defense has impact-point prediction, i.e., it has knowledge of each attacker's intended target prior to allocation of the area interceptors. For a given attack, the defense wishes to allocate its interceptors against attackers so as to maximize the expected total survival value of the targets. In its first move, the offense seeks an attack allocation which will minimize expected total surviving value against best defense. We develop an algorithm to determine optimal attack and defense strategies and the optimal value of this sequential min-max problem. Branch-and-bound techniques are used to obtain integer solutions, and illustrative computational results are provided.     

Planning accelerated life tests for censored two‐parameter exponential distributions

We consider optimal test plans involving life distributions with failure‐free life, i.e., where there is an unknown threshold parameter below which no failure will occur. These distributions do not satisfy the regularity conditions and thus the usual approach of using the Fisher information matrix to obtain an optimal accelerated life testing (ALT) plan cannot be applied. In this paper, we assume that lifetime follows a two‐parameter exponential distribution and the stress‐life relationship is given by the inverse power law model. Near‐optimal test plans for constant‐stress ALT under both failure‐censoring and time‐censoring are obtained. We first obtain unbiased estimates for the parameters and give the approximate variance of these estimates for both failure‐censored and time‐censored data. Using these results, the variance for the approximate unbiased estimate of a percentile at a design stress is computed and then minimized to produce the near‐optimal plan. Finally, a numerical example is presented together with simulation results to study the accuracy of the approximate variance given by the proposed plan and show that it outperforms the equal‐allocation plan. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 169–186, 1999     

Optimal search for a Markovian target

This article is concerned with an optimal search method for detecting a randomly moving target whose dynamics are described by a stochastic differential equation. The key notions are formulating the problem as one of optimal control and establishing the searcher's strategy by finding the control signal minimizing the probability that the searcher fails to detect the target. The search equation and the search function are derived, and sufficient conditions are given for the existence of an optimal search control. Finally, in order to circumvent difficulties arising in the realization of the optimal search algorithm, a successive approximation is presented with simulation studies.     

目标搜索的预测分析及搜索计划的优化逼近

给出了目标搜索的预测分析公式,提出了最优搜索计划的一种优化逼近方法及有关实例     

舰载无人机光电载荷对海搜索方式与搜索宽度

搜索方式与搜索宽度是舰载无人机对海搜索效率与搜索力配置研究的基础。基于舰载无人机及其光电载荷的性能特点,提出了舰载无人机对海搜索的七种基本搜索方式,并从不同的角度对舰载无人机对海搜索方式进行了分类,给出了搜索方式的选择方法;建立了舰载无人机光电载荷搜索宽度计算模型,为舰载无人机系统采用不同的搜索方式进行搜索时计算其搜索效率和搜索力的配置提供了决策依据。     

战役野战油库油料输送力量优化分配研究

如何科学、合理分配战役野战油库油料输送力量是战时油料保障必须面临的一个实际问题。首先根据战役野战油库运油车分配模型得到一个运油车初始分配方案,然后运用计算机模拟技术对分配方案进行模拟,并根据模拟结果不断调整,直至得到优化的分配方案,为制定战役野战油库油料输送计划提供决策依据。