Irad Ben-Gal, Eugene Kagan

Probabilistic Search for Tracking Targets

Theory and Modern Applications

• Gebundenes Buch

Produktbeschreibung

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.

---

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.

---

Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.

Produktdetails

• Verlag: Wiley & Sons
• 1. Auflage
• Seitenzahl: 352
• Erscheinungstermin: 28. Mai 2013
• Englisch
• Abmessung: 249mm x 173mm x 23mm
• Gewicht: 680g
• ISBN-13: 9780470973936
• ISBN-10: 0470973935
• Artikelnr.: 35482039

Autorenporträt

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

Inhaltsangabe

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