Search-based Strategy for Spatio-Temporal Environmental Property Restoration

This paper addresses the spatio-temporal areas restoration problem: a robot, with limited battery life, deployed in a known environment, needs to persistently plan a schedule to visit areas of interest and charge its battery as needed. The goal is to restore the areas’ properties that temporally decay—such as air quality—so that the time the measured property values are below a certain threshold is minimized. This problem is different from typical problems solved in the area of monitoring a spatio-temporal environment. A related problem is the orienteering problem, where a robot visits nodes to maximize the profit collected at each visited node within a time budget frame. That problem is NP-hard. The typical formulation considers static profit, while we consider a time-varying one. Given look-ahead time window or schedule length, we formulate the problem as an optimization search problem with a temporal objective, and devise a heuristic function that enables finding solutions in polynomial time. The heuristic evaluates the discounted opportunity costs of a visit—a concept borrowed from economics. We then develop a greedy algorithm that takes the immediate feasible visit that minimizes this heuristic. This strategy addresses a primary limitation of a recent approach in applications where being able to revisit highly urgent areas within the time window of the schedule is critical. We provide a theoretical analysis on lower and upper bounds for the problem. Extensive experimental results with a robotic simulator show that our method is able to keep the areas in the environment above the threshold better than other methods and closer to the optimal. This work can enable high-impact applications, such as environmental preservation.