best-first search from LAMA

[Jeremy Murphy]

Hi everyone,

I just started working on the Fast-Downard code, so I have at least one naive/beginner questions that I hope someone has time to answer.

I was working on the best-first search component of LAMA when I learned that FD is where the on-going development is happening.  But I cannot see an obvious best-first search implementation in FD such as there is in LAMA (where it is a subclass of SearchEngine).  Is it hiding somewhere under a different name?  Or did it not make the cut?

Thanks, cheers.

Jeremy

[Gabi Röger]

Dear Jeremy,

Best-first search is implemented in eager_search.cc and lazy_search.cc
(eager and lazy is referring to the evaluation strategy). The
implementation is
quite generic, so it can be used with almost arbitrary ranking functions
to decide
which is the best node to expand. The exact instantiation is done by the
parser
according to the options given on the command line.
See http://www.fast-downward.org/SearchEngine for an overview.

In the code, you find the respective functionality in the parse
functions at the bottom,
for example
static SearchEngine *_parse_greedy(OptionParser &parser) {...}
for Greedy best-first search.

Cheers.
Gabi

[Erez Karpas]

Hi Jeremy, 

The search code in Fast Downward is indeed messy, but you can find it at:

src/search/lazy_search.cc   implements (general) lazy best search, which LAMA uses, whie

src/search/eager_search.cc   implements (general) eager best first search

Cheers,

Erez.

[Malte Helmert]

On 13.01.2013 13:37, Erez Karpas wrote:
> Hi Jeremy,
>
> The search code in Fast Downward is indeed messy, but you can find it at:
>
> src/search/lazy_search.cc implements (general) lazy best search, which
> LAMA uses, whie
>
> src/search/eager_search.cc implements (general) eager best first search

Adding to what Erez and Gabi wrote: LAMA 2011, the version of LAMA run
at the last IPC, is what you get when you run Fast Downward's search
component with the options "ipc seq-sat-lama-2011". In the
src/search/downward script, you can see which "manual" option settings
this corresponds to. For problems where not all actions are unit-cost,
the options are:

--heuristic "hlm1,hff1=lm_ff_syn(lm_rhw(
reasonable_orders=true,lm_cost_type=1,cost_type=1))" \
--heuristic "hlm2,hff2=lm_ff_syn(lm_rhw(
reasonable_orders=true,lm_cost_type=2,cost_type=2))" \
--search "iterated([lazy_greedy([hff1,hlm1],preferred=[hff1,hlm1],
cost_type=1,reopen_closed=false),
lazy_greedy([hff2,hlm2],preferred=[hff2,hlm2],
reopen_closed=false),
lazy_wastar([hff2,hlm2],preferred=[hff2,hlm2],w=5),
lazy_wastar([hff2,hlm2],preferred=[hff2,hlm2],w=3),
lazy_wastar([hff2,hlm2],preferred=[hff2,hlm2],w=2),
lazy_wastar([hff2,hlm2],preferred=[hff2,hlm2],w=1)],
repeat_last=true,continue_on_fail=true)"

You can find out more about the various bits and pieces (e.g.
"lazy_greedy", "lm_rhw", "lm_ff_sym") by searching for these strings in
the code or on the Fast Downward homepage.

Cheers,
Malte