``Briareus was a hundred-handed creature with fifty heads. During the battle against the Titans, Briareus took advantage of his one hundred hands by throwing rocks at the Titans.'' Whereas, the problems like ``take $N$ balls from one room to another by means of a robot with $k$ grips'', are typical combinatorially exploded examples for AIPS Planning Competitions.

Since 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 exponential (it is even EXPTIME-complete in the case of games `Robot against Nature'), the AI planners are very sensitive to the number of variables, the inherent symmetry of the problem, and the nature of the logic formalisms being used.

We have established a clear and easy-to-check syntactical criterion for detecting symmetry in planning domains, and developed techniques to break the extreme combinatorial explosion caused by the symmetry by reducing the unbounded number of `real' objects to a single `generic' object, 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 polytime solutions to the original problem.

From the technical point of view, we take advantage of linear logic formalism, where the fact that ``one copy of $b$ has property $P$, and another has property $Q$'' can be recorded as a formula of the form $(P(b)\otimes Q(b))$. Notice that the situation is generally more subtle and messy, in particular, $(P(b)\otimes Q(b))$ can be interpreted (and used!) as ``one and the same copy of $b$ has both properties $P$ and $Q$''.

In closing, I would speculatively explain that Briareus won because he took advantage of his `multiset' logic (fifty heads!), as well.

This is a joint paper with Jacqueline Vauzeilles (U. Paris-Nord).

For more information about the Penn Logic and Computation Seminar, please see the seminar web page.