In this paper, nogood recording is investigated for CSP within the randomization and restart framework. Our goal is to avoid the same situations to occur from one run to the next ones. More precisely, nogoods are recorded when the current cutoff value is reached, i.e. before restarting the search algorithm. Such a set of nogoods is extracted from the last branch of the current search tree and exploited using the structure of watched literals originally proposed for SAT. We prove that the worst-case time complexity of extracting such nogoods at the end of each run is only O(n²d) where n is the number of variables of the constraint network and d the size of the greatest domain, whereas for any node of the search tree, the worst-case time complexity of exploiting these nogoods to enforce Generalized Arc Consistency (GAC) is O(nβ) where β denotes the number of recorded nogoods. As the number of nogoods recorded before each new run is bounded by the length of the last branch, the total number of recorded nogoods is polynomial in the number of restarts. Interestingly, we show that when the minimization of the nogoods is envisioned with respect to an inference operator φ, it is possible to directly identify some nogoods that cannot be minimized. For φ=AC (i.e. for MAC), the worst-case time complexity of extracting minimal nogoods is slightly increased to O(en²d³) where e is the number of constraints of the network. Experimentation over a wide range of CSP instances using a generic state-of-the-art CSP solver demonstrates the effectiveness of this approach. Recording nogoods (and in particular, minimal nogoods) from restarts significantly improves the robustness of the solver.

A key feature of modern optimal planners such as Graphplan and Blackbox is their ability to prune large parts of the search space. Previous Partial Order Causal Link (POCL) planners provide an alternative branching scheme but lacking comparable pruning mechanisms do not perform as well. In this paper, a domain-independent formulation of temporal planning based on Constraint Programming is introduced that successfully combines a POCL branching scheme with powerful and sound pruning rules. The key novelty in the formulation is the ability to reason about supports, precedences, and causal links involving actions that are not in the plan. Experiments over a wide range of benchmarks show that the resulting optimal temporal planner is much faster than current ones and is competitive with the best parallel planners in the special case in which actions have all the same duration.

Planners of the Graphplan family (Graphplan, IPP, STAN...) are currently considered to be the most efficient ones on numerous planning domains. Their partially ordered plans can be represented as sequences of sets of actions. The sets of actions generated by Graphplan satisfy a strong independence property which allows one to manipulate each set as a whole. We present a detailed formal analysis that demonstrates that the independence criterion can be partially relaxed in order to produce valid plans in the sense of Graphplan. Indeed, two actions at a same level of the planning-graph do not need to be marked as mutually exclusive if there exists a possible ordering between them that respects a criterion of "authorization", less constrained than the criterion of independence. The ordering between the actions can be set up after the plan has been generated, and the extraction of the solution plan needs an extra checking process that guarantees that an ordering can be found for actions considered simultaneously, at each level of the planning-graph. This study lead us to implement a modified Graphplan, LCGP (for "Least Committed GraphPlan"), which is still sound and complete and generally produces plans that have fewer levels than those of Graphplan (the same number in the worst cases). We present an experimental study which demonstrates that, in classical planning domains, LCGP solves more problems than planners from the family of Graphplan (Graphplan, IPP, STAN...). In most cases, LCGP also outperforms the other planners.

An original approach, termed Divide-and-evolve is proposed to hybridize Evolutionary Algorithms (EAs) with Operational Research (OR) methods in the domain of Temporal Planning Problems (TPPs). Whereas standard Memetic Algorithms use local search methods to improve the evolutionary solutions, and thus fail when the local method stops working on the complete problem, the Divide-and-evolve approach splits the problem at hand into several, hopefully easier, sub-problems, and can thus solve globally problems that are intractable when directly fed into deterministic OR algorithms. But the most prominent advantage of the Divide-and-evolve approach is that it immediately opens up an avenue for multi-objective optimization, even though the OR method that is used is single-objective. Proof of concept approach on the standard (single-objective) Zeno transportation benchmark is given, and a small original multi-objective benchmark is proposed in the same Zeno framework to assess the multi-objective capabilities of the proposed methodology, a breakthrough in Temporal Planning.

