Learning Subjective Representations for Planning

1 Introduction

Planning, at its essence, involves searching an appropriately defined state space. This state space is a consequence of the agent's model of the effects of its actions (e.g., STRIPS [Fikes and Nilsson, 1971], Markov Decision Processes [Puterman, 1994]). It is assumed that these models can be defined from domain experts and planning uses these models to find sequences of actions to achieve given goals. The problem is that models are not always known or easily built for a domain of interest. Others have studied methods for learning or agumenting models, such as STRIPS operators [Wang, 1995] or MDP transitions [Peng and Williams, 1993]. All of these techniques still require expert intuition about the domain to provide, at the least, an appropriate state representation.

This paper focuses on learning an appropriate representation for planning, using only an agent's observations and actions. We call this a subjective representation as the learned representation is extracted based only on the agent's experience, and requires no expert knowledge of the domain. The approach solves two important problems: (i) learning an appropriate state-space representation, and (ii) learning the effects of the agent's actions in this representation. 1 The required input is a sequence of actions and observations from the agent's subjective experience, but no semantic meaning (domain-specific or otherwise) is required. This input is used in a three step process.

1 The approach of learning a subjective representation more

First, Section 2 reviews Action Respecting Embedding (ARE). ARE is a technique for dimensionality reduction that specifically makes use of a temporal sequence of observations and actions. ARE learns manifolds that capture the important underlying dynamics of the high-dimensional data in much fewer dimensions (addressing the first problem). Next, Section 3 describes a method for learning operators for each action that can be applied to any point in the learned representation (addressing the second problem). Examples of learned operators are provided along with a discussion of how the semantic meaning of the associated actions can sometimes be extracted. Finally, Section 4 shows the results of planning in the resulting representation using the learned operators. Both the resulting plan in the learned representation, and the result of applying the plans in the original high-dimensional domain are compared.

2 Action Respecting Embedding

High-dimensional data sets, such as sequences of images, can often be characterized by a low-dimensional representation that is related to the process generating the data. For example, a low-dimensional representation for image data may correspond to the degrees of freedom of a platform moving a camera. Such a representation is ideal for planning as it directly captures the actions' effects on the world. The goal here is to take a temporal sequence of data points, z1, . . . , zn, and associated actions, a1, . . . , an-1, and find a low-dimensional representation for zi that is appropriate for planning.

Recently, nonlinear manifold learning techniques have been used to map a high-dimensional dataset into a smaller dimensional space. Semidefinite Embedding (SDE) [Weinberger and Saul, 2004] is one such technique. SDE learns a kernel matrix, which represents a non-linear projection of the input data into a more linear representation. It then uses Kernel PCA [Scholkopf and Smola, 2002], a generalization of principle components analysis using feature spaces represented by kernels, to extract out a low-dimensional representation of the data. The kernel matrix K is learned in SDE by solving a semidefinite program with a simple set of constraints. The most important constraints encode the common requirement in dimensionality reduction that the nonlinear embedding should preserve local distances. In other words, nearby points in the original input space should remain nearby in the resulting feature representation. Therefore SDE requires a distance metric || · || on the original input space, and uses this metric to construct a k-nearest neighbors graph. It then adds constraints into the semidefinite program to ensure that the distance between neighbors is preserved. The optimization maximizes Tr(K), i.e., the variance of the learned feature representation, which should minimize its dimensionality. The SDE Algorithm is shown in Table 1.

closely resembles recent work on learning predictive representations [James and Singh, 2004; Rosencrantz et al., 2004; Jaeger, 2000] than previous work on augmenting operators or transition probabilities. This approach, though, is specifically designed for very high-dimensional observation spaces as it implicitly involves a dimensionality reduction component.

SDE does not take into account two important pieces of knowledge about the data: the temporal ordering of the input vectors, zi, and the action labels, ai. Therefore, SDE doesn't guarantee that temporally-nearby input points will be spatially nearby in the feature representation. Also, SDE won't necessarily result in a space where actions have a simple interpretation. The recent Action Respecting Embedding (ARE) algorithm [Bowling et al., 2005] extends SDE to make use of exactly this type of knowledge about the data.

Formally, ARE takes a set of D-dimensional input vectors, z1, . . . , zn (e.g., images), in temporal order, along with associated discrete actions, a1, . . . , an-1, where action ai was executed between input zi and input zi+1. ARE then computes a set of d-dimensional output vectors x1, . . . , xn in one-toone correspondence with the input vectors. This provides a meaningful embedding in d < D dimensions. ARE modifies SDE in two key ways. First, it exploits the knowledge that the images are given in a temporal sequence. It uses this knowledge to build an improved neighborhood graph based on each input's distances to its temporal neighbors using the provided local distance metric 2 . Second, it constrains the embedding to respect the action labels that are associated with adjacent pairs of observations. This ensures that the actions have a simple interpretation in the resulting feature space.

It is this second enhancement of ARE that is the critical feature for subjective planning. ARE constrains the learned manifold to be in a space where the labeled actions correspond to distance-preserving transformations-those consisting only of rotation and translation 3 . Therefore, for any two inputs, zi and zj, the same action from these inputs must preserve their distance in the learned feature space. Letting Φ(zi) denote input zi's representation in the feature space, action a's transformation, fa, must satisfy:

2 We have found that ARE is fairly robust to the choice of distance metrics, and use simple Euclidean distance for all of the experiments in this paper.

Now, let a = ai and consider the case where aj = ai. Then, fa(Φ(zi)) = Φ(zi+1) and fa(Φ(zj)) = Φ(zj+1), and Constraint 1 becomes:

In terms of the kernel matrix, this can be written as:

ARE simply adds Constraint 3 into SDE's usual constraints to arrive at the optimization and algorithm shown in Table 2.

Experiments. Here we define IMAGEBOT, a synthetic image interaction domain used for all experiments. Given an image, imagine a virtual robot that can observe a small patch on that image and also take actions to move the patch around the larger image. This "image robot" provides an excellent domain in which subjective planning can be demonstrated.

For these experiments, IMAGEBOT will always be viewing a 200 by 200 patch of a 2048 by 1536 image displayed Figure 1. IMAGEBOT has eight distinct actions: four translations, two zoom actions, and two rotation actions. The allowed translations are forward (F), back (B), left (L) and right (R) by 25 pixels The zoom changes the scale of the underlying image by a factor of 21/8 (i) or 2-1/8 (o). The rotation rotates the square left (l) or right (r) by π8 radians.

There are three distinct experimental data sets that are looked at in this paper.

3 Notice this is not requiring the actions in the objective space to be rotations and translations, since ARE is learning a non-linear feature representation.

AT : IMAGEBOT follows a path which looks like an "A" using only the translation actions:

F × 10, L × 5, R × 5, B × 5, L × 5, F × 5, B × 10

• AZ: IMAGEBOT follows the same A pattern but substituting zoom in for left actions and zoom out for right actions: F × 10, i × 8, o × 8, B × 5, i × 8, F × 10, B × 20

Fr: IMAGEBOT moves back and forth in a line, but only using F and r actions:

F × 10, r × 8, F × 10, r × 8, F × 5, r × 16, F × 5

Note that in AZ the F and B actions only move half as much when zoomed in as when zoomed out. Note that in Fr there are no opposites for the two actions used. An example of the output of IMAGEBOT, and correspondingly an input for ARE, is shown in Figure 2. These are the images seen in the AT data set. Note that while we know that, for example, action label 3 corresponds to action F, ARE gets no such semantic information-it gets as input only the images and the labels associated with them.

The effectiveness of ARE has been demonstrated previously [Bowling et al., 2005]. Here evidence is shown of its power in capturing useful representations for planning. Figure 3 shows the actual manifold underlying the AT test set (i.e., IMAGEBOT's path). Figure 4 shows the manifold learned by ARE on that test set. Clearly the structure has been captured.

Figure 5 shows a "top" view and a "side" view of the 3dimensional manifold learned for the Fr data set. here the portion of the manifold corresponding to rotating to the right (r) is a black line while the portion corresponding to moving forward (F) is a light-gray line. The point corresponding to the first image is circled. Although not as clear as in the previous case, this manifold is clearly and distinctly capturing the structure of the original path, with two dimensions capturing the r action and a third capturing the F action. In Figure 3, the original domain was one in which the actions were distance-preserving and this structure was, indeed, extracted. In Figure 5 it is not immediately obvious what manifold will be learned which makes the resulting one all the more impressive-not just as a representation appropriate for planning but as an aid to intuitive understanding of the original underlying structure.

3 Distance Preserving Operators

ARE learns a representation with explicit constraints that the actions correspond to distance-preserving transformations in that representation. Before one can plan, though, one needs to discover these transformations. For each unique action a there is a collection of data point pairs (xt, xt+1) which are connected by that action. Another way of thinking of this is that there is a function fa where fa(xt) = xt+1, and such a function needs to be learned for each action. Because of the distance-preserving constraints, fa can be represented as:

Recall that transformations of the above form encode translation in the ba vector, and rotation and scaling in the Aa matrix. Aa and ba could be learned using simple linear regression but scaling is not distance preserving so there is the additional constraint that Aa does not scale, i.e., ATa Aa = I. It turns out that this is similar to the extended orthonormal Procrustes problem [Schoenemann and Carroll, 1970], but without allowing for a global scaling constant. Here the solution to the regression problem is derived.

Let Xa be the d by n matrix whose columns are xt for all t such that at = a, and let Ya be the d by n matrix whose columns are xt+1 for the same t. The goal is to learn a rotation matrix Aa and a translation ba which maps Xa to Ya. Formally, the following optimization problem needs to be solved.

where e is a column vector with n ones.

In order to obtain the least squares estimation of Aa and ba, write the Lagrangian function L:

where Λ is a matrix of lagrangian multipliers, and Tr(.) stands for the trace of a matrix.

Now take the derivative of the Lagrangian function with respect to the unknowns and set to zero:

The translation vector from Equation 5 gives:

Multiplying Equation 4 by ATa /2 on the right:

Since the left hand side is symmetric, the right hand side must also be symmetric. Substituting Equation 6, the right hand side can be written as:

where the last term is symmetric. Thus the rest of the expression must also be symmetric. This can be simplified as:

Since 7 is symmetric, it should be equivalent to its transpose:

One can easily verify that the following satisfies Equation 8:

where svd(·) is the singular value decomposition, so,

because W T W = I (since W is orthonormal) and S = ST (since S is diagonal). Thus Equations 6 and 9 are a solution to the dual function, D = minΛ L(Aa, ba,Λ). Since this solution is also feasible with regards to the primal problem, strong duality holds even though the original problem is non-convex.

Results. Figure 6 shows the two-dimensional representation that ARE generated for AT . The solid arrows show a path which consists of new points resulting from the application of operators learned for each action (F, B, L and R) as described above. Clearly, the operators are intuitively capturing the essence of the actions used to generate the data.

Note that while there is no semantic meaning given with the input actions, such meaning can now be derived. It can easily be tested whether a pair of actions are opposites, such as (F,B) or (R,L). Also two actions can be tested for orthogonality or independence, such as F and R. If the learned representation captures some underlying structure within the data, the learned operators will maintain that structure and, from them, relationships can be successfully hypothesized.

Figure 7 is similar to Figure 6, except the underlying representation is from the AZ data set. Here, note that while some actions are again opposite to each other, no actions are orthoganal-the F and B actions are not independent of the i and o actions. This critical facet of the original data set has been successfully captured in the representation learned by ARE and consequently in the action functions learned in that manifold. Note, in particular, that when zoomed in all the way (i × 8) 10 F actions are equivalent to 5 F actions when zoomed out all the way. Although F action when zoomed in half way was never observed, the learned operators capture the fact that between 7 and 8 F actions at this scale are equivalent to 5 and 10 actions at the other scales.

4 Planning

Now that low-dimensional representations and operators in those representations can be learned, all the pieces are in place to perform planning. The points in the learned representation are states, and the operators learned in Section 3 define transitions between the states. This new domain has two advantages over the original data set. First, the dimensionality has been reduced drastically (from 40,000 to 2 or 3). Second, from the action labels functions have been learned for each unique action that explicitly give the resulting state when that action is applied from any state. Learning such a function in the orignal space is not only intractable, but would require application of knowledge specific to IMAGEBOT (or even the underlying image) in order to attain any success.

Given any two images, one can find a shortest path between them, even if it traverses unobserved parts of the space. First, find the corresponding points in the low-dimensional representation, then find the shortest path between them using traditional search methods and the set of learned operators. Since each operator in the low-dimensional space corresponds to an action label in the orginal space the list of action labels that indicate the desired path can be returned. For the following results, iterative-deepening depth-first search was used and the path whose final point was closest to the desired goal was returned. The quality of a path is demonstrated by starting IMAGEBOT at the initial state, applying the sequence of actions and showing the resulting image.

Results. For each of the three test sets, two sub-figures will be shown. The first shows the representation learned for that data set and the shortest path between a chosen initial state (labelled with a triangle pointing right) and a chosen goal state (labelled with a triangle pointing left). The second figure contains two images. The left image shows the image at the initial state, the right image contains two highlighted boxes. The light-gray dotted box shows the image at the goal state, the darker-gray solid box highlights the image obtained after executing the resulting sequence of actions.

Figures 4(a) and 4(b) show the results for AT-the goal state image and the image corresponding to the final state in our path in Figure 4(b) are the same. Note that the shortest path was successfully found, even though it involves moving through portions of the space that we have never seen.

Figures 4(c) and 4(d) show the results for AZ-the goal state image and the image corresponding to the final state in the path in Figure 4(d) are the same. Note, the path found successfully identifies that action B must occur before action o-if taken after then the B action would jump over the desired end state to a state halfway between it and the next state.

Figures 4(e) and 4(f) show the results for Fr-the goal state image and the image corresponding to the final state in the path in Figure 4(f) are very close to each other. Recall that for this data set, unlike the others, the only actions were F and r with no corresponding opposites. This means that such a path must rotate all the way around, step forward, then rotate all the way around again-a fairly complex path.

5 Conclusion

ARE can be used to learn a subjective representation appropriate for planning. The only input required is a sequence of observations and actions-no additional domain-specific knowledge is necessary. The output from ARE is a new lowdimensional space which captures the critical dynamics of the environment. Operators which reflect these dynamics can be recovered in the new space. Simple search procedures can then can be used to find sequences of operators which achieve goals in the learned representation. Since operators correspond to original actions, this sequence provides a plan in the original space. These plans are accurate, even though they can involve actions in unobserved parts of the space.

Acknowledgments

We thank Finnegan Southey, Dale Schuurmans, and Pascal Poupart for discussions and insight. We thank Wesley Loh for helping with implementation details. We acknowledge Alberta Ingenuity Fund for their support of this research through the Alberta Ingenuity Centre for Machine Learning.