Real-Time Scheduling via Reinforcement Learning

Cyber-physical systems, such as mobile robots, must respond adaptively to dynamic operating conditions. Effective operation of these systems requires that sensing and actu-ation tasks are performed in a timely manner. Additionally, execution of mission specific tasks such as imaging a room must be bal-anced against the need to perform more gen-eral tasks such as obstacle avoidance. This problem has been addressed by maintaining relative utilization of shared resources among tasks near a user-specified target level. Pro-ducing optimal scheduling strategies requires complete prior knowledge of task behavior, which is unlikely to be available in practice. Instead, suitable scheduling strategies must be learned online through interaction with the system. We consider the sample com-plexity of reinforcement learning in this do-main, and demonstrate that while the prob-lem state space is countably infinite, we may leverage the problem’s structure to guarantee efficient learning.