Thomas Thirlwall
Chloe McEntire
Hardness of Reconfiguring Robot Swarms with Uniform External Control in Limited Directions
Title: Hardness of Reconfiguring Robot Swarms with Uniform External Control in Limited Directions
Authors: David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie
This is the full version on arxiv of the initial short abstract Relocation with Uniform External Control in Limited Directions
Link: https://arxiv.org/abs/2003.13097
Abstract: Motivated by advances is nanoscale applications and simplistic robot agents, we look at problems based on using a global signal to move all agents when given a limited number of directional signals and immovable geometry. We study a model where unit square particles move within a 2D grid based on uniform external forces. Movement is based on a sequence of uniform commands which cause all particles to move 1 step in a specific direction. The 2D grid board additionally contains “blocked” spaces which prevent particles from entry. Within this model, we investigate the complexity of deciding 1) whether a target location on the board can be occupied (by any) particle (\emph{occupancy problem}), 2) whether a specific particle can be relocated to another specific position in the board (\emph{relocation problem}), and 3) whether a board configuration can be transformed into another configuration (\emph{reconfiguration problem}). We prove that while occupancy is solvable in polynomial time, the relocation and reconfiguration problems are both NP-Complete even when restricted to only 2 or 3 movement directions. We further define a hierarchy of board geometries and show that this hardness holds for even very restricted classes of board geometry.
Student presenting a CS colloquium talk
On 1/23 at 2pm in room EIEAB 2.208 there will be a 20 minute talk given by current undergraduate student Tim Gomez. He will be presenting his work, along with coauthors, on robot motion planning with uniform external controls. The talk will be the talk he gave at the 2020 Symposium on Discrete Algorithms, and is based on the following paper published in that conference: https://faculty.utrgv.edu/robert.schweller/papers/soda2020.pdf
All are welcome! See you there!
Proceedings from Hack Research
The 2nd Hack Research was a great success with some high-quality output and a lot of great participation. We had about 60 students there and over half of the students were part of a submission. The proceedings are now online on the event website: https://utrgv.hackresearch.com/site/?page_id=319. We’re looking forward to 2020!
2nd Annual Hack Research (HackR 2019)
ASARG is hosting the 2nd annual Hack Research (HackR) on December 7-8, 2019. The website with the details and registration is currently live (utrgv.hackresearch.com). Register and come join us for 24 hours of research, learning, and teamwork.
Paper accepted to SODA 2020
The group just had a paper accepted to appear at the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA) in 2020. The title is “Hierarchical Shape Construction and Complexity for Slidable Polyominos under Uniform External Forces” and the authors are Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Mauricio Flores, Timothy Gomez, Austin Luchsinger, Rene Reyes, Robert Schweller, and Tim Wylie.
Mason Garza
Summer Xtreme Seminar
Come join us at the first Summer Xtreme Algorithms seminar! This is a quick set of 5 talks to showcase some of the work being done in the lab. These are 10 minute talks! If you’re interested in research, come see what topics might interest you. The talks are in IEAB 2.208 on 7/25 starting at 1 pm. For a full list of talks, see the flyer.
Short abstract accepted at JCDCGGG
The short paper “Relocation with Uniform External Control in Limited Directions” was accepted at the 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3). The paper will be presented at the conference in September in Tokyo. http://www.jcdcgg.u-tokai.ac.jp/
The authors on the paper are Jose Balanza-Martinez, David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie.