Robot and method for planning path of the same

• US 9,104,203 B2
• Filed: 10/18/2011
• Issued: 08/11/2015
• Est. Priority Date: 12/06/2010
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Roh, Chang Hyun
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): LOUIE, WAE LENNY
• Application Number:
  US13/275,804
• Publication Number:
  US 20120143372A1
• Time in Patent Office: 1,393 Days
• Field of Search: 701/23
• US Class Current: 1/1
• 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 robot and a method for planning a path of the robot. The method includes storing coordinates of a base cell in a queue structure, setting a plurality of cells adjacent to the base cell as scan cells, calculating a movement direction of the robot from the base cell to each of the scan cells, calculating movement cost of each of the scan cells according to the calculated movement direction, comparing the calculated movement cost and movement cost previously stored in each of the scan cells and determining whether or not coordinates of each of the scan cells are stored in the queue structure, and repeatedly performing a process of recording the movement direction and the movement cost in each of the scan cells and building a map of the movement space of the robot if the coordinates of each of the scan cells are stored in the queue structure.

Claims

1. A method comprising:

setting a respective cell of a plurality of cells configuring a space in which a robot moves as a base cell, and storing coordinates of the base cell in a queue structure;

searching for and setting cells adjacent to the base cell as scan cells;

for each scan cell,

calculating, by a computer, a movement direction of the robot from the base cell to the scan cell,

wherein the movement direction includes a primary movement direction for moving the robot from the base cell to the scan cell, and a secondary movement direction for moving the robot from a cell preceding the base cell to the base cell,

calculating, by the computer, a movement cost of the scan cell according to the calculated movement direction,

comparing, by the computer, the calculated movement cost and a movement cost previously stored in the scan cell,

determining, by the computer, based on said comparing, whether or not coordinates of the scan cell are to be stored in the queue structure and,

storing, by the computer, the coordinates of the scan cell in the queue structure if it is determined by said determining that the coordinates are to be stored;

for each cell having coordinates stored in the queue structure,

setting the respective cell as a base cell and,

performing said searching and setting, said calculating a movement direction, said calculating a movement cost, said comparing, said determining and said storing, to thereby build a map of the space;

calculating, by the computer, a movement path of the robot based on the built map; and

configuring the robot to move along the calculated movement path.

2. The method according to claim 1, further comprising:

updating obstacle information while moving the robot along the calculated movement path.

3. The method according to claim 2, wherein, for each respective scan cell, said comparing, said determining and said storing causes the coordinates of the scan cell to be stored in the queue structure if the calculated movement cost is less than the movement cost previously stored in the scan cell.

4. The method according to claim 1, wherein said performing is repeated until coordinates of the cells configuring the space are not present in the queue structure.

5. The method according to claim 1, wherein the queue structure is of a First-In First-Out (FIFO) type.

6. The method according to claim 1, wherein the movement cost is calculated by selecting any one of a diagonal weight, a straight weight and a rotation weight according to the calculated movement direction and adding the selected weight to the movement cost of the base cell.

7. The method according to claim 6, wherein the weight is selected by comparing a primary movement direction and a secondary movement direction of the scan cell with a primary movement direction and a secondary movement direction of the base cell.

8. The method according to claim 7, wherein the selecting of the weight includes:

selecting the diagonal weight if the primary movement direction of the scan cell coincides with the secondary movement direction of the base cell;

selecting the straight weight if the primary movement direction of the scan cell coincides with the primary movement direction of the base cell; and

selecting the rotation weight if the movement direction of the scan cell does not coincide with the movement direction of the base cell.

9. The method according to claim 1, wherein a goal point of the robot is initially set as the base cell.

10. The method according to claim 9, wherein, if the goal point is set to the base cell, the movement cost of the base cell which is the goal point is set to a predetermined value, the primary movement direction and the secondary movement direction are set to all directions of up, down, left and right, and the set movement cost and movement direction are stored in the cell.

11. The method according to claim 2, further comprising:

determining whether or not an obstacle is present in a cell in which the robot is located while the robot moves and updating obstacle information related to the location of the obstacle; and

determining whether or not the map needs to be rebuilt based on the updated obstacle information.

12. The method according to claim 11, wherein the obstacle information includes position information of the obstacle in a cell, and validity information indicating whether or not the position information of the obstacle is valid by directly sensing the obstacle.

13. A robot comprising:

a driving unit configured to move the robot along a movement path;

a sensor configured to sense an obstacle near the robot driven by the driving unit;

a map builder configured to

set a respective cell of a plurality of cells configuring a space in which the robot moves as a base cell, and store coordinates of the base cell in a queue structure,

search for and set a plurality of cells adjacent to the base cell as scan cells, for each scan cell,

calculate a movement direction of the robot from the base cell to the scan cell,

wherein the movement direction of the robot further comprises a primary movement direction for moving the robot from the base cell to the scan cell, and a secondary movement direction for moving the robot from a cell preceding the base cell to the base cell,

calculate movement cost of the scan cell according to the calculated movement direction,

compare the calculated movement cost and a movement cost previously stored in the scan cell,

determine, based on a result of said compare, whether or not coordinates of the scan cell are to be stored in the queue structure and,

store the coordinates of the scan cell in the queue structure when it is determined that the coordinates are to be stored, and

for each respective cell having coordinates stored in the queue structure,

set the respective scan cell as a base cell and,

perform said search and set, said calculate a movement direction, said calculate movement cost, said compare, said determine and said store to thereby build a map of the space of the robot;

a movement calculator configured to calculate a movement path of the robot based on the map built by the map builder; and

the robot configured to move along the movement path calculated by the movement path calculator.

14. The robot according to claim 13, wherein said compare, said determine and said store cause the map builder to store coordinates of the scan cell in a First-In First-Out queue structure if the calculated movement cost is less than movement cost previously stored in the scan cell.

15. The robot according to claim 13, wherein the map builder builds the map until the coordinates of the cells configuring the space are not present in the queue structure.

16. The robot according to claim 13, wherein the map builder calculates the movement cost of the scan cell by selecting any one of a diagonal weight, a straight weight and a rotation weight according to the calculated movement direction and adding the selected weight to the movement cost of the base cell.

17. The robot according to claim 16, wherein the map builder selects the diagonal weight if the primary movement direction of the scan cell coincides with the secondary movement direction of the base cell, selects the straight weight if the primary movement direction of the scan cell coincides with the primary movement direction of the base cell, and selects the rotation weight if the movement direction of the scan cell does not coincide with the movement direction of the base cell.

18. The robot according to claim 13, further comprising a goal point setting unit configured to set a goal point of the robot, wherein the map builder initially sets the goal point set by the goal point setting unit as the base cell.

19. The robot according to claim 13, further comprising:

an obstacle information updating unit configured to update obstacle information sensed by the sensor while moving the robot along the movement path calculated by the movement path calculator.

20. The robot according to claim 19, wherein:

the obstacle information updating unit determines whether or not the map needs to be rebuilt if the obstacle information is updated, and

the map builder rebuilds the map based on the updated obstacle information if it is determined that the map needs to be rebuilt.

21. The robot according to claim 19, wherein the obstacle information updating unit updates position information of the obstacle in a cell and validity information indicating whether or not the position information of the obstacle is valid by directly sensing the obstacle.