Probabilistic Search for Tracking Targets Theory and Modern Applications

by Ben-Gal, Irad; Kagan, Eugene

• ISBN13: 9780470973936
• ISBN10: 0470973935
• Edition: 1st
• Format: Hardcover
• Copyright: 2013-05-28
• 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

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