Machine Learning and Friends Lunch
Planning with action equivalences
Natalia Hernandez Gardiol
MIT
Abstract
The idea of using logical descriptions for planning problems has a long history in AI planning. The appeal lies in the ability of a logical expression to compactly describe problems that, when ground, may be very large. There is a large body of recent work on planners that take a logical description of a domain (often in a language similar to probabilistic STRIPS) and produce solutions that take advantage of the structure embedded in such a description.
However, the difficulty encountered by such techniques is that, in addition to a large ground state space, there is often an overwhelmingly large action space. Many researchers have observed that action instances often have similar kinds of effects: for example, in a blocks world it often does not matter which block is picked up first as long as a stack of blocks is produced in the end. If it were possible to identify under what conditions actions produce equivalent kinds of effects, the planning problem could be simplified by considering a representative action (from each equivalence class) rather than the whole action space. In this work, we propose a definition of the equivalence of action effects and attempt to describe the implications of such a definition on the soundness and completeness of the resulting planning approach. We describe this approach within the context of related work.