Chen Disser (1121212), страница 9
Текст из файла (страница 9)
These minimizations on the subproblemscan be done efficiently when the functions in the subproblems are convex or linear, whichlead to efficient computation of the overall dual function.Separable programming has similar advantages as our constraint partitioning in that itdecomposes a large problem into multiple much simpler subproblems so that the total timeto solve all subproblems is usually much less than the time to solve the original problem.However, There are several limitations of separable programming. First, it requires theobjective and constraint functions to have a separable structure shown in (2.30). Second,separable programming methods have restricted assumptions, such as linearity or convexityof the functions, that limit their general applications.
An example is the Danzig-Wolfedecomposition [18] that works for problems with separable objective functions and linearconstraints. Third, this method is only necessary but not sufficient in the sense that itdoes not guarantee finding the solution due to the duality gap. That is, the solution of thedual problem may not be a solution to the original problem, and there is a gap betweenRemarks on existing partitioning methodsPartitioning has been used in many existing methods for solving NLPs.
Partitioning methods can be classified as subspace partitioning methods and constraint partitioning methods.Subspace partitioning decomposes a problem by partitioning its variable space into subspaces and by evaluating the subspaces individually. The total complexity of enumeratingall subspaces is very similar to that of searching the original space. Most existing MINLPmethods, including GBD, OA, branch and bound, branch and reduce, GCD, and ECP aresubspace partitioning methods.In contrast, the constraint partitioning approach decomposes the constraints of a probleminto subproblems.
Each subproblem is typically much more relaxed than the original andrequires significantly less time to solve. Therefore, the total time to solve all subproblems issignificantly reduced. Separable programming is a constraint partitioning method that worksfor linear and convex NLPs with a separable structure. In this thesis, we study a generalconstraint partitioning approach that works for general NLPs without special assumptionson functions and structure.2.3Existing Planning Algorithmsthe maximum value of the dual function and the minimum value of the original objectivefunction. In general, there is no duality gap for convex problems and linear problems, andPlanning is the problem of generating a course of actions to finish a give task, subject tothere is a non-zero duality gap for general nonlinear problems [10].propositional, temporal, and numerical constraints.
A planning problem involves a timeIn this research, we study general constrained optimization with no restricted assumptionshorizon for actions to take place and a state space to represent the internal configurations.on the constraint functions. Instead of using duality, we build our theoretical foundation onFigure 2.3 classifies existing planning and scheduling methods based on their state anda penalty formulation discussed in the next section. We show that our condition is necessarytemporal representations and the search techniques used.3738AI planning and scheduling methodsSTAN and HSP; GRT [71] (and its extension to MO-GRT [72]), a two-phase planner thatContinuous TimeDiscrete Timefirst estimates the distances between domain facts and goals, before searching by a simpleMixed StateMixed StateDiscrete Statebest-first strategy; and ASPEN [16], a repair-based local-search method that can handleSystematicSearchHeuristicSearchGraphplanSTANPropPLANUCPOPSystemRHSPFFAltAltGRTLocalSearchASPENTransformationMethodsSystematicSearchSATPLANILP−PLANBlackboxSPIE−2O−Plan2HeuristicSearchMetric−FFGRT−RGRT−MOTransformationMethodsLPSATSystematicSearchSHOP2TALPlannerZENOHeuristicSearchMIPSSapaEuropaLocalSearchdiscrete temporal and metric constraints and that optimizes multiple objectives in the formLPGof a weighted sum.Figure 2.3: A classification of existing planning and scheduling approaches.Last, transformation methods convert a problem into a constrained optimization or satisfaction problem, before solving it by an existing solver based on subspace partitioning.Examples in this class include SATPLAN [46] Blackbox [47], and ILP-PLAN [48].2.3.1Discrete-time discrete-state methodsDiscrete-time discrete-state methods consist of systematic searches, heuristic searches, local2.3.2Discrete-time mixed-state methodssearches, and transformation methods.
Systematic searches that explore the entire stateDiscrete-time mixed-state methods consist of systematic searches, heuristic searches, andspace are complete solvers. After decomposing a search space into subspaces, they evaluatetransformation methods. Similar to discrete-time discrete-state methods, methods in thiseach as a complete planning problem. Examples include UCPOP [64], an early goal-directedclass generally use subspace partitioning in their solution process. SIPE-2 [94] and O-planner based on the Partial Order Causal Link (POCL) technique; Graphplan [11], thatPlan2 [80] are early Hierarchical Task Network (HTN) planners. The HTN planners suffersearches a planning graph in order to minimize the length of a parallel plan; STAN [57], anthe deficiencies of domain dependency, difficulty in engineering, and brittleness in handlingefficient implementation of Graphplan; PropPLAN [25], a planner based on a naive breadth-unexpected states. Metric-FF [37] employs heuristic searches similar to those in FF, using afirst search of ordered binary decision diagrams; and System R [56], a method based onmodified heuristic function to accommodate numeric constraints and to favor the optimiza-regression that solves one goal at a time.tion of a given cost function.
GRT-R [71] is an extension of GRT for solving problems whoseHeuristic solvers explore a partitioned subspace represented as a complete planning prob-resources are represented numerically. Last, LPSAT [96] uses the LCNF representation bylem. Within a subproblem, local searches employ guidance heuristics evaluated over the en-combining propositional logic and linear equalities and inequalities, and searches by a SATtire temporal horizon in estimating the distance from a state to the goal state. They are notsolver which calls an LP system.guaranteed to find feasible plans because their success depends on the guidance heuristicsused.
Examples include HSP [12], a hill-climbing search using heuristic values obtained by2.3.3Continuous-time mixed-state methodssolving a relaxed problem; FF [37], an enforced hill-climbing search using heuristic valuesContinuous-time mixed-state methods can be classified into systematic, heuristic, and localobtained by solving a relaxed Graphplan problem; AltAlt [62], a hybrid planner on top ofsearches. Again, they rely on subspace partitioning in their solution process. Examples in-3940clude LPG [30], a local search guided by a function weighted by discrete penalties on an actiongraph and a temporal precedence graph; MIPS [21], an A∗ -search planner that employs staticanalysis, numeric estimation, plan relaxation, and critical path analysis to derive heuristicfunctions with embedded optimization measures; Sapa [79], a heuristic-search planner thatemploys distance-based heuristics to control its search and that adjusts its heuristics to ac-Variablepartitioningordered byheuristicfunctionscount for resource constraints and optimization objectives; ZENO [65], a systematic POCLplanner with goal-directed planning that can handle continuous time and metric quantities;Variables:a11111111111111111111111111100000000000000000000000000000000000000000000000000001111111111111111111111111100000000000000000000000000111111111111111111111111110000000000000000000000000011111111111111111111111111000000000000000000000000001111111111111111111111111100000000000000000000000000111111111111111111111111110000000000000000000000000011111111111111111111111111000000000000000000000001111111111111111111111100000000000000000000000111111111111111111111110000000000000000000000011111111111111111111111000000000000000000000001111111111111111111111100000000000000000000000111111111111111111111110000000000000000000000011111111111111111111111a2a3SHOP2 [60], an HTN planner that searches by problem reduction using a domain-specificFigure 2.4: Subspace partitioning in planning by branching on variable assignments.knowledge base of methods; TALplanner [19], a logic-based forward-chaining planner us-methods partition recursively a search space by branching on the assignment of variablesing domain-dependent search-control knowledge represented as formulas in Temporal Action(selection of actions).
Their difference is that a complete search enumerates systematicallyLogic (TAL); and Europa [44], a general framework that uses a constraint-based intervalall subspaces, whereas a heuristic search orders and prioritizes subspaces based on heuristic(CBI) representation for representing plan constraint network and in its heuristic search.functions. In contrast, in indirect partitioning, a planning problem is first transformed intoa satisfiability or an optimization problem, before the transformed problem is partitioned by2.3.4Remarks on existing planning methodsits search space into subproblems.From the perspective of partitioning, most general and popular methods for solving largeIn this thesis, we propose an orthogonal constraint-partitioning approach that decomposesplanning problems, such as systematic search, heuristic search, and transformation methods,the constraints of a planning problem into subproblems, each with local constraints and iscan be viewed as an approach that partitions recursively a search space into independentrelated to other subproblems by global constraints.
Our approach is based on the strongsubproblems by branching on the values of its variables, and that solves each subproblem in-locality of constraints observed in many planning applications. We present in Chapter 4dividually until a feasible solution is found. Since the approach results in subproblems whoseour partition-and-resolve planning strategy that iterates between solving the subproblemsaggregate complexity is the same as that of the original problem, it is often combined withusing a basic planner, while considering the local constraints and an objective biased byintelligent backtracking that employs variable/value ordering to order the subproblems gen-the global-constraint violations, and using a constraint-reweighting strategy that resolveserated, that pre-filters partial inconsistent assignments to eliminate infeasible subproblems,violated global constraints across the subproblemsand that prunes subproblems using bounds computed by relaxation or approximation.In summary, existing planners solve a problem as a whole without partitioning, or applySubspace partitioning can be applied directly or indirectly for solving planning problems.subspace partitioning to decompose a problem into subproblems, or transform a problem intoDirect methods include complete and heuristic searches.
As illustrated in Figure 2.4, theseanother form before solving it by existing methods based on subspace partitioning. In this4142thesis, we propose to augment existing approaches by constraint partitioning and decomposeChapter 3the constraints of a large problem into subproblems of a similar form before solving themby existing planners. Instead of developing a new planner to solve the small subproblems,Theory of Extended Saddle Pointsusing an existing planner is more effective because it saves a lot of development efforts. Wedevelop in Chapter 4 our approach on planning problems.In this chapter, we propose a complete theory to characterize the constrained local optimalsolutions of NLPs in discrete, continuous, and mixed spaces.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
