AAAI Publications, Ninth Annual Symposium on Combinatorial Search

Font Size: 
Repair Policies for Not Reopening Nodes in Different Search Settings
Vitaly Sepetnitsky, Ariel Felner, Roni Stern

Last modified: 2016-06-20

Abstract


We examine two policies for reopening of nodes: never reopen (NR) and always reopen (AR). While there are circumstances where each policy isbeneficial, we observed empirically that NR is usually faster. However, NR may fail to return a solution of the desired quality in two scenarios:(1) in a bounded suboptimal search when inconsistent heuristics are usedand (2) in a bounded cost setting. To remedy this we provide two repair policies for NR when the desired quality was not obtained. The firstpolicy is to restart AR. The second policy is to repeatedly place the nodesthat were not reopened back in OPEN and continue with NR. Experimentalresults show that both repair polices outperform the AR policy.

Full Text: PDF