Rapidly-Exploring Random Cycles: Persistent Estimation of Spatio-Temporal Fields with Multiple Sensing Robots

Abstract

This paper considers the problem of planning trajectories for both single and multiple sensing robots to best estimate a spatio-temporal field in a dynamic environment. The robots use a Kalman filter to maintain an estimate of the field value, and to compute the error covariance matrix of the estimate. Two new sampling-based path planning algorithms (RRC and RRC*) are proposed to find periodic trajectories for the sensing robots that minimize the largest eigenvalue of the error covariance matrix over an infinite horizon. The algorithms are proven to find the minimum infinite horizon cost cycle in a random graph, which grows by successively adding random points. The algorithms leverage recently developed methods for periodic Riccati recursions to efficiently compute the infinite horizon cost of the cycles, and they use the monotonicity property of the Riccati recursion to efficiently compare the costs of different cycles without explicitly computing their costs. The algorithms are demonstrated in a study using National Oceanic and Atmospheric Administration (NOAA) data to plan sensing trajectories in the Caribbean Sea. Our algorithms significantly outperform random, greedy, and receding horizon approaches in this environment.