Faster Optimal State-Space Search with Graph Decomposition and Reduced Expansion

for a path from a starting state to the goal in a state space most typically modelled as a directed graph. Prohibitively large sizes of the state space graphs make optimal search difficult. A key observation, as manifested by the SAS+ formalism for planning, is that most commonly a state-space graph is well structured as the Cartesian product of several small subgraphs. This paper proposes novel search algorithms that exploit such structure. The results reveal that standard search algorithms may explore many redundant paths. Our algorithms provide an automatic and mechanical way to remove such redundancy. Theoretically we prove the optimality and complexity reduction of the proposed algorithms. We further show that the proposed framework can accommodate classical planning. Finally, we evaluate our algorithms on various planning domains and report significant complexity reduction