Linear logic as a tool for planning under temporal uncertainty

摘要

The typical AI problem is that of making a plan of the actions to be performed by a controller so that it could get into a set of final situations, if it started with a certain initial situation. The plans, and related winning strategies, happen to be finite in the case of a finite number of states and a finite number of instant actions. The situation becomes much more complex when we deal with planning under temporal uncertainty caused by actions with delayed effects. Here we introduce a tree-based formalism to express plans, or winning strategies, in finite state systems in which actions may have quantitatively delayed effects. Since the delays are non-deterministic and continuous, we need an infinite branching to display all possible delays. Nevertheless, under reasonable assumptions, we show that infinite winning strategies which may arise in this context can be captured by finite plans. The above planning problem is specified in logical terms within a Horn fragment of affine logic. Among other things, the advantage of linear logic approach is that we can easily capture 'preemptive/anticipative' plans (in which a new action β may be taken at some moment within the running time of an action α being carried out, in order to be prepared before completion of action α). In this paper we propose a comprehensive and adequate logical model of strong planning under temporal uncertainty which addresses infinity concerns. In particular, we establish a direct correspondence between linear logic proofs and plans, or winning strategies, for the actions with quantitative delayed effects.