A novel methodology for planning reliable wireless sensor networks

Wireless sensor networks (WSNs) have shown their potentials in various applications, which bring a lot of benefits to users from both research and industrial areas. For many setups, it is envisioned thatWSNs will consist of tens to hundreds of nodes that operate on small batteries. However due to the diversity of the deployed environments and resource constraints on radio communication, sensing ability and energy supply, it is a very challenging issue to plan optimized WSN topology and predict its performance before real deployment. During the network planning phase, the connectivity, coverage, cost, network longevity and service quality should all be considered. Therefore it requires designers coping with comprehensive and interdisciplinary knowledge, including networking, radio engineering, embedded system and so on, in order to efficiently construct a reliable WSN for any specific types of environment. Nowadays there is still a lack of the analysis and experiences to guide WSN designers to efficiently construct WSN topology successfully without many trials. Therefore, simulation is a feasible approach to the quantitative analysis of the performance of wireless sensor networks. However the existing planning algorithms and tools, to some extent, have serious limitations to practically design reliable WSN topology: Only a few of them tackle the 3D deployment issue, and an overwhelming number of works are proposed to place devices in 2D scheme. Without considering the full dimension, the impacts of environment to the performance of WSN are not completely studied, thus the values of evaluated metrics such as connectivity and sensing coverage are not sufficiently accurate to make proper decision. Even fewer planning methods model the sensing coverage and radio propagation by considering the realistic scenario where obstacles exist. Radio signals propagate with multi-path phenomenon in the real world, in which direct paths, reflected paths and diffracted paths contribute to the received signal strength. Besides, obstacles between the path of sensor and objects might block the sensing signals, thus create coverage hole in the application. None of the existing planning algorithms model the network longevity and packet delivery capability properly and practically. They often employ unilateral and unrealistic formulations. The optimization targets are often one-sided in the current works. Without comprehensive evaluation on the important metrics, the performance of planned WSNs can not be reliable and entirely optimized. Modeling of environment is usually time consuming and the cost is very high, while none of the current works figure out any method to model the 3D deployment environment efficiently and accurately. Therefore many researchers are trapped by this issue, and their algorithms can only be evaluated in the same scenario, without the possibility to test the robustness and feasibility for implementations in different environments. In this thesis, we propose a novel planning methodology and an intelligent WSN planning tool to assist WSN designers efficiently planning reliable WSNs. First of all, a new method is proposed to efficiently and automatically model the 3D indoor and outdoor environments. To the best of our knowledge, this is the first time that the advantages of image understanding algorithm are applied to automatically reconstruct 3D outdoor and indoor scenarios for signal propagation and network planning purpose. The experimental results indicate that the proposed methodology is able to accurately recognize different objects from the satellite images of the outdoor target regions and from the scanned floor plan of indoor area. Its mechanism offers users a flexibility to reconstruct different types of environment without any human interaction. Thereby it significantly reduces human efforts, cost and time spent on reconstructing a 3D geographic database and allows WSN designers concentrating on the planning issues. Secondly, an efficient ray-tracing engine is developed to accurately and practically model the radio propagation and sensing signal on the constructed 3D map. The engine contributes on efficiency and accuracy to the estimated results. By using image processing concepts, including the kd-tree space division algorithm and modified polar sweep algorithm, the rays are traced efficiently without detecting all the primitives in the scene. The radio propagation model iv is proposed, which emphasizes not only the materials of obstacles but also their locations along the signal path. The sensing signal of sensor nodes, which is sensitive to the obstacles, is benefit from the ray-tracing algorithm via obstacle detection. The performance of this modelling method is robust and accurate compared with conventional methods, and experimental results imply that this methodology is suitable for both outdoor urban scenes and indoor environments. Moreover, it can be applied to either GSM communication or ZigBee protocol by varying frequency parameter of the radio propagation model. Thirdly, WSN planning method is proposed to tackle the above mentioned challenges and efficiently deploy reliable WSNs. More metrics (connectivity, coverage, cost, lifetime, packet latency and packet drop rate) are modeled more practically compared with other works. Especially 3D ray tracing method is used to model the radio link and sensing signal which are sensitive to the obstruction of obstacles; network routing is constructed by using AODV protocol; the network longevity, packet delay and packet drop rate are obtained via simulating practical events in WSNet simulator, which to the best of our knowledge, is the first time that network simulator is involved in a planning algorithm. Moreover, a multi-objective optimization algorithm is developed to cater for the characteristics of WSNs. The capability of providing multiple optimized solutions simultaneously allows users making their own decisions accordingly, and the results are more comprehensively optimized compared with other state-of-the-art algorithms. iMOST is developed by integrating the introduced algorithms, to assist WSN designers efficiently planning reliable WSNs for different configurations. The abbreviated name iMOST stands for an Intelligent Multi-objective Optimization Sensor network planning Tool. iMOST contributes on: (1) Convenient operation with a user-friendly vision system; (2) Efficient and automatic 3D database reconstruction and fast 3D objects design for both indoor and outdoor environments; (3) It provides multiple multi-objective optimized 3D deployment solutions and allows users to configure the network properties, hence it can adapt to various WSN applications; (4) Deployment solutions in the 3D space and the corresponding evaluated performance are visually presented to users; and (5) The Node Placement Module of iMOST is available online as well as the source code of the other two rebuilt heuristics. Therefore WSN designers will be benefit from v this tool on efficiently constructing environment database, practically and efficiently planning reliable WSNs for both outdoor and indoor applications. With the open source codes, they are also able to compare their developed algorithms with ours to contribute to this academic field. Finally, solid real results are obtained for both indoor and outdoor WSN planning. Deployments have been realized for both indoor and outdoor environments based on the provided planning solutions. The measured results coincide well with the estimated results. The proposed planning algorithm is adaptable according to the WSN designer’s desirability and configuration, and it offers flexibility to plan small and large scale, indoor and outdoor 3D deployments. The thesis is organized in 7 chapters. In Chapter 1, WSN applications and motivations of this work are introduced, the state-of-the-art planning algorithms and tools are reviewed, challenges are stated out and the proposed methodology is briefly introduced. In Chapter 2, the proposed 3D environment reconstruction methodology is introduced and its performance is evaluated for both outdoor and indoor environment. The developed ray-tracing engine and proposed radio propagation modelling method are described in details in Chapter 3, their performances are evaluated in terms of computation efficiency and accuracy. Chapter 4 presents the modelling of important metrics of WSNs and the proposed multi-objective optimization planning algorithm, the performance is compared with the other state-of-the-art planning algorithms. The intelligent WSN planning tool iMOST is described in Chapter 5. RealWSN deployments are prosecuted based on the planned solutions for both indoor and outdoor scenarios, important data are measured and results are analysed in Chapter 6. Chapter 7 concludes the thesis and discusses about future works. vi Resumen en Castellano Las redes de sensores inalámbricas (en inglés Wireless Sensor Networks, WSNs) han demostrado su potencial en diversas aplicaciones que aportan una gran cantidad de beneficios para el campo de la investigación y de la industria. Para muchas configuraciones se prevé que las WSNs consistirán en decenas o cientos de nodos que funcionarán con baterías pequeñas. Sin embargo, debido a la diversidad de los ambientes para desplegar las redes y a las limitaciones de recursos en materia de comunicación de radio, capacidad de detección y suministro de energía, la planificación de la topología de la red y la predicción de su rendimiento es un tema muy difícil de tratar antes de la implementación real. Durante la fase de planificación del despliegue de la red se deben considerar aspectos como la conectividad, la cobertura, el coste, la longevidad de la red y la calidad del servicio. Por lo tanto, requiere de diseñadores con un amplio e interdisciplinario nivel de conocimiento que incluye la creación de redes, la ingeniería de radio y los sistemas embebidos entre otros, con el fin de construir de manera eficiente una WSN confiable para cualquier tipo de entorno. Hoy en día todavía hay una falta de análisis y experiencias que orienten a los diseñadores de WSN para construir las topologías WSN de manera eficiente sin realizar muchas pruebas. Por lo tanto, la simulación es un enfoque viable para el análisis cuantitativo del rendimiento de las redes de sensores inalámbricos. Sin embargo, los algoritmos y herramientas de planificación existentes tienen, en cierta medida, serias limitaciones para diseñar en la práctica una topología fiable de WSN: Sólo unos pocos abordan la cuestión del despliegue 3D mientras que existe una gran cantidad de trabajos que colocan los dispositivos en 2D. Si no se analiza la dimensión completa (3D), los efectos del entorno en el desempeño de WSN no se estudian por completo, por lo que los valores de los parámetros evaluados, como la conectividad y la cobertura de detección, no son lo suficientemente precisos para tomar la decisión correcta. Aún en menor medida los métodos de planificación modelan la cobertura de los sensores y la propagación de la señal de radio teniendo en cuenta un escenario realista donde existan obstáculos. Las señales de radio en el mundo real siguen una propagación multicamino, en la que los caminos directos, los caminos reflejados y los caminos difractados contribuyen a la intensidad de la señal recibida. Además, los obstáculos entre el recorrido del sensor y los objetos pueden bloquear las señales de detección y por lo tanto crear áreas sin cobertura en la aplicación. Ninguno de los algoritmos de planificación existentes modelan el tiempo de vida de la red y la capacidad de entrega de paquetes correctamente y prácticamente. A menudo se emplean formulaciones unilaterales y poco realistas. Los objetivos de optimización son a menudo tratados unilateralmente en los trabajos actuales. Sin una evaluación exhaustiva de los parámetros importantes, el rendimiento previsto de las redes inalámbricas de sensores no puede ser fiable y totalmente optimizado. Por lo general, el modelado del entorno conlleva mucho tiempo y tiene un coste muy alto, pero ninguno de los trabajos actuales propone algún método para modelar el entorno de despliegue 3D con eficiencia y precisión. Por lo tanto, muchos investigadores están limitados por este problema y sus algoritmos sólo se pueden evaluar en el mismo escenario, sin la posibilidad de probar la solidez y viabilidad para las implementaciones en diferentes entornos. En esta tesis, se propone una nueva metodología de planificación así como una herramienta inteligente de planificación de redes de sensores inalámbricas para ayudar a los diseñadores a planificar WSNs fiables de una manera eficiente. En primer lugar, se propone un nuevo método para modelar demanera eficiente y automática los ambientes interiores y exteriores en 3D. Según nuestros conocimientos hasta la fecha, esta es la primera vez que las ventajas del algoritmo de _image understanding_se aplican para reconstruir automáticamente los escenarios exteriores e interiores en 3D para analizar la propagación de la señal y viii la planificación de la red. Los resultados experimentales indican que la metodología propuesta es capaz de reconocer con precisión los diferentes objetos presentes en las imágenes satelitales de las regiones objetivo en el exterior y de la planta escaneada en el interior. Su mecanismo ofrece a los usuarios la flexibilidad para reconstruir los diferentes tipos de entornos sin ninguna interacción humana. De este modo se reduce considerablemente el esfuerzo humano, el coste y el tiempo invertido en la reconstrucción de una base de datos geográfica con información 3D, permitiendo así que los diseñadores se concentren en los temas de planificación. En segundo lugar, se ha desarrollado un motor de trazado de rayos (en inglés ray tracing) eficiente para modelar con precisión la propagación de la señal de radio y la señal de los sensores en el mapa 3D construido. El motor contribuye a la eficiencia y la precisión de los resultados estimados. Mediante el uso de los conceptos de procesamiento de imágenes, incluyendo el algoritmo del árbol kd para la división del espacio y el algoritmo _polar sweep_modificado, los rayos se trazan de manera eficiente sin la detección de todas las primitivas en la escena. El modelo de propagación de radio que se propone no sólo considera los materiales de los obstáculos, sino también su ubicación a lo largo de la ruta de señal. La señal de los sensores de los nodos, que es sensible a los obstáculos, se ve beneficiada por la detección de objetos llevada a cabo por el algoritmo de trazado de rayos. El rendimiento de este método de modelado es robusto y preciso en comparación con los métodos convencionales, y los resultados experimentales indican que esta metodología es adecuada tanto para escenas urbanas al aire libre como para ambientes interiores. Por otra parte, se puede aplicar a cualquier comunicación GSM o protocolo ZigBee mediante la variación de la frecuencia del modelo de propagación de radio. En tercer lugar, se propone un método de planificación de WSNs para hacer frente a los desafíos mencionados anteriormente y desplegar redes de sensores fiables de manera eficiente. Se modelan más parámetros (conectividad, cobertura, coste, tiempo de vida, la latencia de paquetes y tasa de caída de paquetes) en comparación con otros trabajos. Especialmente el método de trazado de rayos 3D se utiliza para modelar el enlace de radio y señal de los sensores que son sensibles a la obstrucción de obstáculos; el enrutamiento de la red se construye utilizando el protocolo AODV; la longevidad de la red, retardo de paquetes ix y tasa de abandono de paquetes se obtienen a través de la simulación de eventos prácticos en el simulador WSNet, y según nuestros conocimientos hasta la fecha, es la primera vez que simulador de red está implicado en un algoritmo de planificación. Por otra parte, se ha desarrollado un algoritmo de optimización multi-objetivo para satisfacer las características de las redes inalámbricas de sensores. La capacidad de proporcionar múltiples soluciones optimizadas de forma simultánea permite a los usuarios tomar sus propias decisiones en consecuencia, obteniendo mejores resultados en comparación con otros algoritmos del estado del arte. iMOST se desarrolla mediante la integración de los algoritmos presentados, para ayudar de forma eficiente a los diseñadores en la planificación de WSNs fiables para diferentes configuraciones. El nombre abreviado iMOST (Intelligent Multi-objective Optimization Sensor network planning Tool) representa una herramienta inteligente de planificación de redes de sensores con optimización multi-objetivo. iMOST contribuye en: (1) Operación conveniente con una interfaz de fácil uso, (2) Reconstrucción eficiente y automática de una base de datos con información 3D y diseño rápido de objetos 3D para ambientes interiores y exteriores, (3) Proporciona varias soluciones de despliegue optimizadas para los multi-objetivo en 3D y permite a los usuarios configurar las propiedades de red, por lo que puede adaptarse a diversas aplicaciones de WSN, (4) las soluciones de implementación en el espacio 3D y el correspondiente rendimiento evaluado se presentan visualmente a los usuarios, y (5) El _Node Placement Module_de iMOST está disponible en línea, así como el código fuente de las otras dos heurísticas de planificación. Por lo tanto los diseñadores WSN se beneficiarán de esta herramienta para la construcción eficiente de la base de datos con información del entorno, la planificación práctica y eficiente de WSNs fiables tanto para aplicaciones interiores y exteriores. Con los códigos fuente abiertos, son capaces de comparar sus algoritmos desarrollados con los nuestros para contribuir a este campo académico. Por último, se obtienen resultados reales sólidos tanto para la planificación de WSN en interiores y exteriores. Los despliegues se han realizado tanto para ambientes de interior y como para ambientes de exterior utilizando las soluciones de planificación propuestas. Los resultados medidos coinciden en gran medida con los resultados estimados. El algoritmo de planificación x propuesto se adapta convenientemente al deiseño de redes de sensores inalámbricas, y ofrece flexibilidad para planificar los despliegues 3D a pequeña y gran escala tanto en interiores como en exteriores. La tesis se estructura en 7 capítulos. En el Capítulo 1, se presentan las aplicaciones de WSN y motivaciones de este trabajo, se revisan los algoritmos y herramientas de planificación del estado del arte, se presentan los retos y se describe brevemente la metodología propuesta. En el Capítulo 2, se presenta la metodología de reconstrucción de entornos 3D propuesta y su rendimiento es evaluado tanto para espacios exteriores como para espacios interiores. El motor de trazado de rayos desarrollado y el método de modelado de propagación de radio propuesto se describen en detalle en el Capítulo 3, evaluándose en términos de eficiencia computacional y precisión. En el Capítulo 4 se presenta el modelado de los parámetros importantes de las WSNs y el algoritmo de planificación de optimización multi-objetivo propuesto, el rendimiento se compara con los otros algoritmos de planificación descritos en el estado del arte. La herramienta inteligente de planificación de redes de sensores inalámbricas, iMOST, se describe en el Capítulo 5. En el Capítulo 6 se llevan a cabo despliegues reales de acuerdo a las soluciones previstas para los escenarios interiores y exteriores, se miden los datos importantes y se analizan los resultados. En el Capítulo 7 se concluye la tesis y se discute acerca de los trabajos futuros.

