Efficient navigation of autonomous carriers

• US 20040117079A1
• Filed: 01/02/2004
• Published: 06/17/2004
• Est. Priority Date: 03/15/2001
• Status: Active Grant

• Current Assignee: Aktiebolaget Electrolux
• Original Assignee: Aktiebolaget Electrolux
• Inventors: Hulden, Jarl
• Granted Patent: US 7,206,677 B2
• Time in Patent Office: Days
• US Class Current: 701/23
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/0219 ensuring the processing of the whole working surface
• CPC Class Codes: G05D 1/0225 involving docking at a fixed facility, e.g. base station or loading bay parking aids B62D15/027
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

According to the invention, autonomous carriers or vehicles are efficiently navigated over a field of operation. The carriers are equipped to execute a selected procedure at more than one desired location on the field, and the navigation system of the invention directs the carrier to the location that is preferentially accessible to it, based on a defined criterion. After the carrier has executed the selected procedure at the location which is preferentially accessible to it, the navigation system directs the carrier to the location which is preferentially accessible to the carrier from the carrier'"'"'s new position. This procedure is repeated until all the locations at which the procedure is to be executed have been reached. The task of determining a navigation route to a location that can be preferentially accessed is based on an efficient, structured search procedure of low computational complexity.

Claims

1. A method of navigating an autonomous surface treatment apparatus over a predetermined field of operation, comprising the steps of:

dividing said predetermined field of operation into cells, each of which being adapted to be indicated as treated, untreated or occupied by an obstacle;

determining, for a current cell in which the autonomous apparatus is located, a navigation route to an obstacle-free and untreated cell that requires the smallest amount of energy for moving the autonomous surface treatment apparatus thereto according to a predetermined energy cost function; and

navigating the autonomous surface treatment. apparatus from the current cell to the obstacle-free and untreated cell according to the determined navigation route and updating the indication of that cell as treated,

characterized by the steps of;

defining a search algorithm based on the question whether there is an untreated cell with cost N, where N starts at 1 and counts upwards to create a number of cost levels based on specific movements of the autonomous surface treatment apparatus required for it to arrive at said untreated cell;

building three lists around the currrent cell each list containing the coordinates of cells with the lowest cost and of the coordinates of cells of the two consecutive higher cost levels, but limited to cells adjacent to the current cell;

processing the lists, one by one in cost-order, starting with the list having the lowest cost, wherein as a list is processed the cells are examined one by one to identify cells indicated as untreated;

during processing of a list, adding cells to the two consecutive lists of higher cost by considering, for each cell under process, adjacent cells in the directions forward, left and right;

after processing of a list and updating the two consecutive lists of higher cost, discarding the list under process and processing the list next to follow;

repeating the search process until an untreated and unoccupied cell has been found;

2. The method according to claim 1, characterized in that said energy cost finction depends both on the distance from the current cell to an obstacle-free and untreated cell as well as the total change of direction required for moving thereto, a larger change of direction and a larger distance being given a larger cost.

3. The method according to claim 1 or 2, characterized by restricting said autonomous apparatus to move from cell to cell in a limited number of directions.

4. The method according to claim 3, characterized in that the cost for a route that requires more than one cell-to-cell movement is determined by accumulating the cost for each change of direction along the route and taking the total distance into account.

5. The method according to any of the preceding claims, characterized in that the step of determining a navigation route that requires the smallest amount of energy according to a predetermined energy cost function includes the steps of:

allocating to each of a number of cells in the surroundings of the current cell a cost based on the distance to that cell as well as the total change of direction required for moving thereto;

checking, in cost-order starting from the cell having the lowest cost, whether any of the cost-allocated cells is indicated as untreated until an untreated cell is found; and

extracting the route to the found cell as a lowest-cost route that is used as the navigation route.

6. The method according to claim 5, characterized by allocating costs to cells in the surroundings of the current cell that fall within a given cost interval and checking the cost-allocated cells for an untreated cell in cost-order, and if no such untreated cell is found among these cells, gradually increasing the cost interval within which cells are allocated costs and continuing to check cells in cost-order until an untreated cell is found.

7. The method according to claim 5 or 6, characterized by assigning to each cost-allocated cell a direction indicator to enable extraction of the lowest-cost route by means of back tracing.

8. The method according to any of the preceding claims, characterized in that the size ofthe cells is approximately equal to or smaller than the size of the autonomous apparatus.

9. The method according to any of the preceding claims, characterized in that said determining step and said navigating step are repeated until the entire field of operation has been treated.

10. The method according to any of the preceding claims, characterized in that cells are being indicated as occupied by an obstacle based on information from an obstacle detection system of the autonomous apparatus.

11. An autonomous surface treatment apparatus having power operated means for moving the apparatus, a sensing system for detection of obstacles and a navigation system for navigating the apparatus over a predetermined field of operation, said navigation system comprising:

means for logically dividing said predetermined field of operation into cells, each of which is being adapted to be indicated as treated, untreated or occupied by an obstacle;

means for determining, for a current cell in which the autonomous apparatus is located, a navigation route to an obstacle-free and untreated cell that requires the smallest amount of energy for moving the autonomous surface treatment apparatus thereto according to a predetermined energy cost function; and

means for navigating the autonomous surface treatment apparatus from the current cell to the obstacle-free and untreated cell according to the determined navigation route and updating the indication of that cell as treated,

characterized by computing means adapted to perform the following operations;

defining a search algorithm based on the question whether there is an untreated cell with cost N, where N starts at 1 and counts upwards, to create a number of cost levels based on specific movements of the autonomous surface treatment apparatus required for it to arrive at said untreated cell;

building three lists around the current cell each list containing the coordinates of cells with the lowest cost and of the coordinates of cells of the two consecutive higher cost levels, but limited to cells adjacent to the current cell;

processing the lists, one by one in cost-order, starting with the list having the lowest cost, wherein as a list is processed the cells are examined one by one to identify cells indicated as untreated;

during processing of a list, adding cells to the two consecutive lists of higher cost by considering, for each cell under process, adjacent cells in the directions forward, left and right;

after processing of a list and updating the two consecutive lists of higher cost, discarding the list under process until an untreated and unocccupied cell has been found.

12. The apparatus according to claim 11, characterized in that said energy cost finction depends both on the distance from the current cell to an obstacle-free and untreated cell as well as the total change of direction required for moving thereto, a larger change of direction and a larger distance being given a larger cost.

13. The apparatus according to claim 11 or 12, characterized in that said autonomous apparatus is restricted to move from cell to cell in a limited number of directions.

14. The apparatus according to claim 13, characterized in that the cost for a route that requires more than one cell-to-cell movement is determined by accumulating the cost for each change of direction along the route and taking the total distance into account.

15. The apparatus according to any of the claims 11-14, characterized in that said means for determining a navigation route that requires the smallest amount of energy according to a predetermined energy cost function includes:

means for allocating to each of a number of cells in the surroundings of the current cell a cost based on the distance to that cell as well as the total change of direction required for moving thereto;

means for checking, in cost-order starting from the cell having the lowest cost, whether any of the cost-allocated cells is indicated as untreated until such an untreated cell is found; and

means for extracting the route to the found cell as a lowest-cost navigation route to an untreated cell.

16. The apparatus according to claim 15, characterized in that said allocating means and said checking means interwork in such a manner that costs are allocated to cells in the surroundings of the current cell that fall within a given cost interval and that these cost-allocated cells are checked in cost-order to find an untreated cell, and that if no such untreated cell is found among these cells the cost interval within which cells are allocated costs is gradually increased and the checking of cells is continued in cost-order until an untreated cell is found.

17. The apparatus according to claim 15 or 16, characterized in that said navigation system further comprises means for assigning to each cost-allocated cell a direction indicator to enable extraction of the lowest-cost route by means of back tracking.

18. The apparatus according to any of the claims 11-17, characterized in that the size of the cells is approximately equal to or smaller than the size of the autonomous apparatus.

19. The apparatus according to any of the claims 11-18, characterized in that determining means is configured for determining a sequence of navigation routes according to which the navigation means operates until the entire field of operation has been treated.

20. The apparatus according to any of the claims 11-19, characterized in that said autonomous surface treatment apparatus is operable for performing floor treatment such as vacuum cleaning, sweeping, brushing or polishing within said field of operation.

21. A computer program for navigating an autonomous surface treatment apparatus over a predetermined field of operation, when the program is executed by a computer arranged in connection with said autonomous apparatus, said computer program comprising:

program means for logically dividing said predetermined field of operation into cells, each of which adapted to be indicated as treated, untreated or occupied by an obstacle;

program means for performing, for a current cell in which the autonomous apparatus is located, a structured search for an obstacle-free and untreated cell, wherein said program means for performing a structured search comprises;

program means for allocating to each of a number of cells in the surroundings of the current cell a cost based on the distance to that cell as well as the total change of direction required for moving thereto;

program means for checking, in cost-order starting from the cell having the lowest cost, whether any of the cost-allocated cells is indicated as untreated until such an untreated cell is found; and

program means for extracting the route to a found cell as a lowest-cost navigation route to an untreated cell; and

program means for navigating the autonomous surface treatment apparatus from the current cell to an obstacle-free and untreated cell according to the extracted lowest-cost navigation route and updating the indication of that cell as treated,

characterized in that said program means for performing a structured search further comprises;

program means for building three lists around the current cell, a first list containing the coordinates of cells with the lowest cost and the two additional lists containing the coordinates for cells of the two following cost levels, respectively;

program means for processing the lists, one by one in cost-order, starting with the list having the lowest cost, wherein as a list is processed the cells are examined one by oneto identify cells indicated as untreated;

said program means for processing the lists in doing so adding cells to the two consecutive lists of higher cost by considering, for each cell under process, adjacent cells in the direction forward, left and right;

said program means for processing the lists, after completion of a list and updating the two consecutive lists of higher cost, discarding the list thus completed and processing the list next to follow;

22. The computer program according to claim 21, characterized in that said allocating program means and said checking program means interwork in such a manner that costs are allocated to cells in the surroundings of the current cell that fall within a given cost interval and that these cost-allocated cells are checked in cost-order to find an untreated cell and that if no such untreated cell is found among these cells the cost interval within which cells are allocated costs is gradually increased and the checking of cells is continued in cost-order until an untreated cell is found.

23. The computer program according to claim 21 or 22, characterized by program means for assigning to each cost-allocated cell a direction indicator to enable extraction of the lowest-cost route by means of back tracing.