System and method for time-aware path finding
US7389279B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 24, 2005 |
| Grant date | Jun 17, 2008 |
| Priority date | — |
| Expiry date | Sep 19, 2025 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY02P90/30
- WIPO fieldIT methods for management
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.