It has recently been shown, for the Constraint Satisfaction Problem (CSP), that the state associated with a node of the search tree built by a backtracking algorithm can be exploited, using a transposition table, to prevent the exploration of similar nodes. This technique is commonly used in game search algorithms, heuristic search or planning. Its application is made possible in CSP by computing a partial state – a set of meaningful variables and their associated domains – preserving relevant information. We go further in this paper by providing two new powerful operators dedicated to the extraction of inconsistent partial states. The first one eliminates any variable whose current domain can be deduced from the partial state, and the second one extracts the variables involved in the inconsistency proof of the subtree rooted by the current node. Interestingly, we show these two operators can be safely combined, and that the pruning capabilities of the recorded partial states can be improved by a dominance detection approach (using lazy data structures).

In this paper, a state-based approach for the Constraint Satisfaction Problem (CSP) is proposed. The key novelty is an original use of state memorization during search to prevent the exploration of similar subnetworks. Classical techniques to avoid the resurgence of previously encountered conflicts involve recording conflict sets. This contrasts with our state-based approach which records subnetworks – a snapshot of some selected domains – already explored. This knowledge is later used to either prune inconsistent states or avoid recomputing the solutions of these subnetworks. Interestingly enough, the two approaches present some complementarity: different states can be pruned from the same partial instantiation or conflict set, whereas different partial instantiations can lead to the same state that needs to be explored only once. Also, our proposed approach is able to dynamically break some kinds of symmetries (e.g. neighborhood interchangeability). The obtained experimental results demonstrate the promising prospects of state-based search.

In this paper, nogood recording is investigated within the randomization and restart framework. Our goal is to avoid the same situations to occur from one run to the next one. More precisely, nogoods are recorded when the current cutoff value is reached, i.e. before restarting the search algorithm. Such a set of nogoods is extracted from the last branch of the current search tree. Interestingly, the number of nogoods recorded before each new run is bounded by the length of the last branch of the search tree. As a consequence, the total number of recorded nogoods is polynomial in the number of restarts. Experiments over a wide range of CSP instances demonstrate the effectiveness of our approach.

In this paper, we propose an approach to guide search to sources of conflicts. The principle is the following: the last variable involved in the last conflict is selected in priority, as long as the constraint network can not be made consistent, in order to find the (most recent) culprit variable, following the current partial instantiation from the leaf to the root of the search tree. In other words, the variable ordering heuristic is violated, until a backtrack to the culprit variable occurs and a singleton consistent value is found. Consequently, this way of reasoning can easily be grafted to many search algorithms and represents an original way to avoid thrashing. Experiments over a wide range of benchmarks demonstrate the effectiveness of this approach.

An original approach, termed Divide-and-Evolve is proposed to hybridize Evolutionary Algorithms (EAs) with Operational Research (OR) methods in the domain of Temporal Planning Problems (TPPs). Whereas standard Memetic Algorithms use local search methods to improve the evolutionary solutions, and thus fail when the local method stops working on the complete problem, the Divide-and-Evolve approach splits the problem at hand into several, hopefully easier, sub-problems, and can thus solve globally problems that are intractable when directly fed into deterministic OR algorithms. But the most prominent advantage of the Divide-and-Evolve approach is that it immediately opens up an avenue for multi-objective optimization, even though the OR method that is used is single-objective. Proof of concept approach on the standard (single-objective) Zeno transportation benchmark is given, and a small original multi-objective benchmark is proposed in the same Zeno framework to assess the multi-objective capabilities of the proposed methodology, a breakthrough in Temporal Planning.

Many benchmark domains in AI planning including Blocks, Logistics, Gripper, Satellite, and others lack the interactions that characterize puzzles and can be solved non-optimally in low polynomial time. They are indeed easy problems for people, although as with many other problems in AI, not always easy for machines. In this paper, we address the question of whether simple problems such as these can be solved in a simple way, i.e., without search, by means of a domain-independent planner. We address this question empirically by extending the constraint-based planner CPT with additional domain-independent inference mechanisms. We show then for the first time that these and several other benchmark domains can be solved with no backtracks while performing only polynomial node operations. This is a remarkable finding in our view that suggests that the classes of problems that are solvable without search may be actually much broader than the classes that have been identified so far by work in Tractable Planning.

A key feature of modern optimal planners such as Graphplan and Blackbox is their ability to prune large parts of the search space. Previous Partial Order Causal Link (POCL) planners provide an alternative branching scheme but lacking comparable pruning mechanisms do not perform as well. In this paper, a domain-independent formulation of temporal planning based on Constraint Programming is introduced that successfully combines a POCL branching scheme with powerful and sound pruning rules. The key novelty in the formulation is the ability to reason about supports, precedences, and causal links involving actions that are not in the plan. Experiments over a wide range of benchmarks show that the resulting optimal temporal planner is much faster than current ones and is competitive with the best parallel planners in the special case in which actions have all the same duration.

Relaxed plans are used in the heuristic search planner FF for computing a numerical heuristic and extracting helpful actions. We present a novel way for extracting information from the relaxed plan and for dealing with helpful actions, by considering the high quality of the relaxed plans in numerous domains. For each evaluated state, we employ actions from these plans in order to find the beginning of a valid plan that can lead to a reachable state. We use this lookahead strategy in a complete best-first search algorithm, modified in order to take into account helpful actions. In numerous planning domains, the performance of heuristic search planning and the size of the problems that can be handled have been drastically improved.

Relaxed plans are used in the heuristic search planner FF for computing a numerical heuristic and extracting helpful actions. We present a novel way for extracting information from the relaxed plan and for dealing with helpful actions, by considering the high quality of the relaxed plans. In numerous domains, the performance of heuristic search planning and the size of the problems that can be handled have been drastically improved.

Planners from the family of Graphplan (Graphplan, IPP, STAN...) are presently considered as the most efficient ones on numerous planning domains. Their partially ordered plans can be represented as sequences of sets of simultaneous actions. Using this representation and the criterion of independence, Graphplan constrains the choice of actions in such sets. We demonstrate that this criterion can be partially relaxed in order to produce valid plans in the sense of Graphplan. Our planner LCGP needs fewer levels than Graphplan to generate these plans (the same number in the worst cases). Then we present an experimental study which demonstrates that, in classical planning domains, LCGP "practically" solves more problems than planners from the family of Graphplan (Graphplan, IPP, STAN...). In most cases, these tests demonstrate the best performances of LCGP. Then, we present a domain-independent heuristic for variable and domain ordering. LCGP is thus improved using this heuristic, and compared with HSP-R, a very efficient non-optimal sequential planner, based on an heuristic backward state space search.

In this paper, we present VVPLAN, a planner based on a classical state space search algorithm. The language used for domain and problem representation is ADL (Pednault 1989). We have compared VVPLAN to UCPOP (Penberthy and Weld 1992)(Weld 1994), a planner that admits the same representation language. Our experiments prove that such an algorithm is often more efficient than a planner based on a search in the space of partial plans. This result is achieved as soon as we introduce in VVPLAN s algorithm a loop test relating to previously visited states. In particular domains, VVPLAN can also outperform IPP (Koehler et al. 1997), which makes a planning graph analysis as GRAPHPLAN. We present here the details of our comparison with UCPOP, the results we obtain and our conclusions.

In this paper, nogood recording is investigated for CSP within the randomization and restart framework. Our goal is to avoid the same situations to occur from one run to the next one. More precisely, nogoods are recorded when the current cutoff value is reached, i.e. before restarting the search algorithm. Such a set of nogoods is extracted from the last branch of the current search tree and managed using the structure of watched literals originally proposed for SAT. Interestingly, the number of nogoods recorded before each new run is bounded by the length of the last branch of the search tree. As a consequence, the total number of recorded nogoods is polynomial in the number of restarts. Experiments over a wide range of CSP instances demonstrate the effectiveness of this approach.

A key feature of modern optimal planners such as Graphplan and Blackbox is their ability to prune large parts of the search space. Previous Partial Order Causal Link (POCL) planners provide an alternative branching scheme but lacking comparable pruning mechanisms do not perform as well. In this paper, a domain-independent formulation of temporal planning based on Constraint Programming is introduced that successfully combines a POCL branching scheme with powerful and sound pruning rules. The key novelty in the formulation is the ability to reason about supports, precedences, and causal links involving actions that are not in the plan. Experiments over a wide range of benchmarks show that the resulting optimal temporal planner is much faster than current ones and is competitive with the best parallel planners in the special case in which actions have all the same duration.

Dans cet article, nous proposons une étude concernant l'identification et l'exploitation des états partiels inconsistants (IPS) dans le cadre de la résolution du problème de satisfaction de contraintes (CSP). Un IPS correspond à un ensemble de « décisions d'appartenance » prises sur un réseau de contraintes et ne menant à aucune solution. Notre étude tend à unifier un certain nombre de travaux récents concernant les nogoods généralisés, le concept de valeurs en échec et la détection de dominance. Nous introduisons un formalisme simple et unificateur et montrons comment la cohérence d'arc généralisée (GAC) peut être établie efficacement sur les contraintes associées aux IPSs tout au long de la recherche. Nous identifions également plusieurs opérateurs qui permettent d'extraire des IPSs à chaque noeud de l'arbre de recherche prouvé comme étant la racine d'un sous-arbre sans solutions.

Dans ce papier, nous proposons une approche basée sur la reconnaissance d'états dans le cadre de la résolution du problème de satisfaction de contraintes (CSP). L'idée principale consiste en la mémorisation d'états pendant la recherche de manière à prévenir la résolution de sous-réseaux similaires. Les techniques classiques évitent la réapparition de conflits précédemment rencontrés en enregistrant des ensembles conflits (conflict sets). Ceci contraste avec notre approche basée sur les états qui mémorise des sousréseaux déjà explorés, c'est à dire une photographie de certains domaines sélectionnés. Ces informations sont ensuite exploitées soit pour éviter le parcours d'états inconsistents ou alors pour éviter de recalculer l'ensemble des solutions de ces sous-réseaux. Les deux approches présentent une certaine complémentarité : en effet différents états peuvent être évités à partir d'une même instantiation partielle ou ensemble conflits tandis que différentes instantiations partielles peuvent mener à un même état qui n'a besoir d'être exploré qu'une seule fois. De plus notre méthode permet de détecter et casser dynamiquement certaines formes de symétries (notamment la neighborhood interchangeability). Les résultats expérimentaux obtenus laissent entrevoir des perspectives prometteuses pour la recherche basée sur les états.

Dans ce papier, nous proposons une nouvelle approche pour guider la recherche vers la source des conflits. Son principe est le suivant : après chaque conflit, la dernière variable assignée est sélectionnée en priorité tant que le réseau de contraintes est inconsistant. Ceci permet de découvrir la variable coupable la plus récente (i.e. à l'origine de l'échec) en remontant la branche courante de la feuille vers la racine de l'arbre de recherche. Autrement dit, l'heuristique de choix de variables est violée jusqu'au moment où un retour-arrière sur la variable coupable est effectué et que l'on découvre une valeur singleton consistante. En conséquence, ce type de raisonnement, qui représente un moyen original d'éviter le thrashing, peut facilement être intégré à de nombreux algorithmes de recherche. Les expérimentations effectuées sur un large éventail d'instances démontrent l'efficacité de cette approche.

Une approche originale dénommée Divide-and-Evolve est proposée pour l'hybridation des Algorithmes Évolutionnaires (AEs) avec des méthodes d'Intelligence Artificielle dans le domaine des Problèmes de Planification Temporelle (PPTs). Alors que les algorithmes mémétiques standards utilisent des méthodes locales de résolution pour améliorer les solutions évolutionnaires, l'approche Divide-and-Evolve divise arbitrairement le problème en plusieurs sous-problèmes (que l'on espère plus faciles), et peut ainsi résoudre globalement des problèmes hors d'atteinte lorsque directement fournis en entrée d'algorithmes spécialisés classiques. Mais le principal avantage de l'approche Divide-and-Evolve est qu'elle ouvre immédiatement une avenue pour l'optimisation multi-objectifs, même avec une méthode spécialisée mono-objectif. La preuve du concept de cette approche sur le benchmark de transport standard Zeno (mono-objectif) est donnée, et un petit benchmark multi-objectifs original est proposé dans ce même cadre Zeno pour montrer les possibilités multi-objectifs de la méthodologie proposée, une percée dans la planification temporelle.

De nombreux problèmes utilisés en planification de tâches dans le domaine de l'intelligence artificielle comme Blocks, Logistics, Gripper, Satellite et d'autres, ne possèdent pas les interactions qui caractérisent les puzzles. Ils peuvent être résolus rapidement mais non optimalement en temps polynomial. Ce sont en effet des problèmes faciles pour les humains, mais comme beaucoup d'autres problèmes en intelligence artifcielle, difficiles pour les machines. Dans ce travail, nous étudions le type d'inférences requises dans un planificateur indépendant du domaine pour résoudre des problèmes simples en évitant au maximum de faire des retours arrière, en ajoutant uniquement quelques opérations polynomiales à chaque noeud de l'arbre de recherche. A cette fin, nous utilisons le planificateur temporel optimal CPT qui combine un schéma de branchement de type POCL avec des mécanismes d'inférence puissants, et montrons que l'ajout de quelques règles d'inférence simples et générales suffisent pour éliminer les retours arrière pour de nombreux domaines. Il s'agit là d'un résultat empirique intéressant, à notre avis, qui pourrait contribuer au développement de planificateurs automatiques plus robustes, et à une meilleure compréhension de la façon des planifier des humains. Nous apportons aussi une amélioration des performances significative par rapport à CPT.

Une des principales caractéristiques des planificateurs optimaux modernes tels Graphplan et Blackbox est leur capacité d'élaguer de larges parts de l'espace de recherche. D'un autre côté, les planificateurs plus anciens effectuant une recherche dans les espaces de plans partiels offrent des possibilités d'exploration de l'espace de recherche intéressantes mais ne disposent pas de mécanismes d'élaguage aussi performants. Nous proposons dans cet article une formulation de la planification temporelle indépendante du domaine basée sur la programmation par contraintes, qui combine avec succès les possibilités d'exploration de l'espace de recherche de la planification dans les espaces de plans partiels avec des règles d'élaguage puissantes et saines. La principale innovation de cette formulation est la capacité de raisonner autour des supports, des relations de précédence et des liens causaux, en faisant intervenir les actions qui n'appartiennent pas encore à un plan partiel. Des expérimentations avec de nombreux benchmarks montrent que le planificateur temporel optimal que nous avons réalisé est beaucoup plus performant que les planificateurs temporels optimaux actuels, et est compétitif avec les meilleurs planificateurs parallèles dans le cas particulier où toutes les actions ont la même durée.

Les plans relaxés sont utilisés dans le planificateur par recherche heuristique FF pour calculer une heuristique numérique et extraire les actions « utiles ». Nous présentons une nouvelle manière d'extraire des informations d'un plan relaxé et d'employer les actions utiles, en considérant la grande qualité de ces plans relaxés dans de nombreux domaines. Pour chaque état évalué, nous employons les actions du plan relaxé retourné par la fonction de calcul de l'heuristique afin de trouver le début d'un plan valide conduisant à un état atteignable. Nous utilisons cette stratégie d'anticipation dans un algorithme de recherche de type meilleur-d'abord, modifié afin de prendre en compte les actions utiles. Dans de nombreux domaines de planification, les performances de la planification par recherche heuristique et la taille des problèmes pouvant être résolus sont très fortement améliorés, tandis que dans d'autres domaines plus « difficiles » ces stratégies restent intéressantes même si elles dégradent parfois un peu la qualité en nombre d'actions des plans produits.

Cet article présente notre synthèse des travaux actuels sur la planification par satisfaction de bases de clauses (planification SAT). Nous y détaillons les améliorations que nous avons apportées aux codages classiques dans les espaces d'états, de plans et au codage du graphe de planification. Celles-ci sont essentiellement basées sur l'introduction du parallélisme et sur l'utilisation de la relation d'autorisation à la place de celle d'indépendance. Nous présentons notre planificateur TSP (Tunable SAT Planner) qui intègre un traducteur permettant d'automatiser toutes ces méthodes de résolution. Chacun des différents codages peut être ainsi indifféremment utilisé pour traiter un problème de planification donné : la base de clauses automatiquement fournie par le traducteur est donnée à un solveur SAT, et fournit, après traduction inverse du modèle qu'il renvoi, le plan-solution. Cet outil nous permet de montrer l'impact de nos améliorations sur les benchmarks classiques de planification.

Nous présentons une amélioration de la procédure d'extraction de plans DPPlan qui exploite la structure de graphe de planification pour effectuer une recherche de type Davis et Putnam. Le graphe n'est pas codé sous forme d'une base de clauses comme dans Satplan, mais utilisé directement par diverses fonctions qui propagent des valeurs attachées aux noeuds d'action et de fluent, conduisant à une procédure de recherche bidirectionnelle. Nous reconstruisons cet algorithme sur la base d'une version « minimale »" qui effectue le moins de propagations possibles, basée sur le codage du graphe de planification sous forme d'une base de clauses. Nous montrons alors comment utiliser la relation d'autorisation entre actions, qui est une relation moins contrainte que la relation classique d'indépendance qui garantit la possibilité pour deux actions d'être exécutées en parallèle. L'utilisation de la relation d'autorisation dans DPPlan, comme dans Graphplan, améliore considérablement les performances de cet algorithme.

Les planificateurs de la famille de Graphplan sont aujourd'hui considérés comme étant les plus performants sur de nombreux domaines de planification. Les plans partiellement ordonnés qu'ils génèrent peuvent être représentés par des séquences d'ensembles d'actions simultanées. Conformément au modèle choisi, Graphplan contraint fortement - au travers du concept d'indépendance - le choix des actions au sein de ces ensembles d'actions. Nous montrons ici que l'on peut relâcher en partie ce critère d'indépendance de manière à produire des plans valides au sens de Graphplan. Leur génération par l'algorithme LCGP ainsi obtenu nécessite moins de niveaux qu'avec Graphplan (le même nombre dans les pires cas). Nous présentons ensuite une étude expérimentale portant sur des jeux de tests classiques qui montre que l'ensemble des problèmes résolus « pratiquement » par Graphplan est strictement inclus dans celui des problèmes résolus « pratiquement » par LCGP, avec des performances qui sont très nettement supérieures dans la plupart des cas.

The planning as heuristic search framework, initiated by the planners ASP from Bonet, Loerincs and Geffner, and HSP from Bonet and Geffner, lead to some of the most performant planners, as demonstrated in the two previous editions of the International Planning Competition. We focus in this paper on a technique introduced by Hoffmann and Nebel in the FF planning system for calculating the heuristic, based on the extraction of a solution from a planning graph computed for the relaxed problem obtained by ignoring deletes of actions. This heuristic is used in a forward-chaining search algorithm to evaluate each encountered state. As a side effect of the computation of this heuristic, more information is derived from the planning graph and its solution, namely the helpful actions which permit FF to concentrate its efforts on more promising ways, forgetting the other actions in a local search algorithm. We introduce a novel way for extracting information from the computation of the heuristic and for tackling with helpful actions, by considering the high quality of the plans computed by the heuristic function in numerous domains. For each evaluated state, we employ actions from these plans in order to find the beginning of a valid plan that can lead to a reachable state, that will often bring us closer to a solution state. The lookahead state thus calculated is then added to the list of nodes that can be chosen to be developed following the numerical value of the heuristic. We use this lookahead strategy in a complete best-first search algorithm, modified in order to take into account helpful actions by preferring nodes that can be developed with such actions over nodes that can be developed with actions that are not considered as helpful. We then provide an empirical evaluation which demonstrates that in numerous planning benchmark domains, the performance of heuristic search planning and the size of the problems that can be handled have been drastically improved, while in more "difficult" domains these strategies remain interesting even if they sometimes degrade plan quality.

Cette thèse s'inscrit dans le cadre de la planification de tâches en Intelligence Artificielle. Après avoir présenté les principales méthodes, en particulier la recherche dans les graphes de planification et la planification par satisfiabilité, nous analysons en détail le planificateur Graphplan. Une étude formelle des plans qu'il calcule nous conduit à réactualiser une idée de base de la planification dans les espaces de plans : le moindre engagement. En effet, une des raisons du succès de ce type de planification est le fait que le choix de l'ordonnancement des actions est retardé le plus possible (suivant les stratégies), ce qui permet de réduire la taille de l'espace de recherche. Nous montrons que l'on peut effectuer certains choix d'ordonnancement d'actions après avoir trouvé un plan-solution, ce qui apporte dans certains domaines une amélioration significative des performances due à une forte réduction de la taille de l'espace de recherche. Le calcul supplémentaire induit est de complexité polynomiale. Nous présentons ensuite le codage d'un problème de planification sous forme de base de clauses en logique propositionnelle. Nous passons en revue les principales techniques de codage proposées dans la littérature, en nous appuyant notamment sur une analyse critique d'un article de référence. Nous proposons des corrections ou des améliorations pour chacun des codages étudiés. Nous présentons enfin la méthode DPPlan qui permet d'utiliser des techniques SAT sur un graphe de planification. Nous analysons l'article qui décrit cet algorithme et montrons que ce dernier possède un problème de conception. Nous proposons alors une formalisation de cette technique qui permet d'exhiber une version « minimale » et correcte de DPPlan, et montrons comment l'étendre avec les règles de propagation de la version originelle. Nous montrons enfin comment profiter de notre stratégie de moindre engagement dans DPPlan.