Chen Disser (1121212), страница 21
Текст из файла (страница 21)
An obvious solution is to employMetric-FF planner. The design of these partitioning methods is open at this time.SGPlanLPG-td.speedcrikeySGPlanLPG-td.speed1010.1variant. It can only solve two instances using strategy SA and eight instances using SB .0.01Figure 4.12 shows, for the Promela domain, that SGPlang can solve the most number of instances in the OPTICAL-TELEGRAPH-FL, PHILOSOPHERS, PHILOSOPHERSDERIVEDPRED, and PHILOSOPHERS-FLUENTS variants.510152530e) TEMPORAL-DEADLINEFurther, SGPlang is thefastest planner in three of the variants and is slightly slower than YAHSP in PHILOSO-Figure 4.11: Comparison of the performance of IPC4 planners on the Pipesworld domain.PHERS.10920instance number1101000010001000nizer of IPC4 provided two versions, one written in pure Strips and another in ADL.
How-100CPU sec.CPU sec.10010for the OPTICAL-TELEGRAPH (resp., OPTICAL-TELEGRAPH-DP) variant. There are10.10.15101520253035400.0145ever, there are only 14 (resp., 19) instances in Strips and 48 (resp., 48) instances in ADL1010.01In the OPTICAL-TELEGRAPH and OPTICAL-TELEGRAPH-DP variants, the orga-10000SGPlanLPG-td.speedMacro-FFcrikeyyahsp51015instance number2025303540tion, whereas instances specified in Strips require large files.
(For example, the file size of45instance numbera) OPTICAL-TELEGRAPH10000OPTICAL-TELEGRAPH-14 is 38 Kbytes in ADL and 8.3 Mbytes in Strips.) Since SGPlangb) OPTICAL-TELEGRAPH-DP10000SGPlan10001000100100CPU sec.CPU sec.more instances available in ADL because ADL is space-efficient in its problem representa-SGPlanLPG-td.speeddiagonally-downwarddownward10cannot handle ADL at this time, it only solved the instances in pure Strips in these two vari-SGPlanLPG-td.speedMacro-FFcrikeyyahspants.
It was able to solve all the instances available in Strips and was the fastest in all theseinstances. However, other planners, such as Macro-FF and Downward, can handle instances10110.10.1in ADL and were able to solve more instances in these two variants.Figure 4.13 shows that SGPlang is the only planner that can solve some instances of all0.015101520253035400.0145four variants of the PSR domain. In the SMALL variant, SGPlang , LPG, and Crikey have51015instance number100030354045comparable performance and cannot solve the few largest instances. Like the AIRPORT-d) PHILOSOPHERSTEMPORAL variant, SGPlang has difficulty with the few largest instances because its basic10000SGPlanLPG-td.speeddiagonally-downwarddownwardCPU sec.100CPU sec.25instance numberc) OPTICAL-TELEGRAPH-FL100002010SGPlan1000planner cannot handle the partitioned subproblems.
In the MIDDLE variant, SGPlang , LPG,100and Downward can solve all 50 instances. The situation in the MIDDLE-COMPILED and10LARGE variants are similar to that in the OPTICAL-TELEGRAPH and the OPTICAL-110.10.1TELEGRAPH-DP variants of the Promela domain. In these variants, Macro-FF and Downward can handle directly the ADL format, but SGPlang must expand the ADL syntax to0.015101520253035400.0145instance number51015202530354045instance numbere) PHILOSOPHERS-DERIVEDPREDf) PHILOSOPHERS-FLUENTSFigure 4.12: Comparison of the performance of IPC4 planners on the Promela domain.pure Strips and exhausted its memory limit when evaluating larger instances.
We plan toextend SGPlang to handle ADL directly in the future.Figure 4.14 and Figure 4.15 show that SGPlang can solve the most number of instancesin seven variants of the Satellite domain. In the eighth variant (TIME), SGPlang was notable to solve the few largest instances because its memory usage exceeded 1 Gbytes. In all1111121000010000100010010110.10.1510152025303540450.015051015instance number100100.10.125301000010000100010001001003540450.0150instance number10110.10.1SGPlanLPG-td.speed510152025300.01355105101520253035401000045the variants, SGPlang is the fastest planner except in the STRIPS variant.Figure 4.16 shows that SGPlang can solve the most number of instances in all the six100010010010110.1variants of the UMTS domain and is the fastest in four of them.
SGPlang , however, isslower than LPG-TD in the FLAW and FLAW-TIL variants. The performance degradationof SGPlang in these variants is attributed to its implementation overhead, since many of1015203035100.1525b) COMPLEX-TIL10000.012010000SGPlan50Figure 4.13: Comparison of the performance of IPC4 planners on the PSR domain.15instance numbera) COMPLEXSGPlandiagonally-downwarddownwardd) LARGE25300.0135SGPlanLPG-td.speed5101520instance numberinstance numberc) COMPLEX-TIL-COMPd) TIME2530Figure 4.14: Comparison of the performance of IPC4 planners on the Satellite domain.their instances are easy and can be solved within five seconds of CPU time.Figure 4.17 shows that SGPlang can solve all the instances in the Settlers domain exceptthe 8th instance, which we learned from the IPC4 organizers that it is an infeasible instance.SGPlang is also the fastest among all the planners.11310instance numberinstance numberc) MIDDLE-COMPILEDSGPlanLPG-td.speed500.01120451011540CPU sec.100CPU sec.CPU sec.10001035b) MIDDLESGPlanMacro-FF5301000010000.0125instance numbera) SMALL1000020CPU sec.0.01SGPlanLPG-td.speeddiagonally-downwarddownwardCPU sec.10CPU sec.CPU sec.CPU sec.SGPlanLPG-td.speedcrikey1000 diagonally-downwarddownwardyahsp100114351000010000SGPlanLPG-td.speedcrikey10001000CPU sec.10.10.10.010.01510152025303540455010a) TEMPORAL100000.10.110001000100100152025300.0135510instance number1520253035instance numbere) TIME-TILf) TIME-TIL-COMPSGPlancrikey10110000.10.10.0151015455045504550SGPlanLPG-td.speedcrikey2025303540455010100010001001000.0135instance numberSGPlanLPG-td.speed51015202530instance numberg) STRIPSh) NUMERIC3525303510000SGPlanLPG-td.speedCPU sec.302040d) FLAW0.12515c) TEMPORAL-TIL-COMP0.12010instance number10000155instance number1104011535100.01100100.01301000CPU sec.CPU sec.1002510000SGPlanLPG-td.speedLPG-td.qualityMacro-FFdiagonally-downwarddownwardyahspCPU sec.100002010000CPU sec.1015b) TEMPORAL-TIL1510instance number10.015instance numberCPU sec.CPU sec.1001010SGPlan100010010110000SGPlanLPG-td.speed100CPU sec.CPU sec.10010000SGPlanLPG-td.speed100010SGPlan10110.10.1Figure 4.15: Comparison of the performance of IPC4 planners on the Satellite domain.0.01510152025303540450.0150instance number510152025303540instance numbere) FLAW-TILf) FLAW-TIL-COMPFigure 4.16: Comparison of the performance of IPC4 planners on the UMTS domain.1151161000100010001001001001010110.10.10.01SGPlanLPG-td.speed2468101214160.0118CPU sec.10000CPU sec.10000CPU sec.10000201SGPlanLPG-1.2LPG.speedFF.speedMIPS.plainVHPOPSimplanner51015100.012010001000100100In addition to the IPC4 domains, we have evaluated the performance of SGPlang onCPU sec.CPU sec.1000010120101SGPlanLPG-1.2LPG.speedMIPS.plainVHPOP0.10.0115b) NUMERIC10000Table 4.3: Number of instances in each IPC3 domain solved by the eight planners compared.10instance numbera) STRIPSDomain # Instances SGPlang LPG-1.2 LPG.speed FF.speed MIPS.plain VHPOP Sapa SimplannerDepots8885877742426522DriverLog10090100984677281411ZenoTravel808080764077261520Rovers80523533292927119Satellite120118114695490343517Settlers20190000000FreeCell20202182001012Total50846441837123731512280915instance numberinstance numberFigure 4.17: Comparison of the performance of IPC4 planners on the Settlers domain.SGPlanLPG-1.2LPG.speedFF.speedMIPS.plain0.151015SGPlanLPG-1.2LPG.speedMIPS.plainSapa0.10.0120instance number5101520instance numberc) SIMPLETIMEd) TIMEFigure 4.18: Comparison of the performance of various planners on the Depots domain.all the IPC3 domains.
We have also downloaded the most recent version of LPG, LPG1.2.planners.Our tests of the IPC3 instances using SGPlang and LPG1.2 were conducted on our localFigures 4.18-4.22 present the performance of the eight planners on the seven IPC3 docomputer, an AMD Athlon MP2000 PC with Linux Redhat 7.2 and 1-Gbyte main memmains. The following are some of the observations on these graphs. a) In the Depots andory. For the other planners, we have used the competition results from the IPC3 Web siteDriverLog domains, SGPlang is generally the third fastest planner, next to FF.speed and(http://planning.cis.strath.ac.uk/competition/). These results are slightly off fromLPG.speed.
b) In the ZenoTravel domain, SGPlang is the fastest in the SIMPLETIME andthe results collected on our local computer because they were collected on an AMD AthlonTIME variants. It is, however, the second fastest in the STRIPS and NUMERIC variants,MP1800 computer with 1-Gbyte main memory.where FF.speed is slightly faster. c) In the Freecell domain, SGPlang and FF.speed are theTable 4.3 summarizes the number of instances in each domain solved by the seven toponly two planners that can solve all the instances.
FF.speed, however, is faster. d) In theplanners. Overall, SGPlang was able to solve the most number of instances than the otherSettlers domain, SGPlang is the single best planner. e) In the Rovers domain, SGPlang1171181001010110.10.10.0124SGPlanLPG-1.2LPG.speedFF.speedMIPS.plain6810121416180.012010000246instance number8101214161820instance numbera) STRIPS1000b) NUMERICSGPlanLPG-1.2LPG.speedMIPS.plainVHPOP10001000SGPlanLPG-1.2LPG.speedFF.speedMIPS.plain100101101100CPU sec.CPU sec.100SGPlanLPG-1.2LPG.speedMIPS.plainSapa1010.10.10.010.011010.10.10.010.012468101214161820instance number2468101214161820246instance number2468101214161820instance numberc) SIMPLETIMEd) TIMEFigure 4.19: Comparison of the performance of various planners on the IPC3 DriverLog domain.1000810121416182014161820instance numbera) STRIPS10000b) NUMERIC10000SGPlanLPG-1.2LPG.speedMIPS.plainVHPOP1000100CPU sec.100010000CPU sec.1001000010000SGPlanLPG-1.2LPG.speedFF.speedMIPS.plainVHPOPSimplannerCPU sec.CPU sec.1001000SGPlanLPG-1.2LPG.speedMIPS.plainSapa100CPU sec.100010000SGPlanLPG-1.2LPG.speedFF.speedMIPS.plainVHPOPSimplannerCPU sec.100001010110.10.1solvers significantly more instances than all other planners.
It is only slightly slower thanFF.speed in some instances and is faster than others. f) In the Satellite domain, SGPlangsolves 118/120 instances, more than any other planners. Only LPG1.2 that solves 114/120 is0.01246810121416180.0120instance number681012d) TIMEFigure 4.20: Comparison of the performance of various planners on the IPC3 ZenoTravel domain.NUMERIC, and COMPLEX variants, but is slightly slower in the other three variants.In summary, we have presented in this section SGPlang , a planner that won the firstprize in the Suboptimal Temporal Metric Track and the second prize in the SuboptimalPropositional Track in IPC4. Our approach is based on the observation that the fractionof active global mutual-exclusion constraints across subproblems is very small, when the1194instance numberc) SIMPLETIMEclose to SGPlang .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
