Bien que le domaine des systèmes multi-agents ait été largement étudié, les interactions entre agents entraînent des pertes de privacité. En effet, la résolution de problèmes distribués, étant fréquemment combinatoires, impose un échange intensif d’informations entre les agents jusqu’à l’obtention d’un accord. Le problème est que les approches existantes ne considèrent généralement pas la confidentialité des données et se concentrent surtout sur la satisfaction des contraintes des agents pour évaluer les solutions. Les travaux présentés dans cette thèse visent donc à prendre en compte de façon principielle la problématique de la privacité dans le raisonnement distribué. Nous montrons que les travaux existants dans le domaine permettent toutefois aux agents de préserver implicitement un certain degré de privacité. Nous proposons une approche basée sur la théorie de l’utilité, un cadre formel bien défini en Intelligence Artificielle, permettant une approche objective et quantitative des intérêts et comportements raisonnables des agents. Plus précisément, le modèle que nous avons développé inclut non seulement les paramètres habituels mais également l’information sur la privacité des agents quantifiée en termes d’utilité. Nous montrons aussi que ces problèmes doivent être envisagés comme des problèmes de planification où les agents choisissent des actions maximisant leur utilité. Des algorithmes actuels peuvent être décrits comme des plans utilisables comme modèle générique par des planificateurs intelligents. Les expérimentations réalisées ont permis de valider l’approche et d’évaluer la qualité des solutions obtenues tout en montrant que leur efficacité peut être accrue à l’aide de traitements de privacité. / Although the field of multi-agent systems has been largely studied, interactions between agents imply privacy loss. Indeed, solving distributed problems, being frequently combinatorial, implies an extensive exchange of information between agents until an agreement is found. The problem is that existing approaches do not generally consider privacy and focus only on the satisfaction of agents’ constraints to evaluate solution. The works presented in this thesis therefore aim at considering systematically the issue of privacy in distributed reasoning. We show that existing works in the field still let agents preserve implicitly some degree of privacy. We propose an approach based on utility theory, a formal setting well defined in Artificial Intelligence, allowing an objective and quantitative approach to the interests and reasonable behaviours of agents. More precisely, the model we have developed includes non only the usual parameters but also information on agents privacy quantified in term of utility. We also show that these problems must be considered as planning problems where agents choose actions maximizing their utility. Common algorithms can be described as plans usable as generic models by intelligent planners. Conducted experiments let us validate the approach and evaluate the quality of obtained solution, while showing that their efficiency can be improved thanks to privacy considerations.

There exists an increasing demand for computing power and performance in real-time embedded systems, as new, more complex customer requirements and function-alities are appearing every day. In order to support these requirements and func-tionalities without breaking the power consumption wall, many embedded systems areswitching from traditional single-core hardware architectures to multi-core architec-tures. Multi-core architectures allow for parallel execution of tasks on the multiplecores. This introduces many benets from the perspective of achievable performance,but in turn introduces major issues when it comes to the timing predictability ofthe real-time embedded system applications deployed on them. The problem arisesfrom unpredictable and potentially unbounded inter-core interferences, which occuras a result of contention for the shared resources, such as the shared system busor shared system memory. This thesis studies the possible application of constraintprogramming as a resource optimization technique for the purpose of creating oineschedules for tasks in real-time embedded system applications executing on a dual-core architecture. The main focus is placed on tightening inter-core data-propagationinterferences, which can result in lower over-all data-propagation delays. A proto-type of an optimization engine, employing constraint programming techniques on ap-plications comprised of tasks structured according to the Phased Execution Model isdeveloped. The prototype is evaluated through several experiments on a large numberof industry inspired intellectual-property free benchmarks. Alongside the experimentsa case study is conducted on an example engine-control application and the resultingschedule is compared to a schedule generated by the Rubus-ICE industrial tool suite.The obtained results show that the proposed method is applicable to a potentially widerange of abstract systems with dierent requirements. The limitations of the methodare also discussed and potential future work is debated based on these results. / <p>Presentation was held over Zoom, due to the COVID-19 situation.</p>

A constraint is a formula in first-order logic expressing a relation between values of various domains. In order to solve a constraint, constructing a propositional encoding is a successfully applied technique that benefits from substantial progress made in the development of modern SAT solvers. However, propositional encodings are generally created by developing a problem-specific generator program or by crafting them manually, which often is a time-consuming and error-prone process especially for constraints over complex domains. Therefore, the present thesis introduces the constraint solver CO4 that automatically generates propositional encodings for constraints over structured finite domains written in a syntactical subset of the functional programming language Haskell. This subset of Haskell enables the specification of expressive and concise constraints by supporting user-defined algebraic data types, pattern matching, and polymorphic types, as well as higher-order and recursive functions. The constraint solver CO4 transforms a constraint written in this high-level language into a propositional formula. After an external SAT solver determined a satisfying assignment for the variables in the generated formula, a solution in the domain of discourse is derived. This approach is even applicable for finite restrictions of recursively defined algebraic data types. The present thesis describes all aspects of CO4 in detail: the language used for specifying constraints, the solving process and its correctness, as well as exemplary applications of CO4.

Ce travail s’inscrit dans le domaine de l’ordonnancement à base de programmation par contraintes. Dans ce cadre, la contrainte de ressource la plus fréquemment rencontrée est la cumulative, qui permet de modéliser des processus se déroulant de manière parallèle.Nous étudions dans cette thèse la contrainte cumulative en nous aidant d’outils rarement utilisés en programmation par contraintes (analyse polyédrale, dualité de la programmation linéaire, dualité de la géométrie projective) et proposons deux contributions pour le domaine.Le renforcement cumulatif est un moyen de générer des contraintes cumulatives redondantes plus serrées, de manière analogue à la génération de coupes en programmation linéaire entière. Il s'agit ici de l'un des premiers exemples de contrainte globale redondante.Le Raisonnement Énergétique est une propagation extrêmement puissante pour la contrainte cumulative, avec jusque-là une complexité élevée en O(n^{3}). Nous proposons un algorithme qui calcule cette propagation avec une complexité O(n^{2}log n), ce qui constitue une amélioration significative de cet algorithme connu depuis plus de 25 ans. / This work falls in the scope of constraint-based scheduling. In this framework, the most frequently encountered resource constraint is the cumulative, which enables the modeling of parallel processes.In this thesis, we study the cumulative constraint with the help of tools rarely used in constraint programming (polyhedral analysis, linear programming duality, projective geometry duality) and propose two contributions for the domain.Cumulative strengthening is a means of generating tighter redundant cumulative constraints, analogous to the generation of cuts in integer linear programming. This is one of the first examples of a redundant global constraint.Energy Reasoning is an extremely powerful propagation for cumulative constraint, with hitherto a high complexity of O(n^{3}). We propose an algorithm that computes this propagation with a O(n^{2}log n) complexity, which is a significant improvement of this algorithm known for more than 25 years.

No description available.

It's commonly assumed that experience leads to efficiency, yet this is largely unaccounted for in resource-constrained project scheduling. This thesis considers the idea that learning effects could allow selected activities to be completed within reduced time, if they're scheduled after activities where workers learn relevant skills. This paper computationally explores the effect of this autonomous, intra-project learning on optimal makespan and problem difficulty. A learning extension is proposed to the standard RCPSP scheduling problem. Multiple parameters are considered, including project size, learning frequency, and learning intensity. A test instance generator is developed to adapt the popular PSPLIB library of scheduling problems to this model. Four different Constraint Programming model formulations are developed to efficiently solve the model. Bounding techniques are proposed for tightening optimality gaps, including four lower bounding model relaxations, an upper bounding model relaxation, and a Destructive Lower Bounding method. Hundreds of thousands of scenarios are tested to empirically determine the most efficient solution approaches and the impact of learning on project schedules. Potential makespan reduction as high as 50% is discovered, with the learning effects resembling a learning curve with a point of diminishing returns. A combination of bounding techniques is proven to produce significantly tighter optimality gaps.

The Planning And Scheduling (PLAS) module of ICE (Intelligent Control Environment) is responsible for planning and scheduling a large fleet of vehicles. This process involves the creation of tasks to be executed by the vehicles. Using this information, PLAS decides which vehicles should execute which tasks, which are modelled as constraint satisfaction problems. Solving the constraint satisfaction problems is slow. To improve efficiency, a number of different techniques exist. One of these is arc consistency, that entails taking a constraint satisfaction problem and evaluating its variables pairwise by applying the constraints among them. Using arc consistency, we can discern the candidate solutions to constraint satisfaction problems faster than doing a pure search. In addition, arc consistency allows us to detect and act early on inconsistencies in constraint satisfaction problems. The work in this master thesis includes the implementation of a constraint solver for symbolic constraints, containing the arc consistency algorithm AC3. Furthermore, it encompasses the implementation of a constraint satisfaction problem generator, based on the Erdős-Rényi graph model, inspired by the quasigroup completion problem with holes, that allows the evaluation of the constraint solver on large-sized problems. Using the constraint satisfaction problem generator, a set of experiments were performed to evaluate the constraint solver. Furthermore, a set of complementary scenarios using manually created constraint satisfaction problems were performed to augment the experiments. The results show that the performance scales up well. / Schemaläggningsmodulen PLAS som är en del av ICE (Intelligent Control Environment) är ansvarig för planering och schemaläggning av stora mängder fordonsflottor. Denna process involverar skapandet av uppgifter som behöver utföras av fordonen. Utifrån denna information bestämmer PLAS vilka fordon som ska utföra vilka uppgifter, vilket är modellerat som villkorsuppfyllelseproblem. Att lösa villkorsuppfyllelseproblem är långsamt. För att förbättra prestandan, så finns det en mängd olika tekniker. En av dessa är bågkonsekvens, vilket involverar att betrakta ett villkorsuppfyllelseproblem och utvärdera dess variabler parvis genom att tillämpa villkoren mellan dem. Med hjälp av bågkonsekvens kan vi utröna kandidatlösningar för villkorsuppfyllelseproblemen snabbare, jämfört med ren sökning. Vidare, bågkonsenvens möjliggör upptäckande och bearbetning av inkonsekvenser i villkorsuppfyllelseproblem. Arbetet i denna masteruppsats omfattar genomförandet av en villkorslösare för symboliska villkor, innehållandes bågkonsekvensalgoritmen AC3. Vidare, så innefattar det genomförandet av en villkorsuppfyllelseproblemgenerator, baserad på grafmodellen Erdős-Rényi, inspirerad av kvasigruppkompletteringsproblem med hål, villket möjliggör utvärdering av villkorslösaren på stora problem. Med hjälp av villkorsuppfyllelseproblemgeneratorn så utfördes en mängd experiment för att utvärdera villkorslösaren. Vidare så kompletterades experimenten av en mängd scenarion utförda på manuellt skapade villkorsuppfyllelseproblem. Resultaten visar att prestandan skalar upp bra.

An efficient scheduling of bottleneck areas within the semiconductor manufactory gets more and more important. Due to the high complexity within the manufacturing area it is currently not possible to optimize the whole (or even a big part of the) factory at once. So mostly only work center specific optimization approaches are investigated. Typically scheduling problems only deal with two dimensions – jobs and equipment. But in some areas of semiconductor manufactory also a third dimension has to be considered – a limited secondary resource. In this paper a Constraint Programming model for such limited secondary resource problems is presented. Thereby the scheduling model also deals with setup matrices for the first and also secondary resource. The modeling of this CP model is shown in detail and the results are compared to a discrete event simulation using dispatching rules. The test data for the first tests are orientated on real production data.

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.

Le trafic aérien en Europe représente environ 30 000 vols quotidiens actuellement. Selon les prévisions de l’organisme Eurocontrol, ce trafic devrait croître de 70% d’ici l’année 2020 pour atteindre 50 000 vols quotidiens. L’espace aérien, découpé en zones géographiques appelées secteurs de contrôle, atteindra bientôt son niveau de saturation vis-à-vis des méthodes actuelles de planification et de contrôle. Afin d’augmenter la quantité de trafic que peut absorber le système, il est nécessaire de diminuer la charge de travail des contrôleurs aériens en les aidant dans leur tâche de séparation des avions. En se fondant sur les demandes de plans de vol des compagnies aériennes, nous proposons une méthode de planification des trajectoires en 4D permettant de présenter au contrôleur un trafic dont la plupart des conflits auront été évités en avance. Cette planification s’établit en deux étapes successives, ayant chacune un unique degré de liberté : une allocation de niveaux de vol permettant la résolution des conflits en croisière puis une allocation d’heures de décollage permettant de résoudre les conflits restants. Nous présentons des modèles pour ces deux problèmes d’optimisation fortement combinatoires, que nous résolvons en utilisant la programmation par contraintes ou les algorithmes évolutionnaires, ainsi que des techniques permettant de prendre en compte des incertitudes sur les heures de décollage ou le suivi de trajectoire. Les simulations conduites sur l’espace aérien français mènent à des situations où tous les conflits sont évités, avec des retards alloués de l’ordre d’une minute en moyenne (80 à90 minutes pour le vol le plus retardé) et un écart par rapport à l’altitude optimale limité à un niveau de vol pour la quasi totalité des vols. La prise en compte d’incertitudes de manière statique dégrade fortement ces solutions peu robustes, mais nous proposons un modèle dynamique utilisant une fenêtre glissante susceptible de prendre en compte des incertitudes de quelques minutes avec un impact réduit sur le coût de l’allocation. / Air traffic in Europe represents about 30,000 flights each day and forecasts from Eurocontrol predict a growth of 70% by 2020 (50,000 flights per day). The airspace, made up of numerous control sectors, will soon be saturated given the current planification and control methods. In order to make the system able to cope with the predicted traffic growth, the air traffic controllers workload has to be reduced by automated systems that help them handle the aircraft separation task. Based on the traffic demand by airlines, this study proposes a new planning method for 4D trajectories that provides conflict-free traffic to the controller. This planning method consists of two successive steps, each handling a unique flight parameter : a flight level allocation phase followed by a ground holding scheme. We present constraint programming models and an evolutionary algorithm to solve these large scale combinatorial optimization problems, as well as techniques for improving the robustness of the model by handling uncertainties of takeoff times and trajectory prediction. Simulations carried out over the French airspace successfully solved all conflicts, with a mean of one minute allocated delay (80 to 90 minutes for the most delayed flight) and a discrepancy from optimal altitude of one flight level for most of the flights. Handling uncertainties with a static method leads to a dramatic increase in the cost of the previous non-robust solutions. However, we propose a dynamic model to deal with this matter, based on a sliding time horizon, which is likely to be able to cope with a few minutes of uncertainty with reasonable impact on the cost of the solutions.