Dissertations / Theses on the topic 'Temporal constraints'
To see the other types of publications on this topic, follow the link: Temporal constraints.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Temporal constraints.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Choi, Ho Jin. "Controlling temporal constraints in planning." Thesis, Imperial College London, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.307601.
Full text
2
Ralley, Richard. "Spatial constraints on attention." Thesis, University of Hertfordshire, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.302301.
Full text
3
Sakai, Rodrigo Katsumoto. "Extensão de um SGBD para incluir o gerenciamento da informação temporal." Universidade de São Paulo, 2007. http://www.teses.usp.br/teses/disponiveis/3/3141/tde-01042009-143157/.
Full textAbstract:
O fator temporal é uma variável natural da maioria dos sistemas de informação, pois no mundo real os eventos ocorrem de maneira dinâmica, modicando continuamente os valores dos seus objetos no decorrer do tempo. Muitos desses sistemas precisam registrar essa modicação e atribuir os instantes de tempo em que cada informação foi válida no sistema. Este trabalho reúne as características relacionadas aos Bancos de Dados Temporais e Bancos de Dados Objeto-Relacionais. O objetivo primordial é propor uma forma de implementar alguns aspectos temporais, desenvolvendo um módulo que faça parte das características e funcionalidades internas de um SGBD. O módulo temporal contempla principalmente a parte de restrições de integridade temporal que é utilizada para manter a consistência da informação temporal armazenada. Para isso, é proposto um novo tipo de dado que melhor representa as marcas temporais dos objetos. Uma parte importante para a implementação desse projeto é a utilização de um SGBD objeto-relacional que possui algumas características orientadas a objetos que permitem a extensão de seus recursos, tornando-o capaz de gerenciar alguns aspectos temporais. O módulo temporal desenvolvido torna esses aspectos temporais transparentes para o usuário. Por conseqüência, esses usuários são capazes de utilizar os recursos temporais com maior naturalidade.The temporal factor is a natural variable of the majority of the information systems, therefore in the real world the events occur in dynamic way, modifying continuously the values of its objects in elapsing of the time. Many of these systems need to register this modication and to attribute the instants of time where each information was valid in the system. This work congregates the characteristics related to the Temporal Databases and Object-Relational Databases. The primordial objective is to consider a form to implement some temporal aspects, developing a module that is part of the characteristics and internal functionalities of a DBMS. The temporal module mainly contemplates the part of restrictions of temporal integrity that is used to keep the consistency of the stored temporal information. For this, a new data type is proposed that better represent the objects timestamps. An important part for the implementation of this project is the use of a object-relational DBMS that has some object-oriented characteristics that allow the extension of its resources, becoming capable to manage some temporal aspects. The developed temporal module becomes these transparent temporal aspects for the user. For consequence, these users are capable to use the temporal resources more naturally.
4
Sandström, Kristian. "Enforcing Temporal Constraints in Embedded Control Systems." Doctoral thesis, KTH, Machine Design, 2002. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-3328.
Full text
5
Ullberg, Jonas. "Towards Continous Activity Monitoring with Temporal Constraints." Thesis, Örebro University, School of Science and Technology, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:oru:diva-10579.
Full textAbstract:
Public demand for intelligent services in their home environments can be expected to grow in the near future once the required technology becomes more widely available and mature. Many intelligent home services cannot be provided in a purely reactive fashion though since they require contextual knowledge about the environment and most importantly the activities the residents are engaged in at any given time. This poses a problem since information about a human’s behavior is not easily accessible and has to be recognized from aggregated sensor data in most cases. Numerous activity recognition techniqueshave been studied in the literature. In this thesis we focus on one such technique which takes a temporal reasoning approach to activity recognition, namely recognizing activities by planning for them with a temporal planner. OMPS is an example of such a planner that has been used in previous work to recognize activities of humans in domestic environments. An important requirement for monitoring activities in a real world application is the ability to do so continuously and reliably. Two shortcomings in the previous approach hindered OMPS’s capability to meet this requirement, namely maintaining the performance of the activity recognition over long monitoring horizons, and ensuring future temporal consistency of recognized activities. This thesis will define the two problems, detail their solutions, and finally evaluate the modified system with the corresponding changes implemented.
6
Owuor, Dickson Odhiambo. "Capturing the temporal constraints of gradual patterns." Thesis, Montpellier, 2020. http://www.theses.fr/2020MONTS019.
Full textAbstract:
La recherche de motifs fréquents permet d’extraire les corrélations d’attributs par le biais de règles graduelles comme: “plus il y a de X, plus il y a de Y”. Ces corrélations sont utiles pour identifier et isoler des relations entre les attributs qui peuvent ne pas être évidentes grâce à des analyses rapides des données. Par exemple, un chercheur peut appliquer une telle recherche pour déterminer quels attributs d’un ensemble de données présentent des corrélations inconnues afin de les isoler pour une exploration plus approfondie ou une analyse. Supposons que le chercheur dispose d’un ensemble de données qui possède les attributs suivants : âge, montant du salaire, du nombre d’enfants et du niveau d’éducation. Un motif graduel extrait peut prendre la forme “plus le niveau d’éducation est bas, plus le salaire est élevé”. Étant donné que cette relation est rare, il peut être intéressant pour le chercheur de mettre davantage l’accent sur ce phénomène afin de comprendre. Les techniques de recherche de motifs graduels existantes extraient des motifs graduels en (1) générant des les candidats de l’ensemble d’éléments, (2) validant des candidats et (3) en élaguant des candidats invalides en fonction sur la propriété d’anti-monotonie. Cette propriété d’anti-monotonie est telle qu’un candidat est considéré comme invalide si l’un de ses sous-ensembles est invalide. Cette propriété améliore l’efficacité du processus d’élagage. L’efficacité de la génération d’ensembles de candidats peut être améliorée en utilisant une approche heuristique qui optimise le processus. Dans ce travail, nous proposons une technique d’optimisation par des colonies de fourmis qui utilise une approche probabiliste imitant le comportement des fourmis biologiques en cherchant le chemin le plus court pour trouver de la nourriture afin de résoudre des problèmes combinatoires. Nous appliquons la technique d’optimisation des colonies de fourmis afin de générer des candidats des motifs graduels dont la probabilité d’être valide est élevée. Ceci, couplé avec la propriété d'anti-monotonie, se traduit par le développement d’une méthode efficace. Dans notre deuxième contribution, nous étendons l’extraction de modèles graduels existante à l’extraction de motifs graduels avec un décalage temporel approximatif entre ses attributs affectés. Un tel modèle est appelé motif graduel temporel flou. Cela peut prendre par exemple la forme: “plus il y a de X, plus il y a de Y presque 3 mois plus tard” Ces modèles ne peuvent être extraits que de séries de données chronologiques car ils impliquent la présence de l’aspect temporel. Dans notre troisième contribution, nous proposons une donnée modèle de croisement qui permet l’intégration d’implémentations d’algorithmes d’exploration de modèle graduel dans une plateforme Cloud. Cette contribution est motivée par la prolifération des applications IoT dans presque tous les domaines de notre société, ce qui s’accompagne de la fourniture de données chronologiques à grande échelle de différentes sources. Il peut être intéressant pour un chercheur de croiser différentes données de séries chronologiques dans le but d’extraire des motifs graduels temporels des attributs cartographiés. Par exemple un ensemble de données ‘humidité’ peut être temporairement croisé avec un ensemble de données indépendant qui enregistre ‘Population de mouches’, et un schéma peut prendre la forme: “plus l’humidité est élevée, plus vole presque 2 heures plus tard”. Notre méthode met l’accent sur l’intégration de l’exploitation des techniques les plus récentes de plate-formes Cloud, car cela facilite l’accès à nos méthodes en allégeant l’installation et la configuration pour les utilisateurs, permettant ainsi aux utilisateurs de passer plus de temps à se concentrer sur les phénomènes qu’ils analysentGradual pattern mining allows for extraction of attribute correlations through gradual rules such as: “the more X, the more Y”. Such correlations are useful in identifying and isolating relationships among the attributes that may not be obvious through quick scans on a data set. For instance, a researcher may apply gradual pattern mining to determine which attributes of a data set exhibit unfamiliar correlations in order to isolate them for deeper exploration or analysis. Assume the researcher has a data set which has the following attributes: age, amount of salary, number of children, and education level. An extracted gradual pattern may take the form “the lower the education level, the higher the salary”. Since this relationship is uncommon, it may interest the researcher in putting more focus on this phenomenon in order to understand it. As for many gradual pattern mining approaches, there is a key challenge to deal with huge data sets because of the problem of combinatorial explosion. This problem is majorly caused by the process employed for generating candidate gradual item sets. One way to improve the process of generating candidate gradual item sets involves optimizing this process using a heuristic approach. In this work, we propose an ant colony optimization technique which uses a popular probabilistic approach that mimics the behavior biological ants as they search for the shortest path to find food in order to solve combinatorial problems. We apply the ant colony optimization technique in order to generate gradual item set candidates whose probability of being valid is high. This coupled with the anti-monotonicity property, results in the development of a highly efficient ant-based gradual pattern mining technique. In our second contribution, we extend an existing gradual pattern mining technique to allow for extraction of gradual patterns together with an approximated temporal lag between the affected gradual item sets. Such a pattern is referred to as a fuzzy-temporal gradual pattern and it may take the form: “the more X, the more Y, almost 3 months later”. The addition of temporal dimension into the proposed approach makes it even worse regarding combinatorial explosion due to added task of searching for the most relevant time gap. In our third contribution, we propose a data crossing model that allows for integration of mostly gradual pattern mining algorithm implementations into a Cloud platform. This contribution is motivated by the proliferation of IoT applications in almost every area of our society and this comes with provision of large-scale time-series data from different sources. It may be interesting for a researcher to cross different time-series data with the aim of extracting temporal gradual patterns from the mapped attributes. For instance, a ‘humidity’ data set may be temporally crossed with an unrelated data set that records the ‘population of flies’, and a pattern may take the form: “the higher the humidity, the higher the number of flies, almost 2 hours later”. Again, the study emphasizes integration of gradual pattern mining techniques into a Cloud platform because this will facilitate their access on a subscription basis. This alleviates installation and configuration hustles for the users; therefore, it allows them to spend more time focusing on the phenomena they are studying
7
Jobczyk, Krystian. "Temporal planning with fuzzy constraints and preferences." Thesis, Normandie, 2017. http://www.theses.fr/2017NORMC259/document.
Full textAbstract:
La planification temporelle constitue conceptuellement une partie du raisonnement temporelle et il appartient au domaine de recherche de l'intelligence artificielle. La planification temporelle peut être considérée comme une extension de la planification classique par les aspects temporels de l'action. La planification temporelle est généralement complété par des préférences ou des types différents decontraintes imposées à l'exécution des actiones. Il existe de nombreuses approches à ce problème. D'une part, il existe différents paradigmes pour la planification temporelle, par example: la planification par un recherche d'une solution optimale dans des graphes de planification (STRIPS), la planification via la satisfiabilité ou la planification pardes processus de Markov. Ces approches sont mutuellement incompatibles. D'autre part, la planification temporelle exige une sujet-spécification – comme il est défini d'une manière méthodologique. Selon cette situation, cette thèse vise à proposer une analyse approfondi de la planification avec des contraintes floues qui contient quelques remèdes à ces difficultés. À savoir, deux approches à la représentation et la modélisation de ces questions sont mises.Dans la première (chapitre 2, chapitre 3) - les relations floues d'Allen en tant que contraintes temporelles floues sont représentés par des normes de convolutions dans un espace de Banach des fonctions intégrables de Lebesgue. Cela nous permet de nous immergerles relations d'Allen dans les contextes computationnels de la planification temporelle (basée sur STRIPS et sur la procedure de Davis-Putnam) et d'élucider leur nature quantitative. Cette approche est développée dans un contexte des problèmes par systèmes multi-agents comme un sujet de cette approche. Dans les chapitres 4 et 5 les contraintes temporelles floues avec flou – introduit par préférences - sont représentées en termes logiques de la logique préférentielle de Halpern-Shoham. Cela nous permet d'adopter ces resultats dans une construction du contrôleur du plan. Cette approche est développée dans un contexte du problème du voyageur de commerce. Enfin, une tentative de réconcilier ces deux lignes de représentation des contraintes temporelles floues a été proposée dans le dernier chapitreTemporal planning forms conceptually a part of temporal reasoning and it belongs to research area of Artificial Intelligence and it may be seen as an extension of classical planning by temporal aspects of acting. Temporal planing is usually complemented by considering preferences or different types of temporal constraints imposed on execution of actions. There exist many approaches to this issue. One one hand, there are different paradigms to temporal planning, such as: planning via search in graphs (STRIPS), planning via satisfiability or planning in terms of Markov processes. These approaches are mutually incompatible. In addition, temporal planning requires a subject-specification as it is rather defined in a methodological way. On the other hand, temporal constraints are represented and modeled in different ways dependently on their quantitative or qualitative nature. In particular, Allen’s relations between temporal intervals – an important class of temporal constraints – do not have any quantitative aspects and cannot be considered in computational contexts. According to this situation, this PhD-thesis is aimed at the proposing a depth-analysis of temporal planning with fuzzy constraints which contains some remedies on these difficulties. Namely, two approaches to the representation and modeling of these issues are put forward. In the first one (chapter 2, chapter 3) – fuzzy Allen’s relations as fuzzy temporal constraints are represented by norms of convolutions in a Banach space of Lebesgue integrable functions. It allows us immerse Allen’s relations in the computational contexts of temporal planning (based on STRIPS and on DavisPutnam procedure) and to elucidate their quantitative nature. This approach is developed in a context of Multi-Agent Problem as a subject basis of this approach. In the second one (chapter 4, chapter 5) – fuzzy temporal constrains with fuzziness introduced by preferences are represented in a logical terms of Preferential Halpern-Shoham Logic. It allows us to adopt these result in a construction of the plan controller. This approach is developed in a context of Temporal Traveling Salesman Problem as a subject basis of this approach. Finally, an attempt to reconcile these two lines of representation of fuzzy temporal constraints was also proposed
8
Gruber, Wolfgang. "Modeling and transformation of workflows with temporal constraints." Berlin : Amsterdam : Aka, Akademische Verlagsgesellschaft ; IOS Press, 2004. http://catalog.hathitrust.org/api/volumes/oclc/57677828.html.
Full text
9
Cotroneo, Orazio. "Mining declarative process models with quantitative temporal constraints." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2021. http://amslaurea.unibo.it/24636/.
Full textAbstract:
Time has always been a subject of study in science, philosophy and religion. Time was referred by the ancient Greeks with two separate words: Chronos and Kairos. Chronos referring to the quantitative aspect of it, while Kairos referring to the qualitative part of it. In this work, time, as a measurement system for a given business context, would be explored in both of its forms.
Specifically in the last few years, embedding the notion of quantitative time in discovering declarative mining models has been a point of focus in research. The aim of this work is to enrich declarative process mining models with the notion of quantitative time, and then to adapt the discovery algorithm, inspired by Mooney in 1995, and then modified by Palmieri in 2020, to discover the enriched models.
10
Teytaut, Yann. "On temporal constraints for deep neural voice alignment." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS196.
Full textAbstract:
S’écouter, se répondre, faire se coïncider, se coordonner, s’accorder, se suivre, s’adapter, être à l’unisson, se synchroniser, s’aligner... Le riche vocabulaire dédié à la mise en correspondance dans le temps des activités humaines montre l’importance que revêt leur organisation temporelle. La communication humaine, multi-modale par nature, est pleinement concernée par cette problématique puisqu’il existe un écart sémantique entre les locutions orales et leurs séquences symboliques : comment bien interpréter un message écrit sans l’intonation vocale ? quel style performatif au delà d’une partition musicale figée ? Cette thèse se propose de révéler et expliquer les complexes relations entre les domaines audio et symbolique afin de réduire cet écart grâce à l’étude fine de l’inhérente temporalité contenue dans les enregistrements vocaux. Au coeur de cet objectif, se trouve la tâche d’alignement de voix qui vise à déterminer l’occurrence temporelle de symboles supposés présents dans un signal vocal. Ces travaux s’intéressent tout particulièrement au développement d’un modèle acoustique, ADAGIO, capable d’estimer de tels liens temps-symboles. Les récents progrès en apprentissage profond amènent à implémenter ADAGIO sous la forme d’un réseau de neurones profond dans un puissant formalisme générique : la “Classification Temporelle Connectioniste” (CTC). Cependant, la grande flexibilité offerte par la CTC est mise en défaut par son absence intrinsèque de garanties de prédictions temporellement précises. Les contributions clefs de cette recherche visent à renforcer la CTC par des contraintes temporelles supplémentaires pour améliorer la qualité des alignements déduits. Pour cela, trois tâches annexes de (1) reconstruction du contenu spectral, (2) propagation de la structure audio, et (3) monotonie guidée sont introduites et induisent un impact positif sur l’alignement entre voix, textes, et notes. Dès lors, ADAGIO contribue à de nombreuses applications pratiques au travers de collaborations telles que la synthèse vocale concaténative ou l’étude des stratégies de production expressives en jeu tant pour les attitudes sociales dans la parole que pour le style de chant dans des performances musicalesTo listen, to respond, to make coincide, to coordinate, to adjust, to follow, to adapt, to be in unison, to synchronize, to align... The rich vocabulary dedicated to the correspondence of human activities shows the importance of their temporal organization. Human communication, multi-modal by nature, is fully concerned by this problematic since there exists a semantic gap between oral locutions and their symbolic sequences: how to interpret a written message without the vocal intonation? what performative style beyond a fixed musical score? This thesis proposes to uncover the complex underlying relationships between the audio and symbolic domains in order to reduce this gap through the fine study of the inherent temporality contained in voice recordings. The voice alignment task lies at the core of this objective, as it aims to determine the temporal occurrence of symbols that are assumed to be present in a voice signal. This work notably focuses on the development of an acoustic model, ADAGIO, capable of estimating such time-symbol links. Recent progress in deep learning have led to implement ADAGIO as a deep neural network in a powerful generic formalism: the “Connectionist Temporal Classification” (CTC). However, the great flexibility offered by CTC is undermined by its intrinsic lack of guarantees for temporally accurate predictions. Therefore, the key contributions of this research consist in reinforcing CTC with additional temporal constraints to improve the quality of the inferred alignments. To do so, three ancillary tasks of (1) spectral content reconstruction; (2) audio structure propagation; and (3) guided monotony are introduced and induce a positive impact on the alignment between voices, texts, and notes. Then, ADAGIO contributes to many practical applications via collaborations such as concatenative speech synthesis or the study of expressive production strategies at play for both social attitudes in speech and singing style in musical performances
11
Taboada, Sophie. "Multi-Agent Motion Planning with Signal Temporal Logic Constraints." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-292870.
Full textAbstract:
Motion planning algorithms allow us to define a sequence of configurations to guide robots from a starting point to an ending goal while considering the environment’s and the robot’s constraints. As all robots and circumstances are different, motion planning can be adapted to fit into the system’s specifications and the user’s preferences. Temporal Logic (TL) has been used to enable the implementation of more complex missions. In this work, we are interested in using TL to establish the affiliation between robots in a multi-robot system, as well as their affiliation with features in the workspace. More specifically, Signal Temporal Logic (STL) is used to guide motion planning into respecting certain preferences linked to the robot’s motion behavior. In fact, user’s preferences are translated into STL formulas, that need to be respected by the motion planning. To achieve this, RRT* sampling-based algorithm is used to study the free space and to identify the best trajectory with the help of a cost analysis of all possible trajectories found. Here, RRT* is adapted to fit into multi-robot systems and to allow the simultaneous planning of trajectories for multiple robots. The robustness metric of STL quantifies the respect trajectories have for STL formulas and influences the cost function of the RRT*. The impact the robustness has on the cost function is responsible for the selection of trajectories with more respect for the STL formulas. The proposed multi-agent motion planning is tested in simulations with environments containing multiple obstacles and robots. To demonstrate the impact STL has on motion planning, a comparison is made between the trajectories extracted with and without the use of STL. These simulations include specific scenarios and different numbers of robots to test the developed algorithm. They deliver asymptotically optimal solutions. Finally, we conduct some hardware experiments up until four robots to present how the developed motion planning can be implemented in real life.Rörelseplaneringsalgoritmer låter oss definiera en sekvens av konfigurationer för att guida robotar från en startposition till en slutposition medan vi tar hänsyn till robotens och miljöns begränsningar. Eftersom alla robotar och omständigheter är olika kan rörelseplanering anpassas för att passa systemets specifikationer och användarens preferenser. Temporal Logik (TL) har använts för att möjliggöra implementationer av mer komplexa uppdrag. I detta arbete är vi intresserade av att använda TL för att fastställa anslutningen mellan robotar i ett multirobotsystem, samt mellan dessa robotar och egenskaper i deras arbetsmiljö. Mer specifikt används signaltemporär logik (eng: Signal Temporal Logic) (STL) för att anpassa rörelseplanering till att respektera vissa preferenser länkade till robotens rörelsebeteende. Faktum är att användarpreferenser översätts till STL-formler som behöver respekteras av rörelseplaneringen. För att uppnå detta används den samplingsbaserade algoritmen RRT* för att studera den fria ytan och för att identifiera den bästa rörelsebanan med hjälp av en kostanalys av alla funna möjliga rörelsebanor. Här anpassas RRT* för multirobotsystem och för att tillåta planering av rörelsebanor för flera robotar samtidigt. Robushetsmåttet för STL kvantifierar respekten som banorna har för STL-formler och påverkar RRT*: s kostnadsfunktion. Påverkan som robustheten har på kostfunktionen är ansvarig för valet av rörelsebanor som till högre grad respekterar STL-formlerna. Den föreslagna röresleplaneringen för flera agenter (eng: multi-agent) testas i simuleringar av miljöer med flera hinder och robotar. För att demonstrera vilken inverkan STL har på rörelseplanering görs en jämförelse mellan rörelsebanor som ges med och utan användning av STL. Dessa simuleringar inkluderar specifika scenarion och olika antal robotar för att testa den utvecklade algoritmen. De levererar asymptotiskt optimala lösningar. Slutligen genomför vi hårdvaruexperiment upp till och med fyra robotar för att presentera hur den framtagna rörelseplaneringsalgoritmen kan implementeras i verkligheten.
12
McInnes, Lynsey. "Spatial and temporal signatures of ecological constraints on diversity." Thesis, Imperial College London, 2011. http://hdl.handle.net/10044/1/7081.
Full textAbstract:
Broad-scale diversity patterns are the outcome of ecological and evolutionary processes that permit different numbers of species to coexist in a region. Many studies have focused on understanding the factors that allow a region to contain more species or a clade to diversify more rapidly. In this thesis, I shift focus to instead explore the constraints that prevent biodiversity increasing unbounded, using a combination of phylogenetic and biogeographical approaches across a range of temporal and spatial scales. In chapter two, I investigate conservatism (i.e., the tendency for more closely related species to be more similar) in the extremes of climate tolerated by a species, assessing the hypothesis that tightly-conserved tolerances are influential in determining the range extents of the species. By using global data from two vertebrate classes and a range of climatic variables, I assess the taxonomic generality of this hypothesis and identify the most strongly conserved variables. In chapters three and four, I develop novel macroecological analyses of factors that may limit the extent of geographic ranges and apply them to Afrotropical birds (chapter three) and all continental mammals (chapter four). Chapter five assesses how the spatial distribution of range limits can be used to compare species’ relative abilities to occupy available landscape. In chapter six, I present new methods to detect signals of past changes to diversity limits in phylogenies, using simulations to explore the power of phylogenies to reveal such patterns of diversity-dependent cladogenesis. In addition to the main research chapters, I append a synthetic review, of which I am joint first author, exploring the evolutionary underpinnings of large-scale species-area relationships. This thesis builds links between the macroecology of species’ distributions with the dynamics of clades over macroevolutionary timescales to determine how geography, phylogeny and history interact in the generation and maintenance of large-scale biodiversity.
13
Hagee, Daniel R. "Baseball Temporal Seam Recognition Study." The Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1458666577.
Full text
14
Bannikova, Marina. "Collective decision-making under the influence of bribers and temporal constraints." Doctoral thesis, Universitat Rovira i Virgili, 2016. http://hdl.handle.net/10803/396291.
Full textAbstract:
Jo estudio la connexió entre la corrupció i les característiques estructurals dels parlaments: nombre de seients, el nombre de partits representats, i regles de decisió adoptades. Amb l'aplicació d'enfocaments analítics i computacionals, a més de simulacions, mostro que el nombre mitjà de diputats que han de ser subornats disminueix a mesura que el nombre de partits augmenta, de manera que el suborn se sent encoratjat per un nombre cada vegada més gran de parts.
També investigo dues formes en que pot afectar el temps a la presa de decisions. En primer lloc, suggereixo un procediment de votació iteratiu en el que el retard en prendre una decisió és costós. Amb dos electors, dues opcions i un ordre de votació fix, demostro que en l’únic equilibri perfecte en subjocs, l’elector que vota primer, obté la seva opció preferida a l'inici del procediment. Si l'ordre s'inverteix en algun moment, identifico la condició sota la qual el votant que vota segon pot obtenir la seva opció preferida al principi.
En segon lloc, proposo un altre procediment de votació iterativa, permetent que els votants canvien els seus vots, però ara amb una data límit: una etapa que, si no s'ha pres una decisió, els resultats de la votació són pitjors. Mostro que (i) si hi ha temps suficient perquè tots els votants canviïn el seu vot, es prendrà una decisió, i (ii) si hi ha una alternativa preferida per la majoria dels votants, aquesta alternativa serà finalment triada. Afegeixo un estudi experimental que indica que fins i tot amb menys temps del necessari per a què cada votant pugui canviar el seu vot, els electors estaran d'acord amb una decisió de totes maneres.Estudio la conexión entre la corrupción y las características estructurales de los parlamentos: número de asientos, el número de partidos representados, y reglas de decisión adoptadas. Con la aplicación de enfoques analíticos y computacionales, además de simulaciones, muestro que el número medio de diputados que deben ser sobornados disminuye a medida que el número de partidos aumenta, por lo que el soborno se siente alentado por un número cada vez mayor de partes. También investigo dos formas en que puede afectar el tiempo en la toma de decisiones. En primer lugar, sugiero un procedimiento de votación iterativo en el que el retraso en tomar una decisión es costoso. Con dos electores, dos opciones y un orden de votación fijo, demuestro que en el único equilibrio perfecto en subjuegos, el elector que vota primero obtiene su opción preferida al inicio del procedimiento. Si el orden se invierte en algún momento, identifico la condición bajo la cual el votante que vota segundo puede obtener su opción preferida al principio. En segundo lugar, propongo otro procedimiento de votación iterativa, permitiendo que los votantes cambian sus votos, pero ahora con una fecha límite: una etapa que, si no se ha tomado una decisión, los resultados de la votación son peores. Muestro que (i) si hay tiempo suficiente para que todos los votantes cambien su voto, se tomará una decisión, y (ii) si hay una alternativa preferida por la mayoría de los votantes, esta alternativa será finalmente elegida. Añado un estudio experimental que indica que los electores estarán de acuerdo con una decisión aunque no haya tiempo sufficiente para que cada votante pueda cambiar su voto.
I study the connection between corruption and structural characteristics of parliaments: number of seats, the number of parties represented, and decision rules adopted. Applying analytical and computational approaches, and running simulations, I show that the average number of deputies needed to be bribed decreases as the number of parties increases, so bribery is encouraged by a growing number of parties. I also investigate two ways in which time may affect decision-making. First, I suggest an iterative voting procedure in which delay to reach a decision is costly. For two voters and two options, with a fixed voting order, I prove that in the unique subgame perfect equilibrium the voter who votes first obtains his most preferred option at the beginning of the procedure. If the fixed order is reversed once at some stage, I identify the condition under which the voter initially voting the second obtains this most preferred option, also at the beginning. Second, I propose another iterative voting procedure, allowing voters to change their votes, but now with a deadline: a stage such that, if no decision has been taken by then, the worst outcome results. I show that (i) if there is enough time for all the voters to change their vote, a decision will be taken, and (ii) if there is an alternative preferred by a majority of the voters, this alternative will be finally chosen. I add an experimental study indicating that even with less time necessary for every voter to change his vote, the voters will agree with a decision anyway.
15
Chen, Jingkai S. M. Massachusetts Institute of Technology. "Fast execution of temporal plans with mixed discrete-continuous state constraints." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/122406.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019Cataloged from PDF version of thesis.
Includes bibliographical references (pages 109-112).
There has been a dramatic rise in networked embedded systems that play a central role in complex tasks. To achieve high performance and robustness, these systems need to configure and reconfigure on the fly, in light of the task requirements and system states. Communications networks, for example, plan routes and allocate bandwidth resources over time for different communication activities, while respecting through-put, delay, loss, and deadline constraints. However, existing approaches use simple discrete models to achieve goal sequences and thus cannot provide a high-fidelity plan for complex plan specifications in terms of time and state. In this thesis, we deliver Amundsen, an efficient configuration manager that supports complex concurrent tasks over time and state by reasoning over high-fidelity models. These models can encode different actuation modes with discrete and continuous specifications and temporal influences.
Amundsen provides plans meeting mission requirements, which specify the timing of events, outline the mode changes throughout the mission, and allocate resources. The primary challenge of the configuration management problem is the computation required to handle the state and time constraints that are highly coupled. We address this challenge through the critical insight that the configuration management problem may be efficiently solved by dividing the problem into smaller subproblems such as scheduling and resource allocation, which is achieved by total ordering the events that represent time points in the goal specification. Each sub-problem may then be solved efficiently with existing highly optimized algorithms. We make two main technical contributions in this thesis. First, we identify the relevant sub-problems in the existing configuration management problems and provide tractable encodings.
Second, we provide an algorithm to efficiently order the stages of the problem by learning and communicating the requirements for successful solutions to the sub-problems. We provide empirical evidence of the efficiency of Amundsen by benchmarking against UnifyHistory, a state-of-the-art solver to configure systems by unifying multiple timelines, on a communication network simulator. We show that our approach can dynamically manage hundreds of network requests over a network with hundreds of communication links in simulated missions given strict time limits. Our approach is also able to find plans in 10 times as many scenarios as the baseline solver. The work described in this thesis thus significantly advances the configuration management problem, both theoretically and practically.
"Acknowledge DARPA for sponsoring this work for two and a half years"--Page 5
by Jingkai Chen.
S.M.
S.M. Massachusetts Institute of Technology, Department of Aeronautics and Astronautics
16
Doktor, Eugeniusz. "Organizing the execution of transportation tasks under spatial, temporal and other constraints." Thesis, University of Strathclyde, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.260543.
Full text
17
Jørgensen, Carl-Johan. "Scheduling activities under spatial and temporal constraints to populate virtual urban environments." Thesis, Rennes 1, 2015. http://www.theses.fr/2015REN1S033/document.
Full textAbstract:
Les modèles de simulation de foules visent généralement à produire des foules visuellement crédibles avec l'intention d'insuffler de la vie à des environnements virtuels. Notre travail se concentre sur la génération de comportements statistiquement cohérents qui peuvent être utilisés pour piloter des modèles de simulation de foules sur de longues périodes de temps, jusqu'à plusieurs jours. Dans les foules réelles, les comportements des individus dépendent principalement de l'activité qu'ils ont l'intention d'effectuer. La façon d’ordonnancer cette activité repose sur l'interaction étroite qui existe entre l'environnement, les contraintes spatiales et temporelles associées à l'activité et les caractéristiques personnelles des individus. Par rapport à l'état de l'art, notre modèle gérer mieux cette interaction. Nos principales contributions se situent dans le domaine de l'ordonnancement d'activités et de la planification de chemin. Dans un premier temps, nous proposons un processus d'ordonnancement d'activités individuelles et son extension aux activités coopératives. Basé sur les descriptions de l'environnement, des activités désirées et des caractéristiques des agents, ces processus génèrent une séquence de la tâche pour chaque agent. Des lieux où ces tâches doivent être effectuées sont sélectionnés et un timing relâché est produit. Cet ordonnancement est compatible avec les contraintes spatiales et temporelles liées à l'environnement et à l'activité prévue par l'agent et par d'autres agents en coopération. Il prend également en compte les caractéristiques personnelles des agents, induisant de la diversité dans les ordonnancements produits. Nous montrons que notre modèle produit des comportements statistiquement cohérents avec ceux produits par des personnes dans les mêmes situations. Dans un second temps, nous proposons un processus de planification de chemins hiérarchique. Il repose sur un processus d'analyse de l'environnement automatique qui produit une représentation hiérarchique sémantiquement cohérente des villes virtuelles. La nature hiérarchique de cette représentation est utilisée pour modéliser différents niveaux de prise de décisions. Un chemin grossier est d'abord calculé, puis raffiné pendant la navigation lorsque de l'information pertinente est disponible, permettant ainsi à l'agent d'adapter son chemin à des événements inattendus. Le modèle proposé gère des décisions rationnelles à long terme guidant la navigation des agents dans les villes virtuelles. Il prend en compte la forte relation entre le temps, l'espace et l'activité pour produire les comportements des agents plus crédibles de. Il peut être utilisé pour peupler facilement des villes virtuelles avec des foules au sein desquelles des phénomènes observables émergent de l'activité individuelleCrowd simulation models usually aim at producing visually credible crowds with the intent of giving life to virtual environments. Our work focusses on generating statistically consistent behaviours that can be used to pilot crowd simulation models over long periods of time, up to multiple days. In real crowds, people's behaviours mainly depend on the activities they intend to perform. The way this activity is scheduled rely on the close interaction between the environment, space and time constraints associated with the activity and personal characteristics of individuals. Compared to the state of the art, our model better handle this interaction. Our main contributions lie in the domain of activity scheduling and path planning. First, we propose an individual activity scheduling process and its extension to cooperative activity scheduling. Based on descriptions of the environment, of intended activities and of agents' characteristics, these processes generate a task schedule for each agent. Locations where the tasks should be performed are selected and a relaxed agenda is produced. This task schedule is compatible with spatial and temporal constraints associated with the environment and with the intended activity of the agent and of other cooperating agents. It also takes into account the agents personal characteristics, inducing diversity in produced schedules. We show that our model produces schedules statistically coherent with the ones produced by humans in the same situations. Second, we propose a hierarchical path-planning process. It relies on an automatic environment analysis process that produces a semantically coherent hierarchical representation of virtual cities. The hierarchical nature of this representation is used to model different levels of decision making related to path planning. A coarse path is first computed, then refined during navigation when relevant information is available. It enable the agent to seamlessly adapt its path to unexpected events. The proposed model handles long term rational decisions driving the navigation of agents in virtual cities. It considers the strong relationship between time, space and activity to produce more credible agents' behaviours. It can be used to easily populate virtual cities in which observable crowd phenomena emerge from individual activities
18
Dutia, Dharini. "Multi-Robot Task Allocation and Scheduling with Spatio-Temporal and Energy Constraints." Digital WPI, 2019. https://digitalcommons.wpi.edu/etd-theses/1298.
Full textAbstract:
Autonomy in multi-robot systems is bounded by coordination among its agents. Coordination implies simultaneous task decomposition, task allocation, team formation, task scheduling and routing; collectively termed as task planning. In many real-world applications of multi-robot systems such as commercial cleaning, delivery systems, warehousing and inventory management: spatial & temporal constraints, variable execution time, and energy limitations need to be integrated into the planning module. Spatial constraints comprise of the location of the tasks, their reachability, and the structure of the environment; temporal constraints express task completion deadlines. There has been significant research in multi-robot task allocation involving spatio-temporal constraints. However, limited attention has been paid to combine them with team formation and non- instantaneous task execution time. We achieve team formation by including quota constraints which ensure to schedule the number of robots required to perform the task. We introduce and integrate task activation (time) windows with the team effort of multiple robots in performing tasks for a given duration. Additionally, while visiting tasks in space, energy budget affects the robots operation time. We map energy depletion as a function of time to ensure long-term operation by periodically visiting recharging stations. Research on task planning approaches which combines all these conditions is still lacking. In this thesis, we propose two variants of Team Orienteering Problem with task activation windows and limited energy budget to formulate the simultaneous task allocation and scheduling as an optimization problem. A complete mixed integer linear programming (MILP) formulation for both variants is presented in this work, implemented using Gurobi Optimizer and analyzed for scalability. This work compares the different objectives of the formulation like maximizing the number of tasks visited, minimizing the total distance travelled, and/or maximizing the reward, to suit various applications. Finally, analysis of optimal solutions discover trends in task selection based on the travel cost, task completion rewards, robot's energy level, and the time left to task inactivation.
19
Abbod, T. H. "Developing a semantic integrity constraints system with temporal dimension to support a database." Thesis, Open University, 1988. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.382588.
Full text
20
Currim, Faiz A. "Spatio-temporal set-based constraints in conceptual modeling: A theoretical framework and evaluation." Diss., The University of Arizona, 2004. http://hdl.handle.net/10150/280599.
Full textAbstract:
The objective of this research is to define and evaluate a framework and detailed specifications for capturing spatio-temporal set-based constraints during conceptual database design. The proposed framework aims to bridge the gap between rule discovery during requirements analysis and rule implementation during the logical design phase. It also aids conceptual design by providing the analyst with a structured way to determine rules from the client. Our research approach takes advantage of multiple research methods in: (i) defining a formal framework and using it to specify spatio-temporal constraints employing set theory and first order logic, (ii) evaluating expressiveness of the proposed framework using a case study, and (iii) evaluating user analyst performance and perceived ease of use via a laboratory experiment. A case study at the Internal Review Board of a major public university demonstrates that the framework is expressive enough to capture discovered rules in this application, and that the rules can be translated to schema constraints at the logical level. The experiment provides answers regarding analyst performance using the framework, perceived ease of use, and explores the utility of the framework as a structured approach to elicit rules from clients. Future work includes additional case studies to test the framework, experiments to establish perceived usefulness from the perspective of real-world analysts, and broadening the framework to incorporate additional types of rules.
21
Chen, Jinjun, and n/a. "Towards effective and efficient temporal verification in grid workflow systems." Swinburne University of Technology, 2007. http://adt.lib.swin.edu.au./public/adt-VSWT20070424.112326.
Full textAbstract:
In grid architecture, a grid workflow system is a type of high-level grid middleware
which aims to support large-scale sophisticated scientific or business processes in a
variety of complex e-science or e-business applications such as climate modelling,
disaster recovery, medical surgery, high energy physics, international stock market
modelling and so on. Such sophisticated processes often contain hundreds of
thousands of computation or data intensive activities and take a long time to
complete. In reality, they are normally time constrained. Correspondingly, temporal
constraints are enforced when they are modelled or redesigned as grid workflow
specifications at build-time. The main types of temporal constraints include upper
bound, lower bound and fixed-time. Then, temporal verification would be conducted
so that we can identify any temporal violations and handle them in time.
Conventional temporal verification research and practice have presented some
basic concepts and approaches. However, they have not paid sufficient attention to
overall temporal verification effectiveness and efficiency. In the context of grid
economy, any resources for executing grid workflows must be paid. Therefore, more
resources should be mainly used for execution of grid workflow itself rather than for
temporal verification. Poor temporal verification effectiveness or efficiency would
cause more resources diverted to temporal verification. Hence, temporal verification
effectiveness and efficiency become a prominent issue and deserve an in-depth
investigation.
This thesis systematically investigates the limitations of conventional temporal
verification in terms of temporal verification effectiveness and efficiency. The
detailed analysis of temporal verification effectiveness and efficiency is conducted
for each step of a temporal verification cycle. There are four steps in total: Step 1 -
defining temporal consistency; Step 2 - assigning temporal constraints; Step 3 -
selecting appropriate checkpoints; and Step 4 - verifying temporal constraints.
Based on the investigation and analysis, we propose some new concepts and develop
a set of innovative methods and algorithms towards more effective and efficient
temporal verification. Comparisons, quantitative evaluations and/or mathematical
proofs are also presented at each step of the temporal verification cycle. These
demonstrate that our new concepts, innovative methods and algorithms can
significantly improve overall temporal verification effectiveness and efficiency.
Specifically, in Step 1, we analyse the limitations of two temporal consistency
states which are defined by conventional verification work. After, we propose four
new states towards better temporal verification effectiveness. In Step 2, we analyse
the necessity of a number of temporal constraints in terms of temporal verification
effectiveness. Then we design a novel algorithm for assigning a series of finegrained
temporal constraints within a few user-set coarse-grained ones. In Step 3, we
discuss the problem of existing representative checkpoint selection strategies in
terms of temporal verification effectiveness and efficiency. The problem is that they
often ignore some necessary checkpoints and/or select some unnecessary ones. To
solve this problem, we develop an innovative strategy and corresponding algorithms
which only select sufficient and necessary checkpoints. In Step 4, we investigate a
phenomenon which is ignored by existing temporal verification work, i.e. temporal
dependency. Temporal dependency means temporal constraints are often dependent
on each other in terms of their verification. We analyse its impact on overall
temporal verification effectiveness and efficiency. Based on this, we develop some
novel temporal verification algorithms which can significantly improve overall
temporal verification effectiveness and efficiency. Finally, we present an extension
to our research about handling temporal verification results since these verification
results are based on our four new temporal consistency states.
The major contributions of this research are that we have provided a set of new
concepts, innovative methods and algorithms for temporal verification in grid
workflow systems. With these, we can significantly improve overall temporal
verification effectiveness and efficiency. This would eventually improve the overall
performance and usability of grid workflow systems because temporal verification
can be viewed as a service or function of grid workflow systems. Consequently, by
deploying the new concepts, innovative methods and algorithms, grid workflow
systems would be able to better support large-scale sophisticated scientific and
business processes in complex e-science and e-business applications in the context
of grid economy.
22
Cardona, Sandra Milena. "Understanding temporal and cellular constraints involved in the development of MLV-induced spongiform neurodegeneration." Kent State University / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=kent1334582961.
Full text
23
Waters, Christopher L. "Temporal and petrogenetic constraints on volcanic accretionary processes at 9-10 degrees North East Pacific Rise." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/59758.
Full textAbstract:
Thesis (Ph. D.)--Joint Program in Oceanography/Applied Ocean Science and Engineering (Massachusetts Institute of Technology, Dept. of Earth, Atmospheric, and Planetary Sciences; and the Woods Hole Oceanographic Institution), 2010.Cataloged from PDF version of thesis.
Includes bibliographical references.
Volcanic accretion at the fast-spreading East Pacific Rise (EPR) occurs over a ~2-4 km wide neo-volcanic zone on either side of the axial summit trough (AST). Eruption ages are critical for understanding the distribution and timing of volcanic and magmatic activity. Uranium series nuclides are susceptible to fractionation by magmatic processes that occur beneath mid-ocean ridges, and the half-lives of 22 6Ra (1.6 kyrs) and 23Th (75 kyrs) make them ideally suited for determining eruption ages and placing constraints on eruption frequency and temporal changes in magma chemistry. Accordingly, major and trace element, and long-lived radiogenic and 2 8 U-2 Th-226Ra isotope compositions were measured in basalts from 9'-10 N EPR to determine eruption ages and to place temporal constraints on volcanic and magmatic processes. At 9030'N EPR, 238U-2 Th-2 26Ra compositions indicate that trace elementally and isotopically enriched mid-ocean ridge basalt (MORB) collected off-axis erupted >8 ka and that E-MORB magmatism is interspersed with normal, depleted MORB magmatism. Lava ages are consistent with eruption from the AST and flow down the ridge flanks, which is in contrast to previous studies that suggested E-MORB erupted from off-axis vents. At 9'50'N EPR, discrete eruptive units are distinguished by high precision 238U, 32 Th, and 226Ra sample concentrations, but because the resolution of the "2 Th-226Ra model age dating technique is ~±1 kyrs, the surprisingly young ages of these lavas prohibit the construction of an explicit, time-constrained lava stratigraphy. Nonetheless, seven different flows identified within 0.8-2.0 km west of the AST imply greater frequency of flows to these distances than previously recognized. Model age dating of ferrobasalts, basaltic andesites, andesites, and dacites sampled from the east limb of the overlapping spreading center at 9'03'N EPR is difficult due to uncertainties in magma residence times. However, (22 6Ra/23 Th) disequilibria indicate recent basaltic volcanism (<<8 ka) up to -4 km off-axis. The axial graben at the rise crest sources the most recent volcanic activity and is the dominant location for eruption of high-silica magmas. Major element, trace element, 87Sr/86Sr, and (3 4U/238U) isotope compositions are consistent with the formation of dacite magmas by extensive crystallization, and 238U-2Fh-226 Ra systematics imply crustal residence times of -8 kyrs.
by Christopher L. Waters.
Ph.D.
24
Strang, Adam. "Effects of Positive and Negative Constraints on Postural Sway Temporal Structure: New Insights for Postural Control." Miami University / OhioLINK, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=miami1278619331.
Full text
25
Buchanan, Katherine Mary. "Behavioural constraints, patterns and conformance : reconciling object-oriented inheritance with temporal restrictions on the ordering of methods." Thesis, University of Hertfordshire, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.340034.
Full text
26
Beaumont, Matthew, and n/a. "Handling Over-Constrained Temporal Constraint Networks." Griffith University. School of Information Technology, 2004. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20041213.084512.
Full textAbstract:
Temporal reasoning has been an active research area for over twenty years, with most work focussing on either enhancing the efficiency of current temporal reasoning algorithms or enriching the existing algebras. However, there has been little research into handling over-constrained temporal problems except to recognise that a problem is over-constrained and then to terminate. As many real-world temporal reasoning problems are inherently over-constrained, particularly in the scheduling domain, there is a significant need for approaches that can handle over-constrained situations. In this thesis, we propose two backtracking algorithms to gain partial solutions to over-constrained temporal problems. We also propose a new representation, the end-point ordering model, to allow the use of local search algorithms for temporal reasoning. Using this model we propose a constraint weighting local search algorithm as well as tabu and random-restart algorithms to gain partial solutions to over-constrained temporal problems. Specifically, the contributions of this thesis are: The introduction and empirical evaluation of two backtracking algorithms to solve over-constrained temporal problems. We provide two backtracking algorithms to close the gap in current temporal research to solve over-constrained problems; The representation of temporal constraint networks using the end-point ordering model. As current representation models are not suited for local search algorithms, we develop a new model such that local search can be applied efficiently to temporal reasoning; The development of a constraint weighting local search algorithm for under-constrained problems. As constraint weighting has proven to be efficient for solving many CSP problems, we implement a constraint weighting algorithm to solve under-constrained temporal problems; An empirical evaluation of constraint weighting local search against traditional backtracking algorithms. We compare the results of a constraint weighting algorithm with traditional backtracking approaches and find that in many cases constraint weighting has superior performance; The development of a constraint weighting local search, tabu search and random-restart local search algorithm for over-constrained temporal problems. We extend our constraint weighting algorithm to solve under-constrained temporal problems as well as implement two other popular local search algorithms: tabu search and random-restart; An empirical evaluation of all three local search algorithms against the two backtracking algorithms. We compare the results of all three local search algorithms with our twobacktracking algorithms for solving over-constrained temporal reasoning problems and find that local search proves to be considerably superior.
27
Beaumont, Matthew. "Handling Over-Constrained Temporal Constraint Networks." Thesis, Griffith University, 2004. http://hdl.handle.net/10072/366603.
Full textAbstract:
Temporal reasoning has been an active research area for over twenty years, with most work focussing on either enhancing the efficiency of current temporal reasoning algorithms or enriching the existing algebras. However, there has been little research into handling over-constrained temporal problems except to recognise that a problem is over-constrained and then to terminate. As many real-world temporal reasoning problems are inherently over-constrained, particularly in the scheduling domain, there is a significant need for approaches that can handle over-constrained situations. In this thesis, we propose two backtracking algorithms to gain partial solutions to over-constrained temporal problems. We also propose a new representation, the end-point ordering model, to allow the use of local search algorithms for temporal reasoning. Using this model we propose a constraint weighting local search algorithm as well as tabu and random-restart algorithms to gain partial solutions to over-constrained temporal problems. Specifically, the contributions of this thesis are: The introduction and empirical evaluation of two backtracking algorithms to solve over-constrained temporal problems. We provide two backtracking algorithms to close the gap in current temporal research to solve over-constrained problems; The representation of temporal constraint networks using the end-point ordering model. As current representation models are not suited for local search algorithms, we develop a new model such that local search can be applied efficiently to temporal reasoning; The development of a constraint weighting local search algorithm for under-constrained problems. As constraint weighting has proven to be efficient for solving many CSP problems, we implement a constraint weighting algorithm to solve under-constrained temporal problems; An empirical evaluation of constraint weighting local search against traditional backtracking algorithms. We compare the results of a constraint weighting algorithm with traditional backtracking approaches and find that in many cases constraint weighting has superior performance; The development of a constraint weighting local search, tabu search and random-restart local search algorithm for over-constrained temporal problems. We extend our constraint weighting algorithm to solve under-constrained temporal problems as well as implement two other popular local search algorithms: tabu search and random-restart; An empirical evaluation of all three local search algorithms against the two backtracking algorithms. We compare the results of all three local search algorithms with our twobacktracking algorithms for solving over-constrained temporal reasoning problems and find that local search proves to be considerably superior.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Institute for Integrated and Intelligent Systems
Full Text
28
Hamilton, Lei Hou. "Reduced-data magnetic resonance imaging reconstruction methods: constraints and solutions." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/42707.
Full textAbstract:
Imaging speed is very important in magnetic resonance imaging (MRI), especially in dynamic cardiac applications, which involve respiratory motion and heart motion. With the introduction of reduced-data MR imaging methods, increasing acquisition speed has become possible without requiring a higher gradient system. But these reduced-data imaging methods carry a price for higher imaging speed. This may be a signal-to-noise ratio (SNR) penalty, reduced resolution, or a combination of both. Many methods sacrifice edge information in favor of SNR gain, which is not preferable for applications which require accurate detection of myocardial boundaries. The central goal of this thesis is to develop novel reduced-data imaging methods to improve reconstructed image performance. This thesis presents a novel reduced-data imaging method, PINOT (Parallel Imaging and NOquist in Tandem), to accelerate MR imaging. As illustrated by a variety of computer simulated and real cardiac MRI data experiments, PINOT preserves the edge details, with flexibility of improving SNR by regularization. Another contribution is to exploit the data redundancy from parallel imaging, rFOV and partial Fourier methods. A Gerchberg Reduced Iterative System (GRIS), implemented with the Gerchberg-Papoulis (GP) iterative algorithm is introduced. Under the GRIS, which utilizes a temporal band-limitation constraint in the image reconstruction, a variant of Noquist called iterative implementation iNoquist (iterative Noquist) is proposed. Utilizing a different source of prior information, first combining iNoquist and Partial Fourier technique (phase-constrained iNoquist) and further integrating with parallel imaging methods (PINOT-GRIS) are presented to achieve additional acceleration gains.
29
Ahlberg, Sofie. "Human-in-the-Loop Control Synthesis for Multi-Agent Systems under Metric Interval Temporal Logic Specifications." Licentiate thesis, KTH, Reglerteknik, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-251666.
Full textAbstract:
With the increase of robotic presence in our homes and work environment, it has become imperative to consider human-in-the-loop systems when designing robotic controllers. This includes both a physical presence of humans as well as interaction on a decision and control level. One important aspect of this is to design controllers which are guaranteed to satisfy specified safety constraints. At the same time we must minimize the risk of not finding solutions, which would force the system to stop. This require some room for relaxation to be put on the specifications. Another aspect is to design the system to be adaptive to the human and its environment. In this thesis we approach the problem by considering control synthesis for multi-agent systems under hard and soft constraints, where the human has direct impact on how the soft constraint is violated. To handle the multi-agent structure we consider both a classical centralized automata based framework and a decentralized approach with collision avoidance. To handle soft constraints we introduce a novel metric; hybrid distance, which quantify the violation. The hybrid distance consists of two types of violation; continuous distance or missing deadlines, and discrete distance or spacial violation. These distances are weighed against each other with a weight constant we will denote as the human preference constant. For the human impact we consider two types of feedback; direct feedback on the violation in the form of determining the human preference constant, and direct control input through mixed-initiative control where the human preference constant is determined through an inverse reinforcement learning algorithm based on the suggested and followed paths. The methods are validated through simulations.I takt med att robotar blir allt vanligare i våra hem och i våra arbetsmiljöer, har det blivit allt viktigare att ta hänsyn till människan plats i systemen när regulatorerna för robotorna designas. Detta innefattar både människans fysiska närvaro och interaktion på besluts- och reglernivå. En viktig aspekt i detta är att designa regulatorer som garanterat uppfyller givna villkor. Samtidigt måste vi minimera risken att ingen lösning hittas, eftersom det skulle tvinga systemet till ett stopp. För att uppnå detta krävs det att det finns rum för att mjuka upp villkoren. En annan aspekt är att designa systemet så att det är anpassningsbart till människan och miljön. I den här uppsatsen närmar vi oss problemet genom att använda regulator syntes för multi-agent system under hårda och mjuka villkor där människan har direkt påverkan på hur det svaga villkoret överträds. För att hantera multi-agent strukturen undersöker vi både det klassiska centraliserade automata-baserade ramverket och ett icke-centraliserat tillvägagångsätt med krockundvikning. För att hantera mjuka villkor introducerar vi en metrik; hybrida avståndet, som kvantifierar överträdelsen. Det hybrida avståndet består av två typer av överträdelse (kontinuerligt avstånd eller missandet av deadlines, och diskret avstånd eller rumsliga överträdelser) som vägs mot varandra med en vikt konstant som vi kommer att kalla den mänskliga preferens kontanten. Som mänsklig påverkan överväger vi direkt feedback på överträdelsen genom att hon bestämmer värdet på den mänskliga preferens kontanten, och direkt påverkan på regulatorn där den mänskliga preferens konstanten bestäms genom en inverserad förstärkt inlärnings algoritm baserad på de föreslagna och följda vägarna. Metoderna valideras genom simuleringar.
QC20190517
30
Dashwood, Ben. "Spatial and temporal constraints on the pattern of crustal rotation in the Central Andean forearc of Northern Chile (27-30°S)." Thesis, University of Plymouth, 2007. http://hdl.handle.net/10026.1/2013.
Full textAbstract:
A total of 125 sites have been collected for palaeomagnetic analysis from two localities within the Coastal Cordillera and Precordillera regions of Northern Chile, between 27-30 °S, in addition to -200 samples collected from a magnetostratigraphic profile through the Pabellón Formation. In the southernmost (Tres Cruces) sampling locality, spanning the Coastal Cordillera- Precordillera boundary, the early, mid and latest Cretaceous-earliest Paleocene magmatic arcs intrude the earliest Cretaceous country rocks to the west and late Cretaceous rocks to the east. An ~50km transect sampled along Quebrada de Los Choros (~29°45'S), indicates that a consistent clockwise rotation of ~10°is recorded by primary magnetisations isolated from all of the units sampled, regardless of age, lithology or location. This is consistent with existing palaeomagnetic data immediately to the south, which has been recalculated, and suggests that localised rotations did not play a significant role in accommodating deformation at this latitude. Palaeomagnetic sampling of two plutons from the latest Cretaceous-earliest Paleocene magmatic arc situated in Quebrada de Los Choros and ~50km to the north, indicates that a sharp discontinuity exists in the regional rotation pattern, with the northern most pluton recording 30° of clockwise rotation. This discontinuity is observed to coincide with an area of diffuse deformation along which sinistral displacement is accommodated along predominantly NW orientated faults. This zone of deformation is interpreted as reflecting a pre-existing fundamental fault zone, similar in nature to a number of such NW striking crustal anisotropies that are observed to pre-determine much of the modern architecture of the modern forearc. These reactivated fault zones are interpreted to form the boundaries of large domains that display homogenous patterns of large magnitude clockwise rotation and are defined through a large number of palaeomagnetic studies. The age of rotation is not well defined in the Tres Cruces area, with a maximum age of 70-60Ma suggested for the youngest rotated plutons sampled, and the observation of a remagnetisation to the south. A second sampling area, situated in the Chilean Precordillera (c.27°45°S), was chosen to try and investigate the temporal accumulation of rotation in the northern Chilean forearc. A wide range of rocks of Triassic to Eocene age were sampled, albeit within the La Temera Fault System, associated with the Incaic orogeny, which marked the initial stages of the most recent phase of mountain building in the Andes. The oldest rocks record primary magnetisations that indicate ~40° of crustal rotation, very similar in magnitude to that recorded in the Coastal-Cordillera-Precordillera boundary zone to the west, suggesting that the La Temera Fault System does not control the regional rotation pattern. In addition, the youngest material sampled, a 40Ma pluton, suggests that rotation was completed prior to the Incaic orogeny, suggesting that crustal rotation in the present day forearc is not a consequence of plateau uplift or crustal thickening.
31
McCulla, James K. "Dating Deformation in the Palmer Zone of Transpression, Central Massachusetts: Temporal Constraints on Models for Progressive Deformation in the Middle Crust." UKnowledge, 2016. http://uknowledge.uky.edu/ees_etds/34.
Full textAbstract:
The Palmer Zone of Transpression (PZoT) in the Bronson Hill zone of central Massachusetts is an expression of late Paleozoic oblique convergence between Avalonia and Laurentia. The steeply W-dipping, N-S trending PZoT is defined by bounding high strain zones (Mt. Dumplin on west, Central Maine and Conant Brook on east) of opposing shear sense enclosing the Monson orthogneiss. Research was designed to establish the timing of deformation to test the hypothesis that strain in transpressional systems occurs contemporaneously. An understanding of the timing of deformation in this zone could elucidate the mechanisms that formed the zone and contribute to a greater overall understanding of fabric evolution in transpressional systems. U-Pb SIMS ages of zircon in deformed pegmatites in Monson orthogneiss and Paxton and Rangeley paragneisses are 369 to 364 Ma. Plutons that contain all fabrics associated with progressive transpression – lineations ranging from subhorizontal (initial) to steeply-plunging parallel to dip (final) – mark the maximum age of deformation. Ages range from 360-355 Ma in the Hardwick tonalite, Wachusett tonalite, West Warren diorite, Walker Mountain orthogneiss, and Nichewaug diorite, and indicate transpression in the PZoT initiated after ca. 355 Ma. Monazite from Rangeley paragneisses and schists selected in the context of petrofabrics and syn-deformational mineral assemblages yield U-Th-Pb EPMA chemical ages that indicate dextral transpression occurred continuously from 355 to 315 Ma. Monazite chemical ages also indicate that sinistral lateral displacement in the west-bounding Mt. Dumplin high strain zone initiated ca. 325 Ma and lasted for roughly 45 m.y., ending around 280 Ma. The data for the Central Maine zone, Conant Brook shear zone, and Greenwich syncline support the idea of contemporaneous deformation across the compartmentalized zones of a transpressive system (355-315 Ma), while the ages for the Mt. Dumplin high strain zone indicate sinistral lateral displacement overlapped dextral transpression by about 10 m.y. but generally continued later in time (325-280 Ma).
32
Beyene, Tewodros Awgichew [Verfasser], Andrey [Akademischer Betreuer] [Gutachter] Rybalchenko, Philipp [Gutachter] Rümmer, and Helmut [Gutachter] Seidl. "Temporal Program Verification and Synthesis as Horn Constraints Solving / Tewodros Awgichew Beyene. Betreuer: Andrey Rybalchenko. Gutachter: Philipp Rümmer ; Helmut Seidl ; Andrey Rybalchenko." München : Universitätsbibliothek der TU München, 2015. http://d-nb.info/1103658468/34.
Full text
33
Mauricio, Toro. "Structured Interactive Scores." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2012. http://tel.archives-ouvertes.fr/tel-00736021.
Full textAbstract:
La plupart des sc\'narios multimédia interactifs sont bas\'{e}s sur des sp\'cifications informelles, il n'est donc pas possible de v\'{e}rifier formellement des propri\'t\'{e}s de ces syst\'mes. Nous pr\'{e}conisons la n\'cessit\'{e} d'un mod\'le g\'{e}n\'ral et formel. Partitions interactives est un formalisme pour d\'{e}crire des sc\'narios multim\'{e}dia interactifs. Nous proposons une nouvelle s\'mantique pour les partitions interactives bas\'{e}e sur les structures d'\'v\'{e}nements temporisés. Avec une telle s\'mantique, nous pouvons sp\'{e}cifier des propri\'t\'{e}s pour le syst\'me, en particulier, des propri\'{e}t\'s sur les traces, qui sont difficiles \'{a} pr\'ciser avec la programmation par contraintes. Nous pr\'{e}sentons \'galement une s\'{e}mantique op\'rationnelle des partitions interactives bas\'{e}e sur le calcul non-d\'terministe, temporis\'{e}, concurrent, par contraintes (ntcc) et nous rapportons la s\'mantique operationelle \'{a} la semantique en structures d'\'v\'{e}nements temporisés. Avec la s\'mantique op\'{e}rationnelle, nous pouvons d\'crire formellement le comportement d'un scenario dont les dur\'{e}es des objets temporels peuvent \^{e}tre des intervalles d'entiers arbitraires. La s\'mantique op\'{e}rationnelle est obtenue \' partir de la s\'{e}mantique en structures d'\'v\'{e}nements temporisés de la partition interactive. Pour fournir une telle traduction, nous avons d'abord d\'fini la forme normale d'une structure d'\'{e}v\'nements temporisés, dans laquel les \'{e}v\'nements li\'{e}s avec une dur\'e z\'{e}ro sont regroup\'s en un seul. Nous avons \'{e}galement d\'fini la notion de structures d'\'{e}v\'nements temporisés r\'{e}partissables, de telle sorte que son graphe de contraintes peut \^{e}tre exp\'di\'{e} en se fondant uniquement sur la propagation locale. Nous croyons que la s\'mantique op\'{e}rationnelle bas\'e sur ntcc offre certains avantages par rapport \'{a} la s\'mantique des partitions interactives bas\'{e}e sur des r\'seaux de Petri; par exemple, les dur\'{e}es des objets temporels peuvent \^{e}tre des intervalles d'entiers arbitraires, tandis que dans la plupart des mod\'les de partitions interactives, les intervalles ne peut \^tre utilis\'{e}s que pour repr\'senter les relations telles que l'\'{e}galit\' et les inégalités. Nos mod\'{e}les ntcc de partitions interactives sont ex\'cut\'{e}s en utilisant Ntccrt, un interpr\'te temps r\'{e}el pour ntcc. Nos mod\'les peuvent \'{e}galement \^{e}tre v\'rifi\'{e}s automatiquement en utilisant ntccMC, un verificateur pour ntcc, de temps born\', bas\'{e}e sur les automates finis, que nous introduisons dans cette th\'se. En utilisant ntccMC, nous pouvons v\'{e}rifier des propri\'t\'{e}s de logique de temps lin\'aire avec des contrantes (CLTL). Dans cette th\'{e}se, nous introduisons deux extensions du formalisme de partitions interactives: (1) l'une pour g\'rer le traitement audio en utilisant le langage de programmation fran\c cais Faust et (2) l'autre pour traiter des condition et des branchements, permettant de sp\'{e}cifier des choix et des boucles. Pour la premi\'re extension, nous pr\'{e}sentons une s\'mantique bas\'{e}e sur les structures d'\'v\'{e}nements temporisés et des id\'es sur la fa\c con de d\'{e}finir une s\'mantique op\'{e}rationnelle. Pour la deuxi\'me extension, nous pr\'{e}sentons une mise en \oe uvre et la comparaison des r\'sultats du jitter relative moyenne d'une impl\'{e}mentation d'un arp\'ge base sur l'algorithme de Karplus-Strong par rapport aux impl\'{e}mentations existants \'crits dans Pure Data. Nous d\'{e}finissons aussi un format de sauvegarde XML pour les partitions interactives et pour la extension avec branchement conditionnel. Un format de sauvegarde est crucial pour assurer la persistance des partitions.
34
Guillame-Bert, Mathieu. "Apprentissage de règles associatives temporelles pour les séquences temporelles de symboles." Thesis, Grenoble, 2012. http://www.theses.fr/2012GRENM081/document.
Full textAbstract:
L'apprentissage de modèles temporels constitue l'une des grandes problématiques de l'Exploration de Données (Data Mining). Dans cette thèse, nous avons développé un nouveau modèle temporel appelé TITA Rules (Règle associative temporelle basé sur des arbres d'intervalles). Ce modèle permet de décrire des phénomènes ayant un certain degré d'incertitude et/ou d'imprécision. Ce modèle permet entre autres d'exprimer la synchronicité entre évènements, les contraintes temporelles disjonctives et la négation temporelle. De par leur nature, les TITA Rules peuvent êtes utilisées pour effectuer des prédictions avec une grande précision temporel. Nous avons aussi développé un algorithme capable de découvrir et d'extraire de manière efficace des TITA Rules dans de grandes bases de données temporelles. Le cœur de l'algorithme est basé sur des techniques de minimisation d'entropie, de filtrage par Apriori et par des analyses de co-dépendance. Note modèle temporelle et notre algorithme ont été appliqués et évalués sur plusieurs jeux de données issues de phénomènes réels et de phénomènes simulés. La seconde partie de cette thèse à consisté à étudier l'utilisation de notre modèle temporel sur la problématique de la Planification Automatique. Ces travaux ont mené au développement d'un algorithme de planification automatique. L'algorithme prend en entrée un ensemble de TITA Rules décrivant le fonctionnement d'un système quelconque, une description de l'état initial du système, et un but à atteindre. En retour, l'algorithme calcule un plan décrivant la meilleure façon d'atteindre le but donné. Par la nature même des TITA Rules, cet algorithme est capable de gérer l'incertain (probabilités), l'imprécision temporelle, les contraintes temporelles disjonctives, ainsi que les événements exogènes prédictibles mais imprécisThe learning of temporal patterns is a major challenge of Data mining. We introduce a temporal pattern model called Temporal Interval Tree Association Rules (Tita rules or Titar). This pattern model can be used to express both uncertainty and temporal inaccuracy of temporal events. Among other things, Tita rules can express the usual time point operators, synchronicity, order, and chaining,disjunctive time constraints, as well as temporal negation. Tita rules are designed to allow predictions with optimum temporal precision. Using this representation, we present the Titar learner algorithm that can be used to extract Tita rules from large datasets expressed as Symbolic Time Sequences. This algorithm based on entropy minimization, apriori pruning and statistical dependence analysis. We evaluate our technique on simulated and real world datasets. The problem of temporal planning with Tita rules is studied. We use Tita rules as world description models for a Planning and Scheduling task. We present an efficient temporal planning algorithm able to deal with uncertainty, temporal inaccuracy, discontinuous (or disjunctive) time constraints and predictable but imprecisely time located exogenous events. We evaluate our technique by joining a learning algorithm and our planning algorithm into a simple reactive cognitive architecture that we apply to control a robot in a virtual world
35
Badache, Nesrine. "Allocation temporelle de systèmes avioniques modulaires embarqués." Phd thesis, Toulouse, INPT, 2016. http://oatao.univ-toulouse.fr/15991/1/badache_.pdf.
Full textAbstract:
L'évolution des architectures des systèmes embarqués temps réel vers des architectures modulaires a permis d'introduire plus de fonctionnalités grâce à l'utilisation de calculateurs répartis et d'interfaces de communication et de service standardisés. Nous nous intéressons dans cette thèse à l'architecture avionique modulaire (IMA) des standards ARINC 653 et ARINC 664 partie 7. Cette évolution a introduit de nouveaux défis de conception relatifs, entre autres, au respect des contraintes temporelles applicatives nécessaires au bon fonctionnement du système. La conception d'un système modulaire est un problème d'intégration sous contraintes, qui regroupe plusieurs problèmes difficiles (dimensionnement, allocation de ressource spaciale et temporelle). Ces difficulutés requierent la mise en place d'outils d'aide à l'intégration qui passent à l'échelle. C'est dans ce cadre-là que ces travaux de thèse ont été menés. Nous nous intéressons principalement à l'allocation des ressources temporelles du système. Plus particulièrement, nous déterminons les périodes d'exécution des fonctions embarquées distribuées qui garantissent les contraintes temporelles applicatives et qui offrent un degré d'évolutivité du système élevé, étant donné une répartition des fonctions sur les calculateurs. Notre démarche prend en compte la variabilité temporelle (bornée) du réseau de communication. La première contribution de cette thèse est la formulation du problème d'intégration d'un système modulaire IMA en un problème d'optimisation multicritère à contraintes temporelles. Pour une distribution des fonctions avioniques aux calculateurs, la périodicité des partitions IMA est recherchée de façon à garantir la fraîcheur et la non-perte des données transmises. Parmi toutes les allocations temporelles vérifiant les contraintes temporelles, nous réalisons une recherche multi-critères qui optimise à la fois un critère de charge des calculateurs et de marge temporelle dans le réseau. Ces deux critères facilitent les évolutions futures de l’architecture. La seconde contribution de cette thèse est la proposition de deux heuristiques de recherche multicritère adaptées à notre problème. Il faut noter que le nombre d'allocations temporelles valides grandit exponentiellement avec le nombre de modules et de partitions hébergées par module. Nous proposons deux algorithmes d'optimisation multicritères : (i) EXHAUST, un algorithme optimal de recherche exhaustive, (ii) TABOU un algorithme semi-optimal basé sur une métaheuristique Tabou. Pour les deux algorithmes, la cardinalité du problème est réduite par une phase d'optimisation locale à chaque module, rendue possible par la linéarité des deux métriques choisies. Cette première étape d'optimisation locale permet de résoudre à l'optimal le problème d'allocation avec EXHAUST pour un système IMA de taille moyenne. Nous montrons que pour des systèmes de grande taille, l'algorithme TABOU est un très bon candidat car il extrait des solutions satisfaisantes en un temps raisonnable, tout en testant un nombre limité d'allocations valides. Ces deux heuristiques sont appliquées à un système IMA. L'analyse des solutions obtenues nous permet de mettre en exergue la qualité des solutions Pareto-optimales obtenues par les deux algorithmes. Elles présentent les caractéristiques recherchées d'évolutivité de la charge des calculateurs et de la marge réseau. Notre dernière contribution réside dans une analyse fine de ces solutions. L'analyse met en avant différentes classes de solutions Pareto-optimales avec différent compromis entre la charge et la marge réseau. La connaissance de ces classes de solutions permet à l'intégrateur de choisir une solution lui fournissant le compromis qu'il recherche entre les critères de charge et de marge réseau.
36
Harbaoui, Houda. "Ordonnancement d’un système de production industriel complexe : flow shop hybride avec des machines dédiées soumis à différentes contraintes temporelles." Thesis, Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2018. http://www.theses.fr/2018IMTA0114/document.
Full textAbstract:
L’accroissement des profits, à travers l’amélioration de la productivité et la réduction des pertes de matières, représente un objectif primordial pour les entreprises industrielles. Dans cette thèse, nous nous intéressons à la résolution d’un problème industriel complexe réel avec des contraintes de temps. Nous nous sommes intéressés, tout d’abord, à un objectif principal, soit la minimisation des dates de fin de production, suivi d’un objectif secondaire qui est la minimisation des quantités de déchets non recyclables. Dans un premier temps, nous avons modéliséle problème par des modèles mathématiques, que nous avons résolu à l’aide d’un solveur. Dans un second temps, nous avons proposé une méthode approchée en forme d’algorithmes évolutionnistes. Cette méthode est appliquée aux deux objectifs mentionnés ci-dessus séparément. Une troisième méthode est ensuite appliquée à l’objectif principal, à savoir une méthode arborescente approchée. Nous avons testé les algorithmes proposés sur des instances inspirées d’un cas réel ; issues d’une entreprise du secteur agroalimentaire et sur des instances inspirées de la littératureIncreasing profits, through the improvement of productivity and minimizing waste, is a primary objective for industrial companies. In this thesis, we are interested insolving a real complex industrial problem with time constraints. Firstly, we were interested in minimizing completion time (Cmax). Secondly, we focused on minimizing of non-recyclable waste. As a first step, we formulated the problem by mathematical models, which we solved using a solver. In a second step, we proposed an approximate method in the form of evolutionary algorithms. Both methods were applied to the two objectives mentioned above separately. Then, a third method which is a tree-search algorithm was applied only to the main objective. We tested the proposed algorithms on instances inspired from a real case; from an agri-food business, and also on instances inspired from the literature
37
Allombert, Antoine. "Aspects temporels d’un système de partitions musicales interactives pour la composition et l’exécution." Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13680/document.
Full textAbstract:
La composition musicale utilise de plus en plus les outils informatiques, mais la question de l'interprétation des pièces soit résoule. Dans le cas des pièces électro-acoustiques sur support, enregistrement d'une organisation temporelle de sons, l'exécution des oeuvres se restreint à leur diffusion. A la différence des pièces instrumentales, un interprète ne peut modifier certains paramètres musicaux lors de l'exécution. Nous cherchons à définir un système de composition et d'exécution de pièces interprétables, en nous focalisant sur les modifications de dates d'événements de la partition. Nous proposons un formalisme de partitions interactives utilisant la programmation par contraintes pour définir l'organisation temporelle et les limites de l'interprétation. Nous présentons un modèle de machine abstraite pour l'exécution des partitions, basée sur les réseaux de Petri et la propagation de contraintes. Enfin, nous exposons quelques applications du systèmeAbstract
38
Olarte, Carlos. "Universal Temporal Concurrent Constraint Programming." Phd thesis, Palaiseau, Ecole polytechnique, 2009. http://pastel.archives-ouvertes.fr/pastel-00005492/en/.
Full text
39
Gao, Feng. "Complex medical event detection using temporal constraint reasoning." Thesis, University of Aberdeen, 2010. http://digitool.abdn.ac.uk:80/webclient/DeliveryManager?pid=153271.
Full textAbstract:
The Neonatal Intensive Care Unit (NICU) is a hospital ward specializing in looking after premature and ill newborn babies. Working in such a busy and complex environment is not easy and sophisticated equipment is used to help the daily work of the medical staff . Computers are used to analyse the large amount of monitored data and extract hidden information, e.g. to detect interesting events. Unfortunately, one group of important events lacks features that are recognizable by computers. This group includes the actions taken by the medical sta , for example two actions related to the respiratory system: inserting an endotracheal tube into a baby’s trachea (ET Intubating) or sucking out the tube (ET Suctioning). These events are very important building blocks for other computer applications aimed at helping the sta . In this research, a strategy for detecting these medical actions based on contextual knowledge is proposed. This contextual knowledge specifies what other events normally occur with each target event and how they are temporally related to each other. The idea behind this strategy is that all medical actions are taken for di erent purposes hence may have di erent procedures (contextual knowledge) for performing them. This contextual knowledge is modelled using a point based framework with special attention given to various types of uncertainty. Event detection consists in searching for consistent matching between a model based on the contextual knowledge and the observed event instances - a Temporal Constraint Satisfaction Problem (TCSP). The strategy is evaluated by detecting ET Intubating and ET Suctioning events, using a specially collected NICU monitoring dataset. The results of this evaluation are encouraging and show that the strategy is capable of detecting complex events in an NICU.
40
Reddy, Pamoori Venkateswara. "Tableau systems for tense logics : a constraint approach." Thesis, Imperial College London, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.283438.
Full text
41
Yu, Peng Ph D. Massachusetts Institute of Technology Department of Aeronautics and Astronautics. "Continuous relaxation to over-constrained temporal plans." Thesis, Massachusetts Institute of Technology, 2013. http://hdl.handle.net/1721.1/79336.
Full textAbstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2013.This electronic version was submitted and approved by the author's academic department as part of an electronic thesis pilot project. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from department-submitted PDF version of thesis.
Includes bibliographical references (p. 165-168).
When humans fail to understand the capabilities of an autonomous system or its environmental limitations, they can jeopardize their objectives and the system by asking for unrealistic goals. The objective of this thesis is to enable consensus between human and autonomous system, by giving autonomous systems the ability to communicate to the user the reasons for goal failure and the relaxations to goals that archive feasibility. We represent our problem in the context of temporal plans, a set of timed activities that can represent the goals and constraints proposed by users. Over-constrained temporal plans are commonly encountered while operating autonomous and decision support systems, when user objectives are in conflict with the environment. Over constrained plans are addressed by relaxing goals and or constraints, such as delaying the arrival time of a trip, with some candidate relaxations being preferable to others. In this thesis we present Uhura, a temporal plan diagnosis and relaxation algorithm that is designed to take over-constrained input plans with temporal flexibility and contingencies, and generate temporal relaxations that make the input plan executable. We introduce two innovative approaches within Uhura: collaborative plan diagnosis and continuous relaxation. Uhura focuses on novel ways of satisfying three goals to make the plan relaxation process more convenient for the users: small perturbation, quick response and simple interaction. First, to achieve small perturbation, Uhura resolves over-constrained temporal plans through partial relaxation of goals, more specifically, through the relaxation of schedules. Prior work on temporal relaxations takes an all-or-nothing approach in which timing constraints on goals, such as arrival times to destinations, are completely relaxed in the relaxations. The Continuous Temporal Relaxation method used by Uhura adjusts the temporal bounds of temporal constraints to minimizes the perturbation caused by the relaxations to the goals in the original plan. Second, to achieve quick responses, Uhura introduces Best-first Conflict-directed Relaxation, a new method that efficiently enumerates alternative options in best-first order. The search space of alternative options to temporal planning problems is very large and finding the best one is a NP-hard problem. Uhura empirically demonstrates fast enumeration by unifying methods from minimal relaxation and conflict-directed enumeration methods, first developed for model based diagnosis. Uhura achieves two orders of magnitude improvement in run-time performance relative to state-of-the-art approaches, making it applicable to a larger group of real-world scenarios with complex temporal plans. Finally, to achieve simple interactions, Uhura presents to the user a small set of preferred relaxations in best-first order based on user preference models. By using minimal relaxations to represent alternative options, Uhura simplifies the options presented to the user and reduces the size of its results and improves their expressiveness. Previous work either generates minimal relaxations or full relaxations based on preference, but not minimal relaxations based on preference. Preferred minimal relaxations simplify the interaction in that the users do not have to consider any irrelevant information, and may reach an agreement with the autonomous system faster. Therefore it makes communication between robots and users more convenient and precise. We have incorporated Uhura within an autonomous executive that collaborates with human operators to resolve over-constrained temporal plans. Its effectiveness has been demonstrated both in simulation and in hardware on a Personal Transportation System concept. The average runtime of Uhura on large problems with 200 activities is two order of magnitude lower compared to current approaches. In addition, Uhura has also been used in a driving assistant system to resolve conflicts in driving plans. We believe that Uhura's collaborative temporal plan diagnosis capability can benefit a wide range of applications, both within industrial applications and in our daily lives.
by Peng Yu.
S.M.
42
Lasbouygues, Adrien. "Exploration robotique de l’environnement aquatique : les modèles au coeur du contrôle." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS078/document.
Full textAbstract:
Les robots sous-marins peuvent aujourd'hui évoluer dans des environnements complexes difficilement accessibles à l'Homme pour des raisons de coût ou de sécurité. Ils peuvent donc intervenir dans une grande variété de missions en environnement aquatique. Or, la complexité de ces milieux impose de doter le vecteur robotique d'une autonomie opérationnelle suffisante afin qu'il puisse mener sa mission à bien tout en préservant son intégrité. Cela nécessite de développer des lois de commande répondant aux spécificités de l'application. Ces lois de commande se basent sur des connaissances provenant de différentes disciplines scientifiques ce qui souligne l'interdisciplinarité inhérente à la robotique. Une fois la loi de commande développée, il faut implémenter le contrôleur sur le robot sous forme de logiciel de contrôle basé sur une architecture logicielle temps-réel.Or la conception actuelle des lois de commande, sous forme de blocs "monolithiques", rend difficile l'évolution d'une loi de commande d'une application à l'autre, l'intégration de connaissances provenant d'autres disciplines scientifiques que ne maitrisent pas forcément les automaticiens et pénalisent son implémentation sur des architectures logicielles qui nécessitent la modularité. Pour résoudre ces problèmes nous cherchons à proprement séparer les différentes connaissances afin que chacune soit aisément manipulable, son rôle clair et que les relations établies entre les différentes connaissances soient explicites. Cela permettra en outre une projection plus efficace sur l'architecture logicielle. Nous proposons donc un nouveau formalisme de description des lois de commande selon une composition modulaire d'entités de base appelées Atomes et qui encapsulent les différents éléments de connaissance. Nous nous intéressons également à l'établissement d'une meilleure synergie entre les aspects automatique et génie logiciel qui se construit autour de préoccupations communes telles que les contraintes temporelles et la stabilité. Pour cela, nous enrichissons nos Atomes de contraintes chargées de véhiculer les informations relatives à ces aspects temporels. Nous proposons également une méthodologie basée sur notre formalisme afin de guider l'implémentation de nos stratégies de commande sur un Middleware temps-réel, dans notre cas le Middleware ContrACT développé au LIRMM.Nous illustrons notre approche par diverses fonctionnalités devant être mises en oeuvre lors de missions d'exploration de l'environnement aquatique et notamment pour l'évitement de parois lors de l'exploration d'un aquifère karstiqueUnderwater robots can nowadays operate in complex environments in a broad scope of missions where the use of human divers is difficult for cost or safety reasons. However the complexity of aquatic environments requires to give the robotic vector an autonomy sufficient to perform its mission while preserving its integrity. This requires to design control laws according to application requirements. They are built on knowledge from several scientific fields, underlining the interdisciplinarity inherent to robotics. Once the control law designed, it must be implemented as a control Software working on a real-time Software architecture.Nonetheless the current conception of control laws, as "monolithic" blocks, makes difficult the adaptation of a control from an application to another and the integration of knowledge from various scientific fields which are often not fully understood by control engineers. It also penalizes the implementation of control on Software architectures, at least its modularity and evolution. To solve those problems we seek a proper separation of knowledge so that each knowledge item can be easily used, its role precisely defined and we want to reify the interactions between them. Moreover this will allow us a more efficient projection on the Software architecture. We thus propose a new formalism for control laws description as a modular composition of basic entities named Atoms used to encapsulate the knowledge items.We also aim at building a better synergy between control and software engineering based on shared concerns such as temporal constraints and stability. Hence we extend the definition of our Atoms with constraints carrying information related to their temporal behaviour. We propose as well a methodology relying on our formalism to guide the implementation of control on a real-time Middleware. We will focus on the ContrACT Middleware developed at LIRMM.Finally we illustrate our approach on several robotic functionalities that can be used during aquatic environments exploration and especially for wall avoidance during the exploration of a karst aquifer
43
Weidner, Thomas. "Probabilistic Logic, Probabilistic Regular Expressions, and Constraint Temporal Logic." Doctoral thesis, Universitätsbibliothek Leipzig, 2016. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-208732.
Full textAbstract:
The classic theorems of Büchi and Kleene state the expressive equivalence of finite automata to monadic second order logic and regular expressions, respectively. These fundamental results enjoy applications in nearly every field of theoretical computer science. Around the same time as Büchi and Kleene, Rabin investigated probabilistic finite automata. This equally well established model has applications ranging from natural language processing to probabilistic model checking.
Here, we give probabilistic extensions Büchi\\\'s theorem and Kleene\\\'s theorem to the probabilistic setting. We obtain a probabilistic MSO logic by adding an expected second order quantifier. In the scope of this quantifier, membership is determined by a Bernoulli process. This approach turns out to be universal and is applicable for finite and infinite words as well as for finite trees. In order to prove the expressive equivalence of this probabilistic MSO logic to probabilistic automata, we show a Nivat-theorem, which decomposes a recognisable function into a regular language, homomorphisms, and a probability measure.
For regular expressions, we build upon existing work to obtain probabilistic regular expressions on finite and infinite words. We show the expressive equivalence between these expressions and probabilistic Muller-automata. To handle Muller-acceptance conditions, we give a new construction from probabilistic regular expressions to Muller-automata. Concerning finite trees, we define probabilistic regular tree expressions using a new iteration operator, called infinity-iteration. Again, we show that these expressions are expressively equivalent to probabilistic tree automata.
On a second track of our research we investigate Constraint LTL over multidimensional data words with data values from the infinite tree. Such LTL formulas are evaluated over infinite words, where every position possesses several data values from the infinite tree. Within Constraint LTL on can compare these values from different positions. We show that the model checking problem for this logic is PSPACE-complete via investigating the emptiness problem of Constraint Büchi automata.
44
Papapetrou, Panagiotis. "Constraint-based Mining of Frequent Arrangements of Temporal Intervals." Boston University Computer Science Department, 2006. https://hdl.handle.net/2144/1894.
Full textAbstract:
The problem of discovering frequent arrangements of temporal intervals is studied. It is assumed that the database consists of sequences of events, where an event occurs during a time-interval. The goal is to mine temporal arrangements of event intervals that appear frequently in the database. The motivation of this work is the observation that in practice most events are not instantaneous but occur over a period of time and different events may occur concurrently. Thus, there are many practical applications that require mining such temporal correlations between intervals including the linguistic analysis of annotated data from American Sign Language as well as network and biological data. Two efficient methods to find frequent arrangements of temporal intervals are described; the first one is tree-based and uses depth first search to mine the set of frequent arrangements, whereas the second one is prefix-based. The above methods apply efficient pruning techniques that include a set of constraints consisting of regular expressions and gap constraints that add user-controlled focus into the mining process. Moreover, based on the extracted patterns a standard method for mining association rules is employed that applies different interestingness measures to evaluate the significance of the discovered patterns and rules. The performance of the proposed algorithms is evaluated and compared with other approaches on real (American Sign Language annotations and network data) and large synthetic datasets.
45
Sioutis, Michaël. "Algorithmic contributions to qualitative constraint-based spatial and temporal reasoning." Thesis, Artois, 2017. http://www.theses.fr/2017ARTO0401/document.
Full textAbstract:
Le raisonnement spatial et temporel qualitatif est un domaine principal d’études de l’intelligence artificielle et, en particulier, du domaine de la représentation des connaissances, qui traite des concepts cognitifs fondamentaux de l’espace et du temps de manière abstraite. Dans notre thèse, nous nous focalisons sur les formalismes du domaine du raisonnement spatial et temporel qualitatif représentant les informations par des contraintes et apportons des contributions sur plusieurs aspects. En particulier, étant donnée des bases de connaissances d’informations qualitatives sur l’espace ou le temps, nous définissons des nouvelles conditions de consistance locale et des techniques associées afin de résoudre efficacement les problèmes fondamentaux se posant. Nous traitons notamment du problème de la satisfiabilité qui est le problème de décider s’il existe une interprétation quantitative de toutes les entités satisfaisant l’ensemble des contraintes qualitatives. Nous considérons également le problème de l’étiquetage minimal qui consiste à déterminer pour toutes les contraintes qualitatives les relations de base participant à au moins une solution ainsi que le problème de redondance consistant à déterminer les contraintes qualitatives non redondantes. En outre, nous enrichissons le domaine des formalismes spatio-temporels par des contributions concernant une logique spatio-temporelle combinant la logique temporelle propositionnelle (PTL) avec un langage de contraintes qualitatives spatiales et une étude de la problématique consistant à gérer une séquence temporelle de configurations spatiales qualitatives devant satisfaire des contraintes de transitionQualitative Spatial and Temporal Reasoning is a major field of study in Artificial Intelligence and, particularly, in Knowledge Representation, which deals with the fundamental cognitive concepts of space and time in an abstract manner. In our thesis, we focus on qualitative constraint-based spatial and temporal formalisms and make contributions to several aspects. In particular, given a knowledge base of qualitative spatial or temporal information, we define novel local consistency conditions and related techniques to efficiently solve the fundamental reasoning problems that are associated with such knowledge bases. These reasoning problems consist of the satisfiability problem, which is the problem of deciding whether there exists a quantitative interpretation of all the entities of a knowledge base such that all of its qualitative relations are satisfied by that interpretation, the minimal labeling problem, which is the problem of determining all the atoms for each of the qualitative relations of a knowledge base that participate in at least one of its solutions, and the redundancy problem, which is the problem of obtaining all the non-redundant qualitative relations of a knowledge base. Further, we enrich the field of spatio-temporal formalisms that combine space and time in an interrelated manner by making contributions with respect to a qualitative spatio-temporal logic that results by combining the propositional temporal logic (PTL) with a qualitative spatial constraint language, and by investigating the task of ordering a temporal sequence of qualitative spatial configurations to meet certain transition constraints
46
Ben, Zakour Asma. "Extraction des utilisations typiques à partir de données hétérogènes en vue d'optimiser la maintenance d'une flotte de véhicules." Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14539/document.
Full textAbstract:
Le travail produit s'inscrit dans un cadre industriel piloté par la société 2MoRO Solutions. La réalisation présentée dans cette thèse doit servir à l'élaboration d'un service à haute valeur, permettant aux exploitants aéronautiques d'optimiser leurs actions de maintenance. Les résultats obtenus permettent d'intégrer et de regrouper les tâches de maintenance en vue de minimiser la durée d'immobilisation des aéronefs et d'en réduire les risques de panne.La méthode que nous proposons comporte trois étapes : (i) une étape de rationalisation des séquences afin de pouvoir les combiner [...]The present work is part of an industrial project driven by 2MoRO Solutions company.It aims to develop a high value service enabling aircraft operators to optimize their maintenance actions.Given the large amount of data available around aircraft exploitation, we aim to analyse the historical events recorded with each aircraft in order to extract maintenance forecasting. Theresults are used to integrate and consolidate maintenance tasks in order to minimize aircraft downtime and risk of failure. The proposed method involves three steps : (i) streamlining information in order to combinethem, (ii) organizing this data for easy analysis and (iii) an extraction step of useful knowledgein the form of interesting sequences. [...]
47
Comin, Carlo. "Complexity in Infinite Games on Graphs and Temporal Constraint Networks." Doctoral thesis, Università degli studi di Trento, 2017. https://hdl.handle.net/11572/368151.
Full textAbstract:
This dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verification of reactive and finite state systems. Particularly, we shall focus on game theoretical methods in order to obtain improved complexity bounds and faster algorithms for the following models: Hyper Temporal Networks, Conditional Simple/Hyper Temporal Networks, Conditional Simple Temporal Networks with Instantaneous Reaction Time, Update Games, Explicit McNaughton-Muller Games, Mean Payoff Games.
48
Comin, Carlo. "Complexity in Infinite Games on Graphs and Temporal Constraint Networks." Doctoral thesis, University of Trento, 2017. http://eprints-phd.biblio.unitn.it/1955/1/phd_thesis.Carlo.pdf.
Full textAbstract:
This dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verification of reactive and finite state systems. Particularly, we shall focus on game theoretical methods in order to obtain improved complexity bounds and faster algorithms for the following models: Hyper Temporal Networks, Conditional Simple/Hyper Temporal Networks, Conditional Simple Temporal Networks with Instantaneous Reaction Time, Update Games, Explicit McNaughton-Muller Games, Mean Payoff Games.
49
Bit-Monnot, Arthur. "Temporal and Hierarchical Models for Planning and Acting in Robotics." Phd thesis, Toulouse, INPT, 2016. http://oatao.univ-toulouse.fr/17704/1/Arthur%20Bit-Monnot.pdf.
Full textAbstract:
The field of AI planning has seen rapid progress over the last decade and planners are now able to find plan with hundreds of actions in a matter of seconds. Despite those important progresses, robotic systems still tend to have a reactive architecture with very little deliberation on the course of the plan they might follow. In this thesis, we argue that a successful integration with a robotic system requires the planner to have capacities for both temporal and hierarchical reasoning. The former is indeed a universal resource central in many robot activities while the latter is a critical component for the integration of reasoning capabilities at different abstraction levels, typically starting with a high level view of an activity that is iteratively refined down to motion primitives. As a first step to carry out this vision, we present a model for temporal planning unifying the generative and hierarchical approaches. At the center of the model are temporal action templates, similar to those of PDDL complemented with a specification of the initial state as well as the expected evolution of the environment over time. In addition, our model allows for the specification of hierarchical knowledge possibly with a partial coverage. Consequently, our model generalizes the existing generative and HTN approaches together with an explicit time representation. In the second chapter, we introduce a planning procedure suitable for our planning model. In order to support hierarchical features, we extend the existing Partial-Order Causal Link approach used in many constraintbased planners, with the notions of task and decomposition. We implement it in FAPE (Flexible Acting and Planning Environment) together with automated problem analysis techniques used for search guidance. We show FAPE to have performance similar to state of the art temporal planners when used in a generative setting. The addition of hierarchical information leads to further performance gain and allows us to outperform traditional planners. In the third chapter, we study the usual methods used to reason on temporal uncertainty while planning. We relax the usual assumption of total observability and instead provide techniques to reason on the observations needed to maintain a plan dispatchable. We show how such needed observations can be detected at planning time and incrementally dealt with by considering the appropriate sensing actions. In a final chapter, we discuss the place of the proposed planning system as a central component for the control of a robotic actor. We demonstrate how the explicit time representation facilitates plan monitoring and action dispatching when dealing with contingent events that require observation. We take advantage of the constraint-based and hierarchical representation to facilitate both plan-repair procedures as well opportunistic plan refinement at acting time.
50
Cohen-Solal, Quentin. "Un cadre algébrique pour le raisonnement qualitatif en présence d'informations hétérogènes : application aux raisonnements multi-échelle et spatio-temporel." Thesis, Normandie, 2017. http://www.theses.fr/2017NORMC245/document.
Full textAbstract:
Parmi les différentes formes de raisonnement étudiées dans le contexte de l'intelligence artificielle, le raisonnement qualitatif permet d'inférer de nouvelles connaissances dans le contexte d'informations imprécises, incomplètes et dépourvues de valeurs numériques. Il permet par exemple de déduire de nouvelles informations à partir d'un ensemble d'informations spatiales telles que « la France est frontalière de l'Allemagne », « la Suisse est à l'est de la France », « l'Italie est en Europe » et « le Luxembourg est proche de la France ». Il peut également être utilisé pour résoudre des abstractions de problèmes quantitatifs difficiles à résoudre, afin par exemple d'accélérer la résolution de ces problèmes.De nombreux formalismes de raisonnement qualitatif ont été proposés dans la littérature. Ils ne se focalisent cependant que sur un seul aspect du monde, alors que la majorité des applications requièrent la prise en compte d'informations hétérogènes. Afin de répondre à ces besoins, plusieurs combinaisons et extensions de formalismes qualitatifs, comme le raisonnement spatio-temporel et le raisonnement multi-échelle, ont récemment été proposées dans la littérature. Le raisonnement spatio-temporel permet de raisonner dans le contexte d'informations spatiales et temporelles interdépendantes. Le raisonnement multi-échelle permet de raisonner avec des informations de précisions différentes, et en particulier de lever des incohérences apparentes.Dans cette thèse, nous nous intéressons au raisonnement multi-échelle, au raisonnement spatio-temporel et aux combinaisons de formalismes qualitatifs.Nous proposons d'étendre le raisonnement qualitatif temporel multi-échelle pour prendre en compte le fait que les intervalles de temps peuvent être perçus comme des instants à certaines échelles de précision, de formaliser intégralement ce raisonnement et d'étudier la décision de la cohérence dans ce contexte ainsi que sa complexité. Nous montrons en particulier que ce formalisme permet de décider la cohérence et que le problème de décision de la cohérence est NP-complet, même dans le cas le plus simple.En outre, nous proposons un cadre général permettant de raisonner sur les séquences temporelles d'informations qualitatives, une forme de description spatio-temporelle. Ce cadre permet notamment de raisonner dans le contexte d'évolutions complexes. Par exemple, les entités considérées peuvent avoir des caractéristiques préservées au cours du temps, évoluer de manière dépendante les unes par rapport aux autres, tout en ayant un comportement potentiellement irréversible et différent selon leur nature. De plus, dans ce cadre, le raisonnement est plus performant computationnellement que les approches de l'état de l'art. Nous étudions en particulier la décision de la cohérence dans le contexte spécifique de régions mobiles de taille constante, et montrons que ce cadre permet effectivement de décider la cohérence.De surcroît, nous proposons un cadre formel unifiant plusieurs formes d'extensions et de combinaisons de formalismes qualitatifs, incluant le raisonnement multi-échelle et les séquences temporelles. Ce cadre permet de raisonner dans le contexte de chacune de ces combinaisons et extensions, mais également d'étudier de manière unifiée la décision de la cohérence et sa complexité. Nous établissons en particulier deux théorèmes complémentaires garantissant que la décision de la cohérence est polynomiale, et nous les utilisons pour prouver que plusieurs fragments de séquences temporelles sont traitables.Nous généralisons également la définition principale de formalisme qualitatif afin d'inclure des formalismes qualitatifs exclus des définitions de la littérature, importants dans le cadre des combinaisonsIn this thesis, we are interested in qualitative multi-scale reasoning, qualitative spatio-temporal reasoning and combinations of qualitative formalisms.We propose to extend the multiscale temporal reasoning to take into account the fact that time intervals can be perceived as instants at certain scales of precision, to fully formalize this reasoning and to study its consistency problem. We show in particular that this formalism decides consistency and that the consistency problem is NP-complete, even in the simplest case.In addition, we propose a general framework for reasoning on temporal sequences of qualitative information, a form of spatio-temporal description. This framework allows for reasoning in the context of complex evolutions. For example, the considered entities may have characteristics preserved over time, evolve in a dependent manner with respect to each other, while having a potentially irreversible and different behavior depending on their nature. Moreover, in this context, reasoning is computationally more efficient than state-of-the-art approaches. In particular, we study the consistency problem in the specific context of constant-size moving regions, and show that this framework actually decides consistency.Furthermore, we propose a formal framework unifying several forms of extensions and combinations of qualitative formalisms, including multi-scale reasoning and temporal sequences. This framework allows one to reason in the context of each of these combinations and extensions, but also to study in a unified way the consistency problem. In particular, we establish two complementary theorems guaranteeing that the consistency problem is polynomial, and we use them to prove that several fragments of temporal sequences are tractable