# Motion planning in cartesian product graphs

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 2, page 207-221
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBiswajit Deb, and Kalpesh Kapoor. "Motion planning in cartesian product graphs." Discussiones Mathematicae Graph Theory 34.2 (2014): 207-221. <http://eudml.org/doc/267655>.

@article{BiswajitDeb2014,

abstract = {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 Pn with itself has been used earlier to develop an approximation algorithm for (n2 − 1)-puzzle},

author = {Biswajit Deb, Kalpesh Kapoor},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {robot motion in a graph; Cartesian product of graphs},

language = {eng},

number = {2},

pages = {207-221},

title = {Motion planning in cartesian product graphs},

url = {http://eudml.org/doc/267655},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Biswajit Deb

AU - Kalpesh Kapoor

TI - Motion planning in cartesian product graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 2

SP - 207

EP - 221

AB - 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 Pn with itself has been used earlier to develop an approximation algorithm for (n2 − 1)-puzzle

LA - eng

KW - robot motion in a graph; Cartesian product of graphs

UR - http://eudml.org/doc/267655

ER -

## References

top- [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[Crossref] Zbl1145.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[Crossref]
- [3] T. Feder, Stable Networks and Product Graphs (Memoirs of the American Mathe- matical Society, 1995). doi:10.1090/memo/0555[Crossref]
- [4] R. Hammack, W. Imrich and S. Klaˇzar, Handbook of Product Graphs, Second Edition (CRC Press, New York, 2011). Zbl1283.05001
- [5] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).
- [6] W. Imrich and S. Klavˇzar, Product Graphs, Structure and Recognition (John Wiley & Sons Inc., New York, 2000).
- [7] W. Woolsey Johnson and W.E. Story, Notes on the ”15” puzzle, Amer. J. Math. 2 (1879) 397-404. doi:10.2307/2369492[Crossref]
- [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[Crossref]
- [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[Crossref]
- [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[Crossref]
- [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[Crossref]
- [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[Crossref] Zbl0704.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 [Crossref]

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.