Guillaume Mottet
email: guillaume.mottet@free.fr

Julien Villemejane
email: julien.villemejane@ens-cachan.fr

Luis M Mir
email: luis.mir@igr.fr

Bruno Le Pioufle
email: bruno.lepioufle@satie.ens-cachan.fr

A technique to design complex 3D lab on chip involving multilayered fluidics, embedded thick electrodes, and hard packaging -Application to dielectrophoresis and electroporation of cells

Keywords: Bonding SU-8, wafer bonding, thick electrodes, packaging, microfluidics, dielectrophoresis, electroporation, Lab On a Chip

published or not. The documents may come

A technique to design complex 3D lab on a chip involving multilayered fluidics, embedded thick electrodes and hard packaging. Application to dielectrophoresis and electroporation of cells.

INTRODUCTION

In 1970s Terry et al proposed to miniaturize a gas chromatography device [START_REF] Stephen | A Gas Chromatographic Air Analyzer Fabricated[END_REF]. They integrated a miniature valve, a long spiral column and a thermal conductivity detector on a single device. This work is often considered as pioneering in LOC fabrication. Thanks to the advent of microtechnology in the 1990s, fluidic microsystems became more complex. Manz [START_REF] Manz | Miniaturized total chemical analysis systems: a novel concept for chemical sensing Sensors and Actuators B[END_REF] suggested to call those microsystems: "micro total analysis system" (TAS). With the evolution and sophistication of the microsystems, the usual term became "Lab-On-a-Chip" (LOC).

Micro and nanotechnologies enabled the development of miniaturization providing hopes and new ideas in this field. Miniaturization provides a better control, interaction and manipulation. At the same time, the complexity of the technology requires more and more energy, time and money. Since most LOCs are developed for a single-use, due to their fragility and to the difficulty or impossibility to clean them, our objective was to make a robust and reusable LOC.

Most LOC have to integrate complex fluidic networks (large size, with any forms, channels at different levels...). Moreover, a large category has to interact with biological materials that require electric or chemical effects to be handled. Finally, LOC should involve sensing functions (electrical, electrochemical or optical) that should be integrated.

A great number of processes were developed to design LOCs. In 1990s the first processes were inherited directly from the microelectronic technologies. These technologies were predominantly based on silicon (Si). Indeed, it is possible to structure it or to dope it to make respectively channels or electrodes. It is also possible to seal these channels using anodic bonding or eutectic bonding. However, the use of silicon brings up several problems: too large electrical resistivity for high current applications, complexity and time consuming processes as Bosh-process requiring the use of an ICP-RIE. Glass technology is another alternative currently used for chip elaboration [START_REF] Harrison | Micromachining a Miniaturized Capillary Electrophoresis-Based Chemical Analysis System on a Chip[END_REF] which remains complicated and costly. Finally the use of an organic polymer [START_REF] Becker | Polymer microfluidic devices[END_REF] like PDMS (Polydimethylsiloxane) showed to be quite convenient for the fabrication of microchannels [START_REF] Duffy | Rapid prototyping of microfluidic systems in poly(dimethylsiloxane)[END_REF], three-dimensional (3D) microfluidic chips [START_REF] Anderson | Fabrication of Topologically Complex Three-Dimensional Microfluidic Systems in PDMS by Rapid Prototyping Anal[END_REF] and even LOCs [START_REF] Sin | Fabrication and testing of a PDMS multi-stacked handoperated LOC for use in portable immunosensing systems[END_REF]. PDMS structures can be obtained by micromoulding technologies, but it remains difficult to make an accurate alignment with another layer or with electrodes.

Surprisingly, an advantageous solution has recently emerged from a specific photoresist dedicated to MEMS devices, named SU-8 [8]. SU-8 is a multifunctional epoxy-based negative resist, interesting for its ability to sustain high aspect ratio and 3D structures [START_REF] Del | SU-8: a photoresist for high-aspect-ratio and 3D submicron lithography[END_REF]. Furthermore, it has an excellent chemical resistance, high transparency, biocompatibility [START_REF] Kotzara | Evaluation of MEMS materials of construction for implantable medical devices[END_REF][START_REF] Lu | SU8-Based micro neural probe for enhanced chronic in-vivo recording of spike signals from regenerated axons[END_REF][START_REF] Voskericiana | Biocompatibility and biofouling of MEMS drug delivery devices[END_REF] and a low bonding temperature (<80 °C). All those advantages make SU-8 a good candidate to elaborate LOCs. Today, several distinct techniques based on SU-8 allow the integration of complex microfluidic networks in a microsystem. A first method to make multilevel fluidic structures is based on the patterning of successive SU-8 layers after UV exposure. To isolate each patterned SU-8 layer from following UV exposures a metallic layer is intercalated [START_REF] Alderman | Microfabrication of channels using an embedded mask in negative resist[END_REF]. In the same way, a second method consists in playing with the exposure dose in order to get a partial insulation [START_REF] Chuang | A novel fabrication method of embedded micro-channels by using SU-8 thick-film photoresists[END_REF]. Other alternative consist in using epoxy resists [START_REF] Ling | In situ fabrication of SU-8 movable parts by using PAG-diluted SU-8 as the sacrificial layer Microsyst[END_REF] or other materials [START_REF] Metz | Polyimide and SU-8 microfluidic devices manufactured by heat-depolymerizable sacrificial material technique Lab on a Chip[END_REF] like sacrificial layers. However, all those methods have an important default: the development of embedded channels remains difficult or even impossible, as the developer penetrates with difficulty long or curved channels.

To overcome this drawback, an alternative approach was suggested, where channels were sealed once structured. This technique relies on the SU-8/SU-8 bonding either by lamination or by wafer bonding. Lamination process allows a SU-8 dry film to be applied on another SU-8 layer already structured. This technique allows reliable fabrication of multilevel fluidic networks [START_REF] Abgrall | A novel fabrication method of flexible and monolithic 3D microfluidic structures using lamination of SU-8 films[END_REF]. This process has multiple advantages: it compatible with non flat surfaces and it requires a low force during the bonding that helps in limiting the flow of SU-8 in channels and thus the risk of channel clogging. Unfortunately, this technique does not allow the bonding of a hard substrate, highly recommended for the chip packaging (physical protection for the chip and easiness fluidic connection).

On the other hand wafer bonding is a commonly used process that enables the bonding of hard substrates, but that requires on the other hand an important external force and a very flat surface. Different reports showed the possibility to use this technique to make channels. Some used auxiliary moats to prevent channels clogging [START_REF] Tuomikoski | Free-standing SU-8 microfluidic chips by adhesive bonding and release etching[END_REF], but it makes the design of the system complex and it is not compatible with insertion of electrodes. Others suggested to bond after a soft bake to avoid the flow of SU-8, but the bonding remains very sensitive to the surface roughness [START_REF] Blanco | Novel three-dimensional embedded SU-8 microchannels fabricated using a low temperature full wafer adhesive bonding[END_REF].

The idea developed in this paper is to combine advantageously two techniques: the photosensitive SU-8 dry films bonding technique and the hard glass substrate bonding technique. Furthermore, we present how thick electrodes (>5m) can be integrated. This type of electrodes could be essential to obtain strong and uniform electric fields [START_REF] Ju | An electrofusion chip with a cell delivery system driven by surface tension[END_REF]. As a proof of concept a cell biochip, devoted to cell arraying prior to electropermeabilization was made using this new technique.

MATERIALS

Single sided polished 2 inch (100) Si wafers (250m thickness) and 2 inch glass wafers (1mm thickness) were used. AZ5214E and AZ developer from Clariant Corp were involved for the liftoff process. We used the commercial SU-8 2100 or SU-8 3050 negative epoxy photoresist for the spin coating [8]. The SU-8 dry film was from Michrochem Corp.: DF 1000-20, as well as. the propylenglycol-monoether-acetate (PGMEA) used for the developing and the remover PG used for the removing.

The fabrication is based on the use of EVG 501, a commercial wafer bonding machine from EVG (St.Florian am Inn, Austria). This machine allows us to squeeze the different substrate with a required force, temperature and vacuum. During the process we use it twice, the first time to level off a layer of SU-8 and the second time to bond two layers of SU-8. The first step is to build thin electrodes on a glass wafer by lift-off technique. Then, we form a SU-8 mold on these thin electrodes to make the thick electrodes by electrodeposition (copper electroplating from sulfuric acid solution). When the deposition is finished, the release of the mold by a hot solution of remover PG reveals the thick electrodes. After that, a first layer of SU-8 is deposited to structure the channels. This first layer is strongly irregular due to the presence of the thick electrodes, which explains why a wafer bonder has to be used to make this layer uniform. Then, the bonding of a dry film of SU-8 is performed to close the channels. This step can be repeated to manufacture 3D interconnected channels. Finally the LOC is sealed with a glass substrate (drilled and covered of SU-8), which permits the fluidic interconnections after PDMS blocks are stuck on the glass substrate. The details of the process fabrication are shown in figure 1.

Thin electrodes

Thin electrodes are obtained by a liftoff process for the rapidity of the process and in order to avoid metal contamination on non metallic surfaces. The glass wafer is cleaned with a succession of acetone, ethanol and water baths. Then, the reversal photoresist AZ 5214E is spin-coated (1000 rpm during 30 seconds) which gives a layer of 3 m of thickness. A prebake at 110 °C during 50 seconds is performed to remove the solvent. Then the resist is exposed a first time to UV light with a dose of 2 mJ/cm through an appropriate mask using a conventional EVG 620 lithographic aligner. After that the resist is reversed via a bake at 120 °C during 2 minutes. Next the resist receives a flood exposure of 180 mJ/cm. Finally the resist is developed in a solution of AZ developer mixed with water (1:1) during approximately 90 seconds.

The metal deposition is obtained by a sputtering system from Denton Vacuum. A first layer of 300 nm of titanium is deposited to improve adhesion, then a second layer of 800 nm of gold. The thin electrodes are finally obtained by dipping the chip in acetone solution, thanks to the cap profile of the inverted resist.

Thick electrodes

The objective of our LOC is the generation of an electric field that could interact homogenously and intensely with the cells. Thereby thick electrodes have to be elaborated. This goal is accomplished in three steps. The first step consists in making the mold for the thick electrodes; the second is the electrodeposition and the third one release of the mold to obtain the desired thick electrodes.

The mold is composed of two layers. The first layer is a thin layer of Omnicoat TM [21] which improves the adhesion of SU-8 on glass and will help to remove the mold afterwards. The second layer made with SU-8 2100 gives the shape of the mold (all parameters used during the fabrication are given in table 1). To ensure that the surface is clean, the sample is exposed to O2/CF4 plasma at 200W during 3 minutes. At this level of the process the mold is ready for the electrodeposition.

Electrodeposition of copper was achieved by immersing the sample in an acid copper solution, then by connecting the sample to the cathode and by applying a current of 3.10 -2 A/cm. With this current intensity, approximately 0,8 m of copper are electroplated per minute. Usually, plating was restricted to 10 or 15m but it is possible to deposit a much thicker layer (~50m). To release the mold, the sample is plunged in a hot solution of remover PG (~80°C). Ultrasonic cleaning can be necessary to remove all the SU-8. Finally the microsystem has both thin electrodes and thick electrodes.

Buried electrodes and first layer channel

To obtain a flat layer, in spite of the strong structuration caused by the presence of thick electrodes, we developed a new technique to smooth the surface. This technique, that removes the large roughness (see figure 3.a), consists in a spin of SU-8 3050 and in its squeezing in a commercial wafer bonder (EVG 501).

The process begins with a dehydrating treatment on a hot plate at 200°C during approximately 30 min. This step is very important as SU-8 is hydrophobic. Also a thin layer of water in the wafer would increase the stress and consequently decreases the adhesion. After that the SU-8 is deposited and baked to remove the solvent (see table 1). At this time the surface level is varying largely. In order to remove these level variations, the sample is squeezed in the wafer bonder with a force of 700 N at 70 °C. To protect the wafer bonder from a SU-8 flow a PET film is put between the sample and the piston (this film is removed after the squeezing). Finally the sample is exposed to UV (in order to structure the channels) baked and developed. After this step, the microsystem is constituted of the thick electrodes and of the side of the channels. One can note that this technique can be used to limit the edge effects after a spin coating.

SU-8 dry film bonding

In order to close the channels, a technique close to the one developed by Abgrall et al [START_REF] Abgrall | A novel fabrication method of flexible and monolithic 3D microfluidic structures using lamination of SU-8 films[END_REF] is applied. Its principle is based on the bonding of a SU-8 dry film on a structured SU-8 layer. The SU-8 dry film (20 m) is sandwiched between two PET protective films. To use it, one PET layer is peeled off to enable the contact between the SU-8 and the SU-8 layer of the device. Then, oxygen plasma is applied on the sample to improve adhesion between SU-8 layers (200 W, 3 minutes). The dry film (SU-8+one PET layer) is then pressed on the sample thanks to the wafer bonder with a force between 200 N and 300N at 65 °C. After that, the chip is perfectly covered by the SU-8 dry film. To finalize the bonding and to structure the inlets and the outlets, we expose the SU-8 dry film to UV light and we bake it. Until the step of baking it is important to maintain the second PET protective layer because if it was removed before, the SU-8 would not enough stuck to the surface and it could tear up. After baking, the second PET film is peeled off to enable the development of the SU-8 layer added (see table 1). To achieve a channels multilevel network this process has to be repeated as many times as necessary.

Hard glass substrate bonding

The hard glass substrate bonding is necessary in order to strength the packaging and to create the external fluidic connections (SU8 dry film is too thin and fragile). The glass substrate is drilled for the inlet and outlet, dehydrated and a layer of SU8-3050 is spun on it with the same parameters as those previously used (see table 1). During this step, the fact that SU-8 is a very viscous resist and the holes are very small (1mm diameter) enable to cover well the glass substrate (without problem of uniformity, except at the edges where homogeneity can be simply imposed by using the wafer bonder, see paragraph 3.3). After spinning and baking, we simply remove the SU-8 covering the holes with a drill. At the end, a glass with holes covered by a uniform layer of SU-8 is obtained. An O 2 plasma is performed on the microsystem (200 W, 3 minutes), in order to improve the adhesion between it and the SU-8 layer. Then, the hard glass substrate with SU-8 and the microsystem are put in contact and squeezed together thanks to a wafer bonder (650 N to 750 N at 65 °C). Due to the fact that the substrate is hard, the force necessary is higher than for a SU-8 dry film. Finally, the whole set-up is exposed to UV light and baked to cross-link the last layer. 1@200°C 3@65°C, 13@95°C 1@65°C, 10@95°C Exposure (mJ/cm) 150 200 180 Post-bake (min) 2@65°C, 10@95°C 1@65°C, 8@95°C 2@65°C, 8@95°C Development in PGMEA (min) 8 5 5 Thickness (m) ~0,02 ~80 ~50 20

Electrical and fluidic connections

To transform the microsystem in a LOC, electric wires are simply welded to the electrodes. For the fluidic connection, PDMS blocks are prepared and drilled to accept the insertion of microcapillaries. Then the microsystem and the PDMS blocks are exposed to oxygen plasma (30 W, 30 s). The PDMS block and the microsystem are assembled to achieve the bonding. The LOC is now ready to be connected with electric generator, syringes pump...

RESULTS AND DISCUSSION

To demonstrate the efficiency of our process two devices were manufactured: the first was a multilevel microfluidic system, and the second a bio-LOC with thick electrodes.

Fabrication of the demonstrators

4.1.1 Fabrication process of a multilevel microfluidic system. This device shows the possibility to use SU-8 dry films and wafer bonding to make multilevel microchannels networks. In this process, five SU-8 dry films were used. The first layer enabled to define the shape of the first channel witch correspond to the letters "_AS". The second and the third layers were bonded to seal the first channel and to consolidate it. The fourth layer structured the second channel with the shape of a "T". Finally the last layer sealed the whole. A drilled glass substrate was bonded to connect it with outside. The figure 2 displays the different fabrication steps. As shown in figure 2.c, glass substrate does not totally cover the device. This is not really a problem because channels were already sealed with SU-8 dry film. A bonding was considered good enough if the inlet and outlet were correctly bonded, which was mostly the case. Lastly, during the sealing of the channel with SU-8 dry film, it could happen that uncross-linked SU-8 flowed at the beginning of the channel. To remove this uncross-linked SU-8, the sample was put in a low power ultrasonic generator during 5 seconds. Normally, if the protocol is followed there is no problem of leakage.

bio-LOC with thick electrodes.

