Jacques Lévy

Véhel Ircyn

Analyse Fractale : une nouvelle génération d'outils pour le Traitement du Signal

Keywords: analyse fractale, traitement du signal, multifractal, IFS, processus stables, segmentation d'images, compression, débruitage, analyse financière, trafic internet fractal analysis, signal processing, multifractal, IFS, stable processes, image segmentation, compression, denoising, financial analysis, internet traffic

Récemment, plusieurs développements importants en analyse fractale ont eu un impact majeur sur les applications en traitement du signal. Nous abordons brièvement la théorie des systèmes de fonctions itérées, l'analyse multifractale, et les processus stables fractionnaires, en expliquant comment des progrès dans ces divers champs ont conduit à de nouvelles méthodes en traitement des images (compression, watermarking, segmentation, débruitage, . . . ), analyse financière, et modélisation du trafic sur les réseaux informatiques. Ces applications, parmi d'autres, montrent que l'analyse fractale est résolument passée depuis quelques années du "stade descriptif" au "stade opérationnel".

ABSTRACT. Recently, a number of important progresses in fractal analysis have had a major impact in signal processing applications. We review briefly IFS theory, multifractal analysis and stable fractional processes theory; we indicate how these theoretical tools lead to new methods for image processing (segmentation, denoising, compression), financial analysis, and internet traffic modeling. Among others, these applications show that fractal analysis is no longer restricted to a descriptive role, but has entered an operational phase.

Géométrie fractale : origines et évolution

La géométrie fractale, apparue dans les années 70 [START_REF] Mandelbrot | The fractal geometry of nature[END_REF] comme fruit d'une synthèse de travaux effectués en mathématiques et en physique depuis plus d'un siècle [28,[START_REF] Hausdorff | Dimension und ausseres Mass[END_REF][START_REF] Richardson | Weather Prediction by numerical process[END_REF][START_REF] Hurst | Long term storage capacity of reservoirs[END_REF], a proposé de nouveaux concepts pour appréhender certains phénomènes complexes. Les notions de dimension fractionnaire et d'invariance d'échelle 1 1: une propriété est dite invariante d'échelle (dans une certaine gamme de résolutions) si elle ne possède pas d'échelle caractéristique dans la gamme considérée. En d'autres termes, on ne peut pas connaître l'échelle d'observation en mesurant cette propriété. Analytiquement, et dans le cas plus simple où cette ont rapidement été reconnues pertinentes pour la description de nombreux objets naturels, des reliefs montagneux [START_REF] Peitgen | The beauty of fractals[END_REF] aux amas de percolation en passant par les fronts de diffusion [START_REF] Bunde | Fractals and disordered systems[END_REF], les milieux poreux [START_REF] Adler | Porous Media: Geometry and Transport[END_REF] ou la catalyse chimique [START_REF] Ed | The Fractal approach to Heterogeneous Chemistry[END_REF]. Ces outils ont par exemple permis de mieux comprendre les phénomènes de croissance loin de l'équilibre qui apparaissent de manière spontanée dans de nombreux domaines, comme le claquage diélectrique ou la croissance dendritique. Les physiciens, les chimistes ou les astronomes ont ainsi pu disposer de nouvelles mesures quantitatives pour caractériser les objets qu'ils étudient : la dimension d'un amas obtenu par agrégation diffusive de particules, par exemple, est différente de celle d'un amas obtenu par agrégation balistique.

Les applications en traitement du signal et plus généralement en sciences de l'information ne sont apparues que plus tardivement, vers le début des années 80. Une caractéristique des premières tentatives est la vision essentiellement descriptive qui y était à l'oeuvre : des signaux étaient analysés et des comportements fractals étaient ou non relevés, le plus souvent sous la forme d'une invariance d'échelle dans une certaine gamme de résolutions. On en déduisait une "dimension fractale", et les développements s'arrêtaient là. Cette phase descriptive était très certainement nécessaire, et elle a en tout cas permis de se familiariser avec des notions nouvelles à l'époque. Cependant, elle a aussi, un temps, donné l'impression que si la géométrie fractale pouvait offrir aux sciences de l'ingénieur une description compacte et "intelligente" de certains phénomènes, elle ne permettait pas de créer des procédés opératoires nouveaux.

Deux importantes évolutions de nature différente ont permis d'entrer dans une phase "opérationnelle" au début des années 90. La première, qui s'inscrit naturellement dans les développements d'une discipline jeune, est l'enrichissement des outils de base de la théorie en vue des applications à la variété des phénomènes naturels : à la caractérisation, somme toute assez pauvre, d'un signal par sa seule "dimension fractale", sont venus s'ajouter des mesures beaucoup plus fines, comme la lacunarité ou l'analyse multifractale ; les modèles de processus fractals, d'abord parfaitement autosimilaires, se sont diversifiés pour tenir compte d'invariances dans des sens généralisés ; enfin, les méthodes statistiques d'analyse des signaux fractals se sont perfectionnées pour fournir des estimateurs plus robustes et applicables dans des situations plus générales. Nous exposerons très brièvement certains de ces développements dans la suite de l'article.

La deuxième évolution est d'essence plus conceptuelle, et, semble-t-il, particulière à nos domaines. Au lieu de continuer à rechercher des phénomènes "fractals" (c'est-à-dire invariants d'échelle) et à décrire cette invariance à l'aide de diverses dimensions, on s'est progressivement rendu compte du bénéfice qu'il pouvait y avoir à appliquer des outils fractals à des signaux a priori quelconques. Autrement dit, au lieu d'analyser un signal pour savoir s'il est un objet fractal, on lui fait subir des traiteinvariance prend la forme d'une auto-similarité, cela se traduit par une relation en loi de puissance entre la résolution d'analyse et la propriété P ( ) mesurée à cette résolution : P ( ) = F ( ) , où F ( ) est une fonction à variation lente. Cette invariance d'échelle est le plus souvent mise en évidence à travers un comportement linéaire dans un diagramme log(P ) vs. log( ). ments fractals indépendamment de sa possible invariance d'échelle. Le traitement des images fournit un exemple frappant de ce changement de point de vue : on ainsi affaire à de la compression fractale des images, et non pas à de la compression d'images fractales (les images incluses dans l'encyclopédie Encarta de Microsoft ne sont certes pas fractales, mais ont été stockées sur CD-Rom sous une forme compressée par une méthode fractale). Il en est de même pour la segmentation, le débruitage, ou encore le watermarking : on traite des images quelconques, et ce sont les méthodes qui sont fractales. Cette évolution importante surprendra moins si on la met en parallèle avec la manière dont on utilise des méthodes plus classiques ; en effet, elle consiste simplement à user de l'analyse fractale comme on le fait habituellement des autres outils mathématiques en sciences de l'ingénieur : moyennant certaines hypothèses, on peut toujours calculer le gradient d'un signal discret (par exemple via un modèle, ou en le régularisant au préalable), ou sa transformée de Fourier (par exemple en le prolongeant de manière adéquate en dehors du domaine où il est observé). De même, on calculera des dimensions ou un spectre multifractal associés à un signal en faisant des hypothèses sur celui-ci. Ces dernières sont d'ailleurs en général de nature semblable à celles faites dans les analyses "classiques", à savoir principalement : appartenance à une classe de modèles, et "régularisation" ou "prolongement" du signal (dans les échelles plutôt qu'en espace).

Nous développons ci-dessous quelques exemples de cette approche, qui a permis aux méthodes fractales de faire désormais partie intégrante de certains procédés industriels. Le reste de ce papier présente succintement trois développements théoriques relativement récents accompagnés chaque fois d'une ou deux applications : IFS et compression d'images ; analyse multifractale et traitement d'images ; processus stables fractionnaires, analyse financière et trafic sur les réseaux.

IFS et compression d'images

Un IFS, où système de fonctions itérées, est la donnée, sur un espace métrique complet (X; d) d'un ensemble de n fonctions fw 1 ; w 2 ; : : : w n g. Si chaque w i est contractant pour d, alors l'opérateur W :

H ! H A 7 ! i w i (A):
où H est l'ensemble des sous-ensembles compacts non vide de X, est lui-même contractant dans (H; Choisissons maintenant pour H l'ensemble des images sur un domaine fixé, et soit A une image particulière. Si l'on arrive à déterminer un IFS dont l'attracteur est A, alors, au lieu de conserver A en mémoire, il suffira de stocker l'IFS. On obtient ainsi une représentation fonctionnelle de l'image, qui est en général beaucoup plus compacte que l'information originale. Notons que cette méthode de compression est conceptuellement très différente des méthodes classiques, qui, elles, cherchent un espace de représentation permettant de supprimer ou de diminuer le plus possible les redondances.

La problématique de la compression fractale est donc, pour une image donnée A, de trouver un IFS dont l'attracteur soit le plus proche possible de A. L'algorithme de base consiste à partitionner d'abord A en blocs destination. Pour chacun ce ces blocs, on cherche ensuite, toujours dans A, un bloc "source", qui, par une transformation contractante simple (translation et rotation spatiale, changement d'échelle, modification du contraste et du niveau de gris moyen) donne une bonne approximation du bloc destination.

Quand tous les blocs destination ont été traités, on a obtenu un ensemble de fonc- tions contractantes qui constitue un IFS dit "partitionné" dont l'attracteur approxime A. On peut ainsi atteindre des taux de compression importants en conservant une bonne qualité d'image (figure 2). Cet algorithme, apparu il y a une dizaine d'années, a donné naissance à une très abondante littérature [START_REF] Fisher | Fractal Image Encoding and Analysis[END_REF], mais aussi à de nombreuses implémentations industrielles. La société américaine Image Tech, en particulier, commercialise plusieurs codeurs/décodeurs fractals fonctionnant sur ce principe pour des images fixes ou animées.

Des généralisations de cette théorie permettent entre autres de réaliser de la synthèse vocale, de faire de la génération interactive d'images ou du watermarking.

Analyse multifractale et applications en traitement d'images

L'analyse multifractale d'un signal consiste essentiellement à le décomposer en sous-ensembles ayant même régularité, puis à mesurer la "taille" des sous-ensembles ainsi obtenus. Plus précisément, on commence par se donner une définition adéquate de la régularité du signal X en un point quelconque t : le plus couramment, on a recours à l'exposant de Hölder ponctuel, X (t), défini comme suit :

X (t) = lim inf v!t log jX(v) X(t)j log jv tj : [1]
(cette définition est valable si X est non dérivable en t ; sinon il faut lui enlever sa partie régulière, [START_REF] Jaffard | Multifractal Formalism for Functions, I and II[END_REF] ; d'autre part, elle s'étend sans difficulté en dimension supérieure).

