Piecewise linear cost propagation for path searching

A method of processing information for finding a low cost path from a source to a target through a traversable region partitioned into a plurality of tiles, each tile being defined by a plurality of boundary segments, the method comprising:

• estimating a target cost function providing the cost to the target from an exit boundary segment of a tile;
• calculating a source cost function from the source to the exit boundary segment, wherein the calculating the source cost function comprises
• determining the relative orientation of the entry and exit boundary segments;
• performing a first type of source cost function propagation if the entry and exit boundary segments have a first relative orientation, wherein the first type of cost function propagation comprises finding a linear minimum convolution of the cost function of the exit boundary segment;
• and
• performing a second type of source cost function propagation if the entry and exit boundary segments have a second relative orientation;
• and
• calculating a path cost function from the source cost and the target cost.

A method of processing information for finding a low cost path from a source to a target through a traversable region partitioned into a plurality of tiles, each tile being defined by a plurality of boundary segments, the method comprising:

• estimating a target cost function providing the cost to the target from an exit boundary segment of a tile;
• calculating a source cost function from the source to the exit boundary segment, wherein the calculating the source cost function comprises:
• determining the relative orientation of the entry and exit boundary segments;
• performing a first type of source cost function propagation if the entry and exit boundary segments have a first relative orientation, wherein the first type of cost function propagation comprises:
• finding the linear minimum convolution of the cost function of the exit boundary segment using a first directional weight value;
• and
• calculating the source cost of the exit boundary segment using the found linear minimum convolution and a second directional weight value;
• and
• performing a second type of source cost function propagation if the entry and exit boundary segments have a second relative orientation;
• and
• calculating a path cost function from the source cost and the target cost.

A method of processing information for finding a low cost path from a source to a target through a traversable region partitioned into a plurality of tiles, each tile being defined by a plurality of boundary segments, the method comprising:

• estimating a target cost function providing the cost to the target from an exit boundary segment of a tile;
• calculating a source cost function from the source to the exit boundary segment, wherein the calculating the source cost function comprises:
• determining the relative orientation of the entry and exit boundary segments;
• performing a first type of source cost function propagation if the entry and exit boundary segments have a first relative orientation;
• and
• performing a second type of source cost function propagation if the entry and exit boundary segments have a second relative orientation, wherein the second type of cost function propagation comprises finding the minimum of a sum of expressions, the expressions including a function determined in part by a first directional weight, a function determined in part by a second directional weight and the cost function of the entry segment, wherein the minimum is found by evaluating the expressions only at knot points and not by evaluating every value of the continuous expressions;
• and
• calculating a path cost function from the source cost and the target cost.

A method of propagating cost from entry segment of a tile to an exit segment of the tile, the method comprising:

• determining the relative orientation of the entry and exit segments;
• performing a first type of cost function propagation if the entry and exit boundary segments have a first relative orientation;
• and
• performing a second type of cost function propagation if the entry and exit boundary segments have a second relative orientation.

A computer program product encoded in computer readable media for propagating cost from an entry segment of a tile to an exit segment of the tile, the product comprising:

• first instructions, executable by an information processing system for determining the relative orientation of the entry and exit segments;
• second instructions, executable by an information processing system for performing a first type of cost function propagation if the entry and exit boundary segments have a first relative orientation;
• and
• third instructions, executable by an information processing system for performing a second type of cost function propagation if the entry and exit boundary segments have a second relative orientation.

A computer program product encoded in at least one computer readable medium for processing information for finding a low cost path from a source to a target through a traversable region partitioned into a plurality of tiles, each tile being defined by a plurality of boundary segments, the computer program product comprising:

• a software module for estimating a target cost function providing the cost to the target from an exit boundary segment of a tile at least in part by finding a convex hull of the exit boundary segment and the target;
• and
• a software module for calculating a source cost function from the exit boundary segment to the source;
• and
• a software module for calculating a path cost function from the source cost and the target cost.

A method of estimating a least cost of a path from any point on a piecewise linear curve to a tile outlined by a plurality of boundary segments, the method comprising:

• finding a convex hull of the piecewise linear curve and the boundary segments of the tile;
• selecting a boundary segment of the tile not on the convex hull;
• propagating a cost function from the piecewise linear curve to the selected boundary segment;
• and
• repeating the selecting and the propagating at least until all boundary segments of the tile not on the convex hull have been selected.