Gotowa bibliografia na temat „Traitement réparti – Planification”

La talectomie est une alternative chirurgicale du traitement des déformations majeures du pied chez l’adulte. Notre série rétrospective comporte dix pieds répartis en six hommes et quatre femmes dont l’étiologie est soit un pied bot varus équin invétéré ou multiopéré, soit un pied neurologique. La marche s’effectue sur le bord externe du pied, avec un appui digitigrade dans neuf cas. Tous les patients sont traités par une talectomie avec arthrodèse tibiocalcanéonaviculaire par voie antérolatérale. Au recul de quatre ans, nous rapportons 90 % de résultats cliniques satisfaisants, un gain moyen de 42 points du score de l’AOFAS, une consolidation de l’arthrodèse chez 80 % des patients et un taux de complications de 50 %. Cette chirurgie permet d’avoir un appui plantigrade, une marche indolente et stable avec un chaussage normal. Elle nécessite une étude des déformations avec une planification préopératoire pour décider de la position de l’arthrodèse.

La plupart des systèmes de planification distribuée sont fondés sur des modèles qui ont été développés pour de 1 planification centralisée. Ces modèles ont ensuite été adaptés au contexte de la distribution et aux problèmes pécifiques qui en découlent. Notre objectif est au contraire de développer un modèle de planification qui intègre a priori les contraintes de la distribution. Pour cela, nous développons un modèle de planification utilisant une recherche de type meilleur d'abord (nous adaptons à cette fin des algorithmes de la famille proof-number search). Nous déclinons ce modèle pour la planification d'une part sur des structures de tâches utilisées dans les systèmes multi-agents et d'autres part sur le formalisme HTN. Dans ce second cas, nous montrons en particulier comment une recherche de type meilleur d'abord permet d'accumuler au plus vite des contraintes qui permettent de fermer certaines branches de l'espace de Ia recherche. Nous nous intéressons en outre à la robustesse des plans produits, c'est-à-dire à la capacité d'un groupe ki'agents planifiants à pallier l'absence d'une ressource ou la défaillance d'un agent
Most of distributed planning systems are based on models which were developped for centralized planning. These models have then been adapted to distribution and its specific contraints. Our goal is at the opposite to design a planning model that considers these constraints as premises. We have developped a planning model that uses a best-first search (as an adaptation of the proof-number search algorithm). We have applied this model to planning over task structures (from multiagent notations) as well as to HTN planning. Ln this latter case, we have shown how a best-first search allows the planner to rapidly gather constraints that can prune branches from the search space. We have also defined plan robustness in order to mitigate the consequences of an agent failure or a resource unavailability

Permettre à plusieurs agents de planifier et de coordonner leurs activités de manière distribuée tel est l'objectif des travaux présentés dans ce mémoire. L'approche proposée s'appuie sur des opérateurs de composition de plans. Afin de gérer au mieux les interactions entre différents agents, leurs plans sont produits par IxTeT, un système de planification permettant la prise en compte de contraintes temporelles numériques et gérant le parallélisme des tâches ainsi que le partage de ressources. Les deux premiers chapitres décrivent le formalisme logique utilisé par IxTeT ainsi que le fonctionnement du planificateur lui-même et les améliorations qu'il est possible d'y apporter. Le troisième chapitre détaille alors formellement les méthodes et algorithmes permettant de réaliser des opérateurs de composition de plans: union de plans, insertion de nouveaux buts dans un plan existant. On y démontre leurs limites théoriques. Le quatrième chapitre décrit la mise en œuvre de ces opérateurs en exhibant des algorithmes tant pour améliorer les performances de la planification incrémentale mono-agent que pour réaliser un système distribué de planification multi-agents. Dans ce système, un plan global est élaboré par composition successive de plans individuels. Ce plan global reste implicite et n'est donc jamais centralisé. On présente ensuite les problèmes spécifiques rencontrés lorsque planification et exécution sont réalisées simultanément. Ces problèmes ouverts sont cruciaux dans un contexte multi-agents. Le document se termine par une illustration et une évaluation sur des exemples appliqués au domaine multi-robots permettant d'apprécier les avantages mais aussi les limites de l'utilisation de ces opérateurs de composition de plans et par une comparaison avec un autre système de planification distribuée.

