Method and apparatus for combining data to construct a floor plan

[0001] This application is a Continuation in Part of U.S. Non-Provisional application Ser. No. 16/594,923, filed Oct. 7, 2019, which is a Continuation of U.S. Non-Provisional patent application Ser. No. 16/048,179, filed Jul. 27, 2018, which claims the benefit of Provisional Patent Application Nos. 62/537,858, filed Jul. 27, 2017; 62/618,964, filed Jan. 18, 2018; and 62/591,219, filed Nov. 28, 2017, each of which is hereby incorporated by reference. This application claims the benefit of U.S. Provisional Patent Application Nos. 62/914,190, filed Oct. 11, 2019; 62/933,882, filed Nov. 11, 2019; 62/942,237, filed Dec. 2, 2019; 62/952,376, filed Dec. 22, 2019; 62/952,384, filed Dec. 22, 2019; 62/986,946, filed Mar. 9, 2020; and 63/037,465, filed Jun. 10, 2020, each of which is hereby incorporated herein by reference.

[0002] In this patent, certain U.S. patents, U.S. patent applications, or other materials (e.g., articles) have been incorporated by reference. Specifically, U.S. patent application Ser. Nos. 15/272,752, 15/949,708, 16/667,461, 16/277,991, 16/048,179, 16/048,185, 16/163,541, 16/851,614, 16/163,562, 16/597,945, 16/724,328, 16/163,508, 16/185,000, 16/109,617, 16/051,328, 15/449,660, 16/667,206, 16/041,286, 16/422,234,15/406,890, 16/796,719, 14/673,633, 15/676,888, 16/558,047, 15/449,531, 16/446,574, 16/219,647, 16/163,530, 16/297,508, 16/418,988, 15/614,284, 16/554,040, 15/955,480, 15/425,130, 15/955,344, 15/243,783, 15/954,335, 15/954,410, 16/832,221, 15/257,798, 16/525,137, 15/674,310, 15/224,442, 15/683,255, 16/880,644, 15/048,827, 14/817,952, 15/619,449, 16/198,393, 16/599,169, 15/981,643, 16/747,334, 15/986,670, 16/568,367, 15/444,966, 15/447,450, 15/447,623, 15/951,096, 16/270,489, 16/130,880, 14/948,620, 16/402,122, 16/127,038, 14/922,143, 15/878,228, 15/924,176, 16/024,263, 16/203,385, 15/647,472, 15/462,839, 16/239,410, 16/230,805, 16/411,771, 16/578,549, 16/129,757, 16/245,998, 16/127,038, 16/243,524, 16/244,833, 16/751,115, 16/353,019, 15/447,122, 16/393,921, 16/389,797, 16/509,099, 16/440,904, 15/673,176, 16/058,026, 14/970,791, 16/375,968, 15/432,722, 16/238,314, 14/941,385, 16/279,699, 16/041,470, 15/006,434, 15/410,624, 16/504,012, 16/389,797, 15/917,096, 15/706,523, 16/241,436, 15/377,674, 16/883,327, 16/427,317, 16/850,269, 16/179,855, 15/071,069, 16/186,499, 15/976,853, 15/442,992, 16/570,242, 16/832,180, 16/399,368, 14/997,801, 16/726,471, 15/924,174, 16/212,463, 16/212,468, 14/820,505, 16/221,425, and 15/986,670, are hereby incorporated herein by reference. The text of such U.S. patents, U.S. patent applications, and other materials is, however, only incorporated by reference to the extent that no conflict exists between such material and the statements and drawings set forth herein. In the event of such conflict, the text of the present document governs, and terms in this document should not be given a narrower reading in virtue of the way in which those terms are used in other materials incorporated by reference.

[0003] The disclosure relates to autonomous robots.

[0004] Autonomous or semi-autonomous robotic devices are increasingly used within consumer homes and commercial establishments. Such robotic devices may include a drone, a robotic vacuum cleaner, a robotic lawn mower, a robotic mop, or other robotic devices. To operate autonomously or with minimal (or less than fully manual) input and/or external control within an environment, methods such as mapping, localization, object recognition, and path planning methods, among others, are required such that robotic devices may autonomously create a map of the environment, subsequently use the map for navigation, and devise intelligent path and task plans for efficient navigation and task completion.

[0005] The following presents a simplified summary of some embodiments of the techniques described herein in order to provide a basic understanding of the invention. This summary is not an extensive overview of the invention. It is not intended to identify key/critical elements of the invention or to delineate the scope of the invention. Its sole purpose is to present some embodiments of the invention in a simplified form as a prelude to the more detailed description that is presented below.

[0006] Some aspects provide is a robot for perceiving a spatial model of an environment, including: an actuator configured to move the robot through the environment; at least one sensor mechanically coupled to the robot; a processor configured to receive sensed data from the at least one sensor and control the actuator; and memory storing instructions that when executed by the processor effectuates operations including: capturing a plurality of data by the at least one sensor of the robot while the robot moves within the environment, wherein: the plurality of data comprises first data comprising pixel characteristics indicative of features of the environment and second data indicative of depth to objects in the environment; the first data and the second data are captured by at least one of: a same sensor; a same sensor in combination with structured light emissions; and at least one depth sensor; the plurality of data is captured from different positions within the environment through which the robot moves, the plurality of data corresponding with respective positions from which the plurality of data was captured; and the plurality of data captured from the respective positions within the environment corresponds to respective fields of view from which the plurality of data was captured; and aligning, with a processor of the robot, the plurality of data as it is captured to more accurately perceive the spatial model of the environment.

[0007] Some aspects include a method of perceiving a spatial model of an environment, including: capturing a plurality of data by at least one sensor of a robot while the robot moves within the environment, wherein: the plurality of data comprises first data comprising pixel characteristics indicative of features of the environment and second data indicative of depth to objects in the environment; the first data and the second data are captured by at least one of: a same sensor; a same sensor in combination with structured light emissions; and at least one depth sensor and at least one image sensor; the plurality of data is captured from different positions within the environment through which the robot moves, the plurality of data corresponding with respective positions from which the plurality of data was captured; and the plurality of data captured from the respective positions within the environment corresponds to respective fields of view from which the plurality of data was captured; and aligning, with a processor of the robot, the plurality of data as it is captured to more accurately perceive the spatial model of the environment.

[0242] The present inventions will now be described in detail with reference to a few embodiments thereof as illustrated in the accompanying drawings. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present inventions. It will be apparent, however, to one skilled in the art, that the present inventions, or subsets thereof, may be practiced without some or all of these specific details. In other instances, well known process steps and/or structures have not been described in detail in order to not unnecessarily obscure the present inventions. Further, it should be emphasized that several inventive techniques are described, and embodiments are not limited to systems implanting all of those techniques, as various cost and engineering trade-offs may warrant systems that only afford a subset of the benefits described herein or that will be apparent to one of ordinary skill in the art.

[0243] Some embodiments may provide an autonomous or semi-autonomous robot including communication, mobility, actuation, and processing elements. In some embodiments, the robot may be wheeled (e.g., rigidly fixed, suspended fixed, steerable, suspended steerable, caster, or suspended caster), legged, or tank tracked. In some embodiments, the wheels, legs, tracks, etc. of the robot may be controlled individually or controlled in pairs (e.g., like cars) or in groups of other sizes, such as three or four as in omnidirectional wheels. In some embodiments, the robot may use differential-drive wherein two fixed wheels have a common axis of rotation and angular velocities of the two wheels are equal and opposite such that the robot may rotate on the spot. In some embodiments, the robot may include a terminal device such as those on computers, mobile phones, tablets, or smart wearable devices. In some embodiments, the robot may include one or more of a casing, a chassis including a set of wheels, a motor to drive the wheels, a receiver that acquires signals transmitted from, for example, a transmitting beacon, a transmitter for transmitting signals, a processor, a memory storing instructions that when executed by the processor effectuates robotic operations, a controller, a plurality of sensors (e.g., tactile sensor, obstacle sensor, temperature sensor, imaging sensor, light detection and ranging (LIDAR) sensor, camera, depth sensor, time-of-flight (TOF) sensor, TSSP sensor, optical tracking sensor, sonar sensor, ultrasound sensor, laser sensor, light emitting diode (LED) sensor, etc.), network or wireless communications, radio frequency (RF) communications, power management such as a rechargeable battery, solar panels, or fuel, and one or more clock or synchronizing devices. In some cases, the robot may include communication means such as Wi-Fi, Worldwide Interoperability for Microwave Access (WiMax), WiMax mobile, wireless, cellular, Bluetooth, RF, etc. In some cases, the robot may support the use of a 360 degrees LIDAR and a depth camera with limited field of view. In some cases, the robot may support proprioceptive sensors (e.g., independently or in fusion), odometry devices, optical tracking sensors, smart phone inertial measurement units (IMU), and gyroscopes. In some cases, the robot may include at least one cleaning tool (e.g., disinfectant sprayer, brush, mop, scrubber, steam mop, cleaning pad, ultraviolet (UV) sterilizer, etc.). The processor may, for example, receive and process data from internal or external sensors, execute commands based on data received, control motors such as wheel motors, map the environment, localize the robot, determine division of the environment into zones, and determine movement paths. In some cases, the robot may include a microcontroller on which computer code required for executing the methods and techniques described herein may be stored.

[0244] In some embodiments, at least a portion of the sensors of the robot are provided in a sensor array, wherein the at least a portion of sensors are coupled to a flexible, semi-flexible, or rigid frame. In some embodiments, the frame is fixed to a chassis or casing of the robot. In some embodiments, the sensors are positioned along the frame such that the field of view of the robot is maximized while the cross-talk or interference between sensors is minimized. In some cases, a component may be placed between adjacent sensors to minimize cross-talk or interference. In some embodiments, the robot may include sensors to detect or sense acceleration, angular and linear movement, motion, static and dynamic obstacles, temperature, humidity, water, pollution, particles in the air, supplied power, proximity, external motion, device motion, sound signals, ultrasound signals, light signals, fire, smoke, carbon monoxide, global-positioning-satellite (GPS) signals, radio-frequency (RF) signals, other electromagnetic signals or fields, visual features, textures, optical character recognition (OCR) signals, spectrum meters, system status, cliffs or edges, types of flooring, and the like. In some embodiments, a microprocessor or a microcontroller of the robot may poll a variety of sensors at intervals. In some embodiments, more than one sensor of the robot may be used to provide additional measurement points to further enhance accuracy of estimations or predictions. In some embodiments, the additional sensors of the robot may be connected to the microprocessor or microcontroller. In some embodiments, the additional sensors may be complementary to other sensing methods of the robot.

[0245] In some embodiments, the MCU of the robot (e.g., ARM Cortex M7 MCU, model SAM70) may provide an onboard camera controller. In some embodiments, the camera may be communicatively coupled with a microprocessor or microcontroller. In some embodiments, the onboard camera controller may receive data from the environment and may send the data to the MCU, an additional CPU/MCU, or to the cloud for processing. In some embodiments, the camera controller may be coupled with a laser pointer that emits a structured light pattern onto surfaces of objects within the environment. In some embodiments, that the camera may use the structured light pattern to create a three dimensional model of the objects. In some embodiments, the structured light pattern may be emitted onto a face of a person, the camera may capture an image of the structured light pattern projected onto the face, and the processor may identify the face of the person more accurately than when using an image without the structured light pattern. In some embodiments, frames captured by the camera may be time-multiplexed to serve the purpose of a camera and depth camera in a single device. In some embodiments, several components may exist separately, such as an image sensor, imaging module, depth module, depth sensor, etc. and data from the different the components may be combined in an appropriate data structure. For example, the processor of the robot may transmit image or video data captured by the camera of the robot for video conferencing while also displaying video conference participants on the touch screen display. The processor may use depth information collected by the same camera to maintain the position of the user in the middle of the frame of the camera seen by video conferencing participants. The processor may maintain the position of the user in the middle of the frame of the camera by zooming in and out, using image processing to correct the image, and/or by the robot moving and making angular and linear position adjustments.

[0246] In embodiments, the camera of the robot may be a charge-coupled device (CCD) or a complementary metal-oxide semiconductor (CMOS). In some embodiments, the camera may receive ambient light from the environment or a combination of ambient light and a light pattern projected into the surroundings by an LED, IR light, projector, etc., either directly or through a lens. In some embodiments, the processor may convert the captured light into data representing an image, depth, heat, presence of objects, etc. In some embodiments, the camera may include various optical and non-optical imaging devices, like a depth camera, stereovision camera, time-of-flight camera, or any other type of camera that outputs data from which depth to objects can be inferred over a field of view, or any other type of camera capable of generating a pixmap, or any device whose output data may be used in perceiving the environment. The camera may also be combined with an infrared (IR) illuminator (such as a structured light projector), and depth to objects may be inferred from images captured of objects onto which IR light is projected (e.g., based on distortions in a pattern of structured light). Examples of methods for estimating depths to objects using at least one IR laser, at least one image sensor, and an image processor are detailed in U.S. patent application Ser. Nos. 15/243,783, 15/954,335, 15/954,410, 16/832,221, 15/257,798, 16/525,137, 15/674,310, 15/224,442, 15/683,255, 16/880,644, 15/447,122, and 16/393,921, the entire contents of each of which are hereby incorporated by reference. Other imaging devices capable of observing depth to objects may also be used, such as ultrasonic sensors, sonar, LIDAR, and LADAR devices. Thus, various combinations of one or more cameras and sensors may be used.

[0247] In embodiments, the camera of the robot (e.g., depth camera or other camera) may be positioned in any area of the robot and in various orientations. For example, sensors may be positioned on a back, a front, a side, a bottom, and/or a top of the robot. Also, sensors may be oriented upwards, downwards, sideways, and/or in any specified angle. In some cases, the position of sensors may be complementary to one other to increase the FOV of the robot or enhance images captured in various FOVs.

[0248] In some embodiments, the camera of the robot may capture still images and record videos and may be a depth camera. For example, a camera may be used to capture images or videos in a first time interval and may be used as a depth camera emitting structured light in a second time interval. Given high frame rates of cameras some frame captures may be time multiplexed into two or more types of sensing. In some embodiments, the camera output may be provided to an image processor for use by a user and to a microcontroller of the camera for depth sensing, obstacle detection, presence detection, etc. In some embodiments, the camera output may be processed locally on the robot by a processor that combines standard image processing functions and user presence detection functions. Alternatively, in some embodiments, the video/image output from the camera may be streamed to a host for further processing or visual usage.

[0249] In some embodiments, images captured by the camera may be processed to identify objects or faces, as further described below. For example, the microprocessor may identify a face in an image and perform an image search in a database on the cloud to identify an owner of the robot. In some embodiments, the camera may include an integrated processor. For example, object detection and face recognition may be executed on an integrated processor of a camera. In some embodiments, the camera may capture still images and record videos and may be a depth camera. For example, a camera may be used to capture images or videos in a first time interval and may be used as a depth camera emitting structured light in a second time interval. Given high frame rates of cameras some frame captures may be time multiplexed into two or more types of sensing. In some embodiments, the camera may be used to capture still images and video by a user of the robot. For example, a user may use the camera of the robot to perform a video chat, wherein the robot may optimally position itself to face the user. In embodiments, various configurations (e.g., types of camera, number of cameras, internal or external cameras, etc.) that allow for desired types of sensing (e.g., distance, obstacle, presence) and desired functions (e.g., sensing and capturing still images and videos) may be used to provide a better user experience. In some embodiments, the camera of the robot may have different fields of view (FOV). For example, a camera may have a horizontal FOV up to or greater than 90 degrees and a vertical FOV up to or greater than 20 degrees. In another example, the camera may have a horizontal FOV between 60-120 degrees and a vertical FOV between 10-80 degrees. In some embodiments, the camera may include lenses and optical arrangements of lenses to increase the FOV vertically or horizontally. For example, the camera may include fish eye lenses to achieve a greater field of view. In some embodiments, the robot may include more than one camera and each camera may be used for a different function. For example, one camera may be used in establishing a perimeter of the environment, a second camera may be used for obstacle sensing, and a third camera may be used for presence sensing. In another example, a depth camera may be used in addition to a main camera. The depth camera may be of various forms. In some embodiments, the camera output may be provided to an image processor for use by a user and to a microcontroller of the camera for depth sensing, obstacle detection, presence detection, etc. In some embodiments, the camera output may be processed locally on the robot by a processor that combine standard image processing functions and user presence detection functions. Alternatively, in some embodiments, the video/image output from the camera may be streamed to a host for processing further or visual usage. In some embodiments, there may be different options for communication and data processing between a dedicated image processor and an obstacle detecting co-processor. For example, a presence of an obstacle in the FOV of a camera may be detected, then a distance to the obstacle may be determined, then the type of obstacle may be determined (e.g., human, pet, table, wire, or another object), then, in the case where the obstacle type is a human, facial recognition may be performed to identify the human. All the information may be processed in multiple layers of abstraction. In embodiments, information may be processed by local microcontrollers, microprocessors, GPUs, on the cloud, or on a central home control unit.

[0250] In some embodiments, the robot may include a controller, a multiplexer, and an array of light emitting diodes (LEDs) that may operate in a time division multiplex to create a structured light which the camera may capture at a desired time slot. In some embodiments, a suitable software filter may be used at each time interval to instruct the LED lights to alternate in a particular order or combination and the camera to capture images at a desirable time slot. In some embodiments, a micro electrical-mechanical device may be used to multiplex one or more of the LEDs such that fields of view of one or more cameras may be covered. In some embodiments, the LEDs may operate in any suitable range of wavelengths and frequencies, such as a near-infrared region of the electromagnetic spectrum. In some embodiments, pulses of light may be emitted at a desired frequency and the phase shift of the reflected light signal may be measured. In some sensor types, the emitted lights may be in the form of square waves or other waveforms. A light may be mixed with a sine wave and a cosine wave that may be synchronized with the LED modulation. Then, a first and a second object present in the FOV of the sensor, each of which is positioned at a different distance, may produce a different phase shift that may be associated with their respective distance.

[0251] In some embodiments, the robot may include a tiered sensing system, wherein data of a first sensor may be used to initially infer a result and data of a second sensor, complementary to the first sensor, may be used to confirm the inferred result. In some embodiments, the robot may include a conditional sensing system, wherein data of a first sensor may be used to initially infer a result and a second sensor may be operated based on the result being successful or unsuccessful. Additionally, in some embodiments, data collected with the first sensor may be used to determine if data collected with the second sensor is needed or preferred. In some embodiments, the robot may include a state machine sensing system, wherein data from a first sensor may be used to initially infer a result and if a condition is met, a second sensor may be operated. In some embodiments, the robot may include a poll based sensing system wherein data from a first sensor may be used to initially infer a result, and if a condition is met, a second sensor may be operated. In some embodiments, the robot may include a silent synapse activator sensing system, wherein data from a first a sensor may be used to make an observation but the observation does not cause an actuation. In some embodiments, an actuation occurs when a second similar sensing occurs within a predefined time period. In some embodiments, there may be variations wherein a microcontroller may ignore a first sensor reading and may allow processing of a second (or third) sensor reading. For example, a missed light reflection from the floor may not be interpreted to be a cliff unless a second light reflection from the floor is missed. In some embodiments, a Hebbian based sensing method may be used to create correlations between different types of sensing. For example, in Hebb's theory, any two cells repeatedly active at the same time may become associated such that activity in one neuron facilitates activity in the other. When one cell repeatedly assists in firing another cell, an axon of the first cell may develop (or enlarge) synaptic knobs in contact with the soma of the second cell. In some embodiments, Hebb's principle may be used to determine how to alter the weights between artificial neurons (i.e., nodes) of an artificial neural network. In some embodiments, the weight between two neurons increases when two neurons activate simultaneously and decreases when they activate at different times. For example, two nodes that are both positive or negative may have strong positive weights while nodes with opposite sign may have strong negative weights. In some embodiments, the weight ω_ij=x_ix_j may be determined, wherein ω_ij is the weight of the connection from neuron j to neuron i and x_i the input for neuron i. For binary neurons, connections may be set to one when connected neurons have the same activation for a pattern. In some embodiments, the weight ω_ij may be determined using

[0252] $\frac{1}{p}\sum _{k=1}^p{x}_i^k{x}_j^k,$
wherein p is the number of training patterns, and x_i^k is input k for neuron i. In some embodiments, Hebb's rule Δω_i=ηx_iy may be used, wherein Δω_i is the change in synaptic weight i, η is a learning rate, and y a postsynaptic response. In some embodiments, the postsynaptic response may be determined using y=Σ_yω_jx_j. In some embodiments, other methods such as BCM theory, Oja's rule, or generalized Hebbian algorithm may be used.

[0253] In some embodiments, a sensor of the robot (e.g., two-and-a-half dimensional LIDAR) observes the environment in layers. For example, FIG. 1A illustrates a robot 6400 taking sensor readings 6401 using a sensor, such as a two-and-a-half dimensional LIDAR. The sensor may observe the environment in layers. For example, FIG. 1B illustrates an example of a first layer 6402 observed by the sensor at a height 10 cm above the driving surface, a second layer 6403 at a height 40 cm above the driving surface, a third layer 6404 at a height 80 cm above the driving surface, a fourth layer 6405 at a height 120 cm above the driving surface, and a fifth layer 6406 at a height 140 cm from the driving surface, corresponding with the five measurement lines in FIG. 1A. In some embodiments, the processor of the robot determines an imputation of the layers in between those observed by the sensor based on the set of layers S={layer 1, layer 2, layer 3, . . . } observed by the sensor. In some embodiments, the processor may generate a set of layers 5′={layer 1′, layer 2′, layer 3′, . . . } in between the layers observed by the sensor, wherein layer 1′, layer 2′, layer 3′ may correspond with layers that are located a predetermined height above layer 1, layer 2, layer 3, respectively. In some embodiments, the processor may combine the set of layers observed by the sensor and the set of layers in between those observed by the sensor, S′+S={layer1, layer 1′, layer2, layer 2′, layer3, layer 3′, . . . }. In some embodiments, the processor of the robot may therefore generate a complete three dimensional map (or two-and-a-half dimensional when the height of the map is limited to a particular range) with any desired resolution. This may be useful in avoiding analysis of unwanted or useless data during three dimensional processing of the visual data captured by a camera. In some embodiments, data may be transmitted in a medium such as bits, each comprised of a zero or one. In some embodiments, the processor of the robot may use entropy to quantify the average amount of information or surprise (or unpredictability) associated with the transmitted data. For example, if compression of data is lossless, wherein the entire original message transmitted can be recovered entirely by decompression, the compressed data has the same quantity of information but is communicated in fewer characters. In such cases, there is more information per character, and hence higher entropy. In some embodiments, the processor may use Shannon's entropy to quantify an amount of information in a medium. In some embodiments, the processor may use Shannon's entropy in processing, storage, transmission of data, or manipulation of the data. For example, the processor may use Shannon's entropy to quantify the absolute minimum amount of storage and transmission needed for transmitting, computing, or storing any information and to compare and identify different possible ways of representing the information in fewer number of bits. In some embodiments, the processor may determine entropy using H(X)=E[−log₂ p(x_i)], H(X)=−∫p(x_i)log₂ p(x_i)dx in a continuous form, or H(X)=−Σ_ip(x_i)log₂ p(x_i) in a discrete form, wherein H(X) is Shannon's entropy of random variable X with possible outcomes x_i and p(x₁) is the probability of x_i occurring. In the discrete case, −log₂ p(x) is the number of bits required to encode x_i.

[0254] In some embodiments, the arrangement of LEDs, proximity sensors, and cameras of the robot may be directed towards a particular FOV. In some embodiments, at least some adjacent sensors of the robot may have overlapping FOVs. In some embodiments, at least some sensors may have a FOV that does not overlap with a FOV of another sensor. In some embodiments, sensors may be coupled to a curved structure to form a sensor array wherein sensors have diverging FOVs. Given the geometry of the robot is known, implementation and arrangement of sensors may be chosen based on the purpose of the sensors and the application.

[0255] In some embodiments, some peripherals or sensors may require calibration before information collected by the sensors is usable by the processor. For example, traditionally, robots may be calibrated on the assembly line. However, the calibration process is time consuming and slows production, adding costs to production. Additionally, some environmental parameters of the environment within which the peripherals or sensors are calibrated may impact the readings of the sensors when operating in other surroundings. For example, a pressure sensor may experience different atmospheric pressure levels depending on its proximity to the ocean or a mountain. Some embodiments may include a method to self-calibrate sensors. For instance, some embodiments may self-calibrate the gyroscope and wheel encoder.

[0256] In some embodiments, sensor may be conditioned. A function ƒ(x)=A⁻¹ x, given A∈R^n×n with an eigenvalue decomposition may have a condition number

[0257] $\frac{{\lambda }_i}{{\lambda }_j}.$
The condition number may be the ratio of the largest eigenvalue to the smallest eigenvalue. A large condition number may indicate that the matrix inversion is very sensitive to error in the input. In some cases, a small error may propagate. The speed at which the output of a function changes with the input the function receives is affected by the ability of a sensor to provide proper information to the algorithm. This may be known as sensor conditioning. For example, poor conditioning may occur when a small change in input causes a significant change in the output. For instance, rounding errors in the input may have a large impact on the interpretation of the data. Consider the functions y=ƒ(x) and

[0258] $\begin{array}{cc}{f}^{\prime }\left(x\right)=\frac{\mathrm{dy}}{\mathrm{dx}},& \end{array}$
wherein dy/dx is the slope of ƒ(x) at point x. Given a small error ∈, ƒ(x+∈)≈ƒ(x)+∈ƒ′(x). In some embodiments, the processor may use partial derivatives to gauge effects of changes in the input on the output. The use of a gradient may be a generalization of a derivative in respect to a vector. The gradient ∇_xƒ(x) of the function ƒ(x) may be a vector including all first partial derivatives. The matrix including all first partial derivatives may be the Jacobian while the matrix including all the second derivatives may be the Hessian,

[0259] $\begin{array}{cc}{H\left(f\left(x\right)\right)}_{i,j}=\frac{{\partial }^2}{\partial x_i\partial x_j}f\left(x\right).& \end{array}$
The second derivatives may indicate how the first derivatives may change in response to changing the input knob, which may be visualized by a curvature.

[0260] In some embodiments, any of a Digital Signal Processor (DSP) and Single Input-Multiple Data (SIMD) architecture may be used. In some embodiments, any of a Reduced Instruction Set (RISC) system, an emulated hardware environment, and a Complex Instruction Set (CISC) system using various components such as a Graphic Processing Unit (GPU) and different types of memory (e.g., Hash, RAM, double data rate (DDR) random access memory (RAM), etc.) may be used. In some embodiments, various interfaces, such as Inter-Integrated Circuit (I2C), Universal Asynchronous Receiver/Transmitter (UART), Universal Synchronous/Asynchronous Receiver/Transmitter (USART), Universal Serial Bus (USB), and Camera Serial Interface (CSI), may be used. In embodiments, each of the interfaces may have an associated speed (i.e., data rate). For example, thirty 1 MB images captured per second results in the transfer of data at a speed of 30 MB per second. In some embodiments, memory allocation may be used to buffer incoming or outgoing data or images. In some embodiments, there may be more than one buffer working in parallel, round robin, or in serial. In some embodiments, at least some incoming data may be time stamped, such as images or readings from odometry sensors, IMU sensor, gyroscope sensor, LIDAR sensor, etc.

