Meta-Level Control of Anytime Algorithms with Online Performance Prediction

Meta-Level Control of Anytime Algorithms with Online Performance Prediction

Justin Svegliato, Kyle Hollins Wray, Shlomo Zilberstein

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1499-1505. https://doi.org/10.24963/ijcai.2018/208

Anytime algorithms enable intelligent systems to trade computation time with solution quality. To exploit this crucial ability in real-time decision-making, the system must decide when to interrupt the anytime algorithm and act on the current solution. Existing meta-level control techniques, however, address this problem by relying on significant offline work that diminishes their practical utility and accuracy. We formally introduce an online performance prediction framework that enables meta-level control to adapt to each instance of a problem without any preprocessing. Using this framework, we then present a meta-level control technique and two stopping conditions. Finally, we show that our approach outperforms existing techniques that require substantial offline work. The result is efficient nonmyopic meta-level control that reduces the overhead and increases the benefits of using anytime algorithms in intelligent systems.
Keywords:
Heuristic Search and Game Playing: Meta-Reasoning and Meta-heuristics
Planning and Scheduling: Real-time Planning