Géométriquement, (1) signifie que le graphe de X autour de t "ressemble" à une courbe du type v ! X(t) + Cjv tj , dans le sens suivant : pour tout > 0, il existe un voisinage de t tel que le graphe de X dans ce voisinage soit tout entier inclus dans l'enveloppe definie par les deux courbes v ! X(t) + Cjv tj et v ! X(t) Cjv tj , cette propriété n'étant plus vraie si on choisit < 0 (figure 3).

f(x 0 )

x 0 cjx x 0 j L'exposant X étant défini en tout t, on peut associer au signal original sa fonction de Hölder, t ! X (t), qui décrit comment varie la régularité de X : plus X (t) est petit, plus X est irrégulier en t, et inversement. L'information apportée par X et ses variations est souvent plus intéressante que celle fournie par X : si l'on veut détecter des contours dans une image, par exemple, la valeur X(t) des niveaux de gris n'est pas pertinente, puisque les contours ne sont pas modifiés si l'on change le contraste ou la luminosité globale de l'image. Par contre, les contours correspondent généralement à des discontinuités ou des variations brusques dans les niveaux de gris, information qui est justement celle enregistrée par X .

La deuxième étape d'une analyse multifractale consiste à mesurer les ensembles E = ft = X (t) = g. Ceci peut se faire de diverses manières, par exemple en privilégiant une approche géométrique ou au contraire une approche statistique. Nous ne pouvons développer ici ces aspects, et nous renvoyons à [START_REF] Véhel | Multifractal Analysis of Choquet Capacities: Preliminary Results[END_REF] pour les détails. Le résultat est dans tous les cas un spectre multifractal, i.e. une fonction ! f( ), qui décrit "combien" de points du signal ont une régularité égale à . Notons que ce spectre est défini sous des conditions très générales, et qu'on ne demande certainement aucune espèce de "fractalité" sur le signal X pour pouvoir le calculer. Ainsi, pour une image quelconque I, on pourra toujours estimer un spectre f I ( ). Voici quelques utilisations possibles de l'analyse multifractale en traitement des images. Intéressons-nous tout d'abord au cas de la détection de contours. Dans de nombreux cas, ceux-ci peuvent être caractérisés par les deux conditions suivantes : tout d'abord, et comme on l'a noté plus haut, les contours correspondent à des points peu réguliers dans les images, c'est-à-dire à des valeurs relativement faibles de . D'autre part, on s'attend à ce que tous les contours d'une image forment un ensemble de lignes, donc un ensemble de dimension 1. Ainsi, on pourra extraire les contours d'une image en sélectionnant les points t dont l'exposant est tel que f( ) = 1 (figure 4) [START_REF] Véhel | Introduction to the Multifractal Analysis of Images[END_REF].

Un deuxième exemple est le débruitage des images. Intuitivement, il est clair que, dans une scène qui apparaît très bruitée, comme par exemple une image SAR (pour Radar à Ouverture Synthétique), la plupart des points auront une régularité faible, alors qu'une image "lisse" contiendra surtout des valeurs élevées de . En terme de spectre, f( ) sera "grand" pour "petit" dans le premier cas, et pour "grand" dans le deuxième cas. Pour débruiter une image, une possibilité est donc de la modifier de telle sorte que son spectre soit translaté vers les grandes valeurs de : on augmente la régularité de chaque point en gardant la forme du spectre, ce qui permet de rendre l'image plus lisible tout en conservant la force respective de chaque singularité (c'està-dire qu'un point bruité sur un contour restera, après traitement, plus irrégulier qu'un point bruité sur une zone uniforme). Cette méthode permet en particulier de traiter efficacement certaines images SAR qui résistent à la plupart des autres techniques de restauration. Un exemple de débruitage est présenté figure 5.

Processus stables fractionnaires et applications en analyse financière

En simplifiant, on peut présenter les processus stables fractionnaires comme une généralisation du classique mouvement Brownien suivant deux directions. En premier lieu, on ne se restreint plus au cadre Gaussien en considérant des processus dont les lois marginales sont des lois stables. Rappelons que les lois stables partagent avec la loi Gaussienne la propriété de stabilité par addition : ce sont toutes les lois L telles que la somme S N convenablement renormalisée de N variables aléatoires, indépendantes et identiquement distribuées suivant L, soit elle aussi distribuée comme L. Un exemple en est la loi de Cauchy. Exception faite de la Gaussienne, chaque loi stable est principalement caractérisée par un paramètre 2 ]0; 2 qui est tel que tous les moments d'ordre existent pour > 0, mais les moments d'ordre supérieur ou égal à n'existent pas. En particulier, ces lois n'ont pas variance bien définie. En conséquence, si par exemple l'on construit un mouvement stable sur le modèle du mouvement Brownien en remplaçant l'aléa Gaussien par un aléa stable, on obtiendra un processus dont les trajectoires sont presque sûrement discontinues (figure 6). Ce même paramètre contrôle la dimension, qui, pour un mouvement stable, est max(1; 2 1= ).

La discontinuité des trajectoires, alliée à la propriété de stabilité, fait des mouvements stables de bons candidats pour modéliser certains phénomènes très irréguliers, dont en particulier les cours financiers. L'importance de la stabilité dans ce contexte est déjà notée par Bachelier (voir [START_REF] Mandelbrot | Fractals and scaling in finance discontinuity, concentration, risk[END_REF]) ; quand à la discontinuité, il suffit d'observer à peu près n'importe quelle chronique boursière pour se rendre compte que, même en l'absence de krach qui ferait chuter brusquement les cours, ceux-ci sont très souvent sujets à des sauts de toutes tailles : ce comportement est caractéristique des trajectoires des mouvements stables (figure 7). Plus quantitativement, de nombreux tests statistiques depuis les années 70 ont montré que certaines chroniques se prêtent effectivement bien à ce type de modélisation [START_REF] Mandelbrot | Fractals and scaling in finance discontinuity, concentration, risk[END_REF][START_REF] Fama | The Behavior of Stock Market Prices[END_REF]. Récemment, et grâce en particulier à des progrès théoriques, on a pu proposer de nouveaux outils d'ingénierie financière fondés sur ces modèles. Par exemple, si l'on admet que les cours n'ont effectivement pas de variance, le concept de risque, central en analyse financière, et qui est défini à partir de la variance, doit être complètement repensé : [START_REF] Belkacem | Generalized Market Equilibrium: "Stable" CAPM[END_REF] propose d'utiliser pour cela la covariation, et bâtit sur cette nouvelle notion un CAPM (Capital Asset Pricing Model) "stable" qui est plus pertinent que sa contrepartie gaussienne classique. D'autres raffinements proposés par exemple par la société suisse Olsen [24] conduisent à des outils maintenant largement utilisés par la communauté internationale.

La deuxième extension du mouvement Brownien qui mène à des processus fractals consiste à introduire des corrélations fortes dans les accroissements. Dans le cas le plus simple, on conserve la gaussianité et la stationnarité des accroissements, mais on abandonne le caractère Markovien du mouvement Brownien, pour définir le mouvement Brownien fractionnaire [START_REF] Mandelbrot | Fractional brownian motion, fractional noises and applications[END_REF]. Ce dernier est caractérisé par un exposant H 2 ]0; 1 qui gouverne la plupart de ses propriétés statistiques et fractales : quand H < 0:5, chaque accroissement est négativement corrélé avec tous les autres, alors que pour H > 0:5, la densité spectrale des accroissements tend vers l'infini à l'origine (le cas H = 0:5 est celui du mouvement Brownien standard) : cette seconde situation correspond à ce que l'on nomme communément la "mémoire longue", terme signifiant que les corrélations du processus décroissent "lentement", i.e. en loi de puissance, au lieu des décroissances exponentielles plus classiquement observées. Ce type de corrélation a été relevé dans de nombreux phénomènes naturels et a donné lieu à une abondante littérature [START_REF] Beran | Statistics for Long Memory Processes[END_REF]. En particulier, et pour revenir à l'application développée ci-dessus, de nombreux marchés financiers ont ce comportement, qui se manifeste dans les chroniques boursières sous la forme de "cycles" apparents mais n'ayant pas de durée caractéristique. Une modélisation plus réaliste des cours combine alors trajectoires discontinues et mémoire longue : on utilise pour cela des processus stables fractionnaires, dont les lois marginales sont stables et la structure de corrélation du même type que celle du mouvement Brownien fractionnaire. Nous ne décrirons pas plus avant ce type de processus et concluons ce paragraphe en citant une autre application et extension du mouvement Brownien fractionnaire.

Il s'agit de l'analyse de traces de trafic sur Internet. Au début des années 90, on s'est rendu compte que le trafic de données possède certaines caractéristiques qui le différentient fortement du trafic téléphonique : au contraire des traces relevées sur le réseau téléphonique, qui n'ont pas ou peu de mémoire et sont bien modélisées par des processus de Poisson, les traces Internet sont le siège de phénomènes de mémoire longue et ont un aspect invariant d'échelle. Des modèles à base de mouvement Brownien fractionnaire ont été proposés pour tenter de comprendre cette situation. Des calculs analytiques et des simulations numériques fondés sur ces modèles ont permis de rendre compte de certains des phénomènes observés par exemple sur le trafic Web, et, quelquefois, de proposer des protocoles pour améliorer les temps de transfert [START_REF] Crovella | Self-similarity in World Wide Web Traffic: evidence and possible causes[END_REF].

Comme mentionné plus haut, le paramètre H gouverne toutes les propriétés fractales du mouvement Brownien fractionnaire : en particulier, presque sûrement, l'exposant de Hölder en tout point d'une trajectoire est égal à H. Des mesures effectuées sur des données de trafic ont montré au contraire que l'exposant de Hölder varie fortement le long des traces réelles, entraînant en particulier des propriétés multifractales nontriviales [START_REF] Véhel | Fractional Brownian motion and data traffic modeling: The other end of the spectrum[END_REF]. Au moins deux possibilités apparaissent alors pour raffiner la modélisation du trafic. La première consiste à généraliser le mouvement Brownien fractionnaire de façon à ce que son exposant puisse évoluer au cours du temps, tout en conservant autant que possible ses autres propriétés, comme par exemple le caractère gaussien et les corrélations en lois de puissance. On définit ainsi le mouvement Brownien multifractionnaire, qui possède une plus grande souplesse et est capable de modéliser une vaste classe de phénomènes [START_REF] Ayache | The Generalized Multifractional Brownian Motion[END_REF][START_REF] Benassi | Gaussian Processes and Pseudodifferential Elliptic Operators[END_REF]. Il permet entre autres de rendre compte de la plupart des propriétés du trafic, et en particulier de son spectre multifractal. Il semble aussi être pertinent pour les applications en finance.