[0261] In some embodiments, the robot may include cable management infrastructure. For example, the robot may include shelves with one or more cables extending from a main cable path and channeled through apertures available to a user with access to the corresponding shelf. In some embodiments, there may be more than one cable per shelf and each cable may include a different type of connector. In some embodiments, some cables may be capable of transmitting data at the same time. In some embodiments, data cables such as USB cables, mini-USB cables, firewire cables, category 5 (CAT-5) cables, CAT-6 cables, or other cables may be used to transfer power. In some embodiments, to protect the security and privacy of users plugging their mobile device into the cables, all data may be copied or erased. Alternatively, in some embodiments, inductive power transfer without the use of cables may be used.

[0262] In some embodiments, the robot may include various software components and/or drivers for controlling and managing general system tasks (e.g., memory management, storage device control, power management, etc.) and facilitating communication between various hardware and software components and data received by various software components from RF and/or external ports such as USB, firewire, or Ethernet. In some embodiments, the robot may include capacitate buttons, push buttons, rocker buttons, dials, slider switches, joysticks, click wheels, keyboard, an infrared port, a USB port, and a pointer device such as a mouse, a laser pointer, motion detector (e.g., a motion detector for detecting a spiral motion of fingers), etc. In embodiments, different interactions with user interfaces of the robot may provide different reactions or results from the robot. For example, a long press, a short press, and/or a press with increased pressure of a button may each provide different reactions or results from the robot. In some cases, an action may be enacted upon the release of a button or upon pressing a button.

[0263] FIG. 2A illustrates an example of a robot including sensor windows 100 behind which sensors are positioned, sensors 101 (e.g., camera, laser emitter, TOF sensor, IR sensors, range finders, LIDAR, depth cameras, etc.), user interface 102, and bumper 103. FIG. 2B illustrates internal components of the robot including sensors 101 of sensor array 104, PCB 105, wheel modules each including suspension 106, battery 107, floor sensor 108, and wheel 109. In some embodiments, a processor of the robot may use data collected by various sensors to devise, through various phases of processing, a polymorphic path plan. FIG. 3 illustrates another example of a robot, specifically an underside of a robotic cleaner including rotating screw compressor type dual brushes 200, drive wheels 201, castor wheel 202, peripheral brush 203, sensors on an underside of the robot 204, USB port 205, power port 206, power button 207, speaker 208, and a microphone 209. Indentations 210 may be indentations for fingers of a user for lifting the robot. In some embodiments, the indentations may be coated with a material different than the underside of the robot such that a user may easily distinguish the indentations. In this example, there are three sensors, one in the front and two on the side. The sensors may be used to sense presence and a type of driving surface. In some embodiments, some sensors are positioned on the front, sides, and underneath the robot. In some embodiments, the robot may include one or more castor wheels. In some embodiments, the wheels of the robot include a wheel suspension system. In some embodiments, the wheel suspension includes a trailing arm suspension coupled to each wheel and positioned between the wheel and perimeter of the robot chassis. An example of a dual wheel suspension system is described in U.S. patent application Ser. Nos. 15/951,096 and 16/270,489, the entire contents of which are hereby incorporated by reference. Other examples of wheel suspension systems that may be used are described in U.S. patent application Ser. No. 16/389,797, the entire contents of which is hereby incorporated by reference. In some embodiments, the different wheel suspension systems may be used independently or in combination. In some embodiments, one or more wheels of the robot may be driven by one or more electric motors. In some embodiments, the wheels of the robot are mecanum wheels. Examples of wheels of the robot are described in U.S. patent application Ser. Nos. 15/444,966 and 15/447,623, the entire contents of which are hereby incorporated by reference. In some embodiments, the robot may include an integrated bumper, such as those described in U.S. patent application Ser. Nos. 15/924,174, 16/212,463, 16/212,468, the entire contents of which are hereby incorporated by reference.

[0264] In some embodiments, peripheral brushes of a robotic cleaner, such as peripheral brush 203 of the robotic cleaner in FIG. 3, may implement strategic methods for bristle attachment to reduce the loss of bristles during operation. For example, FIGS. 4A and 4B illustrate one method for bristle attachment wherein each bristle bundle 700 may be wrapped around a cylinder 701 coupled to a main body 702 of the peripheral brush. Each bristle bundle 700 may be wrapped around the cylinder 701 at least once and then knotted with itself to secure its attachment to the main body 702 of the peripheral brush. FIG. 4C illustrates another method for bristle attachment wherein each bristle bundle 703 may be threaded in and out of main body 702 to create two adjacent bristle bundles which may reduce the loss of bristles during operation. In some cases, the portion of each bristle bundle within the main body 702 may attached to the inside of main body 702 using glue, stitching, or another means. FIGS. 4D-4F illustrate another method for bristle attachments wherein bristle bundles 704 positioned opposite to one another are hooked together, as illustrated in FIG. 4F. In all embodiments, the number of bristles in each bristle bundle may vary. Examples of side brushes and a main brush of the robot are described in U.S. patent application Ser. Nos. 15/924,176, 16/024,263, 16/203,385, 15/647,472, 14/922,143, 15/878,228, and 15/462,839.

[0265] In embodiments, floor sensors, such as those illustrated in FIGS. 2B and 3, may be positioned in different locations on an underside of the robot and may also have different orientations and sizes. FIGS. 5A-5D illustrate examples of alternative positions (e.g., displaced at some distance from the wheel or immediately adjacent to the wheel) and orientations (e.g., vertical or horizontal) for floor sensors 800. The specific arrangement of sensors may depend on the geometry of the robot. In some embodiments, floor sensors may be infrared (IR) sensors, ultrasonic sensors, laser sensors, time-of-flight (TOF) sensors, distance sensors, 3D or 2D range finders, 3D or 2D depth cameras, etc. For example, the floor sensor positioned on the front of the robot in FIG. 3 may be an IR sensor while the floor sensors positioned on the sides of the robot may be TOF sensors. In another example, FIGS. 6A and 6B illustrate examples of alternative positions (e.g., displaced at some distance from the wheel so there is time for the robot to react, wherein the reaction time depends on the speed of the robot and the sensor position) of IR floor sensors 900 positioned on the sides of the underside of the robot. In these examples, the floor sensors are positioned in front of the wheel (relative to a forward moving direction of the wheel) to detect a cliff as the robot moves forward within the environment. Floor sensors positioned in front of the wheel may detect cliffs faster than floor sensors positioned adjacent to or further away from the wheel. In embodiments, the number of floor sensors coupled to the underside of the robot may vary depending on the functionality. For example, some robots may rarely drive backwards while others may drive backwards more often. Some robots may only turn clockwise while some may turn counterclockwise while some may do both. Some robots may execute a coastal drive or navigation from one side of the room. For example, FIG. 7 illustrates an example of an underside of a robotic cleaner with four floor sensors 1000. FIG. 8 illustrates an example of an underside of a robotic cleaner with five floor sensors 1100. FIG. 9 illustrates an example of an underside of a robotic cleaner with six floor sensors 1200. In some embodiments, the processor of the robot may detect cliffs based on data collected by the floor sensors. Such methods are further described in U.S. patent application Ser. Nos. 14/941,385, 16/279,699, and 16/041,470, the entire contents of which are hereby incorporated by reference.

[0266] FIG. 10 illustrates an example of a control system of a robot and components connected thereto. In some embodiments, the control system and related components are part of a robot and carried by the robot as the robot moves. Microcontroller unit (MCU) 800 of main printed circuit board (PCB) 801, or otherwise the control system or processor, has connected to it user interface module 802 to receive and respond to user inputs; bumper sensors 803, floor sensors 804, presence sensors 805 and perimeter and obstacle sensors 806, such as those for detecting physical contacts with objects, edges, docking station, and the wall; main brush assembly motor 807 and side brush assembly motor 808; side wheel assembly 809 and front wheel assembly 810, both with encoders for measuring movement; vacuum impeller motor 811; UV light assembly 812 for disinfection of a floor, for example; USB assembly 813 including those for user programming; camera and depth module 814 for mapping; and power input 815. Included in the main PCB are also battery management 816 for charging; accelerometer and gyroscope 817 for measuring movement; RTC 818 for keeping time; SDRAM 819 for memory; Wi-Fi module 820 for wireless control; and RF module 821 for confinement or communication with docking station. The components shown in FIG. 10 are for illustrative purposes and are not meant to limit the control system and components connected thereto, which is not to suggest that any other description is limiting. Direction of arrows signifies direction of information transfer and is also for illustrative purposes as in other instances direction of information transfer may vary.

[0267] FIG. 11A illustrates another example of a robot with vacuuming and mopping capabilities. In some embodiments, the robot may vacuum and mop simultaneously or individually, depending on the type of cleaning required in different areas of the environment or based on the floor type of different areas (e.g., only vacuuming on carpeted floors). In some embodiments, the robot may clean areas of the environment that require only vacuuming before cleaning areas of the environment that require mopping. The robot includes a module 300 that is removable from the robot, as illustrated in FIG. 11B. FIG. 11C illustrates the module 300 with a dustbin lid 301 that interfaces with an intake path of debris, module connector 302 for connecting the module 300 to the robot, water intake tab 303 that may be opened to insert water into a water container, and a mopping pad (or cloth) 304. FIG. 11D illustrates internal components of the module 300 including a gasket 305 of the dustbin lid 301 to prevent the contents of dustbin 306 from escaping, opening 307 of the dustbin lid 301 that allows debris collected by the robot to enter the dustbin 306, and a water pump 308 positioned outside of the water tank 309 that pumps water from the water tank 309 to water dispensers 310. Mopping pad 304 receives water from water dispensers 310 which moistens the mopping pad 304 for cleaning a floor. FIG. 11E illustrates debris path 311 from the robot into the dustbin 306 and water 312 within water tank 309. Both the dustbin 306 and the water tank 309 may be washed as the impeller is not positioned within the dustbin 306 and the water pump 308 is not positioned within the water tank 309. FIG. 11F illustrates a bottom of module 300 including water dispensers 310 and Velcro strips 311 that may be used to secure mopping pad 304 to the bottom of module 300. FIG. 11G illustrates an alternative embodiment for dustbin lid 301, wherein dustbin lid 301 opens from the top of module 300. FIGS. 12A and 12B illustrates alternative embodiment of the robot in FIGS. 11A-11E. In FIG. 12A the water pump 400 is positioned within the dustbin of module 401 and in FIG. 12B the water pump 400 is positioned outside the module 401 and is connected to the module via connecting tube 402 with gasket 403 to seal fluid and prevent it from escaping at the connection point. FIG. 12C illustrates a module 403 for converting water into hydrogen peroxide and water pump 400 positioned within module 401. In some cases, module 403 may suction water (or may be provided water using a pump) from the water tank of the module 401, convert the water into hydrogen peroxide, and dispense the hydrogen peroxide into an additional container for storing the hydrogen peroxide. The container storing hydrogen peroxide may use similar methods as described for dispensing the fluid onto the mopping pad. In some embodiments, the process of water electrolysis may be used to generate the hydrogen peroxide. In some embodiments, the process of converting water to hydrogen peroxide may include water oxidation over an electrocatalyst in an electrolyte, that results in hydrogen peroxide dissolved in the electrolyte which may be directly applied to the surface or may be further processed before applying it to the surface.

[0268] In some embodiments, the robot is a robotic cleaner. In some embodiments, the robot includes a removable brush compartment with roller brushes designed to avoid collection of hair and debris at a connecting point of the roller brushes and a motor rotating the roller brushes. In some embodiments, the component powering rotation of the roller brushes may be masked from a user, the brush compartment, and the roller brushes by separating the power transmission from the brush compartment. In some embodiments, the roller brushes may be cleaned without complete removal of the roller brushes thereby avoiding tedious removal and realignment and replacement of the brushes after cleaning.

[0269] FIG. 13A illustrates an example of a brush compartment of a robotic cleaner including frame 1300, gear box 1301, and brushes 1302. The robotic cleaner includes a motor 1303 and gearbox 1304 that interfaces with gear box 1301 of the brush compartment when it is fully inserted into the underside of the robotic cleaner, as illustrated in FIG. 13B. In some embodiments, the motor is positioned above the brush compartment such that elements like hair and debris cannot become entangled at the point of connection between the power transmission and brushes. In some embodiments, the motor and gearbox of the robot is positioned adjacent to the brush compartment or in another position. In some embodiments, the power generating motion in the motor is normal to the axis of rotation the brushes. In some embodiments, the motor and gearbox of the robot and the gearbox of the brush compartment may be positioned on either end of the brush compartment. In some embodiments, more than one motor and gearbox interface with the brush compartment. In some embodiments, more than one motor and gearbox of the robot may each interface with a corresponding gearbox of the brush compartment. FIG. 13C illustrates brush 1302 comprised of two portions, one portion of which is rotatably coupled to frame 1300 on an end opposite the gear box 1301 of the brush compartment such that the rotatable portion of the brush may rotate about an axis parallel to the width of the frame. In some embodiments, the two portions of brush 1302 may be separated when the brushes are non-operable. In some embodiments, the two portions of brush 1302 are separated such that brush blade 1305 may be removed from brush 1302 by sliding brush blade 1305 in direction 1306. In some embodiments, brush blades may be replaced when worn out or may be removed for cleaning. In some instances, this eliminates the tedious task of realigning brushes when they are completely removed from the robot. In some embodiments, a brush may be a single piece that may be rotatably coupled to the frame on one end such that the brush may rotate about an axis parallel to the width of the frame. In some embodiments, the brush may be fixed to the module such there is no need for removal of the brush during cleaning and may be put back together by simply clicking the brush into place. In some embodiments, separation of the brush from the module may not be a necessity for fully cleaning the brush but separation may be possible. In some embodiments, either end of a brush may be rotatably coupled to either end of the frame of the brush compartment. In some embodiments, the brushes may be directly attached to the chassis of the robotic cleaner, without the use of the frame. In some embodiments, brushes of the brush compartment may be configured differently from one another. For example, one brush may only rotate about an axis of the brush during operation while the other may additionally rotate about an axis parallel to the width of the frame when the brush is non-operable for removal of brush blades. FIG. 13E illustrates brush blade 1305 completely removed from brush 1302. FIG. 13F illustrates motor 1303 and gearbox 1304 of the robotic cleaner that interfaces with gearbox 1301 of the brush compartment through insert 1307. FIG. 13G illustrates brushes 1302 of the brush compartment, each brush including two portions. To remove brush blades 1305 from brushes 1302, the portions of brushes 1302 opposite gearbox 1301 rotate about an axis perpendicular to rotation axes of brushes 1302 and brush blades 1305 may be slid off of the two portions of brushes 1302 as illustrated in FIGS. 13D and 13E. FIG. 13H illustrates an example of a locking mechanism that may be used to lock the two portions of each brush 1302 together including locking core 1308 coupled to one portion of each brush and lock cavity 1309 coupled to a second portion of each brush. Locking core 1308 and lock 1309 interface with another to lock the two portions of each brush 1302 together.

[0270] FIG. 14A illustrates another example of a brush compartment of a robotic cleaner with similar components as described above including motor 2400 and gearbox 1401 of the robotic cleaner interfacing with gearbox 1402 of the brush compartment. Component 1403 of gearbox 1401 of the robotic cleaner interfacing with gearbox 1402 of the brush compartment differs from that shown in FIG. 14A. FIG. 14B illustrates that component 1403 of gearbox 1401 of the robotic cleaner is accessible by the brush compartment when inserted into the underside of the robotic cleaner, while motor 1400 and gearbox 1401 of the robotic cleaner are hidden within a chassis of the robotic cleaner.

[0271] In some instances, the robotic cleaner may include a mopping module including at least a reservoir and a water pump driven by a motor for delivering water from the reservoir indirectly or directly to the driving surface. In some embodiments, the water pump may autonomously activate when the robotic cleaner is moving and deactivate when the robotic cleaner is stationary. In some embodiments, the water pump may include a tube through which fluid flows from the reservoir. In some embodiments, the tube may be connected to a drainage mechanism into which the pumped fluid from the reservoir flows. In some embodiments, the bottom of the drainage mechanism may include drainage apertures. In some embodiments, a mopping pad may be attached to a bottom surface of the drainage mechanism. In some embodiments, fluid may be pumped from the reservoir, into the drainage mechanism and fluid may flow through one or more drainage apertures of the drainage mechanism onto the mopping pad. In some embodiments, flow reduction valves may be positioned on the drainage apertures. In some embodiments, the tube may be connected to a branched component that delivers the fluid from the tube in various directions such that the fluid may be distributed in various areas of a mopping pad. In some embodiments, the release of fluid may be controlled by flow reduction valves positioned along one or more paths of the fluid prior to reaching the mopping pad. FIG. 15A illustrates an example of a charging station 1500 including signal transmitters 1501 that transmit signals that the robot 1502 may use to align itself with the charging station 1500 during docking, vacuum motor 1503 for emptying debris from the dustbin of the robot 1502 into disposable trash bag (or reusable trash container) 1504 via tube and water pump 1505 for refilling a water tank of robot 1502 via tube 1506 using water from the house supply coming through piping 1507 into water pump 1505. In some cases, the trash bag 1504 of charging station 1500 may be removed by pressing a button on the charging station 1500. FIG. 15B illustrates debris collection path 1508 and charging pads 1509 and FIG. 15C illustrates water flow path 1510 and charging pads 1509 (robot not shown for visualization of the debris path and water flow path). Charging pads of the robot interface with charging pads 1509 during charging. Charging station 1500 may be used for a robot with combined vacuuming and mopping capabilities. In some instances, the dustbin is emptied or the water tank is refilled when the dustbin or the water tank reaches a particular volume, after a certain amount of surface coverage by the robot, after a certain number of operational hours, after a predetermined amount of time, after a predetermined number of working sessions, or based on another metric. In some instances, the processor of the robot may communicate with the charging station to notify the charging station that the dustbin needs to be emptied or the water tank needs to be refilled. In some cases, a user may use an application paired with the robot to instruct the robot to empty its dustbin or refill its water tank. The application may communicate the instruction to the robot and/or the charging station. In some cases, the charging station may be separate from the dustbin emptying station or the water refill station. In some embodiments, the dustbin of the robot is washable. An example of a washable dustbin is described in U.S. patent application Ser. No. 16/186,499, the entire contents of which are hereby incorporated by reference.

[0272] Some embodiments may provide a mopping extension unit for the robotic cleaner to enable simultaneous vacuuming and mopping of a driving surface and reduce (or eliminate) the need for a dedicated robotic mopping to run after a dedicated robotic vacuum. In some embodiments, a mopping extension may be installed in a dedicated compartment of or built into the chassis of the robotic cleaner. In some embodiments, the mopping extension may be detachable by, for example, activating a button or latch. In some embodiments, a cloth positioned on the mopping extension may contact the driving surface as the robotic cleaner drives through an area. In some embodiments, nozzles may direct fluid from a fluid reservoir to a mopping cloth. In some embodiments, the nozzles may continuously deliver a constant amount of cleaning fluid to the mopping cloth. In some embodiments, the nozzles may periodically deliver predetermined quantities of cleaning fluid to the cloth. In some embodiments, a water pump may deliver fluid from a reservoir to a mopping cloth, as described above. In some embodiments, the mopping extension may include a set of ultrasonic oscillators that vaporize fluid from the reservoir before it is delivered through the nozzles to the mopping cloth. In some embodiments, the ultrasonic oscillators may vaporize fluid continuously at a low rate to continuously deliver vapor to the mopping cloth. In some embodiments, the ultrasonic oscillators may turn on at predetermined intervals to deliver vapor periodically to the mopping cloth. In some embodiments, a heating system may alternatively be used to vaporize fluid. For example, an electric heating coil in direct contact with the fluid may be used to vaporize the fluid. The electric heating coil may indirectly heat the fluid through another medium. In other examples, radiant heat may be used to vaporize the fluid. In some embodiments, water may be heated to a predetermined temperature then mixed with a cleaning agent, wherein the heated water is used as the heating source for vaporization of the mixture. In some embodiments, water may be placed within the reservoir and the water may be reacted to produce hydrogen peroxide for cleaning and disinfecting the floor. In such embodiments, the process of water electrolysis may be used to generate hydrogen peroxide. In some embodiments, the process may include water oxidation over an electrocatalyst in an electrolyte, that results in hydrogen peroxide dissolved in the electrolyte which may be directly applied to the driving surface or mopping pad or may be further processed before applying it to the driving surface. In some embodiments, the robotic cleaner may include a means for moving the mopping cloth (and a component to which the mopping cloth may be attached) back and forth (e.g., forward and backwards or left and right) in a horizontal plane parallel to the driving surface during operation (e.g., providing a scrubbing action) such that the mopping cloth may pass over an area more than once as the robot drives. In some embodiments, the robot may pause for a predetermined amount of time while the mopping cloth moves back and forth in a horizontal plane, after which, in some embodiments, the robot may move a predetermined distance before pausing again while the mopping cloth moves back and forth in the horizontal plane again. In some embodiments, the mopping cloth may move back and forth continuously as the robot navigates within the environment. In some embodiments, the mopping cloth may be positioned on a front portion of the robotic cleaner. In some embodiments, a dry cloth may be positioned on a rear portion of the robotic cleaner. In some embodiments, as the robot navigates, the dry cloth may contact the driving surface and because of its position on the robot relative to the mopping cloth, dries the driving surface after the driving surface is mopped with the mopping cloth. For example, FIG. 16A illustrates a robot including sensor windows 1600 behind which sensors are positioned, sensors 1601 (e.g., camera, laser emitter, TOF sensor, etc.), user interface 1602, a battery 1603, a wet mop movement mechanism 1604, a PCB and processing unit 1605, a wheel motor and gearbox 1606, wheels 1607, a wet mop tank 1608, a wet mop cloth 1609, and a dry mop cloth 1610. FIG. 16B illustrates the robot driving in a direction 1611. While driving, or while pausing, wet mop cloth 1609 moves back and forth in a forward direction 1612 and backward direction 1613, respectively. As the robot drives forward, dry cloth 1610 dries the driving surface that has been cleaned by wet mop cloth 1609. In some embodiments, the mopping extension may include a means to vibrate the mopping extension during operation (e.g., eccentric rotating mass vibration motors). In some embodiments, the mopping extension may include a means to engage and disengage the mopping extension during operation by moving the mopping extension up and down in a vertical plane perpendicular to the work surface. In some embodiments, engagement and disengagement may be manually controlled by a user. In some embodiments, engagement and disengagement may be controlled automatically by the processor based on sensory input. For example, the processor may actuate the mopping extension to move in an upwards direction away from the driving surface upon detecting carpet using sensor data. In some embodiments, the robot may include a mopping mechanism as described in U.S. patent application Ser. Nos. 16/440,904, 15/673,176, 16/058,026, 14/970,791, 16/375,968, 15/432,722, 16/238,314, the entire contents of which are hereby incorporated by reference.

[0273] In some embodiments, the robot includes a touch-sensitive display or otherwise a touch screen. In some embodiments, the touch screen may include a separate MCU or CPU for the user interface may share the main MCU or CPU of the robot. In some embodiments, the touch screen may include an ARM Cortex M0 processor with one or more computer-readable storage mediums, a memory controller, one or more processing units, a peripherals interface, Radio Frequency (RF) circuitry, audio circuitry, a speaker, a microphone, an Input/Output (I/O) subsystem, other input control devices, and one or more external ports. In some embodiments, the touch screen may include one or more optical sensors or other capacitive sensors that may respond to a hand of a user approaching closely to the sensor. In some embodiments, the touch screen or the robot may include sensors that measure intensity of force or pressure on the touch screen. For example, one or more force sensors positioned underneath or adjacent to the touch sensitive surface of the touch screen may be used to measure force at various points on the touch screen. In some embodiments, physical displacement of a force applied to the surface of the touch screen by finger or hand may generate a noise (e.g., a “click” noise) or movement (e.g., vibration) that may be observed by the user to confirm that a particular button displayed on the touch screen is pushed. In some embodiments, the noise or movement is generated when the button is pushed or released.

[0274] In some embodiments, the touch screen may include one or more tactile output generators for generating tactile outputs on the touch screen. These components may communicate over one or more communication buses or signal lines. In some embodiments, the touch screen or the robot may include other input modes, such as physical and mechanical control using a knob, switch, mouse, or button). In some embodiments, peripherals may be used to couple input and output peripherals of the touch screen to the CPU and memory. The processor executes various software programs and/or sets of instructions stored in memory to perform various functions and process data. In some embodiments, the peripherals interface, CPU, and memory controller are implemented on a single chip or, in other embodiments, may be implemented on separate chips.

[0275] In some embodiments, the touch screen may display the frame of camera captured and transmitted and displayed to the others during a video conference call. In some embodiments, the touch screen may use liquid crystal display (LCD) technology, light emitting polymer display (LPD) technology, LED display technology with high or low resolution, capacitator touch screen display technology, or other older or newer display technologies. In some embodiments, the touch screen may be curved in one direction or two directions (e.g., a bowl shape). For example, the head of a humanoid robot may include a curved screen that is geared towards transmitting emotions. FIG. 17 includes examples of screens curved in one or more directions.

[0276] In some embodiments, the touch screen may include a touch-sensitive surface, sensor, or set of sensors that accept input from the user based on haptic and/or tactile contact. In some embodiments, detecting contact, a particular type of continuous movement, and the eventual lack of contact may be associated with a specific meaning. For example, a smiling gesture (or in other cases a different gesture) drawn on the touch screen by the user may have a specific meaning. For instance, drawing a smiling gesture on the touch screen to unlock the robot may avoid accidental triggering of a button of the robot. In embodiments, the gesture may be drawn with one finger, two fingers, or any other number of fingers. The gesture may be drawn in a back and forth motion, slow motion, or fast motion and using high or low pressure. In some embodiments, the gesture drawn on the touch screen may be sensed by a tactile sensor of the touch screen. In some embodiments, a gesture may be drawn in the air or a symbol may be shown in front of a camera of the robot by a finger, hand, or arm of the user or using another device. In some embodiments, gestures in front of the camera may be sensed by an accelerometer or indoor/outdoor GPS built into a device held by the user (e.g., a cell phone, a gaming controller, etc.). FIG. 18A illustrates a user 5400 drawing a gesture on a touch screen 5401 of the robot 5402. FIG. 18B illustrates the user 5400 drawing the gesture 5403 in the air. FIG. 18C illustrates the user 5400 drawing the gesture 5403 while holding a device 5404 that may include a built-in component used in detecting movement of the user. FIG. 18D illustrates various alternative smiling gestures.

[0277] In some embodiments, the robot may project an image or video onto a screen (e.g., like a projector). In some embodiments, a camera of the robot may be used to continuously capture images or video of the image or video projected. For example, a camera may capture a red pointer pointing to a particular spot on an image projected onto a screen and the processor of the robot may detect the red point by comparing the projected image with the captured image of the projection. In some embodiments, this technique may be used to capture gestures. For example, instead of a laser pointer, a person may point to a spot in the image using fingers, a stylus, or another device.

