wo 02/075470
`
`PCT/SE02/00471
`
`21
`
`CLAIlVIS
`
`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;
`
`5
`
`-
`
`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
`
`10
`
`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
`
`15
`
`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 adj acentto the current
`
`20
`
`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
`
`25
`
`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;
`
`Silver Star Exhibit 1002 - 501
`Silver Star Exhibit 1002 - 501
`
`

`

`W0 02/075470
`
`PCT/SE02/00471
`
`22
`
`—
`
`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 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 moving thereto, 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 move from cell to cell in
`
`10
`
`'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,
`
`15
`
`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 ofthe 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
`
`20
`
`25
`
`30
`
`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.
`
`7.
`
`The method according to claim 5 or 6,
`
`characterized by assigning to each cost-allocated cell a direction indicator to enable
`
`5
`
`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,
`10 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.
`
`15
`
`1 1 .
`
`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,
`
`20
`
`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
`
`25
`
`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,
`
`30
`
`characterized by computing means adapted to perform the following operations:
`
`Silver Star Exhibit 1002 - 503
`Silver Star Exhibit 1002 - 503
`
`

`

`W0 02/075470
`
`'
`
`PCT/SE02/00471
`
`24
`
`-
`
`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;
`
`5
`
`-—
`
`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
`
`10
`
`i
`
`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,
`
`15
`
`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 function depends both on the distance from the
`
`current cell to an obstacle—free and untreated cell as well as the total change of
`
`20
`
`direction required for moving thereto, a larger change ofdirection 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.
`
`25
`
`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,
`
`30
`
`characterized in that said means for determining a navigation route that requires the
`
`Silver Star Exhibit 1002 - 504
`Silver Star Exhibit 1002 - 504
`
`

`

`W0 02/075470
`
`PCT/SE02/0047l
`
`25
`
`smallest amount ofenergy according to apredetermined 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.
`
`10
`
`'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 ofthe 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,
`
`15
`
`2O
`
`characterized in that the size ofthe 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
`
`30
`
`performing floor treatment such as vacuum cleaning, sweeping, brushing or polishing
`
`Silver Star Exhibit 1002 - 505
`Silver Star Exhibit 1002 - 505
`
`

`

`W0 02/075470
`
`PCT/SE02/0047l
`
`"'R‘
`
`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 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:
`
`H
`
`—
`
`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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`Silver Star Exhibit 1002 - 506
`Silver Star Exhibit 1002 - 506
`
`

`

`W0 02/075470
`
`PCT/SE02/00471
`
`27
`
`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
`
`10
`
`15
`
`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.
`
`Silver Star Exhibit 1002 - 507
`Silver Star Exhibit 1002 - 507
`
`

`

`W0 02/075470
`
`PCT/SE02/00471
`
`1/13
`
`
`
`Silver Star Exhibit 1002 - 508
`Silver Star Exhibit 1002 - 508
`
`

`

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

`

`W0 02/075470
`
`PCT/SE02/00471
`
`3/13
`
`CLK
`
`‘ TRANSMITTER '
`
`_ QENC
`
`L—BUMPER
`'
`
`I
`
`_.L-
`
`R-BUMPER
`TILT
`J___\__ SW'TCHES
`
`F DRIVER
`M MOTOR
`
`
`R—WHEEL
`
`L-WHEEL
`L—WHEEL
`MOTOR
`MOTOR
`
`R-WHEEL
`
`MOTOR
`
`DRIVER
`CPU
`INPUT
`COMMANDS _ QENC
`
`SENSOR
`
`R-HALL
`SENSOR
`
`FPROM
`512X8
`
`RAM
`512x16
`
`EZPROM
`256x16
`
`PWM
`
`BRUSH
`
`
`BRUSH
`m -
`DRIVER
`MOTOR
`DRIVER
`
`FAN
`MOTOR
`
`FAN
`MOTOR
`
`MC68332
`
`RECEIVER
`
`1‘ AID
`_
`
`. = W"
`
`AID
`INPUT
`
`MUX
`INPUT
`
`Fig. 4
`
`Silver Star Exhibit 1002 - 510
`Silver Star Exhibit 1002 - 510
`
`

