Chen Disser (1121212), страница 17
Текст из файла (страница 17)
In contrast, a mutual exclusion is persistent if itholds at every level until the fix-point level (the last level of the graph) is achieved. In thisdissertation, we only consider level-independent, persistent mutual-exclusion relationships,as transient mutual exclusions are used exclusively for searches in GraphPlan.Two facts p and q are persistently mutual exclusive if all possible ways of making p trueare persistently exclusive with all possible ways of making q true; that is, each action ahaving p as an add-effect (p ∈ add(a)) is persistently mutual exclusive with each action bhaving q as an add-effect (q ∈ add(b)).
For simplicity, in the rest of this dissertation, weuse the terms mutual-exclusion actions and facts to refer to the corresponding persistentmutual-exclusion actions and facts.Given a temporal plan, a mutual-exclusion relationship can be active or inactive. Figure 4.2 illustrates the possible scenarios when a mutual-exclusion relationship is active. Notethat for temporal actions, a precondition fact can be effective at the beginning, at the end,or during the entire duration of an action; whereas an add or delete effect can be effectiveonly at the beginning or at the end of an action.When two actions a and b are mutual exclusive due to competing needs, that is, whena precondition fact pa of action a is mutual exclusive with a precondition fact pb of actionb, the mutual-exclusion relationship between a and b is active in a plan when one of theActions a and b are marked as persistently mutual exclusive when one of the followingoccurs.a) Actions a and b have persistent competing needs,1 where competing needs are represented by the persistent mutual exclusion of the preconditions of a and those of b;b) Actions a and b have persistent inconsistent effects, when one of the actions deletes anadd-effect of the other.c) Actions a and b have persistent interference, when one of the actions deletes a precondition of the other.1The terms “competing needs,” “inconsistent effects,” and “interference” were originally proposed forGraphPlan [11].8788pre(a)aaabbpre(b)bpre(b)pre(a)following nine conditions is satisfied (see Figure 4.2a):pre(a)pre(a)pre(b)pre(a)pre(a)aaabbbpre(b)pre(b)pre(b)pre(a)pre(a)pre(a)aaabbbpre(b)pre(b)pre(b)a) Nine scenarios to activate a mutual-exclusion relationship between two actions a and b with competing needs.(pre(a) is assumed to have competing needs to pre(b) : ∃f1 ∈ pre(a), f2 ∈ pre(b), f1 and f2 are mutual exclusive)add(a)add(a)add(a)add(a)aaabbbbdel(b)del(b)adel(b)del(b)b) Four scenarios to activate a mutual-exclusion relationship between two actions a and b with inconsistent effects.(add(a) is assumed to be overlapping with del(b): add(a) ∩ del(b) = ∅)pre(a)pre(a)pre(a)aa⎧⎪⎪⎪s(a) = s(b)⎪⎪⎪⎪⎪⎪⎪⎪e(a) = s(b)⎪⎪⎪⎪⎪⎪⎪⎪s(a) ≤ s(b) ≤ e(a)⎪⎪⎪⎪⎪⎪⎪⎪s(a) = e(b)⎪⎪⎪⎨e(a) = e(b)⎪⎪⎪⎪⎪⎪⎪s(a) ≤ e(b) ≤ e(a)⎪⎪⎪⎪⎪⎪⎪⎪s(b) ≤ s(a) ≤ e(b)⎪⎪⎪⎪⎪⎪⎪⎪s(b) ≤ e(a) ≤ e(b)⎪⎪⎪⎪⎪⎪⎪⎩s(b) ≤ e(a) and s(a) ≤ e(b)if pa is “AT START” and pb is “AT START”if pa is “AT END” and pb is “AT START”if pa is “OVERALL” and pb is “AT START”if pa is “AT START” and pb is “AT END”if pa is “AT END” and pb is “AT END”(4.3)if pa is “OVERALL” and pb is “AT END”if pa is “AT START” and pb is “OVERALL”if pa is “AT END” and pb is “OVERALL”if pa is “OVERALL” and pb is “OVERALL.”When actions a and b are mutual exclusive due to inconsistent effects, that is, when an addeffect aa of action a is also a delete effect db of action b, the mutual-exclusion relationshipbetween a and b is active in a plan when one of the following four conditions is satisfieda(Figure 4.2b):bbdel(b)pre(a)pre(a)del(b)aabbdel(b)bdel(b)pre(a)abdel(b)del(b)c) Six scenarios to activate a mutual-exclusion relationship between two actions a and b with interference.(pre(a) is assumed to be unsupported and overlapping with del(b): pre(a) ∩ del(b) = ∅)⎧⎪⎪⎪s(a) = s(b) if aa is “AT START” and db is “AT START”⎪⎪⎪⎪⎪⎪⎪⎨e(a) = s(b) if aa is “AT END” and db is “AT START”⎪⎪⎪s(a) = e(b) if aa is “AT START” and db is “AT END”⎪⎪⎪⎪⎪⎪⎪⎩e(a) = e(b) if aa is “AT END” and db is “AT END.”(4.4)Figure 4.2: Various scenarios in the activation of mutual-exclusion relationships between actions aand b.
A solid arrow shows the case when a precondition, an add effect, or a delete effect is effectiveat the beginning, the end, or the entire duration of an action. An active mutual exclusion is shownas a dashed arrow.89When actions a and b are mutual exclusive due to interference, that is, when an unsupported precondition effect pa of action a is also a delete effect db of action b, the mutual90exclusion between a and b is active in a plan when one of the following six conditions isof applying the actions in P according to their starting times to I. That is, f ∈ S for allsatisfied (Figure 4.2c):f ∈ G.⎧⎪⎪⎪s(a) ≥ s(b) if pa is “AT START” and db is “AT START”⎪⎪⎪⎪⎪⎪⎪⎪⎪e(a) ≥ s(b) if pa is “AT END” and db is “AT START”⎪⎪⎪⎪⎪⎪⎨e(a) ≥ s(b) if pa is “OVERALL” and db is “AT START”⎪⎪⎪s(a) ≥ e(b) if pa is “AT START” and db is “AT END”⎪⎪⎪⎪⎪⎪⎪⎪e(a) ≥ e(b) if pa is “AT END” and db is “AT END”⎪⎪⎪⎪⎪⎪⎪⎩e(a) ≥ e(b) if pa is “OVERALL” and db is “AT END.”Locality of Mutual-Exclusion Constraints in IPC4 BenchmarksIn this section, we evaluate the partitioning of mutual-exclusion constraints for IPC4 benchmarks.
Our analysis shows the strong locality of these constraints when they are partitioned(4.5)by problem subgoals as compared to partitioned by time. We do not study other partitioningcriteria in this paper because they may lead to subproblems whose initial states and subgoalsare not specified. Such subproblems will be hard to solve by existing planners because theymay require a systematic enumeration of their initial states and subgoals in finding feasibleplans.Note that in the last case, actions a and b do not have to overlap in their durations inFigure 4.3a shows the 93 mutual-exclusion constraints in a solution plan to the 4th in-order to activate the mutual exclusion.
However, in the first two cases, actions a and b muststance of the IPC4 Airport-Temporal domain. The instance involves moving three planesoverlap or be adjacent to each other in order to activate the mutual exclusion.in an airport to designated gates. Each rectangular box in the figure represents an action,Definition 4.5 A temporal plan P is conflict-free if there exists no pair of actions a and bwhereas a line joining two actions represents a mutual-exclusion constraint (that may bein P such that a and b have an active mutual-exclusion relationship.inactive). Figure 4.3b shows the partitioning of the actions into three subproblems, eachinvolving the movement of one plane.
We show local constraints (those that are relevant toThe example plan in Figure 4.1 is not conflict-free, as there exist pairs of active mutualactions in one subproblem) in solid lines and global constraints relating actions in differentexclusion actions. Actions a1 and a2 have active mutual exclusions due to competing needs;a3 and a4 have active mutual exclusions due to inconsistent effects; and a5 and a6 have activemutual exclusions due to interference. Other mutual exclusions (between a2 and a3 , betweena4 and a6 , and between a5 and a7 ) are not active because they do not satisfy the conditionssubproblems in dashed lines.
It is clear that a majority of the constraints (84%) are localafter partitioning them by subgoals.To demonstrate the localization of mutual-exclusion constraints after partitioning themby subgoals, we analyze all the IPC4 instances by a modified Metric-FF planner [37] thatin (4.3)-(4.5).supports the new features in PDDL2.2, such as temporal actions and derived predicates.
ForDefinition 4.6 A solution plan P to a temporal planning problem T = (O, F , I, G) is a planeach instance, we use the modified Metric-FF planner to find an initial subplan for each ofthat is conflict-free, and that all facts f ∈ G are true in the resulting state S = Result(I, P)the subgoals. We then find all the mutual exclusions among the actions, including active919211000011110011001100001100111100110011001100110011001100110011001100001111000011Subgoal 3110011000011110011000011a) 93 mutual-exclusion constraints among actions110011001100001100111100110000111100110011000011110011001100001111001100110000110.40.200 5 10 15 20 25 30 35 40 45 501100110011000011b) 14 global constraints after partitioning4thinstance of the IPC4 AIRPORT-TEMPORALvariant in the Airport domain.
Each rectangular box represents an action, whereas a line joiningtwo actions represents a mutual-exclusion constraint (that may be inactive). Most constraints (79out of 93 or 84%) are local constraints after partitioning them by subgoals. Global constraints areshown in dashed lines in (b).and inactive ones. Finally, we compute the number of global constraints relating actions indifferent subplans, as well as the number of initial active global constraints based on thesubplan evaluated for each subgoal.rg,Trg,Grga,G0.80.60.40.200 5 10 15 20 25 30 35 40 45 50Instance IDa) AIRPORT-TEMPORAL11000011 11000011110011001.01.00.8rg,Trg,Grga,G0.60.40.20Global-constraint fraction0.6Global-constraint fraction1100110011001100110000111100001111000011Figure 4.3: Mutual-exclusion constraints in the110000111100110011000011110011000011001100111100110011000011110000111100rg,Trg,Grga,G1.00.60.40.200 5 10 15 20 25 30 35 40 45 50rg,Trg,Grga,G0.80.60.40.20Instance ID0510 15 20 25 30 35 40Instance IDd) PSR-SMALLd) SATELLITE-TEMPORAL1.002468101214Instance IDb) PIPESWORLD-NONTANKAGE1.0rg,Trg,Grga,G0.8Instance IDc) OPTICAL-TELEGRAPHGlobal-constraint fraction00110011110011001100110011000011Subgoal 2110011000.8Global-constraint fraction1100001111001100110011001.0Global-constraint fraction110000110011110011000011Global-constraint fraction11000011001111000011001100110011110011001111111111100000000000110000000000000111111111110011000000000001111111111111 11000000000000011111111111001100000111001100000000000111111111110011000111001100110011Global-constraint fraction1100110011001100Subgoal 1 110000110011001100110011001100111111111111100000000000110000000000000111111111111100000000000001111111111100 1111000000000001111111111100001100011100110000000000011111111111110000011100111100001100110011110011001.0rg,Trg,Grga,G0.80.60.40.200 2 4 6 8 10 12 14 16 18 20Instance IDe) SETTLERrg,Trg,Grga,G0.80.60.40.200 5 10 15 20 25 30 35 40 45 50Instance IDf) UMTS-TEMPORALAs a comparison, we also evaluate the partitioning of the constraints of each instance byits temporal horizon, which we proposed in our previous work [83, 15].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
