Claudia and I converged to one version that is ready to review:  https://github.com/aibasel/downward/pull/283/

I ran the tests a couple of times on my machine with and without the extra tests and could not see a significant difference in the runtime. So, I added the extra tests (and one for SEARCH_UNSOLVABLE_WITHIN_BOUND) to the PR.

Usually it's a good first approximation that if a test is worth writing, it's worth keeping. A simple way to see how much time the tests take is to use "time", for example "time tox -e driver".

In total they do make the driver tests longer because they all use an unsolvable task (even though it is a small one). I am not sure if the time increase is acceptable and thus committed only five of those.

Furthermore, Simon pointed out that tests for the new SEARCH_UNSOLVABLE_WITHIN_BOUND are missing. I plan to add some for this as well.

Thanks, Claudia! If these are useful tests, I would add them permanently, not just temporarily, provided that they don't take too long.

The pull request now also includes five new test cases for `tox -e driver`. For this, I also added a new benchmark file. It is a small blocksworld problem that I adjusted such that it is unsolvable but where unsolvability is not detected by the translator (otherwise the translator would pass a trivially unsolvable SAS-file to the search component).

I also ran `tox -e driver` once with more than those five new test cases. Specifically, I (temporarily) added the following lines to SEARCH_TESTS in downard/misc/tests/test-exitcodes.py:

    ("unsolvable", [], "astar(blind())",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVABLE)),
    ("unsolvable", [], "astar(lmcut())",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVABLE)),
    ("unsolvable", [], "lazy(single(lmcut()))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVABLE)),
    ("unsolvable", [], "eager(alt([single(const(infinity)),single(const(1))]))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVABLE)),
    ("unsolvable", [], "eager(type_based([const(infinity),const(1)]))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVABLE)),
    ("unsolvable", [], "eager(pareto([const(infinity),const(1)]))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVABLE)),
    ("unsolvable", [], "eager(tiebreaking([const(infinity),const(1)],unsafe_pruning=false))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVABLE)),
    ("unsolvable", [], "ehc(blind())",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVED_INCOMPLETE)),
    ("unsolvable", [], "eager(single(blind(),pref_only=true))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVED_INCOMPLETE)),
    ("unsolvable", [], "eager(pareto([blind()],pref_only=true))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVED_INCOMPLETE)),
    ("unsolvable", [], "eager(pareto([cg(),cea()]))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVED_INCOMPLETE)),
    ("unsolvable", [], "eager(tiebreaking([const(infinity),blind()]))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVED_INCOMPLETE)),
    ("unsolvable", [], "eager(alt([single(cg()),single(const(infinity))]))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVED_INCOMPLETE)),
    ("unsolvable", [], "lazy(type_based([cg(),const(infinity)]))",
        defaultdict(lambda: returncodes.SEARCH_UNSOLVED_INCOMPLETE)),

I suggest these three outputs then.
"Search terminated without finding a solution."
"Search terminated -- no solution exists."
"Search terminated -- no solution for cost bound 42 exists."

We should also discuss how to handle the line "Completely explored statespace -- no solution" from eager and lazy search which is printed when the open list becomes empty. 

With an incomplete configuration this is not correct as the search might not actually have completely explored the state space. Furthermore, with a too small bound but a configuration that is complete relative to that bound this might be misleading.

One option would be to remove the line altogether. However, keeping this (kind of) information in the planner output is probably preferable. So the question is what else to print.

Some ideas:

- "Search terminated without finding a solution."
- Print different text depending on whether the configuration is complete and / or unbounded (which we can now both check). If it is unbounded and complete we could print the current text.

We implemented completeness checks in the search algorithms (except for IteratedSearch, see below), open lists, and pruning methods. For the evaluators we mostly rely on the existing is_safe() function (previously called dead_ends_are_reliable()) and fixed it for the ConstEvaluator and WeightedEvaluator.

Since the completeness checks are only relative to the given g-bound (if one is given) we added the new exit code SEARCH_UNSOLVABLE_WITHIN_BOUND=13. We also use SEARCH_UNSOLVABLE in more places now since the completeness checks enabled this.

We did not yet implement the completeness check for IteratedSearch because without solving the component interaction problem this is not possible from a static context. Instead of making all other completeness checks non-static we return false for the completeness check of IteratedSearch and print a warning that it is not yet implemented.

The current PR is at: https://github.com/aibasel/downward/pull/283/

We plan to also add some tests for the new exit code in the github actions. This should have no impact on the files in src/search and we think the PR could already be reviewed now and the tests could be reviewed later once they are added. But there is no rush so the reviewers can wait it out until we actually added the tests.

Archiving some notes from our February 2026 sprint where we pulled a story to add optimality and completeness checks (we dropped optimality checks at some point during the sprint to focus on completeness checks).


Eager best-first search
-----------------------

- when changing the cost_type we cannot guarantee optimality (with regard to the input task, not necessarily to the configuration)
- without reopening, we cannot guarantee optimality (exception is A* with a consistent heuristic)
- uses is_dead_end (instead of is_reliable_dead_end), which in general also considers unsafe heuristics
- lazy_evaluator is not passed to openlist (and does not do anything if it is not chosen to be the same Evaluator as in the OpenList)
- relevant aspects see the online documentation (except for lazy evaluator)


Notes

- It seems that the OpenLists already have a mechanism to tag unsafe heuristics
- The open list has to check if any of its components (sub-open-lists and heuristics) might violate optimality / completeness.
- completeness is relative to the g bound


Goal for this sprint: report completeness guarantees (not optimality)

- at the moment, there are only pruning methods that preserve completeness, but we should add a method is_complete (for the case that future pruning methods are incomplete) done
- heuristics/evaluators need a method is_safe already have dead_ends_are_reliable
- update exit codes in documentation (11, 12) done

We would like to adapt the search component so that it can in more unsuccessful
cases return that the task is unsolvable (not only that it did not find a
solution).

The idea is to analyze the configuration in a task-independent way
so that it can be done by the task-independent components once the component
interaction problem has been resolved.