Efficiency Analysis in Search Problems.
Thesis Proposal.
Yury Smirnov.
Dept. of Computer Science.
Carnegie Mellon University.

			Abstract

By now Artificial Intelligence (AI), Theoretical Computer Science (CS theory)
and Operations Research (OR) have investigated a variety of search  problems. 
However,  methods  from  these  scientific  areas   use   different   problem 
descriptions, models, and tools. They also address problems  with  particular 
efficiency requirements. For example, theoretical  approaches are mainly 
concerned with the worst-case complexity and are  not  focused  on  empirical 
performance. A few efforts have tried to apply methods across areas.  Usually 
a significant amount of work is required to make different approaches  ``talk 
the same language,'' be successfully implemented,  and,  finally,  solve  the  
actual  same  problem  with  an overall acceptable efficiency.
 
The expected contribution of this thesis is to advance the state of  the  art
in the transfer of knowledge across the above mentioned areas. We propose  to 
investigate a number of problems that belong to or are close to the 
intersection of AI's, OR's and CS  theory's  areas  of  interest.  The  thesis
will demonstrate how the representation of each specific group of problems can 
be changed to obtain a single universal formulation  amenable  to  approaches  
from  the  considered scientific areas. 
 
The methodology that we will follow consists of, first, the analysis  of each 
group of problems along different directions to identify efficient methods of 
solving these problems. Second, we combine the most beneficial features found 
during  the  analysis  phase  utilizing   the   advantage   of   the   common 
representation developed.
 
Based on our work and results produced  so  far,  concretely  we  propose  to
address the following kinds of search  problems:  goal-directed  exploration,
in which search with limited look-ahead occurs  in  partially  or  completely
unknown domains; path optimization  in domains  with  dynamic  effects, where 
the agent's actions can affect directly the search for an optimal or efficient 
tour;  and combinatorial  optimization  problems,  focused  on  a comparative 
performance  analysis of  the  Pigeonhole Principle  and  Integer Programming 
approaches.

Thesis Committee:	Manuela Veloso (Chair)
			Jaime Carbonell
			Avrim Blum
			Bart Selman (AT&T Labs)