Abstract:
Anytime algorithms are algorithms whose quality of results improves gradually as computation time increases. They have attracted growing attention in recent years as a key mechanism for time-critical planning and control of autonomous robots. By introducing computation time as a degree of freedom, anytime algorithms define a scheduling problem involving the activation and interruption of the anytime components. We have implemented a prototype of AT-RALPH in which an off-line compilation process together with a run-time monitoring component guarantee the optimal allocation of time to the anytime modules. The crucial metalevel knowledge is kept in the anytime library in the form of conditional performance profiles. These profiles characterize the performance of each elementary anytime algorithm as a function of runtime and input quality. We have also extended the notion of gradual improvement to sensing and plan execution. While control of sensing is very similar to control of anytime computation, the timing of plan execution can be controlled by varying the resources (such as energy) consumed by the robot. The result is an efficient, flexible control for autonomous robots that optimally exploits the tradeoff between time and quality in planning, sensing and plan execution.