Method of dividing coverage area for robot and device thereof

• US 20080046125A1
• Filed: 02/15/2007
• Published: 02/21/2008
• Est. Priority Date: 08/18/2006
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Myeong, Hyeon, Bang, Seok-won, Lee, Su-jinn, Kang, Jung-won, Chung, Myung-Jin, Kim, Si-jong
• Granted Patent: US 7,933,686 B2
• Time in Patent Office: Days
• US Class Current: 700/253
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

A method of dividing a coverage area of a robot and a device for the same. That is, a method of producing a space map for a robot to work and dividing the space map into at least one segment and a device for the same. The method includes producing an occupancy grid map composed of grid points that are probabilistically distributed by sensing a distance from an obstacle, producing a configuration space map by increasing the thickness of an obstacle and a wall in the occupancy grid map on the basis of the radius and size of the robot, and dividing an area by sweeping the area with a band-typed slice in the configuration space map.

Claims

1. A method of dividing a coverage area of a robot, the method comprising:

producing an occupancy grid map comprising grid points that are probabilistically distributed by sensing a distance from an obstacle;

producing a configuration space map by increasing a thickness of an obstacle and a wall in the occupancy grid map based on a radius and a size of the robot; and

dividing an area by sweeping the area with a band-typed slice in one direction in the configuration space map.

2. The method of claim 1, wherein the producing of an occupancy grid map comprises sensing the distance using a distance measuring sensor.

3. The method of claim 1, further comprising:

producing a grid map which is divided into free space or an obstacle region from the occupancy grid map by applying a critical value.

4. The method of claim 1, further comprising:

removing free space noise from the grid map which is divided into free space or an obstacle region.

5. The method of claim 4, wherein the removing of the free space noise is performed by erosion which increases the thickness of the obstacle and the wall to a predetermined size, and by dilation which decreases the thickness of the obstacle and the wall to a predetermined size.

6. The method of claim 1, wherein the producing of a configuration space map comprises producing the configuration space map by erosion which increases the thickness of an obstacle and a wall up to the radius of the robot.

7. The method of claim 1, further comprising:

obtaining a sweep-direction of the band-typed slice which is perpendicular to a direction of a majority of lines in the configuration space map.

8. The method of claim 7, wherein the obtaining of the sweep-direction comprises obtaining the sweep-direction of the band-typed slice which is perpendicular to the direction the majority of lines in the configuration space map, using at least one of Hough Transform, Radon Transform, and Histogram Method.

9. The method of claim 1, further comprising:

combining a noise cell of which a width or an area is smaller than a predetermined size into an adjacent segment.

10. The method of claim 9, further comprising:

combining two adjacent segments after the combining of a noise cell.

11. A device for dividing a coverage area of a robot, the device comprising:

an occupancy grid map-producing unit to produce an occupancy grid map comprising grid points that are probabilistically distributed by sensing a distance from an obstacle;

a configuration space map-producing unit to produce a configuration space map by increasing a thickness of an obstacle and a wall in the occupancy grid map based on a radius and a size of the robot; and

a dividing unit to divide an area by sweeping the area in a predetermined direction with a band-typed slice in the configuration space map.

12. The device of claim 11, wherein the occupancy grid map-producing unit senses the distance using a distance measuring sensor.

13. The device of claim 12, wherein the distance measuring sensor is at least one of a ultrasonic wave sensor, an infrared sensor and a laser sensor.

14. The device of claim 11, further comprising:

a critical value-applying unit to produce a grid map which is divided into free space or an obstacle region from the occupancy grid map by applying a critical value.

15. The device of claim 14, further comprising:

a free space noise-removing unit to remove a free space noise from the grid map which is divided into free space and an obstacle region.

16. The device of claim 15, wherein the free space noise-removing unit performs erosion which increases the thickness of an obstacle and a wall to a predetermined size, and performs dilation which decreases the thickness of an obstacle and a wall to a predetermined size.

17. The device of claim 11, wherein the configuration space map-producing unit produces the configuration space map by erosion which increases the thickness of an obstacle and a wall up to the radius of the robot.

18. The device of claim 11, further comprising:

a sweep-direction-obtaining unit to obtain a sweep-direction of the band-typed slice which is perpendicular to a direction of a majority of lines in the configuration space map.

19. The device of claim 18, the sweep-direction-obtaining unit obtains the sweep-direction of the band-typed slice which is perpendicular to the direction of the majority of lines in the configuration space map using at least one of Hough Transform, Radon Transform, and Histogram Method.

20. The device of claim 11, further comprising:

a noise cell-removing unit combining a noise cell of which a width or an area is smaller than a predetermined size into an adjacent segment.

21. The device of claim 20, further comprising:

a combining unit combining two adjacent segments after the combining of the noise cell.