Reference: Breese, J. S. & Horvitz, E. J. Principles of Problem Reformulation Under Uncertainty. KSL, September, 1990.
Abstract: The intelligent reformulation of a problem can greatly increase the efficiency with which that problem can be solved. However, time expended for reformulation is not available for the primary execution of the solution. Thus, under time pressure, there exists a tradeoff between the time dedicated to reformulation and the time applied to the implementation of a solution. We explore the ideal partition of resources into time dedicated to reformulation and time applied for executing the reformulated solution. We focus on the problem of determining the ideal time for dwelling on reformulation preprocessing, under conditions of uncertain knowledge about the relationship between reformulation and execution efficiency. After defining the metareasoning-partition problem under uncertainty, we identify efficient, general principles for controlling reformulation through analysis of several prototypical classes of uncertainty and utility.