A simplified spectral approachfor impedance-based damage identification of frp-strengthened rc beams

Hoy en día, el refuerzo y reparación de estructuras de hormigón armado mediante el pegado de bandas de polímeros reforzados con fibras (FRP) se emplea cada vez con más frecuencia a causa de sus numerosas ventajas. Sin embargo, las vigas reforzadas con esta técnica pueden experimentar un modo de fallo frágil a causa del despegue repentino de la banda de FRP a partir de una fisura intermedia. A pesar de su importancia, el número de trabajos que abordan el estudio de este mecanismo de fallo y su monitorización es muy limitado. Por ello, el desarrollo de metodologías capaces de monitorizar a largo plazo la adherencia de este refuerzo a las estructuras de hormigón e identificar cuándo se inicia el despegue de la banda constituyen un importante desafío a abordar. El principal objetivo de esta tesis es la implementación de una metodología fiable y efectiva, capaz de detectar el despegue de una banda de FRP en una viga de hormigón armado a partir de una fisura intermedia. Para alcanzar este objetivo se ha implementado un procedimiento de calibración numérica a partir de ensayos experimentales. Para ello, en primer lugar, se ha desarrollado un modelo numérico unidimensional simple y no costoso representativo del comportamiento de este tipo vigas de hormigón reforzadas con FRP, basado en un modelo de fisura discreta para el hormigón y el método de elementos espectrales. La formación progresiva de fisuras a flexion y el consiguiente despegue en la interface entre el hormigón y el FRP se formulan mediante la introducción de un nuevo elemento capaz de representar ambos fenómenos simultáneamente sin afectar al procedimiento numérico. Además, con el modelo propuesto, se puede obtener de una forma sencilla la respuesta dinámica en altas frecuencias de este tipo de estructuras, lo cual puede hacer muy útil su uso como herramienta de diagnosis y detección del despegue en su fase inicial mediante una monitorización de la variación de las características dinámicas locales de la estructura. Un método de evaluación no destructivo muy prometedor para la monitorización local de las estructuras es el método de la impedancia usando sensores-actuadores piezoeléctricos (PZT). La impedancia eléctrica de los sensores PZT se puede relacionar con la impedancia mecánica de las estructuras donde se encuentran adheridos Ya que la impedancia mecánica de una estructura se verá afectada por su deterioro, se pueden implementar indicadores de daño mediante una comparación del espectro de admitancia (inversa de la impedancia) a lo largo de distintas etapas durante el periodo de servicio de una estructura. Cualquier cambio en el espectro se podría interpretar como una variación en la integridad de la estructura. La impedancia eléctrica se mide a altas frecuencias con lo cual esta metodología debería ser muy sensible a la detección de estados de daño incipiente local, tal como se desea en la aplicación de este trabajo. Se ha implementado un elemento espectral PZT-FRP como extensión del modelo previamente desarrollado, con el objetivo de poder calcular numéricamente la impedancia eléctrica de sensores PZT adheridos a bandas de FRP sobre una viga de hormigón armado. El modelo, combinado con medidas experimentales captadas mediante sensores PZT, se implementa en el marco de una metodología de calibración de modelos para detectar cuantitativamente el despegue en la interfase entre una banda de FRP y una viga de hormigón. El procedimiento de optimización se resuelve empleando el método del enjambre cooperativo con un algoritmo bagging. Los resultados muestran una gran aproximación en la estimación del daño para el problema propuesto. Adicionalmente, se ha desarrollado también un método adaptativo para el mallado de elementos espectrales con el objetivo de localizar las zonas dañadas a partir de los resultados experimentales, el cual contribuye a aumentar la robustez y efectividad del método propuesto a la hora de identificar daños incipientes en su aparición inicial. Finalmente, se ha llevado a cabo un procedimiento de optimización multi-objetivo para detectar el despegue inicial en una viga de hormigón a escala real reforzada con FRP a partir de las impedancias captadas con una red de sensores PZT instrumentada a lo largo de la longitud de la viga. Cada sensor aporta los datos para definir cada una de las funciones objetivo que definen el procedimiento. Combinando el modelo previo de elementos espectrales con un algoritmo PSO multi-objetivo el procedimiento de detección de daño resultante proporciona resultados satisfactorios considerando la escala de la estructura y todas las incertidumbres características ligadas a este proceso. Los resultados obtenidos prueban la viabilidad y capacidad de los métodos antes mencionados y también su potencial en aplicaciones reales. Abstract Nowadays, the external bonding of fibre reinforced polymer (FRP) plates or sheets is increasingly used for the strengthening and retrofitting of reinforced concrete (RC) structures due to its numerous advantages. However, this kind of strengthening often leads to brittle failure modes being the most dominant failure mode the debonding induced by an intermediate crack (IC). In spite of its importance, the number of studies regarding the IC debonding mechanism and bond health monitoring is very limited. Methodologies able to monitor the long-term efficiency of bonding and successfully identify the initiation of FRP debonding constitute a challenge to be met. The main purpose of this thesisis the implementation of a reliable and effective methodology of damage identification able to detect intermediate crack debonding in FRP-strengthened RC beams. To achieve this goal, a model updating procedure based on numerical simulations and experimental tests has been implemented. For it, firstly, a simple and non-expensive one-dimensional model based on the discrete crack approach for concrete and the spectral element method has been developed. The progressive formation of flexural cracks and subsequent concrete-FRP interfacial debonding is formulated by the introduction of a new element able to represent both phenomena simultaneously without perturbing the numerical procedure. Furthermore, with the proposed model, high frequency dynamic response for these kinds of structures can also be obtained in a very simple and non-expensive way, which makes this procedure very useful as a tool for diagnoses and detection of debonding in its initial stage by monitoring the change in local dynamic characteristics. One very promising active non-destructive evaluation method for local monitoring is impedance-based structural health monitoring(SHM)using piezoelectric ceramic (PZT) sensor-actuators. The electrical impedance of the PZT can be directly related to the mechanical impedance of the host structural component where the PZT transducers are attached. Since the structural mechanical impedance will be affected by the presence of structural damage, comparisons of admittance (inverse of impedance) spectra at various times during the service period of the structure can be used as damage indicator. Any change in the spectra might be an indication of a change in the structural integrity. The electrical impedance is measured at high frequencies with which this methodology appears to be very sensitive to incipient damage in structural systems as desired for our application. Abonded-PZT-FRP spectral beam element approach based on an extension of the previous discrete crack approach is implemented in the calculation of the electrical impedance of the PZT transducer bonded to the FRP plates of a RC beam. This approach in conjunction with the experimental measurements of PZT actuator-sensors mounted on the structure is used to present an updating methodology to quantitatively detect interfacial debonding between a FRP strip and the host RC structure. The updating procedure is solved by using an ensemble particle swarm optimization approach with abagging algorithm, and the results demonstrate a big improvement for the performance and accuracy of the damage detection in the proposed problem. Additionally, an adaptive strategy of spectral element mesh has been also developed to detect damage location with experimental results, which shows the robustness and effectiveness of the proposed method to identify initial and incipient damages at its early stage. Lastly, multi-objective optimization has been carried out to detect debonding damage in a real scale FRP-strengthened RC beam by using impedance signatures. A net of PZT sensors is distributed along the beam to construct impedance-based multiple objectives under gradually induced damage scenario. By combining the spectral element model presented previously and an ensemble multi-objective PSO algorithm, the implemented damage detection process yields satisfactory predictions considering the scale and uncertainties of the structure. The obtained results prove the feasibility and capability of the aforementioned methods and also their potentials in real engineering applications.

Design and control of multi-finger haptic devices for dexterous manipulation

En la interacción con el entorno que nos rodea durante nuestra vida diaria (utilizar un cepillo de dientes, abrir puertas, utilizar el teléfono móvil, etc.) y en situaciones profesionales (intervenciones médicas, procesos de producción, etc.), típicamente realizamos manipulaciones avanzadas que incluyen la utilización de los dedos de ambas manos. De esta forma el desarrollo de métodos de interacción háptica multi-dedo dan lugar a interfaces hombre-máquina más naturales y realistas. No obstante, la mayoría de interfaces hápticas disponibles en el mercado están basadas en interacciones con un solo punto de contacto; esto puede ser suficiente para la exploración o palpación del entorno pero no permite la realización de tareas más avanzadas como agarres. En esta tesis, se investiga el diseño mecánico, control y aplicaciones de dispositivos hápticos modulares con capacidad de reflexión de fuerzas en los dedos índice, corazón y pulgar del usuario. El diseño mecánico de la interfaz diseñada, ha sido optimizado con funciones multi-objetivo para conseguir una baja inercia, un amplio espacio de trabajo, alta manipulabilidad y reflexión de fuerzas superiores a 3 N en el espacio de trabajo. El ancho de banda y la rigidez del dispositivo se han evaluado mediante simulación y experimentación real. Una de las áreas más importantes en el diseño de estos dispositivos es el efector final, ya que es la parte que está en contacto con el usuario. Durante este trabajo se ha diseñado un dedal de bajo peso, adaptable a diferentes usuarios que, mediante la incorporación de sensores de contacto, permite estimar fuerzas normales y tangenciales durante la interacción con entornos reales y virtuales. Para el diseño de la arquitectura de control, se estudiaron los principales requisitos para estos dispositivos. Entre estos, cabe destacar la adquisición, procesado e intercambio a través de internet de numerosas señales de control e instrumentación; la computación de equaciones matemáticas incluyendo la cinemática directa e inversa, jacobiana, algoritmos de detección de agarres, etc. Todos estos componentes deben calcularse en tiempo real garantizando una frecuencia mínima de 1 KHz. Además, se describen sistemas para manipulación de precisión virtual y remota; así como el diseño de un método denominado "desacoplo cinemático iterativo" para computar la cinemática inversa de robots y la comparación con otros métodos actuales. Para entender la importancia de la interacción multimodal, se ha llevado a cabo un estudio para comprobar qué estímulos sensoriales se correlacionan con tiempos de respuesta más rápidos y de mayor precisión. Estos experimentos se desarrollaron en colaboración con neurocientíficos del instituto Technion Israel Institute of Technology. Comparando los tiempos de respuesta en la interacción unimodal (auditiva, visual y háptica) con combinaciones bimodales y trimodales de los mismos, se demuestra que el movimiento sincronizado de los dedos para generar respuestas de agarre se basa principalmente en la percepción háptica. La ventaja en el tiempo de procesamiento de los estímulos hápticos, sugiere que los entornos virtuales que incluyen esta componente sensorial generan mejores contingencias motoras y mejoran la credibilidad de los eventos. Se concluye que, los sistemas que incluyen percepción háptica dotan a los usuarios de más tiempo en las etapas cognitivas para rellenar información de forma creativa y formar una experiencia más rica. Una aplicación interesante de los dispositivos hápticos es el diseño de nuevos simuladores que permitan entrenar habilidades manuales en el sector médico. En colaboración con fisioterapeutas de Griffith University en Australia, se desarrolló un simulador que permite realizar ejercicios de rehabilitación de la mano. Las propiedades de rigidez no lineales de la articulación metacarpofalange del dedo índice se estimaron mediante la utilización del efector final diseñado. Estos parámetros, se han implementado en un escenario que simula el comportamiento de la mano humana y que permite la interacción háptica a través de esta interfaz. Las aplicaciones potenciales de este simulador están relacionadas con entrenamiento y educación de estudiantes de fisioterapia. En esta tesis, se han desarrollado nuevos métodos que permiten el control simultáneo de robots y manos robóticas en la interacción con entornos reales. El espacio de trabajo alcanzable por el dispositivo háptico, se extiende mediante el cambio de modo de control automático entre posición y velocidad. Además, estos métodos permiten reconocer el gesto del usuario durante las primeras etapas de aproximación al objeto para su agarre. Mediante experimentos de manipulación avanzada de objetos con un manipulador y diferentes manos robóticas, se muestra que el tiempo en realizar una tarea se reduce y que el sistema permite la realización de la tarea con precisión. Este trabajo, es el resultado de una colaboración con investigadores de Harvard BioRobotics Laboratory. ABSTRACT When we interact with the environment in our daily life (using a toothbrush, opening doors, using cell-phones, etc.), or in professional situations (medical interventions, manufacturing processes, etc.) we typically perform dexterous manipulations that involve multiple fingers and palm for both hands. Therefore, multi-Finger haptic methods can provide a realistic and natural human-machine interface to enhance immersion when interacting with simulated or remote environments. Most commercial devices allow haptic interaction with only one contact point, which may be sufficient for some exploration or palpation tasks but are not enough to perform advanced object manipulations such as grasping. In this thesis, I investigate the mechanical design, control and applications of a modular haptic device that can provide force feedback to the index, thumb and middle fingers of the user. The designed mechanical device is optimized with a multi-objective design function to achieve a low inertia, a large workspace, manipulability, and force-feedback of up to 3 N within the workspace; the bandwidth and rigidity for the device is assessed through simulation and real experimentation. One of the most important areas when designing haptic devices is the end-effector, since it is in contact with the user. In this thesis the design and evaluation of a thimble-like, lightweight, user-adaptable, and cost-effective device that incorporates four contact force sensors is described. This design allows estimation of the forces applied by a user during manipulation of virtual and real objects. The design of a real-time, modular control architecture for multi-finger haptic interaction is described. Requirements for control of multi-finger haptic devices are explored. Moreover, a large number of signals have to be acquired, processed, sent over the network and mathematical computations such as device direct and inverse kinematics, jacobian, grasp detection algorithms, etc. have to be calculated in Real Time to assure the required high fidelity for the haptic interaction. The Hardware control architecture has different modules and consists of an FPGA for the low-level controller and a RT controller for managing all the complex calculations (jacobian, kinematics, etc.); this provides a compact and scalable solution for the required high computation capabilities assuring a correct frequency rate for the control loop of 1 kHz. A set-up for dexterous virtual and real manipulation is described. Moreover, a new algorithm named the iterative kinematic decoupling method was implemented to solve the inverse kinematics of a robotic manipulator. In order to understand the importance of multi-modal interaction including haptics, a subject study was carried out to look for sensory stimuli that correlate with fast response time and enhanced accuracy. This experiment was carried out in collaboration with neuro-scientists from Technion Israel Institute of Technology. By comparing the grasping response times in unimodal (auditory, visual, and haptic) events with the response times in events with bimodal and trimodal combinations. It is concluded that in grasping tasks the synchronized motion of the fingers to generate the grasping response relies on haptic cues. This processing-speed advantage of haptic cues suggests that multimodalhaptic virtual environments are superior in generating motor contingencies, enhancing the plausibility of events. Applications that include haptics provide users with more time at the cognitive stages to fill in missing information creatively and form a richer experience. A major application of haptic devices is the design of new simulators to train manual skills for the medical sector. In collaboration with physical therapists from Griffith University in Australia, we developed a simulator to allow hand rehabilitation manipulations. First, the non-linear stiffness properties of the metacarpophalangeal joint of the index finger were estimated by using the designed end-effector; these parameters are implemented in a scenario that simulates the behavior of the human hand and that allows haptic interaction through the designed haptic device. The potential application of this work is related to educational and medical training purposes. In this thesis, new methods to simultaneously control the position and orientation of a robotic manipulator and the grasp of a robotic hand when interacting with large real environments are studied. The reachable workspace is extended by automatically switching between rate and position control modes. Moreover, the human hand gesture is recognized by reading the relative movements of the index, thumb and middle fingers of the user during the early stages of the approximation-to-the-object phase and then mapped to the robotic hand actuators. These methods are validated to perform dexterous manipulation of objects with a robotic manipulator, and different robotic hands. This work is the result of a research collaboration with researchers from the Harvard BioRobotics Laboratory. The developed experiments show that the overall task time is reduced and that the developed methods allow for full dexterity and correct completion of dexterous manipulations.

A multi-criteria optimization and decision-making approach for improvement of food engineering processes.

The objective of this study was to propose a multi-criteria optimization and decision-making technique to solve food engineering problems. This technique was demostrated using experimental data obtained on osmotic dehydratation of carrot cubes in a sodium chloride solution. The Aggregating Functions Approach, the Adaptive Random Search Algorithm, and the Penalty Functions Approach were used in this study to compute the initial set of non-dominated or Pareto-optimal solutions. Multiple non-linear regression analysis was performed on a set of experimental data in order to obtain particular multi-objective functions (responses), namely water loss, solute gain, rehydration ratio, three different colour criteria of rehydrated product, and sensory evaluation (organoleptic quality). Two multi-criteria decision-making approaches, the Analytic Hierarchy Process (AHP) and the Tabular Method (TM), were used simultaneously to choose the best alternative among the set of non-dominated solutions. The multi-criteria optimization and decision-making technique proposed in this study can facilitate the assessment of criteria weights, giving rise to a fairer, more consistent, and adequate final compromised solution or food process. This technique can be useful to food scientists in research and education, as well as to engineers involved in the improvement of a variety of food engineering processes.

Design of in-building wireless networks deployments using evolutionary algorithms

In this article, a novel approach to deal with the design of in-building wireless networks deployments is proposed. This approach known as MOQZEA (Multiobjective Quality Zone Based Evolutionary Algorithm) is a hybr id evolutionary algorithm adapted to use a novel fitness function, based on the definition of quality zones for the different objective functions considered. This approach is conceived to solve wireless network design problems without previous information of the required number of transmitters, considering simultaneously a high number of objective functions and optimizing multiple configuration parameters of the transmitters.

Optimización de aperturas mediante técnicas de algoritmos evolutivos

Los sistemas de imagen por ultrasonidos son hoy una herramienta indispensable en aplicaciones de diagnóstico en medicina y son cada vez más utilizados en aplicaciones industriales en el área de ensayos no destructivos. El array es el elemento primario de estos sistemas y su diseño determina las características de los haces que se pueden construir (forma y tamaño del lóbulo principal, de los lóbulos secundarios y de rejilla, etc.), condicionando la calidad de las imágenes que pueden conseguirse. En arrays regulares la distancia máxima entre elementos se establece en media longitud de onda para evitar la formación de artefactos. Al mismo tiempo, la resolución en la imagen de los objetos presentes en la escena aumenta con el tamaño total de la apertura, por lo que una pequeña mejora en la calidad de la imagen se traduce en un aumento significativo del número de elementos del transductor. Esto tiene, entre otras, las siguientes consecuencias: Problemas de fabricación de los arrays por la gran densidad de conexiones (téngase en cuenta que en aplicaciones típicas de imagen médica, el valor de la longitud de onda es de décimas de milímetro) Baja relación señal/ruido y, en consecuencia, bajo rango dinámico de las señales por el reducido tamaño de los elementos. Complejidad de los equipos que deben manejar un elevado número de canales independientes. Por ejemplo, se necesitarían 10.000 elementos separados λ 2 para una apertura cuadrada de 50 λ. Una forma sencilla para resolver estos problemas existen alternativas que reducen el número de elementos activos de un array pleno, sacrificando hasta cierto punto la calidad de imagen, la energía emitida, el rango dinámico, el contraste, etc. Nosotros planteamos una estrategia diferente, y es desarrollar una metodología de optimización capaz de hallar de forma sistemática configuraciones de arrays de ultrasonido adaptados a aplicaciones específicas. Para realizar dicha labor proponemos el uso de los algoritmos evolutivos para buscar y seleccionar en el espacio de configuraciones de arrays aquellas que mejor se adaptan a los requisitos fijados por cada aplicación. En la memoria se trata el problema de la codificación de las configuraciones de arrays para que puedan ser utilizados como individuos de la población sobre la que van a actuar los algoritmos evolutivos. También se aborda la definición de funciones de idoneidad que permitan realizar comparaciones entre dichas configuraciones de acuerdo con los requisitos y restricciones de cada problema de diseño. Finalmente, se propone emplear el algoritmo multiobjetivo NSGA II como herramienta primaria de optimización y, a continuación, utilizar algoritmos mono-objetivo tipo Simulated Annealing para seleccionar y retinar las soluciones proporcionadas por el NSGA II. Muchas de las funciones de idoneidad que definen las características deseadas del array a diseñar se calculan partir de uno o más patrones de radiación generados por cada solución candidata. La obtención de estos patrones con los métodos habituales de simulación de campo acústico en banda ancha requiere tiempos de cálculo muy grandes que pueden hacer inviable el proceso de optimización con algoritmos evolutivos en la práctica. Como solución, se propone un método de cálculo en banda estrecha que reduce en, al menos, un orden de magnitud el tiempo de cálculo necesario Finalmente se presentan una serie de ejemplos, con arrays lineales y bidimensionales, para validar la metodología de diseño propuesta comparando experimentalmente las características reales de los diseños construidos con las predicciones del método de optimización. ABSTRACT Currently, the ultrasound imaging system is one of the powerful tools in medical diagnostic and non-destructive testing for industrial applications. Ultrasonic arrays design determines the beam characteristics (main and secondary lobes, beam pattern, etc...) which assist to enhance the image resolution. The maximum distance between the elements of the array should be the half of the wavelength to avoid the formation of grating lobes. At the same time, the image resolution of the target in the region of interest increases with the aperture size. Consequently, the larger number of elements in arrays assures the better image quality but this improvement contains the following drawbacks: Difficulties in the arrays manufacturing due to the large connection density. Low noise to signal ratio. Complexity of the ultrasonic system to handle large number of channels. The easiest way to resolve these issues is to reduce the number of active elements in full arrays, but on the other hand the image quality, dynamic range, contrast, etc, are compromised by this solutions In this thesis, an optimization methodology able to find ultrasound array configurations adapted for specific applications is presented. The evolutionary algorithms are used to obtain the ideal arrays among the existing configurations. This work addressed problems such as: the codification of ultrasound arrays to be interpreted as individuals in the evolutionary algorithm population and the fitness function and constraints, which will assess the behaviour of individuals. Therefore, it is proposed to use the multi-objective algorithm NSGA-II as a primary optimization tool, and then use the mono-objective Simulated Annealing algorithm to select and refine the solutions provided by the NSGA I I . The acoustic field is calculated many times for each individual and in every generation for every fitness functions. An acoustic narrow band field simulator, where the number of operations is reduced, this ensures a quick calculation of the acoustic field to reduce the expensive computing time required by these functions we have employed. Finally a set of examples are presented in order to validate our proposed design methodology, using linear and bidimensional arrays where the actual characteristics of the design are compared with the predictions of the optimization methodology.

Diseño para fabricación digital: definición unívoca entre forma y fabricación en arquitectura

La presente investigación se inicia planteando el objetivo de identificar los parámetros geométricos que son exclusivos del proceso de generación de la Forma y relacionarlos con los invariantes relacionados con la Fabricación digital aplicada a la Arquitectura. Con ello se pretende recuperar la geometría como herramienta principal del proceso de Proyecto ampliando su ámbito de actuación al encontrar una relación con los procesos de fabricación digital. El primer capítulo describe los antecedentes y contexto histórico centrándose especialmente en la influencia de la capacidad de definir geometrías complejas digitalmente mediante la aplicación de algoritmos. En los primeros ejemplos la aproximación del Arquitecto a proyectos con geometrías complejas no euclídeas aún se emplea sin precisión en la comunicación de la geometría ideada para su puesta en obra. Las técnicas constructivas obligan a asumir una tolerancia de desviación entre proyecto y obra y la previsión del comportamiento de esa geometría no permite asegurar su comportamiento final. No será hasta la introducción de herramientas CAD en el proceso de ideación arquitectónica cuando el Arquitecto se capacite para generar geometrías no representables de forma analógica. Sin embargo, la imposibilidad de trasladar la geometría proyectada a la praxis constructiva impedirá la plasmación de un proceso completo, salvo en las contadas ocasiones que se recogen en este texto. “El análisis cronológico de las referencias establece como aspecto esencial para la construcción de geometrías complejas la capacidad primero para definir y comunicar de forma precisa e inequívoca la geometría y después la capacidad de analizar el desempeño prestacional de dicha propuesta geométrica”. La presente investigación se inicia planteando el objetivo de identificar los parámetros geométricos que son exclusivos del proceso de generación de la Forma y relacionarlos con los invariantes relacionados con la Fabricación digital aplicada a la Arquitectura. Con ello se pretende recuperar la geometría como herramienta principal del proceso de Proyecto ampliando su ámbito de actuación al encontrar una relación con los procesos de fabricación digital. El primer capítulo describe los antecedentes y contexto histórico centrándose especialmente en la influencia de la capacidad de definir geometrías complejas digitalmente mediante la aplicación de algoritmos. En los primeros ejemplos la aproximación del Arquitecto a proyectos con geometrías complejas no euclídeas aún se emplea sin precisión en la comunicación de la geometría ideada para su puesta en obra. Las técnicas constructivas obligan a asumir una tolerancia de desviación entre proyecto y obra y la previsión del comportamiento de esa geometría no permite asegurar su comportamiento final. No será hasta la introducción de herramientas CAD en el proceso de ideación arquitectónica cuando el Arquitecto se capacite para generar geometrías no representables de forma analógica. Sin embargo, la imposibilidad de trasladar la geometría proyectada a la praxis constructiva impedirá la plasmación de un proceso completo, salvo en las contadas ocasiones que se recogen en este texto. “El análisis cronológico de las referencias establece como aspecto esencial para la construcción de geometrías complejas la capacidad primero para definir y comunicar de forma precisa e inequívoca la geometría y después la capacidad de analizar el desempeño prestacional de dicha propuesta geométrica”. Establecida la primera conclusión, el capítulo de contexto histórico continúa enfocándose sobre la aplicación de las técnicas digitales en el Proceso de proyecto primero, y en la puesta en obra después. Los casos de estudio identifican claramente como un punto de inflexión para la generación de formas complejas mediante un software CAD el Museo Guggenheim de Bilbao en 1992. El motivo esencial para elegir este proyecto como el primer proyecto digital es el uso de la herramienta de definición digital de la geometría para su reproducción inequívoca en obra. “La revolución digital ha aportado al Arquitecto la posibilidad de abandonar las tipologías arquitectónicas basados en restricciones geométricas-constructivas. La aplicación de técnicas de fabricación digital ha permitido la capacidad de diseñar con independencia del sistema constructivo y libertad formal. En este nuevo contexto las prestaciones suponen los nuevos límites conceptuales, ya que el acceso y disposición de la información del comportamiento de las alternativas que cada geometría conlleva demanda del Arquitecto la jerarquización de los objetivos y la formulación en un conjunto coherente de parámetros”. Los proyectos que emplean herramientas digitales para la resolución de las distintas etapas del proceso proyectual se verán incrementados de forma exponencial desde 1992 hasta nuestros días. A pesar del importante auge de las técnicas de diseño asistido por ordenador el principal desafío sigue siendo la vinculación de las geometrías y materiales propuestos con las capacidades de las técnicas de manufactura y puesta en obra. El proceso de diseño para fabricación en un entorno digital es una tecnología madura en otras industrias como la aeroespacial o la automovilística, incluso la de productos de consumo y decoración, sin embargo en el sector de Construcción es un sistema inmaduro e inconexo. Las particularidades de la industria de la construcción aún no han sido abordadas en su totalidad y las propuestas de investigación realizadas en este ámbito se han centrado hasta 2015 en partes del proceso y no en el proceso total. “El principal obstáculo para la estandarización e implantación globalizada de un proceso digital desde el origen de la forma hasta la construcción es la inexistencia de un protocolo integrado que integre las limitaciones de fabricación, económicas y de puesta en obra junto a la evaluación de desempeño prestacional durante la fases iniciales de proyecto”. En el capítulo número 3 se estudian los distintos procesos de generación de la forma. Se propone una definición específica para el ámbito de la investigación de “forma” en el entendemos que se incluye la envolvente exterior y el conjunto organizativo de espacios interiores conectados. Por lo tanto no es excluyente del interior. El objetivo de este estudio es analizar y clasificar los procesos para la generación digital de formas en los distintos proyectos seleccionados como emblemáticos de cada tipología. Se concluye que la aproximación a este proceso es muy variada y compleja, con aplicación segregada y descoordinada entre los distintos agentes que han intervenir. En un proceso de generación formal analógico los parámetros que intervienen son en parte conscientes y en parte inconscientes o aprendidos. El Arquitecto sólo tiene control sobre la parte consciente de los parámetros a integrar en el diseño, de acuerdo a sus conocimientos y capacidades será capaz de manejar un número limitado de parámetros. La parte aprendida permanece en el inconsciente y dirige el proceso analógico, aportando prejuicios estéticos incorporados durante el proceso formativo y propio del entorno cultural. “El empleo de herramientas digitales basadas en la evaluación prestacional durante el proceso de selección formal permite al Arquitecto conocer “en tiempo real” el desempeño en el conjunto de prestaciones evaluadoras del conjunto de alternativas geométricas a la propuesta previamente definida por la intuición arquitectónica. El proceso definido no persigue identificar una solución óptima sino asistir al Arquitecto en el proceso de generación de la forma mediante la evaluación continua de los vectores direccionales más idóneos que el procedimiento generativo plantea”. La definición de complejidad en generación y producción de formas en relación con el proceso de diseño digital paramétrico global o integrado, es esencial para establecer un protocolo que optimice su gestión. “Se propone como definición de complejidad como factor resultante de multiplicar el número de agentes intervinientes por el número de parámetros e interacciones comunes que intervienen en el proceso de generación de la forma, dividido por la complejidad de intercambio de información digital desde el origen hasta la fase de fabricación y construcción”. Una vez analizados los procesos de generación digital de Arquitectura se propone identificar los parámetros geométricos que definen el proceso de Diseño digital, entendiendose por Diseño el proceso que engloba desde la proposición de una forma inicial basada en la intuición del Arquitecto, la generación y evaluación de variantes y posterior definición digital para producción, tanto de un objeto, un sistema o de la totalidad del Proyecto. En la actualidad el proceso de Diseño es discontinuo y lineal organizandose los parámetros por disciplinas en las que está estructurada las atribuciones profesionales en la industria de la construcción. Para simplificar la identificación y listado se han agrupado siguiendo estos grupos de conocimiento. Entendemos parametros invariables aquellos que son independientes de Tipologías arquitectónicas o que dependen del mismo proceso de generación de la Forma. “El listado de los parámetros que intervienen en un proceso de generación formal es una abstracción de una realidad compleja. La parametrización de las decisiones que intervienen en la selección de una forma determinada mediante “well defined problems” es imposible. El proceso que esta tesis describe entiende esta condición como un elemento que pone en valor el propio procedimiento generativo por la riqueza que la subjetividad que el equipo de diseño aporta”. La segunda parte esencial de esta investigación pretende extraer las restricciones propias del estado del arte de la fabricación digital para posteriormente incorporarlos en los procesos digitales de definición de la Forma arquitectónica. “La integración de las restricciones derivadas de las técnicas de fabricación y construcción digitales en el proceso de generación de formas desde el ámbito de la Arquitectura debe referirse a los condicionantes geométricos asociados a cada sistema constructivo, material y técnica de fabricación. La geometría es además el vínculo que permite asociar el conjunto de parámetros prestacionales seleccionados para un Proyecto con los sistemas de fabricación digital”. A estos condicionantes geométricos obtenidos del análisis de cada sistema de fabricación digital se les ha denominado “invariantes geométricos”. Bajo este término se engloban tanto límites dimensionales de fabricación, como materiales compatibles, tolerancias de manufactura e instalación y cualidades prestacionales asociadas. El objetivo de esta propuesta es emplear la geometría, herramienta fundamental y propia del Arquitecto, como nexo de unión entre el conjunto complejo y heterogéneo de parámetros previamente listados y analizados. Para ello se han simplificado en tablas específicas para cada parámetro prestacional los condicionantes geométricos que se derivan de los Sistemas de fabricación digital compatibles (ver apéndice 1). El estudio y evaluación de las capacidades y objetivos de las distintas plataformas de software disponibles y de las experiencias profesionales evaluadas en los proyectos presentados, permiten concluir que la propuesta de plataforma digital de diseño integral multi-paramétrico de formas arquitectónicas requiere de un protocolo de interoperatibilidad específico aún no universalmente establecido. Actualmente el enfoque de la estrategia para normalizar y universalizar el contexto normativo para regular la interoperatibilidad se centra en figura del gestor denominado “BIM manager”. Las atribuciones y roles de esta figura se enfocan a la gestión del continente y no del contenido (Definición de los formatos de intercambio, niveles de desarrollo (LOD) de los componentes o conjuntos constructivos, detección de interferencias y documentación del propio modelo). Siendo este ámbito un desarrollo necesario para la propuesta de universalización del sistema de diseño para fabricación digital integrado, la presente investigación aporta un organigrama y protocolo asociado. El protocolo: 1. Establece la responsabilidad de identificar y definir la Información que debe determinar el proceso de generación y desarrollo de la forma arquitectónica. 2. Define la forma digital apropiada para generar la geometría del Proyecto, incluyendo la precisión necesaria para cada componente y el nivel de detalle necesario para su exportación inequívoca al proceso de fabricación. 3. Define el tempo de cada etapa de diseño identificando un nivel de detalle acorde. 4. Acopla este organigrama dentro de las estructuras nuevas que se proponen en un entorno BIM para asegurar que no se producen solapes o vacíos con las atribuciones que se identifican para el BIM Manager. “El Arquitecto debe dirigir el protocolo de generación coordinada con los sistemas de producción digital para conseguir que la integración completa. El protocolo debe asistir al proceso de generación de forma mediante la evaluación del desempeño prestacional de cada variante en tiempo real. La comunicación entre herramientas digitales es esencial para permitir una ágil transmisión de información. Es necesario establecer un protocolo adaptado a los objetivos y las necesidades operativas de cada proyecto ya que la estandarización de un protocolo único no es posible”. Una decisión estratégica a la hora de planificar una plataforma de diseño digital común es establecer si vamos a optar por un Modelo digital único o diversos Modelos digitales federados. Cada uno de los modos de trabajo tiene fortalezas y debilidades, no obstante en el ámbito de investigación se ha concluido que un proceso integrado de Diseño que incorpore la evaluación prestacional y conceptual definida en el Capítulo 3, requiere necesariamente de varios modelos de software distintos que han de relacionarse entre sí mediante un protocolo de comunicación automatizado. Una plataforma basada en un modelo federado consiste en establecer un protocolo de comunicación entre los programas informáticos empleados por cada disciplina. En este modelo de operación cada equipo de diseño debe establecer las bases de comunicación en función del número y tipo de programas y procesos digitales a emplear. En esta investigación se propone un protocolo basado en los estándares de intercambio de información que estructura cualquier proceso de generación de forma paramétrico “La investigación establece el empleo de algoritmos evolutivos como el sistema actual óptimo para desarrollar un proceso de generación de formas basadas en la integración y coordinación de invariantes geométricos derivados de un conjunto de objetivos prestacionales y constructivos. No obstante, para la aplicación en el caso práctico realizado se ha podido verificar que la evaluación del desempeño aún no puede realizarse en una única herramienta y por lo tanto el proceso de selección de las variantes genéticas óptimas ha de ejecutarse de forma manual y acumulativa. El proceso debe realizarse de manera federada para la selección evolutiva de los invariantes geométricos dimensionales”. La evaluación del protocolo de integración y los condicionantes geométricos obtenidos como parámetros geométricos que controlan las posibles formas compatibles se realiza mediante su aplicación en un caso práctico. El ejercicio simula la colaboración multidisciplinar con modelos federados de plataformas distintas. La elección del tamaño y complejidad constructiva del proyecto se ha modulado para poder alcanzar un desarrollo completo de cada uno de los parámetros prestacionales seleccionados. Continuando con el mismo objetivo propuesto para los parámetros prestacionales, la tipología constructiva-estructural seleccionada para el ejercicio permite la aplicación la totalidad de invariantes geométricos asociados. El objetivo de este caso práctico es evaluar la capacidad alterar la forma inicialmente propuesta mediante la evaluación del desempeño prestacional de conjunto de variantes geométricas generadas a partir de un parámetro dimensional determinado. Para que este proceso tenga sentido, cada una de las variantes debe ser previamente validada conforme a las limitaciones geométricas propias de cada sistema de fabricación y montaje previstos. El interés de las conclusiones obtenidas es la identificación de una variante geométrica distante a la solución simétrica inicialmente como la solución óptima para el conjunto de parámetros seleccionados. Al tiempo se ha comprobado como la participación de un conjunto de parámetros multi-disciplinares que representan la realidad compleja de los objetivos arquitectónicos favorecen la aparición de variaciones genéticas con prestaciones mejoradas a la intuición inicial. “La herencias tipológicas suponen un límite para la imaginación de variantes formales al proceso de ideación arquitectónica. El ejercicio realizado demuestra que incluso en casos donde aparentemente la solución óptima aparenta ser obvia una variante aleatoria puede mejorar su desempeño global. La posibilidad de conocer las condiciones geométricas de las técnicas de fabricación digital compatibles con el conjunto de parámetros seleccionados por el Arquitecto para dirigir el proceso asegura que los resultados del algoritmo evolutivo empleado sean constructivamente viables. La mejora de imaginación humana con la aportación de geometrías realmente construibles supone el objetivo último de esta tesis”. ABSTRACT Architectural form generation process is shifting from analogical to digital. Digital technology has changed the way we design empowering Architects and Engineers to precisely define any complex geometry envisioned. At the same time, the construction industry, following aeronautical and automotive industries, is implementing digital manufacturing techniques to improve efficiency and quality. Consequently construction complexity will no longer be related to geometry complexity and it is associated to coordination with digital manufacturing capacities. Unfortunately it is agreed that non-standard geometries, even when proposed with performance optimization criteria, are only suitable for projects with non-restricted budgets. Furthemore, the lack of coordinated exportation protocol and geometry management between design and construction is avoiding the globalization of emergence process in built projects Present research first objective is to identify exclusive form-generation parameters related to digital manufacturing geometrical restraints. The intention was to use geometry as the form-generation tool and integrate the digital manufacturing capacities at first stages of the project. The first chapter of this text describes the investigation historical context focusing on the influence between accurate geometry definition at non-standard forms and its construction. At first examples of non-Euclidean geometries built the communication between design and construction were based on analogical partial and imprecise documentation. Deficient communication leads to geometry adaptation on site leaving the final form uncontrolled by the Architect. Computer Aided Design enable Architects to define univocally complex geometries that previously where impossible to communicate. “The univocally definition of the Form, and communication between design and construction is essential for complex geometry Projects”. The second chapter is focused on digital technologies application in form finding process and site construction. The case studies selected identifies a clear inflexion node at 1992 with the Guggenheim Museum in Bilbao. The singularity of this project was the use of Aeronautics software to define digitally the external envelope complex geometry to enable the contractor to build it. “The digital revolution has given the Architect the capacity to design buildings beyond the architectural archetypes driven by geometric-constructive limitations. The application of digital manufacturing techniques has enabled a free-form construction without geometrical limitations. In this new context performance shall be the responsible to set new conceptual boundaries, since the behavior of each possible geometry can be compare and analyze beforehand. The role of the Architect is to prioritize the performance and architectural objectives of each project in a complete and coherent set of parameters”. Projects using digital tools for solving various stages of the design process were increased exponentially since 1992 until today. Despite the significant rise of the techniques of computer-aided design the main challenge remains linking geometries and materials proposed at each design with the capabilities of digital manufacturing techniques. Design for manufacturing in a digital environment is a mature technology in other industries such as aerospace and automotive, including consumer products and decoration, but in the construction sector is an immature and disjointed system. The peculiarities of the construction industry have not yet been addressed in its entirety and research proposals made in this area until 2015 have focused in separate parts of the process and not the total process. “The main obstacle to global standardization and implementation of a complete digital process from the form-finding to construction site is the lack of an integrated protocol that integrates manufacturing, economic and commissioning limitations, together with the performance evaluation of each possible form”. The different form generation processes are studied at chapter number 3. At the introduction of this chapter there is a specific definition of "form" for the research field. Form is identified with the outer envelope geometry, including the organizational set of connected indoor spaces connected to it. Therefore it is not exclusive of the interior. The aim of this study is to analyze and classify the main digital form generation processes using different selected projects as emblematic of each type. The approach to this process is complex, with segregated and uncoordinated different actors have to intervene application. In an analogical form-generation process parameters involved are partly conscious and partly unconscious or learned. The architect has control only over limited part of the parameters to be integrated into the design, according to their knowledge and. There is also a learned aesthetical prejudice that leads the form generation process to a specific geometry leaving the performance and optimization criteria apart from the decision making process. “Using performance evaluation digital tools during form finding process provides real-time comparative information to the Architect enabling geometry selection based on its performance. The generative form generation process described at this document does not ambition to identify the optimum geometry for each set of parameters. The objective is to provide quick information at each generation of what direction is most favorable for the performance parameters selected”. Manufacturing complexity definition in relation to a global and integral process of digital design for manufacture is essential for establishing an efficient managing protocol. “The definition of complexity associated to design for production in Architecture is proposed as the factor between number of different agents involved in the process by the number of interactions required between them, divided by the percentage of the interchange of information that is standardized and proof of information loss”. Design in architecture is a multi-objective process by definition. Therefore, addressing generation process linked to a set of non-coherent parameters requires the selection of adequate generative algorithm and the interaction of the architect. During the second half of the twentieth century and early twenty-first century it have been developed various mathematical algorithms for multi-parametric digital design. Heuristic algorithms are the most adequate algorithms for architectural projects due to its nature. The advantage of such algorithms is the ability to efficiently handle large scale optimization cases where a large number of design objectives and variables are involved. These generative processes do not pursue the optimum solution, in fact it will be impossible to proof with such algorithm. This is not a problem in architectural design where the final goal is to guide the form finding process towards a better performance within the initial direction provided by the architect. This research has focused on genetic algorithms due to its capacity to generate geometric alternatives in multiple directions and evaluate the fitness against a set of parameters specified in a single process. "Any protocol seeks to achieve standardization. The design to manufacturing protocol aims to provide a coordinated and coherent form generation process between a set of design parameters and the geometrical requirements of manufacturing technique. The protocol also provides an information exchange environment where there is a communication path and the level of information is ensured. The research is focused on the process because it is considered that each project will have its own singularities and parameters but the process will stay the same. Again the development of a specific tool is not a goal for the research, the intention is to provide an open source protocol that is valid for any set of tools”. Once the digital generation processes are being analized and classified, the next step is to identify the geometric parameters that define the digital design process. The definition of design process is including from the initial shape proposal based on the intuition of the architect to the generation, evaluation, selection and production of alternatives, both of an object , system or of the entire project . The current design process in Architecture is discontinuous and linear, dividing the process in disciplines in which the construction industry is structured. The proposal is to unify all relevant parameters in one process. The parameters are listed in groups of knowledge for internal classification but the matrix used for parameter relationship determination are combined. “A multi-parameter determination of the form-finding process is the integration all the measurable decisions laying behind Architect intuition. It is not possible to formulate and solve with an algorithm the design in Architecture. It is not the intention to do so with the proposal of this research. The process aims to integrate in one open protocol a selection of parameters by using geometry as common language. There is no optimum solution for any step of the process, the outcome is an evaluation of performance of all the form variations to assist the Architect for the selection of the preferable solution for the project”. The research follows with the geometrical restrictions of today Digital manufacturing techniques. Once determined it has been integrated in the form-finding process. “Digital manufacturing techniques are integrated in the form-finding process using geometry as common language. Geometric restraints define the boundary for performance parametric form-finding process. Geometrical limitations are classified by material and constructive system”. Choose between one digital model or several federate models is a strategic decision at planning a digital design for manufacturing protocol. Each one of the working models have strengths and weakens, nevertheless for the research purposes federated models are required to manage the different performance evaluation software platforms. A protocol based on federated models shall establish a communication process between software platforms and consultants. The manager shall integrate each discipline requirements defining the communication basis. The proposed protocol is based on standards on information exchange with singularities of the digital manufacturing industry. “The research concludes evolutionary algorithms as current best system to develop a generative form finding process based on the integration and coordination of a set of performance and constructive objectives. However, for application in professional practice and standardize it, the performance evaluation cannot be done in only one tool and therefore the selection of optimal genetic variants must be run in several iterations with a cumulative result. Consequently, the evaluation process within the geometrical restraints shall be carried out with federated models coordinated following the information exchange protocol”. The integration protocol and geometric constraints evaluation is done by applying in a practical case study. The exercise simulates multidisciplinary collaboration across software platforms with federated models. The choice of size and construction complexity of the project has been modulated to achieve the full development of each of the parameters selected. Continuing with the same objective proposed for the performance parameters the constructive and structural type selected for the exercise allows the application all geometric invariants associated to the set of parameters selected. The main goal of the case study is to proof the capacity of the manufacturing integrated form finding process to generate geometric alternatives to initial form with performance improved and following the restrictions determined by the compatible digital manufacturing technologies. The process is to be divided in consecutive analysis each one limited by the geometrical conditions and integrated in a overall evaluation. The interest of this process is the result of a non-intuitive form that performs better than a double symmetrical form. The second conclusion is that one parameter evaluation alone will not justify the exploration of complex geometry variations, but when there is a set of parameters with multidisciplinary approach then the less obvious solution emerge as the better performing form. “Architectural typologies impose limitation for Architects capacity to imagine formal variations. The case study and the research conclusions proof that even in situations where the intuitive solution apparently is the optimum solution, random variations can perform better when integrating all parameters evaluation. The capacity of foreseing the geometrical properties linking each design parameter with compatible manufacturing technologies ensure the result of the form-finding process to be constructively viable. Finally, the propose of a complete process where the geometry alternatives are generated beyond the Architect intuition and performance evaluated by a set of parameters previously selected and coordinated with the manufacturing requirements is the final objective of the Thesis”.

Aerodynamic Optimization of the Nose Shape of a High-speed Train

La influencia de la aerodinámica en el diseño de los trenes de alta velocidad, unida a la necesidad de resolver nuevos problemas surgidos con el aumento de la velocidad de circulación y la reducción de peso del vehículo, hace evidente el interés de plantear un estudio de optimización que aborde tales puntos. En este contexto, se presenta en esta tesis la optimización aerodinámica del testero de un tren de alta velocidad, llevada a cabo mediante el uso de métodos de optimización avanzados. Entre estos métodos, se ha elegido aquí a los algoritmos genéticos y al método adjunto como las herramientas para llevar a cabo dicha optimización. La base conceptual, las características y la implementación de los mismos se detalla a lo largo de la tesis, permitiendo entender los motivos de su elección, y las consecuencias, en términos de ventajas y desventajas que cada uno de ellos implican. El uso de los algorimos genéticos implica a su vez la necesidad de una parametrización geométrica de los candidatos a óptimo y la generación de un modelo aproximado que complementa al método de optimización. Estos puntos se describen de modo particular en el primer bloque de la tesis, enfocada a la metodología seguida en este estudio. El segundo bloque se centra en la aplicación de los métodos a fin de optimizar el comportamiento aerodinámico del tren en distintos escenarios. Estos escenarios engloban los casos más comunes y también algunos de los más exigentes a los que hace frente un tren de alta velocidad: circulación en campo abierto con viento frontal o viento lateral, y entrada en túnel. Considerando el caso de viento frontal en campo abierto, los dos métodos han sido aplicados, permitiendo una comparación de las diferentes metodologías, así como el coste computacional asociado a cada uno, y la minimización de la resistencia aerodinámica conseguida en esa optimización. La posibilidad de evitar parametrizar la geometría y, por tanto, reducir el coste computacional del proceso de optimización es la característica más significativa de los métodos adjuntos, mientras que en el caso de los algoritmos genéticos se destaca la simplicidad y capacidad de encontrar un óptimo global en un espacio de diseño multi-modal o de resolver problemas multi-objetivo. El caso de viento lateral en campo abierto considera nuevamente los dos métoxi dos de optimización anteriores. La parametrización se ha simplificado en este estudio, lo que notablemente reduce el coste numérico de todo el estudio de optimización, a la vez que aún recoge las características geométricas más relevantes en un tren de alta velocidad. Este análisis ha permitido identificar y cuantificar la influencia de cada uno de los parámetros geométricos incluídos en la parametrización, y se ha observado que el diseño de la arista superior a barlovento es fundamental, siendo su influencia mayor que la longitud del testero o que la sección frontal del mismo. Finalmente, se ha considerado un escenario más a fin de validar estos métodos y su capacidad de encontrar un óptimo global. La entrada de un tren de alta velocidad en un túnel es uno de los casos más exigentes para un tren por el pico de sobrepresión generado, el cual afecta a la confortabilidad del pasajero, así como a la estabilidad del vehículo y al entorno próximo a la salida del túnel. Además de este problema, otro objetivo a minimizar es la resistencia aerodinámica, notablemente superior al caso de campo abierto. Este problema se resuelve usando algoritmos genéticos. Dicho método permite obtener un frente de Pareto donde se incluyen el conjunto de óptimos que minimizan ambos objetivos. ABSTRACT Aerodynamic design of trains influences several aspects of high-speed trains performance in a very significant level. In this situation, considering also that new aerodynamic problems have arisen due to the increase of the cruise speed and lightness of the vehicle, it is evident the necessity of proposing an optimization study concerning the train aerodynamics. Thus, the aerodynamic optimization of the nose shape of a high-speed train is presented in this thesis. This optimization is based on advanced optimization methods. Among these methods, genetic algorithms and the adjoint method have been selected. A theoretical description of their bases, the characteristics and the implementation of each method is detailed in this thesis. This introduction permits understanding the causes of their selection, and the advantages and drawbacks of their application. The genetic algorithms requirethe geometrical parameterization of any optimal candidate and the generation of a metamodel or surrogate model that complete the optimization process. These points are addressed with a special attention in the first block of the thesis, focused on the methodology considered in this study. The second block is referred to the use of these methods with the purpose of optimizing the aerodynamic performance of a high-speed train in several scenarios. These scenarios englobe the most representative operating conditions of high-speed trains, and also some of the most exigent train aerodynamic problems: front wind and cross-wind situations in open air, and the entrance of a high-speed train in a tunnel. The genetic algorithms and the adjoint method have been applied in the minimization of the aerodynamic drag on the train with front wind in open air. The comparison of these methods allows to evaluate the methdology and computational cost of each one, as well as the resulting minimization of the aerodynamic drag. Simplicity and robustness, the straightforward realization of a multi-objective optimization, and the capability of searching a global optimum are the main attributes of genetic algorithm. However, the requirement of geometrically parameterize any optimal candidate is a significant drawback that is avoided with the use of the adjoint method. This independence of the number of design variables leads to a relevant reduction of the pre-processing and computational cost. Considering the cross-wind stability, both methods are used again for the minimization of the side force. In this case, a simplification of the geometric parameterization of the train nose is adopted, what dramatically reduces the computational cost of the optimization process. Nevertheless, some of the most important geometrical characteristics are still described with this simplified parameterization. This analysis identifies and quantifies the influence of each design variable on the side force on the train. It is observed that the A-pillar roundness is the most demanding design parameter, with a more important effect than the nose length or the train cross-section area. Finally, a third scenario is considered for the validation of these methods in the aerodynamic optimization of a high-speed train. The entrance of a train in a tunnel is one of the most exigent train aerodynamic problems. The aerodynamic consequences of high-speed trains running in a tunnel are basically resumed in two correlated phenomena, the generation of pressure waves and an increase in aerodynamic drag. This multi-objective optimization problem is solved with genetic algorithms. The result is a Pareto front where a set of optimal solutions that minimize both objectives.

Development of Shape-Optimization Tools for the Aerodynamic Design of Turbomachinery Blades

The aim of this work is to develop an automated tool for the optimization of turbomachinery blades founded on an evolutionary strategy. This optimization scheme will serve to deal with supersonic blades cascades for application to Organic Rankine Cycle (ORC) turbines. The blade geometry is defined using parameterization techniques based on B-Splines curves, that allow to have a local control of the shape. The location in space of the control points of the B-Spline curve define the design variables of the optimization problem. In the present work, the performance of the blade shape is assessed by means of fully-turbulent flow simulations performed with a CFD package, in which a look-up table method is applied to ensure an accurate thermodynamic treatment. The solver is set along with the optimization tool to determine the optimal shape of the blade. As only blade-to-blade effects are of interest in this study, quasi-3D calculations are performed, and a single-objective evolutionary strategy is applied to the optimization. As a result, a non-intrusive tool, with no need for gradients definition, is developed. The computational cost is reduced by the use of surrogate models. A Gaussian interpolation scheme (Kriging model) is applied for the estimated n-dimensional function, and a surrogate-based local optimization strategy is proved to yield an accurate way for optimization. In particular, the present optimization scheme has been applied to the re-design of a supersonic stator cascade of an axial-flow turbine. In this design exercise very strong shock waves are generated in the rear blade suction side and shock-boundary layer interaction mechanisms occur. A significant efficiency improvement as a consequence of a more uniform flow at the blade outlet section of the stator is achieved. This is also expected to provide beneficial effects on the design of a subsequent downstream rotor. The method provides an improvement to gradient-based methods and an optimized blade geometry is easily achieved using the genetic algorithm.

Parametric and structural self-adaptation of embedded systems using evolvable hardware

Los sistemas empotrados han sido concebidos tradicionalmente como sistemas de procesamiento específicos que realizan una tarea fija durante toda su vida útil. Para cumplir con requisitos estrictos de coste, tamaño y peso, el equipo de diseño debe optimizar su funcionamiento para condiciones muy específicas. Sin embargo, la demanda de mayor versatilidad, un funcionamiento más inteligente y, en definitiva, una mayor capacidad de procesamiento comenzaron a chocar con estas limitaciones, agravado por la incertidumbre asociada a entornos de operación cada vez más dinámicos donde comenzaban a ser desplegados progresivamente. Esto trajo como resultado una necesidad creciente de que los sistemas pudieran responder por si solos a eventos inesperados en tiempo diseño tales como: cambios en las características de los datos de entrada y el entorno del sistema en general; cambios en la propia plataforma de cómputo, por ejemplo debido a fallos o defectos de fabricación; y cambios en las propias especificaciones funcionales causados por unos objetivos del sistema dinámicos y cambiantes. Como consecuencia, la complejidad del sistema aumenta, pero a cambio se habilita progresivamente una capacidad de adaptación autónoma sin intervención humana a lo largo de la vida útil, permitiendo que tomen sus propias decisiones en tiempo de ejecución. Éstos sistemas se conocen, en general, como sistemas auto-adaptativos y tienen, entre otras características, las de auto-configuración, auto-optimización y auto-reparación. Típicamente, la parte soft de un sistema es mayoritariamente la única utilizada para proporcionar algunas capacidades de adaptación a un sistema. Sin embargo, la proporción rendimiento/potencia en dispositivos software como microprocesadores en muchas ocasiones no es adecuada para sistemas empotrados. En este escenario, el aumento resultante en la complejidad de las aplicaciones está siendo abordado parcialmente mediante un aumento en la complejidad de los dispositivos en forma de multi/many-cores; pero desafortunadamente, esto hace que el consumo de potencia también aumente. Además, la mejora en metodologías de diseño no ha sido acorde como para poder utilizar toda la capacidad de cómputo disponible proporcionada por los núcleos. Por todo ello, no se están satisfaciendo adecuadamente las demandas de cómputo que imponen las nuevas aplicaciones. La solución tradicional para mejorar la proporción rendimiento/potencia ha sido el cambio a unas especificaciones hardware, principalmente usando ASICs. Sin embargo, los costes de un ASIC son altamente prohibitivos excepto en algunos casos de producción en masa y además la naturaleza estática de su estructura complica la solución a las necesidades de adaptación. Los avances en tecnologías de fabricación han hecho que la FPGA, una vez lenta y pequeña, usada como glue logic en sistemas mayores, haya crecido hasta convertirse en un dispositivo de cómputo reconfigurable de gran potencia, con una cantidad enorme de recursos lógicos computacionales y cores hardware empotrados de procesamiento de señal y de propósito general. Sus capacidades de reconfiguración han permitido combinar la flexibilidad propia del software con el rendimiento del procesamiento en hardware, lo que tiene la potencialidad de provocar un cambio de paradigma en arquitectura de computadores, pues el hardware no puede ya ser considerado más como estático. El motivo es que como en el caso de las FPGAs basadas en tecnología SRAM, la reconfiguración parcial dinámica (DPR, Dynamic Partial Reconfiguration) es posible. Esto significa que se puede modificar (reconfigurar) un subconjunto de los recursos computacionales en tiempo de ejecución mientras el resto permanecen activos. Además, este proceso de reconfiguración puede ser ejecutado internamente por el propio dispositivo. El avance tecnológico en dispositivos hardware reconfigurables se encuentra recogido bajo el campo conocido como Computación Reconfigurable (RC, Reconfigurable Computing). Uno de los campos de aplicación más exóticos y menos convencionales que ha posibilitado la computación reconfigurable es el conocido como Hardware Evolutivo (EHW, Evolvable Hardware), en el cual se encuentra enmarcada esta tesis. La idea principal del concepto consiste en convertir hardware que es adaptable a través de reconfiguración en una entidad evolutiva sujeta a las fuerzas de un proceso evolutivo inspirado en el de las especies biológicas naturales, que guía la dirección del cambio. Es una aplicación más del campo de la Computación Evolutiva (EC, Evolutionary Computation), que comprende una serie de algoritmos de optimización global conocidos como Algoritmos Evolutivos (EA, Evolutionary Algorithms), y que son considerados como algoritmos universales de resolución de problemas. En analogía al proceso biológico de la evolución, en el hardware evolutivo el sujeto de la evolución es una población de circuitos que intenta adaptarse a su entorno mediante una adecuación progresiva generación tras generación. Los individuos pasan a ser configuraciones de circuitos en forma de bitstreams caracterizados por descripciones de circuitos reconfigurables. Seleccionando aquellos que se comportan mejor, es decir, que tienen una mejor adecuación (o fitness) después de ser evaluados, y usándolos como padres de la siguiente generación, el algoritmo evolutivo crea una nueva población hija usando operadores genéticos como la mutación y la recombinación. Según se van sucediendo generaciones, se espera que la población en conjunto se aproxime a la solución óptima al problema de encontrar una configuración del circuito adecuada que satisfaga las especificaciones. El estado de la tecnología de reconfiguración después de que la familia de FPGAs XC6200 de Xilinx fuera retirada y reemplazada por las familias Virtex a finales de los 90, supuso un gran obstáculo para el avance en hardware evolutivo; formatos de bitstream cerrados (no conocidos públicamente); dependencia de herramientas del fabricante con soporte limitado de DPR; una velocidad de reconfiguración lenta; y el hecho de que modificaciones aleatorias del bitstream pudieran resultar peligrosas para la integridad del dispositivo, son algunas de estas razones. Sin embargo, una propuesta a principios de los años 2000 permitió mantener la investigación en el campo mientras la tecnología de DPR continuaba madurando, el Circuito Virtual Reconfigurable (VRC, Virtual Reconfigurable Circuit). En esencia, un VRC en una FPGA es una capa virtual que actúa como un circuito reconfigurable de aplicación específica sobre la estructura nativa de la FPGA que reduce la complejidad del proceso reconfiguración y aumenta su velocidad (comparada con la reconfiguración nativa). Es un array de nodos computacionales especificados usando descripciones HDL estándar que define recursos reconfigurables ad-hoc: multiplexores de rutado y un conjunto de elementos de procesamiento configurables, cada uno de los cuales tiene implementadas todas las funciones requeridas, que pueden seleccionarse a través de multiplexores tal y como ocurre en una ALU de un microprocesador. Un registro grande actúa como memoria de configuración, por lo que la reconfiguración del VRC es muy rápida ya que tan sólo implica la escritura de este registro, el cual controla las señales de selección del conjunto de multiplexores. Sin embargo, esta capa virtual provoca: un incremento de área debido a la implementación simultánea de cada función en cada nodo del array más los multiplexores y un aumento del retardo debido a los multiplexores, reduciendo la frecuencia de funcionamiento máxima. La naturaleza del hardware evolutivo, capaz de optimizar su propio comportamiento computacional, le convierten en un buen candidato para avanzar en la investigación sobre sistemas auto-adaptativos. Combinar un sustrato de cómputo auto-reconfigurable capaz de ser modificado dinámicamente en tiempo de ejecución con un algoritmo empotrado que proporcione una dirección de cambio, puede ayudar a satisfacer los requisitos de adaptación autónoma de sistemas empotrados basados en FPGA. La propuesta principal de esta tesis está por tanto dirigida a contribuir a la auto-adaptación del hardware de procesamiento de sistemas empotrados basados en FPGA mediante hardware evolutivo. Esto se ha abordado considerando que el comportamiento computacional de un sistema puede ser modificado cambiando cualquiera de sus dos partes constitutivas: una estructura hard subyacente y un conjunto de parámetros soft. De esta distinción, se derivan dos lineas de trabajo. Por un lado, auto-adaptación paramétrica, y por otro auto-adaptación estructural. El objetivo perseguido en el caso de la auto-adaptación paramétrica es la implementación de técnicas de optimización evolutiva complejas en sistemas empotrados con recursos limitados para la adaptación paramétrica online de circuitos de procesamiento de señal. La aplicación seleccionada como prueba de concepto es la optimización para tipos muy específicos de imágenes de los coeficientes de los filtros de transformadas wavelet discretas (DWT, DiscreteWavelet Transform), orientada a la compresión de imágenes. Por tanto, el objetivo requerido de la evolución es una compresión adaptativa y más eficiente comparada con los procedimientos estándar. El principal reto radica en reducir la necesidad de recursos de supercomputación para el proceso de optimización propuesto en trabajos previos, de modo que se adecúe para la ejecución en sistemas empotrados. En cuanto a la auto-adaptación estructural, el objetivo de la tesis es la implementación de circuitos auto-adaptativos en sistemas evolutivos basados en FPGA mediante un uso eficiente de sus capacidades de reconfiguración nativas. En este caso, la prueba de concepto es la evolución de tareas de procesamiento de imagen tales como el filtrado de tipos desconocidos y cambiantes de ruido y la detección de bordes en la imagen. En general, el objetivo es la evolución en tiempo de ejecución de tareas de procesamiento de imagen desconocidas en tiempo de diseño (dentro de un cierto grado de complejidad). En este caso, el objetivo de la propuesta es la incorporación de DPR en EHW para evolucionar la arquitectura de un array sistólico adaptable mediante reconfiguración cuya capacidad de evolución no había sido estudiada previamente. Para conseguir los dos objetivos mencionados, esta tesis propone originalmente una plataforma evolutiva que integra un motor de adaptación (AE, Adaptation Engine), un motor de reconfiguración (RE, Reconfiguration Engine) y un motor computacional (CE, Computing Engine) adaptable. El el caso de adaptación paramétrica, la plataforma propuesta está caracterizada por: • un CE caracterizado por un núcleo de procesamiento hardware de DWT adaptable mediante registros reconfigurables que contienen los coeficientes de los filtros wavelet • un algoritmo evolutivo como AE que busca filtros wavelet candidatos a través de un proceso de optimización paramétrica desarrollado específicamente para sistemas caracterizados por recursos de procesamiento limitados • un nuevo operador de mutación simplificado para el algoritmo evolutivo utilizado, que junto con un mecanismo de evaluación rápida de filtros wavelet candidatos derivado de la literatura actual, asegura la viabilidad de la búsqueda evolutiva asociada a la adaptación de wavelets. En el caso de adaptación estructural, la plataforma propuesta toma la forma de: • un CE basado en una plantilla de array sistólico reconfigurable de 2 dimensiones compuesto de nodos de procesamiento reconfigurables • un algoritmo evolutivo como AE que busca configuraciones candidatas del array usando un conjunto de funcionalidades de procesamiento para los nodos disponible en una biblioteca accesible en tiempo de ejecución • un RE hardware que explota la capacidad de reconfiguración nativa de las FPGAs haciendo un uso eficiente de los recursos reconfigurables del dispositivo para cambiar el comportamiento del CE en tiempo de ejecución • una biblioteca de elementos de procesamiento reconfigurables caracterizada por bitstreams parciales independientes de la posición, usados como el conjunto de configuraciones disponibles para los nodos de procesamiento del array Las contribuciones principales de esta tesis se pueden resumir en la siguiente lista: • Una plataforma evolutiva basada en FPGA para la auto-adaptación paramétrica y estructural de sistemas empotrados compuesta por un motor computacional (CE), un motor de adaptación (AE) evolutivo y un motor de reconfiguración (RE). Esta plataforma se ha desarrollado y particularizado para los casos de auto-adaptación paramétrica y estructural. • En cuanto a la auto-adaptación paramétrica, las contribuciones principales son: – Un motor computacional adaptable mediante registros que permite la adaptación paramétrica de los coeficientes de una implementación hardware adaptativa de un núcleo de DWT. – Un motor de adaptación basado en un algoritmo evolutivo desarrollado específicamente para optimización numérica, aplicada a los coeficientes de filtros wavelet en sistemas empotrados con recursos limitados. – Un núcleo IP de DWT auto-adaptativo en tiempo de ejecución para sistemas empotrados que permite la optimización online del rendimiento de la transformada para compresión de imágenes en entornos específicos de despliegue, caracterizados por tipos diferentes de señal de entrada. – Un modelo software y una implementación hardware de una herramienta para la construcción evolutiva automática de transformadas wavelet específicas. • Por último, en cuanto a la auto-adaptación estructural, las contribuciones principales son: – Un motor computacional adaptable mediante reconfiguración nativa de FPGAs caracterizado por una plantilla de array sistólico en dos dimensiones de nodos de procesamiento reconfigurables. Es posible mapear diferentes tareas de cómputo en el array usando una biblioteca de elementos sencillos de procesamiento reconfigurables. – Definición de una biblioteca de elementos de procesamiento apropiada para la síntesis autónoma en tiempo de ejecución de diferentes tareas de procesamiento de imagen. – Incorporación eficiente de la reconfiguración parcial dinámica (DPR) en sistemas de hardware evolutivo, superando los principales inconvenientes de propuestas previas como los circuitos reconfigurables virtuales (VRCs). En este trabajo también se comparan originalmente los detalles de implementación de ambas propuestas. – Una plataforma tolerante a fallos, auto-curativa, que permite la recuperación funcional online en entornos peligrosos. La plataforma ha sido caracterizada desde una perspectiva de tolerancia a fallos: se proponen modelos de fallo a nivel de CLB y de elemento de procesamiento, y usando el motor de reconfiguración, se hace un análisis sistemático de fallos para un fallo en cada elemento de procesamiento y para dos fallos acumulados. – Una plataforma con calidad de filtrado dinámica que permite la adaptación online a tipos de ruido diferentes y diferentes comportamientos computacionales teniendo en cuenta los recursos de procesamiento disponibles. Por un lado, se evolucionan filtros con comportamientos no destructivos, que permiten esquemas de filtrado en cascada escalables; y por otro, también se evolucionan filtros escalables teniendo en cuenta requisitos computacionales de filtrado cambiantes dinámicamente. Este documento está organizado en cuatro partes y nueve capítulos. La primera parte contiene el capítulo 1, una introducción y motivación sobre este trabajo de tesis. A continuación, el marco de referencia en el que se enmarca esta tesis se analiza en la segunda parte: el capítulo 2 contiene una introducción a los conceptos de auto-adaptación y computación autonómica (autonomic computing) como un campo de investigación más general que el muy específico de este trabajo; el capítulo 3 introduce la computación evolutiva como la técnica para dirigir la adaptación; el capítulo 4 analiza las plataformas de computación reconfigurables como la tecnología para albergar hardware auto-adaptativo; y finalmente, el capítulo 5 define, clasifica y hace un sondeo del campo del hardware evolutivo. Seguidamente, la tercera parte de este trabajo contiene la propuesta, desarrollo y resultados obtenidos: mientras que el capítulo 6 contiene una declaración de los objetivos de la tesis y la descripción de la propuesta en su conjunto, los capítulos 7 y 8 abordan la auto-adaptación paramétrica y estructural, respectivamente. Finalmente, el capítulo 9 de la parte 4 concluye el trabajo y describe caminos de investigación futuros. ABSTRACT Embedded systems have traditionally been conceived to be specific-purpose computers with one, fixed computational task for their whole lifetime. Stringent requirements in terms of cost, size and weight forced designers to highly optimise their operation for very specific conditions. However, demands for versatility, more intelligent behaviour and, in summary, an increased computing capability began to clash with these limitations, intensified by the uncertainty associated to the more dynamic operating environments where they were progressively being deployed. This brought as a result an increasing need for systems to respond by themselves to unexpected events at design time, such as: changes in input data characteristics and system environment in general; changes in the computing platform itself, e.g., due to faults and fabrication defects; and changes in functional specifications caused by dynamically changing system objectives. As a consequence, systems complexity is increasing, but in turn, autonomous lifetime adaptation without human intervention is being progressively enabled, allowing them to take their own decisions at run-time. This type of systems is known, in general, as selfadaptive, and are able, among others, of self-configuration, self-optimisation and self-repair. Traditionally, the soft part of a system has mostly been so far the only place to provide systems with some degree of adaptation capabilities. However, the performance to power ratios of software driven devices like microprocessors are not adequate for embedded systems in many situations. In this scenario, the resulting rise in applications complexity is being partly addressed by rising devices complexity in the form of multi and many core devices; but sadly, this keeps on increasing power consumption. Besides, design methodologies have not been improved accordingly to completely leverage the available computational power from all these cores. Altogether, these factors make that the computing demands new applications pose are not being wholly satisfied. The traditional solution to improve performance to power ratios has been the switch to hardware driven specifications, mainly using ASICs. However, their costs are highly prohibitive except for some mass production cases and besidesthe static nature of its structure complicates the solution to the adaptation needs. The advancements in fabrication technologies have made that the once slow, small FPGA used as glue logic in bigger systems, had grown to be a very powerful, reconfigurable computing device with a vast amount of computational logic resources and embedded, hardened signal and general purpose processing cores. Its reconfiguration capabilities have enabled software-like flexibility to be combined with hardware-like computing performance, which has the potential to cause a paradigm shift in computer architecture since hardware cannot be considered as static anymore. This is so, since, as is the case with SRAMbased FPGAs, Dynamic Partial Reconfiguration (DPR) is possible. This means that subsets of the FPGA computational resources can now be changed (reconfigured) at run-time while the rest remains active. Besides, this reconfiguration process can be triggered internally by the device itself. This technological boost in reconfigurable hardware devices is actually covered under the field known as Reconfigurable Computing. One of the most exotic fields of application that Reconfigurable Computing has enabled is the known as Evolvable Hardware (EHW), in which this dissertation is framed. The main idea behind the concept is turning hardware that is adaptable through reconfiguration into an evolvable entity subject to the forces of an evolutionary process, inspired by that of natural, biological species, that guides the direction of change. It is yet another application of the field of Evolutionary Computation (EC), which comprises a set of global optimisation algorithms known as Evolutionary Algorithms (EAs), considered as universal problem solvers. In analogy to the biological process of evolution, in EHW the subject of evolution is a population of circuits that tries to get adapted to its surrounding environment by progressively getting better fitted to it generation after generation. Individuals become circuit configurations representing bitstreams that feature reconfigurable circuit descriptions. By selecting those that behave better, i.e., with a higher fitness value after being evaluated, and using them as parents of the following generation, the EA creates a new offspring population by using so called genetic operators like mutation and recombination. As generations succeed one another, the whole population is expected to approach to the optimum solution to the problem of finding an adequate circuit configuration that fulfils system objectives. The state of reconfiguration technology after Xilinx XC6200 FPGA family was discontinued and replaced by Virtex families in the late 90s, was a major obstacle for advancements in EHW; closed (non publicly known) bitstream formats; dependence on manufacturer tools with highly limiting support of DPR; slow speed of reconfiguration; and random bitstream modifications being potentially hazardous for device integrity, are some of these reasons. However, a proposal in the first 2000s allowed to keep investigating in this field while DPR technology kept maturing, the Virtual Reconfigurable Circuit (VRC). In essence, a VRC in an FPGA is a virtual layer acting as an application specific reconfigurable circuit on top of an FPGA fabric that reduces the complexity of the reconfiguration process and increases its speed (compared to native reconfiguration). It is an array of computational nodes specified using standard HDL descriptions that define ad-hoc reconfigurable resources; routing multiplexers and a set of configurable processing elements, each one containing all the required functions, which are selectable through functionality multiplexers as in microprocessor ALUs. A large register acts as configuration memory, so VRC reconfiguration is very fast given it only involves writing this register, which drives the selection signals of the set of multiplexers. However, large overheads are introduced by this virtual layer; an area overhead due to the simultaneous implementation of every function in every node of the array plus the multiplexers, and a delay overhead due to the multiplexers, which also reduces maximum frequency of operation. The very nature of Evolvable Hardware, able to optimise its own computational behaviour, makes it a good candidate to advance research in self-adaptive systems. Combining a selfreconfigurable computing substrate able to be dynamically changed at run-time with an embedded algorithm that provides a direction for change, can help fulfilling requirements for autonomous lifetime adaptation of FPGA-based embedded systems. The main proposal of this thesis is hence directed to contribute to autonomous self-adaptation of the underlying computational hardware of FPGA-based embedded systems by means of Evolvable Hardware. This is tackled by considering that the computational behaviour of a system can be modified by changing any of its two constituent parts: an underlying hard structure and a set of soft parameters. Two main lines of work derive from this distinction. On one side, parametric self-adaptation and, on the other side, structural self-adaptation. The goal pursued in the case of parametric self-adaptation is the implementation of complex evolutionary optimisation techniques in resource constrained embedded systems for online parameter adaptation of signal processing circuits. The application selected as proof of concept is the optimisation of Discrete Wavelet Transforms (DWT) filters coefficients for very specific types of images, oriented to image compression. Hence, adaptive and improved compression efficiency, as compared to standard techniques, is the required goal of evolution. The main quest lies in reducing the supercomputing resources reported in previous works for the optimisation process in order to make it suitable for embedded systems. Regarding structural self-adaptation, the thesis goal is the implementation of self-adaptive circuits in FPGA-based evolvable systems through an efficient use of native reconfiguration capabilities. In this case, evolution of image processing tasks such as filtering of unknown and changing types of noise and edge detection are the selected proofs of concept. In general, evolving unknown image processing behaviours (within a certain complexity range) at design time is the required goal. In this case, the mission of the proposal is the incorporation of DPR in EHW to evolve a systolic array architecture adaptable through reconfiguration whose evolvability had not been previously checked. In order to achieve the two stated goals, this thesis originally proposes an evolvable platform that integrates an Adaptation Engine (AE), a Reconfiguration Engine (RE) and an adaptable Computing Engine (CE). In the case of parametric adaptation, the proposed platform is characterised by: • a CE featuring a DWT hardware processing core adaptable through reconfigurable registers that holds wavelet filters coefficients • an evolutionary algorithm as AE that searches for candidate wavelet filters through a parametric optimisation process specifically developed for systems featured by scarce computing resources • a new, simplified mutation operator for the selected EA, that together with a fast evaluation mechanism of candidate wavelet filters derived from existing literature, assures the feasibility of the evolutionary search involved in wavelets adaptation In the case of structural adaptation, the platform proposal takes the form of: • a CE based on a reconfigurable 2D systolic array template composed of reconfigurable processing nodes • an evolutionary algorithm as AE that searches for candidate configurations of the array using a set of computational functionalities for the nodes available in a run time accessible library • a hardware RE that exploits native DPR capabilities of FPGAs and makes an efficient use of the available reconfigurable resources of the device to change the behaviour of the CE at run time • a library of reconfigurable processing elements featured by position-independent partial bitstreams used as the set of available configurations for the processing nodes of the array Main contributions of this thesis can be summarised in the following list. • An FPGA-based evolvable platform for parametric and structural self-adaptation of embedded systems composed of a Computing Engine, an evolutionary Adaptation Engine and a Reconfiguration Engine. This platform is further developed and tailored for both parametric and structural self-adaptation. • Regarding parametric self-adaptation, main contributions are: – A CE adaptable through reconfigurable registers that enables parametric adaptation of the coefficients of an adaptive hardware implementation of a DWT core. – An AE based on an Evolutionary Algorithm specifically developed for numerical optimisation applied to wavelet filter coefficients in resource constrained embedded systems. – A run-time self-adaptive DWT IP core for embedded systems that allows for online optimisation of transform performance for image compression for specific deployment environments characterised by different types of input signals. – A software model and hardware implementation of a tool for the automatic, evolutionary construction of custom wavelet transforms. • Lastly, regarding structural self-adaptation, main contributions are: – A CE adaptable through native FPGA fabric reconfiguration featured by a two dimensional systolic array template of reconfigurable processing nodes. Different processing behaviours can be automatically mapped in the array by using a library of simple reconfigurable processing elements. – Definition of a library of such processing elements suited for autonomous runtime synthesis of different image processing tasks. – Efficient incorporation of DPR in EHW systems, overcoming main drawbacks from the previous approach of virtual reconfigurable circuits. Implementation details for both approaches are also originally compared in this work. – A fault tolerant, self-healing platform that enables online functional recovery in hazardous environments. The platform has been characterised from a fault tolerance perspective: fault models at FPGA CLB level and processing elements level are proposed, and using the RE, a systematic fault analysis for one fault in every processing element and for two accumulated faults is done. – A dynamic filtering quality platform that permits on-line adaptation to different types of noise and different computing behaviours considering the available computing resources. On one side, non-destructive filters are evolved, enabling scalable cascaded filtering schemes; and on the other, size-scalable filters are also evolved considering dynamically changing computational filtering requirements. This dissertation is organized in four parts and nine chapters. First part contains chapter 1, the introduction to and motivation of this PhD work. Following, the reference framework in which this dissertation is framed is analysed in the second part: chapter 2 features an introduction to the notions of self-adaptation and autonomic computing as a more general research field to the very specific one of this work; chapter 3 introduces evolutionary computation as the technique to drive adaptation; chapter 4 analyses platforms for reconfigurable computing as the technology to hold self-adaptive hardware; and finally chapter 5 defines, classifies and surveys the field of Evolvable Hardware. Third part of the work follows, which contains the proposal, development and results obtained: while chapter 6 contains an statement of the thesis goals and the description of the proposal as a whole, chapters 7 and 8 address parametric and structural self-adaptation, respectively. Finally, chapter 9 in part 4 concludes the work and describes future research paths.

Automated wordlength optimization framework for multi-source statistical interval-based analysis of nonlinear systems with control-flow structures

El uso de aritmética de punto fijo es una opción de diseño muy extendida en sistemas con fuertes restricciones de área, consumo o rendimiento. Para producir implementaciones donde los costes se minimicen sin impactar negativamente en la precisión de los resultados debemos llevar a cabo una asignación cuidadosa de anchuras de palabra. Encontrar la combinación óptima de anchuras de palabra en coma fija para un sistema dado es un problema combinatorio NP-hard al que los diseñadores dedican entre el 25 y el 50 % del ciclo de diseño. Las plataformas hardware reconfigurables, como son las FPGAs, también se benefician de las ventajas que ofrece la aritmética de coma fija, ya que éstas compensan las frecuencias de reloj más bajas y el uso más ineficiente del hardware que hacen estas plataformas respecto a los ASICs. A medida que las FPGAs se popularizan para su uso en computación científica los diseños aumentan de tamaño y complejidad hasta llegar al punto en que no pueden ser manejados eficientemente por las técnicas actuales de modelado de señal y ruido de cuantificación y de optimización de anchura de palabra. En esta Tesis Doctoral exploramos distintos aspectos del problema de la cuantificación y presentamos nuevas metodologías para cada uno de ellos: Las técnicas basadas en extensiones de intervalos han permitido obtener modelos de propagación de señal y ruido de cuantificación muy precisos en sistemas con operaciones no lineales. Nosotros llevamos esta aproximación un paso más allá introduciendo elementos de Multi-Element Generalized Polynomial Chaos (ME-gPC) y combinándolos con una técnica moderna basada en Modified Affine Arithmetic (MAA) estadístico para así modelar sistemas que contienen estructuras de control de flujo. Nuestra metodología genera los distintos caminos de ejecución automáticamente, determina las regiones del dominio de entrada que ejercitarán cada uno de ellos y extrae los momentos estadísticos del sistema a partir de dichas soluciones parciales. Utilizamos esta técnica para estimar tanto el rango dinámico como el ruido de redondeo en sistemas con las ya mencionadas estructuras de control de flujo y mostramos la precisión de nuestra aproximación, que en determinados casos de uso con operadores no lineales llega a tener tan solo una desviación del 0.04% con respecto a los valores de referencia obtenidos mediante simulación. Un inconveniente conocido de las técnicas basadas en extensiones de intervalos es la explosión combinacional de términos a medida que el tamaño de los sistemas a estudiar crece, lo cual conlleva problemas de escalabilidad. Para afrontar este problema presen tamos una técnica de inyección de ruidos agrupados que hace grupos con las señales del sistema, introduce las fuentes de ruido para cada uno de los grupos por separado y finalmente combina los resultados de cada uno de ellos. De esta forma, el número de fuentes de ruido queda controlado en cada momento y, debido a ello, la explosión combinatoria se minimiza. También presentamos un algoritmo de particionado multi-vía destinado a minimizar la desviación de los resultados a causa de la pérdida de correlación entre términos de ruido con el objetivo de mantener los resultados tan precisos como sea posible. La presente Tesis Doctoral también aborda el desarrollo de metodologías de optimización de anchura de palabra basadas en simulaciones de Monte-Cario que se ejecuten en tiempos razonables. Para ello presentamos dos nuevas técnicas que exploran la reducción del tiempo de ejecución desde distintos ángulos: En primer lugar, el método interpolativo aplica un interpolador sencillo pero preciso para estimar la sensibilidad de cada señal, y que es usado después durante la etapa de optimización. En segundo lugar, el método incremental gira en torno al hecho de que, aunque es estrictamente necesario mantener un intervalo de confianza dado para los resultados finales de nuestra búsqueda, podemos emplear niveles de confianza más relajados, lo cual deriva en un menor número de pruebas por simulación, en las etapas iniciales de la búsqueda, cuando todavía estamos lejos de las soluciones optimizadas. Mediante estas dos aproximaciones demostramos que podemos acelerar el tiempo de ejecución de los algoritmos clásicos de búsqueda voraz en factores de hasta x240 para problemas de tamaño pequeño/mediano. Finalmente, este libro presenta HOPLITE, una infraestructura de cuantificación automatizada, flexible y modular que incluye la implementación de las técnicas anteriores y se proporciona de forma pública. Su objetivo es ofrecer a desabolladores e investigadores un entorno común para prototipar y verificar nuevas metodologías de cuantificación de forma sencilla. Describimos el flujo de trabajo, justificamos las decisiones de diseño tomadas, explicamos su API pública y hacemos una demostración paso a paso de su funcionamiento. Además mostramos, a través de un ejemplo sencillo, la forma en que conectar nuevas extensiones a la herramienta con las interfaces ya existentes para poder así expandir y mejorar las capacidades de HOPLITE. ABSTRACT Using fixed-point arithmetic is one of the most common design choices for systems where area, power or throughput are heavily constrained. In order to produce implementations where the cost is minimized without negatively impacting the accuracy of the results, a careful assignment of word-lengths is required. The problem of finding the optimal combination of fixed-point word-lengths for a given system is a combinatorial NP-hard problem to which developers devote between 25 and 50% of the design-cycle time. Reconfigurable hardware platforms such as FPGAs also benefit of the advantages of fixed-point arithmetic, as it compensates for the slower clock frequencies and less efficient area utilization of the hardware platform with respect to ASICs. As FPGAs become commonly used for scientific computation, designs constantly grow larger and more complex, up to the point where they cannot be handled efficiently by current signal and quantization noise modelling and word-length optimization methodologies. In this Ph.D. Thesis we explore different aspects of the quantization problem and we present new methodologies for each of them: The techniques based on extensions of intervals have allowed to obtain accurate models of the signal and quantization noise propagation in systems with non-linear operations. We take this approach a step further by introducing elements of MultiElement Generalized Polynomial Chaos (ME-gPC) and combining them with an stateof- the-art Statistical Modified Affine Arithmetic (MAA) based methodology in order to model systems that contain control-flow structures. Our methodology produces the different execution paths automatically, determines the regions of the input domain that will exercise them, and extracts the system statistical moments from the partial results. We use this technique to estimate both the dynamic range and the round-off noise in systems with the aforementioned control-flow structures. We show the good accuracy of our approach, which in some case studies with non-linear operators shows a 0.04 % deviation respect to the simulation-based reference values. A known drawback of the techniques based on extensions of intervals is the combinatorial explosion of terms as the size of the targeted systems grows, which leads to scalability problems. To address this issue we present a clustered noise injection technique that groups the signals in the system, introduces the noise terms in each group independently and then combines the results at the end. In this way, the number of noise sources in the system at a given time is controlled and, because of this, the combinato rial explosion is minimized. We also present a multi-way partitioning algorithm aimed at minimizing the deviation of the results due to the loss of correlation between noise terms, in order to keep the results as accurate as possible. This Ph.D. Thesis also covers the development of methodologies for word-length optimization based on Monte-Carlo simulations in reasonable times. We do so by presenting two novel techniques that explore the reduction of the execution times approaching the problem in two different ways: First, the interpolative method applies a simple but precise interpolator to estimate the sensitivity of each signal, which is later used to guide the optimization effort. Second, the incremental method revolves on the fact that, although we strictly need to guarantee a certain confidence level in the simulations for the final results of the optimization process, we can do it with more relaxed levels, which in turn implies using a considerably smaller amount of samples, in the initial stages of the process, when we are still far from the optimized solution. Through these two approaches we demonstrate that the execution time of classical greedy techniques can be accelerated by factors of up to ×240 for small/medium sized problems. Finally, this book introduces HOPLITE, an automated, flexible and modular framework for quantization that includes the implementation of the previous techniques and is provided for public access. The aim is to offer a common ground for developers and researches for prototyping and verifying new techniques for system modelling and word-length optimization easily. We describe its work flow, justifying the taken design decisions, explain its public API and we do a step-by-step demonstration of its execution. We also show, through an example, the way new extensions to the flow should be connected to the existing interfaces in order to expand and improve the capabilities of HOPLITE.