[0278] In some embodiments, the robot may communicate using visual outputs such as graphics, texts, icons, videos and/or by using acoustic outputs such as videos, music, different sounds (e.g., a clicking sound), speech, or by text to voice translation. In embodiments, both visual and acoustic outputs may be used to communicate. For example, the robot may play an upbeat sound while displaying a thumb up icon when a task is complete or may play a sad tone while displaying a text that reads ‘error’ when a task is aborted due to error.

[0279] In some embodiments, an avatar may be used to represent the visual identity of the robot. In some embodiments, the user may assign, design, or modify from template a visual identity of the robot. In some embodiments, the avatar may reflect the mood of the robot. For example, the avatar may smile when the robot is happy. In some embodiments, the robot may display the avatar or a face of the avatar on an LCD or other type of screen. In some embodiments, the screen may be curved (e.g., concave or convex). In some embodiments, the robot may identify with a name. For example, the user may call the robot a particular name and the robot may respond to the particular name. In some embodiments, the robot can have a generic name (e.g., Bob) or the user may choose or modify the name of the robot.

[0280] In some embodiments, the robot may charge at a charging station such as those described in U.S. patent application Ser. Nos. 15/071,069, 15/917,096, 15/706,523, 16/241,436, 15/377,674, and 16/883,327, the entire contents of which are hereby incorporated by reference. In some embodiments, the charging station of the robot may be built into an area of an environment (e.g., kitchen, living room, laundry room, mud room, etc.). In some embodiments, the bin of the surface cleaner may directly connect to and may be directly emptied into the central vacuum system of the environment. In some embodiments, the robot may be docked at a charging station while simultaneously connected to the central vacuum system. In some embodiments, the contents of a dustbin of a robot may be emptied at a charging station of the robot. For example, FIG. 19A illustrates robot 500 docked at charging station 501. Robot 500 charges by a connection between charging nodes (not shown) of robot 500 with charging pads 502 of charging station 501. When docked, a soft hose 503 may connect to a port of robot 500 with a vacuum motor 504 connected to a disposable trash bag (or detachable reusable container) 505. Vacuum motor 504 may suction debris 506 from a dustbin of robot 500 into disposable trash bag 505, as illustrated in FIG. 19B. Robot 500 may align itself during docking based on signals received from signal transmitters 507 positioned on the charging station 501. FIG. 19C illustrates components of rear-docking robot 500 including charging nodes 508, port 509 to which soft hose 503 may connect, and presence sensors 510 used during docking to achieve proper alignment. FIG. 19D illustrates magnets 511 that may be coupled to soft hose 503 and port 509. Magnets 511 may be used in aligning and securing a connection between soft hose 503 and port 509 of robot 500. FIG. 19E illustrates an alternative embodiment wherein the vacuum motor 504 is connected to an outdoor bin 512 via a soft plastic hose 513. FIG. 19F illustrates another embodiment, wherein the vacuum motor 504 and soft plastic hose 513 are placed on top of charging station 501. In some cases, the vacuum motor may be connected to a central vacuum system of a home or a garbage disposal system of a home. In embodiments, the vacuum motor may be placed on either side of the charging station. In some embodiments, the processor of the robot may determine and tracking area covered by the robot. In some embodiments, the processor of the robot may track a preset configuration for emptying the bin of the robot. In some embodiments, the robot may navigate to the charging station, empty its bin into the charging station bin, and resume cleaning uncovered areas of the environment after the bin of the robot is emptied into the station bin. The preset configuration may include at least one of a preset amount of coverage by the robot, a preset volume of debris within the bin of the robot, a preset amount of operational time, a preset amount of time, and a preset weight of debris within the bin of the robot.

[0281] In some embodiments, the charging station may be installed beneath a structure, such as a cabinet or counters. In some embodiments, the charging station may be for charging and/or servicing a surface cleaning robot that may perform at least one of: vacuuming, mopping, scrubbing, sweeping, steaming, etc. FIG. 20A illustrates a robot 4100 docked at a charging station 4101 installed at a bottom of cabinet 4102. In this example, a portion of robot 4100 extends from underneath the cabinet when fully docked at charging station 4101. In some cases, the charging station may not be installed beneath a structure and may be used as a standalone charging station, as illustrated in FIG. 20B. Charging pads 4202 of charging station 4101 used in charging robot 4100 are shown in FIG. 20B. FIG. 21 illustrates an alternative charging station that includes a module 4200 for emptying a dustbin of a robot 4201 when docked at the charging station. The module 4200 may interface with an opening of the dustbin and may include a vacuum motor that is used to suction the dust out of the dustbin. The module 4200 may be held by handle 4202 and removable such that its contents may be emptied into a trashcan. FIGS. 22A and 22B illustrate a charging station that includes a vacuum motor 4300 connected to a container 4301 and a water pump 4302. When a robot 4303 is docked at the charging station the vacuum motor interfaces with an opening of a dustbin of the robot 4303 and suctions debris from the dustbin into the container 4301. The water pump 4302 interfaces with a fluid tank of the robot 4303 and can pump fluid (e.g., cleaning fluid) into the fluid tank (e.g., directly from the water system of the environment or from a fluid reservoir) once it is depleted. The robot 4303 charges by connecting to charging pads 4304. In some cases, a separate mechanism that may attach to a robot may be used for emptying a dustbin of the robot. For example, FIG. 23A illustrates a handheld mechanism 4400 positioned within cabinet 4401. When a robot 4402 is docked at a charging station 4403 installed beneath cabinet 4401, the mechanism 4400 interfaces with an opening of the dustbin 4404 and using a vacuum motor 4405 is capable of suctioning the debris from the dustbin into a container 4406. The robot 4402 also charges by connecting with charging contacts 4407. The container 4406 may be detachable such that its contents may be easily emptied into a trash can. The handheld mechanism may be used with a standalone charging station as well, as illustrated in FIG. 23B. The handheld mechanism 4400 may also be used as a standalone vacuum and may include components, such as rod 4408, that attaches to it, as illustrated in FIG. 23C. In one case, the mechanism 4400 may be directly connected to a garbage bin 4409, as illustrated in FIG. 23D. In this way, the debris suctioned from the dustbin of the robot is fed into garbage bin 4409 from container 4406. FIG. 23E illustrates another possibility, wherein the system shown in FIG. 23D is installed within cabinet 4401. In some cases, garbage bin 4409 may be a robotic garbage bin. FIG. 23F illustrates robotic garbage bin 4409 navigating to autonomously empty its contents 4410 by driving out of cabinet 4401 and to a disposal location.

[0282] FIG. 24A illustrates another example of a charging station of a robot. The charging station includes charging pads 600, area 601 behind which signal transmitters are positioned, plug 602, and button 603 for retracting plug 602. Plug 602 may be pulled from hole 604 to a desired length and button 603 may be pushed to retract plug 602 back within hole 604. FIG. 24B illustrates plug 602 extended from hole 604. FIG. 24C illustrates a robot with charging nodes 605 that may interface with charging pads 600 to charge the robot. The robot includes sensor windows 606 behind which sensors (e.g., camera, time of flight sensor, LIDAR, etc.) are positioned, bumper 607, brush 608, wheels 609, and tactile sensors 610. Each tactile sensor may be triggered when pressed and may notify the robot of contact with an object. FIG. 24D illustrates panel 611, printed buttons 612 and indicators 613, and the actual buttons 614 and LED indicators 615 positioned within the robot that are aligned with the printed buttons 612 and indicators 613 on the panel 611. FIG. 24E illustrates the robot positioned on the charging station and a connection between charging nodes 605 of the robot and charging pads 600 of the charging station. The charging pads 600 may be spring loaded such that the robot does not mistake them as an obstacle. FIG. 24F illustrates an alternative embodiment of the charging station wherein the charging pads 616 are circular and positioned in a different location. FIG. 24G illustrates an alternative embodiment of the robot wherein sensors window 617 is continuous. FIG. 24H illustrates an example of an underside of the robot including UV lamp 618. FIG. 24I illustrates a close up of the UV lamp an internal reflective surface 619 to maximize lamp coverage and a bumpy glass cover 620 to scatter UV rays.

[0283] Various different types of charging stations may be used by the robot for charging. For example, one charging station may include retractable charging prongs. In some embodiments, the charging prongs are retracted within the main body of the charging station to protect the charging contacts from damage and dust collection which may affect efficiency of charging. In some embodiments, the charging station detects the robot approaching for docking and extends the charging prongs for the robot to dock and charge. The charging station may detect the robot by receiving a signal transmitted by the robot. In some embodiments, the docking station detects when the robot has departed from the charging station and retracts the charging prongs. The charging station may detect that the robot has departed by the lack of a signal transmitted from the robot. In some embodiments, a jammed state of a charging prong could be detected by the prototyped charging station monitoring the current drawn by the motor of the prong, wherein an increase in the current drawn would be indicative of a jam. The jam could be communicated to the prototyped robot via radio frequency communication which upon receipt could trigger the robot to stop docking.

[0284] In some embodiments, a receiver of the robot may be used to detect an IR signal emitted by an IR transmitter of the charging station. In some embodiments, the processor of the robot may instruct the robot to dock upon receiving the IR signal. In some embodiments, the processor of the robot may mark the pose of the robot when an IR signal is received within a map of the environment. In some embodiments, the processor may use the map to navigate the robot to a best-known pose to receive an IR signal from the charging station prior to terminating exploration and invoking an algorithm for docking. In some embodiments, the processor may search for concentrated IR areas in the map to find the best location to receive an IR signal from the charging station. In cases wherein only a large IR signal area is found, the processor may instruct the robot to execute a spiral movement to pinpoint a concentrated IR area, then navigate to the concentrated IR area and invoke the algorithm for docking. If no IR areas are found, the processor of the robot may instruct the robot to execute one or more 360-degree rotations and if still nothing is found, return to exploration. In some embodiments, the processor and charging station may use code words to improve alignment of the robot with the charging station during docking. In some embodiments, code words may be exchanged between the robot and the charging station that indicate the position of the robot relative to the charging station (e.g., code left and code right associated with observations by a front left and front right presence LED, respectively). In some embodiments, unique IR codes may be emitted by different presence LEDs to indicate a location and direction of the robot with respect to a charging station. In some embodiments, the charging station may perform a series of Boolean checks using a series of functions (e.g., a function ‘isFront’ with a Boolean return value to check if the robot is in front of and facing the charging station or ‘isNearFront’ to check if the robot is near to the front of and facing the charging station).

[0285] Some embodiments may include a fleet of robots with charging capabilities. In some embodiments, the robots may autonomously navigate to a charging station to recharge batteries or refuel. In some embodiments, charging stations with unique identifications, locations, availabilities, etc. may be paired with particular robots. In some embodiments, the processor of a robot or a control system of the fleet of robots may chose a charging station for charging. In some embodiments, the processor of a robot or the control system of the fleet of robots may keep track of one or more charging stations within a map of the environment. In some embodiments, the processor a robot or the control system of the fleet of robots may use the map within which the locations of charging stations are known to determine which charging station to use for a robot. In some embodiments, the processor of a robot or the control system of the fleet of robots may organize or determine robot tasks and/or robot routes (e.g., for delivering a pod or another item from a current location to a final location) such that charging stations achieve maximum throughput and the number of charged robots at any given time is maximized. In some embodiments, charging stations may achieve maximum throughput and the number of charged robots at any given time may be maximized by minimizing the number of robots waiting to be charged, minimizing the number of charging stations without a robot docked for charging, and minimizing transfers between charging stations during ongoing charging of a robot. In some embodiments, some robots may be given priority for charging. For example, a robot with 70% battery life may be quickly charged and ready to perform work, as such the robot may be given priority for charging if there are not enough robots available to complete a task (e.g., a minimum number of robots operating within a warehouse that are required to complete a task by a particular deadline).

[0286] In some embodiments, different components of the robot may connect with the charging station (or another type of station in some cases). In some embodiments, a bin (e.g., dust bin) of the robot may connect with the charging station. In some embodiments, the contents of the bin may be emptied into the charging station. For example, FIG. 25A illustrates an example of a charging station including an interface 4900 (e.g., LCD touchscreen), a suction hose 4901, an access door 4902, and charging pads 4903. In some cases, sensors 4904 may be used to align a robot with the charging station. FIG. 25B illustrates internal components of the charging station including suction motor and impeller 4905 used to create suction needed to draw in the contents of a bin of a robot connected to charging station via the suction hose 4901. FIG. 25C illustrates a robot 4906 connected with the charging station via suction hose 4901. In some cases, the suction hose 4901 may extend from the charging station to connect with the robot 4906. Internal contents of the robot 4906 may be removed via suction hose 4901. Charging contacts of the robot 4906 are connected with charging pads 4903 for recharging batteries of the robot 4906. FIG. 25D illustrates arrows 4907 indicative of the flow path of the contents within the robot 4906, beginning from within the robot 4906, passing through the suction hose 4901, and into a container 4908 of the charging station. The suction motor and impeller 4905 are positioned on a bottom of the container 4908 and create a negative pressure, causing the contents of robot 4906 to be drawn into container 4908. The air drawn into the container 4908 may flow past the impeller and may be expelled through the rear of the charging station. Once container 4908 is full, it may be emptied by opening access door 4902. In other embodiments, the components of the charging station may be retrofitted to other charging station models. For instance, FIGS. 26A and 26B illustrate another variation of a charging station for smaller robots, including suction port 5000 through which contents stored within the robot may be removed, impeller and motor 5001 for generating suction, and exhaust 5002 for expelling air. FIGS. 27A and 27B illustrate yet another variation of a charging station for robots, including suction port 5100 through which contents stored within the robot may be removed, impeller and motor 5101 for generating suction, and exhaust 5102 for expelling air. FIG. 27C illustrates a bin 5103 of a robot 5104 connected with the charging station via suction port 5100. Arrows 5105 indicate the flow of air, eventually expelled through the exhaust 5102. Suction ports of charging stations may be configured differently based on the position of the bin within the robot. For example, FIGS. 28A-28L illustrate a top view of charging stations, each including a suction port 5200, an impeller and motor 5201, a container 5202, and an exhaust 5203. Each charging station is configured with a different suction port 5200, depending on the shape and position of a dustbin 5204 of a robot 5205 connected to the charging station via the suction port 5200. In each case, the flow path of air indicated by arrow 5206, also changes based on the position and shape of the dustbin 5204 of the robot and the suction port 5200 of the charging station.

[0287] In some embodiments, robots may require servicing. In some embodiments, robots may be serviced at a service station or at the charging station. In some cases, particularly when the fleet of robots is large, it may be more efficient for servicing to be provided at a station that is different from the charging station as servicing may require less time than charging. Examples of services include changing a tire or inflating the tire of a robot. In the case of a commercial cleaner, an example of a service may include emptying waste water from the commercial cleaner and adding new water into a fluid reservoir. For a robotic vacuum, an example of a service may include emptying the dustbin. For a disinfecting robot, an example of a service may include replenishment of supplies such as UV bulbs, scrubbing pad, or liquid disinfectant. In some embodiments, servicing received by the robots may be automated or may be manual. In some embodiments, robots may be serviced by stationary robots. In some embodiments, robots may be serviced by mobile robots. In some embodiments, a mobile robot may navigate to and service a robot while the robot is being charged at a charging station. In some embodiments, a history of services may be recorded in a database for future reference. For example, the history of services may be referenced to ensure that maintenance is provided at the required intervals. In some cases, maintenance is provided on an as-need basis. In some cases, the history of services may reducing redundant operations performed on the robots. For example, if a part of a robot was replaced due to failure of the part, the new due date of service is calculated from the date on which the part was replaced instead of the last service date of the part.

[0288] Some embodiments may provide a real time navigational stack configured to provide a variety of functions. In embodiments, the real time navigational stack may reduce computational burden, and consequently may free the hardware (HW) for functions such as object recognition, face recognition, voice recognition, and other AI applications. Additionally, the boot up time of a robot using the real time navigational stack may be faster than prior art methods. For instance, FIG. 29 illustrates the boot up time of a robotic vacuum using the real time navigational stack in comparison to popular brands of robotic vacuums using other technologies known in the art (e.g., ROS and Linux). In general, the real time navigational stack may allow more tasks and features to be packed into a single device while reducing battery consumption and environmental impact. The collection of the advantages of the real time navigational stack consequently improve performance and reduce costs, thereby paving the road forward for mass adoption of robots within homes, offices, small warehouses, and commercial spaces. In embodiments, the real time navigational stack may be used with various different types of systems, such as Real Time Operating System (RTOS), Robot Operating System (ROS), and Linux, as illustrated in FIG. 30.

[0289] Some embodiments may use a Microcontroller Unit (MCU) (e.g., SAM70S MC) including built in 300 MHz clock, 8 MB Random Access Memory (RAM), and 2 MB flash memory. In some embodiments, the internal flash memory may be split into two or more blocks. For example, a lower block may be used as default storage for program code and constant data. In some embodiments, the static RAM (SRAM) may be split into two or more blocks. FIG. 31 provides a visualization of multitasking in real time on an ARM Cortex M7 MCU, model SAM70 from Atmel. Each task is scheduled to run on the MCU. Information is received from sensors and is used in real time by AI algorithms. Decisions actuate the robot without buffer delays based on the real time information. Examples of sensors include, but are not limited to, inertial measurement unit (IMU), gyroscope, optical tracking sensor (OTS), depth camera, obstacle sensor, floor sensor, edge detection sensor, debris sensor, acoustic sensor, speech recognition, camera, image sensor, time of flight (TOF) sensor, TSOP sensor, laser sensor, light sensor, electric current sensor, optical encoder, accelerometer, compass, speedometer, proximity sensor, range finder, LIDAR, LADAR, radar sensor, ultrasonic sensor, piezoresistive strain gauge, capacitive force sensor, electric force sensor, piezoelectric force sensor, optical force sensor, capacitive touch-sensitive surface or other intensity sensors, global positioning system (GPS), etc. In embodiments, other types of MCUs or CPUs than that described in FIG. 31 may be used to achieve similar results. A person skilled in the art would understand the pros and cons of different available options and would be able to choose from available silicon chips to best take advantage of their manufactured capabilities for the intended application.

[0290] In embodiments, the core processing of the real time navigational stack occurs in real time. In some embodiments, a variation RTOS may be used (e.g., Free-RTOS). In some embodiments, a proprietary code may act as an interface to providing access to the HW of the CPU. In either case, AI algorithms such as SLAM and path planning, peripherals, actuators, and sensors communicate in real time and take maximum advantage of the HW capabilities that are available in advance computing silicon. In some embodiments, the real time navigation stack may take full advantage of thread mode and handler mode support provided by the silicon chip to achieve better stability of the system. In some embodiments, an interrupt may occur by a peripheral, and as a result, the interrupt may cause an exception vector to be fetched and the MCU (or in some cases CPU) may be converted to handler mode by taking the MCU to an entry point of the address space of the interrupt service routine (ISR). In some embodiments, a Microprocessor Unit (MPU) may control access to various regions of the address space depending on the operating mode.

[0291] In embodiments, the real time navigational system of the robot may be compatible with a 360 degrees LIDAR and a limited Field of View (FOV) depth camera. This is unlike robots in prior art that are only compatible with either the 360 degrees LIDAR or the limited FOV depth camera. In addition, navigation systems of robots described in prior art require calibration of the gyroscope and IMU and must be provided wheel parameters of the robot. In contrast, some embodiments of the real time navigational system described herein may autonomously learn calibration of the gyroscope and IMU and the wheel parameters.

[0292] In some cases, the real time navigational system may be compatible with systems that do not operate in real time for the purposes of testing, proof of concepts, or for use in alternative applications. In some embodiments, a mechanism may be used to create a modular architecture that keeps the stack intact and only requires modification of the interface code when the navigation stack needs to be ported. In some embodiments, an Application Programming Interface (API) may be used to interface between the navigational stack and customers to provide indirect secure access to modify some parameters in the stack.

[0293] In some embodiments, the processor of the robot may use Light Weight Real Time SLAM Navigational stack to map the environment and localize the robot. In some embodiments, Light Weight Real Time SLAM Navigational Stack may include a state machine portion, a control system portion, a local area monitor portion, and a pose and maps portion. FIG. 32 provides a visualization of an example of a Light Weight Real Time SLAM Navigational Stack algorithm. The state machine 1100 may determine current and next behaviors. At a high level, the state machine 1100 may include the behaviors reset, normal cleaning, random cleaning, and find the dock. The control system 1101 may determine normal kinematic driving, online navigation (i.e., real time navigation), and robust navigation (i.e., navigation in high obstacle density areas). The local area monitor 1102 may generate a high resolution map based on short range sensor measurements and control speed of the robot. The control system 301 may receive information from the local area monitor 1102 that may be used in navigation decisions. The pose and maps portion 1103 may include a coverage tracker 1104, a pose estimator 1105, SLAM 1106, and a SLAM updater 1107. The pose estimator 1105 may include an Extended Kalman Filter (EKF) that uses odometry, IMU, and LIDAR data. SLAM 1106 may build a map based on scan matching. The pose estimator 1105 and SLAM 1106 may pass information to one another in a feedback loop. The SLAM updated 1107 may estimate the pose of the robot. The coverage tracker 1104 may track internal coverage and exported coverage. The coverage tracker 1104 may receive information from the pose estimator 1105, SLAM 1106, and SLAM updated 1107 that it may use in tracking coverage. In one embodiment, the coverage tracker 1104 may run at 2.4 Hz. In other indoor embodiments, the coverage tracker may run at between 1-50 Hz. For outdoor robots, the frequency may increase depending on the speed of the robot and the speed of data collection. A person in the art would be able to calculate the frequency of data collection, data usage, and data transmission to control system. The control system 1101 may receive information from the pose and maps portion 1103 that may be used for navigation decisions.

[0294] In some embodiments, a mapping sensor (e.g., a sensor whose data is used in generating or updating a map) runs on a Field Programmable Gate Array (FPGA) and the sensor readings are accumulated in a data structure such as vector, array, list, etc. The data structure may be chosen based on how that data may need to be manipulated. For example, in one embodiment a point cloud may use a vector data structure. This allows simplification of data writing and reading. FIG. 33 illustrates a mapping sensor 1200 including an image sensor (e.g., camera, LIDAR, etc.) that runs on a FPGA or Graphics Processing Unit (GPU) or an Application Specific Integrated Circuit (ASIC). Data is passed between the mapping sensor and the CPU. FIG. 33 also illustrates the flow of data in Linux based SLAM, indicated by path 1200. In traditional SLAM 1200, data flows between real time sensors 1 and 2 and the MCU and then between the MCU and CPU which may be slower due to several levels of abstraction in each step (MCU, OS, CPU). These levels of abstractions are noticeably reduced in Light Weight Real Time SLAM Navigational Stack, wherein data flows between real time sensors 1 and 2 and the MCU. While, Light Weight Real Time SLAM Navigational Stack may be more efficient, both types of SLAM may be used with the methods and techniques described herein.

[0295] In some embodiments, it may desirable for the processor of the robot (particularly a service robot) to map the environment as soon as possible without having to visit various parts of the environment redundantly. For instance, a map complete with a minimum percentage of coverage to entire coverable area may provide better performance. FIG. 34 illustrates a table comparing time to map an entire area and percentage of coverage to entire coverable area for a robot using Light Weight Real Time SLAM Navigational Stack and a robot using traditional SLAM for a complex and large space. The time to map the entire area and the percentage of area covered were much less with Light Weight Real Time SLAM Navigational Stack, requiring only minutes and a fraction of the space to be covered to generate a complete map. Traditional SLAM techniques require over an hour and some VSLAM solutions require the complete coverage of areas to generate a complete map. In addition, with traditional SLAM, robots may be required to perform perimeter tracing (or partial perimeter tracing) to discover or confirm an area within which the robot is to perform work in. Such SLAM solutions may be unideal for, for example, service oriented tasks, such as popular brands of robotic vacuums. It is more beneficial and elegant when the robot begins to work immediately without having to do perimeter tracing first. In some applications, the processor of the robot may not get a chance to build a complete map of an area before the robot is expected to perform a task. However, in such situations, it is useful to map as much of the area as possible in relation to the amount of the area covered by the robot as a more complete map may result in better decision making. In coverage applications, the robot may be expected to complete coverage of an entire area as soon as possible. For example, for a standard room setup based on International Electrotechnical Commission (IEC) standards, it is more desirable that a robot completes coverage of more than 70% of the room in under 6 minutes as compared to only 40% in under 6 minutes. FIG. 35 illustrates room coverage percentage over time for a robot using Light Weight Real Time SLAM Navigational Stack and four robots using traditional SLAM methods. As can be seen, the robot using Light Weight Real Time SLAM Navigational Stack completes coverage of the room much faster than robots using traditional SLAM methods.

[0296] In some embodiments, the positioning of components of the robot may change. For example, in one embodiment the distance between an IMU and a camera may be different than in a second embodiment. In another example, the distance between wheels may be different in two different robots manufactured by the same manufacturer or different manufacturers. The wheel diameter, the geometry between the side wheels and the front wheel, and the geometry between sensors and actuators, are other examples of distances and geometries that may vary in different embodiments. In some embodiments, the distances and geometries between components of the robot may be stored in one or more transformation matrices. In some embodiments, the values (i.e., distances and geometries between components of the robot) of the transformation matrices may be updated directly within the program code or through an API such that the licensees of the software may implement adjustments directly as per their specific needs and designs. Since different types of robots may use the Light Weight Real Time SLAM Navigational Stack describes herein, the diameter, shape, positioning, or geometry of various components of the robots may be different and may therefore require updated distances and geometries between components.

[0297] In some embodiments, the processor of the robot may generate and update a map (which may also be referred to as a spatial representation, a planar work surface, or another equivalent) of an environment. Some embodiments provide a computationally inexpensive mapping solution (or portion thereof) with minimal (or reduced) cost of implementation relative to traditional techniques. In some embodiments, mapping an environment may constitute mapping an entire environment, such that all areas of the environment are captured in the map. In other embodiments, mapping an environment may constitute mapping a portion of the environment where only some areas of the environment are captured in the map. For example, a portion of a wall within an environment captured in a single field of view of a camera and used in forming a map of a portion of the environment may constitute mapping the environment. Embodiments afford a method and apparatus for combining perceived depths to construct a map of an environment using cameras capable of perceiving depths (or capable of acquiring data by which perceived depths are inferred) to objects within the environment, such as but not limited to (which is not to suggest that any other list herein is limiting), depth cameras or stereo vision cameras or depth sensors comprising, for example, an image sensor and IR illuminator. A charge-coupled device (CCD) or complementary metal oxide semiconductor (CMOS) camera positioned at an angle relative to a horizontal plane combined with at least one IR point or line generator or any other structured form of light may also be used to perceive depths to obstacles within the environment. Objects may include, but are not limited to, articles, items, walls, boundary setting objects or lines, furniture, obstacles, etc. that are included in the map. A boundary of a working environment may be considered to be within the working environment. In some embodiments, a camera is moved within an environment while depths from the camera to objects are continuously (or periodically or intermittently) perceived within consecutively overlapping fields of view. Overlapping depths from separate fields of view may be combined to construct a map of the environment.

