Issue304

Title improve handling of zero-cost actions
Priority feature Status chatting
Superseder Nosy List malte
Assigned To Keywords
Optional summary

Created on 2011-11-21.19:17:44 by malte, last changed by malte.

Messages
msg1974 (view) Author: malte Date: 2011-11-21.19:17:43
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.
History
Date User Action Args
2011-11-21 19:17:44maltecreate