Probabilistic Search for Tracking Targets Theory and Modern Applications

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

LIST OF FIGURES

NOTATION AND TERMS

PREFACE

1. INTRODUCTION

1.1. Motivation and applications

1.2. General description of the search problem

1.3. Solution approaches in the literature

1.4. Methods of local search

1.5. Objective and structure of the book

2. PROBLEM OF SEARCH FOR STATIC AND MOVING TARGETS

2.1. Methods of search and screening

2.1.1. General definitions and notation

2.1.2. Target location density for a Markovian search

2.1.3. The search planning problem

2.2. Group-testing search

2.2.1. General definitions and notation

2.2.2. Combinatorial group-testing search for static targets

2.2.3. Search with unknown number of targets and erroneous observations

2.2.4. Basic information theoretic search with known location probabilities

2.3. Path-planning and search over graphs

2.3.1. General BF* and A* algorithms

2.3.2. Real-Time Search and Learning Real-Time A* algorithm

2.3.3. Moving Target Search and Fringe-Retrieving A* algorithm

2.4. Summary

3. MODELS OF SEARCH AND DECISION MAKING

3.1. Model of search based on Markov Decision Process

3.1.1. General definitions

3.1.2. Search with probabilistic and informational decision rules

3.2. Partially observable MDP model and dynamic programming approach

3.2.1. Markov decision process with uncertain observations

3.2.2. Simple Pollock model of search

3.2.3. Ross model with single-point observations

3.3. Models of moving target search with constrained paths

3.3.1. Eagle model with finite and infinite horizons

3.3.2. Branch-and-bound procedure of constrained search with single searcher

3.3.3. Constrained path search with multiple searchers

3.4. Game-theoretic models of search

3.4.1. Game-theoretic model of search and screening

3.4.2. Probabilistic pursuit-evasion games

3.4.3. Pursuit-evasion games on graphs

3.5. Summary

4. METHODS OF INFORMATION THEORETIC SEARCH

4.1. Entropy and informational distances between partitions

4.2. Static target search: Informational Learning Real-Time A* algorithm

4.2.1. Informational LRTA* algorithm and its properties

4.2.2. Group-testing search using the ILRTA*-algorithm

4.2.3. Search by ILRTA*-algorithm with multiple searchers

4.3. Moving target search: Informational Moving Target Search algorithm

4.3.1. Informational MTS-algorithm and its properties

4.3.2. Simple search using IMTS-algorithm

4.3.3. Dependence of IMTS-algorithm actions on the target’s movement

4.4. Remarks on programming of the ILRTA* and IMTS algorithms

4.4.1. Data structures

4.4.2. Operations and algorithms

4.5. Summary

5. APPLICATIONS AND PERSPECTIVES

5.1. Creating classification trees by the use of recursive ILRTA*-algorithm

5.1.1. Recursive ILRTA*-algorithm

5.1.2. Recursive ILRTA* with weighted distances and simulations results

5.2. Informational search and screening algorithm with single and multiple searchers

5.2.1. Definitions and assumptions

5.2.2. Outline of the algorithm and related functions

5.2.3. Numerical simulations of search with single and multiple searchers

5.3. Application of ILRTA* algorithm for navigation of mobile robots

5.4. Application of IMTS algorithm for paging in cellular networks

5.5. Remark on application of search algorithms for group testing

6. FINAL REMARK

REFERENCES

INDEX

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.