Award Abstract # 1619278
RI: Small: Collaborative Research: Micro-Assembly Exploiting SofT RObotics (MAESTRO)

NSF Org: IIS
Division of Information & Intelligent Systems
Recipient: UNIVERSITY OF HOUSTON SYSTEM
Initial Amendment Date: June 3, 2016
Latest Amendment Date: June 20, 2017
Award Number: 1619278
Award Instrument: Continuing Grant
Program Manager: Wendy Nilsen
wnilsen@nsf.gov
 (703)292-2568
IIS
 Division of Information & Intelligent Systems
CSE
 Directorate for Computer and Information Science and Engineering
Start Date: July 1, 2016
End Date: September 30, 2019 (Estimated)
Total Intended Award Amount: $201,308.00
Total Awarded Amount to Date: $209,308.00
Funds Obligated to Date: FY 2016 = $201,308.00
FY 2017 = $8,000.00
History of Investigator:
  • Aaron Becker (Principal Investigator)
    atbecker@uh.edu
Recipient Sponsored Research Office: University of Houston
4300 MARTIN LUTHER KING BLVD
HOUSTON
TX  US  77204-3067
(713)743-5773
Sponsor Congressional District: 18
Primary Place of Performance: University of Houston
N308 Engineering Building 1
Houston
TX  US  77204-4005
Primary Place of Performance
Congressional District:
18
Unique Entity Identifier (UEI): QKWEF8XLMTT3
Parent UEI:
NSF Program(s): Robust Intelligence,
Unallocated Program Costs
Primary Program Source: 01001617DB NSF RESEARCH & RELATED ACTIVIT
01001718DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 7495, 7923, 9251
Program Element Code(s): 749500, 919900
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.070

ABSTRACT

The MAESTRO project will develop a new type of manufacturing by combining soft robotics and swarm control to construct assemblies in 2D and 3D from individual artificial cells made of hydrogels. MAESTRO will design rules for building tiny factories so that, like a conductor?s baton, global control signals will organize artificial cells into complex configurations. These artificial cells can contain living cells and be assembled into tissue for artificial organs, or contain inorganic particles to assemble into micro-scale tools.

MAESTRO will ferry desired components in artificial cells constructed from polysaccharide-based hydrogels. Current approaches use engineered structures or live bacteria as micro-scale actuators to push or pull desired objects into place. The proposed approach uses the soft robots themselves as building blocks for desired patterns. The artificial cells excel at encapsulating a wide range of micro and nano-sized particles, for example living cells and magnetic nanoparticles. Furthermore, artificial cells can be triggered to efficiently release their payloads. Novel swarm control algorithms using obstacle-based particle computation will steer the cells. In traditional robotics, simultaneous control of multiple robots is based on individual motion control that requires heterogeneity among robots or the ability to deliver multiple input signals; both approaches are currently impractical in small-scale systems. However, these challenges can be overcome by parallel motion planning in obstacle-filled workspaces. This obstacle-based positional control makes the position of microrobots fully controllable using just a single control input. Actuation of these stimuli-responsive artificial cells in micro-fluidic, obstacle-laden environments presents a paradigm shift in fabrication technology.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

