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

• US 20060149465A1
• Filed: 12/28/2005
• Published: 07/06/2006
• Est. Priority Date: 12/30/2004
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Park, Jun-ho, Lee, Hyoung-ki
• Granted Patent: US 7,953,551 B2
• Time in Patent Office: Days
• 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 in a minimum cost 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 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.

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. The method of claim 1, wherein the planning of the minimum cost path comprises:

determining whether a 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 movement therebetween is possible.

5. The method of claim 1, further comprising:

sensing an obstacle existing in a direction toward the second shortest-distance via point;

replanning the minimum cost path in response to the obstacle being sensed in the direction toward the second shortest-distance via point; and

moving to a third shortest-distance via point existing on the replanned minimum cost path.

6. The method of claim 5, wherein the replanning of the minimum cost path comprises:

selecting one or more of the via points from the cells according to information regarding a position of the sensed obstacle; and

replanning the minimum cost path by selecting one or more shortest-distance via points from the selected via points.

7. The method of claim 5, wherein the obstacle is sensed due to contact between the mobile home appliance and the obstacle.

8. The method of claim 5, wherein the obstacle is sensed before or during movement from the first shortest-distance via point to the second shortest-distance via point.

9. The method of claim 5, wherein the obstacle is a dent or a protrusion existing, in the direction toward the second shortest-distance via point, on a surface on which the mobile home appliance is moving.

10. The method of claim 5, further comprising sensing a wall existing at one or more side of the direction toward the second shortest-distance via point and the direction to the third shortest-distance via point.

11. A method of moving in a minimum cost path using a grid map, the method comprising:

dividing a space, in which a mobile home appliance moves, into a plurality of cells including a start point and a goal, and planning the minimum cost path according to cell-unit movement; and

moving from a first cell to a second cell in the minimum cost path;

wherein a movement direction is calculated from physical positions of the first and second cells in response to the first cell and the second cell not neighboring one another.

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

13. The method of claim 11, further comprising:

sensing an obstacle existing in a direction toward the second cell;

replanning the minimum cost path in response to the obstacle being sensed in the direction toward the second cell; and

moving to a third cell existing on the replanned minimum cost path.

14. The method of claim 13, wherein the replanning of the minimum cost path comprises replanning the minimum cost path from a current position of the mobile home appliance to the second cell or the goal.

15. The method of claim 13, wherein the obstacle is sensed due to contact between the mobile home appliance and the obstacle.

16. The method of claim 13, wherein the obstacle is sensed before or during movement from the first cell to the second cell.

17. A mobile home appliance comprising:

a moving unit to be moved by a dynamic force; and

a control unit to plan a path in which the moving unit moves, and to control the moving unit to move in the path;

wherein the control unit comprises;

a path planner to calculate a move cost to a goal, from each of a plurality of cells comprised in a space in which a mobile home appliance moves, and to plan a movement path to the goal according to the move cost,

a via point finder to find one or more via points at which a direction changes on the movement path, and

a minimum cost path planner to plan a minimum cost path from the movement path by selecting one or more shortest-distance via points from the via points.

18. The mobile home appliance of claim 17, further comprising a user interface unit to receive information regarding the space in which the mobile home appliance moves.

19. The mobile home appliance of claim 17, wherein the move cost is calculated as a shortest distance from each cell to the goal according to cell to cell movement.

20. The mobile home appliance of claim 17, wherein the control unit controls the moving unit to move from a first shortest-distance via point to a second shortest-distance via point, the first and second shortest-distance via points being selected by the minimum cost path planner.

21. The mobile home appliance of claim 17, wherein the minimum cost path planner determines whether it is possible to move between a first via point and a second via point which do not neighbor each other among the via points, and erases a via point existing between the first via point and the second via point in response to determining that it is possible to move between the first and second via points.

22. The mobile home appliance of claim 17, further comprising a sensing unit to sense an obstacle existing in a direction in which the moving unit moves, wherein the control unit further comprises a path replanner to replan the minimum cost path in response to the sensing unit sensing the obstacle.

23. The mobile home appliance of claim 22, wherein the path replanner selects one or more of the via points from the cells according to information regarding a position of the obstacle sensed by the sensing unit, and selects one or more shortest-distance via points from the selected via points to replan the minimum cost path.

24. The mobile home appliance of claim 22, wherein the sensing unit comprises a collision sensor to sense a contact, an obstacle sensor to sense the obstacle within a predetermined distance, or a combination thereof.

25. The mobile home appliance of claim 22, wherein the sensing unit comprises a fall sensor to sense a dent or a protrusion existing, in the direction in which the moving unit moves, on a surface on which the mobile home appliance is moving.

26. The mobile home appliance of claim 22, wherein the sensing unit comprises a wall sensor to sense a wall existing at one or more sides of the direction in which the moving unit moves.

27. The mobile home appliance of claim 17, wherein the moving unit comprises:

a driver to receive a dynamic force from a power supply unit and adjust a movement direction;

a traveler to receive the dynamic force from the driver and move in the movement direction adjusted by the driver; and

a movement distance calculator to calculate a distance which the traveler has moved.

28. At least one computer readable medium storing instructions that control at least one processor to perform a method of moving in a minimum cost 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 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.

29. At least one computer readable medium storing instructions that control at least one processor to perform a method of moving in a minimum cost path using a grid map, the method comprising:

dividing a space, in which a mobile home appliance moves, into a plurality of cells including a start point and a goal, and planning the minimum cost path according to cell-unit movement; and

moving from a first cell to a second cell in the minimum cost path,

wherein a movement direction is calculated from physical positions of the first and second cells in response to the first cell and the second cell not neighboring one another.

30. A method of moving in a minimum cost path using a grid map, the method comprising:

determining one or more via points at which a direction changes on a 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.

31. The method of claim 30, 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.

32. The method of claim 30, wherein the movement path exists between a goal and each of a plurality of cells comprised in a space in which a mobile home appliance moves.

33. The method of claim 32, wherein the movement path is planned according to a move cost calculated from each of the cells to the goal.

34. A method of moving a mobile home appliance in a minimum cost path using a grid map, the method comprising:

moving from a first cell to a second cell in the minimum cost path;

wherein a movement direction is determined from positions of the first and second cells in response to the first and second cells not neighboring one another.

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

determining via points at which a direction changes on a movement path; and

moving 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 path between the first and second via points.

36. The method of claim 35, wherein the movement path exists between a goal and each of the plurality of cells comprised in a space in which the mobile home appliance moves.

37. The method of claim 36, wherein the movement path is planned according to a move cost calculated from each of the cells to the goal.

38. The method of claim 36, wherein the movement path is predetermined.

39. The method of claim 36, further comprising calculating the movement path before the determining of the via points.

40. The method of claim 35, further comprising sensing an obstacle between the first and second via points.

41. The method of claim 40, further comprising determining a new portion of the minimum cost path, the new portion avoiding the obstacle between the first and second via points.

42. A method of planning a minimum cost 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 movement path; and

planning the minimum cost path from the movement path by selecting one or more shortest-distance via points from the via points;

wherein the minimum cost path extends from a first shortest-distance via point to a second shortest-distance via point.

43. The method of claim 42, 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.

44. A method of planning a minimum cost 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 movement path; and

planning at least a portion of the minimum cost path 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 path between the first and second via points.

45. The method of claim 44, wherein the movement path exists between a goal and each of the plurality of cells comprised in a space in which the mobile home appliance moves.