Tradeoffs in the Design of On-Line Systems

Contents

We present a general framework for analyzing tradeoffs when designing systems in which an agent with limited computational resources is required to respond in a timely manner to situations arising in a dynamic environment. These tradeoffs are characterized in terms of architectural constraints that limit the computational alternatives available to the agent. We apply the framework to a design problem in which the designer is given a set of controllers, each of which is capable of responding to a subset of situations, and a model of the run-time dynamics that can be used to predict the sets of situations that might arise over time. Exactly one controller is active at any moment, and a fixed time delay is required to activate a controller. Additional architectural constraints limit the number of controllers that are capable of being activated. The objective is to design (off-line) a strategy for activating and deactivating controllers that guarantees that there will be an active controller capable of responding no matter what situation arises. We provide an asymptotic analysis for this design problem, describe exact and approximate algorithms for the off-line design, and sketch how the framework can be applied to real-time avionics scheduling. We argue that the architectural constraints of this design problem model a rich class of planning and control systems.