Learning and monitoring of spatio-temporal fields with sensing robots

Abstract

This thesis proposes new algorithms for a group of sensing robots to learn a para-
\nmetric model for a dynamic spatio-temporal field, then based on the learned model
\ntrajectories are planned for sensing robots to best estimate the field. In this thesis
\nwe call these two parts learning and monitoring, respectively.
\n
\nFor the learning, we first introduce a parametric model for the spatio-temporal
\nfield. We then propose a family of motion strategies that can be used by a group
\nof mobile sensing robots to collect point measurements about the field. Our motion
\nstrategies are designed to collect enough information from enough locations at enough different times for the robots to learn the dynamics of the field. In conjunction with
\nthese motion strategies, we propose a new learning algorithm based on subspace
\nidentification to learn the parameters of the dynamical model. We prove that as the
\nnumber of data collected by the robots goes to infinity, the parameters learned by
\nour algorithm will converge to the true parameters.
\n
\nFor the monitoring, based on the model learned from the learning part, three
\nnew informative trajectory planning algorithms are proposed for the robots to collect the most informative measurements for estimating the field. Kalman filter is used
\nto calculate the estimate, and to compute the error covariance of the estimate. The
\ngoal is to find trajectories for sensing robots that minimize a cost metric on the
\nerror covariance matrix. We propose three algorithms to deal with this problem.
\nFirst, we propose a new randomized path planning algorithm called Rapidly-exploring
\nRandom Cycles (RRC) and its variant RRC* to find periodic trajectories for the
\nsensing robots that try to minimize the largest eigenvalue of the error covariance
\nmatrix over an infinite horizon. The algorithm is proven to find the minimum infinite
\nhorizon cost cycle in a graph, which grows by successively adding random points.
\nSecondly, we apply kinodynamic RRT* to plan continuous trajectories to estimate
\nthe field. We formulate the evolution of the estimation error covariance matrix as a
\ndifferential constraint and propose extended state space and task space sampling to
\nfit this problem into classical RRT* setup. Thirdly, Pontryagin’s Minimum Principle
\nis used to find a set of necessary conditions that must be satisfied by the optimal
\ntrajectory to estimate the field.
\n
\nWe then consider a real physical spatio-temporal field, the surface water temper-
\nature in the Caribbean Sea. We first apply the learning algorithm to learn a linear
\ndynamical model for the temperature. Then based on the learned model, RRC and
\nRRC* are used to plan trajectories to estimate the temperature. The estimation
\nperformance of RRC and RRC* trajectories significantly outperform the trajectories
\nplanned by random search, greedy and receding horizon algorithms.