Completeness and Optimality Preserving Reduction for Search

Speaker:	Dr. Yixin CHEN
		Computer Science and Engineering
		Washington University in St Louis

Title:		"Completeness and Optimality Preserving Reduction for
		 Search"

Date:		Monday, 11 May, 2009

Time:		4:00pm - 5:00pm

Venue:		Lecture Theatre F
		(Leung Yat Sing Lecture Theatre, near lifts 25/26)
		HKUST

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.