Strong Planning under Uncertainty in Domains with Numerous but Identical Elements (a generic approach)

The typical AI problem of making a plan of the actions to be performed by a robot so that it could get into a set of final situations, if it started with a certain initial situation, is generally very complex. Even within the case of ‘well-balanced' actions, strong planning under uncertainty about the effects of actions, or games ‘Robot against Nature', is EXPTIME-complete. As a result, the AI planners are very sensitive to the number of the variables involved, the inherent symmetry of the problem, and the nature of the logic formalisms being used. The paper shows that linear logic provides a convenient and adequate tool for representing strong and weak planning problems in nondeterministic domains. A particular interest of our paper is focused 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 dramatic contraction of the search space (polynomial instead of exponential). The paper addresses the key issue: “How to automatically recognize functions similarity among objects and break the extreme combinatorial explosion caused by the large number of objects that happen to be identical” by means of replacing the unbounded number of specific names of objects with one generic name and contracting thereby the exponential search space over ‘real' objects to a small polynomial search space but over the ‘generic' one, with providing a more abstract formulation whose solutions are proved to be directly translatable into (optimal) polytime solutions to the original planning problem