-
An Analytic Solution to the 3D CSC Dubins Path Problem
Authors:
Victor M. Baez,
Nikhil Navkar,
Aaron T. Becker
Abstract:
We present an analytic solution to the 3D Dubins path problem for paths composed of an initial circular arc, a straight component, and a final circular arc. These are commonly called CSC paths. By modeling the start and goal configurations of the path as the base frame and final frame of an RRPRR manipulator, we treat this as an inverse kinematics problem. The kinematic features of the 3D Dubins p…
▽ More
We present an analytic solution to the 3D Dubins path problem for paths composed of an initial circular arc, a straight component, and a final circular arc. These are commonly called CSC paths. By modeling the start and goal configurations of the path as the base frame and final frame of an RRPRR manipulator, we treat this as an inverse kinematics problem. The kinematic features of the 3D Dubins path are built into the constraints of our manipulator model. Furthermore, we show that the number of solutions is not constant, with up to seven valid CSC path solutions even in non-singular regions. An implementation of solution is available at https://github.com/aabecker/dubins3D.
△ Less
Submitted 14 May, 2024;
originally announced May 2024.
-
Minimum-Time Planar Paths with up to Two Constant Acceleration Inputs and $L_2$ Velocity and Acceleration Constraints
Authors:
Victor M. Baez,
Haoran Zhao,
Nihal Abdurahiman,
Nikhil V. Navkar,
Aaron T. Becker
Abstract:
Given starting and ending positions and velocities, $L_2$ bounds on the acceleration and velocity, and the restriction to no more than two constant control inputs, this paper provides routines to compute the minimal-time path. Closed form solutions are provided for reaching a position in minimum time with and without a velocity bound, and for stopping at the goal position.
A numeric solver is us…
▽ More
Given starting and ending positions and velocities, $L_2$ bounds on the acceleration and velocity, and the restriction to no more than two constant control inputs, this paper provides routines to compute the minimal-time path. Closed form solutions are provided for reaching a position in minimum time with and without a velocity bound, and for stopping at the goal position.
A numeric solver is used to reach a goal position and velocity with no more than two constant control inputs. If a cruising phase at the terminal velocity is needed, this requires solving a non-linear equation with a single parameter. Code is provided on GitHub at https://github.com/RoboticSwarmControl/MinTimeL2pathsConstraints.
△ Less
Submitted 7 March, 2024;
originally announced March 2024.
-
Computing Motion Plans for Assembling Particles with Global Control
Authors:
Patrick Blumenberg,
Arne Schmidt,
Aaron T. Becker
Abstract:
We investigate motion planning algorithms for the assembly of shapes in the \emph{tilt model} in which unit-square tiles move in a grid world under the influence of uniform external forces and self-assemble according to certain rules. We provide several heuristics and experimental evaluation of their success rate, solution length, runtime, and memory consumption.
We investigate motion planning algorithms for the assembly of shapes in the \emph{tilt model} in which unit-square tiles move in a grid world under the influence of uniform external forces and self-assemble according to certain rules. We provide several heuristics and experimental evaluation of their success rate, solution length, runtime, and memory consumption.
△ Less
Submitted 6 July, 2023;
originally announced July 2023.
-
Reconfiguration of a 2D Structure Using Spatio-Temporal Planning and Load Transferring
Authors:
Javier Garcia,
Michael Yannuzzi,
Peter Kramer,
Christian Rieck,
Sándor P. Fekete,
Aaron T. Becker
Abstract:
We present progress on the problem of reconfiguring a 2D arrangement of building material by a cooperative group of robots. These robots must avoid collisions, deadlocks, and are subjected to the constraint of maintaining connectivity of the structure. We develop two reconfiguration methods, one based on spatio-temporal planning, and one based on target swapping, to increase building efficiency. T…
▽ More
We present progress on the problem of reconfiguring a 2D arrangement of building material by a cooperative group of robots. These robots must avoid collisions, deadlocks, and are subjected to the constraint of maintaining connectivity of the structure. We develop two reconfiguration methods, one based on spatio-temporal planning, and one based on target swapping, to increase building efficiency. The first method can significantly reduce planning times compared to other multi-robot planners. The second method helps to reduce the amount of time robots spend waiting for paths to be cleared, and the overall distance traveled by the robots.
△ Less
Submitted 7 March, 2024; v1 submitted 16 November, 2022;
originally announced November 2022.
-
Connected Reconfiguration of Polyominoes Amid Obstacles using RRT*
Authors:
Javier Garcia,
Michael Yannuzzi,
Peter Kramer,
Christian Rieck,
Aaron T. Becker
Abstract:
This paper investigates the use of a sampling-based approach, the RRT*, to reconfigure a 2D set of connected tiles in complex environments, where multiple obstacles might be present. Since the target application is automated building of discrete, cellular structures using mobile robots, there are constraints that determine what tiles can be picked up and where they can be dropped off during reconf…
▽ More
This paper investigates the use of a sampling-based approach, the RRT*, to reconfigure a 2D set of connected tiles in complex environments, where multiple obstacles might be present. Since the target application is automated building of discrete, cellular structures using mobile robots, there are constraints that determine what tiles can be picked up and where they can be dropped off during reconfiguration. We compare our approach to two algorithms as global and local planners, and show that we are able to find more efficient build sequences using a reasonable number of samples, in environments with varying densities of obstacles.
△ Less
Submitted 26 October, 2022; v1 submitted 4 July, 2022;
originally announced July 2022.
-
The Pursuit and Evasion of Drones Attacking an Automated Turret
Authors:
Daniel Biediger,
Luben Popov,
Aaron T. Becker
Abstract:
This paper investigates the pursuit-evasion problem of a defensive gun turret and one or more attacking drones. The turret must ``visit" each attacking drone once, as quickly as possible, to defeat the threat. This constitutes a Shortest Hamiltonian Path (SHP) through the drones. The investigation considers situations with increasing fidelity, starting with a 2D kinematic model and progressing to…
▽ More
This paper investigates the pursuit-evasion problem of a defensive gun turret and one or more attacking drones. The turret must ``visit" each attacking drone once, as quickly as possible, to defeat the threat. This constitutes a Shortest Hamiltonian Path (SHP) through the drones. The investigation considers situations with increasing fidelity, starting with a 2D kinematic model and progressing to a 3D dynamic model. In 2D we determine the region from which one or more drones can always reach a turret, or the region close enough to it where they can evade the turret. This provides optimal starting angles for $n$ drones around a turret and the maximum starting radius for one and two drones.
We show that safety regions also exist in 3D and provide a controller so that a drone in this region can evade the pan-tilt turret. Through simulations we explore the maximum range $n$ drones can start and still have at least one reach the turret, and analyze the effect of turret behavior and the drones' number, starting configuration, and behaviors.
△ Less
Submitted 27 July, 2021;
originally announced July 2021.
-
Enumeration of Polyominoes & Polycubes Composed of Magnetic Cubes
Authors:
Yitong Lu,
Anuruddha Bhattacharjee,
Daniel Biediger,
Min Jun Kim,
Aaron T. Becker
Abstract:
This paper examines a family of designs for magnetic cubes and counts how many configurations are possible for each design as a function of the number of modules.
Magnetic modular cubes are cubes with magnets arranged on their faces. The magnets are positioned so that each face has either magnetic south or north pole outward. Moreover, we require that the net magnetic moment of the cube passes t…
▽ More
This paper examines a family of designs for magnetic cubes and counts how many configurations are possible for each design as a function of the number of modules.
Magnetic modular cubes are cubes with magnets arranged on their faces. The magnets are positioned so that each face has either magnetic south or north pole outward. Moreover, we require that the net magnetic moment of the cube passes through the center of opposing faces. These magnetic arrangements enable coupling when cube faces with opposite polarity are brought in close proximity and enable moving the cubes by controlling the orientation of a global magnetic field. This paper investigates the 2D and 3D shapes that can be constructed by magnetic modular cubes, and describes all possible magnet arrangements that obey these rules. We select ten magnetic arrangements and assign a "colo"' to each of them for ease of visualization and reference. We provide a method to enumerate the number of unique polyominoes and polycubes that can be constructed from a given set of colored cubes. We use this method to enumerate all arrangements for up to 20 modules in 2D and 16 modules in 3D. We provide a motion planner for 2D assembly and through simulations compare which arrangements require fewer movements to generate and which arrangements are more common. Hardware demonstrations explore the self-assembly and disassembly of these modules in 2D and 3D.
△ Less
Submitted 21 July, 2021;
originally announced July 2021.
-
Efficient Parallel Self-Assembly Under Uniform Control Inputs
Authors:
Arne Schmidt,
Sheryl Manzoor,
Li Huang,
Aaron T. Becker,
Sándor P. Fekete
Abstract:
We prove that by successively combining subassemblies, we can achieve sublinear construction times for "staged" assembly of micro-scale objects from a large number of tiny particles, for vast classes of shapes; this is a significant advance in the context of programmable matter and self-assembly for building high-yield micro-factories.The underlying model has particles moving under the influence o…
▽ More
We prove that by successively combining subassemblies, we can achieve sublinear construction times for "staged" assembly of micro-scale objects from a large number of tiny particles, for vast classes of shapes; this is a significant advance in the context of programmable matter and self-assembly for building high-yield micro-factories.The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle; particles bond when forced together with a compatible particle. Previous work considered sequential composition of objects, resulting in construction time that is linear in the number N of particles, which is inefficient for large N. Our progress implies critical speedup for constructible shapes; for convex polyominoes, even a constant construction time is possible. We also show that our construction process can be used for pipelining, resulting in an amortized constant production time.
△ Less
Submitted 4 July, 2018;
originally announced July 2018.
-
Particle Computation: Complexity, Algorithms, and Logic
Authors:
Aaron T. Becker,
Erik D. Demaine,
Sándor P. Fekete,
Jarrett Lonsforda,
Rose Morris-Wright
Abstract:
We investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that move in a 2D workspace using a global input signal (such as gravity or a magnetic field). We show that a maze of obstacles to the environment can be used to create complex systems. We provide a wide range of results for a wide range of questions. These can be subdivided into…
▽ More
We investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that move in a 2D workspace using a global input signal (such as gravity or a magnetic field). We show that a maze of obstacles to the environment can be used to create complex systems. We provide a wide range of results for a wide range of questions. These can be subdivided into external algorithmic problems, in which particle configurations serve as input for computations that are performed elsewhere, and internal logic problems, in which the particle configurations themselves are used for carrying out computations. For external algorithms, we give both negative and positive results. If we are given a set of stationary obstacles, we prove that it is NP-hard to decide whether a given initial configuration of unit-sized particles can be transformed into a desired target configuration. Moreover, we show that finding a control sequence of minimum length is PSPACE-complete. We also work on the inverse problem, providing constructive algorithms to design workspaces that efficiently implement arbitrary permutations between different configurations. For internal logic, we investigate how arbitrary computations can be implemented. We demonstrate how to encode dual-rail logic to build a universal logic gate that concurrently evaluates and, nand, nor, and or operations. Using many of these gates and appropriate interconnects, we can evaluate any logical expression. However, we establish that simulating the full range of complex interactions present in arbitrary digital circuits encounters a fundamental difficulty: a fan-out gate cannot be generated. We resolve this missing component with the help of 2x1 particles, which can create fan-out gates that produce multiple copies of the inputs. Using these gates we provide rules for replicating arbitrary digital circuits.
△ Less
Submitted 4 December, 2017;
originally announced December 2017.
-
Tilt Assembly: Algorithms for Micro-Factories That Build Objects with Uniform External Forces
Authors:
Aaron T. Becker,
Sándor P. Fekete,
Phillip Keldenich,
Dominik Krupke,
Christian Rieck,
Christian Scheffer,
Arne Schmidt
Abstract:
We present algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny particles, which has been proposed in the context of programmable matter and self-assembly for building high-yield micro-factories. The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle; particles can bond when bein…
▽ More
We present algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny particles, which has been proposed in the context of programmable matter and self-assembly for building high-yield micro-factories. The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle; particles can bond when being forced together with another appropriate particle. Due to the physical and geometric constraints, not all shapes can be built in this manner; this gives rise to the Tilt Assembly Problem (TAP) of deciding constructibility. For simply-connected polyominoes $P$ in 2D consisting of $N$ unit-squares ("tiles"), we prove that TAP can be decided in $O(N\log N)$ time. For the optimization variant MaxTAP (in which the objective is to construct a subshape of maximum possible size), we show polyAPX-hardness: unless P=NP, MaxTAP cannot be approximated within a factor of $Ω(N^{\frac{1}{3}})$; for tree-shaped structures, we give an $O(N^{\frac{1}{2}})$-approximation algorithm. For the efficiency of the assembly process itself, we show that any constructible shape allows pipelined assembly, which produces copies of $P$ in $O(1)$ amortized time, i.e., $N$ copies of $P$ in $O(N)$ time steps. These considerations can be extended to three-dimensional objects: For the class of polycubes $P$ we prove that it is NP-hard to decide whether it is possible to construct a path between two points of $P$; it is also NP-hard to decide constructibility of a polycube $P$. Moreover, it is expAPX-hard to maximize a path from a given start point.
△ Less
Submitted 19 September, 2017;
originally announced September 2017.
-
Steering a Particle Swarm Using Global Inputs and Swarm Statistics
Authors:
Shiva Shahrokhi,
Lillian Lin,
Chris Ertel,
Mable Wan,
Aaron T. Becker
Abstract:
Microrobotics has the potential to revolutionize many applications including targeted material delivery, assembly, and surgery. The same properties that promise breakthrough solutions---small size and large populations---present unique challenges for controlling motion.
Robotic manipulation usually assumes intelligent agents, not particle systems manipulated by a global signal. To identify the k…
▽ More
Microrobotics has the potential to revolutionize many applications including targeted material delivery, assembly, and surgery. The same properties that promise breakthrough solutions---small size and large populations---present unique challenges for controlling motion.
Robotic manipulation usually assumes intelligent agents, not particle systems manipulated by a global signal. To identify the key parameters for particle manipulation, we used a collection of online games where players steer swarms of up to 500 particles to complete manipulation challenges. We recorded statistics from over ten thousand players. Inspired by techniques where human operators performed well, we investigate controllers that use only the mean and variance of the swarm. We prove the mean position is controllable and provide conditions under which variance is controllable. We next derive automatic controllers for these and a hysteresis-based switching control to regulate the first two moments of the particle distribution. Finally, we employ these controllers as primitives for an object manipulation task and implement all controllers on 100 kilobots controlled by the direction of a global light source.
△ Less
Submitted 6 June, 2017;
originally announced June 2017.
-
Collecting a Swarm in a Grid Environment Using Shared, Global Inputs
Authors:
Arun V. Mahadev,
Dominik Krupke,
Jan-Marc Reinhardt,
Sándor P. Fekete,
Aaron T. Becker
Abstract:
This paper investigates efficient techniques to collect and concentrate an under-actuated particle swarm despite obstacles. Concentrating a swarm of particles is of critical importance in health-care for targeted drug delivery, where micro-scale particles must be steered to a goal location. Individual particles must be small in order to navigate through micro-vasculature, but decreasing size bring…
▽ More
This paper investigates efficient techniques to collect and concentrate an under-actuated particle swarm despite obstacles. Concentrating a swarm of particles is of critical importance in health-care for targeted drug delivery, where micro-scale particles must be steered to a goal location. Individual particles must be small in order to navigate through micro-vasculature, but decreasing size brings new challenges. Individual particles are too small to contain on-board power or computation and are instead controlled by a global input, such as an applied fluidic flow or electric field.
To make progress, this paper considers a swarm of robots initialized in a grid world in which each position is either free-space or obstacle. This paper provides algorithms that collect all the robots to one position and compares these algorithms on the basis of efficiency and implementation time.
△ Less
Submitted 2 January, 2017;
originally announced January 2017.
-
Algorithms For Shaping a Particle Swarm With a Shared Control Input Using Boundary Interaction
Authors:
Shiva Shahrokhi,
Arun Mahadev,
Aaron T. Becker
Abstract:
Consider a swarm of particles controlled by global inputs. This paper presents algorithms for shaping such swarms in 2D using boundary walls. The range of configurations created by conforming a swarm to a boundary wall is limited. We describe the set of stable configurations of a swarm in two canonical workspaces, a circle and a square. To increase the diversity of configurations, we add boundary…
▽ More
Consider a swarm of particles controlled by global inputs. This paper presents algorithms for shaping such swarms in 2D using boundary walls. The range of configurations created by conforming a swarm to a boundary wall is limited. We describe the set of stable configurations of a swarm in two canonical workspaces, a circle and a square. To increase the diversity of configurations, we add boundary interaction to our model. We provide algorithms using friction with walls to place two robots at arbitrary locations in a rectangular workspace. Next, we extend this algorithm to place $n$ agents at desired locations. We conclude with efficient techniques to control the covariance of a swarm not possible without wall-friction. Simulations and hardware implementations with 100 robots validate these results.
These methods may have particular relevance for current micro- and nano-robots controlled by global inputs.
△ Less
Submitted 7 September, 2016;
originally announced September 2016.