Bio-inspired FPGA Architecture for Self-Calibration of an Image Compression Core based on Wavelet Transforms in Embedded Systems

A generic bio-inspired adaptive architecture for image compression suitable to be implemented in embedded systems is presented. The architecture allows the system to be tuned during its calibration phase. An evolutionary algorithm is responsible of making the system evolve towards the required performance. A prototype has been implemented in a Xilinx Virtex-5 FPGA featuring an adaptive wavelet transform core directed at improving image compression for specific types of images. An Evolution Strategy has been chosen as the search algorithm and its typical genetic operators adapted to allow for a hardware friendly implementation. HW/SW partitioning issues are also considered after a high level description of the algorithm is profiled which validates the proposed resource allocation in the device fabric. To check the robustness of the system and its adaptation capabilities, different types of images have been selected as validation patterns. A direct application of such a system is its deployment in an unknown environment during design time, letting the calibration phase adjust the system parameters so that it performs efcient image compression. Also, this prototype implementation may serve as an accelerator for the automatic design of evolved transform coefficients which are later on synthesized and implemented in a non-adaptive system in the final implementation device, whether it is a HW or SW based computing device. The architecture has been built in a modular way so that it can be easily extended to adapt other types of image processing cores. Details on this pluggable component point of view are also given in the paper.

Evolvable 2D computing matrix model for intrinsic evolution in commercial FPGAs with native reconfiguration support

This paper addresses the modelling and validation of an evolvable hardware architecture which can be mapped on a 2D systolic structure implemented on commercial reconfigurable FPGAs. The adaptation capabilities of the architecture are exercised to validate its evolvability. The underlying proposal is the use of a library of reconfigurable components characterised by their partial bitstreams, which are used by the Evolutionary Algorithm to find a solution to a given task. Evolution of image noise filters is selected as the proof of concept application. Results show that computation speed of the resulting evolved circuit is higher than with the Virtual Reconfigurable Circuits approach, and this can be exploited on the evolution process by using dynamic reconfiguration

Fault Tolerance Analysis and Self-Healing Strategy of Autonomous, Evolvable Hardware Systems

This paper presents an analysis of the fault tolerance achieved by an autonomous, fully embedded evolvable hardware system, which uses a combination of partial dynamic reconfiguration and an evolutionary algorithm (EA). It demonstrates that the system may self-recover from both transient and cumulative permanent faults. This self-adaptive system, based on a 2D array of 16 (4×4) Processing Elements (PEs), is tested with an image filtering application. Results show that it may properly recover from faults in up to 3 PEs, that is, more than 18% cumulative permanent faults. Two fault models are used for testing purposes, at PE and CLB levels. Two self-healing strategies are also introduced, depending on whether fault diagnosis is available or not. They are based on scrubbing, fitness evaluation, dynamic partial reconfiguration and in-system evolutionary adaptation. Since most of these adaptability features are already available on the system for its normal operation, resource cost for self-healing is very low (only some code additions in the internal microprocessor core)

Dynamic Response Optimization of Vehicles through Efficient Multibody Formulations and Automatic Differentiation Techniques

El diseño y desarrollo de sistemas de suspensión para vehículos se basa cada día más en el diseño por ordenador y en herramientas de análisis por ordenador, las cuales permiten anticipar problemas y resolverlos por adelantado. El comportamiento y las características dinámicas se calculan con precisión, bajo coste, y recursos y tiempos de cálculo reducidos. Sin embargo, existe una componente iterativa en el proceso, que requiere la definición manual de diseños a través de técnicas “prueba y error”. Esta Tesis da un paso hacia el desarrollo de un entorno de simulación eficiente capaz de simular, analizar y evaluar diseños de suspensiones vehiculares, y de mejorarlos hacia la solución optima mediante la modificación de los parámetros de diseño. La modelización mediante sistemas multicuerpo se utiliza aquí para desarrollar un modelo de autocar con 18 grados de libertad, de manera detallada y eficiente. La geometría y demás características de la suspensión se ajustan a las del vehículo real, así como los demás parámetros del modelo. Para simular la dinámica vehicular, se utiliza una formulación multicuerpo moderna y eficiente basada en las ecuaciones de Maggi, a la que se ha incorporado un visor 3D. Así, se consigue simular maniobras vehiculares en tiempos inferiores al tiempo real. Una vez que la dinámica está disponible, los análisis de sensibilidad son cruciales para una optimización robusta y eficiente. Para ello, se presenta una técnica matemática que permite derivar las variables dinámicas dentro de la formulación, de forma algorítmica, general, con la precisión de la maquina, y razonablemente eficiente: la diferenciación automática. Este método propaga las derivadas con respecto a las variables de diseño a través del código informático y con poca intervención del usuario. En contraste con otros enfoques en la bibliografía, generalmente particulares y limitados, se realiza una comparación de librerías, se desarrolla una formulación híbrida directa-automática para el cálculo de sensibilidades, y se presentan varios ejemplos reales. Finalmente, se lleva a cabo la optimización de la respuesta dinámica del vehículo citado. Se analizan cuatro tipos distintos de optimización: identificación de parámetros, optimización de la maniobrabilidad, optimización del confort y optimización multi-objetivo, todos ellos aplicados al diseño del autocar. Además de resultados analíticos y gráficos, se incluyen algunas consideraciones acerca de la eficiencia. En resumen, se mejora el comportamiento dinámico de vehículos por medio de modelos multicuerpo y de técnicas de diferenciación automática y optimización avanzadas, posibilitando un ajuste automático, preciso y eficiente de los parámetros de diseño. ABSTRACT Each day, the design and development of vehicle suspension systems relies more on computer-aided design and computer-aided engineering tools, which allow anticipating the problems and solving them ahead of time. Dynamic behavior and characteristics are thus simulated accurately and inexpensively with moderate computational times and resources. There is, however, an iterative component in the process, which involves the manual definition of designs in a trialand-error manner. This Thesis takes a step towards the development of an efficient simulation framework capable of simulating, analyzing and evaluating vehicle suspension designs, and automatically improving them by varying the design parameters towards the optimal solution. The multibody systems approach is hereby used to model a three-dimensional 18-degrees-of-freedom coach in a comprehensive yet efficient way. The suspension geometry and characteristics resemble the ones from the real vehicle, as do the rest of vehicle parameters. In order to simulate vehicle dynamics, an efficient, state-of-the-art multibody formulation based on Maggi’s equations is employed, and a three-dimensional graphics viewer is developed. As a result, vehicle maneuvers can be simulated faster than real-time. Once the dynamics are ready, a sensitivity analysis is crucial for a robust optimization. To that end, a mathematical technique is introduced, which allows differentiating the dynamic variables within the multibody formulation in a general, algorithmic, accurate to machine precision, and reasonably efficient way: automatic differentiation. This method propagates the derivatives with respect to the design parameters throughout the computer code, with little user interaction. In contrast with other attempts in the literature, mostly not generalpurpose, a benchmarking of libraries is carried out, a hybrid direct-automatic differentiation approach for the computation of sensitivities is developed, and several real-life examples are analyzed. Finally, a design optimization process of the aforementioned vehicle is carried out. Four different types of dynamic response optimization are presented: parameter identification, handling optimization, ride comfort optimization and multi-objective optimization; all of which are applied to the design of the coach example. Together with analytical and visual proof of the results, efficiency considerations are made. In summary, the dynamic behavior of vehicles is improved by using the multibody systems approach, along with advanced differentiation and optimization techniques, enabling an automatic, accurate and efficient tuning of design parameters.