Map difference data generation apparatus and map difference data generation method

• US 8,560,573 B2
• Filed: 07/25/2012
• Issued: 10/15/2013
• Est. Priority Date: 07/27/2011
• Status: Active Grant

• Current Assignee: DENSO Corporation, Kousokuya, Inc.
• Original Assignee: DENSO Corporation, Kousokuya, Inc.
• Inventors: Watanabe, Takayuki, Suzuki, Takamitsu, Samizu, Akio, Fujimoto, Hidetoshi, Suzuki, Takayuki, Shibata, Kaoru
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US13/557,567
• Publication Number:
  US 20130031049A1
• Time in Patent Office: 447 Days
• Field of Search: 707600-899
• US Class Current: 707/791
• CPC Class Codes: G01C 21/3859 Differential updating map data
• CPC Class Codes: G01C 21/3889 Transmission of selected map data, e.g. depending on route
• CPC Class Codes: G01C 21/3896 Transmission of map data from central databases
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

A map difference data generation apparatus includes: most recent and supplementary map data storage devices storing primary most recent and supplementary map data, respectively; a map update reflection device generating secondly most recent and supplementary map data according to an update of a first link, and generating tertiary most recent and supplementary map data according to an update of a second link; a determination device determining a dependency relationship between the update of the first and second links, in accordance with results of searching a route in the tertiary most recent and supplementary map data between first and second nodes, which are both ends of the second link; and a map difference data generation device generating map difference data, which defines a combination of the update of the first and second links, when the update of the first and second links have the dependency relationship.

Claims

1. A map difference data generation apparatus comprising:

a most recent map data storage device that stores primary most recent map data indicating a connection status of a node and a link of a map;

a supplementary map data storage device that stores primary supplementary map data indicating a connection status of the node and the link, which is initially equal to the primary most recent map data;

a map update reflection device that generates secondly most recent map data and secondly supplementary map data according to an update of a first link in the primary recent map data when map update for updating the first link is established, and generates tertiary most recent map data and tertiary supplementary map data according to an update of a second link in the secondly most recent map data when map update for updating the second link is established after the update of the first link;

a determination device that determines whether the update of the first link and the update of the second link have a dependency relationship, in accordance with a result of searching a route in the tertiary supplementary map data between a first node and a second node, which are both ends of the second link, respectively, and a result of searching the route between the first node and the second node in the tertiary most recent map data; and

a map difference data generation device that generates map difference data, which defines a combination of the update of the first link and the update of the second link, when the determination device determines that the update of the first link and the update of the second link have the dependency relationship.

2. The map difference data generation apparatus according to claim 1,

wherein the supplementary map data storage device includes a first supplementary map data storage device that stores primary first supplementary map data indicating a connection status of the node and the link, which is initially equal to the primary most recent map data,

wherein the map update reflection device generates the secondly most recent map data by adding the first link on the primary most recent map data, and generates secondly first supplementary map data by maintaining the primary first supplementary map data without any change, when the update of the first link requires adding the first link to the primary most recent map data,

wherein the map update reflection device generates the tertiary most recent map data by deleting the second link from the secondly most recent map data, and generates tertiary first supplementary map data by deleting the second link from the secondly first supplementary map data, when the update of the second link requires deleting the second link from the secondly most recent map data,

wherein, when the determination device searches the route in the tertiary first supplementary map data, and fails to search the route between the first node and the second node, the determination device searches the route in the tertiary most recent map data,

wherein, when the determination device searches the route in the tertiary first supplementary map data, and succeeds to search the route, the determination device determines that addition of the first link and deletion of the second link have the dependency relationship, and

wherein the map difference data generation device generates the map difference data, which defines a combination of the addition of the first link and the deletion of the second link, when the determination device determines that the addition of the first link and the deletion of the second link have the dependency relationship.

3. The map difference data generation apparatus according to claim 2,

wherein the primary supplementary map data includes the primary first supplementary map data,

wherein the secondly supplementary map data includes the secondly first supplementary map data, and

wherein the tertiary supplementary map data includes the tertiary first supplementary map data.

4. The map difference data generation apparatus according to claim 1,

wherein the supplementary map data storage device includes a second supplementary map data storage device that stores primary second supplementary map data indicating a connection status of the node and the link, which is initially equal to the primary most recent map data,

wherein the map update reflection device generates the secondly most recent map data by deleting the first link from the primary most recent map data, and generates secondly second supplementary map data by maintaining the primary second supplementary map data without any change, when the update of the first link requires deleting the first link from the primary most recent map data,

wherein the map update reflection device generates the tertiary most recent map data by deleting the second link from the secondly most recent map data, and generates tertiary second supplementary map data by maintaining the secondly second supplementary map data without any change, when the update of the second link requires deleting the second link from the secondly most recent map data,

wherein the determination device generates temporary second supplementary map data, which is a copy of the tertiary second supplementary map data, and deletes the second link from the temporary second supplementary map data,

wherein the determination device searches the route between the first node and the second node in the temporary second supplementary map data,

wherein, when the determination device succeeds to search the route including the first link in the temporary second supplementary map data, the determination device determines that deletion of the first link and deletion of the second link have the dependency relationship, and

wherein the map difference data generation device generates the map difference data, which defines a combination of the deletion of the first link and the deletion of the second link, when the determination device determines that the deletion of the first link and the deletion of the second link have the dependency relationship.

5. The map difference data generation apparatus according to claim 4,

wherein the primary supplementary map data includes the primary second supplementary map data,

wherein the secondly supplementary map data includes the secondly second supplementary map data, and

wherein the tertiary supplementary map data includes the tertiary second supplementary map data.

6. The map difference data generation apparatus according to claim 1, further comprising:

a map difference data distribution device that distributes the map difference data generated by the map difference data generation device to an in-vehicle apparatus.

7. A map difference data generation method comprising:

preparing primary most recent map data indicating a connection status of a node and a link of a map;

preparing primary supplementary map data indicating a connection status of the node and the link, which is initially equal to the primary most recent map data;

generating secondary most recent map data and secondary supplementary map data in accordance with an update of a first link in the primary most recent map data when map update for updating the first link is established;

generating tertiary most recent map data and tertiary supplementary map data in accordance with an update of a second link in the secondly most recent map data when map update for updating the second link is established after the update of the first link;

determining whether the update of the first link and the update of the second link have a dependency relationship, in accordance with a result of searching a route in the tertiary supplementary map data between a first node and a second node, which are both ends of the second link, respectively, and a result of searching the route between the first node and the second node in the tertiary most recent map data; and

generating map difference data, which defines a combination of the update of the first link and the update of the second link, when the determination device determines that the update of the first link and the update of the second link have the dependency relationship.

8. The map difference data generation method according to claim 7, further comprising:

preparing primary first supplementary map data indicating a connection status of the node and the link, which is initially equal to the primary most recent map data;

generating the secondly most recent map data by adding the first link on the primary most recent map data, and generating secondly first supplementary map data by maintaining the primary first supplementary map data without any change, when the update of the first link requires adding the first link to the primary most recent map data;

generating the tertiary most recent map data by deleting the second link from the secondly most recent map data, and generating tertiary first supplementary map data by deleting the second link from the secondly first supplementary map data, when the update of the second link requires deleting the second link from the secondly most recent map data;

searching the route in the tertiary first supplementary map data;

searching the route in the tertiary most recent map data when the route between the first node and the second node is not searched in the tertiary first supplementary map data;

determining that addition of the first link and deletion of the second link have the dependency relationship when the route between the first node and the second node is searched in the tertiary first supplementary map data; and

generating the map difference data, which defines a combination of the addition of the first link and the deletion of the second link, when the addition of the first link and the deletion of the second link have the dependency relationship.

9. The map difference data generation method according to claim 8,

wherein the primary supplementary map data includes the primary first supplementary map data,

wherein the secondly supplementary map data includes the secondly first supplementary map data, and

wherein the tertiary supplementary map data includes the tertiary first supplementary map data.

10. The map difference data generation method according to claim 7, further comprising:

preparing primary second supplementary map data indicating a connection status of the node and the link, which is initially equal to the primary most recent map data;

generating the secondly most recent map data by deleting the first link from the primary most recent map data, and generating secondly second supplementary map data by maintaining the primary second supplementary map data without any change, when the update of the first link requires deleting the first link from the primary most recent map data;

generating the tertiary most recent map data by deleting the second link from the secondly most recent map data, and generating tertiary second supplementary map data by maintaining the secondly second supplementary map data without any change, when the update of the second link requires deleting the second link from the secondly most recent map data,

generating temporary second supplementary map data, which is a copy of the tertiary second supplementary map data, and deleting the second link from the temporary second supplementary map data;

searching the route between the first node and the second node in the temporary second supplementary map data;

determining that deletion of the first link and deletion of the second link have the dependency relationship when the route including the first link is searched in the temporary second supplementary map data; and

generating the map difference data, which defines a combination of the deletion of the first link and the deletion of the second link, when the deletion of the first link and the deletion of the second link have the dependency relationship.

11. The map difference data generation method according to claim 10,

wherein the primary supplementary map data includes the primary second supplementary map data,

wherein the secondly supplementary map data includes the secondly second supplementary map data, and

wherein the tertiary supplementary map data includes the tertiary second supplementary map data.