Decomposition of planning problems

Article type: Research Article

Authors: Sebastia, Laura | Onaindia, Eva | Marzal, Eliseo

Affiliations: Technical University of Valencia, Camino de Vera s/n, 46022, Valencia, Spain Tel.: +34 963877000; Fax: +34 963877359; E-mail: {lstarin,onaindia,emarzal}@dsic.upv.es

Note: [] Corresponding author.

Abstract: The ability to decompose a problem into manageable sub-components is a necessity in complex problem-solving tasks. In planning, the application of a divide-and-conquer methodology is known as planning decomposition. This technique consists of the following: decomposing a problem into smaller components (subproblems), solving these subproblems individually, and then combining the obtained solutions. The success of this technique is subject to the interactions that may appear between actions from solutions for different subproblems. In this paper, we present a novel technique, STeLLa, to overcome the inherent difficulties in planning decomposition. This technique partitions a planning problem in such a way that its subproblems can then be solved separately (either sequentially or concurrently) and their solutions can be easily combined. The key issue is that interactions among goals are used to come up with the problem decomposition rather than solving them once the problem is decomposed. This approach proves to be very beneficial with respect to other decomposition methods and state-of-the-art planners.

Keywords: Planning, problem decomposition

Journal: AI Communications, vol. 19, no. 1, pp. 49-81, 2006