I like to split out exploration and discovery (research) as a third step (the first step) in the process. Before a plan can be devised research needs to be conducted. The more time between research, planning, and execution increases the likelihood of rework or failure.

The best time to plan is dependent on how stable/unstable the environment is.