BW planning, in the sense of finding some plan or other, is trivial,
and it was shown in 1991 that finding optimal (shortest) plans is NP
hard. Various polynomial time algorithms for approximating optimal
BW planning exist, and there have been attempts to implement these
domain-specific methods in more general planning frameworks. Here we
discuss both theoretical and experimental results concerning optimal
and near-optimal BW planning.