BENJAMIN W. WAH
Department of Electrical and Computer Engineering
and the Coordinated Science Laboratory,
University of Illinois, Urbana-Champaign
Exploring Constraint Partitioning and Their Applications In Planning and Optimization
ABSTRACT:Constraint optimization exists in many engineering applications, including production planning, artificial intelligence, control systems, semiconductor manufacturing, and operations research. A key observation on the constraints of many of these application problems is that they are highly structured and involve variables with strong spatial or temporal locality. Based on this observation, large-scale application problems can be partitioned by their constraints into a small number of much simpler subproblems. Because each subproblem has only a fraction of the original constraints, it is a significant relaxation of the original problem and has a dramatically lower complexity. As a result, many problems that could not be solved before can now be solved easily. In this talk, we present the application of this approach in solving some planning problems in artificial intelligence and mathematical programming problems in nonlinear optimization. The planning problems studied have specifications that include soft goals and trajectory constraints for distinguishing high-quality plans among the many feasible plans in a solution space. Based on a partition-and-resolve strategy, we evaluate techniques for resolving violated global constraints, optimizing goal preferences, and achieving high-quality subgoals in a multi-valued representation. Empirical results on the 5th International Planning Competition (IPC5) benchmarks show that our approach is effective and significantly outperforms other competing planners. We further illustrate the approach in solving some large-scale application problems in spacecraft planning, and operations research.
BIO: Benjamin W. Wah is currently the Franklin W. Woeltge Endowed Professor of Electrical and Computer Engineering and a Professor of the Coordinated Science Laboratory of the University of Illinois, Urbana-Champaign. He received his Ph.D. degree in Computer Science from the University of California, Berkeley, CA, in 1979. Previously, he had served on the faculty of Purdue University (1979-85) and as a Program Director at the National Science Foundation (1988-89). In 1989, he was named a University Scholar of the University of Illinois; in 1998, he received the IEEE Computer Society Technical Achievement Award; in 2000, the IEEE Millennium Medal; in 2003, the Raymond T. Yeh Lifetime Achievement Award from the Society for Design and Process Science; in 2006, the IEEE Computer Society W. Wallace-McDowell Medal and the Pan Wen-Yuan Outstanding Research Award; and in 2007, the IEEE Computer Society Richard E. Merwin Medal and the IEEE-CS Technical Committee on Distributed Processing Outstanding Achievement Award. Professor Wah's current research interests are in the areas of nonlinear search and optimization, multimedia signal processing, and computer networks.
Back to Distinguished Lectures | Back to News & Events
