Les processus markoviens déterministes par morceaux (PDMP) forment une vaste classe de processus stochastiques caractérisés par une évolution déterministe entre des sauts à mécanisme aléatoire. Ce sont des processus de type hybride, avec une composante discrète de mode et une composante d’état qui évolue dans un espace continu. Entre les sauts du processus, la composante continue évolue de façon déterministe, puis au moment du saut un noyau markovien sélectionne la nouvelle valeur des composantes discrète et continue. Dans cette thèse, nous construisons des PDMP évoluant dans des espaces de mesures (de dimension infinie), pour modéliser des population de cellules en tenant compte des caractéristiques individuelles de chaque cellule. Nous exposons notre construction des PDMP sur des espaces de mesure, et nous établissons leur caractère markovien. Sur ces processus à valeur mesure, nous étudions un problème d'arrêt optimal. Un problème d'arrêt optimal revient à choisir le meilleur temps d'arrêt pour optimiser l'espérance d'une certaine fonctionnelle de notre processus, ce qu'on appelle fonction valeur. On montre que cette fonction valeur est solution des équations de programmation dynamique et on construit une famille de temps d'arrêt $epsilon$-optimaux. Dans un second temps, nous nous intéressons à un PDMP en dimension finie, le TCP, pour lequel on construit un schéma d'Euler afin de l'approcher. Ce choix de modèle simple permet d'estimer différents types d'erreurs. Nous présentons des simulations numériques illustrant les résultats obtenus. / Piecewise deterministic Markov processes (PDMP) form a large class of stochastic processes characterized by a deterministic evolution between random jumps. They fall into the class of hybrid processes with a discrete mode and an Euclidean component (called the state variable). Between the jumps, the continuous component evolves deterministically, then a jump occurs and a Markov kernel selects the new value of the discrete and continuous components. In this thesis, we extend the construction of PDMPs to state variables taking values in some measure spaces with infinite dimension. The aim is to model cells populations keeping track of the information about each cell. We study our measured-valued PDMP and we show their Markov property. With thoses processes, we study a optimal stopping problem. The goal of an optimal stopping problem is to find the best admissible stopping time in order to optimize some function of our process. We show that the value fonction can be recursively constructed using dynamic programming equations. We construct some $epsilon$-optimal stopping times for our optimal stopping problem. Then, we study a simple finite-dimension real-valued PDMP, the TCP process. We use Euler scheme to approximate it, and we estimate some types of errors. We illustrate the results with numerical simulations.

Cette étude a pour but de contribuer à l’avancement des connaissances dans le domaine des systèmes de gestion de ponts (Bridge Management System (BMS)) par le développement d’un outil décisionnel pour optimiser les réparations sur les ponts. Cet outil décisionnel se base sur la valeur actualisée nette pour considérer le moment optimal de réparation. Il met ainsi à l’avant-plan la création de richesse permise par un réseau routier efficace. De plus, il permet d’étudier l’incertitude sur plusieurs variables, soit les valeurs financières d’inflation et d’actualisation, ainsi que l’évolution du débit routier. La flexibilité de l’outil décisionnel permet de vérifier l’impact de plusieurs variables. Ainsi, le modèle de détérioration présentement utilisée par le ministère des Transports, de la Mobilité durable et de l'Électrification des transports du Québec est comparé à deux autres modèles, soit un modèle markovien basé sur la théorie des chaînes de Markov et un modèle stochastique développé dans le cadre de cette étude. Le projet innove en considérant les revenus générés par un pont et l’incertitude sur les variables futures de détérioration d’éléments de ponts, d’inflation et d’actualisation, ainsi que celles relatives à l’évolution du débit routier. Considérant la récente implantation du système de gestion du ministère des Transports, de la Mobilité durable et de l'Électrification des transports, cette étude se base sur plusieurs hypothèses. Pour cette étude, la durée de vie maximale du pont est établie à 100 ans, la dégradation et la réparation d’un ouvrage est analysée aux 5 ans et une seule réparation majeure peut être effectuée sur la durée de vie. De plus, cette réparation permet de remettre le pont dans son état initial (neuf) et la détérioration de quelques éléments principaux (la dalle en béton armé et les poutres d’acier) du pont représente la détérioration globale de la structure. En se basant sur les données du ministère des Transports, de la Mobilité durable et de l'Électrification des transports et à l’aide d’une analyse probabiliste de 20 000 simulations, l’étude met en évidence l’importance de considérer la variabilité sur la détérioration d’un élément/pont, sur le taux d’intérêt et dans une moindre mesure, l’inflation. Ainsi, lorsque seul l’état de la dalle représente l’état global du pont et en utilisant l’approche déterministe, une réparation entre 25 et 30 ans est appropriée. Un taux d’intérêt plutôt faible peut même repousser ce choix à 35 ans. Le choix de date optimale de réparation est très étalé avec l’approche markovienne considérant les probabilités élevées de maintien du pont en bon état. Finalement, l’approche stochastique favorise une réparation entre 20 et 35 ans selon la rapidité de la détérioration. Ce choix peut encore une fois changer légèrement avec l’ajout de taux d’intérêt et d’inflation variables. Lorsque seul l’état de la dalle et des poutres est considéré représenter l’état de l’ensemble du pont, l’approche déterministe propose une réparation à 25 ans pour le dalle en béton armé et une réparation à 30 ans pour les poutres en acier. Les paramètres financiers stochastiques peuvent affecter ce choix rendant possible une réparation optimale de 25 à 35 ans pour les deux types d’éléments. Les moments optimaux de réparation sont très étalés pour l’approche markovienne considérant les probabilités élevées de maintien des éléments en bon état. Finalement, l’approche stochastique propose une réparation entre 20 et 35 ans pour le dalle en béton armé et entre 15 et 40 ans pour les poutres en acier. Ces moments de réparations sont aussi affectés légèrement par l’ajout d’un taux d’intérêt et d’inflation variables. Une analyse de sensibilité permet de considérer l’impact de plusieurs paramètres du modèle considéré, soit la matrice de transition, la pénalité d’état, la variabilité de la matrice pour une détérioration stochastique et l’ajout d’un avantage de réparation simultanée à deux éléments. Une modification de la matrice de transition a surtout un impact sur la volatilité des résultats, alors qu’une modification sur la pénalité d’état crée une translation sur la distribution du moment optimal de réparation pour une détérioration de type markovienne et stochastique. La variabilité de la matrice pour une détérioration stochastique a directement un impact sur la volatilité du moment optimal de réparation. Plus le pourcentage de variation de la matrice est faible, plus les moments optimaux de réparation seront concentrés (plage moins étendue). Finalement, s’il est considéré que la réparation simultanée de deux éléments coûte moins cher que lorsque ces deux éléments sont réparés à des dates différentes (avantage de réparation simultanée de deux éléments plutôt que deux réparations distinctes), il y alors un impact sur le moment optimal de réparation. Cet effet est principalement perceptible lorsque les dates de réparation optimales sont séparées de moins de 10 ans. Pour une détérioration déterministe, il suffit que la réparation simultanée coûte de 3,72% de moins que deux réparations distinctes pour favoriser de réparer les deux éléments simultanément à 30 ans, la dalle étant réparée à 25 ans sans avantage (réduction des coût) de réparation simultanée. Cependant, un avantage de réparation simultanée a peu d’impact sur le moment optimal de réparation lorsque la détérioration se base sur un modèle markovien en raison de la grande répartition des moments optimaux de réparation. Enfin, l’avantage de réparation simultanée a un impact considérable pour une détérioration stochastique, la majorité des réparations se produisant entre 15 et 40 ans. / This study extends the existing literature on Bridge Management Systems (BMS) by developing a decision-making program to optimize bridge rehabilitations. This decision-making tool analyses the net present value to consider the optimal moment to repair a bridge. It highlights wealth creation by the maintenance of an efficient road network. Moreover, it allows the study of uncertainty on several parameters, such as financial values of inflation and interest rates as well as the evolution of traffic flow. The ability of the decision-making tool to verify the impact of several variables and the deterioration model currently used by the ministère des Transports, de la Mobilité durable et de l'Électrification des transports is compared to two other models; a Markovian model and a stochastic model developed under this study. This project breaks new ground by considering the revenue generated by the bridge’s efficiency. It also considers uncertainty on several parameters, such as financial values of inflation and interest rate, and the evolution of traffic flow. Considering the recent establishment of the management system used by the ministère des Transports, de la Mobilité durable et de l'Électrification des transports, this study is based on several assumptions. The life span of the bridge is limited to 100 years, degradation and repairs can only be done every 5 years, a single repair can be made over the bridge lifespan and the bridge condition is represented by only a few bridge components (elements). The study highlights the importance of considering variability on the deterioration of an element/bridge, interest rates and, to a lesser extent, inflation based on the ministère des Transports, de la Mobilité durable et de l'Électrification des transports data and using a probabilistic analysis of 20,000 simulations. Thus, when the bridge is only represented by its reinforced concrete deck and using the deterministic deterioration approach, a repair between 25 and 30 years is appropriate. A rather low interest rate can even push this choice to 35 years. This choice is very broad with the Markovian approach considering the high probabilities of keeping the bridge in good condition. Finally, the stochastic approach favors repair between 20 and 35 years depending on the speed of deterioration. This choice may again change slightly with the addition of both a variable interest rate and a variable inflation rate. When a reinforced concrete deck and steel beams are considered to represent the entire bridge, the deterministic approach suggests a 25-year repair for the reinforced concrete deck and a 30-year repair for the steel beams. Stochastic financial parameters can affect this choice, making an optimal repair of 25 to 35 years possible for both elements. The optimal moments of repair are very spread out for the Markovian approach considering the high probabilities of maintaining the elements in good condition. Finally, the stochastic approach proposes a repair between 20 and 35 years for the reinforced concrete deck and between 15 and 40 years for the steel beams. These repairs are slightly affected by the addition of a variable interest rate and inflation rate as well. An in-depth analysis shows the impact that several parameters have on the model considered. These parameters include: the transition matrix, the state penalty, the variability of the matrix for stochastic deterioration, and the addition of a simultaneous repair advantage. A change in the transition matrix mainly has an impact on the volatility of the results, whereas a modification on the state penalty shifts the optimal repair time distribution for Markovian and stochastic deteriorations. The variability of the matrix for stochastic deterioration directly affects the volatility of the optimal repair time. For example, the lower the percentage of variation of the matrix, the more the optimal repair moments will be concentrated (or fixed). Finally, the implementation of a simultaneous repair benefit mainly has an impact when the optimal repair time is within 10 years of a simultaneous repair. For a deterministic deterioration, a reduction in costs of 3.72% is sufficient to reconcile repair dates to 30 years, the bridge being repair at 25 years without this benefit. However, this advantage has little impact on Markovian deterioration due to the wide distribution of optimal repair times but a considerable impact on stochastic deterioration, with the majority of repairs occurring within a range of 15 to 40 years. / Cette étude a pour but de contribuer à l’avancement des connaissances dans le domaine des systèmes de gestion de ponts (Bridge Management System (BMS)) par le développement d’un outil décisionnel pour optimiser les réparations sur les ponts. Cet outil décisionnel se base sur la valeur actualisée nette pour considérer le moment optimal de réparation. Il met ainsi à l’avant-plan la création de richesse permise par un réseau routier efficace. De plus, il permet d’étudier l’incertitude sur plusieurs variables, soit les valeurs financières d’inflation et d’actualisation, ainsi que l’évolution du débit routier. La flexibilité de l’outil décisionnel permet de vérifier l’impact de plusieurs variables. Ainsi, le modèle de détérioration présentement utilisée par le ministère des Transports, de la Mobilité durable et de l'Électrification des transports du Québec est comparé à deux autres modèles, soit un modèle markovien basé sur la théorie des chaînes de Markov et un modèle stochastique développé dans le cadre de cette étude. Le projet innove en considérant les revenus générés par un pont et l’incertitude sur les variables futures de détérioration d’éléments de ponts, d’inflation et d’actualisation, ainsi que celles relatives à l’évolution du débit routier. Considérant la récente implantation du système de gestion du ministère des Transports, de la Mobilité durable et de l'Électrification des transports, cette étude se base sur plusieurs hypothèses. Pour cette étude, la durée de vie maximale du pont est établie à 100 ans, la dégradation et la réparation d’un ouvrage est analysée aux 5 ans et une seule réparation majeure peut être effectuée sur la durée de vie. De plus, cette réparation permet de remettre le pont dans son état initial (neuf) et la détérioration de quelques éléments principaux (la dalle en béton armé et les poutres d’acier) du pont représente la détérioration globale de la structure. En se basant sur les données du ministère des Transports, de la Mobilité durable et de l'Électrification des transports et à l’aide d’une analyse probabiliste de 20 000 simulations, l’étude met en évidence l’importance de considérer la variabilité sur la détérioration d’un élément/pont, sur le taux d’intérêt et dans une moindre mesure, l’inflation. Ainsi, lorsque seul l’état de la dalle représente l’état global du pont et en utilisant l’approche déterministe, une réparation entre 25 et 30 ans est appropriée. Un taux d’intérêt plutôt faible peut même repousser ce choix à 35 ans. Le choix de date optimale de réparation est très étalé avec l’approche markovienne considérant les probabilités élevées de maintien du pont en bon état. Finalement, l’approche stochastique favorise une réparation entre 20 et 35 ans selon la rapidité de la détérioration. Ce choix peut encore une fois changer légèrement avec l’ajout de taux d’intérêt et d’inflation variables. Lorsque seul l’état de la dalle et des poutres est considéré représenter l’état de l’ensemble du pont, l’approche déterministe propose une réparation à 25 ans pour le dalle en béton armé et une réparation à 30 ans pour les poutres en acier. Les paramètres financiers stochastiques peuvent affecter ce choix rendant possible une réparation optimale de 25 à 35 ans pour les deux types d’éléments. Les moments optimaux de réparation sont très étalés pour l’approche markovienne considérant les probabilités élevées de maintien des éléments en bon état. Finalement, l’approche stochastique propose une réparation entre 20 et 35 ans pour le dalle en béton armé et entre 15 et 40 ans pour les poutres en acier. Ces moments de réparations sont aussi affectés légèrement par l’ajout d’un taux d’intérêt et d’inflation variables. Une analyse de sensibilité permet de considérer l’impact de plusieurs paramètres du modèle considéré, soit la matrice de transition, la pénalité d’état, la variabilité de la matrice pour une détérioration stochastique et l’ajout d’un avantage de réparation simultanée à deux éléments. Une modification de la matrice de transition a surtout un impact sur la volatilité des résultats, alors qu’une modification sur la pénalité d’état crée une translation sur la distribution du moment optimal de réparation pour une détérioration de type markovienne et stochastique. La variabilité de la matrice pour une détérioration stochastique a directement un impact sur la volatilité du moment optimal de réparation. Plus le pourcentage de variation de la matrice est faible, plus les moments optimaux de réparation seront concentrés (plage moins étendue). Finalement, s’il est considéré que la réparation simultanée de deux éléments coûte moins cher que lorsque ces deux éléments sont réparés à des dates différentes (avantage de réparation simultanée de deux éléments plutôt que deux réparations distinctes), il y alors un impact sur le moment optimal de réparation. Cet effet est principalement perceptible lorsque les dates de réparation optimales sont séparées de moins de 10 ans. Pour une détérioration déterministe, il suffit que la réparation simultanée coûte de 3,72% de moins que deux réparations distinctes pour favoriser de réparer les deux éléments simultanément à 30 ans, la dalle étant réparée à 25 ans sans avantage (réduction des coût) de réparation simultanée. Cependant, un avantage de réparation simultanée a peu d’impact sur le moment optimal de réparation lorsque la détérioration se base sur un modèle markovien en raison de la grande répartition des moments optimaux de réparation. Enfin, l’avantage de réparation simultanée a un impact considérable pour une détérioration stochastique, la majorité des réparations se produisant entre 15 et 40 ans. / Cette étude a pour but de contribuer à l’avancement des connaissances dans le domaine des systèmes de gestion de ponts (Bridge Management System (BMS)) par le développement d’un outil décisionnel pour optimiser les réparations sur les ponts. Cet outil décisionnel se base sur la valeur actualisée nette pour considérer le moment optimal de réparation. Il met ainsi à l’avant-plan la création de richesse permise par un réseau routier efficace. De plus, il permet d’étudier l’incertitude sur plusieurs variables, soit les valeurs financières d’inflation et d’actualisation, ainsi que l’évolution du débit routier. La flexibilité de l’outil décisionnel permet de vérifier l’impact de plusieurs variables. Ainsi, le modèle de détérioration présentement utilisée par le ministère des Transports, de la Mobilité durable et de l'Électrification des transports du Québec est comparé à deux autres modèles, soit un modèle markovien basé sur la théorie des chaînes de Markov et un modèle stochastique développé dans le cadre de cette étude. Le projet innove en considérant les revenus générés par un pont et l’incertitude sur les variables futures de détérioration d’éléments de ponts, d’inflation et d’actualisation, ainsi que celles relatives à l’évolution du débit routier. Considérant la récente implantation du système de gestion du ministère des Transports, de la Mobilité durable et de l'Électrification des transports, cette étude se base sur plusieurs hypothèses. Pour cette étude, la durée de vie maximale du pont est établie à 100 ans, la dégradation et la réparation d’un ouvrage est analysée aux 5 ans et une seule réparation majeure peut être effectuée sur la durée de vie. De plus, cette réparation permet de remettre le pont dans son état initial (neuf) et la détérioration de quelques éléments principaux (la dalle en béton armé et les poutres d’acier) du pont représente la détérioration globale de la structure. En se basant sur les données du ministère des Transports, de la Mobilité durable et de l'Électrification des transports et à l’aide d’une analyse probabiliste de 20 000 simulations, l’étude met en évidence l’importance de considérer la variabilité sur la détérioration d’un élément/pont, sur le taux d’intérêt et dans une moindre mesure, l’inflation. Ainsi, lorsque seul l’état de la dalle représente l’état global du pont et en utilisant l’approche déterministe, une réparation entre 25 et 30 ans est appropriée. Un taux d’intérêt plutôt faible peut même repousser ce choix à 35 ans. Le choix de date optimale de réparation est très étalé avec l’approche markovienne considérant les probabilités élevées de maintien du pont en bon état. Finalement, l’approche stochastique favorise une réparation entre 20 et 35 ans selon la rapidité de la détérioration. Ce choix peut encore une fois changer légèrement avec l’ajout de taux d’intérêt et d’inflation variables. Lorsque seul l’état de la dalle et des poutres est considéré représenter l’état de l’ensemble du pont, l’approche déterministe propose une réparation à 25 ans pour le dalle en béton armé et une réparation à 30 ans pour les poutres en acier. Les paramètres financiers stochastiques peuvent affecter ce choix rendant possible une réparation optimale de 25 à 35 ans pour les deux types d’éléments. Les moments optimaux de réparation sont très étalés pour l’approche markovienne considérant les probabilités élevées de maintien des éléments en bon état. Finalement, l’approche stochastique propose une réparation entre 20 et 35 ans pour le dalle en béton armé et entre 15 et 40 ans pour les poutres en acier. Ces moments de réparations sont aussi affectés légèrement par l’ajout d’un taux d’intérêt et d’inflation variables. Une analyse de sensibilité permet de considérer l’impact de plusieurs paramètres du modèle considéré, soit la matrice de transition, la pénalité d’état, la variabilité de la matrice pour une détérioration stochastique et l’ajout d’un avantage de réparation simultanée à deux éléments. Une modification de la matrice de transition a surtout un impact sur la volatilité des résultats, alors qu’une modification sur la pénalité d’état crée une translation sur la distribution du moment optimal de réparation pour une détérioration de type markovienne et stochastique. La variabilité de la matrice pour une détérioration stochastique a directement un impact sur la volatilité du moment optimal de réparation. Plus le pourcentage de variation de la matrice est faible, plus les moments optimaux de réparation seront concentrés (plage moins étendue). Finalement, s’il est considéré que la réparation simultanée de deux éléments coûte moins cher que lorsque ces deux éléments sont réparés à des dates différentes (avantage de réparation simultanée de deux éléments plutôt que deux réparations distinctes), il y alors un impact sur le moment optimal de réparation. Cet effet est principalement perceptible lorsque les dates de réparation optimales sont séparées de moins de 10 ans. Pour une détérioration déterministe, il suffit que la réparation simultanée coûte de 3,72% de moins que deux réparations distinctes pour favoriser de réparer les deux éléments simultanément à 30 ans, la dalle étant réparée à 25 ans sans avantage (réduction des coût) de réparation simultanée. Cependant, un avantage de réparation simultanée a peu d’impact sur le moment optimal de réparation lorsque la détérioration se base sur un modèle markovien en raison de la grande répartition des moments optimaux de réparation. Enfin, l’avantage de réparation simultanée a un impact considérable pour une détérioration stochastique, la majorité des réparations se produisant entre 15 et 40 ans.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2015-2016 / Nous abordons deux problèmes différents et complémentaires : le problème du chemin couvrant (ou CPP) et le problème du chemin de recherche optimal (ou OSP). Le CPP est un défi important en robotique mobile alors que l’OSP est un classique de la théorie de la recherche. Nous effectuons d’abord une revue de littérature qui souligne leurs différences et leurs similitudes du point de vue d’une opération de recherche. Le CPP et l’OSP sont comparés par rapport aux données connues sur la position d’un objet de recherche. Ensuite, nous formalisons une généralisation du problème CPP aux détections imparfaites et distantes nommée CPPIED. Nous présentons un algorithme heuristique efficace qui utilise à la fois la programmation dynamique et une réduction au problème du voyageur de commerce (TSP). Nous appliquons l’algorithme dans le contexte des opérations de déminage sous-marin sur des cartes qui contiennent plus de 21 000 cellules. Nous poursuivons par l’étude d’un nouveau modèle de programmation par contraintes (CP) pour l’OSP pour lequel nous proposons une amélioration de la définition de la fonction objectif. Cette nouvelle définition permet un filtrage plus fort des variables de probabilité prodiguant ainsi une amélioration des performances du modèle. Nous proposons, pour l’OSP, une nouvelle heuristique nommée « détection totale » (ou TD). Les résultats expérimentaux démontrent que notre modèle, utilisé avec l’heuristique TD, est compétitif avec des algorithmes de séparation et d’évaluation (ou branch-and-bound) spécifiques au problème de l’OSP (l’approche CP étant plus générale). Cette dernière observation supporte notre assertion que la CP est un bon outil pour résoudre des problèmes de la théorie de la recherche. Finalement, nous proposons la contrainte de transition de Markov (Mtc) en tant que nouvel outil de modélisation pour simplifier l’implémentation de modèles basés sur les chaînes de Markov. Nous démontrons, tant empiriquement que formellement, que l’arithmétique des intervalles est insuffisante pour l’atteinte de la cohérence de bornes, c’est-à-dire, pour filtrer les variables de probabilité de cette contrainte. Or, l’arithmétique des intervalles est l’outil utilisé par les solveurs CP pour filtrer une Mtc lorsque celle-ci est décomposée en contraintes arithmétiques individuelles. Nous proposons donc un algorithme basé sur la programmation linéaire qui atteint la cohérence de bornes. Du fait que la programmation linéaire est coûteuse en temps de calcul pour un solveur CP lorsqu’utilisée à chaque noeud de l’arbre de recherche, nous proposons aussi une approche intermédiaire basée sur le problème du sac à dos fractionnel. L’utilisation des Mtcs est illustrée sur l’OSP. / We tackle two different and complementary problems: the coverage path planning (CPP) and the optimal search path (OSP). The CPP is a main challenge in mobile robotics. The OSP is a classic from search theory. We first present a review of both problems that highlights their differences and their similarities from the point of view of search (coverage) operations. Both problems are positioned on the continuum of the a priori knowledge on the whereabouts of a search object. We then formalize an extension of the CPP we call the CPP with imperfect extended detections (CPPIED). We present a novel and powerful heuristic algorithm that uses dynamic programming and a traveling salesman (TSP) reduction. We apply the method to underwater minesweeping operations on maps with more than 21 thousand cells. We then study a novel constraint programming (CP) model to solve the OSP.We first improve on using the classical objective function found in the OSP definition. Our novel objective function, involving a single modification of the operators used to compute the probability of success of a search plan, leads to a stronger filtering of the probability variables of the model. Then, we propose a novel heuristic for the OSP: the total detection (TD) heuristic. Experiments show that our model, along with the proposed heuristic, is competitive with problem-specific branch-and-bounds supporting the claim that CP is a good technique to solve search theory problems. We finally propose the Markov transition constraint (Mtc) as a novel modeling tool in CP to simplify the implementation of models based on Markov chains. We prove, both empirically and theoretically, that interval arithmetic is insufficient to filter the probability variables of a single Mtc, i.e., to enforce bounds consistency on these variables. Interval arithmetic is the only available tool to filter an Mtc when it is decomposed into individual arithmetic constraints. We thus propose an algorithm based on linear programming which is proved to enforce bounds consistency. Since linear programming is computationally expensive to use at each node of the search tree of a CP solver, we propose an in-between solution based on a fractional knapsack filtering. The Mtc global constraint usage is illustrated on a CP model of the OSP.

L’allocation de ressources est un problème omniprésent qui survient dès que des ressources limitées doivent être distribuées parmi de multiples agents autonomes (e.g., personnes, compagnies, robots, etc). Les approches standard pour déterminer l’allocation optimale souffrent généralement d’une très grande complexité de calcul. Le but de cette thèse est de proposer des algorithmes rapides et efficaces pour allouer des ressources consommables et non consommables à des agents autonomes dont les préférences sur ces ressources sont induites par un processus stochastique. Afin d’y parvenir, nous avons développé de nouveaux modèles pour des problèmes de planifications, basés sur le cadre des Processus Décisionnels de Markov (MDPs), où l’espace d’actions possibles est explicitement paramétrisés par les ressources disponibles. Muni de ce cadre, nous avons développé des algorithmes basés sur la programmation dynamique et la recherche heuristique en temps-réel afin de générer des allocations de ressources pour des agents qui agissent dans un environnement stochastique. En particulier, nous avons utilisé la propriété acyclique des créations de tâches pour décomposer le problème d’allocation de ressources. Nous avons aussi proposé une stratégie de décomposition approximative, où les agents considèrent des interactions positives et négatives ainsi que les actions simultanées entre les agents gérants les ressources. Cependant, la majeure contribution de cette thèse est l’adoption de la recherche heuristique en temps-réel pour l’allocation de ressources. À cet effet, nous avons développé une approche basée sur la Q-décomposition munie de bornes strictes afin de diminuer drastiquement le temps de planification pour formuler une politique optimale. Ces bornes strictes nous ont permis d’élaguer l’espace d’actions pour les agents. Nous montrons analytiquement et empiriquement que les approches proposées mènent à des diminutions de la complexité de calcul par rapport à des approches de planification standard. Finalement, nous avons testé la recherche heuristique en temps-réel dans le simulateur SADM, un simulateur d’allocation de ressource pour une frégate. / Resource allocation is an ubiquitous problem that arises whenever limited resources have to be distributed among multiple autonomous entities (e.g., people, companies, robots, etc). The standard approaches to determine the optimal resource allocation are computationally prohibitive. The goal of this thesis is to propose computationally efficient algorithms for allocating consumable and non-consumable resources among autonomous agents whose preferences for these resources are induced by a stochastic process. Towards this end, we have developed new models of planning problems, based on the framework of Markov Decision Processes (MDPs), where the action sets are explicitly parameterized by the available resources. Given these models, we have designed algorithms based on dynamic programming and real-time heuristic search to formulating thus allocations of resources for agents evolving in stochastic environments. In particular, we have used the acyclic property of task creation to decompose the problem of resource allocation. We have also proposed an approximative decomposition strategy, where the agents consider positive and negative interactions as well as simultaneous actions among the agents managing the resources. However, the main contribution of this thesis is the adoption of stochastic real-time heuristic search for a resource allocation. To this end, we have developed an approach based on distributed Q-values with tight bounds to diminish drastically the planning time to formulate the optimal policy. These tight bounds enable to prune the action space for the agents. We show analytically and empirically that our proposed approaches lead to drastic (in many cases, exponential) improvements in computational efficiency over standard planning methods. Finally, we have tested real-time heuristic search in the SADM simulator, a simulator for the resource allocation of a platform.

L'apprentissage par renforcement est une approche d'apprentissage automatique permettant de développer des systèmes s'améliorant à partir d'interactions avec un environnement. Les processus décisionnels de Markov partiellement observables (PDMPO) font partie des modèles mathématiques fréquemment utiliser pour résoudre ce type de problème d'apprentissage. Cependant, la majorité des méthodes de résolution utilisées dans les processus décisionnels de Markov partiellement observables nécessitent la connaissance du modèle. De plus, les recherches actuelles sur le PDMPO se restreignent principalement aux espaces d'états discrets, ce qui complique son application à certains problèmes naturellement modélisés par un espace d'état continu. Ce mémoire présente une vision des PDMPO basée sur les processus Gaussiens, une méthode d'apprentissage supervisée ayant comme propriété particulière d'être une distribution de probabilité dans l'espace des fonctions. Cette propriété est notamment très intéressante du fait qu'elle ouvre la porte à un traitement Bayésien de l'incertitude sur les fonctions inconnues d'un PDMPO continu. Les résultats obtenus avec l'approche d'apprentissage par processus Gaussien montrent qu'il est possible d'opérer dans un environnement tout en identifiant le modèle de ce celui-ci. À partir des conclusions tirées à la suite de nos travaux sur le PDMPO, nous avons observé un certain manque pour ce qui est de l'identification du modèle sous l'incertain. Ainsi, ce mémoire expose aussi un premier pas vers une extension de l'apprentissage de PDMPO continu utilisant des séquences d'états de croyances lors de l'identification du modèle. Plus précisément, nous proposons une méthode de régression par processus Gaussiens utilisant des ensembles d'entraînement incertain pour réaliser l'inférence dans l'espace des fonctions. La méthode proposée est particulièrement intéressante, du fait qu'elle s'applique exactement comme pour le cas des processus Gaussiens classiques et qu'elle n'augmente p±as la complexité de l'apprentissage.

L'incidence de l'infection par le VIH, définie comme le nombre de sujets nouvellement infectés par le VIH au cours du temps, est le seul indicateur permettant réellement d'appréhender la dynamique de l'épidémie du VIH/SIDA. Sa connaissance permet de prévoir les conséquences démographiques de l'épidémie et les besoins futurs de prise en charge, mais également d'évaluer l'efficacité des programmes de prévention. Jusqu'à très récemment, l'idée de base pour estimer l'incidence de l'infection par le VIH a été d'utiliser la méthode de rétro-calcul à partir des données de l'incidence du SIDA et de la connaissance de la distribution de la durée d'incubation du SIDA. L'avènement, à partir de 1996, de nouvelles combinaisons thérapeutiques très efficaces contre le VIH a contribué à modifier la durée d'incubation du SIDA et, par conséquent, à augmenter la difficulté d'utilisation de la méthode de rétro-calcul sous sa forme classique. Plus récemment, l'idée d'intégrer des informations sur les dates de diagnostic VIH a permis d'améliorer la précision des estimations. La plupart des pays occidentaux ont mis en place depuis quelques années un système de surveillance de l'infection à VIH. En France, la notification obligatoire des nouveaux diagnostics d'infection VIH, couplée à la surveillance virologique permettant de distinguer les contaminations récentes des plus anciennes a été mise en place en mars 2003. L'objectif de ce travail de thèse est de développer de nouvelles méthodes d'estimation de l'incidence de l'infection par le VIH capables de combiner les données de surveillance des diagnostics VIH et SIDA et d'utiliser les marqueurs sérologiques recueillis dans la surveillance virologique dans le but de mieux saisir l'évolution de l'épidémie dans les périodes les plus récentes. / The knowledge of the dynamics of the HIV/AIDS epidemic is crucial for planning current and future health care needs. The HIV incidence, i.e. the number of new HIV infections over time, determines the trajectory and the extent of the epidemic but is difficult to measure. The backcalculation method has been widely developed and used to estimate the past pattern of HIV infections and to project future incidence of AIDS from information on the incubation period distribution and AIDS incidence data. In recent years the incubation period from HIV infection to AIDS has changed dramatically due to increased use of antiretroviral therapy, which lengthens the time from HIV infection to the development of AIDS. Therefore, it has become more difficult to use AIDS diagnosis as the basis for back-calculation. More recently, the idea of integrating information on the dates of HIV diagnosis has improved the precision of estimates. In recent years, most western countries have set up a system for monitoring HIV infection. In France, the mandatory reporting of newly diagnosed HIV infection, coupled with virological surveillance to distinguish recent infections from older, was introduced in March 2003. The goal of this PhD thesis is to develop new methods for estimating the HIV incidence able to combine data from monitoring HIV and AIDS diagnoses and use of serologic markers collected in the virological surveillance in order to better understand the evolution of the epidemic in the most recent periods.

Nous proposons un algorithme basé sur une approche orientée d'ensemble de système dynamique pour extraire une organisation grossière de l'espace d'état de cerveau sur la base des signaux de l'EEG. Nous l'utilisons pour comparer l'organisation de l'espace d'état des données simulées à grande échelle avec la dynamique cérébrale réelle au repos chez des sujets sains et pathologiques (SEP). / We propose an algorithme based on set oriented approach of dynamical system to extract a coarse grained organization of brain state space on the basis of EEG signals. We use it for comparing the organization of the state space of large scale simulation of brain dynamics with actual brain dynamics of resting activity in healthy and SEP subjects.

Les travaux présentés concernent trois thématiques autonomes :<br /><br />(1) Modèles biologiques et statistique : modèles compartimentaux, pharmacocinétique et pharmacodynamie de population, estimateurs pour problèmes inverses stochastiques, modèles non-linéaires à effets mixtes, modèles de mélanges, algorithmes de type EM et ICF, modèles graphiques de covariance, modélisation en cancérologie, processus ponctuels, particules, files d'attentes, renormalisation de processus markoviens inhomogènes et formules de Feynman-Kac<br /><br />(2) Inégalités fonctionnelles : inégalités de type Sobolev, concentration de la mesure, isopérimétrie rôle de la convexité dans les inégalités entropiques, tensorisation, noyau de la chaleur, groupe d'Heisenberg et dynamiques hypoelliptiques, files d'attentes, mélanges de lois<br /> <br />(3) Matrices aléatoires : spectre des matrices markoviennes aléatoires, graphes à poids aléatoires, théorèmes de type Wigner, Marchenko-Pastur, et Girko-Bai, convergence des valeurs propres extrémales, déformations de rang un.<br /><br />Le concept le plus récurrent ici est celui de dynamique markovienne. Dans la première partie, ce sont les modèles à compartiments de la pharmacologie qui sont liés à de telles dynamiques. La seconde partie traite d'inégalités fonctionnelles associées à la vitesse et à la géométrie de dynamiques markoviennes. Enfin, la troisième partie traite de dynamiques markoviennes aléatoires. Ces trois parties ne se réduisent pas à l'étude de facettes de problèmes markoviens. Leur contenu balaye un spectre à la fois théorique et appliqué, et met en oeuvre des techniques et des concepts variés issus de l'analyse, des probabilités, et de la statistique.

Selon les domaines d'applications, différentes façons de modéliser le partage de ressources ont été envisagées. Un des premiers modèles apparus est issu du "Dining Philosophers Problem" de Dijkstra, généralisé par la suite par Chandy et Misra à travers le "Drinking Philosophers Problem". Nous nous intéressons à des versions markoviennes de ces situations, dans lesquelles les durées pour la prise et l'utilisation des ressources sont aléatoires. L'évaluation puis l'optimisation des performances des systèmes de ressources partagées nous conduit à étudier l'équilibre de ces modèles. Cette étude s'inscrit dans le contexte des propriétés de Markov des champs aléatoires sur les graphes dont nous présentons quelques résultats généraux. Nous utilisons également le formalisme des systèmes de particules. Nous introduisons une nouvelle classe de modèles markoviens de ressources partagées pour lesquels nous généralisons des outils classiques. Nous présentons des résultats de réversibilité et envisageons des techniques de comparaison stochastique. Pour des systèmes finis, nous donnons quelques calculs explicites de mesures d'équilibre. Des systèmes qui augmentent en taille et en complexité peuvent être approchés par des systèmes infinis. Pour des systèmes sur des graphes infinis construits à partir d'un arbre, nous mettons en évidence des phénomenes de transition de phase.

Utilisés dans de nombreux domaines scientifiques, les Automates Cellulaires Probabilistes, usuellement abrégés en PCA, de l'anglais "Probabilistic Cellular Automata", constituent, au sein des dynamiques aléatoires à temps discret, une classe de systèmes infinis de particules, c'est à dire de processus stochastiques markoviens à valeurs dans un espace infini S^G où S désigne un ensemble fini et G est un graphe infini. On considère ici toujours le cas où G=Z^d. La particularité de ces dynamiques est l'évolution en parallèle, ou synchrone, de chacune des coordonnées ou composants élémentaires en interaction. Nous nous intéressons dans un premier temps à l'existence et à l'unicité des mesures stationnaires pour les dynamiques PCA non dégénérées i.e. dont le comportement local n'est jamais déterministe, ainsi qu'à la caractérisation de ces états d'équilibre en tant que mesures gibbsiennes. Nous fondant sur les résultats de Dai Pra, Kozlov, Künsch, Lebowitz, Vasilyev et al., nous précisons, pour la classe des dynamiques PCA réversibles, les relations existant entre les mesures stationnaires, les mesures réversibles et les mesures de Gibbs associées à un potentiel dont le lien avec la dynamique est explicité. Pour une famille paramétrée de dynamiques PCA réversibles, nous démontrons l'existence d'un phénomène de transition de phase et explicitons dans ce cas le comportement de différentes mesures de Gibbs sous l'action de ces dynamiques. En particulier, nous exhibons des mesures de Gibbs non-stationnaires. Dans un second temps, nous étudions l'ergodicité, i.e. la convergence vers l'équilibre des dynamiques PCA qui sont de plus attractives. Nous construisons à cet effet un couplage de ces dynamiques préservant l'ordre stochastique. En nous référant aux travaux de Martinelli et Olivieri pour les dynamiques de Glauber, nous établissons qu'en l'absence de transition de phase, dès que l'unique mesure de Gibbs vérifie une condition de faible mélange, il y a ergodicité et convergence à vitesse exponentielle vers cet unique état d'équilibre, améliorant en cela grandement les critères d'ergodicité pour les PCA existant dans la littérature. Enfin, nous illustrons ces résultats par la réalisation de simulations numériques de certaines des dynamiques réversibles précédemment étudiées, et présentons un algorithme parallèle convergeant vers les mesures de Gibbs extrémales du modèle d'Ising.