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.

Formal methods for control synthesis in partially observed environments : application to autonomous robotic manipulation

Modern robots are increasingly expected to function in uncertain and dynamically challenging environments, often in proximity with humans. In addition, wide scale adoption of robots requires on-the-fly adaptability of software for diverse application. These requirements strongly suggest the need to adopt formal representations of high level goals and safety specifications, especially as temporal logic formulas. This approach allows for the use of formal verification techniques for controller synthesis that can give guarantees for safety and performance. Robots operating in unstructured environments also face limited sensing capability. Correctly inferring a robot's progress toward high level goal can be challenging.

This thesis develops new algorithms for synthesizing discrete controllers in partially known environments under specifications represented as linear temporal logic (LTL) formulas. It is inspired by recent developments in finite abstraction techniques for hybrid systems and motion planning problems. The robot and its environment is assumed to have a finite abstraction as a Partially Observable Markov Decision Process (POMDP), which is a powerful model class capable of representing a wide variety of problems. However, synthesizing controllers that satisfy LTL goals over POMDPs is a challenging problem which has received only limited attention.

This thesis proposes tractable, approximate algorithms for the control synthesis problem using Finite State Controllers (FSCs). The use of FSCs to control finite POMDPs allows for the closed system to be analyzed as finite global Markov chain. The thesis explicitly shows how transient and steady state behavior of the global Markov chains can be related to two different criteria with respect to satisfaction of LTL formulas. First, the maximization of the probability of LTL satisfaction is related to an optimization problem over a parametrization of the FSC. Analytic computation of gradients are derived which allows the use of first order optimization techniques.

The second criterion encourages rapid and frequent visits to a restricted set of states over infinite executions. It is formulated as a constrained optimization problem with a discounted long term reward objective by the novel utilization of a fundamental equation for Markov chains - the Poisson equation. A new constrained policy iteration technique is proposed to solve the resulting dynamic program, which also provides a way to escape local maxima.

The algorithms proposed in the thesis are applied to the task planning and execution challenges faced during the DARPA Autonomous Robotic Manipulation - Software challenge.

Diseño y verificación del sistema de interpolación de trayectorias de un mecanismo de cinemática paralela

[ES]El objetivo principal del presente Trabajo Fin de Grado es diseñar un interpolador de trayectorias y programarlo en Labview. Para ello, se ha de analizar primeramente la cinemática del mecanismo a utilizar, un robot de cinemática paralela 5R, y calcular su espacio de trabajo. Después, se deducirán y programarán diversos perfiles de velocidades (trapezoidal de velocidades, trapezoidal de aceleraciones y sinusoidal) para moverse en rectas, así como el movimiento en curvas mediante splines. También se hallarán experimentalmente las características de los motores disponibles y se averiguarán las velocidades máximas que puede alcanzar el mecanismo. Así podremos presentar un software que sirva para generar trayectorias para el robot 5R. Se presentan también, entre otros, el presupuesto del proyecto y los riesgos en los que se puede incurrir. El documento finaliza con unos anexos de planos CAD, resultados y código de programación.

Diseño, fabricación y montaje de un robot de cinemática paralela de dos grados de libertad

[ES]Este Trabajo consiste en diseñar un robot de cinemática paralela de dos grados de libertad partiendo de unos requisitos mínimos necesarios que habrán de verificarse. A continuación, se fabricará siguiendo dicho diseño para finalmente montarlo sobre unas guías lineales constituyendo así una máquina de cinemática paralela, objetivo final conjunto de este Trabajo añadido al mencionado control de las guías. Resulta de especial interés su particular arquitectura, aspecto clave cuando se pretende un sistema preciso y reducir las vibraciones.

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

SCARA motako robot industrialaren simulazio birtuala eta interakzioa

