Apparatus and method for generating and using a grid map path

• US 20100211244A1
• Filed: 02/17/2010
• Published: 08/19/2010
• Est. Priority Date: 02/18/2009
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Su-jinn, Jeong, Woo-yeon
• Granted Patent: US 8,849,559 B2
• Time in Patent Office: Days
• US Class Current: 701/25
• CPC Class Codes: A47L 2201/04 Automatic control of the travelling movement; Automatic obstacle detection
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images

Abstract

An apparatus and method for generating a path using a limited memory size are provided. An approximate path is generated based on a reduced grid map generated by reducing an original grid map. Then, an approximate path is mapped onto the original grid map, and the mapped path is enlarged and divided into a plurality of sections based on an available memory size used for path calculation. Based on a start point and a destination point set in each of the divided sections, a detailed path in each of the sections is generated.

Claims

1. An apparatus for generating a path, comprising:

a path generator generating an approximate path for an object moving relative to a map, based on a reduced map generated by reducing the map, dividing the map into a plurality of sections based on divisions of the approximate path, and generating a detailed path in each of the divided sections based on the approximate path.

2. The apparatus of claim 1, wherein the map includes information of obstacles and a free area in which the object can move unrestrictedly without collision with the obstacles.

3. The apparatus of claim 1, wherein the path generator determines a free area in the map in which a mobile object can move unrestrictedly without collision with obstacles in consideration of a size of the mobile object, and generates the reduced map by reducing the map including information about the determined free area.

4. The apparatus of claim 3, wherein the map is a grid map and the path generator reduces the grid map by respectively anti-aliasing filtering information from different grids of the grid map.

5. The apparatus of claim 4, wherein the path generator maps waypoints in the approximate path, generated in the reduced map, into the map before division of the map in order to generate the detailed paths.

6. The apparatus of claim 3, wherein the path generator maps waypoints in the approximate path, generated in the reduced map, into the map before division of the map in order to generate the detailed paths.

7. The apparatus of claim 6, wherein when one or more of the mapped waypoints are located outside of the free area in the map, the path generator moves the one or more waypoints located outside of the free area to closest locations from the waypoints in the free area, respectively.

8. The apparatus of claim 6, wherein the path generator classifies the waypoints mapped onto the map according to respective divided sections, of the plural divided sections, when dividing the map into the divided sections based on the divisions of the approximate path, sets a start waypoint and a destination waypoint in each of the divided sections, generates the detailed path in each of the divided sections, and generates a final detailed path by sequentially combining each of the detailed paths.

9. The apparatus of claim 8, wherein a destination waypoint for at least one divided section overlaps a start waypoint of another divided section.

10. The apparatus of claim 1, wherein the path generator generates the reduced map generated by reducing the map.

11. The apparatus of claim 10, wherein the map is a grid map and the path generator reduces the grid map using each grid of a determined free area of the grid map.

12. The apparatus of claim 10, wherein the reducing of the map is a linear reduction of the map.

13. The apparatus of claim 10, wherein the reducing of the map is limited to a normalizing of the map according to a size of the object.

14. The apparatus of claim 1, wherein the path generator maps waypoints in the approximate path, generated from the reduced map, into the map before division of the map in order to generate the detailed paths.

15. The apparatus of claim 1, further comprising a memory in which writing and reading of data generated in the operation of the path generator are performed.

16. The apparatus of claim 15, wherein the path generator divides the approximate path into the divided sections based on an available space of the memory.

17. The apparatus of claim 15, the generating of each of the detailed paths in each of the respective divided sections are respectively performed, in parallel, through at least one search algorithm.

18. The apparatus of claim 1, the generating of each of the detailed paths in each of the respective divided sections are respectively performed, in parallel, through at least one search algorithm.

19. The apparatus of claim 1, wherein the mobile object is a mobile robot and the mobile robot is controlled to move sequentially along the detailed paths.

20. The apparatus of claim 1, wherein the mobile object is an avatar in a computer generated environment.

21. The apparatus of claim 1, wherein the apparatus is one of a cellular phone, a portable media player (PMP), and a personal digital assistant (PDA).

22. A method of generating a path of an object in a map, comprising:

generating an approximate path within a reduced map generated from reducing the map;

dividing the map into a plurality of sections based upon divisions of the approximate path; and

generating a detailed path in each of the divided sections based on the approximate path.

23. The method of claim 22, wherein the map includes information of obstacles and a free area in which the object can move unrestrictedly without collision with the obstacles.

24. The method of claim 22, further comprising generating the reduced map by determining a free area in the map in which the object can move unrestrictedly without collision with obstacles in consideration of a size of the object and by reducing the map including information about the determined free area.

25. The method of claim 24, wherein the map is a grid map and the reducing of the grid map is performed by respectively anti-aliasing filtering information from different grids of the grid map.

26. The method of claim 22, wherein the dividing of the approximate path includes mapping waypoints in the approximate path into the map.

