Abstract
Given n robots contained within a square grid surrounded by four walls, we ask the question of whether it is possible to move a particular robot a to a particular grid location b by performing a sequence of global step operations in which all robots move one grid step in the same cardinal direction (if not blocked by a wall or other blocked robots). We show this problem is NP-complete when restricted to just two directions (south and west). This answers the simplest fundamental problem in uniform global unit tilt swarm robotics.
This research was supported in part by National Science Foundation Grant CCF-1817602.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akitaya, H., Aloupis, G., Löffler, M., Rounds, A.: Trash compaction. In: Proceedings of 32nd European Workshop on Computational Geometry, pp. 107–110 (2016)
Akitaya, H.A., Löffler, M., Viglietta, G.: Pushing blocks by sweeping lines. In: Proceedings of the 11th International Conference on Fun with Algorithms, FUN 2022 (2022)
Balanza-Martinez, J., et al.: Hierarchical shape construction and complexity for slidable polyominoes under uniform external forces. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pp. 2625–2641 (2020). https://doi.org/10.1137/1.9781611975994.160
Balanza-Martinez, J., et al.: Full tilt: universal constructors for general shapes with uniform external forces. In: Proceedings of the 2019 ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pp. 2689–2708 (2019). https://doi.org/10.1137/1.9781611975482.167
Becker, A., Demaine, E.D., Fekete, S.P., Habibi, G., McLurkin, J.: Reconfiguring massive particle swarms with limited, global control. In: Flocchini, P., Gao, J., Kranakis, E., Meyer auf der Heide, F. (eds.) ALGOSENSORS 2013. LNCS, vol. 8243, pp. 51–66. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-45346-5_5
Becker, A.T., Demaine, E.D., Fekete, S.P., McLurkin, J.: Particle computation: designing worlds to control robot swarms with only global signals. In: sIEEE International Conference on Robotics and Automation, ICRA 2014, pp. 6751–6756 (May 2014). https://doi.org/10.1109/ICRA.2014.6907856
Becker, A.T., Habibi, G., Werfel, J., Rubenstein, M., McLurkin, J.: Massive uniform manipulation: controlling large populations of simple robots with a common input signal. In: 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 520–527 (Nov 2013). https://doi.org/10.1109/IROS.2013.6696401
Caballero, D., Cantu, A.A., Gomez, T., Luchsinger, A., Schweller, R., Wylie, T.: Fast reconfiguration of robot swarms with uniform control signals. Nat. Comput. 20(4), 659–669 (2021). https://doi.org/10.1007/s11047-021-09864-0
Caballero, D., Cantu, A.A., Gomez, T., Luchsinger, A., Schweller, R., Wylie, T.: Building patterned shapes in robot swarms with uniform control signals. In: Proceedings of the 32nd Canadian Conference on Computational Geometry, CCCG 2020, pp. 59–62 (2020)
Caballero, D., Cantu, A.A., Gomez, T., Luchsinger, A., Schweller, R., Wylie, T.: Hardness of reconfiguring robot swarms with uniform external control in limited directions. J. Inf. Process. 28, 782–790 (2020)
Caballero, D., Cantu, A.A., Gomez, T., Luchsinger, A., Schweller, R., Wylie, T.: Relocating units in robot swarms with uniform control signals is pspace-complete. In: Proceedings of the 32nd Canadian Conference on Computational Geometry, CCCG 2020, pp. 49–55 (2020)
Caballero, D., Cantu, A.A., Gomez, T., Luchsinger, A., Schweller, R., Wylie, T.: Unit tilt row relocation in a square (short abstract). In: Proceedings of the 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games, TJCDCG3’2020+1, pp. 122–123 (2021)
Chiang, P.T., et al.: Toward a light-driven motorized nanocar: Synthesis and initial imaging of single molecules. ACS Nano 6(1), 592–597 (2012). https://doi.org/10.1021/nn203969b, pMID: 22129498
Felfoul, O., Mohammadi, M., Gaboury, L., Martel, S.: Tumor targeting by computer controlled guidance of magnetotactic bacteria acting like autonomous microrobots. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1304–1308 (Sep 2011). https://doi.org/10.1109/IROS.2011.6094991
Martel, S.: Bacterial microsystems and microrobots. In: Biomedical Microdevices, vol. 14, pp. 1033–1045 (2012). https://doi.org/10.1007/s10544-012-9696-x
Martel, S., Taherkhani, S., Tabrizian, M., Mohammadi, M., de Lanauze, D., Felfoul, O.: Computer 3D controlled bacterial transports and aggregations of microbial adhered nano-components. J. Micro-Bio Robot. (4), 23–28 (2014). https://doi.org/10.1007/s12213-014-0076-x
Shirai, Y., Osgood, A.J., Zhao, Y., Kelly, K.F., Tour, J.M.: Directional control in thermally driven single-molecule nanocars. Nano Lett. 5(11), 2330–2334 (2005). https://doi.org/10.1021/nl051915k, pMID: 16277478
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Caballero, D., Cantu, A.A., Gomez, T., Luchsinger, A., Schweller, R., Wylie, T. (2023). Uniform Robot Relocation Is Hard in only Two Directions Even Without Obstacles. In: Genova, D., Kari, J. (eds) Unconventional Computation and Natural Computation. UCNC 2023. Lecture Notes in Computer Science, vol 14003. Springer, Cham. https://doi.org/10.1007/978-3-031-34034-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-031-34034-5_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-34033-8
Online ISBN: 978-3-031-34034-5
eBook Packages: Computer ScienceComputer Science (R0)