Symbol Acquisition for Probabilistic High-Level Planning

Introduction

There is a long history of research in intelligent robotics that combines high-level planning with low-level control [Nilsson, 1984; Malcolm and Smithers, 1990; Gat, 1998; Cambon et al., 2009; Choi and Amir, 2009; Dornhege et al., 2009; Wolfe et al., 2010; Kaelbling and Lozano-P´erez, 2011]. Such systems are capable of generating complex, goal-driven behavior but are hard to design because they require a difficult integration of symbolic reasoning and low-level motor control.

Recently, Konidaris et al. [2014] showed how to automatically construct a symbolic representation suitable for planning in a high-dimensional, continuous domain. This work modeled the low-level domain as a semi-Markov decision process (SMDP) and formalized a propositional symbol as the name given to a grounding set of low-level states (represented compactly using a classifier). Their key result was that the symbols required to determine the feasibility of a plan are directly determined by characteristics of the actions available to an agent. This close relationship removes the need to handdesign symbolic representations of the world and enables an agent to, in principle, acquire them autonomously.

However, a set-based symbol formulation cannot deal with learned sets that may not be exactly correct, and can only determine whether or not the probability of successfully executing a plan is 1. These restrictions are ill-suited to the realworld, where learning necessarily results in uncertainty and all plans have some probability of failure.

We introduce a probabilistic reformulation of symbolic representations capable of naturally dealing with uncertain representations and probabilistic plans. This is achieved by moving from sets and logical operations to probability distributions and probabilistic operations. We use this framework to design an agent that autonomously learns a completely symbolic representation of a computer game domain, enabling very fast planning using an off-the-shelf probabilistic planner.

Background

Semi-Markov Decision Processes

We assume that the low-level sensor and actuator space of the agent can be described as a fully observable, continuousstate semi-Markov decision process, described by a tuple M = (S,O,R, P, γ), where S ⊆ Rn is the n-dimensional continuous state space; O(s) is a finite set of temporally extended actions, or options [Sutton et al., 1999], available in state s ∈ S; R(s′ , τ|s, o) is the reward received when executing option o ∈ O(s) at state s ∈ S and arriving in state s′ ∈ S after τ time steps; P(s′ , τ|s, o) is a PDF describing the probability of arriving in state s′ ∈ S, τ time steps after executing option o ∈ O(s) in state s ∈ S; and γ ∈ (0, 1] is a discount factor.

An option o consists of three components: an option policy, πo, which is executed when the option is invoked; an initiation set, Io = {s|o ∈ O(s)}, which describes the states in which the option may be executed; and a termination condition, βo(s) → [0, 1], which describes the probability that option execution terminates upon reaching state s. The combination of initiation set, reward model, and transition model for an option o is known as o's option model. We assume that the agent does not have access to its option models, and can only observe whether its current state is in Io and the transitions resulting from actually executing o.

Probabilistic High-Level Planning

High-level planning approaches operate using symbolic states and actions. The simplest formalism for high-level planning is the set-theoretic representation [Ghallab et al., 2004]. A typical formalization of the probabilistic version of this [Younes and Littman, 2004] describes a planning domain as a set of propositional symbols P = {p1, ..., pn} and a set of actions A = {α1, ..., αm}. A state Pt at time t assigns a truth value Pt(i) to every pi ∈ P, and so can be represented by a binary vector.

Each action αi is a tuple describing a precondition and a set of possible outcomes, along with the probability of each occurring: αi = (precondi , {(ρ1, effect+i1 , effect-i1 ), ..., (ρk, effect+ik , effect-ik )}) , where precondi ⊆ P lists the propositions that must be true in a state for the action to be applicable, each ρj ∈ [0, 1] is an outcome probability such that ∑kj=1 ρj = 1, and effect+ij and effect-ij are the positive (propositions set to be true) and negative (propositions set to be false) effects of outcome j occurring, respectively. All other propositions retain their values. A planning problem is obtained by additionally specifying a start state, s0, and set of goal states, Sg. The planner is typically tasked with finding a sequence of actions that leads from s0 to some state in Sg with high probability.

Symbols for Planning

When a high-level planning formalism is used to solve a lowlevel problem, each proposition can be considered to evaluate to true or false at each low-level state. The propositions can thus be viewed as referring to (or naming) the set of low-level states in which the proposition holds (i.e., evaluates to true). Consequently, Konidaris et al. [2014] used the following definition of a symbol:

Definition 1. A propositional symbol σZ is the name associated with a test τZ, and the corresponding set of states Z = {s ∈ S | τZ(s) = 1}.

The test, or grounding classifier, is a compact representation of a set of infinitely many continuous, low-level states. High-level planning can then be performed using set operations over the grounding classifiers (corresponding to logical operations over the symbols). Defining a symbol for each option's initiation set, and the symbols necessary to compute its image (the set of states the agent might be in after executing the option from any of a given set of starting states) are necessary and sufficient for planning [Konidaris et al., 2014]. The feasibility of a plan is evaluated by computing each successive option's image, and then testing whether it is a subset of the next option's initiation set. This process is depicted in Figure 1.

Konidaris et al. [2014] defined two option classes (subgoal and abstract subgoal options) for which computing the image simply required one symbol for each option's effects set (the set of states the agent could find itself in after executing the option from any state). The grounding classifiers for the resulting symbols are sufficiently well defined that an agent can gather labeled training data by executing the options and observing the results. In principle, this enables the agent to acquire its own symbolic representation solely through interaction with the environment.

However, the resulting learned classifiers will be difficult to plan with in real domains, for three reasons. First, this formalism cannot account for the uncertainty inherent in learning the symbols themselves. Instead, planning proceeds as if the agent's estimate of each of its grounding classifiers is exactly correct. Second, it cannot model the fact that some transitions are more likely than others-effectively assuming that all transitions with a non-zero probability of occurring are equivalently important. Consequently, it cannot be used to reason about expected reward, since expectation requires a probability distribution. Finally, it can only determine whether a plan can certainly be executed, or not-it cannot determine the probability with which it can be executed. These restrictions make it unlikely that a set-based framework can be applied to real problems.

Probabilistic Symbols and Plans

We now describe a probabilistic formulation of symbolic representations that allows an agent to reason about the probability that a plan can be executed using uncertain symbols (such as are obtained during learning), and compute the expected reward of executing a plan. This requires generalizing the idea of a symbol as a set to that of a symbol as a probability distribution. Instead of referring to a grounding set via a grounding classifier, a symbol will now refer to a grounding distribution. There are two senses in which this will be useful, leading to two types of symbols, referred to as types 1 and 2.

In the first sense, a set is a collection of equally likely states, which we can generalize to a probability distribution over states:

Definition 2. A probabilistic symbol σZ of type 1 is the name associated with a distribution, Z(S), over states.

Symbols of type 1 will be useful in expressing a distribution over start states and for representing an option's image. During learning, the task of estimating the grounding distribution of a type 1 symbol is that of density estimation, which is a well-studied unsupervised learning problem.

In the second sense, a set is a collection of states in which some condition holds. We generalize this to a distribution expressing the probability that a condition holds in each state:

Definition 3. A probabilistic symbol σE of type 2 is the name associated with the probability P(C(s) = 1) of some condition C holding at every state s ∈ S.

Symbols of type 2 are probabilistic classifiers, giving the probability that a condition holds for every state in S. Since the agent operates in an SMDP, a condition either holds at each state or it does not-but the agent must necessarily generalize when learning from data, and the probabilistic classifier expresses the agent's uncertainty about the condition in states it has not yet encountered.

We now generalize the notion of a plan from one that starts from a set of states to one that starts from a distribution over states (a probabilistic symbol of type 1):

Definition 4. A probabilistic plan p = {o1, ..., opn } from a start state symbol σZ (corresponding to state distribution Z(S)) is a sequence of options oi ∈ O, 1 ≤ i ≤ pn, to be executed from a state drawn from Z(S).

