Proximity-based non-uniform abstractions for approximate planning
From MaRDI portal
Publication:2887083
Abstract: In a deterministic world, a planning agent can be certain of the consequences of its planned sequence of actions. Not so, however, in dynamic, stochastic domains where Markov decision processes are commonly used. Unfortunately these suffer from the curse of dimensionality: if the state space is a Cartesian product of many small sets (dimensions), planning is exponential in the number of those dimensions. Our new technique exploits the intuitive strategy of selectively ignoring various dimensions in different parts of the state space. The resulting non-uniformity has strong implications, since the approximation is no longer Markovian, requiring the use of a modified planner. We also use a spatial and temporal proximity measure, which responds to continued planning as well as movement of the agent through the state space, to dynamically adapt the abstraction as planning progresses. We present qualitative and quantitative results across a range of experimental domains showing that an agent exploiting this novel approximation method successfully finds solutions to the planning problem using much less than the full state space. We assess and analyse the features of domains which our method can exploit.
Recommendations
- Abstraction and approximate decision-theoretic planning.
- Stochastic dynamic programming with factored representations
- Efficient approximate planning in continuous space Markovian decision problems
- Performance bounds for planning in unknown terrain
- Task decomposition on abstract states, for planning under nondeterminism
Cited in
(3)
This page was built for publication: Proximity-based non-uniform abstractions for approximate planning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2887083)
