WO 02/075470
`
`PCT/SE02/00471
`
`21
`
`CLAIMS
`
`1. A method of navigating an autonomous surface treatment apparatus over a
`
`predeterminedfield of operation, comprising the stepsof:
`
`-
`
`dividing said predeterminedfield of operation into cells, each of which being
`
`adapted to be indicated as treated, untreated or occupied by an obstacle;
`
`5
`
`-
`
`determining, for a currentcell in which the autonomousapparatusis 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 autonomoussurface treatment apparatus from the currentcell
`
`10
`
`to the obstacle-free and untreated cell according to the determined navigation
`
`route and updating the indication of that cell as treated,
`
`characterized bythe stepsof:
`
`—
`
`defining a search algorithm based on the question whether there is an
`untreated cell with cost N, where N starts at 1 and counts upwardsto create
`a numberof cost levels based on specific movements of the autonomous
`
`15
`
`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 ofthe coordinates ofcells of the
`
`two consecutive highercost levels, but limited to cells adjacentto the current
`
`20
`
`cell;
`
`—
`
`processing thelists, one by onein cost-order, starting with the list having the
`lowest cost, whereinasa list is processed the cells are examined oneby one
`to identify cells indicated as untreated;
`
`—
`
`during processing ofa list, adding cells to the two consecutive lists of higher
`
`25
`
`cost by considering, for each cell under process, adjacent cells in the
`
`directions forward, left and right;
`
`-
`
`after processing ofa list and updating the two consecutivelists of higher cost,
`
`discarding the list under process and processing the list next to follow;
`
`Silver Star Exhibit 1002 - 501
`Silver Star Exhibit 1002 - 501
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`22
`
`—
`
`repeating the search processuntil an untreated and unoccupied cell has been
`
`found;
`
`2.
`
`The method according to claim 1,
`
`characterized in that said energy cost function dependsboth on the distance from the
`
`current cell to an obstacle-free and untreated cell as well as the total change of
`
`direction required for movingthereto, a larger change ofdirection 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 movefrom cell to cell in
`a limited numberofdirections.
`
`10
`
`15
`
`20
`
`4,
`
`The method accordingto claim 3,
`
`characterized in that the cost for a route that requires more than onecell-to-cell
`
`movementis 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 ofthe preceding claims,
`characterized in that the step of determining a navigation route that requires the
`
`smallest amountofenergy according to a predetermined energy cost function includes
`
`the steps of:
`
`-
`
`-
`
`allocating to each of a numberofcells in the surroundings ofthe current cell
`a cost based onthe distanceto thatcell as well as the total changeofdirection —
`
`required for moving thereto;
`
`checking, in cost-orderstarting from the cell having the lowest cost, whether
`any ofthe cost-allocated cells is indicated as untreated until an untreated cell
`is found; and
`
`25
`
`— _ extracting the route to the found cell as a lowest-cost route that is used as the
`
`navigation route.
`
`The method according to claim 5,
`6.
`characterized by allocating costs to cells in the surroundingsofthe current cell that
`
`fall within a given cost interval and checking the cost-allocated cells for an untreated
`
`30
`
`cell in cost-order, and if no such untreated cell is found amongthesecells, gradually
`
`Silver Star Exhibit 1002 - 502
`Silver Star Exhibit 1002 - 502
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`23
`
`increasing the cost interval within which cells are allocated costs and continuing to
`
`check cells in cost-order until an untreated cell is found.
`
`The method according to claim 5 or6,
`7.
`characterized by assigning to each cost-allocated cell a direction indicator to enable
`extraction of the lowest-cost route by meansof backtracing.
`8.
`The method according to any of the preceding claims,
`
`characterizedin that the size ofthe cells is approximately equal to or smaller than the
`
`size of the autonomous apparatus.
`
`9.
`
`The method accordingto 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 autonomoussurface treatment apparatus having power operated meansfor
`
`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:
`
`—
`
`meansfor 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 autonomousapparatus
`
`is located, a navigation route to an obstacle-free and untreated cell that
`
`requires the smallest amount of energy for moving the autonomoussurface
`
`25
`
`treatment apparatus thereto according to a predetermined energy cost
`
`function; and
`
`— means for navigating the autonomoussurface 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 meansadapted to perform the following operations:
`
`30
`
`Silver Star Exhibit 1002 - 503
`Silver Star Exhibit 1002 - 503
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`24
`
`-
`
`defining a search algorithm based on the question whetherthere is an
`
`untreated cell with cost N, where N starts at 1 and counts upwards, to create
`
`a numberof cost levels based on specific movements of the autonomous
`
`surface treatment apparatus requiredforit 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 highercost levels, but limited to cells adjacent to the currentcell;
`
`—
`
`processingthelists, one by one in cost-order, starting with the list having the
`
`lowest cost, wherein asalist is processed the cells are examined one by one
`
`10
`
`to identify cells indicated as untreated;
`
`—
`
`during processing ofa list, adding cells to the two consecutivelists of higher
`
`cost by considering, for each cell under process, adjacent cells in the
`
`directions forward, left and right;
`
`-
`
`after processing ofa list and updating the two consecutivelists of higher cost,
`
`15
`
`discarding the list underprocess until an untreated and unocccupiedcell has
`
`been found.
`
`12.
`
`The apparatus accordingto claim 11,
`
`characterized in that said energy cost function 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 movingthereto, alarger change ofdirection andalarger distance
`
`being given a larger cost.
`
`13.
`
`The apparatus according to claim 11 or 12,
`
`characterizedin that said autonomousapparatusis restricted to movefrom cellto cell
`
`in a limited number ofdirections.
`
`25
`
`14,
`
`The apparatus according to claim 13,
`
`characterized in that the cost for a route that requires more than onecell-to-cell
`
`movementis determined by accumulating the cost for each changeofdirection along
`
`the route and taking the total distance into account.
`
`15.
`
`The apparatus according to any of the claims 11-14,
`
`30
`
`characterized in that said means for determining a navigation route that requires the
`
`Silver Star Exhibit 1002 - 504
`Silver Star Exhibit 1002 - 504
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`25
`
`smallest amount ofenergy according to apredetermined energy cost function includes:
`
`— means for allocating to each of a numberofcells in the surroundings of the
`
`current cell a cost based on the distanceto thatcell as wellas 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
`
`—
`
`meansfor extracting the route to the found cell as a lowest-cost navigation
`
`route to an untreated cell.
`The apparatus accordingto claim 15,
`16.
`characterizedin that said allocating means and said checking meansinterworkin such
`
`a mannerthat costs are allocated to cells in the surroundingsofthe currentcell thatfall
`
`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 amongthesecells
`
`15
`
`the cost interval within which cells are allocated costs is gradually increased and the
`
`checking ofcells 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 meansfor assigning
`
`to each cost-allocated cell a direction indicator to enable extraction of the lowest-cost
`
`20
`
`route by means of backtracking.
`
`18.
`
`The apparatus according to any of the claims 11-17,
`
`characterizedin that the size ofthe cells is approximately equal to or smaller than the
`
`size of the autonomousapparatus.
`
`19,
`
`The apparatus accordingto any of the claims 11-18,
`
`characterized in that determining meansis configured for determining a sequence of
`
`navigation routes according to which the navigation means operates until the entire
`
`field of operation has beentreated.
`
`20.
`
`The apparatus according to any of the claims 11-19,
`
`characterized in that said autonomous surface treatment apparatus is operable for
`
`30
`
`performingfloor treatment such as vacuum cleaning, sweeping, brushing orpolishing
`
`Silver Star Exhibit 1002 - 505
`Silver Star Exhibit 1002 - 505
`
`

