Decreasing Uncertainty in Planning with State Prediction

1 Introduction

Planning for real world environments often means planning with incomplete and uncertain information. For example, in robotic domains and other dynamic environments there can be large numbers of unknown areas and objects. Moreover, in dynamic environments planning has to be completed quickly. However, exploration and observation in these scenarios can be costly. This uncertainty has severe consequences for planning. The planning problem becomes more complex, taking longer to solve, and exacerbating the issue of scalability.

Some uncertainty can be handled during the planning process with, for example, contingency planning [Bonet and Geffner, 2000; Hoffmann and Brafman, 2005], conformant planning [Smith and Weld, 1998; Palacios and Geffner, 2006], probabilistic planning [Camacho et al., 2016], or replanning techniques [Brafman and Shani, 2014]. These approaches come with an associated cost in terms of complexity and robustness. Moreover, if the lack of information is severe, then the problem can be rendered unsolvable with current approaches.

We enhance the standard procedure of planning by adding the state prediction step between sensing and planning as shown in the Figure 1.

∗The research leading to these results has received funding from the European Community's Seventh Framework Programme FP7/2007-2013 (Specific Programme Cooperation, Theme 3, Information and Communication Technologies) under grant agreement no. 610532, SQUIRREL.

We propose an approach to reduce the uncertainty by making predictions about the state. We translate the state to a partially-known multigraph to enable prediction of the state with machine learning techniques. In particular, we exploit the method for prediction in partially-known multigraphs presented in [Krivic et al., 2015]. Missing edges are predicted by exploiting the similarities between known properties. We introduce a confidence measure for these edges. Edges with high prediction confidence are translated back to the state, decreasing uncertainty.

The resulting problem is consequently less costly to solve and plans generated require fewer sensing actions. The resulting problem can be passed to any kind of planning system. Incorrect predictions can increase the chance of plan failure during execution. We show in our evaluation, over a range of planning domains, the accuracy of the predictions is very high, and these cases are rare.

We integrated the prediction with a planning and execution system. Our system uses an adapted version of Maximum Margin Multi-Valued Regression (M3VR ) [Krivic et al., 2015] for learning missing edges. The planner CLG [Bonet and Geffner, 2000] is used to solve the resulting planning problems. We demonstrate in real scenarios, when contingency planning with CLG, prediction increases scalability, allowing the solver to tackle many more problems at an acceptable cost to robustness.

The paper is structured as follows. In Section 2 we present the problem formulation, and how a state can be represented as a partially-known multigraph. In Section 3 we describe the prediction process that acts upon a multigraph. In Section 4 we present the experimental results and we conclude in Section 5.

2 Predictions in the Planning Problem

In this section we describe in detail the problem of state prediction.

Definition 1 (Planning Problem) A planning instance Π is a pair 〈D, P〉, where domain D = 〈Pred, A, arity〉 is a tuple consisting of a finite set of predicate symbols Pred, a finite set of (durative) actions A, and a function arity mapping all symbols in Pred to their respective arities. The triple describing problem P = 〈O, s′ ,G〉 consists of a finite set of domain objects O, the partial state s′ , and the goal specification G.

The atoms of the planning instance are the (finitely many) expressions formed by grounding; applying the predicate symbols Pred to the objects in O (respecting arities). The resultant expressions are the set of propositions Prop.

A state s is described by a set of literals formed from the propositions in Prop, {lp, ¬lp, ∀p ∈ Prop}. If every proposition from Prop is represented by a literal in the state, then we say that s is a complete state.

A partial state is a set of literals s′ ⊂ s, where s is a complete state. A partial state s′ can be extended into a more complete state s′′ by adding literals.

Definition 2 (Extending a Partial State) Let s′ be a partial state of Planning problem Π. Extending the state s′ is a function Extend(Π, s′ ) : s′ → s′′ where s′ ⊆ s′′ and s′′ ⊆ s.

We describe a processing step implementing Extend. In order to be able to apply a machine learning technique to extend an incomplete state, we first translate it to a multigraph. Thus, the function Extend(Π, s′ ) is implemented as follows: (1) the partial state s′ is converted into a multigraph; (2) edges in the multigraph are learned using M3VR ; (3) the new edges are added as literals to the partially-known state.

2.1 Constructing the Multigraph

We represent a partially-known state s′ as a partially-known multigraph M ′ .

Definition 3 (Partially-knownMultigraph) A partiallyknown multigraph M ′ is a pair 〈V,E′ 〉, where V is a set of vertices, and E′ a set of values of directed edges.

The values assigned to all possible edges are {0, 1, ?} corresponding to {not-existing, existing, unknown}. We use E′ to denote a set of edge values in a partially-known multigraph, while E denotes the set of edges values in a completed multigraph M. The partial state s' is described as a partiallyknown multigraph with an edge for each proposition p ∈ P that is either unknown or known to be true. That is:

The existence of a directed edge epred(b, u) between two vertices b and u for a predicate pred is described by the function Lpred : V × V → {0, 1, ?}. Edges are directed in the order the object symbols appear in the proposition.

For example, let b and u be two vertices in set V . For proposition p involving objects b and u, Lpred(b, u) = 0 if ¬lp ∈ s′ , Lpred(b, u) = 1 if lp ∈ s′ , and Lpred(b, u) =? otherwise.

For an origin object b and a destination object u, we define the edge-vector as the vector:

This vector describes the existence of all edges directed from b to u. This is illustrated in an example below.

2.2 Example

Consider the problem where a robot is able to move between waypoints, pick up, push, and manipulate objects, and put them in boxes. The predicates can-pickup, can-push, can-stack-on, and can-fit-inside describe whether it is possible to perform certain actions upon objects in the environment.

In this problem we restrict our attention to four objects: robot, cup01, box01, and block01. In PDDL 2.1 [Fox and Long, 2003] literals that are absent from the state are assumed to be false. However, we assume those literals to be unknown.

A graph M is generated, the vertices of which are O := {robot, cup01, box01, block01} (Figure 2). An edge-vector example in this graph is given with:

This example edge-vector describes the edge between the nodes robot and block01. In the example state it is known that the propositions (can-fit-inside robot block01) and (can-stack-on robot block01) are false. It is also known that the proposition (can-push robot block01) is true. Finally, (can-pickup robot block01) is unknown.

3 PredictingMissing Edges in aMultigraph

Once a multigraph is created, a machine learning method can be used for completing a multigraph [Cesa-Bianchi et al., 2013; Gentile et al., 2013; Latouche and Rossi, 2015]. In our system we use the Maximum Margin Multi-Valued Regression (M3VR ) which was used at the core of a recommender system [Ghazanfar et al., 2012] and for an affordance learning problem [Szedmak et al., 2014]. Their results show that it can deal with sparse, incomplete and noisy information. Moreover, Krivic et al. [2015] use M3VR to refine spatial relations for planning to tidy up a child's room. We build on this, describing how the approach can be generalised for use in planning domains.

The structure of the multigraph represents the structure of the domain. Edges in the multigraph are partially known and thus this is a supervised learning problem. The main idea of M3VR is to capture this hidden structure in the graph with a model and use it to predict missing edges. This model is represented by a collection of predictor functions that learn mappings between edges and vertices.

Edges are directed. Therefore we differentiate between origin and destination vertices for each edge. B denotes the set of origin vertices and U the set of destination vertices, where B = U = V . Edges between the vertices describe a relation between the sets B and U. To predict a missing edge between two vertices, knowledge about other known edges involving those vertices can be exploited (Figure 3). This concept extends to predictions for n-ary relations.

Using M3VR we construct a function which captures knowledge about existing edges. This is done by assigning a predictor function fb to each origin vertex b ∈ B that maps all destination vertices to corresponding edges. Thus the number of predictor functions is equal to the number of vertices.

These predictor functions have to capture the underlying structure of a graph which can be very complex and nonlinear. Thus it can be very hard to define in Euclidean space. Therefore these functions are defined on feature representations of vertices and edges. Thus, we choose:

• A function ψ that maps the edges into a Hilbert space Hψ .
• Another function φ that maps the destination vertices u ∈ U into the Hilbert space Hφ which can be chosen as a product space of Hψ.

Hφ and Hψ are feature representations of the domains of U and E. The vectors φ(·) and ψ(·) are called feature vectors. This allows us to use the inner product as a measure of similarity.

Now prediction functions for each origin vertex b can be defined on feature vectors, i.e., Fb : Hφ → Hψ. We assume that there is a linear relationship in feature space between the feature vector of all destination vertices Hφ and the feature vector of all connected edges Hψ. This is represented by linear operator Wb. The non-linearity of the mapping fb can be expressed by choosing non-linear functions ψ and φ.

To exploit the knowledge about existing edges linking the same destination vertices u ∈ U, predictor functions for origin vertices are coupled by shared slack variables representing the loss to be minimized by the learners Fb. In this way, knowledge about existing edges is exploited to train prediction functions. Once determined, the linear mappings Wb allow us to make predictions of missing edges for elements b.

The similarity between the vectors Wbφ(u) and ψ(ebu) is described by the inner product 〈ψ(ebu),Wbφ(u)〉Hψ . If the similarity between Wbφ(u) and ψ(ebu) is higher, the inner product will have a greater value. As a consequence ψ(ebu) can be predicted as

Detailed descriptions of this procedure can be found in related work [Krivic et al., 2015; Ghazanfar et al., 2012].

In the optimization procedure for determining linear mappings there are as many constraints as the number of known edges in E′ . Therefore the complexity of the prediction problem is equal to O(|E′ |), where |E′ | stands for the cardinality of the set E′ .

The value of the inner product of the edge feature vector ψ(ebu) and Wbφ(u) should be interpreted as a measure of confidence of the edge belonging to a specific class (in this case 0 or 1):

where k ∈ {0, 1}, and L∗pred (b, u) is an unknown value in ebu ∈ E ∖ E′ of predicate pred.

For each prediction L∗pred (b, u), we update the existence of the directed edges:

Thus, the graph is completed and each edge is labelled by a confidence value.

3.1 Extending a Partialy-known State with Predictions

Given a complete multigraph and confidences, we extend the partially-known state s′ by adding literals to the state where confidence exceeds a predefined confidence threshold, that is,

where lp is the positive literal of proposition p, formed from predicate pred linking objects b and u, and ct is the confidence threshold.

For edges predicted not to exist in a graph with confidence higher than a threshold value ct, we extend the partiallyknown state s′ in a similar fashion:

For example, the partially-known graph in Figure 4 contains a dashed edge representing that the proposition (can-pickup robot block01) is unknown. Initially,

After prediction, Lcan-push(robot, block01) = 1, with confidence higher than ct. Therefore, the literal (can-pickup robot block01) is added to the current state.

4 Evaluation

The system integrates the prediction into a planning and execution framework, ROSPlan [Cashmore et al., 2015]. The M3VR method is integrated as a ROS service enabling its use as an automatic routine. Gaussian kernels, which appeared the best for this family of the problems, are used as the feature functions in M3VR with equal parameters for all domains and experiments.

With this framework we were able to generate randomised problem instances from four domains: tidy-room, inspired by the problem of cleaning a child's room with an autonomous robot presented in Krivic et al. [2015], courseadvisor, adapted from Guerin et al. [2012]; mars-rovers, a multi-robot version of the navigation problem of Cassandra et al. [1996], in which several robots are gathering samples; and persistent-auv, described by Palomeras et al. [2016]. The system together with all domains and test scripts is available and can be found at github.com/Senka2112/IJCAI2017. The system can be easily used with other domains as well.

4.1 Evaluating State Predictions

To evaluate prediction accuracies we generated examples of states in each domain varying the size of the problem and the percentage of the knowledge on the state. The problem size is varied by increasing the number of objects from 5 to 100 by an increment of 5. The knowledge is varied by generating complete states and removing literals at random. Percentages of knowledge used in tests are 0.5%, 1%, 2%, 3%, 5%, 8%, 10%, 20%, 30%, 40%, 50%, 60%, 70%, 80%. To examine the reproducibility of prediction problems we randomly generated 10 states for each combination of the percentage of knowledge and problem size utilizing 10cross-fold-validation. Thus, for each domain were generated 20×14×10 problems in total.

The prediction was applied to every problem and results were compared to the ground truth. To examine the lower limit on problem size, we extracted which amount of the known data that is needed to achieve accuracy higher than 90%. This is shown in the Figure 5. The number of learned relations is large for each domain: with 20% of the known predicates and with 20 objects, accuracy is higher than 90% for all domains except mars-rovers.

Accuracy increases with the size of the problems. With

40 objects in the each problem domain only 8% of known data is enough for accuracy over 90%. Course-advisor and persistent-auv domains contain more instances of objects and more predicates compared with the other two domains. This results in larger networks. Thus, for these domains, the accuracy is better for smaller numbers of objects as well. The high accuracy of predictions in these domains indicates domains with structure and order. Compared to other domains, the rovers domain appears to be the most unbalanced. With a small number of objects and initial knowledge, it is harder to capture the structure. Thus 60% initial knowledge is required to achieve 90% accuracy in the case of 15 objects.

The confidence for predictions is taken directly from the learning algorithm as described in the Section 3. It represents the measure of similarity between the learner output vector and the feature vector representing the existence of an edge. Figure 6 demonstrates the mean values of confidences for all four domains in case of 20 objects and varying percentage of initial data. Confidence saturates very quickly which corresponds the high accuracy results given in the Figure 5. This is the result of the structure which appears in the networks and which are captured by learners. Moreover, since the datasets were created by randomly removing knowledge, many vertices remained connected to the graph and their existing edges were exploited for predictions. The prediction confidence is expected to be very low for vertices for which no known edges exist within the rest of the graph.

The high accuracy and confidence allows us to solve many otherwise unsolvable instances, while maintaining a high degree of robustness.

4.2 Evaluating Robustness

We investigate whether the high accuracy results in robust prediction. We make the problem deterministic by accepting all predictions with any positive confidence. The problem instances were made deterministic using prediction, and also by a baseline of assuming unknown propositions to be true. The problems were solved using POPF [Coles et al., 2010]. The resulting plans were validated against the ground truth using VAL [Fox, 2004]. The results are shown in the Figure 7, showing that even for > 30% of Known Data, the prediction leads to robust plans.

Without prediction, none of our problems could be solved using a deterministic planner. Even with knowledge of 80% of the state, the goal was not in the reachable state-space. To provide a more illustrative analysis, we generate a relaxed plan-graph (RPG) and count the number of reachable actions before and after prediction.

Figure 8 shows the number of new reachable actions as a percentage of the total number of reachable actions in the ground truth. The increase in reachable actions is very large, especially with a smaller amount of Known Data. This increase in valid actions enabled by the prediction demonstrates an increase in size of reachable state space.

The prediction can be applied with a high confidence threshold, removing some uncertainty. Conditional planning can be used to deal with the remaining uncertainty by executing sensing actions to observe remaining unknown propositions.

4.3 Evaluating with Conditional Planning

Sensing actions were introduced into the tidy-room domain, allowing the agent(s) to determine the ground truth of unknown propositions. Problems were generated as described above, with 10% to 80% initial knowledge and 10-fold cross validation. All of the problems involve 20 objects. The number of goals was varied from 2 to 6. We used the planner CLG [Albore and Geffner, 2009] (offline mode) to solve problems in these extended domains, with a time limit of 1800 [s]. The prediction was applied before a single planning attempt. We recorded the time taken to solve and the duration of the execution trace of the contingent plan. The solution times are shown in Figure 9.

For problems with 5 goals and 6 goals, the problem could not be solved by CLG without predictions within the time limit. With prediction these problems were solved with an average of 89 [s]. These results illustrate the benefit of prediction in enhancing the scalability of contingent planning. The plan duration shows another benefit of state prediction in the quality of the plans produced: predictions can be used to avoid spending time on sensing actions when the confidence is high.

5 Conclusion

An agent can build hypotheses on unknown relations in the world model by exploiting similarities among the existing and possible relations. In this paper we have shown how uncertainty in planning can be decreased with predictions made by exploiting these similarities. We presented a system for such an approach where a state with uncertainty is represented as a partially-known multigraph, we showed how M3VR is used to predict edges in such a graph, and finally showed how these edges are reintroduced into the state as predicted propositions. This procedure is performed online.

We use the confidence values of predictions, filtering the number of unknown facts verifiable by sensing action. A lower confidence indicates a proposition that should be verified by a sensing action, while a high confidence prediction indicates a proposition that can be assumed true (or assumed false).

We have shown that with 20% knowledge of the state the accuracy of the state prediction is 90% with prediction tests in four different domains. We also demonstrated that the accuracy of the predictions leads to plans that are robust, and increase the scalability of our planners.

We noted that the high accuracy is in part due to the fact that many vertices remained connected to the graph after knowledge was randomly removed. This is not always the case in practice. In future work we intend to investigate how predictions can be used in order to inform a contingent planning approach. In particular, by directing the executive agent to perform sensing actions that connect disconnected nodes. These actions, while not supporting actions leading towards the goal, will allow for a higher confidence prediction of many other facts involving similar objects. This also might include new definitions of the prediction confidence measure.