Pruning strategies

Using A$^*$ search with $h^{\mathrm{adm}}$ or $h^{\mathrm{emp}}$, the search space that needs to be explored is still huge and memory is frequently exhausted before a solution is found. In A$^*$ search, we store states in a priority queue. Memory-bounded A$^*$ limits the size of this queue by removing states that look unpromising. We present three such pruning strategies.

The first strategy is to prune the state $w_1^l = \mathrm{arg} \min _{w_1^l \in \mathrm{queue}} g(w_1^l) + h(w_1^l)$ when the priority queue's size exceeds a threshold. However, as $l$ increases $g(w_1^l) + h(w_1^l)$ tends to increase as well, so this pruning strategy tends to prune long partial paths before shorter ones. This introduces a bias towards short partial paths, and can be undesirable. We call this first strategy $g+h$.

The second strategy is to prune based on the normalized score $\mathrm{arg} \min _{w_1^l \in \mathrm{queue}} \left(g(w_1^l) + h(w_1^l)\right)/l$ when the threshold is exceeded. This corrects the bias caused by differences in length among the states. We call this strategy $(g+h)/l$.

A third strategy is to prune short states first; that is, prune $\mathrm{arg} \min _{w_1^l \in \mathrm{queue}} \lambda l + g(w_1^l) + h(w_1^l)$, where $\lambda$ is large enough that all states of length $l-1$ are pruned before states of length $l$. This strategy directly exploits the earlier insight that short partial paths are most likely to be safe to prune. Note that using strategy $\lambda l+g+h$, after the memory limit has been reached, our A$^*$ search is similar to beam search.