Bien que l'ordinateur soit a present banal sur les lieux de travail, sa presence n'a guere modifie les relations et les contacts entre individus. Mais les technologies de l'informatique et de la communication continuent a converger et cette evolution favorise, d'une part, les collaborations entre individus, et d'autre part, la coordination des taches qu'ils executent au sein d'un veritable espace de travail electronique. Les recherches afferentes ont fait emerger un nouveau domaine scientifique appele computer-supported cooperative work (cscw) ou le travail cooperatif assiste par ordinateur (tcao). Ce domaine est vraisemblablement le plus vaste et le plus complexe qui soit du fait qu'il marie plusieurs disciplines telles que l'informatique, la psychologie, la sociologie, les sciences cognitives, l'expertise (en medecine, en education et enseignement,), etc. Les logiciels issus de ces recherches sont communement appeles groupware, ou encore collecticiels. Comme les utilisateurs d'une certaine categorie de groupware sont repartis dans l'espace et le temps, il est naturel de concevoir des systemes qui soient des systemes distribues, mettant en valeur la decentralisation des donnees et du controle. Il faut egalement considerer les groupware sous l'angle de la coordination afin que les interactions, ainsi rendues possibles, deviennent aussi efficaces que les echanges face a face, evitant tout a la fois les ruptures dans les processus de conversation (breakdowns) et les conflits. L'objectif de cette these consiste en l'etude d'architectures logicielles qui permettent la coordination des taches dans un environnement distribue. La modelisation des processus de conversation s'est appuyee sur la theorie du workflow de winograd & flores. L'accent est mis sur la coordination de taches impliquant de nombreux agents differents. Le partage des taches induit souvent des conflits entre participants. La recherche est particulierement orientee dans cet aspect resolution et prevention de conflits. Nous proposons a titre d'exemple, d'appliquer notre recherche a la coordination des taches dans les unites de soins intensifs et de reanimation ou la cohesion du travail doit etre primordiale entre medecins et infirmieres. Les defauts de coordination sont ici a l'origine de breakdowns qui peuvent etre prejudiciables au fonctionnement de l'unite medicale comme a la prise en charge des malades. Lesdits breakdowns proviennent essentiellement des mauvaises interactions entre participants.

Cette thèse s'inscrit dans le contexte de l'allocation en ligne multi-agents multi-tâches, dont le but est de coordonner efficacement un ensemble d'agents (ressources) afin de distribuer des tâches entre eux. À titre d'exemple d'application, nous pouvons citer les cas où des clients font des requêtes à un fournisseur de services qui cherchera la meilleure répartition des tâches parmi son ensemble d'agents : des taxis répondant à la demande des clients ou des robots assurant la distribution de colis.Contrairement au cadre hors ligne, qui suppose une connaissance totale du problème d'allocation à résoudre avant le début de l’allocation, dans le cadre en ligne, les tâches arrivent au cours du temps et doivent être allouées de manière dynamique. Ce cadre d'optimisation en ligne présente plusieurs défis. Tout d'abord, l'allocation répétée des tâches aux agents est un problème NP-difficile, dont une solution doit être trouvée en un temps limité, parfois très court. Ensuite, la connaissance sur l'arrivée de futures tâches (par exemple, moment d'arrivée et localisation) est en général modeste, ce qui rend difficile le raisonnement sur le long terme (c’est-à-dire optimiser le positionnement des agents pour la planification à plus long terme). Enfin, la taille du problème à traiter en termes d'agents et de tâches peut être importante, particulièrement dans un cadre réaliste où la recherche d’une solution en temps limité peut être parfois compromise.Dans ce contexte, cette thèse propose différentes contributions. Tout d'abord, cette thèse propose une approche proactive qui permet d'anticiper la disponibilité des agents dans un futur proche afin d'obtenir une coordination efficace (c’est-à-dire minimisant la distance parcourue par les agents et le temps qu'ils restent désœuvrés). Cette approche proactive a été comparée à une approche réactive classique. Les résultats obtenus dans deux problèmes de référence, l'un synthétique et l'autre basé sur des données réelles, montrent que la méthode proactive permet d'obtenir de meilleurs résultats en termes de coûts et de nombre de tâches allouées aux agents par rapport à une approche réactive, tout en diminuant le temps d'inactivité des ressources. Malgré les résultats encourageants obtenus, la méthode proposée présente des limitations de scalabilité dans notre problème de référence basé sur des données réelles. Pour pallier cette limitation, cette thèse propose une deuxième approche qui développe une méta-heuristique d'allocation multi-agent multi-tâche, appelée SKATE - Successive Rank-based Task Assignment for Proactive Online Planning, permettant le passage à l'échelle. SKATE permet de traiter des problèmes avec des milliers d'agents et de tâches en obtenant des solutions efficaces en temps limité. SKATE présente de bons résultats en termes de coût des solutions trouvées pour un tel ordre de grandeur d'agents et de tâches, comparé à des méthodes classiques de la littérature, telles qu'un algorithme génétique ou la programmation linéaire en nombres entiers. Grâce à ces résultats, cette thèse a pu envisager deux extensions à SKATE. La première extension permet d'optimiser non seulement les assignations de tâches, mais aussi le nombre d'agents à considérer. Pour cela, cette thèse développe deux méthodes qui permettent d'optimiser à la fois le nombre d'agents (économie de ressources pour le fournisseur de services) tout en garantissant la satisfaction des utilisateurs (temps d'attente avant réalisation d'une tâche). La deuxième extension couple SKATE avec des outils de calcul vérifiable, permettant d'une part aux agents de vérifier que l'assignation des tâches a été correctement effectuée par le serveur central, et d'autre part de contrer des attaques cyber-physiques qu'un réseau d'agents mobiles pourrait subir dans des environnements hostiles, par exemple
This thesis is set in the context of online multi-agent multi-task allocation, aiming to efficiently coordinate a set of agents (resources) to distribute tasks among them. As an application example, we can cite cases where clients make requests to a service provider who seeks the best distribution of tasks among its set of agents: taxis responding to customer demands or robots ensuring the delivery of parcels.Unlike the offline framework, which assumes full knowledge of the allocation problem to be solved before the start of the allocation, in the online framework, tasks arrive over time and must be allocated dynamically. This online optimization framework presents several challenges. Firstly, the repeated allocation of tasks to agents is an NP-hard problem, whose solution must be found in a limited time, sometimes very short. Secondly, knowledge about the arrival of future tasks (e.g., arrival time and location) is generally modest, making long-term reasoning difficult (i.e., optimizing the positioning of agents for long-term planning). Finally, the size of the problem to be handled in terms of agents and tasks can be substantial, especially in a realistic setting where finding a solution within a limited time can sometimes be compromised.In this context, this thesis proposes various contributions. Firstly, this thesis proposes a proactive approach that anticipates the availability of agents in the near future to achieve efficient coordination (i.e., minimizing the distance traveled by agents and the time they remain idle). This proactive approach has been compared to a classic reactive approach. The results obtained in two benchmark problems, one synthetic and the other based on real data, show that the proactive method achieves better results in terms of costs and the number of tasks allocated to agents compared to a reactive approach, while reducing the idle time of resources. Despite the encouraging results obtained, the proposed method has scalability limitations in our real-data-based benchmark problem. To address this limitation, this thesis proposes a second approach that develops a multi-agent multi-task allocation meta-heuristic called SKATE - Successive Rank-based Task Assignment for Proactive Online Planning, enabling scalability. SKATE allows for handling problems with thousands of agents and tasks, obtaining effective solutions in a limited time. SKATE shows good results in terms of the cost of the solutions found for such a scale of agents and tasks when compared to classical methods in the literature, such as a genetic algorithm or integer linear programming. Thanks to these results, this thesis subsequently considered two extensions to SKATE. The first extension optimizes not only task assignments but also the number of agents to consider. To achieve this, this thesis develops two methods that optimize both the number of agents (resource savings for the service provider) while ensuring user satisfaction (waiting time before task completion). The second extension couples SKATE with verifiable computing tools, allowing agents to verify that task assignment has been correctly performed by the central server and countering cyber-physical attacks that a network of mobile agents could face in hostile environments, for example

La dernière décennie a vu l’émergence de systèmes parallèles pour l’analyse de grosse quantités de données (DISC) , tels que Hadoop, et la demande qui en résulte pour les politiques de gestion des ressources, pouvant fournir des temps de réponse rapides ainsi qu’équité. Actuellement, les schedulers pour les systèmes de DISC sont axées sur l’équité, sans optimiser les temps de réponse. Les meilleures pratiques pour surmonter ce problème comprennent une intervention manuelle et une politique de planification ad-hoc , qui est sujette aux erreurs et qui est difficile à adapter aux changements. Dans cette thèse, nous nous concentrons sur la planification basée sur la taille pour les systèmes DISC. La principale contribution de ce travail est le scheduler dit Hadoop Fair Sojourn Protocol (HFSP), un ordonnanceur préemptif basé sur la taille qui tient en considération le vieillissement, ayant comme objectifs de fournir l’équité et des temps de réponse réduits. Hélas, dans les systèmes DISC, les tailles des job d’analyse de données ne sont pas connus a priori, donc, HFSP comprends un module d’estimation de taille, qui calcule une approximation et qui affine cette estimation au fur et a mesure du progrès d’un job. Nous démontrons que l’impact des erreurs d’estimation sur les politiques fondées sur la taille n’est pas significatif. Pour cette raison, et en vertu d’être conçu autour de l’idée de travailler avec des tailles estimées, HFSP est tolérant aux erreurs d’estimation de la taille des jobs. Nos résultats expérimentaux démontrent que, dans un véritable déploiement Hadoop avec des charges de travail réalistes, HFSP est plus performant que les politiques de scheduling existantes, a la fois en terme de temps de réponse et d’équité. En outre, HFSP maintiens ses bonnes performances même lorsque le cluster de calcul est lourdement chargé, car il focalises les ressources sur des jobs ayant priorité. HFSP est une politique préventive: la préemption dans un système DISC peut être mis en œuvre avec des techniques différentes. Les approches actuellement disponibles dans Hadoop ont des lacunes qui ont une incidence sur les performances du système. Par conséquence, nous avons mis en œuvre une nouvelle technique de préemption, appelé suspension, qui exploite le système d’exploitation pour effectuer la préemption d’une manière qui garantie une faible latence sans pénaliser l’avancement des jobs a faible priorité
The past decade have seen the rise of data-intensive scalable computing (DISC) systems, such as Hadoop, and the consequent demand for scheduling policies to manage their resources, so that they can provide quick response times as well as fairness. Schedulers for DISC systems are usually focused on the fairness, without optimizing the response times. The best practices to overcome this problem include a manual and ad-hoc control of the scheduling policy, which is error-prone and difficult to adapt to changes. In this thesis we focus on size-based scheduling for DISC systems. The main contribution of this work is the Hadoop Fair Sojourn Protocol (HFSP) scheduler, a size-based preemptive scheduler with aging; it provides fairness and achieves reduced response times thanks to its size-based nature. In DISC systems, job sizes are not known a-priori: therefore, HFSP includes a job size estimation module, which computes approximated job sizes and refines these estimations as jobs progress. We show that the impact of estimation errors on the size-based policies is not signifi- cant, under conditions which are verified in a system such as Hadoop. Because of this, and by virtue of being designed around the idea of working with estimated sizes, HFSP is largely tolerant to job size estimation errors. Our experimental results show that, in a real Hadoop deployment and with realistic workloads, HFSP performs better than the built-in scheduling policies, achieving both fairness and small mean response time. Moreover, HFSP maintains its good performance even when the cluster is heavily loaded, by focusing the resources to few selected jobs with the smallest size. HFSP is a preemptive policy: preemption in a DISC system can be implemented with different techniques. Approaches currently available in Hadoop have shortcomings that impact on the system performance. Therefore, we have implemented a new preemption technique, called suspension, that exploits the operating system primitives to implement preemption in a way that guarantees low latency without penalizing low-priority jobs

Ce travail de thèse est motivé par la proposition de modèles multi-agents pour le problème du Transport A la Demande (TAD). Le TAD est un problème dynamique de grande complexité qui se prête bien à une modélisation multi-agent. Nos propositions mettent l'accent sur les modèles d'Auto-Organisation dans les Systèmes Multi-Agents qui permettent de considérer de nouveaux critères pour l'évaluation des systèmes proposés, et qui rompent avec la considération stricte de l'utilité de l'opérateur de transport. Nous proposons dans ce travail différentes architectures multi-agents pour la réalisation du système de TAD. Après l'évaluation expérimentale des différentes architectures, nous proposons des améliorations algorithmiques de la meilleure architecture. L'objectif de ces améliorations est de pallier les inconvénients relatifs à la myopie des heuristiques d'insertion et le caractère séquentiel de leur processus d'insertion. D'une part, nous levons la contrainte de non-révocation des décisions d'affectation en permettant aux véhicules d'échanger des clients qu'ils ont déjà affectés. D'autre part, en adoptant une extension du protocole Contract Net, nous proposons aux agents Véhicule de traiter plusieurs clients en parallèle. La troisième contribution de cette thèse est la proposition de deux modèles d'Auto-Organisation (spatiale et temporelle) permettant une meilleure couverture spatiale et temporelle du réseau. Un ensemble d'expérimentations valident nos différentes propositions. Enfin, nous implémentons une plateforme permettant le déploiement de systèmes de TAD dans un contexte opérationnel
This PhD thesis is motivated by the proposal of multiagent models for the Dial A Ride Problem with Time Windows (DARPTW). The DARPTW is a highly complex dynamic problem, for which a multiagent design is relevent. Our proposals focus on Self-Organization models in multiagent systems that allows for the consideration of new criteria for the assessment of the proposed systems, which with the strict consideration of the utility of the transport operator. In our work, we propose several multiagent architectures for the implementation of the DARPTW system. After experimentally evaluating the different architectures, we popose algorrithmic improvements of the best architecture. The objective of these improvements is to palliate the drawbacks related to the myopic behavior of insertion heuristics and the sequentiality of their insertion process. On the one side, we relax the constraint on the non-revokation of assignment decisions by allowing vehicles to exchange customers that they have inserted. On the other side, by adopting an extension of the Contract Net Protocol, we propose to Vehicle agents to process several customers in parallel. The third contribution of this PhD thesis is the proposal of two Self-Organization models (spatial and temporal) allowing a better spatial and temporal coverage of the network. A set of experiments validate our proposals. Finally, we implement a platform allowing for the deployment of DARPTW systems

Dans les problèmes de planification temporelle multi-agents avec des durées incertaines, les agents doivent coordonner et synchroniser l'exécution de leurs tâches (le début et la durée d'une tâche). Ici, la coordination et la synchronisation se concentrent sur la durée des tâches qu'un agent contrôle mais qui sont incontrôlables pour les autres agents du système. Cela signifie qu'une tâche exécutée par un agent du système a une durée qui est décidée par l'agent qui l'exécute (propriétaire) mais qui est incontrôlable pour ceux qui l'observent. Cela est dû à certaines contraintes qualitatives entre les tâches (par exemple, la relation de précédence), notamment le fait qu'un autre agent (observateur) doit attendre l'achèvement de cette tâche pour exécuter les siennes. Pour un tel agent observateur, la durée de cette tâche est incontrôlable à moins d'une communication ou d'une coordination, qui peut avoir lieu avant ou pendant l'exécution du plan. Néanmoins, cet agent a besoin de trouver un plan exécutable selon qu'une telle coordination est effectuée ou non. Telles sont les questions auxquelles cette thèse vise à répondre : Comment pouvons-nous modéliser un tel problème de coordination temporelle ? Comment négocier ces durées incertaines sous le contrôle d'un agent pour réparer un plan non exécutable ? Comment les agents peuvent-ils communiquer lorsqu'ils ne partagent pas une représentation commune du temps ?Pour la première question, un nouveau modèle multi-agent est proposé en utilisant la sémantique des réseaux temporels sous incertitude pour représenter la contrainte temporelle comme un intervalle de valeur possible entre deux instants, qui peuvent être, par exemple, l'instant de début et l'instant de fin d'une tâche. Ce nouveau modèle MISTNU (Multi-agent Interdependent Simple Temporal Network under Uncertainty) représente les tâches partagées comme des contrats négociables entre agents. Ce modèle vise à garantir l'exécutabilité des plans des agents en fonction du moment où la durée des contrats est partagée entre les agents. Si le modèle est jugé incontrôlable et, par conséquent, non exécutable, une phase de réparation est initiée par les agents qui négocieront la durée de ces contrats afin de garantir la contrôlabilité du modèle. Cette thèse a proposé plusieurs solutions au problème de réparation des MISTNU : celles qui sont centralisées, en supposant un agent central doté d'une autorité et d'une observabilité totales, et celles qui n'ont pas d'agent central, ce qui fait que les agents négocient indépendamment la durée de leurs contrats jusqu'à ce qu'une solution soit trouvée (si elle existe).Pour assurer l'interopérabilité entre les agents, une ontologie formelle est fournie qui donne un vocabulaire commun pour les contraintes temporelles sur les intervalles. Cela permet aux agents de se comprendre et de répondre correctement aux demandes
In multi-agent temporal planning problems with uncertain durations, agents must coordinate and synchronize the execution of their tasks (the start and duration of a task). Here, coordination and synchronization are focused on the duration of tasks that an agent controls but are uncontrollable for other agents of the systems. This means a task being performed by one agent of the system has a duration that is decided by the agent executing it (owner) but is uncontrollable for those who observe it. This is due to some qualitative constraints amongst tasks (e.g., precedence relation), such as another agent (observer) needing to wait for the completion of this task to execute its tasks. For such an observer agent, the duration of this task is uncontrollable unless some communication or coordination is made, which can happen before or during the execution of the plan. Nonetheless, this agent needs to find an executable plan for whether such coordination is made. These are the questions this thesis aims to answer: How can we model such temporal coordination problem? How can we negotiate those uncertain durations under the control of one agent to repair a non executable plan? How can agents communicate when they do not share a common representation of time?For the first one, a new multi-agent model is proposed using the semantics of Temporal Networks under Uncertainty to represent temporal constraint as an interval of possible value between two instants, which can be, for instance, the start and end instant of a task. This new Multi-agent Interdependent Simple Temporal Network under Uncertainty (MISTNU) model represents shared tasks as negotiable contracts between agents. This model aims to guarantee the executability of agents 'plans depending on when the duration of the contracts is shared among the agents. If the model is deemed uncontrollable and, hence, not executable, then a repair phase is initiated by the agents that will negotiate the duration of these contracts to ensure the controllability of the model. This thesis proposed multiple solutions to the repair problem of MISTNUs: those that are centralized, assuming a central agent with full authority and observability, and those without such a central agent, resulting in agents independently negotiating the duration of their contracts until a solution is found (if it exists).To ensure interoperability between agents, a formal ontology is provided that gives a common vocabulary for temporal constraints on intervals. This ensures agents can understand each other and properly answer requests

