The constraint paradigm provides powerful concepts to represent and solve different kinds of planning problems. Typically a large and conflicting set of restrictions, objectives and preferences has to be considered for real planning problems. We introduce a unified formalism - called Petri decision nets - for representation and implementation of complex CSP solution algorithms. The formalism enables the consideration of the problem structure as well as given objectives and the usage of problem specific heuristics or expert knowledge. It is based on the fundamental assumption that designing CSP solution algorithms means designing decision networks.