Chen Disser (1121212), страница 16
Текст из файла (страница 16)
ThisW ((y, αmax , γ)) ≤ W ((y, α, γ)),(3.53)W ((y, α, γmax)) ≤ W ((y, α, γ)),(3.54)∗is true because the only different part between yi−1and yi∗ is y(i), and the connectivityrequirement for the discrete neighborhood Nd (y(i)) ensures that we can find a path fromy(i) to y ∗ (i).Based on (3.56) to (3.58), we have path from y to y∗ :which can be combined to get:W ((y, αmax , γmax )) ≤ W ((y, α, γ)),(3.55)y → y0,1 → y0,2 · · · → y0∗ → y1,1 → y1,2 · · · → y1∗∗∗∗· · · → yN−1 → yN,1 → yN,2 · · · → yN = y7980y ∗ (0)y(0)111000000111000111000111000111000111000111000111000111000111001100110011y(1)y(2)y(N)yy0∗y ∗ (0)y ∗ (0)y ∗ (0)y ∗ (1)y ∗ (1)y ∗ (1)y ∗ (2)y ∗ (2)11000011001100110011001100110011001111000011000111000111y1∗tree T (y∗ ) of y∗ with cost C(y∗ ), satisfying:W (y) − C(y∗ ) =r{[L(yk ) − L(yk−1 )]+ − [L(yk−1 ) − L(yk )]+ }k=1111000000111y ∗ (N)== L(y, αmax , γmax ) − L(y ∗ , αmax , γmax ) > 0,Figure 3.7: The construction of a path from y to y∗ .partitioned components y(0) to y(N) of y, the black circles show y ∗(0) to y ∗ (N) of y∗ , and[L(yk ) − L(yk−1 )] = L(yr ) − L(y0 )k=1∗yN= y∗Figure 3.7 illustrates the construction of a path from y to y ∗ .
The white circles show therbased on the definition of γ. Because W ((y ∗, αmax , γmax )) ≤ C((y, αmax , γmax ), we haveW ((y ∗, αmax , γmax )) ≤ C((y ∗ , αmax , γmax )) < W ((y, αmax , γmax )).c) Summarizing a) and b), we have that, for any y ∈ D − Yopt , y ∗ ∈ Yopt , α, and γ,the other circles are shaded because y(t) may change during the transition due to variablesharing.W ((y ∗, αmax , γmax )) ≤ W ((y, α, γ)).In the first step, we find a path from y to(3.59)Since the only different part between yis y(0), we only need to find a path from y(0) to y ∗ (0).
Such a path must exist due toTherefore, we conclude that virtual energy W (y) of y = (y, α, γ) is minimized at CGMdthe connectivity requirement for the discrete neighborhood Nd (y(0)). After we transit from(y ∗ , αmax , γmax ). Thus, the Markov chain converges to CGMd y ∗ ∈ Yopt with probability oney(0) to y ∗(0), the values of y(1), · · · , y(N) may also get changed to y (1), · · · , y (N) sinceaccording to Proposition 3.1.andy0∗y0∗ .they share some variables with y(0).In the second step, we find a path from y0∗ to y1∗ . Since y ∗(0) is already reached,the only different part betweeny0∗andy1∗3.4Summaryis y(1) and we only need to find a path fromIn this section, we have developed a theory of extended saddle points to characterize the∗y (1) to y (1).
Again, such a path must exist due to the connectivity requirement for thediscrete neighborhood Nd (y(1)). Therefore, we can continue this process until we reach∗= (y ∗(0), y ∗(1), · · · , y ∗(N)) = y∗ .yNAfter reversing the path from y to y∗ , we obtain a path from y to y∗ and also a spanningconstrained local minimum of NLPs under constraint partitioning, proposed a search framework to look for points that satisfy the condition, and proved convergence results. Basedon a penalty function, we have developed the necessary and sufficient ESPC conditions forconstrained local minimum of discrete, continuous, and mixed NLPs.
The conditions holdtrue over an extended region of penalty values that are larger than some thresholds.8182Next, we have extended the ESPC conditions and have applied it to solve NLPs underChapter 4constraint partitioning. After formulating the MINLP problem under constraint partitioningin a mathematical form, we have developed the concepts of neighborhood and constrainedApplications on Planninglocal minimum under constraint partitioning, and have derived a set of partitioned necessary conditions for resolving global constraints under constraint partitioning. The theoryfacilitates constraint partitioning by providing a set of necessary conditions, one for eachsubproblem, to characterize a constrained local minimum under constraint partitioning.Finally, we have presented an iterative search framework for finding points that satisfythe partitioned ESPC condition.
The framework searches in each subproblem by solving amodified problem with an objective function that is biased by global constraint violations,and performs ascents in the subspace of penalty values for violated global constraints. Wehave proved the asymptotic convergence of a partitioned search algorithm that performsstochastic descents and ascents using simulated annealing.A planning problem involves arranging actions and assigning resources in order to accomplishsome given tasks and objectives over a period of time. It can be defined by a state spacewith discrete, continuous, or mixed variables; a discrete or continuous time horizon; a setof actions defining valid state transitions; a set of effects associated with each action; a setof constraints to be satisfied in each state or throughout an action; and a set of goals to beachieved.In this chapter, we apply constraint partitioning to solve planning problems.
We studytwo planning models, including planning with the standard PDDL2.2 model and ASEPNplanning for NASA’s applications. For each planning application, we evaluate the constraintstructure and locality of the planning problems by measuring the ratio of global constraints,and by identifying a suitable dimension for partitioning the constraints.
We then developtwo planning systems that partition the constraints of large planning problems, solve eachsubproblem using a basic planner, and study new strategies for resolving global inconsistencies. Finally we present experimental results to show that our proposed approach canimprove significantly the solution time and quality over those of existing solvers.4.1Applications on PDDL2.2 PlanningIn this section, we first discuss the constraint locality property in PDDL2.2 planning. Wethen present a subgoal partitioning strategy and its implementation in SGPlang for solving8384temporal planning problems.
The subscript ”g” in SGPlang means that it partitions theactionactive mutual exclusionsconstraints of a planning problem by its subgoal facts. Our strategy partitions the mutual-pre(a1 )11111110000000a1000000011111110000000111111111111110000000exclusion constraints of a temporal planning problem by its subgoals into subproblems, solvesthe subproblems individually, and resolves iteratively violated global constraints across thepre(a5 )add(a4 )00000 111111111111110000000001111111111111100000000000000a4a500000000000000111111111100000 1111111110000000001111111110000000111111100000001111111a20000000111111100000001111111subproblems.
We evaluate various heuristics for resolving global constraints and demon-pre(a2 )1111111000000000000001111111a60000000111111100000001111111add(a2 )strate the performance of SGPlang in solving the benchmarks of the Third and the FourthInternational Planning Competitions.del(a6 )11111000000000011111a300000111110000011111000000111111000000111111a7000000111111111111000000del(a7 )del(a3 )4.1.1Locality of mutual-exclusion constraints in temporaltimeFigure 4.1: An example temporal plan.
Active mutual exclusions between actions are shown asdashed lines, whereas inactive mutual exclusions are shown as dotted lines.planninga) pre(o), a set of facts that define the preconditions of action o;In this section, we first define the mutual-exclusion constraints in a MINLP formulation ofplanning problems. Based on the structure of these constraints in IPC4 benchmarks, weshow that partitioning by subgoals leads to constraints that can be localized better thanb) add(o), a set of facts that define the add-effects of o;c) del(o), a set of facts that define the delete-effects of o; andpartitioning by time.d) s(o) and e(o), two quantities that define, respectively, the starting and the ending timesRepresentation of Mutual-Exclusion ConstraintsBy following standard notations and definitions in the literature [37], we introduce in thisof o.The resulting state of applying action o to state S is defined as:section the basic definitions and the constraints used in a constrained formulation of planning⎧⎪⎪⎨(Sproblems.Result(S, o) =Definition 4.1 A planning problem T = (O, F , I, G) is a quadruple, where O is the set ofadd(o))\del(o) if pre(o) ∈ S⎪⎪⎩S(4.1)if pre(o) ∈ S.possible actions in T , F is the set of all facts, I is the set of initial facts, and G is the set ofgoal facts.The resulting state of applying a sequence of actions to S is defined recursively as: Definition 4.2 A state S = f1 , · · · , fnS is a subset of facts in F that are true.Result(S, (o1 , · · · , on )) = Result(Result(S, (o1 , · · · , on−1 )), on ).Definition 4.3 A temporal action o ∈ O is associated with the following attributes:8586(4.2)Definition 4.4 A temporal plan Pm = {a1 , a2 , · · · , am } is a list of m temporal actions,where ai has been assigned starting time s(ai ) and ending time e(ai ).Figure 4.1 illustrates a temporal plan of seven actions.
In each action, we indicate, whereappropriate, its preconditions, add-effects, and delete-effects.Concurrent actions in a plan must be arranged in such a way that observes mutualexclusions. The notion of mutual exclusion (mutex) was first proposed in GraphPlan [11]. Itwas defined for a planning graph, which is a level-by-level constraint graph that alternatesbetween a fact level and an action level. The mutual-exclusion relations in a planning graphcan be classified into transient (level-dependent) and persistent (level-independent) [11]. Amutual exclusion is transient if it exists only in certain levels of the graph and vanishesas more levels of the graph are built.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