We can also define the corresponding plan space-the set of all plans the agent should be able to evaluate.

Definition 5. The probabilistic plan space for an SMDP is the set of all tuples (σZ, p), where σZ is a start symbol and p is a plan.

The essential function of a symbolic representation for probabilistic planning is to compute, on demand, the probability that an agent can execute any element of the plan space to completion, and the expected reward received for successfully doing so. We now introduce probabilistic symbols that are provably sufficient for doing so by defining probabilistic versions of the precondition symbol and image operator. The probabilistic precondition symbol expresses the probability that an option can be executed from each state:

Definition 6. The probabilistic precondition is a probabilistic symbol of type 2, defined as Pre(o) = P(s ∈ Io).

Given a distribution over s (a probabilistic symbol of type 1) representing a distribution over start states, we now require a probabilistic image operator that computes an output distribution (also of type 1) over s′ , representing the distribution over states in which the agent expects to find itself in after option execution.

Definition 7. Given a start distribution Z(S) and an option o, we define the probabilistic image of o from Z(S) as:

where P(s′ |s, o) = ∫ P(s′ , τ |s, o) dτ , since we are not concerned with the time taken to execute o.

These generalizations of the precondition set and image operator allow us to prove the probabilistic generalization of Theorem 1 from Konidaris et al. [2014]:

Theorem 1. Given an SMDP, the ability to represent the probabilistic preconditions of each option and to compute the probabilistic image operator is sufficient to determine the probability of being able to execute any probabilistic plan tuple (σZ, p).

Proof. Consider an arbitrary plan tuple (σZ, p), with plan length n. To determine the probability of executing p from σZ, we can set Z0 = Z and repeatedly compute Zj+1 = Im(pj,Zj), for j ∈ {1, ..., n}. The probability of being able to execute the plan is given by Πnj=1 [∫S Pre(oj , s)Zj-1(s) ds] .

Computation proceeds as follows. Starting with an initial distribution over states, the agent repeatedly applies the image operator to obtain the distribution over low-level states it expects to find itself in after executing each option in the plan. It can thereby compute the probability of being able to execute each successive option, and multiply these to compute the probability of successfully executing the entire plan.

To obtain the expected reward of the plan, the agent requires one additional operator:

Definition 8. Given a start distribution Z(S) and an option o, the reward operator J(o,Z) = ∫S ∫S ∫R+ P (s′ , τ |s, o)R(s′ , τ |s, o)Z(s) dτ ds′ ds.

The expected reward of a plan tuple (σZ0 , p) of length n is then ∑ni=1 J(pi, Zi-1), where each state distribution Zi(S) is defined as in Theorem 1. Although the definition of the reward operator involves three integrals, during learning we use the following equation:

which simply estimates the expected reward for executing an option from each state. The reward obtained after option execution from a state is a sample of the right hand side of this equation, resulting in a standard supervised learning problem. Computing the expected reward now requires integration over the distribution over start states only.

The symbol and operators described above are defined in terms of option models. One approach to planning in SMDPs is to learn the option models themselves, and use them to perform sample-based planning. Representing the operators directly as defined above may allow more efficient planning using analytical methods for computing the image operator. However, when the characteristics of the available options support it, the agent can go further and construct completely symbolic models it can use to plan-after which its grounding distributions are no longer required.

Subgoal Options and Abstract Subgoal Options

As in the deterministic planning case, computing the image operator for a subgoal option is particularly straightforward. A subgoal option in the probabilistic setting satisfies:

for all distributions over states X(S). Eff(o) is the effects distribution-the distribution over states after executing o from any start distribution. This means that the image distribution is the same regardless of the start distribution-a stronger condition than in the set-based case, where the set of states that the agent has non-zero probability of arriving in cannot depend on the start set, but the probability of arriving in each state can.

