International audience

Recent domain-determinization techniques have been very successful in many probabilistic planning problems. We claim that traditional heuristic MDP algorithms have been unsuccessful due mostly to the lack of efficient heuristics in structured domains. Previous attempts like mGPT used classical planning heuristics to an all-outcome determinization of MDPs without discount factor; yet, discounted optimization is required to solve problems with potential dead-ends. We propose a general extension of classical planning heuristics to goal-oriented discounted MDPs, in order to overcome this flaw. We apply our theoretical analysis to the well-known classical planning heuristics Hmax and Hadd, and prove that the extended Hmax is admissible. We plugged our extended heuristics to popular graph-based (Improved-LAO*, LRTDP, LDFS) and ADD-based (sLAO*, sRTDP) MDP algorithms: experimental evaluations highlight competitive results compared with the winners of previous competitions (FF-Replan, FPG, RFF), and show that our discounted heuristics solve more problems than non-discounted ones, with better criteria values. As for classical planning, the extended Hadd outperforms the extended Hmax on most problems.

Multicore machines are becoming a standard way to speed up the system performance. After having instantiated the evolutionary metaheuristic DAEX with the forward search YAHSP planner, we investigate on the global parallelism approach, which exploits the intrinsic parallelism of the individual evaluation. This paper describes a parallel shared-memory version of the DAEYAHSP planning system using the OpenMP directive-based API. The parallelization scheme applies at a high level of abstraction and thus can be used by any evolutionary algorithm implemented with the Evolving Objects framework. The proof of concept is validated on a 48-core machine with two planning tasks extracted from the last international planning competition. Experiments show significant speedups with an increasing number of cores. This preliminary work opens an avenue for parallelizing any evolutionary algorithm developed with EO that would target multicore architectures.

Divide-and-Evolve (DaE) is an original "memeticization" of Evolutionary Computation and Artificial Intelligence Planning. However, like any Evolutionary Algorithm, DaE has several parameters that need to be tuned, and the already excellent experimental results demonstrated by DaE on benchmarks from the International Planning Competition, at the level of those of standard AI planners, have been obtained with parameters that had been tuned once and forall using the Racing method. This paper demonstrates that more specific parameter tuning (e.g. at the domain level or even at the instance level) can further improve DaE results, and discusses the trade-off between the gain in quality of the resulting plans and the overhead in terms of computational cost.

Motivated by the recent hardware evolution towards multi-core machines, we investigate parallel planning techniques in a shared-memory environment. We consider, more specifically, parallel versions of a best-first search algorithm that run K threads, each expanding the next best node from the open list. We show that the proposed technique has a number of advantages. First, it is (reasonably) simple: we show how the algorithm can be obtained from a sequential version mostly by adding parallel annotations. Second, we conduct an extensive empirical study that shows that this approach is quite effective. It is also dynamic in the sense that the number of nodes expanded in parallel is adapted during the search. Overall we show that the approach is promising for parallel domain-independent, suboptimal planning.