Information processing device

An information processing device comprising a processor and a memory storing instructions that are executable by the processor and that cause the processor to:

• acquire a reference map and an input map each including a plurality of nodes and a plurality of edges;
• divide each region of the reference map and the input map into a branch region in which a road or a lane is branched and a non-branch region other than the branch region;
• determine the branch region and the non-branch region of the input map corresponding to the branch region and the non-branch region of the reference map based on a degree of overlap between the branch region of the reference map and the branch region of the input map and a degree of overlap between the non-branch region of the reference map and the non-branch region of the input map;
• delete a non-branch intermediate node that is not a branch node and edit nodes at both ends of the non-branch intermediate node so as to be connected using an edge, the non-branch intermediate node being a node other than an entry end and an exit end of the branch region or the non-branch region;
• after deleting the non-branch intermediate node and editing the nodes, calculate, for each of the corresponding regions, a graph editing path that minimizes an editing cost, the graph editing path being a sequence of editing operations including adding, deleting, and replacing nodes and edges;
• and
• output graph editing paths for a plurality of the corresponding regions as a difference between the reference map and the input map, wherein
• the editing cost is determined based on a coordinate system that compresses a scale in a traveling direction for distances between the nodes while maintaining a scale in a width direction orthogonal to the traveling direction, and
• the editing cost is larger as nodes to be correlated are positioned farther, and a larger editing cost is given to positional deviation in a direction orthogonal to a traveling direction of a road corresponding to a node than to positional deviation in the traveling direction.