Robust scheduling in team-robotics

In most cooperating teams of robots each robot has about the same set of sensors. Distributed sensor fusion is a technique that enables a team to take advantage of this redundancy to get a more complete view of the world with a better quality of the provided information. This paper sketches a fusion algorithm for laser-scanner data and derives the requirements that the execution of this algorithm has on the underlying system infrastructure, especially CPU-scheduling. It shows that a scheduling algorithm is needed that fulfills timing guarantees without using worst case execution times (WCET). The time-aware fault-tolerant (TAFT) scheduler provides this feature: each execution entity is divided into a MainPart, with possibly unknown timing behavior, and in an ExceptionPart, with known execution time. The integrated scheduling of both parts is done by a combination of two earliest deadline scheduling strategies. One focuses on enhancing the CPU utilization and the other on guaranteeing the timely execution. The paper discusses the proposed scheduling strategy, briefly describes its implementation in a real-time OS and presents results that show the achieved real-time behavior with an increased acceptance rate, a higher throughput, and a graceful degradation in transient overload situations compared to standard schedulers.