Search

How should a firm structure its concept testing processes when testing efforts must be delegated to self-interested testing agents? In "Delegated Concept Testing in New Product Development," J. Schlapp and G. Schumacher analyze different configurations of testing processes and compare their relative benefits. The authors show that the optimal number of agents to be involved in a testing process critically depends on the costs of testing, the informational quality of test outcomes, and the agents' tendency to strategically prolong the testing process. The authors also provide guidelines on how to manage the testing process: which product concepts a firm should test (or not), and how it should structure the incentives of agents. Rather surprisingly, the authors also find that the delegation of testing activities can increase a firm's chances of successful concept selection. The article thus provides a comprehensive analysis of a key organizational issue that firms encounter during their concept testing processes, and it challenges some common decision rules. Testing a large variety of different product concepts is an integral part of nearly all new product development initiatives—especially in the concept selection phase, where firms seek to identify the most promising concept for further development. Test results are usually collected by agents, who must be incentivized not only to exert effort in testing the concepts but also to report their findings truthfully. We ask: How should a firm structure its concept testing processes when testing efforts must be delegated to self-interested agents? To answer this question, we devise a principal–(multi)agent model that allows us to analyze different testing processes and to compare their relative benefits. We find that several factors determine how the firm should construct its testing processes: the efficiency of concept testing, the extent of heterogeneity in the quality of test outcomes, and the severity of information asymmetry between agents and the firm. Finally, we determine how the firm should adjust agents' incentives to reflect its chosen testing process and which product concepts should (or should not) be tested. [ABSTRACT FROM AUTHOR]

Unmanned aerial vehicles (UAVs) have been proved to be successful and efficient for information collection in a modern battlefield, especially in areas that are considered to be dangerous for human pilots. Currently, a UAV is remotely controlled by a ground station through frequent data communications, which make the current system vulnerable in a threat environment. We propose a decentralized control strategy while requiring UAVs to maintain radio silence during the entire mission. The strategy is analyzed based on a scenario where a fleet of vehicles is assigned to search and collect uncertain information in a set of regions within a given mission time. We demonstrate that a region-sharing strategy is beneficial even when there is no extra reward gained from additional information collection. Implementing a region-sharing strategy requires solving a decentralized time allocation problem, which is computationally intractable. To overcome this, an approximate formulation is developed under an independence assumption for information collected by different vehicles. This approximate formulation allows us to decompose, by vehicle, the time allocation problem, and obtain an easily implementable policy that takes on a Markovian form. We develop a sufficient condition under which the approximate formulation becomes exact. A numerical study establishes the computational efficiency of the method; only a few CPU seconds are needed for problems with a planning horizon of 300 time units and 40 regions. We further present a case study to illustrate region-sharing behaviors among UAVs while using practical parameter values. Finally, we compare the obtained policy with the optimal policy found using a complete enumeration method for small instances. Under different parameter settings, the average optimality gap ranges from 0.23% to 19.90%. [ABSTRACT FROM AUTHOR]

A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance between the two players is two. We show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best-known result (3.9546, 4.3931). To achieve the improved bounds, we call upon results from absorbing Markov chain theory and mathematical programming theory--particularly fractional quadratic programming and semidefinite programming. Moreover, we also establish some important properties of this problem, which could be of independent interest and useful for resolving this problem completely. Finally, we conjecture that the symmetric rendezvous value is asymptotically equal to 4.25 based on our numerical calculations. [ABSTRACT FROM AUTHOR]

There is an extensive theory regarding optimal continuous path search for a mobile or immobile 'target.' The traditional theory assumes that the target is one of three types: (i) an object with a known distribution of paths, (ii) a mobile or immobile hider who wants to avoid or delay capture, or (iii) a rendezvouser who wants to find the searcher. This paper introduces a new type of search problem by assuming that aims of the target are not known to the searcher. The target may be either a type (iii) cooperator (with a known cooperation probability c) or a type (ii) evader. This formulation model searches problems like that for a lost teenager who may be a 'runaway,' or a lost intelligence agent who may be a defector. In any given search context, it produces a continuum of search problems T (c), 0 ≤ c ≤ 1, linking a zero-sum search game (with c = 0) to a rendezvous problem (with c = 1). These models thus provide a theoretical bridge between two previously distinct parts of search theory, namely search games and rendezvous search. [ABSTRACT FROM AUTHOR]

