Search for a Moving Target: The FAB Algorithm

Alan R. Washburn
Alan R. Washburn
Naval Postgraduate School, Monterey, California
Search for more papers by this author

Naval Postgraduate School, Monterey, California

Published Online:1 Aug 1983https://doi.org/10.1287/opre.31.4.739

Abstract

We propose and study an iterative Forward And Backward (FAB) algorithm applicable to the problem of computing optimal search plans when the target's motion is modeled by a discrete space and time Markov chain. This paper generalizes the class of objective functions to which the method applies.

Cited by
- Following the trail: An analysis of the path constrained trail-based moving target problem
  Computers & Operations Research, Vol. 193
- Comparative Evaluation of Bandit-Style Heuristic Policies for Moving Target Detection in a Linear Grid Environment
  29 December 2025 | Sensors, Vol. 26, No. 1
- A maritime search and rescue path planning method based on improved DQN
  6 October 2025 | International Journal of Digital Earth, Vol. 18, No. 2
- An autonomous coverage path planning algorithm for maritime search and rescue of persons-in-water based on deep reinforcement learning
  Ocean Engineering, Vol. 291
- Detection of Hidden Moving Targets by a Group of Mobile Agents with Deep Q-Learning
  14 July 2023 | Robotics, Vol. 12, No. 4
- Target search with a radar on an airborne platform
- A competitive search game with a moving target
  European Journal of Operational Research, Vol. 303, No. 2
- A Multi-AUV Maritime Target Search Method for Moving and Invisible Objects Based on Multi-Agent Deep Reinforcement Learning
  7 November 2022 | Sensors, Vol. 22, No. 21
- Detection of Static and Mobile Targets by an Autonomous Agent with Deep Q-Learning Abilities
  22 August 2022 | Entropy, Vol. 24, No. 8
- Aided Optimal Search: Data-Driven Target Pursuit from On-Demand Delayed Binary Observations
  12 June 2021
- Sampling-based search for a semi-cooperative target
- A Markov Decision Process approach for balancing intelligence and interdiction operations in city-level drug trafficking enforcement
  Socio-Economic Planning Sciences, Vol. 69
- Context-Aware Decision Support for Anti-Submarine Warfare Mission Planning Within a Dynamic Environment
  IEEE Transactions on Systems, Man, and Cybernetics: Systems, Vol. 50, No. 1
- Motion in an Unknown Environment
  6 September 2019
- Tracking a Markov Target in a Discrete Environment With Multiple Sensors
  IEEE Transactions on Automatic Control, Vol. 64, No. 6
- Moving target search optimization – A literature review
  Computers & Operations Research, Vol. 105
- Moving Object Search with Multiple Agents
- Aided Optimal Search: Data-Driven Target Pursuit from On-Demand Delayed Binary Observations
  14 November 2018
- Always choose second best: Tracking a moving target on a graph with a noisy binary sensor
- Search for a Moving Target in Discrete Space and Time
  6 April 2016
- Search for Moving Targets in Continuous Space
  6 April 2016
- SEARCH GAMES: LITERATURE AND SURVEY
  Journal of the Operations Research Society of Japan, Vol. 59, No. 1
- Search for Ground Moving Targets Using Dynamic Probability Maps
  Journal of Society of Korea Industrial and Systems Engineering, Vol. 38, No. 4
- Bibliography
  17 June 2015
- An Analysis on the Identification Rate of Detection System Using Non-Homogeneous Discrete Absorbing Markov Chains
  Journal of the Korean Operations Research and Management Science Society, Vol. 40, No. 2
- A SEARCH ALLOCATION GAME WITH PRIVATE INFORMATION OF INITIAL TARGET POSITION
  Journal of the Operations Research Society of Japan, Vol. 58, No. 4
- A Based-DC Programming Approach for Planning a Multisensor Multizone Search for a Moving Target
- Two phase solution for an intelligent moving target search problem based on a 0–1 linear model
  15 October 2014 | International Journal of Production Research, Vol. 52, No. 24
- Response Threshold Model Based UAV Search Planning and Task Allocation
  28 September 2013 | Journal of Intelligent & Robotic Systems, Vol. 75, No. 3-4
- Bi-level Sensor Planning Optimization Process with Calls to Costly Sub-processes
- A DC programming approach for planning a multisensor multizone search for a target
  Computers & Operations Research, Vol. 41
- On Confinement of the Initial Location of an Intruder in a Multi-robot Pursuit Game
  1 November 2012 | Journal of Intelligent & Robotic Systems, Vol. 71, No. 3-4
- Problem of Search for Static and Moving Targets
  1 April 2013
- Search Theory
  23 January 2016
- Planning Sensors with Cost-Restricted Subprocess Calls: A Rare-Event Simulation Approach
- A Column Generation Based Label Correcting Approach for the Sensor Management in an Information Collection Process
- Optimal Search and Detection of Clustered Hidden Targets under Imperfect Inspections
  IFAC Proceedings Volumes, Vol. 46, No. 9
