search

aibasel / pyperplan

A lightweight STRIPS planner written in Python.
GNU General Public License v3.0
93 stars 41 forks source link

Nodes expanded for pyperplan vs. fast downward #17

Closed tomsilver closed 2 years ago

tomsilver commented 2 years ago

Hello! Thanks again for making this great library available.

This isn't an issue, but a bit of a puzzle, and I was wondering if you would know the answer right away.

I'm comparing the number of nodes expanded by pyperplan and fast downward. For pyperplan, I'm using hFF and GBFS. For fast downward, I'm looking at two configurations: --alias lama-first and --search eager_greedy([ff()]).

I was expecting to see that in most cases, the number of nodes expanded by pyperplan (hFF / GBFS) would be similar to the number of nodes expanded by fast downward (hff / GBFS), or that fast downward would be better due to some optimizations. I was also expecting that fast downward with lama-first would be better than both.

But instead, I'm finding that the number of nodes expanded by pyperplan is often better than both versions of fast downward in terms of nodes expanded. For example, here are some results averaged across the first 10 problems for each of the listed domains (from the benchmarks in pyperplan).

Screen Shot 2022-08-04 at 6 38 38 PM

For example, in elevators, pyperplan only expands 33.9 nodes on average, while fast downward with hFF / GBFS expands 526.20 and lama-first expands 97.80.

It's certainly possible that I am doing something silly in the way that I am collecting these results, but I wanted to see if any possible causes occurred to you immediately.

Thanks for your time!

maltehelmert commented 2 years ago

Hi Tom,

that's interesting!

There are some reasons why the hFF/GBFS numbers could differ. The FF heuristic depends on tie-breaking, as does GBFS itself. But I wouldn't expect such large and systematic swings in favour of pyperplan.

I ran some tests myself on the Gripper domain because it's a fairly regular domain where I wouldn't expect tie-breaking to affect the heuristic or GBFS much, and on the two tasks I tested (problem 01 and problem 10), pyperplan (-H hff -s gbf) and Fast Downward (--search eager_greedy([ff()])) gave me the same number of expansions (26 for problem 01, 566 for problem 10).

Are you sure you measured expansions for both? I'm asking because Fast Downward reports several related numbers. If so, can you share the individual numbers you get for pyperplan and Fast Downward on the first 10 Gripper tasks?

tomsilver commented 2 years ago

Hi Malte,

Thanks very much for your help! Your intuition was exactly right, I was using the wrong metric from Fast Downward ("Evaluated" instead of "Expanded"). Silly me! I confirmed that the numbers match in the Gripper tasks between Pyperplan and Fast Downward after fixing that.

Thanks again!