[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publication: [PUBLink])

The benchmark problems of the AIPS-2000 planning competition (track 2) are used in the following. Because of the stochastic nature of the planning system, 1,000 test runs were executed per problem setting. This means that it was only possible to analyze small problems (problems 4 to 10 with variations 0 and 1) because of limited computing power. Instead of computation time, the number of iterations was measured, because the test runs were executed on different types of computers (the average being about 400 iterations per second). A test run was stopped if it failed to find a solution after 100,000 iterations.

The figures below show the number of iterations necessary to find a solution (to facilitate comparison, problem 9-1 is included in both figures). The heavy-tail phenomenon (which roughly means that a small fraction of test runs take very long - see [PUBLink] for details) is clearly evident, and a restart technique could be applied to greatly improve average-case behavior.

The time taken to solve a problem is closely related to the number of actions necessary to solve the problem (see the figures below). The `steps' in the graphs can be explained by the fact that it does not normally harm a plan to add an action and then add another action to undo the preceding one, e.g., to load a package and then unload it, whereas the addition of a single action can result in a different outcome. Thus, more test runs will yield results with two additional steps instead of one.

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek