Scheduling Classifiers for Real-Time Hazard Perception Considering Functional Uncertainty

Tarek F. Abdelzaher, Sanjoy Baruah, Iain John Bate, Alan Burns, Robert Ian Davis, Yigong Hu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper addresses the problem of real-time classification-based machine perception, exemplified by a mobile autonomous system that must continually check that a designated area ahead is free of hazards. Such hazards must be identified within a specified time. In practice, classifiers are imperfect; they exhibit functional uncertainty. In the majority of cases, a given classifier will correctly determine whether there is a hazard or the area ahead is clear. However, in other cases it may produce false positives, i.e. indicate hazard when the area is clear, or false negatives, i.e. indicate clear when there is in fact a hazard. The former are undesirable since they reduce quality of service, whereas the latter are a potential safety concern. A stringent constraint is therefore placed on the maximum permitted probability of false negatives. Since this requirement may not be achievable using a single classifier, one approach is to (logically) OR the outputs of multiple disparate classifiers together, setting the final output to hazard if any of the classifiers indicates hazard. This reduces the probability of false negatives; however, the trade-off is an inevitably increase in the probability of false positives and an increase in the overall execution time required.

In this paper, we provide optimal algorithms for the scheduling of classifiers that minimize the probability of false positives, while meeting both a latency constraint and a constraint on the maximum acceptable probability of false negatives. The classifiers may have arbitrary statistical dependences between their functional behaviors (probabilities of correct identification of hazards), as well as variability in their execution times, characterized by typical and worst-case values.
Original languageEnglish
Title of host publicationRTNS '23: Proceedings of the 31st International Conference on Real-Time Networks and Systems
Number of pages12
ISBN (Print)9781450399838
Publication statusPublished - 6 Jun 2023
Event31st International Conference on Real-Time Networks and Systems -
Duration: 6 Jun 20238 Jun 2023


Conference31st International Conference on Real-Time Networks and Systems
Abbreviated titleRTNS 2023

Bibliographical note

© 2023 Copyright held by the owner/author(s).


  • Real-Time
  • arbitrary dependences
  • DNN
  • Classifiers
  • Optimal Ordering

Cite this