Motion planning in Cartesian product graphs

Let $G$ be an undirected graph with $n$ vertices. Assume that a robot is placed on a vertex and $n − 2$ obstacles are placed on the other vertices. A vertex on which neither a robot nor an obstacle is placed is said to have a hole. Consider a single player game in which a robot or obstacle can be moved to adjacent vertex if it has a hole. The objective is to take the robot to a fixed destination vertex using minimum number of moves. In general, it is not necessary that the robot will take a shortest path between the source and destination vertices in graph $G$. In this article we show that the path traced by the robot coincides with a shortest path in case of Cartesian product graphs. We give the minimum number of moves required for the motion planning problem in Cartesian product of two graphs having girth 6 or more. A result that we prove in the context of Cartesian product of $P_n$ with itself has been used earlier to develop an approximation algorithm for ($n^2 − 1$)-puzzle