(12)Un1ted States Patent
`(10) Patent No.:
`US 6,809,490 B2
`
`Jones et al.
`(45) Date of Patent:
`Oct. 26, 2004
`
`USOO6809490B2
`
`(54) METHOD AND SYSTEM FOR MULTI-MODE
`COVERAGE FOR AN AUTONOMOUS
`ROBOT
`
`(75)
`
`(73)
`
`.
`.
`Inventors %%§?Phl{"hi0nes’]3Actt°n’32%;)
`1 1p
`'
`355’
`OS on’
`(
`)
`.
`.
`.
`.
`ASSIgHCCZ IRObOt corporatlom Burhngmm MA
`(US)
`.
`.
`.
`.
`SUbJCCt to any disclalmer, the term of thls
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`.
`(*) Notice:
`
`(21) Appl. No.: 10/167,851
`
`(22)
`
`Filed:
`
`Jun. 12, 2002
`
`(65)
`
`Prior Publication Data
`US 2003/0025472 A1 Feb. 6, 2003
`
`(60)
`
`Related US. Application Data
`Provisional application No. 60/297,718, filed on Jun. 12,
`2001.
`
`Int. Cl.7 ................................................... 1325] 5/00
`(51)
`(52) US. Cl.
`............................ 318/568.12; 318/568.16;
`318/568.17; 700/245
`(58) Field of Search ....................... 318/568.12, 568.16,
`318/568.17; 700/245
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`6/1987 Okumura .................... 364/424
`4,674,048 A
`4,962,453 A * 10/1990 Pong et al.
`................... 701/23
`5,086,535 A *
`2/1992 Grossmeyer et al.
`......... 15/319
`5,109,566 A
`5/1992 Kobayashi et al.
`15/319
`
`5,204,814 A *
`4/1993 Noonan et al.
`........
`701/25
`.
`5,284,522 A
`2/1994 Kobayashi et al.
`134/18
`
`5,321,614 A *
`6/1994 Ashworth ..........
`701/26
`.....
`.. 15/319
`5,341,540 A *
`8/1994 Soupert et al.
`
`5,548,511 A *
`8/1996 Bancroft .........
`701/23
`
`.. 342/127
`5,682,313 A * 10/1997 Edlund et al.
`...............
`5,867,800 A *
`2/1999 Leif
`701/23
`
`................ 701/23
`5,935,179 A
`8/1999 Kleiner et al.
`
`5,940,927 A
`....... 15/319
`8/1999 Haegermarck et al.
`5,942,869 A *
`8/1999 Katou et al.
`........... 318/568.12
`6,076,025 A *
`........ 701/23
`6/2000 Ueno etal.
`
`6,076,226 A
`6/2000 Reed .............
`15/319
`
`6,240,342 B1
`..... 701/25
`5/2001 Fiegert et al.
`.
`
`6,327,741 B1
`12/2001 Reed .............
`15/319
`
`6,370,453 B2 *
`4/2002 Sommer .
`701/23
`6,389,329 B1
`5/2002 Colens ..........
`700/262
`
`6,459,955 B1
`10/2002 Bartsch et al.
`.
`700/245
`6,463,368 B1 * 10/2002 Feiten et al. .............. 701/23
`
`6,481,515 B1
`11/2002 Kirkpatrick et al.
`..... 180/25.1
`6,493,612 B1
`12/2002 Bisset et al.
`.................. 701/23
`
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`JP
`JP
`JP
`JP
`JP
`
`60259895
`60293095
`63—183032
`62074018
`2—6312
`
`6/1987
`7/1987
`7/1988
`10/1988
`1/1990
`
`(List continued on next page.)
`OTHER PUBLICATIONS
`
`Doty, Keith L. et al., “Sweep Strategies for a Sensory-
`—Driven, Behavior—Based Vacuum Cleaning Agent,” AAAI
`1993 Fall Symposium Series, US.
`Karcher RC 3000 Cleaning Robot—user Manual. Manufac-
`turer: Alfred Karcher GmbH & Co., Cleaning Systems,
`Alfred—Karcher—Str. 28—40, PO. Box 160, D—71349 Win-
`nenden, Germany, Dec. 2002.
`
`Primary Examiner—Rita Leykin
`(74) Attorney, Agent, or Firm—Glen D. Weinstein, Esq.;
`Gesmer Updegrove LLP
`
`(57)
`
`ABSTRACT
`
`A control system for a mobile robot (10) is provided to
`effectively cover a given area by operating in a plurality of
`modes, including an obstacle following mode (51) and a
`random bounce mode (49). In other embodiments, spot
`coverage, such as spiraling (45), or other modes are also
`used to increase effectiveness. In addition, a behavior based
`architecture is used to implement the control system, and
`various escape behaviors are used to ensure full coverage.
`
`42 Claims, 16 Drawing Sheets
`
`
`
`Silver Star Exhibit 1001
`
`Silver Star Exhibit 1001
`
`

`

