W0 03/040845
`
`PCT/GB02/049l9
`
`14
`
`alternative criterion is for the system to choose the closest boundary section to the
`
`machine’s current position which has free space located adjacent to it. Boundary sections
`
`with free space adjacent to them are located at 610, 612, 614. Having found the longest
`
`boundary with free space (section 610),
`the navigation system attempts to find the
`dominant edge orientation of this part of the area (step 520). In performing a reciprocating
`
`pattern, the machine is particularly prone to accumulating odometry errors at the places
`
`where it turns through 180 degrees. Thus, it is preferred to traverse an area in a manner
`
`which minimises the number of turns. We have found that the dominant edge orientation
`
`of an area has been found to be the best direction to traverse an area.
`
`There are various ways in which the dominant edge orientation can be found. One way is
`
`to plot the direction (as an absolute angle) of each segment of the selected path section 610
`
`on a histogram. One axis of the chart represents the absolute angle of the paths and the
`
`other axis represents the accumulated length of path segments at a particular angle. For a
`
`complicated path this could result in a lot of computation. The computation can be
`
`simplified by only recording a segment of the path as a different angle when its angular
`
`direction differs from an earlier part of the path by more than a particular angular range,
`
`e.g. ten degrees.
`
`If this simplification is followed, the plot at each angular value can be
`
`represented by a distribution curve. Segments which are separated by 180 degrees can be
`
`plotted at the same angular value on the bar chart since they are parallel to one another.
`
`This bar chart can be readily processed to derive the dominant direction of the area.
`
`Having identified the dominant direction, the navigation system isolates the area of the
`
`map in which the selected boundary path section lies, as shown in Figure 14. The
`
`navigation system rotates the isolated part of the area until it is aligned in the dominant
`
`direction and then finds the extremities of this part of the area. The navigation system then
`
`selects one of the extremities as a start point for the scan.
`
`A further analysis is made of the selected part of the room area. This determines whether
`
`the free space is located inside or outside the boundary. Figure 15 shows two types of area
`
`which can be encountered. An internal free space area is enclosed by the boundary section
`
`whereas an external area free space area surrounds the boundary section. The navigation
`
`10
`
`15
`
`20
`
`25
`
`30
`
`539
`
`539
`
`

`

`wo 03/040845
`
`PCT/GBoz/04919
`
`15
`
`system can determine the type of free space area by summing the angular change between
`
`each segment of the boundary section. An angular change sum of 360 degrees indicates an
`
`internal area whereas an angular sum of -360 degrees represents an external area.
`
`There are some heuristics in selecting the start point. If the end points 620, 630 of a scan
`
`area are spaced apart from one another. on the map by more than a predetermined distance
`
`then they are considered to represent an open area.
`
`If the free space area is an internal
`
`area, the navigation system will try not to choose one of these end points as a start point as
`
`this will tend to cause the machine to scan towards the boundary in a direction which is
`
`possibly away from other free space that could be cleaned. The navigation system
`attempts to select a start point located elsewhere on the boundary, i.e. bounded on both
`
`sides by other path segments of the selected path section. A start point of this type has
`
`been found to cause the machine to scan inwards into the area rather than outwards. When
`
`the machine scans inwards it can often clean other free space areas after the isolated area
`
`has been cleaned, which can reduce the overall number of separate scanning operations
`
`that are required to cover the room area. Also, if there is a choice of start point, the nearer
`
`start point to the current position of the machine is chosen, providing the machine is able to
`
`localise (reset odometry errors) before reaching the start point.
`
`As shown in Figure 16, once a start point on the map has been selected, an L meter section
`
`of the boundary path data preceding the desired scan start point is extracted from the
`
`memory (step 530).
`
`If necessary, the machine then selects a point further back along the
`
`boundary from the start of the extracted section and marks this as a target point. The
`machine then attempts to find a path across the room to this target point from its current
`
`location. It does this by searching the room map for places that it has previously visited it
`
`then plots a path over these spaces to the target point on the boundary. It then moves to the
`
`target point and follows the boundary until it matches the trajectory section for the start of
`
`the next cleaning scan. Matching of this segment of the boundary path data is carried out
`
`in the same way as that of matching to find the start position.
`
`If it fails to find a route to the target point (step 545), either because the route was too risky
`
`or because it encountered an object on the way, then it moves onto the boundary. It moves
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`540
`
`540
`
`

`

