Loosely Coupled Formulations for Automated Planning: An Integer
  Programming Perspective
  We represent planning as a set of loosely coupled network flow problems,
where each network corresponds to one of the state variables in the planning
domain. The network nodes correspond to the state variable values and the
network arcs correspond to the value transitions. The planning problem is to
find a path (a sequence of actions) in each network such that, when merged,
they constitute a feasible plan. In this paper we present a number of integer
programming formulations that model these loosely coupled networks with varying
degrees of flexibility. Since merging may introduce exponentially many ordering
constraints we implement a so-called branch-and-cut algorithm, in which these
constraints are dynamically generated and added to the formulation when needed.
Our results are very promising, they improve upon previous planning as integer
programming approaches and lay the foundation for integer programming
approaches for cost optimal planning.
