Refinement Planning Mandatory reading for next class (summary required before class--post as a comment on the blog)
Here is the paper you have to read for next class. You will be required to write and post a summary of the paper as a comment to this posting on the blog
The paper introduces a generalized approach to plan synthesis called refinement planning and relates it to various other plan synthesis approaches. The basic idea behind refinement planning is to start with the set of all possible action sequences and narrow it down to the set of all solutions. The sets of action sequences are represented in terms of partial plans. Plan synthesis in refinement planning involves a split and prune approach. Splitting is done by separating the components in a plan set into different search branches. The motivation for this is to reduce the time involved in looking for a solution. The pruning is done by applying refinement operations. The motivation here is to get rid of nonsolutions from the candidate set. There are various refinement strategies used for this purpose. A refinement strategy maps a plan set P to a plan set P' such that the candidate set of P' is a subset of the candidate set of P. The refinement strategy is progressive if the candidate set of P' is a strict subset of that of P and is strongly progressive if the length of the minimal candidates increases after the refinement. The strategy is systematic if no action sequence falls in the candidate set of more than one component of P'. The refinement strategy is complete if P' contains all the solutions that P contains. Planning using refinement strategies basically checks if the plan set P has a minimal candidate that is a solution and terminates if it does. Else, a refinement strategy is applied in order to obtain P' and the whole process is repeated.
Introducing splitting into refinement is done by separating each component into a different search branch. The refinement strategies can be broadly classified into 4 types - state space, plan space, task reduction and tractability refinement. State space refinement is of two types - forward state space and backward state space. Forward state space deals with adding actions to the prefix of the plan sequence such that the preconditions are satisfied by the effects of the head step. Backward state space refinement deals with adding actions to the suffix of the plan sequence such that the effects of the actions satisfy the preconditions of the tail step. The preconditions to the actions added might have to be updated. Plan space refinement deals with selecting an open condition and finding actions that satisfy the open condition. This also means that additional constraints might have to be added which might increase the number of open conditions. Hierarchical refinements deal with introducing non-primitive actions that can be reduced to primitive tasks using user-defined reduction schema. The planner's access to the primitive tasks is restricted because of the reduction schema. This is useful when a user has a priority for some solution. Tractability refinement can be classified into 3 categories. The first category consists of preorder refinements which order two unordered steps(actions) and prepositioning which constrain the relative positions of two steps. This is done in order to reduce the number of linearizations of the plan. The second category attempts to make all linearizations safe with respect to auxiliary constraints. This category contains presatisfaction refinements which splits the plan in such a way that a given auxiliary constraint is satisfied in all the linearizations of the components. This refinements use three strategies - promotion, demotion and confrontation. The third category of tractability refinements attempts to reduce uncertainty in action identities. One of the refinements is prereduction that converts a plan containing non-primitive actions to a set of plans. All the refinement strategies can be interleaved in order to solve a single planning problem. The paper also discusses about the role of least commitment in planning. Commitment reduces the time taken to check for a solution but increases the probability of backtracking. Least commitment makes a difference only when a planner splits the components into different search branches.
The paper also discusses about the tradeoffs in the different choices of refinement specifically, asymptotic tradeoffs and emperical results of tradeoffs among tractability and protection strategies. The paper also discusses about the problems of the planners with scaling up and gives two approaches to deal with scaling up. The first approach is through customization. One way is to bias the search of the planner by using the knowledge of the user. Non-primitive actions and reduction refinements can be used for this. Another way is to use machine learning techniques in order to make the planner learn from its successes and failures. The second approach to deal with scaling up is to reduce the search space by using disjunctive representations and constraint satisfaction techniques. Disjunctive techniques can be applied to state space refinements or plan space refinements by allowing disjunctive constraints. The refinement strategies need to be generalized in order to handle disjunctive plans. For forward space refinements, an actions can be selected only if its preconditions are subsumed by the union of the effects of the previous action. However, there might be a problem with disjunctive contraints in that the actions in the disjunction may not be executable at the same time. This would mean that the effect is not the union of the effects of all actions in the disjunction. One way to handle this is to make the effects of actions that cannot occur at the same time as mutually exclusive as done in graph plans. The paper then discusses the open issues with planning using disjunctive representations.
The paper begins with an overview of the main elements of the classical planning problem (which are also applied in more relaxed planning scenarios): states, goals, and actions. It briefly describes how actions can be applied progressively and regressively, and how plans can similarly be verified as solutions by progressively or regressively simulating the effects of their action sequences. This is followed by a historical summary of main conceptualizations of the classical planning problem. Next, elements of the key terminology of refinement planning are introduced, including partial plans, candidates, plan sets, components, candidate sets, and the terms "split" and "prune" (as applied to refinement planning). Partial plans are declared to be expressible as sets of constraints, consisting of four total subtypes of two different types of constraints: precedence and contiguity constraints make up the "ordering constraints," while the "auxiliary constraints" consist of interval-preservation constrains (IPCs) and point-truth constraints. A distinction is made between linearizations of partial plans, which obey all ordering constraints, and safe linearizations, which obey all constraints of both types. Candidate sets are then presented as being the "semantic" consequences of specific partial plans (while the constraints discussed earlier compose the "syntax" of the partial plan). To make practical use of candidate sets derived from partial plans, the concept of a minimal candidate is introduced; it is shown that the minimal candidates of a partial plan have a one-to-one correspondence with that partial plan's safe linearizations.
Next, characteristics of refinement strategies -- procedures which modify a partial plan in such a way that the resulting candidate set becomes a subset of the candidate set at the time that the procedure was invoked -- are discussed, including the attributes progressive, strongly progressive, and systematic, as well as the concept of the progress factor. A general algorithm for applying refinement strategies is then presented. The paper then discusses a modified algorithm for use with strategies that divide the components of the partial plan into the search space. Following this, the paper introduces more terminology for use in discussing existing refinement strategies, including the concepts of the head and tail of a plan, head and tail steps, the head and tail fringe, and "middle steps." Forward state-space refinement is presented first, and is described as growing the head (prefix) of the plan; the concept of combining "noninteracting" actions is discussed as one way of improving performance. This is followed by a discussion of two approaches for using goal-directed refinements to reduce the number of unnecessary actions which are considered. First, means-ends analysis is presented, including its somewhat flawed implementation in the early STRIPS planner, and as well as techniques which could be used to make means-ends analysis computationally complete. The second approach is the use of backward state-space refinement, which grows the tail of a plan by applying actions regressively. It is stated that backward state-space refinement is generally more efficient that forward state-space refinement, although the use of complete states in the latter approach may be desirable when applying "effective search-control strategies."
The discussion then turns to the concepts of applying plan-space refinements, as opposed to the state-space refinements used in more traditional approaches. An algorithm is presented which provides a general strategy for planning using plan-space refinements, including an optional bookkeeping step for introducing IPCs. Other concepts are introduced by means of an ongoing "rocket world" example, including causation preconditions (preconditions for achieving a particular conditional effect from an action), as well as the three general strategies for de-clobbering. Hierarchical refinement is then discussed, including the use of non-primitive actions and corresponding reduction schemas to apply specific restrictions to actions used in a plan in order to reflect the "desirability" of a solution. Tractability refinements are then discussed; there are three types, described as those which "attempt to reduce the number of linearizations" in a plan, those which seek "to make all linearizations safe," and those attempting to "reduce uncertainty in the action identity." The first category contains preordering and prepositioning refinements; the second category consists solely of presatisfaction refinements; in the third category, prereduction refinements are given as an example. It is stated that most planning algorithms differ primarily in how they apply tractability refinements.
Next, following an example use of multiple, interleaved refinements to solve a planning problem, a general comparison of characteristics of planning approaches is given, which expresses how the search space of planning, the difficulty of extracting solutions from partial plans, and other considerations relate to each other. Next, the author (whoever he is) discusses his own research into the effects of applying different types of refinement techniques. This is followed by two potential approaches for scaling planning for application to large problems. The first strategy is the use of domain-specific customization; the second is to use disjunctive representations in combination with existing approaches for constraint-satisfaction. The second strategy is discussed in some detail, including the nature and consequences of disjunctive representations in plans, and how some planners, such as GRAPHPLAN, resolve disjunctions. One last generalized refinement algorithm is presented, and then the paper concludes with an overview of relevant contemporary developments and potential avenues for research.
[From Thad Boyd] I noticed the other day that I haven't been receiving class E-Mails and can't post to the blog. I looked up my registration information and discovered that, while my override for your class was processed two weeks ago, I was never enrolled. I'll bring a late add form to class today; in the meantime, since I can't post comments to the blog, here's the article summary for today's class.
--- This paper unifies all classical planning methods as subtypes of refinement planning, which starts with all possible states and actions and narrows the results, reducing candidate set size while increasing the length of minimal candidates. The two major refinement strategies are and state-space and plan-space; other strategies include tractability refinement and task reduction. In all cases, a plan split up into sub-plans.
State-space refinement can be performed either forward or backward. Forward state-space refinement entails adding actions to the plan prefix whose preconditions are satisfied by the head step, while backward adds actions to the suffix whose effects satisfy the preconditions of the tail step.
Plan-space refinement emphasizes finding actions to meet conditions; actions take priority over states. A step t is selected to meet a precondition C prior to a state s; any step between t and s must preserve C.
Tractability refinements do not reduce the size of a given candidate set, but reduce the costs of processing the plan. They may reduce the number of linearizations in the plan through preordering or prepositioning, make linearizations presatisfy constraints through promotion, demotion, and confrontation, or reduce uncertainty in actions, as in prereduction refinement, which splits a plan containing a nonprimitive action into a set of smaller plans.
Of course, each type of refinement has its advantages, and optimization depends on the problem. The paper speaks of asymptotic tradeoffs, and explores ways to select appropriate refinement strategies. It speaks first of subgoal interaction analysis, and explains that the best guideline is to select the refinement planner with the highest commitment and the highest number of trivially-serializable goals. It then refers to scaling up planners through customization and disjunctive representations. Customization refers to tailoring the planner's search to the specific problem, eg through the user's knowledge or through the program's own learning. Disjunctive representations compact multiple plans into smaller disjunctive steps with disjunctive constraints. Disjunctive representation of state-space refinements sacrifices a measure of progressivity, but pruning is still possible, as in cases of interactive steps and steps which must occur in a given sequence.
The paper closes by listing some known issues with disjunction, then outlining how different types of planning all fall under the umbrella of refinement planning through the principles described earlier.
Important vocabulary for refinement where plan P is mapped to subset P': complete: P' contains all solutions of P progressive: the candidate set of P' is a strict subset of the candidate set of P (prunes candidate set) strongly progressive: length of minimal candidates increases from P to P' systematic: no action sequence appears in the candidate set of more than one component of P' progress factor: the ratio of the size of the candidate set for P' to the size of the candidate set for P subgoal interaction: when a planner backtracks into the plan for one subgoal in order to achieve another subplan: a partial plan whose linearizations will all execute and achieve its given subgoal trivially serializable: subgoals G1 and G2 are trivially serializable if every subplan of one goal can be refined into a subplan for both goals.
Refinement planning is presented as a superset of existing methods in planning, unifying them into a more general conceptual framework.
Refinement planning works by modifying partial plans over multiple iterations to reach a set of solutions.
A refinement solution is said to be progressive if the number of minimal candidates decreases and no new candidates are introduced, and it is said to be strongly progressive if the length of these minimal candidates increases.
Many types of refinement strategies are presented, including forward and backward state-space refinements, whereby actions are added to the head or the tail of the partial plan, respectively.
Position, relevance, and plan-space refinement strategies are also presented, whereby the exact position of a new action is not necessary for refinement, valuing the concept of least-commitment.
Tractability refinements are the last set of strategies presented. Tractability refinements are not progressive, but rather move handling of disjunctions into the search space.
Trade-offs between refinement strategies are analysed in terms of the cost of handling plan sets versus the amount by which a given strategy increases the size of the search space. Strategies that are progressive will reduce the search space, but also have a high cost in terms of managing/refining the plan sets, whereas tractability refinements, for example, are designed to decrease that cost while increasing the size of the search space.
This paper introduces a generalized approach to classical planning known as refinement planning. The author aims to show that most planning algorithms that are applied towards classical planning are special cases of this envelope concept, and that by analyzing the issues involved in planning at the higher level of refinement planning, various planning approaches can be analyzed objectively and applied towards problems sets for which they are among the best methods available.
An introduction to planning and its classical realm is offered, and a history of planning systems from the times of planning as theorem-proving to CSP satisficing is provided for contextual reference. The author then provides an overview of refinement planning, which is defined as the process of starting with the set of all action sequences and gradually narrowing it downt o reach the set of all solutions.
Following the introduction, the syntax and semantics of partial plans are introduced. This section is extremely important in that not only does it introduce the nomenclature used in the rest of the paper, but also that partial plans form the basis of the rest of the discussion dealing with refinement planning approaches. As evinced by the definition, refinement planning is the refinment of partial plans using various techniques to achieve the goals of classical planning.
Then, in what forms the core of the paper, refinment strategies are introduced, and each strategy is correlated with the types of planning algorithms that it simulates. The first among these is Forward State-Space Refinement, which involves growing the prefix of a plan by introducing actions into the set of all actions contiguous with the initial state (known as the head fringe). Forward state-space refinement corresponds to the ideas behind what is commonly known and understood as progression in classical planning terms.
Another classical planning technique, regression, can be modelled by the second refinement strategy mentioned, which is backward state-space refinement. The interesting comparison in this section is that since backward state-space refinement is goal-focussed, it has a lower branching factor than its forward counterpart. However, this is offset by the fact that backward refinement works with the set of partially specified states, whereas forward refinement works with completely specified states.
The next set of refinements are grouped under the umbrella of plan-space refinements. In this section, there is some discussion of least commitment and the parallels in ideas between plan-space planning (partial order planning is an example) and plan-space refinement.
The last refinement technique that is talked about is Hierarchical Refinement, which allows plan users to have preferences among solutions. This refinement technique is important because all the techniques introduced uptil this point consider all plans equal as long as they are valid minimal (in terms of number of actions) solutions to the planning task at hand. However, with the use of hierarchical refinement, nonprimitive actions can be used to control and limit the plans that are acceptable as solutions.
After the plan-space refinement strategies are introduced and explained, the focus of the paper turns to tractability issues and how plans may be further refined with an eye to efficiency. Three categories of refinements are introduced with respect to this notion. The author then goes on to present an argument that interleaving refinement strategies could improve planner performance, and that the nature and success of such interleaving could depend on the problem and solution density.
The paper approaches its conclusion with a discussion of the asymptotic and empirical trade-offs involved. The asymptotic section fails to make any conclusive predictions, and it is left to the empirical analysis to show how the various refinement strategies work for various scenarios, based on a number of factors, such as the plan handling costs and the size of the fringe in the plan space.
The final technical contribution comes in the form of methods to scale refinement planning up. The first such method presented is customization, in which there are 2 sub-types: either a user or domain expert can feed in control knowledge to the planner, or the system can be subject to learning from its failures and successes. The other method presented for scale-up is through disjunctive and constraint satisfaction techniques. The paper concludes by talking about open issues in refinement planning, and the potential that lies in applying this unified framework to non-classical planning streams as well.
The paper presents a new generalized approach to plan synthesis, called Refinement Planning. The first sections of the paper discuss the basis of planning, what is planning and classical planning and how can we specify them and how to model and specify actions and states. In addition, it describes two basic ways of action application, progression and regression, and the conditions and processes involved in these. The basic overview part of the paper ends with a short section on the various planning approaches and their chronology.
The paper then focuses on refinement planning. The main idea is to start with a large set of possible plans and slowly reduce them into smaller sets till we obtain the solution(s) to the planning problem. It is based on partial planning. The actual sets of action sequences are represented as partial plans. The action sequences corresponding to the consistent partial plans are called its candidates. A set of partial plans is referred to as a plan set, its partial plans as components. Then the candidate set is given as the union of candidate sets of its components. The plan synthesis in refinement planning includes a “split and prune” kind of search. Splitting splits the actual components of a plan set into multiple plan sets. The pruning refers to the refinement/reduction of a plan set. There are many ways as how to achieve this, and are referred to as refinement strategies. They can be looked at as procedures computing the consequences of the metatheory of planning and the actions. A refinement strategy maps one plan set P into another plan set P’, such that the candidate set P’ is a subset of the candidate set P. If P’ contains all the solutions P does, R is call complete. If P’ is a strict subset of P, we refer to R as progressive. If the length of minimal candidates does increase after R is applied, R is strongly progressive. Finally, R is called systematic if no action sequence in the candidate sets falls into more then one component of P’. A ratio between the candidate sets of P and P’ is referred to as progress factor. Completeness of R ensures we preserve all the solutions, progressiveness ensures we are reducing our plan set and systematicity ensures that for any candidate is consider only once.
The general refinement planning, given a plan set P, can be summarized in three following steps, with an extra first verifying step. First we check if a plan set is empty, if so we fail. If that is not the case, we check if a minimal candidate of P is a solution, if so we succeed and return it as a solution. If not, we select a refinement strategy R and apply R to P to obtain P’. Then we recourse back to the first step. Assuming any R we choose is complete, we never loose a solution. This approach is a generalized version of graphplan and satplan. The given algorithm does not consider any form of splitting, which can improve performance. To do this, we separate the components of a plan set and handle them individually. This is done in the recursive step, where we do not recourse for the whole plan, but only for one of its component. Hence even in complete case, we will have to backtrack.
There are many existing refinement strategies. The can be roughly divided into state space refinement, plan space refinement, hierarchical refinement and tractability refinement. Furthermore, we can divide the state space refinement into forward and backward one, and we can make them goal directed, using for example means ends analysis and others. In the first case, we grow the prefix of a partial plan by introducing actions into the plan head. This refinement is progressive, complete and systematic. In addition, the solution extraction can be performed in a simple way. The backward state space refinement is to grow the tail of the partial state by applying actions in the backward directions and on the tail state. This approach has lower branching factor then the previous one, but since we are not working with complete states. The overall complexity may vary. Plan space refinement decides on the position of a new action, as well as actual action. Hierarchical refinement deals with non primitive and primitive actions, supplied by the user via reduction schemas. Tractability refinement consists of reducing the number of linearization’s of the plan (preordering, propositioning), making all linearization’s safe (presatisfaction) and reducing the uncertainty in the action identity (prereduction). We can also interleave different refinements.
The paper further discusses the various tradeoffs in refinement planning. It gives asymptotic tradeoffs, provides empirical study of tradeoffs with the result that the performance differentials in planners are mainly due to tractability refinements. It further discusses the selection of sub goals and the scalability issues and techniques of refinement planning. The techniques include the use of disjunction, customization and CSP techniques. In case of disjunction, it gives a short discussion on open issues with this kind of planning.
This paper introduces basic concepts in classical planning and then shows how they can be integrated into a generic planning framework of refinement planning.
The view refinement planning takes is that of starting with a partial plan and constraining it incrementally in order to get a solution plan. A partial plan is a set of steps (each associated with an action) with partially specified position/precedence constraints and auxiliary constraints. A partial plan may have multiple minimal and infinite non-minimal linearizations. A partial plan can be thought of (only loosely) as a regular expression corresponding to multiple sequences of actions. Starting with an empty partial plan, which corresponds to all sequences of actions, the partial plan is refined incrementally to converge to more constrained partial plans having at least one of their minimal-length linearizations as the solution plan.
The search tree involved has got nodes representing partial plan(s) and its children nodes are nodes representing refined partial plans. Goal test involves checking if a minimal-length candidate of a partial plan is a solution. Depending upon the refinement techniques used, a partial plan can lead to multiple refined partial plans, which together are desired to retain all the solution candidates of partial plan (completeness), while at the same time get rid of some visibly non-solution candidates (progression). Also, if the refinement technique is systematic then each refinement of a partial plan explores an exclusive candidate set.
The steps in a partial plan can be constrained by ordering or auxiliary constraints. An ordering constraints among two steps can be precedence based (order of occurrence in plan) or contiguity (ordered adjacency) based. Auxiliary constraints can be interval-preservation constraint, which require a condition to hold true between an establisher step and a step needing it, or point-truth constraint, which require a condition to hold true at a particular point. A linearizations of a partial plan is a permutation of its steps consistent with all ordering constraints. A safe linearization is a linearization which satisfied all auxiliary constraints. A safe linearization corresponds to a minimal-length candidate of a plan. A plan with no safe linearization has no candidates, and hence it cannot lead to a solution.
The paper presents an algorithm for refinement planning using split and prune search. The motivation for splitting a plan into separate refinements is to keep the solution extraction cost low. Refinement strategies can be assessed on the basis of completeness, progressiveness, and being systematic. The paper then explains existing refinement strategies. It introduces some terminology involved with state-space refinement. State-space refinement can be classified into forward state-space refinement and backward state-space refinement.
Forward state-space refinement involves concatenating executable actions to the head step. A plan is found when head state satisfies the regressed tail state. This strategy is progressive, complete and systematic. It is further suggested that multiple independent actions can be added to the head step, so as to reduce the candidates and also reduce the branching factor of split. The papers discusses ways to improve branching factor by introducing goal directed-ness by performing means-end analysis in forward state-space refinement, and through backward state-space refinement. Backward state-space refinement is goal directed and regresses over the tail step by adding actions i.e. it grows the suffix. A plan is found head state satisfies the regressed tail state. Being goal directed in nature, this strategy has a lower branching factor as it considers only relevant actions. However, control policies work in favor of forward state-space refinement as it works with complete states which are easier to evaluate against a formula.
State-space refinement tends to be over-committed to ordering constraints, and thus may incur more backtracking. Plan-space refinement is a least-commitment strategy with partial plans, at the cost of higher per-node cost and solution extraction cost. Plan-space refinement works with selecting open-preconditions and attempts to satisfy them through introducing new steps and/or adding ordering and auxiliary constraints between established and step needing the precondition.
HTN refinement allow users with qualitative control over the plans through ability to abstract sequence of actions into higher level tasks and providing schema for expanding the tasks into desired domain-level actions. However, acquiring and specifying this control knowledge in the form of reduction schema is a non-trivial task.
Tractability refinements drop the progressiveness (pruning) requirement, for reduction in plan handling costs. They are classified as preordering, prepositioning, and presatisfaction refinements. Presatisfaction refinement produces refined plans such that all their linearizations satisfy auxiliary constraints. Constraints added by presatisfaction refinement are conserved after further refinements.
The paper then discusses combining multiple refinement strategies to create customized planners. These refinement strategies are then given some mathematical treatment to analysis the trade-offs in terms of plan handling cost, search space size, branching factor, candidate set size, progress factor etc. The paper then discusses scale up techniques for refinement planner through incorporating domain level control knowledge, and through CSP techniques by using disjunctive representations. It discusses extension to refinement for disjunctive steps, also providing an introduction to Graphplan, and open issues involved.
The paper concludes with suggestions on extensions to refinement planning in classical planning to non-classical planning scenarios, exploring totally new refinement strategies, further analysis of trade-offs between the strategies.
The paper presents a unifying view of the past work in planning by presenting the refinement planning paradigm. It attempts to put past works into a logical framework so that we can see how they are related and analyze future potential.
It begins by presenting a review of classical planning, assumptions, states, action definition and application, and giving a historical list of previous work in this domain.
Next it gives an introduction to partial order planning syntax, semantics. Beyond syntactic terms several additional important concepts of are presented:
Safe Linearization – A permutation of steps in a partial order plan that satisfies all ordering constraints, such as precedence and contiguity, as well as any constraints specifying the truth of conditions over time periods in the plan such as interval preservation constraints and point truth constraints.
Minimal Candidates – All safe linearizations of a partial order plan that only include the actions listed in the plan. This narrows our attention down from the potentially infinite set of candidates with loops or unnecessary steps.
After the concept of partial order planning has been thoroughly introduced the paper covers how partial order planning fits into the refinement planning paradigm. It starts by defining refinements. Essentially refinements are procedures that can be performed on the candidate set to remove possible candidates and therefore bring us closer to a candidate set that only contains valid plans. Several more important terms are defined here.
Completeness – A candidate set is said to be complete if all solutions are contained in it.
Progressive – A refinement is said to be progressive if no candidates are added in the refinement and one or more candidates are removed from the set. The progress factor of a refinement is a measure of how progressive it is.
Systematic – A refinement is said to be systematic if it does not duplicate any candidates in the set so that no further work will be considering a possible plan twice.
The next topic covered is splitting. By dividing the candidate set we hope to reduce the solution extraction cost. The main problem with this technique is it introduces backtracking, even for complete candidate sets because for any division the candidate of either set is no longer guaranteed to be complete. If we knew which set of a division all solutions existed in, we could discard the irrelevant part of the split, and this would itself be a refinement.
With the introduction to splitting and the definition of a few terms relating to segments of a plan, such as the plan head and tail, the paper then proceeds to classify forward, backward, means end, and HTN planners in the context of the refinement framework.
Forward state searching works by growing the head of the partial order plan with contiguity constraints until it connects to the tail. It is progressive, systematic, and complete, but the splitting involved by non-deterministically selecting which action to append to the head creates the problem of backtracking.
To attempt to address this non-determinism problem the paper presents means end analysis and backward search, both of which grow the plan by attempting to only apply actions to the plan that are relevant to the goals.
Means end analysis continues to grow the head of the plan but first looks for actions that directly cause goals, or chains of actions to cause goals in HTN planning. The historical dilemma proposed in the paper is whether to recompute the relevant actions at each refinement cycle. The author concludes that doing so has been proven to both speed up the application of means end analysis and to prevent the incompleteness present in STIPS style planners.
Backward state space refinement on the other hand attempts to grow the tail end of the plan rather than the head in the hopes that it can lower the branching factor by only considering actions that apply to the goals. It seems to me that this only makes the starting state of the plan the new goals, and so does very little good. There is the point that the final state of the domain is usually not completely specified and so the branching factor should be less near the start. Dealing with this uncertainly however forces backward state space refiners to deal in the art of theorem proving, which the author suggests will be more difficult than model checking.
The author next talks about refining in plan space rather than state space. Not knowing the exact position of a plan of course makes model checking more difficult, however overcommitting to action location can cause unnecessary backtracking. An algorithm for plan space refinement is presented then the author discusses the necessity for interval preservation constraints and methods of maintaining them such as promotion, demotion, and declobbering.
The author next introduces hierarchical refinement, which essentially weights the plan to use higher order actions and then provides a set of reduction schemas to translate the higher order actions into primitive actions. This essentially adds constraints on the plan that only plans using higher order actions are valid and if this is true then these reduction schemas prevent planners from making progress towards unwanted plans. Completeness can only be guaranteed if the reduction schemas are accurate and all constraints imposed are truly requirements. Writing these reduction schemas can be difficult however, especially in cases where the domain writer is not intimately familiar with the problem.
The next discussion is on tractability refinements, refinements of the plan space that do not have any pruning power and yet are still useful by lowering plan handling costs. A few more quick definitions are given:
Preodering refinements – Split the plan space by ordering two unordered steps
Prepositions refinements – Constrain the relative position of two steps.
Presatisfaction refinements – Split the plan space such that all orderings will be safe linearizations.
Prereduction refinements – Split the plan into multiple plans, each corresponding to one reduction schema.
Finally in this section the author classified several of the more recent planners in terms of which tractability refinements they choose to implement.
The next section of the paper covers design tradeoffs in the use of various refinement strategies. The results of the section are essentially summarized near the start. The tradeoffs in design can be put in terms of the equation:
T = (CS + CR ) F
Where F = the number of nodes on the fringe of the search tree generated by the refinement planner, CR= the cost of applying refinements, CS = the cost of extracting solutions from the plan. All design tradeoffs essentially aim to lower some part of this equation at the expense of some other part.
The author next talks about the issue of scale with refinement planners. Most real world problems that people would like to use planners for, the problems they would be willing to write a domain for because of the planning difficulty, are simply too large for planners to deal with effectively. The work done in making planners more scalable has taken two directions, customizing the planner for a specific domain and by using disjunctive representations.
9 comments:
The paper introduces a generalized approach to plan synthesis called refinement planning and relates it to various other plan synthesis approaches. The basic idea behind refinement planning is to start with the set of all possible action sequences and narrow it down to the set of all solutions. The sets of action sequences are represented in terms of partial plans. Plan synthesis in refinement planning involves a split and prune approach. Splitting is done by separating the components in a plan set into different search branches. The motivation for this is to reduce the time involved in looking for a solution. The pruning is done by applying refinement operations. The motivation here is to get rid of nonsolutions from the candidate set. There are various refinement strategies used for this purpose. A refinement strategy maps a plan set P to a plan set P' such that the candidate set of P' is a subset of the candidate set of P. The refinement strategy is progressive if the candidate set of P' is a strict subset of that of P and is strongly progressive if the length of the minimal candidates increases after the refinement. The strategy is systematic if no action sequence falls in the candidate set of more than one component of P'. The refinement strategy is complete if P' contains all the solutions that P contains. Planning using refinement strategies basically checks if the plan set P has a minimal candidate that is a solution and terminates if it does. Else, a refinement strategy is applied in order to obtain P' and the whole process is repeated.
Introducing splitting into refinement is done by separating each component into a different search branch. The refinement strategies can be broadly classified into 4 types - state space, plan space, task reduction and tractability refinement. State space refinement is of two types - forward state space and backward state space. Forward state space deals with adding actions to the prefix of the plan sequence such that the preconditions are satisfied by the effects of the head step. Backward state space refinement deals with adding actions to the suffix of the plan sequence such that the effects of the actions satisfy the preconditions of the tail step. The preconditions to the actions added might have to be updated. Plan space refinement deals with selecting an open condition and finding actions that satisfy the open condition. This also means that additional constraints might have to be added which might increase the number of open conditions. Hierarchical refinements deal with introducing non-primitive actions that can be reduced to primitive tasks using user-defined reduction schema. The planner's access to the primitive tasks is restricted because of the reduction schema. This is useful when a user has a priority for some solution. Tractability refinement can be classified into 3 categories. The first category consists of preorder refinements which order two unordered steps(actions) and prepositioning which constrain the relative positions of two steps. This is done in order to reduce the number of linearizations of the plan. The second category attempts to make all linearizations safe with respect to auxiliary constraints. This category contains presatisfaction refinements which splits the plan in such a way that a given auxiliary constraint is satisfied in all the linearizations of the components. This refinements use three strategies - promotion, demotion and confrontation. The third category of tractability refinements attempts to reduce uncertainty in action identities. One of the refinements is prereduction that converts a plan containing non-primitive actions to a set of plans. All the refinement strategies can be interleaved in order to solve a single planning problem. The paper also discusses about the role of least commitment in planning. Commitment reduces the time taken to check for a solution but increases the probability of backtracking. Least commitment makes a difference only when a planner splits the components into different search branches.
The paper also discusses about the tradeoffs in the different choices of refinement specifically, asymptotic tradeoffs and emperical results of tradeoffs among tractability and protection strategies. The paper also discusses about the problems of the planners with scaling up and gives two approaches to deal with scaling up. The first approach is through customization. One way is to bias the search of the planner by using the knowledge of the user. Non-primitive actions and reduction refinements can be used for this. Another way is to use machine learning techniques in order to make the planner learn from its successes and failures. The second approach to deal with scaling up is to reduce the search space by using disjunctive representations and constraint satisfaction techniques. Disjunctive techniques can be applied to state space refinements or plan space refinements by allowing disjunctive constraints. The refinement strategies need to be generalized in order to handle disjunctive plans. For forward space refinements, an actions can be selected only if its preconditions are subsumed by the union of the effects of the previous action. However, there might be a problem with disjunctive contraints in that the actions in the disjunction may not be executable at the same time. This would mean that the effect is not the union of the effects of all actions in the disjunction. One way to handle this is to make the effects of actions that cannot occur at the same time as mutually exclusive as done in graph plans. The paper then discusses the open issues with planning using disjunctive representations.
The paper begins with an overview of the main elements of the classical planning problem (which are also applied in more relaxed planning scenarios): states, goals, and actions. It briefly describes how actions can be applied progressively and regressively, and how plans can similarly be verified as solutions by progressively or regressively simulating the effects of their action sequences. This is followed by a historical summary of main conceptualizations of the classical planning problem. Next, elements of the key terminology of refinement planning are introduced, including partial plans, candidates, plan sets, components, candidate sets, and the terms "split" and "prune" (as applied to refinement planning). Partial plans are declared to be expressible as sets of constraints, consisting of four total subtypes of two different types of constraints: precedence and contiguity constraints make up the "ordering constraints," while the "auxiliary constraints" consist of interval-preservation constrains (IPCs) and point-truth constraints. A distinction is made between linearizations of partial plans, which obey all ordering constraints, and safe linearizations, which obey all constraints of both types. Candidate sets are then presented as being the "semantic" consequences of specific partial plans (while the constraints discussed earlier compose the "syntax" of the partial plan). To make practical use of candidate sets derived from partial plans, the concept of a minimal candidate is introduced; it is shown that the minimal candidates of a partial plan have a one-to-one correspondence with that partial plan's safe linearizations.
Next, characteristics of refinement strategies -- procedures which modify a partial plan in such a way that the resulting candidate set becomes a subset of the candidate set at the time that the procedure was invoked -- are discussed, including the attributes progressive, strongly progressive, and systematic, as well as the concept of the progress factor. A general algorithm for applying refinement strategies is then presented. The paper then discusses a modified algorithm for use with strategies that divide the components of the partial plan into the search space. Following this, the paper introduces more terminology for use in discussing existing refinement strategies, including the concepts of the head and tail of a plan, head and tail steps, the head and tail fringe, and "middle steps." Forward state-space refinement is presented first, and is described as growing the head (prefix) of the plan; the concept of combining "noninteracting" actions is discussed as one way of improving performance. This is followed by a discussion of two approaches for using goal-directed refinements to reduce the number of unnecessary actions which are considered. First, means-ends analysis is presented, including its somewhat flawed implementation in the early STRIPS planner, and as well as techniques which could be used to make means-ends analysis computationally complete. The second approach is the use of backward state-space refinement, which grows the tail of a plan by applying actions regressively. It is stated that backward state-space refinement is generally more efficient that forward state-space refinement, although the use of complete states in the latter approach may be desirable when applying "effective search-control strategies."
The discussion then turns to the concepts of applying plan-space refinements, as opposed to the state-space refinements used in more traditional approaches. An algorithm is presented which provides a general strategy for planning using plan-space refinements, including an optional bookkeeping step for introducing IPCs. Other concepts are introduced by means of an ongoing "rocket world" example, including causation preconditions (preconditions for achieving a particular conditional effect from an action), as well as the three general strategies for de-clobbering. Hierarchical refinement is then discussed, including the use of non-primitive actions and corresponding reduction schemas to apply specific restrictions to actions used in a plan in order to reflect the "desirability" of a solution. Tractability refinements are then discussed; there are three types, described as those which "attempt to reduce the number of linearizations" in a plan, those which seek "to make all linearizations safe," and those attempting to "reduce uncertainty in the action identity." The first category contains preordering and prepositioning refinements; the second category consists solely of presatisfaction refinements; in the third category, prereduction refinements are given as an example. It is stated that most planning algorithms differ primarily in how they apply tractability refinements.
Next, following an example use of multiple, interleaved refinements to solve a planning problem, a general comparison of characteristics of planning approaches is given, which expresses how the search space of planning, the difficulty of extracting solutions from partial plans, and other considerations relate to each other. Next, the author (whoever he is) discusses his own research into the effects of applying different types of refinement techniques. This is followed by two potential approaches for scaling planning for application to large problems. The first strategy is the use of domain-specific customization; the second is to use disjunctive representations in combination with existing approaches for constraint-satisfaction. The second strategy is discussed in some detail, including the nature and consequences of disjunctive representations in plans, and how some planners, such as GRAPHPLAN, resolve disjunctions. One last generalized refinement algorithm is presented, and then the paper concludes with an overview of relevant contemporary developments and potential avenues for research.
[From Thad Boyd]
I noticed the other day that I haven't been receiving class E-Mails and can't post to the blog. I looked up my registration information and discovered that, while my override for your class was processed two weeks ago, I was never enrolled. I'll bring a late add form to class today; in the meantime, since I can't post comments to the blog, here's the article summary for today's class.
---
This paper unifies all classical planning methods as subtypes of refinement planning, which starts with all possible states and actions and narrows the results, reducing candidate set size while increasing the length of minimal candidates. The two major refinement strategies are and state-space and plan-space; other strategies include tractability refinement and task reduction. In all cases, a plan split up into sub-plans.
State-space refinement can be performed either forward or backward. Forward state-space refinement entails adding actions to the plan prefix whose preconditions are satisfied by the head step, while backward adds actions to the suffix whose effects satisfy the preconditions of the tail step.
Plan-space refinement emphasizes finding actions to meet conditions; actions take priority over states. A step t is selected to meet a precondition C prior to a state s; any step between t and s must preserve C.
Tractability refinements do not reduce the size of a given candidate set, but reduce the costs of processing the plan. They may reduce the number of linearizations in the plan through preordering or prepositioning, make linearizations presatisfy constraints through promotion, demotion, and confrontation, or reduce uncertainty in actions, as in prereduction refinement, which splits a plan containing a nonprimitive action into a set of smaller plans.
Of course, each type of refinement has its advantages, and optimization depends on the problem. The paper speaks of asymptotic tradeoffs, and explores ways to select appropriate refinement strategies. It speaks first of subgoal interaction analysis, and explains that the best guideline is to select the refinement planner with the highest commitment and the highest number of trivially-serializable goals. It then refers to scaling up planners through customization and disjunctive representations. Customization refers to tailoring the planner's search to the specific problem, eg through the user's knowledge or through the program's own learning. Disjunctive representations compact multiple plans into smaller disjunctive steps with disjunctive constraints. Disjunctive representation of state-space refinements sacrifices a measure of progressivity, but pruning is still possible, as in cases of interactive steps and steps which must occur in a given sequence.
The paper closes by listing some known issues with disjunction, then outlining how different types of planning all fall under the umbrella of refinement planning through the principles described earlier.
Important vocabulary for refinement where plan P is mapped to subset P':
complete: P' contains all solutions of P
progressive: the candidate set of P' is a strict subset of the candidate set of P (prunes candidate set)
strongly progressive: length of minimal candidates increases from P to P'
systematic: no action sequence appears in the candidate set of more than one component of P'
progress factor: the ratio of the size of the candidate set for P' to the size of the candidate set for P
subgoal interaction: when a planner backtracks into the plan for one subgoal in order to achieve another
subplan: a partial plan whose linearizations will all execute and achieve its given subgoal
trivially serializable: subgoals G1 and G2 are trivially serializable if every subplan of one goal can be refined into a subplan for both goals.
My short summary:
Refinement planning is presented as a superset of existing methods in planning, unifying them into a more general conceptual framework.
Refinement planning works by modifying partial plans over multiple iterations to reach a set of solutions.
A refinement solution is said to be progressive if the number of minimal candidates decreases and no new candidates are introduced, and it is said to be strongly progressive if the length of these minimal candidates increases.
Many types of refinement strategies are presented, including forward and backward state-space refinements, whereby actions are added to the head or the tail of the partial plan, respectively.
Position, relevance, and plan-space refinement strategies are also presented, whereby the exact position of a new action is not necessary for refinement, valuing the concept of least-commitment.
Tractability refinements are the last set of strategies presented. Tractability refinements are not progressive, but rather move handling of disjunctions into the search space.
Trade-offs between refinement strategies are analysed in terms of the cost of handling plan sets versus the amount by which a given strategy increases the size of the search space. Strategies that are progressive will reduce the search space, but also have a high cost in terms of managing/refining the plan sets, whereas tractability refinements, for example, are designed to decrease that cost while increasing the size of the search space.
This paper talks about refinement
planning, a powerful and generalized plan
synthesis paridigm. The paper first
explains about the classical planning
scenario, the environment, action
sequences and states and then moves on to
progression and regression planners. The
planning algorithms and their summary was
also explained. Then, refinement planning
was introduced and the terms used in
refinement planning, namely candidate
sets, components were explained. The use
of partial plans to represent a plan set
was also elaboarated. Plan synthesis in
refinement planning was explained using
the split and prune approach. The syntax
of the partial plan was then described
which is expressed below. A partial plan
which consists of ordering
constraints(precedence and contiguity
constraints that talk about the order of
the actions), steps(or actions) and
auxiliary constraints(interval
preservation constraints and point truth
constraints that involves statements about
the truth of certain conditions over
certain time intervals). The linearization
and safe linearization was then explained
which are when the partial plan is
consistent with the ordering
constraint(rather, a topological sort) and
when the partial plan is consistent with
the auxiliary constraint respectively.
Then, the semantics of a partial plan was
explained, which are given in terms of
candidate sets. The notion of minimal
candidates has been explained and it has
also been said that there is a one to one
correspondence between the minimal
candidates and the safe linearizations of
the plan. This implies that a plan with no
safe linearizations will have an empty
candidate set. Different characteristics
of refinement strategies like
pregressiveness, systematicity,
completeness were explained. A general
refinement planning template was given
which recursively searches for a minimal
candidate and refines if not found. It was
noted that there would be a solution if
the refinement strategy used was complete.
Introduction of splitting into refinement
planning and its advantages, namely the
reduction in the solution extraction cost
and handling of individual components
separately.
The refinement strategies were explained
using the head and tail of a plan and the
term middle steps.
Forward and backward state space
refinement were the two types of state
space refinement strategies which can be
explained as follows. Forward state space:
adding actions to the prefix of the
partial plan and if and only if the
preconditions are satisfied by the effects
of the head step.
Backward state space: adding actions to
the suffix of the partial plan and if and
only if the effects of the actions(steps)
satisfy the preconditions of the tail
step.
Plan space refinements starts by picking
any precondition of any step in the plan
and introducing constraints to ensure that
the precondition is established and not
intervened. The difference between the
state space and plan space refinements has
been understood in terms of least
commitment. The three ways to shore up the
establishment are: promotion, demotion and
confrontation were explained.
Hierarchical refinement is useful in some
problems where there are preferences over
the solutions. It provides a way to
introduce biases between solutions.
Tractability refinement is the non
progressive refinement whose goal was to
reduce the plan-handling costs. There are
three categories of tractability
refinements: (1)To reduce the number of
linearizations which are further
classified into preordering and
prepositioning refinements. (2) To make
linearizations safe w.r.t auxiliary
constraints where we have presatisfaction
constraints. (3) To reduce uncertainty in
the action identity where we have
pre-reduction refinements.
Next, an interleaving of refinement
strategies has been suggested and
explained.
Then, the paper talks about the tradeoffs
of refinements and starts this discussion
by talking about asymptotic tradeoffs and
then explains about subgoal interaction
analysis and then talks about the term
trivially serializable. Then, there is a
discussion on which refinement strategy
should be chosen on which criteria(highest
commitment and the highest number of
trivially serializable goals).
The author then moves on to scaling up of
planners through two mehtods namely,
customization and using disjunctive
representations. Customization involves
incorporating the control knowledge into
the planner and various techniques
including machine learning have been
applied. Disjunctive representations allow
disjunctive steps, ordering and auxiliary
constraints into a plan. They have lead to
an increase in the cost of the plan
handling. Disjunctive plans can also be
refined but at the expense of some
progressivity of the refinment.
The author concluded by stating that
refinement planning provides the
theoretical backbone for most of the AI
planning techniques.
This paper introduces a generalized approach to classical planning known as refinement planning. The author aims to show that most planning algorithms that are applied towards classical planning are special cases of this envelope concept, and that by analyzing the issues involved in planning at the higher level of refinement planning, various planning approaches can be analyzed objectively and applied towards problems sets for which they are among the best methods available.
An introduction to planning and its classical realm is offered, and a history of planning systems from the times of planning as theorem-proving to CSP satisficing is provided for contextual reference. The author then provides an overview of refinement planning, which is defined as the process of starting with the set of all action sequences and gradually narrowing it downt o reach the set of all solutions.
Following the introduction, the syntax and semantics of partial plans are introduced. This section is extremely important in that not only does it introduce the nomenclature used in the rest of the paper, but also that partial plans form the basis of the rest of the discussion dealing with refinement planning approaches. As evinced by the definition, refinement planning is the refinment of partial plans using various techniques to achieve the goals of classical planning.
Then, in what forms the core of the paper, refinment strategies are introduced, and each strategy is correlated with the types of planning algorithms that it simulates. The first among these is Forward State-Space Refinement, which involves growing the prefix of a plan by introducing actions into the set of all actions contiguous with the initial state (known as the head fringe). Forward state-space refinement corresponds to the ideas behind what is commonly known and understood as progression in classical planning terms.
Another classical planning technique, regression, can be modelled by the second refinement strategy mentioned, which is backward state-space refinement. The interesting comparison in this section is that since backward state-space refinement is goal-focussed, it has a lower branching factor than its forward counterpart. However, this is offset by the fact that backward refinement works with the set of partially specified states, whereas forward refinement works with completely specified states.
The next set of refinements are grouped under the umbrella of plan-space refinements. In this section, there is some discussion of least commitment and the parallels in ideas between plan-space planning (partial order planning is an example) and plan-space refinement.
The last refinement technique that is talked about is Hierarchical Refinement, which allows plan users to have preferences among solutions. This refinement technique is important because all the techniques introduced uptil this point consider all plans equal as long as they are valid minimal (in terms of number of actions) solutions to the planning task at hand. However, with the use of hierarchical refinement, nonprimitive actions can be used to control and limit the plans that are acceptable as solutions.
After the plan-space refinement strategies are introduced and explained, the focus of the paper turns to tractability issues and how plans may be further refined with an eye to efficiency. Three categories of refinements are introduced with respect to this notion. The author then goes on to present an argument that interleaving refinement strategies could improve planner performance, and that the nature and success of such interleaving could depend on the problem and solution density.
The paper approaches its conclusion with a discussion of the asymptotic and empirical trade-offs involved. The asymptotic section fails to make any conclusive predictions, and it is left to the empirical analysis to show how the various refinement strategies work for various scenarios, based on a number of factors, such as the plan handling costs and the size of the fringe in the plan space.
The final technical contribution comes in the form of methods to scale refinement planning up. The first such method presented is customization, in which there are 2 sub-types: either a user or domain expert can feed in control knowledge to the planner, or the system can be subject to learning from its failures and successes. The other method presented for scale-up is through disjunctive and constraint satisfaction techniques. The paper concludes by talking about open issues in refinement planning, and the potential that lies in applying this unified framework to non-classical planning streams as well.
The paper presents a new generalized approach to plan synthesis, called Refinement Planning. The first sections of the paper discuss the basis of planning, what is planning and classical planning and how can we specify them and how to model and specify actions and states. In addition, it describes two basic ways of action application, progression and regression, and the conditions and processes involved in these. The basic overview part of the paper ends with a short section on the various planning approaches and their chronology.
The paper then focuses on refinement planning. The main idea is to start with a large set of possible plans and slowly reduce them into smaller sets till we obtain the solution(s) to the planning problem. It is based on partial planning. The actual sets of action sequences are represented as partial plans. The action sequences corresponding to the consistent partial plans are called its candidates. A set of partial plans is referred to as a plan set, its partial plans as components. Then the candidate set is given as the union of candidate sets of its components. The plan synthesis in refinement planning includes a “split and prune” kind of search. Splitting splits the actual components of a plan set into multiple plan sets. The pruning refers to the refinement/reduction of a plan set. There are many ways as how to achieve this, and are referred to as refinement strategies. They can be looked at as procedures computing the consequences of the metatheory of planning and the actions. A refinement strategy maps one plan set P into another plan set P’, such that the candidate set P’ is a subset of the candidate set P. If P’ contains all the solutions P does, R is call complete. If P’ is a strict subset of P, we refer to R as progressive. If the length of minimal candidates does increase after R is applied, R is strongly progressive. Finally, R is called systematic if no action sequence in the candidate sets falls into more then one component of P’. A ratio between the candidate sets of P and P’ is referred to as progress factor. Completeness of R ensures we preserve all the solutions, progressiveness ensures we are reducing our plan set and systematicity ensures that for any candidate is consider only once.
The general refinement planning, given a plan set P, can be summarized in three following steps, with an extra first verifying step. First we check if a plan set is empty, if so we fail. If that is not the case, we check if a minimal candidate of P is a solution, if so we succeed and return it as a solution. If not, we select a refinement strategy R and apply R to P to obtain P’. Then we recourse back to the first step. Assuming any R we choose is complete, we never loose a solution. This approach is a generalized version of graphplan and satplan. The given algorithm does not consider any form of splitting, which can improve performance. To do this, we separate the components of a plan set and handle them individually. This is done in the recursive step, where we do not recourse for the whole plan, but only for one of its component. Hence even in complete case, we will have to backtrack.
There are many existing refinement strategies. The can be roughly divided into state space refinement, plan space refinement, hierarchical refinement and tractability refinement. Furthermore, we can divide the state space refinement into forward and backward one, and we can make them goal directed, using for example means ends analysis and others. In the first case, we grow the prefix of a partial plan by introducing actions into the plan head. This refinement is progressive, complete and systematic. In addition, the solution extraction can be performed in a simple way. The backward state space refinement is to grow the tail of the partial state by applying actions in the backward directions and on the tail state. This approach has lower branching factor then the previous one, but since we are not working with complete states. The overall complexity may vary. Plan space refinement decides on the position of a new action, as well as actual action. Hierarchical refinement deals with non primitive and primitive actions, supplied by the user via reduction schemas. Tractability refinement consists of reducing the number of linearization’s of the plan (preordering, propositioning), making all linearization’s safe (presatisfaction) and reducing the uncertainty in the action identity (prereduction). We can also interleave different refinements.
The paper further discusses the various tradeoffs in refinement planning. It gives asymptotic tradeoffs, provides empirical study of tradeoffs with the result that the performance differentials in planners are mainly due to tractability refinements. It further discusses the selection of sub goals and the scalability issues and techniques of refinement planning. The techniques include the use of disjunction, customization and CSP techniques. In case of disjunction, it gives a short discussion on open issues with this kind of planning.
This paper introduces basic concepts in classical planning and then shows how they can be integrated into a generic planning framework of refinement planning.
The view refinement planning takes is that of starting with a partial plan and constraining it incrementally in order to get a solution plan. A partial plan is a set of steps (each associated with an action) with partially specified position/precedence constraints and auxiliary constraints. A partial plan may have multiple minimal and infinite non-minimal linearizations. A partial plan can be thought of (only loosely) as a regular expression corresponding to multiple sequences of actions. Starting with an empty partial plan, which corresponds to all sequences of actions, the partial plan is refined incrementally to converge to more constrained partial plans having at least one of their minimal-length linearizations as the solution plan.
The search tree involved has got nodes representing partial plan(s) and its children nodes are nodes representing refined partial plans. Goal test involves checking if a minimal-length candidate of a partial plan is a solution. Depending upon the refinement techniques used, a partial plan can lead to multiple refined partial plans, which together are desired to retain all the solution candidates of partial plan (completeness), while at the same time get rid of some visibly non-solution candidates (progression). Also, if the refinement technique is systematic then each refinement of a partial plan explores an exclusive candidate set.
The steps in a partial plan can be constrained by ordering or auxiliary constraints.
An ordering constraints among two steps can be precedence based (order of occurrence in plan) or contiguity (ordered adjacency) based. Auxiliary constraints can be interval-preservation constraint, which require a condition to hold true between an establisher step and a step needing it, or point-truth constraint, which require a condition to hold true at a particular point.
A linearizations of a partial plan is a permutation of its steps consistent with all ordering constraints. A safe linearization is a linearization which satisfied all auxiliary constraints. A safe linearization corresponds to a minimal-length candidate of a plan. A plan with no safe linearization has no candidates, and hence it cannot lead to a solution.
The paper presents an algorithm for refinement planning using split and prune search. The motivation for splitting a plan into separate refinements is to keep the solution extraction cost low.
Refinement strategies can be assessed on the basis of completeness, progressiveness, and being systematic. The paper then explains existing refinement strategies. It introduces some terminology involved with state-space refinement. State-space refinement can be classified into forward state-space refinement and backward state-space refinement.
Forward state-space refinement involves concatenating executable actions to the head step. A plan is found when head state satisfies the regressed tail state. This strategy is progressive, complete and systematic. It is further suggested that multiple independent actions can be added to the head step, so as to reduce the candidates and also reduce the branching factor of split.
The papers discusses ways to improve branching factor by introducing goal directed-ness by performing means-end analysis in forward state-space refinement, and through backward state-space refinement. Backward state-space refinement is goal directed and regresses over the tail step by adding actions i.e. it grows the suffix. A plan is found head state satisfies the regressed tail state. Being goal directed in nature, this strategy has a lower branching factor as it considers only relevant actions. However, control policies work in favor of forward state-space refinement as it works with complete states which are easier to evaluate against a formula.
State-space refinement tends to be over-committed to ordering constraints, and thus may incur more backtracking. Plan-space refinement is a least-commitment strategy with partial plans, at the cost of higher per-node cost and solution extraction cost. Plan-space refinement works with selecting open-preconditions and attempts to satisfy them through introducing new steps and/or adding ordering and auxiliary constraints between established and step needing the precondition.
HTN refinement allow users with qualitative control over the plans through ability to abstract sequence of actions into higher level tasks and providing schema for expanding the tasks into desired domain-level actions. However, acquiring and specifying this control knowledge in the form of reduction schema is a non-trivial task.
Tractability refinements drop the progressiveness (pruning) requirement, for reduction in plan handling costs. They are classified as preordering, prepositioning, and presatisfaction refinements. Presatisfaction refinement produces refined plans such that all their linearizations satisfy auxiliary constraints. Constraints added by presatisfaction refinement are conserved after further refinements.
The paper then discusses combining multiple refinement strategies to create customized planners. These refinement strategies are then given some mathematical treatment to analysis the trade-offs in terms of plan handling cost, search space size, branching factor, candidate set size, progress factor etc. The paper then discusses scale up techniques for refinement planner through incorporating domain level control knowledge, and through CSP techniques by using disjunctive representations.
It discusses extension to refinement for disjunctive steps, also providing an introduction to Graphplan, and open issues involved.
The paper concludes with suggestions on extensions to refinement planning in classical planning to non-classical planning scenarios, exploring totally new refinement strategies, further analysis of trade-offs between the strategies.
-Anupam
The paper presents a unifying view of the past work in planning by presenting the refinement planning paradigm. It attempts to put past works into a logical framework so that we can see how they are related and analyze future potential.
It begins by presenting a review of classical planning, assumptions, states, action definition and application, and giving a historical list of previous work in this domain.
Next it gives an introduction to partial order planning syntax, semantics. Beyond syntactic terms several additional important concepts of are presented:
Safe Linearization – A permutation of steps in a partial order plan that satisfies all ordering constraints, such as precedence and contiguity, as well as any constraints specifying the truth of conditions over time periods in the plan such as interval preservation constraints and point truth constraints.
Minimal Candidates – All safe linearizations of a partial order plan that only include the actions listed in the plan. This narrows our attention down from the potentially infinite set of candidates with loops or unnecessary steps.
After the concept of partial order planning has been thoroughly introduced the paper covers how partial order planning fits into the refinement planning paradigm. It starts by defining refinements. Essentially refinements are procedures that can be performed on the candidate set to remove possible candidates and therefore bring us closer to a candidate set that only contains valid plans. Several more important terms are defined here.
Completeness – A candidate set is said to be complete if all solutions are contained in it.
Progressive – A refinement is said to be progressive if no candidates are added in the refinement and one or more candidates are removed from the set. The progress factor of a refinement is a measure of how progressive it is.
Systematic – A refinement is said to be systematic if it does not duplicate any candidates in the set so that no further work will be considering a possible plan twice.
The next topic covered is splitting. By dividing the candidate set we hope to reduce the solution extraction cost. The main problem with this technique is it introduces backtracking, even for complete candidate sets because for any division the candidate of either set is no longer guaranteed to be complete. If we knew which set of a division all solutions existed in, we could discard the irrelevant part of the split, and this would itself be a refinement.
With the introduction to splitting and the definition of a few terms relating to segments of a plan, such as the plan head and tail, the paper then proceeds to classify forward, backward, means end, and HTN planners in the context of the refinement framework.
Forward state searching works by growing the head of the partial order plan with contiguity constraints until it connects to the tail. It is progressive, systematic, and complete, but the splitting involved by non-deterministically selecting which action to append to the head creates the problem of backtracking.
To attempt to address this non-determinism problem the paper presents means end analysis and backward search, both of which grow the plan by attempting to only apply actions to the plan that are relevant to the goals.
Means end analysis continues to grow the head of the plan but first looks for actions that directly cause goals, or chains of actions to cause goals in HTN planning. The historical dilemma proposed in the paper is whether to recompute the relevant actions at each refinement cycle. The author concludes that doing so has been proven to both speed up the application of means end analysis and to prevent the incompleteness present in STIPS style planners.
Backward state space refinement on the other hand attempts to grow the tail end of the plan rather than the head in the hopes that it can lower the branching factor by only considering actions that apply to the goals. It seems to me that this only makes the starting state of the plan the new goals, and so does very little good. There is the point that the final state of the domain is usually not completely specified and so the branching factor should be less near the start. Dealing with this uncertainly however forces backward state space refiners to deal in the art of theorem proving, which the author suggests will be more difficult than model checking.
The author next talks about refining in plan space rather than state space. Not knowing the exact position of a plan of course makes model checking more difficult, however overcommitting to action location can cause unnecessary backtracking. An algorithm for plan space refinement is presented then the author discusses the necessity for interval preservation constraints and methods of maintaining them such as promotion, demotion, and declobbering.
The author next introduces hierarchical refinement, which essentially weights the plan to use higher order actions and then provides a set of reduction schemas to translate the higher order actions into primitive actions. This essentially adds constraints on the plan that only plans using higher order actions are valid and if this is true then these reduction schemas prevent planners from making progress towards unwanted plans. Completeness can only be guaranteed if the reduction schemas are accurate and all constraints imposed are truly requirements. Writing these reduction schemas can be difficult however, especially in cases where the domain writer is not intimately familiar with the problem.
The next discussion is on tractability refinements, refinements of the plan space that do not have any pruning power and yet are still useful by lowering plan handling costs. A few more quick definitions are given:
Preodering refinements – Split the plan space by ordering two unordered steps
Prepositions refinements – Constrain the relative position of two steps.
Presatisfaction refinements – Split the plan space such that all orderings will be safe linearizations.
Prereduction refinements – Split the plan into multiple plans, each corresponding to one reduction schema.
Finally in this section the author classified several of the more recent planners in terms of which tractability refinements they choose to implement.
The next section of the paper covers design tradeoffs in the use of various refinement strategies. The results of the section are essentially summarized near the start. The tradeoffs in design can be put in terms of the equation:
T = (CS + CR ) F
Where F = the number of nodes on the fringe of the search tree generated by the refinement planner, CR= the cost of applying refinements, CS = the cost of extracting solutions from the plan. All design tradeoffs essentially aim to lower some part of this equation at the expense of some other part.
The author next talks about the issue of scale with refinement planners. Most real world problems that people would like to use planners for, the problems they would be willing to write a domain for because of the planning difficulty, are simply too large for planners to deal with effectively. The work done in making planners more scalable has taken two directions, customizing the planner for a specific domain and by using disjunctive representations.
Post a Comment