Anytime Problem Solving Using Dynamic Programming

Mark Boddy

In previous work, we have advocated explicitly scheduling computation time for planning and problem solving (deliberetion) using a framework called ezpectation-driven iterative refinement. Within this framework, we have explored the problem of allocating deliberation time when the procedures used for deliberation implement anytime algorithms: algorithms that return some answer for any allocation of time. In our search for useful techniques for constructing anytime algorithms, we have discovered that dynemic programming shows considerable promise for the construction of anytime algorithms for a wide variety of problems. In this paper, we show how dynamic programming techniques can be used to construct useful anytime procedures for two problems: multiplying sequences of matrices, and the Travelling Salesman Problem. Dynamic programming can be applied to a wide variety of optimization and control problems, many of them relevant to current AI research (e.g., scheduling, probabilistic reasoning, and controlling machinery). Being able to solve these kinds of problems using anytime procedures increases the range of problems to which expectation-driven iterative refinement can be applied.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.