Apparatus and method for generating and using a grid map path

• US 8,849,559 B2
• Filed: 02/17/2010
• Issued: 09/30/2014
• Est. Priority Date: 02/18/2009
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Jeong, Woo-yeon, Lee, Su-jinn
• Primary Examiner(s): Amin, Bhavesh V
• Application Number:
  US12/656,793
• Publication Number:
  US 20100211244A1
• Time in Patent Office: 1,686 Days
• Field of Search: None
• US Class Current: 701/400
• 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 the 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,

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.

2. 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.

3. The apparatus of claim 2, 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.

4. The apparatus of claim 2, 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.

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

6. The apparatus of claim 4, 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.

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

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

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

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

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

12. 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.

13. 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.

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

15. The apparatus of claim 13, 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.

16. The apparatus of claim 1, 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.

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

18. The apparatus of claim 1, wherein an illustration of the object is provided by the apparatus as an avatar in a computer generated environment.

19. 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).

20. A method of generating a path of an object based on 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,

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.

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

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

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

24. The method of claim 23, wherein the dividing of the map further includes, when one or more of the mapped waypoints are located outside of the 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.

25. The method of claim 23, 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.

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

27. The method of claim 23, further comprising generating the reduced map by identifying a free area in the map so the object can move unrestrictedly without collision with the obstacles in consideration of a size of the object and by reducing the map including information about the identified free area.

28. The method of claim 20, further comprising generating the reduced map generated by reducing the map.

29. The method of claim 28, wherein the map is a grid map and the grid map is reduced using each grid of the free area of the grid map.

30. The method of claim 28, wherein the reducing of the map is a linear reduction of the map.

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

32. The method of claim 20, 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.

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

34. The method of claim 33, 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.

35. The method of claim 20, 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.

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

37. The method of claim 36, further comprising, prior to the generating of the approximate path, sensing an environment of the mobile robot and generating the map with generated obstacle information and free area information for the map so the mobile robot can move unrestrictedly without collision with obstacles represented by the obstacle information.

38. The method of claim 20, wherein the object is provided as an avatar in a computer generated environment.

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

40. An apparatus for generating a path, comprising:

a path generator generating an approximate path for the object, moving relative to the 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, and

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.

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

42. The apparatus of claim 40, wherein the path generator identifies a free area in the map so the object can move unrestrictedly without collision with the obstacles in consideration of a size of the object, and generates the reduced map by reducing the map including information about the identified free area.

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

44. The apparatus of claim 42, 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.

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

46. A method for generating a path, comprising:

generating an approximate path for the object, moving relative to the map, for 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, and

wherein the map is a grid map and the reduced map is generated by reducing the grid map by respectively anti-aliasing filtering information from different grids of the grid map.

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

48. The method of claim 46, further comprising identifying a free area in the map so the object can move unrestrictedly without collision with the obstacles in consideration of a size of the object, and generating the reduced map by reducing the map including information about the identified free area.

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

50. The method of claim 48, wherein when one or more of the mapped waypoints are located outside of the identified 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 identified free area, respectively.

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

52. At least one non-transitory computer readable medium comprising computer readable code to control at least one processing device to implement a method for generating a path of an object, the method for generating the path of the object being based on a map including information of obstacles and information of a free area in which the object can move relative to the map and avoid collision with the obstacles, the method comprising:

generating an approximate path within a reduced map generated from reducing the map including the information of the obstacles and the free area;

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,

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.

53. At least one non-transitory computer readable medium comprising computer readable code to control at least one processing device to implement a method for generating a path, the method for generating the path being based on a map including information of obstacles and information of a free area in which an object can move relative to the map and avoid collision with the obstacles, the method comprising:

generating an approximate path for the object, moving relative to the map, for 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,

wherein the map is a grid map and the reduced map is generated by reducing the grid map by respectively anti-aliasing filtering information from different grids of the grid map.