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     

搜索路径给定时的搜索对策问题及其应用

搜索路径给定时的最优搜索方案问题,也可以理解为是关于搜索者和目标的二人对策问题,主要讨论了当搜索路径给定时的单个搜索者和单个目标的搜索对策问题。首先根据问题的特点,利用动态规划和迭代的方法,确定关于目标逃逸路径混合策略的最优分区,证明该分区是多面体凸集;针对目标不同逃逸路径的分区,求出搜索者的最大期望收益,再将问题转化为二人有限零和对策,计算出搜索者的支付矩阵,确定最优搜索策略。最后结合海军护航行动,对我舰载直升机搜索小型海盗船进行分析和计算,说明搜索路径给定时的最优搜索对策对于双方的资源分配和提高搜索效率具有一定的应用价值。     

A cooperative game in search theory

Search theory originates from the military research efforts of WWII. Most researchers of that period modeled their search games in noncooperative games, where players are enemies or compete against each other. In this article, we deal with a cooperative search game, where multiple searchers behave cooperatively. First we describe several search problems and discuss the possibility of a coalition or cooperation among searchers. For the cooperative search game, we define a function named quasi‐characteristic function, which gives us a criterion similar to the so‐called characteristic function in the general coalition game with transferable utility. The search operation includes a kind of randomness with respect to whether the searchers can detect a target and get the value of the target. We also propose a methodology to divide the obtained target value among members of the coalition taking account of the randomness. As a concrete problem of the cooperative search game, we take the so‐called search allocation game, where searchers distribute their searching resources to detect a target in a cooperative way and the target moves in a search space to evade the searchers. Lastly, we discuss the core of the cooperative search allocation game. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

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     

军事云环境下基于动态博弈的资源调度方法

针对军事云环境下联合指挥资源调度优化问题,综合考虑了多部队任务需求,多目标优化,多部队资源竞争等约束条件,运用动态博弈理论及方法,建立并提出了一种基于完全信息扩展博弈的资源调度模型及方法,提高了资源调度效率,兼顾了多部队利益,增加了联合作战效益。最后通过实验验证了其有效性及准确性。     

Non‐zero‐sum nonlinear network path interdiction with an application to inspection in terror networks

A simultaneous non‐zero‐sum game is modeled to extend the classical network interdiction problem. In this model, an interdictor (e.g., an enforcement agent) decides how much of an inspection resource to spend along each arc in the network to capture a smuggler. The smuggler (randomly) selects a commodity to smuggle—a source and destination pair of nodes, and also a corresponding path for traveling between the given pair of nodes. This model is motivated by a terrorist organization that can mobilize its human, financial, or weapon resources to carry out an attack at one of several potential target destinations. The probability of evading each of the network arcs nonlinearly decreases in the amount of resource that the interdictor spends on its inspection. We show that under reasonable assumptions with respect to the evasion probability functions, (approximate) Nash equilibria of this game can be determined in polynomial time; depending on whether the evasion functions are exponential or general logarithmically‐convex functions, exact Nash equilibria or approximate Nash equilibria, respectively, are computed. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 139–153, 2017     

Technical note: Find a hidden “treasure”

This paper deals with a two searchers game and it investigates the problem of how the possibility of finding a hidden object simultaneously by players influences their behavior. Namely, we consider the following two‐sided allocation non‐zero‐sum game on an integer interval [1,n]. Two teams (Player 1 and 2) want to find an immobile object (say, a treasure) hidden at one of n points. Each point i ∈ [1,n] is characterized by a detection parameter λ_i (μ_i) for Player 1 (Player 2) such that p_i(1 ? exp(?λ_ix_i)) (p_i(1 ? exp(?μ_iy_i))) is the probability that Player 1 (Player 2) discovers the hidden object with amount of search effort x_i (y_i) applied at point i where p_i ∈ (0,1) is the probability that the object is hidden at point i. Player 1 (Player 2) undertakes the search by allocating the total amount of effort X(Y). The payoff for Player 1 (Player 2) is 1 if he detects the object but his opponent does not. If both players detect the object they can share it proportionally and even can pay some share to an umpire who takes care that the players do not cheat each other, namely Player 1 gets q₁ and Player 2 gets q₂ where q₁ + q₂ ≤ 1. The Nash equilibrium of this game is found and numerical examples are given. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

军事攻防中的多属性资源分配对策模型

