| Résumé | In many AI applications, such as medical diagnostic systems and motion
planning under kinetic constraints, the available computation time is
uncertain. Interruptible algorithms are extremely useful in precisely
such environments: these algorithms have the property that they can be
interrupted at any point during their execution, at which point they must
be able to report some satisfactory solution. On the other hand, a contract
algorithm is an algorithm whose computation time is provided as part of its
input. Such algorithms may very well fail to return any meaningful solution,
if interrupted prior to their allotted execution time.
In this talk I will discuss black-box techniques for generating interruptible
versions of contract algorithms in a variety of settings. Our techniques
involve scheduling multiple executions of contract algorithms in identical
parallel processors, and in many cases optimal schedules can be obtained.
The presentation will survey some of the recent results and the future
challenges in related areas.
|