Comparative Evaluation of Bandit-Style Heuristic Policies for Moving Target Detection in a Linear Grid Environment

Area of Science:

• Robotics and Autonomous Systems
• Search Theory
• Information Theory

Background:

• Moving-target detection is crucial for surveillance, search-and-rescue, and autonomous robotics.
• Strict sensing constraints necessitate efficient search strategies.
• Target dynamics often involve random-walk patterns.

Purpose of the Study:

• To minimize expected time to detection for a moving target on a 1D grid.
• To compare greedy and belief-proportional sampling (BPS) decision rules.
• To establish a baseline for search strategies under binary observations.

Main Methods:

• Simulated a target with reflecting random-walk dynamics on a finite grid.
• Implemented and compared a greedy probing policy with a BPS policy.
• Utilized Monte Carlo simulations to analyze performance and trade-offs.

Main Results:

• The greedy policy consistently achieved the shortest expected detection time.
• Greedy policy improved detection time by approximately 17-20% over BPS and random probing.
• BPS offered stochastic exploration, potentially beneficial for model mismatch scenarios.

Conclusions:

• The greedy policy is a highly effective and interpretable baseline for moving-target detection under strict sensing constraints.
• Quantitative results provide a reference for future research, including noisy sensing and higher dimensions.
• Understanding the exploitation-exploration trade-off is key for optimizing search strategies.