Performance Guarantees for Receding Horizon Search with Terminal Cost We present a novel method of using terminal costs in the construction of a receding horizon search path. We prove that the proposed method of constructing search paths provides a theoretical lower bound on the performance of the search path. Our result can be interpreted as ensuring that the receding horizon path performs no worse in expectation than a given suboptimal search path. This result is especially practical for subsea applications where, due to use of sidescan sonar in search applications, search paths typically consist of parallel straight lines. Thus for subsea search applications, our approach ensures that expected performance is no worse than the usual subsea search path, and it might be much better. We demonstrate the efficacy of the proposed method by planning search paths in simulation using realworld data that was acquired by an autonomous underwater vehicle during a subsea survey of Boston Harbor.

Online Planning for Autonomous Underwater Vehicles Performing Information Gathering Tasks in Large Subsea Environments We present an anytime Monte Carlo tree search (MCTS) algorithm to generate realtime, nearoptimal search paths in large subsea environments. The MCTS planner continuously builds a tree of the search space until either the allowed time per move is reached or the budget constraint for the search mission is met. In order to improve the performance of the MCTS planner, we propose a novel heuristic action selection policy to determine the value of a leaf node. The proposed heuristic is tailored to problems where making a turn incurs a higher cost than moving straight, such as the case on autonomous underwater vehicles. Through extensive simulations, we show that our heuristic yields a significant performance improvement over a lawnmover path planner xe2x80x93 a commonly employed approach in subsea search applications xe2x80x93 and over a simple MCTS planner where actions are selected uniformly at random. In our numerical illustrations, we use a real data set abstracted from sonar measurements acquired from the Boston Harbor.