# US 12,181,289 B2 · Link information generation method, link information generation device, and link information generation program > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,181,289 B2 - Document ID: US12181289B2 - Status: Granted - Kind: B2 - Application number: 17/609,308 - Filed: 2019-05-09 - Published: 2022-10-06 - Granted: 2024-12-31 - Earliest claimed: 2019-05-09 - Assignees: Nippon Telegraph and Telephone Corporation - Applicants: Nippon Telegraph and Telephone Corporation - Inventors: Shunsuke Konagai; Hiroshi Konishi; Chihiro Yamamoto; Hitoshi Seshimo - Web page: https://patentgrep.com/patent/US12181289B2 ## CPC - G01C 21/30: Map- or contour-matching - G01C 21/3484: {Personalized, e.g. from learned user behaviour or user-defined profiles} - G08G 1/00: Traffic control systems for road vehicles (arrangement of road signs or traffic signals E01F9/00 {; automatic vehicle control B62D}) - 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) - G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93}) ## Abstract Information relating to each link based on location information of a user can be generated with high accuracy even without measuring the location information at a high frequency. A map matching unit (101) associates location information of a moving user at each time with pedestrian network data (120) formed by a plurality of nodes and links connecting the nodes through a map matching process, and a calculation unit (102) calculates a passage record of a link of interest as link information based on whether or not the link of interest is connected to preceding and succeeding links in a link row acquired by aligning the links with which the location information is associated in order of times of pieces of the location information. ## Claims ### Claim 1 A link information generation method comprising: associating pieces of location information of a moving user moving through a route during a predetermined time interval with nodes of a plurality of nodes in network data, wherein the network data is used for a route search for a pedestrian as a type of movement by the moving user, the network data comprises the plurality of nodes and a link connecting a pair of nodes of the plurality of nodes, the pair of nodes comprises a start node and an end node of the link, the link is searchable based on the type of movement and a piece of the pieces of the location information as the start node of the link, and the link includes a road type of the link and a time duration for the pedestrian to move across the link according to the type of movement; determining link information, wherein the link information represents a passage record of the moving user having passed through a link of a series of links, and the link information is based on aligning links of the series of links in chronological order of the moving user passing through the pieces of the location information; updating the link information by removing a part of the link information that corresponds to one or more links of the series of links when the one or more links at least either do not connect from a preceding link or do not connect to a subsequent link in the series of links, wherein the part of the link information being removed comprises a link on which the moving user has turned back without passing through the link; and generating, based on the updated link information, a route for another moving user with the pedestrian as the type of movement to move according to the updated link information. ### Claim 2 (depends on 1) The link information generation method according to claim 1, wherein the determining the link information further comprises determining passage time at nodes located at both ends of a link of interest having a passage record based on a time of the location information associated with a preceding link or a subsequent link connected to the node, and further determines a required time for the link of interest as the link information from the passage time acquired by determining for the nodes located at both ends of the link of interest. ### Claim 3 (depends on 2) The link information generation method according to claim 2, wherein the determining further comprises determining, as the link information, a time cost acquired by statistical processing on a required time for the link of interest acquired by calculating based on location information of a plurality of users. ### Claim 4 (depends on 2) The link information generation method according to claim 2, wherein road-type information indicated by a link is added to the link, and the determining further comprises determining, for a link of a predetermined specific road type, a required time for a partial route including two or more links selected from the link of the predetermined specific road type and links connected to nodes located at both ends of the link of the predetermined specific road type. ### Claim 5 (depends on 2) The link information generation method according to claim 2, wherein the determining further comprises determining, as the link information, a subjective cost with a length of a link and a required time for the link as parameters. ### Claim 6 (depends on 5) The link information generation method according to claim 5, wherein the determining further comprises determining the subjective cost that further includes difficulty of walking on a road indicated by the link as a parameter. ### Claim 7 (depends on 1) The link information generation method according to claim 1, wherein the determining further comprises determining the link information for attributes of users. ### Claim 8 (depends on 1) The link information generation method according to claim 1, wherein, among the pieces of the location information during the predetermined time interval, the associating the pieces of the location information comprises making location information whose certainty satisfies a predetermined condition correspond to the network data. ### Claim 9 A link information generation device comprising a processor configured to execute operations comprising: associating pieces of location information of a moving user moving through a route during a predetermined time interval with nodes of a plurality of nodes in network data, wherein the network data is used for a route search for a pedestrian as a type of movement by the moving user, the network data comprises the plurality of nodes and a link connecting a pair of nodes of the plurality of nodes, the pair of nodes comprises a start node and an end node of the link, the link is searchable based on the type of movement and a piece of the pieces of the location information as the starting node of the link, and the link includes a road type of the link and a time duration for the pedestrian to move across the link according to the type of movement; determining link information, wherein the link information represents a passage record of the moving user having passed through a link of a series of links, and the link information is based on aligning links of the series in chronological order of the moving user passing through the pieces of the location information; updating the link information by removing a part of the link information that corresponds to one or more links of the series of links when the one or more links at least either do not connect from a preceding link or do not connect to a subsequent link in the series of links, wherein the part of the link information being removed comprises a link on which the moving user has turned back without passing through the link; and generating, based on the updated link information and the network data, a route for another moving user with the pedestrian as the type of movement to move according to the updated link information. ### Claim 10 (depends on 9) The link information generation device according to claim 9, wherein the determining the link information further comprises determining passage time at nodes located at both ends of a link of interest having a passage record based on a time of the location information associated with a preceding link or a subsequent link connected to the node, and further determines a required time for the link of interest as the link information from the passage time acquired by determining for the nodes located at both ends of the link of interest. ### Claim 11 (depends on 10) The link information generation device according to claim 10, wherein the determining further comprises determining, as the link information, a time cost acquired by statistical processing on a required time for the link of interest acquired by calculating based on location information of a plurality of users. ### Claim 12 (depends on 10) The link information generation device according to claim 10, wherein road-type information indicated by a link is added to the link, and the determining further comprises determining, for a link of a predetermined specific road type, a required time for a partial route including two or more links selected from the link of the predetermined specific road type and links connected to nodes located at both ends of the link of the predetermined specific road type. ### Claim 13 (depends on 10) The link information generation device according to claim 10, wherein the determining further comprises determining, as the link information, a subjective cost with a length of a link and a required time for the link as parameters. ### Claim 14 (depends on 13) The link information generation device according to claim 13, wherein the determining further comprises determining the subjective cost that further includes difficulty of walking on a road indicated by the link as a parameter. ### Claim 15 (depends on 9) The link information generation device according to claim 9, wherein the determining further comprises determining the link information for attributes of users. ### Claim 16 (depends on 9) The link information generation device according to claim 9, wherein, among the pieces of the location information during the predetermined time interval, the associating comprises making location information whose certainty satisfies a predetermined condition correspond to the network data. ### Claim 17 A computer-readable non-transitory recording medium storing computer-executable program instructions that when executed by a processor cause a computer system to perform operations comprising: associating pieces of location information of a moving user moving through a route during a predetermined time interval with nodes of a plurality of nodes in network data, wherein the network data is used for a route search for a pedestrian as a type of movement by the moving user, the network data comprises the plurality of nodes and a link connecting a pair of nodes of the plurality of nodes, the pair of nodes comprises a start node and an end node of the link, the link is searchable based on the type of movement and a piece of the pieces of the location information as the starting node of the link, and the link includes a road type of the link and a time duration for the pedestrian to move across the link according to the type of movement; determining link information, wherein the link information represents a passage record of the moving user having passed through a link of a series of links, and the link information is based on aligning links of the series of links in chronological order of the moving user passing through the pieces of the location information; updating the link information by removing a part of the link information that corresponds to one or more links of the series of links when the one or more links at least either do not connect from a preceding link or do not connect to a subsequent link in the series of links, wherein the part of the link information being removed comprises a link on which the moving user has turned back without passing through the link; and generating, based on the updated link information, a route for another moving user with the pedestrian as the type of movement to move according to the updated link information. ### Claim 18 (depends on 17) The computer-readable non-transitory recording medium according to claim 17, wherein the determining further comprises determining, as the link information, a time cost acquired by statistical processing on a required time for a link of interest acquired by calculating based on location information of a plurality of users. ### Claim 19 (depends on 17) The computer-readable non-transitory recording medium according to claim 17, wherein road-type information indicated by a link is added to the link, and the determining the link information further comprises determining, for a link of a predetermined specific road type, a required time for a partial route including two or more links selected from the link of the predetermined specific road type and links connected to nodes located at both ends of the link of the predetermined specific road type. ### Claim 20 (depends on 17) The computer-readable non-transitory recording medium according to claim 17, wherein the determining further comprises determining, as the link information, a subjective cost with a length of a link and a required time for the link as parameters.