Method and apparatus for moving in minimum cost path using grid map

• US 7,953,551 B2
• Filed: 12/28/2005
• Issued: 05/31/2011
• Est. Priority Date: 12/30/2004
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Hyoung-ki, Park, Jun-ho
• Primary Examiner(s): Tran; Khoi
• Assistant Examiner(s): Peche; Jorge O
• Application Number:
  US11/319,054
• Publication Number:
  US 20060149465A1
• Time in Patent Office: 1,980 Days
• Field of Search: 701/209, 701/23, 701/26, 701/201, 701/202, 701/210, 901/50, 318/568.12, 706/19, 180/168
• US Class Current: 701/209
• 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/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/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

Abstract

A method of moving in a minimum cost path using a grid map, and an apparatus to perform the method, the method including calculating a move cost to a goal, from each of a plurality of cells comprises in a space in which a mobile home appliance moves, and planning a movement path to the goal according to the move cost; determining one or more via points at which a direction changes on the movement path; planning the minimum cost path from the movement path by selecting one or more shortest-distance via points from the via points; and moving from a first shortest-distance via point to a second shortest-distance via point.

Claims

1. A method of moving a mobile appliance in a shortest path using a grid map, the method comprising:

calculating a move cost to a goal, from each of a plurality of cells comprised in a space in which the mobile home appliance moves, and planning a neighbor-cell based movement direction to the goal according to the minimum move cost while maintaining a size of each of the plurality of cells;

determining one or more via points at which a direction changes on the neighbor-cell based movement direction;

planning the shortest path from an apart-cell based movement direction by selecting one or more shortest-distance via points from the via points; and

moving the mobile home appliance according to the apart-cell based movement direction,

wherein the neighbor-cell based movement direction is calculated from a central cell and a neighbor cell,

wherein the apart-cell based movement direction is calculated from the central cell and an apart cell,

wherein the shortest path determining initial via points is planned using the neighbor-cell based movement direction, and then the shortest path is planned using both the neighbor-cell based movement direction and the apart-cell based movement direction,

wherein the planning of the shortest path comprises;

determining whether a straight movement is possible between a first via point and a second via point which do not neighbor each other; and

erasing a via point existing between the first via point and the second via point in response to determining that the straight movement therebetween is possible, and

wherein the method is performed using at least one processor.

2. The method of claim 1, further comprising receiving information regarding the space in which the mobile home appliance moves.

3. The method of claim 1, wherein the move cost is calculated as a shortest distance from each cell to the goal according to cell to cell movement.

4. A method of moving a mobile home appliance in a shortest path using a grid map, the method comprising:

determining one or more via points at which a direction changes on a neighbor-cell based movement direction;

planning the shortest path from an apart-cell based movement direction by selecting one or more shortest-distance via points from the via points while maintaining a size of each of a plurality of cells comprised in a space in which the neighbor-cell based movement direction is located; and

moving the mobile home appliance according to the apart-cell based movement,

wherein the neighbor-cell based movement direction is calculated from a central cell and a neighbor cell,

wherein the apart-cell based movement direction is calculated from the central cell and an apart cell,

wherein the shortest path determining initial via points is planned using the neighbor-cell based movement direction, and then the shortest path is planned using both the neighbor-cell based movement direction and the apart-cell based movement direction,

wherein the planning of the shortest path comprises;

determining whether a straight movement is possible between a first via point and a second via point which do not neighbor each other; and

erasing a via point existing between the first via point and the second via point in response to determining that the straight movement therebetween is possible, and

wherein the method is performed using at least one processor.

5. The method of claim 4, wherein at least one of the via points exists in an intermediate position between a first and second shortest-distance via points on the apart-cell based movement direction.

6. The method of claim 4, wherein the neighbor-cell based movement direction exists between a goal and each of a plurality of cells comprised in a space in which a mobile home appliance moves.

7. The method of claim 6, wherein the neighbor-cell based movement direction is planned according to a minimum move cost calculated from each of the cells to the goal.

8. A method of moving a mobile home appliance in a shortest path using a grid map having a plurality of cells, the method comprising:

determining via points at which a direction changes on a neighbor-cell based movement direction while maintaining a size of each of a plurality of cells of the grid map on which the neighbor-cell based movement direction is located;

moving the mobile home appliance from a first via point to a second via point among the via points, wherein at least one of the via points exists at an intermediate point on the movement direction between the first and second via points;

determining whether a straight movement is possible between a first via point and a second via point which do not neighbor each other; and

erasing a via point existing between the first via point and the second via point in response to determining that the straight movement therebetween is possible,

wherein the neighbor-cell based movement direction is calculated from a central cell and a neighbor cell,

wherein the apart-cell based movement direction is calculated from the central cell and an apart cell,

wherein the shortest path determining initial via points is planned using the neighbor-cell based movement direction, and then the shortest path is planned using both the neighbor-cell based movement direction and the apart-cell based movement direction, and

wherein the method is performed using at least one processor.

9. The method of claim 8, wherein the neighbor-cell based movement direction exists between a goal and each of the plurality of cells comprised in a space in which the mobile home appliance moves.

10. The method of claim 9, wherein the neighbor-cell based movement direction is planned according to a minimum move cost calculated from each of the cells to the goal.

11. The method of claim 9, wherein the neighbor-cell based movement direction is predetermined.

12. The method of claim 9, further comprising calculating the neighbor-cell based movement direction before the determining of the via points.

13. A method of planning a shortest path on which a mobile home appliance moves using a grid map, the method comprising:

determining one or more via points at which a direction changes on a neighbor-cell based movement direction; and

planning the shortest path from an apart-cell based movement direction by selecting one or more shortest-distance via points from the via points while maintaining a size of each of a plurality of cells of the grid map on which the movement direction is located,

wherein the shortest path extends from a first shortest-distance via point to a second shortest-distance via point,

wherein the neighbor-cell based movement direction is calculated from a central cell and a neighbor cell,

wherein the apart-cell based movement direction is calculated from the central cell and an apart cell,

wherein the shortest path determining initial via points is planned using the neighbor-cell based movement direction, and then the shortest path is planned using both the neighbor-cell based movement direction and the apart-cell based movement direction,

wherein the planning of the shortest path comprises;

determining whether a straight movement is possible between a first via point and a second via point which do not neighbor each other; and

erasing a via point existing between the first via point and the second via point in response to determining that the straight movement therebetween is possible, and

wherein the method is performed using at least one processor.

14. The method of claim 13, wherein at least one of the via points exists in an intermediate position between the first and second shortest-distance via points on the movement path.

15. A method of planning a shortest path on which a mobile home appliance moves using a grid map having a plurality of cells, the method comprising:

determining via points at which a direction changes on a neighbor-cell based movement direction; and

planning at least a portion of the shortest path from a first via point to a second via point among the via points while maintaining a size of each of a plurality of cells of the grid map on which the movement direction is located,

wherein at least one of the via points exists at an intermediate point in the movement direction between the first and second via points,

wherein the neighbor-cell based movement direction is calculated from a central cell and a neighbor cell,

wherein the apart-cell based movement direction is calculated from the central cell and an apart cell,

wherein the shortest path determining initial via points is planned using the neighbor-cell based movement direction, and then the shortest path is planned using both the neighbor-cell based movement direction and the apart-cell based movement direction,

wherein the planning of at least a portion of the shortest path comprises;

determining whether a straight movement is possible between a first via point and a second via point which do not neighbor each other; and

erasing a via point existing between the first via point and the second via point in response to determining that the straight movement therebetween is possible, and

wherein the method is performed using at least one processor.