Free Access

Technical Note—The Complexity of the Optimal Searcher Path Problem

K. E. Trummel
K. E. Trummel
Daniel H. Wagner, Associates, Sunnyvale, California
Search for more papers by this author
,
J. R. Weisinger
J. R. Weisinger
Daniel H. Wagner, Associates, Sunnyvale, California
Search for more papers by this author

K. E. Trummel

Daniel H. Wagner, Associates, Sunnyvale, California

Search for more papers by this author

J. R. Weisinger

Daniel H. Wagner, Associates, Sunnyvale, California

Search for more papers by this author

Published Online:1 Apr 1986https://doi.org/10.1287/opre.34.2.324

Cited by
- Bio-inspired adaptive PSO for swarm robotics: balancing search efficiency and physical limitations for dynamic target scenarios
  25 May 2026 | Swarm Intelligence, Vol. 20, No. 1
- Following the trail: An analysis of the path constrained trail-based moving target problem
  Computers & Operations Research, Vol. 193
- NeuPath: A hybrid learning-based optimization approach for emergency search path planning
  Information Processing & Management, Vol. 63, No. 4
- Improved Approximation Algorithms for the Expanding Search Problem
  17 March 2026 | SIAM Journal on Discrete Mathematics, Vol. 40, No. 1
- A reinforcement learning-based artificial bee colony algorithm for resolving the UAV logistics path planning problem in a 3D space
  Swarm and Evolutionary Computation, Vol. 102
- Coverage Path Planning for Minimizing Expected Time to Search for an Object with Continuous Sensing
  1 May 2026
- Linear programming for UAVs search path planning in livestock health monitoring
  Computers and Electronics in Agriculture, Vol. 240
- Informative path planning for unmanned aerial vehicles using cost-benefit spanning tree
  3 December 2025 | Robotica, Vol. 43, No. 12
- Enhancing Object Search in Indoor Spaces via Personalized Object-Factored Ontologies
- Grey Wolf Optimizer Based on Variable Population and Strategy for Moving Target Search Using UAVs
  31 August 2025 | Drones, Vol. 9, No. 9
- Analysis of Reliability and Efficiency of Information Extraction Using AI-Based Chatbot: The More-for-Less Paradox
  3 July 2025 | Algorithms, Vol. 18, No. 7
- Provable Methods for Searching with an Imperfect Sensor
- Coverage path planning for multi-AUV considering ocean currents and sonar performance
  9 January 2025 | Frontiers in Marine Science, Vol. 11
- DSSE: An environment for simulation of reinforcement learning-empowered drone swarm maritime search and rescue missions
  Journal of Open Source Software, Vol. 9, No. 99
- Deep Reinforcement Learning Approach for UAV Search Path Planning In Discrete Time and Space
- An improved sand cat swarm optimization for moving target search by UAV
  Expert Systems with Applications, Vol. 238
- An iterated greedy heuristic for collaborative Human-UAV search of missing tourists
  Knowledge-Based Systems, Vol. 286
- Advancements in Rank-Based Ant System: Enhancements for Improved Solution Quality in Combinatorial Optimization
  16 February 2024
- Multi-USV Target Search Algorithm Based on Markov Prediction Model in Ocean Environment
- Ant colony optimization for path planning in search and rescue operations
  European Journal of Operational Research, Vol. 305, No. 1
- Joint or decoupled optimization: Multi-UAV path planning for search and rescue
  Ad Hoc Networks, Vol. 138
- Coverage Path Planning for UAV Based on Improved Back-and-Forth Mode
  IEEE Access, Vol. 11
- UAV Search Path Planning For Livestock Monitoring
- Cloud DEVS-based computation of UAVs trajectories for search and rescue missions
  5 April 2022 | Journal of Simulation, Vol. 16, No. 6
- People search via deep compressed sensing techniques
  2 February 2022 | Robotica, Vol. 40, No. 7
- Exact and Approximation Algorithms for the Expanding Search Problem
  Ben Hermans,
  Roel Leus,
  Jannik Matuschke
  10 March 2021 | INFORMS Journal on Computing, Vol. 34, No. 1
- Aided Optimal Search: Data-Driven Target Pursuit from On-Demand Delayed Binary Observations
  12 June 2021
- Coverage path planning for maritime search and rescue using reinforcement learning
  Ocean Engineering, Vol. 241
- Acceleration-Aware Path Planning with Waypoints
  27 November 2021 | Drones, Vol. 5, No. 4
- General Cops and Robbers games with randomness
  Theoretical Computer Science, Vol. 887
- Motion-Encoded Electric Charged Particles Optimization for Moving Target Search Using Unmanned Aerial Vehicles
  30 September 2021 | Sensors, Vol. 21, No. 19
- Unmanned Maneuvering Force Route Recommendation Method Based on Improved Artificial Potential Field Method
- UAVs Path Planning under a Bi-Objective Optimization Framework for Smart Cities
  17 May 2021 | Electronics, Vol. 10, No. 10
- Near-optimal search-and-rescue path planning for a moving target
  27 January 2020 | Journal of the Operational Research Society, Vol. 72, No. 3
- Scheduling an autonomous robot searching for hidden targets
  14 March 2019 | Annals of Operations Research, Vol. 298, No. 1-2
- Multi-agent Path Planning Problem Under a Multi-objective Optimization Framework
- State of the Art
  1 July 2021
- Private Genetic Genealogy Search
  SSRN Electronic Journal, Vol. 36
- Motion-encoded particle swarm optimization for moving target search using UAVs
  Applied Soft Computing, Vol. 97
- Evolutionary Collaborative Human-UAV Search for Escaped Criminals
  IEEE Transactions on Evolutionary Computation, Vol. 24, No. 2
- Competitive Two Team Target Search Game with Communication Symmetry and Asymmetry
  7 May 2020
- Attention-based active visual search for mobile robots
  3 August 2019 | Autonomous Robots, Vol. 44, No. 2
- 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
- Ignorance is Not Bliss: An Analysis of Central-Place Foraging Algorithms
- UAV trajectory optimization for Minimum Time Search with communication constraints and collision avoidance
  Engineering Applications of Artificial Intelligence, Vol. 85
- A Survey of Probabilistic Search Based on Bayesian Framework
- Minimum Time Search in Real-World Scenarios Using Multiple UAVs with Onboard Orientable Cameras
  Journal of Sensors, Vol. 2019
- Solving the moving target search problem using indistinguishable searchers
  European Journal of Operational Research, Vol. 275, No. 1
- An Improved Genetic Algorithm for Optimal Search Path of Unmanned Underwater Vehicles
  2 August 2019
- Evolutionary Planning of Multi-UAV Search for Missing Tourists
  IEEE Access, Vol. 7
- UAV/UGV Search and Capture of Goal-Oriented Uncertain Targets
- Competitive target search with multi-agent teams: symmetric and asymmetric communication constraints
  2 December 2017 | Autonomous Robots, Vol. 42, No. 6
- Big data on the shop-floor: sensor-based decision-support for manual processes
  4 January 2018 | Journal of Business Economics, Vol. 88, No. 5
- Near-optimal probabilistic search using spatial Fourier sparse set
  6 February 2017 | Autonomous Robots, Vol. 42, No. 2
- Distributed information-based guidance of multiple mobile sensors for urban target search
  26 July 2017 | Autonomous Robots, Vol. 42, No. 2
- Aided Optimal Search: Data-Driven Target Pursuit from On-Demand Delayed Binary Observations
  14 November 2018
- Ant colony optimization for multi-UAV minimum time search in uncertain domains
  Applied Soft Computing, Vol. 62
- Trajectory optimization under kinematical constraints for moving target search
  Computers & Operations Research, Vol. 88
- Simultaneous search and monitoring by unmanned aerial vehicles
- A multi-UAV minimum time search planner based on ACO R
  1 July 2017
- A Fast Algorithm for Detecting Hidden Objects by Smart Mobile Robots
- Near-optimal probabilistic search via submodularity and sparse regression
  29 December 2015 | Autonomous Robots, Vol. 41, No. 1
- Static target search path planning optimization with heterogeneous agents
  7 March 2016 | Annals of Operations Research, Vol. 244, No. 2
- Real-time path planning for long-term information gathering with an aerial glider
  30 October 2015 | Autonomous Robots, Vol. 40, No. 6
- A Real World Multi-UAV Evolutionary Planner for Minimum Time Target Detection
  20 July 2016
- Constrained Probabilistic Search for a One-Dimensional Random Walker
  IEEE Transactions on Robotics, Vol. 32, No. 2
- Optimal Placement for a Limited-Support Binary Sensor
  IEEE Robotics and Automation Letters, Vol. 1, No. 1
- Optimal Search for Hidden Targets by Unmanned Aerial Vehicles under Imperfect Inspections
  American Journal of Operations Research, Vol. 06, No. 02
- 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
- Technical Note—Trading Off Quick versus Slow Actions in Optimal Search
  Steven M. Shechter,
  Farhad Ghassemi,
  Yasin Gocgun,
  Martin L. Puterman
  6 March 2015 | Operations Research, Vol. 63, No. 2
- Bounding an Optimal Search Path with a Game of Cop and Robber on Graphs
  13 August 2015
- An innovative multi-agent search-and-rescue path planning approach
  Computers & Operations Research, Vol. 53
- Hierarchical Heuristic Search Using a Gaussian Mixture Model for UAV Coverage Planning
  IEEE Transactions on Cybernetics, Vol. 44, No. 12
- An orienteering model for the search and rescue problem
  19 July 2013 | Computational Management Science, Vol. 11, No. 4
- Multi-UAV target search using decentralized gradient-based negotiation with expected observation
  Information Sciences, Vol. 282
- Minimum Time Search in Uncertain Dynamic Domains with Complex Sensorial Platforms
  4 August 2014 | Sensors, Vol. 14, No. 8
- Single robot search for a stationary object in an unknown environment
- The Markov Transition Constraint
- A bayesian approach for constrained multi-agent minimum time search in uncertain dynamic domains
  6 July 2013
