The problem appeared in the Sunday Telegraph newspaper on 2nd September 1999, in an article by Robert Matthews, Labyrinthine theories to stop us getting lost.
Peter van Beek and Xinguang Chen have shown that constraint satisfaction can be a viable approach to solve planning problems. They distribute CPlan, a C program for solving planning problems (see the README file for more details).
Encoding planning problems into propositional satisfiability has also been highly popular in the last few years. See, for example, Henry Kautz’s Blackbox system.