Motions of a connected subgraph representing a swarm of robots inside a graph of work stations

Aarón Atilano, Sebastian Bejos, Christian Rubio-Montiel

Abstract


Imagine that a swarm of robots is given, these robots must communicate with each other, and they can do so if certain conditions are met. We say that the swarm is connected if there is at least one way to send a message between each pair of robots. A robot can move from a work station to another only if the connectivity of the swarm is preserved in order to perform some tasks. We model the problem via graph theory, we study connected subgraphs and how to motion them inside a connected graph preserving the connectivity. We determine completely the group of movements.


Keywords


edge-blocks, the Wilson group, motion planning, robots swarps, pebble motion

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2022.10.2.12

References

A. Atilano, Keeping connectivity in simple graphs (In spanish), Thesis (BSc.)–National Autonomous University of Mexico, in preparation.

V. Auletta and P. Persiano, Optimal pebble motion on a tree, Inform. and Comput. 165(1) (2001), 42–68.

A. Cornejo, F. Kuhn, R. Ley-Wild, and N.A. Lynch, Keeping mobile robot swarms connected, In Idit Keidar, editor, Distributed Computing, 23rd International Symposium, DISC 2009, Elche, Spain, September 23-25, 2009. Proceedings, volume 5805 of Lecture Notes in Computer Science, Springer, (2009), 496–511.

E.D. Demaine, S.P. Fekete, P. Keldenich, H. Meijer, and C. Scheffer, Coordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch, SIAM J. Comput. 48(6) (2019), 1727–1762.

S. Fujita, T. Nakamigawa, and T. Sakuma, Colored pebble motion on graphs, European J. Combin. 33 (5) (2012), 884–892.

G. Goraly and R. Hassin, Multi-color pebble motion on graphs, Algorithmica 58(3) (2010), 610–636.

D. Kornhauser, G. Miller, and P. Spirakis, Coordinating pebble motion on graphs, the diameter of permutation groups, and applications, In 25th Annual Symposium on Foundations of Computer Science 1984, IEEE (1984), 241–250.

D. Ratner and M. K. Warmuth, Finding a shortest solution for the n × n extension of the 15-puzzle is intractable, In Tom Kehler, editor, Proceedings of the 5th National Conference on Artificial Intelligence. Philadelphia, PA, USA, August 11-15, 1986. Volume 1: Science, Morgan Kaufmann (1986), 168–172.

J.J. Rotman, An introduction to the theory of groups, volume 148 of Graduate Texts in Mathematics, Springer-Verlag, New York, fourth edition, 1995.

R.M. Wilson, Graph puzzles, homotopy, and the alternating group, J. Combinatorial Theory Ser. B 16 (1974), 86–96.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats