Proximity-based non-uniform abstractions for approximate planning

DOI10.1613/JAIR.3414zbMATH Open1237.68183arXiv1401.4592OpenAlexW103181800MaRDI QIDQ2887083FDOQ2887083

Authors: Jiří Baum, Ann E. Nicholson, Trevor I. Dix 

Publication date: 16 May 2012

Published in: The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1401.4592

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

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Agent technology and artificial intelligence (68T42)

Cited In (3)

• Task decomposition on abstract states, for planning under nondeterminism
• Abstraction and approximate decision-theoretic planning.
• Learning hierarchical task network domains from partially observed plan traces

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)