Some embodiments of the invention provide a method of expanding a path in a space with dimensional states. In some embodiments, the space includes a set of states and a transition map that specifies a set of states that can be reached from each particular state. The method identifies a first expansion for the path from a start state to a first destination state. It then specifies a first cost function that expresses the cost of the first expansion. The first cost function is defined over the destination state. The method also identifies a second expansion for the path from a first portion of the first destination state to a second destination state. From a portion of the first cost function that is defined over the first portion of the first destination state, the method computes a second cost function that specifies the cost of the second expansion.