`wo 03/040845
`
`PCT/GBtIZ/04919
`
`16
`
`round the boundary until it reaches one of the better free space points and starts a scan
`
`from there.
`
`Once the machine reaches the scan start point it orients to the chosen scan direction (the
`
`dominant direction identified earlier) and proceeds to scan in a reciprocating manner into
`
`the uncleaned space (step 550). While the machine is moving in a straight line it is
`
`constantly checking to see if it has already visited the space it is on. Once it sees that it has
`
`run over a previously visited space by its own length then it stops and carries out a step
`
`across. Since this step across is in open space it is a single segment step across. This
`
`cleaning scan continues until either it is blocked or there have been a small number of
`short traverses or the whole of the previous traverse was on space that had been visited
`
`previously. During the scanning process, the navigation system records the travelled path
`
`on the map, such that the machine knows which positions of the map have been cleaned,
`
`and also continues to record the distance to the nearest obstacle seen by the machine’s
`
`sensors on the map. After each scanning operation the machine processes the distance
`information recorded on the map, taking account of the areas already cleaned by the
`machine, to calculate a free space vector.‘ The free space vectors are plotted on the map
`
`and can then be used by the navigation system to decide the next area where scanning
`
`should occur.
`
`A period of reciprocating scanning will induce odometry errors. Therefore, between each
`
`period of scanning, the machine looks for the boundary of the area and follows the
`
`boundary of the area (step 560). As the machine travels around the boundary of the area it
`
`stores the path travelled by the machine. The machine travels for a distance of at least the
`
`minimum distance necessary for finding a match, i.e. L metres. The matching process
`
`attempts to match the new block of boundary path data with the boundary path data that
`
`was originally stored in the memory.
`
`If a block of path data matches positively then the
`
`machine knows it has returned to as known position on the map and can thus rest the
`
`10
`
`15
`
`20
`
`25
`
`odometry error to zero.
`
`If the matching process fails to find a good match then the
`
`3O
`
`machine will continue on the boundary until it should have reached one of the marker
`
`positions. If this also fails then it assumes that it is on a central object.
`
`541
`
`541
`
`

