Method and apparatus for constructing map for mobile robot

• US 9,207,678 B2
• Filed: 09/26/2013
• Issued: 12/08/2015
• Est. Priority Date: 05/07/2013
• Status: Active Grant

• Current Assignee: Hanwha Aerospace Co., Ltd. (Hanwha Corporation)
• Original Assignee: Hanwha Techwin Co., Ltd. (Hanwha Corporation)
• Inventors: Kim, Dongshin
• Primary Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US14/037,510
• Publication Number:
  US 20140334713A1
• Time in Patent Office: 803 Days
• Field of Search: 382/181, 382/224, 382/225, 382/155, 382/159, 382/115, 382/100, 382/153, 701/533, 701/420, 701/423, 701/23, 901/1, 901/9, 901/4, 901/7, 700/104, 700/255, 700/259, 414/744.3
• US Class Current: 1/1
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06F 18/2163 Partitioning the feature space
• CPC Class Codes: G06V 10/765 using rules for classification or partitioning the feature space
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

A method and apparatus for constructing a map for a mobile robot to be able to reduce a data amount and increase an approach speed. The method includes: searching for a plurality of feature data occupying an arbitrary space by scanning a surrounding environment of the mobile robot; performing quadtree segmentation on first feature data of the plurality of feature data to generate a plurality of first node information as a result of the quadtree segmentation; determining a position of second feature data of the plurality of feature data with respect to the first feature data; and performing a neighborhood moving algorithm for generating a plurality of second node information of the second feature data according to the position of second feature data by using the plurality of first node information.

Claims

1. A method of constructing a map for a mobile robot, the method comprising:

searching, by at least one processor, for a plurality of feature data occupying an arbitrary space by scanning a surrounding environment of the mobile robot;

performing quadtree segmentation, by the at least one processor, on first feature data of the plurality of feature data to generate a plurality of first node information;

determining, by the at least one processor, a position of second feature data of the plurality of feature data with respect to the first feature data; and

performing, by the at least one processor, a neighborhood moving algorithm for generating a plurality of second node information of the second feature data according to the position of second feature data by using the plurality of first node information.

2. The method of claim 1, wherein the determining the position comprises determining the second feature data being in one of a first position, a second position, a third position and a fourth position,

wherein the first, second, third and fourth positions are located orthogonally from one another.

3. The method of claim 2, wherein the performing the neighborhood moving algorithm comprises performing one of a first neighborhood moving algorithm, a second neighborhood moving algorithm, a third neighborhood moving algorithm and a fourth neighborhood moving algorithm for generating the plurality of second node information of the second feature data according to the determined position of the second feature data.

4. The method of claim 3, wherein the performing the one of the first, second, third and fourth neighborhood moving algorithm comprises:

performing the first neighborhood moving algorithm for generating the plurality of second node information of the second feature data in response to the determined position being the first position;

performing the second neighborhood moving algorithm for generating the plurality of second node information of the second feature data in response to the determined position being the second position;

performing the third neighborhood moving algorithm for generating the plurality of second node information of the second feature data in response to the determined position being the third position; and

performing the fourth neighborhood moving algorithm for generating the plurality of second node information of the second feature data in response to the determined position being the fourth position.

5. The method of claim 3, wherein the performing the one of the first, second, third and fourth neighborhood moving algorithm comprises determining whether a bottom node in the plurality of first node information of the first feature data comprises a determining direction opposite from a direction extending from the first feature data to the determined position of the second feature data.

6. The method of claim 5, wherein the performing the one of the first, second, third and fourth neighborhood moving algorithm further comprises generating a first plurality of second node information of the second feature data in response to the bottom node in the plurality of first node information of the first feature data having the determining direction.

7. The method of claim 6, wherein the performing the one of the first, second, third and fourth neighborhood moving algorithm further comprises generating a second plurality of second node information of the second feature data in response to the bottom node in the plurality of first node information of the first feature data having the direction from the first feature data to the determined position of the second feature data.

8. The method of claim 7, wherein the generating the first plurality of second node information of the second feature data comprises:

changing the determining direction of the bottom node in the plurality of first node information of the first feature data to the direction from the first feature data to the determined position of the second feature data; and

generating the plurality of second node information of the second feature data as a result of combining the changed bottom node of the first node information and remaining nodes of the first node information.

9. The method of claim 7, wherein the generating the second plurality of second node information of the second feature data comprises:

changing the direction from the first feature data to the determined position of the second feature data of the bottom node in the plurality of first node information of the first feature data to the determining direction and moving to a parent node of the bottom node;

changing the determining direction of the parent node to the direction from the first feature data to the determined position of the second feature data; and

generating the plurality of second node information of the second feature data as a result of combining the changed bottom node and the changed parent node of the first node information and remaining nodes of the first node information.

10. An apparatus for constructing a map for a mobile robot, the apparatus comprising:

an environment recognizer configured to search for a plurality of feature data occupying an arbitrary space by scanning a surrounding environment of the mobile robot;

a quadtree information generator configured to perform quadtree segmentation on first feature data of the plurality of feature data to generate a plurality of first node information;

a searcher configured to determine a position of second feature data of the plurality of feature data with respect to the first feature data; and

a neighborhood moving information generator configured to perform a neighborhood moving algorithm for generating a plurality of second node information of the second feature data according to the position of second feature data by using the plurality of first node information.

11. The apparatus of claim 10, wherein the searcher is configured to determine the second feature data being in one of a first position, second position, a third position and a fourth position,

wherein the first, second, third and fourth positions are located orthogonally from one another.

12. The apparatus of claim 11, wherein the neighborhood moving information generator is configured to perform one of a first neighborhood moving algorithm, a second neighborhood moving algorithm, a third neighborhood moving algorithm and a fourth neighborhood moving algorithm for generating the plurality of second node information of the second feature data according to the position of the second feature data.

13. The apparatus of claim 12, wherein the neighborhood moving information generator is configured to perform the first neighborhood moving algorithm for generating the plurality of second node information of the second feature data in response to the determined position being the first position, performs the second neighborhood moving algorithm for generating the plurality of second node information of the second feature data in response to the determined position being the second position, performs the third neighborhood moving algorithm for generating the plurality of second node information of the second feature data in response to the determined position being the third position, and performs the fourth neighborhood moving algorithm for generating the plurality of second node information of the second feature data in response to the determined position being the fourth position.

14. The apparatus of claim 12, wherein the neighborhood moving information generator is configured to determine whether a bottom node in the plurality of first node information of the first feature data comprises a determining direction opposite from a direction extending from the first feature data to the determined position of the second feature data.

15. The apparatus of claim 14, wherein the neighborhood moving information generator is configured to generate a first plurality of second node information of the second feature data in response to the bottom node in the plurality of first node information of the first feature data having the determining direction.

16. The apparatus of claim 15, wherein the neighborhood moving information generator is configured to generate a second plurality of second node information of the second feature data in response to the bottom node in the plurality of first node information of the first feature data having the direction from the first feature data to the determined position of the second feature data.

17. The apparatus of claim 16, wherein the neighborhood moving information generator is configured to change the determining direction of a bottom node in the plurality of first node information of the first feature data to the direction from the first feature data to the determined position of the second feature data and generates the first plurality of second node information of the second feature data as a result of combining the changed bottom node of the first node information and remaining nodes of first node information.

18. The apparatus of claim 16, wherein the neighborhood moving information generator is configured to change the direction from the first feature data to the determined position of the second feature data of the bottom node in the plurality of first node information of the first feature data to the determining direction, moves to a parent node of the bottom node, changes the determining direction to the direction from the first feature data to the determined position of the second feature data, and generates the second plurality of second node information of the second feature data as a result of combining the changed bottom node and the changed parent node of the first node information, and the remaining nodes of the first node information.