Le but des travaux présentés dans cette thèse est de proposer un système d'aide à la décision pour la régulation du trafic au sein d'un réseau de transport collectif multimodal. Nous définissons la régulation comme la réaffectation, à travers différentes décisions, des horaires et des itinéraires aux différents véhicules du réseau en cas de perturbation. Afin de mieux représenter les aspects statiques et dynamiques du réseau, nous proposons une modélisation hybride du système de transport (agents et graphes). Le Système Multi-Agent d'Aide à la Décision (SMAAD) proposé réalise les deux phases principales du processus de régulation: le diagnostic des incidents et la prise de décision. Le SMAAD inclut des agents ZONEREG qui génèrent des décisions via une approche évolutionniste de régulation qui peut mener à une reconfiguration partielle du réseau. Cette approche tient compte de la flexibilité courante. Elle intègre ainsi un algorithme de recherche de chemins hamiltoniens.

Nous nous intéressons dans cette thèse à la planification pour les problèmes de prise de décision décentralisée séquentielle dans l'incertain. Dans le cadre centralisé, l'utilisation des formalismes MDP et POMDP a permis d'élaborer des techniques de planification efficaces. Le cadre Dec-POMDP permet de formaliser les problèmes décentralisés. Ce type de problèmes appartient à une autre classe de complexité que les problèmes centralisés. Pour cette raison, jusqu'à récemment, seuls de très petits problèmes pouvaient être résolus et uniquement pour des horizons très faibles. Des algorithmes heuristiques ont récemment été proposés pour traiter des problèmes de taille plus conséquente mais n'ont pas de preuve théorique de qualité de solution. Nous montrons comment une information heuristique sur le problème à résoudre représentée par une distribution de probabilité sur les croyances centralisées permet de guider la recherche approchée de politique. Cette information heuristique permet de formuler chaque étape de la planification comme un problème d'optimisation combinatoire. Cette formulation conduit à des politiques de meilleure qualité que les approches existantes
In this thesis, we focus on planning in decentralised sequentialdecision taking in uncertainty. In the centralised case, the MDP andPOMDP frameworks leads to efficient planning algorithms. The Dec-POMDPframework is used to model decentralised problems. This kind ofproblems is in a higher class of complexity than the centralisedproblem. For this reason, until recently, only very small problem could be solved and only for very small horizons. Recently, some heuristic algorithms have been proposed to handle problem of higher size but there is no theoretic proof of the solution quality. In this thesis, we show how to use a heuristic information in the problem, modelled as a probability distribution on the centralised beliefs, to guide the search for a good approximate policy. Using this heuristic information, we formulate each time step of the planning procedure as a combinatorial optimisation problem. This formulation leads to policies of better quality than previously existing approaches