This paper illustrates how a modified version of a modern Partial Order Planner (POP) can be combined with a replanning algorithm
to solve planning problems in Web service domains. The contributions of the work are (i) a method of using feedback gained
from plan execution for improving plan search and (ii) a novel approach of dealing with nondeterministic Web service operations.