This page contains the description of the competition domains for the satisfying, optimal and multi-core tracks. For each domain the characteristics of the selected problems are shown. For the sake of comparisons, we have used the same problems in the sequential multi-core and in the sequential satisficing tracks. The domains used are:

*other fluents apart from total-cost are defined

Barman

Author: Sergio Jiménez Celorrio.

In this domain there is a robot barman that manipulates drink dispensers, glasses and a shaker. The goal is to find a plan of the robot's actions that serves a desired set of drinks. In this domain deletes of actions encode relevant knowledge given that robot hands can only grasp one object at a time and given that glasses need to be empty and clean to be filled.

For the satisficing track 4 problems for each configuration have been created:

For the optimal track 4 problems for each configuration have been created:

Elevators

From the original description of this domain (click here):

The idea for this domain came up from the Miconic domain of IPC2, however the domain has been designed from scratch. The scenario is the following: There is a building with N+1 floors, numbered from 0 to N. The building can be separated in blocks of size M+1, where M divides N. Adjacent blocks have a common floor. For example, suppose N=12 and M=4, then we have 13 floors in total (ranging from 0 to 12), which form 3 blocks of 5 floors each, being 0 to 4, 4 to 8 and 8 to 12.

The building has K fast (accelerating) elevators that stop only in floors that are multiple of M/2 (so M has to be an even number). Each fast elevator has a capacity of X persons. Furthermore, within each block, there are L slow elevators, that stop at every floor of the block. Each slow elevator has a capacity of Y persons (usually Y<X).

There are costs associated with each elevator starting/stopping and moving. In particular, fast (accelerating) elevators have negligible cost of starting/stopping but have significant cost while moving. On the other hand, slow (constant speed) elevators have significant cost when starting/stopping and negligible cost while moving.

Traveling times between floors are given for any type of elevator, taking into account the constant speed of the slow elevators and the constant acceleration of the fast elevators.

There are several passengers, for which their current location (i.e. the floor they are) and their destination are given. The planning problem is to find a plan that moves the passengers to their destinations while it maximizes some criterion.

In the sequential tracks the objective function is to minimize the total cost of moving the passengers to their destinations. The total cost is increased each time an elevator starts/stops or moves.

For the satisficing track, in the 2008 competition, problems ranged from 9 floors, 4 passengers, and 4 elevators (2 fast, 2 slow) to 25 floors, 39 passengers, and 5 elevators (2 fast, 3 slow). Initial capacity of fast elevators is 3 and of slow ones is 2. The 10 first problems of IPC 2008 increased the number of passengers by one from the previous problem. The number 11, doubled the floors and made passenger = 8, while increasing in one the elevators' capacity. From it, 2 passengers were added till problem 20. From problem 21, a slow elevator was added, the capacity was increased to 6 for fast lifts and to 4 for slow ones, the number of floors was raised to 25 and the number of passengers was 12 an was increased by 3 in each problem. In IPC 2008 planners either only solved the 4-5 first problems or did not have trouble until the last ten.

We have reused the last 9 problems, plus problem 14 (only solved by one planner like a bunch of other ones). The remaining 10 problems start from characteristics of old problem 30 (current problem 10), adding 2 fast elevators, 1 slow and 1 passenger. The next 4 increase the number of passengers by 3. From problem 16 floors are 40, 4 fast lifts with capacity for 6 passengers, 4 slow ones for 4 passengers, and 40 passengers, increasing the number of passengers in 5 per problem.

The next table shows the problems chosen (numbers in parenthesis are floors, passengers, fast and slow elevators):

For the optimal track, in the last competition, problems started with 9 floors, 3 passengers and 3 elevators (1 fast for 3 passengers, 2 slow for 2 passengers). Next problem increased by one the number of fast elevators. Problem 3 had 3 elevators again and 1 more passenger. Problem 4 increased fast elevators and so on until number 10. Most of the planners were not able to solve more than the problem number 4. Problem 11 increased floors to 13 (with the other parameters left as in problem 1), which allowed planners to solve 3-4 problems more. So the difficulty is in the number of passengers and not in the number of floors. Problem 21 was like problem 11 but with 4 elevators (1 fast, 3 slow), so a couple of planners were able to solve it. Capacity was not changed in any problem.

