Issue407

Title g-bound for trivially solved tasks
Priority bug Status chatting
Superseder Nosy List gabi, jendrik, malte
Assigned To Keywords
Optional summary

Created on 2013-12-26.15:34:04 by jendrik, last changed by jendrik.

Messages
msg2851 (view) Author: malte Date: 2013-12-27.18:13:38
While we're looking at it, there's a related thing we're not currently handling
properly, and that's if the initial state should be pruned because of its
heuristic value.

Currently, we add it to the open list unconditionally, and this happens to work
by accident, but the output is messed up (e.g. showing that a state with a
heuristic value of 2147483647 is expanded). This also causes an
out-of-memory-style error when using single_buckets() since the code attempts to
create 2147483648 buckets. For example, try

$ ./plan ../benchmarks/mystery/prob07.pddl --search 'eager(single_buckets(blind()))'

The better solution would be to use the same criteria (and ideally the same
code, factored out) as during state expansion for deciding whether the initial
state should be added to the open list.
msg2850 (view) Author: gabi Date: 2013-12-27.15:12:36
I find it also more naturally to report that there is no plan
cheaper than 0.
msg2849 (view) Author: malte Date: 2013-12-26.20:35:37
> Setting bound=0 essentially means telling the planner that no plan is
> acceptable since the bound is exclusive. To me this seems like a usage error
> and not  something the searches should have to deal with.

Good code supports corner cases properly. If it doesn't, breakage occurs, like
we see with the portfolio script. The logical answer to the question "Try to
find a plan that costs less than zero" is "There is no such plan", not "Error!".
Obviously, there is no reason to call the planner with a bound manually set to
0. But there are many perfectly good reasons for a larger script invoking
multiple planner calls (such us our portfolios) to pass in the "current best
known solution" or something like this as a bound, and there is no reason not to
support the case where the cost of this solution is 0.

Otherwise everybody using the bounds feature must add a special check that the
bound is not zero. For example, our iterated search code also currently relies
on the fact that bounds of zero can be passed in.

> If we go for your proposed solution, I guess we would need to prevent the
> initial node from being added to the open list in all searches' initialize()
> methods separately, right?

Yes; the clean way to address this would be to use the same bounds-checking code
whenever a node is added to the open list, no matter where the node comes from
(initial node or successor node).
msg2848 (view) Author: jendrik Date: 2013-12-26.19:41:54
Setting bound=0 essentially means telling the planner that no plan is acceptable 
since the bound is exclusive. To me this seems like a usage error and not 
something the searches should have to deal with.

If we go for your proposed solution, I guess we would need to prevent the initial 
node from being added to the open list in all searches' initialize() methods 
separately, right?
msg2847 (view) Author: malte Date: 2013-12-26.15:59:34
> I would suggest to forbid setting bound=0.

Why? This seems like an arbitrary limitation to me; I'd rather see the
underlying bug fixed. This would also mean that nothing needs to be done about 2).
msg2846 (view) Author: jendrik Date: 2013-12-26.15:34:04
The first briefcaseworld task is solved by the empty plan. This uncovered two 
bugs:

1) Even with the exclusive g-bound set to 0 the empty plan is accepted as a 
solution. I would suggest to forbid setting bound=0.

2) Satisficing portfolis repeatedly find the empty plan, set the bound to 0 and 
find the empty plan again... I would suggest to alter portfolio.py and stop once 
the bound falls below 1.
History
Date User Action Args
2015-07-29 20:33:54jendriksetassignedto: jendrik ->
2013-12-27 18:13:38maltesetmessages: + msg2851
2013-12-27 15:12:36gabisetnosy: + gabi
messages: + msg2850
2013-12-26 20:35:37maltesetmessages: + msg2849
2013-12-26 19:41:54jendriksetmessages: + msg2848
2013-12-26 15:59:34maltesetstatus: unread -> chatting
messages: + msg2847
2013-12-26 15:34:04jendrikcreate