Packing a trunk : a physically based approach with full motional freedom

Geometric packing problems may be formulated mathematically as constrained optimization problems. But finding a good solution is a challenging task. The more complicated the geometry of the container or the objects to be packed, the more complex the non-penetration constraints become. In this work we propose the use of a physics engine that simulates a system of colliding rigid bodies. It is a tool to resolve interpenetration conflicts and to optimize configurations locally. We develop an efficient and easy-to-implement physics engine that is specialized for collision detection and contact handling. In succession of the development of this engine a number of novel algorithms for distance calculation and intersection volume were designed and imple- mented, which are presented in this work. They are highly specialized to pro- vide fast responses for cuboids and triangles as input geometry whereas the concepts they are based on can easily be extended to other convex shapes. Especially noteworthy in this context is our ε-distance algorithm - a novel application that is not only very robust and fast but also compact in its im- plementation. Several state-of-the-art third party implementations are being presented and we show that our implementations beat them in runtime and robustness. The packing algorithm that lies on top of the physics engine is a Monte Carlo based approach implemented for packing cuboids into a container described by a triangle soup. We give an implementation for the SAE J1100 variant of the trunk packing problem. We compare this implementation to several established approaches and we show that it gives better results in faster time than these existing implementations.

Microarray based real-time analysis of nucleic acid hybridization kinetics and thermodynamics

Ziel dieser Dissertation ist die experimentelle Charakterisierung und quantitative Beschreibung der Hybridisierung von komplementären Nukleinsäuresträngen mit oberflächengebundenen Fängermolekülen für die Entwicklung von integrierten Biosensoren. Im Gegensatz zu lösungsbasierten Verfahren ist mit Microarray Substraten die Untersuchung vieler Nukleinsäurekombinationen parallel möglich. Als biologisch relevantes Evaluierungssystem wurde das in Eukaryoten universell exprimierte Actin Gen aus unterschiedlichen Pflanzenspezies verwendet. Dieses Testsystem ermöglicht es, nahe verwandte Pflanzenarten auf Grund von geringen Unterschieden in der Gen-Sequenz (SNPs) zu charakterisieren. Aufbauend auf dieses gut studierte Modell eines House-Keeping Genes wurde ein umfassendes Microarray System, bestehend aus kurzen und langen Oligonukleotiden (mit eingebauten LNA-Molekülen), cDNAs sowie DNA und RNA Targets realisiert. Damit konnte ein für online Messung optimiertes Testsystem mit hohen Signalstärken entwickelt werden. Basierend auf den Ergebnissen wurde der gesamte Signalpfad von Nukleinsärekonzentration bis zum digitalen Wert modelliert. Die aus der Entwicklung und den Experimenten gewonnen Erkenntnisse über die Kinetik und Thermodynamik von Hybridisierung sind in drei Publikationen zusammengefasst die das Rückgrat dieser Dissertation bilden. Die erste Publikation beschreibt die Verbesserung der Reproduzierbarkeit und Spezifizität von Microarray Ergebnissen durch online Messung von Kinetik und Thermodynamik gegenüber endpunktbasierten Messungen mit Standard Microarrays. Für die Auswertung der riesigen Datenmengen wurden zwei Algorithmen entwickelt, eine reaktionskinetische Modellierung der Isothermen und ein auf der Fermi-Dirac Statistik beruhende Beschreibung des Schmelzüberganges. Diese Algorithmen werden in der zweiten Publikation beschrieben. Durch die Realisierung von gleichen Sequenzen in den chemisch unterschiedlichen Nukleinsäuren (DNA, RNA und LNA) ist es möglich, definierte Unterschiede in der Konformation des Riboserings und der C5-Methylgruppe der Pyrimidine zu untersuchen. Die kompetitive Wechselwirkung dieser unterschiedlichen Nukleinsäuren gleicher Sequenz und die Auswirkungen auf Kinetik und Thermodynamik ist das Thema der dritten Publikation. Neben der molekularbiologischen und technologischen Entwicklung im Bereich der Sensorik von Hybridisierungsreaktionen oberflächengebundener Nukleinsäuremolekülen, der automatisierten Auswertung und Modellierung der anfallenden Datenmengen und der damit verbundenen besseren quantitativen Beschreibung von Kinetik und Thermodynamik dieser Reaktionen tragen die Ergebnisse zum besseren Verständnis der physikalisch-chemischen Struktur des elementarsten biologischen Moleküls und seiner nach wie vor nicht vollständig verstandenen Spezifizität bei.

Tissue engineering strategies for biomaterial-based anticancer drug delivery and enhancement of angiogenesis in tumor-resected bone

Patienten, die an Osteosarkom leiden werden derzeit mit intravenös applizierten krebstherapeutischen Mitteln nach Tumorresektion behandelt, was oftmals mit schweren Nebenwirkungen und einem verzögerten Knochenheilungsprozess einhergeht. Darüber hinaus treten vermehrt Rezidive aufgrund von verbleibenden neoplastischen Zellen an der Tumorresektionsstelle auf. Erfolgreiche Knochenregeneration und die Kontrolle von den im Gewebe verbleibenden Krebszellen stellt eine Herausforderung für das Tissue Engineering nach Knochenverlust durch Tumorentfernung dar. In dieser Hinsicht scheint der Einsatz von Hydroxyapatit als Knochenersatzmaterial in Kombination mit Cyclodextrin als Medikamententräger, vielversprechend. Chemotherapeutika können an Biomaterial gebunden und direkt am Tumorbett über einen längeren Zeitraum freigesetzt werden, um verbliebene neoplastische Zellen zu eliminieren. Lokal applizierte Chemotherapie hat diverse Vorteile, einschließlich der direkten zytotoxischen Auswirkung auf lokale Zellen, sowie die Reduzierung schwerer Nebenwirkungen. Diese Studie wurde durchgeführt, um die Funktionsfähigkeit eines solchen Arzneimittelabgabesystems zu bewerten und um Strategien im Bereich des Tissue Engineerings zu entwickeln, die den Knochenheilungsprozess und im speziellen die Vaskularisierung fördern sollen. Die Ergebnisse zeigen, dass nicht nur Krebszellen von der chemotherapeutischen Behandlung betroffen sind. Primäre Endothelzellen wie zum Beispiel HUVEC zeigten eine hohe Sensibilität Cisplatin und Doxorubicin gegenüber. Beide Medikamente lösten in HUVEC ein tumor-unterdrückendes Signal durch die Hochregulation von p53 und p21 aus. Zudem scheint Hypoxie einen krebstherapeutischen Einfluss zu haben, da die Behandlung sensitiver HUVEC mit Hypoxie die Zellen vor Zytotoxizität schützte. Der chemo-protektive Effekt schien deutlich weniger auf Krebszelllinien zu wirken. Diese Resultate könnten eine mögliche chemotherapeutische Strategie darstellen, um den Effekt eines zielgerichteten Medikamenteneinsatzes auf Krebszellen zu verbessern unter gleichzeitiger Schonung gesunder Zellen. Eine erfolgreiche Integration eines Systems, das Arzneimittel abgibt, kombiniert mit einem Biomaterial zur Stabilisierung und Regeneration, könnte gesunden Endothelzellen die Möglichkeit bieten zu proliferieren und Blutgefäße zu bilden, während verbleibende Krebszellen eliminiert werden. Da der Prozess der Knochengeweberemodellierung mit einer starken Beeinträchtigung der Lebensqualität des Patienten einhergeht, ist die Beschleunigung des postoperativen Heilungsprozesses eines der Ziele des Tissue Engineerings. Die Bildung von Blutgefäßen ist unabdingbar für eine erfolgreiche Integration eines Knochentransplantats in das Gewebe. Daher ist ein umfangreich ausgebildetes Blutgefäßsystem für einen verbesserten Heilungsprozess während der klinischen Anwendung wünschenswert. Frühere Experimente zeigen, dass sich die Anwendung von Ko-Kulturen aus humanen primären Osteoblasten (pOB) und humanen outgrowth endothelial cells (OEC) im Hinblick auf die Bildung stabiler gefäßähnlicher Strukturen in vitro, die auch effizient in das mikrovaskuläre System in vivo integriert werden konnten, als erfolgreich erweisen. Dieser Ansatz könnte genutzt werden, um prä-vaskularisierte Konstrukte herzustellen, die den Knochenheilungsprozess nach der Implantation fördern. Zusätzlich repräsentiert das Ko-Kultursystem ein exzellentes in vitro Model, um Faktoren, welche stark in den Prozess der Knochenheilung und Angiogenese eingebunden sind, zu identifizieren und zu analysieren. Es ist bekannt, dass Makrophagen eine maßgebliche Rolle in der inflammatorisch-induzierten Angiogenese spielen. In diesem Zusammenhang hebt diese Studie den positiven Einfluss THP-1 abgeleiteter Makrophagen in Ko-Kultur mit pOB und OEC hervor. Die Ergebnisse zeigten, dass die Anwendung von Makrophagen als inflammatorischer Stimulus im bereits etablierten Ko-Kultursystem zu einer pro-angiogenen Aktivierung der OEC führte, was in einer signifikant erhöhten Bildung blutgefäßähnlicher Strukturen in vitro resultierte. Außerdem zeigte die Analyse von Faktoren, die in der durch Entzündung hervorgerufenen Angiogenese eine wichtige Rolle spielen, eine deutliche Hochregulation von VEGF, inflammatorischer Zytokine und Adhäsionsmoleküle, die letztlich zu einer verstärkten Vaskularisierung beitragen. Diese Resultate werden dem Einfluss von Makrophagen zugeschrieben und könnten zukünftig im Tissue Engineering eingesetzt werden, um den Heilungsprozess zu beschleunigen und damit die klinische Situation von Patienten zu verbessern. Darüber hinaus könnte die Kombination der auf Ko-Kulturen basierenden Ansätze für das Knochen Tissue Engineering mit einem biomaterial-basierenden Arzneimittelabgabesystem zum klinischen Einsatz kommen, der die Eliminierung verbliebener Krebszellen mit der Förderung der Knochenregeneration verbindet.

Einfluss der Landnutzungsänderung auf die Variabilität von Grundwasserneubildungs- und Sickerwasserrate - Qualitative Grundwassergefährdungsabschätzung mit einem GIS -

Ziel der Arbeit ist die Entwicklung eines allgemeingültigen, im mittleren Maßstabsbereich durchgeführten, GIS-Bewertungsverfahrens zur Ermittlung der Grundwasserneubildungsrate unter Berücksichtigung einer langzeitlichen Landnutzungsänderung sowie die Darstellung eines Szenarios zur Grundwassergefährdungsabschätzung für ausgewählte rüstungsspezifi-sche organische Verbindungen. Das Untersuchungsgebiet befindet sich in einem während der beiden Weltkriege stark militär- und rüstungstechnisch genutzten Raum. Die Beurtei-lungsszenarien der Grundwassergefährdung erfolgen rein qualitativ.Die Abhängigkeit der Grundwasserneubildungsrate von der Landnutzungsänderung ist deut-lich zu erkennen. Mit zunehmender Flächenversiegelung, einher gehend mit veränderten Sickerwasserraten und des oberflächennahen Abflusses, reduziert sich die Grundwasser-neubildungsrate deutlich. Die Abschätzung der Grundwassergefährdung für die sprengstofftypischen Verbindungen erfolgt im ersten Schritt emissionsbezogen für die ungesättigte Zone unter Berücksichtigung der Standort- und Bodeneigenschaften und der physikalisch-chemischen Stoffeigenschaften. Im zweiten Schritt erfolgt eine immissionsbezogene Betrachtung der potenziellen Belastun-gen von Trinkwasserbrunnen.Trotz starker Generalisierungseffekte bietet dieser stoffspezifische Bewertungsansatz in Verbindung mit physikalischen Methoden für organische Verbindungen einen guten ersten Überblick über eine potenzielle Gefährdungen des Grundwassers. Die Datenbestände der entwickelten GIS-Anwendung sind leicht erweiterbar, so dass eine Abschätzung der potenzi-ellen Gefährdung auch für andere organische Stoffgruppen sowie auch eine Übertragung auf andere Untersuchungsgebiete möglich ist.

Reinforcement Lernen mit Regularisierungsnetzwerken

