In many dynamic application domains, the environment changes during problem solving. A problem solver, in these applications, does not have complete information about the task and resources, a priori. The problem solver is required to use up-to-date information that becomes available on line. It must use this information to avoid producing solutions that are obsolete by the time they are to be executed. Real-time applications, on the other hand, require a problem solver to produce an answer within a given deadline. Moreover, a real-time problem solver is expected to predict whether it can meet a deadline or not. If a task deadline is predicted to be missed, the problem solver has an option to avoid executing that task. Due to the changes over time, real-time problem solving in dynamic d...[ Read more ]

In many dynamic application domains, the environment changes during problem solving. A problem solver, in these applications, does not have complete information about the task and resources, a priori. The problem solver is required to use up-to-date information that becomes available on line. It must use this information to avoid producing solutions that are obsolete by the time they are to be executed. Real-time applications, on the other hand, require a problem solver to produce an answer within a given deadline. Moreover, a real-time problem solver is expected to predict whether it can meet a deadline or not. If a task deadline is predicted to be missed, the problem solver has an option to avoid executing that task. Due to the changes over time, real-time problem solving in dynamic domains is a difficult task. Minimizing tardiness and guaranteeing deadlines under varying degrees of dynamicity is difficult to model and guarantee. In this thesis, we propose a class of algorithms which perform real-time problem solving on line, in order to obtain new information about the availability of resources in the system. The proposed algorithms adjust themself automatically to adapt to the degree of dynamicity in the environment. We introduce a model of dynamicity in a graph representation of a task. We provide empirical analyses of our algorithms for a routing problem in the proposed dynamic model. Our results show that the proposed technique can minimize tardiness and that we can reasonably predict deadline compliance under varying degrees of dynamicity, in our proposed model.