Method and apparatus for planning path of mobile robot

• US 20090182464A1
• Filed: 10/03/2008
• Published: 07/16/2009
• Est. Priority Date: 01/11/2008
• Status: Abandoned Application

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Myeong, Hyeon, Bang, Seok-Won
• Application Number:
  US12/285,427
• Publication Number:
  US 20090182464A1
• Time in Patent Office: Days
• US Class Current: 701/25
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

The apparatus includes a coarse map creating unit creating a coarse map which includes path information of the mobile robot; and a virtual door extracting unit extracting virtual doors which divide the coarse map into a plurality of sub regions, where the mobile robot sequentially cleans the sub regions one by one. The method includes creating a coarse map which includes path information of the mobile robot; extracting virtual doors which divide the coarse map into a plurality of sub regions; and sequentially cleaning the sub regions one by one.

Claims

1. An apparatus for planning a path of a mobile robot, the apparatus comprising:

a coarse map creating unit creating a coarse map which comprises path information of the mobile robot; and

a virtual door extracting unit extracting virtual doors which divide the coarse map into a plurality of sub regions,

wherein the mobile robot sequentially cleans the sub regions one by one.

2. The apparatus of claim 1, wherein the path information comprises information on whether a specified cell has been cleaned and information on whether a current line comprising the specified cell and another line directly under the current line have been cleaned.

3. The apparatus of claim 1, wherein each of the virtual doors is extracted by using a road map, which extends between obstacles, and a configuration space which is created based on the coarse map.

4. The apparatus of claim 3, wherein each of the virtual doors is formed by drawing a virtual line from each intersecting point of the road map and the configuration space to the obstacles in a direction perpendicular to the road map.

5. The apparatus of claim 4, wherein the road map is a generalized Voronoi diagram in which each point placed between the obstacles and separated from the obstacles by an equal distance is connected.

6. The apparatus of claim 4, wherein the configuration space is created by eroding the coarse map as much as half the size of a room door, and a plurality of discrete regions are formed within the configuration space.

7. The apparatus of claim 6, wherein the virtual doors are extracted based on the intersecting points, each of which is adjacent to at least two of the discrete regions.

8. The apparatus of claim 1., further comprising a path setting unit setting a path, along which the mobile robot can move within a shortest time, in each of the sub regions.

9. The apparatus of claim 8, wherein the path enables the mobile robot to move within the shortest time from among all paths which can be created in each of the sub regions based on a starting point of the mobile robot and a direction in which the mobile robot is to move.

10. The apparatus of claim 1, wherein the mobile robot closes the virtual doors when cleaning one of the sub regions and opens the virtual doors when moving between the sub regions.

11. A method of planning a path of a mobile robot, the method comprising:

creating a coarse map which comprises path information of the mobile robot;

extracting virtual doors which divide the coarse map into a plurality of sub regions; and

sequentially cleaning the sub regions one by one.

12. The method of claim 11, wherein the path information comprises information on whether a specified cell has been cleaned and information on whether a current line comprising the specified cell and another line directly under the current line have been cleaned.

13. The method of claim 11, wherein the extracting of the virtual doors comprises:

creating a road map which extends between obstacles;

creating a configuration space based on the coarse map; and

extracting the virtual doors by using the road map and the configuration space.

14. The method of claim 13, wherein the extracting of the virtual doors by using the road map and the configuration space comprises:

extracting intersecting points of the road map and the configuration space; and

forming a virtual door to extend from each intersecting point of the road map and the configuration space to the obstacles in a direction perpendicular to the road map.

15. The method of claim 14, wherein the road map is a generalized Voronoi diagram in which each point placed between the obstacles and separated from the obstacles by an equal distance is connected.

16. The method of claim 14, wherein the configuration space is created by eroding the coarse map as much as half the size of a room door, and a plurality of discrete regions are formed within the configuration space.

17. The method of claim 16, wherein the virtual doors are extracted based on the intersecting points, each of which is adjacent to at least two of the discrete regions.

18. The method of claim 11, further comprising setting a path, along which the mobile robot can move within a shortest time, in each of the sub regions.

19. The method of claim 18, wherein the path enables the mobile robot to move within the shortest time from among all paths which can be created in each of the sub regions based on a starting point of the mobile robot and a direction in which the mobile robot is to move.

20. The method of claim 11, wherein the mobile robot closes the virtual doors when cleaning one of the sub regions and opens the virtual doors when moving between the sub regions.

21. A mobile cleaning robot, comprising:

a relative position measuring unit;

an absolute position measuring unit;

an obstacle sensing unit,

a coarse map creating unit to create a coarse map which includes path information for the mobile robot;

a virtual door extracting unit to extract virtual doors which divide the coarse map into a plurality of sub regions;

a path setting unit to set a path, along which the mobile cleaning robot can move within a shortest time, in each of the sub regions; and

a motion control unit to move the mobile robot to sequentially clean the sub regions one by one.

22. The mobile cleaning robot of claim 21, wherein the path information comprises information on whether a specified cell has been cleaned and information on whether a current line comprising the specified cell and another line directly under the current line have been cleaned.

23. The mobile cleaning robot of claim 21, wherein each of the virtual doors is extracted by using a road map, which extends between obstacles, and a configuration space which is created based on the coarse map, and

each of the virtual doors is formed by drawing a virtual line from each intersecting point of the road map and the configuration space to the obstacles in a direction perpendicular to the road map.

24. The mobile cleaning robot of claim 23, wherein the road map is a generalized Voronoi diagram in which each point placed between the obstacles and separated from the obstacles by an equal distance is connected.

25. The mobile cleaning robot of claim 23, wherein the configuration space is created by eroding the coarse map as much as half the size of a room door, and a plurality of discrete regions are formed within the configuration space, and

the virtual doors are extracted based on the intersecting points, each of which is adjacent to at least two of the discrete regions.