CCCG 2020 Presentations

Due to the pandemic, the Canadian Conference on Computational Geometry was held virtually this year. We had two papers published, and the presentations were given as pre-recorded videos. If you’re interested in seeing these, we’ve posted them to the ASARG youtube channel.

The two presentations:

Paper accepted to DNA 2020

The research group has a paper accepted to the 26th International Conference on DNA Computing and Molecular Programming (DNA). The paper is Verification and Computation in Restricted Tile Automata. The authors are David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie.

Two papers accepted to CCCG 2020

The research group has had two papers accepted to the 32nd Canadian Conference on Computational Geometry this year. The papers explore different aspects of the single step tilt model with robotic motion planning. The papers are as follows:

Title: Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete. Authors: David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie.

Title Building Patterned Shapes in Robot Swarms with Uniform Control Signals. Authors: David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, and Tim Wylie.

 

New Arxiv Paper

A preprint of an upcoming journal paper is now online at arxiv.

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.
Link: arXiv:2003.13097

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!