This second demonstrator of our technology targeted a biological application of LOC, namely a biochip devoted to cell placement at precise locations and to cell treatment by means of electric fields. This LOC was constituted of channels, thick electrodes and dielectric structures to focus the electric fields. A bottleneck that could be overcome thanks to the technique presented in this paper was the capability to get thick electrodes buried in thick SU8 (channel), while keeping the capability to seal the whole system with a glass substrate. Indeed, a smooth SU-8 surface (see figure 3 (c) A bubble in the channel of the bio-LOC filled of water.

Biological tests on the bio-LOC.

The LOC was designed in order to optimize the electric field needed to establish a convenient interaction with the cells. Thick electrodes and dielectric structures were integrated into the device. The bio-LOC had two purposes: cell placement thanks to dielectrophoresis and cell electropermeabilization. A non-uniform alternating electric field can be used to handle a neutral particle, like a cell, in a liquid. This phenomenon is the consequence of the dielectrophoresis force [START_REF] Ha Pohl | The motion and precipitation of suspensoids in divergent electric fields[END_REF][START_REF] Zimmermann | Electromanipulation of cells[END_REF]. Depending of the frequency the particle will be move toward maxima of electric field (positive DEP) or toward minima of electric field (negative DEP). If the cell is approximated to a spherical dielectric with losses, the average dielectrophoresis force is expressed:

2 3 )]. ( Re[ 2 ) ( eff m DEP E w K r t F >= <
Where r is the radius of the cell, E symbolizes the electric field and K is called the criterion of Clausius-Mossotti which is:

* * * * 2 ) ( m p m p w K + = p *
is the complex permittivity of the particle and m * is the complex permittivity of the surrounding liquid. The orientation of the force depends on the sign of the criterion of Clausius-Mossotti which is linked to the frequency. For our experiments either a high frequency (>100 kHz) which forced the cells to move toward the maxima of the field (figure 7.b), or inversely a low frequency (<10 kHz) to force the cells to move toward the minima of field (figure 7.b) were applied. The consequences of the application of a high and a low frequency signals on the B16 cells are shown in figure 7.

The second objective of the bio-LOC was to electropermeabilize the membrane of the cells which had been previously arrayed thanks to DEP. This point was checked using a fluorescent dye (calceine) introduced inside the cell before the experiment. This molecule can only be externalized from the cell, if the cell membrane is permeabilized. Figure 8 shows that after the application of cell permeabilizing electric pulses, the cells fluorescence decreases due to the leakage of calceine, demonstrating the proper functioning of our bio-LOC. During our tests, the importance of a good cleaning after the end of the experiment to preserve the LOC from obstruction was noticed. Indeed, during biologic experiments a lot of cellular debris could clog the channels. To eliminate existing or potential clogging, the microfluidic system was cleaned with bleach, isopropanol and deionized water. This cleaning with corrosive products allowed us to reuse the microsystem until very big dusts definitively clogged the microchannels.

CONCLUSIONS

A new, simple and efficient technique which enables the microfabrication of complex 3D microfluidic structures, involving multilevel fluidics, thin or thick electrodes, and hard packaging with glass is proposed in this paper. In order to prove the feasibility of the method, two demonstrators have been elaborated: a 3D multilevel fluidic demonstrator which showed the functionality of flowing fluids at each level without leakages, and a bio-LOC capable to handle and treat cells thanks to electrical field applied between thick electrodes embedded in the channel.

Figure 1 .

 1 Figure 1. Fabrication process of the fluidic chips.

Figure 2 .

 2 Figure 2. Fabrication steps of the multilevel fluidic system : (a) First microfluidic level with the channel "AS". (b) Second level with the channel 'T'. (c) Third bonding of a glass substrate.

  .b, 4.a and 4.b) was obtained, allowing a compatibility with further packaging steps (sealing with a SU-8 dry film and a glass substrate). A cross section of the complete device is shown in figure 5.a and an overview in figure 5.b.

Figure 3 .

 3 Figure 3. Mechanical profilometer measures of the SU-8 surface just after spinning (a) and at the end of the process (insulation, post-bake and development) (b). At the top, schematic views of the different phenomena.

Figure 4 .

 4 Figure 4. Integration of thick electrodes and dielectrics structures in the channel: (a) Mechanical profilometer measures of a channel. (b) SEM image of a channel within its center dielectrics structures (SU-8).

Figure 5 .

 5 Figure 5. Images of the complete device: (a) SEM image of a cross section. (b) Overview of the sample.

4. 2

 2 Hydraulic and biologic tests on the demonstrators 4.2.1 Hydraulic tests on the multilevel microfluidic system. Our demonstrator device has two levels: a first level where the channel forms the letters 'AS', and a second level with the letter T. Two fluorescent molecules (DCM and Eosine) where injected respectively in these two levels in order to test the functionality of the microfluidic chip. Flowing of the two markers, without any crosscontamination, was clearly demonstrated by fluorescence observations (figure 6.a, 6.b). These tests validated our technology from a hydraulic point of view.

Figure 6 .

 6 Figure 6. Hydraulic tests: (a) Injection of DCM marker (fluorescence emission 620nm) in the channel "AS". (b) Injection of Eosine marker (fluorescence emission at 555nm) in the channel "T".(c) A bubble in the channel of the bio-LOC filled of water.

Figure 7 .

 7 Figure 7. Dielectrophoresis experiment on B16 cells (we put blue points on cells to make easier their visibility): (a) Negative dielectrophoresis on 4 cells (10 kHz, 10Vpp). (b) Positive dielectrophoresis on the 4 same cells (1 MHz, 10Vpp).

Figure 8 .

 8 Figure 8. Electroporation experiment on DC3F cells (a) Just before the electroporation (high: image in visible, low: fluorescence image). (b) 5 minutes after two pulses (25 V, 80 s), the fluorescence has drastically decrease.

Table 1st .

 1st Omnicoat, SU-8 and SU-8 dry film process parameters used in this study.

	Resist	Omnicoat	SU-8 2100	SU-8 3050	SU-8 dry film
	1 spin Acceleration (rpm s -1 )	300	300	300
	1 spin Rotation Speed (rpm)	500	500	500
	Time (s)	10	30	30
	2 nd spin Acceleration (rpm s -1 )	300	300	300
	2 nd spin Rotation Speed (rpm)	1000	5000	3000
	Time (s)	60	60	60
	Soft bake (min)

6 ACKNOWLEDGEMENTS This work has been financially supported by the Centre National de la Recherche Scientifique (CNRS), IGR, the French National Agency (ANR) through Nanoscience and Nanotechnology Program (Nanopulsebiochip n° ANR-08-NANO-024) and the PRES Universud. The devices were made in the clean room CTU MINERVE of IEF from the university Paris XI Orsay. Authors would like to thank V. Mathet and D. Bouville for their help in the clean room and V. Joubert for her help in biology experiments. Finally thanks to M. Maire, J. Duquennoy and L. Malaquin for proofreading.


Raz Nissim

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

Malte Helmert

Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning

A * with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&S yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction -not distinguishing between certain groups of operators -without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a simple hybrid of two such variants is competitive with the leading heuristic LM-cut.

Introduction

Many optimal planning systems are based on state-space search with A * and admissible heuristics. The research question is how to derive the heuristic automatically. Merge-andshrink abstraction [Dräger et al., 2006;[START_REF] Helmert | [END_REF], in short M&S, uses solution distance in a smaller, abstract state space to yield a consistent and admissible heuristic.

The abstract state space is built in an incremental fashion, starting with a set of atomic abstractions corresponding to individual variables, then iteratively merging two abstractions -replacing them with their synchronized product -and shrinking them -aggregating pairs of states into one. Thus, despite the exponential size of the state space, M&S allows to select individual pairs of states to aggregate. This freedom in abstraction design comes with significant advantages. M&S dominates most other known frameworks for computing admissible planning heuristics: for any given state, it can with polynomial overhead compute a larger lower bound [START_REF] Helmert | Malte Helmert and Carmel Domshlak. Landmarks, critical paths and abstractions: What's the difference anyway?[END_REF]. Further, in difference to most other known frameworks, M&S is able to compute, in polynomial time, perfect heuristics for some benchmark domains where optimal planning is easy [START_REF] Helmert | [END_REF][START_REF] Helmert | Helmert and Robert Mattmüller. Accuracy of admissible heuristic functions in selected planning domains[END_REF].

M&S currently does not live up to its promises: (A) in the international planning competition (IPC) benchmarks, it gives worse empirical performance than the currently leading heuristics, in particular LM-cut [START_REF] Helmert | Malte Helmert and Carmel Domshlak. Landmarks, critical paths and abstractions: What's the difference anyway?[END_REF]; (B) it does not deliver perfect heuristics in the benchmarks where it could. The theoretical power of M&S hinges on the ability to take perfect decisions as to which pairs of states to aggregate. Little is known about how to take such decisions in practice. We herein address this issue, largely solving (B), and making headway towards solving (A).

Our investigation is based on the notion of bisimulation, a well-known criterion under which an abstract state space "exhibits the same observable behavior" as the original state space [Milner, 1990]. Two states s, t are bisimilar if: (1) they agree on whether or not the goal is true; and (2) every transition label, i.e., every planning operator, leads into the same abstract state from both s and t. If we aggregate only bisimilar states during M&S, then the heuristic is guaranteed to be perfect. A coarsest bisimulation can be efficiently constructed, and thus this offers a practical strategy for selecting the states to aggregate. Indeed, this was observed already by Dräger et al. [2006] (in a model checking context). However, bisimulations are exponentially big even in trivial examples, including the aforementioned benchmarks (B). Our key observation is that, for the purpose of computing a heuristic, we can relax bisimulation significantly without losing any information. Namely, we do not need to distinguish the transition labels. Such a fully label-reduced bisimulation still preserves solution distance, while often being exponentially smaller.

Unfortunately, while full label reduction does not affect solution distances per se, its application within the M&S framework is problematic. The merging step, in order to synchronize transitions, needs to know which ones share the same label, i.e., correspond to the same operator. We tackle this by using partial label reductions, ignoring the difference between two labels only if they are equivalent for "the rest" of the M&S construction. We thus obtain, again, a strategy that guarantees to deliver a perfect heuristic. This method largely solves challenge (B), in that its runtime is polynomially bounded in most of the relevant domains.

Even label-reduced bisimulations are often prohibitively big, thus for practicality one needs a strategy to approximate further if required. We experiment with a variety of such strategies, and examine their performance empirically. Each single strategy still is inferior to LM-cut. However, the different strategies exhibit complementary strengths, i.e., they work well in different domains. We thus experiment with simple hybrid planners running two of the stragies sequentially. We find that, addressing challenge (A), one of these hybrids is competitive with LM-cut in the IPC benchmarks, and even outperforms it when ignoring the Miconic domain.

For space reasons, we omit many details and only outline proofs. Full details are available from the authors on request.

Background

We consider optimal sequential planning with finite-domain variables. A planning task is a 4-tuple (V, O, s 0 , s ⋆ ). V is a finite set of variables, where each v ∈ V is associated with a finite domain

D v . A partial state over V is a function s on a subset V s of V, so that s(v) ∈ D v for all v ∈ V s ; s is a state if V s = V. The initial state s 0 is a state. The goal s ⋆ is a partial state.
O is a finite set of operators, each being a pair (pre, eff) of partial states, called its precondition and effect.

The semantics of planning tasks are, as usual, defined via their state spaces, which are (labeled) transition systems. Such a system is a 5-tuple Θ = (S, L, T, s 0 , S ⋆ ) where S is a finite set of states, L is a finite set of transition labels, T ⊆ S × L × S is a set of labeled transitions, s 0 ∈ S is the start state, and S ⋆ ⊆ S is the set of solution states. In the state space of a planning task, S is the set of all states; s 0 is identical with the initial state of the task; s ∈ S ⋆ if s ⋆ ⊆ s; the transition labels L are the operators O; and (s, (pre, eff),

s ′ ) ∈ T if s complies with pre, s ′ (v) = eff(v) for v ∈ V eff , and s ′ (v) = s(v) for v ∈ V \ V eff .
A plan is a path from s 0 to any s ⋆ ∈ S ⋆ . The plan is optimal iff its length is equal to sd (s 0 ), where sd : S → N 0 assigns to s the length of a shortest path from s to any s ⋆ ∈ S ⋆ , or sd (s) = ∞ if there is no such path.

A heuristic is a function h : S → N 0 ∪{∞}. The heuristic is admissible iff, for every s ∈ S, h(s) ≤ sd (s); it is consistent iff, for every (s, l, s ′ ) ∈ T , h(s) ≤ h(s ′ ) + 1. As is well known, A * with an admissible heuristic returns an optimal solution, and does not need to re-open any nodes if the heuristic is consistent. We will also consider perfect heuristics, that coincide with sd . If we know that h is perfect, then we can extract an optimal plan without any search.

How to automatically compute a heuristic, given a planning task as input? Our approach is based on designing an abstraction. This is a function α mapping S to a set of abstract states S α . The abstract state space Θ α is defined as (S α , L, T α , s α 0 , S α ⋆ ), where

T α := {(α(s), l, α(s ′ )) | (s, l, s ′ ) ∈ T }, s α 0 := α(s 0 ), and S α ⋆ := {α(s ⋆ ) | s ⋆ ∈ S ⋆ }.
The abstraction heuristic h α maps each s ∈ S to the solution distance of α(s) in Θ α ; h α is admissible and consistent. We will sometimes consider the induced equivalence relation ∼ α , defined by setting s ∼ α t iff α(s) = α(t).

To illustrate abstractions, Figure 1 gives an example. In the Gripper benchmark, one needs to transport n objects from a room A into a room B, with a robot R that can carry two AAA BAA ARA BRA BBA ABA ABR BBR BBB ABB AAR BAR BAB AAB ARB BRB s t Figure 1: An abstraction of (simplified) Gripper. objects at a time. We show here the state space for n = 2, in the simplified situation where the robot can carry only a single object. The planning task has 4 variables, R with D R = {A, B}, F with D F = {0, 1} (hand free?), O i with D Oi = {A, B, R} for i = 1, 2. States in Figure 1 are shown as triples giving the value of R, O 1 , and O 2 in this order (omitting F , whose value is implied). For example, in the state marked "s", the robot is at A, O 1 is at B, O 2 is at A (and F = 1). The abstraction α is indicated by the (blue) dashed boxes. This abstraction aggregates states -assigns them to the same abstract state -iff they agree on the status of the robot and on the number of objects in each room. Thus the abstraction does not distinguish the upper solution path (transporting O 1 first) from the lower one (transporting O 2 first). This does not affect solution length, so h α is perfect. The same can be done for arbitrary n, yielding perfect heuristics and polynomial-sized (measured in |S α |) abstractions.

How to choose a good α in general? Pattern databases (PDBs) [START_REF] Edelkamp | Stefan Edelkamp. Planning with pattern databases[END_REF] simplify this question by limiting α to be a projection. Given V ⊆ V, the projection π V onto V is defined by setting π V (s) to be the restriction of s onto V . π V can be computed very efficiently, and the solution distances in Θ πV can be pre-computed and stored in a table (the PDB) prior to search.

The downside of PDBs is their lack of flexibility in abstraction design. To be computationally efficient, any PDB can consider only a small subset of variables. Thus, even in trivial domains, PDBs cannot compactly represent the perfect heuristic [START_REF] Helmert | [END_REF]. For example, in Gripper, any polynomial-sized PDB considers only a logarithmic number of objects. The position of the other objects will be abstracted away, thus under-estimating sd to an arbitrarily large extent. For example, in Figure 1, if V = {R, O 1 }, then s and its right neighbor are aggregated, shortening the upper solution path. Summing over "additive PDBs" does not help, since at most one such PDB may consider the robot position.

Inspired by work in the context of model checking automata networks [Dräger et al., 2006], [START_REF] Helmert | [END_REF] propose M&S abstraction as an alternative allowing more fine-grained abstraction design, selecting individual pairs of states to aggregate. To make such selection feasible in exponentially large state spaces, the approach builds the abstraction in an incremental fashion, iterating between merging and shrinking steps. In detail, an abstraction α is a M&S abstraction over V ⊆ V if it can be constructed using these rules:

(i) For v ∈ V, π {v} is an M&S abstraction over {v}.

(ii) If β is an M&S abstraction over V and γ is a function on S β , then γ • β is an M&S abstraction over V . (iii) If α 1 and α 2 are M&S abstractions over disjoint sets

V 1 and V 2 , then α 1 ⊗ α 2 is an M&S abstraction over V 1 ∪ V 2 .
It is important to keep these rules in mind since we will be referring back to them throughout the paper. Rule (i) allows to start from atomic projections, i.e., projections π {v} onto a single variable, also written π v in the rest of this paper. Rule (ii), the shrinking step, allows to iteratively aggregate an arbitrary number of state pairs, in abstraction β. Formally, this simply means to apply an additional abstraction γ to the image of β. In rule (iii), the merging step, the merged abstraction α 1 ⊗ α 2 is defined by

(α 1 ⊗ α 2 )(s) := (α 1 (s), α 2 (s)).
It is easy to see that this definition generalizes PDBs: 1

Proposition 2.1 [START_REF] Helmert | [END_REF] Let Θ be the state space of a planning task with variables V, and let α be an M&S abstraction over V ⊆ V constructed using only rules (i) and (iii). Then Θ α is isomorphic to Θ πV .

Moreover, as [START_REF] Helmert | [END_REF] show, M&S strictly generalizes PDBs in that it can compactly represent the perfect heuristic in domains where PDBs cannot. For example, in Gripper we obtain the perfect heuristic by aggregating states as exemplified in Figure 1.

Proposition 2.1 holds even if we drop the constraint V 1 ∩ V 2 = ∅ in rule (iii). That constraint plays an important role in the computation of h α . Note that, a priori, this issue is separate from the design of α. We follow [START_REF] Helmert | [END_REF] in that, while designing α, we maintain also the abstract state space Θ α (and are thus able to compute h α ). In a little more detail, we maintain a transition system Θ α , in a way so that Θ α is identical with the (mathematically defined) abstract state space Θ α of α; note the use of α as a subscript respectively superscript to distinguish these two. The correct maintenance of Θ α is trivial for rules (i) and (ii), but is a bit tricky for rule (iii). We need to compute the abstract state space Θ α1⊗α2 of α 1 ⊗ α 2 , based on the transition systems Θ α1 and Θ α2 computed for α 1 and α 2 beforehand. As an induction hypothesis, assume that Θ α1 = Θ α1 and Θ α2 = Θ α2 . We compute Θ α1⊗α2 as the synchronized product Θ α1 ⊗ Θ α2 . This is a standard operation, its state space being S α1 × S α2 , with a transition from (s 1 , s 2 ) to

(s ′ 1 , s ′ 2 ) via label l iff (s 1 , l, s ′ 1 ) ∈ T α1 and (s 2 , l, s ′ 2 ) ∈ T α2 . For this to be correct, i.e., to have Θ α1 ⊗ Θ α2 = Θ α1⊗α2 , the constraint V 1 ∩ V 2 = ∅ is required.
Namely, this constraint ensures that α 1 and α 2 are orthogonal in the sense of [START_REF] Helmert | [END_REF], meaning basically that there exists no variable on whose value both abstractions depend. Then: Theorem 2.2 [START_REF] Helmert | [END_REF] Let Θ be the state space of a planning task, and let α 1 and α 2 be orthogonal abstractions of Θ.

Then Θ α1 ⊗ Θ α2 = Θ α1⊗α2 .
In practice, we need a merging strategy deciding which abstractions to merge in (iii), and a shrinking strategy deciding which (and how many) states to aggregate in (ii). Helmert et al. do not investigate this in detail. Our main issue herein is with their shrinking strategy. This aggregates states until a size limit N -an input parameter -is reached. The strategy is based exclusively on the initial state and goal distances in the abstract state space at hand; it is f -preserving in that (if possible) it aggregates states only if they agree on these 1 Helmert et al. do not state Proposition 2.1 (or Theorem 2.2 below) in this form, but they follow trivially from their discussion. v1, . . . , vn := an ordering of V α := πv 1 , Θα := Θ πv 1 /* rule (i) */ σ 1 := function projecting operators onto {v2, . . . , vn} apply σ 1 to transition labels in Θα for i := 2, . . . , n do α distances. This strategy preserves distances locally -in the abstraction at hand -but does not take into account at all the global impact of aggregating states. For example, in a transportation domain, if we consider only the position of a truck, then any states s, t equally distant from the truck's initial and target position can be aggregated: locally, the difference is irrelevant. Globally, however, there are transportable objects to which the difference in truck positions does matter, and thus aggregating s and t results in information loss. Similar situations occur in Gripper, thus the heuristic computed is not perfect although, theoretically, it could be. The variable ordering v 1 , . . . , v n will be defined by the merging strategy (a simple heuristic, cf. Section 8). Note that the merging strategy is linear, i.e., α ′ is always atomic in the application of rule (iii). Iterating over v 1 , . . . , v n , the algorithm maintains an abstraction α, along with the transition system Θ α , as described earlier. In this way, M&S-bop is a straightforward instance of the M&S framework. Its distinguishing features are (a) the label reduction functions σ i that remove operator preconditions/effects pertaining to variables indexed ≤ i, and (b) coarsest bisimulation over the thus label-reduced abstract state spaces. (b) defines the shrinking strategy, which is influenced by (a) because reducing labels changes the bisimulation. Reducing labels may also change the outcome of the synchronized product (rule (iii)), therefore (a) endangers the correctness of Θ α relative to Θ α .

′ := πv i , Θ α ′ := Θ πv i /* rule (i) */ apply σ i-1 to transition labels in Θ α ′ α := α ⊗ α ′ , Θα := Θα ⊗ Θ α ′ /*

M&S-bop Overview

In the following three sections, we fill in the formal details on (a) and (b), proving (in particular) that the abstraction heuristic h α of α as returned by M&S-bop is perfect, and can be extracted from the returned transition system Θ α . We begin by defining bisimulation, and pointing out some basic facts about its behavior in the M&S framework. We then formally define label reduction and the conditions under which it preserves the correctness of Θ α . We finally point out that the two techniques can be combined fruitfully.

Bisimulation

Bisimulation is a well-known criterion under which abstraction does not significantly change the system behavior. Namely, let Θ = (S, L, T, s 0 , S ⋆ ) be a transition system. An equivalence relation ∼ on S is a bisimulation for Θ if: (1) s ∼ t implies that either s, t ∈ S ⋆ or s, t ∈ S ⋆ ; (2) for every pair of states s, t ∈ S so that s ∼ t, and for every transition label l ∈ L, if (s, l, s ′ ) ∈ T then there exists t ′ s.t. (t, l, t ′ ) ∈ T and s ′ ∼ t ′ . Intuitively, (1) s and t agree on the status of the goal, and (2) whatever operator applies to s applies also to t, leading into equivalent states. An abstraction α is a bisimulation iff the induced equivalence relation ∼ α is.

For a comprehensive treatment of bisimulation, see the work by Milner [1990]. There always exists a unique coarsest bisimulation, i.e., a bisimulation that contains all other bisimulations. The coarsest bisimulation can be computed efficiently, in a bottom-up process starting with a single equivalence class containing all states, then iteratively separating non-bisimilar states. This process can be used as a shrinking strategy, and it preserves solution distance at the local level: Proposition 4.1 Let Θ be a transition system, and let α be a bisimulation for Θ. Then h α is perfect.

This holds because abstract solution paths are real solution paths. Consider some state t, and an abstract solution for t. Say the abstract solution starts with the transition (A, l, A ′ ), where A and A ′ are abstract states. Since (A, l, A ′ ) is a transition in Θ α , there exist states s ∈ A and s ′ ∈ A ′ so that (s, l, s ′ ) is a transition in Θ. By construction, we have α(t) = A = α(s) and thus s ∼ α t. Thus, by bisimulation property (2), we have a transition (t, l, t ′ ) in Θ where s ′ ∼ α t ′ , i.e., α(t ′ ) = α(s ′ ) = A ′ . In other words, there exists a transition from t taking us into the desired state subset A ′ . Iterating the argument, we can execute all transitions on the abstract solution for t. The last state t ′ reached this way must be a solution state because of bisimulation property (1) and the fact that α(t ′ ) is a solution state in Θ α .

Note that the argument we just made is much stronger than what is needed to prove that h α is perfect -we preserve the actual solutions, not only their length. That is exactly what we will exploit further below. First, note that Proposition 4.1 tells us nothing about what will happen if we interleave bisimulation with merging steps. This works, too: Corollary 4.2 Let Θ be the state space of a planning task with variables V. Let α be an M&S abstraction over V ⊆ V constructed so that, in any application of rule (ii), γ is a bisimulation for Θ β . Then α is a bisimulation for Θ πV . This can be shown by induction over rules (i)-(iii). The claim is obvious for atomic α. Induction over rule (ii) is easy by exploiting a transitivity property of bisimulations. For rule (iii), assume that α 1 is a bisimulation for Θ πV 1 , and α 2 is a bisimulation for Θ πV 2 . Since Θ πV 1 and Θ πV 2 are orthogonal, by Theorem 2.2 their synchronized product is equal to Θ πV 1 ⊗πV 2 which is isomorphic with Θ πV 1 ∪V 2 . We can apply α 1 and α 2 to the states in Θ πV 1 ∪V 2 (applying their component atomic projections to partial states), and it is easy to see that the bisimulation property is preserved. 2 By Corollary 4.2 and Proposition 4.1, if we always stick to bisimulation during step (ii), then we obtain a perfect heuris-2 Dräger et al. [2006] mention a result similar to Corollary 4.2. The result is simpler in their context because, there, the overall state space is defined in terms of the synchronized product operation. tic. Alas, in practical examples there rarely exist compact bisimulations. For example, in Gripper, the perfect abstraction of Figure 1 is not a bisimulation. If s and t agree on the number of objects in a room, this does not imply that they agree on the operators needed to transport them. For example, s and t as indicated in Figure 1 require to pick up O 2 (s) vs. O 1 (t). Thus the transition labels into the equivalent states (right neighbors in Figure 1) are different, violating property (2). Indeed, it is easy to see that the size of bisimulations in Gripper is exponential in the number of objects.

Motivated by the size of bisimulations, Dräger et al. [2006] propose a more approximate shrinking strategy that we will call the DFP shrinking strategy. When building the coarsest bisimulation, the strategy keeps separating states until the size limit N is reached. The latter may happen before a bisimulation is obtained, in which case we may lose information. The strategy prefers to separate states close to the goal, thus attempting to make errors only in more distant states where the errors will hopefully not be as relevant.

The DFP shrinking strategy is not a bad idea; some of the strategies we experiment with herein are variants of it. However, before resorting to approximations, there is a more fundamental issue we can improve. As noted in the proof of Proposition 4.1, bisimulation preserves solution paths exactly. This suits its traditional purpose in model checking. For computing a perfect heuristic, however, it suffices to preserve solution length. In bisimulation property (2), we can completely ignore the transition labels. This makes all the difference in Gripper. States s and t in Figure 1 can reach the same equivalence classes, but using different labels. Ignoring the latter, s and t are bisimilar. Indeed, the perfect abstraction of Figure 1 is such a fully label-reduced bisimulation.

Label Reduction

Unfortunately, full label reduction cannot be applied within the M&S framework, at least not without significant information loss during the merging step. Figure 3 shows the atomic projections of our running example from Figure 1. For simplicity, we omit F and show the two variables O 1 and O 2 in terms of a single generic variable O. Consider the transition label l = ({R = A, O = A}, {O = R}) picking up the object in room A. This transitions O from A to R in Θ πO (right hand side), but does not affect R and hence labels only a self-loop in Θ πR (left hand side). Hence, in the synchronized system Θ πR ⊗ Θ πO , as desired the robot does not move while loading the object. If we ignore the difference between l and the label l ′ = ({R = A}, {R = B}) moving R, however, then the synchronized system may apply l and l ′ together, acting as if they were the result of applying the same operator. Thus we may move and pick-up at the same timea spurious transition not present in the original task.

We now derive a way of reducing subsets of labels during M&S, so that no spurious transitions are introduced, and thus the correctness of Θ α relative to Θ α is preserved. We remark that a simpler version of the technique, pertaining only to linear merging strategies, was implemented already in the initial version of M&S reported by [START_REF] Helmert | [END_REF]; the technique has not yet been described anywhere.

Let Θ = (S, L, T, s 0 , S ⋆ ) be a transition system. A label reduction is a function τ mapping L to a label set L τ . We associate τ with the reduced transition system Θ| τ := (S, L τ , T | τ , s 0 , S ⋆ ) where T | τ := {(s, τ (l), s ′ ) | (s, l, s ′ ) ∈ T }. Labels l 1 , l 2 ∈ L are equivalent in Θ if, for every pair of states s, s ′ ∈ S, (s, l 1 , s ′ ) ∈ T if and only if (s, l 2 , s ′ ) ∈ T . We say that τ is conservative for Θ if, for all l 1 , l 2 ∈ L, τ (l 1 ) = τ (l 2 ) only if l 1 and l 2 are equivalent. Such label reduction is distributive with the synchronized product: Lemma 5.1 Let L be a set of labels, let Θ 1 and Θ 2 be transition systems using L, and let τ be a label reduction on L. If

τ is conservative for Θ 2 , then Θ 1 | τ ⊗ Θ 2 | τ = (Θ 1 ⊗ Θ 2 )| τ .
For illustration, consider the labels l = ({R = A, O = A}, {O = R}) and l ′ = ({R = A}, {R = B}) discussed at the start of this section. These are not equivalent in Θ πO (Figure 3 right), and if τ (l) = τ (l ′ ) then, as discussed,

Θ πR | τ ⊗ Θ πO | τ = (Θ πR ⊗ Θ πO )| τ in contrast to Lemma 5.1.
We apply conservative label reduction within M&S by, when considering an abstraction over variable subset V , applying a label reduction conservative for the other variables V \ V . A key issue here is that one cannot "reduce in opposite directions". To illustrate, say Θ 1 (variables V ) has the single label l 1 and Θ 2 (variables V \ V ) has the single label l 2 = l 1 . Then Θ 1 ⊗ Θ 2 contains no transitions at all. However, mapping all labels to some unique symbol r is conservative for each of Θ 1 and Θ 2 . If we synchronize the systems after this reduction, we obtain a transition between every pair of states.

To avoid said difficulties, we apply label reduction upwards in a sequential ordering of the variables (given by the merging strategy). Let V ⊆ V, and let v 1 , . . . , v n be an ordering of V . We say that an M&S abstraction α over V allows v 1 , . . . , v n if α is constructed so that, in any application of rule (iii), there exist i, j, k so that V 1 = {v i , . . . , v j } and V 2 = {v j+1 , . . . , v k }. In other words, the construction of α corresponds to a tree whose leaves are ordered v 1 , . . . , v n .

Let

σ n • • • • • σ 1 be a chain of label reductions for Θ. We denote τ >i := σ i • • • • • σ 1 . We say that σ n • • • • • σ 1 is conservative for v 1 , . . . , v n if, for each 1 ≤ i < n, τ >i
is conservative for each of Θ πv i+1 , . . . , Θ πv n . Note that the last reduction σ n is not restricted at all, and may thus be a full label reduction mapping all labels to the same unique symbol.

In practice, the label reductions σ i we use are those from M&S-bop (cf. Figure 2), projecting operators onto {v i+1 , . . . , v n }, i.e., removing any preconditions/effects pertaining to the variables v 1 , . . . , v i that have already been merged. This chain of label reductions is conservative: Proposition 5.2 Let Θ be the state space of a planning task with variables V. Let V ⊆ V, and let v 1 , . . . , v n be an ordering of V . Then operator projection is conservative for v 1 , . . . , v n , and is maximal among all chained label reductions with this property.

For the first part of the claim, we need τ >i = σ i to be conservative -map only equivalent labels (pre, eff), (pre ′ , eff ′ ) to the same label -for each of Θ πv i+1 , . . . , Θ πv n . This holds because (*) (pre, eff) and (pre ′ , eff ′ ) are equivalent in Θ πv j if and only if their projection onto v j is identical. The second part of the claim, maximality, holds in that τ >i maps all equivalent labels to the same label. This follows from the "only if" direction in (*).

Say that in our running example (omitting F ) the variable order is R, O 1 , O 2 , . . . , O n . Consider again the labels l = ({R = A, O = A}, {O = R}) and l ′ = ({R = A}, {R = B}). For i = 1, the robot move l ′ is projected onto τ >1 (l ′ ) = (∅, ∅), ignoring the information about the robot position. However, τ >1 (l) = ({O = A}, {O = R}), so τ >1 (l) = τ >1 (l ′ ) as desired. On the other hand, for i > 1 and every j ≤ i, all labels in Θ πO j will be mapped to (∅, ∅) (compare Figure 3 right), so that the differences between any "already merged" objects will effectively be ignored. For i = n, all labels are mapped to (∅, ∅) so the label reduction is full.

With conservative label reductions, for α that allows v 1 , . . . , v n , we can maintain Θ α during M&S similarly as before. Namely, the transition system associated with α, written Θ τ α , is constructed using these rules:

(i) If α = π vi for a variable v i ∈ V , then Θ τ α := Θ πv i if i = 1, and Θ τ α := Θ πv i | τ >i if i = 1. (ii) If α = γ • β where β is an M&S abstraction and γ is a function on S β , then Θ τ α := (Θ τ β ) γ . (iii) If α = α 1 ⊗ α 2 where α 1 (α 2 ) is an M&S abstraction of Θ over V 1 = {v i , . . . , v j } (V 2 = {v j+1 , . . . , v k }), then Θ τ α := Θ τ α1 ⊗ Θ τ α2 if i = 1, and Θ τ α := (Θ τ α1 ⊗ Θ τ α2 | τ >j )| σ k •••••σ j+1 if i = 1.
In words, we apply label reduction only if the underlying variable set V starts at the first variable v 1 , and we choose the reduction pertaining to the last variable in V . This construction is correct relative to Θ α , in the following sense: Theorem 5.3 Let Θ be the state space of a planning task with variables V. Let V ⊆ V, and let v 1 , . . . , v n be an ordering of V . Let σ n • • • • • σ 1 be a chained label reduction for Θ that is conservative for v 1 , . . . , v n , and let α be an M&S abstraction over V that allows v 1 , . . . , v n . Then Θ τ α = Θ α | τ >n . Note here that "the correctness of Θ α relative to Θ α " is now interpreted in a different way. The transition system Θ τ α we maintain is no longer equal to the abstract state space Θ α , but instead to the label-reduced version Θ α | τ >n of that abstract state space. Since, obviously, the labels are irrelevant for h α , the heuristic computed is the same.

The proof of Theorem 5.3 is a bit technical, but essentially simple. We prove by induction over the construction of α that, for any intermediate abstraction β over {v i , . . . , v j },

Θ τ β = Θ β if i = 1, and Θ τ β = Θ β | τ >j if i = 1.
The key step is induction over rule (iii) when i = 1. Since τ >j is conservative for each of Θ πv j+1 , . . . , Θ πv k , we can easily conclude that τ >j is conservative for Θ τ α2 . The claim then follows by applying Lemma 5.1 and Theorem 2.2.

Summing up, whenever during M&S we face an abstraction over variables v 1 , . . . , v j , we can project the operators labeling the transitions onto the remaining variables v j+1 , . . . , v n . We then still obtain the correct (label-reduced) abstract state space. In the initial implementation of [START_REF] Helmert | [END_REF], the motivation for doing so was the reduced number of labels -planning tasks often contain many operators, so this was time-and space-critical. Here, we observe that label reduction favorably interacts with bisimulation.

Bisimulation and Label Reduction

Label reduction obviously preserves Proposition 4.1: Proposition 6.1 Let Θ be a transition system, τ be a label reduction, and α a bisimulation for Θ| τ . Then h α is perfect. Proposition 6.1 is important because, as shown by our running example, label reduction may make a big difference: Proposition 6.2 There exist families F of transition systems Θ with associated label reductions τ so that the coarsest bisimulation for Θ| τ is exponentially smaller than the coarsest bisimulation for Θ.

Corollary 4.2 tells us that, if the shrinking strategy sticks to bisimulation of the original (non label-reduced) abstract state spaces, then the final outcome will be a bisimulation. Does a similar result hold if we stick to bisimulation of the label-reduced abstract state spaces? Unsurprisingly, the answer is "yes". Given variables v 1 , . . . , v n and a chained label reduction σ n •• • ••σ 1 , we say that α is constructed by labelreduced bisimulation if it is constructed so that, in any application of rule (ii) where β is over the variables {v i , . . . , v j }:

if i = 1 then γ is a bisimulation for Θ β ; if i = 1 then γ is a bisimulation for Θ β | τ >j .
By combining the proofs of Corollary 4.2 and Theorem 5.3, we get: Theorem 6.3 Let Θ be the state space of a planning task with variables V. Let V ⊆ V, and let v 1 , . . . , v n be an ordering of V . Let σ n • • • • • σ 1 be a chained label reduction for Θ that is conservative for v 1 , . . . , v n , and let α be an M&S abstraction constructed by label-reduced bisimulation. Then α is a bisimulation for Θ πV | τ >n . By Theorem 6.3 and Proposition 6.1, if α is constructed by label-reduced bisimulation, then h α is perfect. With Proposition 5.2, this hold for α as returned by M&S-bop. By Theorem 5.3 we can maintain the suitable abstract state spaces. In particular, h α can be extracted from M&S-bop's returned transition system Θ α . We will see next that M&S-bop has polynomial runtime in quite a number of benchmarks.

Domain-Specific Performance Bounds

We measure the performance of M&S-bop in terms of bounds on abstraction size, i.e., the number of abstract states. Runtime is a polynomial function of abstraction size. We express the bounds as functions of domain parameters like the number of objects. Polynomial bounds on abstraction size are possible only in domains with polynomial-time optimal solution algorithms. Helmert [2006] identifies six such domains in the IPC benchmarks: Gripper, Movie, PSR, Schedule, and two variants of Promela. [START_REF] Helmert | [END_REF] state that for each of these except PSR there exist suitable merging and shrinking strategies, but do not provide a way to come up with such strategies automatically. We begin with an easy result: Proposition 7.1 Let P = {Π n } be the family of Gripper respectively Ext-Movie planning tasks, where n is the number of objects respectively snacks. Then, for any merging strategy, abstraction size for M&S-bop in P is bounded by a cubic respectively linear function in n.

Ext-Movie is an extended version of Movie, allowing to scale the number of snacks. Both results hold because the M&S-bop shrinking strategy aggregates states that agree on the relevant object counts (number of objects in a room, number of snacks already obtained). It should be noted that label reduction is really needed here -in both domains, non-labelreduced bisimulations are exponentially large. The same holds true for all domains discussed below.

We next consider scheduling-like domains, where each task consists of some machines used to change the features f (o) of processable objects o. The relevant property is that, for o o ′ , f (o) and f (o ′ ) are mutually independent, i.e., not affected by any common operator -processing an object may affect the status of the machines but does not have immediate consequences for any other object. It is easy to see that the STRIPS variant Schedule-Strips of IPC'00 Schedule is a scheduling-like domain. We thus have: Proposition 7.2 Let P = {Π n } be the family of Schedule-Strips planning tasks, where n is the number of processable objects. There exists a merging strategy so that abstraction size for M&S-bop in P is bounded by a polynomial in n.

For Promela, this investigation is difficult because M&Sbop depends directly on task syntax, and the IPC'04 Promela domains are syntactically very complicated (compiled from Promela into an expressive PDDL dialect). For a straightforward direct encoding of one of the domains (Dining Philosophers), we found that M&S-bop exhibits exponential behavior. However, a variant that we tentatively named greedy bisimulation gives a polynomial bound. Greedy bisimulation demands bisimulation property (2) only for transitions l, s ′ ) where sd (s ′ ) ≤ sd (s). Under certain additional conditions on the planning task -which hold in Dining Philosophers -greedy bisimulation results in a perfect heuristic.

Of course, M&S-bop is not omnipotent. For example, say we extend Gripper by scaling the number of robot hands. Then, for any merging strategy, there exists a shrinking strategy so that abstraction size is polynomially bounded. However, M&S-bop does not have such a bound. Robot hands H appear as object-variable values ("O = H") in the effect of pick-up operators. So, unless all object variables were already merged, operator projection does not remove these distinctions, and states using different hands are not bisimilar.

Experiments

In most benchmark domains, coarsest bisimulations are still large even under operator projection. We thus designed a family of (mostly) more approximate shrinking strategies. The family is characterized by 3 parameters: (1) overall scheme, (2) bisimulation variant, (3) label reduction on/off. For (1), the options are DFP shrinking strategy with abstraction size limit N vs. coarsest bisimulation without size limit. The former will be indicated by "DFP" in the strategy's name, total number of tasks for which computing the M&S abstraction did not exceed the available time/memory. the latter will be indicated by "M&S-". For (2), the options are bisimulation vs. greedy bisimulation. The strategy name is extended with "b" respectively "g". In (3), we do vs. do not use operator projection. If we do, "op" is attached to the name. In the DFP-g options, we use greedy bisimulation only if bisimulation would break the size limit. Our merging strategy is linear, and follows Fast-Downward's "level heuristic". This orders variables "closest to the root of the causal graph" up front, so that, in operator projection, the most influential variables are projected away earlier on. We experiment with: the previous M&S heuristic HHH [START_REF] Helmert | [END_REF]; LM-cut [START_REF] Helmert | Malte Helmert and Carmel Domshlak. Landmarks, critical paths and abstractions: What's the difference anyway?[END_REF], the currently leading heuristic for optimal planning; and structural patterns (SP) [START_REF] Katz | [END_REF], a competitive heuristic related to ours in that it is based on (implicit) abstract state spaces. Our implementation is on top of Fast-Downward, with the same A * implementation for all heuristics. We ran all IPC benchmarks supported by LMcut and HHH. The experiments were performed on dual-CPU Opteron 2384 machines, running eight experiments simultaneously in order to fully utilize the available (eight-core) machines. Each planner instance ran on a single core with a time limit of 30 minutes and a memory limit of 2 GB.

Different shrinking strategies sometimes result in complementary strengths (better performance in different domains). Thus we experimented also with all hybrid planners running any two of these strategies, sequentially with a 15 minute limit for each. The best, in terms of total coverage, of these 2-option combinations runs M&S-gop, and DFP-gop with N=200K. This is simply called "Hybrid" in what follows.

Table 1 gives the coverage data. Consider first the "no bound on N " columns on the right hand side. Comparing M&S-b with M&S-bop, we see that operator projection improves performance significantly. Recall that the heuristic in both cases is guaranteed to be perfect, so no actual search is needed in the 192 tasks where M&S-bop succeeds. The effect of using greedy bisimulation (which in general forfeits this guarantee) is dramatic. Note in particular that the number of instances where the abstraction can be built completely -without any size bound -goes up to 802. Interestingly, the effect of the parameter changes is reversed when using DFP: there, operator projection has a much larger impact on performance than greedy bisimulation.

DFP-bop dominates DFP-b (solves at least as many tasks) in 65 of the 66 combinations of domain and N value. DFPgop dominates HHH in the total, and in 50 of these combinations; Hybrid dominates HHH in 64 combinations. SP is more competitive, but is inferior in the total to Hybrid as well as to DFP-bop and DFP-gop with N = 10K. LMcut clearly dominates the total, but this is largely due to Miconic-STRIPS, where LM-cut delivers an exceptionally high-quality heuristic. Disregarding this domain, Hybrid solves 1 more task than LM-cut. In 11 of the 22 domains, Hybrid is one of the top performers, and in 4 more domains, only one task separates it from the top performer.

Coverage is a function of the trade-off between the quality of a heuristic, and the effort needed for computing it. Due to the multitude of domains and algorithms tested, it is beyond the scope of this paper to give detailed data. We provide a summary using [START_REF] Richter | [END_REF]'s expansions score (E) and score (T ). Both range between 0 and 100, for each individual instance. E = 100 if ≤ 100 expansions were made, E = 0 if ≥ 1, 000, 000 expansions were made. In between, E interpolates logarithmically, so that an additive difference of 7.53 in scores corresponds to a factor 2. Similarly, T = 100 for runtimes ≤ 1 second, T = 0 for time-outs, and doubling the runtime decreases the score by about 9.25. The advantage of these scores is that they are absolute, i.e., there is no need to restrict the set of instances considered to those solved by all planners. 3.7 -1.7 driverlog 1.9 1.2 mystery 9.2 33.6 gripper 40.6 25.7 pipesnota 10.2 48.2 gripper 41.9 30.2 freecell 0.5 33.6 mystery 0.4 5.2 mystery 1.2 -0.2 blocks 7.9 5.5 satellite

Figure 2 :

 2 Figure 2: Overview of M&S-bop algorithm.distances. This strategy preserves distances locally -in the abstraction at hand -but does not take into account at all the global impact of aggregating states. For example, in a transportation domain, if we consider only the position of a truck, then any states s, t equally distant from the truck's initial and target position can be aggregated: locally, the difference is irrelevant. Globally, however, there are transportable objects to which the difference in truck positions does matter, and thus aggregating s and t results in information loss. Similar situations occur in Gripper, thus the heuristic computed is not perfect although, theoretically, it could be.

Figure 2

 2 Figure 2 outlines our algorithm computing perfect heuristics, M&S-bop (M&S with bisimulation and operator pruning).The variable ordering v 1 , . . . , v n will be defined by the merging strategy (a simple heuristic, cf. Section 8). Note that the merging strategy is linear, i.e., α ′ is always atomic in the application of rule (iii). Iterating over v 1 , . . . , v n , the algorithm maintains an abstraction α, along with the transition system Θ α , as described earlier. In this way, M&S-bop is a straightforward instance of the M&S framework. Its distinguishing features are (a) the label reduction functions σ i that remove operator preconditions/effects pertaining to variables indexed ≤ i, and (b) coarsest bisimulation over the thus label-reduced abstract state spaces. (b) defines the shrinking strategy, which is influenced by (a) because reducing labels changes the bisimulation. Reducing labels may also change the outcome of the synchronized product (rule (iii)), therefore (a) endangers the correctness of Θ α relative to Θ α .In the following three sections, we fill in the formal details on (a) and (b), proving (in particular) that the abstraction heuristic h α of α as returned by M&S-bop is perfect, and can be extracted from the returned transition system Θ α . We begin by defining bisimulation, and pointing out some basic facts about its behavior in the M&S framework. We then formally define label reduction and the conditions under which it preserves the correctness of Θ α . We finally point out that the two techniques can be combined fruitfully.

Figure 3 :

 3 Figure 3: Atomic projections in (simplified) Gripper.

Table 1 :

 1 Comparison of solved tasks over 22 IPC benchmark domains. Best results are highlighted in bold. "Total M&S built":

	Domain	Hybrid LM-cut SP	N=10K DFP-b DFP-bop DFP-gop HHH DFP-b DFP-bop DFP-gop HHH DFP-b DFP-bop DFP-gop HHH M&S-b M&S-bop M&S-gop N=100K N=200K No bound on N
	airport	22	28 21	23	23	23	19	15	15	15	13	11	11	11	12	1	1	22
	blocks	21	28 21	21	21	21	18	18	18	18	19	18	18	18	19	6	6	21
	depots	7	7 7	7	7	7	7	7	7	7	3	5	6	6	3	1	1	7
	driverlog	13	13 13	12	13	13	12	12	12	13	13	12	12	13	14	4	5	12
	freecell	16	15 16	15	16	16	15	4	6	6	9	4	3	3	6	3	3	16
	grid	3	2 1	1	2	2	2	1	3	3	2	0	3	3	0	0	0	2
	gripper	20	7 7	7	11	11	7	7	20	20	7	7	20	20	7	6	20	7
	logistics00	20	20 22	20	20	20	16	20	20	20	21	20	20	20	22	10	10	16
	logistics98	5	6 6	4	4	4	5	5	5	5	5	5	5	5	5	2	1	4
	miconic	67	141 53	55	56	56	55	55	65	65	55	55	67	67	56	40	56	50
	mprime	23	22 23	18	19	19	21	8	12	12	14	4	9	9	9	1	1	23
	mystery	15	16 15	13	13	13	14	7	8	8	11	6	6	6	7	2	3	15
	openstacks	7	7 7	7	7	7	7	7	7	7	7	7	7	7	7	7	7	7
	pathways	4	5 4	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4
	pipesworld-notank	15	17 14	15	17	17	9	9	9	9	2	6	6	6	0	2	2	15
	pipesworld-tank	16	11 10	13	14	14	13	7	8	8	7 45	50
	rovers	8	7 6	6	7	7	7	7	8	8	7	6	8	8	7	4	4	6
	satellite	7	7 6	6	6	6	6	6	7	7	6	6	7	7	6	4	6	6
	tpp	7	6 6	6	6	6	6	6	7	7	6	6	7	7	6	5	5	6
	trucks	7	10 7	6	7	7	6	5	7	7	6	5	7	7	6	4	4	6
	zenotravel	11	13 11

Experimenting with such summaries, we found that they often misrepresented the results. For example, on instances solved by both, M&S-gop beats LM-cut even in some domains where LM-cut

23.7 8.8 blocks 8.6 14.7 openstack 21.9 9.7 gripper -0.7 5.3 log98 -0.6 0.1 psr 0.8 0.2 depots 1.6 10.4 pipesnota 21.7 28.1 mystery 3.5 27.0 pipesnota 8.1 14.6 psr -1.1 4.5 openstack -0.8 -0.4 rovers 0.5 0.7 mprime 1.1 38.2 pathways 13.7 3.9 airport 2.2 21.5 freecell 4.1 5.9 pipesnota -2.1 36.4 log00 -0.9 -0.9 freecell 0.5 0.4 psr -2.0 3.0 pipestank 9.3 21.5 depots 1.6 14.1 log00 3.6 2.7 openstack -6.6 11.5 psr -1.0 0.9 log98 0.4 0.7 freecell -3.1 28.1 airport 8.4 0.0 freecell -0.5 27.0 satellite 2.4 -5.8 blocks -14.0 -10.1 airport -1.0 -0.7 satellite 0.3 -0.5 airport -6.2 22.2 grid 7.3 10.3 pipestank -0.7 43.2 psr 1.6 1.7 tpp -15.3 -4.5 rovers -1.3 -5.4 pipestank 0.3 -0.8 log98 -8.4 -5.6 miconic 6.1 2.0 mprime -1.0 27.7 tpp -2.2 -9.4 pipestank -17.0 3.7 depots -1.6 0.1 pipesnota 0.2 -0.1 driverlog -9.0 4.2 zenotravel 4.9 3.0 gripper -2.0 0.8 pipestank -5.6 -16.3 depots -19.8 14.9 trucks -4.1 -4.9 tpp 0.1 0.5 rovers -9.5 -7.3 trucks 3.4 4.5 grid -3.8 5.8 driverlog -9.3 -1.8 driverlog -20.3 1.2 freecell -4.2 3.7 trucks 0.1 -0.1 pipestank -10.0 21.7 freecell 3.1 -0.6 trucks -6.8 0.1 grid -9.5 9.9 grid -20.6 5.4 tpp -4.4 -1.9 log00 0.1 -0.2 trucks -10.1 -4.5 rovers 1.1 1.9 zenotravel -6.9 -6.4 rovers -13.5 -7.7 mystery -21.5 2.5 zenotravel -6.8 -13.9 0.1 -0.5 grid -11.1 -4.0 blocks 0.2 8.7 miconic -7.2 -3.1 zenotravel -15.6 -1.8 mprime -23.1 9.0 driverlog -6.9 -2.4 airport 0.0 0.7 pipesnota -11.2 19.2 openstack 0.1 1.4 rovers -8.9 -6.2 pathways -15.8 -16.1 rovers -23.5 -15.8 miconic -7.7 -2.2 grid 0.0 0.6 zenotravel -11.6 -9.9 depots -0.3 4.1 pathways -12.4 8.8 depots -21.7 4.8 log00 -24.9 -9.5 pipestank -7.9 -2.3 miconic 0.0 0.1 tpp -12.9 -3.5 tpp -0.4 -0.1 psr -13.0 0.6 blocks -22.4 -16.1 zenotravel -27.4 -11.2 pipesnota -9.4 2.9 gripper 0.0 0.0 miconic -13.4 -5.0 mprime -2.1 -10.6 log98 -13.3 -8.8 mprime -24.2 -29.3 satellite -38.9 -16.5 mprime -10.4 0.2 mprime 0.0 -0.1 log00 -21.1 -12.5 driverlog -4.4 -3.6 tpp -13.4 -4.2 mystery -29.5 -31.3 airport -39.2 -15.3 pathways -11.0 -1.7 openstack 0.0 -0.1 pathways -26.1 4.7 mystery -4.5 -6.9 driverlog -15.4 -0.6 trucks -31.9 -20.6 pathways -41.9 -11.2 grid -11.2 -23.8 pathways 0.0 -0.1 openstack -28.5 1.8 log98 -4.9 -3.4 satellite -17.5 -1.9 airport -33.0 -36.8 trucks -42.1 -25.0 satellite -28.1 -10.5 depots -0.3 0.4 satellite -41.0 -11.2 log00 -6.8 4.2 log00 -28.1 -8.1 log98 -47.5 -24.4 log98 -55.9 -29.8 gripper -37.6 -25.7 blocks -0.5 -0.5 gripper -42.6 -24.9 psr -10.3 2.2 openstack -28.5 2.1 miconic -66.5 -56.8 miconic -80.0 -61.9 Total -6.9 -3.

Table 2 considers 7 pairs of heuristics X, Y . The 3 pairs in the left part illustrate the differences between the shrinking strategies proposed herein. We do not include M&S-b and M&S-bop because their expansions behavior is not interesting: they either have perfect expansions, or fail. Comparing X = DFP-bop to Y = DFP-b, we clearly see the advantage of operator projection. E(Y ) -E(X) is negative for 20 of 22 domains, meaning that X has fewer expansions. The picture is not quite as clear for runtime because DFP-bop sometimes generates more overhead (taking more time to reach the size limit N ). Comparing X = DFP-bop to Y = DFP-gop, we clearly see that the performance difference is very small. By contrast, X = DFP-bop vs. Y = M&S-gop exhibits a huge variance, showing their complementary strengths. This reflects the fact that these two strategies are quite different. M&S-gop enforces bisimulation only on "sd (s ′ ) ≤ sd (s)" transitions, but on all of those; DFP-variants enforce bisimulation everywhere but drop it completely if N is exceeded. The former has the edge in heuristic quality (E(Y )-E(X) is negative for 18 domains), the latter is better in total runtime since building the abstraction generates less overhead (e.g., consider the pipesworld-notankage domain).

The middle and right parts of Table 2 show the competition with HHH respectively LM-cut. DFP-gop clearly beats HHH in expansions, and it largely keeps this advantage in runtime. M&S-gop most often produces worse heuristics than HHH, but with less overhead and thus better runtime. As for LM-cut, without any doubt this remains the most informative heuristic here -only in a few domains does DFP-gop manage to beat it. Everywhere else, the question is whether the faster heuristic calls for M&S (amortizing the cost for creating the abstraction in the first place) make up for the larger search space. For DFP-gop, this is the case only in depots. For M&S-gop, this happens in 11 of the domains, and partly to a considerable extent (e.g. freecell, blocks, depots, mprime).

actually scales better -because M&S-gop's cheap heuristic solves the small tasks very quickly, and times out on the larger ones.

Future Work

Our immediate future work concerns greedy bisimulation. First results suggest that there are many other interesting bisimulation variants along these lines, and corresponding conditions under which they yield perfect heuristics. The guiding idea is to test conditions on the degree and form of interactions between the current variable and the remaining ones, using the outcome to fine-tune the subset of transitions for which bisimulation property (2) is demanded.