Using multiple levels of costs for a pathfinding computation
AssigneeEtak, Inc.
InventorRichard Frederick Poppen
Life of this patent
Estimating the term…
Abstract
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.
Claims50
A computer implemented method for finding a path between an origin and a destination using a processor readable representation of a network, comprising the steps of:
- distinguishing a first set of one or more elements in said processor readable representation of said network, each of said first set of elements being associated with one or more original costs;
- creating a first set of one or more new costs associated with said first set of elements, said one or more new costs including at least two levels of representation;
- and
- determining a path in said processor readable representation of said network from said origin to said destination, using a processor, said step of determining uses at least one of said new costs.
A method for creating an electronic map, comprising the steps of:
- identifying nodes,
- identifying a set of links between nodes;
- identifying a first subset of links to attempt to avoid;
- assigning costs for traversing said set of links, at least a first subset of one or more costs including a first level of representation and a second level of representation, said second level of representation being superior to said first level of representation, said first subset of one or more costs being associated with said first subset of links;
- and
- storing data representing said nodes, said links and said costs in a map database, said map database residing in a processor readable storage medium.
A method of enhancing an electronic map database, said map database including nodes, links between nodes and costs of links, the method comprising the steps of:
- receiving an input identifying a set of links to attempt to avoid;
- creating an indication of a second level of costs for said set of links;
- and
- storing said indication of second level of costs in a processor readable storage medium, said stored second level of costs being associated with said electronic map database such that said electronic map database and said second level of costs can be used to determine a path in said electronic map database from an origin to a destination that attempts to avoid said set of links.
A processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method of finding a path using a processor readable representation of a network, said processor readable code comprising:
- first program code, said first program code finds a first path from a first node to a second node, said first path including a first set of one or more links and a first set of one or more costs;
- second program code, said second program code finds a second path from said first node to said second node, said second path including a second set of one or more links and a second set of one or more costs, at least one of said second set of costs having at least two levels of representation, and
- third program code, said third program code chooses said first path because said first set of one or more costs is more efficient than said second set of one or more costs.
An apparatus for finding a path from an origin to a destination using a processor readable representation of a network, comprising:
- an input device;
- a processor readable storage device capable of storing at least a portion of said processor readable representation of said network;
- a display;
- and
- a processor in communication with said input device, said storage device and said display, said processor being programmed to:
- distinguish a first set of one or more elements in said network;
- create a first cost associated with a first element of said first set of elements, said first cost including at least two levels of representation;
- and
- determine a path from said origin to said destination using said first cost.
A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method of finding a path from an origin to a destination using a processor readable representation of a network, said method comprising the steps of:
- distinguishing a first set of one or more elements in said network, each of said first set of elements being associated with one or more original costs;
- creating a first set of one or more new costs associated with said first set of elements, said new costs including at least two levels of representation;
- and
- determining a path in said processor readable representation of said network from said origin to said destination using at least one of said new costs.
A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method of finding a path from an origin to a destination using a processor readable representation of a network, said method comprising the steps of:
- creating an indication of a second level of costs for a set of one or more elements in said processor readable representation of a network;
- and
- determining a path in said processor readable representation of said network from said origin to said destination using said second level of costs.
Dependencies are inferred from the claim text.