Chen Disser (1121212), страница 23
Текст из файла (страница 23)
. . , 60;// color state constraint for act 1(c4)s(cc b) = t =⇒ c(t) − 1 = 0; ∀ t = 0, . . . , 60;// color changer cc b effect constraintThe constraints are either equality or inequality constraints (such as (c1) and (c2)), or125126B are equality or inequality constraints, can be encoded as an equivalent equality constraintH(A =⇒ B) = 0:Activitiesdeduction constraints (such as (c3) and (c4)). A deduction constraint A =⇒ B, where A andsrsspssinlightcsgcclimtc2tc1sporsposspecasspinitiifhheescpcotcftconccnocdocapaotnao0H(A =⇒ B) =1000020000300004000050000Time Horizon60000700008000090000100000Figure 4.25: The 3,687 constraints of an initial infeasible schedule generated by ASPEN in solving⎧⎪⎪⎨0if A is false, or A and B are both true⎪⎪⎩numerical violation of Bif A is true but B is false.CX1-PREF with 16 orbits.
Each constraint is shown as a line that relates two activities (labeledin the y-axis) scheduled at two time instances in the horizon (x-axis). The partitioning of theconstraints into four stages (separated by bold vertical lines) leads to 3,580 local constraints and107 global constraints. A local constraint remains associated with a stage even when activities arerescheduled. The number of iterations to find a better solution to the problem is reduced from12,043 taken by ASPEN to 1,102 after partitioning.For example, the equivalent equality constraint encoding (c3) returns 0 if s(act 1) = t isfalse; otherwise, it returns the value of (c(t) − 2).resulting problem has fifteen (resp.
3,580) local constraints and four (resp. 107) global constraints. Since some global constraints may be satisfied or new constraints corresponding to4.2.2Temporal locality in ASPEN planningnew actions may be added as planning progresses, we also study algorithms to determine aIn this research, we analyze the constraints of a temporal planning problem in order tosuitable number of stages and to repartition the constraints periodically in order to balancepartition them into a small number of simpler subproblems (stages). In general, it is hard tothe number of violated constraints in each stage.develop a good partitioning algorithm that minimizes the time to solve a planning problemIf the number of stages is small, the overhead of resolving a small number of globalbecause the relation between the time to solve a stage and that to resolve violated globalconstraints will be low, but the overhead of evaluating each stage will be high. On the otherconstraints is complex and unknown.
A good partitioning algorithm must achieve a properhand, if the number of stages is large, then the resolution of the many global constraints willbalance between the overheads of local evaluation and global resolution.be costly, even though the overhead of evaluating a stage will he low.In this research, we exploit the temporal locality of constraints in ASPEN planningNext, we describe a partition-and-resolve procedure that implements constraint parti-problems when partitioning them into stages. Starting from an initial (possibly infeasible)tioning in the ASPEN planning system.
The procedure iterates between calling a modifiedschedule, we partition the constraints along the horizon into a small number of stages, eachASPEN planner to solve the constraint-partitioned subproblems, and using a constraint-with an approximately equal number of constraints.reweighting strategy to resolve the violated global constraints across the subproblems. WeTo illustrate the temporal locality of constraints in ASPEN planning problems, Fig-demonstrate significant improvements in solving some ASPEN benchmarks for aerospaceure 4.24 (resp. Figure 4.25) shows the nineteen (resp. 3,687) constraints of an initial in-operations.
For example, the problem in Figure 4.24 (resp. 4.25) can be solved by ASPENfeasible schedule generated by ASPEN [16] in solving the toy example (resp. CX1-PREFin 16 (resp. 12,043) iterations and by our our implementation in 12 (resp. 1,102) iterationswith sixteen orbits). After partitioning the constraints into three (resp.
four) stages, thewith the same (resp. better) quality.1271281. procedure SGPlant (ASPEN,N)2.generate initial plan and set initial temperature T ;3.partition time horizon into N stages;4.repeat5.num descents ← 1;6.for t = 1 to N7.for k = 1 to num descents8.call ASPEN to solve (3.31) by generating a new schedule in a child process;9.evaluate Γd (t) and the Metropolis probability controlled by T ;10.if Γd (t) is accepted then11.call ASPEN to apply the action in the main process;12.update penalties α(t) and β(t) on violated local constraints;13.end if14.end for15.end for16.update penalties γ and η on violated global constraints;17.num descents ← min(100, num descents ∗ 2);18.reduce temperature T ← T × c;19.dynamically repartition the stages (only done in SGPlant (ASPEN,N,DYNP ));20.until no change in z, α, β, γ, η in an iteration;21.
end procedureFigure 4.26: SGPlant (ASPEN,N): The partition-and-resolve procedure used in SGPlan that par-applications are not differentiable, the new schedule generated does not likely follow descentdirections, and a local search may get stuck easily in infeasible local minima. To this end,SGPlant (ASPEN,N) employs annealing to determine whether to accept the new schedule(Lines 9-10).
Using a parameter called temperature, it accepts the new schedule with largerΓd based on the Metropolis probability, with the acceptance probability decreasing as thetemperature decreases. In our algorithm, we fix the initial temperature to 1,000 and reduceit in every iteration by a factor c = 0.8.Two other important issues that must be addressed in our partition-and-resolve implementation are the number of stages used and the duration of each.
In ASPEN, a conflict hasan active window bounded by a start time and an end time called the time points. Adjacenttime points can be collapsed into a stage, since ASPEN has discrete time horizons.We have studied both the static and the dynamic partitioning of stages. In static par-titions a planning problem along its temporal horizon into N subproblems, that calls ASPEN tosolve the subproblems, and that resolves violated global constraints. Annealing (Lines 9-10) is usedto probabilistically accept a probe with worse penalty-function value during descents of Γd .titioning, SGPlant (ASPEN,N,STATICP ) partitions the horizon statically and evenly into N4.2.3stages. During a search, some stages may contain no conflicts to be resolved, while othersImplementation of partition-and-resolve search in ASPEN.Based on the pseudo code in Figure 5.2, we have implemented SGPlant (ASPEN,N), a plannerthat partitions a planning problem along its temporal horizon into N subproblems of theform in (3.31) and that calls ASPEN to solve the subproblems [15].
In our implementation,we set the weight of the objective function J(z) in (3.31) to 100 (since the preference scoreis between 0 to 1), initialize all penalties to zeroes, and increase the penalties of violatedschedule constraints in each iteration by 0.1.In generating a new schedule from the current schedule during descents of Γd (Line 8 ofFigure 4.26), ASPEN chooses probabilistically among its repair and optimization actions,selects a random feasible action at each choice point, and applies the selected actions tothe current schedule. Since many of the objectives and constraints in complex spacecraft129stages. This simple strategy often leads to an unbalanced number of time points in differentmay contain a lot of conflicts. Such an imbalance leads to search spaces of different sizesacross different stages and search times that may be dominated by those in a few stages.To achieve a better balance of activities across stages, SGPlant (ASPEN,DYNP ) adjuststhe boundary of stages dynamically.
This is accomplished by finding M, the number of timepoints in the horizon related to conflicts, at the end of the outer loop (Line 15) and bypartitioning the horizon into N stages in such a way that each stage contains approximatelythe same number (M/N) of such time points (Line 19). To determine the best N, Figure 4.27plots the number of iterations taken by static and dynamic partitioning in finding a feasibleschedule of the 8-orbit CX1-PREF problem.
The results show that N = 100 is a good choice.Since other benchmarks lead to similar conclusions, we set N = 100 in our experiments. Note1303000200010000110100Number of Stages N1000Figure 4.27: Number of iterations taken by static and dynamic partitioning to find a feasible planin the 8-orbit CX1-PREF problem.that although N is relatively large, some stages will have all their local constraints satisfied asplanning progresses. To avoid managing such defunct stages, our implementation collapsesautomatically adjacent defunct stages in such a way that each resulting stage contains at0.680.640.60.56ASPENSGPlant(ASPEN,1)SGPlant(ASPEN,100,STATICP)SGPlant(ASPEN,100,DYNP)0.520.4802000ASPENSGPlant(ASPEN,1)SGPlant(ASPEN,100,STATICP)SGPlant(ASPEN,100,DYNP)0.600.400.2000100ASPENSGPlant(ASPEN,1)SGPlant(ASPEN,100,STATICP)SGPlant(ASPEN,100,DYNP)0.60.550.50.45010000200300Iteration400Best Feasible Score (Higher is Better)(a version of our planner without partitioning) on the five benchmarks described earlier inthis section.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