We have taken following problems:

Floortile

Author: Tomás de la Rosa.

A set of robots use different colors to paint patterns in floor tiles. The robots can move around the floor tiles in four directions (up, down, left and right). Robots paint with one color at a time, but can change their spray guns to any available color. However, robots can only paint the tile that is in front (up) and behind (down) them, and once a tile has been painted no robot can stand on it.

For the IPC set, robots need to paint a grid with black and white, where the cell color is alternated always. This particular configuration makes the domain hard because robots should only paint tiles in front of them, since painting tiles behind make the search to reach a dead-end.

For the satisficing track 2 problems for each configuration have been created:

For the optimal track also 2 problems for each configuration have been created:

Nomystery

Author: Hootan Nakhost

From the original domain description:

Nomystery is a transportation domain designed to study resource constrained planning [1,2]. In this domain, a truck moves in a weighted graph; a set of packages must be transported between nodes; actions move along edges, and load/unload packages; each move consumes the edge weight in fuel. In brief, Nomystery is a straightforward problem similar to the ones contained in many IPC benchmarks. Its key feature is that it comes with a domain-specific optimal solver allowing to control the constrainedness of the resources. The generator first creates a random connected undirected graph with n nodes, and it adds k packages with random origins and destinations. The edge weights are uniformly drawn between 1 and an integer W. The optimal solver computes the minimum required amount of fuel M, and the initial fuel supply is set to [C ×M], where C ≥1 is a (float) input parameter of the generator. The parameter C denotes the ratio between the available fuel vs. the minimum amount required. The problem becomes more constrained when C approaches 1.

A ubiquitous feature of planning problems is the need to economize limited resources such as fuel or money. While heuristic search, mostly based on relaxation heuristics, is currently the superior method for most varieties of planning, its ability to solve critically resource-constrained problems is limited: relaxation heuristics basically ignore the resource consumption by actions. Nomystery generator is a nice test domain to study the behavior of planning algorithms in planning problems with resources.

There are two ways to scale problem difficulty in Nomystery: increasing the number of packages and locations, and decreasing C. The generator is very fast up to 18 locations and 18 packages. Two types of encoding can be used for the problems: Hard and Hard-cost. The only difference is in the action costs. While all actions have a unit cost in Hard encoding, in Hard-cost version action costs are equal to the amount of fuel consumed by the action. Therefore, the total cost of a plan for Hard-cost encoding equals the amount of fuel consumed in the plan. In Hard encoding, problems with 12 locations and 12 packages become quite challenging for state of the art planners when C is close 1 [1]. Hard-cost encoding makes the problems easier for the current planners. The reason is that the heuristic functions that consider costs are not any more completely ignorant to the resource consumption of actions. However, this type of encoding is not always feasible for resource planning; there might be several resources and the cost of the plan might be different from the amount of the resource consumption. However, our initial experiments show problems in this encoding with 12 locations and 15 packages become challenging for current planners when C is close to 1.

From the two versions of the domain we have chosen the non-cost one (cost of the plan and resource consumption are not related). As the domain creator says, this is the most difficult one of the two formulations. In addition, it is the less similar to the Transport domain. According to the domain creator planners find it difficult to solve problems with more than 12 locations and 12 packages when the constraint on the resource tends to 1. For the satisficing track, problems 1-10 start with 6 locations and 6 packages with c=1.5 and each problem increases 1 package and 1 location to the previous one (so problem 10 has 15 packages and 15 locations). Problems 11-20 also start in 6-6 and increase parameters by 1, but in this case c=1.1.

