Tag: cccg

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, Tim Wylie

Conference: The 32nd Canadian Conference on Computational Geometry (CCCG 2020)

Abstract: This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond to global signals that cause them to move one unit distance in a particular direction on a 2D grid board with geometric obstacles. We show that the problem of deciding if a particular particle can be relocated to a specified location on the board is PSPACE-complete when only allowing 1×1 particles. This shows a separation between this problem, called the relocation problem, and the occupancy problem in which we ask whether a particular location can be occupied by any particle on the board, which is known to be in P with only 1×1 particles. We then consider both the occupancy and relocation problems for the case of extremely simple rectangular geometry, but slightly more complicated pieces consisting of 1×2 and 2×1 domino particles, and show that in both cases the problems are PSPACE-complete.

Virtual Talk:

Accompanying Videos:

Title: Building Patterned Shapes in Robot Swarms with Uniform Control Signals

Authors: David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie

Conference: The 32nd Canadian Conference on Computational Geometry (CCCG 2020)

Abstract:
This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond to global signals that cause them to move one unit distance in a particular direction. We look at the problem of assembling patterns within this model. We
first derive upper and lower bounds on the worst-case number of steps needed to reconfigure a general purpose board into a target pattern. We then show that the construction of k-colored patterns of size-n requires Ω(n log k) steps in general, and Ω(n log k +√k) steps if the constructed shape must always be placed in a designated output location. We then design algorithms to approach these lower bounds: We show how to construct k-colored 1 × n lines in O(n log k + k) steps with unique output locations. For general colored shapes within a w×h bounding box, we achieve O(wh log k+hk) steps.

Patterned Line Building:

General Pattern Builder:

Title: Discrete Planar Map Matching

Authors: Bin Fu, Robert Schweller, Tim Wylie

Conference: The 31st Canadian Conference on Computational Geometry (CCCG’19)

Abstract:

Route reconstruction is an important application for Geographic Information Systems (GIS) that rely heavily upon GPS data and other location data from IoT devices. Many of these techniques rely on geometric methods involving the Frechet distance to compare curve similarity. The goal of reconstruction, or map matching, is to find the most similar path within a given graph to a given input curve, which is often only approximate location data. This process can be approximated by sampling the curves and using the discrete Frechet distance. Due to power and coverage constraints, the GPS data itself may be sparse causing improper constraints along the edges during the reconstruction if only the continuous Frechet distance is used. Here, we look at two variations of discrete map matching: one constraining the walk length and the other limiting the number of vertices visited in the graph. We give an efficient algorithm to solve one and prove the other is NP-complete and the minimization version is APX-hard while also giving a parameterized algorithm to solve the problem.