Ben-Gal / Kagan Probabilistic Search for Tracking Targets

Theory and Modern Applications
1. Auflage 2013
ISBN: 978-1-118-59710-1
Verlag: John Wiley & Sons
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 352 Seiten, E-Book

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.

Autoren/Hrsg.

Ben-Gal, Irad

Kagan, Eugene

Inhaltsverzeichnis

List of figures xi
Preface xv
Notation and terms xvii
1 Introduction 1
1.1 Motivation and applications 4
1.2 General description of the search problem 5
1.3 Solution approaches in the literature 7
1.4 Methods of local search 11
1.5 Objectives and structure of the book 14
References 15
2 Problem of search for static and moving targets 19
2.1 Methods of search and screening 20
2.1.1 General definitions and notation 20
2.1.2 Target location density for a Markovian search 24
2.1.3 The search-planning problem 30
2.2 Group-testing search 55
2.2.1 General definitions and notation 56
2.2.2 Combinatorial group-testing search for static targets63
2.2.3 Search with unknown number of targets and erroneousobservations 71
2.2.4 Basic information theory search with known locationprobabilities 84
2.3 Path planning and search over graphs 108
2.3.1 General BF* and A* algorithms 109
2.3.2 Real-time search and learning real-time A* algorithm122
2.3.3 Moving target search and the fringe-retrieving A*algorithm 131
2.4 Summary 140
References 140
3 Models of search and decision making 145
3.1 Model of search based on MDP 146
3.1.1 General definitions 146
3.1.2 Search with probabilistic and informational decision rules152
3.2 Partially observable MDP model and dynamic programmingapproach 161
3.2.1 MDP with uncertain observations 162
3.2.2 Simple Pollock model of search 166
3.2.3 Ross model with single-point observations 174
3.3 Models of moving target search with constrained paths179
3.3.1 Eagle model with finite and infinite horizons 180
3.3.2 Branch-and-bound procedure of constrained search withsingle searcher 184
3.3.3 Constrained path search with multiple searchers 189
3.4 Game theory models of search 192
3.4.1 Game theory model of search and screening 192
3.4.2 Probabilistic pursuit-evasion games 201
3.4.3 Pursuit-evasion games on graphs 206
3.5 Summary 214
References 215
4 Methods of information theory search 218
4.1 Entropy and informational distances between partitions219
4.2 Static target search: Informational LRTA* algorithm227
4.2.1 Informational LRTA* algorithm and its properties228
4.2.2 Group-testing search using the ILRTA* algorithm234
4.2.3 Search by the ILRTA* algorithm with multiplesearchers 244
4.3 Moving target search: Informational moving target searchalgorithm 254
4.3.1 The informational MTS algorithm and its properties 254
4.3.2 Simple search using the IMTS algorithm 260
4.3.3 Dependence of the IMTS algorithm's actions on thetarget's movement 269
4.4 Remarks on programming of the ILRTA* and IMTSalgorithms 270
4.4.1 Data structures 270
4.4.2 Operations and algorithms 282
4.5 Summary 290
References 290
5 Applications and perspectives 293
5.1 Creating classification trees by using the recursiveILRTA* algorithm 293
5.1.1 Recursive ILRTA* algorithm 294
5.1.2 Recursive ILRTA* with weighted distances andsimulation results 297
5.2 Informational search and screening algorithm with single andmultiple searchers 299
5.2.1 Definitions and assumptions 299
5.2.2 Outline of the algorithm and related functions 300
5.2.3 Numerical simulations of search with single and multiplesearchers 304
5.3 Application of the ILRTA* algorithm for navigation ofmobile robots 305
5.4 Application of the IMTS algorithm for paging in cellularnetworks 310
5.5 Remark on application of search algorithms for group testing312
References 313
6 Final remarks 316
References 317
Index 319

Über Autor(innen)

Eugene Kagan, Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Israel
Irad Ben-Gal, Department of Industrial Engineering, Tel-Aviv University, Israel