`

`W0 02/075470
`
`PCT/SE02/00471
`
`
`
`
`fififififi
`fiafifia
`Eaaaa
`magafi
`
` afifififi
`
`Silver Star Exhibit 1002 - 511
`Silver Star Exhibit 1002 - 511
`
`

`

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

`

`W0 02/075470
`
`PCT/SE02/0047l
`
`fififififi
`Eafiafi
`aafiaa
`
`
`
` mafiafi
`
`fiaaafi
`
`Silver Star Exhibit 1002 - 513
`Silver Star Exhibit 1002 - 513
`
`

`

`W0 02/075470
`
`PCT/SE02/00471
`
`7/13
`
`[fly/Q%
`
`Fig. 10
`
`Fig. 11A
`
`Fig. 113
`
`Silver Star Exhibit 1002 - 514
`Silver Star Exhibit 1002 - 514
`
`
`
`
`

`

`W0 02/075470
`
`PCT/SE02/0047l
`
`8/13
`
`
`
`Fig. 11E
`
`Silver Star Exhibit 1002 - 515
`Silver Star Exhibit 1002 - 515
`
`

`

`W0 02/075470
`
`PCT/SE02/00471
`
`9/13
`
`
`
`Fig. 116
`
`Fig. 11H
`
`Silver Star Exhibit 1002 - 516
`Silver Star Exhibit 1002 - 516
`
`
`

`

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

`

`W0 02/075470
`
`PCT/SE02/0047]
`
`11/13
`
`
`
`Fig. 11M
`
`Fig. 11N
`
`Silver Star Exhibit 1002 - 518
`Silver Star Exhibit 1002 - 518
`
`
`

`

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

`

`W0 02/075470
`
`PCT/SE02/00471
`
`13/13
`
`
`
`GWNmmmmCSr
`
`Fig. 12
`
`Silver Star Exhibit 1002 - 520
`Silver Star Exhibit 1002 - 520
`
`
`