`US 6,809,490 132
`
`Page 2
`
`US. PATENT DOCUMENTS
`
`6,493,613 B2
`6,574,536 B1 *
`6,605,156 B1
`6,615,108 B1
`2001/0047231 A1
`
`.................. 701/23
`12/2002 Peless et a1.
`6/2003 Kawagoe et a1.
`............. 701/23
`
`8/2003 Clark et a1.
`.......
`134/6
`................ 700/245
`9/2003 Peless et a1.
`11/2001 Peless et a1.
`
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`
`FOREIGN PATENT DOCUMENTS
`6—3251
`1/1994
`7—295636
`11/1995
`07338573
`7/1997
`08000393
`7/1997
`2555263
`8/1997
`08016776
`8/1997
`3375843
`8/1998
`09043901
`9/1998
`11.510935
`9/1999
`11162454
`12/2000
`2001—525567
`12/2001
`2002—204768
`7/2002
`
`JP
`JP
`JP
`JP
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`
`2002—323925
`2003—036116
`2003-052596
`2003—061882
`WO 97/40734
`WO 97/41451 A1
`WO 97/41451
`WO 99/38056
`WO 9959042 A
`WO 00/38026
`WO 00/38029
`WO 97/78410 A1
`WO 01/06904 A1
`WO 02/39864 A1
`W0 02/067744 A1
`W0 02/075469 A1
`W0 02/075470 A1
`W0 03/040845 A1
`W0 03/040846 A1
`
`11/2002
`2/2003
`2/2003
`3/2003
`11/1997
`11/1997
`11/1997
`7/1999
`11/1999
`6/2000
`6/2000
`12/2000
`2/2001
`5/2002
`9/2002
`9/2002
`9/2002
`5/2003
`5/2003
`
`* cited by examiner
`
`Silver Star Exhibit 1001 - 2
`
`Silver Star Exhibit 1001 - 2
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 1 0f 16
`
`US 6,809,490 B2
`
`
`
`Silver Star Exhibit 1001 - 3
`
`Silver Star Exhibit 1001 - 3
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 2 0f 16
`
`US 6,809,490 B2
`
`40
`
`
`
`Silver Star Exhibit 1001 - 4
`
`Silver Star Exhibit 1001 - 4
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 3 0f 16
`
`US 6,809,490 B2
`
`33
`
`Power
`
`User
`
`User
`
`Button
`
`I II F“
`
`21
`PWM
`Bump - Wrnbond
`Sensors
`W78XXX Series W Right
`14
`8-bit processor
`._ Wheei
`(on-board Program H
`-= memory and RAM)
`PWM
`16 _
`:— MOtOY
`w,"
`l""—
`Sensors
`21
`PWM
`- Vacuum
`Motor
`
`Ri ht
`Whgeel
`
`PWM Left Wheel
`
`Left Wheel
`
`—
`
`Sensors -
`
`RCON
`Sensor
`
`R8232 ‘
`
`Wheeldrop
`Sensor
`
`PWM
`
`Brush
`- Motor
`
`Silver Star Exhibit 1001 - 5
`
`Silver Star Exhibit 1001 - 5
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 4 0f 16
`
`US 6,809,490 B2
`
`IV
`
`(t=t,)
`
`(i=0)
`
`iIIiIiIIi
`
`III
`
`
`
`Silver Star Exhibit 1001 - 6
`
`Silver Star Exhibit 1001 - 6
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 5 0f 16
`
`US 6,809,490 B2
`
`
`
`
`Selection
`Device
`
`
`
`
`
`Spot
`
`Cieaning
`
`
`
`FIG. 5
`
`45
`
`40
`
`@
`
`10
`
`45
`
`160,10
`
`FIG. 6A
`
`FIG. 6B
`
`101
`
`45
`
`Kg 10
`
`FIG. 6C
`
`Silver Star Exhibit 1001 - 7
`
`Silver Star Exhibit 1001 - 7
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 6 0f 16
`
`US 6,809,490 B2
`
`
`
` 201
`
`Spiral begins
`set initial r value
`
`
`
`Setr=ae
`
`240
`
`
`
`
`Max.
`
`spiral
`distance
`
`Exit spiral
`
`
`
`FIG. 7
`
`Silver Star Exhibit 1001 - 8
`
`Silver Star Exhibit 1001 - 8
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 7 0f 16
`
`US 6,809,490 B2
`
`110
`
`100
`
`10
`
`46
`
`FIG. 8A
`
`M
`
`110
`
`FIG. 88
`
`Silver Star Exhibit 1001 - 9
`
`Silver Star Exhibit 1001 - 9
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 8 0f 16
`
`US 6,809,490 B2
`
`HA
`101
`
`Min
`
`46
`
`FIG. 80
`
`IA
`101
`
`ng
`
`46
`
`,L
`101
`
`Mt“
`
`MEX
`
`FIG. 8D
`
`Silver Star Exhibit 1001 - 10
`
`Silver Star Exhibit 1001 - 10
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 9 0f 16
`
`US 6,809,490 B2
`
` Edge detection
`begins set
`
`value
`
`301
`
`Set rating
`most
`
`335
`
`
`negative
`
`
` R to NR
`transit
`
`
`Set rating
`most
`
`positive
`
`
` NR to R
`
`transit
`
`
`
`
`
`Decrease absolute
`
`
`value of r
`
`FIG. 9A
`
`Silver Star Exhibit 1001 - 11
`
`Silver Star Exhibit 1001 - 11
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 10 0f 16
`
`US 6,809,490 B2
`
`Obstacle?
`
`
`
`Continue WF
`
`Silver Star Exhibit 1001 - 12
`
`Silver Star Exhibit 1001 - 12
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 11 0f 16
`
`US 6,809,490 B2
`
`
`
`
`Enter bounce model
`
`90 straight
`
`401
`
`
`
`Obstacle?
`
`
`
` 410
`
`
`
`from obstacle
`
` Turn away
`
`
`Silver Star Exhibit 1001 - 13
`
`Silver Star Exhibit 1001 - 13
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 12 0f 16
`
`US 6,809,490 B2
`
`48
`
`101
`
`V A
`
`m '1‘
`
`FIG. 11
`
`Silver Star Exhibit 1001 - 14
`
`Silver Star Exhibit 1001 - 14
`
`

`

`US. Patent
`
`4002
`
`e
`
`08
`
`2B0
`
`
`
`m.o?BoaI!a"om8v0oz2.F13mma
`
`
`
`omoA32wwo>oovmAwm
`
`(---------
`
`a
`
`_.+$3.
`
`m8»
`
`am
`L---.--- ---..--------.-.-----...---..-J
`
`IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
`
`mto52mM8v9%Boz02
`
`mm>
`
`ma3comA«fix0A2.05
`
`$>
`
`wI9,<30;
`
`acow20mM8v2%Uoz
`
`mmwmw>
`
`MMm«Mmou9mmmfimcm
`
`mm>
`
`«8395
`
`02
`
`8v9%
`
`I...mm>m:
`
`mmm
`
`.EEw
`
`zmok
`
`mmw
`
`2935
`
`8vsou
`
`Silver Star Exhi
`
`it 1001 - 15
`
`Silver Star Exhibit 1001 - 15
`
`
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 14 0f 16
`
`US 6,809,490 B2
`
`
`
`Brush off
`time = 0
`
`level + 90
`
`
`
`1_3_Q
`
`No
`
`Level > 250
`
`£52
`
`FIG. 128
`
`Silver Star Exhibit 1001 - 16
`
`Silver Star Exhibit 1001 - 16
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 15 0f 16
`
`US 6,809,490 B2
`
`100
`
`115
`100
`
`115
`
`FIG. 138
`
`Silver Star Exhibit 1001 - 17
`
`Silver Star Exhibit 1001 - 17
`
`

`

`US. Patent
`
`Oct. 26, 2004
`
`Sheet 16 0f 16
`
`US 6,809,490 B2
`
`
`
`FIG. 14
`
`Silver Star Exhibit 1001 - 18
`
`Silver Star Exhibit 1001 - 18
`
`

