No description available.

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.

No description available.

We find an orientation of a tree with 20 vertices such that the corresponding fixed-template constraint satisfaction problem (CSP) is NP-complete, and prove that for every orientation of a tree with fewer vertices the corresponding CSP can be solved in polynomial time. We also compute the smallest tree that is NL-hard (assuming L≠NL), the smallest tree that cannot be solved by arc consistency, and the smallest tree that cannot be solved by Datalog. Our experimental results also support a conjecture of Bulín concerning a question of Hell, Nešetřil and Zhu, namely that ‘easy trees lack the ability to count’. Most proofs are computer-based and make use of the most recent universal-algebraic theory about the complexity of finite-domain CSPs. However, further ideas are required because of the huge number of orientations of trees. In particular, we use the well-known fact that it suffices to study orientations of trees that are cores and show how to efficiently decide whether a given orientation of a tree is a core using the arc-consistency procedure. Moreover, we present a method to generate orientations of trees that are cores that works well in practice. In this way we found interesting examples for the open research problem to classify finite-domain CSPs in NL.

Les problèmes de satisfaction de contraintes distribués (DisCSP) permettent de formaliser divers problèmes qui se situent dans l'intelligence artificielle distribuée. Ces problèmes consistent à trouver une combinaison cohérente des actions de plusieurs agents. Durant cette thèse nous avons apporté plusieurs contributions dans le cadre des DisCSPs. Premièrement, nous avons proposé le Nogood-Based Asynchronous Forward-Checking (AFC-ng). Dans AFC-ng, les agents utilisent les nogoods pour justifier chaque suppression d'une valeur du domaine de chaque variable. Outre l'utilisation des nogoods, plusieurs backtracks simultanés venant de différents agents vers différentes destinations sont autorisés. En deuxième lieu, nous exploitons les caractéristiques intrinsèques du réseau de contraintes pour exécuter plusieurs processus de recherche AFC-ng d'une manière asynchrone à travers chaque branche du pseudo-arborescence obtenu à partir du graphe de contraintes dans l'algorithme Asynchronous Forward-Checking Tree (AFC-tree). Puis, nous proposons deux nouveaux algorithmes de recherche synchrones basés sur le même mécanisme que notre AFC-ng. Cependant, au lieu de maintenir le forward checking sur les agents non encore instanciés, nous proposons de maintenir la consistance d'arc. Ensuite, nous proposons Agile Asynchronous Backtracking (Agile-ABT), un algorithme de changement d'ordre asynchrone qui s'affranchit des restrictions habituelles des algorithmes de backtracking asynchrone. Puis, nous avons proposé une nouvelle méthode correcte pour comparer les ordres dans ABT_DO-Retro. Cette méthode détermine l'ordre le plus pertinent en comparant les indices des agents dès que les compteurs d'une position donnée dans le timestamp sont égaux. Finalement, nous présentons une nouvelle version entièrement restructurée de la plateforme DisChoco pour résoudre les problèmes de satisfaction et d'optimisation de contraintes distribués. / Distributed Constraint Satisfaction Problems (DisCSP) is a general framework for solving distributed problems. DisCSP have a wide range of applications in multi-agent coordination. In this thesis, we extend the state of the art in solving the DisCSPs by proposing several algorithms. Firstly, we propose the Nogood-Based Asynchronous Forward Checking (AFC-ng), an algorithm based on Asynchronous Forward Checking (AFC). However, instead of using the shortest inconsistent partial assignments, AFC-ng uses nogoods as justifications of value removals. Unlike AFC, AFC-ng allows concurrent backtracks to be performed at the same time coming from different agents having an empty domain to different destinations. Then, we propose the Asynchronous Forward-Checking Tree (AFC- tree). In AFC-tree, agents are prioritized according to a pseudo-tree arrangement of the constraint graph. Using this priority ordering, AFC-tree performs multiple AFC-ng processes on the paths from the root to the leaves of the pseudo-tree. Next, we propose to maintain arc consistency asynchronously on the future agents instead of only maintaining forward checking. Two new synchronous search algorithms that maintain arc consistency asynchronously (MACA) are presented. After that, we developed the Agile Asynchronous Backtracking (Agile-ABT), an asynchronous dynamic ordering algorithm that does not follow the standard restrictions in asynchronous backtracking algorithms. The order of agents appearing before the agent receiving a backtrack message can be changed with a great freedom while ensuring polynomial space complexity. Next, we present a corrigendum of the protocol designed for establishing the priority between orders in the asynchronous backtracking algorithm with dynamic ordering using retroactive heuristics (ABT_DO-Retro). Finally, the new version of the DisChoco open-source platform for solving distributed constraint reasoning problems is described. The new version is a complete redesign of the DisChoco platform. DisChoco 2.0 is an open source Java library which aims at implementing distributed constraint reasoning algorithms.