Synthetic molecular machines for active self-assembly : prototype algorithms, designs, and experimental study

Computer science and electrical engineering have been the great success story of the twentieth century. The neat modularity and mapping of a language onto circuits has led to robots on Mars, desktop computers and smartphones. But these devices are not yet able to do some of the things that life takes for granted: repair a scratch, reproduce, regenerate, or grow exponentially fast–all while remaining functional.

This thesis explores and develops algorithms, molecular implementations, and theoretical proofs in the context of “active self-assembly” of molecular systems. The long-term vision of active self-assembly is the theoretical and physical implementation of materials that are composed of reconfigurable units with the programmability and adaptability of biology’s numerous molecular machines. En route to this goal, we must first find a way to overcome the memory limitations of molecular systems, and to discover the limits of complexity that can be achieved with individual molecules.

One of the main thrusts in molecular programming is to use computer science as a tool for figuring out what can be achieved. While molecular systems that are Turing-complete have been demonstrated [Winfree, 1996], these systems still cannot achieve some of the feats biology has achieved.

One might think that because a system is Turing-complete, capable of computing “anything,” that it can do any arbitrary task. But while it can simulate any digital computational problem, there are many behaviors that are not “computations” in a classical sense, and cannot be directly implemented. Examples include exponential growth and molecular motion relative to a surface.

Passive self-assembly systems cannot implement these behaviors because (a) molecular motion relative to a surface requires a source of fuel that is external to the system, and (b) passive systems are too slow to assemble exponentially-fast-growing structures. We call these behaviors “energetically incomplete” programmable behaviors. This class of behaviors includes any behavior where a passive physical system simply does not have enough physical energy to perform the specified tasks in the requisite amount of time.

As we will demonstrate and prove, a sufficiently expressive implementation of an “active” molecular self-assembly approach can achieve these behaviors. Using an external source of fuel solves part of the the problem, so the system is not “energetically incomplete.” But the programmable system also needs to have sufficient expressive power to achieve the specified behaviors. Perhaps surprisingly, some of these systems do not even require Turing completeness to be sufficiently expressive.

Building on a large variety of work by other scientists in the fields of DNA nanotechnology, chemistry and reconfigurable robotics, this thesis introduces several research contributions in the context of active self-assembly.

We show that simple primitives such as insertion and deletion are able to generate complex and interesting results such as the growth of a linear polymer in logarithmic time and the ability of a linear polymer to treadmill. To this end we developed a formal model for active-self assembly that is directly implementable with DNA molecules. We show that this model is computationally equivalent to a machine capable of producing strings that are stronger than regular languages and, at most, as strong as context-free grammars. This is a great advance in the theory of active self- assembly as prior models were either entirely theoretical or only implementable in the context of macro-scale robotics.

We developed a chain reaction method for the autonomous exponential growth of a linear DNA polymer. Our method is based on the insertion of molecules into the assembly, which generates two new insertion sites for every initial one employed. The building of a line in logarithmic time is a first step toward building a shape in logarithmic time. We demonstrate the first construction of a synthetic linear polymer that grows exponentially fast via insertion. We show that monomer molecules are converted into the polymer in logarithmic time via spectrofluorimetry and gel electrophoresis experiments. We also demonstrate the division of these polymers via the addition of a single DNA complex that competes with the insertion mechanism. This shows the growth of a population of polymers in logarithmic time. We characterize the DNA insertion mechanism that we utilize in Chapter 4. We experimentally demonstrate that we can control the kinetics of this re- action over at least seven orders of magnitude, by programming the sequences of DNA that initiate the reaction.

In addition, we review co-authored work on programming molecular robots using prescriptive landscapes of DNA origami; this was the first microscopic demonstration of programming a molec- ular robot to walk on a 2-dimensional surface. We developed a snapshot method for imaging these random walking molecular robots and a CAPTCHA-like analysis method for difficult-to-interpret imaging data.

Pick and Place Aplikazioaren Garapena ABBko IRB120 Errobotarekin

