×

Motion planning in Cartesian product graphs. (English) Zbl 1290.05125

Summary: 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.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C57 Games on graphs (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68T40 Artificial intelligence for robotics
91A43 Games involving graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] G. Calinescu, A. Dumitrescu and J. Pach, Reconfigurations in graphs and grids, in: Latin American Theoretical Informatics Conference Lecture Notes in Computer Science 3887 (2006) 262-273. doi:10.1007/11682462 27; · Zbl 1145.68471
[2] B. Deb, K. Kapoor and S. Pati, On mrj reachability in trees Discrete Math., Alg. and Appl. 4 (2012). doi:10.1142/S1793830912500553; · Zbl 1282.91067
[3] T. Feder, Stable Networks and Product Graphs (Memoirs of the American Mathe- matical Society, 1995). doi:10.1090/memo/0555;
[4] R. Hammack, W. Imrich and S. Klaˇzar, Handbook of Product Graphs, Second Edition (CRC Press, New York, 2011).; · Zbl 1283.05001
[5] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).; · Zbl 0182.57702
[6] W. Imrich and S. Klavˇzar, Product Graphs, Structure and Recognition (John Wiley & Sons Inc., New York, 2000).; · Zbl 0963.05002
[7] W. Woolsey Johnson and W.E. Story, Notes on the “15” puzzle, Amer. J. Math. 2 (1879) 397-404. doi:10.2307/2369492; · JFM 11.0818.05
[8] D. Kornhauser, G. Miller, and P. Spirakis, Coordinating pebble motion on graphs, the diameter of permutation groups, and applications, in: Annual Symposium on Foundations of Computer Science, IEEE Computer Society (1984) 241-250. doi:10.1109/SFCS.1984.715921;
[9] E. Masehian and A.H. Nejad, Solvability of multi robot motion planning problems on trees, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, Piscataway, NJ, USA (2009), IEEE Press. 5936-5941. doi:10.1109/IROS.2009.5354148;
[10] C.H. Papadimitriou, P. Raghavan, M. Sudan and H. Tamaki, Motion planning on a graph, in: FOCS’94 (1994) 511-520. doi:10.1109/SFCS.1994.365740;
[11] I. Parberry, A real-time algorithm for the (n2 −1)-puzzle, Inform. Process. Lett. 56 (1995) 23-28. doi:10.1016/0020-0190(95)00134-X; · Zbl 0875.68539
[12] D. Ratner and M.K. Warmuth, The (n2 −1)-puzzle and related relocation problems, J. Symbolic Comput. 10 (1990) 111-137. doi:10.1016/S0747-7171(08)80001-6; · Zbl 0704.68057
[13] D. Ratner and M.K. Warmuth, Finding a shortest solution for the n × n extension of the 15-puzzle is intractable, in: AAAI(1986) 168-172.;
[14] R.M. Wilson, Graph puzzles, homotopy, and the alternating group, J. Combin. The- ory (B) 16 (1974) 86-96. doi:10.1016/0095-8956(74)90098-7; · Zbl 0285.05110
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.