Multi-Robot Task Allocation for Inspection Problems with Cooperative Tasks Using Hybrid Genetic Algorithms

In dieser Dissertation werden Methoden zur optimalen Aufgabenverteilung in Multirobotersystemen (engl. Multi-Robot Task Allocation – MRTA) zur Inspektion von Industrieanlagen untersucht. MRTA umfasst die Verteilung und Ablaufplanung von Aufgaben für eine Gruppe von Robotern unter Berücksichtigung von operativen Randbedingungen mit dem Ziel, die Gesamteinsatzkosten zu minimieren. Dank zunehmendem technischen Fortschritt und sinkenden Technologiekosten ist das Interesse an mobilen Robotern für den Industrieeinsatz in den letzten Jahren stark gestiegen. Viele Arbeiten konzentrieren sich auf Probleme der Mobilität wie Selbstlokalisierung und Kartierung, aber nur wenige Arbeiten untersuchen die optimale Aufgabenverteilung. Da sich mit einer guten Aufgabenverteilung eine effizientere Planung erreichen lässt (z. B. niedrigere Kosten, kürzere Ausführungszeit), ist das Ziel dieser Arbeit die Entwicklung von Lösungsmethoden für das aus Inspektionsaufgaben mit Einzel- und Zweiroboteraufgaben folgende Such-/Optimierungsproblem. Ein neuartiger hybrider Genetischer Algorithmus wird vorgestellt, der einen teilbevölkerungbasierten Genetischen Algorithmus zur globalen Optimierung mit lokalen Suchheuristiken kombiniert. Zur Beschleunigung dieses Algorithmus werden auf die fittesten Individuen einer Generation lokale Suchoperatoren angewendet. Der vorgestellte Algorithmus verteilt die Aufgaben nicht nur einfach und legt den Ablauf fest, sondern er bildet auch temporäre Roboterverbünde für Zweiroboteraufgaben, wodurch räumliche und zeitliche Randbedingungen entstehen. Vier alternative Kodierungsstrategien werden für den vorgestellten Algorithmus entworfen: Teilaufgabenbasierte Kodierung: Hierdurch werden alle möglichen Lösungen abgedeckt, allerdings ist der Suchraum sehr groß. Aufgabenbasierte Kodierung: Zwei Möglichkeiten zur Zuweisung von Zweiroboteraufgaben wurden implementiert, um die Effizienz des Algorithmus zu steigern. Gruppierungsbasierte Kodierung: Zeitliche Randbedingungen zur Gruppierung von Aufgaben werden vorgestellt, um gute Lösungen innerhalb einer kleinen Anzahl von Generationen zu erhalten. Zwei Umsetzungsvarianten werden vorgestellt. Dekompositionsbasierte Kodierung: Drei geometrische Zerlegungen wurden entworfen, die Informationen über die räumliche Anordnung ausnutzen, um Probleme zu lösen, die Inspektionsgebiete mit rechteckigen Geometrien aufweisen. In Simulationsstudien wird die Leistungsfähigkeit der verschiedenen hybriden Genetischen Algorithmen untersucht. Dazu wurde die Inspektion von Tanklagern einer Erdölraffinerie mit einer Gruppe homogener Inspektionsroboter als Anwendungsfall gewählt. Die Simulationen zeigen, dass Kodierungsstrategien, die auf der geometrischen Zerlegung basieren, bei einer kleinen Anzahl an Generationen eine bessere Lösung finden können als die anderen untersuchten Strategien. Diese Arbeit beschäftigt sich mit Einzel- und Zweiroboteraufgaben, die entweder von einem einzelnen mobilen Roboter erledigt werden können oder die Zusammenarbeit von zwei Robotern erfordern. Eine Erweiterung des entwickelten Algorithmus zur Behandlung von Aufgaben, die mehr als zwei Roboter erfordern, ist möglich, würde aber die Komplexität der Optimierungsaufgabe deutlich vergrößern.

A hybridised evolutionary algorithm for multi-criterion minimum spanning tree problems

A hybridised and Knowledge-based Evolutionary Algorithm (KEA) is applied to the multi-criterion minimum spanning tree problems. Hybridisation is used across its three phases. In the first phase a deterministic single objective optimization algorithm finds the extreme points of the Pareto front. In the second phase a K-best approach finds the first neighbours of the extreme points, which serve as an elitist parent population to an evolutionary algorithm in the third phase. A knowledge-based mutation operator is applied in each generation to reproduce individuals that are at least as good as the unique parent. The advantages of KEA over previous algorithms include its speed (making it applicable to large real-world problems), its scalability to more than two criteria, and its ability to find both the supported and unsupported optimal solutions.

Groud of Model for the Generalized Criterion Forming at Differential Diagnostics of Dermatological Diseases

The basic methods of decisions making in multi-criterion conditions are considered, from which the method of the weighed total for calculation of diagnostic indexes significance in differential diagnostics of dermatological diseases is chosen.

A multi-criteria decision support system for a routing problem in waste collection

Autor proof

SLA-Driven Simulation of Multi-Tenant Scalable Cloud-Distributed Enterprise Information Systems

Cloud Computing is an enabler for delivering large-scale, distributed enterprise applications with strict requirements in terms of performance. It is often the case that such applications have complex scaling and Service Level Agreement (SLA) management requirements. In this paper we present a simulation approach for validating and comparing SLA-aware scaling policies using the CloudSim simulator, using data from an actual Distributed Enterprise Information System (dEIS). We extend CloudSim with concurrent and multi-tenant task simulation capabilities. We then show how different scaling policies can be used for simulating multiple dEIS applications. We present multiple experiments depicting the impact of VM scaling on both datacenter energy consumption and dEIS performance indicators.

Modelo gráfico para la datación de vías romanas empedradas a partir del estudio de sus estados de frecuentación y del análisis superficial de roderas

La presente tesis doctoral se orienta al estudio y análisis de los caminos empedrados antiguos, desde la época prerromana, tanto desde el punto de vista histórico como desde el técnico. La cuantificación de la romanidad de un camino representa un objetivo importante para la mayoría de los estudiosos de la caminería antigua, así como para los arqueólogos, por los datos que ofrece acerca del uso del territorio, los trazados de caminos en la antigüedad y los tráficos asociados. Cuantificar la romanidad de un camino no es tarea sencilla debido a que intervienen multitud de condicionantes que están vivos y son cambiantes como consecuencia del dinamismo inherente al propio camino. En cuanto al aspecto histórico, se realiza una descripción y análisis de la evolución del camino en la Península Ibérica desde sus orígenes hasta mediados del siglo XX, que permite diferenciar la red itineraria según su momento histórico. Así mismo, se describen y analizan: las ruedas y los carros desde sus orígenes, especialmente en la época romana -incluyendo una toma de medidas de distintos tipos de carro, existentes en instituciones y colecciones particulares-; las técnicas de transporte en la antigüedad y las características de la infraestructura viaria de época romana, detallando aspectos generales de sus técnicas de ingeniería y construcción. Desde el punto de vista técnico, el enfoque metodológico ha sido definir un Índice de Romanidad del Camino (IRC) para la datación de vías romanas empedradas, basado en un análisis multicriterio, a partir de los distintos factores que caracterizan su romanidad. Se ha realizado un exhaustivo estudio de campo, con la correspondiente toma de datos en las vías. Se han realizado una serie de ensayos de laboratorio con un prototipo creado exprofeso para simular el desgaste de la piedra producido por el traqueteo del carro al circular por el camino empedrado y dar una hipótesis de datación del camino. Se ha realizado un tratamiento estadístico con la muestra de datos medidos en campo. Se ha definido además el concepto de elasticidad de rodera usando la noción de derivada elástica. En cuanto a los resultados obtenidos: se ha calculado el Índice de Romanidad del Camino (IRC) en una serie de vías empedradas, para cuantificar su romanidad, obteniéndose un resultado coherente con la hipótesis previa sobre la datación de dichas vías; y se ha formulado un modelo exponencial para el número de frecuentaciones de carga que lo relaciona con la elasticidad de rodera y con su esbeltez y que se ha utilizado para relacionar la elasticidad de la rodera con la geología de la roca. Se ha iniciado una línea de investigación sobre la estimación de tráficos históricos en la caminería antigua, considerando que el volumen de tráfico a lo largo del tiempo en un tramo de vía está relacionado con los valores de elasticidad de rodera de dicho tramo a través de la tipología de la roca. En resumen, la presente tesis doctoral proporciona un método para sistematizar el estudio de los caminos antiguos, así como para datarlos y estimar la evolución de sus tráficos. The present Ph. D. Thesis aims to study and to analyze ancient cobbled ways, since pre-roman times, both from the historical and technical points of view. The quantification of the Roman character of a way represents an important target for most of the researchers of ancient ways, as well as for the archaeologists, due to information that it offers about the use of the territory, the tracings of ways in the antiquity and the associate flows. To quantify the Roman character of a way is not a simple task because it involves multitude of influent factors that are alive and variable as a result of the dynamism inherent to the way. As for the historical aspect, a description and analysis of the evolution of the way in the Iberian Peninsula from its origins until the middle of the twentieth century has been done. This allows us to distinguish between elements of the network according to its historical moment. Likewise, a description and analysis is given about: the wheels and the cars since their origins, especially in the Roman time - including a capture of measurements of different types of car, belonging to institutions and to particular collections-; the transport techniques on the antiquity and the characteristics of the road infrastructure of Roman epoch, detailing general technical engineering and constructive aspects. From the technical point of view, the methodological approach has been to define an Index of the Roman Character of the Way (IRC) for the dating of cobbled Roman routes, based on a multi-criterion analysis, involving different factors typical of Roman ways. An exhaustive field study has been realized, with the corresponding capture of information in the routes. A series of laboratory essays has been realized with an ad hoc prototype created to simulate the wear of the stone produced by cars circulating along the cobbled way, and to give a dating hypothesis of the way. A statistical treatment has been realized with the sample of information measured in field. There has been defined also the concept of elasticity of rolling trace using the notion of elastic derivative. As for the obtained results: there has been calculated the Index of Roman Character of the Way (IRC) in a series of cobbled routes, to quantify its Roman character, obtaining a coherent result with the previous dating hypothesis of the above mentioned routes; and an exponential model has been formulated for the number of frequent attendances of load that relates this number to the elasticity of rolling trace and to its slenderness and that has been used to relate the elasticity of the rolling trace to the geology of the rock. An investigation line has been opened about the estimation of historical flows in ancient ways, considering that the traffic volume over the course of time in a route stretch is related to the values of elasticity of rolling trace of the above mentioned stretch by means of the typology of the rock. In short, the present Ph. D. Thesis provides a method to systematize the study of ancient ways, as well as to date them and to estimate the evolution of their flows.

A hedging point strategy - balancing effluent quality, economy and robustness in the control of wastewater treatment plants

An operational space map is an efficient tool to compare a large number of operational strategies to find an optimal choice of setpoints based on a multicriterion. Typically, such a multicriterion includes a weighted sum of cost of operation and effluent quality. Due to the relative high cost of aeration such a definition of optimality result in a relatively high fraction of the effluent total nitrogen in the form of ammonium. Such a strategy may however introduce a risk into operation because a low degree of ammonium removal leads to a low amount of nitrifiers. This in turn leads to a reduced ability to reject event disturbances, such as large variations in the ammonium load, drop in temperature, the presence of toxic/inhibitory compounds in the influent etc. Hedging is a risk minimisation tool, with the aim to "reduce one's risk of loss on a bet or speculation by compensating transactions on the other side" (The Concise Oxford Dictionary (1995)). In wastewater treatment plant operation hedging can be applied by choosing a higher level of ammonium removal to increase the amount of nitrifiers. This is a sensible way to introduce disturbance rejection ability into the multi criterion. In practice, this is done by deciding upon an internal effluent ammonium criterion. In some countries such as Germany, a separate criterion already applies to the level of ammonium in the effluent. However, in most countries the effluent criterion applies to total nitrogen only. In these cases, an internal effluent ammonium criterion should be selected in order to secure proper disturbance rejection ability.

Semi-Partitioned Scheduling of Fork-Join Tasks using Work-Stealing

13th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing (EUC 2015). 21 to 23, Oct, 2015, Session W1-A: Multiprocessing and Multicore Architectures. Porto, Portugal.

Population based screening - the difficulty of how to do more good than harm and how to achieve it.

Screening people without symptoms of disease is an attractive idea. Screening allows early detection of disease or elevated risk of disease, and has the potential for improved treatment and reduction of mortality. The list of future screening opportunities is set to grow because of the refinement of screening techniques, the increasing frequency of degenerative and chronic diseases, and the steadily growing body of evidence on genetic predispositions for various diseases. But how should we decide on the diseases for which screening should be done and on recommendations for how it should be implemented? We use the examples of prostate cancer and genetic screening to show the importance of considering screening as an ongoing population-based intervention with beneficial and harmful effects, and not simply the use of a test. Assessing whether screening should be recommended and implemented for any named disease is therefore a multi-dimensional task in health technology assessment. There are several countries that already use established processes and criteria to assess the appropriateness of screening. We argue that the Swiss healthcare system needs a nationwide screening commission mandated to conduct appropriate evidence-based evaluation of the impact of proposed screening interventions, to issue evidence-based recommendations, and to monitor the performance of screening programmes introduced. Without explicit processes there is a danger that beneficial screening programmes could be neglected and that ineffective, and potentially harmful, screening procedures could be introduced.

Caracterización de pólipos colorectales en pacientes sometidos a colonoscopia en el Hospital Universitario de la Samaritana durante el periodo 2009 a 2011

Los pólipos del colon son un importante factor de riesgo para el desarrollo de neoplasia, su identificación precoz, remoción y clasificación histológica es fundamental para determinar curación y sobrevida. OBJETIVO: Describir las características de los pólipos del colon resecados en un hospital de tercer nivel de Cundinamarca. METODOS: Estudio descriptivo retrospectivo tipo serie de casos, de pacientes mayores de 18 años sometidos a colonoscopía en quienes se resecaron pólipos de colon, durante el periodo 2009 a 2011. RESULTADOS: Durante el periodo de estudio de realizaron 3267 colonoscopías, se excluyeron los pacientes que no tenían pólipos, sin reporte de patología o en quienes no se recupero la pieza para histología. Se analizaron 381 pacientes con pólipos los cuales fueron incluidos en el análisis final. La localización principal de los pólipos fueron recto y sigmoide 66%, poliposis múltiple se identifico en el 2,9%. Los pólipos hiperplásicos fueron los mas frecuentemente diagnosticado, seguido por adenomas tubulares. En los pacientes que se le realizó resección de múltiples pólipos se diagnosticó cáncer en 2. Las indicaciones de realización de colonoscopía que no están claramente aprobadas pero en las cuales se identificaron y resecaron pólipos son mas del 30%. CONCLUSIONES: La mayoría de pacientes eran mujeres, sigue siendo el sangrado digestivo la principal indicación de realización de colonoscopía. Los pólipos hiperplásicos seguido de los adenomas son el principal hallazgo de patología.

Instance generators and test suites for the multiobjective quadratic assignment problem

We describe, and make publicly available, two problem instance generators for a multiobjective version of the well-known quadratic assignment problem (QAP). The generators allow a number of instance parameters to be set, including those controlling epistasis and inter-objective correlations. Based on these generators, several initial test suites are provided and described. For each test instance we measure some global properties and, for the smallest ones, make some initial observations of the Pareto optimal sets/fronts. Our purpose in providing these tools is to facilitate the ongoing study of problem structure in multiobjective (combinatorial) optimization, and its effects on search landscape and algorithm performance.

BEE COLONIES APPLIED TO MULTIPROCESSOR SCHEDULING

In order to achieve the high performance, we need to have an efficient scheduling of a parallelprogram onto the processors in multiprocessor systems that minimizes the entire executiontime. This problem of multiprocessor scheduling can be stated as finding a schedule for ageneral task graph to be executed on a multiprocessor system so that the schedule length can be minimize [10]. This scheduling problem is known to be NP- Hard.In multi processor task scheduling, we have a number of CPU’s on which a number of tasksare to be scheduled that the program’s execution time is minimized. According to [10], thetasks scheduling problem is a key factor for a parallel multiprocessor system to gain betterperformance. A task can be partitioned into a group of subtasks and represented as a DAG(Directed Acyclic Graph), so the problem can be stated as finding a schedule for a DAG to beexecuted in a parallel multiprocessor system so that the schedule can be minimized. Thishelps to reduce processing time and increase processor utilization. The aim of this thesis workis to check and compare the results obtained by Bee Colony algorithm with already generatedbest known results in multi processor task scheduling domain.

Modelo de referência para o processo de desenvolvimento de produtos de empresas eletrônicas de base tecnológica de médio porte

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Reuse Mechanisms and Concurrency: From Actors to Agent-Oriented Programming

La presente tesi è dedicata al riuso nel software. Eccettuata un'introduzione organica al tema, l'analisi è a livello dei meccanismi offerti dai linguaggi di programmazione e delle tecniche di sviluppo, con speciale attenzione rivolta al tema della concorrenza. Il primo capitolo fornisce un quadro generale nel quale il riuso del software è descritto, assieme alle ragioni che ne determinano l'importanza e ai punti cruciali relativi alla sua attuazione. Si individuano diversi livelli di riuso sulla base dell'astrazione e degli artefatti in gioco, e si sottolinea come i linguaggi contribuiscano alla riusabilità e alla realizzazione del riuso. In seguito, viene esplorato, con esempi di codice, il supporto al riuso da parte del paradigma ad oggetti, in termini di incapsulamento, ereditarietà, polimorfismo, composizione. La trattazione prosegue analizzando differenti feature – tipizzazione, interfacce, mixin, generics – offerte da vari linguaggi di programmazione, mostrando come esse intervengano sulla riusabilità dei componenti software. A chiudere il capitolo, qualche parola contestualizzata sull'inversione di controllo, la programmazione orientata agli aspetti, e il meccanismo della delega. Il secondo capitolo abbraccia il tema della concorrenza. Dopo aver introdotto l'argomento, vengono approfonditi alcuni significativi modelli di concorrenza: programmazione multi-threaded, task nel linguaggio Ada, SCOOP, modello ad Attori. Essi vengono descritti negli elementi fondamentali e ne vengono evidenziati gli aspetti cruciali in termini di contributo al riuso, con esempi di codice. Relativamente al modello ad Attori, viene presentata la sua implementazione in Scala/Akka come caso studio. Infine, viene esaminato il problema dell'inheritance anomaly, sulla base di esempi e delle tre classi principali di anomalia, e si analizza la suscettibilità del supporto di concorrenza di Scala/Akka a riscontrare tali problemi. Inoltre, in questo capitolo si nota come alcuni aspetti relativi al binomio riuso/concorrenza, tra cui il significato profondo dello stesso, non siano ancora stati adeguatamente affrontati dalla comunità informatica. Il terzo e ultimo capitolo esordisce con una panoramica dell'agent-oriented programming, prendendo il linguaggio simpAL come riferimento. In seguito, si prova ad estendere al caso degli agenti la nozione di riuso approfondita nei capitoli precedenti.

Population based screening - the difficulty of how to do more good than harm and how to achieve it

Screening people without symptoms of disease is an attractive idea. Screening allows early detection of disease or elevated risk of disease, and has the potential for improved treatment and reduction of mortality. The list of future screening opportunities is set to grow because of the refinement of screening techniques, the increasing frequency of degenerative and chronic diseases, and the steadily growing body of evidence on genetic predispositions for various diseases. But how should we decide on the diseases for which screening should be done and on recommendations for how it should be implemented? We use the examples of prostate cancer and genetic screening to show the importance of considering screening as an ongoing population-based intervention with beneficial and harmful effects, and not simply the use of a test. Assessing whether screening should be recommended and implemented for any named disease is therefore a multi-dimensional task in health technology assessment. There are several countries that already use established processes and criteria to assess the appropriateness of screening. We argue that the Swiss healthcare system needs a nationwide screening commission mandated to conduct appropriate evidence-based evaluation of the impact of proposed screening interventions, to issue evidence-based recommendations, and to monitor the performance of screening programmes introduced. Without explicit processes there is a danger that beneficial screening programmes could be neglected and that ineffective, and potentially harmful, screening procedures could be introduced.