[ES]El origen de este proyecto se encuentra dentro de la línea de investigación del equipo CompMech del Departamento de Ingeniería Mecánica de la Escuela, el cual financia tanto la inversión como el mantenimiento del prototipo utilizado en este proyecto. Partiendo de esta base, el objetivo principal de esta línea de estudio es profundizar en el control del robot para poder después llegar a desarrollar una aplicación práctica. Para lograr este objetivo se trabajará con el software RobotStudio, mediante el cual se llevarán a cabo diferentes tareas tales como la generación de trayectorias, optimización de las mismas y la implementación de aplicaciones prácticas. En este trabajo se dan los primeros pasos hacia el control del robot, siendo una base de partida para estudios más complejos y profundos. De modo que el objetivo principal es dar los primeros pasos en el campo de estudio de la robótica, para proporcionar una base sólida y útil que sea válida para el desarrollo de posteriores aplicaciones prácticas más complejas.

Efficient methods for stochastic optimal control

The Hamilton Jacobi Bellman (HJB) equation is central to stochastic optimal control (SOC) theory, yielding the optimal solution to general problems specified by known dynamics and a specified cost functional. Given the assumption of quadratic cost on the control input, it is well known that the HJB reduces to a particular partial differential equation (PDE). While powerful, this reduction is not commonly used as the PDE is of second order, is nonlinear, and examples exist where the problem may not have a solution in a classical sense. Furthermore, each state of the system appears as another dimension of the PDE, giving rise to the curse of dimensionality. Since the number of degrees of freedom required to solve the optimal control problem grows exponentially with dimension, the problem becomes intractable for systems with all but modest dimension.

In the last decade researchers have found that under certain, fairly non-restrictive structural assumptions, the HJB may be transformed into a linear PDE, with an interesting analogue in the discretized domain of Markov Decision Processes (MDP). The work presented in this thesis uses the linearity of this particular form of the HJB PDE to push the computational boundaries of stochastic optimal control.

This is done by crafting together previously disjoint lines of research in computation. The first of these is the use of Sum of Squares (SOS) techniques for synthesis of control policies. A candidate polynomial with variable coefficients is proposed as the solution to the stochastic optimal control problem. An SOS relaxation is then taken to the partial differential constraints, leading to a hierarchy of semidefinite relaxations with improving sub-optimality gap. The resulting approximate solutions are shown to be guaranteed over- and under-approximations for the optimal value function. It is shown that these results extend to arbitrary parabolic and elliptic PDEs, yielding a novel method for Uncertainty Quantification (UQ) of systems governed by partial differential constraints. Domain decomposition techniques are also made available, allowing for such problems to be solved via parallelization and low-order polynomials.

The optimization-based SOS technique is then contrasted with the Separated Representation (SR) approach from the applied mathematics community. The technique allows for systems of equations to be solved through a low-rank decomposition that results in algorithms that scale linearly with dimensionality. Its application in stochastic optimal control allows for previously uncomputable problems to be solved quickly, scaling to such complex systems as the Quadcopter and VTOL aircraft. This technique may be combined with the SOS approach, yielding not only a numerical technique, but also an analytical one that allows for entirely new classes of systems to be studied and for stability properties to be guaranteed.

The analysis of the linear HJB is completed by the study of its implications in application. It is shown that the HJB and a popular technique in robotics, the use of navigation functions, sit on opposite ends of a spectrum of optimization problems, upon which tradeoffs may be made in problem complexity. Analytical solutions to the HJB in these settings are available in simplified domains, yielding guidance towards optimality for approximation schemes. Finally, the use of HJB equations in temporal multi-task planning problems is investigated. It is demonstrated that such problems are reducible to a sequence of SOC problems linked via boundary conditions. The linearity of the PDE allows us to pre-compute control policy primitives and then compose them, at essentially zero cost, to satisfy a complex temporal logic specification.

Desarrollo de software para la realización de ensayos dinámicos de mecanismos de cinemática paralela

