HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item:
Title: Problem solving in dynamic and real-time task domains
Authors: Afshar Mehrabi, Alireza
Issue Date: 1996
Abstract: 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.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1996
1, 63 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 1996 Afshar
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat

All items in this Repository are protected by copyright, with all rights reserved.