[EU]Gradu amaierako lan honetan, Industria Ingenieritza graduan zehar emandako zenbait irakasgaietan landutako kontzeptuak oinarri bezala hartuta SCARA robot industrialaren analisia egin da. Lau askatasun gradu dituzten robot hauek oso erabiliak dira industrian beraien lan ziklo azkar, karga handiak jasateko kapazitate, errepikortasun eta aplikazio ugariengatik. Proiektua, bi zati nagusitan banandu da: SCARA motako robot baten analisi zinematikoa, robotaren irudikapena eta ibilbideen sorkuntza Matlab programa erabiliz. Adept Cobra e-Vario 600, SCARA motako prototipo errealarekin interakzioa. Proiektuan zehar garatuko diren edukien egitura ondorengoa izango da: Lehenik eta behin, proiektuko lehen atalean proiektua kokatuta dagoen testuinguruaren azalpena emango da, baita ere testuinguru horrek gaur egun, sail desberdinetan, duen garrantzia. Proiektuko bigarren atalean, lana egiterakoan proposatu diren helburuak eta proiektuak eskaintzen dituen onurak adieraziko dira. Bestetik, proiektuko hirugarren atalean, gaiaren egoeran, SCARA robotera heldu arte robotek historian zehar izan duten garapena eta hauen sailkapen desberdinak azalduko dira. Laugarren atalean, metodologian, proiektu honetan garatuko diren bi zati nagusien deskribapen zehatza emango da. Azkenik, proiektuko azken atalean, lana burutzeko bete behar izan diren ataza bakoitzaren deskribapena eta iraupena, aurrekontua, arriskuen analisia eta proiektu honetatik atera ditugun ondorioak ematen dira.

SCARA errobota: mugimendu gaitasunen eta ibilbide sorkuntzaren inplementazioa software grafikoan

[EU]Lan honen gaia SCARA errobot motaren mugimendu gaitasunen analisia egitea da, eta ibilbideen sorkuntzarako metodoekin batera software grafiko batean inplementatzea mugimenduaren simulazioa egin ahal izateko. Errobot serieen zinematikaren oinarrizko ezagutzatik hasita, mota konkretu batetara aplikatu egiten da eta honek aurkezten dituen berezitasunak garatu egiten dira, bi helburutara bideratuta: SCARA errobotaren mugimendu gaitasunak ezagutzea. Ibilbideen sorkuntzarako metodo baten inplementazioa. Hasteko, gaiaren egoera aztertu da, aplikazio nagusien eta ibilbide moten informazioa batzeko. Halaber ibilbideen sorkuntzarako metodoak arakatu dira, erabilera honetarako aproposena aurkitzeko. Jarraian, errobotaren analisia burutu da, ohizko erreminta matematikoak erabiliz, funtsezkoak diren lan eremua eta kokapen singularrak lortzeko. Ostean, software grafikoa garatu da mugimendu gaitasun hauek simulatzeko. Ohiko aplikazioetan oinarritutako ibilbideak sortzeko aukerak gehitu dira. Amaitzeko, oztopoak saihesten dituen ibilbideen sorkuntzarako metodoa inplementatu da, “pick and place” ibilbide motaren barruan.

Recent research in the African Great Lakes: fisheries, biodiversity and cichlid evolution

The East African Great Lakes are now well known for (1) their fisheries, of vital importance for their rapidly rising riparian human populations, and (2) as biodiversity hotspots with spectacular endemic faunas, of which the flocks of cichlid fishes unique to each of the three largest lakes, Tanganyika, Malawi and Victoria, offer unique opportunities to investigate how new species evolve and coexist. Since the early 1990s research involving over a hundred scientists, financed by many international bodies, has produced numerous reports and publications in widely scattered journals. This article summarizes their main discoveries and examines the status of, and prospects for, the fisheries, as well as current ideas on how their rich endemic fish faunas have evolved. It first considers fisheries projects in each of the three lakes: the deep rift valley lakes Tanganyika and Malawi and the huge Victoria, all of which share their waters between several East African countries. Secondly it considers the biodiversity surveys of each lake, based on underwater (SCUBA) observations of fish ecology and behaviour which have revealed threats to their fish faunas, and considers what conservation measures are needed. Thirdly, using the lakes as laboratories, what have the international investigations (including DNA techniques and follow-up aquarium experiments) now revealed about the origins and relationships of their cichlid species flocks and mechanisms of evolution?

Diseño y evaluación de un sistema de medida de aceleración en el elemento terminal de un manipulador de cinemática paralela

[ES]Este proyecto tiene como objetivo desarrollar una línea de investigación de opciones de sensorización de un mecanismo mediante acelerómetros. Se construirá para ello un sistema de adquisición y tratamiento de señales destinado a la sensorización de un mecanismo de cinemática paralela en base a los conocimientos adquiridos durante el curso. Se trabajará además con otros alumnos para llevar a cabo el diseño y montaje de un robot prototipo de cinemática paralela de dos grados de libertad sobre el que se experimentará y llevará a cabo el proyecto. Se plantean de este modo dos líneas de trabajo que se desarrollarán en este proyecto: Elaboración de un sistema de adquisición y tratamiento de señales adaptable a distintos sensores. Utilización de señales de múltiples acelerómetros para conocer en primer lugar aceleración, y de ser posible, posición de puntos de interés del mecanismo.

Ecologia de Astyanax taeniatus na Bacia do Rio Mato Grosso, Saquarema - RJ: Dieta, uso do micro-hábitat e uma breve análise comportamental

Neste trabalho tivemos como objetivo caracterizar a dieta, uso do habitat e padrões comportamentais de Astyanax taeniatus da bacia do Rio Mato Grosso, que encontra-se na porção leste do Estado do Rio de Janeiro (22 52 S; 42 40 W e 22 53 S; 42 34 W). Para a análise da dieta, os exemplares foram coletados bimestralmente entre março de 2006 e janeiro de 2007 em três localidades que diferiram pelas variáveis físicas. As observações de uso dos recursos do habitat foram realizadas por observação subaquática, na posição focal dos exemplares avistados, enquanto a quantificação da disponibilidade foi realizada em 50 quadrats de 20x20cm (400cm2) ao longo dos mesmos 50m onde foi realizada a observação sub-aquática. A análise do conteúdo estomacal de 651 exemplares foi realizada sob microscópio estereoscópico de acordo com métodos qualitativos e quantitativos (Freqüência de Ocorrência e Volumétrica). A participação relativa de cada item registrado nos estômagos em relação à totalidade da dieta foi analisada através do Índice Alimentar (IAi). Para verificar possíveis diferenças entre as proporções dos itens de origem animal e vegetal, autóctone e alóctone, os valores proporcionais foram testados pelo 2 de contingência. A partir dos dados de comprimento padrão e comprimento do intestino, foi calculado o valor do quociente intestinal. Os itens de origem vegetal tiveram maior contribuição na dieta da espécie para as localidades com maior altitude, enquanto os itens animais tiveram maior contribuição na localidade baixa. A diferença na contribuição dos itens de origem autóctone e alóctone também foi significativa. Na dieta de jovens e adultos, houve diferença significativa na contribuição de itens de origem vegetal e animal somente na localidade mais alta, onde os adultos consumiram maior quantidade de matéria vegetal. Os valores médios de quociente intestinal em jovens e adultos foram significativamente diferentes nas localidades de maior altitude, com valores maiores para indivíduos adultos. Observamos 52% dos indivíduos em profundidades entre 30 e 45 cm, 72% em áreas de rápido, 72% em velocidades entre 0 e 0,5km/h, 66% encontravam-se distantes da margem entre 40 e 120 cm, 37,6% em substrato do tipo areia e 34,4% em substrato do tipo pedra. De todos os padrões comportamentais observados, aquele que mais se destacou foi o forrageamento, onde 70,91% dos indivíduos estavam forrageando no meio da coluna dágua. Os resultados da dieta reforçam a idéia de as espécies de Astyanax têm hábito alimentar onívoro e oportunista, onde a espécie alimentou-se dos recursos disponíveis no ambiente evidenciando sua alta plasticidade alimentar ao longo do riacho. Espécies do gênero Astyanax são consideradas generalistas em relação ao uso do habitat e altamente ativas, corroborando com os resultados do presente estudo.

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.