- Search for a mobile target by ground vehicle on a topographic terrain
- Algorithm of search for static or moving target by autonomous mobile agent with erroneous sensor
- A SEARCH GAME TAKING ACCOUNT OF LINEAR EFFECTS AND LINEAR CONSTRAINTS OF SEARCHING RESOURCE
  Journal of the Operations Research Society of Japan, Vol. 55, No. 1
- Search and pursuit-evasion in mobile robotics
  20 July 2011 | Autonomous Robots, Vol. 31, No. 4
- The Search Allocation Game
  19 July 2013
- Inspection Games
  19 April 2013
- Obstacle Avoidance: Static Obstacles
  15 December 2010
- Collision Avoidance
  8 November 2010
- Probabilistic double-distance algorithm of search after static or moving target by autonomous mobile agent
- Path optimization for the resource‐constrained searcher
  9 April 2010 | Naval Research Logistics (NRL), Vol. 57, No. 5
- On Probabilistic Search Decisions under Searcher Motion Constraints
- Hierarchical Bayesian models applied to air surveillance radars
  European Journal of Operational Research, Vol. 184, No. 3
- Constrained minimax optimization of continuous search efforts for the detection of a stationary target
  28 March 2007 | Naval Research Logistics (NRL), Vol. 54, No. 6
- A convex programming with nested constraints on the amount of resources
  International Journal of Computer Mathematics, Vol. 83, No. 10
- Search allocation game
  European Journal of Operational Research, Vol. 172, No. 1
- Continuous Learning Method for a Continuous Dynamical Control in a Partially Observable Universe
- On non-escape search for a moving target by multiple mobile sensor agents
- Conflito em redes: origens e destinos cotados
  Pesquisa Operacional, Vol. 24, No. 1
- Optimal Path Planning in a Threat Environment
- Detection of a Markovian target with optimization of the search efforts under generalized linear constraints
  8 February 2002 | Naval Research Logistics (NRL), Vol. 49, No. 2
- Optimal Risk Path Algorithms
- Optimal ambushing search for a moving target
  European Journal of Operational Research, Vol. 133, No. 1
- Search theory
  25 October 2005
- Searching tracks
  IEEE Transactions on Aerospace and Electronic Systems, Vol. 36, No. 4
- Detection with spatial and temporal optimization of search efforts involving multiple modes and multiple resources management
- A CONCAVE MAXIMIZATION PROBLEM WITH DOUBLE LAYERS OF CONSTRAINTS ON THE TOTAL AMOUNT OF RESOURCES
  Journal of the Operations Research Society of Japan, Vol. 43, No. 1
- OPTIMAL SEARCH FOR A MOVING TARGET WITH NO TIME INFORMATION MAXIMIZING THE EXPECTED REWARD
  Journal of the Operations Research Society of Japan, Vol. 42, No. 2
- OPTIMAL SURVIVOR SEARCH FOR A TARGET WITH CONDITIONALLY DETERMINISTIC MOTION UNDER REWARD CRITERION
  Journal of the Operations Research Society of Japan, Vol. 41, No. 2
- RANDOMIZED LOOK STRATEGY FOR A MOVING TARGET WHEN A SEARCH PATH IS GIVEN
  Journal of the Operations Research Society of Japan, Vol. 41, No. 3
- A SEARCH GAME WITH REWARD CRITERION
  Journal of the Operations Research Society of Japan, Vol. 41, No. 4
- Optimal strategy of route and look for the path constrained search problem with reward criterion
  European Journal of Operational Research, Vol. 100, No. 1
- S
- Finite method for a nonlinear allocation problem
  Journal of Optimization Theory and Applications, Vol. 85, No. 3
- Moving-target search: a real-time search for changing goals
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, No. 6
- Criteria and approximate methods for path-constrained moving-target search problems
  Naval Research Logistics, Vol. 42, No. 1
- PATH CONSTRAINED SEARCH PROBLEM WITH REWARD CRITERION
  Journal of the Operations Research Society of Japan, Vol. 38, No. 2
- Optimal Search Among False Contacts
  SIAM Journal on Applied Mathematics, Vol. 52, No. 6
- Introduction special issue on search theory
  Naval Research Logistics, Vol. 38, No. 4
- A survey of the search theory literature
  Naval Research Logistics, Vol. 38, No. 4
- On optimal search plans to detect a target moving randomly on the real line
  Stochastic Processes and their Applications, Vol. 20, No. 2
- Numerical methods in search path planning
- Search game for a moving target with dynamically generated informations

Volume 31, Issue 4

July-August 1983

Pages 603-801

Article Information

Metrics

Information

Published Online:August 01, 1983

Cite as

Alan R. Washburn, (1983) Search for a Moving Target: The FAB Algorithm. Operations Research 31(4):739-751.

https://doi.org/10.1287/opre.31.4.739

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Search for a Moving Target: The FAB Algorithm

Abstract

Volume 31, Issue 4

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News