Some of our design decisions should be rethought in the presence of 0-cost
actions. For example, there are cases where A* with a perfect
(bisimulation-based) heuristic performs significant amounts of search, e.g. in
the experiments for issue301, where we get the following numbers:
??? [WORK-mas-bisim-false-rl-pegsol-08-strips-p05.pddl] did not go straight to
goal: expansions 15 vs. length 11
??? [WORK-mas-bisim-false-rl-openstacks-opt08-strips-p01.pddl] did not go
straight to goal: expansions 182 vs. length 17
??? [WORK-mas-bisim-false-rl-openstacks-opt08-strips-p02.pddl] did not go
straight to goal: expansions 898 vs. length 20
??? [WORK-mas-bisim-false-rl-openstacks-opt08-strips-p03.pddl] did not go
straight to goal: expansions 2306 vs. length 23
??? [WORK-mas-bisim-false-rl-openstacks-opt08-strips-p04.pddl] did not go
straight to goal: expansions 10115 vs. length 27
??? [WORK-mas-bisim-false-rl-openstacks-opt08-strips-p05.pddl] did not go
straight to goal: expansions 16260 vs. length 31
??? [WORK-mas-bisim-false-rl-openstacks-opt08-strips-p06.pddl] did not go
straight to goal: expansions 2770 vs. length 32
??? [WORK-mas-bisim-false-rl-openstacks-opt08-strips-p07.pddl] did not go
straight to goal: expansions 217613 vs. length 38
??? [WORK-mas-bisim-false-rl-openstacks-opt08-strips-p08.pddl] did not go
straight to goal: expansions 231069 vs. length 41
??? [WORK-mas-bisim-false-rl-sokoban-opt08-strips-p03.pddl] did not go straight
to goal: expansions 84 vs. length 55
For M&S in particular, one possible way of fixing this would be to store the
action count ("distance" as opposed to "cost") that corresponds to an optimal
abstract solution and use that for tie-breaking in some way.
|