Using multiple levels of costs for a pathfinding computation5893081Abstract A system for computing a path in a processor readable representation of a network which can minimize an identified cost. The cost can include time, distance, tolls paid, ease of turning, quality of scenery, processing time, waiting time, etc. A user of the pathfinding system can choose one or more categories of elements to avoid. For example, the user may want to avoid toll roads in a map of roads. The costs associated with the elements to avoid includes at least two levels of representation. The two levels of representation include a first level and a second level such that the second level is superior to the first level. The pathfinding system will determine a path which minimizes costs. Claims I claim: Description CROSS-REFERENCE TO RELATED APPLICATIONS/PATENTS
TABLE 1
______________________________________
C = A + B
A = a.sub.2 .omega..sup.2 + a.sub.1 .omega. + a.sub.o
B = b.sub.2 .omega..sup.2 + b.sub.1 .omega. + b.sub.o
C = (a.sub.2 + b.sub.2).omega..sup.2 + (a.sub.1 + b.sub.1).omega. +
(a.sub.0 + b.sub.0)
F = D + E
D = d.sub.1 .omega. + d.sub.o
E = e.sub.o
F = d.sub.1 .omega. + (d.sub.o + e.sub.o)
______________________________________
Similarly, the result of multiplication of the non-standard integer a.sub.1 .omega.+a.sub.0 by an integer x is equal to xa.sub.1 .omega.+xa.sub.0. Under non-standard arithmetic, one compares two costs A=a.sub.n .omega..sup.n +a.sub.n-1 .omega..sup.n-1 + . . . +a.sub.1 .omega.+a.sub.0 and B=b.sub.n .omega..sup.n +b.sub.n-1 .omega..sup.n-1 + . . . +b.sub.1 .omega.+b.sub.0 finding the largest j, such that a.sub.j .noteq.b.sub.j. If there is such a j and if a.sub.j >b.sub.j, then A>B. If a.sub.j <b.sub.j, then A<B. If there is no j such that a.sub.j .noteq.b.sub.j, then A=B. In one implementation, the costs will use powers of .omega. up to some fixed maximum. For example, it may be that all cost use only .omega. and .omega..sup.2. Other cost models may use higher powers of .omega.. By using a fixed maximum number of powers of .omega., a non-standard value can be represented by a computer as an array of integers. If the maximum power of .omega. used is .omega..sup.n, then costs can be represented by arrays of (n+1) integers. For purposes of using a computer, it is convenient to let the array ›a›n!,a›n-1!, . . . ,a›1!,a›0!! represent the value a›n!.omega..sup.n +a›n-1!.omega..sup.n-1 + . . . +a›1!.omega.+a›0!. Of course, there are other schemes for representing non-standard numbers. Given such representation of non-standard costs, two costs can be added by adding the corresponding elements and their respective arrays. That is, if the two costs represented by two arrays ›a›n!,a›n-1!, . . . a›1!,a›0!! and ›b›n!,b›n-1!1, . . . ,b›1!,b›0!! then the sum is represented by the array ›a›n!+b›n!,a›n-1!+b›n-1!, . . . ,a›1!+b›1!,a›0!+b›0!!. Similarly, to compare the representation of two non-standard costs, successive array values are compared starting with the n.sup.th element and proceeding towards the 0.sup.th element, until a difference is found. If no two corresponding values differ, the two costs are equal. For example, in the two arrays discussed above a›n! is first compared with b›n!. If these two values are unequal, the array with the greater value is the greater cost. If these two values are equal, then compare a›n-1! with b›n-1!, and so on. If it is the case that array B has no corresponding value to a›n!, that is, there is no b›n! or b›n!=0, then the A array is the greater cost. When multiplying a non-standard number represented by the array by a standard integer x, the result is represented by the array ›xa›n!,xa›n-1!, . . . ,xa›1!,xa›0!!. Using the above principle, the costs for the pathfinding process have multiple levels of representation, each level of representation being a different element of the array. In the array ›a›n!,a›n-1!, . . . ,a›1!,a›0!!, the first level of representation is a›0!, the second level of representation is a›1!, the third level of representation is a›2!, . . . , the (n+1).sup.th level of representation is a›n!. Each of the values in the array corresponds to a magnitude of a level of representation of the cost. That is, the array element a›n! is a magnitude of the (n+1).sup.th level of representation. A higher level of representation is considered superior to a lower level of representation. For example, a cost having its highest non-zero magnitude at a second level of representation is always greater than a cost having its highest non-zero magnitude at a first level of representation. In mathematical terms, a.omega..sup.n >b.omega..sup.n-1 for every non-zero a and non-zero b, where a and b are members of the set Z. Looking back at FIG. 3, assume that the network of FIG. 3 is an electronic map and that each of the links represents a road in an electronic map. The road is divided up into various categories of roads. Example categories include alleys, residential roads, arterials, freeways, toll roads and ferries. If a user wants to avoid toll roads unless they are absolutely necessary, the user may create a cost model where all the road types include costs having a non-zero magnitude for the first level of representation and zero magnitudes at all other levels, the exception being toll roads which will have non-zero magnitudes at the second level of representation. For example, if the cost is driving time and the particular segment of a toll road (a link) has a driving time of 5 driving time units, and the cost will be represented as 5.omega.+0 or by an array ›5,0!. If the user wanted to avoid ferries even more than avoiding toll roads, the cost model may include representing the costs of a ferry as (assuming ferry crossing time as 10) 10.omega..sup.2 +0.omega.+0 or ›10,0,0!. Looking at FIG. 3, assume that links 132 and 134 represent toll roads and that a user wants to avoid toll roads. A cost model is set up with two levels of representations. The costs of link 132 would be ›1,0! and the costs of link 134 is ›2,0!. The cost of path QT would be ›2,0!, the cost of QRST is ›1,4! and the cost of path QPRST is ›0,10!. In this example, the path with the smallest cost is QPRST. Since QPRST has the smallest total cost, it is defmed to be the most efficient path. A second example assumes that the user wants to avoid toll roads, and avoid ferries even more than avoiding toll roads. Assume that link 134 represents a toll road and link 132 represents a ferry. A cost model is set up with three levels of representation. The costs of link 134 is represented as ›0,2,0!. The costs of link 132 is represented as ›1,0,0!. The cost of traveling along the path QT is equal to ›0,2,0!, the cost of traveling along QRST is ›1,0,4!. That is, the path QRST includes traversing links 132, 138 and 140. The sum of the costs of those links, respectively, are ›1,0,0!+›0,0,2!+›0,0,2!=›1,0,4!. The cost of traveling along path QPRST is ›0,0,10!. Again, the shortest path is QPRST. In a third example, assume that the user wants to avoid using toll roads and that links 130, 132 and 134 are all toll roads. A cost model is set up with two levels of representation. The cost of traveling along path QT is ›2,0!. The cost of traveling along path QRST is ›1,4!. The cost of traveling along path QPRST is equal to ›4,6!. In that situation, all paths involve traveling on a toll road; therefore, the goal would be to minimize use of the toll road. This is accomplished by comparing all three costs. As discussed above, to compare the three costs first look at the highest power of .omega. or the element of the array with the largest index. In this case, the path QRST includes the smallest cost because the magnitude of its second level of representation is one. The magnitude of the second level of representation of the cost for the path QT is two and the magnitude of the second level of representation of the cost for the path QPRST is four. Multiple levels of costs can be used to perform a secondary minimization. For example, sometimes graphs can be simplified such that one link actually represents an aggregate of many other links. When creating that aggregate link, the sum of the costs can be stored as a second level of representation. The first level of representation is used to maintain a sum of the number of links in the aggregate. Thus, if two links of a cost 2 are added together, the result would be an aggregate sum of 4.omega.+2 or ›4,2!. The 4.omega. represents the sum of the two costs. The +2 represents the count of the number of links added together. The result of using this type of cost model allows the pathfinding system to minimize costs among paths that have the same costs by minimizing the total number of links in the computed path. Another alternative is to put the number of links as the higher level of representation than the actual cost, which allows the number of links be minimized ahead of costs. Another alternative includes using the norm of the cost. For a cost value A=a.sub.n .omega..sup.n +a.sub.n-1 .omega..sup.n-1 + . . . +a.sub.1,.omega.+a.sub.0, the norm is defined to be a.sub.n +a.sub.n-1 + . . . a.sub.1 +a.sub.0. The costs can be arranged so that the norm of the cost of a link provides an estimate of driving time (or another type of cost) for the link. However, one magnitude, on its own, may not necessarily be equal to the driving time. This will allow other factors to be used in minimizing costs. For example, assume a given geographic area has two highway links, both having a driving time of 10. One highway has ugly scenery and a lot of pot holes while the other highway has a smooth road and borders beautiful scenery. The pathfinding system may want to encourage use of the nicer highway. Rather than represent both costs as ›10,0!, the nice highway may be represented as 2.omega.+8 or ›2,8! while the ugly highway is represented 7.omega.+3 or ›7,3!. FIG. 4 shows a flow chart describing the process of finding a path using multiple levels of costs. Step 150 includes distinguishing elements for different levels of costs. This includes identifying one or more sets of elements (e.g. links or nodes) that are to be avoided. In one embodiment, the user of a pathfinding system would use a standard map database which only includes one level of costs. At run time, prior to finding a path, the user would be queried as to which elements should be avoided. The query could be open ended, allowing the user to select any element to be avoided or the user may be asked whether a specific category of elements should be avoided. The categories may be predefined categories inherent in the network database (e.g. toll roads, arterials, residentials, etc.) or user defmed categories. Alternatively, the pathfinding process could automatically choose a category to avoid. For example, the pathfinding system may be sold as a system that always attempts to avoid using toll roads. Alternatively, the map database can be created to include different levels of costs, thus, preselecting which types of elements are to be avoided. Step 150 can include distinguishing one category of elements or many categories of elements. Another alternative embodiment includes singling out a category of links to be favored. That is, the analysis could be reversed. A cost with a second level of representation could be considered less than one with a first level of representation. Alternatively, all the costs not favored would have a second level of representation and the costs favored would only include a first level of representation. In step 152, the system creates new levels of costs. A cost structure may need to be set up if it has not already been done. For each category that was distinguished in step 150, data is inserted in the array such that the cost information includes a non-zero magnitude in a level of representation higher than the first level. For example, in Step 150, if the user distinguished toll roads as the only category for avoidance, then in step 152 costs for toll roads would be set up with non-zero magnitudes in the second levels of representation. If at step 150, the user distinguished toll roads and ferries as elements for different levels, with ferries to be avoided more than toll roads, then at step 152, toll roads would be set up with non-zero magnitudes in the second level of representation and ferries would be set up with non-zero magnitudes in the third level of representation. Step 152 includes creating or filling the arrays discussed above. If the system is working with a preexisting map database that already includes costs having only one level of representations, than some of these costs will be replaced with the new costs having a non-zero magnitude at a second level of representation. In one alternative, a new map database can be created which includes the new costs. This new map database is stored in a processor readable storage medium. In a second alternative, the original map database will remain unedited and the new costs will be stored in an additional data structure. After step 152, the system performs a pathfinding exploration in step 154. FIG. 5 represents the directed graph for a portion of an electronic map. The directed graph depicted includes ten nodes (A, B, C, D, E, F, G, H, J, and O) and various links between the nodes. Each of the links include a number adjacent to the link. This number represents the cost of traveling along that link. FIG. 5 will be used along with FIG. 6 to further explain the details of step 154 in FIG. 4. For example purposes, assume that in step 150 of FIG. 4, a user distinguished toll roads as the only category of links to be avoided. Assume for purposes of this example that the links connecting node H to node D (two links in opposition directions), are part of a toll road and the remainder of the links are not toll roads. The original map data base included the costs as shown in FIG. 5. In step 152, the cost structure for toll roads is changed to include two levels of representation. The cost of the link for traveling from node H to node D is represented as 4.omega.+0 or ›4,0!. FIG. 6 is a flow chart which explains the pathfinding computation (also called a pathfinding exploration). The pathfinding computation of FIG. 6, which is based at least in part on the work of Edsger W. Dijkstra, is only one of many pathfinding methods that can be used with the present invention. One reference that discusses Dijkstra's method is M. N. S. Swamy and K. Thulasiraman, Graphs, Networks, and Algorithms, John Wiley & Sons (1981). In step 202 the system initializes the pathfinding computation. That is, the system stores the origin and destination of the path and sets up two queues: an origin priority queue and a destination priority queue. The origin priority queue consists of an ordered list of nodes, to each of which a path from the origin is known, and a key for each node. The queue is sorted according to the key. There are various alternatives for determining the key. In one alternative, the key is the lowest known cost of traveling from the origin to the node. An alternative key includes the sum of the shortest known distance from the origin to the node plus an estimated cost of traveling from the node to the destination. There are various alternatives for estimating the cost for traveling from the node to the destination which is suitable for this method. One example includes multiplying the direct "as-the-crow-flies" distance by the estimated cost per unit distance. That is, disregarding the nodes and links, determining the physical distance between the node and the destination and multiplying that distance by an estimated cost per unit distance. The destination priority queue consists of an ordered list of nodes, from each of which a path to the destination is known, and a key for each node. The queue is sorted according to the key. There are many alternatives for determining a destination key. One alternative includes using the lowest known cost path from the node to the destination. An alternative key includes using the sum of the lowest known cost from the node to the destination plus an estimated cost from the origin to the node. Other methods of computing a key are suitable within the scope of the present invention. Additionally, the system sets up an origin visited list and a destination visited list. The origin visited list maintains a list of all nodes to which paths from the origin are known, the lowest cost for traveling from the origin to the node, and the previous node along the path with that lowest cost. The destination visited list stores the name of each node for which paths to the destination are known, the lowest known cost for traveling from the node to the destination, and the identity of the next node along the path to the destination with that lowest cost. After the initialize step 202 is completed, the origin priority queue and the origin visited list include the origin, and the destination priority queue and the destination visited list include the destination. Once the system is initialized, the system chooses a queue according to a rule in step 204. There are many rules of picking a queue which are suitable for the present invention. In one system, the queue containing the element with the smallest key is chosen, with ties broken arbitrarily. In another system, the queue containing the fewest elements is chosen. Other examples of rules for choosing a queue include alternating between queues, choosing the origin queue for a time period, switching to the destination queue for a time period, switching back to the origin queue for a time period, etc. Since the queues are sorted by keys, the node with the smallest key will be at the head of the queue (also called the front or the top of the queue). This node is called the "head node." In the example discussed below, the method for picking a queue will be to alternate starting with the origin priority queue. In step 206 the system looks for all nodes which are adjacent nodes to the head node of the chosen queue. Since the system just started, the only node in the origin priority queue is the origin. The adjacent nodes are those nodes which can be traveled to from the origin without going through any other nodes. The adjacent nodes for the origin O are nodes A, B, G and H. Since there are four adjacent nodes, the system arbitrarily picks one adjacent node. In step 208 the system determines whether there is a lower cost known on the visited list or the priority queue for the adjacent node picked. That is, the system determines the cost of traveling between the adjacent node and the head node. In this case, the adjacent node picked is node A, the cost of traveling from the origin to node A is 9. Since the pathfinding computation has just started, node A is not on the visited list or the origin priority queue so there is no other cost known for node A. If there is a lower cost known (in step 208), the system loops back to step 206 Since there is no known cost, in step 210 the system edits the visited list and the priority queue to add node A and its cost. The method loops back to step 206 to determine whether any additional adjacent nodes have not been considered. In this case there are three adjacent nodes that have not been considered: B, G and H. In step 208 the system determines whether there is a lower cost known for node B. The cost for traveling from origin to B is 3 and B does not appear on the priority queue or the visited list. In step 210 node B is added to the priority queue and the visited list. The system loops back to step 206 and considers node G, and since there is no cost known lower than the cost of going directly from the origin O to G, which is 7, G is added to the priority queue and the visited list. The system then loops back to step 206 and considers node H. Since there is no known cost lower than the cost of going directly from origin O to node H, which is 2, H is added to priority queue in the visitor list. The system loops back to step 206 and determines that there are no additional adjacent nodes; therefore, in step 212 the head node, which is currently the origin O, is removed from the priority queue. Table 2 reflects the contents of the origin priority queue and the visited list at this point in the pathfinding computation. There are four nodes on the origin priority queue: B, G, A and H. Their keys represent the cost of traveling from the origin to that node. The visited list has three columns: Node, Cost and Prev. The node column lists the node identification, the cost column lists the lowest known cost of traveling from the origin to that node and the Prev column lists the previous node along the path from the origin to the listed node when traveling along the path utilizing the lowest known cost. The order that the nodes are listed in the visited list can be any order that makes it easy to search the list. For example, the nodes can be listed in alphabetical order. In one implementation, the nodes are named by numerical codes and the visited list is a hash table.
TABLE 2
______________________________________
Origin Priority Queue
Origin Visited List
Node Key Node Cost Prev
______________________________________
H ›0,2! A ›0,9!
O
B ›0,3! B ›0,3!
O
G ›0,7! G ›0,7!
O
A ›0,9! H ›0,2!
O
O ›0,0!
O
______________________________________
In step 214 the system determines whether a stopping condition has been met. There are many stopping conditions which are suitable for the present invention, for example, stopping when a node has been the head node on both the origin priority queue and the destination priority queue. Another stopping condition, which is the stopping condition used in this example, is stopping when the cost of traveling from the origin to the head node in the origin priority queue plus the cost of traveling from the head node of the destination priority queue to the destination is greater than or equal to the total cost of the best connection node. A connection node is a node that appears on the destination visited list and the origin visited list. The total cost of a connection node is the cost from the origin to the connection node plus the cost from the connection node to the destination. The best connection node is the connection node with the lowest total cost. In the present case there is no connection node so the stopping condition fails and, in step 204, the system picks a queue. As discussed above, the method for picking a priority queue in the present example is simply alternating; therefore, the system picks the destination queue. In step 206 the system determines whether there are any nodes adjacent to the destination D. In the present example, there are three adjacent nodes C, F and H. In step 208 the system looks at node C and determines whether there is a lower known cost. Since there is not, in step 210 the destination priority queue and visited list are edited to add node C and its cost. The method loops back to step 206 which determines that there is another adjacent node, node F. In step 208 the system determines that there is not a lower cost known for F. The priority queue and visited list are edited in step 210 to add node F. The method then loops back to step 206 which determines that there is another adjacent node, node H. In step 208, the system determines that there is not a lower cost known for traveling from H to D. In step 210, the destination priority queue and the visited list are edited to add node H and its cost to traveling to D, which is 4.omega. or ›4,0!. In step 206 the system determines there are no more adjacent nodes to node D and node D is removed from the destination priority queue in step 212. Table 3 reflects the state of the destination priority queue and visited list at this point in the method.
TABLE 3
______________________________________
Dest. Priority Queue
Dest. Visited List
Node Key Node Cost Next
______________________________________
F ›0,2! C ›0,5!
D
C ›0,5! D ›0,0!
D
H ›4,0! F ›0,2!
D
H ›4,0!
D
______________________________________
In step 214, the system determines whether the stopping condition has been met. At this point there is a connection node. Node H is on both visited lists. The total cost for node H is ›4,2! or 4.omega.+2. That is, the cost of traveling from the origin to node H is ›0,2! and from node H to the destination is ›4,0!. The stopping condition is not met because the cost of traveling from the origin to the head node in the origin priority queue (H) is ›0,2! and the cost of traveling from the head node of the destination queue (F) to the destination is ›0,2!. The sum of the two costs is ›0,4! which is lower than the total cost of the connection node H; therefore, the stopping condition fails and the system picks the origin priority queue in step 204. The head node on the origin priority queue is node H. The only adjacent node to node H is node D. In step 208, there is not a lower cost known for node D. Therefore, in step 210 the visited list and priority queue are edited to include the cost of traveling to node D from node H, which is ›4,0!. Table 4 reflects the current state of the origin priority queue and the visited list after node 4 was removed from the priority queue (step 212).
TABLE 4
______________________________________
Origin Priority Queue
Origin Visited List
Node Key Node Cost Prev
______________________________________
B ›0,3! A ›0,9!
O
G ›0,7! B ›0,3!
O
A ›0,9! D ›4,2!
H
D ›4,2! G ›0,7!
O
H ›0,2!
O
O ›0,0!
O
______________________________________
In step 214, the system determines whether the stopping condition has been met. At this point, there are two connection nodes: node H and node D. The total cost of node H is ›4,2!. The total cost for node D is also ›4,2!. The cost of traveling from the origin to the head node of the origin priority queue and from the head node of the destination queue to the destination is equal to ›0,7! which is less than the total cost for nodes H and D; therefore, the stopping condition fails. In step 206 the system looks for adjacent nodes to the head node on the destination queue. Since the head node is node F, the only adjacent node is node E. Note that node D is not processed as an adjacent node because it is the node used to get to F. The cost of traveling from E to F is ›0,2!, thus, the cost traveling from E to F to D is ›0,4!. In step 208 the system determines that there is not a lower cost known for traveling from E to D so the visited list and priority queue are updated accordingly. In step 206 the system determines that there is not another adjacent node and F is removed from the priority queue in step 212. Table 5 reflects the state of the destination priority queue and visited list at this point in the method.
TABLE 5
______________________________________
Dest. Priority Queue
Dest. Visited List
Node Key Node Cost Next
______________________________________
E ›0,4! C ›0,5!
D
C ›0,5! D ›0,0!
D
H ›4,0! E ›0,4!
F
F ›0,2!
D
H ›4,0!
D
______________________________________
In step 214, the system determines whether the stopping condition has been met. At this point there are still two connection nodes: H and D. The stopping condition is not met because the cost of traveling from the origin to the head node (B) in the origin priority queue is ›0,3! and the cost of traveling from the head node (C) from the destination priority queue to the destination is ›0,5!. The sum of the two costs is ›0,8! which is lower than the total cost for connection nodes H or D. From Table 4, it can be seen that the head node on the origin priority queue is node B. The adjacent nodes to node B are nodes A and E. In step 208, the system looks at node A and determines that there is not a lower cost known for node A. Although A does appear in the visited list with a cost of ›0,9!, the cost of traveling from the origin to node A via node B is ›0,6!. That is, the cost of traveling from 0 to B is ›0,3! and the cost of traveling from B to A is ›0,3!. Thus, the cost of traveling from O to B to A is ›6,0! which is lower than the cost of traveling from 0 directly to A. Therefore, in step 210, the visited list and the priority queue are edited to include the cost of traveling to node A from the origin, which is now ›0,6! and the previous node in the visited list for node A becomes B. That is, to get from A to O at a cost of ›0,6!, one must travel through node B. In step 206, the system determines that there is another adjacent node, E. In step 208 the system determines that there is not a lower cost known for E and the priority queue and visitor list are edited to include E. Table 6 reflects the current state of the origin priority queue and the visitor list after node B was removed from the priority queue (step 212).
TABLE 6
______________________________________
Origin Priority Queue
Origin Visited List
Node Key Node Cost Prev
______________________________________
E ›0,5! A ›0,6!
B
A ›0,6! B ›0,3!
O
G ›0,7! D ›4,2!
H
D ›4,2! E ›0,5!
B
G ›0,7!
O
H ›0,2!
O
O ›0,0!
O
______________________________________
In Step 214 the system determines that the stopping condition has been met. At this point there are three connection nodes: E, H, D. The total cost of connection node E is ›0,9!, the total cost of connection node H is ›4,2! and the total cost of connection node D is ›4,2!. Since node E has the lowest total costs of all the connection nodes, node E is considered the best connection node. The cost of traveling from the origin to the head node on the origin priority queue is ›0,6!. The cost of traveling from the head node of the destination priority queue to the destination is ›0,5!. Therefore, the cost of traveling to and from the head nodes is ›0,11!, which is greater than the total cost of the best cost connection node, which is ›0,9!. Thus, the stopping condition is met and the system builds the path in step 216. The step of building the path is as follows. A rule selects some connection node. One such rule is to choose the best connection node. The selected connection node K is looked up in the origin visited list and the previous node P.sub.1 on the path from the origin is found. If P.sub.1 is not the origin, then P.sub.1 is looked up in the visited list and the previous node P.sub.2 on the path in the origin is found. This continues until the origin is reached. Suppose the origin is reached as node P.sub.L. Similarly, K is looked up in the destination visited list and the next node N.sub.1 on the path to the destination is found. If N.sub.1 is not the destination, then N.sub.1 is looked up in the visited list This continues until the destination is reached. Suppose the destination is reached as node N.sub.M. At this point the path from the origin to the destination is known: it is the path from P.sub.L (the origin) to P.sub.L-1, to P.sub.L-2, . . . to P.sub.2, to P.sub.1, to K, to N.sub.1, . . . , to N.sub.M-1, to N.sub.M (the destination). In the present example, node E was the best connection node. Looking at the visited list in Table 6, the best known cost of traveling from the origin to node E involves traveling from node B to node E. Thus, the path being built will travel from B to E. The system then finds node B in the visited list and determines that the best path to node B is directly from the origin O. At this point the path built includes traveling from O to B to E. After the system reaches the origin, the system builds a path from the connection node to the destination. Looking at the visited list in Table 5, the best path from E to the destination involves traveling from E to F. Thus, P is added to the path. The visited list also indicates that the best path from P to D is directly from F to D. Thus, the path built is OBEFD. As can be seen, the pathfinding computation avoids the use of the toll road represented by the link from H to D. In some systems, the pathfinding computation is speeded up by not considering all nodes to which a head node is connected to. Rather, the exploration is limited to certain neighboring nodes. One such method classifies nodes according to the importance of the roads on which they occur, and progressively restricts the use of neighboring nodes as a distance from the origin (or to the destination) increases. For example, if the cost measure being used is an estimate of driving time, the exploration might not use residential-level roads more than two minutes' driving time from the origin or destination, nor use arterial-level roads more than ten minutes' driving time from the origin or destination, and so on. In one implementation of the current invention, an electronic map will be stored as a separate database and the pathfinding apparatus will include software with two main modules. A first module performs steps 150 and 152 of FIG. 4. The second module performs the pathfinding function. The first module will set up a cost model which indicates how many levels of representation to use for storing the costs and an index (or definition) for determining costs. The index would include such information as for every arterial the cost will be equal to X multiplied by each unit of distance of the link, for each residential the cost will be equal to Y multiplied by each unit of distance for the link, and so on. The cost model is passed to the pathfinding function. In one alternative, the present invention can be used as part of a dynamic traffic avoidance system using an electronic map. A driver may learn that a particular road or set of roads are experiencing traffic problems. Looking at FIG. 4, the driver will use the system to identify the roads experiencing traffic problems in step 150. The costs for the roads experiencing traffic problems will have a non-zero magnitude for the second level of representation (e.g. a.sub.1 .omega.+a.sub.0, where a.sub.1 .noteq.0). In step 154, a path will be computed which directs the driver to the destination while avoiding the roads experiencing traffic problems. Although the examples used above to describe the present invention were directed to an electronic map of roads, the present invention also applies to any suitable processor readable representation of a network. Suitable networks include a graph of a manufacturing process, intermodal travel plan (e.g., a graph representing travel between points via airplanes, trains, automobiles, buses, etc.), a system for providing medical treatment, etc. For example, if the network represents a manufacturing process, the nodes may represent decision points in the process (e.g. which station to transport the article of manufacture or which semiconductor process to use), and the links can represent process time or manufacturing costs. The foregoing detailed description of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and obviously many modifications and variations are possible in light of the above teaching. The described embodiment was chosen in order to best explain the principles of the invention and its practical application to thereby enable others skilled in the art to best utilize the invention in various embodiments and with various modifications as suited to the particular use contemplated. It is intended that the scope of the invention be defmed by the claims appended hereto.
|
Same subclass Same class Consider this |
||||||||||