Ph.D Thesis

Ph.D StudentFinkelstein Lev
SubjectOffline Scheduling of Anytime Algorithms
DepartmentDepartment of Computer Science
Supervisors PROF. Shaul Markovitch
PROF. Ehud Rivlin


Many algorithms used for solving AI problems are anytime, i.e., the quality of their solution increases with time. Such problems are common in many areas such as learning, robot navigation, search, and constraint satisfaction. Some of these problems can be solved more efficiently by simultaneously applying several instances of algorithm-problem pairs (for example, by applying the same algorithm to different initial states or by applying different algorithms to the same initial state). If we were only interested in time speedup, the best strategy would have obviously been to let all the processes to work simultaneously. If, however, we are interested in reducing the resource cost as well, then the scheduling problem becomes more complex, and its solution depends on various parameters, such as the tradeoff between time and resource costs, constraints on resource usage, and the statistical behavior of the processes.

This thesis presents a methodology for designing an optimal scheduling policy based on the statistical characteristics of the algorithms involved. We formally analyze two major cases: the case where the processes share resources on a mutual exclusion basis, and the case of independent processes. We also analyze the related problem of monitoring a single anytime algorithm, while querying it periodically to determine if the given goal predicate has been satisfied. For each of the above setups, we provide algorithms for optimal scheduling, and evaluate them theoretically and empirically.  The empirical results show that the intuitive scheduling approaches often used for such problems are significantly outperformed by theoretically optimal schedules.