This paper considers rational methods for the design of search densities when the intended target is stationary among stationary, Poisson-distributed false contacts. Attention is restricted to situations in which the searcher must immediately decide, based on sensed information, whether a contact is the intended target and, if the answer is yes, end the search and commit to the contact. Discrimination of false contact from target is modeled as reliable only with given probabilities. We seek to allocate search effort to maximize the probability of finding the intended target in a fixed time. Modeling space and time as discrete, we apply the Kuhn-Tucker theorem to obtain a set of necessary conditions for an optimum. For the particular case of a discrete space and time approximation of search for a normally distributed target in R² and a uniform density of false contacts, we develop a computer algorithm that converges to a solution of the necessary conditions. Numerical results are presented. [ABSTRACT FROM AUTHOR]

This article is based on a talk that I gave at the 1988 TIMS/ORSA meeting in Washington, D.C. about developments in search theory since the Lanchester Prize for 1975 was awarded to me for Theory of Optimal Search. The answer to the question in the title is that a lot has happened, particularly in the area of the search for moving targets and in the use of computers in search theory and applications. [ABSTRACT FROM AUTHOR]

This paper presents an empirically derived formula for computing the threshold contrast C for visually detecting distant objects in search situations. The threshold contrast is the value of contrast that produces detection probability 1/2 on a single glimpse of about 1/3 to 1 second in duration. The formula allows one to compute C as a function of background luminance, target angular area A, and an empirically determined constant K. For small A, the formula reduces to Ricco's law, which says that the threshold constrast C, and Area A, are directly proportional for small values of A. The limiting threshold contrast is determined by K. Results of fitting this formula to a set of observational data are shown. The formula provides a useful approximation for determining detection capability for planning visual searches. [ABSTRACT FROM AUTHOR]

An unknown number N of cells are arranged in numerical order. An object is hidden in cell N. The problem is to locate the object--thereby determining N--within n searches. We consider a version of this problem that has applications in several problem settings: locating flaws in a discrete circuit, locating nerve endings, or locating the end of a tree root. A search of a site determines whether a cell is present and contains the object, except that it might overlook, with known probability w, a cell that is present; that is, a cell can "wink." A search of site i reveals an empty cell if i < N; the cell containing the object if i = N and the cell does not wink; and no cell if i > N or if i less than or equal to N and the cell winks. Various special cases are considered. We define "bisection strategies" and show that they are optimal when w = 0. When w > 0, we partially characterize optimal strategies when n = 2, and completely characterize optimal strategies when there are at most two cells. For various values of n and w we give tables of the probability of finding the object for three intuitively reasonable strategies. [ABSTRACT FROM AUTHOR]

A search is conducted for a target moving in discrete time among a finite number of cells according to a known Markov process. The searcher must choose one cell in which to search in each time period. The set of cells available for search depends upon the cell chosen in the last time period. The problem is to find a searcher path, i.e., a sequence of search cells, that maximizes the probability of detecting the target in a fixed number of time periods. We formulate the problem as a partially observable Markov decision process and present a finite time horizon POMDP solution technique which is simpler than the standard linear programming methods. [ABSTRACT FROM AUTHOR]

We propose and study an iterative Forward And Backward (FAB) algorithm applicable to the problem of computing optimal search plans when the target's motion is modeled by a discrete space and time Markov chain. This paper generalizes the class of objective functions to which the method applies. [ABSTRACT FROM AUTHOR]