针对资源受限情形下的两阶段攻防资源分配问题,提出一种基于多属性决策的资源分配对策模型。防守者首先将有限的防护资源分配到不同的目标上,继而进攻者选择一种威胁组合方式对目标实施打击。基于博弈论相关知识,模型的求解结果可以使防守者最小化自身损失,使进攻者最大化进攻收益。同时,针对模型的特点,给出了一些推论和证明。通过一个示例验证了模型的合理性以及相关推论的准确性,能够为攻、防双方规划决策提供辅助支持。     

基于协商的Agent资源冲突消解算法研究

针对分布式规划系统中Agent计划的资源冲突问题,研究了资源冲突的分类;基于Agent协商理论,从资源最优配置的角度,论证了最优的协商策略,提出了可重复利用的不可分享型资源的冲突消解算法,较好地解决了Agent分布式规划中出现的一类资源冲突问题。算例表明,给出的冲突消解算法是有效的。     

On valuing appreciating human assets in services

This paper derives optimal policies for when to hire, train, and lay off employees in service organizations when worker productivity appreciates deterministically or stochastically under constant, monotonic, and cyclic service demand. The model, an extension of the machine replacement problem from the engineering economy literature, uses infinite horizon linear programming to produce optimal personnel planning strategies and dual prices that characterize the workforce's economic value. The effect of employee attrition is also considered. In its valuation of human assets, unlike pure accounting approaches that only try to measure, this paper proposes an approach to capture the interaction between firm decisions pertaining to human resources and human resource value. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A specially structured nonlinear integer resource allocation problem

We present an algorithm for solving a specially structured nonlinear integer resource allocation problem. This problem was motivated by a capacity planning study done at a large Health Maintenance Organization in Texas. Specifically, we focus on a class of nonlinear resource allocation problems that involve the minimization of a convex function over one general convex constraint, a set of block diagonal convex constraints, and bounds on the integer variables. The continuous variable problem is also considered. The continuous problem is solved by taking advantage of the structure of the Karush‐Kuhn‐Tucker (KKT) conditions. This method for solving the continuous problem is then incorporated in a branch and bound algorithm to solve the integer problem. Various reoptimization results, multiplier bounding results, and heuristics are used to improve the efficiency of the algorithms. We show how the algorithms can be extended to obtain a globally optimal solution to the nonconvex version of the problem. We further show that the methods can be applied to problems in production planning and financial optimization. Extensive computational testing of the algorithms is reported for a variety of applications on continuous problems with up to 1,000,000 variables and integer problems with up to 1000 variables. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 770–792, 2003.     

装甲装备车务管理信息资源规划

针对装甲装备车务管理信息化建设过程中,出现的数据环境不适应信息化发展的问题,分析了造成数据环境混乱,形成信息孤岛的原因,提出了用信息资源规划的思想和技术对数据环境进行改造,建立车务管理的功能模型、数据模型和数据管理的基础标准,实现信息共享的方案,解决了车务管理信息化建设过程中的信息孤岛问题,为实现车务管理信息化的跨越式发展奠定了基础.     

Detection of a Markovian target with optimization of the search efforts under generalized linear constraints

This paper deals with search for a target following a Markovian movement or a conditionally deterministic motion. The problem is to allocate the search efforts, when search resources renew with generalized linear constraints. The model obtained is extended to resource mixing management. New optimality equations of de Guenin's style are obtained. Practically, the problem is solved by using an algorithm derived from the FAB method. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 117–142, 2002; DOI 10.1002/nav.10009     

支持并行工程的造船分段作业计划系统

针对传统造船模式下,车间作业计划与工艺设计串行工作方式的缺点,基于并行工程的原理,提出了分段作业计划与工艺设计的集成运行模式,为实现造船CAPP系统与PPC系统的集成化和并行化提供了实现的基础。针对集成模式的特点,建立了分段作业计划系统资源优化的数学模型,应用遗传算法解决了针对任意分段装配工艺方案的多资源平衡优化问题,可以得到每项作业最优的开工时间,同时能够给出多种资源的最优分布结果,满足了多工艺方案之间资源利用率的比较。最后,给出了计算实例,计算机模拟结果说明了这一方法的有效性。     

VNS和SA相结合的指挥控制资源部署

针对指挥控制资源部署问题,引入任务复杂度来定义决策实体的工作负载,并建立以最小化决策实体工作负载的均方根为目标的优化模型。针对传统的层次聚类法容易陷入局部最优,提出了一种变邻域搜索(Variable Neighborhood Search,VNS)和模拟退火(Simulated Annealing,SA)相结合的具有全局性的求解方法,使用VNS进行全局寻优,使用SA对VNS中的邻域进行局部寻优。最后通过一个联合作战案例的平台调度方案,验证了所提方法的优越性。     