For the optimal track, we developed a first version where problems 1-10 start with 2 locations and 1 package with c=1.5 and each problem increases 1 location and 1 package to the previous one (so problem 10 has 10 packages and 11 locations). Problems 11-20 also start in 2-1 and increase parameters by 1, but in this case c=1.1. This version resulted to be quite simple, so we generated a tougher one. We started with 4 locations and 3 packages (last problem had 13 locations and 12 packages) with c=1.5 and c=1.1. That version was also quite simple, so a third one has been generated. From experiments it seems the lower the constraint the easier the problems are for the optimal planners: the search space is pruned quickly as the cost limits the number of applicable actions. Taking that into account we have generated problems with c=1.1, 1.5 and 2.0. Problems 1-6 have c=1.1 and start in 9 locations and 8 packages till 14-13. From 7-13 c=1.5, starting in 8 locations and 7 packages. Problems 14-20 are like 7-13 but with c=2.0.

References:

[1] Nakhost, H.; Hoffmann, J.; and Müler, M. 2010. Improving local search for resource-constrained planning. Technical Report TR 10-02, Dept. of Computing Science, University of Alberta, Edmonton, Alberta, Canada.

[2] Hoffmann, J.; Kautz, H.; Gomes, C.; and Selman, B. 2007. SAT Encodings of State-Space Reachability Problems in Numeric Domains. In Proc. 20th International Joint Conference on Artificial Intelligence (IJCAI-07), 1918–1923

Openstacks

From the original domain description (click here): This domain was first used at IPC-2006. The openstacks domain is based on the "minimum maximum simultaneous open stacks" combinatorial optimization problem, which can be stated as follows: A manufacturer has a number of orders, each for a combination of different products, and can only make one product at a time.

The total required quantity of each product is made at the same time (because changing from making one product to making another requires a production stop). From the time that the first product included in an order is made to the time that all products included in the order have been made, the order is said to be "open" and during this time it requires a "stack" (a temporary storage space). The problem is to order the making of the different products so that the maximum number of stacks that are in use simultaneously, or equivalently the number of orders that are in simultaneous production, is minimized (because each stack takes up space in the production area).

