Chen Disser (1121212), страница 20
Текст из файла (страница 20)
In theFigure 4.8: The planning process of SGPlang using SA in the second iteration in solving thefirst iteration, SGPlang solves each subgoal individually, without considering their globalAIRPORT-TEMPORAL-14 instance. Each box corresponds to an action in a subplan, whereaseach arrow corresponds to an active global constraint.constraints. It then combines all the subplans into an integrated plan in order to determinethe initial active global constraints across the subgoals. In subsequent iterations, SGPlangfinds a local feasible plan for each subgoal, while minimizing the weighted sum of violatedglobal constraints. At the end of each iteration, SGPlang increases the penalty of a violatedglobal constraint in proportion to its violation.
The process ends when all the constraints(k)where γi,j is the penalty for the global constraints between gi and gj in the k th iteration,mi,j is the number of active global constraints between gi and gj defined in (4.6), ξ is a largeinitial value, and α is a parameter controlling the rate of penalty updates. We set ξ = 100and α = 0.1 in our experiments. Intuitively, SA tries to minimize the global-constraintviolations at the beginning of the planning process. As a result, the subplans will have lowerare satisfied.We have designed two strategies for initializing the penalty of global constraints. Thefirst strategy SA sets a very large initial value for all penalties and updates them by rate α:concurrency, and the number of global constraints will be reduced quickly.
The strategy iseffective for solving most of the IPC4 instances and was employed in SGPlang in the IPC4competition.(SA )(0)γi,j = ξ,(k)(k−1)γi,j = γi,j103+ α × mi,j ,k = 1, 2, . . . ,(4.7)Figure 4.8 illustrates the planning process of SGPlang using SA on the AIRPORT-104evaluating the first, second, and third subgoal in the second iteration. The strategy is effec-SASB201510506 8 10 12 14 16 18 20 22 24 26 28total # of subgoals evaluatedtive and reduces the number of active global constraints quickly from 14 in the beginning toSASB504030201006810 12 14 16 18 20total # of subgoals evaluateda) AIRPORT-TEMPORAL-30zero in just one iteration.250SASB2001501005002220 25 30 35 40 45 50 55 60 65 70 75total # of subgoals evaluatedb) PIPESWORLD-NONTANKAGE-30c)the second strategy SB sets the initial penalty values to zero and gradually increases them(0)γi,j = 0,(k)(k−1)γi,j = γi,j+ α × mi,j ,k = 1, 2, .
. .(4.8)Figure 4.9 illustrates the performance of SA and SB on nine representative instances of the02468 10 12 14total # of subgoals evaluated14SASB12108642010152025# of active global constraints1009080706050403020100SASB40 60 80 100 120 140 160 180 200total # of subgoals evaluated454035302520151050SASB15 20 25 30 35 40 45 50 55 60total # of subgoals evaluatede) SATELLITE-TEMPORAL-2030total # of subgoals evaluatedIPC4 domains. For each instance, we plot the progress of SGPlang by showing the remaining16d) PSR-SMALL-40# of active global constraintsin each iteration:SASBg) UMTS-TEMPORAL-503512SASB108642001020304050f) SETTLERS-20# of active global constraintsplaces too much emphasis on satisfying violated global constraints.
To address this issue,# of active global constraintsporal deadlines. It has difficulty in satisfying deadlines in individual subgoals because it181614121086420# of active global constraintsDEADLINE, where temporal concurrency has to be exploited heavily in order to meet tem-# of active global constraintsOPTICAL-TELEGRAPH-10The first strategy, however, does not work well for some domains, such as PIPESWORLD-(SB )60# of active global constraintsstraints. The figure shows, respectively, the subplans and the active global constraints after25# of active global constraintseach subgoal once in the first iteration in order to determine the initial active global con-# of active global constraintsTEMPORAL-14 instance. Given the three subgoals in this instance, SGPlang first evaluates60total # of subgoals evaluatedh) PIPESWORLD-DEADLINE-057050454035302520151050SASB510152025303540total # of subgoals evaluatedi) PIPESWORLD-DEADLINE-10Figure 4.9: Resolution of active violated global constraints in nine IPC4 instances using SA andnumber of active violated global constraints with respect to the total number of subgoalsevaluated, where a subgoal evaluation involves the execution of Lines 5-9 in Figure 4.6.We use the number of subgoals evaluated, instead of the number of iterations through allthe subgoals, because the number of active global constraints changes after evaluating eachSB for updating penalty values.
In each instance, we plot the remaining number of active globalconstraints with respect to the total number of subgoals evaluated during planning. The x axisincludes the number of subgoals evaluated in the first iteration in order to determine the activeglobal constraints.Both SA and SB , however, has difficulty in solving the PIPESWORLD-DEADLINE-10instance (Figure 4.9i). For this domain, SGPlang can only solve two instances (1 and 2)subgoal.Figure 4.9 shows that active violated global constraints can be resolved efficiently byusing SA and eight instances (1, 2, 5, 6, 8, 14, 22, and 30) using SB (Figure 4.9h).
AlthoughSGPlang in most cases. We observe that SA is better than SB in most of the instances, andthe number of initial active violated global constraints is small for this domain (an averagethat the remaining number of active violated global constraints is generally reduced in anof 3.3% of all constraints as shown in Table 4.1), both strategies may get stuck at somealmost linear fashion with respect to the number of subgoals evaluated.infeasible solutions and cannot make progress afterwards. The reason is that both strategies105106do not have enough backtracking to generate new candidate subplans for each subgoal.
As aresult, both keep generating the same subplan at some point, regardless of how the violatedconstraints are penalized.One way to improve convergence is to use backtracking within each run of Metric-FF inorder to generate more candidate plans and to find new descent direction for the penaltyfunction. Currently, our modified Metric-FF returns when it finds the first feasible plan.Another way is to reduce the number of subproblems, which will lead to larger subproblemsTable 4.2: Number of instances in each domain solved by the top planners that participated inIPC4.Domain # Instances SGPlang LPG-TD Downward Diag-Downward Macro-FF YAHSP CrikeyAirport2001551345050213664Pipesworld26016611360806293111Promela272167838383384213PSR20012299131131324829Satellite288207157363636−−Settlers201913−−−−−UMTS300274200−−−−−Total15401110799360380189219217with less global constraints to be resolved.Experimental results100001000010001000SGPlanLPG-td.speedMacro-FFcrikeydiagonally-downwarddownwardyahsp100IPC4 and IPC3 benchmark suites.
Each suite contains seven domains, with several variantsCPU sec.In this section, we compare the performance of SGPlang and other planners in solving thein each. These variants address different features of PDDL2.2 that include versions on Strips,Strips with DP (derived predicates), temporal, temporal with TIL (deadlines), numeric, and100CPU sec.4.1.41010.10.10.010.01complex (temporal and numeric). A complete description of each variant and its problem510152025303540455010001000100100101tition, a 3-GHz two-CPU Linux PC.
Following the rules of IPC4, all random planners set a0.10.110751015202530253035404550455010planners to solve. In IPC4, all runs were carried out on the official computer of the compe-0.0120b) TEMPORAL1Table 4.2 summarizes the number of instances solved by some of the best planners in1510000CPU sec.CPU sec.organized by the International Conference on Automated Planning and Scheduling. Eachand execute under a CPU time limit of 30 minutes and a main memory limit of 1 Gbytes.10instance numberSGplanLPG-td.speedThe International Planning Competition (IPC) is a biannual event started from 1998 andmust be fully automated, run with a fixed parameter setting for each instance attempted,5a) NONTEMPORAL10000fixed random seed, once and for all, throughout their experiments. Moreover, all plannersSGPlanLPG-td.speedcrikeyinstance numberfiles can be found in the web sites of IPC4 and IPC3.competition provides a set of planning problems from various domains for the participating1013540450.0150instance numberc) TEMPORAL-TIMEWINDOWSSGPlancrikey510152025303540instance numberd) TEMPORAL-TIMEWINDOWS-COMPILEDFigure 4.10: Comparison of the performance of IPC4 planners on the Airport domain.each IPC4 domain.
Figures 4.10-4.17 further depict the complete results on these planners.10810000solve 44 instances but not those numbered 44, and 46 to 50; whereas Downward, the leadingCPU sec.SGPlang can solve more instances than other planners in the TEMPORAL and the TEMPORALTIMEWINDOWS-COMPILED variants.
In the NONTEMPORAL variant, SGPlang can10000SGPlanLPG-td.speedMacro-FF1000crikeydiagonally-downwarddownwardyahsp100planner for this variant, can solve all 50 instances. SGPlang cannot solve the five largestinstances because some of the partitioned subproblems are too large and cannot be evaluated1000100CPU sec.Figure 4.10 shows the performance in solving the instances of the Airport domain.1010110.10.10.010.015101520253035404550a) NONTEMPORAL10001000ods so that the complexity of each subproblem is low enough to be handled by our modified100100CPU sec.our partition-and-resolve approach. Another solution is to develop new partitioning methCPU sec.100001010.10.0151015202530100time in most cases, although the difference is generally within one order of magnitude.
Last,as is discussed in Section 4.1.3, SGPlang is not competitive in the TEMPORAL-DEADLINECPU sec.only two planers that can solve all 50 instances. YAHSP, however, has the shortest solution354045503540454550SGPlanLPG-td.speedcrikey0.0150510152025303540instance numberd) TANKAGE-TEMPORAL100001000300.1instance numberTEMPORAL variants. In the NONTEMPORAL variant, YAHSP and SGPlang are the2510c) TANKAGE-NONTEMPORALest solution time in the TEMPORAL, TANKAGE-NONTEMPORAL, and TANKAGE-201SGPlanLPG-td.speedMacro-FFcrikeydiagonally-downwarddownwardyahspFigure 4.11 shows that SGPlang can solve more instances in the NONTEMPORAL,Further, SGPlang consistently has the short-15b) TEMPORAL10000Pipesworld domain than other planners.10instance numbera more efficient basic planner when it is available. In fact, this is one of the major benefits ofTEMPORAL, TANKAGE-NONTEMPORAL, and TANKAGE-TEMPORAL variants of the5instance numberby the modified Metric-FF planner embedded in SGPlang .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
