TODOs:

- Rename to "lazy_ehc".

- Add user documentation that references one
of
the original EHC papers (perhaps the FF JAIR paper is the canonical
reference?)
and explains the main differences: the "lazy" nature of the
algorithm, the way
that this version handles duplicates, and the differences
between FF's helpful
actions and our preferred operators. (The latter should
perhaps be part of the
ff() documentation, but it might make sense to point to
it here if we discuss
"FF the planner" here, which is linked to EHC and the FF
heuristic).

I think the plan to simply make clear the differences between FastDownward's implementation and EHC in the FF 
planner is sufficient. Additional to the mentioned differences, I believe the current implementation is also 
a uniform cost search instead of a breadth first search---but this may be noted somewhere already, I forget.

We were using EHC as part of an experiment for a paper that's appearing in AAAI next week. I ended up re-
implementing EHC for our purposes since our investigation was quite specific. The tech report for the paper 
is here: https://arxiv.org/pdf/2511.09549, in appendix C we talk a bit about our implementation of EHC and 
the implementation itself is included as supplemental material.

And regarding EHC-style algorithms as an undergrad thesis, I put this together today based on my 
implementation for our paper: https://github.com/dawson-brown/downward/blob/ehc-
completeness/src/search/search_algorithms/enforced_hill_climbing_search.cc. Its pretty bare bones, but 
perhaps a useful starting point. I'll admit my testing was not super thorough. 

And lastly, I think beyond EHC style algorithms, a nice addition to FastDownward would be more convenient 
facilities for performing local searches. EHC being just a special case of using a local search strategy. I 
don't know if that's something that's been discussed or is wanted by the FastDownward community, but come the 
summer I'd be interested in contributing to that.

Note: we currently use "ehc" in one place in the seq-sat-fd-autotune-2 alias. 

That's the only use of ehc I could find with grep outside of the test suite.
There are also some tests that use it.

We had a meeting today where we discussed the way forward.

For now, we decided
not to remove the algorithm and not change its behaviour, but to rename the
plugin to "lazy_ehc" and to add documentation that makes the global duplicate
elimination (and its consequences) clear.

We'll also offer exploring the space
of EHC-style algorithms more thoroughly as a Bachelor's thesis topic because
it's a good fit in terms of interestingness and difficulty. Most years we have a
large demand for Bachelor's thesis topics between January and March.

If nobody
is interested in doing something with EHC in the next few months or so, we'll
revisit this and potentially remove the algorithm. For this it would be good to
know if anyone actually like it. :-) I've set myself a reminder to look into
this again in July.

Dawson, one of the questions that came up in our discussion
was why you ran Fast Downward's EHC in the first place. Was it because you
wanted to do something "useful" with the algorithm, or was it more because you
wanted to compare another algorithm to EHC for a paper experiment or similar?
What we want to figure out is if there are people out there that actually like
Fast Downward's ehc plugin, which would of course be an argument against
removing it.

Thanks for the bug report, example and analysis! Very thorough, much
appreciated.

I can confirm that ehc(ff()) fails to find a solution for the
task.

In defense of the current implementation, I wouldn't say that it
misreports that a solution does not exist. It uses the exit code for "an
incomplete algorithm didn't find a solution", not the error code for "There is
no solution". The output text is "Search stopped without finding a solution."
The claim that no solution exists isn't expressed or intended. But that's the
only positive thing, really.


We know that EHC is incomplete and that the "ehc"
in Fast Downward is substantially different from what one normally thinks of as
the EHC algorithm, but even being aware of this, seeing it fail on solvable
tasks in an undirected state space appears unexpected. I haven't tried verifying
that using a global closed list for pruning is the culprit here, but it
certainly makes sense. I'm not sure I'd call this a bug, but at the very least
the algorithm is underdocumented.

The question is what to do about it. ehc is a
neglected part of the code. With the standards we're applying these days, we
would never have merged it in this form.

Looking back at issue631, if we'd been
aware at the time that the global duplicate detection causes this additional
form of incompleteness, we might have acted differently at the time.

Some
things we could do:

1) Document the behaviour better, leave code as is.

2) Get
rid of this form of duplicate elimination to make the algorithm complete on
undirected tasks. (We  might still get most of the benefit of this global
duplicate elimination from the heuristic caching that we have anyway.)

3) Have
an option to enable/disable this form of duplicate elimination, as in the
rejected patch in issue631.

4) Remove the algorithm from the code.

5)
Implement a more normal (non-lazy) EHC that actually behaves like textbook EHC.

Some combinations are possible of course, such as 4+5.

Thoughts?

Dear Dawson,

thanks for reporting. Let me move the text of your issue from the
"optional summary" field to the discussion:


=============================================================================================================

The current EHC implementation can possibly misreport that a solution does not exist even 
when using a completeness-preserving heuristic in a state spaces that has no dead-ends.

The issue arises due to the global closed list. Due to only pushing globally new states to 
the local open  list, if the only way to reach a state with a lower heuristic value is by passing through the closed list, the current implementation will not find that path. 

Attached is a small blocksworld instance where exactly this happens. Blocksworld has no deadends, and FF will not misreport solvable states as dead-end states, this should be solvable. 

This issue is related to the closed issue631.

relevant: https://link.springer.com/chapter/10.1007/3-540-39963-1_23, 
https://gki.informatik.uni-freiburg.de/papers/hoffmann-ijcai-01.pdf,  and 
https://www.jair.org/index.php/jair/article/view/10430/25008