Skip to content

v0.0.59: [PE] Extend heuristic search by cost-based pruning

Compare
Choose a tag to compare
@mirror-releases mirror-releases released this 27 Jun 12:35
· 713 commits to main since this release
3fa86f0
During heuristic search, whenever we find a goal state during state
expansion, we know that the shortest path is no more costly than the
current cost `g` by which we reached that goal state.  We can exploit
this fact to prune all states that are more costly from the search. This
is done by remembering the least cost by which a goal was reached in
`least_path_cost`. Whenever a new state with equal or higher `g` is
generated during expansion, that state can immediately be discarded.
This does not violate soundness, completeness, or optimality.

The amount of pruning achieved by this method highly depends on the
search problem and needs extensive evaluation.

Heuristic search with cost-based pruning can be bootstrapped by running
a greedy search first, which gives us an upper bound for the cost of a
shortest path.  This cost is then used to initialize `least_path_cost`.
Currently, we use GOO for initializing `least_path_cost`.