La deuxième modélisation possible du trafic qui est compatible avec les propriétés évoquées ci-dessus est fondée sur l'utilisation de cascades multiplicatives, qui sont le paradigme des processus multifractals (figure 8). Nous renvoyons le lecteur intéressé à [START_REF] Véhel | Fractional Brownian motion and data traffic modeling: The other end of the spectrum[END_REF] pour plus de détails sur cette approche.

Conclusion

La géométrie fractale est un outil commun à plusieurs domaines, et nous n'avons pas évoqué de nombreuses et récentes avancées importantes en mathématiques (diffusion sur des fractals [START_REF] Barlow | St Flour Lecture Notes: Diffusions on Fractals[END_REF], liens avec l'analyse en ondelettes [START_REF] Jaffard | Multifractal Formalism for Functions, I and II[END_REF]), physique théorique [START_REF] Duplantier | [END_REF], génie chimique [START_REF] Coppens | Accessibility of a Catalyst's Surface to Diffusing and Reacting Molecules[END_REF], . . . . Une mention particulière doit être faite aux progrès extrêmement significatifs accomplis en électrodynamique fratale [START_REF] Jaggard | Fractal Electrodynamics and Modeling[END_REF]. Cette discipline nouvelle s'intéresse aux interactions entre des ondes et des structures fractales comme des antennes, des réseaux ou certaines surfaces irrégulières (océan, . . . ). Entre autres résultats, ces études ont permis de mettre au point des antennes fractales multibandes. Un procédé de fabrication de telles antennes a d'ailleurs obtenu le grand prix 1998 des technologies de l'information [START_REF] Puente | On the behavior of the Sierpinski multiband antenna[END_REF].

Les développements ci-dessus montrent que l'analyse fractale fait maintenant partie des outils de base de l'ingénieur, et qu'elle a fourni, au delà des paysages artificiels de Star Trek, des méthodes utilisées couramment dans divers domaines industriels.

[28] K. Weierstrass, Mathematische Werke, Mayer et Muller, Berlin, 1895.

Figure 1 .

 1 Figure 1. Une "fougère fractale", attracteur d'un IFS. La forme complète est l'union des quatre sous-parties délimitées par un cadre dans l'image de droite, chacune de ces parties étant elle-même une réduction affine du tout. nous intéresse pour la compression, G est totalement déterminé dès que l'on connaît fw 1 ; : : : ; w n g, et il existe un algorithme rapide pour le calculer.

Figure 2 .

 2 Figure 2. Image originale et compression d'un facteur 50.

Figure 3 .

 3 Figure 3. Signal irrégulier X et son enveloppe Hölderienne en un point t 0 .

Figure 4 .

 4 Figure 4. Image originale et contours détectés par analyse multifractale.

Figure 5 .Figure 6 .

 56 Figure 5. Image SAR originale et débruitage multifractal.

Figure 7 .

 7 Figure 7. Indice CAC40 (prix quotidien entre le 9/7/87 et le 31/5/95), en haut, et modélisation par un mouvement stable avec = 1:7, en bas.

Figure 8 .

 8 Figure 8. Trafic TCP (en haut) et modélisation par cascade multiplicative (en bas).

à l'union de copies réduite de lui-même (figure1). De plus, et c'est la propriété qui


Jacques Lévy Véhel

Bertrand Guiheneuf
email: guiheneu@bora.inria.fr

TEXTURE BASED VIDEO INDEXING

Keywords: Multimedia, Video Indexing, Texture

We present a method for indexing and searching video sequences based on textural information. Our method proceeds by first defining and computing texture descriptors relevant to the database at hand. Then a similarity distance is computed between a video sample given by the user and small space-time regions in the sequences. The system returns an ordered set of best matches. We show some results on real sequences, which indicate that this scheme has reasonable complexity and performs well in practice. We believe that these good results stem mainly from a) the introduction of a new texture descriptor based on dynamic local Hölder exponents, and b) the automated adapted choice of the relevant parameters.

INTRODUCTION

Indexing and searching video sequences have become matters of paramount importance with the development of multimedia computing and the World Wide Web. While many methods have been proposed for indexing e.g. faces or simple manufactured objects, much less work has been devoted to highly complex structures such as ones present in textured regions of sequences [START_REF] Cullen | Document Image Database Retrieval and Browsing Using Texture Analysis[END_REF][START_REF] Randen | Image Content Search by Color and Texture Properties[END_REF][START_REF] Saber | Integration of Color, Shape, and Texture for Image Annotation and Retrieval[END_REF] 1 . A first explanation of this fact is that it is simply not as easy to formulate a request that deals with texture as it is for simple objects. Nevertheless, textures and specially moving textures are an essential part of the semantic content of images, and, in some cases, textural criteria are crucial for determining a given sequence. One could for instance be interested in scenes that contains rivers flowing in an rapid and chaotic way, or, on the contrary very quietly. The same type of requests could be made concerning clouds in the sky, or movement in the branches of a tree. A second reason is of course that indexing textures in an efficient way is a difficult problem, and that none of the various approaches give fully satisfactory results. Indeed, it is already a hard task to have a simple and general enough definition of a texture. Depending on the definition chosen, one then uses different geometric and/or statistical characterizations, which only capture partly the complexity of the real data. As a consequence, although most works on image indexing mention texture as a relevant information, very few systems actually use it in real applications.

Our aim in this work is to propose a method for indexing and searching video sequences based on requests that pertain to a dynamical textural information. Our approach displays the following features:

The indexing step makes use of a large number of texture descriptors (several hundreds) and selects the most pertinent ones for a given database through a learning strategy.

Request are made by examples, i.e. the user selects on a particular sequence a space-time region for which he is interested in finding a similar textural content.

Temporal information is explicitly taken into account for characterizing a texture.

We have implement our method in an algorithm, called Sumi, which proceeds in two steps. The first is off-line: Texture descriptors are computed on the database, and a relevant subset of these descriptors is stored in an index. This is described in details in the next section. In the second, online, step, when presented with a request from a user, Sumi computes a similarity distance between the given image and the elements of the database, and returns an ordered list of best matches. This part is explained in section 3. Finally, section 4 shows the results of some numerical experiments.

INDEXING STEP

To build an index which is both meaningful and of reasonable size for a given database, we proceed in two steps: first, a large number of texture descriptors are computed on each sequence. Then, using data analysis techniques, the most discriminating ones are selected and gathered to constitute the index. For both steps, we used the same strategy as in the texture analysis software called ARTHUR developed at Inria [START_REF] Mignot | ARTHUR : un Système d'Analyse de Textures[END_REF]. This software allows to classify and segment images on the basis of textural information, and has been used with success for automated recognition tasks on still images such as satellite images of the earth or MR medical images. We now proceed to describe precisely the indexing step.

Phase 1: Computation of the texture descriptors

Each sequence in the database is first cut into elementary space-time regions of fixed size, typically 32 32 10,

where the two first figures refer to a number of pixels and the last one to a number of frames (the sequences in the database are subsampled in time so that there are 10 frames per second). On each region, the following texture features are computed:

Statistical parameters. These are based on co-occurrence matrices [START_REF] Haralick | Statistical and Structural Approaches to texture[END_REF], from which 8 classical descriptors are extracted: energy, entropy and contrasts. Recall that the coefficient a i;j the co-occurrence matrix C T is the proportion of pairs of pixels (P 1 ; P 2 ) such that the grey level at P 1 is i, the grey level at P 2 is j, and the (2D + t) translation between P 1 and P 2 is T . descriptors are quite classical in texture analysis, and generally give good results for homogeneous textures such as grass, water or wool. We consider roughly 20 translations, which yield approximately 150 co-occurrence parameters. Another class of statistical parameters is based on the use of an autoregressive model for the texture in the 32 32 10 region. The three parameters of the AR model are used as texture descriptors.

For both classes, it was found that using the additional information brought by time increased very much the performances. Since a direct implementation in 2D+ t does however also increase greatly the computational burden, a specific fast algorithm was designed in this case.

Time-Space-Frequency parameters. We compute a Gabor decomposition of each region, i.e. a set of coefficients whose square describes the amount of energy in the image around a given location in time, space and frequency [START_REF]Gabor Analysis and Algorithms[END_REF]. In addition, the time-spacefrequency atoms used for the analysis have a preferred orientation, which allows to characterize anisotropic textures. Such parameters are useful to discriminate between textures which display varying structures at different resolution, or which are not homogeneous.

Examples include wood, fabrics with repetitive patterns or facades of buildings. We use 8 different frequencies bands and 8 orientations on each region. For each of the 64 filtered images thus derived from the original region, we compute the energy and entropy. This results in a total of 128 parameters.

Fractal parameters. Textures are by definition very irregular regions. It thus seems relevant to try to classify them according to some regularity indices. These indices must be local, so that they can capture the variation in space and time of irregularity. In that view, we have used local Hölder exponents [START_REF] Guiheneuf | Multifractal Image Denoising[END_REF]. For a still image, these are roughly defined for each 32 32 region by comparing the oscillation in the region (i.e. the total variation of the grey levels) with functions of the form ! . For a sequence, we compute a dynamic exponent (t) by centering a 3D window of size 32x32x6 around each frame. Such descriptors are specially relevant for discriminating e.g. water or clouds with slow or rapid movements, and scale invariant textures. We provide in the Appendix more details about the precise definition and computation of local Hölder exponents.

Color parameters.

Color is an important aid to discriminate between textures otherwise indistinguishable. An example is leaves texture on a tree at different periods of the year, e.g. spring and autumn. We use simply the mean, energy and entropy in each band R, G and B (HSV coding would also do), which yields a total of 9 parameters. The time dimension was not found to be important for color features, so that, contrarily to all parameters described above, the color characterization does not take into account the time varying nature of the searched textures.

The total number of parameters computed in this phase is of the order of 300. For a 10 seconds sequence of images at resolution 352 288 subsampled at 10 frames per second, the computational time is of the order of a few minutes on a PC. The total size for storing all the parameters is a little less than one third of the size of the original sequence.

Most of the time, many of the parameters are not very discriminating, and the information they provide is largely redundant. In order to build an efficient index, i.e. an index which is compact and contains parameters which are both discriminating and "independent", we use data analysis techniques described below.

Phase 2: Selection of the most discriminating descriptors