The surveillance search problem is a generalization of the detection search problem studied by Brown and Stone, among others. In the surveillance version of the problem, the search terminates only if the time and location of a detection satisfy certain problem specific conditions; the objective is to maximize the expected value of a payoff received during and at the end of the search. For instance, we may wish to maximize the probability of finding the target in a specified subset of the state space or at a specified time. Consequently, we might detect the target several times before the search terminates. A search strategy, i.e., an allocation of the available search effort, must account for this possibility. In this paper, we formulate the surveillance search problem for applications in which the target moves according to a (not necessarily time-homogeneous) Markov process. We then derive a set of necessary conditions for the optimality of a search strategy, end develop algorithms, based on the algorithm of Brown for the detection search problem, to find strategies that satisfy these necessary conditions for problems in which the search effort is infinitely divisible. [ABSTRACT FROM AUTHOR]

Picard and Ratliff recently proposed a cut approach to the rectilinear distance location problem and claimed it is fundamentally different from the direct search approach as developed by Pritsker and Ghare, Rap, Juel and Love, and Sherali and Shetty. Our objective is to show that the cut approach is essentially a direct search approach. [ABSTRACT FROM AUTHOR]

The optimal survivor search problem is to maximize the probability of finding a moving target alive. The target may be a person missing at sea or lost in a wilderness area. In a multistate target problem, the target is moving and changing states stochastically. Each state may imply different motion and detectability assumptions. We find necessary and sufficient conditions for optimal detection plans for multistate targets. Using these conditions, we extend the algorithms of Brown and Stone for finding optimal detection search plans for moving targets to multistate target problems, and show that the optimal survivor search problem may be solved as a special case of the multistate target problem. [ABSTRACT FROM AUTHOR]

We consider optimal search for a moving target in discrete space. A limited amount of search effort is available at each of a fixed number of time intervals and we assume an exponential detection function. We show that a search plan maximizes the overall probability of detection if and only if for each time interval l the search conducted at time I maximizes the probability of detecting a stationary target with the probability that the stationary target occupies cell c equal to the probability that the moving target occupies cell c at time l and is not detected by the search at any time interval other than l. This characterization gives an iterative algorithm to compute optimal search plans. These plans are compared with incrementally optimal plans. [ABSTRACT FROM AUTHOR]

A game where a Searcher attempts to trap an Evader who knows the location of all past traps is formulated and solved, using average time to capture as the payoff The Evader can move around freely, except that he is constrained to remain within a certain region. [ABSTRACT FROM AUTHOR]

This paper applies the test of operational meaningfulness to the many detection laws that have been formulated and used in the mathematical optimization of search, and given as generalizations of those first developed in the United States Navy during and immediately following World War II. The word "operational" is used both in the sense of practical O.R. and in that of P. W. Bridgman's well-known requirement: that in applying mathematics to the material world, the physical preconditions implied in the quantities used, the operations for measuring them, and their laws of consistency must be set forth explicitly. It is submitted that this criterion will orient O.R. work toward useful developments in the search theory and may serve to identify as such those theories that are of chief interest as developments in pure mathematics. Finally, we note that the requirement that every numerical assumption of probability distributions in a study of the outside world must be based on objective evidence is perfectly consistent with the "subjective" conception of probability, viz., that its meaning is apprehended intuitively--the former measures what the latter defines. [ABSTRACT FROM AUTHOR]

This paper establishes a connection between information theory and search theory. In the case of an exponential detection function we show that the search that maximizes the probability of detection also minimizes the information content of the posterior distribution. We also show that if the search plan that maximizes the probability of detection also minimizes the information content of the posterior distribution, then the detection function is exponential. We prove our results in both the continuous and discrete cases. [ABSTRACT FROM AUTHOR]

This paper describes and discusses some search problems, starting with the case of no false contacts, to provide a foundation for developing a search theory in the presence of false contacts. Important properties of the search plan are defined and illustrated by examples. After a general description of false-contact generators and alternative actions that may be used when contacts are made, the problem is formulated for the case in which false contacts are generated by real stationary objects that are investigated when contacted. It is shown that the formulation and solution of the standard optimization functionals are contingent on the number of false targets found, in general, and possibly on the locations and times of contact as well. The optimization functional is difficult to write and more difficult to solve. The formulation is made for the expected-time functional when the number of false targets is bounded. Finally, the paper outlines a procedure for ending the solution and illustrates it with an example. [ABSTRACT FROM AUTHOR]

