Please use this identifier to cite or link to this item:

Problem solving in dynamic and real-time task domains

Authors Afshar Mehrabi, Alireza
Issue Date 1996
Summary 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.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1996
Language English
Format Thesis
Access View full-text via DOI
Files in this item:
File Description Size Format
th_redirect.html 345 B HTML
Copyrighted to the author. Reproduction is prohibited without the author’s prior written consent.