What is classically done in texture recognition is the following: one computes a series of parameters on a learning set, which contains several instances of each texture. The discriminating power of each parameter is then evaluated according to a procedure that takes into account the number of cases where a texture has been misclassified. In addition, the correlation to other parameters is measured. This allows to extract a set of robust and "independent" parameters that serve to classify new images.

Unfortunately, such an approach cannot be used in our case, since we do not know a priori which textures will be present in the database. Indeed, it would be a severe restriction to allow the user to search only for textures belonging to a predefined limited set. We have thus adopted a different strategy. What we need to do is obtain an index reasonable in size by discarding parameters which are not relevant. Two main factors render a descriptor useless: it may have poor discriminating power in the considered database and/or be very much correlated to another descriptor which has better discriminating capability. This leads naturally to the following criteria:

A parameter is considered good if it has high variability on the database. This ensures that the parameter holds at least some information allowing to discriminate regions.

A parameter is considered good if it has low correlation with the other ones.

The selection then proceeds by first ranking the descriptors by decreasing order of variance to obtain a list D 1 ; : : : ; D n . Then, the following operations are performed sequentially for j = 2; : : : ; n: a) compute the correlation of D j with all its predecessors, b) if the max of these correlations exceeds a given ratio r, remove D j from the list. The result is the index sought for. r is set such that the total size of the index is of the order of one tenth of the size of the database. Note that this strategy allows to adapt the size of the index to the complexity of the database. Also, it yields an automated adaptive scheme which allows a blind selection of the best parameters for any given database.

In most of the tests that were performed, it was found that the fractal parameters based on the behaviour of the dynamic local Hölder exponents were selected in priority, i.e. they were the ones with best discriminating power. This was in particular the case for sequences containing water, clouds, tree branches or grass, moving with different velocity. Time-space-frequency parameters usually came second, and were found particularly efficient for building facades. To our knowledge, this is the first time that (dynamic) local Hölder exponents are used for indexing. Our results thus show that this new technique is indeed relevant, as it improves on more classical ones in most cases.

SEARCHING STEP

The searching proceeds as follows. The user first chooses a space-time block in the database. More precisely, he selects a 32 32 region in a particular image and the system understands that the user is interested in the dynamical textural content of this region around this particular frame. Usually the time neighbourhood is of size 10, i.e. 5 frames are considered on each side of the selected one. This allows to discriminate between e.g. slowly and rapidly moving water. The parameters of the chosen space-time region are then retrieved, and compared to the parameters of all other regions in the database : Let D = (D 1 ; : : : ; D p ) be the vector of texture descriptors for the region selected by the user, and D k = (D k

EXPERIMENTAL RESULTS

We tested our method on a database composed of 40 video sequences of outdoor scenes. Strong textural information contained in these sequences include flowing water, moving clouds, facades of buildings, trees, grass, stones, . . . . Each sequence lasts approximately thirty seconds, the images being 352 288. In step 1/phase 1, all the parameters are computed. This took a little less that an hour. Phase 2 selects approximately 100 parameters, which constitute the index. Thus the additional amount of storage for the index is roughly one tenth of the size of the original database. Step 2 (the searching) is fast: each query is processed in around 0.1 second (all times are given for a computation on a PC).

We display in figure 1 an example of a query and the associated result. The top image is the one that serves to formulate the query by example. The image is split into regions of size 32 32, and the user selects a zone whose texture he is interested in, here a particular facade of a building. The image at the bottom shows the best match found in another sequence. This example show that Sumi is able to retrieve quite finely detailed textures.

As a second example, we show in figures 2 and 3 another reference image with selected texture, along with the four best matches found by Sumi. Again, we display only one image per matching sequence in order to have a meaningful illustration. Since the delicate color texture of the sky might not appear clearly on the printed paper, the interested reader might look at an electronic version on our site: http :// wwwrocq.inria.fr/fractales/.

These results show that Sumi indeed allows for robust and efficient video indexing based on textural information. Figure 3: Four best matches in different sequences.

APPENDIX : LOCAL H ÖLDER EXPONENTS

We describe in this section some basic facts about local Hölder exponents. The interested reader is refered to [START_REF] Guiheneuf | Multifractal Image Denoising[END_REF] for more details. For the sake of notationnal simplicity, we shall give the definitions in 1D. Extension to 3D is straightforward.

Hölder exponents are tools akin to evaluating the regularity of a function f : K ! IR where K is a bounded subset of IR. jf(x) P (x x 0 )j cjx x 0 j :

(1) When 2]0; 1 , this reduces to: jf(x) f(x 0 )j cjx x 0 j (2)
The pointwise Hölder exponent of f at x 0 , denoted (x 0 ), is the supremum of the for which (1) holds.

The pointwise Hölder function of f is defined as:

(x) = sup f : f 2 C x g :

This regularity characterization is widely used in fractal analysis because it has direct interpretations both mathematically and in applications. It has been shown for instance [START_REF] Daoudi | Construction of continuous functions with prescribed local regularity[END_REF] that f indeed corresponds to the auditive perception of smoothness for voice signals. Similarly, simply computing the Hölder exponent at each point of an image already gives a good idea of its structure, as for instance its edges or the roughness of its textures at any particular point. More generally, the pointwise Hölder exponent is useful in all applications where it is desirable to model, synthetize or process signals which are highly irregular, and for which the relevant information lies in the singularities more than in the amplitude : this is in particular exactly the case for the problem of indexing textures in video sequences. However, the pointwise Hölder characterization has also a number of drawbacks. A first one is that it is not stable under the action of (pseudo) differential operators. This precludes, for instance, the use of the Hilbert transform, commonly used in signal processing. In the same way, knowing the pointwise Hölder exponent of a function at a point x 0 is not sufficient to predict the Hölder exponent of its derivative at the same point. Second, this exponent is generally hard to compute numerically, in particular when the data at hand do not have a sufficiently high resolution, as is typically the case for video sequences.

An alternative solution is to consider the local Hölder exponent: Let 2]0; 1 , IR. One says that f 2 C l ( ) if:

9C : 8x; y 2 : jf(x) f(y)j jx yj

C

Then, let: l (f; x 0 ; ) = sup f : f 2 C l (B (x 0 ; ))g l (f; x 0 ; ) is non increasing as a function of .

We are now in position to give the definition of the local Hölder exponent :

Definition 2 Let f be a continuous function. The local Hölder exponent of f at x 0 is the real number: l (f; x 0 ) = lim !0 l (f; x 0 ; )

This exponent is stable under differentiation or integration. Moreover, and this is crucial for our application, it is easier to estimate than the pointwise Hölder exponent. In particular, it is possible to obtain reasonable estimates even for video sequences2 . Finally, in most cases, the local Hölder exponent corresponds just as much to the intuitive perception of regularity as the pointwise one does, so it is in general equally useful for our purpose of discriminating time-varying textures.

1 ;

 1 : : : ; D k p ) be the vector corresponding to the k th region in the database. For each k, we compute a distance D k = d(D ; D k ), where d is a given distance function. The program then returns the list of regions ordered by increasing magnitude of D k . We tested several distance functions. Best results seem to be obtained when one uses a simple weighted L 2 norm and the Kullback distance (weights are necessary because all the parameters do not have the same importance).

Figure 1 :

 1 Figure 1: Image on which the user has selected a region for search of similar textural information in the database (top).Image in another sequence in which there is a region whose textural content yields the best match to the request (bottom).

Figure 2 :

 2 Figure 2: Image containing the query.Figure3: Four best matches in different sequences.

  Pointwise Hölder exponent Let be a positive real number, 6 2 IN, and x 0 2 IR. A function f : IR ! IR is in C x0 if there exists a polynomial P of degree less than such that:

	There are basically two ways to define a mean-
	ingful Hölder exponent :
	Definition 1

By textured regions, we mean parts of the video sequences where information lies e.g. in water, the sky, trees or more generally natural landscapes, but also complicated manufactured objects such as facades of some buildings, fabrics, etc...

There is a profound mathematical reason why the local Hölder exponent is easier to estimate. This is however a bit technical, and we refer the reader to[START_REF] Guiheneuf | Multifractal Image Denoising[END_REF] for a precise statement.

Acknowledgements

This work was supported by the french CNET under grant #96ME28


Jörg Hoffmann
email: joerg.hoffmann@inria.fr

Where Ignoring Delete Lists Works, Part II: Causal Graphs

Keywords: Logistics [0, 1] Ferry [0, 1] Satellite [4, 4] Tyreworld [0, 6] Dining-Phil. [31, 31] Grid [0] Optical ] Blocksworld-NoArm [0] Transport [0] Blocksworld-Arm Depots Driverlog

, it was observed that the optimal relaxation heuristic h + has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to earlier disappointing results (Hoffmann 2005) -the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains -we herein answer this question in the affirmative. We establish connections between causal graph structure and h + topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of local minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish "easy" domains from "hard" ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.

Introduction

The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning (e.g., [START_REF] Bonet | Using component abstraction for automatic generation of macro-actions[END_REF][START_REF] Hoffmann | The FF planning system: Fast plan generation through heuristic search[END_REF][START_REF] Richter | Landmarks revisited[END_REF][START_REF] Helmert | Landmarks, critical paths and abstractions: What's the difference anyway? ICAPS[END_REF]. The planners based on it approximate, in a variety of ways, the optimal relaxation heuristic h + which itself is NP-hard to compute. As earlier observed [START_REF] Hoffmann | Where 'ignoring delete lists' works: Local search topology in planning benchmarks[END_REF], h + has some rather amazing qualities in many classical planning benchmarks. Figure 1 gives an overview of these results. 1 The results divide domains into classes along two dimensions. We will herein ignore the horizontal dimension, which pertains to dead ends (easy-to-test powerful Figure 1: Overview of h + topology [START_REF] Hoffmann | Where 'ignoring delete lists' works: Local search topology in planning benchmarks[END_REF]. criteria implying that a task is "undirected"/"harmless" are known). The vertical dimension divides the domains into three classes, with respect to the behavior of exit distance, defined as d-1 where d is the distance to a state with strictly smaller h + value. In the "easiest" bottom class, there exist constant upper bounds on exit distance from both, states on local minima and states on benches (flat regions). In the figure, the bounds are given in square brackets. For example, in Logistics, the bound for local minima is 0 -meaning that no local minima exist at all -and the bound for benches is 1. In the middle class, a bound exists only for local minima; that bound is 0 (no local minima at all) for all domains shown. In the "hardest" top class, both local minima and benches may take arbitrarily many steps to escape.

The proofs underlying Figure 1 are hand-made. For dealing with unseen domains, the question arises whether one can design domain analysis methods leading such proofs automatically. The potential uses of such analysis methods are manifold; we discuss this at the end of the paper. For now, note that addressing this question is quite a formidable challenge -at least if we are willing to take as an indication that (the decision problem is hard and) research trying to address it [START_REF] Hoffmann | Where 'ignoring delete lists' works: Local search topology in planning benchmarks[END_REF]) managed only to design an analysis whose runtime explodes quickly with task size, and that succeeds only in Movie and Simple-TSP -arguably the two most simplistic benchmarks in existence. 2By contrast, the TorchLight tool developed herein has low-order polynomial runtime and usually terminates in split seconds. Distinguishing between global (per task) and lo-cal (per state) analysis, it proves the global absence of local minima in Movie, Simple-TSP, Logistics, and Miconic-STRIPS. It gives a strong guarantee for local analysis in Ferry, Gripper, Elevators, and Transport. Empirically its local analysis exhibits strong performance also in Zenotravel, Satellite, Tyreworld, Grid, Driverlog, and Rovers. In this way, TorchLight can distinguish domains with "easy" h + topology from "hard" ones, even based on analyzing only a single state per instance. By summarizing structural reasons for analysis failure, TorchLight also gives diagnostic output indicating problematic aspects of the domain, i.e., aspects that may cause local minima under h + .

What is the key to this performance boost? Consider Logistics and Blocksworld-Arm. At the level of their PDDL domain descriptions, the difference is not evident -both have delete effects, so why do those in Blocksworld-Arm "hurt" and those in Logistics don't? What does the trick is to move to the finite-domain variable representation (e.g., [START_REF] Helmert | The fast downward planning system[END_REF]) and to consider the associated structures, notably the causal graph capturing the precondition and effect dependencies between variables. The causal graph of Blocksworld-Arm contains cycles. That of Logistics does not. Looking into this, it was surprisingly easy to derive the following basic result: If the causal graph is acyclic, and every variable transition is invertible, then there are no local minima under h + . This result is certainly interesting in that, for the first time, it establishes a connection between causal graph structure and h + topology. However, by itself the result is much too weak for domain analysis -of the considered benchmarks, it applies only in Logistics. We devise generalizations and approximations yielding the analysis results described above. Aside from their significance for domain analysis, these techniques are also interesting with respect to research on causal graphs. Whereas traditional methods (e.g., [START_REF] Jonsson | Incremental planning[END_REF][START_REF] Brafman | Structure and complexity in planning with unary operators[END_REF] seek execution paths solving the overall task, here we seek "only" execution paths decreasing the value of h + . In local analysis, this enables us to consider small fragments of the causal graph, creating the potential to successfully analyze states in tasks whose causal graphs are otherwise arbitrarily complex.

We next give some background, then describe an illustrative example before delving into the technicalities. After pointing out some domain-specific performance guarantees, we report on a large-scale experiment with TorchLight. We close by discussing related and future work. We omit many details, and only outline the proofs. Full details are available in the journal version of the paper [START_REF] Hoffmann | Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h +[END_REF].

Background

We adopt the terminology and notation of [START_REF] Helmert | The fast downward planning system[END_REF], with a number of modifications suiting our purposes. A (finite-domain variable) planning task is a 4-tuple (X, s I , s G , O). X is a finite set of variables, where each x ∈ X is associated with a finite domain D x . A partial state over X is a function s on a subset X s of X, so that s

(x) ∈ D x for all x ∈ X s ; s is a state if X s = X. The ini- tial state s I is a state. The goal s G is a partial state. O is a finite set of operators. Each o ∈ O is a pair o = (pre o , eff o )
of partial states, called its precondition and effect. The semantics of planning tasks are defined as usual, based on allowing to transition from s to s ′ via o if pre o ⊆ s, eff o ⊆ s ′ , and s(x) = s ′ (x) for all x ∈ X \ X effo . We denote the state space with S. We identify partial states with sets of variable-value pairs, which we will often refer to as facts.

We next define the two basic structures in our analysis: domain transition graphs and causal graphs. For the former, we diverge from Helmert's definition only in introducing additional notations for responsible operators and "side effects". In detail, let x ∈ X. The domain transition graph DT G x of x is the labeled directed graph with vertex set D x and the following arcs.

) := eff o \ {(x, c ′ )}. For each o ∈ O where x ∈ X effo \ X pre o with c ′ := eff o (x), for every c ∈ D x with c = c ′ , DT G x contains an arc (c, c ′ ) labeled with rop(c, c ′ ) := o, cond(c, c ′ ) := pre o , and seff(c, c ′ ) := eff o \ {(x, c ′ )}.
The reader familiar with causal graphs may have wondered why we introduced a notion of side effects, seeing as causal graphs can be acyclic only if all operators are unary (affect only a single variable). The reason is that we do handle cases where operators are non-unary. The variant of causal graphs we use can still be acyclic in such cases, and indeed this happens in some of our benchmark domains. We define the support graph SG to be the directed graph with vertex set X, and with an arc (x, y) iff DT G y has a relevant transition (c, c ′ ) so that x ∈ X cond(c,c ′ ) . Here, a transition (c, c ′ ) on variable x is called relevant iff (x, c ′ ) ∈ s G ∪ o∈O pre o .

Our definition modifies the most commonly used one in that it uses relevant transitions only, and that it does not introduce arcs between variables co-occurring in the same operator effect. Transitions with side effects are handled separately in our analysis. Note that irrelevant transitions occur naturally, in domains with non-unary operators. For example, unstacking a block induces the irrelevant transition making the arm non-empty, and departing a passenger in Miconic-STRIPS makes the passenger "not-boarded".

We now introduce the relevant notations pertaining to h + and its topology. Let s ∈ S be a state. A relaxed plan for s is an operator sequence achieving s G when allowing to transition from fact set s to fact set s ′ via o if pre o ⊆ s and s ′ = s ∪ eff o . h + (s) is the length of an optimal (shortest) relaxed plan for s, or h + (s) = ∞ if no relaxed plan exists. Say that 0 < h + (s) < ∞. Then an exit is a state s ′ reachable from s so that h + (s ′ ) = h + (s) and there exists a neighbor s ′′ of s ′ so that h + (s ′′ ) < h + (s ′ ). The exit distance ed(s) of s is the length of a shortest path to an exit, or ed(s) = ∞ if no exit exists. A path in S is called monotone iff there exist no two consecutive states s 1 and s 2 on it so that h + (s 1 ) < h + (s 2 ). We say that s is a local minimum if there exists no monotone path to an exit.

The topology definitions, adapted from [START_REF] Hoffmann | Where 'ignoring delete lists' works: Local search topology in planning benchmarks[END_REF], should be self-explanatory. (They are specific to h + only because we will not consider any other heuristics.) Regarding h + , [START_REF] Helmert | The fast downward planning system[END_REF] first described the presented adaptation to finite-domain variables. To understand the definition, just note that "ignoring deletes" essentially means to act as if "what was true once will remain true forever". This is exactly what we do to the finite-domain variables here. Domain analysis has a long tradition in planning (e.g., [START_REF] Fox | The automatic inference of state invariants in TIM[END_REF][START_REF] Gerevini | Inferring state-constraints for domain independent planning[END_REF][START_REF] Edelkamp | Exhibiting knowledge in planning problems to minimize state encoding length[END_REF][START_REF] Rintanen | An iterative algorithm for synthesizing invariants[END_REF]. However, there exists no prior work at all trying to automatically infer topological properties of a heuristic function -the single exception being the aforementioned disappointing results [START_REF] Hoffmann | Where 'ignoring delete lists' works: Local search topology in planning benchmarks[END_REF]). 3 It is worth noting that such analysis is computationally hard: Theorem 1 It is PSPACE-complete to decide whether or not the state space of a given planning task contains a local minimum, and given an integer K it is PSPACE-complete to decide whether or not for all states s we have ed(s) ≤ K. Further, it is PSPACE-complete to decide whether or not a given state s is a local minimum, and given an integer K it is PSPACE-complete to decide whether or not ed(s) ≤ K.

These results are hardly surprising, but have not been stated anywhere yet. The hardness results still hold when restricting the input to solvable tasks/states. Their proofs reduce plan existence, the trick being to flatten h + using a new operator that can always achieve the goal but that has a fatal side effect, and giving the planner a choice whether to solve this modified task or a custom-designed alternative one. In practice, computational hardness here is particularly challenging because, in most applications of domain analysis, we are not willing to run a worst-case exponential search. After all, the analysis will not actually solve the problem.

The reader will have noticed the state-specific analysis problems in Theorem 1. We distinguish between global analysis per-task, and local analysis per-state. Domain analysis traditionally considers only the global variant (or even more generalizing variants looking at only the PDDL domain file). While global once-and-for-all analysis is also the "holy grail" in the present work, local analysis has its advantages. It applies in any domain, including those that do contain local minima, or that don't but where global analysis is not strong enough to recognize this. Indeed, we will see that local analysis, based on very limited sampling, can be used to produce accurate information about a domain.

An Illustrative Example

The basic connection we identify between causal graphs and h + topology is quite simple. It is instructive to understand this first, before delving into the full results. Figure 2 shows fragments of the domain transition graphs (DTGs) of three variables x 0 , x 1 , and x 2 . All DTG transitions here are assumed to be invertible, and to have no side effects.

T 1 X 0 X 1 X 2 g 0 R1 R2 R3 L2 L1 L3 t 0 T 2 c c s s 1 1 2 2
Figure 2: An example illustrating our basic result.

The imaginative reader is invited to think of x 0 as a car whose battery is currently empty and that therefore requires the help of two people, x 1 and x 2 , in order to push-start it. The people may, to solve different parts of the task, be required for other purposes too, but here we consider only the sub-problem of achieving the goal x 0 = g 0 . We wish to take the x 0 transition t 0 , which has the two conditions c 1 and c 2 These conditions are currently not fulfilled. In the state s at hand, x 1 is in s 1 and x 2 is in s 2 . We must move to a different state, s 0 , in which x 1 = c 1 and x 2 = c 2 . What will happen to h + along the way?

Say that an optimal relaxed plan P + (s) for s moves x 1 to c 1 along the path marked T 1 , and moves x 2 to c 2 along the path marked T 2 -clearly, some such paths will have to be taken by any P + (s). Key observation 1 is similar to a known from transportation benchmarks. When moving x 1 and x 2 , whichever state s ′ we are in, as long as s ′ remains within the boundaries of the values traversed by T 1 and T 2 , we can construct a relaxed plan

P + (s ′ ) for s ′ so that |P + (s ′ )| ≤ |P + (s)|.
Namely, to obtain P + (s ′ ), we simply replace the respective move sequence -→ o i in P + (s), for i = 1, 2, with its inverse ←o i . For example, say we got to s ′ by -→ o 1 = R1, R2, R3 moving x 1 to c 1 , as indicated in Figure 2. Then wlog P + (s) has the form R1, R2, R3 • P . We define P + (s ′ ) := L3, L2, L1 • P . The postfix P of both relaxed plans is the same; at the end of the prefix, the set of values achieved for x 1 , namely s 1 , c 1 , and the two values in between, is also the same. Thus P + (s ′ ) is a relaxed plan for s ′ . This is true in general, i.e., ←o 1 is necessarily applicable in s ′ , and will achieve, within relaxed execution of P + (s ′ ), the same set of facts as achieved by -→ o 1 in P + (s). Thus h + (s ′ ) ≤ h + (s) for any state s ′ , including the state s 0 we're after. Key observation 2: if x 0 moves only for its own sake, i.e., the car position is not important for any other goal, then h + will decrease by 1 after executing t 0 in s 0 . Thus s 0 is an exit. With observation 1, the path to s 0 is monotone, hence s is not a local minimum, and its exit distance is bounded by the number of moves on the path.

It is not difficult to imagine that the above works also if preconditions need to be established recursively, as long as no cyclic dependencies exist. A third person may be needed to first persuade x 1 and x 2 , the third person may need to take a bus, and so on. Now, say that the support graph is acyclic, and that all transitions are invertible and have no side effects. Given any state s, unless s is already a goal state, some variable x 0 moving only for its own sake necessarily exists. But then, within any optimal relaxed plan for s, a situation as above exists, and therefore we have a monotone exit path, Q.E.D. for no local minima under h + .

The execution path construction we have just discussed is not so different from known results exploiting causal graph acyclicity and notions of connectedness or invertibility of domain transition graphs, e.g., [START_REF] Jonsson | Incremental planning[END_REF]. What is new here is the connection to h + .

The technical results in what follows are structured in a way similar to the above: (A) we identify circumstances under which we can deduce from an optimal relaxed plan that a monotone exit path exists. (B) we devise support-graph based sufficient criteria implying that analysis (A) will always succeed. (B) underlies TorchLight's global analysis. By feeding (A) with the usual relaxed plans as computed, e.g., by FF's heuristic function, we obtain TorchLight's main instrument for (approximate) local analysis. Thus we do not provide only a minimal version of (A) that would suffice to prove (B). We identify special cases much richer than what we can actually infer from support graphs (as yet).

Analyzing Optimal Relaxed Plans

We consider a state s and an optimal relaxed plan P + (s) for s. To describe the circumstances under which a monotone exit path is guaranteed to exist, we will need a number of notations pertaining to properties of transitions etc. We will introduce these notations along the way, rather than up front, in the hope that this makes them easier to digest.

Given o 0 ∈ + (s), by P + <0 (s) and P + >0 (s) we denote the parts of P + (s) in front of o 0 and behind o 0 , respectively. By P + (s, x) we denote the sub-sequence of P + (s) affecting x. We capture the dependencies between the variables used in P + (s) for achieving the precondition of o 0 , as follows:

Definition 1 Let (X, s I , s G , O) be a planning task, let s ∈ S with 0 < h + (s) < ∞, let P + (s) be an optimal relaxed plan for s, let x 0 ∈ X, and let o 0 ∈ P + (s) be an operator taking a relevant transition of the form t 0 = (s(x 0 ), c).

An optimal rplan dependency graph is a graph oDG + = (V, A) with unique leaf vertex x 0 , and where x ∈ V and (x, x ′ ) ∈ A if either: x ′ = x 0 , x ∈ X pre o 0 , and pre o0 (x) = s(x); or x = x ′ ∈ V \ {x 0 } and there exists o ∈ P + <0 (s) taking a relevant transition on x ′ so that x ∈ X pre o and pre o (x) = s(x).

For x ∈ V \ {x 0 }, by oDT G + x we denote the sub-graph of DT G x that includes only the values true at some point in P + <0 (s, x), the relevant transitions t using an operator in P + <0 (s, x), and at least one inverse of such t where an inverse exists. We refer to the inverse transitions as induced.

The transition t 0 with responsible operator o 0 will be our candidate for reaching the exit state, like t 0 in Figure 2. oDG + collects all variables x connected to a variable x ′ insofar as P + <0 (s) uses an operator preconditioned on x in order to move x ′ . These are the variables we will need to move, like x 1 and x 2 in Figure 2, to obtain a state s 0 where t 0 can be taken. For any such variable x, oDT G +

x captures the domain transition graph fragment that P + <0 (s) traverses and within which we will stay, like T 1 and T 2 in Figure 2.

Note that there is no need to consider the operators P + >0 (s) behind o 0 , simply because these operators are not used in order to establish o 0 's precondition. This is of paramount importance in practice. For example, if o 0 picks up a ball b in Gripper, then P + (s) will also contain -behind o 0 -an operator o ′ dropping b. If we considered o ′ in Definition 1, then oDG + would contain a cycle because the definition would assume that o ′ is used for making the respective gripper hand free. In TorchLight's approximate local analysis, whenever we consider an operator o 0 , before we build oDG + we re-order P + (s) by moving operators behind o 0 if possible. This minimizes P + <0 (s), and oDG + thus indeed contains only the necessary variables and arcs.

Under which circumstances will t 0 actually "do the job"? The sufficient criterion we identify is rather complex. To provide an overview of the criterion, we next state its definition. The items in this definition will be explained below. Definition 2 Let (X, s I , s G , O), s, P + (s), x 0 , o 0 , t 0 , and oDG + = (V, A) be as in Definition 1. We say that oDG + is successful if all of the following holds:

(1) oDG + is acyclic.

(2) We have that either:

(a) the oDG + -relevant deletes of t 0 are P + >0 (s)recoverable; or (b) s(x 0 ) is not oDG + -relevant, and t 0 has replacable side effect deletes; or (c) s(x 0 ) is not oDG + -relevant, and t 0 has recoverable side effect deletes. (3) For x ∈ V \ {x 0 }, all oDT G +

x transitions either have self-irrelevant deletes, or are invertible/induced and have irrelevant side effect deletes and no side effects on V \ {x 0 }. The most basic prerequisite, (1), is that oDG + is acyclic. If there are cycles, then moving a variable may involve moving itself in the first place, which of course kills our exit path construction. For the oDT G +

x transitions, we are fine if, as in the example, all transitions are invertible and have no side effects. However, we can easily generalize this condition, to the present condition (3). We need some notations. Let t = (c, c ′ ) be a transition on variable x. The context of t is the set ctx(t) of all facts that may be deleted by side effects of t. That is, for each (y, d) ∈ seff(t), (y, cond(t)(y)) ∈ ctx(t) if a condition on y is defined; else all D y values = d are inserted. We say that:

• t is invertible iff there exists a transition (c ′ , c) in DT G x so that cond(c ′ , c) ⊆ cond(c, c ′ ). • t has irrelevant side effect deletes iff ctx(t) ∩ (s G ∪ o∈O pre o ) = ∅, and self-irrelevant side effect deletes iff ctx(t) ∩ (s G ∪ rop(t) =o∈O pre o ) = ∅. • t has self-irrelevant deletes iff it has self-irrelevant side effect deletes and (x, c) ∈ s G ∪ rop(t) =o∈O pre o .
A transition is invertible if we can "go back" without introducing any new conditions (e.g. Logistics). Examples of irrelevant side effect deletes are transitions with no side effects at all, or a move in Simple-TSP, whose side effect deletes the target location's being "not-visited". Examples of self-irrelevant deletes are inflating a spare wheel in Tyreworld (the wheel is no longer "not-inflated"), or departing a passenger in Miconic-STRIPS, whose own effect deletes "not-served(passenger)" and whose side effect delete "boarded(passenger)" is used only by this operator itself.

How do these notions affect our exit path construction? Recall that we are trying to traverse states s ′ within the value ranges for x ∈ V \ {x 0 } defined by oDT G +

x , to reach a state s 0 where we can apply t 0 . Along the way, we construct relaxed plans P + (s ′ ) with |P + (s ′ )| ≤ |P + (s)| by inverting transitions of P + <0 (s). If all oDT G + x transitions t we may be using have irrelevant side effect deletes, then, as far as not disvalidating any facts needed elsewhere is concerned, this is just as good as having no side effects at all. 4 Regarding the own delete of t, this poses no problem here if t is invertible. If it is not but all deletes of t are irrelevant except maybe for the responsible operator itself, then to obtain P + (s ′ ) we can simply remove rop(t) from P + (s). Thus |P + (s ′ )| < |P + (s)| so we have reached an exit and can stop.

Consider now our endpoint transition t 0 and its responsible operator o 0 . We previously demanded that x 0 "moves for its own sake", i.e., that x 0 has a goal value and is not important for achieving any other goal. This is unnecessarily restrictive. For example, in Driverlog, a driver may have its own goal and be needed to drive vehicles, and still t 0 moving the driver results in decreased h + if the location moved away from is not actually needed anymore. All we really want is that "any deletes of t 0 are not needed in the rest of the relaxed plan". We can then remove o 0 from the relaxed plan, and have reached an exit as desired.

Recall the situation we are addressing. We have reached a state s 0 in which t 0 = (s(x 0 ), c) can be applied, yielding a state s 1 . We have a relaxed plan P + (s 0 ) for s 0 so that |P + (s 0 )| ≤ |P + (s)|, where P + (s 0 ) is constructed from P + (s) by replacing some operators of P + <0 (s) with operators responsible for induced oDT G +

x transitions for x ∈ V \ {x 0 }. We construct P + 1 by removing o 0 from P + (s 0 ), and we need P + 1 to be a relaxed plan for s 1 . What are the facts possibly needed in P + 1 ? A safe approximation is the union of s G , the precondition of any o 0 = o ∈ P + (s), and any oDT G +

