Multiscale Time Abstractions for Long-Range Planning under Uncertainty
Roykrong Sukkerd,
Javier Cámara,
David Garlan and Reid Simmons.
In Proceedings of the 2nd ICSE Workshop on Software Engineering for Smart Cyberphysical Systems, Austin, Texas, 16 May 2016.
Online links:   Plain Text
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 satisfi es 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
fi delity 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. |
Keywords: Cyberphysical Systems, Planning, uncertainty.
|
|