Probabilistic resource pooling games

We study a setting with a single type of resource and with several players, each associated with a single resource (of this type). Unavailability of these resources comes unexpectedly and with player‐specific costs. Players can cooperate by reallocating the available resources to the ones that need the resources most and let those who suffer the least absorb all the costs. We address the cost savings allocation problem with concepts of cooperative game theory. In particular, we formulate a probabilistic resource pooling game and study them on various properties. We show that these games are not necessarily convex, do have non‐empty cores, and are totally balanced. The latter two are shown via an interesting relationship with Böhm‐Bawerk horse market games. Next, we present an intuitive class of allocation rules for which the resulting allocations are core members and study an allocation rule within this class of allocation rules with an appealing fairness property. Finally, we show that our results can be applied to a spare parts pooling situation.     

Continuous accumulation games on discrete locations

In an accumulation game, a HIDER attempts to accumulate a certain number of objects or a certain quantity of material before a certain time, and a SEEKER attempts to prevent this. In a continuous accumulation game the HIDER can pile material either at locations $1, 2, …, n, or over a region in space. The HIDER will win (payoff 1) it if accumulates N units of material before a given time, and the goal of the SEEKER will win (payoff 0) otherwise. We assume the HIDER can place continuous material such as fuel at discrete locations i = 1, 2, …, n, and the game is played in discrete time. At each time k > 0 the HIDER acquires h units of material and can distribute it among all of the locations. At the same time, k, the SEEKER can search a certain number s < n of the locations, and will confiscate (or destroy) all material found. After explicitly describing what we mean by a continuous accumulation game on discrete locations, we prove a theorem that gives a condition under which the HIDER can always win by using a uniform distribution at each stage of the game. When this condition does not hold, special cases and examples show that the resulting game becomes complicated even when played only for a single stage. We reduce the single stage game to an optimization problem, and also obtain some partial results on its solution. We also consider accumulation games where the locations are arranged in either a circle or in a line segment and the SEEKER must search a series of adjacent locations. © 2002 John Wiley & Sons, Inc. Naval Research Logistics, 49: 60–77, 2002; DOI 10.1002/nav.1048     

被动传感器融合检测系统的优化分布密度

被动传感器由于采用无源探测,而且制造成本低,体积小,在战场环境中将采用并配置大量的被动传感器来检测目标.不论是主动还是被动式传感器,在实际应用中均存在资源优化配置问题.针对被动传感器的具体应用模型,采取了若干合理近似,得到了在"OR"融合检测条件下,基于最大检测概率的被动传感器优化配置密度计算公式.     

Generalized orienteering problem with resource dependent rewards

We introduce a generalized orienteering problem (OP) where, as usual, a vehicle is routed from a prescribed start node, through a directed network, to a prescribed destination node, collecting rewards at each node visited, to maximize the total reward along the path. In our generalization, transit on arcs in the network and reward collection at nodes both consume a variable amount of the same limited resource. We exploit this resource trade‐off through a specialized branch‐and‐bound algorithm that relies on partial path relaxation problems that often yield tight bounds and lead to substantial pruning in the enumeration tree. We present the smuggler search problem (SSP) as an important real‐world application of our generalized OP. Numerical results show that our algorithm applied to the SSP outperforms standard mixed‐integer nonlinear programming solvers for moderate to large problem instances. We demonstrate model enhancements that allow practitioners to represent realistic search planning scenarios by accounting for multiple heterogeneous searchers and complex smuggler motion. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

基于XML／RDF的油料装备模块化协同设计网格主体资源表达

针对协同设计网格中油料装备模块化协同设计主体资源规范化表达问题,提出按照模块设计能力划分油料装备模块化协同设计主体资源的分类体系,给出油料装备模块化协同设计主体资源的信息描述模型。在此基础上,采用元数据完成了油料装备模块化协同设计主体资源描述的元数据集的定义,并采用可扩展的资源描述框架RDF实现了元数据集的描述,规范了具有值域要求属性的赋值空间,给出了基于元数据集的油料装备模块化协同设计主体资源的RDF描述方法,解决了协同设计网格中统一完整和无二义性地描述资源对象的问题,并提出了利用资源表达向导的策略,规范和简化了资源主体的资源表达。