Research Areas
Artificial Intelligence, Machine Learning, Computational Learning Theory, Applications to Computer Integrated Manufacturing, Information Retrieval, Scheduling, and Game Playing.

Research Description
The ability to learn is fundamental to intelligence. My main research interest is in developing computer programs that learn by interacting with their environments and improving their performance with time. Our work ranges from theoretical analyses of learning problems and design of algorithms to implementation and experimental evaluation of algorithms and their application to real-world problems.

Computational learning theory provides a rich set of models to formulate and classify learning problems into easy and hard problems. We extensively use this theory in our work to design new algorithms and prove their correctness and to show that some learning problems are likely to be too hard to solve within reasonable computational resources. For example, my former Ph.D. student Chandra Reddy and I were able to show that the class of non-recursive single-predicate Horn programs is learnable from examples and membership queries. With another former Ph.D. student, Thomas Amoth, and Prof. Paul Cull, I showed that the language of unordered tree patterns, a natural class of semi-structured objects like the Web pages, is not learnable in that manner.

We are investigating algorithms for "Average-reward Reinforcement Learning," where an agent receives rewards and punishments from the environment and changes its behavior over time to maximize the average reward received per time step. In our previous work, we designed a model-based learning method called "H-Learning" and showed that it outperforms all other algorithms in optimally scheduling a simulated Autonomous Guided Vehicle (AGV) in a simple setting. We are currently exploring different ways of scaling these results to large real-world problems such as multiple AGV scheduling, and vehicle routing for product delivery in the distribution industry.

Relational Reinforcement Learning (RRL) generalizes Reinforcement Learning to domains which are naturally represented by relational structures. We are studying applications of RRL to information extraction and integration on the Web. Since the content of the Web is mostly
in semi-structured and natural language forms, we are exploring ways to learn relational transformational rules that automatically extract relevant information from the Web and translate it into more formal notation. Similarly the user queries may be translated into more formal notation, optimized, and processed using rules learned via RRL.

Applications of Research
There are many applications to our research. For example, a program that we developed to analyze medical databases and extract simple diagnostic decision rules is being used by physicians. Our research in performance improvement learning is aimed at applications to real-time control tasks such as AGV scheduling and air traffic control. Our work on personal learning apprentice systems is likely to be useful in information retrieval and in building automatic knowledge acquisition tools for expert systems.