Multiscale time abstractions for long-range planning under uncertainty

Abstract

Planning in CPSs requires temporal reasoning to handle the dynamics of the environment, including human behavior, as well as temporal constraints on system goals and durations of actions that systems and human actors may take. The discrete abstraction of time in a state space planning should have a time sampling parameter value that satisfies some relation to achieve a certain precision. In particular, the sampling period should be small enough to allow the dynamics of the problem domain to be modeled with sufficient precision. Meanwhile, in many cases, events in the far future (relative to the sampling period) may be relevant to the decision making earlier in the planning timeline; therefore, a longer planning look-ahead horizon can yield a closer-to-optimal plan. Unfortunately, planning with a uniform fine-grained discrete abstraction of time and a long look-ahead horizon is typically computationally infeasible. In this paper, we propose a multiscale temporal planning approach -- formulated as MDP planning -- to preserve the required time fidelity of the problem domain and at the same time approximate a globally optimal plan. We illustrate our approach in a middleware used to monitor large sensor networks.