[ 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])

The optimization problem without the deliver_humans action could have been optimally solved by calculating an upper bound for the plan length and starting the planning system with the requirement to consider only plans with a length of this bound. A no_action action could be introduced to allow for plans that are shorter than the length allowed by the bound. The bound is easy to calculate because a plan's Performers and Pain increase strictly monotonically with the plan length, and after an application of 5 actions the goal condition for the Performers is met anyway, and the Pain can only get worse for longer plans.

However, this simple way of calculating an upper bound is no longer applicable with an action like deliver_humans that destroys the monotony. You think about the new problem for a bit, but it is far too complex for an Orc. Lacking a method to calculate the upper bound, you decide to run the planning system with some random bounds for the plan length. Starting with a bound of 6, the plan that consists of 5 times catch_only_one is returned. With a length of 7, you still get this solution. You decide to raise the bound to 15, and ... wait. After a long period, the solution is confirmed again. It seems to be the optimum, but you test a bound of 30 just to be sure, and ... wait. After a while, the planning system returns a different solution than before. Unfortunately, this solution is beyond your comprehension and you are gradually overcome by the unpleasant feeling that the suggested plan «out of memory» is just another feature of the system designed to mislead helpless Orcs.

The wizard is quite astonished when you tell him that his offer would not help you to improve your plan. You offer to demonstrate this with your planning system, but he wants to try his own. Shortly afterward, he presents you with a plan that entails no pain for you. The plan has a plan length of 60, and you wonder how his system was able to return a solution that quickly.

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek