Motion planning in cartesian product graphs

Biswajit Deb; Kalpesh Kapoor

Discussiones Mathematicae Graph Theory (2014)

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

Abstract

top
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

How to cite

top

Biswajit 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. [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. [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. [3] T. Feder, Stable Networks and Product Graphs (Memoirs of the American Mathe- matical Society, 1995). doi:10.1090/memo/0555[Crossref] 
  4. [4] R. Hammack, W. Imrich and S. Klaˇzar, Handbook of Product Graphs, Second Edition (CRC Press, New York, 2011). Zbl1283.05001
  5. [5] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969). 
  6. [6] W. Imrich and S. Klavˇzar, Product Graphs, Structure and Recognition (John Wiley & Sons Inc., New York, 2000). 
  7. [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. [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. [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. [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. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.