Artificial Intelligence How to progress a database *

One way to think about a STRIPS operator is as a mapping from databases to databases, in the following sense: suppose we want to know what the world would be like if an action, represented by the STRIPS operator (Y, were done in some world, represented by the STRIPS database Do. To find out, simply perform the operator (Y on DO (by applying (Y’S elementary add and delete revision operators to DO). We describe this process as progressing the database 230 in response to the action (Y. In this paper, we consider the general problem of progressing an initial database in response to a given sequence of actions. We appeal to the situation calculus and an axiomatization of actions which addresses the frame problem (Reiter ( 1991). This setting is considerably more general than STRIPS. Our results concerning progression are mixed. The (surprising) bad news is that, in general, to characterize a progressed atabase we must appeal to second-order logic. The good news is that there are many useful special cases for which we can compute the progressed database in first-order logic; not only that, we can do so efficiently. Finally, we relate these results about progression to STRIPS-like systems by providing a se