This paper presents several fault-testing models. Our system is composed of n components that either work or fail. The systems treated are the k-out-of-n type (k/n). This system works if and only if k or more of its components work, making the series (n/n) and parallel (1/n) systems special cases. Components can be individually tested end tests give perfect information. Each test has a time to complete it and testing procedures are judged by the expected cumulative testing time they require. In the first model, the components are assumed to function or fail independently of each other. A feasible test procedure must determine (as) if the system is working or has failed. This is solved for the series and parallel systems and, under a possibly restrictive hypothesis, for the general k/n system. In another model, the components are assumed to be nominally independent conditioned on the system being failed. Here a feasible test procedure must locate all failed components. This problem is solved for the general k/n system. [ABSTRACT FROM AUTHOR]

This paper deals with a search model for allocating effort when there are many target objects of differing sizes present in a search area. All target objects are initially present in the search area and remain at least until discovered; no new objects are generated during the search process. Targets are not moveable. The search process is characterized by the quantity of search effort. The model describes the distribution of the number and sizes of target objects present. The probability of discovery is assumed proportional to object size. The paper gives many results, including the probability distribution of the number and sizes of discovered objects, and the prior and posterior distributions of the number of objects remaining undiscovered. Then it gives the method of maximum likelihood estimation of the model parameters, and solves the sequential decision problem of when to terminate the search process. [ABSTRACT FROM AUTHOR]

Presents information on the preparation of a survey of search theory using access to two theories. General references and bibliography; Search objectives; Stationary point target.

A penetrator, P, attempts to cross a linear barrier patrolled by a searcher, S. S receives intermittent reports of P's position, P[sub 1], P[sub 2], ... , but P knows only that S is somewhere on the barrier. After receiving report P[sub 1], a time tau can elapse before the next report P[sub 2] may reveal that S may be unable to intercept P even if he received continuous information thereafter. S attempts to select a position S(P,) that maximizes tau, while P attempts to choose a course alpha that minimizes tau. If the searcher is faster than the penetrator (speed ratio lambda > 1), values of alpha and S(P[sub 1]) that produce maximin tau are deduced. However, maximin tau < minimax tau, and P is obliged to use a mixed strategy in order to obtain the maximin. If the harrier is finite, contours of constant maximin tau are segments of conic sections. If lambda < 1, S should modify the maximin tau strategy when P is close to the barrier. An indication is given of the frequency with which reports are needed as P approaches the barrier. [ABSTRACT FROM AUTHOR]

In this paper we consider certain nonlinear and constrained variational problems that occur in the theory of search. The problems are definitely of a nonclassical variety, but, by using a device of R. COURANT, a sequence of unconstrained variational problems is generated, the solutions of which converge to the solution of the constrained problem. The maximum principle of L. PONTRYAGIN ET AL., is then utilized to construct a corresponding sequence of nonlinear, two-point boundary value problems such that a solution to the variational problem will then necessarily satisfy the boundary value problem. An effective computational method, based on the notion of a generalized Newton-Raphson operator, is then applied to solve iteratively, in a rapid and accurate manner, the nonlinear boundary value problem; under suitable assumptions, this method yields solutions to the variational problem. The technique is illustrated in several examples. [ABSTRACT FROM AUTHOR]

Exploration for natural resources has followed traditional trial-and-error procedures from the original prospector and burro to the latest airborne detection devices and each kind of resource tends to be associated with an individual type of search program. If the real-world objective of 'making a profit' is substituted for the resource as the ultimate target of endeavor then a systems approach, in which the kind of target is immaterial and all targets are equally welcome, appears to be most efficacious. Under these circumstances systematic grid drilling is a financially feasible search program, and this conclusion is borne out by two independent simulation procedures. Drilling on a systematic grid across areas such as Kansas, or Pennsylvania and Ohio, leads to returns that appear ample to pay for both search and development costs, and to include a profit. Similarly, using the 'Engel Model' for search and varying the parameter values over ranges such that some 'real-world' situations must be included, also indicates that a reasonable profit is assured. Given a systematic search procedure, such as a drilling grid, then the geological information that accrues would form a sound basis for development of all the resources of an area. [ABSTRACT FROM AUTHOR]