`

`W0 03/040845
`
`PCT/GBOZ/(l49l9
`
`17
`
`If the machine correctly recognised a position on the boundary then it realigns the just
`
`completed traverse scan and the boundary section onto the free space map, based on the
`
`measured error between the machine’s perceived position on the map and the actual
`position on the map. The navigation system then finds the next largest uncleaned part of
`
`the area (step 505).
`
`The machine then repeats the search for freespace and the moves to them until all the space
`
`that can be identified on the map has been completed (steps 510, 515).
`
`10
`
`During the matching process, in addition to looking for a strong match between blocks
`of data, the matching process also makes a number of safety checks.
`It makes sure that
`
`the orientation of the matching section is roughly the same as the extracted section and
`
`that they both roughly lie in the same part of the internal map. The odometry error
`
`gradually increases with distance travelled. The matching process sets an event horizon,
`
`15
`
`i.e. a boundary for possible positions on the map where, due to odometry error, a match
`
`may occur. Any matches which correspond to positions in the room which are not, due
`
`to the size of the odometry error, possible positions for the machine are discounted.
`
`Central Objects
`
`A complex area is likely to include obstacles which are located away from the boundary of
`
`the area, such as a coffee table. Figure 17 shows a strategy for coping with central objects.
`
`The machine performs a scanning operation 750 and eventually reaches a point at 760
`
`where it can no longer continue the scanning movement. The machine then proceeds to
`follow the edge of the object 785, cleaning around the edge of the object. After travelling
`a distance of L metres around the object 785 the machine will attempt to match the last L
`
`metre path section with the path recorded around the boundary of the room. This should
`
`fail to give a suitable match. Thus, the machine recognises that it is following the edge of
`
`an object. The machine jumps off of the object at position 780, on the remote side of the
`
`object in the direction of the scan, and follows the boundary of the room 790 until it can
`
`30
`
`match the travelled path with the previously stored boundary path data. At this point the
`
`navigation system can reset any odometry error and accurately place the position of the
`
`542
`
`542
`
`

`

`W0 03/040845
`
`PCT/GB02I04919
`
`18
`
`object 785. Note, in following the edge of a central object, the machine may travel around
`the object several times until it has travelled a distance of L metres.
`
`Scanning behaviours
`Figures 18-20 show some of the ways in which the machine operates during a scanning
`operation. As previously described with reference to Figure 12, the scanning operation
`comprises a series of parallel straight line paths which are offset from one another by a
`distance W, which will usually be equal to the width of the cleaning head of the
`
`10
`
`machine. However, irregular boundary shapes do not always permit the machine to
`follow a regular scanning pattern. Figure 18 shows a segmented step across where the
`machine follows the boundary 800 of the room in segments 804, 806 until it has
`
`travelled the total required step across distance W. At each step the machine rotates
`
`until it sees a clear path ahead and travels forward until it needs to turn. The step across
`
`distance W can be determined from trigonometry of the travelled paths 804, 806. A
`
`15
`
`complex step across movement may comprise more segments than are shown here.
`This movement allows the machine to properly cover the floor surface and to continue
`
`the scanning movement at the regular width W.
`
`20
`
`Figures 19 and 20 show other situations where the boundary prevents the machine from
`performing a regular step across movement.
`In Figure 19 the machine reaches the end
`of movement 810 and follows the wall along path 812 until it can step across at 813 to
`
`the proper scan separation distance W. Figure 20 shows a similar scenario where the
`machine must travel back on itself along path 822 until it can travel across along path
`
`823 and continue the scanning movement at the regular width W.
`
`In these movements
`
`25
`
`the machine monitors, during path 810, 820 the distance on its right hand side to the
`
`wall/obstacles to determine whether the machine will be able to step across to continue
`
`its scanning movement.
`
`Markers
`
`30
`
`Markers are L metre sections of path data which can be used at various times by the
`
`navigation system to quickly determine the current position on the boundary. They are
`particularly useful in allowing the machine to cope with the kinds of errors that can
`
`543
`
`543
`
`

`

`wo 03/040845
`
`PCT/GBOZ/04919
`
`19
`
`occur when the machine is forced to folow a different path around the boundary, e. g.
`
`because something has been moved. If the machine is travelling around the boundary
`
`looking for a particular L metre section of the path but fails to find it, it will usually find
`
`the marker positioned after that particular section of required boundary and thus allow
`
`the machine to quickly recognise the error. Markers are also useful when the machine
`
`attempts to travel across a room area to reach a start point for a scan but misses it for
`
`some reason. This may occur if the machine does not properly reach the target point
`
`before the L metre section of boundary preceding the start point (see Figure 16). Should
`
`the machine not find the start point, it follows the boundary of the area and should find
`
`the next marker on the boundary. Upon finding the marker the machine can recognise
`
`its error and try again.
`
`Alternatives
`
`The described method of recognising a previously visited position in an area by
`
`matching travelled path sections is dependent on several factors. Firstly, the navigation
`
`system should be able to cause the machine to travel in a closely similar manner when
`
`negotiating the same boundary on different occasions. The value of the ‘quality of
`
`match’ threshold and the process of sub—sampling path data so that the matching process
`
`considers the underlying path rather than the detailed path does allow for some variation
`
`between travelled paths while still allowing a successful match. Secondly, the matching
`
`process is dependent on the L metre path that is used during the matching process being
`
`In rooms that possess one or more lines of symmetry,
`unique to a position in the room.
`it is possible for the L metre path to be common to two or more positions within the
`
`room. Obviously, a truly rectangular room with no other obstacles on the boundary
`
`would cause a problem. The system can be made more robust in several ways.
`
`Firstly, the length of the path used in the matching process can be increased until it does
`
`represent a unique position in the room. This can be performed automatically as part of
`
`the navigation method. Should the machine travel for more than a predetermined time
`
`period without finding a match, the navigation system can automatically increase the
`
`length of the matching window.
`
`10
`
`15
`
`25
`
`30
`
`544
`
`544
`
`

`

`W0 03/040845
`
`PCT/G802/04919
`
`20
`
`Secondly, the path data can be supplemented by other information gathered by the
`
`machine during a traverse of the area. This additional information can be absolute
`
`direction information obtained from an on-board compass,
`
`information about
`
`the
`
`direction, intensity and/or colour of the light field around the machine obtained from on-
`
`board light detectors or information about the distance of near or far objects from the
`
`machine detected by on—board distance sensors.
`
`In each case,
`
`this additional
`
`information is recorded against positions on the travelled path.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`The map correction process described above applies a linear correction to the travelled
`
`path. In an alternative embodiment, the accumulated error can be divided among the set
`
`of Coordinates in a more complex manner. For example, if the machine is aware that
`
`wheel slippage occurred half way around the traverse of the room boundary, it can
`
`distribute more (or all) of the accumulated error to the last half of the path coordinates.
`
`The above method describes the machine following a clockwise path around an area. The
`
`machine may equally take an anti—clockwise path around the area during its initial lap of
`
`the boundary of the area. Also, in following the boundary to reach a start position for area
`
`scanning, the machine may follow the boundary in a clockwise or anti-clockwise direction.
`
`In performing the cleaning method, it is preferred that the cleaning machine steps across by
`
`substantially the width of the cleaner head on the cleaner so that the cleaning machine
`
`covers all of the floor surface in the minimum amount of time. However, the distance by
`
`which the cleaning machine steps inwardly or outwardly can have other values. For
`
`example, by stepping by only a fraction of the width of the cleaner head, such as'one half
`
`of the width, the cleaning machine overlaps with a previous traverse of the room which is
`
`desirable if a user requires a particularly thorough cleaning of the floor. The step distance
`
`can be chosen by the user. There are various ways in which the user can choose the step
`
`distance: the user can be presented with a plurality of buttons or a control that specifies the
`
`step distances, or controls having symbols or descriptions indicative of the effect of the
`
`cleaner operating at the step distances, such as “normal cleaning”, “thorough Cleaning”.
`
`The buttons can be incorporated in the user panel (140, Fig. 1), a remote control or both of
`these.
`
`545
`
`545
`
`

`

`W0 03/040845
`
`PCT/GBOZ/O-wl‘)
`
`21
`
`Claims
`
`1.
`
`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
`area,
`
`10
`
`means for determining when the machine has retumed to a previously visited position
`
`within the area,
`
`15
`
`20
`
`25
`
`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.
`
`2.
`
`An autonomous machine according to claim 1 wherein the correcting means
`
`distributes any error among the points on the map which has been constructed.
`
`3.
`
`An autonomous machine according to claim 1 or 2 wherein 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.
`
`4.
`
`An autonomous machine according to claim 3 wherein the path information is
`
`30
`
`stored at regular intervals.
`
`5.
`
`An autonomous machine according to claim 4 wherein the path information is
`
`546
`
`546
`
`

`

`W0 03/040845
`
`PCT/GBll2/049l9
`
`22
`
`stored at intervals which are spaced by an equal distance from one another.
`
`6.
`
`An autonomous machine according to any one of claims 3-5 wherein the path
`
`information is representative of the change in direction of the machine as the machine
`
`follows the boundary of the area.
`
`7.
`
`An autonomous machine according to claim 6 wherein the path information is the
`
`relative change in direction of the machine compared to a previous point at which path
`
`information was stored.
`
`8.
`
`An autonomous machine according to any one of claims 3-7 wherein the
`
`navigation system is arranged to derive, from the stored path information, a second set of
`
`path information which is a less detailed representation of the travelled path.
`
`9.
`
`An autonomous machine according to claim 8 wherein the comparison means is
`
`arranged to use the second set of path information in deciding ,whether the new path
`
`information and previously stored path information are substantially the same.
`
`10.
`
`An autonomous machine according to any one of claims 3-9 wherein the
`
`navigation system also comprises means for sensing another parameter and for storing this
`
`other parameter in the memory along with the path information as the machine follows the
`
`boundary of the area.
`
`11.
`
`An autonomous machine according to claim 10 wherein the comparison means
`
`also uses, on at least some occasions, the other parameter to determine when the machine
`
`has returned to a previously visited position in the area.
`
`12.
`
`An autonomous machine according to claim 10 or 11 wherein the other parameter
`
`is the absolute direction of the machine.
`
`13.
`
`A method of controlling an autonomous machine comprising:
`
`- causing the machine to explore the area in which it is located, constructing a map
`
`10
`
`15
`
`20
`
`30
`
`547
`
`547
`
`

`

`W0 03/040845
`
`PCT/G302/04919
`
`23
`
`of the area based on information collected by the machine as the machine explores the
`area,
`
`— determining when the machine has returned to a previously visited position within
`
`the area,
`
`- 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.
`
`Software for controlling an autonomous machine to perform the method according
`14
`to claim 13.
`
`10
`
`15.
`
`An autonomous machine, a method of controlling an autonomous machine or
`
`software method for controlling an autonomous machine substantially as described herein
`
`with reference to the accompanying drawings.
`
`15
`
`548
`
`548
`
`

`

`W0 03/040845
`
`PCT/G302/04919
`
`1/13
`
`
`
`549
`
`549
`
`

`

`W0 03/040845
`
`PCT/G802/04919
`
`2/13
`
`CONTROL
`MW
`
`210
`
`220
`
`299
`
`MICROPROCESSOR
`
`
`
`230
`
`110
`
`1}
`
`.1
`
`160 m
`@»
`PIR SENSORS
`
`POWER CONTROL
`A41
`
`“ h
`‘
`11.2
`
`122
`
`105
`0 00 0 132
`
`144
`
`0‘9? '33 '53"
`
`125
`
`104
`
`104
`
`1 30
`
`150,154
`
`152
`
`’1
`
`62
`
`Fig. 2
`
`550
`
`550
`
`

`

`W0 03/040845
`
`PCT/G802/04919
`
`3/13
`
`
` No Perimeter
`Initial Find Wall
`
`
`Perimeter Scan Wait
`
`
`
`
`
`Find Freespace Start
`
`Find Free Space
`
`
`
`waspace
`
`Freespace Find Wall
`
`No Perimeter Jump
`
`
`
`
`
`Freespace Perimeter Scan
`
`Orient to Freespace Vector
`
`Start Freespace Scan
`
`Do Reciprocate
`
`Do Primary Traverse Wait
`
`Main Traverse
`
`Localise Find Wall
`
`
`
`
`
`
`
`Step Across
`
`Localise Perimeter Scan
`
`
`Initial Perimeter
`
`
`
`Traverse Freespace
`
`
`
`
`
`
`
`I
`
`Shadow Fill
`
`
`
`
`
`Centrai Object
`
`
`
`Move Round Object
`
`
`
`551
`
`551
`
`

`

`W0 03/040845
`
`PCT/GBII2/049I9
`
`4/13
`
`300
`
`302
`
`FIND NEAREST WALL
`
` START UP
`
`
`
`
`
`
`
`
`
`
`_
`FOLLOW PERIMETER OF AREA;
`STORE PATH DATA; STORE DISTANCE'INFORMATION;
`STORE OTHER DATA}
`
`'GENERATE MAP OF AREA;
`COMPARE 'TEST WINDOW' WITH WINDOW OF
`
`PREVIOUSLY STORED DATA }
`VALID MATCH FOUND?
`
`
`
` YES
`NO MATCH/
`VALID MATCH
`INVALID MATCH
`
`
`
`
`
`UPDATE (CORRECT) MAP
`320
`
`
`STOP MACHINE
`
`Fig; 4
`
`552
`
`552
`
`

`

`W0 03/040845
`
`PCT/G302/049l9
`
`5/ 13
`
`
`
`553
`
`553
`
`