[0298] In some embodiments, a camera and at least one control system installed on the robot perceives depths from the camera to objects within a first field of view, e.g., such that a depth is perceived at each specified increment. Depending on the type of depth perceiving device used, depth may be perceived in various forms. The depth perceiving device may be a depth sensor, a camera, a camera coupled with IR illuminator, a stereovision camera, a depth camera, a time-of-flight camera or any other device which can infer depths from captured depth images. A depth image may be any image containing data which can be related to the distance from the depth perceiving device to objects captured in the image. For example, in one embodiment the depth perceiving device may capture depth images containing depth vectors to objects, from which the Euclidean norm of each vector may be calculated, representing the depth from the camera to objects within the field of view of the camera. In some instances, depth vectors may originate at the depth perceiving device and may be measured in a two-dimensional plane coinciding with the line of sight of the depth perceiving device. In other instances, a field of three-dimensional vectors originating at the depth perceiving device and arrayed over objects in the environment may be measured. In another embodiment, the depth perceiving device may infer depth of an object based on the time required for a light (e.g., broadcast by a depth-sensing time-of-flight camera) to reflect off of the object and return. In a further example, the depth perceiving device may comprise a laser light emitter and two image sensors positioned such that their fields of view overlap. Depth may be inferred by the displacement of the laser light projected from the image captured by the first image sensor to the image captured by the second image sensor (see, U.S. patent application Ser. No. 15/243,783, which is hereby incorporated by reference). The position of the laser light in each image may be determined by identifying pixels with high brightness (e.g., having greater than a threshold delta in intensity relative to a measure of central tendency of brightness of pixels within a threshold distance). The control system may include, but is not limited to, a system or device(s) that perform, for example, methods for receiving and storing data; methods for processing data, including depth data; methods for processing command responses to stored or processed data, to the observed environment, to internal observation, or to user input; methods for constructing a map or the boundary of an environment; and methods for navigation and other operation modes. For example, a processor of the control system may receive data from an obstacle sensor, and based on the data received, the processor may respond by commanding the robot to move in a specific direction. As a further example, the processor may receive image data of the observed environment, process the data, and use it to create a map of the environment. The processor of the control system may be a part of the robot, the camera, a navigation system, a mapping module or any other device or module. The processor may also include a separate component coupled to the robot, the navigation system, the mapping module, the camera, or other devices working in conjunction with the robot. More than one processor may be used.

[0299] The robot and attached camera may rotate to observe a second field of view partly overlapping the first field of view. In some embodiments, the robot and camera may move as a single unit, wherein the camera is fixed to the robot, the robot having three degrees of freedom (e.g., translating horizontally in two dimensions relative to a floor and rotating about an axis normal to the floor), or as separate units in other embodiments, with the camera and robot having a specified degree of freedom relative to the other, both horizontally and vertically. For example, but not as a limitation (which is not to imply that other descriptions are limiting), the specified degree of freedom of a camera with a 90 degrees field of view with respect to the robot may be within 0-180 degrees vertically and within 0-360 degrees horizontally. Depths may be perceived to objects within a second field of view (e.g., differing from the first field of view due to a difference in camera pose). The depths for the second field of view may be compared to those of the first field of view. An area of overlap may be identified when a number of consecutive depths from the first and second fields of view are similar, as determined with techniques like those described below. The area of overlap between two consecutive fields of view may correlate with the angular movement of the camera (relative to a static frame of reference of a room) from one field of view to the next field of view. By ensuring the frame rate of the camera is fast enough to capture more than one frame of measurements in the time it takes the robot to rotate the width of the frame, there is always overlap between the measurements taken within two consecutive fields of view. The amount of overlap between frames may vary depending on the angular (and in some cases, linear) displacement of the robot, where a larger area of overlap is expected to provide data by which some of the present techniques generate a more accurate segment of the map relative to operations on data with less overlap. In some embodiments, a processor of the robot may infer the angular disposition of the robot from the size of the area of overlap and use the angular disposition to adjust odometer information to overcome the inherent noise of the odometer.

[0300] FIG. 36A illustrates an embodiment wherein camera 100, which may include a depth camera or a digital camera combined with an IR illuminator or a camera using natural light for illumination, mounted on robot 101 with at least one control system, is perceiving depths 102 at increments 103 within first field of view 104 to object 105, which in this case is a wall. Depths perceived may be in 2D or in 3D. FIG. 36B illustrates 2D map segment 106 resulting from plotted depth measurements 102 taken within first field of view 104. Dashed lines 107 demonstrate that resulting 2D floor plan segment 104 corresponds to plotted depths 102 taken within field of view 104.

[0301] FIG. 37A illustrates camera 100 mounted on robot 101 perceiving depths 200 within second field of view 201 partly overlapping depths 102 within first field of view 104. After depths 102 within first field of view 104 are taken, as shown in FIG. 36A, robot 101 with mounted camera 100 rotates to observe second field of view 201 with overlapping depths 202 between first field of view 104 and second field of view 201. In another embodiment, camera 100 rotates independently of robot 101. As the robot rotates to observe the second field of view the values of depths 102 within first field of view 104 are adjusted to account for the angular movement of camera 100.

[0302] FIG. 37B illustrates 2D floor map segments 106 and 203 approximated from plotted depths 102 and 200, respectively. Segments 106 and 200 are bounded by dashed lines 107 and 204, respectively. 2D floor map segment 205 constructed from 2D floor map segments 106 and 203 and bounded by the outermost dashed lines of 107 and 204 is also illustrated. Depths 200 taken within second field of view 201 are compared to depths 102 taken within first field of view 104 to identify the area of overlap bounded by the innermost dashed lines of 204 and 107. An area of overlap is identified when a number of consecutive depths from first field of view 104 and second field of view 201 are similar. In one embodiment, the area of overlap, once identified, may be extended to include a number of depths immediately before and after the identified overlapping area. 2D floor plan segment 106 approximated from plotted depths 102 taken within first field of view 104 and 2D floor plan segment 203 approximated from plotted depths 200 taken within second field of view 201 are combined at the area of overlap to construct 2D floor plan segment 205. In some embodiments, matching patterns in the value of the depths recognized in depths 102 and 200 are used in identifying the area of overlap between the two. For example, the sudden decrease in the value of the depth observed in depths 102 and 200 can be used to estimate the overlap of the two sets of depths perceived. The method of using camera 100 to perceive depths within consecutively overlapping fields of view and the processor to combine them at identified areas of overlap is repeated until all areas of the environment are discovered and a map is constructed. In some embodiments, the constructed map is stored in memory for future use. In other embodiments, a map of the environment is constructed at each use. In some embodiments, once the map is constructed, the processor determines a path for the robot to follow, such as by using the entire constructed map, waypoints, or endpoints, etc.

[0303] In some embodiments, it is not necessary that the value of overlapping depths from the first and second fields of view be the exact same for the area of overlap to be identified. It is expected that measurements will be affected by noise, resolution of the equipment taking the measurement, and other inaccuracies inherent to measurement devices. Similarities in the value of depths from the first and second fields of view may be identified when the values of the depths are within a tolerance range of one another. The area of overlap may also be identified by recognizing matching patterns among the depths from the first and second fields of view, such as a pattern of increasing and decreasing values. Once an area of overlap is identified, in some embodiments, it may be used as the attachment point and the two fields of view may be attached to form a larger field of view. Since the overlapping depths from the first and second fields of view within the area of overlap do not necessarily have the exact same values and a range of tolerance between their values is allowed, the overlapping depths from the first and second fields of view may be used to calculate new depths for the overlapping area using a moving average or another suitable mathematical convolution. This is expected to improve the accuracy of the depths as they are calculated from the combination of two separate sets of measurements. The newly calculated depths may be used as the depths for the overlapping area, substituting for the depths from the first and second fields of view within the area of overlap. The new depths may then be used as ground truth values to adjust all other perceived depths outside the overlapping area. Once all depths are adjusted, a first segment of the map is complete. This method may be repeated such that the camera perceives depths (or pixel intensities indicative of depth) within consecutively overlapping fields of view as it moves, and the processor identifies the area of overlap and combines overlapping depths to construct a map of the environment.

[0304] In some embodiments, the amount of rotation between two consecutively observed fields of view may vary. In some cases, the amount of overlap between the two consecutive fields of view may depend on the angular displacement of the robot as it moves from taking measurements within one field of view to taking measurements within the next field of view, or a robot may have two or more cameras at different positions (and thus poses) on the robot to capture two fields of view, or a single camera may be moved on a static robot to capture two fields of view from different poses. In some embodiments, the mounted camera may rotate (or otherwise scans, e.g., horizontally and vertically) independently of the robot. In such cases, the rotation of the mounted camera in relation to the robot is measured. In another embodiment, the values of depths perceived within the first field of view may be adjusted based on the predetermined or measured angular (and in some cases, linear) movement of the depth perceiving device.

[0305] In some embodiments, the depths from the first field of view may be compared with the depths from the second field of view. An area of overlap between the two fields of view may be identified (e.g., determined) when (e.g., during evaluation a plurality of candidate overlaps) a number of consecutive (e.g., adjacent in pixel space) depths from the first and second fields of view are equal or close in value. Although the value of overlapping perceived depths from the first and second fields of view may not be exactly the same, depths with similar values, to within a tolerance range of one another, may be identified (e.g., determined to correspond based on similarity of the values). Furthermore, identifying matching patterns in the value of depths perceived within the first and second fields of view may also be used in identifying the area of overlap. For example, a sudden increase then decrease in the depth values observed in both sets of measurements may be used to identify the area of overlap. Examples include applying an edge detection algorithm (like Haar or Canny) to the fields of view and aligning edges in the resulting transformed outputs. Other patterns, such as increasing values followed by constant values or constant values followed by decreasing values or any other pattern in the values of the perceived depths, may also be used to estimate the area of overlap. A Jacobian and Hessian matrix may be used to identify such similarities. The processor may determine the Jacobian m×n matrix using

[0306] $J=\left[\begin{array}{ccc}\frac{\partial f_1}{\partial x_1}& \cdots & \frac{\partial f_1}{\partial x_n}\\ ⋮& \ddots & ⋮\\ \frac{\partial f_m}{\partial x_1}& \cdots & \frac{\partial f_m}{\partial x_n}\end{array}\right],$
wherein ƒ is a function with input vector x=(x₁, . . . , x_n). The Jacobian matrix generalizes the gradient of a function of multiple variables. If the function ƒ is differentiable at a point x, the Jacobian matrix provides a linear map of the best linear approximation of the function ƒ near point x. If the gradient of function ƒ is zero at point x, then x is a critical point. To identify if the critical point is a local maximum, local minimum or saddle point, the Hessian matrix may be determined, which when compared for the two sets of overlapping depths, may be used to identify overlapping points. This proves to be relatively computationally inexpensive. The Hessian matrix is related to Jacobian matrix by H=J(∇ƒ(x)).

[0307] In some embodiments, thresholding may be used in identifying the area of overlap wherein areas or objects of interest within an image may be identified using thresholding as different areas or objects have different ranges of pixel intensity. For example, an object captured in an image, the object having high range of intensity, can be separated from a background having low range of intensity by thresholding wherein all pixel intensities below a certain threshold are discarded or segmented, leaving only the pixels of interest. In some embodiments, a metric can be used to indicate how good of an overlap there is between the two sets of perceived depths. For example, the Szymkiewicz-Simpson coefficient may be determine by the processor by dividing the number of overlapping readings between two overlapping sets of data, X and Y, by the number of readings of the smallest of the two data sets, i.e., overlap

[0308] $\left(X,Y\right)=\frac{X\bigcap Y}{\min \left(X,Y\right)}.$
The data sets are a string of values, the values being the Euclidean norms in the context of some embodiments. A larger overlap coefficient indicates higher accuracy. In some embodiments lower coefficient readings are raised to the power of alpha, alpha being a number between 0 and 1 and are stored in a table with the Szymkiewicz-Simpson coefficient.

[0309] Or some embodiments may determine an overlap with a convolution. Some embodiments may implement a kernel function that determines an aggregate measure of differences (e.g., a root mean square value) between some or all of a collection of adjacent depth readings in one image relative to a portion of the other image to which the kernel function is applied. Some embodiments may then determine the convolution of this kernel function over the other image, e.g., in some cases with a stride of greater than one pixel value. Some embodiments may then select a minimum value of the convolution as an area of identified overlap that aligns the portion of the image from which the kernel function was formed with the image to which the convolution was applied.

[0310] To ensure an area of overlap exists between depths perceived within consecutive frames of the camera, the frame rate of the camera should be fast enough to capture more than one frame of measurements in the time it takes the robotic device to rotate the width of the frame. This is expected to guarantee that at least a minimum area of overlap exists if there is angular displacement, though embodiments may also operate without overlap in cases where stitching is performed between images captured in previous sessions or where images from larger displacements are combined. The amount of overlap between depths from consecutive fields of view may be dependent on the amount of angular displacement from one field of view to the next field of view. The larger the area of overlap, the more accurate the map segment constructed from the overlapping depths. If a larger portion of depths making up the map segment are the result of a combination of overlapping depths from at least two overlapping fields of view, accuracy of the map segment is improved as the combination of overlapping depths provides a more accurate reading. Furthermore, with a larger area of overlap, it is easier to find the area of overlap between depths from two consecutive fields of view as more similarities exists between the two sets of data. In some cases, a confidence score may be determined for overlap determinations, e.g., based on an amount of overlap and aggregate amount of disagreement between depth vectors in the area of overlap in the different fields of view, and the above Bayesian techniques down-weight updates to priors based on decreases in the amount of confidence. In some embodiments, the size of the area of overlap may be used to determine the angular movement and may be used to adjust odometer information to overcome inherent noise of the odometer (e.g., by determining an average movement vector for the robot based on both a vector from the odometer and a movement vector inferred from the fields of view). The angular movement of the robot from one field of view to the next may, for example, be determined based on the angular increment between vector measurements taken within a field of view, parallax changes between fields of view of matching objects or features thereof in areas of overlap, and the number of corresponding depths overlapping between the two fields of view.

[0311] Due to measurement noise, discrepancies between the value of depths within the area of overlap from the first field of view and the second field of view may exist and the values of the overlapping depths may not be the exact same. In such cases, new depths may be calculated, or some of the depths may be selected as more accurate than others. For example, the overlapping depths from the first field of view and the second field of view (or more fields of view where more images overlap, like more than three, more than five, or more than 10) may be combined using a moving average (or some other measure of central tendency may be applied, like a median or mode) and adopted as the new depths for the area of overlap. The minimum sum of errors may also be used to adjust and calculate new depths for the overlapping area to compensate for the lack of precision between overlapping depths perceived within the first and second fields of view. By way of further example, the minimum mean squared error may be used to provide a more precise estimate of depths within the overlapping area. Other mathematical methods may also be used to further process the depths within the area of overlap, such as split and merge algorithm, incremental algorithm, Hough Transform, line regression, Random Sample Consensus, Expectation-Maximization algorithm, or curve fitting, for example, to estimate more realistic depths given the overlapping depths perceived within the first and second fields of view. The calculated depths are used as the new depths for the overlapping area. In another embodiment, the k-nearest neighbors algorithm can be used where each new depth may be calculated as the average of the values of its k-nearest neighbors.

[0312] For instance, due to measurement noise, discrepancies may exist between the value of overlapping depths 102 and 200 resulting in staggered floor plan segments 106 and 203, respectively, shown in FIG. 38A. If there were no discrepancies, segments 106 and 203 would perfectly align. When there are discrepancies, overlapping depths may be averaged and adopted as new depths within the overlapping area, resulting in segment 300 halfway between segment 106 and 203, shown in FIG. 38B. It can be seen that the mathematical adjustment applied to the overlapping depths is applied to depths beyond the area of overlap wherein the new depths for the overlapping area are considered ground truth. In other embodiments, new depths for the area of overlap may be calculated using other mathematical methods, such as the minimum sum of errors, minimum mean squared error, split and merge algorithm, incremental algorithm, Hough Transform, line regression, Random Sample Consensus, Expectation-Maximization algorithm, or curve fitting, for example, given overlapping depths perceived within consecutive fields of view. In another example, plotted depths 102 are fixed and used as a reference while second set of depths 200, overlapping with first set of depths 102, are transformed to match fixed reference 102 such that map segment 203 is aligned as best as possible with segment 106, resulting in segment 301 after combining the two in FIG. 38C. In some embodiments, the k-nearest neighbors algorithm may be used where new depths are calculated from k-nearest neighbors, wherein k is a specified integer value. FIG. 38D illustrates map segment 302 from using k-nearest neighbors approach with overlapping depths 102 and 200.

[0313] Some embodiments may implement DB-SCAN on depths and related values like pixel intensity, e.g., in a vector space that includes both depths and pixel intensities corresponding to those depths, to determine a plurality of clusters, each corresponding to depth measurements of the same feature of an object. Some embodiments may execute a density-based clustering algorithm, like DBSCAN, to establish groups corresponding to the resulting clusters and exclude outliers. To cluster according to depth vectors and related values like intensity, some embodiments may iterate through each of the depth vectors and designate a depth vector as a core depth vector if at least a threshold number of the other depth vectors are within a threshold distance in the vector space (which may be higher than three dimensional in cases where pixel intensity is included). Some embodiments may then iterate through each of the core depth vectors and create a graph of reachable depth vectors, where nodes on the graph are identified in response to non-core corresponding depth vectors being within a threshold distance of a core depth vector in the graph, and in response to core depth vectors in the graph being reachable by other core depth vectors in the graph, where to depth vectors are reachable from one another if there is a path from one depth vector to the other depth vector where every link and the path is a core depth vector and is it within a threshold distance of one another. The set of nodes in each resulting graph, in some embodiments, may be designated as a cluster, and points excluded from the graphs may be designated as outliers that do not correspond to clusters.

[0314] Some embodiments may then determine the centroid of each cluster in the spatial dimensions of an output depth vector for constructing maps. In some cases, all neighbors may have equal weight and in other cases the weight of each neighbor may depend on its distance from the depth considered or (i.e., and/or) similarity of pixel intensity values. In some embodiments, the k-nearest neighbors algorithm may only be applied to overlapping depths with discrepancies. In some embodiments, a first set of readings may be fixed and used as a reference while the second set of readings, overlapping with the first set of readings, may be transformed to match the fixed reference. In one embodiment, the transformed set of readings may be combined with the fixed reference and used as the new fixed reference. In another embodiment, only the previous set of readings may be used as the fixed reference. Initial estimation of a transformation function to align the newly read data to the fixed reference may be iteratively revised in order to produce minimized distances from the newly read data to the fixed reference. The transformation function may be the sum of squared differences between matched pairs from the newly read data and prior readings from the fixed reference. For example, in some embodiments, for each value in the newly read data, the closest value among the readings in the fixed reference may be found. In a next step, a point to point distance metric minimization technique may be used such that it may best align each value in the new readings to its match found in the prior readings of the fixed reference. One point to point distance metric minimization technique that may be used estimates the combination of rotation and translation using a root mean square. The process may be iterated to transform the newly read values using the obtained information. These methods may be used independently or may be combined to improve accuracy. In one embodiment, the adjustment applied to overlapping depths within the area of overlap may be applied to other depths beyond the identified area of overlap, wherein the new depths within the overlapping area may be considered ground truth when making the adjustment.

[0315] In some embodiments, a modified RANSAC approach may be used where any two points, one from each data set, are connected by a line. A boundary may be defined with respect to either side of the line. Any points from either data set beyond the boundary are considered outliers and are excluded. The process may be repeated using another two points. The process is intended to remove outliers to achieve a higher probability of being the true distance to the perceived wall. Consider an extreme case where a moving object is captured in two frames overlapping with several frames captured without the moving object. The approach described or RANSAC method may be used to reject data points corresponding to the moving object. This method or a RANSAC method may be used independently or combined with other processing methods described above. As an example, consider two overlapping sets of plotted depths 400 and 401 of a wall in FIG. 39A. If overlap between depths 400 and 401 is ideal, the map segments used to approximate the wall for both sets of data align, resulting in combined map segment 402. However, in certain cases there are discrepancies in overlapping depths 400 and 401, resulting in FIG. 39B where segments 403 and 404 approximating the depth to the same wall do not align. To achieve better alignment of depths 400 and 401, any two points, one from each data set, such as points 405 and 406, are connected by line 407. Boundary 408 is defined with respect to either side of line 407. Any points from either data set beyond the boundary are considered outliers and are excluded. The process is repeated using another two points. The process is intended to remove outliers to achieve a higher probability of determining the true distance to the perceived wall.

[0316] In some embodiments, images may be preprocessed before determining overlap. For instance, some embodiments may infer an amount of displacement of the robot between images, e.g., by integrating readings from an inertial measurement unit or odometer (in some cases after applying a Kalman filter), and then transform the origin for vectors in one image to match an origin for vectors in the other image based on the measured displacement, e.g., by subtracting a displacement vector from each vector in the subsequent image. Further, some embodiments may down-res images to afford faster matching, e.g., by selecting every other, every fifth, or more or fewer vectors, or by averaging adjacent vectors to form two lower-resolution versions of the images to be aligned. The resulting alignment may then be applied to align the two higher resolution images.

[0317] In some embodiments, computations may be expedited based on a type of movement of the robot between images. For instance, some embodiments may determine if the robot's displacement vector between images has less than a threshold amount of vertical displacement (e.g., is zero). In response, some embodiments may apply the above described convolution in with a horizontal stride and less or zero vertical stride, e.g., in the same row of the second image from which vectors are taken in the first image to form the kernel function.

[0318] In some embodiments, the area of overlap may be expanded to include a number of depths perceived immediately before and after (or spatially adjacent) the perceived depths within the identified overlapping area. Once an area of overlap is identified (e.g., as a bounding box of pixel positions or threshold angle of a vertical plane at which overlap starts in each field of view), a larger field of view may be constructed by combining the two fields of view using the perceived depths within the area of overlap as the attachment points. Combining may include transforming vectors with different origins into a shared coordinate system with a shared origin, e.g., based on an amount of translation or rotation of a depth sensing device between frames, for instance, by adding a translation or rotation vector to depth vectors. The transformation may be performed before, during, or after combining.

[0319] In some embodiments, more than two consecutive fields of view overlap, resulting in more than two sets of depths falling within an area of overlap. This may happen when the amount of angular movement between consecutive fields of view is small, especially if the frame rate of the camera is fast such that several frames within which vector measurements are taken are captured while the robot makes small movements, or when the field of view of the camera is large or when the robot has slow angular speed and the frame rate of the camera is fast. Higher weight may be given to depths within areas of overlap where more than two sets of depths overlap, as increased number of overlapping sets of depths provide a more accurate ground truth. In some embodiments, the amount of weight assigned to perceived depths may be proportional to the number of depths from other sets of data overlapping with it. Some embodiments may merge overlapping depths and establish a new set of depths for the overlapping area with a more accurate ground truth. The mathematical method used may be a moving average or a more complex method. FIG. 40A illustrates robot 500 with mounted camera 501 perceiving depths 502, 503, and 504 within consecutively overlapping fields of view 505, 506, and 507, respectively. In this case, depths 502, 503, and 504 have overlapping depths 508. FIG. 40B illustrates map segments 509, 510, and 511 approximated from plotted depths 502, 503, and 504, respectively. The map segments 509, 510, and 511 are combined at overlapping areas to construct larger map segment 512. In some embodiments, depths falling within overlapping area 513, bound by lines 514, have higher weight than depths beyond overlapping area 513 as three sets of depths overlap within area 513 and increased number of overlapping sets of perceived depths provide a more accurate ground truth.

[0320] In some embodiments, the processor of the robot may generate or update a map of the environment using data collected by at least one imaging sensor or camera. In one embodiment, an imaging sensor may measure vectors from the imaging sensor to objects in the environment and the processor may calculate the L2 norm of the vectors using ∥x∥_P=(Σ_i|x_i|^P)^1/P with P=2 to estimate depths to objects. In some embodiments, each L2 norm of a vector may be replaced with an average of the L2 norms corresponding with neighboring vectors. In some embodiments, the processor may use more sophisticated methods to filter sudden spikes in the sensor readings. In some embodiments, sudden spikes may be deemed as outliers. In some embodiments, sudden spikes or drops in the sensor readings may be the result of a momentary environmental impact on the sensor. In some embodiments, the processor may adjust previous data to account for a measured movement of the robot as it moves from observing one field of view to the next (e.g., differing from one another due to a difference in sensor pose). In some embodiments, a movement measuring device such as an odometer, OTS, gyroscope, IMU, optical flow sensor, etc. may measure movement of the robot and hence the sensor (assuming the two move as a single unit). In some instances, the processor matches a new set of data with data previously captured. In some embodiments, the processor compares the new data to the previous data and identifies a match when a number of consecutive readings from the new data and the previous data are similar. In some embodiments, identifying matching patterns in the value of readings in the new data and the previous data may also be used in identifying a match. In some embodiments, thresholding may be used in identifying a match between the new and previous data wherein areas or objects of interest within an image may be identified using thresholding as different areas or objects have different ranges of pixel intensity. In some embodiments, the processor may determine a cost function and may minimize the cost function to find a match between the new and previous data. In some embodiments, the processor may create a transform and may merge the new data with the previous data and may determine if there is a convergence. In some embodiments, the processor may determine a match between the new data and the previous data based on translation and rotation of the sensor between consecutive frames measured by an IMU. For example, overlap of data may be deduced based on interoceptive sensor measurements. In some embodiments, the translation and rotation of the sensor between frames may be measured by two separate movement measurement devices (e.g., optical encoder and gyroscope) and the movement of the robot may be the average of the measurements from the two separate devices. In some embodiments, the data from one movement measurement device is the movement data used and the data from the second movement measurement device is used to confirm the data of the first movement measurement device. In some embodiments, the processor may use movement of the sensor between consecutive frames to validate the match identified between the new and previous data. Or, in some embodiments, comparison between the values of the new data and previous data may be used to validate the match determined based on measured movement of the sensor between consecutive frames. For example, the processor may use data from an exteroceptive sensor (e.g., image sensor) to determine an overlap in data from an IMU, encoder, or OTS. In some embodiments, the processor may stitch the new data with the previous data at overlapping points to generate or update the map. In some embodiments, the processor may infer the angular disposition of the robot based on a size of overlap of the matching data and may use the angular disposition to adjust odometer information to overcome inherent noise of an odometer.

