Add to ORKGWe are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the ver-tices; this vertex is labeled s. Each of several other vertices contains a single movable obstacle. The ro-bot and the obstacles may only reside at vertices, although they may be moved across edges. A ver-tex may never contain more than one object (ro-bot/obstacle). In one step, we may move either the robot or one of the obstacles from its current posi-tion v to a vacant vertex adjacent to v. Our goal is to move the robot to a designated vertex t using the smallest number of steps possible. The problem is a simple abstraction of a robot mo-tion planning problem, with the geometry replaced by the adjacencies in the graph. We point out its co...