Following a line of approach recently applied to the 0-1 integer programming problem with some success by EGON BALAS, the algorithm of this paper is based upon an underlying tree-search structure upon which a series of tests is superimposed to exclude large portions of the tree of all possible 0-1 solutions from examination. In our method, the specific design of the enumeration and tests, supplemented by the use of a special type of constraint called a 'surrogate constraint,' results in an algorithm that appears to be quite efficient in relation to other algorithms currently available for solving the 0-1 integer programming problem. Early indications of efficiency must, however, be regarded as suggestive rather than conclusive, due to the limited range and size of problems so far examined. Following the analytical development of the method, three example problems are solved in detail with the Multiphase-Dual Algorithm to illustrate various aspects of its application. An extension of the algorithm to the general integer programming problem in bounded variables is briefly sketched in a concluding section. [ABSTRACT FROM AUTHOR]

The fundamental problem of search theory is to allocate a given amount of search effort in such a way as to maximize the over-all probability of discovering an object located in a given space The problem has already been solved under the assumption that the probability of detecting the object is a negative exponential function of the search effort density, this assumption seems to be fairly realistic in many military apphcations, but has definite drawbacks in others In this paper a method is provided for solving the problem in the general case, where no assumption is made concerning the form of the detection probability function A theorem is derived that gives a general relation governing the optimal solution. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of whether or not a search activity should be started and, if started, whether or not it should be continued. This problem suggests a model that is described. The model gives rise to a general functional equation for which existence and uniqueness conditions are given. Several examples are discussed, solutions to the specific functional equations appropriate to the examples are given, and the optimal policies are characterized [ABSTRACT FROM AUTHOR]

This is Part III, concluding the series of three papers on The Theory of Search Part I, Kinematic Bases, appeared in Opns Res 4, 324-346 (1956) and Part II, Target Detection, in 4, 503-531 (1956). The present paper, while similar in content and results to the third chapter of Search and Screening (O E G Report No 56, CONFIDENTIAL) represents a considerable change in methodology as well as in exposition. The material was first presented by the author at the fall meeting of the OPERATIONS RESEARCH SOCIETY OF AMERICA in 1953, where it was treated as a natural extension of his paper, The Optimum Distribution of Effort [this JOURNAL, 1, 52-63 (1953)] [ABSTRACT FROM AUTHOR]

Discusses the uncertainties inherent in the act of detection under various specific conditions of contact. Development of the body of methods for applying probability to problems of detection; Calculation of probabilities of detection by means of formulas; Consideration of the effect of statistically combining observations made under operational conditions in which the physical situation is not constant.

This note extends the model of unemployment insurance reported by D. Zuckerman in 1985. The following extensions are incorporated into the model: The government's objective function is now formulated in a more economically appealing fashion; the search process is allowed to continue beyond the coverage period; the time value of money is explicitly incorporated; and the individual's search strategy is compared with the socially optimal policy. Using techniques and concepts from game theory, we investigate the socially and individually optimal strategies and derive an unemployment insurance strategy that best suits the government's objective. [ABSTRACT FROM AUTHOR]

POLLOCK has examined a model of search for a target whose transitions between two regions are described by a two-state stationary Markov chain. The minimum-search policy is characterized by a threshold probability r[sup*] that determines which region to search next. This note presents a simple recursive procedure for calculating. [ABSTRACT FROM AUTHOR]

This article presents the author's formula for the optimality of the (periodic) geometric trajectory for the m Ray search. The optimality of the (periodic) geometric trajectory which has a first break point, easily follows from the minimax theorems.