Extended Performance Guarantees for Receding Horizon Search with Terminal Cost

The computational difficulty of planning search paths that seek to maximize a general deterministic value function increases dramatically as desired path lengths increase. Mobile search agents with limited computational resources often utilize receding horizon methods to address the path planning problem. Unfortunately, receding horizon planners may perform poorly due to myopic planning horizons. We provide methods of incorporating terminal costs in the construction of receding horizon paths that provide a theoretical lower bound on the performance of the search paths produced. The results presented in this paper are of particular value in subsea search applications. We present results from simulated subsea search missions that use real-world data acquired by an autonomous underwater vehicle during a subsea survey of Boston Harbor.