`

`WO 02/075470
`
`|
`
`PCT/SE02/00471
`
`within said field of operation.
`
`26
`
`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 autonomousapparatus,
`
`said computer program comprising:
`
`—
`
`program meansfor 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 numberofcells in the
`
`surroundingsof the current cell a cost based on the distanceto that cell as
`
`well as the total changeof direction required for moving thereto;
`
`-
`
`program meansfor checking,in cost-orderstarting 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 meansfor 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 ofthat
`
`cell as treated,
`
`characterized in that said program means for performinga structured search further
`
`comprises:
`
`-
`
`program meansfor building three lists around the currentcell, 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
`
`Silver Star Exhibit 1002 - 506
`Silver Star Exhibit 1002 - 506
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`27
`
`cost levels, respectively;
`
`-
`
`program meansfor processingthelists, one by one in cost-order, starting
`
`with the list having the lowest cost, wherein as a list is processed the cells
`
`are examined oneby oneto identify cells indicated as untreated;
`said program meansfor processing thelists in doing so addingcells 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 meansfor processingthelists, after completion of a list and
`
`updating the two consecutive lists of higher cost, discarding the list thus
`
`10
`
`completed and processing the list next to follow;
`
`22.
`
`The computer program accordingto claim 21,
`
`characterizedin that said allocating program means andsaid checking program means
`
`interwork in such a mannerthat costs are allocated to cells in the surroundingsof the
`
`current cell that fall within a given cost interval andthat these cost-allocated cells are
`checked in cost-order to find an untreated cell and that if no such untreated cell is
`
`15
`
`found amongthese 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 meansfor assigning to each cost-allocated cell a direction
`
`indicator to enable extraction of the lowest-cost route by means of back tracing.
`
`Silver Star Exhibit 1002 - 507
`Silver Star Exhibit 1002 - 507
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`1113
`
`Silver Star Exhibit 1002 - 508
`Silver Star Exhibit 1002 - 508
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`2/13
`
`
`
`Silver Star Exhibit 1002 - 509
`Silver Star Exhibit 1002 - 509
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`3/13
`
`[___<] TRANSMITTER |
`
`>|ENC
`
`L-WHEEL
`MOTOR
`DRIVER
`
`L-WHEEL
`MOTOR
`
`R-WHEEL
`MOTOR
`
`R-WHEEL
`MOTOR
`DRIVER
`CPU
`INPUT
`COMMANDS
`>——ss——s—s—C—s—sés}T CQENC
`
`
`
`
`CLK
`
`L-BUMPER
`
`R-BUMPER
`
`TILT
`SWITCHES
`
`Ne
`
`- L-HALL
`SENSOR
`
`MC68332
`
`R-HALL
`SENSOR
`
`FPROM
`512X8
`
`o
`
`oO
`
`foros|aes
`
`BRUSH
`
`DRIVER
`
`FANMOTOR
`
`DRIVER
`
`MOTOR
`
`RECEIVER
`
`LS} A/D
`i
`
`AID
`INPUT
`
`E?PROM
`
`256x16
`
`MUXa-<}-—_—___—____5, MUX INPUT
`
`Fig. 4
`
`Silver Star Exhibit 1002 - 510
`Silver Star Exhibit 1002 - 510
`
`

`

`PCT/SE02/00471
`
`
`bezebzzzbe
`sttzpe(ipzpeperp
`
`WO 02/075470 2popepore
`
`Silver Star Exhibit 1002 - 511
`Silver Star Exhibit 1002 - 511
`
`

`

`WO02/075470
`
`PCT/SE02/00471
`
`5/13
`
`STARTING IN
`A CURRENT CELL
`
`101
`
`
`
`BUILD LIST OF CELL(S)
`WITH COST N
`
`
`(N INITIATED AS EQUALTO1)
`
`
`INCREMENT N
`(BY 1)
`
`
`
` IS ANY CELL
`
`IN THE LIST INDICATED
`AS UNTREATED?
`
`102
`
`EXTRACT ROUTE TO
`THE UNTREATED CELL
`
`104
`
`Fig. 7
`
`Silver Star Exhibit 1002 - 512
`Silver Star Exhibit 1002 - 512
`
`

`

`WO02/075470
`
`PCT/SE02/00471
`
`nzzero
`bbe
`err
`
` pore2ioe
`
`
`
`Silver Star Exhibit 1002 - 513
`Silver Star Exhibit 1002 - 513
`
`

`

`WO02/075470
`
`PCT/SE02/00471
`
`7/13
`
`Fig. 10
`
`Fig. 11A
`
`Fig. 11B
`
`Silver Star Exhibit 1002 - 514
`Silver Star Exhibit 1002 - 514
`
`
`
`
`

`

`WO02/075470
`
`PCT/SE02/00471
`
`8/13
`
`Fig. 11C
`
`Fig. 11D
`
`Fig. 11E
`
`Silver Star Exhibit 1002 - 515
`Silver Star Exhibit 1002 - 515
`
`
`
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`9/13
`
`Fig. 11F
`
`Fig. 11G
`
`Fig. 11H
`
`Silver Star Exhibit 1002 - 516
`Silver Star Exhibit 1002 - 516
`
`
`
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`10/13
`
`Fig. 111
`
`Fig. 11J
`
`Fig. 11K
`
`Silver Star Exhibit 1002 - 517
`Silver Star Exhibit 1002 - 517
`
`
`
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`11/13
`
`Fig. 11L
`
`Fig. 11M
`
`Fig. 11N
`
`Silver Star Exhibit 1002 - 518
`Silver Star Exhibit 1002 - 518
`
`
`
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`12/13
`
`Fig. 110
`
`Fig. 11P
`
`Silver Star Exhibit 1002 - 519
`Silver Star Exhibit 1002 - 519
`
`
`
`

`

`WO 02/075470
`
`PCT/SE02/00471
`
`13/13
`
`
`
`i|!r-4_|ILi||—_)||
`
`Low—
`
`|
`—!
`
`
`|
`
`Fig. 12
`
`®ZzG6<<OnK
`
`Silver Star Exhibit 1002 - 520
`Silver Star Exhibit 1002 - 520
`
`
`
`

`

`A. CLASSIFICATION OF SUBJECT MATTER
`
`
`International application No.
`PCT/SE 02/00471
`
`C. DOCUMENTS CONSIDERED TO BE RELEVANT
`
`Category*| Citation of document, with indication, where appropriate, of the relevant passages
`
`
`WO 9940496 A (SIEMENS AKTIENGESELLSCHAFT),
`12 August 1999 (12.08.99), page 2,
`
`
`US 4674048 A (K.OKUMURA), 16 June 1987 (16.06.87),
`
`column 3,
`line 33 - column 6,
`line 17, figures 3-6,
`cited in the application
`
`US 5353224 A (J.W.LEE ET AL), 4 October 1994
`(04.10.94), column 3,
`line 41 - column 5,
`abstract
`,
`
`
`line 4,
`
`
`
`
`IPc7: GO5D 1/02
`According to International Patent Classification (IPC) or to both national classification and IPC
`
`
`
`B. FIELDS SEARCHED
`.
`Minimum documentation searched (classification system followed byclassification symbols)
`:
`
`
`IPC7: B25J, GO5D
`Documentation searched other than minimum documentation to the extent that such documents are included in the fields searched
`
`
`
`
`SE,DK,FI,NO classes as above
`
`
`Electronic data base consulted during the international search (name of data base and, where practicable, search terms used)
`
` EPO-INTERNAL,WPI, PAJ
`
`
`
`line 29 - line 36, abstract
`
`
`
`
`
`
`
`
`
`[x] Further documents are listed in the continuation of Box C.[xl See patent family annex. '
`
`*
`Special categories of cited documents
`“[” later document published after the international filing date or priarity
`“A”
`document defining the general state of the art which is not considered
`date andnot in conflict with the application but cited to understand
`to be of particular relevance
`the principle or theory underlying the invention
`earlier application or patent but published on or after the international
`documentof particular relevance: the claimedinvention cannot be
`“B’
`ete filing date
`. .
`.
`considered novel or cannot be considered to involve an inventive
`L”
`document which may throw doubts on priority claim(s) or which is
`step when the documentis taken alone
`Cited to establish the publication date of another citation or other
`.
`:
`.
`.
`Special reason (as speci fied)
`documentof particular relevance: the claimed invention cannoi be
`.
`.
`sigs
`considered to involve an inventive step when the documentis
`"0"
`9 document referring to an oral disclosure, use, exhibition or other
`combined with one or more other such
`documents, such cambination
`.
`.
`.
`.
`.
`being obviousto a person skilledin the art
`“P"
`document published prior to the international filing date but later than
`8
`P
`the priority date claimed
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`“&” document member of the same patent family Date of the actual completion of the international search
`
`Date of mailing of the international search report
`gz-O7- 2002
`
`
`
`6 June 2002
`
`Authorized officer
`
`Name and mailing address of the ISA/
`
`Swedish Patent Office
`
`
`
`Goran Magnusson /itw
`
`
`
`Box 5055, S-102 42 STOCKHOLM
`Facsimile No. +46 8 666 02 86
`Telephone No.
`+46 8 782 25 00
`
`
`
`
`
`Form PCTJISA/210 (second sheet) (July 1998)
`
`
`
`“X"
`
`“Y”
`
`Silver Star Exhibit 1002 - 521
`Silver Star Exhibit 1002 - 521
`
`

`

`INTERNATIONAL SEARCH REPORT
`
`International application No.
`
`
`
`Citation of document, with indication, where appropriate, of the relevant passages
`
`
`
`
`
`
`
` US 5321614 A (G.T.D.ASHWORTH), 14 June 1994
`(14.06.94), column 1,
`line 56 - column 4,
`
`figure 4, abstract
`
`
`
`line 17 - line 37
`
`line 28,
`
`
`US 5659779 A (R.T.LAIRD ET AL), 19 August 1997
`(19.08.97), column 3,
`
`Form PCT/ISA/210 (continuation of second sheet) (July 1998)
`
`Silver Star Exhibit 1002 - 522
`Silver Star Exhibit 1002 - 522
`
`

`

`INTERNATIONAL SEARCH REPORT
`
`International application No
`
`
`PCT/SE 02/00471
`
`
`
`
`Patent document
`cited in search report
`
`19804195 “
`WO
`9940496
`
`
`59900221 D
`DE
`
`
`1053516 A,B
`EP
`
`
`1053516 T3
`SE
`JP
`2002502997 T
`29/01/02
`
`
`US
`6240342 B
`29/05/01
`
`
`
` 4674048
`16/06/87
`T
`15/07/89
`CA
`1217836 A
`07/02/87
`DE
`3478824 D
`00/00/00
`
`
`EP
`0142594 A,B
`29/05/85
`
`
`SE
`0142594 T3
`25/05/85
`JP
`60093522 A
`
`
`11/11/92
`JP
`1708982 C
`
`
`JP
`3079723 B
`19/12/91
`
`
`JP
`60093524 A
`25/05/85
`
`esce ee nes oes ems se eea meA SE SEne ee ey Sy eed Sa a SESS SDAD StSs pSFS ED SO ESSH tS) A OY fd SS) SSGY SAOSSA SD
`
` 69124587 D,T
`11/09/97
`EP
`0490736 A,B
`17/06/92
`
`
`JP
`4333902 A
`20/11/92
`
`
`- KR
`9300081 B
`08/01/93
`
`9605628 Y 10/07/96
`
`ae ae me see OU RS Gs Set ST PD NS SE SD SNE SERS OEON SoD Re SaveAD SS Am GERD SED eySG ed res Det Sy SR SD SS GS SPSS SS GSSS SS SS SY SS PS PO SS SOD SS NSOS
`
`
`
`Publication
`date
`
`12/08/99
`
`A
`
`
`Patent family
`member(s)
`
`Publication
`date
`
`"05/08/99
`00/00/00
`22/11/00 ©
`
`ee i re rm rraaaeet ee ne ere reme mees ereat esa sy ear ke et me eh Sms se isa fe ee emee ee He Se
`
`
`Form PCT/ISA/210 (patent family annex) (July 1998)
`
`Silver Star Exhibit 1002 - 523
`Silver Star Exhibit 1002 - 523
`
`

`

`(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY(PCT)
`
`(19) World Intellectual Property Organization
`International Burcau
`
`(43) International Publication Date
`15 May 2003 (15.05.2003)
`
`
`
`IU GRANENAAA
`
`(10) International Publication Number
`WO 03/040845 Al
`
`(31)
`
`(21)
`
`(22)
`
`International Patent Classification’:
`
`GO5D 1/02
`
`Iuternational Application Number:
`
`PCT/GB02/04919
`
`International Filing Date: 31 October 2002 (31.10.2002)
`
`(25)
`
`Filing Language:
`
`Publication Language:
`
`English
`
`English
`
`(26)
`
`(30)
`
`(71)
`
`(72)
`(75)
`
`AUGUCMEAAAEAAA
`WO03/040845Al
`
`(74)
`
`(81)
`
`Agents: CAGE,John, D. et al.; Intellectual Property De-
`partment, Dyson Limited, Tetbury Hill, Malmesbury, Wilt-
`shire SN16 ORP (GB).
`
`Designated States (national): AE, AG, AL, AM, AT, AU,
`AZ, BA, BB, BG,BR, BY, BZ, CA, CH, CN, CO, CR, CU,
`CZ, DE, DK, DM, DZ, EC, EE, ES, FI, GB, GD, GE, GH,
`GM, HR, HU, ID,IL, IN,IS, JP, KE, KG, KP, KR, KZ, LC,
`LK, LR, LS, LT, LU, LV, MA, MD, MG, MK, MN, MW,
`Mx, MZ, NO, NZ, OM,PH, PL, PT, RO, RU, SD, SE, SG,
`SI, SK, SL, ‘TS, 1M, TN, TR, TT, TZ, UA, UG, US, UZ,
`VC, VN, YU, ZA, 7M, Z7.W.
`
`Designated States (regional): ARIPO patent (GH, GM,
`KE, LS, MW, MZ, SD, SL, SZ, TZ, UG, ZM, ZW),
`Eurasian patent (AM, AZ, BY, KG, KZ, MD, RU, TJ, TM),
`European patent (AT, BE, BG, CH, CY, CZ, DE, DK, EE,
`ES, FI, FR, GB, GR, IE, IT, LU, MC, NL, PT, SE, SK,
`TR), OAPI patent (BF, BJ, CF, CG, CI, CM, GA, GN, GQ,
`GW,ML, MR,NE, SN, TD, TG).
`
`Published:
`
`with international search report
`
`Priority Data:
`0126497.7
`
`3 November 2001 (03.11.2001)
`
`GB
`
`Applicant (for all designated States except US): DYSON
`LTD [GB/GB]; Tetbury Hill, Malmesbury, Wiltshire SN16
`ORP (GB).
`
`(84)
`
`Inventors; and
`Inventors/Applicants (for US only): ALDRED,Michael,
`David [GB/GB}; 16 Sutherland Cresent, Cepen Park North,
`Chippenham, Wiltshire SN14 6RS (GB). SHARDLOW,
`Andrew, Michael [GB/GB]; 4 Castlewood Cottages, High-
`walls Road, Dinas Powys, South Glamorgan CF64 4AN
`(GB).
`
`[Continued on next page]
`
`
`(54) Titles AN AUTONOMOUS MACHINE
`
`
`
`(57) Abstract: An autonomous machine explores the area in which it is located, constructing 4 mapofthe area based on information
`collected by the machine as the machine explores the area. The machine determines whenit has returned to a previously visited
`position within the area. The mapis corrected when the machine returns to the previously visited position, based on the knowledge
`that the current position andthe previously visited position are the same.
`
`Silver Star Exhibit 1002 - 524
`Silver Star Exhibit 1002 - 524
`
`

`

`WO 03/040845 AA
`
`___IDMIUNNCNIRIINI ANDCAIAEACAMCM
`
`For two-letter codes and other abbreviations, refer to the "Guid-
`ance Notes on Codes and Abbreviations" appearing at the begin-
`ning ofeach regular issue ofthe PCT Gazette.
`
`Silver Star Exhibit 1002 - 525
`Silver Star Exhibit 1002 - 525
`
`

`

`WO 03/040845
`
`PCT/GB02/04919
`
`An Autonomous Machine
`
`This invention relates to an autonomous machine, such as an autonomous machine for
`
`cleaning a floor area.
`
`There have been various proposals to provide autonomous or robotic machines for
`performing duties such as cleaning or polishing a floor area or for mowing grass.
`In their
`simplest form, an autonomous machinerequires a training phase during whichthe machine
`is manually led around the area in which it is to work. Following this training phase, the
`autonomous machine will then perform the required work asit follows the path whichit
`stored in its memory during the training phase. Other machines may simply follow a
`predetermined route which is marked by meanssuch as a cable which is buried beneath the
`
`10
`
`working area.
`
`15
`
`Other autonomous machines are supplied with a map of the environmentin which they are
`to be used. The machine then uses this map to plan a route around the environment.
`
`20
`
`There have also been proposals for autonomous machines which are capable of exploring
`the environment in which they are placed without human supervision, and without advance
`knowledge of the layout of the environment. The machine may explore the environment
`during a learning phase and will subsequently use this information during a working phase.
`An autonomous machine shown in WO 00/38025initially travels around the perimeterof
`an area, recognises when it has completedasingle lap of the area, and then steps inwardly
`after that and subsequent laps of the room so as to cover the area in a spiral-like pattern.
`Autonomous machines are known to build a map of the working area using the
`information they acquire during the learning phase. Autonomous machines of this last
`type are particularly attractive to users as they can beleft to work with minimal human
`
`supervision.
`
`30
`
`Autonomous machines usually have some form of odometry system for measuring the
`distance and direction travelled by the machine. Distance and direction information can be
`derived from sensors which monitor movement of each of the wheels. The machine uses
`
`Silver Star Exhibit 1002 - 526
`Silver Star Exhibit 1002 - 526
`
`

`

`WO 03/040845
`
`PCT/GB02/04919
`
`2
`
`the odometry information to deduce howfar it has travelled since a starting position in the
`working area, and thus where it currently is located within the area. Unfortunately,
`relying on odometry information alone is unreliable as errors can quickly accumulate,
`and this can eventually lead to a complete disorientation of the machine. For example,if
`one of the drive wheels of the machineslips on the floor surface the odometry system will
`
`record a movement, since the wheel has turned, whereas, due to the wheel slippage, the
`
`machine does not actually move across the surface. Poor odometry informationresults in a
`difference between the calculated position of the machine and the actual position of the
`machine. In a floor cleaning machinethis could result in the machine not travelling across
`
`10
`
`some areas of the floor surface, which would remain dirty, or the machine becominglost.
`
`Odometry information can be supplemented,or replaced entirely, by other information. A
`
`paper entitled “Gyrodometry: A New Method for Combining Data from Gyros and
`
`Odometry in Mobile Robots” presented at the 1996 IEEE International Conference on
`
`15
`
`Robotics and Automation, Minneapolis, Apr 22-28, 1996, pp. 423-428, describes a
`
`proposal for reducing the problems of odometry-based robots in which the odometry data
`
`is substituted by gyro data during the short periods when odometry data is unreliable.
`
`Some systems position navigation beacons around an area such that the machine can
`
`calculate its position by a process of triangulating information received from a numberof
`
`20
`
`beacons. However,
`
`this has the obvious disadvantage of requiring beacons to be
`
`positioned around each area where the machine will work, and the associated cost of these
`
`beacons. US 6,255,793 describes a system of this type where the boundary of the working
`area is defined by markers. One of the ways in which the calculated location of the
`
`autonomous machine can be corrected is by detecting the presence of markers which each
`have a unique identity.
`
`25
`
`The present invention seeks to provide an improved autonomous machine.
`
`Silver Star Exhibit 1002 - 527
`Silver Star Exhibit 1002 - 527
`
`

`

`WO 03/040845
`
`PCT/GB02/04919
`
`A first aspect of the present invention provides an autonomous machine comprising:
`
`- driving means for moving the machine along a surface, and
`- a navigation system, including a memory means, for navigating the cleaning
`machine around an area,
`
`the navigation system comprising:
`
`means for causing the machine to explore the area in which it is located, constructing a
`
`map of the area based on information collected by the machine as the machine explores the
`
`10
`
`area,
`
`means for determining when the machine has returned to a previously visited position
`within the area,
`
`meansfor correcting the map when the machinereturnsto the previously visited position,
`
`based on the knowledgethat the current position and the previously visited position are the
`same.
`
`This allows the machine to create a map which is an accurate representation of the area,
`
`even where the machine may suffer from errors in gathering information to construct the
`map, such as the errors which accumulate when relying on odometry information.
`
`15
`
`20
`
`Preferably, the exploring meansis arranged to cause the machine to follow a boundary of
`
`the area, storing path information on the path travelled by the machine as the machine
`
`follows the boundary; and the determining means is arranged to determine when the
`
`machine has returned to a previously visited position in the area by comparing the latest
`
`25
`
`section of the path travelled by the machine with information representing a section of the
`
`path previously stored in the memory, and for deciding when the new path information and
`
`previously stored path information are substantially the same.
`
`The boundary can take many forms.
`
`In a room of a building, the boundary will be the
`
`30
`
`walls of the room and the boundaries of objects placed within the room such as items of
`
`furniture. In an outdoor area, the boundary maybe a pre-existing barrier such as a fence
`
`Silver Star Exhibit 1002 - 528
`Silver Star Exhibit 1002 - 528
`
`

`

`WO 03/040845
`
`PCT/GB02/04919
`
`4
`
`or wall or it may be any form of barrier which is positioned especially for use with the
`
`autonomous machine.
`
`As an alternative to using path data to recognise when the machine has returned to a
`previously visited position,
`the machine can use feature-based information which is
`collected by sensors on the machine. The feature-based information can be light-based
`
`information such as the amplitude, direction and/or colour of light at positions within the
`
`room, magnetic measurements or distance measurements. Alternatively,
`
`the machine
`
`could recognise somekind of markerat a position in the area.
`
`10
`
`The navigation system can be implementedentirely in hardware, in software running on a
`processor, or a combination of these. Accordingly, a further aspect of the present
`
`invention provides software for operating the cleaning machine in the manner described
`
`herein. The software is conveniently stored on a machine-readable medium such as a
`
`15
`
`memory device.
`
`The autonomous machine can take many forms: it can be a robotic vacuum cleaner, floor
`
`polisher,
`
`lawn mower or a robotic machine which performs some other function.
`
`Alternatively, it could be a general purpose robotic vehicle which is capable of carrying or
`
`20
`
`towing a work implement chosen by a user.
`
`Embodiments of the present invention will now be described, by way of example only,
`
`with reference to the accompanying drawings, in which:-
`
`25
`
`Figure i shows an embodiment of an autonomous machine according to the
`
`invention;
`
`Figure 2 showsthe electrical systems in the machineof Figure 1;
`
`Figure 3 showsthe overall set of machine behaviours;
`
`Figure 4 shows the method for navigating the machine around the boundary ofa
`
`30
`
`working area;
`
`Figures 5 and 6 show the machine operating in an example room scenario,
`
`Figure 7 showsthe process for matching path sections;
`
`Silver Star Exhibit 1002 - 529
`Silver Star Exhibit 1002 - 529
`
`

`

`WO 03/040845
`
`PCT/GB02/04919
`
`5
`
`Figure 8 shows the machine-generated map of the working area following an
`
`initial traverse of the boundary of the working area;
`
`Figure 9 showsthe map correction process;
`
`Figure 10 showsthe coordinate system used in the map correction process;
`
`Figure 11 shows the method for scanning the working area;
`
`Figure 12 showsa reciprocating scanning movement;
`
`Figure 13 shows the mapof a room andfree space areas;
`
`Figure 14 showsoneofthe selected free space are