Constraint Graph: Blocks World Planning

This is a picture of the logical structure of blocks world planning problems with 8 blocks and a notional plan length of 12. The dots represent decision variables, most of which are parts of the state descriptions, notably the function saying what each block is on in each state. A few of them (coloured purple in this image) represent the possible actions in each state, and the ones at the end of the coiled plan template represents the initial state. In the middle, causing the circular shape, are the variables recording the goal, which of course must be accessed at every step in order to check whether the plan is complete.

Constraint graphs of this kind are most useful for performance debugging, as they reveal problem structure such as critical variables, clustering and symmetries. Static pictures such as the one above are used in conjunction with their dynamic counterparts which show the pattern of variable assignment and propagation through constraints as the search progresses.