This independence assumption models the case where a feedback controller or learned policy guides the agent to a specific target distribution before completing option execution. It drastically simplifies planning because the image operator always evaluates to the effects distribution, and may be a reasonable approximation in practice even when it does not strictly hold.

If an agent has only subgoal options, a very simple abstract data structure suffices for planning. Given a collection of options and their effects distributions, define an abstract plan graph G as follows. Each option oi has corresponding vertex vi, with edges eij from vi to vj with reward J(oj, Eff(oi)) and probability of success ∫S Pre(oj, s) Eff(oi)(s) ds. After computing G the agent can discard its grounding distributions and evaluate the reward and probability of a plan succeeding by adding the rewards and multiplying the probabilities along the corresponding path in the graph.

Abstract subgoal options model the more general case where the state vector can be partitioned into two parts s = [a, b], such that executing o leaves the agent in state s′ = [a, b′ ]; the m feature values in a ∈ A ⊆ Rm are left unchanged, and the state features values in b ∈ B ⊆ Rn-m (o's mask) are set to a subgoal distribution P(b′ ) independent of the starting distribution. In this case:

where P (a) = ∫B Z([a, b]) db (integrating b out of Z(S)) and Eff(o) is a distribution over the variables in b′ .

In some cases an (abstract) subgoal option can be best modeled using multiple effect outcomes, where executing the option leads to one of a number of distinct (abstract) subgoals, each with some probability. The effect outcome distributions can be modeled as a single mixture distribution if they all have the same mask; if not, they must be modeled individually. In such cases an option oi is characterized by a single precondition Pre(oi) and a set of effect outcomes Effj (oi), each with an associated mask and probability ρj of occurrence.

The options available to an agent may in some cases not satisfy the (abstract) subgoal property, but can be partitioned into a finite number options that do. For example, consider an agent with an option for moving through a corridor. This is not a subgoal option in a building with multiple corridors, but if the agent partitions the building into a finite number of corridors and considers the option executed in each to be distinct, then the subgoal property may hold for each partitioned option. Identifying such partitions is a major challenge when learning a probabilistic symbolic representation in practice. Fortunately, partitioning reflects a statistical measure of independence-a partition should be made when the effect distribution is not independent of the start distribution, but is independent conditioned on assignment to a partition.

Generating a Symbolic Domain Description

We now show that an agent can build a probabilistic STRIPSlike representation given a collection of abstract subgoal options. Our target is PPDDL, the Probabilistic Planning and Domain Definition Language [Younes and Littman, 2004], which can serve as input to an off-the-shelf planner.

Reasoning about the soundness and completeness of a symbolic representation requires a grounding scheme that specifies the semantics of that symbolic representation. Recall that a STRIPS-like representation is based on a collection of propositional symbols P = {p1, ..., pn}. We choose to use probabilistic symbols of type 1, so that each pi symbol refers to a distribution over states: pi has associated grounding distribution G(pi). We then define the grounding distribution of an abstract state as the multiplication of the grounding distributions of the propositions set to true in that state:

The abstract state Pt can therefore be interpreted as representing the distribution of states in which the agent expects to find itself in at time t.

Finding Factors To proceed, the agent must identify the appropriate factors, similarly to Konidaris et al. [2014]- given the function modifies(si) (the list of options that modify a low-level SMDP state variable), the agent groups state variables modified by the same list of options together into factors. It can then define the functions factors(oi) (the list of factors affected by executing oi) and factors(σi) (the list of factors that probability distribution σi is defined over).

Building the Symbol Set We define a natural notion of independent factors-those that are statistically independent in the joint distribution Eff(oi):

Definition 9. Factor fs is independent in effect distribution Eff(oi) iff Eff(oi) = [∫fs Eff(oi)dfs ] × [∫ ¯ fs Eff(oi)d ¯ fs ] , where ¯ fs = factors(oi) \ fs.

Factor fs is independent in Eff(oi) if the two sets of random variables fs and ¯ fs are statistically independent in the joint distribution Eff(oi). When that is the case, Eff(oi) can be broken into independent factors with separate propositions for each.

Let Effr(oi) denote the effect set that remains after integrating out all independent factors from Eff(oi), and factorsr(oi) denote the remaining factors. Our method requires a separate propositional symbol for Effr(oi) with each possible subsets of factorsr(oi) integrated out. The vocabulary P thus contains the following symbols:

1. For each option oi and factor fs independent in Eff(oi), create a propositional symbol with grounding distribution ∫ ¯ fs Eff(oi)d ¯ fs.
2. For each set of factors fr ⊆ factorsr(oi), create a propositional symbol with grounding distribution ∫fr Effr(oi)dfr.

Propositions that are approximate duplicates can be merged.

Constructing Operator Descriptions Given that it can be executed, each option oi with possible effect outcome Effj (oi) results in the following effects:

1. All propositional symbols with grounding distributions for each factor independent in Effj (oi), and an additional proposition with grounding distribution Effjr (oi) if necessary, are set to true.

1. All propositional symbols (except the above) σj such that factors(σj) ⊆ factors(oi) and ∫S G(σj)(s)Pre(oi, s)ds > 0, are set to false.
2. All currently true propositional symbols σj where fij = factors(σj) ∩ factors(oi) ̸= ∅ but factors(σj) ̸⊆ factors(oi), and ∫S G(σj)(s)Pre(oi, s)ds > 0, are set to false. For each such σj, the predicate with grounding distribution ∫fij G(σj)dfij is set to true.

Each such potential outcome is listed with the probability ρj of it occurring.

This computation is analogous to the effects computation in Theorem 1, computing Im(oi,Z) = P(a)Eff(oi), where P(a) = ∫B Z([a, b]) db (integrating out b, the variables in oi's mask). The first effect in the above list corresponds to Eff(oi), and the remaining two types of effect model P(a). The second type of effect removes predicates defined entirely using variables within mask(oi), whose distributions are completely overwritten. The third models the side-effects of the option, where an existing distribution has the variables in mask(oi) integrated out. The proof that this image computation is correct closely follows the one given by Konidaris et al. [2014] and we omit it here.

However, we face a complication present in the probabilistic setting. Given high-level state Pt and action o, the agent can compute the probability, ρ, that o can be executed from Pt, and the positive and negative effects for that outcome. But that is a probabilistic precondition, and PPDDL only allows for probabilistic outcomes. This does not occur in the deterministic case, because the subset relationship is always either true or not. For simplicity, we get around this by adding a virtual proposition named notfailed, which is set to true during initialization and is a precondition for every operator. An effect of ¬notfailed is added to each action with probability (1 - ρ).

Symbol Acquisition in the Treasure Game

The Treasure Game features an agent in a 2D, 528 × 528 pixel video-game like world, whose task is to obtain treasure and return to its starting position on a ladder at the top left of the screen (see Figure 2). The agent's path may be blocked by closed doors. Flipping the direction of either of the two handles switches the status of the two doors on the top left of the screen (flipping one switch also flips the other). The agent must obtain the key and use it in the lock to open the door on the bottom right of the screen to reach the treasure.

The agent can move up, down, left, and right, jump, interact, and perform a no-op. Left and right movement is available when the agent's way is not directly blocked, while up and down are only available when the agent is on or above, or on or below, respectively, a ladder. These actions move the agent between 2 and 4 pixels (chosen uniformly at random). The interact action is available when the agent is standing in front of a handle (flipping the handle's position from right to left, or vice versa, with probability 0.8), or when it possesses the key and is standing in front of the lock (whereupon the agent loses the key). The no-op action lets the game dynamics continue for one time step, and is useful after a jump action or when the agent is falling. Each action has a reward of -1, except for the jump action, which receives a reward of -5. Returning to the top ladder with the treasure ends the episode. The low-level state space is 9-dimensional, featuring the x and y positions of the agent, key, and treasure, the angles of the two handles, and the state of the lock. When the agent has possession of an item (the key or the treasure), it is displayed in the lower-right corner of the screen.

The agent has access to the following 9 high-level options, implemented using simple control loops:

• go-left and go-right, which move the agent continuously left or right, respectively, until it reaches a wall, an edge, an object with which it can interact, or a ladder. These options can only be executed when they would succeed.
• up-ladder and down-ladder, which cause the agent to ascend or descend a ladder, respectively.
• down-left and down-right, which cause the agent to execute a controlled fall off an edge onto the nearest solid cell on its left or right, respectively.
• jump-left and jump-right, which cause the agent to jump and move left, or right, respectively, for about 48 pixels. These options are only available to the agent when the area above its head, and above its head and to the left and right, respectively, are clear.
• interact, which executes a primitive interaction.

All options have stochastic termination conditions which, when combined with the stochasticity present in the primitive actions, results in outcome variance ranging from a few pixels (for the go-left and go-right options) to a much larger amount (e.g., in the case where the jump-left option can miss the ledge, causing the agent to fall).

The shortest plan that solves to the Treasure Domain with non-zero probability consists of 42 high-level actions, requiring approximately 3800 low-level actions.

Data was gathered as follows. 100 randomly chosen options were executed sequentially, resulting in one set of data recording whether each option could run at states observed before or after option execution, and another recording the transition data xi = (si, oi, ri, s′i ) for each executed option. This was repeated 40 times.

Partitioning the Options

First, the options must be partitioned so that the abstract subgoal property approximately holds. This was done using the following procedure for each option o:

1. The mask mi was computed for each sample transition xi, and the data was partitioned by mask.
2. For each mask mj, the effect states s′i [mj] were clustered and each cluster was assigned to its own partition. The data was now partitioned into distinct effect distributions, but may have been over-partitioned because distinct effects may occur from the same start state partition.
3. For each pair of partitions, the agent determinedwhether their start states samples si overlapped substantially by clustering the combined start state samples si from each partition, and determining whether each resulting cluster contained data from both partitions. If so, the common data was merged into a single partition.
4. When merging, an outcome was created for each effect cluster (which could be distinct due of clustering or due to a different mask) and assigned an outcome probability based on the fraction of the samples assigned to it.

Clustering was performed using the DBSCAN algorithm [Ester et al., 1996] in scikit-learn [Pedregosa et al., 2011], with parameters min samples = 5 and ϵ = 0.4/14 (for partitioning effects) or ϵ = 0.8/14 (for merging start states). This resulted in 39 partitioned options. Example partitions are visualized in Figures 3 and 4. Note that fuzzy or transparent sprites indicate variance in the distribution.

Creating the Symbolic Vocabulary

The agent created symbols for each of the partitioned options as follows (all parameters set using 3-fold cross-validation):

1. A precondition mask was computed using feature selection with a support vector machine (SVM) [Cortes and Vapnik, 1995].
2. An SVM with Platt scaling [Platt, 1999] was used as a probabilistic precondition classifier, using states assigned to that partition as positive examples and all other states (including those from other partitions of the same option) as negative examples.
3. Kernel density estimation [Rosenblatt, 1956; Parzen, 1962] was used to model each effect distribution.
4. The reward model was learned using support vector regression [Drucker et al., 1997].

The agent identified 7 factors from the resulting partitioned probabilistic symbols: (playerx; playery; handle1angle; handle2-angle; key-x and key-y; bolt-locked; and goldcoin-x and goldcoin-y). The effect distributions were split into 30 distinct type 1 probabilistic symbols (duplicates were detected by a simple coverage interval and mean similarity test). The factors extracted, and the number of effect symbols defined over each factor, are shown in Table 1.

Constructing a PPDDL Representation

The agent constructed a PPDDL representation by recursing through possible combinations of symbols that overlapped with each partitioned option's precondition mask, and computing the probability of executing that option using Monte Carlo sampling (m = 100 samples). Operators estimated to be executable with a probability of less than 5% were discarded, and those with an estimated execution probability of greater than 95% were rounded up to certainty. This resulted in 345 operators; an example operator along with its grounding distributions is given in Figure 5.

Once the PPDDL description was constructed the agent was free to discard its grounding distributions and plan solely using the completely symbolic PPDDL representation. Table 2 shows the time required to compute a policy for the resulting PPDDL problem using the off-the-shelf mGPT planner [Bonet and Geffner, 2005] with the built-in lrtdp method and min-min relaxation heuristic. All policies were computed in less than one fifth of a second.

Related Work

The most closely related work is that of Jetchev et al. [2013], which uses a symbol-as-set definition of a propositional symbol, and then searches for the symbol definitions and a relational, probabilistic STRIPS description of the domain simultaneously. This method is based on a metric that balances predictability and model size, but is hampered by the size of the resulting search. It does not consider uncertainty in the symbol definitions themselves, but is able to find relational operators, which we leave to future work.

Similarly, the early framework described by Huber [2000] can describe transition uncertainty but not uncertainty in the symbols themselves. It is unclear how such uncertainty might be added, since this approach does not refer to low-level states but instead to the discrete states of a set of controllers, which are described in terms of their convergence conditions.

Several researchers have combined a given symbolic vocabulary with learning to obtain symbolic operator models for use in planning [Drescher, 1991; Schmill et al., 2000; Dˇzeroski et al., 2001; Pasula et al., 2007; Amir and Chang, 2008; Kruger et al., 2011; Lang et al., 2012; Mour˜ao et al., 2012]. Our work shows how to construct the symbolic vocabulary itself.

Option discovery is an active topic of research in hierarchical reinforcement learning; see the recent review by Hengst [2012]. This area is largely concerned with discovering an appropriate set of options in an MDP, the presence of which is assumed in our work.

Modayil and Kuipers [2008] use a learned model of the effect of actions on an object to perform high-level planning. However, the learned models are still in the original state space. Later work by Mugan and Kuipers [2012] use qualitative distinctions to adaptively discretize a continuous state space to acquire a discrete model suitable for planning; here, discretization is based on the ability to predict the outcome of executing an action.

Other approaches to MDP abstraction have focused on discretizing large continuous MDPs into abstract discrete MDPs [Munos and Moore, 1999] or minimizing the size of a discrete MDP model [Dean and Givan, 1997].

Conclusion

We have specified the symbolic representation required by an agent that wishes to perform probabilistic planning using a set of high-level actions. Our formalization enables an agent to autonomously learn its own symbolic representations, and to use those representations to perform efficient high-level probabilistic planning.

Acknowledgements

We thank the anonymous reviewers for their thoughtful suggestions. This work was supported in part by the NSF (grant 1420927). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. We also gratefully acknowledge support from the ONR (grant N00014-14-1-0486), from the AFOSR (grant FA23861014135), and from the ARO (grant W911NF1410433). GDK was supported in part by an MIT Intelligence Initiative Fellowship.

(:action jump_left_option319 :parameters () :precondition (and (notfailed) (symbol29) (symbol28) ) :effect (probabilistic 0.4723 (and (symbol17) (symbol1) (not (symbol28)) (not (symbol29)) (decrease (reward) 62.39)) 0.5277 (and (symbol20) (symbol1) (not (symbol28)) (not (symbol29)) (decrease (reward) 36.32)) ) ) (a) Generated PDDL Operator

(g) symbol1

Figure 5: The automatically generated PPDDL operator for one partition of the jump-left option (a), together with 50 samples drawn from each symbol's grounding distribution. The precondition distributions (symbol29 and symbol28, b and c) together indicate that the agent should be atop the concrete block in the center of the domain (d). Executing the option results in one of two y coordinate outcomes named by symbol17 and symbol20 (e and f). Both outcomes set the agent's x coordinate according to the distribution named by symbol1 (g). The two outcomes have different rewards-the failed jump costs more because the agent has to wait until it has fallen past the bottom of the ledge before it can finish moving left.