`

`W0 03/040845
`
`PCT/(3302/049 1 9
`
`6/13
`
`IEEEEEIIEE
`5.me
`3002.3
`
`
`
`x095omhmm:
`
`
`
`IIIEHEHIIIEIIIE«28:3:5
`
`
`
`105‘s..x.
`
`
`EEIIIIEE:35:
`
`HIE!-Emw3:2595
`mmozmmmmuanom._m<._.
`
`554
`
`554
`
`
`

`

`W0 03/040845
`
`PCT/GB02/04919
`
`7/13
`
`
`
`555
`
`555
`
`

`

`W0 03/040845
`
`PCT/GBOZ/04919
`
`8/13
`
`START
`
`350
`
`FOLLOW PERIMETER OF WORKING AREA;
`CONSTRUCT MAP OF WORKING AREA USING ODOMETRY DATA
`
`355
`
`
`
`HAS PATH MATCHING PROCESS RECOGNISED
`START POINT?
`
`360
`
`YES
`
`365
`
`CONSTRUCT LOCAL CO-ORDINATE SYSTEM f_1_ AT START SEGMENT
`CONSTRUCT LOCAL CO-ORDINATE SYSTEM _F_z_ AT FINISH SEGMENT
`
`370
`
`
`
`FOR EACH POINT ALONG THE PERIMETER PATH,
`CONSTRUCT INTERMEDIATE CO-ORDINATE SYSTEMS
`AS A FUNCTION OF DISTANCE TRAVELLED
`PERIMETER PATH LENGTH
`
`OBTAIN NEW POINT BY RESOLVING POINT INTO
`INTERMEDIATE CO-ORDINATE SYSTEM
`
`375
`
`TRANSLATE ALL POINTS ON PERIMETER PATH TO
`ROBOT CO-ORDINATE SYSTEM
`
`380
`
`Fig. 9
`
`556
`
`556
`
`

`

`W0 03/040845
`
`PCT/G302/04919
`
`9/13
`
`START
`
`S O O -
`
`
`EXAMINE MAP FOR FREESPACE VECTORS;
`IDENTIFY PATH SECTIONS WITH FREESPACE
`
`
`ADJACENT TO THEM
`
`' 505
`
`ANY FREESPACE AREAS ?
`
`ROOM CLEANED
`
`510
`YES
`
`
`
`FIND LONGEST PATH SECTION WITH ADJACENT FREESPACE;
`FIND DOMINANT ORIENTATION OF EDGES,’
`
`FIND MAX. & MIN. POINTS OF THE FREESPACE AREA BY
`ORIENTING THE FREESPACE AREA WITH THE DOMINANT
`ORIENTATIONI
`EXAMINE MAX. & MIN. POINTS}
`E TART POINT
`
`5’15
`
`
`
`
`
`
`
`
`
`FIND TARGET POINT; EXTRACT SECTION OF PATH DATA
`PRECEDING SCAN START POINT
`
`520
`
`530
`
`FIND ROUTE TO TARGET POINT;
`ROUTE POSSIBLE ACROSS AREA?
`'
`
`535
`NO
`
`FOLLOW ROUTE TO
`TARGET POINT
`
`FOLLOW PERIMETER TO
`TARGET POINT
`
`TRAVERSE UNCLEANED AREA FROM START POINT;
`DURING TRAVERSE; RECORD PATH OF MACHINE +
`RECORD DISTANCE INFORMATION ON MAP
`
`51.5
`
`
`
`
`
`
`
`
`SCAN FINISHED ?
`
`YES
`
`LOCALISE ON PERIMETER. DETERMINE ERROR]
`UPDATE PATH RECORDED ON MAP
`
`560
`
`
`
`
`Fig. 11
`
`557
`
`557
`
`

`

`_ W0 03/040845
`
`PCT/GBOZ/049l9
`
`10/13
`
`292550
`
`Pz<z§8_
`
`!!!!!_\\
`
`.\\3OS,\\$33$5
`
`x
`
`_.
`
`Sa:
`
`gamma/
`
`_/z<ommoV/
`
`/
`
`/
`
`/
`
`‘/.
`
`__I.E
`
`X733
`
`J525
`
`558
`
`558
`
`

`

`
`
`559
`
`

`

`W0 03/040845
`
`PCT/0302/04919
`
`CURRENT / /
`POSITION
`
`
`
`
`
`
`560
`
`560
`
`

`

`W0 03/040845
`
`PCT/GBO2/049l9
`
`13/13
`
`800
`
`802
`
`808
`
`
`
`561
`
`561
`
`

`

`H“TEEH&ATN3NFH.SEU\RCH+liEP£MRT
`
`A. cmssmcmon or: SUBJECT MAr-ren
`IPC 7
`605D1 02
`
`Internati
`
`\ppllcfltlon No
`
`PCT/GE 02/04919
`
`According to international Patent Classification (IPC) orlo both national classification and lPC
`B. FIELDS SEARCHED
`Minimum documentation searched (classification system followed by classification symbols)
`IPC 7
`GOSD A47L
`A01D
`
`Documentation searched other than minimum documentation to the extent that such documents are Included in the fields searched
`
`Electronic data base consulted during the lntcmational search (name of data base and, where practical, search terms used)
`
`EPO—Internal, WPI Data, PAJ
`
`C. DOCUMENTS CONSIDERED TO BE RELEVANT
`Category “ Citation of document, with indication, where appropriate. of the relevant passages
`
`Relevant to claim NO
`
`NO 00 38025 A (NOTETRY LTD ;ALDRED MICHAEL
`DAVID (GB); BISSET DAVID LINDSEY (63))
`29 June 2000 (2000—06—29)
`cited in the application
`the whole document
`
`"Coordination of
`LANG S Y T ET AL:
`behaviours for mobile robot floor
`cleaning"
`INTELLIGENT ROBOTS AND SYSTEMS, 1998.
`PROCEEDINGS., 1998 IEEE/RSJ INTERNATIONAL
`CONFERENCE ON VICTORIA, BC, CANADA 13-17
`OCT. 1998, NEW YORK, NY, USA,IEEE, US,
`13 October 1998 (1998—10~13), pages
`1236-1241, XP010311567
`ISBN: 0—7803—4465—0
`Paragraph 4. Environment Exploration and
`Motion Planning
`
`_/__
`
`.
`
`
`
`1—14
`
`1-14
`
`-
`
`
`
`Further documents are listed In the continuation of box C.
`
`Patent tamiiy members are listed in annex.
`
`ited dowme ls:
`" S eclal cate
`n
`gorles 0‘ c
`p
`-
`-
`It document defining the general state of the art which is not
`considered to be at particular relevance
`'E' eanler document but published on or after the international
`filing date
`'L' document which may throw doubts on priority claimts) or
`which is cited 1° estapilsh "‘E’ publication. date 0' another
`citation or other special reason (as specrtied)
`'0' document referring to an oral disclosure. use, exhibition or
`other means
`'P' document published prior to the International filing date but
`laierthan the priority date claimed
`Date of the actual completion of the international search
`
`14 January 2003
`Name and maltan address of the ISA
`European Patent Office, P3 5818 Patenllaan 2
`Tel. (+31 —-70) 340—2040,
`x.
`epo n ,
`ML — 2280 HV Rijswilk T 81 651
`I
`Fax: (+3140) 340—8016
`Form PCT/ISAIZIO (second Shoal) (July 1992)
`
`'T'
`
`.
`later document published after the rntematlonal tiling date
`or prionly dale and not In conflict with the application but
`.
`'nci
`|
`in 0
`un
`Etieeitlcggnderstand "'5 p"
`p e or
`e '7
`denying the
`'X' document of particular relevance; the claimed invention
`cannot be considered novel or cannot be considered to
`involve an inventive step when the document is taken alone
`'Y' document of particular relevance- the claimed invention
`cannot be considered 10 Involve an inventive step when the
`document to combined with one or more other such docu~
`monts, such combination being obvrous to a person skilled
`I" "'6 art-
`'
`'Bi‘ document member oi the same patent family
`Date or mailing of the international search report
`
`27/01/2003
`Authorl7ed oliicer
`
`Gardel la , S
`
`562
`
`562
`
`

`

