Patent ID: 8280574
Filing Date: 2012-10-02
Classification: G05D,G06Q

Abstract:
1. A path search device that selects a minimum cost path among paths from a start point to an end point, which are included in an area represented by a grid, the path search device comprising: a path cost calculation section that calculates a cost of a path from the start point to the end point, assuming that each grid point is a node and that, when a node obtained by tracing back a predetermined number of nodes from a focus node of current interest in a direction toward the start point along the path is a reference node, a cost of an edge extending from the focus node to a neighboring node adjacent to the focus node is a value given by subtracting a second distance representing a distance from the reference node to the focus node from a first distance representing a distance from the reference node to the neighboring node; a path determination section that determines a path according to the cost of the path; an edge generation section that generates edges extending to neighboring nodes located at least forward, diagonally forward right, and diagonally forward left of a focus node, assuming that a minimum cost node among end nodes each located at an end of the edges is the focus node, when a cost from the start point to a given node is a cost of the given node; and an edge cost calculation/readout section that calculates the first distance and the second distance or reads out the first distance and the second distance from a database, wherein: the path cost calculation section calculates a cost of a path from the start point to each of the neighboring nodes as a sum of costs of edges constituting the path; and the path determination section selects a path having a minimum cost from the start point to the end point, when the neighboring node corresponds to the end point.