Benjamin W Wah - US grants

The goal of this research is to develop a multiprocessing system that automatically learns strategies for dynamic decision problems, both in hardware and software, such that the strategy learned is targeted for a multiprocessing system, and that the strategy is the best among those that can be found in the given time and resource constraints of the learning system and the knowledge provided by the users. The class of problems being explored is called dynamic decision problems. These problems may possess one or more of the following properties: the decisions necessary to solve the problem may be interrelated, the decisions are based on dynamic parameters which may be uncertain, the number of possible strategies is very large, and the effects of a decision may not be immediately available after the decision is made. A dynamic decision problem is solved by a combination of domain knowledge and meta-knowledge. Domain knowledge consists of the definition of the problem and its parameters, its representation, and possibly an algorithm (or class of algorithms) to solve it. Meta-level knowledge is knowledge about selecting alternatives to implement in the algorithm and its representation, or finding new ways of solving the given problem. Domain knowledge can be implemented in the form of a program in a computer, for instance, while meta-knowledge is provided by the designers. This research focuses on the development of methods so that some of the meta-knowledge supplied by the designers can be obtained by automatic learning methods. Initially, the focus is on dynamic decision problems for which there are some known solutions, and on learning strategies to solve these problems. The dynamic decision problems addressed include combinatorial search problems and real-time decision problems. The distinguishing features of this research are as follows: First, architectural constraints are being included so that the learning system will find the best strategy given a fixed amount of time and resources, and the computer on which the learning system is implemented. Second, the strategy learned by the learning system also includes consideration of the computer on which it will be implemented. The objectives of this research are to develop methods for automatic learning and to study multiprocessor architectures suitable for learning systems. This area of research is very important and timely. The investigator is well qualified to direct this research. Support is highly recommended.

Wah This conference, sponsored by the EUROMICRO Association, the IEEE Computer Society, IFIP, AEI, and AICA, focuses on parallel computing, system design methodologies, technology and implementation within the context of application specific computing. Application specific computing is directly related to high performance computing and is a major component in this program. This conference will take place in conjunction with the IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems. This grant supports travel by selected graduate students to permit them to attend the conference.

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.