ROUTE PLANNING DEVICE AND METHOD, COST EVALUATION DEVICE AND MOBILE BODY

摘要

To generate an optimal path in a search space represented by a grid. A path search device includes: an edge generation section (21) that generates edges extending to neighboring nodes located at least forward and diagonally forward right and left of a focus node, assuming that each grid point is a node and that a minimum cost node among end nodes each located at an end of the edges is the focus node, when a cost from a start point to a given node is a cost of the given node; an edge cost calculation/readout section (22) that reads out a shortest distance from a reference node to the neighboring node (first distance) and a shortest distance from the reference node to the focus node (second distance) from a database, assuming that a node obtained by tracing back a predetermined number of nodes from the focus node in a direction toward the start point along the path is the reference node; a path cost calculation section (23) that calculates a cost of a path from the start point to the neighboring node as a sum of costs of edges constituting the path; and a path determination section (24) that selects a path having a minimum cost from the start point to the end point.