Information Search After Static or Moving Targets Theory and Modern Applications

by Ben-Gal, Irad; Kagan, Eugene

• ISBN13: 9781118596593
• ISBN10: 1118596595
• Edition: 1st
• Format: eBook
• Copyright: 2013-04-02
• Publisher: Wiley

Summary

This text looks at search algorithms that are applicable in various practical settings. With the implementation of suitable data structures and metrics within the suggested search algorithms, the book presents a unified framework to demonstrate immediate merits and applications. It also looks at applying information theory to search models and algorithms on graphs that can be represented by Markov decision processes and demonstrates that such an approach can lead to the construction of optimal search plans and policies.

Author Biography

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

Table of Contents

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 targets 63

2.2.3 Search with unknown number of targets and erroneous observations 71

2.2.4 Basic information theory search with known location probabilities 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∗ algorithm 122

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 rules 152

3.2 Partially observable MDP model and dynamic programming approach 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 paths 179

3.3.1 Eagle model with finite and infinite horizons 180

3.3.2 Branch-and-bound procedure of constrained search with single 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 partitions 219

4.2 Static target search: Informational LRTA∗ algorithm 227

4.2.1 Informational LRTA∗ algorithm and its properties 228

4.2.2 Group-testing search using the ILRTA∗ algorithm 234

4.2.3 Search by the ILRTA∗ algorithm with multiple searchers 244

4.3 Moving target search: Informational moving target search algorithm 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 the target’s movement 269

4.4 Remarks on programming of the ILRTA∗ and IMTS algorithms 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 recursive ILRTA∗ algorithm 293

5.1.1 Recursive ILRTA∗ algorithm 294

5.1.2 Recursive ILRTA∗ with weighted distances and simulation results 297

5.2 Informational search and screening algorithm with single and multiple 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 multiple searchers 304

5.3 Application of the ILRTA∗ algorithm for navigation of mobile robots 305

5.4 Application of the IMTS algorithm for paging in cellular networks 310

5.5 Remark on application of search algorithms for group testing 312

References 313

6 Final remarks 316

References 317

Index 319