[ES]El presente Trabajo de Fin de Grado tiene como objetivo contribuir al desarrollo de un proyecto de investigación mediante la programación y control del movimiento de mecanismos de cinemática paralela para la realización de ensayos dinámicos. Dicho proyecto está enmarcado dentro de una línea de investigación del grupo de investigación CompMech de la UPV-­‐EHU que gira en torno al desarrollo y estudio de este tipo de mecanismos. Esto es; este trabajo, más allá de la utilidad que pudiera tener por sí mismo, está pensado para formar parte de un proyecto de mayor envergadura, para cuyo éxito será imprescindible la colaboración con otros investigadores y la integración de este trabajo con los realizados por ellos. Consiste en la creación de un software para el control y movimiento de mecanismos, generando vibraciones para la realización de ensayos dinámicos. Para ello, se programarán sobre la plataforma LabVIEW la interfaz de usuario y el motor de cálculo. Una vez se compruebe que el programa funciona correctamente, se integrará dentro de un programa principal, un control articular que será el encargado de comunicarse con la máquina. Posteriormente, se procederá a la realización de ensayos experimentales sobre los propios robots, en taller. Se tomarán medidas mediante acelerómetros y otros dispositivos, determinando las medidas más adecuadas para su correcta validación. Finalmente, se generalizará el trabajo realizado para posibilitar su empleo futuro en diferentes mecanismos

Análisis cinemático del robot antropomórfico IRB120 de ABB

[ES]En el siguiente Trabajo Fin de Grado se va a exponer el análisis cinemático y desarrollo de un modelo virtual para la implementación de las ecuaciones cinemáticas del robot IRB120 de ABB llevados a cabo durante el curso 2013/2014. Comenzando por un estudio del Estado del Arte de la robótica industrial, se plantean seguidamente las ecuaciones de localización del robot en función de las variables de entrada mediante el método matricial. Estas ecuaciones son implementadas en un modelo de MatLab para usarlas en la resolución del problema de posición directo e inverso, y son también usadas en herramientas de creación de trayectorias. Además, sus derivadas se utilizan en el cálculo de velocidades del elemento terminal. Por último, se muestra la creación del prototipo 3D del robot, así como un interfaz gráfico de control del robot para el usuario, y los trabajos de validación llevados a cabo de los mencionados modelos virtuales sobre el robot real.

Análisis Dinámico de mecanismos paralelos con requisitos de diseño mecatrónico

[ES]El objetivo del presente TFG es el Análisis Dinámico de mecanismos paralelos según las necesidades de la mecatrónica. La mecatrónica requiere expresiones explícitas de las fuerzas motoras que sólo dependen de las propias posiciones, velocidades y aceleraciones en los accionamientos. Ello requiere métodos avanzados de la mecánica analítica de sólido rígido. Concretamente se han desarrollado la ecuación de Lagrange modificada (según [11]) y la ecuación de Boltzmann-Hamel modificada, siendo esta última una aportación de este TFG. Como aplicación práctica se ha programado un modelo mecatrónico para un manipulador paralelo 5R y se ha optimizado el diseño de una Multi Axis Simulation Table 3PRS.

Interacción y programación de trayectorias de robot industrial tipo SCARA.

[ES]En el desarrollo de este Trabajo de Fin De Grado (TFG) en el curso 2014-2015 se ha trabajado con un robot de tipo SCARA, muy utilizado en la industria. El objetivo era analizar su cinemática y programar trayectorias que el robot pudiera realizar. En primer lugar se ha llevado a cabo un estudio del Estado del Arte, en el que se describe la robótica industrial y su desarrollo histórico hasta nuestros días, desarrollo que presenta un futuro prometedor. Además, se han descrito las particularidades que atañen al SCARA: sus características, su relevancia y su historia. En cuanto al robot, previamente se ha realizado un análisis cinemático del SCARA. Mediante métodos matriciales se han resuelto los problemas de posiciones y velocidades, para luego programarlas en MATLAB. Una vez comprendida su cinemática, se ha interactuado con él en el taller para poder entender su funcionamiento, sus componentes y su control. Después, con los conocimientos que se han adquirido, se han programado varias trayectorias usando el lenguaje del robot, el lenguaje V+, para finalmente ejecutar esos movimientos. El Trabajo se completa con la descripción de las tareas mediante un diagrama de Gantt, el presupuesto, la declaración de gastos y el análisis de riesgos.