In this paper we introduce techniques for state pruning at runtime in a priori unknown domains. We describe how to identify states that can be deleted from the state-space when looking for both optimal and suboptimal solutions. We discuss general graphs and special cases like 8-connected grids. Experimental results show a speed up of up to an order of magnitude when applying our techniques on real-time agent-centered search problems.