Die Arbeit behandelt das Problem der Skalierbarkeit von Reinforcement Lernen auf hochdimensionale und komplexe Aufgabenstellungen. Unter Reinforcement Lernen versteht man dabei eine auf approximativem Dynamischen Programmieren basierende Klasse von Lernverfahren, die speziell Anwendung in der Künstlichen Intelligenz findet und zur autonomen Steuerung simulierter Agenten oder realer Hardwareroboter in dynamischen und unwägbaren Umwelten genutzt werden kann. Dazu wird mittels Regression aus Stichproben eine Funktion bestimmt, die die Lösung einer "Optimalitätsgleichung" (Bellman) ist und aus der sich näherungsweise optimale Entscheidungen ableiten lassen. Eine große Hürde stellt dabei die Dimensionalität des Zustandsraums dar, die häufig hoch und daher traditionellen gitterbasierten Approximationsverfahren wenig zugänglich ist. Das Ziel dieser Arbeit ist es, Reinforcement Lernen durch nichtparametrisierte Funktionsapproximation (genauer, Regularisierungsnetze) auf -- im Prinzip beliebig -- hochdimensionale Probleme anwendbar zu machen. Regularisierungsnetze sind eine Verallgemeinerung von gewöhnlichen Basisfunktionsnetzen, die die gesuchte Lösung durch die Daten parametrisieren, wodurch die explizite Wahl von Knoten/Basisfunktionen entfällt und so bei hochdimensionalen Eingaben der "Fluch der Dimension" umgangen werden kann. Gleichzeitig sind Regularisierungsnetze aber auch lineare Approximatoren, die technisch einfach handhabbar sind und für die die bestehenden Konvergenzaussagen von Reinforcement Lernen Gültigkeit behalten (anders als etwa bei Feed-Forward Neuronalen Netzen). Allen diesen theoretischen Vorteilen gegenüber steht allerdings ein sehr praktisches Problem: der Rechenaufwand bei der Verwendung von Regularisierungsnetzen skaliert von Natur aus wie O(n**3), wobei n die Anzahl der Daten ist. Das ist besonders deswegen problematisch, weil bei Reinforcement Lernen der Lernprozeß online erfolgt -- die Stichproben werden von einem Agenten/Roboter erzeugt, während er mit der Umwelt interagiert. Anpassungen an der Lösung müssen daher sofort und mit wenig Rechenaufwand vorgenommen werden. Der Beitrag dieser Arbeit gliedert sich daher in zwei Teile: Im ersten Teil der Arbeit formulieren wir für Regularisierungsnetze einen effizienten Lernalgorithmus zum Lösen allgemeiner Regressionsaufgaben, der speziell auf die Anforderungen von Online-Lernen zugeschnitten ist. Unser Ansatz basiert auf der Vorgehensweise von Recursive Least-Squares, kann aber mit konstantem Zeitaufwand nicht nur neue Daten sondern auch neue Basisfunktionen in das bestehende Modell einfügen. Ermöglicht wird das durch die "Subset of Regressors" Approximation, wodurch der Kern durch eine stark reduzierte Auswahl von Trainingsdaten approximiert wird, und einer gierigen Auswahlwahlprozedur, die diese Basiselemente direkt aus dem Datenstrom zur Laufzeit selektiert. Im zweiten Teil übertragen wir diesen Algorithmus auf approximative Politik-Evaluation mittels Least-Squares basiertem Temporal-Difference Lernen, und integrieren diesen Baustein in ein Gesamtsystem zum autonomen Lernen von optimalem Verhalten. Insgesamt entwickeln wir ein in hohem Maße dateneffizientes Verfahren, das insbesondere für Lernprobleme aus der Robotik mit kontinuierlichen und hochdimensionalen Zustandsräumen sowie stochastischen Zustandsübergängen geeignet ist. Dabei sind wir nicht auf ein Modell der Umwelt angewiesen, arbeiten weitestgehend unabhängig von der Dimension des Zustandsraums, erzielen Konvergenz bereits mit relativ wenigen Agent-Umwelt Interaktionen, und können dank des effizienten Online-Algorithmus auch im Kontext zeitkritischer Echtzeitanwendungen operieren. Wir demonstrieren die Leistungsfähigkeit unseres Ansatzes anhand von zwei realistischen und komplexen Anwendungsbeispielen: dem Problem RoboCup-Keepaway, sowie der Steuerung eines (simulierten) Oktopus-Tentakels.