27. The method of claim 26, wherein the dividing of the map further includes, when one or more of the mapped waypoints are located outside of a free area of the map, moving the one or more waypoints located outside of the free area to closest locations from the waypoints in the free area, respectively.

28. The method of claim 26, wherein the dividing of the map further includes classifying the waypoints mapped into the map according to the divided sections, and

the generating of each detailed path includes respectively setting a start waypoint and a destination waypoint in each of the divided sections, generating each respective detailed path in each of the divided sections, and generating a final detailed path by sequentially combining each detailed path.

29. The method of claim 28, wherein a destination waypoint for at least one divided section overlaps a start waypoint of another divided section.

30. The method of claim 26, further comprising generating the reduced map by determining the free area in the map in which the object can move unrestrictedly without collision with obstacles in consideration of a size of the object and by reducing the map including information about the determined free area.

31. The method of claim 22, further comprising generating the reduced map generated by reducing the map.

32. The method of claim 31, wherein the map is a grid map and the grid map is reduced using each grid of a determined free area of the grid map.

33. The method of claim 31, wherein the reducing of the map is a linear reduction of the map.

34. The method of claim 31, wherein the reducing of the map is limited to a normalizing of the map according to a size of the object.

35. The method of claim 22, further comprising mapping waypoints in the approximate path, generated from the reduced map, into the map before division of the map in order to generate the detailed paths.

36. The method of claim 22, wherein the map is divided into the divided sections based on an available space of a memory.

37. The method of claim 36, wherein the generating of each of the detailed paths in each of the respective divided sections are respectively performed, in parallel, through at least one search algorithm.

38. The method of claim 22, the generating of each of the detailed paths in each of. the respective divided sections are respectively performed, in parallel, through at least one search algorithm.

39. The method of claim 22, wherein the object is a mobile robot and the method further comprises controlling the mobile robot to move sequentially along the detailed paths.

40. The method of claim 39, further comprising sensing an environment of the mobile robot and generating the map with obstacle information and free area information in the map in which the mobile robot can move unrestrictedly without collision with obstacles represented by the obstacle information.

41. The method of claim 22, wherein the object is an avatar in a computer generated environment.

42. The method of claim 41, further comprising controlling the avatar to move within the generated environment according to the detailed paths.

55. At least one computer readable medium comprising computer readable code to control at least one processing device to implement the method of claim 22.

43. An apparatus for generating a path, comprising:

a path generator generating an approximate path for an object moving relative to a map, of a reduced map, dividing the map into a plurality of sections based on a mapping of the approximate path of the reduced map into the map, and generating a detailed path in each of the divided sections respectively through at least one search algorithm,

wherein the path generator further sets a start waypoint and a destination waypoint in each of the divided sections based on points from the approximate path and generates the detailed path in each of the divided sections based on a path generating algorithm applied to each divided section using each set start and destination waypoint.

44. The apparatus of claim 43, wherein the path generating algorithm is at least one of an A-star and D-star algorithm.

45. The apparatus of claim 43, wherein the path generator determines a free area in the map in which the object can move unrestrictedly without collision with obstacles in consideration of a size of the object, and generates the reduced map by reducing the map including information about the determined free area.

46. The apparatus of claim 45, wherein the respective start and destination waypoints are mapped into the map before division of the map in order to generate the detailed paths.

47. The apparatus of claim 45, wherein when one or more of the mapped waypoints are located outside of the free area in the map, the path generator moves the one or more waypoints located outside of the free area to closest locations from the waypoints in the free area, respectively.

48. The apparatus of claim 43, wherein a destination waypoint for at least one divided section overlaps a start waypoint of another divided section.

49. A method for generating a path, comprising:

generating an approximate path for an object moving relative to a map, of a reduced map, dividing the map into a plurality of sections based on a mapping of the approximate path of the reduced map into the map, and generating a detailed path in each of the divided sections respectively through at least one search algorithm,

wherein the dividing of the map further comprises setting a start waypoint and a destination waypoint in each of the divided sections based on points from the approximate path and generating the detailed path in each of the divided sections based on a path generating algorithm applied to each divided section using each set start and destination waypoint.

50. The method of claim 49, wherein the path generating algorithm is at least one of an A-star and D-star algorithm.

51. The method of claim 49, further comprising determining a free area in the map in which the object can move unrestrictedly without collision with obstacles in consideration of a size of the object, and generating the reduced map by reducing the map including information about the determined free area.

52. The method of claim 51, wherein the respective start and destination waypoints are mapped into the map before division of the map in order to generate the detailed paths.

53. The method of claim 51, wherein when one or more of the mapped waypoints are located outside of the free area in the map, the one or more waypoints located outside of the free area are moved to closest locations from the waypoints in the free area, respectively.

54. The method of claim 49, wherein a destination waypoint for at least one divided section overlaps a start waypoint of another divided section.

56. At least one computer readable medium comprising computer readable code to control at least one processing device to implement the method of claim 49.