Chen Disser (1121212), страница 3
Текст из файла (страница 3)
. . . . . 1044.9Resolution of active violated global constraints in nine IPC4 instances using SA andSB for updating penalty values. In each instance, we plot the remaining numberof active global constraints with respect to the total number of subgoals evaluateddashed lines, whereas inactive mutual exclusions are shown as dotted lines. . . . .during planning.
The x axis includes the number of subgoals evaluated in the first86iteration in order to determine the active global constraints. . . . . . . . . . . . . 1064.10 Comparison of the performance of IPC4 planners on the Airport domain. . . . . . 1084.11 Comparison of the performance of IPC4 planners on the Pipesworld domain. . . . 1104.12 Comparison of the performance of IPC4 planners on the Promela domain. .
. . . 111xiiixiv4.13 Comparison of the performance of IPC4 planners on the PSR domain. . . . . . . 1134.26 SGPlant (ASPEN,N): The partition-and-resolve procedure used in SGPlan that par-4.14 Comparison of the performance of IPC4 planners on the Satellite domain. . . . . 114titions a planning problem along its temporal horizon into N subproblems, that calls4.15 Comparison of the performance of IPC4 planners on the Satellite domain. . . .
. 115ASPEN to solve the subproblems, and that resolves violated global constraints. An-4.16 Comparison of the performance of IPC4 planners on the UMTS domain. . . . . . 116nealing (Lines 9-10) is used to probabilistically accept a probe with worse penalty-4.17 Comparison of the performance of IPC4 planners on the Settlers domain. . . . . .
117function value during descents of Γd . . . . . . . . . . . . . . . . . . . . . . . . . 1294.18 Comparison of the performance of various planners on the Depots domain. . . . . 1184.27 Number of iterations taken by static and dynamic partitioning to find a feasible4.19 Comparison of the performance of various planners on the IPC3 DriverLog domain. 1194.20 Comparison of the performance of various planners on the IPC3 ZenoTravel domain. 120plan in the 8-orbit CX1-PREF problem. . .
. . . . . . . . . . . . . . . . . . . . 1314.28 Quality-time comparisons of ASPEN, SGPlant (ASPEN,1), SGPlant (ASPEN,100,STATICP ),4.21 Comparison of the performance of various planners on the IPC3 Rovers domain. . 121and SGPlant (ASPEN,100,DYNP ). (All runs involving SGPlant were terminated at4.22 Comparison of the performance of various planners on the IPC3 Freecell and Settlers24,000 iterations.). . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132domains. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1224.23 Comparison of the performance of various planners on the IPC3 Satellite domain.1235.1dot in each graph represents a variable associated with a constraint. . . . . . 1354.24 A toy example from ASPEN [16] whose goal is to find a valid schedule that completes4 activities, act 1 and act 2 that are instances of type A1 and act 3 and act 4 thatRegular structures of constraints in some MINLP and CNLP benchmarks. A5.2CPOPT: Implementation of the partition-and-resolve framework to look forCLMm of (5.1). .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138are instances of type A2, while minimizing the total power used. The number ofiterations to solve the problem is reduced from 16 taken by ASPEN to 12 after5.3Ratio of global constraints when partitioned by different PIVs for two MINLPs.141partitioning.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1265.4An iterative algorithm to estimate the optimal number of partitions. . . . . . 1424.25 The 3,687 constraints of an initial infeasible schedule generated by ASPEN in solving CX1-PREF with 16 orbits.
Each constraint is shown as a line that relates twoactivities (labeled in the y-axis) scheduled at two time instances in the horizon(x-axis). The partitioning of the constraints into four stages (separated by boldvertical lines) leads to 3,580 local constraints and 107 global constraints. A localconstraint remains associated with a stage even when activities are rescheduled.The number of iterations to find a better solution to the problem is reduced from12,043 taken by ASPEN to 1,102 after partitioning.
. . . . . . . . . . . . . . . . 128xvxviChapter 1as PDDL, and are usually drawn from real-world applications, such as airport operations,petroleum delivery, optical-network routing, satellite operations, electricity networks, mobilecommunication networks, logistics, and games. An AI planning problem typically involvesIntroductionfinding a sequential or parallel schedule of actions to achieve a set of subgoals, subject tological, temporal, and numerical constraints among actions.The NASA-related planning problems of spacecraft operations entail finding a sequence1.1Problem Formulationof low-level actions to achieve some user-defined high-level scientific goals subject to temporal constraints among actions, while optimizing a objective function at the mean time.Nonlinear optimization is an important problem that has abundant applications in scienceAt NASA, some of the primary systems that require autonomous operations include deepand engineering.
In this thesis, we study general mixed-integer nonlinear programmingspace probes, planetary rovers, and deep-space communication antennae. Automated planproblems (MINLPs) of the following form:ning/scheduling technologies have great promise in reducing operations cost while increasing(Pm ) :minzf (z),(1.1)the autonomy of aerospace systems. Automating the sequence-generation process allowsspacecraft commands by non-operations personnel, hence allowing significant reductions insubject toh(z) = 0 and g(z) ≤ 0,where variable z = (x, y), x ∈ Rv is the continuous part, and y ∈ D w is the discrete part.The objective function f is lower bounded and is continuous and differentiable with respectto x, whereas the constraint functions g = (g1 , .
. . , gr )T and h = (h1 , . . . , hm )T are generalfunctions that can be discontinuous, non-differentiable, or not even in closed form.MINLPs defined in (1.1) cover a large class of nonlinear optimization problems, withdiscrete nonlinear programming problems (DNLPs) and continuous nonlinear programmingproblems (CNLPs) as special cases.
Ample applications exist in operations research, planningand scheduling, optimal control, engineering designs, and production management. Theapplications we have studied in this research include AI and NASA-related planning andscheduling problems, and engineering design applications formulated as NLPs.The AI planning problems are modelled in some standard modelling languages, such1mission operations workforce.Many engineering design problems are also formulated and solved as NLPs.
Exampleapplications include trajectory optimization for robots and missiles, structural optimization,power flow design, financial portfolio management, principle component analysis, filter design, facility location selection, and optimal control. The constraint and objective functionscan be linear, quadratic, and nonlinear, the variables can be discrete, continuous, or mixed,and the typical size of a problem ranges from 10 to 5000 variables and constraints.MINLPs defined in (1.1) are difficult and expensive to solve.
Their prohibitive searchcomplexity is a key factor that hinders the development of many important computer scienceand engineering applications. For instance, automated planning and theorem proving inAI are not practical for large applications due to their high computational costs involvedin solving problems that can be formulated as discrete NLPs. As another example, our2capabilities in nonlinear optimal control are very limited because we do not have efficientways for solving multistage nonlinear optimization problems.Variable IDMINLPs are technologically difficult to solve for several reasons.
First, they involve hugesearch spaces that grow exponentially with respect to the number of variables. Existingsolvers have difficulties in solving large instances because of the exponential complexity.Second, the constraints in (1.1) may not be continuous and differentiable, which can beutilized to facilitate an efficient search. These constraints could be discontinuous, nondifferentiable, and not even in closed form.
Third, we do not assume any special properties18016014012010080604020001020on these functions, such as linearity and convexity. The functions can be nonlinear orsymbolic.304050607080Constraint IDFigure 1.1: Regular structure of constraints in TRIMLON12. A dot in the graph representsIn this research, we have made a key observation that most MINLPs from real-worlda variable associated with a constraint.applications have strong structures and locality of constraints.
Motivated by this observation,we propose a general approach to significantly reduce the search complexity by exploitingrolls by assigning continuous variables m and y and integer variables n in order to minimizethe constraint structure and by partitioning the problem constraints.f as a function of the trim loss and the overall production cost.lems and by showing how the partitioning of constraints can lead to a significant reductiony[j], m[j], n[j, i] where i = 1, · · · , I; j = 1, · · · , Jminz=(y,m,n) f (z) = Jj=1 (c[j] · m[j] + C[j] · y[j])Bmin ≤ Ii=1 (b[i] · n[i, j]) ≤ BmaxIi=1 n[i, j] − Nmax ≤ 0of solution time.y[i] − m[j] ≤ 0(C3)(C4)1.2.1m[j] − M · y[j] ≤ 0Nord[i] − Jj=1 (m[j] · n[i, j]) ≤ 0.1.2Observations on Constraint Structurevariables:objective:We motivate this research work by examining the constraint structure of two example prob-subject to:Example I: The TRIMLON Benchmark(OBJ)(C1)(C2)(C5)We start by showing the problem structure of an example MINLP called TRIMLON12 thatcannot be solved by existing solvers.
This is an instance of the TRIMLON benchmark [36]with I = 12 and J = 12. The goal is to produce a set of product paper rolls from raw paperAn instance of TRIMLON can be specified by defining I and J, leading to (I + 2)J variables and 5J + I constraints. For example, there are 168 variables and 72 constraints inTRIMLON12.341800.2160140Variable ID120GlobalConstraints100806040Subproblem 2Subproblem 1Local Constraints20001020304050Constraint ID607080Figure 1.2: An illustration of the partitioning of the constraints in TRIMLON12 into 12Fraction of Global ConstraintsSubproblem 12Subproblem 110.15TRIMLON12C-ReloadORTHRGDSOPTCDEG30.10.05002468Number of Partitions1012Figure 1.3: Monotonic increase in the fraction of constraints that are global with respect tosubproblems.increasing number of partitions on four benchmarks.A key observation we have made on many application benchmarks, including TRIMLON12, is that their constraints do not involve variables that are picked randomly from(OBJ).
(C1)-(C4) are its local constraints because each involves only local indexes on j.their variable sets. Invariably, many constraints in existing benchmarks are highly struc-(C5), however, is a global constraint because it involves a summation over all j.tured because they model spatial and temporal relationships that have strong locality, suchas those in physical structures and task scheduling.Figure 1.1 illustrates this point by depicting the constraint structure of TRIMLON12. ItFigure 1.2 illustrates the partitioning of TRIMLON12 into N = 12 stages, where SJ ispartitioned evenly and Sk = {k}.
Out of the 72 constraints, 60 are local constraints and 12are global constraints. Hence, the fraction of constraints that are global is 16.7%.shows a dot where a constraint (with unique ID on the x axis) is related to a variable (withThe fraction of global constraints in a problem instance depends strongly on its constrainta unique ID on the y axis). With the order of the variables and the constraints arrangedstructure and the number of partitions. Using the straightforward scheme as in TRIMLON12properly, the figure shows a strong regular structure of the constraints.to partition the constraints evenly, Figure 1.3 illustrates the fraction of global constraintsBased on the regular constraint structure of a problem instance, we can cluster its con-either increases monotonically or stays unchanged with respect to the number of partitionsstraints into multiple loosely coupled groups.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
