A Structural Complexity Measure for Predicting Human Planning Performance


Humans have an impressive ability to solve even computationally complex problems. Limited cognitive processing capabilities, however, impede an exhaustive search of the problem space. Thus, planning problems of the same size may require a different cognitive effort. Formal complexity aspects are inherent to a problem and set computational limits that a solver must deal with. For a measure of cognitive complexity, operational aspects of human cognition must be taken into account. We present a structural complexity measure for predicting human planning performance. This measure is based on the number and connectedness of subgoals necessary to solve a problem. This measure is evaluated on the PSPACE-complete puzzle game Rush Hour and is able to capture empirically measured difficulty for this game.

Back to Table of Contents