x values needed by induced oDT G + x transitions. Denote that set with R + 1 . The values potentially deleted by t 0 are contained in C 0 := {(x 0 , s(x 0 ))}∪ctx(t 0 ). Thus if R + 1 ∩ C 0 = ∅ then we are fine. We can sharpen this further. Consider the set of facts F 0 that are true after relaxed execution of P + <0 (s). If p ∈ F 0 , then p is not needed in the part of P + 1 pertaining to P + <0 (s); if it is needed in the part pertaining to P + >0 (s), behind o 0 , then it is established by some operator o ′ ∈ P + >0 (s). Since o ′ will still be in P + 1 , it thus suffices if R + 1 ∩C 0 ∩F 0 = ∅. Now, even this last condition can still be sharpened. Say that there exists a (possibly empty) sub-sequence -→ o 0 of P + >0 (s) so that -→ o 0 is applicable at the start of P + 1 , and -→ o 0 re-achieves all facts in R + 1 ∩ C 0 ∩ F 0 (both are easy to define and test). Then moving -→ o 0 to the start of P + 1 does the job. We say in this case that the oDG +relevant deletes of t 0 are P + >0 (s)-recoverable. For example, say o 0 picks up ball b in Gripper. Then P + >0 (s) contains a sub-sequence -→ o 0 moving to another room and dropping b. This re-achieves R + 1 ∩ C 0 ∩ F 0 = "free-gripper".

Definition 2 (2b) and (2c) identify two alternative sufficient conditions under which t 0 is suitable. Both require that s(x 0 ) is not contained in R + 1 . We say in this case that s(x 0 ) is not oDG + -relevant. Then, R + 1 ∩ C 0 = ∅ unless t 0 has side effects. Replacable side effect deletes means, in a nutshell, that any endangered operator can always be replaced with an equivalent one (this happens, e.g., in Simple-TSP). Recoverable side effect deletes means that there exists an operator o ′ that will be applicable and recovers all relevant side effect deletes (e.g., in Rovers taking a rock/soil sample fills a "store", but we can easily empty the store again). Reaching an exit then takes one more step, applying o ′ after o 0 .

What will the length of the exit path be? We have one move for x 0 . Each non-leaf variable x must provide a new value at most once for every move of a variable x ′ depending on it, i.e., where (x, x ′ ) ∈ A. The new value can be reached by a oDT G +

x traversal. Denote the maximum length of such a traversal by d(oDT G +

x ). Now, we may have d(oDT

G + x ) > d(DT G x ) because oDT G +
x removes not only vertices but also arcs: there may be "short-cuts" not traversed by P + (s). Under certain circumstances it is safe to take these short-cuts. Say that (*) all oDT G +

x transitions are invertible or induced, and all other transitions are either irrelevant, or have empty conditions and irrelevant side effect deletes. While traversing a short-cut, it may happen that h + increases. But when we reach the end of the short-cut, we are back in the region of states s ′ where a relaxed plan P + (s ′ ) can be constructed as above. Denote by V * the subset of V \ {x 0 } for which (*) holds. We define

cost d * (oDG + ) := x∈V cost d * (x), where cost d * (x) :=        1 x = x 0 d(oDT G + x ) * x ′ :(x,x ′ )∈A cost d * (x ′ ) x = x 0 , x ∈ V * min(d(oDT G + x ), d(DT G x )) * x = x 0 , x ∈ V *
x ′ :(x,x ′ )∈A cost d * (x ′ ) For Definition 2 (2a,b), the exit distance is cost d * (oDG + )-1 because we count the step reducing h + . Thus: Theorem 2 Let (X, s I , s G , O), s, P + (s), and oDG + be as in Definition 1. If oDG + is successful, then s is not a local minimum, and ed(s) ≤ cost d * (oDG + ). If we have Definition 2 (2a) or (2b), then ed(s) ≤ cost d * (oDG + ) -1.

Theorem 2 does not hold if P + (s) is not optimal, even if P + (s) is non-redundant and parallel-optimal: at the end of the "exit path" we may obtain a relaxed plan shorter than P + (s) but not shorter than h + (s). My example proving this is fairly contrived, though, and it seems unlikely that situations like this will occur in practice.

Note that cost d * (.) is exponential in the depth of the graph. This is not an artifact of the length estimation. It is easy to construct examples where exit distance is exponential in that parameter.

Conservative Approximations

We now identify sufficient criteria guaranteeing that Theorem 2 can be applied. We consider both the local case where a particular state is given, and the global case where we generalize over all states in the task. We approximate optimal rplan dependency graphs as follows:

Definition 3 Let (X, s I , s G , O) be a planning task, let s ∈ S with 0 < h + (s) < ∞, let x 0 ∈ X sG , and let t 0 = (s(x 0 ), c) be a relevant transition in DT G x0 with o 0 := rop(t 0 ).

A local dependency graph is a graph lDG = (V, A) with unique leaf vertex x 0 , and where x ∈ V and (x, x ′ ) ∈ A if either: x ′ = x 0 , x ∈ X pre o 0 , and pre o0 (x) = s(x); or x ′ ∈ V \ {x 0 } and (x, x ′ ) is an arc in SG.

A global dependency graph is a graph gDG = (V, A) with unique leaf vertex x 0 , and where x ∈ V and (x, x ′ ) ∈ A if either: x ′ = x 0 and x 0 = x ∈ X pre o 0 ; or x ′ ∈ V \{x 0 } and (x, x ′ ) is an arc in SG.

If an optimal relaxed plan P + (s) for s contains o 0 , then oDG + as per Definition 1 will be a sub-graph of lDG and gDG as defined here. This is simply because any optimal rplan dependency graph has only arcs (x, x ′ ) contained in the support graph of the task.5 I remark that the support graph may contain a lot more arcs than actually necessary. Consider the earlier point that, when constructing oDG + , it is important to consider only operators in front of o 0 in P + (s). This information is of course not contained in SG.

In Gripper, to stick with our previous example, SG will suggest that dropping a ball may be needed in order to support "free-gripper" for picking up the same ball. Thus SG "detects" a cyclic dependency here. One of the main open directions is to improve this part of the approximation, by devising conservative methods recognizing operators that will never have to precede o 0 in an optimal relaxed plan.

Defining when an lDG respectively gDG is successful does not involve any new notation: Definition 4 Let (X, s I , s G , O), s, x 0 , t 0 , o 0 , and G = lDG or G = gDG be as in Definition 3. We say that G = (V, A) is successful if all of the following hold:

(1) G is acyclic.

(2) If G = lDG then s G (x 0 ) = s(x 0 ), and there exists no transitive successor x ′ of x 0 in SG so that x ′ ∈ X sG and s G (x ′ ) = s(x ′ ).

(3) We have that t 0 either:

(a) has self-irrelevant side effect deletes; or (b) has replacable side effect deletes; or (c) has recoverable side effect deletes. (4) For x ∈ V \ {x 0 }, all DT G x transitions either are irrelevant, or have self-irrelevant deletes, or are invertible and have irrelevant side effect deletes and no side effects on V \ {x 0 }.

Consider first only local dependency graphs G = lDG; we will discuss G = gDG below. Assume that we have an optimal relaxed plan P + (s) for s that contains o 0 , and thus oDG + is a sub-graph of lDG. Then condition (1) obviously implies Definition 2 (1). Condition (4) implies Definition 2 (3) because oDT G +

x does not contain any irrelevant transitions. Condition (2) implies that s(x 0 ) is not oDG +relevant, i.e., s(x 0 ) is not needed in the rest of the relaxed plan. This is simply because no other un-achieved goal depends on x 0 . But then, condition (3a) implies Definition 2 (2a) because R + 1 ∩ C 0 = ∅, in the notation introduced previously. Conditions (3b) and Definition 2 (2b), respectively (3c) and Definition 2 (2c), are equivalent under this premise.

Regarding exit distance, we do not know which part of x ∈ V \ {x 0 } will be traversed by P + (s). An obvious bound on d(oDT G +

x ) is the length mD(DT G x ) of a longest non-redundant path through the graph (a path visiting each vertex at most once). Unfortunately, we cannot compute mD(.) efficiently: there exists a Hamiltonian path in a graph G = (V, A) iff mD(G) = |V | -1. Torch-Light over-approximates mD(G) simply by |V | -1. On a more positive note, we can sometimes use d(DT G x ) instead of mD(DT G x ), namely if we are certain that x is one of the variables V * used in the definition of cost d * (oDG + ). This can be ensured by postulating that all DT G x transitions either are irrelevant, or are invertible, have empty conditions, irrelevant side effect deletes, and no side effects on V \ {x 0 }. Say that V * * contains this variable subset. We define cost D * (G) :

= x∈V cost D * (x), where cost D * (x) :=    1 x = x 0 mD(DT G x ) * x ′ :(x,x ′ )∈A cost D * (x ′ ) x = x 0 , x ∈ V * * d(DT G x ) * x ′ :(x,x ′ )∈A cost D * (x ′ ) x = x 0 , x ∈ V * *
Because x 0 must move -to attain its own goal -every optimal relaxed plan must take at least one transition leaving s(x 0 ). Thus, with Theorem 2 and the above, we have that:

Theorem 3 Let (X, s I , s G , O) be a planning task, and let s ∈ S be a state with 0 < h + (s) < ∞. Say that x 0 ∈ X so that, for every o 0 = rop(s(x 0 ), c) in DT G x0 where (s(x 0 ), c) is relevant, lDG o0 is a successful local dependency graph. Then s is not a local minimum, and ed(s) ≤ max o0 cost D * (lDG o0 ). If, for every lDG o0 , we have Definition 4 (3a) or (3b), then ed(s) ≤ max o0 cost D * (lDG o0 )-1.

Theorem 3 is our tool for guaranteed local analysis, i.e., a search-state analysis that guarantees its information to be correct. For guaranteed global analysis, we simply look at the set of all global dependency graphs gDG, requirthem to be successful. In particular, all gDG are then acyclic, from which it is not difficult to deduce that any nongoal state s will have a variable x 0 fulfilling Definition 4 (2). For that x 0 , we can apply Theorem 3 and thus get: Theorem 4 Let (X, s I , s G , O) be a planning task. Say that all global dependency graphs gDG are successful. Then S does not contain any local minima and, for any state s ∈ S with 0 < h + (s) < ∞, ed(s) ≤ max gDG cost D * (gDG). If, for every gDG, we have Definition 4 (3a) or (3b), then ed(s) ≤ max gDG cost D * (gDG) -1.

If SG is acyclic and all transitions are invertible and have no side effects, then Theorem 4 applies, whereby we have now in particular proved our basic result. Vice versa, note that, if Theorem 4 applies, then SG is acyclic. As far as local minima are concerned, one may thus reformulate Theorem 4 in simpler terms not relying on a notion of "successful dependency graphs". The present formulation already paves the way for future research: a gDG is defined relative to a concrete variable x 0 and operator o 0 , and may thus allow for more accurate analysis of which other variables may actually become important for x 0 and o 0 , in a relaxed plan.

Benchmark Performance Guarantees