[0321] In some embodiments, the processor may generate or update a spatial representation using data of captured images of the environment (e.g., depth data inferred from the image, pixel intensities from the image, etc.), as described above. In some embodiments, the processor combines image data at overlapping points to generate the spatial representation. In some embodiments, the processor may localize patches with gradients in two different orientations by using simple matching criterion to compare two image patches. Examples of simple matching criterion include the summed square difference or weighted summed square difference, E_WSSD(UU)=Σ_iω(x_i)[I₁(x_i+u)−I₀(x_i)]², wherein I₀ and I₁ are the two images being compared, u=(u, v) is the displacement vector, w(x) is a spatially varying weighting (or window) function. The summation is over all the pixels in the patch. In embodiments, the processor may not know which other image locations the feature may end up being matched with. However, the processor may determine how stable the metric is with respect to small variations in position Δu by comparing an image patch against itself. In some embodiments, the processor may need to account for scale changes, rotation, and/or affine invariance for image matching and object recognition. To account for such factors, the processor may design descriptors that are rotationally invariant or estimate a dominant orientation at each detected key point. In some embodiments, the processor may detect false negatives (failure to match) and false positives (incorrect match). Instead of finding all corresponding feature points and comparing all features against all other features in each pair of potentially matching images, which is quadratic in the number of extracted features, the processor may use indexes. In some embodiments, the processor may use multi-dimensional search trees or a hash table, vocabulary trees, K-Dimensional tree, and best bin first to help speed up the search for features near a given feature. In some embodiments, after finding some possible feasible matches, the processor may use geometric alignment and may verify which matches are inliers and which ones are outliers. In some embodiments, the processor may adopt a theory that a whole image is a translation or rotation of another matching image and may therefore fit a global geometric transform to the original image. The processor may then only keep the feature matches that fit the transform and discard the rest. In some embodiments, the processor may select a small set of seed matches and may use the small set of seed matches to verify a larger set of seed matches using random sampling or RANSAC. In some embodiments, after finding an initial set of correspondences, the processor may search for additional matches along epipolar lines or in the vicinity of locations estimated based on the global transform to increase the chances over random searches.

[0322] In some embodiments, the processor may execute a classification algorithm for baseline matching of key points, wherein each class may correspond to a set of all possible views of a key point. The algorithm may be provided various images of a particular object such that it may be trained to properly classify the particular object based on a large number of views of individual key points and a compact description of the view set derived from statistical classifications tools. At run-time, the algorithm may use the description to decide to which class the observed feature belongs. Such methods (or modified versions of such methods) may be used and are further described by V. Lepetit, J. Pilet and P. Fua, “Point matching as a classification problem for fast and robust object pose estimation,” Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004, the entire contents of which are hereby incorporated by reference. In some embodiments, the processor may use an algorithm to detect and localize boundaries in scenes using local image measurements. The algorithm may generate features that respond to changes in brightness, color and texture. The algorithm may train a classifier using human labeled images as ground truth. In some embodiments, the darkness of boundaries may correspond with the number of human subjects that marked a boundary at that corresponding location. The classifier outputs a posterior probability of a boundary at each image location and orientation. Such methods (or modified versions of such methods) may be used and are further described by D. R. Martin, C. C. Fowlkes and J. Malik, “Learning to detect natural image boundaries using local brightness, color, and texture cues,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 5, pp. 530-549, May 2004, the entire content of which is hereby incorporated by reference. In some embodiments, an edge in an image may correspond with a change in intensity. In some embodiments, the edge may be approximated using a piecewise straight curve composed of edgels (i.e., short, linear edge elements), each including a direction and position. The processor may perform edgel detection by fitting a series of one-dimensional surfaces to each window and accepting an adequate surface description based on least squares and fewest parameters. Such methods (or modified versions of such methods) may be used and are further described by V. S. Nalwa and T. O. Binford, “On Detecting Edges,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, no. 6, pp. 699-714, November 1986. In some embodiments, the processor may track features based on position, orientation, and behavior of the feature. The position and orientation may be parameterized using a shape model while the behavior is modeled using a three-tier hierarchical motion model. The first tier models local motions, the second tier is a Markov motion model, and the third tier is a Markov model that models switching between behaviors. Such methods (or modified versions of such methods) may be used and are further described by A. Veeraraghavan, R. Chellappa and M. Srinivasan, “Shape-and-Behavior Encoded Tracking of Bee Dances,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 3, pp. 463-476, March 2008.

[0323] In some embodiments, the processor may detect sets of mutually orthogonal vanishing points within an image. In some embodiments, once sets of mutually orthogonal vanishing points have been detected, the processor may search for three dimensional rectangular structures within the image. In some embodiments, after detecting orthogonal vanishing directions, the processor may refine the fitted line equations, search for corners near line intersections, and then verify the rectangle hypotheses by rectifying the corresponding patches and looking for a preponderance of horizontal and vertical edges. In some embodiments, the processor may use a Markov Random Field (MRF) to disambiguate between potentially overlapping rectangle hypotheses. In some embodiments, the processor may use a plane sweep algorithm to match rectangles between different views. In some embodiments, the processor may use a grammar of potential rectangle shapes and nesting structures (between rectangles and vanishing points) to infer the most likely assignment of line segments to rectangles.

[0324] In some embodiments, the processor may locally align image data of neighbouring frames using methods (or a variation of the methods) described by Y. Matsushita, E. Ofek, Weina Ge, Xiaoou Tang and Heung-Yeung Shum, “Full-frame video stabilization with motion inpainting,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 7, pp. 1150-1163, July 2006. In some embodiments, the processor may align images and dynamically construct an image mosaic using methods (or a variation of the methods) described by M. Hansen, P. Anandan, K. Dana, G. van der Wal and P. Burt, “Real-time scene stabilization and mosaic construction,” Proceedings of 1994 IEEE Workshop on Applications of Computer Vision, Sarasota, Fla., USA, 1994, pp. 54-62.

[0325] In some embodiments, the processor may use least squares, non-linear least squares, non-linear regression, preemptive RANSAC, etc. for two dimensional alignment of images, each method varying from the others. In some embodiments, the processor may identify a set of matched feature points {(x_i, x_i′)} for which the planar parametric transformation may be given by x′=ƒ(x; p), wherein p is best estimate of the motion parameters. In some embodiments, the processor minimizes the sum of squared residuals

[0326] $E_{LS}\left(u\right)=\sum _i{r_i}^2=\sum _i{f\left(x_i;p\right)-x_i^{\prime }}^2,$
wherein

[0327] $r_i=f\left(x_i;p\right)-x_i^{\prime }=x_i^{\bigwedge \prime }-x_i^{\sim \prime }$
is the residual between the measured location

[0328] $x_i^{\bigwedge \prime }$
and the predicted location

[0329] $x_i^{\sim \prime }=f\left(x_i;p\right).$
In some embodiments, the processor may minimize the sum of squared residuals by solving the Symmetric Positive Definite (SPD) system of normal equations and associating a scalar variance estimate σ_i² with each correspondence to achieve a weighted version of least squares that may account for uncertainty. FIG. 41A illustrates an example of four unaligned two dimensional images. FIG. 41B illustrates the alignment of the images achieved using methods such as those described herein, and FIG. 41C illustrates the four images stitched together after alignment. In some embodiments, the processor may use three dimensional linear or non-linear transformations to map translations, similarities, affine, by least square method or using other methods. In embodiments, there may be several parameters that are pure translation, a clean rotation, or affine. Therefore, a full search over the possible range of values may be impractical. In some embodiments, instead of using a single constant translation vector such as u, the processor may use a motion field or correspondence map x′(x; p) that is spatially varying and parameterized by a low dimensional vector p, wherein x′ may be any motion model. Since the Hessian and residual vectors for such parametric motion is more computationally demanding than a simple translation or rotation, the processor may use a sub block and approach the analysis of motion using parametric methods. Then, once a correspondence is found, the processor may analyze the entire image using non-parametric methods.

[0330] In some embodiments, the processor may associate a feature in a captured image with a light point in the captured image. In some embodiments, the processor may associate features with light points based on machine learning methods such as K nearest neighbors or clustering. In some embodiments, the processor may monitor the relationship between each of the light points and respective features as the robot moves in following time slots. The processor may disassociate some associations between light points and features and generate some new associations between light points and features. FIG. 42A illustrates an example of two captured images 8000 including three features 8001 (a tree, a small house, a large house) and light points 8002 associated with each of the features 8001. Associated features 8001 and light points 8002 are included within the same dotted shape 8003. FIG. 42B illustrates the captured image 8000 in FIG. 42A at a first time point, a captured image 8004 at a second time point, and a captured image 8005 at a third time point as the robot moves within the environment. As the robot moves, some features 8001 and light points 8802 associated at one time point become disassociated at another time point, such as in image 8004 wherein a feature (the large house) from image 8000 is no longer in the image 8004. Or some new associations between features 8001 and light points 8002 emerge at a next time point, such as in image 8005 wherein a new feature (a person) is captured in the image. In some embodiments, the robot may include an LED point generator that spins. FIG. 43A illustrates a robot 8100, a spinning LED light point generator 8101, light points 8102 that are emitted by light point generator 8101, and camera 8103 that captures images of light points 8102. In some embodiments, the camera of the robot captures images of the projected light point. In some embodiments, the light point generator is faster than the camera resulting in multiple light points being captured in an image fading from one side to another. This is illustrated in FIG. 43B, wherein light points 8104 fade from one side to the other. In some embodiments, the robot may include a full 360 degrees LIDAR. In some embodiments, the robot may include multiple cameras. This may improve accuracy of estimates based on image data. For example, FIG. 43C illustrates the robot 8100 with four cameras 8103.

[0331] In embodiments, the goal of extracting features of an image is to match the image against other images. However, it is not uncommon that matched features need some processing to compensate for feature displacements. Such feature displacements may be described with a two or three dimensional geometric or non-geometric transformation. In some embodiments, the processor may estimate motion between two or more sets of matched two dimensional or three dimensional points when superimposing virtual objects, such as predictions or measurements on a real live video feed. In some embodiments, the processor may determine a three dimensional camera motion. The processor may use a detected two dimensional motion between two frames to align corresponding image regions. The two dimensional registration removes all effects of camera rotation and the resulting residual parallax displacement field between the two region aligned images is an epipolar field centered at the Focus-of-Expansion. The processor may recover the three dimensional camera translation from the epipolar field and may compute the three dimensional camera rotation based on the three dimensional translation and detected two dimensional motion. Such methods (or modified versions of such methods) may be used and are further described by M. Irani, B. Rousso and S. Peleg, “Recovery of ego-motion using region alignment,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 3, pp. 268-272, March 1997. In some embodiments, the processor may compensate for three dimensional rotation of the camera using an EKF to estimate the rotation between frames. Such methods (or modified versions of such methods) may be used and are further described by C. Morimoto and R. Chellappa, “Fast 3D stabilization and mosaic construction,” Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Juan, Puerto Rico, USA, 1997, pp. 660-665. In some embodiments, the processor may execute an algorithm that learns parametrized models of optical flow from image sequences. A class of motions are represented by a set of orthogonal basis flow fields computed from a training set. Complex image motions are represented by a linear combination of a small number of the basis flows. Such methods (or modified versions of such methods) may be used and are further described by M. J. Black, Y. Yacoob, A. D. Jepson and D. J. Fleet, “Learning parameterized models of image motion,” Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Juan, Puerto Rico, USA, 1997, pp. 561-567. In some embodiments, the processor may align images by recovering original three dimensional camera motion and a sparse set of three dimensional static scene points. The processor may then determine a desired camera path automatically (e.g., by fitting a linear or quadratic path) or interactively. Finally, the processor may perform a least squares optimization that determines a spatially-varying warp from a first frame into a second frame. Such methods (or modified versions of such methods) may be used and are further described by F. Liu, M. Gleicher, H. Jin and A. Agarwala, “Content-preserving warps for 3D video stabilization,” in ACM Transactions on Graphics, vol. 28, no. 3, article 44, July 2009.

[0332] In some embodiments, the processor may use methods such as video stabilization used in camcorders and still cameras and software such as Final Cut Pro or imovie available for improving the quality of shaky hands to compensate for movement of the robot on imperfect surfaces. In some embodiments, the processor may estimate motion by computing an independent estimate of motion at each pixel by minimizing the brightness or color difference between corresponding pixels summed over the image. In continuous form, this may be determined using an integral. In some embodiments, the processor may perform the summation by using a patch-based or window-based approach. While several examples illustrate or describe two frames, wherein one image is taken and a second image is taken immediately after, the concepts described herein are not limited to being applied to two images and may be used for a series of images (e.g., video).

[0333] In some embodiments, the processor may generate a velocity map based on multiple images taken from multiple cameras at multiple time stamps, wherein objects do not move with the same speed in the velocity map. Speed of movement is different for different objects depending on how the objects are positioned in relation to the cameras. FIG. 44 illustrates an example of a velocity map, each line corresponding with a different object. In embodiments, tracking objects as a whole, rather than pixels, results in objects at different depths moving in the scene at different speeds. In some embodiments, the processor may detect objects based on features and objects grouped together based on shiny points of structured light emitted onto the object surfaces (as described above). In some embodiments, the processor may determine at which speed the shiny points in the images move. Since the shiny points of the emitted structured light move within the scene when the robot moves, each of the shiny points create a motion, such as Brownian Motion. According to Brownian motion, when speed of movement of the robot increases, the entropy increases. In some embodiments, the processor may categorize areas with higher entropy with different depths than areas with low entropy. In some embodiments, the processor may categorize areas with similar entropy as having the same depths from the robot. In some embodiments, the processor may determine areas the robot may traverse based on the entropy information. For example, FIG. 45 illustrates a robot 8400 tasked with passing through a narrow path 8401 with obstacles 8402 on both sides. The processor of the robot 8400 may know where to direct the robot 8400 based on the entropy information. Obstacles 8402 on the two sides of the path 8401 have similar entropies while the path 8401 has a different entropy than the obstacles as the path 8401 is open ended, resulting in the entropy presenting as far objects which is opposite than the entropy of obstacles 8402 presenting as near objects.

[0334] In some embodiments, the processor may not know the correspondence between data points a priori when merging images and may start by matching nearby points. The processor may then update the most likely correspondence and iterate on. In some embodiments, the processor of the robot may localize the robot against the environment based on feature detection and matching. This may be synonymous to pose estimation or determining the position of cameras and other sensors of the robot relative to a known three dimensional object in the scene. In some embodiments, the processor stitches images and creates a spatial representation of the scene after correcting images with preprocessing.

[0335] In some embodiments, a captured image may be processed prior to using the image in generating or updating the map. In some embodiments, processing may include replacing readings corresponding to each pixel with averages of the readings corresponding to neighboring pixels. FIG. 46 illustrates an example of replacing a reading 1800 corresponding with a pixel with an average of the readings 1801 of corresponding neighboring pixels 1802. In some embodiments, pixel values of an image may be read into an array or any data structure or container capable of indexing elements of the pixel values. In some embodiments, the data structure may provide additional capabilities such as insertion or deletion in the middle, start, or end by swapping pointers in memory. In some embodiments, indices such as i, j, and k may be used to access each element of the pixel values. In some embodiments, negative indices count from the last element backwards. In some embodiments, the processor of the robot may transform the pixel values into grayscale. In some embodiments, the grayscale may range from black to white and may be divided into a number of possibilities. For example, numbers ranging from 0 to 256 may be used to describe 256 buckets of color intensities. Each element of the array may have a value that corresponds with one of buckets of color intensities. In some embodiments, the processor may create a chart showing the popularity of each color bucket within the image. For example, the processor may iterate through the array and may increase a popularity vote of the 0 color intensity bucket for each element of the array having a value of 0. This may be repeated for each of the 256 buckets of color intensities. In some embodiments, characteristics of the environment at the time the image is captured may affect the popularity of the 256 buckets of color intensities. For example, an image captured on a bright day may have increased popularity for color buckets corresponding with less intense colors. In some embodiments, principal component analysis may be used to reduce the dimensionality of an image as the number of pixels increases with resolution. For example, dimensions of a megapixel image are in the millions. In some embodiments, singular value decomposition may be used to find principal components.

[0336] In some embodiments, the processor of the robot may store a portion of the L2 norms, such as L2 norms to critical points within the environment. In some embodiments, critical points may be second or third derivatives of a function connecting the L2 norms. In some embodiments, critical points may be second or third derivatives of raw pixel values. In some embodiments, the simplification may be lossy. In some embodiments, the lost information may be retrieved and pruned in each tick of the processor as the robot collects more information. In some embodiments, the accuracy of information may increase as the robot moves within the environment. For example, a critical point may be discovered to include two or more critical points over time. In some embodiments, loss of information may not occur or may be negligible when critical points are extracted with high accuracy.

[0337] In some embodiments, information sensed by a depth perceiving sensor may be processed and translated into depth measurements, which, in some embodiments, may be reported in a standardized measurement unit, such as millimeter or inches, for visualization purposes, or may be reported in non-standard units. Depth may be inferred (or otherwise perceived) in various ways. For example, depths may be inferred based (e.g., exclusively based on or in combination with other inputs) on pixel intensities from a depth image captured by a depth camera. Depths may be inferred from the time it takes for an infrared light (or sound) transmitted by a sensor to reflect off of an object and return back to the depth perceiving device or by a variety of other techniques. For example, using a time-of-flight camera, depth may be estimated based on the time required for light transmitted from a robot to reflect off of an object and return to a camera on the robot, or using an ultrasonic sensor, depth may be estimated based on the time required for a sound pulse transmitted from a robot-mounted ultrasonic transducer to reflect off of an object and return to the sensor. In some embodiments, a one or more IR (or with other portions of the spectrum) illuminators (such as those mounted on a robot) may project light onto objects (e.g., with a spatial structured pattern (like with structured light), or by scanning a point-source of light), and the resulting projection may be sensed with one or more cameras (such as robot-mounted cameras offset from the projector in a horizontal direction). In resulting images from the one or more cameras, the position of pixels with high intensity may be used to infer depth (e.g., based on parallax, based on distortion of a projected pattern, or both in captured images). In some embodiments, raw data (e.g., sensed information from which depth has not been inferred), such as time required for a light or sound pulse to reflect off of an object or pixel intensity may be used directly (e.g., without first inferring depth) in creating a map of an environment, which is expected to reduce computational costs, as the raw data does not need to be first processed and translated into depth values, e.g., in metric or imperial units.

[0338] In embodiments, raw data may be provided in matrix form or in an ordered list (which is not to suggest that matrices cannot be encoded as ordered lists in program state). When the raw data of the sensor are directly used by an artificial intelligence (AI) algorithm, these extra steps may be bypassed and raw data may be directly used by the algorithm, wherein raw values and relations between the raw values may be used to perceive the environment and construct the map directly without converting raw values to depth measurements with metric or imperial units prior to inference of the map (which may include inferring or otherwise perceiving a subset of a map, like inferring a shape of a piece of furniture in a room that is otherwise mapped with other techniques). For example, in embodiments, where at least one camera coupled with at least one IR laser is used in perceiving the environment, depth may be inferred based on the position and/or geometry of the projected IR light in the image captured. For instance, some embodiments may infer map geometry (or features thereof) with a trained convolutional neural network configured to infer such geometries from raw data from a plurality of sensor poses. Some embodiments may apply a multi-stage convolutional neural network in which initial stages in a pipeline of models are trained on (and are configured to infer) a coarser-grained spatial map corresponding to raw sensor data of a two-or-three-dimensional scene and then later stages in the pipeline are trained on (and are configured to infer) finer-grained residual difference between the coarser-grained spatial map and the two-or-three-dimensional scene. Some embodiments may include three, five, ten, or more such stages trained on progressively finer-grained residual differences relative to outputs of earlier stages in the model pipeline. In some cases, objects may be detected and mapped with, for instance, a capsule network having pose invariant representations of three dimensional objects. In some cases, complexity of exploiting translational invariance may be reduced by leveraging constraints where the robot is confined to two dimensions of movement, and the output map is a two dimensional map, for instance, the capsules may only account for pose invariance within a plane. A digital image from the camera may be used to detect the position and/or geometry of IR light in the image by identifying pixels with high brightness (or outputs of transformations with high brightness, like outputs of edge detection algorithms). This may be used directly in perceiving the surroundings and constructing a map of the environment. The raw pixel intensity values may be used to determine the area of overlap between data captured within overlapping fields of view in order to combine data and construct a map of the environment. In the case of two overlapping images, the area in which the two images overlap contain similar arrangement of pixel intensities in at least a portion of the digital image. This similar arrangement of pixels may be detected and the two overlapping images may be stitched at overlapping points to create a segment of the map of the environment without processing the raw data into depth measurements.

[0339] As a further example, raw time-of-flight data measured for multiple points within overlapping fields of view may be compared and used to find overlapping points between captured data without translating the raw times into depth measurements, and in some cases, without first triangulating multiple depth measurements from different poses to the same object to map geometry of the object. The area of overlap may be identified by recognizing matching patterns among the raw data from the first and second fields of view, such as a pattern of increasing and decreasing values. Matching patterns may be detected by using similar methods as those discussed herein for detecting matching patterns in depth values perceived from two overlapping fields of views. This technique, combined with the movement readings from the gyroscope or odometer and/or the convolved function of the two sets of raw data may be used to infer a more accurate area of overlap in some embodiments. Overlapping raw data may then be combined in a similar manner as that described above for combing overlapping depth measurements. Accordingly, some embodiments do not require that raw data collected by the sensor be translated into depth measurements or other processed data (which is not to imply that “raw data” may not undergo at least some processing between when values are sensed by a sensor and when the raw data is subject to the above techniques, for instance, charges on charge-coupled image sensors may be serialized, normalized, filtered, and otherwise transformed without taking the result out of the ambit of “raw data”).

[0340] In some embodiments, prior to perceiving depths within a next field of view, an adjustment range may be calculated based on expected noise, such as measurement noise, robot movement noise, and the like. The adjustment range may be applied with respect to depths perceived within a previous field of view and is the range within which overlapping depths from the next field of view are expected to fall within. In another embodiment, a weight may be assigned to each perceived depth. The value of the weight may be determined based on various factors, such as quality of the reading, the perceived depth's position with respect to the adjustment range, the degree of similarity between depths recorded from separate fields of view, the weight of neighboring depths, or the number of neighboring depths with high weight. In some embodiments, depths with weights less than an amount (such as a predetermined or dynamically determined threshold amount) may be ignored as depths, with higher weight considered to be more accurate. In some embodiments, increased weight may be given to overlapping depths with a larger area of overlap, and less weight may be given to overlapping depths with a smaller area of overlap. In some embodiments, the weight assigned to readings may be proportional to the size of the overlap area identified. For example, data points corresponding to a moving object captured in one or two frames overlapping with several other frames captured without the moving object may be assigned a low weight as they likely do not fall within the adjustment range and are not consistent with data points collected in other overlapping frames and would likely be rejected for having low assigned weight.

[0341] In embodiments, structure of data used in inferring depths may have various forms. For instance, several off-the-shelf depth perception devices express measurements as a matrix of angles and depths to the perimeter. Measurements may include, but are not limited to (which is not to suggest that any other description is limiting), various formats indicative of some quantified property, including binary classifications of a value being greater than or less than some threshold, quantized values that bin the quantified property into increments, or real number values indicative of a quantified property. For example, a matrix containing pixel position, color, brightness, and intensity or a finite ordered list containing x, y position and norm of vectors measured from the camera to objects in a two-dimensional plane or a list containing time-of-flight of light signals emitted in a two-dimensional plane between camera and objects in the environment. Some traditional techniques may use that data to create a computationally expensive occupancy map. In contrast, some embodiments implement a less computationally expensive approach for creating a map whereby, in some cases, the output matrix of depth cameras, any digital camera (e.g., a camera without depth sensing), or other depth perceiving devices (e.g., ultrasonic or laser range finders) may be used. In some embodiments, pixel intensity of captured images is not required. In some cases, the resulting map may be converted into an occupancy map.

[0342] For ease of visualization, data from which depth is inferred may be converted and reported in the format of millimeters or inches of depth, however, this is not a requirement, which is not to suggest that other described features are required. For example, pixel intensities from which depth may be inferred may be converted into meters of depth for ease of visualization, or they may be used directly given that the relation between pixel intensity and depth is known. To reduce computational expense, the extra step of converting data from which depth may be inferred into a specific format may be eliminated, which is not to suggest that any other feature here may not also be omitted in some embodiments. The methods of perceiving or otherwise inferring depths and the formats of reporting depths used herein are for illustrative purposes and are not intended to limit the invention, again which is not to suggest that other descriptions are limiting. Depths may be perceived (e.g., measured or otherwise inferred) in any form and be reported in any format. For example, a camera installed on a robot may perceive depths from the camera to objects within a first field of view. Depending on the type of depth perceiving device used, depth data may be perceived in various forms. In one embodiment, the depth perceiving device may measure a vector to the perceived object and calculate the Euclidean norm of each vector, representing the depth from the camera to objects within the first field of view. The L^P norm is used to calculate the Euclidean norm from the vectors, mapping them to a positive scalar that represents the depth from the camera to the observed object. The L^P norm is given by ∥x∥_P=(Σ_i|x_i|^P)^1/P whereby the Euclidean norm uses P=2. In some embodiments, this data structure maps the depth vector to a feature descriptor to improve frame stitching, as described, for example, in U.S. patent application Ser. No. 15/954,410, the entire contents of which are hereby incorporated by reference. In some embodiments, the depth perceiving device may infer depth of an object based on the time required for a light to reflect off of the object and return. In a further example, depth to objects may be inferred using the quality of pixels, such as brightness, intensity, and color, in captured images of the objects, and in some cases, parallax and scaling differences between images captured at different camera poses. It is noted that each step taken in the process of transforming a matrix of pixels, for example, each having a tensor of color, intensity and brightness, into a depth value in millimeters or inches is a loss and computationally expensive compression and further reduces the state space in each step when digitizing each quality. In order to reduce the loss and computational expenses, it is desired and useful to omit intermediary steps if the goal may be accomplished without them. Based on information theory principal, it may be beneficial to increase content for a given number of bits. For example, reporting depth in specific formats, such as metric units, is only necessary for human visualization. In implementation, such steps may be avoided to save computational expense and loss of information. The amount of compression and the amount of information captured and processed is a trade-off, which a person of ordinary skill in the art may balance to get the desired result with the benefit of this disclosure.

[0343] Some embodiments described afford a method and apparatus for combining perceived depths from cameras or any other depth perceiving device(s), such as a depth sensor comprising, for example, an image sensor and IR illuminator, to construct a map. Cameras may include depth cameras, such as but not limited to, stereo depth cameras or structured light depth cameras or a combination thereof. A CCD or CMOS camera positioned at an angle with respect to a horizontal plane combined with an IR illuminator, such as an IR point or line generator, projecting IR dots or lines or any other structured form of light (e.g., an IR gradient, a point matrix, a grid, etc.) onto objects within the environment sought to be mapped and positioned parallel to the horizontal plane may also be used to measure depths. Other configurations are contemplated. For example, the camera may be positioned parallel to a horizontal plane (upon which the robot translates) and the IR illuminator may be positioned at an angle with respect to the horizontal plane or both the camera and IR illuminator are positioned at angle with respect to the horizontal plane. Various configurations may be implemented to achieve the best performance when using a camera and IR illuminator for measuring depths. Examples of cameras which may be used are the OmniPixel3-HS camera series from OmniVision Technologies Inc. or the UCAM-II JPEG camera series by 4D Systems Pty Ltd. Any other depth perceiving device may also be used including but not limited to ultrasound and sonar depth perceiving devices. Off-the-shelf depth measurement devices, such as depth cameras, may be used as well. Different types of lasers may be used, including but not limited to edge emitting lasers and surface emitting lasers. In edge emitting lasers the light emitted is parallel to the wafer surface and propagates from a cleaved edge. With surface emitting lasers, light is emitted perpendicular to the wafer surface. This is advantageous as a large number of surface emitting lasers can be processed on a single wafer and an IR illuminator with a high density structured light pattern in the form of, for example, dots can improve the accuracy of the perceived depth. Several co-pending applications by the same inventors that describe methods for measuring depth may be referred to for illustrative purposes. For example, one method for measuring depth includes a laser light emitter, two image sensors and an image processor whereby the image sensors are positioned such that their fields of view overlap. The displacement of the laser light projected from the image captured by the first image sensor to the image captured by the second image sensor is extracted by the image processor and used to estimate the depth to the object onto which the laser light is projected (see, U.S. patent application Ser. No. 15/243,783). In another method two laser emitters, an image sensor and an image processor are used to measure depth. The laser emitters project light points onto an object which is captured by the image sensor. The image processor extracts the distance between the projected light points and compares the distance to a preconfigured table (or inputs the values into a formula with outputs approximating such a table) that relates distances between light points with depth to the object onto which the light points are projected (see, U.S. patent application Ser. No. 15/257,798). Some embodiments described in U.S. patent application Ser. No. 15/224,442 apply the depth measurement method to any number of light emitters, where for more than two emitters the projected light points are connected by lines and the area within the connected points is used to determine depth to the object. In a further example, a line laser positioned at a downward angle relative to a horizontal plane and coupled with an image sensor and processer are used to measure depth (see, U.S. patent application Ser. No. 15/674,310). The line laser projects a laser line onto objects and the image sensor captures images of the objects onto which the laser line is projected. The image processor determines distance to objects based on the position of the laser line as projected lines appear lower as the distance to the surface on which the laser line is projected increases.

