Issue255

Title m&s shouldn't use "1" for "unbounded", especially not in output to the user
Priority bug Status resolved
Superseder Nosy List malte, moritz, raznis
Assigned To malte Keywords
Optional summary

Created on 2011-08-05.17:46:21 by malte, last changed by malte.

Messages
msg1744 (view) Author: malte Date: 2011-09-05.18:08:24
This was fixed as part of issue211.
msg1480 (view) Author: malte Date: 2011-08-05.19:29:15
I see, thanks! I remember Raz mentioning that he used "1" for "unbounded" in
some places as a quick hack. We should eventually clean this up, but it's
probably not terribly urgent.

Note to self and Raz: this should not be changed in the master repository before
the refactoring of Moritz has landed; it's not worth the (code) merging worries.

Moritz, if it's very little work to change this during refactoring, feel free --
but if it's a logically separate change, don't.

I'll change the title for this issue to reflect what this is about.
msg1478 (view) Author: moritz Date: 2011-08-05.19:00:03
In case you mean this part:

> unreachable: 5333 nodes, irrelevant: 0 nodes
> shrink by 899999 nodes (from 900000 to 1)
> Size of collapsed groups =248771
> Simplification was not f-preserving -- must recompute distances.
> size of abstraction after shrink: 248771, Threshold: 1 

I think this is a forced shrink to prune unreachable states. In the
unused_* version, the threshold was equal to the size of the abstraction
in this case. In the raz_*-version the threshold was changed to 1 (see
line 131 in raz_abstraction.cc), which also makes the output wrong (see
line 1931). I don't know the reason for this change.
msg1474 (view) Author: malte Date: 2011-08-05.17:50:26
Hmm, so maybe this is not overflow related. I get similarly strange output
already when using

$ ./downward-1-debug < output --search
'astar(mas(max_states=1000,max_states_before_merge=200))'

(Again on blocksworld 8-0.)

Maybe it's just the output that is wrong and there's something else that
actually goes on there?
msg1473 (view) Author: malte Date: 2011-08-05.17:46:21
I stumbled over this when testing issue236.

./downward-1-debug < output --search 'astar(mas(max_states_before_merge=100000))'

results in the following output on blocksworld 8-0:
=========================================================================
Simplifying transitions... done!
Conducting best first search with reopening closed nodes, (real) bound = 2147483647
Initializing merge-and-shrink heuristic...!!!
Abstraction size limit: 2147483647
Abstraction size limit right before merge: 100000
Number of abstractions to maximize over: 1
Merge strategy: linear CG/GOAL, tie breaking on level (main)
Shrink strategy: high f/low h (main)
Label simplification: enabled
Expensive statistics: disabled
Building abstraction nr 0...
Building atomic abstractions...
Building atomic abstractions... done!
Merging abstractions...
16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 
next variable: #16
abstraction: 1/17 vars, 9 nodes, ???/16 arcs, 2068 bytes
             init h=0, max f=4, max g=2, max h=2 [t=0s]
next variable: #9
abstraction: 2/17 vars, 18 nodes, ???/1536 arcs, 20976 bytes
             init h=0, max f=6, max g=3, max h=3 [t=0s]
next variable: #15
operator registry: 2 vars, 128 operators, 128 canonical operators
abstraction: 3/17 vars, 162 nodes, ???/12096 arcs, 149692 bytes
             init h=2, max f=10, max g=5, max h=5 [t=0s]
next variable: #14
operator registry: 3 vars, 128 operators, 126 canonical operators
abstraction: 4/17 vars, 1458 nodes, ???/93312 arcs, 1142844 bytes
             init h=4, max f=14, max g=7, max h=7 [t=0.02s]
next variable: #13
operator registry: 4 vars, 128 operators, 122 canonical operators
abstraction: 5/17 vars, 13122 nodes, ???/699840 arcs, 8588380 bytes
             init h=6, max f=18, max g=9, max h=9 [t=0.13s]
next variable: #12
operator registry: 5 vars, 128 operators, 116 canonical operators
abstraction: 6/17 vars, 118098 nodes, ???/5038848 arcs, 62161116 bytes
             init h=8, max f=22, max g=11, max h=11 [t=1.38s]
