Run-Time Monitoring of Fixed-Contract Interruptible Algorithms

Anytime algorithms give intelligent real-time systems the ability to trade deliberation time for quality of results. This capability is essential in domains where computing the optimal result is not computationally feasible or is not economically desirable. Examples of such domains include avionics, air traffic control, process control and mission-critical computations. Run-time monitoring of anytime algorithms defines a framework for reducing the effect of uncertainty on the performance of the system. In this paper, we discuss ongoing work aiming at extending the scope of anytime computing when performance profiles of basic components are not predictable at compile time. More precisely, we describe a two-levels model of run-time monitoring for resource-bounded problem-solving systems: at meta-level, original fixed-contracts are allocated to interruptible tasks according to some expectations on the environment behavior. At resource-level, contracts adjustments are dynamically performed by a scheduler according to the computational resources workload and the quality of the available approximate r sults, estimated at run-time. This work, supported by the French Ministry of Defense (DRET)1, has been conducted in collaboration with G. Champigneux and J. Sardou from Dassault-Aviation Company