Some embodiments of the invention provide a path-searching method. This method identifies two sets of states in a multi-state space, where at least some of the states have at least one dimension. It then performs an epsilon-optimal path search to identify an epsilon-optimal path between the two set of states. The epsilon-optimal path is a path that is within an epsilon of the optimal path between the two sets of states. During the espsilon optimal search, the method propagates a cost function that is defined over one state to another state.