(Showing: 1 - 10 of 46)
Aaron T. Becker, Erik D. Demaine, Sa?ndor P. Fekete, Jarrett Lonsford, Rose Morris-Wright "Particle Computation: Complexity, Algorithms, and Logic" Natural Computing , 2017 https://doi.org/10.1007/s11047-017-9666-6
Aaron T. Becker, Sa?ndor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, and Arne Schmidt "Tilt Assembly: Algorithms for Micro-Factories That Build Objects with Uni- form External Forces" 28th International Symposium on Algorithms and Computation (ISAAC 2017) , 2017 10.4230/LIPIcs.ISAAC.2017.11
Arun Mahadev, Dominik Michael Krupke, Jan-Marc Reinhardt, S{\'a}ndor Fekete, Aaron T. Becker "Collecting a Swarm in a Grid Environment Using Shared, Global Inputs" IEEE Conference on Automation Science and Engineering , 2017 , p.1231
Arun Mahadev, Dominik Michael Krupke, Sa?ndor Fekete, Aaron T. Becker "Mapping and Coverage with a Particle Swarm Controlled by Uniform Inputs" IEEE/RSJ International Conference on Intelli- gent Robots and Systems (IROS) , 2017 10.1109/IROS.2017.8202280
A. {Schmidt} and S. {Manzoor} and L. {Huang} and A. T. {Becker} and S. P. {Fekete} "Efficient Parallel Self-Assembly Under Uniform Control Inputs" IEEE Robotics and Automation Letters , v.3 , 2018 , p.3521-3528 10.1109/LRA.2018.2853758
A. {Schmidt} and S. {Manzoor} and L. {Huang} and A. T. {Becker} and S. P. {Fekete} "Efficient Parallel Self-Assembly Under Uniform Control Inputs" IEEE Robotics and Automation Letters , v.3 , 2018 , p.3521-3528 10.1109/LRA.2018.2853758
A. {Schmidt} and V. M. {Baez} and A. T. {Becker} and S. P. {Fekete} "Coordinated Particle Relocation Using Finite Static Friction With Boundary Walls" IEEE Robotics and Automation Letters , v.5 , 2020 , p.985-992 10.1109/LRA.2020.2967275
Baez, Victor M. and Becker, Aaron T. and Fekete, S{\'a}ndor P. and Schmidt, Arne "Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition)" 36th International Symposium on Computational Geometry (SoCG 2020) , v.164 , 2020 10.4230/LIPIcs.SoCG.2020.72 Citation Details
Becker, Aaron T and Demaine, Erik D and Fekete, S{\'a}ndor P and Lonsford, Jarrett and Morris-Wright, Rose "Particle computation: complexity, algorithms, and logic" Natural Computing , v.18 , 2019 , p.181--201 https://doi.org/10.1007/s11047-017-9666-6
Becker, Aaron T. and Demaine, Erik D. and Fekete, Sรกndor P. and Lonsford, Jarrett and Morris-Wright, Rose "Particle computation: complexity, algorithms, and logic" Natural Computing , 2017 10.1007/s11047-017-9666-6 Citation Details
Becker, Aaron T and Fekete, S{\'a}ndor P and Keldenich, Phillip and Krupke, Dominik and Rieck, Christian and Scheffer, Christian and Schmidt, Arne "Tilt assembly: Algorithms for micro-factories that build objects with uniform external forces" Algorithmica , 2018 , p.1--23 https://doi.org/10.1007/s00453-018-0483-9
(Showing: 1 - 10 of 46)

PROJECT OUTCOMES REPORT

Disclaimer

This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.

The MAESTRO project developed a new type of manufacturing by combining soft robotics and swarm control to construct assemblies in 2D and 3D from individual artificial cells made of hydrogels. Often it is difficult or impossible to individually manipulate these cells. Instead, this project uses an exterior, global force (e.g. gravitational or magnetic fields) to move all the cells at once.

MAESTRO designed rules for building tiny factories so that, like a conductor?s baton, the global control forces can organize artificial cells into complex configurations. The underlying model has cells moving under the influence of uniform external forces until they hit an obstacle. Cells bond when forced together with another appropriate cell.

We developed new algorithms (step-by-step procedures) for controlling many cells in unison, and derived complexity class bounds. This enables us to predict how complicated the factory needs to be for any desired final assembly shape, and how long it will take to produce components.  

We also completed a branch of theoretical work on algorithmic self-assembly. We derived algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny cells, which was proposed in the context of programmable matter and self-assembly for building high-yield micro-factories. Due to the physical and geometric constraints, not all shapes can be built in this manner; so, we designed an efficient test to decide constructibility, whether a shape can be generated by an automated factory with global forces. 

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 sequentially constructible path from a given start point. (A polycube is a solid figure formed by joining one or more equal cubes face to face.)

We proved that by successively combining subassemblies, we can achieve sublinear construction times for ?staged? assembly of microscale objects from a large number of tiny cells, for vast classes of shapes; this is a significant advance in the context of programmable matter and self-assembly for building high-yield microfactories. Our initial work considered sequential composition of objects, resulting in construction time that is linear in the number N of cells, 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 (an assembly is completed every cycle).

We also derived analytical results using workspace obstacles and global inputs to reshape a group of cells. Shape control of many cells is necessary for conveying information, construction, and navigation. First, we show how the cells? characteristic angle of repose can be used to reshape the group by controlling angle of attack and the magnitude of the driving force. These can then be used to control the force and torque applied to a rectangular rigid body. Next, we examine the full set of stable, achievable mean and variance configurations for the shape of a cell group in two canonical environments: a square and a circular workspace. Finally, we show how workspaces with linear boundary layers can be used to achieve a richer set of mean and variance configurations.

The funding resulted in the publication of 8 conference papers, 11 Journal papers, and 2 book chapters. Two PhD students, 10 Master of Science students, and 10 undergraduate students participated in research experiences involved with this award.

 


Last Modified: 02/14/2020
Modified by: Aaron T Becker

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page