Chen Disser (1121212), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

For example, given the six actions planned in g1 and g2 , there are sixS5the subplan if it improves (4.6). If no better subplans can be found from all possible startingstates, SGPlang leaves the local subplan unchanged and moves on to the next subgoal.S3S2S0Landmark analysis. First proposed by Porteous, Sebastia, and Hoffmann [66], landmarkS1analysis allows a large planning problem to be decomposed into a series of much simplerFigure 4.7: Generating multiple starting states for Subgoal g3 . S0 is the initial state, whereasSi , i = 1, . . . , 6, is the state at the time action ai is finished. SGPlang generates a local subplanfrom each starting state and evaluates (4.6) in order to find a subplan that improves the penaltyfunction.subproblems. It aims to find some intermediate facts that must be true in any feasible plan,given the initial and the goal states.

For example, assume that object O is to be deliveredfrom A to D, and that the only path from A to D is A → B → C → D. Then factsor an action whose preconditions are all producible.The planning tasks will be significantly easier if producible facts and resources can beAT (O, B) and AT (O, C) are both landmark facts, since any feasible plan must make themtrue before reaching goal state AT (O, D).detected in the preprocessing phase and be made available during planning.

In SGPlang ,Originally, landmark analysis was used to find intermediate facts to reach all the subgoalswe first identify all these facts and resources and derive a relaxed initial state by setting allof a planning problem [66]. In SGPlang , we first partition the constraints of a problem byproducible facts to be true and all producible numerical resources to be large enough. Aftertheir subgoals, before applying landmark analysis to find intermediate facts to reach eachfinding a feasible plan from the relaxed initial state, SGPlang removes the unused numericalsubgoal individually.resources in the initial state and plans again. The process is repeated until there are noFor each subgoal, we find landmarks using a relaxed planning approach. Given planningredundant initial resources.

At that point, SGPlang inserts into the beginning of the plansubproblem T = (O, F , I, G), we first test for each fact f ∈ F to see if it is a landmark fact.the necessary actions to generate the minimum initial producible resources needed.We construct from initial state I a relaxed planning graph by ignoring the delete effects, andby enforcing f to be false at each level (even if it is made true by some actions). As a result,Subgoal-level techniquesall the actions preconditioned by f will not be included in the relaxed planning graph. AfterEvaluating multiple subplans for a subgoal. In finding a local feasible subplan for athe planning graph has been constructed, we check whether all the goal facts in goal statesubgoal that improves (4.6), SGPlang generates a number of subplans from multiple startingG are achieved. We know that f is a landmark fact and must be reached in any plan for thestates. Since no active global constraints exist between two identical subplans, we generaterelaxed problem if there exists a goal fact that cannot be reached.

Further, any feasible planmultiple starting states for a given subgoal by applying all possible prefix actions from eachfor the original problem must reach f at least once. This is true because any solution plan99100of the original problem is also a solution plan of the relaxed problem.Note that our reduction analysis is not complete, since the relevance list may still containAfter finding all the landmark facts of a subgoal, we build a sequential list of subproblemssome irrelevant actions. For example, we can further reduce the relevance list by a forwardjoined by landmark facts, and apply the basic planner to achieve each subproblem in order.analysis and by finding all applicable actions from the initial states before the backwardSearch-space reduction.

After partitioning a planning problem into subproblems, wecan often eliminate many irrelevant actions in the search space of each subproblem beforeanalysis. However, further analysis may not be cost effective for reducing the overhead inplanning.solving it. Such reductions are not very useful in planning problems that are not partitionedModified Metric-FF basic planner.

After landmark analysis, each subproblem asso-because all their actions are generally relevant.ciated with a subgoal may be decomposed further into subproblems bounded by landmarkAs an example, consider a transportation domain whose goal is to move packages, drivers,facts. SGPlang solves each subproblem identified (or the original subgoal in case no land-and trucks to various locations, given an initial configuration. Suppose in a problem instance,mark facts are identified) using a modified Metric-FF planner [37].

