Partial order planners have suffered a period of being unfashionable, supplanted by Graphplan and, more recently, relaxed-plan-based heuristic state-space search planners. VHPOP [Younes SimmonsYounes Simmons2003] represents an interesting indication that partial order planning is far from defunct. In particular, the partial order framework offers a powerful way to handle temporal constraints. In VHPOP a simple temporal network is used to manage the temporal constraints between the end points of durative actions and this allows the planner to successfully treat concurrency and other features of temporal plan structure. Within the framework of a partial-order planner, VHPOP makes use of plan graph distance estimates to guide its search.