The problem is NP-hard and known to be equivalent to several other problems. It was recently posed as a challenge problem for the constraint programming community (see http://www.dcs.st-and.ac.uk/~ipg/challenge/).

Note that this is an optimization problem: for any instance of the problem every ordering of the making of products is a solution, which at worst uses as many simultaneously open stacks as there are orders. Thus, finding a plan is quite trivial (in the sense that there exists a domain-specific linear-time algorithm that solves the problem), but finding a plan of high quality is hard (even for a domain-specific algorithm).

There are two versions of this domain, STRIPS and ADL. As there are few ADL compliant planners and in the last IPC there were not too much differences in results between both versions, we have not generated ADL problems for this IPC. In the STRIPS version the goal is to minimize the total number of stacks. The number of stacks is represented using symbols and universally quantified preconditions have been replaced by multiple semi-ground actions. Note that this requires a different domain file for each problem.

For the satisficing track, in the 2008 competition, objects ranged from 5 to 100. For the first 12 problems, three versions with the same difficulty were created and objects were increased by 5 from one triplet to the next (i.e. problems 1, 2 and 3 were similar, with 5 objects; problems 4, 5 and 6 had 10 objects...). From 13 to 24 objects were increased by 10, while for the last 6, objects were increased by 20. The density parameter has been lost. For IPC 2011, as in the other reused domains, we reused the 10 first problems. From 11 to 20, objects are increased starting from 130 by 30, and 2 problems of the same size have been created, one with density = 20 and the other with density = 80.

The selected problems are (numbers in parenthesis are number of objects of each new problem):

For the optimal track, in the IPC 2008 a total of 9 problems were not solved by any planner (problem 20 and from 23 to 30). As in the satisficing version, there is no record of the density used to generate the problems. The first problem in IPC 2008 started with 5 objects and each problem had 1 object more than the previous one. So problem 30 had 34 objects.

Five first problems were quite simple so they have been removed from the selection. This results in 16 problems previously solved and 4 non solved for this edition. The selected problems are:

Parcprinter

From the original domain description (click here): This domain models the operation of the multi-engine printer, for which one prototype is developed at the Palo Alto Research Center (PARC). This type of printer can handle multiple print jobs simultaneously. Multiple sheets, belonging to the same job or different jobs, can be printed simultaneously using multiple Image Marking Engines (IME). Each IME can either be color, which can print both color and black&white images, or mono, which can only print black&white image. Each sheet needs to go through multiple printer components such as feeder, transporter, IME, inverter, finisher and need to arrive at the finisher in order. Thus, sheet (n+1) needs to be stacked in the same finisher with sheet n of the same job, but needs to arrive at the finisher right after sheet n (no other sheet stacked in between those two consecutive sheets). Given that the IMEs are heterogeneous (mixture of color and mono) and can run at different speeds, optimizing the operation of this printer for a mixture of print jobs, each of them is an arbitrary mixture of color/b&w pages that are either simplex (one-sided print) or duplex (two-sided print) is a hard problem. For the detail description of this domain and the continual online planner controlling it, please refer to the references listed at the end of this page.

This domain is used in two tracks: sequential and temporal. The temporal track is the most natural fit due to the default objective function for the printer of maximizing its productivity, which equals to finish printing all print job requests as quickly as possible. For the sequential track, we use a more seldom used objective function of minimizing printing cost. For example, using a more expensive color IME to print a black&white page costs more than using a mono IME. However, the cost tradeoff may not be clearcut if the feeder, where the blank sheets originally reside at is closer to the mono IME than to the color IME.

Overall, three different printers have been modeled, two with 2 IMEs (one color and one mono) and one with 4 IMEs (two colors and two monos). Two with rather symmetric design and a third one is asymmetric. Even those the printers are hypothetical, the hardware that can be used to make those printers are real.

For the problem files, to reduce complexity, print request of a single job with multiple sheets have been created. The sheets are randomly set to be either simplex (one-sided print) or duplex (two-sided print) and each image is also randomly selected to be either mono or color. The number of sheets varies from 1 to 20. Given this print job request and a particular printer configuration, the competing planner needs to find a plan with lowest total printing cost in the sequential track (matching well between image requirement and IME capabilities) and smallest makespan in the temporal track (synchronize well different IMEs).

There is no generator for this domain, so new problems will be by-hand generated using IPC 2008 ones. New problems will add some sheets to old problems or will make two-sided some of them. As in the IPC 2008, three different printers are used, one for problems 1-10, another for 11-20, and another for 21-30.

Remark: Printer 1 is not able to turn a page once printed, so if a problem prints something in the back side, the sheet needs to finish with back side up.

For the satisficing track, in the IPC 2008 the first problem had 1 sheet, second one 2 sheets and so on until problem 10. The same applies for problems 11-20 (changing the printer) and 21-30. We have reused the 10 following problems:

FF solves the previous problems quite quickly (less than 30 seconds), so the battlefield of this domain is going to be quality. From last IPC results it seems printer 1 and 3 are more difficult than printer 2 (out of the 10 most difficult problems, 5 belong to printer 3, 4 to printer 1 and only 1 to printer 2). We have generated 3-3-4 new problems increasing sheets or sides from the previously created problems.

For the optimal track, there were 10 unsolved problems in last IPC. Problem number 1 had only 1 sheet and 1 image to be printed in the sheet. Printer had 2 IMEs (one color and one mono). Problem number 2 had 2 sheets and 2 images, and so on until problem 10. In problems 11 to 20 another more complex printer with also 2 IMEs was modeled. In problem 11, using this printer 1 sheet was printed in 1 image, and so on until problem 20. In problem 21 a new printer with 4 IMEs was modelled and we start again with 1 image in 1 sheet (some of them like problem 15 and problems 29 and 30 include extra images so some sheets are two-sided).

We have eliminated problems 3, 11, 1 and 21 as they were quite easy, so we have 16 solved and 4 unsolved problems, as follows:

References:

1. On-line Planning and Scheduling for High-speed Manufacturing. Wheeler Ruml, Minh B. Do, & Markus Fromherz. In Proc. of the 15th International Conference on Automated Planning and Scheduling (ICAPS) 2005. (PDF)

2. Lessons Learned in Applying Domain-Independent Planning to High-Speed Manufacturing. Minh B. Do, & Wheeler Ruml. In Proc. of 16^th International Conference on Automated Planning and Scheduling (ICAPS), 2006. (PDF)

3. On-line Planning and Scheduling: An Application to Controlling Modular Printers. Minh B. Do, Wheeler Ruml, and Rong Zhou. In the Proc. of 23^rd AAAI Conference on Artificial Intelligence (AAAI), NECTAR Track.(PDF)

4. Planning for Modular Printers: Beyond Productivity. Minh B. Do, Wheeler Ruml, and Rong Zhou. To appear in the 18^th International Conference on Automated Planning and Scheduling (ICAPS), (PDF)

Parking

This domain is original from the learning part of IPC2008. The domain involves parking cars on a street with N curb locations, and where cars can be double-parked but not triple-parked. The goal is to find a plan to move from one configuration of parked cars to another configuration, by driving cars from one curb location to another. The problems in the competition contain 2*(N-1) cars, which allows one free curb space and guarantees solvability. For the satisficing track these problems have been created:

For the optimal track these problems have been created:

Pegsol

This domain models the Peg Solitaire game.

In IPC 2008 problems were the same both in sequential satisficing and in sequential optimal. They were taken from a pool of problems. The problem generator (in Ruby) takes problems from the library and converts them to pddl files. A total of 105 problems (some of them unsolvable) were generated. It seems it is the number of pegs and not the number of required movements what makes difficult for planners to find a solution. But most of the problems with more than 17 pegs (problem 20 of the last IPC) had been already selected. So for this year's competition most of the problems (and all of the most difficult ones) come from the last IPC. Then, planners are expected to behave quite well in this domain, solving most or almost all the problems. We include this domain just to check that this year's planners are at least as good as past competition ones.

For the satisficing track, we have reused 15 problems from the last IPC and have added 5 new problems taken from the pool. The selected problems are:

where problems 4-8 are the new ones.

For the optimal track, there were only 3 unsolved problems in the 2010 set, and a lot of planners solved about 25 problems. The first unsolved problem of last IPC is the number 28 which corresponds with problem 074 in the library, which has 25 pegs and in theory is solvable with cost 12.

The following table shows the problems selected for this year competition (the most difficult problems, in number of pegs, from the available pool), last column states whether the problem was also selected for last IPC.

Scanalyzer

This domain models the problem of automatic greenhouse logistic management. More information about it can be found in the ICAPS 2010 paper There is no generator nor information about how problems were generated. In IPC 2008 problems in this domain were the same for both the optimal and the satisficing tracks. In addition, problems 22, 23 and 24 are exactly the same problem.

The following table shows the number of objects in each problem for IPC 2008 and how did they increase:

This was continued until problem 21: problems were organized in triplets, where first problem of each triplet (3n+1) had 2 more cars and segments than first problem of previous triplet (3n-2), and (cars/2)^2 CYCLE-2 segments, which were divided by (cars/2) for the next 2 problems. From problem 22, number of cars was initialized to 4 and CYCLE-2 was changed by CYCLE-4 (again with car/2 predicates). As said, problem 23 and 24 were exactly the same as problem 22. Problem 25 had 4 more cars, while 26 and 27 divided by 2 the CYCLE-4 predicates. The same applies for 28-30 (12 cars, starting with 9 CYCLE-4 and dividing by 3)

For the satisficing track, taking into account that there is no generator and that there is margin for increasing the quality of the found plans, we have reused the problems of last competition as follows:

For the optimal track, there were 13 unsolved problems in the last IPC. In addition no planner solved more than 11 problems. From results we can see that usually first problem of a triplet is easiest than the two last problems from the previous triplet. The selected problems are:

So we have 14 solved problems. To select the remaining 6 ones we rely on the fact that from 1 to 21 a triplet is always easier than the next one, and the same applies for triplets 22 to 30. So we have taken the second element of each triplet (8,11,14,17,20) and 28 from the last triplet.

Sokoban

This domain models the Sokoban game.

For the satisficing track, in IPC 2008 performance of planners in this domain was somehow poor (best planner had 5 unsolved problems), so instead of generating new problems we have reused the most difficult problems of last IPC.

For the optimal track, at the 2008 edition there were 20 solved problems, and no problem over 21st was solved. We discarded problems 1, 2 and 3, as they were quite easy, which results in 17 solved problems. So 3 unsolved problems have to be added. At IPC 2008 problems were taken from a library, so we have assumed problem 21 is easier than 22 and so on, and have chosen problems 21-23. The selected problems are then:

Tidybot

Author: Bhaskara Marthi

From the original description: The Tidybot domain models a household cleaning task, in which one or more robots must pick up a set of objects and put them into goal locations. The world is structured as a 2d grid, divided into navigable locations and surfaces on which objects may lie. Robots have a gripper, which moves relative to the robot, up to some maximum radius. Existing objects block the gripper, so that it may be necessary to move one object out of the way to put another one down. Robots can carry one object at a time in the gripper, but may also make use of a cart, that can hold multiple objects. The instance generator creates worlds that contain rectangular surfaces ("tables"), as well as U-shaped enclosures ("cupboards"), which are the goal locations of objects.

In many real-world problems, the difficulty is due to the large state space and number of objects, rather than due to complex, "puzzle-like" combinatorial constraints. Humans are able to quickly find feasible solutions in such domains, because they seem to be able to decompose the problem into separate parts and make use of the geometrical structure. This domain is thus intended to exercise the ability of planners to find and exploit structure in large but mostly unconstrained problems.

Optimal reasoning in such problems is challenging for humans as well, and a secondary motivation for the domain is to test the ability to do optimal reasoning in geometrically structured worlds. The presence of the carts adds another combinatorial decision: it might be worthwhile to spend some time fetching the cart to avoid later having to go back and forth with each object.

The instance generator is provided as a .jar file, together with the source code (in the Clojure language). To generate an instance: java -cp tidybot.jar tidybot world-size num-tables num-cupboards table-min-size table-max-size cupboard-size

The number of objects will be num-cupboards * objects-per-cupboard, where objects-per-cupboard = (cupboard-size - 2)^2. Thus, num-cupboards should be >= 1, otherwise there will be no objects. It is recommended to set cupboard-size = 4. Scaling world-size will then increase the number of literals/states, while scaling num-cupboards will increase the number of objects and goals. Scaling num-tables will tend to make the domain more constrained (since there are more obstacles), and also to increase the branching factor, since there are more places to set objects down.

Problems with the same size can be quite different in difficulty, so we will generate various problems of the same size. The automatic generator returns error quite often (9 out of 10 times at least) when the size of the world is lower than 9. But problems with size 9 are quite challenging even for the satisficing planners. In addition some of the generated problems are unsolvable or are equal to other generated problems. This makes quite hard to generate problems for this domain.

For the satisficing track, problems with world size=8 are solved quite easily, but problems with size=9 are challenging. The following table shows the parameters chosen for the problems at IPC 2011.

For the optimal track, the following table shows the parameters chosen for the problems at IPC 2011.

Transport

There is no description of this domain in the last IPC, but it seems to be a kind of logistics one. Each vehicle can transport some packages depending on its capacity and moving has a cost depending on the length of the road. Picking up or dropping a package costs 1.

For the satisficing track, the following table depicts the parameters of IPC 2008 problems:

So the first 10 problems consider only 1 city, starting in 5 locations and increasing them by 5, with 2 packages that are increased by 2. Trucks are 2 for p01 and p02, 3 for p03-p05 and 4 for the remaining problems. Problems 11-20 follow the same rules for trucks and packages, but have 2 cities, and number of total nodes is increased by 6 from problem to problem. The same rules apply for problems 21-30, but in this case there are 3 cities.

It seems that most difficult problems are those with 2 cities, and easiest those with 3. So for the 10 new problems have generated 3-3-4 problems of 1-2-3 cities. Starting from parameters of problems 10, 20 and 30 with slow increases so we can characterize the phase transition (first problem increases packages, second one nodes and third one both). So problems for this domain are:

The number in parenthesis are cities-nodes-trucks-packages.

For the optimal track, the following table shows the objects of problems at last IPC and how do they increase:

We remove problems 1, 2, 11, 21 and 22, which are quite easy. This gives us only 6 solved problems and 14 non solved. As this would make the domain too difficult, we have generated some new problems so the number of previously unsolved problems remains lower than 5. From the tables above we can see that the most important parameters to measure the difficulty of the problems are the number of nodes and of packages. From problem 14 we can elicit that nodes seem to be more important than packages; its equivalents with 7 packages, problems 4 and 24 have both 12 nodes and are solved, while problem 14 (not solved) has 16 nodes. Effect of trucks cannot be measured as no problem with 3 trucks is solved. The phase transition in terms of nodes seems to be between 12 (solved) and 16 (non solved). So we have generated problems with 13, 14 and 15 nodes with 1 city, 14 nodes with 2 cities and 15 nodes with 3 cities (number of nodes needs to be a multiplier of number of cities). We did it for 2 and 3 trucks. This results in 10 new problems.

The selected problems are then:

The number in parenthesis are cities-nodes-trucks-packages.

Visit-all

Author: Nir Lipovetzky

From the attached paper: "The heuristics used in state-of-the-art (satisficing) planners are a decade old and are based on the delete-relaxation. Several heuristics that take deletes into account have been formulated but they haven’t been shown to be cost-effective. One problem with delete-relaxation heuristics that aproximate h+, appears in instances with multiple conflicting goals. In these cases, that are very common, progress towards one goal means moving away from other goals. Such instances produce large plateaus where the heuristic is almost useless. Indeed, in some cases, state-of-the-art heuristics are no better than heuristics that ignore the problem structure completely and just count, for example, the number of unachievable goals. As an illustration of this, consider the Visit-All domain where an agent in the middle of a square grid nxn must visit all the cells in the grid. Solving optimally the delete relaxation h+ gives the exact goal distance as long as there exists a hamiltonian path visiting every cell. Recall that in a 1xn grid, no hamiltonian path exists."

"The use of delete-relaxation heuristics to appraise the cost of achieving all goals together runs into a situation resembling Buridan’s ass: where a hungry and thirsty donkey, placed between a bundle of hay and a pail of water, dies of hunger and thirst for not finding a reason to choose one over the other.

* Visit-All domain description paper

Woodworking

There is no description of this domain in the last IPC. It simulates the works in a woodworking workshop where there is some quantity of wood that has to be polished, coloured, etc. using different tools with different costs. Parameters of each problem are the parts to be done and the quantity (in % of necessary) of available wood (boards). The higher the number of parts and the boards the more difficult the problem is.

In the satisficing track, at IPC 2008 a lot of planners solved almost all the problems in this domain. We have reused the 10 most difficult from last IPC and have generated 10 more difficult than those.

In the last IPC problems were generated as follows:

Problems 11-20 followed the same pattern, but with a 120% of wood, so they did problems 21-30 but with a 100% of wood. It seems the more the wood the more difficult a problem is. We will generate problems with 120% and 140% of wood, increasing also parts by 3. If we take a 3-parts problem with 1 tool of each type, and generate a similar one with 3 tools, solving time passes from some seconds to some minutes. But if we generate an equivalent one with 5 tools time is reduced and is similar to the 1-tool problem! Increasing tools to 7 reduces the time even more. So we have generated problems with 1 and 3 tools of each type.

Problems for the competition are depicted in the following table (numbers in brackets are wood-parts-tools):

For the optimal track, at IPC 2008 ten first problems had a 140% of wood and parts were increased by one from one problem to another, starting from 3 parts. Similarly problems 11-20 started with 120% and 3 parts. Problems 21-30 decreased the available wood to 100%. From last IPC results it seems most planners are not able to handle problems with more than 5 parts. The lower the boards the easier the problem seem to be. Tthe performance of planners in this domain is quite poor. The easiest problems are solved by almost all the planners, but as soon as number of parts is above 5 only one planner is able to solve problems. But this planner finds non optimal or invalid plans for the easiest instances.

Problems selected are: