HONG KONG BAPTIST UNIVERSITY
FACULTY OF SCIENCE

Department of Computer Science Colloquium
2009 Series

Completeness and Optimality Preserving Reduction for Search

Dr. Yixin Chen
Washington University

Date: May 12, 2009 (Tuesday)
Time: 4:00 - 5:00 pm
Venue: SCT909, Cha Chi Ming Science Tower, Ho Sin Hang Campus

Abstract
Search is a pervasive approach for artificial intelligence. A central problem in search is its scalability to very large state spaces. As shown by recent work, searches even with almost perfect heuristic guidance have some fundamental limitations. In this talk, we propose an orthogonal way to reduce the search cost by recognizing problem structure and reduce the space. The reduction algorithms expand only a subset of applicable actions at each state. By exploiting semi-commutativeness among actions, the reduction algorithms preserve the completeness and optimality of the original search algorithm. Experimental results show that the reduction algorithms can give orders of magnitude of reduction in search space and computing time without sacrificing solution quality, especially for difficult domains where accurate heuristic functions are difficult to obtain.

Biography
Yixin Chen is an Assistant Professor of Computer Science at the Washington University in St Louis. His research interests include planning and scheduling, computational optimization, data mining, and machine learning. His work on planning has won First Prizes in optimal and satisficing tracks in the International Planning Competitions (2004 & 2006) and the Best Paper Award at the International Conference on Tools for AI (2005). He has received an Early Career Principal Investigator Award from the Department of Energy (2006) and a Microsoft Research New Faculty Fellowship (2007). He serves on the Editorial Board of Journal of Artificial Intelligence Research and IEEE Transactions on Knowledge and Data Engineering. He received a Ph.D. in Computing Science from University of Illinois at Urbana-Champaign in 2005.

********* ALL INTERESTED ARE WELCOME ***********
(For enquiry, please contact Computer Science Department at 3411 2385)

http://www.comp.hkbu.edu.hk/v1/?page=seminars&id=99
Photos