`

`US 6,809,490 B2
`
`1
`METHOD AND SYSTEM FOR MULTI-MODE
`COVERAGE FOR AN AUTONOMOUS
`ROBOT
`
`This application is entitled to the benefit of US. provi-
`sional application Ser. No. 60/297,718 filed Jun. 12, 2001.
`
`FIELD OF THE INVENTION
`
`This invention relates generally to autonomous vehicles
`or robots, and more specifically to methods and mobile
`robotic devices for covering a specific area as might be
`required of, or used as, robotic cleaners or lawn mowers.
`DESCRIPTION OF PRIOR ART
`
`For purposes of this description, examples will focus on
`the problems faced in the prior art as related to robotic
`cleaning (e.g., dusting, buffing, sweeping, scrubbing, dry
`mopping or vacuuming). The claimed invention, however, is
`limited only by the claims themselves, and one of skill in the
`art will recognize the myriad of uses for the present inven-
`tion beyond indoor, domestic cleaning.
`Robotic engineers have long worked on developing an
`effective method of autonomous cleaning. By way of
`introduction,
`the performance of cleaning robots should
`concentrate on three measures of success: coverage, clean-
`ing rate and perceived effectiveness. Coverage is the per-
`centage of the available space visited by the robot during a
`fixed cleaning time, and ideally, a robot cleaner would
`provide 100 percent coverage given an infinite run time.
`Unfortunately, designs in the prior art often leave portions of
`the area uncovered regardless of the amount of time the
`device is allowed to complete its tasks. Failure to achieve
`complete coverage can result from mechanical limitations--
`e.g., the size and shape of the robot may prevent it from
`reaching certain areas--or the robot may become trapped,
`unable to vary its control to escape. Failure to achieve
`complete coverage can also result from an inadequate cov-
`erage algorithm. The coverage algorithm is the set of
`instructions used by the robot to control its movement. For
`the purposes of the present invention, coverage is discussed
`as a percentage of the available area visited by the robot
`during a finite cleaning time. Due to mechanical and/or
`algorithmic limitations, certain areas within the available
`space may be systematically neglected. Such systematic
`neglect is a significant limitation in the prior art.
`A second measure of a cleaning robot’s performance is
`the cleaning rate given in units of area cleaned per unit time.
`Cleaning rate refers to the rate at which the area of cleaned
`floor increases; coverage rate refers to the rate at which the
`robot covers the floor regardless of whether the floor was
`previously clean or dirty. If the velocity of the robot is v and
`the width of the robot’s cleaning mechanism (also called
`work width) is w then the robot’s coverage rate is simply wv,
`but its cleaning rate may be drastically lower.
`A robot that moves in a purely randomly fashion in a
`closed environment has a cleaning rate that decreases rela-
`tive to the robot’s coverage rate as a function of time. This
`is because the longer the robot operates the more likely it is
`to revisit already cleaned areas. The optimal design has a
`cleaning rate equivalent to the coverage rate, thus minimiz-
`ing unnecessary repeated cleanings of the same spot. In
`other words, the ratio of cleaning rate to coverage rate is a
`measure of efficiency and an optimal cleaning rate would
`mean coverage of the greatest percentage of the designated
`area with the minimum number of cumulative or redundant
`
`passes over an area already cleaned.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`A third metric of cleaning robot performance is the
`perceived effectiveness of the robot. This measure is ignored
`in the prior art. Deliberate movement and certain patterned
`movement is favored as users will perceive a robot that
`contains deliberate movement as more effective.
`
`While coverage, cleaning rate and perceived effectiveness
`are the performance criteria discussed herein, a preferred
`embodiment of the present invention also takes into account
`the ease of use in rooms of a variety of shapes and sizes
`(containing a variety of unknown obstacles) and the cost of
`the robotic components. Other design criteria may also
`influence the design, for example the need for collision
`avoidance and appropriate response to other hazards.
`As described in detail in Jones, Flynn & Seiger, Mobile
`Robots: Inspiration to Implementation second edition, 1999,
`A K Peters, Ltd., and elsewhere, numerous attempts have
`been made to build vacuuming and cleaning robots. Each of
`these robots has faced a similar challenge: how to efficiently
`cover the designated area given limited energy reserves.
`We refer to maximally efficient cleaning, where the clean-
`ing rate equals the coverage rate, as deterministic cleaning.
`As shown in FIG. 1A, a robot 1 following a deterministic
`path moves in such a way as to completely cover the area 2
`while avoiding all redundant cleaning. Deterministic clean-
`ing requires that the robot know both where it is and where
`it has been; this in turn requires a positioning system. Such
`a positioning system—a positioning system suitably accu-
`rate to enable deterministic cleaning might rely on scanning
`laser rangers, ultrasonic transducers, carrier phase differen-
`tial GPS, or other methods—can be prohibitively expensive
`and involve user set-up specific to the particular room
`geometries. Also, methods that rely on global positioning are
`typically incapacitated by the failure of any part of the
`positioning system.
`One example of using highly sophisticated (and
`expensive) sensor technologies to create deterministic clean-
`ing is the RoboScrub device built by Denning Mobile
`Robotics and Windsor Industries, which used sonar, infrared
`detectors, bump sensors and high-precision laser navigation.
`RoboScrub’s navigation system required attaching large
`bar code targets at various positions in the room. The
`requirement that RoboScrub be able to see at least four
`targets simultaneously was a significant operational prob-
`lem. RoboScrub, therefore, was limited to cleaning large
`open areas.
`
`Another example, RoboKent, a robot built by the Kent
`Corporation, follows a global positioning strategy similar to
`RobotScrub. RoboKent dispenses with RobotScrub’s more
`expensive laser positioning system but having done so
`RoboKent must restrict itself only to areas with a simple
`rectangular geometry, e.g.
`long hallways. In these more
`constrained regions, position correction by sonar ranging
`measurements is sufficient. Other deterministic cleaning
`systems are described, for example, in US. Pat. No. 4,119,
`900 (Kremnitz), US. Pat. No. 4,700,427 (Knepper), US.
`Pat. No. 5,353,224 (Lee et al, US. Pat. No. 5,537,017
`(Feiten et al.), US. Pat. No. 5,548,511 (Bancroft), 5,650,702
`(Azumi).
`Because of the limitations and difficulties of deterministic
`
`cleaning, some robots have relied on pseudo-deterministic
`schemes. One method of providing pseudo-deterministic
`cleaning is an autonomous navigation method known as
`dead reckoning. Dead reckoning consists of measuring the
`precise rotation of each robot drive wheel
`(using for
`example optical shaft encoders). The robot can then calcu-
`late its expected position in the environment given a known
`
`Silver Star Exhibit 1001 - 19
`
`Silver Star Exhibit 1001 - 19
`
`

`

`US 6,809,490 B2
`
`3
`starting point and orientation. One problem with this tech-
`nique is wheel slippage. If slippage occurs, the encoder on
`that wheel registers a wheel rotation even though that wheel
`is not driving the robot relative to the ground. As shown in
`FIG. 1B, as the robot 1 navigates about the room, these drive
`wheel slippage errors accumulate making this type of system
`unreliable for runs of any substantial duration. (The path no
`longer consists of tightly packed rows, as compared to the
`deterministic coverage shown in FIG. 1A.) The result of
`reliance on dead reckoning is intractable systematic neglect;
`in other words, areas of the floor are not cleaned.
`One example of a pseudo-deterministic a system is the
`Cye robot from Probotics, Inc. Cye depends exclusively on
`dead reckoning and therefore takes heroic measures to
`maximize the performance of its dead reckoning system.
`Cye must begin at a user-installed physical registration spot
`in a known location where the robot fixes its position and
`orientation. Cye then keeps track of position as it moves
`away from that spot. As Cye moves, uncertainty in its
`position and orientation increase. Cye must make certain to
`return to a calibration spot before this error grows so large
`that it will be unlikely to locate a calibration spot. If a
`calibration spot is moved or blocked or if excessive wheel
`slippage occurs then Cye can become lost (possibly without
`realizing that it is lost). Thus Cye is suitable for use only in
`relatively small benign environments. Other examples of
`this approach are disclosed in US. Pat. No. 5,109,566
`(Kobayashi et al.) and US. Pat. No. 6,255,793 (Peless et al.).
`Another approach to robotic cleaning is purely random
`motion. As shown in FIG. 1C, in a typical room without
`obstacles, a random movement algorithm will provide
`acceptable coverage given significant cleaning time. Com-
`pared to a robot with a deterministic algorithm, a random
`cleaning robot must operate for a longer time to achieve
`acceptable coverage. To have high confidence that
`the
`random-motion robot has cleaned 98% of an obstacle-free
`room, the random motion robot must run approximately five
`times as long as a deterministic robot with the same cleaning
`mechanism moving at the same speed.
`The coverage limitations of a random algorithm can be
`seen in FIG. 1D. An obstacle 5 in the room can create the
`effect of segmenting the room into a collection of chambers.
`The coverage over time of a random algorithm robot in such
`a room is analogous to the time density of gas released in one
`chamber of a confined volume. Initially, the density of gas
`is highest in the chamber where it is released and lowest in
`more distant chambers. Similarly the robot is most likely to
`thoroughly clean the chamber where it starts, rather than
`more distant chambers, early in the process. Given enough
`time a gas reaches equilibrium with equal density in all
`chambers. Likewise given time, the robot would clean all
`areas thoroughly. The limitations of practical power
`supplies, however, usually guarantee that the robot will have
`insufficient time to clean all areas of a space cluttered with
`obstacles. We refer to this phenomenon as the robot diffusion
`problem.
`As discussed, the commercially available prior art has not
`been able to produce an effective coverage algorithm for an
`area of unknown geometry. As noted above, the prior art
`either has relied on sophisticated systems of markers or
`beacons or has limited the utility of the robot to rooms with
`simple rectangular geometries. Attempts to use pseudo-
`deterministic control algorithms can leave areas of the space
`systematically neglected.
`OBJECTS AND ADVANTAGES
`
`It is an object of the present invention to provide a system
`and method to allow a mobile robot to operate in a plurality
`of modes in order to effectively cover an area.
`
`4
`It is an object of the present invention to provide a mobile
`robot, with at least one sensor, to operate in a number of
`modes including spot-coverage, obstacle following and
`bounce.
`
`It is a further object of the invention to provide a mobile
`robot that alternates between obstacle following and bounce
`mode to ensure coverage.
`It is an object of the invention to return to spot-coverage
`after the robot has traveled a pre-determined distance.
`It is an object of the invention to provide a mobile robot
`able to track the average distance between obstacles and use
`the average distance as an input to alternate between opera-
`tional modes.
`
`It is yet another object of the invention to optimize the
`distance the robot travels in an obstacle following mode as
`a function of the frequency of obstacle following and the
`work width of the robot, and to provide a minimum and
`maximum distance for operating in obstacle following
`mode.
`
`It is an object of a preferred embodiment of the invention
`to use a control system for a mobile robot with an opera-
`tional system program able to run a plurality of behaviors
`and using an arbiter to select which behavior is given control
`over the robot.
`
`It is still another object of the invention to incorporate
`various escape programs or behavior to allow the robot to
`avoid becoming stuck.
`Finally, it is an object of the invention to provide one or
`more methods for controlling a mobile robot to benefit from
`the various objects and advantages disclosed herein.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`These and further features of the present invention will be
`apparent with reference to the accompanying drawings,
`wherein:
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`FIGS. 1A—D illustrate coverage patterns of various robots
`in the prior art;
`FIG. 2 is a top-view schematic representation of the basic
`components of a mobile robot used in a preferred embodi-
`ment of the invention;
`FIG. 3 demonstrates a hardware block diagram of the
`robot shown in FIG. 2;
`FIG. 4A is a diagram showing a method of determining
`the angle at which the robot encounters an obstacle;
`FIG. 4B is a diagram showing the orientation of a
`preferred embodiment of the robot control system;
`FIG. 5 is a schematic representation of the operational
`modes of the instant invention;
`FIG. 6A is a schematic representation of the coverage
`pattern for a preferred embodiment of SPIRAL behavior;
`FIG. 6B is a schematic representation of the coverage
`pattern for an alternative embodiment of SPIRAL behavior;
`FIG. 6C is a schematic representation of the coverage
`pattern for yet another alternative embodiment of SPIRAL
`behavior;
`FIG. 7 is a flow-chart illustration of the spot-coverage
`algorithm of a preferred embodiment of the invention;
`FIGS. 8A & 8B are schematic representations of the
`coverage pattern for a preferred embodiment of operation in
`obstacle following mode;
`FIG. 8C is a schematic illustration of the termination of
`
`the obstacle following mode when an obstacle is encoun-
`tered after the mobile robot has traveled a minimum dis-
`tance.
`
`Silver Star Exhibit 1001 - 20
`
`Silver Star Exhibit 1001 - 20
`
`

`

`US 6,809,490 B2
`
`5
`FIG. 8D is a schematic illustration of the termination of
`
`the obstacle following mode after the mobile robot has
`traveled a maximum distance.
`FIG. 9A is a flow-chart illustration of the obstacle fol-
`
`lowing algorithm of a preferred embodiment of the inven-
`tion;
`FIG. 9B is a flow-chart illustration of a preferred algo-
`rithm for determining when to exit obstacle following mode.
`FIG. 10 is a schematic representation of the coverage
`pattern for a preferred embodiment of BOUNCE behavior;
`FIG. 11 is a flow-chart illustration of the room coverage
`algorithm of a preferred embodiment of the invention;
`FIGS. 12A & 12B are flow-chart
`illustrations of an
`
`exemplary escape behavior;
`FIG. 13A is a schematic representation of the coverage
`pattern of a mobile robot with only a single operational
`mode;
`FIG. 13B is a schematic representation of the coverage
`pattern for a preferred embodiment of the instant invention
`using obstacle following and room coverage modes; and
`FIG. 14 is a schematic representation of the coverage
`pattern for a preferred embodiment of the instant invention
`using spot-coverage, obstacle following and room coverage
`modes.
`
`DESCRIPTION OF INVENTION
`
`In the present invention, a mobile robot is designed to
`provide maximum coverage at an effective coverage rate in
`a room of unknown geometry. In addition, the perceived
`effectiveness of the robot is enhanced by the inclusion of
`patterned or deliberate motion. In addition, in a preferred
`embodiment, effective coverage requires a control system
`able to prevent the robot from becoming immobilized in an
`unknown environment.
`
`While the physical structures of mobile robots are known
`in the art, the components of a preferred, exemplary embodi-
`ment of the present invention is described herein. A pre-
`ferred embodiment of the present invention is a substantially
`circular robotic sweeper containing certain features. As
`shown in FIG. 2, for example, the mobile robot 10 of a
`preferred embodiment
`includes a chassis 11 supporting
`mechanical and electrical components. These components
`include various sensors, including two bump sensors 12 &
`13 located in the forward portion of the robot, four cliff
`sensors 14 located on the robot shell 15, and a wall following
`sensor 16 mounted on the robot shell 15.
`In other
`
`embodiments, as few as one sensor may be used in the robot.
`One of skill in the art will recognize that the sensor(s) may
`be of a variety of types including sonar,
`tactile,
`electromagnetic, capacitive, etc. Because of cost restraints,
`a preferred embodiment of the present invention uses bump
`(tactile) sensors 12 & 13 and reflective IR proximity sensors
`for the cliff sensors 14 and the wall-following sensor 16.
`Details of the IR sensors are described in US. patent
`application U.S. Ser. No. 09/768,773, which disclosure is
`hereby incorporated by reference.
`A preferred embodiment of the robot also contains two
`wheels 20, motors 21 for driving the wheels independently,
`an inexpensive low-end microcontroller 22, and a recharge-
`able battery 23 or other power source known in the art.
`These components are well known in the art and are not
`discussed in detail herein. The robotic cleaning device 10
`further includes one or more cleaning heads 30. The clean-
`ing head might contain a vacuum cleaner, various brushes,
`sponges, mops, electrostatic cloths or a combination of
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`various cleaning elements. The embodiment shown in FIG.
`2 also includes a side brush 32.
`
`As mentioned above, a preferred embodiment of the
`robotic cleaning device 10 comprises an outer shell 15
`defining a dominant side, non-dominant side, and a front
`portion of the robot 10. The dominant side of the robot is the
`side that
`is kept near or in contact with an object (or
`obstacle) when the robot cleans the area adjacent to that
`object (or obstacle). In a preferred embodiment, as shown in
`FIG. 1, the dominant side of the robot 10 is the right-hand
`side relative to the primary direction of travel, although in
`other embodiments the dominant side may be the left-hand
`side. In still other embodiments, the robot may be symmetric
`and thereby does not need a dominant side; however, in a
`preferred embodiment, a dominant side is chosen for reasons
`of cost. The primary direction of travel is as shown in FIG.
`2 by arrow 40.
`In a preferred embodiment, two bump sensors 12 & 13 are
`located forward of the wheels 20 relative to the direction of
`
`forward movement, shown by arrow 40. One bump sensor
`13 is located on the dominant side of the robot 10 and the
`
`other bump sensor 12 is located on the non-dominant side of
`the robot 10. When both of these bump sensors 12 & 13 are
`activated simultaneously,
`the robot 10 recognizes an
`obstacle in the front position. In other embodiments, more or
`fewer individual bump sensors can be used. Likewise, any
`number of bump sensors can be used to divide the device
`into any number of radial segments. While in a preferred
`embodiment the bump sensors 12 & 13 are IR break beam
`sensors activated by contact between the robot 10 and an
`obstacle, other types of sensors can be used,
`including
`mechanical switches and capacitive sensors that detect the
`capacitance of objects touching the robot or between two
`metal plates in the bumper that are compressed on contact.
`Non-contact sensors, which allow the robot to sense prox-
`imity to objects without physically touching the object, such
`as capacitive sensors or a curtain of IR light, can also be
`used.
`
`It is useful to have a sensor or sensors that are not only
`able to tell if a surface has been contacted (or is nearby), but
`also the angle relative to the robot at which the contact was
`made. In the case of a preferred embodiment, the robot is
`able to calculate the time between the activation of the right
`and left bump switches 12 & 13, if both are activated. The
`robot is then able to estimate the angle at which contact was
`made. In a preferred embodiment shown in FIG. 4A, the
`bump sensor comprises a single mechanical bumper 44 at
`the front of the robot with sensors 42 & 43 substantially at
`the two ends of the bumper that sense the movement of the
`bumper. When the bumper is compressed,
`the timing
`between the sensor events is used to calculate the approxi-
`mate angle at which the robot contacted the obstacle. When
`the bumper is compressed from the right side, the right bump
`sensor detects the bump first, followed by the left bump
`sensor, due to the compliance of the bumper and the bump
`detector geometry. This way, the bump angle can be approxi-
`mated with only two bump sensors.
`For example, in FIG. 4A, bump sensors 42 & 43 are able
`to divide the forward portion of the robot into six regions
`(I—VI). When a bump sensor is activated, the robot calcu-
`lates the time before the other sensor is activated (if at all).
`For example, when the right bump sensor 43 is activated, the
`robot measures the time (t) before the left bump sensor 42
`is activated. Ift is less than t1, then the robot assumes contact
`occurred in region IV. If t is greater than or equal to t1 and
`less than t2, then the robot assumes contact was made in
`region V. If t is greater than or equal to t2 (including the case
`
`Silver Star Exhibit 1001 - 21
`
`Silver Star Exhibit 1001 - 21
`
`

`

`US 6,809,490 B2
`
`7
`of where the left bump sensor 42 is not activated at all within
`the time monitored), then the robot assumes the contact
`occurred in region VI. If the bump sensors are activated
`simultaneously,
`the robot assumes the contact was made
`from straight ahead. This method can be used the divide the
`bumper into an arbitrarily large number of regions (for
`greater precision) depending on of the timing used and
`geometry of the bumper. As an extension, three sensors can
`be used to calculate the bump angle in three dimensions
`instead of just two dimensions as in the preceding example.
`Apreferred embodiment also contains a wall-following or
`wall-detecting sensor 16 mounted on the dominant side of
`the robot 10. In a preferred embodiment, the wall following
`sensor is an IR sensor composed of an emitter and detector
`pair collimated so that a finite volume of intersection occurs
`at the expected position of the wall. This focus point is
`approximately three inches ahead of the drive wheel in the
`direction of robot forward motion. The radial range of wall
`detection is about 0.75 inches.
`
`Apreferred embodiment also contains any number of IR
`cliff sensors 14 that prevent the device from tumbling over
`stairs or other vertical drops. These cliff sensors are of a
`construction similar to that of the wall following sensor but
`directed to observe the floor rather than a wall. As an
`
`additional safety and sensing measure, the robot 10 includes
`a wheel-drop sensor that is able to detect if one or more
`wheels is unsupported by the floor. This wheel-drop sensor
`can therefore detect not only cliffs but also various obstacles
`upon which the robot is able to drive, such as lamps bases,
`high floor transitions, piles of cords, etc.
`Other embodiments may use other known sensors or
`combinations of sensors.
`
`FIG. 3 shows a hardware block diagram of the controller
`and robot of a preferred embodiment of the invention. In a
`preferred embodiment, a Winbond W78XXX series proces-
`sor is used.
`It
`is a microcontroller compatible with the
`MCS-51 family with 36 general purpose I/O ports, 256 bytes
`of RAM and 16K of ROM. It is clocked at 40 MHZ which
`
`is divided down for a processor speed of 3.3 MHZ. It has two
`timers which are used for triggering interrupts used to
`process sensors and generate output signals as well as a
`watchdog timer. The lowest bits of the fast timer are also
`used as approximate random numbers where needed in the
`behaviors. There are also two external interrupts which are
`used to capture the encoder inputs from the two drive
`wheels. The processor also has a UART which is used for
`testing and debugging the robot control program.
`The I/O ports of the microprocessor are connected to the
`sensors and motors of the robot and are the interface
`
`to the internal state of the robot and its
`connecting it
`environment. For example,
`the wheel drop sensors are
`connected to an input port and the brush motor PWM signal
`is generated on an output port. The ROM on the micropro-
`cessor is used to store the coverage and control program for
`the robot. This includes the behaviors (discussed below),
`sensor process