`

`A. CLASSIFICATION OF SUBJECF MATTER
`
`International application No.
`
`PCT/SE 02/00471
`
`IP87: 605D 1/02
`According to International Patent Classification (IPC) or to both national classification and IPC
`B. FIELDS SEARCHED
`.
`
`Minimum documentation searched (classification system followed by classification symbols)
`
`.
`
`IPC7: BZ5J, 605D
`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
`
`c. DOCUMENTS CONSIDERED TO BE RELEVANT
`
`Citation of document. with indication, where appropriate, of the relevant passages
`
`Relevant to claim No.
`
`NO 9940496 A (SIEMENS AKTIENGESELLSCHAFT),
`12 August 1999 (12.08.99), page 2,
`line 29 - line 36, abstract
`
`US 4674048 A (K.0KUMURA), 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,
`
`[E Further documents are listed in the continuation of Box C.
`Special categories of Cited documents
`document defining the general state of the art which is not conn'dered
`to be of particular relevance
`earlier application or patent but published on or alter the international
`filing date
`.
`.
`.
`.
`’
`.
`document which may throw doubts on priority claIm(s) or which rs
`Cited to establish the publication date of another citation or other
`special reason (as specified)
`.
`.
`.
`.
`(1
`.
`11:25:th rcfcrnng to an oral disclosure, “5“ exluhttron or other
`.
`.
`.
`.
`_
`down-tent published prior to the International filing date but later than
`the priority date claimed
`Date of the actual completion of the international search
`
`”T”
`
`a
`
`.
`[3 See patent family annex.
`later document published after the international filing date or priority
`date and not in conflict with the applicationlbut cited to understand
`the principle or theory under]yrng the Invmtron
`”X” document of particular relevance: the claimed invention cannot be
`considered novel or cannot be cmndered to involve an inventive
`step when the document is taken alone
`.
`_
`”Y" document of particular relevance: the claimed invention cannot be
`considered to involve an inventive St when the document is .
`.
`combined With one or more other su
`documents, such combination
`hein obvious to a arson skilled ‘n the art
`g
`p
`l
`.
`&” document member of the same patent family
`Date of mailing of the international search report
`Ffi‘Tf-ill-
`2mm
`
`
`
`6 June 2002
`Name and mailing address of the ISA/
`Swedish Patent Office
`
`Authorized officer
`
`Box 5055, 8-102 42 STOCKHOLM
`Facsimile No. +46 8 666 02 86
`Form PC'I‘IISAJZlO (second sheet) (July 1998)
`
`Garan Magnusson litw
`Telephone No.
`+46 8 782 25 00
`
`Silver Star Exhibit 1002 - 521
`Silver Star Exhibit 1002 - 521
`
`

`

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

`

`INTERNATIONAL SEARCH REPORT
`
`Immmnal ”PM” N°'
`PCT/SE 02/00471
`
`9940496
`
`A
`
`12/08/99
`
`4674048
`
`16/06/87
`
`19804195 A
`59900221 D
`1053516
`1053516
`2002502997
`6240342
`
`7 05/08/99
`00/00/00
`22/11/00.
`,
`29/01/02
`29/05/01
`
`15/07/89
`07/02/87
`00/00/00
`29/05/85
`
`_——————————___————————-_———-—_..——___——____—-——_——_____—__——_____———___——_
`
`1217836
`3478824
`0142594
`0142594
`25/05/85
`60093522
`11/11/92
`1708982
`19/12/91
`3079723
`25/05/85
`60093524
`—_—-——_—___—————————__———.—_..—___—————-—.—_._...._.__—__—___—_———————————————_—
`
`69124587
`0490736
`4333902
`9300081
`9605628
`
`11/09/97
`17/06/92
`20/11/92
`08/01/93
`10/07/96
`
`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)
`
`(l9) World Intellectual Property Organization
`Intemational Bureau
`
`(43) International Publication Date
`
`15 May 2003 (15.05.2003) |lllllIllllllllllllllllllllllll|||Illllllllllllllllllllll|||||||||lllllllllllllllllll
`
`(l0) International Publication Number
`W0 03/040845 A1
`
`(51) International Patent Classifieation7:
`
`005D [/02
`
`(21) International Application Number:
`
`PC’l‘IGBOPJO4919
`
`(22) International Filing Date: 31 October 2002 (31.10.2002)
`,
`.
`,
`(25) “mg La“g“age‘
`“"31““
`(26) Publication Language:
`English
`
`(30) Priority Data;
`0126497]
`
`3 November 2001 (03.11.2001)
`
`GB
`
`(71)' Applicant (for all designated States except US): DYSON
`LTD [GB/GB]; 'I‘etbury Hill, Malmesbury, Wiltshire SN16
`ORP (GB).
`
`(74) Agents: CAGE, John, D. et al.; Intellectual Property De-
`partment, Dyson Limited, Tetbury Hill, Malmesbury, Wilt-
`shire SN16 ORP (GB).
`
`(81) Designated States (national): AE, AG, AL, AM, AT, AU,
`AZ, BA, BB, BG, BR, BY, BZ, CA, CH, CN, (:0, 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, 313, SE, SG,
`SI, SK, SL, TJ. TM, TN. TR, ’11: ’12, UA, UG. U8, UZ,
`VC, VN, YU, ZA, ZM, ZW.
`
`'
`(72) InventorS; and
`(75) Inventors/Applicants (for US only): ALDRED, Michael,
`David [GB/GB]; 16 Sutherland Cresent, Cepen Park North,
`Chippenham, Wiltshire SN14 6R8 (GB). SHARDLOW,
`Andrew, Michael [GB/GB]; 4 Castlewood Cottages, High-
`walls Road, Dinas Powys, South Glamorgan CF64 4AN Published:
`(GB).
`with international search report
`
`(84) 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, 'l'J, TM),
`European patent (AT, BE, BG, CH, CY, CZ, DE, DK, BE,
`ES, 171, FR, GB, GR, IE, IT, LU, MC, NL, 171‘, SE, SK,
`TR), OAPI patent (BF, BJ, CF, CG, (:1, CM, GA, GN, GQ,
`0W, ML, MR, NE, SN, TD, TG).
`
`[Continued on next page]
`
`
`(54) Title: AN AUTONOMOUS MACHINE
`
`
`
`(57) Abstract: An autonomous machine explores 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 area. The machine determines when it has returned to a previously visited
`position within the area. The map is corrected when the machine returns to the previously visited position, based on the knowledge
`that the current position and the previously visited position are the same.
`
`Silver Star Exhibit 1002 - 524
`Silver Star Exhibit 1002 - 524
`
`llllllllllllllllIllllllllllllllllllllllllllllll||||||lll||||l||||||||||||||||||||||||
`W003/040845A1
`
`

`

`W0 03/040845 A1
`
`|lllllIlllllllllllllllllllllllllll||l|||l|IIIIIIIIIIIIIIIIIIIIIIIIIllllllllllllllllll
`
`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
`
`

`

`W0 03/040845
`
`PCT/GBOZ/049l9
`
`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 machine requires a training phase during which the machine
`
`is manually led around the area in which it is to work. Following this training phase, the
`
`10
`
`autonomous machine will then perform the required work as it follows the path which it
`
`stored in its memory during the training phase. Other machines may simply follow a
`
`predetermined route which is marked by means such as a cable which is buried beneath the
`
`working area.
`
`15
`
`Other autonomous machines are supplied with a map of the environment in which they are
`
`to be used. The machine then uses this map to plan a route around the environment.
`
`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
`
`20
`
`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/38025 initially travels around the perimeter of
`
`an area, recognises when it has completed a single lap of the area, and then steps inwardly
`
`after that and subsequent laps of the room so as to cover the area in a spira1~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 be left 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/GBOZ/049l9
`
`2
`
`the odometry information to deduce how far 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 machine slips 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 information results in a
`
`difference between the calculated position of the machine and the actual position of the
`
`machine. In a floor cleaning machine this could result in the machine not travelling across
`
`some areas of the floor surface, which would remain dirty, or the machine becoming lost.
`
`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
`
`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 tn'angulating information received from a number of
`
`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
`
`10
`
`15
`
`20
`
`25
`
`have a unique identity.
`
`The present invention seeks to provide an improved autonomous machine.
`
`Silver Star Exhibit 1002 - 527
`Silver Star Exhibit 1002 - 527
`
`

`

`u
`
`W0 03/040845
`
`PCT/G802/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,
`
`means for correcting the map when the machine returns to the previously visited position,
`
`based on the knowledge that 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.
`
`Preferably, the exploring means is 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
`
`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
`
`walls of the room and the boundaries of objects placed within the room such as items of
`
`furniture. In an outdoor area, the boundary may be a pre—existing barrier such as a fence
`
`15
`
`20
`
`25
`
`30
`
`Silver Star Exhibit 1002 - 528
`Silver Star Exhibit 1002 - 528
`
`

`

`W0 03/040845
`
`PCT/G802/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 some kind of marker at a position in the area.
`
`10
`
`The navigation system can be implemented entirely 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
`
`invention;
`
`Figure 1 shows an embodiment of an autonomous machine according to the
`
`Figure 2 shows the electrical systems in the machine of Figure 1;
`
`Figure 3 shows the overall set of machine behaviours;
`
`Figure 4 shows the method for navigating the machine around the boundary of a
`
`30
`
`working area;
`
`Figures 5 and 6 show the machine operating in an example room scenario;
`
`Figure 7 shows the process for matching path sections;
`
`Silver Star Exhibit 1002 - 529
`Silver Star Exhibit 1002 - 529
`
`

`

`W0 03/040845
`
`PCT/GBOZ/049l9
`
`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 shows the map correction process;
`
`Figure 10 shows the coordinate system used in the map correction process;
`
`Figure 11 shows the method for scanning the working area;
`
`0
`
`Figure 12 shows a reciprocating scanning movement;
`
`Figure 13 shows the map of a room and free Space areas;
`
`Figure 14 shows one of the selected free space areas of the room;
`
`Figure 15 shows types of free space areas which may exist within the room;
`
`10
`
`Figure 16 shows a way of reaching scanning start points;
`
`Figure 17 shows a way of coping with centrally positioned