Probabilistic Search for Tracking Targets

Presents a probabilistic and information-theoretic framework for a search for static or moving targets in discrete time and space. Probabilistic Search for Tracking Targets uses an information-theoretic scheme to present a unified approach for known search methods to allow the development of new algorithms of search. The book addresses search methods under different constraints and assumptions, such as search uncertainty under incomplete information, probabilistic search scheme, observation errors, group testing, search games, distribution of search efforts, single and multiple targets and search agents, as well as online or offline search schemes. The proposed approach is associated with path planning techniques, optimal search algorithms, Markov decision models, decision trees, stochastic local search, artificial intelligence and heuristic information-seeking methods. Furthermore, this book presents novel methods of search for static and moving targets along with practical algorithms of partitioning and search and screening. Probabilistic Search for Tracking Targets includes complete material for undergraduate and graduate courses in modern applications of probabilistic search, decision-making and group testing, and provides several directions for further research in the search theory. The authors: Provide a generalized information-theoretic approach to the problem of real-time search for both static and moving targets over a discrete space. Present a theoretical framework, which covers known information-theoretic algorithms of search, and forms a basis for development and analysis of different algorithms of search over probabilistic space. Use numerous examples of group testing, search and path planning algorithms to illustrate direct implementation in the form of running routines. Consider a relation of the suggested approach with known search theories and methods such as search and screening theory, search games, Markov decision process models of search, data mining methods, coding theory and decision trees. Discuss relevant search applications, such as quality-control search for nonconforming units in a batch or a military search for a hidden target. Provide an accompanying website featuring the algorithms discussed throughout the book, along with practical implementations procedures.

Presents a probabilistic and information-theoretic frameworkfor a search for static or moving targets in discrete time andspace.Probabilistic Search for Tracking Targets uses aninformation-theoretic scheme to present a unified approach forknown search methods to allow the development of new algorithms ofsearch. The book addresses search methods under differentconstraints and assumptions, such as search uncertainty underincomplete information, probabilistic search scheme, observationerrors, group testing, search games, distribution of searchefforts, single and multiple targets and search agents, as well asonline or offline search schemes. The proposed approach isassociated with path planning techniques, optimal searchalgorithms, Markov decision models, decision trees, stochasticlocal search, artificial intelligence and heuristicinformation-seeking methods. Furthermore, this book presents novelmethods of search for static and moving targets along withpractical algorithms of partitioning and search and screening.Probabilistic Search for Tracking Targets includescomplete material for undergraduate and graduate courses in modernapplications of probabilistic search, decision-making and grouptesting, and provides several directions for further research inthe search theory.The authors:* Provide a generalized information-theoretic approach to theproblem of real-time search for both static and moving targets overa discrete space.* Present a theoretical framework, which covers knowninformation-theoretic algorithms of search, and forms a basis fordevelopment and analysis of different algorithms of search overprobabilistic space.* Use numerous examples of group testing, search and pathplanning algorithms to illustrate direct implementation in the formof running routines.* Consider a relation of the suggested approach with known searchtheories and methods such as search and screening theory, searchgames, Markov decision process models of search, data miningmethods, coding theory and decision trees.* Discuss relevant search applications, such as quality-controlsearch for nonconforming units in a batch or a military search fora hidden target.* Provide an accompanying website featuring the algorithmsdiscussed throughout the book, along with practical implementationsprocedures.

List of figures xiPreface xvNotation and terms xvii1 Introduction 11.1 Motivation and applications 41.2 General description of the search problem 51.3 Solution approaches in the literature 71.4 Methods of local search 111.5 Objectives and structure of the book 14References 152 Problem of search for static and moving targets 192.1 Methods of search and screening 202.1.1 General definitions and notation 202.1.2 Target location density for a Markovian search 242.1.3 The search-planning problem 302.2 Group-testing search 552.2.1 General definitions and notation 562.2.2 Combinatorial group-testing search for static targets632.2.3 Search with unknown number of targets and erroneousobservations 712.2.4 Basic information theory search with known locationprobabilities 842.3 Path planning and search over graphs 1082.3.1 General BF* and A* algorithms 1092.3.2 Real-time search and learning real-time A* algorithm1222.3.3 Moving target search and the fringe-retrieving A*algorithm 1312.4 Summary 140References 1403 Models of search and decision making 1453.1 Model of search based on MDP 1463.1.1 General definitions 1463.1.2 Search with probabilistic and informational decision rules1523.2 Partially observable MDP model and dynamic programmingapproach 1613.2.1 MDP with uncertain observations 1623.2.2 Simple Pollock model of search 1663.2.3 Ross model with single-point observations 1743.3 Models of moving target search with constrained paths1793.3.1 Eagle model with finite and infinite horizons 1803.3.2 Branch-and-bound procedure of constrained search withsingle searcher 1843.3.3 Constrained path search with multiple searchers 1893.4 Game theory models of search 1923.4.1 Game theory model of search and screening 1923.4.2 Probabilistic pursuit-evasion games 2013.4.3 Pursuit-evasion games on graphs 2063.5 Summary 214References 2154 Methods of information theory search 2184.1 Entropy and informational distances between partitions2194.2 Static target search: Informational LRTA* algorithm2274.2.1 Informational LRTA* algorithm and its properties2284.2.2 Group-testing search using the ILRTA* algorithm2344.2.3 Search by the ILRTA* algorithm with multiplesearchers 2444.3 Moving target search: Informational moving target searchalgorithm 2544.3.1 The informational MTS algorithm and its properties 2544.3.2 Simple search using the IMTS algorithm 2604.3.3 Dependence of the IMTS algorithm's actions on thetarget's movement 2694.4 Remarks on programming of the ILRTA* and IMTSalgorithms 2704.4.1 Data structures 2704.4.2 Operations and algorithms 2824.5 Summary 290References 2905 Applications and perspectives 2935.1 Creating classification trees by using the recursiveILRTA* algorithm 2935.1.1 Recursive ILRTA* algorithm 2945.1.2 Recursive ILRTA* with weighted distances andsimulation results 2975.2 Informational search and screening algorithm with single andmultiple searchers 2995.2.1 Definitions and assumptions 2995.2.2 Outline of the algorithm and related functions 3005.2.3 Numerical simulations of search with single and multiplesearchers 3045.3 Application of the ILRTA* algorithm for navigation ofmobile robots 3055.4 Application of the IMTS algorithm for paging in cellularnetworks 3105.5 Remark on application of search algorithms for group testing312References 3136 Final remarks 316References 317Index 319