Patent Document ID: 8392455
Application ID: 12497353
Patent Status: 1

Claim One:
1. A method for determining a target path for a model-based control system which employs target value searching, wherein said model-based control system includes a directed acyclic graph, wherein the directed acyclic graph includes a plurality of vertices interconnected by a plurality of edges, wherein each of the plurality of vertices includes a range set, said method comprising the steps of: (1) generating, using an electronic processor, a multi-interval pattern database for the model-based control system including: (a) propagating the range sets of each of the plurality of vertices in a bottom-up order, wherein each of the propagated range sets is propagated from a source vertex to an immediate ancestor over an edge, wherein the range set of at least one of the plurality of vertices includes a plurality of intervals; and (b) adding the each of the propagated range sets to the range set of the immediate ancestor corresponding to the each of the propagated range sets, and fusing intervals of the each of the propagated range sets with intervals of the range set of the immediate ancestor corresponding to the each of the propagated range sets until a number of the intervals of the range set of the immediate ancestor corresponding to the each of the propagated range sets is within a maximum number of intervals, and (2) performing, using an electronic processor, a heuristic based target value search of the directed acyclic graph for determining the target path, wherein the heuristic based target value search uses a multi-interval heuristic to prune search space, and wherein the multi-interval heuristic uses the multi-interval pattern database to compare a prefix's target value against a prefix's last vertex's range, the prefix representing a path from an initial vertex to another vertex in the directed acyclic graph.