# US 12,222,207 B2 · Map matching apparatus and map matching method > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,222,207 B2 - Document ID: US12222207B2 - Status: Granted - Kind: B2 - Application number: 17/796,417 - Filed: 2020-03-24 - Published: 2023-02-16 - Granted: 2025-02-11 - Earliest claimed: 2020-03-24 - Assignees: Mitsubishi Electric Corporation - Applicants: Mitsubishi Electric Corporation - Inventors: Kentaro Daikoku; Yuko Ohta - Web page: https://patentgrep.com/patent/US12222207B2 ## CPC - G01C 21/30: Map- or contour-matching - G01C 21/32: Structuring or formatting of map data - G01C 21/3815: {Road data} - G01C 21/3841: {Data obtained from two or more sources, e.g. probe vehicles} - G01C 21/3878: {Hierarchical structures, e.g. layering} - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) ## Abstract According to the present disclosure, a map matching apparatus includes a map information acquisition unit configured to acquire map information expressed by a plurality of links, a movement information acquisition unit configured to acquire movement information of a moving body on a predetermined route, and a matching unit configured to specify a link string, which is a string of the links corresponding to the route, based on the map information and the movement information, in which the matching unit is configured to generate a physical network, which is a road network, based on the connection relationship and the map information, generate a hierarchical logical network in which the physical network is duplicated in a plurality of layers and configured in a hierarchical manner, and specify the link string indicating a minimized cost in the hierarchical logical network. ## Claims ### Claim 1 A map matching apparatus of an autonomous driving vehicle comprising: a processor to execute a program; and a memory to store the program which, when executed by the processor, performs processes of, acquiring map information including link endpoint coordinates, which are coordinates of endpoints of a plurality of links, and a connection relationship of each of the links; acquiring movement information of a moving body on a predetermined route; and specifying a link string, which is a string of the links corresponding to the route, based on the map information and the movement information; and providing the specified link string to a controller, which controls an autonomous driving operation of a vehicle on the basis of the specified link string, wherein the process of specifying a link string includes generating a physical network, which is a road network, based on the connection relationship and the movement information, generating a hierarchical logical network in which the physical network is duplicated in a plurality of layers and configured into a hierarchy based on an offset relative to a common point of the route, the physical network being duplicated by copying the same road network data into each of the plurality of layers, and specifying the link string indicating a minimized cost in the hierarchical logical network. ### Claim 2 (depends on 1) The map matching apparatus according to claim 1, wherein when a part of a section of the route is not included in the movement information, the link string corresponding to the part of the section is not specified. ### Claim 3 (depends on 1) The map matching apparatus according to claim 1, wherein the route is a route on which the moving body is to travel in the future. ### Claim 4 (depends on 1) The map matching apparatus according to claim 1, wherein the route is a route on which the moving body traveled in the past. ### Claim 5 A map matching apparatus of an autonomous driving vehicle comprising a processor to execute a program; and a memory to store the program which, when executed by the processor, performs processes of, acquiring map information including link endpoint coordinates, which are coordinates of endpoints of a plurality of links, and a connection relationship of each of the links; acquiring movement information of a moving body on a predetermined route; specifying a link string, which is a string of the links corresponding to the route, based on the map information and the movement information; and providing the specified link string to a controller, which controls an autonomous driving operation of a vehicle on the basis of the specified link string, wherein the process of specifying a link string includes generating a physical network, which is a road network, based on the connection relationship and the movement information, generating a hierarchical logical network in which the physical network is duplicated in a plurality of layers and configured into a hierarchy based on an offset relative to a common point of the route, the physical network being duplicated by copying the same road network data into each of the plurality of layers, and specifying the link string indicating a minimized cost in the hierarchical logical network, the movement information includes a coordinate point string of positions on the route, a number of layers in the hierarchical logical network is equal to or greater than a number of divided sections obtained by dividing the route by the coordinate point string, a start link in the hierarchical logical network is a logical link within a layer corresponding to a first coordinate point of the coordinate point string and closest to the first coordinate point, and an end link in the hierarchical logical network is the logical link within a layer corresponding to a last coordinate point of the coordinate point string and closest to the last coordinate point. ### Claim 6 (depends on 5) The map matching apparatus according to claim 5, wherein the process of specifying a link string includes determining that the logical link existing within a predetermined radius centered on the first coordinate point is the start link and determine that the logical link existing within a predetermined radius centered on the last coordinate point is the end link. ### Claim 7 (depends on 6) The map matching apparatus according to claim 6, wherein the start link and the end link include, in addition to the logical link existing within the predetermined radius, the logical links connected before and after thereof distanced by a predetermined distance from the logical link based on the connection relationship. ### Claim 8 (depends on 5) The map matching apparatus according to claim 5, wherein each layer in the hierarchical logical network corresponds to each of the divided sections, and the process of specifying a link string includes determining a cost for moving between each of the layers in the hierarchical logical network based on a distance between coordinates corresponding to each of the layers of the coordinate point string and the link endpoint coordinates in the physical network. ### Claim 9 (depends on 5) The map matching apparatus according to claim 5, wherein the movement information includes a traveling direction of the moving body at a branch point of a road, each layer in the hierarchical logical network corresponds to each of the divided sections, and the process of specifying a link string includes determining a cost of a logical link within each layer in the hierarchical logical network based on a traveling direction of the moving body at the branch point of each of the layers and at least one of presence/absence of a branch of the physical link in the physical network and the traveling direction after the branch of the physical link in the physical network. ### Claim 10 (depends on 5) The map matching apparatus according to claim 5, wherein the movement information includes a road attribute on the route, each layer in the hierarchical logical network corresponds to a divided section divided the route by the road attribute, and the process of specifying a link string includes determining a cost of a logical link within each layer in the hierarchical logical network based on the road attribute based on the movement information corresponding to each of the layers, and the road attribute included in the map information in the physical network. ### Claim 11 (depends on 10) The map matching apparatus according to claim 10, wherein the road attribute includes at least one of a road type, a link type, the number of lanes, a road width, a speed limit, presence/absence of toll, a link number, a road name, a national road number, and a prefectural road number. ### Claim 12 A map matching method comprising the steps of a processor: acquiring map information including link endpoint coordinates, which are coordinates of endpoints of a plurality of links, and a connection relationship of each of the links; acquiring movement information of a moving body on a predetermined route; and specifying a link string, which is a string of the links corresponding to the route, based on the acquired map information and the acquired movement information; and providing the specified link string to a controller, which controls an autonomous driving operation of a vehicle on the basis of the specified link string, wherein specifying a link string includes generating a physical network, which is a road network, based on the connection relationship and the map information, generating a hierarchical logical network in which the physical network is duplicated a plurality of times and configured into a hierarchy based on an offset relative to a common point of the route, the physical network being duplicated by copying the same road network data into each of the plurality of layers, the physical network being duplicated by copying the same road network data into each of the plurality of layers, and specifying a route with a minimized cost in the hierarchical logical network as the link string.