[0344] The angular resolution of perceived depths may be varied in different implementations but generally depends on the camera resolution, the illuminating light, and the processing power for processing the output. For example, if the illuminating light generates distinctive dots very close to one another, the resolution of the device is improved. The algorithm used in generating the vector measurement from the illuminated pixels in the camera may also have an impact on the overall angular resolution of the measurements. In some embodiments, depths may be perceived in one-degree increments. In other embodiments, other incremental degrees may be used depending on the application and how much resolution is needed for the specific task or depending on the robot and the environment it is running in. For robots used within consumer homes, for example, a low-cost, low-resolution camera can generate enough measurement resolution. For different applications, cameras with different resolutions may be used. In some depth cameras, for example, a depth measurement from the camera to an obstacle in the surroundings is provided for each angular resolution in the field of view.

[0345] In some embodiments, the accuracy of the map may be confirmed when the locations at which contact between the robot and perimeter coincides with the locations of corresponding perimeters in the map. When the robot makes contact with a perimeter the processor of the robot checks the map to ensure that a perimeter is marked at the location at which the contact with the perimeter occurred. Where a boundary is predicted by the map but not detected, corresponding data points on the map may be assigned a lower confidence in the Bayesian approach above, and the area may be re-mapped. This method may also be used to establish ground truth of Euclidean norms. In some embodiments, a separate map may be used to keep track of the boundary discovered thereby creating another map. Two maps may be merged using different methods, such as the intersection or union of two maps. For example, in some embodiments, the union of two maps may be applied to create an extended map of the working environment with areas which may have been undiscovered in the first map and/or the second map. In some embodiments, a second map may be created on top of a previously created map in a layered fashion, resulting in additional areas of the work space which may have not been recognized in the original map. Such methods may be used, for example, in cases where areas are separated by movable obstacles that may have prevented the robot from determining the full map of the working environment and in some cases, completing an assigned task. For example, a soft curtain may act as a movable object that appears as a wall in a first map. In this case, a second map may be created on top of the previously created first map in a layered fashion to add areas to the original map which may have not been previously discovered. The processor of the robot may then recognize (e.g., determine) the area behind the curtain that may be important (e.g., warrant adjusting a route based on) in completing an assigned task.

[0346] FIG. 47A illustrates a complete 2D map 600 constructed using depths perceived in 2D within consecutively overlapping fields of view. In another embodiment, 2D map 600 may be constructed using depths perceived in 3D. 2D map 600 may, for example, be used by robot 601 with mounted camera 602 to autonomously navigate throughout the working environment during operation. In FIG. 47B, initial map 600 includes perimeter segment 603 extending from dashed line 604 to dashed line 605 and perimeter segment 606 extending from dashed line 607 to 608, among the other segments combined to form the entire perimeter shown. Based on initial map 600 of the working environment, coverage path 609 covering central areas of the environment may be devised and executed for cleaning. Upon completion of coverage path 609, the robot may cover the perimeters for cleaning while simultaneously verifying the mapped perimeters using at least one depth sensor and/or tactile sensor of the robot, beginning at location 610 in FIG. 47C. As the robot follows along the perimeter, area 611 beyond previously mapped perimeter segment 603 is discovered. This may occur if, for example, a door in the location of perimeter segment 603 was closed during initial mapping of the working environment. Newly discovered area 611 may then be covered by the robot as is shown in FIG. 47C, after which the robot may return to following along the perimeter. As the robot continues to follow along the perimeter, area 612 beyond previously mapped perimeter segment 606 is discovered. This may occur if, for example, a soft curtain in the location of perimeter segment 606 is drawn shut during initial mapping of the working environment. Newly discovered area 612 may then be covered by the robot as is shown in FIG. 47C, after which the robot may return to following along the perimeter until reaching an end point 613. In some embodiments, the newly discovered areas may be stored in a second map separate from the initial map. In some embodiments, the two maps may be overlaid.

[0347] In one embodiment, construction of the map is complete after the robot has made contact with all perimeters and confirmed that the locations at which contact with each perimeter was made coincides with the locations of corresponding perimeters in the map. In some embodiments, a conservative coverage algorithm may be executed to cover the internal areas of the map before the robot checks if the observed perimeters in the map coincide with the true perimeters of the environment. This ensures more area is covered before the robot faces challenging areas such as perimeter points and obstacles.

[0348] In some embodiments, the processor of the robot progressively generates the map as new sensor data is collected. For example, FIG. 48A illustrates robot 4500 at a position A and 360 degrees depth measurements 4501 (dashed lines emanating from robot 4500) taken by a sensor of the robot 4500 of environment 4502. Depth measurements 4501 within area 4503 measure depths to perimeter 4504 (thin black line) of the environment, from which the processor generates a partial map 4505 (thick black line) with known area 4503. Depth measurements 4501 within area 4506 return maximum or unknown distance as the maximum range of the sensor does not reach a perimeter 4504 off of which it may reflect to provide a depth measurement. Therefore, only partial map 4505 including known area 4503 is generated due limited observation of the surroundings. In some embodiments, the map is generated by stitching images together. In some cases, the processor may assume that area 4506, wherein depth measurements 4501 return maximum or unknown distance, is open but cannot be very sure. FIG. 48B illustrates the robot 4500 after moving to position B. Depth measurements 4501 within area 4507 measure depths to perimeter 4504, from which the processor updates partial map 4505 to also include perimeters 4504 within area 4507 and area 4507 itself. Some depth measurements 4501 to perimeter 4504 within area 4503 are also recorded and may be added to partial map 4505 as well. In some cases, the processor stitches the new images captured from positioned B together then stitches the stitched collection of images to partial map 4505. In some cases, a multi-scan approach that stitches together consecutive scans and then triggers a map fill may improve map building rather than considering only single scan metrics before filling the map with or discarding sensor data. As before, depth measurements 4501 within area 4508 and some within previously observed area 4503 return maximum or unknown distance as the range of the sensor is limited and does not reach perimeters 4501 within area 4508. In some cases, information gain is not linear, as illustrated in FIGS. 48A and 48B, wherein the robot first discovers larger area 4503 then smaller area 4507 after traveling from position A to B. FIG. 48C illustrates the robot 4500 at position C. Depth measurements 4501 within area 4508 measure depths to perimeter 4504, from which the processor updates partial map 4505 to also include perimeters 4504 within area 4508 and area 4508 itself. Some depth measurements 4501 to perimeter 4504 within area 4507 are also recorded and may be added to partial map 4505 as well. In some cases, the processor stitches the new images captured from position C together then stitches the stitched collection of images to partial map 4505. This results in a full map of the environment. As before, some depth measurements 4501 within previously observed area 4507 return maximum or unknown distance as the range of the sensor is limited and does not reach some perimeters 4501 within area 4507. In this example, the map of the environment is generated as the robot navigates within the environment. In some cases, real-time integration of sensor data may reduce accumulated error as there may be less impact from errors in estimated movement of the robot.

[0349] In some embodiments, the processor generates a global map and at least one local map. FIG. 49A illustrates an example of a global map of environment 4600 generated by an algorithm in simulation. Grey areas 4601 are mapped areas that are estimated to be empty of obstacles, medium grey areas 4602 are unmapped and unknown areas, and black areas 4603 are obstacles. Grey areas 4601 start out small and progressively get bigger in discrete map building steps. The edge 4604 at which grey areas 4601 and medium grey areas 4602 meet form frontiers of exploration. Coverage box 4604 is the current area being covered by robot 4605 by execution of a boustrophedon pattern 4606 within coverage box 4604. In some cases, the smooth boustrophedon movement of the robot, particularly the smooth trajectory from a current to a next location while rotating 180 degrees by the time it reaches the next location, may improve efficiency as less time is wasted on multiple rotations (e.g., two separate 90 degree rotations to rotate 180 degrees). Perpendicular lines 4607 and 4608 are used during coverage within coverage box 4605. The algorithm uses the two lines 4607 and 4608 to help define the subtask for each of the control actions of the robot 4605. The robot drives parallel to the line 4607 until it hits the perpendicular line 4608, which it uses as a condition to know when its reached the edge of the coverage area or to tell the robot 4605 when to turn back. During the work session, the size and location of coverage box 4604 changes as the algorithm chooses the next area to be covered. The algorithm avoids coverage in unknown spaces (i.e. placement of a coverage box in such areas) until it has been mapped and explored. Additionally, small areas may not be large enough for dedicated coverage and wall follow in these small areas may be enough for their coverage. In some embodiments, the robot alternates between exploration and coverage. In some embodiments, the processor of the robot (i.e., an algorithm or computer code executed by the processor) first builds a global map of a first area (e.g., a bedroom) and covers that first area before moving to a next area to map and cover. In some embodiments, a user may use an application of a communication device paired with the physical robot to view a next zone for coverage or the path of the robot.

[0350] In FIG. 49B, the global map is complete as there are no medium grey areas 4602 remaining. Robot 4609 (shown as a perfect circle) is the ground truth position of the robot while robot 4605 (shown as an ellipse) is the position of the robot estimated by the algorithm. In this example, the algorithm estimates the position of the robot 4605 using wheel odometry, LIDAR sensor, and gyroscope data. The path 4610 (including boustrophedon path 4606 in FIG. 49A) is the ground truth path of the robot recorded by simulation, however, light grey areas 4611 are the areas the algorithm estimated as covered. The robot 4605 first covers low obstacle density areas (light grey areas in FIG. 49B), then performs wall follow, shown by path 4610 in FIG. 49B. At the end of the work session, the robot performs robust coverage, wherein high obstacle density areas (remaining grey areas 4601 in FIG. 49B) are selected for coverage, such as the grey area 4601 in the center of the environment, representing an area under a table. As robust coverage progresses, the robot 4605 tries to reach a new navigation goal each time by following along the darker path 4612 in FIG. 49C to the next navigation goal. In some cases, the robot may not reach its intended navigation goal as the algorithm may time out while attempting to reach the navigation goal. The darker paths 4612 used in navigating from one coverage box to the next and for robust coverage are planned offline, wherein the algorithm plans the navigation path ahead of time before the robot executes the path and the path planned is based on obstacles already known in the global map. While offline navigation may be considered static navigation, the algorithm does react to obstacles it might encounter along the way through a reactive pattern of recovery behaviors.

[0351] FIG. 50 illustrates an example of a LIDAR local map 4700 generated by an algorithm in simulation. The LIDAR local map 4700 follows a robot 4701, with the robot 4701 centered within the LIDAR local map 4700. The LIDAR local map 4700 is overlaid on the global map illustrated in FIGS. 49A-49C. Obstacles 4702, hidden obstacles 4703, and open areas (i.e., free space) 4704 are added into the LIDAR local map based on LIDAR scans. Hidden obstacles 4703 are added whenever there is a sensor event, such as a TSSP sensor event (i.e., proximity sensor), edge sensor event, and bumper event. Hidden obstacles are useful as the LIDAR does not always observed every obstacle. Some areas in LIDAR local map 4700 may not be mapped as the local map is limited size. In some cases, the LIDAR local map 4700 may be used for online navigation (i.e., real-time navigation), wherein a path is planned around obstacles in the LIDAR local map 4700 in real-time. For example, online navigation may be used during any of: navigating to a start point at the end of coverage, robust coverage, normal coverage, all the time, wall follow coverage, etc. In FIG. 50, the path executed by the robot 4701 to return to starting point 4705 after finishing robust coverage is planned using online navigation. During online navigation, the LIDAR local map may be updated based on LIDAR scans collected in real-time. Areas already observed by the LIDAR remain in the local map even when the LIDAR is no longer observing the area in its field of view until the areas are pushed out of the LIDAR local map due to the size of the LIDAR local map. Offset between actual location of obstacles and locations in the LIDAR local map may correspond with the offset between the position of the ground truth robot 4706 and the estimated position of the robot 4701.

[0352] In some embodiments, online navigation uses a real-time local map, such as the LIDAR local map, in conjunction with a global map of the environment for more intelligent path planning. In some cases, the global map may be used to plan a global movement path and while executing the global movement path, the processor may create a real-time local map using fresh LIDAR scans. In some embodiments, the processor may synchronize the local map with obstacle information from the global map to eliminate paths planned through obstacles. In some embodiments, the global and local map may be updated with sensor events, such as bumper events, TSSP sensor events, safety events, TOF sensor events, edge events, etc. For example, marking an edge event may prevent the robot from repeatedly visit the same edge after a first encounter. In some embodiments, the processor may check whether a next navigation goal (e.g., a path to a particular point) is safe using the local map. A next navigation goal may be considered safe if it is within the local map and at a safe distance from local obstacles, is in an area outside of the local map, or is in an area labelled as unknown. In some embodiments, wherein the next navigation goal is unsafe, the processor may perform a wave search from the current location of the robot to find a safe navigation goal that is inside of the local map and may plan a path to the new navigation goal.

[0353] FIG. 51 illustrates an example of a local TOF map 4800 that is generated in simulation using data collected by TOF sensors located on robot 4801. The TOF local map is overlaid on the global map illustrated in FIGS. 49A-49C. The TOF sensors may be used to determine short range distances to obstacles. While the robot 4801 is near obstacles (e.g. the wall) the obstacles appear in the local TOF map 4800 as small black dots 4802. The white areas 4803 in the local TOF map 4800 are inferred free space within the local TOF map 4800. Given the position of TOF sensors on the robot 4801 and depending on which side of the robot a TOF sensor is triggered, a white line between the center of robot 4801 and the center of the obstacle that triggered the TOF is inferred free space. The white line is also the estimated TOF sensor distance from the center of robot 4801 to the obstacle. White areas 4803 come and go as obstacles move in and out of the fields of view of TOF sensors. In some embodiments, the local TOF map is used for wall following.

[0354] In some embodiments, the map may be a state space with possible values for x, y, z. In some embodiments, a value of x and y may be a point on a Cartesian plane on which the robot drives and the value of z may be a height of obstacles or depth of cliffs. In some embodiments, the map may include additional dimensions (e.g., debris accumulation, floor type, obstacles, cliffs, stalls, etc.). For example, FIG. 52 illustrates an example of a map that represents a driving surface with vertical undulations (e.g., indicated by measurements in x-, y-, and z-directions). In some embodiments, a map filler may assign values to each cell in a map (e.g., Cartesian). In some embodiments, the value associated with each cell may be used to determine a location of the cell in a planar surface along with a height from a ground zero plane. In some embodiments, a plane of reference (e.g., x-y plane) may be positioned such that it includes a lowest point in the map. In this way, all vertical measurements (e.g., z values measured in a z-direction normal to the plane of reference) are always positive. In some embodiments, the processor of the robot may adjust the plane of reference each time a new lower point is discovered and all vertical measurements accordingly. In some embodiments, the plane of reference may be positioned at a height of the work surface at a location where the robot begins to perform work and data may be assigned a positive value when an area with an increased height relative to the plane of reference is discovered (e.g., an inclination or bump) and assigned a negative value when an area with a decreased height relative to the plane of reference is observed. In some embodiments, a map may include any number of dimensions. For example, a map may include dimensions that provide information indicating areas that were previously observed to have a high level of debris accumulation or areas that were previously difficult to traverse or areas that were previously identified by a user (e.g., using an application of a communication device), such as areas previously marked by a user as requiring a high frequency of cleaning. In some embodiments, the processor may identify a frontier (e.g., corner) and may include the frontier in the map.

[0355] In embodiments, the map of the robot may include multiple dimensions. In some embodiments, a dimension of the map may include a type of flooring (e.g., cement, wood, carpet, etc.). The type of flooring is important as it may be used by the processor to determine actions, such as when to start or stop applying water or detergent to a surface, scrubbing, vacuuming, mopping, etc. In some embodiments, the type of flooring may be determined based on data collected by various different sensors. For example, a camera of the robot may capture an image and the processor perform a planar work surface extraction from the image, representing the floor of the environment. In some cases, the planar work surface may be divided into rooms and hallways based on arrangement of areas within the environment, visual features, or divisions chosen by a user. In some cases, the extraction may provide information about the type of flooring. In some embodiments, the processor may use image-based segmentation methods to separate objects from one another. For example, FIGS. 53A, 53B, 54A, and 54B illustrate the use of image-based segmentation for extraction of floors 4900 and 5000, respectively, from the rest of an environment. FIGS. 53A and 54A illustrate two different environments captured in an image. FIGS. 53B and 54B illustrate extractions of floors 4900 and 5000, respectively, from the rest of the environment. In some cases, the processor may detect a type of flooring (e.g., tile, marble, wood, carpet, etc.) based on patterns and other visual clues processed by the camera. For example, FIGS. 55A, 55B, 56A, and 56B illustrate examples of a grid pattern 5101 and 5201, respectively, used in helping to detect the floor type or characteristics of the corresponding floor 5100 and 5200. While the floor extraction alone may provide a guess about the type of flooring, the processor may also consider other sensing information such as data collected by floor-facing optical tracking sensors or floor distance sensors, IR sensors, electrical current sensors, etc.

[0356] In some embodiments, depths may be measured to all objects within the environment. In some embodiments, depths may be measured to particular landmarks (e.g., some identified objects) or a portion of the objects within the environment (e.g., a subset of walls). In some embodiments, the processor may generate a map based on depths to a portion of objects within the environment. FIG. 57A illustrates an example of a robot 1900 with a sensor collecting data that is indicative of depth to a subset of points 1901 along the walls 1902 of the environment. FIG. 57B illustrates an example of a spatial model 1903 generated based on the depths to the subset of points 1901 of the environment shown in FIG. 57A, assuming the points are connected by lines. As robot 1900 moves from a first position at time t₀ to a second position at time t₁₀ within the environment and collects more data, the spatial model 1903 may be updated to more accurately represent the environment, as illustrated in FIG. 57C.

[0357] In some embodiments, the sensor of the robot 1900 continues to collect data to the subset of points 1901 along the walls 1902 as the robot 1900 moves within the environment. For example, FIG. 58A illustrates the sensor of the robot 1900 collecting data to the same subset of points 1901 at three different times 2000, 2001, and 2002 as the robot moves within the environment. In some cases, depending on the position of the robot, two particularities may appear as a single feature (or characteristic). For example, FIG. 58B illustrates the robot 1900 at a position s₁ collecting data indicative of depths to points A and B. From position s₁ points A and B appear to be the same feature. As the robot 1900 travels to a position s₂ and observes the edge on which points A and B lie from a different angle, the processor of the robot 1900 may differentiate points A and B as separate features. In some embodiments, the processor of the robot gains clarity on features as it navigates within the environment and observes the features from different positions and may be able to determine if a single feature is actually two features combined.

[0358] In some embodiments, the path of the robot may overlap while mapping. For example, FIG. 59 illustrates a robot 2100, a path of the robot 2101, an environment 2102, and an initial area mapped 2103 while performing work. In some embodiments, the path of the robot may overlap resulting in duplicate coverage of areas of the environment. For instance, the path 2101 illustrated in FIG. 59 includes overlapping segment 2104. In some cases, the processor of the robot may discard some overlapping data from the map (or planar work surface). In some embodiments, the processor of the robot may determine overlap in the path based on images captured with a camera of the robot as the robot moves within the environment.

[0359] In some embodiments, the robot is in a position where observation of the environment by sensors is limited. This may occur when, for example, the robot is positioned at one end of an environment and the environment is very large. In such a case, the processor of the robot constructs a temporary partial map of its surroundings as it moves towards the center of the environment where its sensors are capable of observing the environment. This is illustrated in FIG. 60A, where robot 2601 is positioned at a corner of large room 3100, approximately 20 centimeters from each wall. Observation of the environment by sensors is limited due to the size of room 3100 wherein field of view 3101 of the sensor does not capture any features of environment 3100. A large room, such as room 3100, may be 8 meters long and 6 meters wide for example. The processor of robot 2601 creates a temporary partial map using sensor data as it moves towards center 3102 of room 3100 in direction 3103. In FIG. 60B robot 2601 is shown at the center of room 3100 where sensors are able to observe features of environment 3100.

[0360] In some embodiments, the processor may extract lines that may be used to construct the environment of the robot. In some cases, there may be uncertainty associated with each reading of a noisy sensor measurement and there may be no single line that passes through the measurement. In such cases, the processor may select the best possible match, given some optimization criterion. In some cases, sensor measurements may be provided in polar coordinates, wherein x_i=(ρ_i, θ_i). The processor may model uncertainty associated with each measurement with two random variables, X_i=(P_i, Q₁). To satisfy the Markovian requirement, the uncertainty with respect to the actual value of P and Q must be independent, wherein E[P_i·P_j]=E[P_i]E[P_j], E[Q_i·Q_j]=E[Q_i]E[Q_j], and E[P_i·Q_j]=E[P_i]E[Q_j], ∀i,j=1, . . . , n. In some embodiments, each random variable may be subject to a Gaussian probability, wherein P_i˜N(ρ_i,(σ²)_ρi) and Q_i˜N(θ_i, (ρ²)_θi). In some embodiments, the processor may determine corresponding Euclidean coordinates x=ρ cos θ and y=ρ sin θ of a polar coordinate. In some embodiments, the processor may determine a line on which all measurements lie, i.e., ρ cos θ cos α+ρ sin θ sin α−r=ρ cos(θ−α)−r=0. However, obtaining a value of zero represents an ideal situation wherein there is no error. In actuality, this is a measure of the error between a measurement point (ρ, θ) and the line, specifically in terms of the minimum orthogonal distance between the point and the line. In some embodiments, the processor may minimize the error. In some embodiments, the processor may minimize the sum of square of all the errors using S=Σ_id_i²=Σ_i(ρ_i cos(θ_i−α)−r)², wherein

[0361] $\frac{\partial S}{\partial \alpha }=0$
and

[0362] $\frac{\partial S}{\partial r}=0.$
In some instances, measurements may not have the same errors. In some embodiments, a measurement point of the spatial representation of the environment may represent a mean of the measurement and a circle around the point may indicate the variance of the measurement. The size of circle may be different for different measurements and may be indicative of the amount of influence that each point may have in determining where the perimeter line fits. For example, in FIG. 61A, three measurements A, B, and C are shown, each with a circle 2200 indicating variance of the respective measurement. The perimeter line 2201 is closer to measurement B as it has a higher confidence and less variance. In some instances, the perimeter line may not be a straight line depending on the measurements and their variance. While this method of determining a position of a perimeter line may result in a perimeter line 2201 shown in FIG. 61B, the perimeter line of the environment may actually look like the perimeter line 2202 or 2203 illustrated in FIG. 61C or FIG. 61D. In some embodiments, the processor may search for particular patterns in the measurement points. For example, it may be desirable to find patterns that depict any of the combinations in FIG. 62.

[0363] In some embodiments, the processor (or a SLAM algorithm executed by the processor) may obtain scan data collected by sensors of the robot during rotation of the robot. In some embodiments, a subset of the data may be chosen for building the map. For example, 49 scans of data may be obtained for map building and four of those may be identified as scans of data that are suitable for matching and building the map. In some embodiments, the processor may determine a matching pose of data and apply a correction accordingly. For example, a matching pose may be determined to be (−0.994693, −0.105234, −2.75821) and may be corrected to (−1.01251, −0.0702046, −2.73414) which represents a heading error of 1.3792 degrees and a total correction of (−0.0178176, 0.0350292, 0.0240715) having traveled (0.0110555, 0.0113022, 6.52475). In some embodiments, a multi map scan matcher may be used to match data. In some embodiments, the multi map scan matcher may fail if a matching threshold is not met. In some embodiments, a Chi-squared test may be used.

[0364] Some embodiments may afford the processor of the robot constructing a map of the environment using data from one or more cameras while the robot performs work within recognized areas of the environment. The working environment may include, but is not limited to (a phrase which is not here or anywhere else in this document to be read as implying other lists are limiting), furniture, obstacles, static objects, moving objects, walls, ceilings, fixtures, perimeters, items, components of any of the above, and/or other articles. The environment may be closed on all sides or have one or more openings, open sides, and/or open sections and may be of any shape. In some embodiments, the robot may include an on-board camera, such as one with zero-degrees of freedom of actuated movement relative to the robot (which may itself have three degrees of freedom relative to an environment), or some embodiments may have more or fewer degrees of freedom; e.g., in some cases, the camera may scan back and forth relative to the robot.

[0365] In some embodiments, a camera, installed on the robot, for example, measures the depth from the camera to objects within a first field of view. In some embodiments, a processor of the robot constructs a first segment of the map from the depth measurements taken within the first field of view. The processor may establish a first recognized area within the working environment, bound by the first segment of the map and the outer limits of the first field of view. In some embodiments, the robot begins to perform work within the first recognized area. As the robot with attached camera rotates and translates within the first recognized area, the camera continuously takes depth measurements to objects within the field of view of the camera. In some embodiments, the processor combines new depth measurements with previous depth measurements, increasing the size of the recognized area within which the robot may operate while continuing to collect depth data and build the map. Assuming the frame rate of the camera is fast enough to capture more than one frame of data in the time it takes the robot to rotate the width of the frame, a portion of data captured within each field of view overlaps with a portion of data captured within the preceding field of view. As the robot moves to observe a new field of view, in some embodiments, the processor adjusts measurements from previous fields of view to account for movement of the robot. The processor, in some embodiments, uses data from devices such as an odometer, gyroscope and/or optical encoder to determine movement of the robot with attached camera.

[0366] For example, FIG. 62A illustrates camera 2600 mounted on robot 2601 measuring depths 2602 at predetermined increments within a first field of view 2603 of working environment 2604. Depth measurements 2602 taken by camera 2600 measure the depth from camera 2600 to object 2605, which in this case is a wall. FIG. 62B illustrates a processor of the robot constructing 2D map segment 2606 from depth measurements 2602 taken within first field of view 2603. Dashed lines 2607 demonstrate that resulting 2D map segment 2606 corresponds to depth measurements 2602 taken within field of view 2603. The processor establishes first recognized area 2608 of working environment 2604 bounded by map segment 2606 and outer limits 2609 of first field of view 2603. Robot 2601 begins to perform work within first recognized area 2608 while camera 2600 continuously takes depth measurements.

[0367] FIG. 64A illustrates robot 2601 translating forward in direction 2700 to move within recognized area 2608 of working environment 2604 while camera 2600 continuously takes depth measurements within the field of view of camera 2600. Since robot 2601 translates forward without rotating, no new areas of working environment 2604 are captured by camera 2600, however, the processor combines depth measurements 2701 taken within field of view 2702 with overlapping depth measurements previously taken within area 2608 to further improve accuracy of the map. As robot 2601 begins to perform work within recognized area 2608 it positions to move in vertical direction 2703 by first rotating in direction 2704. FIG. 64B illustrates robot 2601 rotating in direction 2704 while camera 2600 takes depth measurements 2701, 2705 and 2706 within fields of view 2707, 2708, and 2709, respectively. The processor combines depth measurements taken within these fields of view with one another and with previously taken depth measurements 2602 (FIG. 64A), using overlapping depth measurements as attachment points. The increment between fields of view 2707, 2708, and 2709 is trivial and for illustrative purposes. In FIG. 64C the processor constructs larger map segment 2710 from depth measurements 2602, 2701, 2705 and 2706 taken within fields of view 2603, 2707, 2708 and 209, respectively, combining them by using overlapping depth measurements as attachment points. Dashed lines 2711 demonstrate that resulting 2D map segment 2710 corresponds to combined depth measurements 2602, 2701, 2705, and 2706. Map segment 2710 has expanded from first map segment 2606 (FIG. 64B) as plotted depth measurements from multiple fields of view have been combined to construct larger map segment 2710. The processor also establishes larger recognized area 2712 of working environment 2604 (compared to first recognized area 2608 (FIG. 64B)) bound by map segment 2710 and outer limits of fields of view 2603 and 2710 represented by dashed line 2713.

[0368] FIG. 65A illustrates robot 2601 continuing to rotate in direction 2704 before beginning to move vertically in direction 2703 within expanded recognized area 2712 of working environment 2604. Camera 2600 measures depths 2800 from camera 2600 to object 2605 within field of view 2801 overlapping with preceding depth measurements 2706 taken within field of view 2709 (FIG. 65B). Since the processor of robot 2601 is capable of tracking its position (using devices such as an odometer or gyroscope) the processor can estimate the approximate overlap with previously taken depth measurements 2706 within field of view 2709. Depth measurements 2802 represent the overlap between previously taken depth measurements 2706 and depth measurements 2800. FIG. 65B illustrates 2D map segment 2710 resulting from previously combined depth measurements 2602, 2701, 2705 and 2706 and map segment 2803 resulting from depth measurements 2800. Dashed lines 2711 and 2804 demonstrate that resulting 2D map segments 2710 and 2803 correspond to previously combined depth measurements 2602, 2701, 2705, 2706 and to depth measurements 2800, respectively. The processor constructs 2D map segment 2805 from the combination of 2D map segments 2710 and 2803 bounded by the outermost dashed lines of 2711 and 2804. The camera takes depth measurements 2800 within overlapping field of view 2801. The processor compares depth measurements 2800 to previously taken depth measurements 2706 to identify overlapping depth measurements bounded by the innermost dashed lines of 2711 and 2804. The processor uses one or more of the methods for comparing depth measurements and identifying an area of overlap described above. The processor estimates new depth measurements for the overlapping depth measurements using one or more of the combination methods described above. To construct larger map segment 2805, the processor combines previously constructed 2D map segment 2710 and 2D map segment 2803 by using overlapping depth measurements, bound by innermost dashed lines of 2711 and 2804, as attachment points. The processor also expands recognized area 2712 within which robot 2601 operates to recognized area 2808 of working environment 2604 bounded by map segment 2805 and dashed line 2809.

[0369] FIG. 66A illustrates robot 2601 rotating in direction 2900 as it continues to perform work within working environment 2604. The processor expanded recognized area 308 to area 2901 bound by wall 2605 and dashed line 2902. Camera 2600 takes depth measurements 2903 from camera 2600 to object 2605 within field of view 2904 overlapping with preceding depth measurements 2905 taken within field of view 2906. Depth measurements 2907 represent overlap between previously taken depth measurements 2905 and depth measurements 2903. FIG. 66B illustrates expanded map segment 2908 and expanded recognized area 2909 resulting from the processor combining depth measurements 2903 and 2905 at overlapping depth measurements 2907. This method is repeated as camera 2600 takes depth measurements within consecutively overlapping fields of view as robot 2601 moves within the environment and the processor combines the depth measurements at overlapping points until a 2D map of the environment is constructed. FIG. 67 illustrates an example of a complete 2D map 3000 with bound area 3001. The processor of robot 2601 constructs map 3000 by combining depth measurements taken within consecutively overlapping fields of view of camera 2600. 2D map 3000 can, for example, be used by the processor of robot 2601 to autonomously navigate the robot 2601 throughout the working environment during operation.

[0370] In some embodiments, the processor may identify overlap using raw pixel intensity values. FIGS. 68A and 68B illustrate an example of identifying an area of overlap using raw pixel intensity data and the combination of data at overlapping points. In FIG. 68A, the overlapping area between overlapping image 2400 captured in a first field of view and image 2401 captured in a second field of view may be determined by comparing pixel intensity values of each captured image (or transformation thereof, such as the output of a pipeline that includes normalizing pixel intensities, applying Gaussian blur to reduce the effect of noise, detecting edges in the blurred output (such as Canny or Haar edge detection), and thresholding the output of edge detection algorithms to produce a bitmap like that shown) and identifying matching patterns in the pixel intensity values of the two images, for instance by executing operations by which some embodiments determine an overlap with a convolution. Lines 2402 represent pixels with high pixel intensity value (such as those above a certain threshold) in each image. Area 2403 of image 2400 and area 2404 of image 2401 capture the same area of the environment and, as such, the same pattern for pixel intensity values is sensed in area 2403 of image 2400 and area 2404 of image 2401. After identifying matching patterns in pixel intensity values in image 2400 and 2401, a matching overlapping area between both images may be determined. In FIG. 68B, the images are combined at overlapping area 2405 to form a larger image 2406 of the environment. In some cases, data corresponding to the images may be combined. For instance, depth values may be aligned based on alignment determined with the image. FIG. 68C illustrates a flowchart describing the process illustrated in FIGS. 68A and 68B wherein a process of the robot at first stage 907 compares pixel intensities of two images captured by a sensor of the robot, at second stage 908 identifies matching patterns in pixel intensities of the two images, at third stage 909 identifies overlapping pixel intensities of the two images, and at fourth stage 910 combines the two images at overlapping points.

[0371] FIGS. 69A-69C illustrate another example of identifying an area of overlap using raw pixel intensity data and the combination of data at overlapping points. FIG. 69A illustrates a top (plan) view of an object, such as a wall, with uneven surfaces wherein, for example, surface 2500 is further away from an observer than surface 2501 or surface 2502 is further away from an observer than surface 2503. In some embodiments, at least one infrared line laser positioned at a downward angle relative to a horizontal plane coupled with at least one camera may be used to determine the depth of multiple points across the uneven surfaces from captured images of the line laser projected onto the uneven surfaces of the object. Since the line laser is positioned at a downward angle, the position of the line laser in the captured image will appear higher for closer surfaces and will appear lower for further surfaces. Similar approaches may be applied with lasers offset from a camera in the horizontal plane. The position of the laser line (or feature of a structured light pattern) in the image may be detected by finding pixels with intensity above a threshold. The position of the line laser in the captured image may be related to a distance from the surface upon which the line laser is projected. In FIG. 69B, captured images 2504 and 2505 of the laser line projected onto the object surface for two different fields of view are shown. Projected laser lines with lower position, such as laser lines 2506 and 2507 in images 2504 and 2505 respectively, correspond to object surfaces 2500 and 2502, respectively, further away from the infrared illuminator and camera. Projected laser lines with higher position, such as laser lines 2508 and 2509 in images 2504 and 2505 respectively, correspond to object surfaces 2501 and 2503, respectively, closer to the infrared illuminator and camera. Captured images 2504 and 2505 from two different fields of view may be combined into a larger image of the environment by finding an overlapping area between the two images and stitching them together at overlapping points. The overlapping area may be found by identifying similar arrangement of pixel intensities in both images, wherein pixels with high intensity may be the laser line. For example, areas of images 2504 and 2505 bound within dashed lines 2510 have similar arrangement of pixel intensities as both images captured a same portion of the object within their field of view. Therefore, images 2504 and 2505 may be combined at overlapping points to construct larger image 2511 of the environment shown in FIG. 69C. The position of the laser lines in image 2511, indicated by pixels with intensity value above a threshold intensity, may also be used to infer depth of surfaces of objects from the infrared illuminator and camera (see, U.S. patent application Ser. No. 15/674,310, the entire contents of which is hereby incorporated by reference).

[0372] In some embodiments, the processor uses measured movement of the robot with attached camera to find the overlap between depth measurements taken within the first field of view and the second field of view. In other embodiments, the measured movement is used to verify the identified overlap between depth measurements taken within overlapping fields of view. In some embodiments, the area of overlap identified is verified if the identified overlap is within a threshold angular distance of the overlap identified using at least one of the method described above. In some embodiments, the processor uses the measured movement to choose a starting point for the comparison between measurements from the first field of view and measurements from the second field of view. For example, the processor uses the measured movement to choose a starting point for the comparison between measurements from the first field of view and measurements from the second field of view. The processor iterates using a method such as that described above to determine the area of overlap. The processor verifies the area of overlap if it is within a threshold angular distance of the overlap estimated using measured movement.

[0373] In some cases, a confidence score is calculated for overlap determinations, e.g., based on an amount of overlap and aggregate amount of disagreement between depth vectors in the area of overlap in the different fields of view, and the above Bayesian techniques down-weight updates to priors based on decreases in the amount of confidence. In some embodiments, the size of the area of overlap is used to determine the angular movement and is used to adjust odometer information to overcome inherent noise of the odometer (e.g., by calculating an average movement vector for the robot based on both a vector from the odometer and a movement vector inferred from the fields of view). The angular movement of the robot from one field of view to the next may, for example, be determined based on the angular increment between vector measurements taken within a field of view, parallax changes between fields of view of matching objects or features thereof in areas of overlap, and the number of corresponding depths overlapping between the two fields of view.

[0374] In some embodiments, the processor expands the number of overlapping depth measurements to include a predetermined (or dynamically determined) number of depth measurements recorded immediately before and after (or spatially adjacent) the identified overlapping depth measurements. Once an area of overlap is identified (e.g., as a bounding box of pixel positions or threshold angle of a vertical plane at which overlap starts in each field of view), the processor constructs a larger field of view by combining the two fields of view using the overlapping depth measurements as attachment points. Combining may include transforming vectors with different origins into a shared coordinate system with a shared origin, e.g., based on an amount of translation or rotation of a depth sensing device between frames, for instance, by adding a translation or rotation vector to depth vectors. The transformation may be performed before, during, or after combining. The method of using the camera to perceive depths within consecutively overlapping fields of view and the processor to identify and combine overlapping depth measurements is repeated, e.g., until all areas of the environment are discovered and a map is constructed.

[0375] In some embodiments, more than one sensor providing various perceptions may be used to improve understanding of the environment and accuracy of the map. For example, a plurality of depth measuring devices (e.g., camera, TOF sensor, TSSP sensor, etc. carried by the robot) may be used simultaneously (or concurrently) where depth measurements from each device are used to more accurately map the environment. For example, FIGS. 70A-70C illustrate an autonomous vehicle with various sensors having different fields of view that are collectively used by its processor to improve understanding of the environment. FIG. 70A illustrates a side view of the autonomous vehicle with field of view 5300 of a first sensor and 5301 of a second sensor. The first sensor may be a camera used for localization as it has a large FOV and can observe many things within the surroundings that may be used by the processor to localize the robot against. The second sensor may be an obstacle sensor used for obstacle detection, including dynamic obstacles. The second sensor may also be used for mapping in front of the autonomous vehicle and observing the perimeter of the environment. Various other sensors may also be used, such as sonar, LIDAR, LADAR, depth camera, camera, optical sensor, TOF sensor, TSSP sensor, etc. In some cases, fields of view 5300 and 5301 may overlap vertically and/or horizontally. In some cases, the data collected by the first and second sensor may be complimentary to one another. In some cases, the fields of view 5300 and 5301 may collectively define a vertical field of view of the autonomous vehicle. There may be multiple second sensors 5301 arranged around a front half of the vehicle, as illustrated in the top view in FIG. 70A. FIG. 70B illustrates a top view of another example of an autonomous vehicle including a first set of sensors (e.g., cameras, LIDAR, etc.) with fields of view 5302 and second set of sensors (e.g., TOF, TSSP, etc.) with fields of view 5303. In some cases, the fields of view 5302 and 5303 may collectively define a vertical and/or horizontal fields of view of the autonomous vehicle. In some cases, overlap between fields of view may occur over the body of the autonomous vehicle. In some embodiments, overlap between fields of view may occur at a further distance than the physical body of the autonomous vehicle. In some embodiments, overlap between fields of view of sensors may occur at different distances. FIG. 70C illustrates the fields of view 5304 and 5305 of sensors at a front and back of an autonomous vehicle overlapping at closer distances (with respect to the autonomous vehicle) than the fields of view 5306 and 5307 of sensors at the sides of the autonomous vehicle. In cases wherein overlap of fields of view of sensors are at far distances, there may be overlap of data from the two sensors that is not in an image captured within the field of view of one of the sensors. The use of a plurality of depth measuring devices is expected to allow for the collection of depth measurements from different perspectives and angles, for example. Where more than one depth measuring device is used, triangulation or others suitable methods may be used for further data refinement and accuracy. In some embodiments, a 360-degree LIDAR is used to create a map of the environment. It should be emphasized, though, that embodiments are not limited to techniques that construct a map in this way, as the present techniques may also be used for plane finding in augmented reality, barrier detection in virtual reality applications, outdoor mapping with autonomous drones, and other similar applications, which is not to suggest that any other description is limiting.

[0376] In some embodiments, the processor (or set thereof) on the robot, a remote computing system in a data center, or both in coordination, may translate depth measurements from on-board sensors of the robot from the robot's (or the sensor's, if different) frame of reference, which may move relative to a room, to the room's frame of reference, which may be static. In some embodiments, vectors may be translated between the frames of reference with a Lorentz transformation or a Galilean transformation. In some cases, the translation may be expedited by engaging a basic linear algebra subsystem (BLAS) of a processor of the robot. In some instances where linear algebra is used, Basic Linear Algebra Subprograms (BLAS) are implemented to carry out operations such as vector addition, vector norms, scalar multiplication, matrix multiplication, matric transpose, matrix-vector multiplication, linear combinations, dot products, cross products, and the like.

[0377] In some embodiments, the robot's frame of reference may move with one, two, three, or more degrees of freedom relative to that of the room, e.g., some frames of reference for some types of sensors may both translate horizontally in two orthogonal directions as the robot moves across a floor and rotate about an axis normal to the floor as the robot turns. The “room's frame of reference” may be static with respect to the room, or as designation and similar designations are used herein, may be moving, as long as the room's frame of reference serves as a shared destination frame of reference to which depth vectors from the robot's frame of reference are translated from various locations and orientations (collectively, positions) of the robot. Depth vectors may be expressed in various formats for each frame of reference, such as with the various coordinate systems described above. (A data structure need not be labeled as a vector in program code to constitute a vector, as long as the data structure encodes the information that constitutes a vector.) In some cases, scalars of vectors may be quantized, e.g., in a grid, in some representations. Some embodiments may translate vectors from non-quantized or relatively granularly quantized representations into quantized or coarser quantizations, e.g., from a sensor's depth measurement to 16 significant digits to a cell in a bitmap that corresponds to 8 significant digits in a unit of distance. In some embodiments, a collection of depth vectors may correspond to a single location or pose of the robot in the room, e.g., a depth image, or in some cases, each depth vector may potentially correspond to a different pose of the robot relative to the room.

[0378] In embodiments, the constructed map may be encoded in various forms. For instance, some embodiments may construct a point cloud of two dimensional or three dimensional points by transforming each of the vectors into a vector space with a shared origin, e.g., based on the above-described displacement vectors, in some cases with displacement vectors refined based on measured depths. Or some embodiments may represent maps with a set of polygons that model detected surfaces, e.g., by calculating a convex hull over measured vectors within a threshold area, like a tiling polygon. Polygons are expected to afford faster interrogation of maps during navigation and consume less memory than point clouds at the expense of greater computational load when mapping. Vectors need not be labeled as “vectors” in program code to constitute vectors, which is not to suggest that other mathematical constructs are so limited. In some embodiments, vectors may be encoded as tuples of scalars, as entries in a relational database, as attributes of an object, etc. Similarly, it should be emphasized that images need not be displayed or explicitly labeled as such to constitute images. Moreover, sensors may undergo some movement while capturing a given image, and the pose of a sensor corresponding to a depth image may, in some cases, be a range of poses over which the depth image is captured.

[0379] In some embodiments, maps may be three dimensional maps, e.g., indicating the position of walls, furniture, doors, and the like in a room being mapped. For example, FIG. 71A illustrates 3D depths 700 and 701 taken within consecutively overlapping fields of view 702 and 703 bound by lines 704 and 705, respectively, using 3D depth perceiving device 706 mounted on robot 707. FIG. 71B illustrates 3D floor plan segment 708 approximated from the combination of plotted depths 700 and 701 at area of overlap 709 bound by innermost dashed lines 704 and 705. This method is repeated where overlapping depths taken within consecutively overlapping fields of view are combined at the area of overlap to construct a 3D floor plan of the environment. In some embodiments, maps may be two dimensional maps, e.g., point clouds or polygons or finite ordered list indicating obstructions at a given height (or range of height, for instance from zero to 5 or 10 centimeters or less) above the floor. Two dimensional maps may be generated from two dimensional data or from three dimensional data where data at a given height above the floor is used and data pertaining to higher features are discarded. Maps may be encoded in vector graphic formats, bitmap formats, or other formats. In some embodiments, maps may include two or more floors of the environment.

[0380] The robot may, for example, use the map to autonomously navigate the environment during operation, e.g., accessing the map to determine that a candidate route is blocked by an obstacle denoted in the map, to select a route with a route-finding algorithm from a current point to a target point, or the like. In some embodiments, the map is stored in memory for future use. Storage of the map may be in temporary memory such that a stored map is only available during an operational session or in more permanent forms of memory such that the map is available at the next session or startup. In some embodiments, the map is further processed to identify rooms and other segments. In some embodiments, the processor of the robot detects a current room or floor within the map of the environment based on visual features recognized in sensor data. In some embodiments, the processor uses a map including the current room or floor to autonomously navigate the environment. In some embodiments, a new map is constructed at each use, or an extant map is updated based on newly acquired data.

[0381] Some embodiments may reference previous maps during subsequent mapping operations. For example, embodiments may apply Bayesian techniques to simultaneous localization and mapping and update priors in existing maps based on mapping measurements taken in subsequent sessions. Some embodiments may reference previous maps and classifying objects in a field of view as being moveable objects upon detecting a difference of greater than a threshold size.

[0382] Feature and location maps as described herein are understood to be the same. For example, in some embodiments a feature-based map includes multiple location maps, each location map corresponding with a feature and having a rigid coordinate system with origin at the feature. Two vectors X and X′, correspond to rigid coordinate systems S and S′ respectively, each describe a different feature in a map. The correspondences of each feature may be denoted by C and C′, respectively. Correspondences may include, angle and distance, among other characteristics. If vector X is stationary or uniformly moving relative to vector X′, the processor of the robot may assume that a linear function U(X′) exists that may transform vector X′ to vector X and vice versa, such that a linear function relating vectors measured in any two rigid coordinate systems exists.

[0383] In some embodiments, the processor determines transformation between the two vectors measured. In some embodiments, the processor uses Galilean Group Transformation to determine the transformations between the two vectors, each measured relative to a different coordinate system. Galilean transformation may be used to transform between coordinates of two coordinate systems that only differ by constant relative motion. These transformations combined with spatial rotations and translations in space and time form the inhomogeneous Galilean Group, for which the equations are only valid at speeds much less than the speed of light. In some embodiments, the processor uses the Galilean Group for transformation between two vectors X and X′, measured relative to coordinate systems S and S′, respectively, the coordinate systems with spatial origins coinciding at t=t′=0 and in uniform relative motion in their common directions.

[0384] In some embodiments, the processor determines the transformation X′=RX+a+vt between vector X′ measured relative to coordinate system S′ and vector X measured relative to coordinate system S to transform between coordinate systems, wherein R is a rotation matrix acting on vector X, X is a vector measured relative to coordinate system S, X′ is a vector measured relative to coordinate system S′, a is a vector describing displacement of coordinate system S′ relative to coordinate system S, v is a vector describing uniform velocity of coordinate system S′ and t is the time. After displacement, the time becomes t′=t+s where s is the time over which the displacement occurred. If T₁=T₁(R₁; a₁; v₁; s₁) and T₂=T₂(R₁; a₁; v₁; s₁) denote a first and second transformation, the processor of the robot may apply the first transformation to vector X at time t resulting in T₁{X, t}={X′, t′} and apply the second transformation to resulting vector X′ at time t′ giving T₂{X′, t′}={X″, t″}. Assuming T₃=T₂T₁, wherein the transformations are applied in reverse order, is the only other transformation that yields the same result of {X″, t″}, then the processor may denote the transformations as T₃{X, t}={X″, t″}. The transformation may be determined using X″=R₂ (R₁X+a₁+v₁t)+a₂+v₂(t+s₁) and t″=t+s₁+s₂, wherein (R₁X+a₁+v₁t) represents the first transformation T₁{X, t}={X′, t′}. Further, R₃=R₂R₁, a₃=a₂+R₂a₁+R₂s₁, v₃=v₂+R₂v₁, and s₃=s₂+s₁ hold true.

[0385] In some embodiments, the Galilean Group transformation is three dimensional and there are ten parameters used in relating vectors X and X′. There are three rotation angles, three space displacements, three velocity components and one time component, with the three rotation matrices

[0386] $R_1\left(\theta \right)=\left[\begin{array}{ccc}1& 0& 0\\ 0& \cos \theta & -s\mathrm{in}\theta \\ 0& \sin \theta & \cos \theta \end{array}\right],$

[0387] $R_2\left(\theta \right)=\left[\begin{array}{ccc}\cos \theta & 0& \sin \theta \\ 0& 1& 0\\ -s\mathrm{in}\theta & 0& \cos \theta \end{array}\right],$
and

[0388] $R_3\left(\theta \right)=\left[\begin{array}{ccc}\cos \theta & -s\mathrm{in}\theta & 0\\ \sin \theta & \cos \theta & 0\\ 0& 0& 1\end{array}\right].$

[0389] The vector X and X′ may for example be position vectors with components (x, y, z) and (x′, y′, z′) or (x, y, θ) and (x′, y′, θ′), respectively. The method of transformation described herein allows the processor to transform vectors measured relative to different coordinate systems and describing the environment to be transformed into a single coordinate system.

[0390] The mapping steps described herein may be performed in various settings, such as with a camera installed on a robotic floor cleaning device, robotic lawn mowers, and/or other autonomous and semi-autonomous robots. The methods and techniques described, in some embodiments, are expected to increase processing efficiency and reduce computational cost using principals of information theory. Information theory provides that if an event is more likely and the occurrence of the event is expressed in a message, the message has less information as compared to a message that expresses a less likely event. Information theory formalizes and quantifies the amount of information born in a message using entropy. This is true for all information that is digitally stored, processed, transmitted, calculated, etc. Independent events also have additive information. For example, a message may express, “An earthquake did not happen 15 minutes ago, an earthquake did not happen 30 minutes ago, an earthquake happened 45 minutes ago”, another message may also express, “an earthquake happened 45 minutes ago”. The information born in either message is the same however the second message can express the message with less bits and is therefore said to have more information than the first message. Also, by definition of information theory, the second message, which reports an earthquake, is an event less likely to occur and therefor has more information than the first message which reports the more likely event of no earthquake. The entropy is defined as number of bits per symbol in a message and provided by −Σ_ip_i log₂(p_i), wherein p_i is the probability of occurrence of the i-th possible value of the symbol. If there is a way to express, store, process or transfer a message with the same information but with fewer number of bits, it is said to have more information. In the context of an environment of a robot, the perimeters within the immediate vicinity of and objects closest to the robot are most important. Therefore, if only information of the perimeters within the immediate vicinity of and objects closest to the robot are processed, a lot of computational costs are saved as compared to processing empty spaces, the perimeters and all the spaces beyond the perimeters. Perimeters or objects closest to the robot may be, for example, 1 meter away or may be 4 meters away. Avoiding the processing of empty spaces between the robot and closest perimeters or objects and spaces beyond the closest perimeters or objects substantially reduces computational costs. For example, some traditional techniques construct occupancy grids that assign statuses to every possible point within an environment, such statuses including “unoccupied”, “occupied” or “unknown”. At least some of the methods described herein may be considered a lossless (or less lossy) compression as an occupancy grid may be constructed at any time as needed. This is expected to save a lot of computational cost as additional information is not unnecessarily processed while access to the information is possible if required. This computational advantage enables the proposed mapping methods to run on, for example, an ARM M7 microcontroller as compared to much faster CPUs used in the current state of the art, thereby reducing costs for robots used within consumer homes. When used with faster CPUs, computational costs are saved, allowing the CPU to process other computational needs. Some embodiments may include an application specific integrated circuit (e.g., an AI co-processor ASIC) that cooperates with a physically separate or integrated central processing unit to analyze frames of video (and depth-camera readings) in the manner described herein. In some cases, the ASIC may include a relatively large number (e.g., more than 500) arithmetic logic units (ALUs) configured to operate concurrently on data. In some cases, the ALUs may be configured to operate on relatively low-precision data (e.g., less than or equal to 16 bits, 8 bits, or 4 bits) to afford more parallel computing units per unit area of chip substrate. In some cases, the AI co-processor ASIC may have an independent memory interface (relative to the CPU) to memory, and in some cases, independent memory from that accessed by the CPU. In some cases, the interface may be to high bandwidth memory (HBM), e.g., as specified by the JEDEC HBM2 specification, that includes a 3-dimensional stack of dynamic random access memory. In some cases, the memory accessed by the AI co-processor ASIC may be packed in a multi-chip package with such a 3-dimensional stack of memory, e.g., on a shared package substrate that connects to the CPU via a system board.

[0391] Other aspects of some embodiments are expected to further reduce computational costs (or increase an amount of image data processed for a given amount of computational resources). For example, in one embodiment, Euclidean norm of vectors may be processed and stored, expressing the depth to perimeters in the environment with a distribution density. This approach may have less loss of information when compared to some traditional techniques using an occupancy grid, which expresses the perimeter as points with an occupied status. This is a lossy compression. Information is lost at each step of the process due to the error in, for example, the reading device, the hardware word size, 8-bit processer, 16-bit processor, 32-bit processor, software word size of the reading device (using integers versus float to express a value), the resolution of the reading device, the resolution of the occupancy grid itself, etc. In this exemplary embodiment, the data is processed giving a probability distribution over the Euclidean norm of the measurements. The initial measurements begin with a triangle or Gaussian distribution and, following measurements, narrow down the overlap area between two sets of data to two possibilities that can be formulated with a Bernoulli distribution, simplifying calculations drastically. Additionally, to further off-load computational costs on the robot, in some embodiments, some data are processed on at least one separate device, such as a docking station of the robot or on the cloud.

[0392] In some embodiments, the processor of the robot uses sensor data to estimate its location within the environment prior to beginning and during the mapping process. In some embodiments, sensors of the robot capture data and the processor initially estimates the location of the robot based on the data and measured movement (e.g., using devices such as a gyroscope, optical encoder, etc.) of the robot. As more data is collected, the processor increases the confidence in the estimated location of the robot, and when movement occurs the processor decreases the confidence due to noise in measured movement.

[0393] In some embodiments, IMU measurements in a multi-channel stream indicative of acceleration along three or six axes may be integrated over time to infer a change in pose of the robot, e.g., with a Kalman filter. In some cases, the change in pose may be expressed as a movement vector in the frame of reference of the room through which the robot moves. Some embodiments may localize the robot or map the room based on this movement vector (and contact sensors in some cases) even if the image sensor is inoperative or degraded. In some cases, IMU measurements may be combined with image-based (or other exteroceptive) mapping data in a map or localization determination, e.g., with techniques like those described in Chen et. al “Real-time 3D mapping using a 2D laser scanner and IMU-aided visual SLAM,” 2017 IEEE International Conference on Real-time Computing and Robotics (RCAR), DOI: 10.1109/RCAR.2017.8311877, or in Ye et. al, LiDAR and Inertial Fusion for Pose Estimation by Non-linear Optimization, arXiv:1710.07104 [cs.RO], the contents of each of which are hereby incorporated by reference. Or in some cases, data from one active sensor may be used at a time for localization or mapping, and the other sensor may remain passive, e.g., sensing data, but that data may not be used for localization or mapping while the other sensor is active. Some embodiments may maintain a buffer of sensor data from the passive sensor (e.g., including measurements over a preceding duration, like one second or ten seconds), and upon failover from the active sensor to the passive sensor, which may then become active, some embodiments may access the buffer to infer a current position or map features based on both currently sensed data and buffered data. In some embodiments, the buffered data may be calibrated to the location or mapped features from the formerly active sensor, e.g., with the above-described sensor fusion techniques.

[0394] In embodiments, the constructed map of the robot may only be valid with accurate localization of the robot. For example, in FIG. 72, accurate localization of robot 3200 at location 3201 with position x₁, y₁ may result in map 3202 while inaccurate localization of robot 3200 at location 3203 with position x₂, y₂ may result in inaccurate map 3204 wherein perimeters of the map incorrectly appearing closer to robot 3200 as robot 3200 is localized to incorrect location 3203. To eliminate or reduce such occurrences, in some embodiments, the processor constructs a map for each or a portion of possible locations of robot 3200 and evaluates the alternative scenarios of possible locations of robot 3200 and corresponding constructed maps of such locations. The processor determines the number of alternative scenarios to evaluate in real-time or it is predetermined. In some embodiments, each new scenario considered adds a new dimension to the environment of robot 3200. Over time, the processor discards less likely scenarios. For example, if the processor considers a scenario placing robot 3200 at the center of a room and yet robot 3200 is observed to make contact with a perimeter, the processor determines that the considered scenario is an incorrect interpretation of the environment and the corresponding map is discarded. In some embodiments, the processor substitutes discarded scenarios with more likely scenarios or any other possible scenarios. In some embodiments, the processor uses a Fitness Proportionate Selection technique wherein a fitness function is used to assign a fitness to possible alternative scenarios and the fittest locations and corresponding maps survive while those with low fitness are discarded. In some embodiments, the processor uses the fitness level of alternative scenarios to associate a probability of selection with each alternative scenario that may be determined using the fitness function

[0395] $p_i=\frac{f_i}{\sum _{j=1}^N{f}_j},$
wherein ƒ₁ is the fitness of alternative scenario i of N possible scenarios and p_i is the probability of selection of alternative scenario i. In some embodiments, the processor is less likely to eliminate alternative scenarios with higher fitness level from the alternative scenarios currently considered. In some embodiments, the processor interprets the environment using a combination of a collection of alternative scenarios with high fitness level.

[0396] In some embodiments, the movement pattern of the robot during the mapping process is a boustrophedon movement pattern. This can be advantageous for mapping the environment. For example, if the robot begins in close proximity to a wall of which it is facing and attempts to map the environment by rotating 360 degrees in its initial position, areas close to the robot and those far away may not be observed by the sensors as the areas surrounding the robot are too close and those far away are too far. Minimum and maximum detection distances may be, for example, 30 and 400 centimeters, respectively. Instead, in some embodiments, the robot moves backwards (i.e., opposite the forward direction as defined below) away from the wall by some distance and the sensors observe areas of the environment that were previously too close to the sensors to be observed. The distance of backwards movement is, in some embodiments, not particularly large, it may be 40, 50, or 60 centimeters for example. In some cases, the distance backward is larger than the minimal detection distance. In some embodiments, the distance backward is more than or equal to the minimal detection distance plus some percentage of a difference between the minimal and maximal detection distances of the robot's sensor, e.g., 5%, 10%, 50%, or 80%.

[0397] The robot, in some embodiments, (or sensor thereon if the sensor is configured to rotate independently of the robot) then rotates 180 degrees to face towards the open space of the environment. In doing so, the sensors observe areas in front of the robot and within the detection range. In some embodiments, the robot does not translate between the backward movement and completion of the 180 degree turn, or in some embodiments, the turn is executed while the robot translates backward. In some embodiments, the robot completes the 180 degree turn without pausing, or in some cases, the robot may rotate partially, e.g., degrees, move less than a threshold distance (like less than 10 cm), and then complete the other 90 degrees of the turn.

[0398] References to angles should be read as encompassing angles between plus or minus 20 degrees of the listed angle, unless another tolerance is specified, e.g., some embodiments may hold such tolerances within plus or minus 15 degrees, 10 degrees, 5 degrees, or 1 degree of rotation. References to rotation may refer to rotation about a vertical axis normal to a floor or other surface on which the robot is performing a task, like cleaning, mapping, or cleaning and mapping. In some embodiments, the robot's sensor by which a workspace is mapped, at least in part, and from which the forward direction is defined, may have a field of view that is less than 360 degrees in the horizontal plane normal to the axis about which the robot rotates, e.g., less than 270 degrees, less than 180 degrees, less than 90 degrees, or less than 45 degrees. In some embodiments, mapping may be performed in a session in which more than 10%, more than 50%, or all of a room is mapped, and the session may start from a starting position, is where the presently described routines start, and may correspond to a location of a base station or may be a location to which the robot travels before starting the routine.

[0399] The robot, in some embodiments, then moves in a forward direction (defined as the direction in which the sensor points, e.g., the centerline of the field of view of the sensor) by some first distance allowing the sensors to observe surroundings areas within the detection range as the robot moves. The processor, in some embodiments, determines the first forward distance of the robot by detection of an obstacle by a sensor, such as a wall or furniture, e.g., by making contact with a contact sensor or by bringing the obstacle closer than the maximum detection distance of the robot's sensor for mapping. In some embodiments, the first forward distance is predetermined or in some embodiments the first forward distance is dynamically determined, e.g., based on data from the sensor indicating an object is within the detection distance.

[0400] The robot, in some embodiments, then rotates another 180 degrees and moves by some second distance in a forward direction (from the perspective of the robot), returning back towards its initial area, and in some cases, retracing its path. In some embodiments, the processor may determine the second forward travel distance by detection of an obstacle by a sensor, such moving until a wall or furniture is within range of the sensor. In some embodiments, the second forward travel distance is predetermined or dynamically determined in the manner described above. In doing so, the sensors observe any remaining undiscovered areas from the first forward distance travelled across the environment as the robot returns back in the opposite direction. In some embodiments, this back and forth movement described is repeated (e.g., with some amount of orthogonal offset translation between iterations, like an amount corresponding to a width of coverage of a cleaning tool of the robot, for instance less than 100% of that width, 95% of that width, 90% of that width, 50% of that width, etc.) wherein the robot makes two 180 degree turns separated by some distance, such that movement of the robot is a boustrophedon pattern, travelling back and forth across the environment. In some embodiments, the robot may not be initially facing a wall of which it is in close proximity with. The robot may begin executing the boustrophedon movement pattern from any area within the environment. In some embodiments, the robot performs other movement patterns besides boustrophedon alone or in combination.

[0401] In other embodiments, the boustrophedon movement pattern (or other coverage path pattern) of the robot during the mapping process differs. For example, in some embodiments, the robot is at one end of the environment, facing towards the open space. From here, the robot moves in a first forward direction (from the perspective of the robot as defined above) by some distance then rotates 90 degrees in a clockwise direction. The processor determines the first forward distance by which the robot travels forward by detection of an obstacle by a sensor, such as a wall or furniture. In some embodiments, the first forward distance is predetermined (e.g., and measured by another sensor, like an odometer or by integrating signals from an inertial measurement unit). The robot then moves by some distance in a second forward direction (from the perspective of the room, and which may be the same forward direction from the perspective of the robot, e.g., the direction in which its sensor points after rotating); and rotates another 90 degrees in a clockwise direction. The distance travelled after the first 90-degree rotation may not be particularly large and may be dependent on the amount of desired overlap when cleaning the surface. For example, if the distance is small (e.g., less than the width of the main brush of a robotic vacuum), as the robot returns back towards the area it began from, the surface being cleaned overlaps with the surface that was already cleaned. In some cases, this may be desirable. If the distance is too large (e.g., greater than the width of the main brush) some areas of the surface may not be cleaned. For example, for small robots, like a robotic vacuum, the brush size typically ranges from 15-30 cm. If 50% overlap in coverage is desired using a brush with 15 cm width, the travel distance is 7.5 cm. If no overlap in coverage and no coverage of areas is missed, the travel distance is 15 cm and anything greater than 15 cm would result in coverage of area being missed. For larger commercial robots brush size can be between 50-60 cm. The robot then moves by some third distance in forward direction back towards the area of its initial starting position, the processor determining the third forward distance by detection of an obstacle by a sensor, such as wall or furniture. In some embodiments, the third forward distance is predetermined. In some embodiments, this back and forth movement described is repeated wherein the robot repeatedly makes two 90-degree turns separated by some distance before travelling in the opposite direction, such that movement of the robot is a boustrophedon pattern, travelling back and forth across the environment. In other embodiments, the directions of rotations are opposite to what is described in this exemplary embodiment. In some embodiments, the robot may not be initially facing a wall of which it is in close proximity. The robot may begin executing the boustrophedon movement pattern from any area within the environment. In some embodiments, the robot performs other movement patterns besides boustrophedon alone or in combination.

[0402] FIGS. 73A-73F illustrate an example of a boustrophedon movement pattern of the robot. In FIG. 73A robot 3300 begins near wall 3301, docked at its charging or base station 3302. Robot 3300 rotates 360 degrees in its initial position to attempt to map environment 3303, however, areas 3304 are not observed by the sensors of robot 3300 as the areas surrounding robot 3300 are too close, and the areas at the far end of environment 3303 are too far to be observed. Minimum and maximum detection distances may be, for example, 30 and 400 centimeters, respectively. Instead, in FIG. 73B, robot 3300 initially moves backwards in direction 3305 away from charging or base station 3302 by some distance 3306 where areas 3307 are observed. Distance 3306 is not particularly large, it may be 40 centimeters, for example. In FIG. 73C, robot 3300 then rotates 180 degrees in direction 3308 resulting in observed areas 3307 expanding. Areas immediately to either side of robot 3300 are too close to be observed by the sensors while one side is also unseen, the unseen side depending on the direction of rotation. In FIG. 73D, robot 3300 then moves in forward direction 3309 by some distance 3310, observed areas 3307 expanding further as robot 3300 explores undiscovered areas. The processor of robot 3300 determines distance 3310 by which robot 3300 travels forward by detection of an obstacle, such as wall 3311 or furniture or distance 3310 is predetermined. In FIG. 73E, robot 3300 then rotates another 180 degrees in direction 3308. In FIG. 73F, robot 3300 moves by some distance 3312 in forward direction 3313 observing remaining undiscovered areas. The processor determines distance 3312 by which the robot 3300 travels forward by detection of an obstacle, such as wall 3301 or furniture or distance 3312 is predetermined. The back and forth movement described is repeated wherein robot 3300 makes two 180 degree turns separated by some distance, such that movement of robot 3300 is a boustrophedon pattern, travelling back and forth across the environment while mapping. In other embodiments, the direction of rotations may be opposite to what is illustrated in this exemplary embodiment.

[0403] FIGS. 74A-74D illustrate another embodiment of a boustrophedon movement pattern of the robot during the mapping process. FIG. 74A illustrates robot 3300 beginning the mapping process facing wall 3400, when for example, it is docked at charging or base station 3401. In such a case, robot 3300 initially moves in backwards direction 3402 away from charging station 3401 by some distance 3403. Distance 3403 is not particularly large, it may be 40 centimeters for example. In FIG. 74B, robot 3300 rotates 180 degrees in direction 3404 such that robot 3300 is facing into the open space of environment 3405. In FIG. 74C, robot 3300 moves in forward direction 3406 by some distance 3407 then rotates 90 degrees in direction 3404. The processor determines distance 3407 by which robot 3300 travels forward by detection of an obstacle, such as wall 3408 or furniture or distance 3407 is predetermined. In FIG. 74D, robot 3300 then moves by some distance 3409 in forward direction 3410 and rotates another 90 degrees in direction 3404. Distance 3409 is not particularly large and depends on the amount of desired overlap when cleaning the surface. For example, if distance 3409 is small (e.g., less than the width of the main brush of a robotic vacuum), as robot 3300 returns in direction 3412, the surface being cleaned may overlap with the surface that was already cleaned when robot 3300 travelled in direction 3406. In some cases, this may be desirable. If distance 3409 is too large (e.g., greater than the width of the main brush) some areas of the surface may not be cleaned. For example, for small robots, like a robotic vacuum, the brush size typically ranges from 15-30 cm. If 50% overlap in coverage is desired using a brush with 15 cm width, the travel distance is 7.5 cm. If no overlap in coverage and no coverage of areas is missed, the travel distance is 15 cm and anything greater than 15 cm would result in coverage of area being missed. For larger commercial robots brush size can be between 50-60 cm. Finally, robot 3300 moves by some distance 3411 in forward direction 3412 towards charging station 3401. The processor determines distance 3411 by which robot 3300 travels forward may be determined by detection of an obstacle, such as wall 3400 or furniture or distance 3411 is predetermined. This back and forth movement described is repeated wherein robot 3300 repeatedly makes two 90-degree turns separated by some distance before travelling in the opposite direction, such that movement of robot 3300 is a boustrophedon pattern, travelling back and forth across the environment while mapping. Repeated movement 3413 is shown in FIG. 74D by dashed lines. In other embodiments, the direction of rotations may be opposite to what is illustrated in this exemplary embodiment.

[0404] FIG. 75 illustrates a flowchart describing embodiments of a path planning method of a robot 3500, 3501, 3502 and 3503 corresponding with steps performed in some embodiments.

[0405] In some embodiments, the processor may manipulate the map by cleaning up the map for navigation purposes or aesthetics purposes (e.g., displaying the map to a user). For example, FIG. 76A illustrates a perimeter 3600 of an environment that may not be aesthetically pleasing to a user. FIG. 76B illustrates an alternative version of the map illustrated in FIG. 76A wherein the perimeter 3601 may be more aesthetically pleasing to the user. In some embodiments, the processor may use a series of techniques, a variation of each technique, and/or a variation in order of applying the techniques to reach the desired outcome in each case. For example, FIG. 77A illustrates a series of measurements 3700 to perimeter 3701 of an environment. In some cases, it may be desirable that the perimeter 3701 of the environment is depicted. In embodiments, different methods may be used in processing the data to generate a perimeter line. In some embodiments, the processor may generate a line from all the data points using least square estimation, such as in FIG. 77A. In some embodiments, the processor may determine the distances from each point to the line and may select local maximum and minimum L2 norm values. FIG. 77B illustrates the series of measurements 3700 to line 3701 generated based on least square estimation of all data points and selected local maximum and minimum L2 norm values 3702. In some embodiments, the processor may connect local maximum and minimum L2 norm values. For example, FIG. 77C illustrates local maximum and minimum L2 norm values 3702 connected to each other. In some embodiments, the connected local maximum and minimum L2 norm values may represent the perimeter of the environment. FIG. 77D illustrates a possible depiction of the perimeter 3703 of the environment.

[0406] In another method, the processor may initially examine a subset of the data. For example, FIG. 78A illustrates data points 3800. Initially, the processor may examine data points falling within columns one to three or area 3801. In some embodiments, the processor may fit a line to the subset of data using, for example, least square method. FIG. 78B illustrates a line 3802 fit to data points falling within columns one to three. In some embodiments, the processor may examine data points adjacent to the subset of data and may determine whether the data points belong with the same line fitted to the subset of data. For example, in FIG. 78C, the processor may consider data points falling within column four 3803 and may determine if the data points belong with the line 3802 fitted to the data points falling with columns one to three. In some embodiments, the processor may repeat the process of examining data adjacent to the last set of data points examined. For example, after examining data points falling with column four in FIG. 78C, the processor may examine data points falling with column five. In some embodiments, other variations of this technique may be used. For example, the processor may initially examine data falling within the first three columns, then may examine the next three columns. The processor may compare a line fitted to the first three columns to a line fitted to the next three columns. This variation of the technique may result in a perimeter line such as that illustrated in FIG. 79. In another variation, the processor examines data points falling within the first three columns, then examines data points falling within another three columns, some of which overlap with the first three columns. For example, the first three columns may be columns one to three and the other three columns may be columns three to five or two to four. The processor may compare a line fitted to the first three columns to a line fitted to the other three columns. In other embodiments, other variations may be used.

[0407] In another method, the processor may choose a first data point A and a second data point B from a set of data points. In some embodiments, data point A and data point B may be next to each other or close to one another. In some embodiments, the processor may choose a third data point C from the set of data points that is spatially positioned in between data point A and data point B. In some embodiments, the processor may connect data point A and data point B by a line. In some embodiments, the processor may determine if data point C fits the criteria of the line connecting data points A and B. In some embodiments, the processor determines that data points A and B within the set of data points are not along a same line. For example, FIG. 80 illustrates a set of data points 4000, chosen data points A, B, and C, and line 4001 connecting data point A and B. Since data point C does not fit criteria of lines 4001, it may be determined that data points A and B within the set of data point 4000 do not fall along a same line. In another variation, the processor may choose a first data point A and a second data point B from a set of data points and may connect data points A and B by a line. In some embodiments, the processor may determine a distance between each data point of the set of data points to the line connecting data points A and B. In some embodiments, the processor may determine the number of outliers and inliers. In some embodiments, the processor may determine if data points A and B fall along the same line based on the number of outliers and inliers. In some embodiments, the processor may choose another two data points C and D if the number of outliers or the ratio of outliers to inliers is greater than a predetermined threshold and may repeat the processor with data points C and D. FIG. 81A illustrates a set of data points 4100, data points A and B and line 4101 connecting data points A and B. The processor determines distances 4102 from each of the data points of the set of data points 4100 to line 4101. The processor determines the number of data points with distances falling within region 4103 as the number of inlier data points and the number of data points with distances falling outside of region 4103 as the number of outlier points. In this example, there are too many outliers. Therefore, FIG. 81B illustrates another two selected data points C and D. The process is repeated and less outliers are found in this case as there are less data points with distances 4104 falling outside of region 4105. In some embodiments, the processor may continue to choose another two data points and repeat the process until a minimum number of outliers is found or the number of outliers or the ratio of outliers to inliers is below a predetermined threshold. In some embodiments, there may be too may data points within the set of data points to select data points in sets of two. In some embodiments, the processor may probabilistically determine the number of data points to select and check based on the accuracy or minimum probability required. For example, the processor may iterate the method 20 times to achieve a 99% probability of success. Any of the methods and techniques described may be used independently or sequentially, one after another, or may be combined with other methods and may be applied in different orders.

[0408] In some embodiments, the processor may use image derivative techniques. Image derivative techniques may be used with data provided in various forms and are not restricted to being used with images. For example, image derivative techniques may be used with an array of distance readings (e.g., a map) or other types of readings just as well work well with a combination of these methods. In some embodiments, the processor may use a discrete derivative as an approximation of a derivative of an image I. In some embodiments, the processor determines a derivative in an x-direction for a pixel x₁ as the difference between the value of pixel x₁ and the values of the pixels to the left and right of the pixel x₁. In some embodiments, the processor determines a derivative in a y-direction for a pixel y₁ as the difference between the value of pixel y₁ and the values of the pixels above and below the pixel y₁. In some embodiments, the processor determines an intensity change I_x and I_y for a grey scale image as the pixel derivatives in the x- and y-directions, respectively. In some embodiments, the techniques described may be applied to color images. Each RGB of a color image may add an independent pixel value. In some embodiments, the processor may determine derivatives for each of the RGB or color channels of the color image. More colors and channels may be used for better quality. In some embodiments, the processor determines an image gradient ∇I, a 2D vector, as the derivative in the x- and y-direction. In some embodiments, the processor may determine a gradient magnitude,

[0409] $\nabla I=\sqrt{\left(I_x^2+I_y^2\right)},$
which may indicate the strength of intensity change. In some embodiments, the processor may determine a gradient angle, α=arctan 2 (I_x, I_y), which may indicate the angle at which the image intensity change is more dominant. Since the derivatives of an image are discrete values, there is no mathematical derivative, therefore the processor may employ approximations for the derivatives of an image using discrete differentiation operators. For example, the processor may use the Prewitt operator which convolves the image with a small, separable, and integer valued filter in horizontal and vertical directions. The Prewitt operator may use two 3×3 kernels,

[0410] $\hspace{1em}\left[\begin{array}{ccc}-1& 0& 1\\ -1& 0& 1\\ -1& 0& 1\end{array}\right]$
and

[0411] $\left[\begin{array}{ccc}-1& -1& -1\\ 0& 0& 0\\ 1& 1& 1\end{array}\right],$
that may be convolved with the original image I to determine approximations of the derivatives in an x- and y-direction, i.e., I_x=I*

[0412] $\hspace{1em}\left[\begin{array}{ccc}-1& 0& 1\\ -1& 0& 1\\ -1& 0& 1\end{array}\right]$
and I_y=I*

[0413] $\hspace{1em}\left[\begin{array}{ccc}-1& -1& -1\\ 0& 0& 0\\ 1& 1& 1\end{array}\right].$
In another example, the processor may use the Sobel-Feldman operator, an isotropic 3×3 image gradient operator which at each point in the image returns either the corresponding gradient vector or the norm of the gradient vector, which convolves the image with a small, separable, and integer valued filter in horizontal and vertical directions. The Sobel-Feldman operator may use two 3×3 kernels,

[0414] $\hspace{1em}\left[\begin{array}{ccc}-1& 0& 1\\ -2& 0& 2\\ -1& 0& 1\end{array}\right]$
and

[0415] $\left[\begin{array}{ccc}-1& -2& -1\\ 0& 0& 0\\ 1& 2& 1\end{array}\right],$
that may be convolved with the original image I to determine approximations of the derivatives in an x- and y-direction, i.e., I_x=I*

[0416] $\hspace{1em}\left[\begin{array}{ccc}-1& 0& 1\\ -2& 0& 2\\ -1& 0& 1\end{array}\right]$
and I_y=I*

[0417] $\left[\begin{array}{ccc}-1& -2& -1\\ 0& 0& 0\\ 1& 2& 1\end{array}\right].$
The processor may use other operators, such as Kayyali operator, Laplacian operator, and Robert Cross operator.

[0418] In some embodiments, the processor may use image denoising methods image in one or more processing steps to remove noise from an image while maintaining the integrity, detail, and structure of the. In some embodiments, the processor may determine the total variation of an image as the sum of the gradient norm, J(I)=∫|∇I|dxdy or J(I)=Σ_xy|∇I|, wherein the integral is taken over all pixels of the image. In some embodiments, the processor may use Gaussian filters to determine derivatives of an image, I_x=I*G_σx and I_y=I*G_σy, wherein G_σx and G_σy are the x and y derivatives of a Gaussian function G_σ with standard deviation σ. In some embodiments, the processor may use total variation denoising or total variation regularization to remove noise while preserving edges. In some embodiments, the processor may determine a total variation norm of 2D signals y (e.g., images) using V(y)=Σ_i,j√{square root over (|y_i+1,j−y_i,j|²+|y_i,j+1−y_i,j|²)}, which is isotropic and not differentiable. In some embodiments, the processor may use an alternative anisotropic version, V(y)=Σ_i,j√{square root over (|y_i+1,j−y_i,j|²)}+√{square root over (|y_i,j+1−y_i,j|²)}=Σ_i,j|y_i+1,j−y_i,j|+|y_i,j+1−y_i,j. In some embodiments, the processor may solve the standard total variation denoising problem
[E(x,y)+Δ V(y)],
wherein E is the 2D L2 norm. In some embodiments, different algorithms may be used to solve the problem, such as prime dual method or split-Bergman method. In some embodiments, the processor may employ Rudin-Osher-Fatemi (ROF) denoising technique to a noisy image ƒ to determine a denoised image u over a 2D space. In some embodiments, the processor may solve the ROF minimization problem

[0419] $\underset{u\in BV\left(\Omega \right)}{\min }{u}_{TV\left(\Omega \right)}+\frac{\lambda }{2}{\int }_{\Omega }{\left(f-u\right)}^{2}dx,$
wherein BV(Ω) is the bounded variation over the domain Ω, TV(Ω) is the total variation over the domain, and λ is a penalty term. In some embodiments, u may be smooth and the processor may determine the total variation using ∥u∥_{TV (Ω)}=∫_Ω∥∇u∥dx and the minimization problem becomes

[0420] $\underset{u\in BV\left(\Omega \right)}{\min }{\int }_{\Omega }{\left[\nabla u+\frac{\lambda }{2}\left(f-u\right)\right]}^{2}dx.$
Assuming no time dependence, the Euler-Lagrange equation for minimization may provide the nonlinear elliptic partial differential equation

[0421] $\{\begin{array}{c}\nabla ·\left(\frac{\nabla u}{\nabla u}\right)+\lambda \left(f-u\right)=0,u\in \Omega \\ \frac{\partial u}{\partial n}=0,u\in \partial \Omega \end{array}.$
In some embodiments, the processor may instead solve the time-dependent version of the ROF problem,

[0422] $\frac{\partial u}{\partial t}=\nabla ·\left(\frac{\nabla u}{\nabla u}\right)+\lambda \left(f-u\right).$
In some embodiments, the processor may use other denoising techniques, such as chroma noise reduction, luminance noise reduction, anisotropic diffusion, Rudin-Osher-Fatemi, and Chambolle. Different noise processing techniques may provide different advantages and may be used in combination and in any order.