SOKOBAN and other motion planning problems

We consider a natural family of motion planning problems with movable obsta cles and obtain hardness results for them. Some members of the family are s hown to be PSPACE-complete thus improving and extending (and also simplifyi ng) a previous NP-hardness result of Wilfong. The family considered include s a motion planning problem which forms the basis of a popular computer gam e called SOKOBAN. The decision problem corresponding to SOKOBAN is shown to be NP-hard. The motion planning problems considered are related to the "wa rehouseman's problem" considered by Hopcroft, Schwartz and Sharir, and to g eometric versions of the motion planning problem on graphs considered by Pa padimitriou, Raghavan, Sudan and Tamaki. (C) 1999 Elsevier Science B.V. All rights reserved.