|
|
Created on 2026-01-01.23:38:59 by dawson-tomasz, last changed by dawson-tomasz.
|
| File name |
Uploaded |
Type |
Edit |
Remove |
|
probBLOCKS-4-2.pddl
|
dawson-tomasz,
2026-01-01.23:38:59
|
application/octet-stream |
|
|
|
| Date |
User |
Action |
Args |
| 2026-01-02 06:30:50 | dawson-tomasz | set | summary: 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. This should
not be so; see [https://link.springer.com/chapter/10.1007/3-540-39963-1_23] and
[https://gki.informatik.uni-freiburg.de/papers/hoffmann-ijcai-01.pdf]. Furthermore, in
[https://www.jair.org/index.php/jair/article/view/10430/25008] it's noted that "the behavior of
h+ with respect to deadends is provably the same as that of hFF".
The issue arises due to the global closed list. Say an instance of EHC is beginning its next
search for a new minimum from state s. 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 than s is by passing through
the closed list, the current implementation will not find that path. Instead, the open list is
emptied and the algorithm will fail.
Attached is a small blocksworld instance where exactly this happens---states are not added to
the local open list because they were visited in a previous EHC search step. Blocksworld has no
deadends, and FF will not misreport solvable states as dead-end states, and so this behaviour is
inconsistent with the theoretical guarantees of EHC with the FF heuristic.
This issue is related to the closed issue631. -> 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 |
| 2026-01-01 23:38:59 | dawson-tomasz | create | |
|