A Systematic and Complete Algorithm to Computer Higher Order Execution Relations

Planning graphs and binary mutual exclusion (mutex) relations presented a major breakthrough in automated planning technology. They have been exploited in three ways, i.e. extracting optimal parallel plans through search in the space of planning subgraphs; extracting informative heuristics to guide search either in state- or in plan-space; and converting the planning problem into an equivalent satisfiability one. This paper advances the area of planning graphs a step further, by providing for the first time a systematic and complete algorithm to compute exclusion relations (or nands as we call them) without a bound on their order. Computing all exclusion relations among the propositions of a planning problem is equivalent to enforcing strong k-consistency, with k being the number of propositions, i.e., global consistency. The expected consequence is that, if global consistency has been achieved, plans can be extracted in a backtracking free manner. This is proved in the paper for the proposed algorithm and demonstrated experimentally over various small problems from several planning domains. The obvious limitation is that it is practically impossible to compute all higher order exclusion relations for all problems but the smaller ones. So, our work is mainly of theoretical importance; its potential practical importance lies in serving as a starting point for obtaining unexplored relaxations, i.e., new families of heuristics, to be exploited by a graph or state-space based search procedure