The neighborhood of a solution plan is generated by the application of a set of declarative plan-rewriting rules. These rules embody the domain-specific knowledge about what transformations of a solution plan are likely to result in higher-quality solutions. The application of a given rule may produce one or several rewritten plans or fail to produce a plan, but the rewritten plans are guaranteed to be valid solutions. First, we describe the syntax and semantics of the rules. Second, we introduce two approaches to rule specification. Third, we present the rewriting algorithm, its formal properties, and the complexity of plan rewriting. Finally, we present a taxonomy of plan-rewriting rules.