next variable: #11
shrink by 18098 nodes (from 118098 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 6/17 vars, 100000 nodes, ???/5038848 arcs, 61998220 bytes
             init h=8, max f=22, max g=11, max h=11 [t=1.48s]
operator registry: 6 vars, 128 operators, 108 canonical operators
abstraction: 7/17 vars, 900000 nodes, ???/32653344 arcs, 404742316 bytes
             init h=10, max f=26, max g=13, max h=13 [t=11.25s]
next variable: #10
shrink by 800000 nodes (from 900000 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 7/17 vars, 100000 nodes, ???/32653344 arcs, 397542316 bytes
             init h=10, max f=26, max g=13, max h=13 [t=11.94s]
operator registry: 7 vars, 128 operators, 98 canonical operators
abstraction: 8/17 vars, 900000 nodes, ???/28403862 arcs, 353748532 bytes
             init h=12, max f=27, max g=15, max h=15 [t=21.55s]
next variable: #8
shrink by 800000 nodes (from 900000 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 8/17 vars, 100000 nodes, ???/28403862 arcs, 346548532 bytes
             init h=12, max f=27, max g=15, max h=15 [t=22.17s]
operator registry: 8 vars, 128 operators, 86 canonical operators
abstraction: 9/17 vars, 200000 nodes, ???/6501189 arcs, 81816456 bytes
             init h=12, max f=27, max g=16, max h=15 [t=25.4s]
next variable: #7
shrink by 100000 nodes (from 200000 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 9/17 vars, 100000 nodes, ???/6501189 arcs, 80916456 bytes
             init h=12, max f=27, max g=16, max h=15 [t=25.53s]
operator registry: 9 vars, 128 operators, 73 canonical operators
abstraction: 10/17 vars, 200000 nodes, ???/6855710 arcs, 86070708 bytes
             init h=12, max f=27, max g=18, max h=17 [t=27.94s]
next variable: #6
shrink by 100000 nodes (from 200000 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 10/17 vars, 100000 nodes, ???/6855710 arcs, 85170708 bytes
             init h=12, max f=27, max g=18, max h=17 [t=28.07s]
operator registry: 10 vars, 128 operators, 59 canonical operators
abstraction: 11/17 vars, 200000 nodes, ???/6576518 arcs, 82720404 bytes
             init h=14, max f=27, max g=18, max h=17 [t=30.49s]
next variable: #5
shrink by 100000 nodes (from 200000 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 11/17 vars, 100000 nodes, ???/6576518 arcs, 81820404 bytes
             init h=14, max f=27, max g=18, max h=17 [t=30.61s]
operator registry: 11 vars, 128 operators, 47 canonical operators
abstraction: 12/17 vars, 200000 nodes, ???/6502026 arcs, 81826500 bytes
             init h=14, max f=27, max g=18, max h=17 [t=32.95s]
next variable: #4
shrink by 100000 nodes (from 200000 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 12/17 vars, 100000 nodes, ???/6502026 arcs, 80926500 bytes
             init h=14, max f=27, max g=18, max h=17 [t=33.08s]
operator registry: 12 vars, 128 operators, 37 canonical operators
abstraction: 13/17 vars, 200000 nodes, ???/6592807 arcs, 82915872 bytes
             init h=14, max f=27, max g=19, max h=17 [t=35.51s]
next variable: #3
shrink by 100000 nodes (from 200000 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 13/17 vars, 100000 nodes, ???/6592807 arcs, 82015872 bytes
             init h=14, max f=27, max g=19, max h=17 [t=35.64s]
operator registry: 13 vars, 128 operators, 29 canonical operators
abstraction: 14/17 vars, 200000 nodes, ???/6788152 arcs, 85260012 bytes
             init h=14, max f=27, max g=19, max h=18 [t=38.14s]
next variable: #2
shrink by 100000 nodes (from 200000 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 14/17 vars, 100000 nodes, ???/6788152 arcs, 84360012 bytes
             init h=14, max f=27, max g=19, max h=18 [t=38.28s]
operator registry: 14 vars, 128 operators, 23 canonical operators
abstraction: 15/17 vars, 200000 nodes, ???/7892257 arcs, 98509272 bytes
             init h=15, max f=27, max g=19, max h=18 [t=40.9s]
next variable: #1
shrink by 100000 nodes (from 200000 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 15/17 vars, 100000 nodes, ???/7892257 arcs, 97609272 bytes
             init h=15, max f=27, max g=19, max h=18 [t=41.07s]
operator registry: 15 vars, 128 operators, 19 canonical operators
unreachable: 1288 nodes, irrelevant: 0 nodes
shrink by 199999 nodes (from 200000 to 1)
Size of collapsed groups =194480
Simplification was not f-preserving -- must recompute distances.
size of abstraction after shrink: 194480, Threshold: 1
abstraction: 16/17 vars, 194480 nodes, ???/8205390 arcs, 102320020 bytes
             init h=15, max f=27, max g=19, max h=18 [t=56.93s]
next variable: #0
shrink by 94480 nodes (from 194480 to 100000)
Size of collapsed groups =100000
size of abstraction after shrink: 100000, Threshold: 100000
abstraction: 16/17 vars, 100000 nodes, ???/8205390 arcs, 101366868 bytes
             init h=15, max f=27, max g=19, max h=18 [t=57.06s]
operator registry: 16 vars, 128 operators, 17 canonical operators
unreachable: 5333 nodes, irrelevant: 0 nodes
shrink by 899999 nodes (from 900000 to 1)
Size of collapsed groups =248771
Simplification was not f-preserving -- must recompute distances.
size of abstraction after shrink: 248771, Threshold: 1
abstraction: 17/17 vars, 248771 nodes, ???/9913116 arcs, 126065196 bytes
             init h=18, max f=27, max g=20, max h=19 [t=90.38s]
Done initializing merge-and-shrink heuristic [90.38s]
initial h value: 18
Estimated peak memory: 126065196 bytes
f = 18 [1 evaluated, 0 expanded, t=90.38s]
Best heuristic value: 18 [g=0, 1 evaluated, 0 expanded, t=90.38s]
Best heuristic value: 17 [g=1, 2 evaluated, 1 expanded, t=90.38s]
Best heuristic value: 16 [g=2, 6 evaluated, 2 expanded, t=90.38s]
Best heuristic value: 15 [g=3, 9 evaluated, 3 expanded, t=90.38s]
Best heuristic value: 14 [g=4, 11 evaluated, 4 expanded, t=90.38s]
Best heuristic value: 13 [g=5, 15 evaluated, 5 expanded, t=90.38s]
Best heuristic value: 12 [g=6, 17 evaluated, 6 expanded, t=90.38s]
Best heuristic value: 11 [g=7, 23 evaluated, 7 expanded, t=90.38s]
Best heuristic value: 10 [g=8, 32 evaluated, 10 expanded, t=90.38s]
Best heuristic value: 9 [g=9, 123 evaluated, 48 expanded, t=90.38s]
Best heuristic value: 8 [g=10, 371 evaluated, 152 expanded, t=90.38s]
Best heuristic value: 7 [g=11, 379 evaluated, 153 expanded, t=90.38s]
Best heuristic value: 6 [g=12, 393 evaluated, 157 expanded, t=90.38s]
Best heuristic value: 5 [g=13, 397 evaluated, 158 expanded, t=90.38s]
Best heuristic value: 4 [g=14, 617 evaluated, 233 expanded, t=90.38s]
Best heuristic value: 3 [g=15, 702 evaluated, 255 expanded, t=90.38s]
Best heuristic value: 2 [g=16, 703 evaluated, 256 expanded, t=90.38s]
Best heuristic value: 1 [g=17, 705 evaluated, 257 expanded, t=90.38s]
Best heuristic value: 0 [g=18, 706 evaluated, 258 expanded, t=90.38s]
Solution found!
Actual search time: 0s [t=90.38s]
unstack d h (1)
put-down d (1)
unstack a g (1)
put-down a (1)
unstack g e (1)
stack g b (1)
pick-up a (1)
stack a g (1)
pick-up c (1)
stack c a (1)
unstack h f (1)
stack h c (1)
pick-up e (1)
stack e h (1)
pick-up f (1)
stack f e (1)
pick-up d (1)
stack d f (1)
Plan length: 18 step(s).
Plan cost: 18
Initial state h value: 18.
Expanded 259 state(s).
Reopened 0 state(s).
Evaluated 706 state(s).
Evaluations: 706
Generated 1083 state(s).
Dead ends: 0 state(s).
Expanded until last jump: 0 state(s).
Reopened until last jump: 0 state(s).
Evaluated until last jump: 1 state(s).
Generated until last jump: 0 state(s).
search space hash size: 706
search space hash bucket count: 769
Search time: 90.38s
Total time: 90.38s
Peak memory: 891200 KB
=========================================================================

Note the places where one of the abstractions is shrunk to size 1
(supposedly -- if you follow the output, I don't think it actually is
shrunk to this size, but this is a separate issue).

I didn't look into the actual code, so this is speculation, but maybe
there's a problem with the target size computation here because some
intermediate result overflows? (Note that max_states is max_int here!)
History
Date User Action Args
2011-09-05 18:08:24maltesetstatus: chatting -> resolved
assignedto: malte
messages: + msg1744
2011-08-05 19:29:15maltesetmessages: + msg1480
title: overflow errors in m&s size computations? -> m&s shouldn't use "1" for "unbounded", especially not in output to the user
2011-08-05 19:00:03moritzsetmessages: + msg1478
2011-08-05 17:50:26maltesetmessages: + msg1474
2011-08-05 17:46:21maltecreate