This research will develop formal mathematical conditions for reducing the search space of planning problems, and will demonstrate performance improvements in search engines of planners and other discrete searches. Based on the observation that temporal planning problems can be arranged into stages by time, they can be formulated as dynamic optimization problems with dynamic variables that evolve over time. Due to the presence of general constraints that span across multiple stages, path dominance in dynamic programming cannot be applied to reduce the search complexity. This research will seek new node-dominance conditions in each stage by developing the necessary or necessary-and-sufficient conditions for local optimality and by partitioning the conditions into distributed necessary conditions, based on local constraints in each stage and constraints between adjacent stages. By partitioning the search into stages and by finding only dominating states in each stage using the necessary conditions, the search for feasible or optimal plans can be restricted to a much smaller subspace in each stage, leading to a smaller number of combinations of possible paths that need to be searched across multiple stages.
Three research tasks will be completed in this work. Based on the discrete-space variational search implementing the stopping conditions, research will develop a new planning system that fully supports PDDL2.1 language features, using the constraint-based-interval representation. Temporal flexible scheduling will be extended by formulating a temporal constraint network with flexible time points into a constrained nonlinear optimization problem and by partitioning the search space. Research will study algorithms for partitioning satisfiability (SAT), mixed-integer optimization, and planning problems.
The research is on a new approach that reduces the computational complexity by exploiting the locality of constraints in multi-stage optimization problems. By developing node dominance conditions that identify dominating nodes in each stage, it will lead to reduced search space in each stage and a significant reduction in base of the exponential number of possible paths to be searched across multiple stages. Although a similar approach has been studied in calculus of variations in continuous space, the extension to discrete problems requires the development of a completely new foundation in the theory of Lagrange multipliers in discrete space. The approach developed is general and can be used as stopping conditions in existing planners or integrated into new search algorithms. It can also benefit the solution of other discrete optimization problems, including SAT and mixed-integer optimization.
In addition to training graduate and undergraduate students in their research, the project develops a fundamental approach that will be incorporated into courses on optimization. The results will also carry significant impact on autonomous vehicle planning and will be applied to planners currently developed at the National Aeronautics and Space Administration and Jet Propulsion Laboratory. Improved planners will allow higher dependability of space missions that will benefit society at large.
