Provided is a system update procedure planning apparatus capable of preventing an explosive increase in the amount of computation when solving an automatic planning problem in system update. The state element model simplification section 101 outputs a simplified state element model by applying a simplification transformation based on the unit affiliation information to the state element model. The automatic planning section 102 outputs an executable route, for the simplified state element model, from an initial state thereof to a target state. The internal transition completion section 103 converts the executable route from the initial state to the target state on the simplified state element model into the executable route from an initial state to a target state on the state element model before simplification.