Chen Disser (1121212), страница 4
Текст из файла (страница 4)
To illustrate the idea, consider the partitioningfor the four benchmarks [55], including TRIMLON, C-Reload (a MINLP problem modellingof the constraints in TRIMLON12 by index j ∈ SJ = {1, · · · , 12}. Suppose SJ is partitionednuclear core reload pattern optimization), ORTHRGDS (a CNLP problem of finding theinto N disjoint subsets such that S1 ∪· · ·∪SN = SJ .
Then the k th subproblem, k = 1, . . . , N,least square error in orthogonal regression), and OPTCDEG3 (a CNLP problem for nonlinearhas variables y[j], m[j], n[j, i], where i = 1, · · · , I, j ∈ Sk , and the same objective functionoptimal control in a noise damping system).56Avg Time for Solving a SubproblemAvg Time for Solving a Subproblem10000100010010124681012Number of Partitions100001000An exampleDomain:100A1(start)10g12g2g1602004006008001000b) ORTHRGDS(CNLP)Figure 1.4: Exponential decrease in the average time to solve a subproblem with respect toincreasing number of partitions on the TRIMLON12 and the ORTHRGDS benchmarks.g10g17g6g18g15g14g41g11A2(end)g13g3MunichAirportNumber of Partitionsa) TRIMLON12(MINLP)A3(start)g1g9A1(end)A2(start)g7g8A3(end)g5Facts: at(A1,g1), blocked(g1), unblocked(g1)Actions: move(A1,g1,g2)Initial Facts: at(A1,g1), at(A2,g5), at (A3,g13)Subgoals:at(A1,g9), at(A2,g12), at (A3,g8)Objective: minimize total timemove(A1,g1,g2)move(A1,g2,g6)move(A2,g5,g4)Planningmove(A3,g13,g14)move(A3,g7,g8)TimeProblem specificationA Solution PlanIn contrast, the time required to solve a subproblem decreases monotonically as theFigure 1.5: The topology of the airport in the AIRPORT4 planning problem instance.number of partitions is increased.
When a problem is partitioned by its constraints, eachsubproblem is much more relaxed than the original problem and can be solved in exponentially less time than the original. Figure 1.4 illustrates this exponential decrease on theaverage time for solving a subproblem with increasing number of partitions.
The overheadsbetween no partitioning and partitioning can be several orders of magnitude.problem in a modelling language to specify the facts, actions, initial state, and goals of theplanning problem. Note that the goal includes multiple subgoals, one for each airplane. Asolution plan, shown in the right bottom part of Figure 1.5, is a temporal plan where actionshave durations and can have overlapping execution times.Figure 1.6 illustrate the solution time of two existing planners in solving the AIRPORT1.2.2Example II: The AIRPORT Planning Problemproblem with various number of airplanes.
The two solvers are LPG [30], a stochastic plannerOur second example is an AI planning problem called AIRPORT from the test problemthat performs random probing in the solution space, and FF [37], a heuristic search plannersuite used by the Fourth International Planning Competition (IPC4) [23]. The AIRPORTthat performs hill climbing based on a relaxed-plan heuristic function. We can see that theproblem models an airport scheduling domain, where there are multiple airplanes to betime to solve the problem increases exponentially with increasing number of airplanes, whichmoved around in an airport.makes the scheduling of multiple airplanes very expensive.Figure 1.5 illustrates the topology of an airport in the AIRPORT4 instance. The exampleTo explain the exponential increase of search complexity of existing planners, we need toinvolves a planning task for moving three airplanes from their starting positions to someclosely examine the constraints involved with the problem.
In temporal planning problems,destination gates. To apply a planning system to solve the problem, we first model thisthe constraints are mutual exclusion constraints. Two actions are mutually exclusive if they781e+061000010001001000011000011001110000011110011000011111000000111100012345678109Number of planes0123456780011110011000011110000119Number of planesa) LPG (stochastic search)0011110000111 Subgoal (1 Plane)100000Time (ms)Time (ms)100000102 Subgoals (2 Planes)1e+06b) FF (heuristic search)Figure 1.6: The exponential growth in complexity of two existing planners on the AIRPORTdomain. The x-axis shows the number of airplanes (subgoals) in the problem instance, and3 Subgoals(3 Planes)00110011110000111100001100110011110000110011110000110011001111 111100000000110000000000011111111111001100111100000000000001111111111111001100 0011001111111111111000000000001100000000000001111111111100110000000000011111111111001100110011001100110011110000110011110000111100001111001100001100110011001111000011001111001100110000110011001100110011001100110011110000111100000000000001111111111111000011000000000001111111111100110011000000000001111111111111 1100000000000001111111111100110000011100110000000000011111111111001100110001110011001100110011110000110011110000110011001100110011001100111100001111000011110011001100110000110011 110000111100110000111100001100110011 1100110000111111 000011000011001111000011001100111100001111001100001111000011110000110011the y-axis shows the solution time to find a feasible solution.
We have used LPG1.2 [30] andFigure 1.7: Illustration of the mutual exclusion constraints in the AIRPORT planning probFF2.0 [37] on an AMD Athlon MP2800 PC running Linux AS4.lem. Each box represents an action, and there is a line between two actions if there is ainterfere with each other and cannot be scheduled in certain ways. Mutual exclusion will bedefined in detail in Chapter 4.
Here, it suffices to know that a plan is feasible when thereare no violated mutual exclusion constraints.mutual-exclusion constraint between them.a few global constraints relate two actions from different subproblems. This observation isintuitively sound because the movements of airplanes are largely independent. Two airplanesFigure 1.7 plots the mutual exclusion constraints in three AIRPORT planning problems,with one, two, and three subgoals, respectively. We see that the number of actions andthe number of constraints grow in proportion to the number of subgoals, which lead to anexponential growth in search complexity by existing planners that solve the planning problemas a whole.interact with each other only when they are at the same position and can be scheduledindependently most of the time.Based on the observation of constraint locality shown in Figure 1.8, we propose in thisthesis to partition the constraints by their subgoals into multiple subproblems, one for eachsubgoal, and solve each subproblem individually before composing the solution plan.
Fig-Figure 1.8 shows that the seemingly random constraints in the solution plans are infact highly structured and can be clustered by their subgoals. To see this, we generate aplan using LPG [30] for each of the three subgoals in the AIRPORT-4 instance, composethe plans together, and plot all the actions and the constraints. We show that most of theure 1.9 compares the search time of our planner SGPlan based on the constraint-partitioningapproach and those of LPG and FF. We see that the proposed approach leads to a significantreduction of search time and much better scalability.The performance improvement is due to the fact that, after we partition the problem intoconstraints are local constraints relating two actions from the same subproblem, and that only910Subgoal 2at(A2,g12)001100111100110000110011110000111100110011001100110000111100001111000011 1100110011000011110000111100001111000011110000110011110011000011110011000011Subgoal 3at(A3,g8)00111100001100111e+0600111100110011000011001111111111111000000000000011000000000001111111111111000000000000011111111111001100000000000111111111110000 1111100011 1100000000000001111111111100111000110000000000000 11111111111110011001111001100001111000011110011000011Metric-FFLPGSGPlan100000Time (ms)Subgoal 1at(A1,g1)10000100011001100100110000 1111000011001100111100001111000011Figure 1.8: Illustration of constraint locality in the AIRPORT4 instance.100123456Number of planes789Figure 1.9: Comparison of solution times of LPG, FF, and SGPlan on the AIRPORT planning domain with an increasing number of airplanes.multiple subproblems, each subproblem is much more relaxed than the original problem, andcan be solved much faster.
The subproblems are much more relaxed because they involvea much smaller number of constraints than that of the original problem. Thus, the totaltime to solve all the subproblems is significantly reduced. However, since there are globalconstraints that may be violated when multiple subplans are combined, the efficiency inresolving inconsistent global constraints is a key factor for the overall performance of theproposed constraint partitioning approach.identification of the constraint structure of a problem instance, the strategy to optimallypartition the problem, and the efficient resolution of its violated global constraints. To thisend, we study the following problems in this thesis:a) Automated partitioning strategy. There are two components of a partitioning scheme:the dimension in which constraints can be partitioned and the number of partitions.
Todetermine the dimension for partitioning constraints, we study methods for determining thestructure of a problem instance after possibly reorganizing its variables and constraints,1.3Research Goal and Problemsand identifying the dimension by which the constraints can be partitioned. To determineThe general goal of this thesis is to solve large-scale NLPs from planning and engineeringthe optimal number of partitions, we exploit trade-offs among the number of partitionsapplications efficiently by exploiting the problem structure and the partitioning of the con-(Figures 1.3), the overhead for evaluating each subproblem (Figure 1.4), and the overheadstraints.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