- Cooperative Search and Exploration in Robotic Networks
  20 June 2013 | Unmanned Systems, Vol. 01, No. 01
- Generalized orienteering problem with resource dependent rewards
  13 April 2013 | Naval Research Logistics (NRL), Vol. 60, No. 4
- Search and Detection of Failed Components in Repairable Complex Systems under Imperfect Inspections
- Optimal Search and Detection of Clustered Hidden Targets under Imperfect Inspections
  IFAC Proceedings Volumes, Vol. 46, No. 9
- Optimization Model of Routing-and-Searching for Unmanned Aerial Vehicles in Special Target-Detection Operations
  IFAC Proceedings Volumes, Vol. 46, No. 9
- Exact Solution for Search-and-Rescue Path Planning
  International Journal of Computer and Communication Engineering, Vol. 41
- A restricted-direction target search approach based on coupled routing and optical sensor tasking optimization
  Optik, Vol. 123, No. 24
- Minimum time search for lost targets using cross entropy optimization
- Analysis of Search Decision Making Using Probabilistic Search Strategies
  IEEE Transactions on Robotics, Vol. 28, No. 1
- Constraint Programming for Path Planning with Uncertainty
- Search and pursuit-evasion in mobile robotics
  20 July 2011 | Autonomous Robots, Vol. 31, No. 4
- Optimal search path for service in the presence of disruptions
  Computers & Operations Research, Vol. 38, No. 11
- A sequential perspective on searching for static targets
  European Journal of Operational Research, Vol. 215, No. 1
- Cooperative Search by UAV Teams: A Model Predictive Approach using Dynamic Graphs
  IEEE Transactions on Aerospace and Electronic Systems, Vol. 47, No. 4
- On the detection of intelligent mobile targets in a mobile sensor network
- Learning search heuristics for finding objects in structured environments
  Robotics and Autonomous Systems, Vol. 59, No. 5
- Multiscale search using probabilistic quadtrees
- On the Time to Search for an Intermittent Signal Source Under a Limited Sensing Range
  IEEE Transactions on Robotics, Vol. 27, No. 2
- Path optimization for the resource‐constrained searcher
  9 April 2010 | Naval Research Logistics (NRL), Vol. 57, No. 5
- Searching for objects: Combining multiple cues to object locations using a maximum entropy model
- Modeling Sequential Searches with Ancillary Target Dependencies
  Advances in Decision Sciences, Vol. 2010
- Detection of Intelligent Mobile Target in a Mobile Sensor Network
  IEEE/ACM Transactions on Networking, Vol. 18, No. 1
- The Ant Search Algorithm: An Ant Colony Optimization Algorithm for the Optimal Searcher Path Problem with Visibility
- Optimal search-relocation trade-off in Markovian-target searching
  Computers & Operations Research, Vol. 36, No. 6
- Probabilistic search optimization and mission assignment for heterogeneous autonomous agents
- A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search
  European Journal of Operational Research, Vol. 193, No. 2
- On Probabilistic Search Decisions under Searcher Motion Constraints
- Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times
  European Journal of Operational Research, Vol. 190, No. 2
- Multi-agent probabilistic search in a sequential decision-theoretic framework
- Multi-agent search with interim positive information
- Cooperative Graph Search Using Fractal Decomposition
- A Decision-Making Framework for Control Strategies in Probabilistic Search
- Cooperative graph-based model predictive search
- Honey-pot constrained searching with local sensory information
  Nonlinear Analysis: Theory, Methods & Applications, Vol. 65, No. 9
- Probabilistic Search for a Moving Target in an Indoor Environment
- The search for an alerted moving target
  21 December 2017 | Journal of the Operational Research Society, Vol. 56, No. 5
- Searching for a moving target: optimal path planning
- Constrained search for a moving target
- A search game when a search path is given
  European Journal of Operational Research, Vol. 124, No. 1
- Complexity of searching an immobile hider in a graph
  Discrete Applied Mathematics, Vol. 78, No. 1-3
- Optimal strategy of route and look for the path constrained search problem with reward criterion
  European Journal of Operational Research, Vol. 100, No. 1
- 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
- A remark on a helicopter and submarine game
  Naval Research Logistics, Vol. 40, No. 5
- 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
- Cumulative search-evasion games
  Naval Research Logistics, Vol. 38, No. 4
- Resource finding in store-and-forward networks
  Acta Informatica, Vol. 28, No. 7
- Resource finding in store-and-forward networks
- A one-dimensional helicopter-submarine game
  Naval Research Logistics, Vol. 36, No. 4
- Optimal layered search
  Naval Research Logistics, Vol. 36, No. 1

Volume 34, Issue 2

March-April 1986

Pages 190-330

Article Information

Metrics

Information

Published Online:April 01, 1986

Cite as

K. E. Trummel, J. R. Weisinger, (1986) Technical Note—The Complexity of the Optimal Searcher Path Problem. Operations Research 34(2):324-327.

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

Keywords

751 optimal searcher path problem

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Technical Note—The Complexity of the Optimal Searcher Path Problem

Volume 34, Issue 2

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News