System and method for time-aware path finding
View Patent ↗A method for obtaining solutions to combinatorial problems by way of a discrete state-based search approach utilizes a node evaluation function based both on solution quality and distance in search steps to a goal. The method considers the problem as finding the shortest path between an initial state and a goal state in a large graph and performs solution evaluation utilizing computation time balanced against solution quality. Rather than solely using a lower bound on the solution cost achievable below a search node, an estimate of the distance (in search steps) to the nearest solution below a search node is also utilized. These are combined using the user's stated utility function (represented as a function of time and cost) to evaluate candidate search nodes.
1. A method for obtaining solutions to a combinatorial problem, said method comprising:
maintaining a plurality of nodes, each of said nodes comprising a partial solution to said combinatorial problem;
performing a discrete state-based search of said plurality of nodes utilizing a user-specified utility function based both on solution quality and distance in search steps to a goal, said method stored and executed as a computer application, and said goal being a node comprising a desired solution;
initializing operation by creating an open queue to hold nodes that have been generated but not expanded;
applying the utility function to identify one of said nodes having a highest utility value, wherein said utility function considers both solution quality and solution time;
providing a utility default value, wherein said utility default value represents the utility of immediately returning an empty solution;
providing a solution quality importance factor;
providing a computation time importance factor;
determining solution cost for a particular node by multiplying an estimated cost of a solution with said solution quality factor;
determining solution time for a particular node by multiplying an estimated time at which a solution could be returned to the user with said computation time importance factor;
summing said solution cost for a particular node and said solution time for a particular node to determine a sum;
subtracting said sum from said utility default value; and
repeating determining said solution cost for another node, determining said solution time for another node, summing said solution cost and said solution time for said another node to determine another sum, and subtracting said another sum from said utility default value until a node with highest utility is identified;
removing said node with highest utility value from said open queue;
determining whether said node with highest utility value is a goal, wherein said goal is a desired problem solution;
generating a plurality of child nodes for said node with highest utility value if said node is not a goal, wherein each of said child nodes represents a different way of continuing to fill in the partial solution of the parent node, wherein said parent node comprises the node with highest utility value;
adding said parent node's child nodes to said open queue;
repeating the sequence of applying said utility function, removing a highest utility valued node, determining whether said highest utility valued node is a goal, generating child nodes, and adding said child nodes to said open queue until a problem solution is identified; and
returning at least one of said desired solution and path to said goal to the user.
2. A method for obtaining solutions to a combinatorial problem, said method comprising:
maintaining a plurality of nodes, each of said nodes comprising a partial solution to said combinatorial problem;
performing a discrete state-based search of said plurality of nodes utilizing a user-specified utility function based both on solution quality and distance in search steps to a goal, said method stored and executed as a computer application, and said goal being a node comprising a desired solution;
initializing operation by creating an open queue to hold nodes that have been generated but not expanded;
applying the utility function to identify one of said nodes having a highest utility value, wherein said utility function considers both solution quality and solution time;
removing said node with highest utility value from said open queue;
determining whether said node with highest utility value is a goal, wherein said goal is a desired problem solution;
generating a plurality of child nodes for said node with highest utility value if said node is not a goal, wherein each of said child nodes represents a different way of continuing to fill in the partial solution of the parent node, wherein said parent node comprises the node with highest utility value;
adding said parent node's child nodes to said open queue;
determining whether the utility value for each of said child nodes is less than zero;
repeating the sequence of applying said utility function, removing a highest utility valued node, determining whether said highest utility valued node is a goal, generating child nodes, and adding said child nodes to said open queue until a problem solution is identified; and
returning at least one of said desired solution and path to said goal to the user.
3. The method according to claim 2 , further comprising determining for each current of said child nodes whether a previously determined child node corresponding to each current child node is included within said closed list if said utility for each of said child nodes is not less than zero.
4. The method according to claim 3 , further comprising:
evaluating whether said current child node utility is better than said previously determined child node if said previously determined child node is included within said closed list; and
updating said previously determined child node and its children if said previously determined child node is better than said current child node.
5. The method according to claim 3 , further comprising:
evaluating whether said current child node utility is better than said previously determined child node if said previously determined child node is included within said closed list;
if said current child node utility is better, removing said previously determined child node from said closed list;
updating said previously determined child node; and
adding said updated previously determined child node to said open queue.
6. The method according to claim 3 , further comprising determining whether said previously determined child node is included in said open queue if said previously determined child node is not included in said closed list.
7. The method according to claim 6 , further comprising adding said current child node to said open queue if said previously determined child node is not included in said open queue.
8. The method according to claim 6 , further comprising determining whether said current child node utility is better than said previously determined child node if said previously determined child node is included in said open queue.
9. The method according to claim 8 , further comprising updating said previously determined child node if said current child node utility is better than said previously determined child node.
10. A method for obtaining solutions to a combinatorial problem, said method comprising:
maintaining a plurality of nodes, each of said nodes comprising a partial solution to said combinatorial problem;
performing a discrete state-based search of said plurality of nodes utilizing a user-specified utility function based both on solution quality and distance in search steps to a goal, said method stored and executed as a computer application, and said goal being a node comprising a desired solution, wherein said plurality of nodes are maintained in the form of a search tree, and wherein a utility bound is used to restrict a depth-first search to visit only nodes with high utility, and wherein stack frames represent the state of the search at each level in the search tree, and wherein a stack data structure is maintained to hold the frames, said discrete state-based search comprising:
initializing a root frame with an initial search node, wherein said root frame represents the state of the search at a first level in the search tree;
placing said root frame on the top of the stack frames, wherein said root frame becomes the top frame;
identifying a search node from said top frame;
determining whether said search node is a goal, wherein said goal is the desired problem solution;
determining whether said search node has child nodes above said utility bound if said node is not a goal;
generating a plurality of child nodes above said utility bound for said node if said node has child nodes, wherein each of said child nodes represents a different way of continuing to fill in the partial solution of the parent node;
initializing a new stack frame with said child nodes, wherein said new stack frame is pushed on top of the stack, wherein said frame on top of the stack comprises a top frame;
determining whether said top frame has another node if said search node does not have children;
determining whether said top frame is a root frame, if said top frame does not have another node;
decrementing said utility bound if said top frame is the root frame;
repeating said method steps from the step of identifying a search node from another top frame and determining whether said another search node is a goal until a goal is reached if said top frame has another node or said stack frames have been restructured or said new stack frame with said child nodes has been initialized; and
repeating said method steps from the step of initializing a new root frame, and determining whether said new search node is a goal until a goal is reached when said utility bound is decremented; and
returning at least one of said desired solution and a path to said goal to the user.
11. The method according to claim 10 , wherein decrementing said utility bound comprises using a highest utility value of any node that was generated but not expanded.
12. The method according to claim 10 , wherein decrementing said utility bound comprises using a statistical estimation to determine a decrement value by which to decrement said bound such that additional child nodes are generated when repeating the step of generating a plurality of child nodes based on a constant factor times a number of generated child nodes currently generated.
13. A method for obtaining solutions to a combinatorial problem, said method comprising:
maintaining a plurality of nodes, each of said nodes comprising a partial solution to said combinatorial problem;
performing a discrete stat-based search of said plurality of nodes utilizing a user-specified utility function based both on solution quality and distance in search steps to a goal, said method stored and executed as a computer application, and said goal being a node comprising a desired solution;
initializing operation by creating an open queue to hold nodes that have been generated but not expanded;
applying the utility function to identify one of said nodes having a highest utility value, wherein said utility function considers both solution quality and solution time;
removing said node with highest utility value from said open queue;
determining whether said node with highest utility value is a goal, wherein said goal is a desire problem solution;
generating a plurality of child nodes for said node with highest utility value if said node is not a goal, wherein each of said child nodes represents a different way of continuing to fill in the partial solution of the parent node, wherein said parent node comprises the node with highest utility value;
adding said parent node's child nodes to said open queue;
repeating the sequence of applying said utility function, removing a highest utility valued node, determining whether said highest utility valued node is a goal, generating child nodes, and adding said child nodes to said open queue until a problem solution is identified;
imposing a deadline on the search time or on the sum of the search time and solution execution time; and
returning at least one of said desired solution and a path to said goal to the user.
14. A method for obtaining solutions to a combinatorial problem, said method comprising:
maintaining a plurality of nodes, each of said nodes comprising a partial solution to said combinatorial problem;
performing a discrete state-based search of said plurality of nodes utilizing a user-specified utility function based both on solution quality and distance in search steps to a goal, said method stored and executed as a computer application, and said goal being a node comprising a desired solution, wherein said utility function utilizes estimates for cost and time when calculating utility;
initializing operation by creating an open queue to hold nodes that have been generated but not expanded;
applying the utility function to identify one of said nodes having a highest utility value, wherein said utility function considers both solution quality and solution time;
removing said node with highest utility value from said open queue;
determining whether said node with highest utility value is a goal, wherein said goal is a desired problem solution;
generating a plurality of child nodes for said node with highest utility value if said node is not a goal, wherein each of said child nodes represents a different way of continuing to fill in the partial solution of the parent node, wherein said parent node comprises the node with highest utility value;
adding said parent node's child nodes to said open queue;
repeating the sequence of applying said utility function, removing a highest utility valued node, determining whether said highest utility valued node is a goal, generating child nodes, and adding said child nodes to said open queue until a problem solution is identified; and
returning at least one of said desired solution and a path to said goal to the user.
15. The method according to claim 14 , wherein temporal difference learning is applied to calculate said estimates for cost and time.