Strong planning under uncertainty in domains with numerous but identical elements (a generic approach)

Abstract: The typical AI problem is that of making a plan of the actions to be performed by a robot so that the robot could get into a set of final situations, if it started with a certain initial situation. The planning problem is known to be generally very complex. Even within the case of ‘well-balanced’ actions, strong planning under uncertainty about the effects of actions, or games such as ‘Robot against Nature’, is EXPTIME-complete. As a result, AI planners are very sensitive to the number of the variables involved in making a plan, the inherent symmetry of the problem, and the nature of the logical formalisms being used. This paper shows that linear logic provides a convenient and adequate tool for representing strong and weak planning problems in non-deterministic domains. A particular focus of this paper is on planning problems with an unbounded number of functionally identical objects. We show that for such problems linear logic is especially effective and leads to a dramatic contraction of the search space from exponential to polynomial in size. We employ the ability of linear logic to reason about multisets, which in this instance are created by identifying several distinct objects as being functionally equivalent for the problem at hand (think of a number of balls, each of which must be moved to some new location — the balls are distinct, but are functionally equivalent for the problem). In linear logic terms, we establish a clear syntactic condition that allows us to show that solving a generic planning problem where there is only one generic object, directly implies a solution to the original real planning problem over several real objects, the isomorphic copies of the generic object. Moreover, this correspondence also guarantees to produce a real solution that works in polynomial time. [Copyright &y& Elsevier]