Fast suboptimal planning with nexus states

Despite recent advances, general-purpose planning still lags behind domain-specific planning in efficiency. We propose a method for automatic incorporation of domain knowledge into general-purpose planning by the identification of nexus, or well-connected, states in the domain. We present an analysis of under what circumstances this method will be applicable, and show that the method significantly improves planning time in two common benchmark domains, albeit with a measurable loss of plan optimality