Path planning device and method, cost evaluation device, and moving body

Abstract

To generate an optimal path in a search space represented by a grid. A path search device includes: an edge generation section 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 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 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 that selects a path having a minimum cost from the start point to the end point.