Chen Disser (1121212), страница 18
Текст из файла (страница 18)
In each instance, weuse the modified Metric-FF planner to find an initial plan, set the number of temporal stagesFigure 4.4: Variations of rg,T , rg,G , and rga,G across the instances of seven IPC4 domains.constraint partitioning by subgoals. We then compute the following ratios:to be the same as the number of subgoals, and partition the horizon of the solution planevenly into multiple stages. We then count the number of local constraints in each stage andrg,T = (NgT /Nc ) : fraction of global constraints under constraint partitioning by time,the number of global constraints relating actions in different stages.rg,G = (NgG /Nc ) : fraction of global constraints under constraint partitioning by subgoals,Figure 4.4 illustrates the results for seven IPC4 domains.
For each instance, let Nc be theGrga,G = (Nga/Nc ) : fraction of initial active global constraints under subgoal partitioning.total number of mutual-exclusion constraints, NgT be the number of global constraints underconstraint partitioning by time, NgG be the number of global constraints under constraintThe results show that constraint partitioning by subgoals leads to a lower fraction of globalGpartitioning by subgoals, and Ngabe the number of initial active global constraints underconstraints than that of constraint partitioning by time, and that the fractions do not vary9394significantly across the instances of a domain. The results also show that the fraction of initialactive global constraints under subgoal partitioning is very small. Except for two domains(PSR-Small and Settler), the fractions of initial active global constraints are consistently lessthan 0.1.
This behavior is important because only active global constraints will need to beresolved during planning, and the number of such constraints should decrease as planningprogresses. We describe in Section 4.1.3 two strategies for reducing the number active globalconstraints in planning.Since the fractions of global constraints in a domain do not vary significantly acrossdifferent instances, we summarize for each domain the average fraction of global constraintsunder constraint partitioning by time and that under constraint partitioning by subgoals, asTable 4.1: Average rg,T , rg,G , rga,G across the instances of IPC4 domains. Boxed numbers are lessthan 0.1.Domain Variantrg,Trg,GAIRPORT-STRIPSAIRPORT-TIMEWINDOWSPIPES-TANKAGE0.5570.4940.6870.2190.1840.677PIPES-DEADLINES-COOPTICAL-TELEGRAPH-DPPHILOSOPHER-DPPHILOSOPHER0.6820.7590.8550.5540.2960.2650.5760.370PSR-MIDDLE-COMPILEDPSR-SMALLSATELLITE-NUMERICSATELLITE-COMPLEX0.8820.8970.2880.6420.4780.4890.3050.282SATELLITE-TIMESATELLITE-COMP-TIL-COUMTS-TEMPORALUMTS-TEMPORAL-TIL0.6860.6980.4630.4370.2890.1530.1570.126UMTS-TEMPORAL-TIL-COMP 0.4070.098r ga,G0.017 0.013 0.070 0.039 0.020 0.019 0.066 0.049 0.1140.078 0.069 0.093 0.042 0.006 0.008 0.008 Domain Variantr g,Tr g,GAIRPORT-TEMPORALPIPES-NONTANKAGEPIPES-DEADLINES0.5680.6950.6740.2080.3130.297OPTICAL-TELEGRAPHOPTICAL-TELEGRAPH-FLPHILOSOPHER-FLPSR-MIDDLE0.5750.7990.8220.8960.3990.4260.5070.504PSR-LARGESATELLITE-STRIPSSETTLERSSATELLITE-COMP-TIL0.9020.6890.5490.6330.6650.2880.4510.124SATELLITE-TIME-TILSATELLITE-TIL-COUMTS-FLAWUMTS-FLAW-TIL0.6480.6330.4590.4280.1140.3070.1360.110UMTS-FLAW-TIL-COMP0.4140.086r ga,G0.014 0.044 0.033 0.052 0.037 0.087 0.092 0.096 0.096 0.1000.041 0.027 0.075 0.006 0.008 0.007 well as the average fraction of initial active global constraints under constraint partitioningby subgoals.
The results show that constraint partitioning by subgoals consistently leadto a lower fraction of global constraints than constraint partitioning by time, and that thefraction of initial active global constraints under constraint partitioning by subgoals is veryThe partition-and-resolve approach in SGPlang is different from incremental planning [50]that uses a goal agenda.
In incremental planning, a planner maintains a set of target facts,adds goal states incrementally into the target set, and extends the solution by using the newtarget set. This means that a goal state will always be satisfied once it is satisfied in ansmall.earlier target set. Because the search space increases as more goal states are added in the4.1.2System architecture of SGPlangFigure 4.5 shows the design of SGPlang that implements the partition-and-resolve procedure.At the global level, SGPlang partitions a planning problem into N subproblems, G1 , · · · , GN ,one for each subgoal. It then orders the subproblems, evaluates the composed plans, andupdates the penalties of violated global constraints.
At the subgoal level, it applies landmarktarget set, it may be more expensive to solve subsequent problems with larger target sets.Moreover, it is difficult to tell which goals should be satisfied before others. In contrast,SGPlang always addresses one goal fact at a time in a subproblem, without increasing itssearch space as other subproblems are solved.Global-level techniquesanalysis to further partition Gi into ci subproblems Pi,1 , · · · , Pi,ci . For each subproblem,Resolution of violated global constraints. We apply the partition-and-resolve proceit performs subspace-reduction analysis to prune irrelevant facts and actions, and calls adure in Figure 5.2 to resolve violated global constraints in SGPlang .
Our procedure alternatesmodified Metric-FF planner to find a feasible local plan that reaches the local subgoal andbetween finding feasible plans for all subgoals and updating the penalties of violated globalthat minimizes the penalty function.9596Global-Level PlanningPlanEvaluationTechniquesStudiedPenalty-ValueUpdate StrategyGlobalConstraintResolutionGlobal Constraints on SubgoalsG1G2constraints.For subgoal gi , i = 1, . . . , N, we use a basic planner to find a feasible plan zi , while tryingto minimize the local 1 -penalty function defined as follows:ProducibleResourcesGNΓ(zi ) = J(z) +ConstraintPartitioningby Subgoalsγi,j × mi,j ,(4.6)j=1,··· ,N,j=iSubgoal-Level Planningwhere mi,j is the number of active global constraints between the actions in the subplanP1,1P1,c1PN,1PN,cNLandmarkAnalysisfor gi and those for gj .
To limit the number of penalties while characterizing the prioritiesamong the subgoals, we assign a single penalty γi,j for each pair of subgoals gi and gj ,TemporalEngineModified Metric−FFDerived−predicatesengineTemporalengineSubspacereductioninstead of a penalty for each global constraint between gi and gj . In SGPlang , we haveDerivedPredicatesEngineadopted an implementation in LPG1.2 [30] for detecting persistent mutual exclusions andSearchSpaceReductionor not.Figure 4.5: SGPlang : A planner implementing the partition-and-resolve procedure in Figure 5.2.1.
procedure SGPlang/* global-level planning */2.parse problem file and preprocess;3.repeat /* subgoal-level planning */4.for each goal fact in the subgoal list5.perform landmark analysis to generate a list of subproblems;6.for each subproblem in the list7.call search space-reduction procedure to eliminate irrelevant actions;8.call basic planner (modified Metric-FF) to solve the subproblem;9.end for10.end for11.evaluate plan z and update penalty values of violated global constraints;12.periodically re-order the subgoals;13.until feasible solution plan has been found or time limit is exceeded;14.
end procedureFigure 4.6: SGPlang : A planner implementing the partition-and-resolve procedure in Figure 5.2.have implemented the conditions in (4.3)-(4.5) to determine if a mutual exclusion is activeAfter solving all the subproblems, we evaluate the composed plan, find all the activeglobal constraints, and update their penalty values in order to bias the search in the nextiteration towards resolving them. In Section 4.1.3, we evaluate two strategies for updatingpenalty values and compare their effectiveness.Producible resources. In some planning problems, there may be facts that can be madetrue anytime when needed and numerical resources that can be produced anytime we necessary. For example, in the Settlers domain, coal can always be produced in a mine.
Wedefine these producible logical and numerical resources as follows:a) A fact is producible if it is an add-effect of an action with zero precondition, or anaction whose preconditions are all producible.b) A numerical resource is producible if it is increased by an action with zero precondition,97980g1a1a3a2g2Timea5a4possible starting states when developing a subplan for g3 . For each starting state, SGPlanga6generates a local feasible subplan by gradient descents from the starting state and acceptsS6g3S4of the other subgoals.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
