Chen Disser (1121212), страница 22
Текст из файла (страница 22)
In terms of speed, SGPlang is faster than LPG1.2 in the HARDNUMERIC,212010001000010000100010001001001001010101110.10.10.10.010.010.012468101214161820246instance number1000101214161820b) NUMERICSGPlanLPG-1.2LPG.speedMIPS.plainVHPOP101SGPlanLPG-1.2LPG.speedFF.speedVHPOPSimplanner2instance numbera) STRIPS100008CPU sec.CPU sec.100SGPlanLPG-1.2LPG.speedFF.speedMIPS.plainCPU sec.100010000SGPlanLPG-1.2LPG.speedFF.speedMIPS.plainVHPOPSimplannerCPU sec.1000046810121416180.10.0120SGPlanLPG-1.2FF.speed24instance number68101214161820instance numbera) Freecell domainb) Settlers domainFigure 4.22: Comparison of the performance of various planners on the IPC3 Freecell and Settlersdomains.CPU sec.1004.210Applications on ASPEN Planning1In this section, we describe the ASPEN (Automated Scheduling and Planning Environment)0.10.012468101214161820instance numberc) SIMPLETIMEFigure 4.21: Comparison of the performance of various planners on the IPC3 Rovers domain.system [16] developed at the Jet Propulsion Laboratory and its available benchmarks onspacecraft operation planning.
We then present our prototype planner SGPlant (ASPEN,N)that partitions a problem along its temporal horizon into N stages, that calls ASPEN tosolve the subproblems, and that resolves violated global constraints. Finally, we compareconstraints of a planning problem are partitioned by its subgoals into subproblems. Based onthe performance between ASPEN and SGPlant (ASPEN,N).the theory of extended saddle points, the partition-and-resolve approach can limit the searchspace to be backtracked in resolving violated global constraints. We have also discussed otherrelated techniques in SGPlang for reducing the search space and for handling the new features4.2.1SGPlant (ASPEN): A planner using ASPEN to solvepartitioned problemsin PDDL2.2.
Our experimental results show that SGPlang performs well on both the IPC3ASPEN [16] is an objective-based planning system for the automated planning and schedul-and IPC4 domains.ing of complex spacecraft operations. The application [45] involves finding a sequence oflow-level commands from a set of high-level science and engineering goals, such as spacecraftoperability constraints, flight rules, hardware models, science experiment goals, and operation procedures, subject to parameter dependencies and temporal and resource constraints.1211221000CPU sec.10010000SGPlanLPG-1.2LPG.speedFF.speedMIPS.plainVHPOPSimplanner1000100.10.146810121416180.0120ment goals, and operations procedures.
It defines various types of schedule constraints thatmay be in procedural form among or within the parallel activities to be scheduled. Such con-12spacecraft operability constraints, flight rules, spacecraft hardware models, science experi-1010.01Using a discrete time horizon and a discrete state space, an ASPEN model encodesSGPlanLPG-1.2LPG.speedFF.speedMIPS.plain100CPU sec.10000straints include temporal, decomposition, resource, state-dependency, and goal constraints.In addition, the quality of a schedule is defined in a preference score, which is a weighted246instance numbera) STRIPS100001000101214161820sum of multiple preferences (that may also be procedural) to be optimized by the planner.b) NUMERIC10000SGPlanLPG-1.2LPG.speedMIPS.plainVHPOP1000100Preferences can be related to the number of conflicts, the number of actions, the value of aSGPlanLPG-1.2FF.speedMIPS.plainresource state, or the value of an activity parameter.100CPU sec.CPU sec.8instance number10Since ASPEN cannot optimize plan quality and search for feasible plans at the same time,10110.10.1it alternates between a repair phase and an optimization phase.
In the repair phase [69],ASPEN generates an initial schedule that may have conflicts and searches for a feasible plan0.01246810121416180.0120from this initial plan, using iterative repairs to resolve conflicts individually. In a repair246instance number10001214161820iteration, the planner must decide at each choice point a conflict to resolve and a conflict-d) HARDNUMERIC10000SGPlanLPG-1.2LPG.speedMIPS.plainSapa1000CPU sec.100CPU sec.10instance numberc) SIMPLETIME100008resolution method from a rich collection of repair heuristics.
In the optimization phase,SGPlanLPG-1.2MIPS.plainSapaASPEN uses a preference-driven, incremental, local-optimization method to optimize plan100quality defined by a preference score. It decides the best search direction at each choice point,10based on information from multiple choice points. In our experiments, we allow ASPEN to11alternate between a repair phase with an unlimited number of iterations and an optimization0.10.10.010.01102468101214161820instance numberphase with 200 iterations (both defaults in ASPEN).2468101214161820instance numbere) TIMEf) COMPLEXFigure 4.23: Comparison of the performance of various planners on the IPC3 Satellite domain.The ASPEN software can be tested on several publicly available benchmarks that scheduleparallel spacecraft operations.
In this thesis, we have tested the four available benchmarksin the public domain: a) The CX1-PREF benchmark [95] models the planning of operationsof the Citizen Explorer-1 (CX-1) satellite that involve taking data related to ozone anddownloading the data to ground for scientific analysis.
Its problem generator can generate123124problem instances with a user-specified number of satellite orbits. In our experiments, wehave studied CX1-PREF with 8 and 16 orbits, respectively. b) The DCAPS benchmark [68]models the operation of DATA-CHASER shuttle payload that is managed by the Universityof Colorado at Boulder. c) OPTIMIZE and PREF are two benchmarks developed at JPLthat come with the licensed release of ASPEN.Figure 4.24 illustrates a toy problem in ASEPN [16] model and its constrained formulation. The problem involves scheduling four activities: act 1 and act 2 of type A1 andact 3 and act 4 of type A2, over a discrete horizon of 60 seconds. Its goal is to satisfymodel toy HORIZON START = 1998-1/00:00:00; horizon duration = 60s; time scale =second;;parameter string color domain = ("red", "blue", "green");;state variable color sv states = ("red", "blue", "green"); default state = "red";;resource power type = non depletable; capacity = 25; min value = 0;;activity color changer color c; duration = 1; reservations = color sv change toc;;activity A1 duration = [10,20]; constraints = ends before start of A2 by [0,30];reservations = power use 10, color sv must be "green";;activity A2 duration = 10; reservations = power use 20, color sv must be "blue";;prefer linearly less resource power total value;; //optimization objective// initial infeasible scheduleA1 act 1 start time = 0; duration = 15;; A1 act 2 start time = 20; duration = 10;;A2 act 3 start time = 30; duration = 10;; A2 act 4 start time = 50; duration =10;;0the nineteen constraints, E1 through E19 , on positive and negative facts and preconditionsand effects of actions, while minimizing the total power resource used.
Based on the initial infeasible schedule, the 19 constraints are partitioned into 3 stages, {E1 , E5 , E9 , E11 },{E2 , E3 , E6 , E7 , E10 , E12 , E13 , E15 }, and {E4 , E8 , E14 }, and 4 global constraints {E16 , E17 , E18 , E19 }.A110act 120E11act 2Stage 1A2E1cc bcolor changer30E12E16E5E2E64060Time HorizonStage 3Stage 2E18E15act 3cc gE10 E3E9color statered50- power resource constraints E5 -E8 for act 1-act 4;- color state transition constraints E9 and E10E17act 4E13E4E7E810020relating color changer and color state;- act 2 ends before start of act 3 by [0,30] (E15 )Global constraints (dashed arrows):- act 1 ends before start of act 3 by [0,30] (E16 );- act 2 ends before start of act 4 by [0,30] (E17 );power resourceIn a MINLP formulation of the toy example, each of the nineteen constraints E1 -E19 inE14- duration constraints E11 -E14 for act 1-act 4;greenblueLocal constraints (solid arrows):- color state constraints E1 -E4 for act 1-act 4;0E1920- act 1 ends before start of act 4 by [0,30] (E18 );- power resource always less than capacity ofpower resource (E19 ).Figure 4.24 is transformed into one or more equivalent constraints.
We use two variables s(a)and e(a) to denote, respectively, the starting and ending times of activity a. For each state,we assign a vector of state variables denoting their values indexed by time. For example,Figure 4.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 that are instances oftype A2, while minimizing the total power used. The number of iterations to solve the problem isreduced from 16 taken by ASPEN to 12 after partitioning.we use c(t) to denote the color state at time t, which can be set to 0 (red), 1 (blue), or 2(green); p(t) to denote the power supply at t; and w(t) to denote the power usage at t.
The(c1)w(t) ≤ p(t) ≤ 25, ∀ t = 0, . . . , 60;// power resource capacity constraintfollowing illustrates a small portion of the resulting constraints encoded:(c2)0 ≤ s(act 3) − e(act 1) ≤ 30;// act 1 ends before start of act 3 by [0,30](c3)s(act 1) = t =⇒ c(t) − 2 = 0; ∀ t = 0, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
