A theoretical analysis of conjunctive-goal problems

摘要

Region analysis is a new technique for analyzing search problems by applying graph theory to problem state spaces. The analysis here is of search problems, not search algorithms; analyzing problems and classes of problems lets us understand the underlying structure and inherent complexity of those problems. The analysis technique is demonstrated in the domain of robot planning problems. Region analysis of conjunctive-goal planning problems gives us a characterization of subgoal interactions that is independent of the problem representation. We give a formal characterization of nonlinear planning problems, and show that nonlinearity is a weak characterization of the difficulty in planning problems.