[ 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 publications: [PUBLink] [PUBLink])

If the planning system is started, the shortest possible plan that results in no pain for the Orc can quickly be obtained (55 times catch_only_one and 5 times deliver_humans, which yields a plan duration of 115 hours, a 0 on the pain scale and 5 performers). The figure below shows the temporal distribution for 100,000 test runs with different random seeds (e.g., after 1,000 improvement iterations, 100% of the test runs found a plan that yields enough performers, 94% of the test runs found a plan that yields enough performers and no pain, and 41% of the test runs found the shortest plan that yields enough performers and no pain).

A comparison to other systems is not very useful, as these would either come up with the plan that primarily minimizes the plan length (catch_a_group & catch_a_group) or require a bound for the plan length. If we cheat in favor of the other planning systems and provide the information that the optimal length bound is 60 actions, an encoding according to CPlan [PUBLink] of this simple problem would require 129,600 variables - not to speak of constraints! Even the time required to create a list of these domain variables (tested with CHIP, which is a state-of-the-art constraint programming system) is longer than any of the test runs in the figure above needed to compute the optimal plan. However, we actually cheated in favor of CPlan by providing the optimal length bound. In general, the comparison is not a quantitative question of speed but a qualitative question of capability to find the optimum.

However, if one insist on quantitative results, it is a matter of improving the heuristics. The conceptual approach of the planning system allows us to easily integrate domain-dependent knowledge. For example, the Pain constraint can be improved by paying more attention keeping the same number of performers if an option to reduce the pain is chosen. For this purpose, three additional catch_only_one actions can be added if the option to delete a catch_a_group action is chosen. In the same way, the number of performers can be replenished by adding catch_only_one and catch_a_group actions (partitioning them according to the preference values) if the option of adding a deliver_humans action is chosen. These simple modifications already make it possible to considerably reduce the execution times (see the figure below).

Because of the logarithmic scales of the figures above, the improvement is not very evident, but the average number of iterations needed until the optimal plan is found is reduced by 20%.

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek