Patent Description:
Autonomous robots are robots which can perform desired tasks in environments without continuous human guidance. Robots may be autonomous to different degrees and in different ways. For example, an autonomous robot can traverse a work surface of an unstructured environment without continuous human guidance to perform one or more tasks. In other examples, an autonomous robot may perform tasks in structured environments or with human supervision. In the field of home, office and/or consumer-oriented robotics, mobile robots have been adopted for performing functions such as vacuum cleaning, floor washing, patrolling, lawn cutting, and other such tasks.

However, many conventional autonomous robots do not adequately or precisely determine robot position and/or pose and do not adequately control the robot's movements to ensure the robot stays on a given route and/or reach a designated position and/or pose. <CIT> describes a technique for carpet drift estimation using a one dimensional image sensor.

In particular, contemplated aspects include methods and non-transitory computer-readable medium embodying some or all concepts of one or more aspects described herein.

Systems and methods are described for estimating drift, such as carpet drift, experienced by a robot moving across a surface, such as a carpet, and for compensating for such drift, such as carpet drift. By way of further example, certain systems and methods described may be configured to estimate drift due to other effects that may impact the motion of a robot traversing a surface, such as motion drift due to sloped floors, unstable surfaces (e.g., sand or dirt surfaces), and/or due to wind pushing or pulling the robot.

The present invention relates to a method for estimating a carpet drift or a carpet drift vector of an autonomous cleaning robot as set out in claim <NUM> and a system as set out in claim <NUM>.

These drawings and the associated description herein are provided to illustrate specific embodiments of the invention and are not intended to be limiting.

Methods and systems are described for estimating drift, such as carpet drift. Example embodiments are described herein in the context of systems and methods for estimating carpet drift experienced by a cleaning robot, but will be applicable to other types of devices, such as mobile robotic devices capable of traversing a carpeted surface. It is understood that the term carpet is intended to include rugs and other floor coverings that may have a grain or nap. It is also understood that example embodiments described herein will be applicable to estimating drift due to effects other than carpet effects, such as, by way of example, motion drift due to sloped floors, unstable surfaces (e.g., sand or dirt surfaces), and/or due to wind forces (e.g., relatively constant or slowly time-varying wind pushing or pulling on the robot).

The manufacturing process of carpets may align the carpet's fibers such that the fibers tend to bend in a particular direction. This direction that the fibers are biased may be referred to as the carpet's grain direction or nap direction. The effect of the grain direction may be experienced by an object when the object moves over the carpet, for example, by vacuuming the carpet or running your hand over the carpet. If the object moves across the carpet along the grain direction, the fibers of the carpet may tend to fall down in the direction of the motion, thereby aiding robot movement in the grain direction. However, if the object moves against the grain direction, the fibers of the carpet may tend to stand up, thereby resisting or inhibiting robot movement.

The direction-dependent forces of the carpet due to the carpet grain acting upon a moving object can influence the motion of the object. For example, the trajectory of an autonomous cleaning device may be disturbed by the influence of the carpet grain. The effect of the carpet grain on the motion of the object may be referred to as carpet drift. Carpet drift may be represented by a carpet drift vector, which has both a magnitude and a direction. The carpet drift vector may be a property of the carpet.

For autonomous robots, carpet drift can pose a problem. In particular, an autonomous robot may rely on estimates of its position and/or orientation determined by using sensors such as wheel encoders, gyroscope, accelerometers, and/or the like sensors. For example, a wheel encoder sensor may be used to determine a distance traveled based on sensing an amount that the wheels of the robotic device rotated during a period of time. However, when an autonomous robot navigates in a carpeted environment, its wheels can make the carpet fibers stand up or fall down based on the motion of the robot relative to the carpet grain. In particular, when the fibers fall down along the carpet grain, the carpet can push or guide the robot in the direction of the carpet grain. As a result, the robot can travel a distance greater than the distance determined based on the wheels' rotations when the robot moves in the direction of the carpet grain. On the other hand, when the robot travels over erect fibers against the carpet grain, the robot can travel a distance less than the distance determined based on the wheels' rotations. In either case, the actual distance traveled may be different than the distance measured by the sensors, such as the wheel encoders and the like sensors used for dead-reckoning.

While the carpet drift vector direction may be fixed or constant in the environment for a particular carpet, the amount of drift may be proportional or somewhat related to the distance traveled. Hence, the position estimate error can accumulate over time as the robot traverses the carpet. Accordingly, the robot may not be able to build an accurate map of the environment or may not be able to navigate the environment efficiently, accurately, and/or safely for carrying out tasks such as vacuuming.

Estimates of the carpet drift can optionally be generated based in whole or in part on the motion of the robotic device that is not accounted for by its odometry sensors (e.g., integrated differential motion sensors). In particular, carpet drift may optionally be estimated by combining two or more types of sensor measurements. In an example embodiment, measurements from a sensor can provide an indication of the desired motion or commanded motion, and measurements from another sensor (e.g., a different type of sensor) can provide an indication of the true or actual motion. For example, in an example embodiment, odometry sensors (e.g., one or more sensors that measure wheel rotation amounts) may provide an indication of the desired or commanded motion based on measured or commanded wheel rotations. Other characteristics of the actuator system may be used in addition or instead, such as wheel velocity, wheel acceleration, and/or the motor control signals. The true motion, such as changes in the robotic devices orientation or heading, may be estimated using, for example, data from gyroscopic sensors, image sensors, or any combination of the like sensors or other sensors. The carpet drift (or carpet drift vector) may be estimated by comparing the desired motion and the actual motion.

Estimates of the carpet drift may be used to improve or correct the motion estimate. For example, the estimated carpet drift vector may be used with a motor controller to compensate for the effects of carpet grain and/or may be used to generate a correction term to adjust odometry data. Estimates of the carpet drift may also be used to estimate whether the robot is on carpeted or non-carpeted floor.

<FIG> is a schematic diagram illustrating a top view of an example robotic device <NUM> (although it is understood that the internal components of the robotic device are shown schematically and the illustration is not intended to depict that actual positioning or location of such internal components within the robotic device <NUM>). The robotic device <NUM> includes a body <NUM>, an actuator system <NUM>, a communication bus <NUM>, a controller <NUM>, a first set of sensors <NUM>, a second set of sensors <NUM>, a third set of sensors <NUM>, and a cleaning mechanism <NUM>.

The body <NUM> can include structures that form the exterior surfaces of the robotic device <NUM> as well as various internal structures, such as a chassis. Accordingly, the body <NUM> may be configured to house the actuator system <NUM>, the communication bus <NUM>, the controller <NUM>, the first set of one or more sensors <NUM>, the second set of one or more sensors <NUM>, the third set of one or more sensors <NUM>, and the cleaning mechanism <NUM>. It is understood that fewer or additional sets of sensors may be used.

The exterior surfaces of the example robotic device <NUM> can define any applicable shape, including but not limited to shapes having top-view profiles that define substantially straight edges, such as a rectangular and triangular configurations, or one or more substantially curved or arcuate edges, such as circular, oval, and D-shaped configurations; however, the body <NUM> may define other shapes as well. In operation, the exterior surfaces may become in contact with obstacles, such as a wall. Accordingly, the exterior surface of the body <NUM> may include portions formed from material having friction coefficients that allows the robotic device <NUM> to slidably move along such obstacles.

The actuator system <NUM> is configured to move the body <NUM> across a surface, such as a carpeted and/or non-carpeted floors. For example, the actuator system <NUM> can receive a drive command from the controller <NUM> via the communication bus <NUM> for controlling an actuator motion or force generated by the actuator system <NUM>, such as driving one or more wheels to rotate on the surface. The actuator system <NUM> and the body <NUM> may be operatively coupled such that the generated actuator motion or force causes the body <NUM> to move. The actuator system <NUM> can include any applicable number of motor, wheel, transmission, and the like assemblies for generation of a force for causing movement of the body <NUM>. The actuator system <NUM> will be described in greater detail later in connection with <FIG>.

The communication bus <NUM> is configured to communicatively interconnect the actuator system <NUM>, the controller <NUM>, and the first, second, and third sets of sensors <NUM>, <NUM>, <NUM>. The communication bus <NUM> can transmit electrical, optical, and/or mechanical signals. Although the illustrated embodiments shows the communication bus <NUM> as a shared bus, it will be appreciated by one skilled in the art that other configurations may be implemented, such as additional or alternative communication channels between any individual or subgroups of the actuator system <NUM>, the controller <NUM>, and the first, second, and third sets of sensors <NUM>, <NUM>, <NUM>.

The controller <NUM> may be configured to receive data/measurements from the sensors <NUM>, <NUM>, <NUM> as inputs and to estimate drift, such as carpet drift. For example, the controller <NUM> may be configured to estimate drift, such as carpet drift, based at least on the actuation characteristic sensed by the first set of sensors <NUM> and the motion characteristic sensed by the second set of sensors <NUM> received from the communication bus <NUM>. Examples of the actuation characteristic include, but are not limited to, wheel rotational positions, rates, accelerations, and/or like actuator measurements that provide an indication of the commanded or desired movement. For example, if the robotic device <NUM> is moved by wheels of the actuator system <NUM>, the desired displacement of the robotic device <NUM> may be estimated by odometry (e.g., based on the amount rotations of the wheels and the diameter of the wheels). Examples of the motion characteristic include, but are not limited to, rotational characteristics (e.g., angular orientation, velocity, and/or acceleration) of the body <NUM>, the path angle (e.g., the angle or change in angle of the velocity vector of the robotic device <NUM> in the room coordinates), and/or like measurements that provide an indication of the true motion of the robotic device <NUM>. For example, gyroscopic sensors can provide measurement of the rotational changes of the orientation of the robotic device <NUM>. As an additional example, imaging sensors can provide measurements related to path angle of the device.

In addition, the controller <NUM> may be configured to control the operation of the actuator system <NUM> and/or the cleaning mechanism <NUM>. For example, the controller <NUM> can send control signals to the actuator system <NUM> via the communication bus <NUM> to move the robotic device <NUM> in a desired trajectory. In addition, in some embodiments, the controller <NUM> can engage the cleaning mechanism <NUM> by sending a control signal to the actuator system <NUM>, or to the cleaning mechanism <NUM> directly. The controller <NUM> will be described in greater detail later with reference to <FIG>.

The first set of sensors <NUM> may be configured to sense an actuation characteristic of the actuator system <NUM>. For example, the first set of sensors <NUM> may be coupled to the actuator system <NUM>. In a particular embodiment, the first set of sensors <NUM> can include one or more odometry sensors, such as linear or rotary encoders coupled to one or more wheels of the actuator system <NUM>, or sensors or modules that measure or collect control or power signals supplied to the actuator system <NUM>. These measurements can provide a way to estimate motion of the robotic device <NUM> by odometry or dead-reckoning methods. However, the estimates may deviate from the actual motion, for example, due to carpet drift.

The second set of sensors <NUM> may be configured to sense a motion characteristic of the body <NUM>. For example, the first set of sensors <NUM> may be coupled to the body <NUM> for sensing the motion characteristic relative to the environment or an inertial frame. The sensed motion characteristic may be provided to the controller <NUM> via the communication bus <NUM>. In an example embodiment, the second set of sensors <NUM> can include one or more gyroscopic sensors for sensing rotation of the body <NUM>. In another embodiment, the second set of sensors <NUM> can in addition or instead include one or more image sensors for capturing images of the environment for estimating the path angle of the robotic device <NUM>.

The third set of sensors <NUM> can optionally be included for sensing a second motion characteristic of the body <NUM>. For example, while some embodiments of the robotic device <NUM> can sense changes in only one of body rotation or path angle, other embodiments can sense both optionally using, for example, the second and third sets of sensors <NUM>, <NUM>. Accordingly, in an example embodiment the robotic device <NUM> can include one or more gyroscopic sensors, compass sensors, and/or accelerometers for sensing rotation of the body <NUM> (e.g., corresponding to the second set of sensors <NUM>) and can include one or more image sensors for imaged-based heading estimates (e.g., corresponding to the third set of sensors <NUM>).

As stated, each of the first, second, and third sets of sensors <NUM>, <NUM>, <NUM> may optionally be a different type of sensor. For example, in an example embodiment the first set of sensors <NUM> can include one more odometry sensors, the second set of sensors <NUM> can include one or more gyroscopic sensors, and the optional third set of sensors <NUM> can include one or more image sensors.

The cleaning mechanism <NUM> may be configured to capture dirt from the surface. For example, the cleaning mechanism <NUM> can include a brush, cleaning mat and/or a vacuum assembly coupled to the body <NUM> and positioned such that it can capture dirt from the surface as the robotic device <NUM> traverses the surface. In some embodiments, the cleaning mechanism may be configured to be powered by the actuator system <NUM>, for example, to power a brush assembly (which may be a pliable multi-vane beater or a have pliable beater flaps between rows of brush bristles) and create suction for vacuuming. It will be appreciated that the cleaning mechanism <NUM> need not be included and is optional.

In operation, the controller <NUM> can command the actuator system <NUM> to move the robotic device <NUM> a desired displacement (and/or at a desired velocity), represented in the illustrated embodiment by the vector a. As stated, a carpeted floor may affect the motion of the robotic device <NUM> due, in part, to the carpet grain of the carpet. Accordingly, the robotic device <NUM> can experience carpet drift, represented in the illustrated embodiment by the vector b. The actual displacement vector c may be a superposition of the desired displacement vector a and the carpet drift vector b.

In operation, the controller <NUM> may receive measurement from the first set of sensors <NUM> via the communication bus <NUM>. For example, the measurements of the first set of sensors <NUM> may be related to the desired displacement vector a. In addition, the controller <NUM> can receive measurements from the second set of sensors <NUM> via the communication bus <NUM>. For example, the measurements of the second set of sensors <NUM> may be related to the actual motion vector b. Based (in whole or in part) on these measurements, the controller <NUM> can estimate the effect of the carpet drift vector c. The estimate can aid in correcting measurements (e.g., odometry measurements) from the first set of sensors <NUM> and/or compensate for carpet drift.

<FIG> is a schematic diagram illustrating an example embodiment of an actuator system <NUM> of the robotic device <NUM> of <FIG>. The actuator system <NUM> includes a left rotatable wheel <NUM>, a right rotatable wheel <NUM>, a left transmission assembly <NUM>, a right transmission assembly <NUM>, and a drive sub-system <NUM>.

The drive sub-system <NUM> may be configured to generate power for rotating the left and right rotatable wheels <NUM>, <NUM> for moving the robotic device <NUM>. For example, the left transmission assembly <NUM> may be configured to transmit mechanical power generated by the drive sub-system <NUM> to rotate the left wheel <NUM>. Similarly, the right transmission assembly <NUM> may be configured to transmit mechanical power generated by the drive sub-system <NUM> to rotate the right wheel <NUM>. The left and right wheels <NUM>, <NUM> may be driven differentially. For example, the drive sub-system <NUM> can drive the left wheel <NUM> at a velocity vl and the right wheel <NUM> independently at a velocity vr. Varying the differential velocities of the left and right wheels <NUM>, <NUM> can turn the robotic device <NUM> by a radius based on the magnitude of the differential velocities and a distance L of the wheelbase (e.g., the distance between the left and right wheels <NUM>, <NUM>). Accordingly, the illustrated embodiment of the actuator system <NUM> may be configured to move the robotic device <NUM> as the wheels <NUM>, <NUM> rotate in contact with the floor on a controllable path or heading.

It will be appreciated that any applicable wheel type may be selected, and that each of the left and right wheels <NUM>, <NUM> may be part of a left and right wheel sub-systems (not shown) that can include a plurality of left wheels interconnected by a left track, and a plurality of right wheels interconnected by a right track, similar to the drive system of a tank. It will be further appreciated that in other embodiments the actuator system <NUM> can include one or more left legs and one or more right legs for providing movement. It will be further appreciated that in yet other embodiments the actuator system <NUM> can include one or more rotatable and pivotable wheels configured to move the robotic device <NUM> as it rotates, in a variable direction in accordance with the angle that the wheels are pivoted.

When the robotic device <NUM> is moving along the direction of the carpet grain, the displacement estimated by the rotation of the wheels <NUM>, <NUM> (e.g., by odometry) may be less than the actual displacement. When the robotic device <NUM> is moving and going against the direction of the carpet grain, the effect may be reversed in whole or in part. In the illustrated embodiment of <FIG>, the carpet drift vector c is at an angle θ with respect to the robot wheelbase. For example, if the left wheel <NUM> is being driven at velocity vl and the right wheel <NUM> at velocity vr, the robotic device <NUM> would drive in an arc defined by vl, vr, and L in the absence of carpet drift and wheel slippage. However, the carpet drift can move the robotic device <NUM> in the direction of the carpet drift vector c and the actual displacement may be different from the desired one.

To further illustrate, if the left and the right wheels <NUM>, <NUM> move a distance dl and dr, respectively, during a duration (e.g., a unit time), this motion may be sensed by a displacement sensor such as wheel odometry sensors. The change in heading caused by this motion (e.g., absent carpet drift, wheel slippage, and the like actuator disturbances) may be approximately modeled by the following example equation: <MAT>.

Accounting for carpet drift in the direction of the wheel travel, the actual displacement for each of the wheels can include a dot product between the carpet drift vector c and wheel motion direction as an additional term. As a result, the actual left and right displacements dlc, dlr may be approximately modeled by the following example equations: <MAT> <MAT>.

Given this displacement, the change in heading, which is what may be measured by a heading sensor like a gyroscope, may be approximately modeled by the following example equation: <MAT>.

The change in heading due to carpet drift may be estimated by taking the difference between the change in heading computed from odometry and the change in heading computed from a gyroscopic sensor: <MAT> <MAT>.

As is evident in Equation <NUM>, the difference in heading computed from a displacement sensor (such as an odometry sensor) and a heading sensor (such as a gyroscope) may be proportional to the carpet drift direction with respect to the robot heading. From Equation <NUM>, the absolute displacement of the individual wheels should be substantially different and constant. Thus, if the robot is made to cover all the possible orientations (e.g., move in an arc to cover a complete rotation), the difference in heading as estimated by Equation <NUM> should result in a sinusoidal function. The maxima and the minima of the sinusoid should occur when the robot is approximately aligned in the direction of the carpet grain and in the opposite direction of the carpet grain, respectively.

<FIG> is a schematic diagram illustrating an example embodiment of a controller <NUM> of the robotic device <NUM> of <FIG>. The controller <NUM> includes a processor <NUM> and memory <NUM>. The memory <NUM> includes an actuator module <NUM>, a sensor module <NUM>, a controller module <NUM>, and an estimation module <NUM>.

The processor <NUM> includes circuitry, such as a microprocessor or microcontroller, configured to execute instructions from memory <NUM> and to control and operate the actuator system (e.g., the actuator system <NUM> of <FIG>), sensors (e.g., first, second, and third sets of sensors <NUM>, <NUM>, <NUM> of <FIG>), cleaning mechanisms (e.g., the cleaning mechanism <NUM> of <FIG>), and/or the like components of the robotic system <NUM>. In particular, the processor <NUM> may be a general purpose single- or multi-chip microprocessor (e.g., an ARM), a special purpose microprocessor (e.g., a digital signal processor (DSP)), a microcontroller, a programmable gate array, etc. Although a single processor <NUM> is shown in the controller <NUM>, in an alternative configuration, a combination of processors (e.g., ARMs and DSPs) could be used.

The memory <NUM> includes tangible non-transitory computer-readable mediums configured to store information by chemical, magnetic, electrical, optical, or the like means. For instance, the memory <NUM> may be a non-volatile memory device, such as flash memory or a hard-disk drive, and/or a volatile memory device, such as dynamic-random access memory (DRAM) or static random-access memory (SRAM), or a system of a combination of non-volatile and volatile memories.

Within the memory <NUM> is the actuator module <NUM> that includes instructions that configure the processor <NUM> to operate the actuators of the robotic device <NUM>. For example, the actuator module <NUM> may include instructions that enable various modules residing in the memory <NUM> to use the actuator system <NUM> of <FIG>. In particular, the actuator module <NUM> may include instructions that form a driver for controlling communication of data and control messages between the controller <NUM> and the actuator system <NUM> of <FIG>.

Within the memory <NUM> is the sensor module <NUM> that includes instructions that configure the processor <NUM> to operate the sensors of the robotic device <NUM>. For example, the sensor module <NUM> can include instructions that enable various modules residing in the memory <NUM> to use the sensors <NUM>, <NUM>, <NUM> of <FIG>. In particular, the sensor module <NUM> can include instructions that form a driver for controlling communication of data and control messages between the controller <NUM> and the sensors <NUM>, <NUM>, <NUM> of <FIG>.

Within the memory <NUM> is the controller module <NUM> that includes instructions that configure the processor <NUM> to control the actuators <NUM> and the sensors <NUM>, <NUM>, <NUM> of the robotic system <NUM>, as well as the execution of the actuator module <NUM>, the sensor module <NUM>, and the estimation module <NUM>. For example, the controller module <NUM> can include instruction related to generating control signals (e.g., motor control laws) for the actuators and for calling instructions of the actuator module <NUM> for sending the generated control signals to the actuator system <NUM>. The controller module <NUM> can include instructions related to calling instructions of the sensor module <NUM> for receiving the measurements from the sensors <NUM>, <NUM>, <NUM>. The controller module <NUM> can include instructions controlling the execution of instructions of the estimation module <NUM> for estimating carpet drift.

Within the memory <NUM> is the estimation module <NUM> that includes instructions that configure the processor <NUM> to estimate carpet drift. Various methods implemented by the example estimation module <NUM> will be described in greater detail below in connection with <FIG>.

<FIG> is a flow diagram of method <NUM> of estimating carpet drift. In an example embodiment, the robotic device <NUM> executes instructions of the estimation module <NUM> in memory <NUM> for performing the operations of the method <NUM>. The method <NUM> starts at block <NUM> and proceeds to block <NUM> for moving the robotic device <NUM> in a pattern. For example, the controller <NUM> can command actuator system <NUM> to move the robotic device <NUM> across a surface. In some embodiments, moving the robotic device <NUM> may be part of a carpet-drift calibration phase (for example, during an initial operation on the surface or upon start-up). For instance, during a calibration process, the robotic device <NUM> may be commanded to perform a maneuver that rotates the robotic device <NUM> at least about <NUM> degrees or at least about <NUM> degrees. Rotating the robotic device at least <NUM> degrees enables the robotic device to align at least with or against the carpet drift vector during the rotation. Accordingly, the direction of the carpet drift vector c may be estimated, for example, by Equation <NUM> and determining the location of maxima/minima of Δαdrift. Rotating the robotic device at least <NUM> degrees enables the robotic device to align with and against the carpet drift vector during the rotation. Accordingly, the direction of the carpet drift vector c may be estimated, for example, by Equation <NUM> and determining the location of maxima and/or minima of Δαdrift. Additionally or alternatively, the movement of the robotic device <NUM> may be performed as part of a separate task, such as covering or cleaning a space. For example, the maneuver may be a turn made in response to encountering an obstacle, such as a wall. As another example, the maneuver may optionally be a substantially straight path, for example, as the robotic device <NUM> traverses from a first wall to a second wall.

During or concurrently with the operation of block <NUM>, the method <NUM> can perform block <NUM> for sensing an actuation characteristic of an actuator system of the robotic device <NUM>. For example, the controller <NUM> can receive a plurality of measurements of the actuation characteristic using the first set of sensors <NUM>. The actuation characteristic, for instance, can correspond to rotations of one or more wheels of the actuator system <NUM> to generate odometry. As discussed above in connection with <FIG>, odometry measurements may be used to estimate the desired change in heading of the robotic device <NUM>.

During or concurrently with the operation of block <NUM>, the method <NUM> may perform block <NUM> for sensing a motion characteristic of the robotic device <NUM>. For example, the controller <NUM> can receive a plurality of measurements of the motion characteristic using the second or third sets of sensors <NUM>, <NUM>. The motion characteristic, for instance, can correspond to a change in the rotation of the robotic device <NUM> sensed by a gyroscopic sensor or a change in the path angle sensed by an image based sensor.

After collecting measurements of each of the actuation characteristic and the motion characteristic, the method <NUM> can proceed to block <NUM> for estimating carpet drift based at least on the actuation characteristic and the motion characteristic. For example, the controller <NUM> may compare measurements of the actuation characteristic and the motion characteristic collected while the robotic device <NUM> performed a maneuver. The process of estimation performed at block <NUM> can depend on the nature of the motion characteristic. For example, the controller <NUM> may use one method (e.g., method 410a of <FIG>) of estimation if the motion characteristic is related to a rotation of the robotic device <NUM> and another method (e.g., method 410b of <FIG>) of estimation if the motion characteristic is related to a path angle. Both of such example methods of estimation are described in further detail later in connection with <FIG>.

Additionally or alternatively, the method of estimation can depend on the maneuver performed at block <NUM>. For example, if the maneuver includes a substantial rotation, such as a rotation of at least about <NUM> degrees or at least about <NUM> degrees, the method of estimation may be in accordance with the description below in reference to <FIG>. If the maneuver includes a substantially straight desired trajectory-such as a desired trajectory corresponding to commanded differential rotations or velocities of left and right wheels (e.g., wheels <NUM>, <NUM> of <FIG>) being less than about <NUM>% or less than about <NUM>% different-the process of estimation may be in accordance with the description below with reference to <FIG>. It will be appreciated, however, by one skilled in the art that the process of estimation of <FIG> may not require substantially straight desired trajectories, and other trajectories, such as curved trajectories, may be used.

Once the carpet drift is estimated, the method <NUM> continues to block <NUM> for applying carpet drift correction. For example, odometry readings may be corrected by adding a drift component proportional or otherwise related to the grain magnitude in the grain direction. The corrected odometry values may be used to estimate the robot position. The correction can significantly improve dead-reckoning of the robotic device <NUM> on carpeted floors.

The method <NUM> may optionally be run at intervals over the run of the robotic device <NUM> in order adjust the carpet drift estimation and improve position estimates. For example, the method <NUM> may be run periodically with respect to time or distance traveled. For example, robotic device <NUM> may be configured to run the method <NUM> after or in response to traveling a distance greater than a threshold distance (which may optionally be pre-specified) since the previous estimate was performed. In addition, the method <NUM> may optionally be performed to evaluate whether the robotic device <NUM> is operating in a multi-carpet (or multi-surface) environment. For example, different carpeted surface can have different carpet drift vectors associated with them. Method <NUM> may be performed a number of times to generate multiple carpet drift estimates. If the carpet drift estimates differ, then it may be estimated or determined that there exists multiple carpeted surfaces. In addition, if the carpet drift estimate indicate no or substantially no carpet drift, then it may be estimated or determined that the vehicle is operating on a non-carpeted surface. Once the method <NUM> completes, it can proceed to block <NUM> to end.

<FIG> is a flow diagram illustrating an example embodiment of a method 410a of estimating carpet drift based at least on measurements from odometry and gyroscopic sensors. For example, the method 410a may be executed as part of a calibration phase for corrected odometry with the estimated carpet drift. The method 410a may also be executed during performance of a task to adjust the estimated carpet drift. For example, the method 410a may be executed while the robotic device <NUM> is cleaning the surface of a room. In particular, the method 410a may be executed when the robotic device <NUM> rotates, for example, in response to encountering or navigating around an obstacle. One optional advantage, among others, of certain embodiments that use a gyroscopic sensor may be improved accuracy and reduced complexity in terms of hardware, implementation, and runt-time computations, as compared to, for example, image based sensors. In an example embodiment, the robotic device <NUM> executes instructions of the estimation module <NUM> in memory <NUM> for performing the operations of the method 410a.

The method 410a starts at block <NUM> and proceeds to block <NUM> for comparing a plurality of first and second heading estimates. For example, prior to starting the method 410a at block <NUM>, measurements may be collected while the robotic device <NUM> performs a maneuver including, for instance, a full rotation by pivoting around one wheel. Other motions can also be used. For example, maneuvers may be performed with non-zero differential between drive wheels (e.g., |dr| - |dl|). In an example embodiment, the N first heading estimates Δαodom,n (n = <NUM>, <NUM>,. , N) may be generated from the odometry measurements by utilizing Equation <NUM>. The N second heading estimates Δαgyro,n (n = <NUM>, <NUM>,. , N) may be generated by the gyroscopic sensors. In some embodiments, the pairs of measurements (Δαodom,n, Δαgyro,n)may be collected at approximate intervals, for example, whenever the robotic device <NUM> has rotated about <NUM> radians as compared to the last reading. The difference in heading due to carpet drift Δαdrift,n may be approximated by the following example equation: <MAT>.

The method 410a can proceed to block <NUM> for estimating a direction of the carpet drift based at least on difference in the comparisons made at block <NUM>. For example, the plot of Δαdrift,n over a complete rotation can approximate a sinusoidal signal as modeled in Equation <NUM>. The extrema or peak of the estimated heading change Δαdrift,n due to carpet drift can occur approximately when the odometry sensors and the gyroscopic sensors differ the most. For example, when the robotic device <NUM> is perfectly aligned with the direction of the carpet grain, the odometry sensors can under-estimate the turn angle and can lag behind the heading measured by the gyroscopic sensor, resulting in a maxima. Conversely, the minima can occur when the robotic device <NUM> is aligned against the carpet grain and the odometry sensors can overestimate the turn angle. Accordingly, the carpet grain direction may be estimated based on a peak of the comparisons of the first and second heading estimates. Standard or non-standard correlation/convolution and/or search techniques may be used for this purpose.

The method 410a can proceed to block <NUM> for estimating a magnitude of the carpet drift based at least on the total drift and the change of heading. For example, an estimate of the carpet drift magnitude may be obtained using the following example equation: <MAT>.

Equation <NUM> is the ratio of the total drift over one complete rotation (e.g., <NUM>π). Other amounts of rotations may be used by replacing the denominator of Equation <NUM> with the total change of the heading during the maneuver.

If the floor is not carpeted, the plot of Δαdrift,n may not resemble a sinusoidal wave having a period of N. Hence, if Δαdrift,n does not have a fundamental period of N (or if Δαdrift,n does not have a substantially sinusoidal waveform as expected from Equation <NUM>), the floor may be estimated or identified as not being carpeted. The method 410a can then proceed to block <NUM> to end.

One particular challenge of estimating carpet drift is that certain effects of carpet drift cannot be detected with a gyroscopic sensor. For example, if the robotic device <NUM> is being commanded to follow a straight path, one aspect of carpet drift can influence the motion of the robotic device <NUM> (e.g., by changing the path angle) in a way that does not substantially rotate or change the heading of the robotic device <NUM>. For example, carpet drift can affect the translational motion of the robotic device <NUM> without rotating the robotic device <NUM>. Accordingly, a gyroscopic sensor may not be effective for estimating aspects of carpet drift during maneuvers that have a substantially straight desired path (e.g., substantially zero absolute differential wheel displacements |dr| - |dl|) and/or when there is no substantial heading change. There is therefore a need for improved estimation of carpet drift.

<FIG> is a flow diagram illustrating an example embodiment of a method 410b of estimating carpet drift based at least on measurements from odometry and image sensors. For example, if the robotic device <NUM> is equipped with an imaging sensor such as a camera, image-based measurements may be used to perform on-line estimation of the carpet drift. In other example embodiments, the robotic device <NUM> may not include an integral imaging sensor. For example, images captured by an external camera may be communicated, for example, wirelessly to the robotic device <NUM>. Additionally or alternatively, an external system including a processor and a camera may image the robot and determine from the images the robotic device's <NUM> location and/or orientation and communicate the data to the robotic device <NUM>. Accordingly, the image-based estimation is described below in the context a fully integrated robot, but will be applicable to separate robot-camera systems.

Image-based estimation may optionally be effective for environments having multiple carpets, area rugs on hard floors, and other generic surface arrangements. Image based sensing may be effective even in situations in which there is no substantial commanded wheel differential (e.g., during an approximately straight-line maneuver). In other words, the method 410b may be effective for estimating carpet drift during maneuvers in which the robotic device <NUM> is not commanded to rotate. In an example embodiment, the robotic device <NUM> executes instructions of the estimation module <NUM> in memory <NUM> for performing the operations of the method 410b.

The method 410b starts at block <NUM> and proceeds to block <NUM> for determining a visual observation of motion from two or more images captured by the image sensor. There are various methods to determine visual observations of motion from visual information, including epipolar matching, visual odometry, phase correlation, and structure from motion. It will be appreciated by one skilled in the art that any suitable method for determining the visual observation may be used. An example embodiment involving epipolar matching is described in greater detail below in connection with <FIG>.

After determining the visual observation of motion, the method 410b proceeds to block <NUM> for executing a statistical filter. Estimates of the robotic device's <NUM> motion extracted from camera images may be combined using a statistical estimation filter. The statistical estimation filter can maintain an estimate of the carpet drift or carpet drift vector. There are various statistical estimation filters that can combine the visual observations including variants of Extended Kalman Filters (EKF), Extended Information Filters, non-linear optimization, and particle filters. An example embodiment that uses an iterative EKF (IEKF) is described in greater detail below in connection with <FIG>. The method 410b can end at block <NUM>.

In an example embodiment, the robotic device <NUM> may implement only one of the methods 410a or 410b. Another example embodiment, however, may implement both the methods 410a, 410b and switch between the two methods or modes during operation. For example, the robotic device <NUM> may include both a gyroscopic sensor and an image sensor. The robotic device <NUM> may execute method 410a during a calibration phase and/or during certain maneuvers in which the robotic device <NUM> is commanded to rotate. In addition, the robotic device <NUM> may execute method 410b during certain maneuvers in which the robotic device <NUM> is not commanded to rotate. For example, in a particular example embodiment the robotic device <NUM> may be configured to repeatedly traverse between two walls in order to clean a floor of a room. As such, the robotic device <NUM> may be configured to move in a substantially straight line from one wall to the other wall. During this straight-line maneuver, the robotic device <NUM> may be configured to selectively execute method 410b. When the robotic device <NUM> encounters the other wall, the robotic device <NUM> may be configured to rotate (e.g., approximately <NUM> degrees) to face the first wall. During this turning maneuver, the robotic device <NUM> may be configured to selectively execute method 410a.

Another example embodiment, however, may run both the methods 410a, 410b in parallel and switch between the two methods during operation. For example, the controller <NUM> of <FIG> may monitor the operation of the methods 410a, 410b to select the output that may provide the most reliable estimates. For example, the controller <NUM> may select to use the output of the process executing method 410a when the wheel differential (e.g., |dr| - |dl|) is large, or select away when the wheel differential is small. As another example, the controller <NUM> may select to use the output of the process executing method 410b when there are indications of accurate visual observation of motion. For example, as described below in further detail in connection with <FIG>, the method 410b may calculate certainty levels and can measure the closeness of feature matches. In an example embodiment, method 410b may be selected when there is low uncertainty and/or close feature matches.

Additionally or alternatively, to aid deciding between the two methods 410a, 410b or modes, the controller <NUM> may compare two hypothetical performance metrics that can be evaluated and compared online. For example, the method 410a may be assigned a performance metric P<NUM> with can be evaluated online. One example choice for the metric may be P<NUM> = µ<NUM> (|dr| - |dl|)-<NUM>, where µ<NUM> may be a design variable that can be selected based on application-specific considerations. Likewise, the method 410b may be assigned similar or different performance metric P<NUM>. One example choice for the metric may be P<NUM> = µ<NUM>∥P∥, where µ<NUM> may be a design variable that can be selected based on application-specific considerations and ∥P∥ may be a matrix norm of a covariance matrix P of a Kalman Filter used to generate vision based estimates of the drift (see, e.g., <FIG>). In an example embodiment, the controller <NUM> may select to use the output of method 410a if P<NUM> < P<NUM> and may select to use the output of the method 410b if P<NUM> < P<NUM>. It will be appreciated that other performance metrics can be selected and other decision rules may be used.

<FIG> is a flow diagram illustrating an example embodiment of a method <NUM> of determining visual observation of motion. For example, in an example embodiment the robotic device <NUM> executes instructions of the estimation module <NUM> in memory <NUM> to generate visual observations indicative of the robotic device's <NUM> path angle from images captured by imaging sensors. The illustrated embodiment of the method <NUM> is based on epipolar matching of features detected in the images. Epipolar matching estimates translation (e.g., when using multiple cameras), translation direction, and rotation of the camera in one image to another image by an epipolar relationship between matching features of the images. For example, the change of the position and/or orientation of a detected feature in one image relative to another image can provide an indication of the motion of the camera relative to the detected feature. For simplicity, "translation" as used below may refer to translation and/or translation direction. For example, in the case of an example embodiment having a single camera, translation direction can be estimated. Advantageously, epipolar matching may not require knowledge of the structure of the scene that the camera is imaging (although such knowledge may be used). One aspect of the example visual estimator is to find an estimate of the translation that has low uncertainty and enough translation relative to the depth of objects in the scene. For example, this type of estimate may be useful as an observation for processing by a statistical estimation filter. Since epipolar matching may be effective with two images at time, it may use less computation than other visual motion estimation methods, for example, based on structure from motion. In an example embodiment, the robotic device <NUM> executes instructions of the estimation module <NUM> in memory <NUM> for performing the operations of the method <NUM>.

The method <NUM> starts at block <NUM> and proceeds to block <NUM> for initialization by setting a saved feature set to an empty set and by resetting the odometry measurements. For example, the saved feature set may be stored in the memory <NUM> of the robotic device <NUM>. After resetting the odometry, the method <NUM> proceeds to block <NUM> for retrieving the next odometry data and the next camera frame (e.g., image). For example, the robotic device <NUM> can move across the surface and can collect odometry measurements with a first set of sensor that includes odometry sensors and collect the next frame with a second set of sensors that includes one or more cameras.

After collecting the next frame, the method can move from block <NUM> to block <NUM> for extracting a current feature set of the frame. For example, features such as scale invariant feature transformation (SIFT), Harris features, or the like may be extracted from the frame. At block <NUM>, the method <NUM> checks if the saved feature set is the empty set. If the saved features set is the empty set, the method <NUM> proceeds to block <NUM> for storing the current feature set to the saved feature set and for resetting the accumulated odometry. The method <NUM> can return to block <NUM> for retrieving the next odometry data and camera frame.

If, at block <NUM>, the saved feature set is not empty, the method proceeds to block <NUM> for finding epipolar matches between the current feature set and the saved feature set. After finding the epipolar matches, the method <NUM> can proceed to block <NUM> for checking the threshold of the matching. For example, the method <NUM> can check the sufficiency of the matches. In particular, the feature matching may be assisted by information about the expected motion from other sources in the system such as odometry or other visual motion estimators. The matches are accepted if enough features match and the error between the matches (e.g., the residual) is low enough. For example, the matches meet the threshold if the number of the matches exceeds a threshold mount, the uncertainty of the matches is below a certain limit, and/or the difference between the motion of the matches and the motion predicted by odometry is below a threshold. Accordingly, the matches may be based on reliable measurements, and so it is determined that the matches can be used. On the other hand, matches that include too few matching features or large errors between the matches may indicate the presence unreliable measurements and thus it is determined that the matches should not be used.

If the matches do not meet the threshold, the method <NUM> proceeds to block <NUM> for storing the current feature set to the saved feature set and for resetting the accumulated odometry. The method <NUM> can return to block <NUM> for retrieving the next odometry data and camera frame.

If the matches do meet the threshold at block <NUM>, the method proceeds to block <NUM> for computing the rotation and translation of the camera between the saved feature set and the current feature set. For example, the computed rotation and translation of the camera may be based on the epipolar relationship between the current feature set and the saved feature set. For instance, translation and rotation of features in the frame coordinates can be mapped to translation and rotation of, for example, the camera relative to a fixed or inertial frame (such as the room) according to geometric relationships. In example embodiments, the mapping from epipolar coordinates to translation and rotation of the camera can be computed by using numerical optimization or mathematical programming functions or methods.

After computing the rotation and the translation, the method <NUM> proceeds to block <NUM> for determining if the rotation and translation meet some thresholds. If the thresholds are met, the method <NUM> proceeds to block <NUM> for setting a visual observation of motion. For example, if the rotation and translation have a magnitude above a threshold and uncertainty is below a threshold, a visual motion observation may be generated, and the method <NUM> can terminate at block <NUM>. The visual observation of motion can include one or more of an estimated change in pose, an uncertainty of the estimate, and a change in odometry-based pose between the two camera positions.

On the other hand, if the rotation and/or translation have a magnitude below a threshold or the uncertainty is above a threshold, the method <NUM> can move from block <NUM> to block <NUM> for retrieving the next odometry data and camera frame. Accordingly, the saved feature set is not changed and a new image and odometry data is retrieved. This way another observation attempt may be made when there is enough motion between matched frames. One optional advantage, among others, of applying a threshold to the observed rotation and the translation is to improve performance in the presence of image noise (e.g., camera jitter and sensor noise).

As stated above, uncertainty of the rotation and/or translation may be included in the visual observation of motion. Uncertainty information can be useful in some example embodiments for determining the degree upon which visual information can be relied. For example, visual observations associated with relatively low uncertainty may be weighted more heavily than visual observations associated with relatively high uncertainty. To that end, the uncertainty of the visual observation may be determined by various factors, such as the uncertainty associated with the current and/or saved feature sets extracted at block <NUM>. In addition, the uncertainty of the visual observation may be determined by the closeness of the matching found at block <NUM>. Epipolar matches with close matching may have less uncertainty assigned than does epipolar matches with weak matching.

Uncertainty at the feature set level can be based on predetermined uncertainty levels (e.g., design choices and/or assumptions based on the application), on characteristics of the features, and characteristics of the images. For example, certain features may provide higher quality matching than other features. For instances, particular shapes may match more easily than other. For example, features with sharp, high-contrast edges may be associated with less uncertainty than features having only blurry or low-contrast edges. In addition, features having corners may be associated with lower uncertainty.

Uncertainties at the feature level can be mapped to uncertainties at the rotation and translation level (e.g., the visual observation level). For example, the uncertainties can be input into the function of block <NUM> for mapping the epipolar domain to the translation and rotation domain.

<FIG> is a flow diagram illustrating an example embodiment of a method <NUM> of <FIG> of executing a statistical filter. In the illustrated embodiment, an IEKF may be used to track a normalized carpet drift vector (NCDV). The NCDV is the carpet drift vector per unit of translation. The NCDV may be a property of the floor surface and may be independent of how far the robot travels and the robot's orientation. The IEKF of the illustrated embodiment may be used to estimate of the NCDV, as described below in further detail. For example, the state estimate x of the IEKF can correspond to an estimate of the NCDV, and the covariance of the state x may be denoted by P. One optional advantage of using an IEKF over a standard EKF is improved accuracy by reducing the errors due to linearization. It will be appreciated by one skilled in the art that other estimation techniques could also be used. In an example embodiment, the robotic device <NUM> executes instructions of the estimation module <NUM> in memory <NUM> for performing the operations of the method <NUM>.

Accordingly, the method <NUM> starts at block <NUM> and proceeds block <NUM> to retrieve the visual observation of motion. For example, the visual observations may be determined according to method <NUM> described in connection with <FIG>. The visual motion observation may contain information related to the estimated relative pose Ω of the robotic device <NUM> from time ti to ti+<NUM>. Pose may refer to translation, translation direction, and/or orientation information. For example, the visual motion observation may be transformed into the following form: a relative pose Ω estimated from odometry and associated covariance B; a direction θ of motion in the ground plane estimated by image processing (e.g., by block <NUM> of <FIG>) and associated variance r. If the camera coordinate frame and robot coordinate frame are not the same, one skilled in the art would appreciate that the appropriate transformation should be applied to the visual motion estimate and its associated covariance to put it in the appropriate coordinates (e.g., in the room coordinates). Also given is the estimated orientation of the robot in the form of a rotation matrix M which rotates the state x into the coordinate frame of Ω at ti+<NUM>.

After retrieving the visual observation data at block <NUM>, the method <NUM> proceeds to block <NUM> for estimating an angle θ̃ of travel based on odometry and a current state estimate x̂. Formulaically, the following equations may be used to generate the estimates of the angle θ̃ of travel based on odometry and the current state estimate x̂: <MAT> <MAT> <MAT> <MAT>.

In Equation <NUM>, the distance d is the estimated distance traveled between ti to ti+<NUM> based on odometry. In Equation <NUM>, the components h<NUM> and h<NUM> are the components of vector h.

After estimating the angle of travel θ̃ , the method <NUM> moves from block <NUM> to block <NUM> for computing the Jacobian Jd of the change in the predicted angle θ̃ with respect to the change in state x̂. For example, in some embodiments the Jacobian may be computed as <MAT>.

The method <NUM> proceeds from block <NUM> to block <NUM> to compute the innovation v and innovation variance Q. For example, in some embodiments the innovation v and innovation variance Q may be computed by using the following equations: <MAT> <MAT> <MAT>.

After the innovation v and innovation variance Q become available, the method <NUM> proceeds from block <NUM> to gate the observation by comparing the innovation v to the innovation variance Q. The method <NUM> proceeds from block <NUM> to block <NUM> to update the new mean x̂next. For example, the new mean x̂next may be the mean x̂ for the next iteration. In an example embodiment, the new mean x̂next may be computed by the following equations: <MAT> <MAT> <MAT> <MAT>.

After completing one iteration of blocks <NUM>-<NUM>, the method <NUM> proceeds to block <NUM> to check whether the method should proceed with another iteration or terminate at block <NUM>. If the iterations are completed, the new state x = x̂next and variance P = (Y + P-<NUM>)-<NUM> may be set. The number of iterations for the IEKF may be determined based in whole or in part on difference in state between iterations, or based on a fixed number of iterations.

A corrected odometry estimate may be obtained by applying the NCDV to the odometry at each time step. For example, given the odometry change in pose Ω and the estimated NCDV x, the corrected odometry change in pose may be estimated by Ωc = Ω + d · Mx. As previously stated above, the quantity d is the estimated distance traveled from odometry and M is the estimated orientation of the robot in the form of a rotation matrix that rotates the estimated NCDV x into the coordinate frame of Ω.

Thus, systems and methods are described for estimating drift, such as carpet drift experienced by a robot moving across a carpet, and for compensating for such carpet drift.

The foregoing description and claims may refer to elements or features as being "connected" or "coupled" together. As used herein, unless expressly stated otherwise, "connected" means that one element/feature is directly or indirectly connected to another element/feature, and not necessarily mechanically. Likewise, unless expressly stated otherwise, "coupled" means that one element/feature is directly or indirectly coupled to another element/feature, and not necessarily mechanically. Thus, although the various schematics shown in the figures depict example arrangements of elements and components, additional intervening elements, devices, features, or components may be present in an actual embodiment (assuming that the functionality of the depicted circuits is not adversely affected).

The methods and processes described herein may have fewer or additional steps or states and the steps or states may be performed in a different order. Not all steps or states need to be reached. The methods and processes described herein may be embodied in, and fully or partially automated via, software code modules executed by one or more general and/or specialized computers. The code modules may be stored in any type of computer-readable medium or other computer storage device. The results of the disclosed methods may be stored in any type of computer data repository that use volatile and/or non-volatile memory (e.g., magnetic disk storage, optical storage, EEPROM and/or solid state RAM).

Claim 1:
A method for estimating a carpet drift or a carpet drift vector of an autonomous cleaning robot,
wherein the autonomous cleaning robot includes a cleaning mechanism (<NUM>) configured to capture dirt from a surface, the method comprising:
estimating an actual motion of an autonomous robot (<NUM>) using an image sensor (<NUM>);
estimating a carpet drift or a carpet drift vector by comparing a desired motion and the actual motion; and
using the estimate of the carpet drift or the carpet drift vector to improve or correct a motion estimate of the autonomous robot,
wherein the estimate of the carpet drift or the carpet drift vector is used with a motor controller to compensate for the effects of carpet grain and/or is used to generate a correction term to adjust odometry data,
characterized in that:
the image sensor is a camera observing objects in a scene the autonomous cleaning robot operates in.