Motion planning in Cartesian product graphs
Biswajit Deb, Kalpesh Kapoor · Discussiones Mathematicae Graph Theory · 2013
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.