`
` ppllcatlon No
`
` lnternaq
`PCT/GB 02/04919
`
`
`
`
`Relevant to claJm No.
`
`
`
`
`
`INTERNATIONAL SEARCH REPORT
`
`c.(Contlnuatlon) DOCUMENTS CONSIDERED TO BE RELEVANT
`Citation of documenl, wllh Indicaltonmhere appropriate. of the relevant passages
`
`
`
`
`
`
`
`we 95 26512 A (ELECTROLUX AB ;EDLUND LEIF
`($9) 5 October 1995 (1995—10—05)
`page 9, 1ine 5 —page 11,
`line 35
`
` US 5 001 635 A (YASUTOMI FUMIO ET AL)
`
`
`19 March 1991 (1991—03—19)
`the whole document
`
`Form PCT/ISAI210 (confinuaklnn of swcnd sheen (JU‘Y 199?)
`
`563
`
`563
`
`

`

`FURTHER INFORMATION CONTINUED FROM PCTIISAI 210
`
`Continuation of Box 1.2
`
`International Application No. PCTIGB 02 04919
`
`15
`
`include any technical feature but merely refers to the
`Claim 15 does not
`description and to the drawings.
`
`The applicant’s attention is drawn to the fact that claims, or parts of
`claims, relating to inventions in respect of which no international
`search report has been established need not be the subject of an
`international preliminary examination (Rule 66.1(e) PCT). The applicant
`is advised that the EPO policy when acting as an International
`Preliminary Examining Authority is normally not to carry out a
`preliminary examination on matter which has not been searched. This is
`the case irrespective of whether or not the claims are amended following
`receipt of the search report or during any Chapter II procedure.
`
` Claims Nos.:
`
`564
`
`564
`
`

`

`INTERNATIONAL SEARCH REPORT
`
`
`lnteri
`nal application No.
`
`
`
`”V63 02/04919
`
`
`Box I Observation wh r c rtain claims w re found unsearchabie (Continuation of it m 1 of first sheet)
`
`Claims Nos:
`
`because they relate to subject matter not required to be searched by this Authority, namely:
`
`This international Search Report has not been established in respect of certain claims under Article 17(2)(a) for the following reasons:
`
`
`
`
`
`
`
`
`15
`2. IE Claims Nos;
`because they relate to parts of the international Application that do not comply with the prescribed requirements to such
`an extent that no meaningful international Search can be carried out, specifically:
`
`see FURTHER INFORMATION sheet PCT/ISA/ZIO
`
`3. [:I Claims Nos:
`because they are dependent claims and are not drafted in accordance with the second and third sentences of Rule 6.4(a).
`
`Box ll Observations where unity of invention is lacking (Continuation of Item 2 of first sheet)
`
`This international Searching Authority found multiple inventions in this international application, as follows:
`
`
`
`
`1. D As all required additional search fees were timely paid by the applicant, this international Search Report covers all
`searchable claims.
`
` As all searchable claims could be searched without effortjustifylng an additional fee, this Authority did not invite payment
`
`of any additional fee.
`-
`
` As only some of the required additional search fees were timely paid by the applicant. this international Search Report
`
`covers only those claims for which fees were paid. specifically claims Nos:
`
`
`
` No required additional search fees were timely paid by the applicant. Consequently, this international Search Report Is
`restricted to the invention first mentioned in the claims; it is covered by claims Nos.:
`
`
`Remark on Protest
`[:l The additional search fees were accompanied by the applicant's protest.
`E] No protest accompanied the payment of additional search fees.
`
`
`Form PCT/lSA/210(coniinuation of first sheet (1)) (July 1998)
`
`565
`
`565
`
`

`

`INTEFflVATflJNA¢.SEARC#IREFK)RT
`Iniwallon on patent family members
`
`
`
`Patent document
`cited In search report
`
`Publicatlon
`date
`
`Patent famlly
`member(s)
`
`Internal“
`\ppllcatlon No
`
`PCT/(3F 02/04919
`Publicatlon
`date
`
`
`
`
`
`NO 0038025
`
`29— 06- 2000
`
`GB
`
`21-06-2000
`2344900 A
`12-07--2000
`1575300 A
`
`
`24-10-2001
`2361553 A
`
`
`0038025
`29~06-2000
`
`
`NO 9526512
`A
`05-10—1995
`502834
`29—01-1996
`
`
`
`689571 BZ
`02—04—1998
`AU
`
`
`AU
`2155495 A
`17—10—1995
`CA
`2186223 A1
`05—10—1995
`DE
`69520736 D1
`23—05—2001
`
`
`DE
`69520736 T2
`22—11—2001
`EP
`0753160 A1
`15-01-1997
`
`
`ES
`2156940 T3
`01—08—2001
`JP
`9511060 T
`04-11—1997
`
`
`SE
`9401061 A
`30-09—1995
`
`
`WO
`9526512 A1
`05-10-1995
`5867800
`02—02—1999
`
`
`
`18—0791989
`1180010
`19-03—1991
`A
`
`
`
`
`
`9200946
`31-01—1992
`
`
`
`
`
`Fon-n PCT/ISAIZ10 (patanl family annex) (Ju1y 1992)
`
`566
`
`566
`
`

`

`PCT
`
`WORLD INTELLECTUAL PROPERTY ORGANIZATION
`lntematxonal Bureau
`
`
`
`INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION T