Child, C. H. T. (2012). Approximate Dynamic Programming with Parallel Stochastic Planning Operators (TR/2012/DOC/03). City University London.
Abstract
This report presents an approximate dynamic programming (ADP) technique for environment modelling agents. The agent learns a set of parallel stochastic planning operators (PSPOs) by evaluating changes in its environment in response to actions, using an association rule mining approach. An approximate policy is then derived by iteratively improving state value aggregation estimates attached to the operators using the PSPOs as a model in a DynaQlike architecture. Reinforcement learning and dynamic programming are powerful techniques for automated agent decision making in stochastic environments. Dynamic programming is effective when there is a known environment model, while reinforcement learning is effective when a model is not available. The techniques derive a policy: a mapping from each environment state to an action which optimizes the long term reward the agent receives. The standard methods become less effective as the state space for the environment increases because they require values to be associated with each state, the storage and processing of which is exponential to the number of state variables. Resolving this “curse of dimensionality” is an important topic of research amongst all communities working on this problem. Two key methods are to: (i) derive an estimate of the value (approximate dynamic programming) using function approximation or state aggregation; or (ii) build a model of the environment from experience. This report presents a method of combining these approaches by exploiting structure in the state transition and value functions captured in a set of planning operators which are learnt through experience in the environment. Standard planning operators define the deterministic changes that occur in an environment in response to an action. This work presents Parallel Stochastic Planning Operators (PSPOs), a novel form of planning operator providing a structured model of the state transition function in environments which are both nondeterministic and for which changes can occur outside the influence of actions. Next, an automated method for extracting PSPOs from observations in an environment is explored using an adaptation of association rule mining. Finally, methods of relating the state transition structure encapsulated in the PSPOs to state values, using the operators to store state value aggregation estimates, are evaluated. The framework described provides a method by which approximate dynamic programming can be applied by designers of AI agents and AI planning systems for which they have minimal prior knowledge. The framework and PSPO based implementations are tested against standard techniques in two benchmark stochastic environments: a “slippery gripper” block painting robot; and a “predatorprey” agent environment. Experimental results show that an agent using a PSPObased approach is able to learn an accurate model of its environment if successor state variables exhibit conditional independence, and an approximate model in the nonindependent case. Results also demonstrate that the agent’s ability to generalise to previously unseen states using the model allow it to form an improved policy over an agent employing a standard DynaQ based technique. Finally, an approximate policy stored in state aggregation estimates attached to operators is shown to be optimal in experiments for which the PSPO set contains sufficient information for effective aggregations to be formed.
Publication Type:  Report 

Subjects:  T Technology > T Technology (General) 
Departments:  School of Mathematics, Computer Science & Engineering > Computer Science 
URI:  http://openaccess.city.ac.uk/id/eprint/8076 

Text
 Published Version
Download (1MB)  Preview 
Export
Downloads
Downloads per month over past year
Actions (login required)
Admin Login 