B-LOG: A branch and bound methodology for the parallel execution of logic programs

We propose a computational methodology -"B-LOG"-, which offers the potential for an effective implementation of Logic Programming in a parallel computer. We also propose a weighting scheme to guide the search process through the graph and we apply the concepts of parallel "branch and bound" algorithms in order to perform a "best-first" search using an information theoretic bound. The concept of "session" is used to speed up the search process in a succession of similar queries. Within a session, we strongly modify the bounds in a local database, while bounds kept in a global database are weakly modified to provide a better initial condition for other sessions. We also propose an implementation scheme based on a database machine using "semantic paging", and the "B-LOG processor" based on a scoreboard driven controller.

Supporting pruning in tabled LP

This paper analyzes issues which appear when supporting pruning operators in tabled LP. A version of the once/1 control predicate tailored for tabled predicates is presented, and an implementation analyzed and evaluated. Using once/1 with answer-on-demand strategies makes it possible to avoid computing unneeded solutions for problems which can benefit from tabled LP but in which only a single solution is needed, such as model checking and planning. The proposed version of once/1 is also directly applicable to the efficient implementation of other optimizations, such as early completion, cut-fail loops (to, e.g., prune at the top level), if-then-else, and constraint-based branch-and-bound optimization. Although once/1 still presents open issues such as dependencies of tabled solutions on program history, our experimental evaluation confirms that it provides an arbitrarily large efficiency improvement in several application areas.

Nonparametric Message Passing Methods for Cooperative Localization and Tracking

The objective of this thesis is the development of cooperative localization and tracking algorithms using nonparametric message passing techniques. In contrast to the most well-known techniques, the goal is to estimate the posterior probability density function (PDF) of the position of each sensor. This problem can be solved using Bayesian approach, but it is intractable in general case. Nevertheless, the particle-based approximation (via nonparametric representation), and an appropriate factorization of the joint PDFs (using message passing methods), make Bayesian approach acceptable for inference in sensor networks. The well-known method for this problem, nonparametric belief propagation (NBP), can lead to inaccurate beliefs and possible non-convergence in loopy networks. Therefore, we propose four novel algorithms which alleviate these problems: nonparametric generalized belief propagation (NGBP) based on junction tree (NGBP-JT), NGBP based on pseudo-junction tree (NGBP-PJT), NBP based on spanning trees (NBP-ST), and uniformly-reweighted NBP (URW-NBP). We also extend NBP for cooperative localization in mobile networks. In contrast to the previous methods, we use an optional smoothing, provide a novel communication protocol, and increase the efficiency of the sampling techniques. Moreover, we propose novel algorithms for distributed tracking, in which the goal is to track the passive object which cannot locate itself. In particular, we develop distributed particle filtering (DPF) based on three asynchronous belief consensus (BC) algorithms: standard belief consensus (SBC), broadcast gossip (BG), and belief propagation (BP). Finally, the last part of this thesis includes the experimental analysis of some of the proposed algorithms, in which we found that the results based on real measurements are very similar with the results based on theoretical models.

Performance of artificial neural networks and genetical evolved artificial neural networks unfolding techniques

With the Bonner spheres spectrometer neutron spectrum is obtained through an unfolding procedure. Monte Carlo methods, Regularization, Parametrization, Least-squares, and Maximum Entropy are some of the techniques utilized for unfolding. In the last decade methods based on Artificial Intelligence Technology have been used. Approaches based on Genetic Algorithms and Artificial Neural Networks have been developed in order to overcome the drawbacks of previous techniques. Nevertheless the advantages of Artificial Neural Networks still it has some drawbacks mainly in the design process of the network, vg the optimum selection of the architectural and learning ANN parameters. In recent years the use of hybrid technologies, combining Artificial Neural Networks and Genetic Algorithms, has been utilized to. In this work, several ANN topologies were trained and tested using Artificial Neural Networks and Genetically Evolved Artificial Neural Networks in the aim to unfold neutron spectra using the count rates of a Bonner sphere spectrometer. Here, a comparative study of both procedures has been carried out.

Present and Future of Photovoltaic Solar Electricity

Ponencia Invitada presentada en el IEEE Region 8 Student Branch and GOLD Congress

A Ground-Truth Video Dataset for the Development and Evaluation of Vision-based Sense-and-Avoid systems

The importance of vision-based systems for Sense-and-Avoid is increasing nowadays as remotely piloted and autonomous UAVs become part of the non-segregated airspace. The development and evaluation of these systems demand flight scenario images which are expensive and risky to obtain. Currently Augmented Reality techniques allow the compositing of real flight scenario images with 3D aircraft models to produce useful realistic images for system development and benchmarking purposes at a much lower cost and risk. With the techniques presented in this paper, 3D aircraft models are positioned firstly in a simulated 3D scene with controlled illumination and rendering parameters. Realistic simulated images are then obtained using an image processing algorithm which fuses the images obtained from the 3D scene with images from real UAV flights taking into account on board camera vibrations. Since the intruder and camera poses are user-defined, ground truth data is available. These ground truth annotations allow to develop and quantitatively evaluate aircraft detection and tracking algorithms. This paper presents the software developed to create a public dataset of 24 videos together with their annotations and some tracking application results.

New definitions of margin for multi-class Boosting algorithms

La familia de algoritmos de Boosting son un tipo de técnicas de clasificación y regresión que han demostrado ser muy eficaces en problemas de Visión Computacional. Tal es el caso de los problemas de detección, de seguimiento o bien de reconocimiento de caras, personas, objetos deformables y acciones. El primer y más popular algoritmo de Boosting, AdaBoost, fue concebido para problemas binarios. Desde entonces, muchas han sido las propuestas que han aparecido con objeto de trasladarlo a otros dominios más generales: multiclase, multilabel, con costes, etc. Nuestro interés se centra en extender AdaBoost al terreno de la clasificación multiclase, considerándolo como un primer paso para posteriores ampliaciones. En la presente tesis proponemos dos algoritmos de Boosting para problemas multiclase basados en nuevas derivaciones del concepto margen. El primero de ellos, PIBoost, está concebido para abordar el problema descomponiéndolo en subproblemas binarios. Por un lado, usamos una codificación vectorial para representar etiquetas y, por otro, utilizamos la función de pérdida exponencial multiclase para evaluar las respuestas. Esta codificación produce un conjunto de valores margen que conllevan un rango de penalizaciones en caso de fallo y recompensas en caso de acierto. La optimización iterativa del modelo genera un proceso de Boosting asimétrico cuyos costes dependen del número de etiquetas separadas por cada clasificador débil. De este modo nuestro algoritmo de Boosting tiene en cuenta el desbalanceo debido a las clases a la hora de construir el clasificador. El resultado es un método bien fundamentado que extiende de manera canónica al AdaBoost original. El segundo algoritmo propuesto, BAdaCost, está concebido para problemas multiclase dotados de una matriz de costes. Motivados por los escasos trabajos dedicados a generalizar AdaBoost al terreno multiclase con costes, hemos propuesto un nuevo concepto de margen que, a su vez, permite derivar una función de pérdida adecuada para evaluar costes. Consideramos nuestro algoritmo como la extensión más canónica de AdaBoost para este tipo de problemas, ya que generaliza a los algoritmos SAMME, Cost-Sensitive AdaBoost y PIBoost. Por otro lado, sugerimos un simple procedimiento para calcular matrices de coste adecuadas para mejorar el rendimiento de Boosting a la hora de abordar problemas estándar y problemas con datos desbalanceados. Una serie de experimentos nos sirven para demostrar la efectividad de ambos métodos frente a otros conocidos algoritmos de Boosting multiclase en sus respectivas áreas. En dichos experimentos se usan bases de datos de referencia en el área de Machine Learning, en primer lugar para minimizar errores y en segundo lugar para minimizar costes. Además, hemos podido aplicar BAdaCost con éxito a un proceso de segmentación, un caso particular de problema con datos desbalanceados. Concluimos justificando el horizonte de futuro que encierra el marco de trabajo que presentamos, tanto por su aplicabilidad como por su flexibilidad teórica. Abstract The family of Boosting algorithms represents a type of classification and regression approach that has shown to be very effective in Computer Vision problems. Such is the case of detection, tracking and recognition of faces, people, deformable objects and actions. The first and most popular algorithm, AdaBoost, was introduced in the context of binary classification. Since then, many works have been proposed to extend it to the more general multi-class, multi-label, costsensitive, etc... domains. Our interest is centered in extending AdaBoost to two problems in the multi-class field, considering it a first step for upcoming generalizations. In this dissertation we propose two Boosting algorithms for multi-class classification based on new generalizations of the concept of margin. The first of them, PIBoost, is conceived to tackle the multi-class problem by solving many binary sub-problems. We use a vectorial codification to represent class labels and a multi-class exponential loss function to evaluate classifier responses. This representation produces a set of margin values that provide a range of penalties for failures and rewards for successes. The stagewise optimization of this model introduces an asymmetric Boosting procedure whose costs depend on the number of classes separated by each weak-learner. In this way the Boosting procedure takes into account class imbalances when building the ensemble. The resulting algorithm is a well grounded method that canonically extends the original AdaBoost. The second algorithm proposed, BAdaCost, is conceived for multi-class problems endowed with a cost matrix. Motivated by the few cost-sensitive extensions of AdaBoost to the multi-class field, we propose a new margin that, in turn, yields a new loss function appropriate for evaluating costs. Since BAdaCost generalizes SAMME, Cost-Sensitive AdaBoost and PIBoost algorithms, we consider our algorithm as a canonical extension of AdaBoost to this kind of problems. We additionally suggest a simple procedure to compute cost matrices that improve the performance of Boosting in standard and unbalanced problems. A set of experiments is carried out to demonstrate the effectiveness of both methods against other relevant Boosting algorithms in their respective areas. In the experiments we resort to benchmark data sets used in the Machine Learning community, firstly for minimizing classification errors and secondly for minimizing costs. In addition, we successfully applied BAdaCost to a segmentation task, a particular problem in presence of imbalanced data. We conclude the thesis justifying the horizon of future improvements encompassed in our framework, due to its applicability and theoretical flexibility.

Experimentel ADS-B based surveillance

This paper describes an ADS-B implementation in air-to-air and ground based experimental surveillance within a prototype ATM system. The relations between airborne and ground systems related to surveillance are detailed, and the prototype surveillance systems and their algorithms described. Their performance is analysed, based both on simulated and real data.

Thresholding Soil Surface Images

Soil erosion is a complex phenomenon involving the detachment and transport of soil particles, storage and runoff of rainwater, and infiltration. The relative magnitude and importance of these processes depends on several factors being one of them surface micro-topography, usually quanti[U+FB01]ed trough soil surface roughness (SSR). SSR greatly affects surface sealing and runoff generation, yet little information is available about the effect of roughness on the spatial distribution of runoff and on flow concentration. The methods commonly used to measure SSR involve measuring point elevation using a pin roughness meter or laser, both of which are labor intensive and expensive. Lately a simple and inexpensive technique based on percentage of shadow in soil surface image has been developed to determine SSR in the field in order to obtain measurement for wide spread application. One of the first steps in this technique is image de-noising and thresholding to estimate the percentage of black pixels in the studied area. In this work, a series of soil surface images have been analyzed applying several de-noising wavelet analysis and thresholding algorithms to study the variation in percentage of shadows and the shadows size distribution

Medidas autosemejantes en el plano, momentos y matrices de Hessenberg

La tesis MEDIDAS AUTOSEMEJANTES EN EL PLANO, MOMENTOS Y MATRICES DE HESSENBERG se enmarca entre las áreas de la teoría geométrica de la medida, la teoría de polinomios ortogonales y la teoría de operadores. La memoria aborda el estudio de medidas con soporte acotado en el plano complejo vistas con la óptica de las matrices infinitas de momentos y de Hessenberg asociadas a estas medidas que en la teoría de los polinomios ortogonales las representan. En particular se centra en el estudio de las medidas autosemejantes que son las medidas de equilibrio definidas por un sistema de funciones iteradas (SFI). Los conjuntos autosemejantes son conjuntos que tienen la propiedad geométrica de descomponerse en unión de piezas semejantes al conjunto total. Estas piezas pueden solaparse o no, cuando el solapamiento es pequeño la teoría de Hutchinson [Hut81] funciona bien, pero cuando no existen restricciones falla. El problema del solapamiento consiste en controlar la medida de este solapamiento. Un ejemplo de la complejidad de este problema se plantea con las convoluciones infinitas de distribuciones de Bernoulli, que han resultado ser un ejemplo de medidas autosemejantes en el caso real. En 1935 Jessen y A. Wintner [JW35] ya se planteaba este problema, lejos de ser sencillo ha sido estudiado durante más de setenta y cinco años y siguen sin resolverse las principales cuestiones planteadas ya por A. Garsia [Gar62] en 1962. El interés que ha despertado este problema así como la complejidad del mismo está demostrado por las numerosas publicaciones que abordan cuestiones relacionadas con este problema ver por ejemplo [JW35], [Erd39], [PS96], [Ma00], [Ma96], [Sol98], [Mat95], [PS96], [Sim05],[JKS07] [JKS11]. En el primer capítulo comenzamos introduciendo con detalle las medidas autosemejante en el plano complejo y los sistemas de funciones iteradas, así como los conceptos de la teoría de la medida necesarios para describirlos. A continuación se introducen las herramientas necesarias de teoría de polinomios ortogonales, matrices infinitas y operadores que se van a usar. En el segundo y tercer capítulo trasladamos las propiedades geométricas de las medidas autosemejantes a las matrices de momentos y de Hessenberg, respectivamente. A partir de estos resultados se describen algoritmos para calcular estas matrices a partir del SFI correspondiente. Concretamente, se obtienen fórmulas explícitas y algoritmos de aproximación para los momentos y matrices de momentos de medidas fractales, a partir de un teorema del punto fijo para las matrices. Además utilizando técnicas de la teoría de operadores, se han extendido al plano complejo los resultados que G. Mantica [Ma00, Ma96] obtenía en el caso real. Este resultado es la base para definir un algoritmo estable de aproximación de la matriz de Hessenberg asociada a una medida fractal u obtener secciones finitas exactas de matrices Hessenberg asociadas a una suma de medidas. En el último capítulo, se consideran medidas, μ, más generales y se estudia el comportamiento asintótico de los autovalores de una matriz hermitiana de momentos y su impacto en las propiedades de la medida asociada. En el resultado central se demuestra que si los polinomios asociados son densos en L2(μ) entonces necesariamente el autovalor mínimo de las secciones finitas de la matriz de momentos de la medida tiende a cero. ABSTRACT The Thesis work “Self-similar Measures on the Plane, Moments and Hessenberg Matrices” is framed among the geometric measure theory, orthogonal polynomials and operator theory. The work studies measures with compact support on the complex plane from the point of view of the associated infinite moments and Hessenberg matrices representing them in the theory of orthogonal polynomials. More precisely, it concentrates on the study of the self-similar measures that are equilibrium measures in a iterated functions system. Self-similar sets have the geometric property of being decomposable in a union of similar pieces to the complete set. These pieces can overlap. If the overlapping is small, Hutchinson’s theory [Hut81] works well, however, when it has no restrictions, the theory does not hold. The overlapping problem consists in controlling the measure of the overlap. The complexity of this problem is exemplified in the infinite convolutions of Bernoulli’s distributions, that are an example of self-similar measures in the real case. As early as 1935 [JW35], Jessen and Wintner posed this problem, that far from being simple, has been studied during more than 75 years. The main cuestiones posed by Garsia in 1962 [Gar62] remain unsolved. The interest in this problem, together with its complexity, is demonstrated by the number of publications that over the years have dealt with it. See, for example, [JW35], [Erd39], [PS96], [Ma00], [Ma96], [Sol98], [Mat95], [PS96], [Sim05], [JKS07] [JKS11]. In the first chapter, we will start with a detailed introduction to the self-similar measurements in the complex plane and to the iterated functions systems, also including the concepts of measure theory needed to describe them. Next, we introduce the necessary tools from orthogonal polynomials, infinite matrices and operators. In the second and third chapter we will translate the geometric properties of selfsimilar measures to the moments and Hessenberg matrices. From these results, we will describe algorithms to calculate these matrices from the corresponding iterated functions systems. To be precise, we obtain explicit formulas and approximation algorithms for the moments and moment matrices of fractal measures from a new fixed point theorem for matrices. Moreover, using techniques from operator theory, we extend to the complex plane the real case results obtained by Mantica [Ma00, Ma96]. This result is the base to define a stable algorithm that approximates the Hessenberg matrix associated to a fractal measure and obtains exact finite sections of Hessenberg matrices associated to a sum of measurements. In the last chapter, we consider more general measures, μ, and study the asymptotic behaviour of the eigenvalues of a hermitian matrix of moments, together with its impact on the properties of the associated measure. In the main result we demonstrate that, if the associated polynomials are dense in L2(μ), then necessarily follows that the minimum eigenvalue of the finite sections of the moments matrix goes to zero.

Contribution to the quality improvement of the antenna measurement using post-processing techniques = Contribución a la mejora de la calidad de medida de antena usando técnicas de post-procesado

One important task in the design of an antenna is to carry out an analysis to find out the characteristics of the antenna that best fulfills the specifications fixed by the application. After that, a prototype is manufactured and the next stage in design process is to check if the radiation pattern differs from the designed one. Besides the radiation pattern, other radiation parameters like directivity, gain, impedance, beamwidth, efficiency, polarization, etc. must be also evaluated. For this purpose, accurate antenna measurement techniques are needed in order to know exactly the actual electromagnetic behavior of the antenna under test. Due to this fact, most of the measurements are performed in anechoic chambers, which are closed areas, normally shielded, covered by electromagnetic absorbing material, that simulate free space propagation conditions, due to the absorption of the radiation absorbing material. Moreover, these facilities can be employed independently of the weather conditions and allow measurements free from interferences. Despite all the advantages of the anechoic chambers, the results obtained both from far-field measurements and near-field measurements are inevitably affected by errors. Thus, the main objective of this Thesis is to propose algorithms to improve the quality of the results obtained in antenna measurements by using post-processing techniques and without requiring additional measurements. First, a deep revision work of the state of the art has been made in order to give a general vision of the possibilities to characterize or to reduce the effects of errors in antenna measurements. Later, new methods to reduce the unwanted effects of four of the most commons errors in antenna measurements are described and theoretical and numerically validated. The basis of all them is the same, to perform a transformation from the measurement surface to another domain where there is enough information to easily remove the contribution of the errors. The four errors analyzed are noise, reflections, truncation errors and leakage and the tools used to suppress them are mainly source reconstruction techniques, spatial and modal filtering and iterative algorithms to extrapolate functions. Therefore, the main idea of all the methods is to modify the classical near-field-to-far-field transformations by including additional steps with which errors can be greatly suppressed. Moreover, the proposed methods are not computationally complex and, because they are applied in post-processing, additional measurements are not required. The noise is the most widely studied error in this Thesis, proposing a total of three alternatives to filter out an important noise contribution before obtaining the far-field pattern. The first one is based on a modal filtering. The second alternative uses a source reconstruction technique to obtain the extreme near-field where it is possible to apply a spatial filtering. The last one is to back-propagate the measured field to a surface with the same geometry than the measurement surface but closer to the AUT and then to apply also a spatial filtering. All the alternatives are analyzed in the three most common near-field systems, including comprehensive noise statistical analyses in order to deduce the signal-to-noise ratio improvement achieved in each case. The method to suppress reflections in antenna measurements is also based on a source reconstruction technique and the main idea is to reconstruct the field over a surface larger than the antenna aperture in order to be able to identify and later suppress the virtual sources related to the reflective waves. The truncation error presents in the results obtained from planar, cylindrical and partial spherical near-field measurements is the third error analyzed in this Thesis. The method to reduce this error is based on an iterative algorithm to extrapolate the reliable region of the far-field pattern from the knowledge of the field distribution on the AUT plane. The proper termination point of this iterative algorithm as well as other critical aspects of the method are also studied. The last part of this work is dedicated to the detection and suppression of the two most common leakage sources in antenna measurements. A first method tries to estimate the leakage bias constant added by the receiver’s quadrature detector to every near-field data and then suppress its effect on the far-field pattern. The second method can be divided into two parts; the first one to find the position of the faulty component that radiates or receives unwanted radiation, making easier its identification within the measurement environment and its later substitution; and the second part of this method is able to computationally remove the leakage effect without requiring the substitution of the faulty component. Resumen Una tarea importante en el diseño de una antena es llevar a cabo un análisis para averiguar las características de la antena que mejor cumple las especificaciones fijadas por la aplicación. Después de esto, se fabrica un prototipo de la antena y el siguiente paso en el proceso de diseño es comprobar si el patrón de radiación difiere del diseñado. Además del patrón de radiación, otros parámetros de radiación como la directividad, la ganancia, impedancia, ancho de haz, eficiencia, polarización, etc. deben ser también evaluados. Para lograr este propósito, se necesitan técnicas de medida de antenas muy precisas con el fin de saber exactamente el comportamiento electromagnético real de la antena bajo prueba. Debido a esto, la mayoría de las medidas se realizan en cámaras anecoicas, que son áreas cerradas, normalmente revestidas, cubiertas con material absorbente electromagnético. Además, estas instalaciones se pueden emplear independientemente de las condiciones climatológicas y permiten realizar medidas libres de interferencias. A pesar de todas las ventajas de las cámaras anecoicas, los resultados obtenidos tanto en medidas en campo lejano como en medidas en campo próximo están inevitablemente afectados por errores. Así, el principal objetivo de esta Tesis es proponer algoritmos para mejorar la calidad de los resultados obtenidos en medida de antenas mediante el uso de técnicas de post-procesado. Primeramente, se ha realizado un profundo trabajo de revisión del estado del arte con el fin de dar una visión general de las posibilidades para caracterizar o reducir los efectos de errores en medida de antenas. Después, se han descrito y validado tanto teórica como numéricamente nuevos métodos para reducir el efecto indeseado de cuatro de los errores más comunes en medida de antenas. La base de todos ellos es la misma, realizar una transformación de la superficie de medida a otro dominio donde hay suficiente información para eliminar fácilmente la contribución de los errores. Los cuatro errores analizados son ruido, reflexiones, errores de truncamiento y leakage y las herramientas usadas para suprimirlos son principalmente técnicas de reconstrucción de fuentes, filtrado espacial y modal y algoritmos iterativos para extrapolar funciones. Por lo tanto, la principal idea de todos los métodos es modificar las transformaciones clásicas de campo cercano a campo lejano incluyendo pasos adicionales con los que los errores pueden ser enormemente suprimidos. Además, los métodos propuestos no son computacionalmente complejos y dado que se aplican en post-procesado, no se necesitan medidas adicionales. El ruido es el error más ampliamente estudiado en esta Tesis, proponiéndose un total de tres alternativas para filtrar una importante contribución de ruido antes de obtener el patrón de campo lejano. La primera está basada en un filtrado modal. La segunda alternativa usa una técnica de reconstrucción de fuentes para obtener el campo sobre el plano de la antena donde es posible aplicar un filtrado espacial. La última es propagar el campo medido a una superficie con la misma geometría que la superficie de medida pero más próxima a la antena y luego aplicar también un filtrado espacial. Todas las alternativas han sido analizadas en los sistemas de campo próximos más comunes, incluyendo detallados análisis estadísticos del ruido con el fin de deducir la mejora de la relación señal a ruido lograda en cada caso. El método para suprimir reflexiones en medida de antenas está también basado en una técnica de reconstrucción de fuentes y la principal idea es reconstruir el campo sobre una superficie mayor que la apertura de la antena con el fin de ser capaces de identificar y después suprimir fuentes virtuales relacionadas con las ondas reflejadas. El error de truncamiento que aparece en los resultados obtenidos a partir de medidas en un plano, cilindro o en la porción de una esfera es el tercer error analizado en esta Tesis. El método para reducir este error está basado en un algoritmo iterativo para extrapolar la región fiable del patrón de campo lejano a partir de información de la distribución del campo sobre el plano de la antena. Además, se ha estudiado el punto apropiado de terminación de este algoritmo iterativo así como otros aspectos críticos del método. La última parte de este trabajo está dedicado a la detección y supresión de dos de las fuentes de leakage más comunes en medida de antenas. El primer método intenta realizar una estimación de la constante de fuga del leakage añadido por el detector en cuadratura del receptor a todos los datos en campo próximo y después suprimir su efecto en el patrón de campo lejano. El segundo método se puede dividir en dos partes; la primera de ellas para encontrar la posición de elementos defectuosos que radian o reciben radiación indeseada, haciendo más fácil su identificación dentro del entorno de medida y su posterior substitución. La segunda parte del método es capaz de eliminar computacionalmente el efector del leakage sin necesidad de la substitución del elemento defectuoso.

IDRA (IDeal Resource Allocation): A tool for computing ideal speedups

Performance studies of actual parallel systems usually tend to concéntrate on the effectiveness of a given implementation. This is often done in the absolute, without quantitave reference to the potential parallelism contained in the programs from the point of view of the execution paradigm. We feel that studying the parallelism inherent to the programs is interesting, as it gives information about the best possible behavior of any implementation and thus allows contrasting the results obtained. We propose a method for obtaining ideal speedups for programs through a combination of sequential or parallel execution and simulation, and the algorithms that allow implementing the method. Our approach is novel and, we argüe, more accurate than previously proposed methods, in that a crucial part of the data - the execution times of tasks - is obtained from actual executions, while speedup is computed by simulation. This allows obtaining speedup (and other) data under controlled and ideal assumptions regarding issues such as number of processor, scheduling algorithm and overheads, etc. The results obtained can be used for example to evalúate the ideal parallelism that a program contains for a given model of execution and to compare such "perfect" parallelism to that obtained by a given implementation of that model. We also present a tool, IDRA, which implements the proposed method, and results obtained with IDRA for benchmark programs, which are then compared with those obtained in actual executions on real parallel systems.

Algoritmos de distribución de cargas de proceso en computación con membranas

Con el surgir de los problemas irresolubles de forma eficiente en tiempo polinomial en base al dato de entrada, surge la Computación Natural como alternativa a la computación clásica. En esta disciplina se trata de o bien utilizar la naturaleza como base de cómputo o bien, simular su comportamiento para obtener mejores soluciones a los problemas que los encontrados por la computación clásica. Dentro de la computación natural, y como una representación a nivel celular, surge la Computación con Membranas. La primera abstracción de las membranas que se encuentran en las células, da como resultado los P sistemas de transición. Estos sistemas, que podrían ser implementados en medios biológicos o electrónicos, son la base de estudio de esta Tesis. En primer lugar, se estudian las implementaciones que se han realizado, con el fin de centrarse en las implementaciones distribuidas, que son las que pueden aprovechar las características intrínsecas de paralelismo y no determinismo. Tras un correcto estudio del estado actual de las distintas etapas que engloban a la evolución del sistema, se concluye con que las distribuciones que buscan un equilibrio entre las dos etapas (aplicación y comunicación), son las que mejores resultados presentan. Para definir estas distribuciones, es necesario definir completamente el sistema, y cada una de las partes que influyen en su transición. Además de los trabajos de otros investigadores, y junto a ellos, se realizan variaciones a los proxies y arquitecturas de distribución, para tener completamente definidos el comportamiento dinámico de los P sistemas. A partir del conocimiento estático –configuración inicial– del P sistema, se pueden realizar distribuciones de membranas en los procesadores de un clúster para obtener buenos tiempos de evolución, con el fin de que la computación del P sistema sea realizada en el menor tiempo posible. Para realizar estas distribuciones, hay que tener presente las arquitecturas –o forma de conexión– de los procesadores del clúster. La existencia de 4 arquitecturas, hace que el proceso de distribución sea dependiente de la arquitectura a utilizar, y por tanto, aunque con significativas semejanzas, los algoritmos de distribución deben ser realizados también 4 veces. Aunque los propulsores de las arquitecturas han estudiado el tiempo óptimo de cada arquitectura, la inexistencia de distribuciones para estas arquitecturas ha llevado a que en esta Tesis se probaran las 4, hasta que sea posible determinar que en la práctica, ocurre lo mismo que en los estudios teóricos. Para realizar la distribución, no existe ningún algoritmo determinista que consiga una distribución que satisfaga las necesidades de la arquitectura para cualquier P sistema. Por ello, debido a la complejidad de dicho problema, se propone el uso de metaheurísticas de Computación Natural. En primer lugar, se propone utilizar Algoritmos Genéticos, ya que es posible realizar alguna distribución, y basada en la premisa de que con la evolución, los individuos mejoran, con la evolución de dichos algoritmos, las distribuciones también mejorarán obteniéndose tiempos cercanos al óptimo teórico. Para las arquitecturas que preservan la topología arbórea del P sistema, han sido necesarias realizar nuevas representaciones, y nuevos algoritmos de cruzamiento y mutación. A partir de un estudio más detallado de las membranas y las comunicaciones entre procesadores, se ha comprobado que los tiempos totales que se han utilizado para la distribución pueden ser mejorados e individualizados para cada membrana. Así, se han probado los mismos algoritmos, obteniendo otras distribuciones que mejoran los tiempos. De igual forma, se han planteado el uso de Optimización por Enjambres de Partículas y Evolución Gramatical con reescritura de gramáticas (variante de Evolución Gramatical que se presenta en esta Tesis), para resolver el mismo cometido, obteniendo otro tipo de distribuciones, y pudiendo realizar una comparativa de las arquitecturas. Por último, el uso de estimadores para el tiempo de aplicación y comunicación, y las variaciones en la topología de árbol de membranas que pueden producirse de forma no determinista con la evolución del P sistema, hace que se deba de monitorizar el mismo, y en caso necesario, realizar redistribuciones de membranas en procesadores, para seguir obteniendo tiempos de evolución razonables. Se explica, cómo, cuándo y dónde se deben realizar estas modificaciones y redistribuciones; y cómo es posible realizar este recálculo. Abstract Natural Computing is becoming a useful alternative to classical computational models since it its able to solve, in an efficient way, hard problems in polynomial time. This discipline is based on biological behaviour of living organisms, using nature as a basis of computation or simulating nature behaviour to obtain better solutions to problems solved by the classical computational models. Membrane Computing is a sub discipline of Natural Computing in which only the cellular representation and behaviour of nature is taken into account. Transition P Systems are the first abstract representation of membranes belonging to cells. These systems, which can be implemented in biological organisms or in electronic devices, are the main topic studied in this thesis. Implementations developed in this field so far have been studied, just to focus on distributed implementations. Such distributions are really important since they can exploit the intrinsic parallelism and non-determinism behaviour of living cells, only membranes in this case study. After a detailed survey of the current state of the art of membranes evolution and proposed algorithms, this work concludes that best results are obtained using an equal assignment of communication and rules application inside the Transition P System architecture. In order to define such optimal distribution, it is necessary to fully define the system, and each one of the elements that influence in its transition. Some changes have been made in the work of other authors: load distribution architectures, proxies definition, etc., in order to completely define the dynamic behaviour of the Transition P System. Starting from the static representation –initial configuration– of the Transition P System, distributions of membranes in several physical processors of a cluster is algorithmically done in order to get a better performance of evolution so that the computational complexity of the Transition P System is done in less time as possible. To build these distributions, the cluster architecture –or connection links– must be considered. The existence of 4 architectures, makes that the process of distribution depends on the chosen architecture, and therefore, although with significant similarities, the distribution algorithms must be implemented 4 times. Authors who proposed such architectures have studied the optimal time of each one. The non existence of membrane distributions for these architectures has led us to implement a dynamic distribution for the 4. Simulations performed in this work fix with the theoretical studies. There is not any deterministic algorithm that gets a distribution that meets the needs of the architecture for any Transition P System. Therefore, due to the complexity of the problem, the use of meta-heuristics of Natural Computing is proposed. First, Genetic Algorithm heuristic is proposed since it is possible to make a distribution based on the premise that along with evolution the individuals improve, and with the improvement of these individuals, also distributions enhance, obtaining complexity times close to theoretical optimum time. For architectures that preserve the tree topology of the Transition P System, it has been necessary to make new representations of individuals and new algorithms of crossover and mutation operations. From a more detailed study of the membranes and the communications among processors, it has been proof that the total time used for the distribution can be improved and individualized for each membrane. Thus, the same algorithms have been tested, obtaining other distributions that improve the complexity time. In the same way, using Particle Swarm Optimization and Grammatical Evolution by rewriting grammars (Grammatical Evolution variant presented in this thesis), to solve the same distribution task. New types of distributions have been obtained, and a comparison of such genetic and particle architectures has been done. Finally, the use of estimators for the time of rules application and communication, and variations in tree topology of membranes that can occur in a non-deterministic way with evolution of the Transition P System, has been done to monitor the system, and if necessary, perform a membrane redistribution on processors to obtain reasonable evolution time. How, when and where to make these changes and redistributions, and how it can perform this recalculation, is explained.

Diseño, optimización y análisis de sistemas basados en técnicas láser, para el modelado geométrico, registro y documentación, aplicados a entidades de interés patrimonial.

El objetivo de la presente tesis doctoral es el desarrollo e implementación de un sistema para mejorar la metodología de extracción de la información geométrica necesaria asociada a los procesos de documentación de entidades de interés patrimonial, a partir de la información proporcionada por el empleo de sensores láser, tanto aéreos como terrestres. Para ello, inicialmente se realiza una presentación y justificación de los antecedentes y la problemática en el registro de información geométrica para el patrimonio, detallando todos aquellos sistemas de registro y análisis de la información geométrica utilizados en la actualidad. Este análisis permitirá realizar la comparación con los sistemas de registro basados en técnicas láser, aportando sugerencias de utilización para cada caso concreto. Posteriormente, se detallan los sistemas de registro basados en técnicas láser, comenzando por los sensores aerotransportados y concluyendo con el análisis pormenorizado de los sensores terrestres, tanto en su aplicación en modo estático como móvil. Se exponen las características técnicas y funcionamiento de cada uno de ellos, así como los ámbitos de aplicación y productos generados. Se analizan las fuentes de error que determinan la precisión que puede alcanzar el sistema. Tras la exposición de las características de los sistemas LiDAR, se detallan los procesos a realizar con los datos extraídos para poder generar la información necesaria para los diferentes tipos de objetos analizados. En esta exposición, se hace hincapié en los posibles riesgos que pueden ocurrir en algunas fases delicadas y se analizarán los diferentes algoritmos de filtrado y clasificación de los puntos, fundamentales en el procesamiento de la información LiDAR. Seguidamente, se propone una alternativa para optimizar los modelos de procesamiento existentes, basándose en el desarrollo de algoritmos nuevos y herramientas informáticas que mejoran el rendimiento en la gestión de la información LiDAR. En la implementación, se han tenido en cuenta características y necesidades particulares de la documentación de entidades de interés patrimonial, así como los diferentes ámbitos de utilización del LiDAR, tanto aéreo como terrestre. El resultado es un organigrama de las tareas a realizar desde la nube de puntos LiDAR hasta el cálculo de los modelos digitales del terreno y de superficies. Para llevar a cabo esta propuesta, se han desarrollado hasta 19 algoritmos diferentes que comprenden implementaciones para el modelado en 2.5D y 3D, visualización, edición, filtrado y clasificación de datos LiDAR, incorporación de información de sensores pasivos y cálculo de mapas derivados, tanto raster como vectoriales, como pueden ser mapas de curvas de nivel y ortofotos. Finalmente, para dar validez y consistencia a los desarrollos propuestos, se han realizado ensayos en diferentes escenarios posibles en un proceso de documentación del patrimonio y que abarcan desde proyectos con sensores aerotransportados, proyectos con sensores terrestres estáticos a media y corta distancia, así como un proyecto con un sensor terrestre móvil. Estos ensayos han permitido definir los diferentes parámetros necesarios para el adecuado funcionamiento de los algoritmos propuestos. Asimismo, se han realizado pruebas objetivas expuestas por la ISPRS para la evaluación y comparación del funcionamiento de algoritmos de clasificación LiDAR. Estas pruebas han permitido extraer datos de rendimiento y efectividad del algoritmo de clasificación presentado, permitiendo su comparación con otros algoritmos de prestigio existentes. Los resultados obtenidos han constatado el funcionamiento satisfactorio de la herramienta. Esta tesis está enmarcada dentro del proyecto Consolider-Ingenio 2010: “Programa de investigación en tecnologías para la valoración y conservación del patrimonio cultural” (ref. CSD2007-00058) realizado por el Consejo Superior de Investigaciones Científicas y la Universidad Politécnica de Madrid. ABSTRACT: The goal of this thesis is the design, development and implementation of a system to improve the extraction of useful geometric information in Heritage documentation processes. This system is based on information provided by laser sensors, both aerial and terrestrial. Firstly, a presentation of recording geometric information for Heritage processes is done. Then, a justification of the background and problems is done too. Here, current systems for recording and analyzing the geometric information are studied. This analysis will perform the comparison with the laser system techniques, providing suggestions of use for each specific case. Next, recording systems based on laser techniques are detailed. This study starts with airborne sensors and ends with terrestrial ones, both in static and mobile application. The technical characteristics and operation of each of them are described, as well as the areas of application and generated products. Error sources are also analyzed in order to know the precision this technology can achieve. Following the presentation of the LiDAR system characteristics, the processes to generate the required information for different types of scanned objects are described; the emphasis is on the potential risks that some steps can produce. Moreover different filtering and classification algorithms are analyzed, because of their main role in LiDAR processing. Then, an alternative to optimize existing processing models is proposed. It is based on the development of new algorithms and tools that improve the performance in LiDAR data management. In this implementation, characteristics and needs of the documentation of Heritage entities have been taken into account. Besides, different areas of use of LiDAR are considered, both air and terrestrial. The result is a flowchart of tasks from the LiDAR point cloud to the calculation of digital terrain models and digital surface models. Up to 19 different algorithms have been developed to implement this proposal. These algorithms include implementations for 2.5D and 3D modeling, viewing, editing, filtering and classification of LiDAR data, incorporating information from passive sensors and calculation of derived maps, both raster and vector, such as contour maps and orthophotos. Finally, in order to validate and give consistency to the proposed developments, tests in different cases have been executed. These tests have been selected to cover different possible scenarios in the Heritage documentation process. They include from projects with airborne sensors, static terrestrial sensors (medium and short distances) to mobile terrestrial sensor projects. These tests have helped to define the different parameters necessary for the appropriate functioning of the proposed algorithms. Furthermore, proposed tests from ISPRS have been tested. These tests have allowed evaluating the LiDAR classification algorithm performance and comparing it to others. Therefore, they have made feasible to obtain performance data and effectiveness of the developed classification algorithm. The results have confirmed the reliability of the tool. This investigation is framed within Consolider-Ingenio 2010 project titled “Programa de investigación en tecnologías para la valoración y conservación del patrimonio cultural” (ref. CSD2007-00058) by Consejo Superior de Investigaciones Científicas and Universidad Politécnica de Madrid.

Automatic-dependent surveillance-broadcast experimental deployment using system wide information management

This paper describes an automatic-dependent surveillance-broadcast (ADS-B) implementation for air-to-air and ground-based experimental surveillance within a prototype of a fully automated air traffic management (ATM) system, under a trajectory-based-operations paradigm. The system is built using an air-inclusive implementation of system wide information management (SWIM). This work describes the relations between airborne and ground surveillance (SURGND), the prototype surveillance systems, and their algorithms. System's performance is analyzed with simulated and real data. Results show that the proposed ADS-B implementation can fulfill the most demanding surveillance accuracy requirements.