Research Interests

My research
interests are in the interdisciplinary areas of artificial intelligence,
computer science, and operations research. My focus is artificial intelligence
as a discipline of designing intelligent computer systems for automatic reasoning,
decision making, planning, control, diagnosis, and learning, which is important
in application domains such as corporate decision making, factory production
control, project management, and intelligent human-computer interfaces. I am
especially interested in exploring representation frameworks for problem
formulation, mathematical foundations for proving formal properties, and
algorithms for efficient computation. Fundamental concepts and computational
machineries from probability theory, operations research, optimal control, and
theoretical computer science, have been utilized in my research for coping with
many challenging computational tasks required in designing modern intelligent
systems. The following is a brief outline of my research :

__Part I : Decision Making with Markov Decision Processes__

__Part II : Related Probabilistic Models and Research__

__Part III: Task Scheduling and Temporal Reasoning__

__Part IV: Parallel Computing__

**Part I :
Decision Making with Markov Decision Processes**

Recently Markov decision processes have been used as an important mathematical
and computational foundation for decision making under uncertainty. Markov
decision processes are probabilistic finite automata augmented with the
information of state-transition cost and performance criteria such as
minimizing the expected cumulative cost. Many decision-making problems can be
conveniently viewed as control problems over the underlying Markov decision
processes. See more details in {Lin Dissertation-97}, {Dean
and Lin IJCAI-95}, {Lin and Dean EWSP-95}. See professor Andrew Moore's web site about commercial systems built along this
direction.

**Decision Making under
Uncertainty
**Decision making under uncertainty is critical in application domains
such as transportation planning, factory production control, and robot
navigation. Using feature-based compact representation, the features of
application domains are represented as state variables. Decisions involve
preconditions, cost, and uncertainty in their consequences, all of which can be
compactly specified by probabilistic rules governing the state variables.
Decision making under uncertainty is often compactly represented as sequential
decision networks. The nodes in sequential decision network are
decision stages, each of which is associated many decision options. Links
between decision stages represent dependency among decision stages. Intelligent
decision-making systems must determine or approximate optimal decision-making
policies for the underlying Markov decision processes to attain optimal
performance. See an application in transportation planning and also
see more applications in industry and corporate management as described in my
dissertation {Lin Dissertation-97}.

Coping with

Decomposition Techniques

While many important decision-making problems can be conveniently viewed as control problems over the underlying Markov decision processes, standard dynamic-programming algorithms for computing optimal policies can not be naively applied for solving the problems. This is because these standard algorithms require explicit enumeration of the underlying state spaces. This is a great computational challenge for researchers since the sizes of the state spaces explode exponentially in the number of state variables.

In our research, we develop decomposition techniques to exploit structure for computational leverage. Given a problem instance, we first symbolically decompose the underlying dynamical system into subsystems. After analyzing the local dynamics within subsystems and the dependency across subsystems, we decompose the original planning problem into a sequence of subproblems governing the subsystems. Three approaches are investigated for decomposing large Markov decision process: namely hierarchical decomposition, iterative approximation, and strongly-connected component decomposition. These decomposition techniques shed light on how to exploit locality and dependency to cope with very large state spaces. See more details in {Lin Dissertation-97}, {Dean and Lin IJCAI-95}, {Lin and Dean EWSP-95}.

Abstraction and Dimensionality Reduction

Rather than explicitly constructing the entire system, often we can compactly construct each subsystem by abstracting away the state variables that are irrelevant to the subsystem and succinctly capture the interactions among subsystems. Abstraction can result in significant dimensionality reduction in computation in some application domains. Solutions of the decision-making subproblems can then be derived by applying standard algorithms for the corresponding control problems to these compactly constructed subsystems, while a solution to the original decision-making problem is derived by systematically compiling and propagating the solutions to the subproblems. See more details in {Lin Dissertation-97}, {Lin and Dean EWSP-95}.

Insight from Mathematical Programming

**Abstraction and Model
Minimization for Markov Decision Processes**:

**Continuing Work**

As well acknowledged, naively enumerating states explicitly is
infeasible since the sizes of the underlying state spaces grow exponentially in
the number of state variables involved. Abstraction or dimensionality reduction through symbolic aggregation of states continue to
be of great interest to researchers coping with the dimensionality curse.
Instead of naive enumeration, the goal is to symbolically construct equivalent
minimal models for very large Markov decision processes. See web sites of professor Tom Dean and professor
Craig Boutilier for other related papers
along this direction.

**Optimal Control with Weakly-coupled Markov Decision Processes**:

**Continuing Work**

As well acknowledged, there are important problem instances in transportation
planning, factory production control, and robot navigation. The underlying
weakly-coupled Markov decision processes exhibit structure for computation
leverage. Decomposition techniques for weakly-coupled Markov decision processes
continue to be an important topic for the researchers. See web sites of Ron Parr
and professor Tom Dean, for related papers and research.

**Part II : Related Probabilistic Models and Research**

**Learning
Optimal Control for Markov Decision Processes**:

How does an intelligent system learn on the fly to make decisions to attain
optimal performance in the long run even if not much is known in advance about
the transition probability and transition cost of the underlying Markov
decision processes? Could trial-and-error exploration lead to optimal
performance? Research on reinforcement learning provides mathematical
foundations and algorithms for the challenge. See the web sites of professor Leslie Kaebling for
a nice survey paper and links to related work.

**Coping with Partially Observable Markov Decision
Processes
**For partially observable Markov
decision processes, noisy sensors provide noisy state information. How does an
intelligent system make decisions to attain optimal performance? Could decision
making according to the best estimate of current state still lead to optimal
performance? If not, what should be the solution? Research on partially
observable Markov decision processes provides mathematical foundations and
algorithms for this challenge. See the web sites of professor Leslie Kaebling and
professor
Michael Littman for links to related
papers.

With noisy sensors providing noisy state information, hidden Markov models are partially observable Markov chains. Using Bayes rule and prior knowledge of the underlying transition probability, an intelligent system can predict the most likely state trajectory according to noisy sensor history. On the other hand, an intelligent system can also somewhat learn the transition probability through observation of sensor history using EM algorithm. Hidden Markov models are important tools in the recent research on statistical language learning. See applications in part-of-speech tagging and in training probabilistic context free grammars in professor Eugene Charniak's web site.

**Part III : Task
Scheduling and Temporal Reasoning**

Task scheduling and temporal reasoning is
important in project management. An engineering project is typically
represented as a task network, specifying how the project is divided into component
tasks and in what order these tasks could be executed. Tasks are also
associated with causal rules, specifying preconditions before tasks can be
executed and the consequences after tasks are finished.

For project-management purpose, an intelligent system for project management
must verify that tasks can be executed in any order consistent with the
task-network specification without resulting in an undesirable side effect. If
there does exist an execution order that can result in an undesirable side effect,
the system must report such a task sequence as an evidence of fault within the
task network. This is the essence of temporal reasoning problems considered in
our research. See {Lin and Dean IOS-94} {Lin and Dean TIME-94}, {Lin and Dean
CIJ-96} , {Lin Dissertation-97} for more details.

**Tradeoffs of Computational
Complexity**

Previous research has shown that it is NP-Complete to
determine the existence of a task sequence that results in a specified effect.
Our research further identifies three key factors that contribute to the
computational complexity, namely, ordering constraints on tasks, number of
variables involved, and the type of causal rules associated with tasks. We
establish complexity results regarding how these three factors contribute to the
computational complexity, develop polynomial-time algorithms when the key
factors are restricted, and show the underlying complexity tradeoffs
. {Lin and Dean IOS-94},

{Lin and Dean CIJ-96}.

**Exploiting Structure in
Hierarchical Task Networks
**For hierarchical task networks, we can systematically exploit
locality in execution order and causal dependency for computational leverage.
In a hierarchical task network, tasks are organized into hierarchical levels.
The only one task at the root level symbolically represents the entire project.
A task at one level can be further decomposed into subtasks at the next level,
with precedence constraints specifying how these subtasks should be executed at
the next level. Hierarchical task networks embed strong temporal locality in
task execution since the subtasks of a given task are executed as an atomic
group. Locality in causal dependency is also available when tasks at the same
level only interact with one another through a few common variables. This
allows us to develop a localized temporal reasoning algorithm to transform a
global temporal reasoning query into a series of local graph-reachability queries. See more details in {Lin and Dean
CIJ-96},{Lin Dissertation-97}.

My master thesis is on the design and analysis of a generic parallel simplex
algorithm on multi-computers with various interconnection topologies. We
investigate data mapping of large linear programs onto multi-computers, and
then identify various communication patterns embedded in different
interconnection topologies for implementing the simplex algorithm. The focus is
to analyze the bounds on the number of processing elements allowed in different
communication patterns in order to attain linear speedup. See {Chen, Ho, Lin, Sheu ICPP-88}, {Lin thesis-89}, and {Chen, Ho, Lin,
Sheu-90} for more details.