Multi-agent Receding Horizon Search with Terminal Cost

We present a multi-agent approach to receding horizon path planning that utilizes terminal costs. We show that the value of the receding horizon paths produced using the proposed methods have a guaranteed lower bound that can be determined using any readily-available, naive solution. We present a modified sequentially allocated optimal path planner with terminal costs that is guaranteed to satisfy the assumptions required to provide a guaranteed lower bound. We utilize a slightly modified version of the Decentralized Monte Carlo Tree Search algorithm to solve for near-optimal paths within a short planning horizon with an appended terminal cost to demonstrate the flexibility of the proposed method. We compare these receding horizon methods that incorporate a terminal cost to related receding horizon methods that do not incorporate a terminal cost. Our approach is developed specifically for multiple agents engaged in search, but can be easily adapted for other information gathering applications.