We have made severalthe goal set is {(AT D1 S1), (AT T1 S1), (AT P1 S0), (AT P2 S0)}, given two packages P1modifications in Metric-FF in order to entertain the new features in PDDL2.2.and P2, one driver D1, one truck T1, and two locations S1 and S2. Without partitioning,The original Metric-FF can only solve problems in PDDL2.1 with propositional actionsall the actions are relevant in resolving the subgoals. On the other hand, after partitioning,but does not support any temporal features.

We have extended the parser of Metric-FF tothe actions for moving P2 around are irrelevant in the subproblem of resolving (AT P1 S0)support the full PDDL2.2 syntax and the definition of actions from atomic logical to dura-and can be eliminated. Similarly, those actions for moving P1 or P2 are irrelevant in thetional temporal. The planning process has also been extended from sequential propositionalsubproblem of resolving (AT D1 S1).planning to parallel temporal planning. Specifically, in the original Metric-FF, actions withWe have designed a backward relevance analysis to eliminate some irrelevant actions in aan atomic length of one unit are ordered sequentially. In our modified Metric-FF planner, ac-subproblem before solving it by the basic planner.

In the analysis, we maintain an open listtions can be arranged in parallel, each with a numerical duration pre-defined in the problemof unsupported facts, a close list of relevant facts, and a relevance list of relevant actions.specification.In the beginning, the open list contains only the subgoal facts of the subproblem, and theWe have also extended Metric-FF to support a new feature called derived predicatesrelevance list is empty. In each iteration, for each fact in the open list, we find all the actionsintroduced in PDDL2.2.

Derived predicates define axioms whose derived facts are de-supporting that fact and not already in the relevance list. We then add these actions to therived by a set of precondition facts. For example, in a domain with boxes, if box A isrelevance list, and add the action preconditions that are not in the close list to the openabove B and B is above C, then a derived predicate that A is above C can be generated:list. We move a fact from the open list to the close list when it is processed. The analysisif (above(A, B) and above(B, C)) then above(A, C).

Derived predicates can only appear inends when the open list is empty. At that point, the relevance list will contain all possiblepreconditions and goals but not in effects.relevant actions and exclude those irrelevant actions. This analysis takes polynomial time.101In our modified Metric-FF, we have implemented a technique proposed in MIPS 2.2 [22]102for handling derived predicates. We encode any derived predicate d as a special action o,where the precondition facts of o are the preconditions facts of d, the add-effects of o arethe derived facts of d, and the delete-effect of o is empty.

During the heuristic-function10010101011001101010110010010010011110011001101010101010g110010 0101 110g2101010011010computation of Metric-FF, all these “derived-predicate actions” are also included in the100100110101010110101001010110011010100 01101relaxed plan but not the number of “derived-predicate actions.” Also, only real actions are10011001101010101010 010 011011010100101010101100011011 001101010relaxed plan.

However, the heuristic value only counts the number of real actions in the1001010101100110101011001001001001111001100110101010101010011 0001 11010010011010101011010100101011001g20101100 0110110101010 010 011011010100101010101100011011 001101010g3a) At the start of Iteration 2g1g3b) After solving Subgoal g1considered as candidates for forward expansion in any state. At any state, we expand theg101111 0001 0010101110011000110100101100101100101101010011000110011set of true facts by applying all applicable derived predicates iteratively until we reach afixed-point state where no more true facts can be added.g2100110014.1.31001Updating the penalties of violated global constraintsg31010In this section, we evaluate two strategies for updating the penalties of violated globalconstraints and demonstrate that SGPlang can resolve them effectively.0101011000110110101011 0001101010010110011000110110101010100101110011000111 001 00101010100110110100111010010100101101010011000110011g1g210100110100111000011101 00110100110011001100101g31010101010101001c) After solving Subgoal g20101011000110110101011 00011010100101100110001101101001011001011010101010100110100111000011101 0011010010110101001d) After solving Subgoal g3SGPlang first initializes the penalties of all global constraints when it starts.

Характеристики

Список файлов лекций