Planning under periodic observations: bounds and bounding-based solutions

We study planning problems faced by robots operating in uncertain environments with incomplete knowledge of state and, actions that are noisy and/or imprecise. This paper identifies a new problem sub-class that models settings in which information is revealed only intermittently through some exogenous process that provides state information periodically. Several practical domains fit this model, including the specific scenario that motivates our research: autonomous navigation of a remote rover. With an eye to efficient specialized solution methods, we examine the structure of instances of this sub-class. They lead to Markov Decision Processes with exponentially large action-spaces but for which, as those actions comprise sequences of more atomic elements, one may establish performance bounds by comparing policies under different information assumptions. For instance, policies with actions that have a prefix form entail waiting to obtain information. They give lower bounds. Or instead, one might imagine extra information becoming available so that the robot obtains its state estimate early; these yield upper bounds. Moving beyond the pattern apparent in these basic intuitions, we also describe a way to construct bounds systematically. Bounds are useful because, in conjunction with the insights they confer, they can be employed in bounding-based methods to obtain high- quality solutions efficiently; the empirical results we present demonstrate their effectiveness for the considered problems. The foregoing has also alluded to the distinctive role that time (specifically: the time until information is revealed) plays for these problems. We uncover several interesting subtleties: one may quantify the value of knowing when information arrives, as distinct from the value of information itself. Also, obtaining information earlier isn’t always better, even under exponential discounting.