Control de un sistema de accionamientos de traslación basado en correa para un manipulador de cinemática paralela

[ES]Este Trabajo de Fin de Grado “Control de un sistema de accionamientos de traslación basado en correa para un manipulador de cinemática paralela” tiene como objetivo principal la implementación de un sistema de control que nos permita manejar un manipulador de cinemática paralela de dos grados de libertad accionado mediante dos motores eléctricos de corriente continua. Como componente central de este sistema de control, se dispondrá de un ordenador portátil cuyo procesador será el encargado de ejecutar las acciones necesarias para que pueda llevarse a cabo esta actividad de control. De esta forma, la tarea más importante y laboriosa a llevar cabo en este proyecto será el desarrollo de un aplicación de control que, corriendo en el citado ordenador, permitirá al usuario manejar el manipulador de cinemática paralela en cuestión. Para ello, esta aplicación deberá ser capaz de interpretar las ordenes de movimiento dadas por el usuario y transmitirlas al procesador del mencionado ordenador. Además de todo lo anterior, para completar el desarrollo del sistema de control, será necesaria la implementación de diversos sensores que se encargarán de detectar y transmitir las señales necesarias para evitar situaciones de emergencia en el que el manipulador estuviese a punto de chocar con algún objeto o persona. En conclusión, mediante el cumplimiento de los objetivos de este Trabajo de Fin de Grado, se va a disponer de un sistema de control sencillo, intuitivo y fácilmente operable, que va a permitir a cualquier futuro usuario del mismo el manejo de un robot de cinemática paralela.

Simulación del robot Delta mediante MATLAB

[ES]El presente Trabajo Fin de Grado: SIMULACIÓN DEL ROBOT DELTA MEDIANTE MATLAB trata sobre el robot Delta. El objetivo principal del trabajo es servir de base para futuros proyectos. Incluye información sobre los robots Delta, así como de sus aplicaciones. Este tipo de robots tienen numerosas aplicaciones y beneficios gracias a las numerosas características favorables que se mencionan a lo largo del trabajo, como lo es por ejemplo la gran velocidad a la que se puede mover. En el trabajo se verán las resoluciones de los problemas cinemáticos: directo e inverso. Además, se podrán describir trayectorias tomando como base los anteriores problemas cinemáticos. Finalmente, es especialmente interesante la introducción de los interpoladores en la generación de trayectorias y los beneficios que ello trae consigo.

Record of a colloquium organised by IUBS on the methodology of radiation measurement under water. [Translation from: Mem. Inst. Ital. Idrobiol. 17, 57-79, 1964]

These minutes report on colloquium on the methodology of radiation measurement under water. The meeting was held on 3-5 January 1957, at the Biological Station, Lunz, Austria. The participants of the colloquium discussed various methodologies of radiation measurements, basic methods such as Secchi Disc and underwater photometer as well as specialist equipment like the absolute radiation apparatus.

Turbidity and plant growth in large slow-flowing lowland rivers. Progress Report: March 1989

The River Great Ouse is a highly managed large lowland river in eastern England. It drains rich arable land in the Midlands and Eastern England and over the years nutrient concentrations have increased and there is a general perception that the clarity of the water has decreased. The main river channels have been dredged a number of times partly for flood control reasons but also for recreational boating and navigation activities. The period covered by this first report has been used to develop specific methodology and instrumentation for measuring turbidity, suspended solids and underwater irradiance for conditions found in the middle abd lower reaches of the River Great Ouse. Sampling strategies have been developed and an extensive sampling programme is now underway covering phytoplankton, suspended solids and turbidity in relation to algal epiphyte growth on underwater macrophytes. Preliminary data are presented relating light levels on the river bed to the river bed profile, turbidity levels and phytoplankton chlorophyll a concentrations. Studies are underway concerning the extent of macrophyte cover and periphyton densities.