We now state some guarantees that our analysis gives in benchmark domains. The underlying finite-domain variable formalizations are straightforward.

Proposition 1 Let (X, s I , s G , O) be a planning task from the Logistics, Miconic-STRIPS, Movie, or Simple-TSP domain. Then Theorem 4 applies, and the bound delivered is at most 1, 3, 1, and 1 respectively.

Proposition 2 Let (X, s I , s G , O) be a planning task from the Elevators, Ferry, Gripper, or Transport domain, and let s ∈ S. In Ferry and Gripper, for every optimal relaxed plan P + (s) there exists oDG + so that Theorem 2 applies, the bound being at most 1. In Elevators and Transport, there exists at least one P + (s) and oDG + so that Theorem 2 applies, the bound being at most 1 in Elevators and at most the road map diameter in Transport.

Proposition 2 holds because all vehicle capacity deletes are recovered inside the relaxed plan. For Elevators and Transport, the result is slightly weaker because a vehicle may have capacity > 1, allowing relaxed plans to use unloading operators recovering a capacity not actually present.

Experiments

TorchLight is implemented in C based on FF-v2.3, using Fast-Downward's translator to find the finite-domain variables. 6 We run experiments in 37 domains, including those of Figure 1 and all IPC STRIPS domains up to 2008, except Cyber-Security which involved parsing and/or translation difficulties. The test instances, 1160 in total, were taken from the IPC collection(s) where applicable, and (randomly) generated elsewhere. All experiments are run on a 1.8 GHZ CPU, with a 30 minute runtime and 2 GB memory cut-off.

TorchLight runs global analysis checking the preconditions of Theorem 4. It then generates R sample states by random walks. We run R = 1, 10, 100, 1000. Each state is analyzed using guaranteed local analysis checking Theorem 3, as well as approximate local analysis checking Theorem 2 on a relaxed plan as computed by FF. The latter uses the aforementioned relaxed plan re-ordering technique, and a simple technique allowing to recognize situations where failure due to one operator can be avoided by replacing with an alternative operator. The local analyzes return statistics concerning in particular the success rate, i.e., the fraction of sample states where Theorem 3/Theorem 2 applied.

The code is currently optimized much more for readability than for speed. Still, TorchLight is fast. Up to R = 100, the main bottleneck is Fast-Downward's translator. With R = 1 and R = 10, in 99% of the instances the actual analysis takes at most as much time as the translator. With R = 100 this holds for 96%. On average, the translator takes 6.1 seconds; for analysis this is 0.8, 0.9, 1.9 with R = 1, 10, 100. For R = 1000, analysis can be more expensive, up to >1 minute in 5 domains. As we will see, this many samples are not needed to obtain useful information. 6 The source code of TorchLight is available at http://www. loria.fr/ ˜hoffmanj/TorchLight.zip Figure 3: Overview of TorchLight domain analysis results. "*": global analysis always succeeds; "+": local analysis always succeeds if provided an optimal relaxed plan; mean success rates when sampling one state per domain instance. The guarantees of Proposition 1 are confirmed, i.e., global analysis succeeds as described in Logistics, Miconic-STRIPS, Movie, and Simple-TSP. It never succeeds in any other domain, though. In some domains, fractions of the gDGs are successful, e.g., up to 97% in Satellite. However, if the fraction is below 100% then nothing is proved so this data may at best serve as an indication of which aspects of the domain are "good-natured". As for guaranteed local analysis, this generally is not much more applicable than global analysis. In what follows, we hence concentrate on approximate local analysis (via Theorem 2) exclusively.

Proposition 2 is backed up impressively. Approximate local analysis succeeds in every single sample state of Ferry, Gripper, Elevators, and Transport. Thus the potentially suboptimal relaxed plans do not hurt here. Indeed, the analysis yields high success rates in almost all domains where local minima are non-present or limited. This is not the case for the other domains, and thus TorchLight can distinguish domains with "easy" h + topology from "hard" ones. Consider Figure 3, showing mean success rates per-domain with R = 1. The picture is similar for R = 10, 100, 1000.

The domains whose h + topology is not known are shown separately on the right hand side in Figure 3. For the other domains, we see quite nicely that "harder" domains tend to have lower success rates. To some extent, we can even distinguish Pipesworld-Tankage from Pipesworld-NoTankage, and Mprime from Mystery (in Mprime, fuel can be transferred between locations). Strong outliers are Driverlog, Rovers, Hanoi, and Blocksworld-NoArm. But all of these are more problems of the hand-made analysis than of Torch-Light's. In Driverlog and Rovers, deep local minima do exist, but only in awkward situations that don't tend to arise in the IPC instances. As for Hanoi and Blocksworld-NoArm, these are not actually easy to solve for FF, and the absence of local minima is due to rather idiosyncratic reasons.

Success rates can also be obtained by search probing (SP). For each sample state, we search (using FF's helpful actions) for a monotone exit path under FF's heuristic. Runtime is worst-case exponential for any R, but in this experiment is competitive up to R = 10. For R = 1000, in 11 (4) domains runtime can be >1 (>30) minute(s). To some extent, one can handle this by a small time cut-off. Allowing 1 second per sample state changes the success rate by at most 5%, in 99% of these benchmarks. In general, though, of course such a cut-off severely limits the lookahead capability of search.

Remarkably, the prediction quality of TorchLight is just as good as -sometimes even better than -that of unlimited SP. For details, see [START_REF] Hoffmann | Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h +[END_REF]. We consider primitive classifiers based on only the success rate, predicting whether or not FF's enforced hill-climbing search will succeed in solving the overall task. The classifiers answered "yes" iff the success rate was above a threshold T in 0, 10, . . . , 100. The best rate of correct predictions (T being around 80) is 71.8% (R = 100) and 71.9% (R = 10) for TorchLight vs. 71.2% and 70.2% for SP; a baseline always answering "yes" would achieve 60.7% success here. This simplistic prediction method does not work as well for FF as a whole and for LAMA, which solve many tasks with unfavorable h + topology. However, looking at the runtime distributions below and above T , the mean of the latter is significantly smaller in all cases for TorchLight, and in most cases for SP.

TorchLight can also tell us why analysis failed, identifying domain features causing the presence of local minima. Since the tested criteria are sufficient but not necessary, there is no correctness guarantee. Still, at least for analysis using Theorem 2, the diagnosis can be quite accurate. It currently does not do much more than report all variable/operator pairs failing to qualify for x 0 , o 0 . In Zenotravel, this always correctly identifies fuel consumption as the problem. In Mprime and Mystery, most of the time the same correct diagnosis is returned. In Satellite and Rovers, it always reports the problem to be that switching on an instrument, respectively taking an image, deletes calibration -precisely the only reason why local minima exist here. In Tyreworld, Grid, Blocksworld-Arm, and Freecell, the diagnosis identifies critical resources (like "hand-empty" and "have-cellspace"). It seems likely that these results could still be much improved, by combining them with other information sources in TorchLight and/or with other domain analysis techniques.

Discussion

We identified a connection between causal graphs and h + , and devised a tool allowing to analyze search space topology without actually running any search. The tool is not yet an "automatic Hoffmann", but its analysis quality is impressive even when compared to unlimited search probing.

Causal graphs were previously used to identify tractable fragments (e.g., [START_REF] Jonsson | Incremental planning[END_REF][START_REF] Brafman | Structure and complexity in planning with unary operators[END_REF]Haslum 2007). However, tractability and absence of local minima are orthogonal properties. The strongest connection is that, if Theorem 4 applies, then plan existence (but not plan generation nor optimal planning) is tractable. For our basic result, but not for the full scope of Theorem 4, this tractability is known [START_REF] Hoffmann | Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h +[END_REF].

At a technical level, this work establishes two new aspects of causal graph analysis. (1) One can "localize" the analysis, considering only the fragment relevant for solving a particular state. This enables succes in tasks that are otherwise arbitrarily complex. (2) One can construct paths improving the value of a heuristic, rather than achieving the global goal. This is not limited to h + . Both (1) and (2) suggest completely new avenues of causal graph research.

TorchLight is useful for performance prediction. Like limited SP, it generates a highly informative feature without jeopardizing runtime, thus enabling automatic planner configuration. Unlike for SP, this may even work on-line during search. Based on a single relaxed plan, e.g., one might choose a different search strategy, or switch helpful actions on/off, depending on the outcome of checking Theorem 2.

Local analysis can be used to generate macro-actions, following the path to the better state. This relates to work on macros (e.g., Botea, Müller, and Schaeffer 2004), but with a very targeted analytical way of generating them.

One could use TorchLight's diagnosis facility as the basis of an abstraction technique for deriving search guidance. The diagnosis can pin-point which operator effects are causing problems for search. If we remove enough harmful effects so that Theorem 4 applies, then the abstract problem is tractable. If we do not abstract that much, the information provided may still outweigh the effort for abstract planning.

Another interesting issue is domain reformulation. Haslum (2007) identifies as a main open problem the lack of guiding information. TorchLight's diagnosis may come to the rescue. Automatic reformulation could, e.g., precompose variable subsets touched by harmful effects, or hide these effects within macro-actions. The diagnosis could also give modeling advice to non-planning experts, supporting them in the design of hierarchies of domains giving different trade-offs between planning effort and plan accuracy, thus helping to make planning technology more accessible.

  For each o ∈ O where x ∈ X pre o ∩ X effo with c := pre o (x) and c ′ := eff o (x), DT G x contains an arc (c, c ′ ) labeled with responsible operator rop(c, c ′ ) := o, with conditions cond(c, c ′ ) := pre o \ {(x, c)}, and with side effects seff(c, c ′

Simple-TSP encodes TSP but on a fully connected graph with uniform edge cost. The domain was originally introduced as a benchmark for symmetry detection.

This method enumerates all ways in which facts may support each other in a non-redundant relaxed plan. If there is no "conflict" then h + is the exact solution distance. This applies only in Simple-TSP. A slightly more general special case applies in Movie and trivial Logistics tasks with 2 locations, 1 truck, and 1 package.

We must require no side effects on V \ {x0} due to a subtlety in the construction of P + (s ′ ). We omit this for brevity.

For gDG, note that pre o 0 (x0), if defined, will be = s(x0) and thus x0 does not need to be recorded as its own predecessor.

Acknowledgments. I had long ago given up on this problem. Thanks to Carlos Areces' and Luciana Benotti's insistence, I finally saw the connection to causal graphs -while trying to convince them that such an analysis is not possible.


Antoine Ayache

Jacques Lévy

Generalized Multifractional Brownian Motion: Definition and Preliminary Results