Chen Disser (1121212), страница 2
Текст из файла (страница 2)
. . . . . . . . . . . . . . 122viii4.2.1SGPlant (ASPEN): A planner using ASPEN to solve partitioned problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1224.34.2.2Temporal locality in ASPEN planning . . . . . . . . . . . . . . . . . 1274.2.3Implementation of partition-and-resolve search in ASPEN. . . . . .
. 1294.2.4Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . 131Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133Chapter 55.15.2List of TablesApplication on Mathematical Programming Benchmarks .
. . . 1344.1Average rg,T , rg,G , rga,G across the instances of IPC4 domains. Boxed numbers are4.2Number of instances in each domain solved by the top planners that participatedless than 0.1.Problem Structure of Benchmarks . . . . . . . . . . .
. . . . . . . . . . . . . 134Partitioning and Resolution Strategies . . . . . . . . . . . . . . . . . . . . . 1375.2.1CPOPT: the partition-and-resolve procedure . . . . . . . . . . . . . . 1385.2.2Strategies for partitioning constraints into subproblems . . . . . . . .
1395.2.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .96in IPC4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1081174.3Number of instances in each IPC3 domain solved by the eight planners compared.Strategies for updating penalty values . . . . . . . . . . . . .
. . . . . 1435.1Trade-offs between N and total solution time on the SPACE-960-r problem . 1425.3Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1445.2Average and standard deviation of solution time per subproblem for two5.4Summary . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 154benchmarks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1435.3Chapter 6Results on solving MINLP benchmarks from the MacMINLP library [55]. Results onConclusions and Future Work . . . . .
. . . . . . . . . . . . . . . 155MINLP BB and BARON were obtained by submitting jobs to the NEOS server [61]6.1Summary of Work. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1556.2Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 156and BARON’s site [76], respectively; results of other solvers were collected on anAMD Athlon MP2800 PC running RH Linux AS4 and a time limit of 3,600 sec.References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158All timing results are in seconds and should be compared within a solver but notacross solvers because they might be run on different computers. Solutions withVita . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167the best quality are boxed. “−” means that no feasible solutions were found in thetime limit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1465.5Results on solving selected CNLP benchmarks from the CUTE library [13].Results of all solvers were collected on an AMD Athlon MP2800 PC runningRH Linux AS4 and a time limit of 3,600 sec. Solutions with the best qualityare boxed. “−” means that no feasible solutions were found in the time limit.
148ixx5.7Results on solving CNLP benchmarks from the CUTE library [13]. Results ofall solvers were collected on an AMD Athlon MP2800 PC running RH LinuxAS4 and a time limit of 3,600 sec. Solutions with the best quality are boxed.“−” means that no feasible solutions were found in the time limit.List of Figures. . .
. . 1491.1Regular structure of constraints in TRIMLON12. A dot in the graph represents a variable associated with a constraint. . . . . . . . . . . . . . . . . . .1.2An illustration of the partitioning of the constraints in TRIMLON12 into 12subproblems. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .1.35Monotonic increase in the fraction of constraints that are global with respectto increasing number of partitions on four benchmarks. . . . . . . . . . . . .1.446Exponential decrease in the average time to solve a subproblem with respectto increasing number of partitions on the TRIMLON12 and the ORTHRGDSbenchmarks. . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .71.5The topology of the airport in the AIRPORT4 planning problem instance. .81.6The exponential growth in complexity of two existing planners on the AIRPORT domain. The x-axis shows the number of airplanes (subgoals) in theproblem instance, and the y-axis shows the solution time to find a feasible solution. We have used LPG1.2 [30] and FF2.0 [37] on an AMD Athlon MP2800PC running Linux AS4. .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.79Illustration of the mutual exclusion constraints in the AIRPORT planningproblem. Each box represents an action, and there is a line between two1.8xiactions if there is a mutual-exclusion constraint between them. . . . . . . . .10Illustration of constraint locality in the AIRPORT4 instance. . . . . . . . .
.11xii1.94.2Comparison of solution times of LPG, FF, and SGPlan on the AIRPORTplanning domain with an increasing number of airplanes. . . . . . . . . . . .122.1A classification of existing penalty methods. . . . . . . . . . . . . . . . . . .192.2An illustration of subspace partitioning and constraint partitioning. SubspaceVarious scenarios in the activation of mutual-exclusion relationships between actionsa and b.
A solid arrow shows the case when a precondition, an add effect, or a deleteeffect is effective at the beginning, the end, or the entire duration of an action. Anactive mutual exclusion is shown as a dashed arrow. . . . . . . . . . . . .
. . . .4.3partitioning decomposes P into a disjunction (∨) of subproblems, where the89instance of the IPC4 AIRPORT-TEMPORALvariant in the Airport domain. Each rectangular box represents an action, whereascomplexity of each subproblem is similar to that of P . In contrast, constrainta line joining two actions represents a mutual-exclusion constraint (that may bepartitioning decomposes P into a conjunction (∧) of subproblems and a set ofinactive). Most constraints (79 out of 93 or 84%) are local constraints after parti-global constraints (G) to be resolved, where the complexity of each subproblemis substantially smaller than that of P .Mutual-exclusion constraints in the4th. .
. . . . . . . . . . . . . . . . . .302.3A classification of existing planning and scheduling approaches. . . . . . . .392.4Subspace partitioning in planning by branching on variable assignments. . . . . .423.1An illustration that (3.4) is satisfied when α∗∗ > α∗ = 10 for the CNLPtioning them by subgoals. Global constraints are shown in dashed lines in (b).
. .934.4Variations of rg,T , rg,G , and rga,G across the instances of seven IPC4 domains. . . .944.5SGPlang : A planner implementing the partition-and-resolve procedure in Figure 5.2. 974.6SGPlang : A planner implementing the partition-and-resolve procedure in Figure 5.2. 974.7Generating 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 aproblem in (2.26). Lc (x, α∗∗ ) is a strict local minimum around x∗ = 5 whenα∗∗ > α∗ but is not one when α∗∗ = α∗ . . . . . . . . . . . . . . . . . . . . . .50local subplan from each starting state and evaluates (4.6) in order to find a subplan3.2Iterative procedures to look for CLMc of Pc and CLMm of Pm . . . . . .
. . .57that improves the penalty function. . . . . . . . . . . . . . . . . . . . . . . . .3.3The partition-and-resolve procedure to look for CLMm of Pt . . . . . . . . . .643.4The search procedure of constraint partitioned simulated annealing (CPSA).673.5CPSA: the constraint partitioned simulated annealing algorithm.. . . . . .683.6Proof strategy for Theorem 3.8.. . . . . . . . . . . . . .
. . . . . . . . . .783.7The construction of a path from y to y∗ . . . . . . . . . . . . . . . . . . . . .814.1An example temporal plan. Active mutual exclusions between actions are shown as4.899The planning process of SGPlang using SA in the second iteration in solving theAIRPORT-TEMPORAL-14 instance. Each box corresponds to an action in a subplan, whereas each arrow corresponds to an active global constraint. . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
