DISCRETE WAREHOUSE PROBLEMS

A discrete warehouse is a collection of two-dimensional unit-square ob jects (robot and obstacles), which are allowed to move horizontally an d vertically along grid lines. In this paper, we consider motion plann ing problems in a discrete warehouse with movable obstacles. In such a setup one is allowed to move some of the obstacles in order to: (1) n avigate the robot between an initial and a final position of the wareh ouse, and (2) construct a clearing (path) between two specified points . The final positions of the obstacles are unimportant for our problem s. We consider two forms of obstacle manipulations: (a) remote, when t he obstacles are moved by a remote mechanism, and (b) contact, when th e obstacles are moved only by direct contact of the robot. We present necessary and sufficient conditions for the existence of a motion in b oth cases, and propose efficient algorithms for constructing feasible motions.