Patent Description:
In many cases, a mobile robot may utilize a navigation system that relies on satellite-based positioning information. This can allow the robot to determine its current position and to follow pre-planned paths based on world coordinates. To make use of satellite-based positioning, the robot may include a sensor that receives satellite signals. Such a sensor may be referred to as a global navigation satellite system (GNSS) receiver, and compatible satellites may be referred to as GNSS satellites. Examples of currently operational GNSSs include the United States' Global Positioning System (GPS), Russia's Global Navigation Satellite System (GLONASS), China's BeiDou Satellite Navigation System, the European Union's (EU) Galileo, Japan's Quasi-Zenith Satellite System (QZSS), and the Indian Regional Navigation Satellite System (IRNSS).

The accuracy of GNSS-based positioning systems rely on several factors, among which include the availability of multiple GNSS satellites having a line-of-sight (LOS) relationship with the GNSS receiver, as well as the limited presence of multipath interference, which is a significant source of inaccuracy for GNSS-based computations. Multipath interference may be caused by wireless signals reflecting off objects while on their way to the GNSS receiver. Such objects may include mountains, trees, buildings, ground, water, persons, etc. A reflected signal, also referred to as a multipath signal, arrives at the GNSS receiver later than a LOS signal since it has to travel over a greater distance. While reflected signals with large time delays can be filtered out, reflected signals with shorter delays often distort the correlation function shape used for time delay estimation. If reflected signals are strong enough in comparison to the LOS signals, the reflected signals can confuse the GNSS receiver and cause erroneous measurements.

As such, problems can arise when a mobile robot using a satellite- or GNSS-based positioning system is placed in a location with significant multipath interference or a lack of a sufficient number of LOS satellite signals. This can often occur when the robot's view of the sky is obscured by objects that the robot is travelling near or under. Due to their size and complex geometries (e.g., trees, buildings with overhands, elevated solar panels, etc.), these objects are often not detected by the robot's sensors capturing nearby ground-based information. As such, new systems, methods, and other techniques are needed to address these and other issues.

<CIT> discloses systems and methods for vehicle navigation. A navigation system for a vehicle comprises a processor programmed to obtain a route from a location of the vehicle to a destination; receive signal information indicative of a quality characteristic of a signal associated with at least one location along the route; determine a quality parameter for at least one operational characteristic associated with a communication system; and determine at least one modification to the route for the vehicle based on the signal information and the quality parameter.

The invention is directed to a method according to independent claim <NUM>, a system according to independent claim <NUM> and a non-transitory computer-readable medium according to independent claim <NUM>. Further details are included in the dependent claims.

The accompanying drawings, which are included to provide a further understanding of the disclosure, are incorporated in and constitute a part of this specification, illustrate embodiments of the disclosure and together with the detailed description serve to explain the principles of the disclosure. No attempt is made to show structural details of the disclosure in more detail than may be necessary for a fundamental understanding of the disclosure and various ways in which it may be practiced.

Navigation systems employed by autonomous mobile robots can utilize both ground-based information and satellite-based information to generate, follow, and modify a path between start and destination locations. The satellite-based information may be captured using a global navigation satellite system (GNSS) receiver that may be mounted on the robot at a position where light-of-sight (LOS) wireless signals may be received from one or more satellites. Since satellite-based information can be unreliable in locations that exhibit significant multipath interference or that lack a sufficient number of LOS satellite signals, it can be beneficial for the robot to predict where these problematic locations are, modify the robot's path to avoid these locations, and alter the positioning algorithm if the robot is positioned in these locations to rely less on (or ignore completely) satellite-based information in favor of ground-based information.

Embodiments of the present disclosure relate to techniques for handling satellite-based data in navigation systems for mobile machines. As used herein, a mobile machine may refer to a robot (autonomous or non-autonomous), a vehicle, or any machine that can move over a distance, for example, along a path. As used herein, satellite-based data (or simply "satellite data") may refer to any data or other information captured by a sensor, such as a GNSS receiver, from satellite(s) located in the sky above the mobile machine, for example, in low Earth or medium-Earth orbit.

Some embodiments of the present disclosure include a technique of forming a hybrid sky and ground navigation map (or simply "navigation map") and using the navigation map to modify the navigation of the mobile machine. The navigation map may include a set of ground scores related to the accessibility or navigability of the terrain surrounding the mobile machine. For example, positions along the ground that may be difficult for the mobile machine to move through, such as due to an obstacle, such as a tree, a bench, or a curb, may have a low ground score while positions along the ground that are more easily moved through, such as flat ground, may have a high ground score.

The navigation map may further include a set of sky scores related to the accuracy of potentially calculated geospatial positions at the same positions along the ground as the set of ground scores. For example, a sky score for a particular position along the ground (or ground position) may be high if it is determined that the availability of LOS satellites would be high (e.g., greater than three LOS satellites) and/or that multipath interference would be low if the mobile machine were to be positioned at the particular ground position. In contrast, a sky score for a particular ground position may be low if it is determined that the availability of LOS satellites would be low (e.g., less than three LOS satellites) and/or that multipath interference would be high if the mobile machine were to be positioned at the particular ground position.

The navigation map may be formed using the various sensors employed by the mobile machine. For example, the set of ground scores may be calculated using data (referred to as ground data) captured using any sensor (referred to as a ground sensor) that captures data indicative of the physical surface of the ground. Ground sensors may include cameras, depth sensors, acoustic sensors, radar, LiDAR, among other possibilities. The set of sky scores may be calculated using satellite data captured using a GNSS receiver and an image of the sky captured by an upward-facing camera mounted to the mobile machine. The image may be a camera image captured by a camera, a depth image captured by a depth sensor, among other possibilities. The image captured by the upward-facing camera may be referred to as an upward-facing image.

In some examples, a sky score for a particular ground position may be calculated by estimating the quantity of LOS satellites that would be available at the particular ground position. This quantity may be estimated by modeling the environment surrounding the mobile machine using a single or multiple upward-facing images. For example, multiple images can be used to estimate the height of an object based on the distance traveled by the mobile machine between the images being captured and the movement of the object within the images (e.g., number of pixels moved).

Some embodiments described herein allow for selectively processing received satellite signals. For example, each satellite signal that is received can be processed differently based on where in the upward-facing image the corresponding satellite is located. For example, using the satellite's location within the image, it can be determined whether there is a direct visible LOS to the satellite or if it is blocked by an object. This can be accomplished by projecting the orbital positions of the satellites onto the image and determining whether a radio frequency (RF)-blocking object is aligned with the projection. Tracking of a blocked satellite indicates that the pseudorange and carrier phase measurements correspond to reflected signals and should either be ignored or deweighted relative to the LOS signals.

The upward-facing image is segmented into multiple regions based on the predicted RF characteristics of objects in the image, and the orbital positions of the satellites are projected onto one of the regions. In one example, the upward-facing image is segmented into three regions: one region having objects that provide little RF obstruction (e.g., clear sky, clouds), one region having objects that provide some RF obstruction (e.g., vegetation, foliage), and one region having objects that provide significant RF obstruction (e.g., buildings, mountains). The segmentation can be performed using a machine-learning model, such as a neural network, or using any one of various image segmentation techniques.

Upon receiving a satellite signal, the GNSS receiver can look up the orbital position of the satellite that transmitted the signal and project the orbital position onto the upward-facing image. The orbital position may be determined based on the satellite signal itself (e.g., extracted from the ephemeris data modulated onto the satellite signal) or may be obtained elsewhere. The pixel location onto which the orbital position is projected is recorded. Next, the pixel location is compared to the segmented regions to determine in which region the pixel location is located. The identified region is associated with the satellite and the corresponding satellite signal. Projecting the orbital positions of the satellites is facilitated by an accurate measurement of the position and orientation of the imaging device and the corresponding upward-facing image.

<FIG> illustrates an example of a mobile machine <NUM> navigating within an environment that includes objects that may block, reflect, or distort satellite signals, in accordance with some embodiments of the present disclosure. In some instances, <FIG> may correspond to a scenario in which mobile machine <NUM> is operating in an environment with multipath interference. Mobile machine <NUM> may include a GNSS receiver <NUM> that receives wireless signals <NUM> that are broadcasted by GNSS satellites <NUM>. Wireless signals <NUM> may contain pseudo-random-noise (PRN) codes modulated onto carrier frequencies. Broadcasted wireless signals <NUM> may include both LOS signals <NUM>, i.e., signals transmitted and received without reflection off objects, and reflected signals <NUM>, i.e., signals received by GNSS receiver <NUM> after reflection off at least one object, such as buildings <NUM>. LOS signals <NUM> and reflected signals <NUM> are each received by GNSS receiver <NUM> via a GNSS antenna while GNSS receiver <NUM> is attempting to compute its geospatial position.

To navigate through the environment, mobile machine <NUM> may generate a navigation map <NUM> that includes sky scores and/or ground scores for multiple ground positions surrounding mobile machine <NUM>. The scores included in navigation map <NUM> may be defined over a grid, as shown, or over some other spatial distribution (evenly or unevenly spaced). As described herein, navigation map <NUM> may facilitate mobile machine <NUM> in generating a path between start and destination locations or modifying a pre-planned path. For example, the sky scores in navigation map <NUM> may inform mobile machine <NUM> as to the accuracy of potentially calculated geospatial positions at the ground positions and the ground scores in navigation map <NUM> may inform mobile machine <NUM> as to the accessibility or navigability of the terrain at the ground positions.

In many instances, mobile machine <NUM> may want to distinguish between LOS signals <NUM> and reflected signals <NUM> for the purpose of generating sky scores for navigation map <NUM>. For example, the sky scores may be calculated such that a ground position that is able to receive multiple LOS signals <NUM> and few reflected signals <NUM> may have a high sky score and a ground position that is able to receive few LOS signals <NUM> and multiple reflected signals <NUM> may have a low sky score. In some implementations, the sky scores may be calculated based on LOS signals <NUM> alone since mobile machine <NUM> may have the capability of ignoring or deweighting reflected signals <NUM>.

To distinguish between LOS signals <NUM> and reflected signals <NUM>, mobile machine <NUM> may capture an image <NUM> using an imaging device <NUM> that is at least partially oriented in the upward direction toward GNSS satellites <NUM>. Image <NUM> may be analyzed and segmented into different regions, and the orbital positions of GNSS satellites <NUM> may be projected onto image <NUM>. A location <NUM>-<NUM> within image <NUM> onto which the orbital location of GNSS satellite <NUM>-<NUM> is projected indicates that wireless signals <NUM>-<NUM> at least include LOS signal <NUM>. Based on the proximity of buildings <NUM>, GNSS receiver <NUM> may also predict that wireless signals <NUM>-<NUM> further includes reflected signal <NUM>-<NUM>. A location <NUM>-<NUM> within image <NUM> onto which the orbital location of GNSS satellite <NUM>-<NUM> is projected indicates that wireless signals <NUM>-<NUM> do not include a LOS signal but instead include reflected signal <NUM>-<NUM>.

GNSS receiver <NUM> may accordingly track wireless signals <NUM>-<NUM> while ignoring wireless signals <NUM>-<NUM>, since wireless signals <NUM>-<NUM> only include a reflected signal. In some instances, GNSS receiver <NUM> may weight wireless signals <NUM>-<NUM> and <NUM>-<NUM> differently while computing its geospatial position. For example, GNSS receiver <NUM> may process wireless signals <NUM>-<NUM> with a weight value of <NUM> and wireless signals <NUM>-<NUM> with a weight value of <NUM>. GNSS receiver <NUM> may later modify (decrease) the weight value associated with wireless signals <NUM>-<NUM> when wireless signals from additional GNSS satellites become available and unobstructed by objects.

<FIG> illustrates an example image <NUM> captured by an imaging device, in accordance with some embodiments of the present disclosure. Image <NUM> is an upward-facing image and shows the vertical hemisphere in a setting with buildings, trees, and open sky. In the illustrated example, the imaging device used to capture image <NUM> includes a wide-angle lens, such as a fisheye lens.

<FIG> illustrates an example segmentation of image <NUM> into multiple regions <NUM>, in accordance with the invention. Each of regions <NUM> includes objects with similar RF-blocking characteristics and different regions include objects with dissimilar RF-blocking characteristics. Region <NUM>-<NUM> corresponds to clouds or open sky and includes objects that provide little RF obstruction. Region <NUM>-<NUM> corresponds to vegetation or foliage and includes objects that provide some RF obstruction. Region <NUM>-<NUM> corresponds to buildings and includes objects that provide significant RF obstruction.

<FIG> illustrates an example projection of GNSS satellites onto image <NUM>, in accordance with some embodiments of the present disclosure. In the illustrated example, a GNSS receiver receives GNSS signals from satellite #<NUM> (indicated in <FIG> as "#<NUM>"), determines the orbital position of satellite #<NUM>, projects satellite #<NUM> onto image <NUM> by determining the pixel location for satellite #<NUM> based on the position and orientation of image <NUM> and the orbital position of satellite #<NUM>, and region <NUM>-<NUM> is identified as including the pixel location for satellite #<NUM>. Similarly, the GNSS receiver receives GNSS signals from satellite #<NUM>, determines the orbital position of satellite #<NUM>, projects satellite #<NUM> onto image <NUM> by determining the pixel location for satellite #<NUM> based on the position and orientation of image <NUM> and the orbital position of satellite #<NUM>, and region <NUM>-<NUM> is identified as including the pixel location for satellite #<NUM>. Similar steps are performed for each of satellites #<NUM>, #<NUM>, #<NUM>, and #<NUM>, except that region <NUM>-<NUM> is identified as including the pixel location for satellite #<NUM> and region <NUM>-<NUM> is identified as including the pixel locations for satellites #<NUM> and #<NUM>.

In some embodiments, the received GNSS signals corresponding to satellites #<NUM>, #<NUM>, and #<NUM> may be determined to be LOS signals, the received GNSS signals corresponding to satellites #<NUM> and #<NUM> may be determined to be reflected signals, and the received GNSS signals corresponding to satellite #<NUM> may be flagged as possibly being either LOS or reflected. The GNSS signals in the three regions may be processed in accordance with their region. For example, a weight table may provide that pseudoranges computed using GNSS signals in region <NUM>-<NUM> may be weighted by a weight of <NUM>, pseudoranges computed using GNSS signals in region <NUM>-<NUM> may be weighted by a weight of <NUM>, and pseudoranges computed using GNSS signals in region <NUM>-<NUM> may be weighted by a weight of <NUM>.

In some embodiments, the weight assigned to a satellite may be modified based on the proximity of the satellite's pixel location to a neighboring region. For example, the weight assigned to satellite #<NUM> may be less than the weight assigned to satellite #<NUM> due to the proximity of the pixel location for satellite #<NUM> to region <NUM>-<NUM>. As another example, the weight assigned to satellite #<NUM> may be greater than the weight assigned to satellite #<NUM> due to the proximity of the pixel location for satellite #<NUM> to region <NUM>-<NUM>. In some instances, the assigned weight may be increased or decreased linearly as a function of distance from the nearest neighboring region, with some minimum threshold distance from the boundary at which the assigned weight begins to be adjusted, e.g., <NUM> pixels, <NUM> pixels, <NUM> pixels, etc..

In some embodiments, the weight table may be modified based on the number of detected satellites. For example, the weight table may be initialized or set to [<NUM>, <NUM>, <NUM>] (corresponding to regions <NUM>-<NUM>, <NUM>-<NUM>, and <NUM>-<NUM>, respectively) until a threshold number of satellites (e.g., four or five) is reached. For example, upon receiving GNSS signals from the fourth or fifth satellite, the weight table may be modified from [<NUM>, <NUM>, <NUM>] to [<NUM>, <NUM>, <NUM>], thereby deweighting the GNSS signals in regions <NUM>-<NUM> and <NUM>-<NUM>. Continuing with the above example, upon receiving GNSS signals from a second threshold number of satellites (e.g., six or seven), the weight table may be modified from [<NUM>, <NUM>, <NUM>] to [<NUM>, <NUM>, <NUM>] , thereby further deweighting the GNSS signals in regions <NUM>-<NUM> and <NUM>-<NUM>. Other possibilities of dynamically adjusting the weight table based on the number of detected satellites are contemplated and are considered to be within the scope of the present disclosure.

In some embodiments, a sky score for a ground position may be calculated using image <NUM> and the identified regions. For example, the sky score may be calculated by a formulation that sums the satellites in image <NUM> and weights each satellite in accordance with the corresponding region that was identified for the satellite. For example, the sky score may be calculated by summing satellite #<NUM>, #<NUM>, and #<NUM> and weighting each with a first weight (e.g. <NUM>(<NUM>) + <NUM>(<NUM>) + <NUM>(<NUM>) = <NUM>), summing satellite #<NUM> and weighting it with a second weight (e.g., <NUM>(<NUM>) = <NUM>), summing satellites #<NUM> and #<NUM> and weighting each with a third weight (e.g., <NUM>(<NUM>) + <NUM>(<NUM>) = <NUM>), and setting the sky score equal to the total (e.g., <NUM> + <NUM> + <NUM> = <NUM>).

<FIG> illustrates an example of a mobile machine <NUM> navigating between start and destination locations using a navigation map <NUM>, in accordance with some embodiments of the present disclosure. In the example of <FIG>, navigation map <NUM> includes a set of ground scores for a set of ground positions. Each of the set of ground scores in navigation map <NUM> may indicate how accessible a particular ground position is to mobile machine <NUM>. For example, the ground score for ground positions that are relatively flat is equal to <NUM> while the ground score for impassible ground positions (e.g., due to a tree or building) is equal to <NUM>.

After forming navigation map <NUM>, the navigation system of mobile machine <NUM> may analyze navigation map <NUM> to generate a path <NUM> that connects start and destination locations. In some instances, path <NUM> may be generated based on navigation parameters <NUM>, which may be generated at mobile machine <NUM> or received from an external computing system. In the example of <FIG>, navigation parameters <NUM> specify that mobile machine <NUM> is to generate path <NUM> such that path <NUM> only passes through ground positions with ground scores greater than or equal to <NUM>. As such, path <NUM> is generated such that it passes between the bench and tree as shown. Mobile machine <NUM> is then caused to follow path <NUM> until arriving at the destination location. While traveling along path <NUM>, mobile machine <NUM> may capture new sensor data and update navigation map <NUM> to reflect the newly captured sensor data. In some instances, path <NUM> may be modified while mobile machine <NUM> is traveling along path <NUM> in response to changes to navigation map <NUM> or navigation parameters <NUM>.

<FIG> illustrates an additional example of mobile machine <NUM> navigating between start and destination locations using navigation map <NUM>, in accordance with some embodiments of the present disclosure. In the example of <FIG>, navigation map <NUM> includes a set of sky scores (italicized and bold) and a set of ground scores for a set of ground positions. Each of the set of sky scores in navigation map <NUM> may indicate how accurate a calculated geospatial position using satellite data would be at a particular ground position. For example, the sky score for ground positions near objects that are large or have significant overhangs (and therefore could potentially obstruct LOS satellites) is equal to <NUM>, <NUM>, or <NUM> while the sky score for ground positions further away from these objects is equal to <NUM>, <NUM>, or <NUM>.

After forming navigation map <NUM>, the navigation system of mobile machine <NUM> may analyze navigation map <NUM> to generate a path <NUM> that connects start and destination locations. In the example of <FIG>, navigation parameters <NUM> specify that mobile machine <NUM> is to generate path <NUM> such that path <NUM> only passes through ground positions with sky scores greater than or equal to <NUM> and ground scores greater than or equal to <NUM>. As such, path <NUM> is generated such that it goes around the right side of the tree as shown. Mobile machine <NUM> is then caused to follow path <NUM> until arriving at the destination location. While traveling along path <NUM>, mobile machine <NUM> may capture new sensor data and update navigation map <NUM> (sky scores and/or ground scores) to reflect the newly captured sensor data. In some instances, path <NUM> may be modified while mobile machine <NUM> is traveling along path <NUM> in response to changes to navigation map <NUM> (sky scores and/or ground scores) or navigation parameters <NUM>.

<FIG> illustrates an additional example of mobile machine <NUM> navigating between start and destination locations using navigation map <NUM>, in accordance with some embodiments of the present disclosure. Similar to the example of <FIG>, in the example of <FIG>, navigation map <NUM> includes a set of sky scores (italicized and bold) and a set of ground scores for a set of ground positions. Navigation parameters <NUM> specify that mobile machine <NUM> is to generate path <NUM> such that path <NUM> only passes through ground positions with sky scores greater than or equal to <NUM> and ground scores greater than or equal to <NUM>. As such, path <NUM> is generated such that it goes around the left side of the bench as shown. Mobile machine <NUM> is then caused to follow path <NUM> until arriving at the destination location.

<FIG> illustrates an additional example of mobile machine <NUM> navigating between start and destination locations using navigation map <NUM>, in accordance with some embodiments of the present disclosure. While specific sky scores and ground scores are not shown, navigation map <NUM> in <FIG> may be similar to navigation map <NUM> shown in <FIG> or <FIG>. Navigation parameters <NUM> specify that mobile machine <NUM> is to generate path <NUM> such that path <NUM> only passes through ground positions with ground scores greater than or equal to <NUM>. Furthermore, navigation parameters <NUM> specify that, for the purposes of calculating the position of mobile machine <NUM>, only non-GNSS (non-satellite) positioning data is to be used for ground positions with sky scores less than or equal to <NUM> and only GNSS (satellite) data is to be used for ground positions with sky scores greater than or equal to <NUM>. In some instances, different zones may be created that modify how mobile machine <NUM> calculates its position as mobile machine <NUM> passes through the zones while traveling to the destination location.

In the example of <FIG>, mobile machine <NUM> is able to follow the shortest accessible path while properly handling satellite data. In some embodiments, various aspects of the examples described in <FIG> may be combined. For example, in a situation where finding the shortest accessible path is less important, such as the example of <FIG> in which path <NUM> is able to pass through ground positions with sky scores greater than or equal to <NUM> and ground scores greater than or equal to <NUM>, mobile machine <NUM> may use sky scores to both generate path <NUM> as well as to handle how satellite data and non-satellite positioning data are used for calculating the position of mobile machine <NUM>. For example, again in reference to the example of <FIG>, satellite data may exclusively be used to calculate the position of mobile machine <NUM> while at ground positions with sky scores equal to <NUM> while both satellite data and non-satellite positioning data may be used to calculate the position of mobile machine <NUM> while at ground positions with sky scores equal to <NUM>. Other possibilities are contemplated.

<FIG> illustrates an example block diagram of a mobile machine <NUM>, in accordance with some embodiments of the present disclosure. Mobile machine <NUM> may include various machine sensors <NUM>, actuators <NUM>, computing devices, and software/hardware modules for allowing autonomous or non-autonomous operation of mobile machine <NUM>. The components of mobile machine <NUM> may be communicatively coupled to each other via one or more wired and/or wireless connections.

Mobile machine <NUM> may include a control unit <NUM> that receives data from sensors and generates commands that are sent to the various actuators and output devices. In the illustrated example, control unit <NUM> receives sensor data <NUM> from machine sensors <NUM>, and generates control signal(s) <NUM> which are sent to actuator(s) <NUM>. Control unit <NUM> may include one or more processors and an associated memory. In some embodiments, control unit <NUM> may be communicatively coupled to an external computing system <NUM> located external to mobile machine <NUM>. External computing system <NUM> may send instructions, alerts, or other general information to control unit <NUM>. In some instances, external computing system <NUM> may provide a destination location and/or navigation parameters to mobile machine <NUM>.

In some embodiments, machine sensors <NUM> may include a GNSS receiver <NUM> that may be configured to receive satellite data <NUM> from one or more satellites. Satellite data <NUM> may include one or more GNSS signals from which a geospatial position of mobile machine <NUM> may be computed. In some embodiments, machine sensors <NUM> may include an imaging device <NUM> that may be configured to capture an upward-facing image <NUM>. Imaging device <NUM> may be at least partially oriented toward the one or more satellites.

In some embodiments, machine sensors <NUM> may include ground sensor(s) <NUM> that may be configured to capture ground data <NUM> that may be used to calculate a set of ground scores of the navigation map. Ground sensor(s) <NUM> may include cameras, depth sensors, acoustic sensors, radar, LiDAR, among other possibilities. In some embodiments, machine sensors <NUM> may include non-satellite positioning sensor(s) <NUM> that may be configured to capture positioning data <NUM> that may be used to calculate the position of mobile machine <NUM>. Non-satellite positioning sensor(s) <NUM> may include cameras, IMUs, or any type of sensor capable of calculating position that do not rely on satellite signals.

In some embodiments, machine sensors <NUM> may include orientation sensor(s) <NUM> that may be configured to capture an orientation <NUM> of imaging device <NUM> and/or mobile machine <NUM>. In some examples, orientation sensor(s) <NUM> may include one or more gyroscopes for detecting angular acceleration, angular rate and/or angular position, one or more accelerometers for detecting linear acceleration, linear velocity, and/or linear position, one or more inertial measurement units (IMUs) which may each include one or more accelerometers, one or more gyroscopes, and/or one or more magnetometers for detecting the above-listed types of data, among other possibilities.

Control unit <NUM> may include various controllers and modules to assist in the generation of control signal(s) <NUM>. Each of the controllers and modules may include dedicated hardware and/or may be performed using the main processor and/or memory of control unit <NUM>. For example, control unit <NUM> may include various self-driving or autonomous modules that may make navigation decisions based on sensor data <NUM>. In some embodiments, control unit <NUM> includes a navigation map generator <NUM> that generates a navigation map based on sensor data <NUM>. For example, navigation map generator <NUM> may generate the navigation map based on satellite data <NUM>, image <NUM>, and orientation <NUM>.

Control signal(s) <NUM> may include direct current (DC) or alternating current (AC) voltage signals, DC or AC current signals, and/or information-containing signals. An example of an information-containing signal may be controller area network (CAN) message that may be sent along a CAN bus or other communication medium. In some instances, control signal(s) <NUM> include a pneumatic or hydraulic pressure. Upon receiving control signal(s) <NUM>, actuator(s) <NUM> may be caused to move in a specified manner, such as by extending, retracting, rotating, lifting, or lowering by a specified amount. Actuator(s) <NUM> may use various forms of power to provide movement to the components of mobile machine <NUM>. For example, actuator(s) <NUM> may be electric, hydraulic, pneumatic, mechanical, or thermal, among other possibilities.

<FIG> illustrates an example method <NUM> of navigating a mobile machine, in accordance with some embodiments of the present disclosure. One or more steps of method <NUM> may be omitted during performance of method <NUM>, and steps of method <NUM> need not be performed in the order shown. One or more steps of method <NUM> may be performed by one or more processors. Method <NUM> may be implemented as a computer-readable medium or computer program product comprising instructions which, when the program is executed by one or more computers, cause the one or more computers to carry out the steps of method <NUM>.

At step <NUM>, sensor data (e.g., sensor data <NUM>) is captured using one or more machine sensors (e.g., machine sensors <NUM>) of a mobile machine (e.g., mobile machines <NUM>, <NUM>, <NUM>).

At step <NUM>, satellite data (e.g., satellite data <NUM>) is captured from one or more satellites (e.g., GNSS satellites <NUM>) using a GNSS receiver (e.g., GNSS receivers <NUM>, <NUM>). The one or more machine sensors may include the GNSS receiver. Capturing the satellite data may include receiving one or more satellite signals (e.g., wireless signals <NUM>) from the one or more satellites.

At step <NUM>, an image (e.g., images <NUM>, <NUM>, <NUM>) is captured using an imaging device (e.g., imaging devices <NUM>, <NUM>). The one or more machine sensors may include the imaging device. The imaging device may be at least partially oriented toward the one or more satellites. The image may be an upward-facing image. The imaging device may be a camera, a depth sensor, among other possibilities.

At step <NUM>, a set of sky scores are calculated for a set of ground positions surrounding the mobile machine based on the satellite data and the image. In some embodiments, each of the set of sky scores may be indicative of an accuracy of a potential (or actual) satellite-based position at the corresponding one of the set of ground positions. In various embodiments, each of the set of sky scores may be calculated using any computation that is mathematically equivalent, scaled or proportional in any way to the example embodiments, or otherwise has an algorithmically useful measure of the imaging device's clear LOS access to the sky. In some embodiments, performing step <NUM> may include performing one or both of steps <NUM> and <NUM>.

At step <NUM>, one of the set of sky scores is calculated for a current position of the set of ground positions. The current position may be the position of the mobile machine at the time that step <NUM> is performed. A method of calculating a sky score is described in reference to method <NUM> in <FIG>.

At step <NUM>, one of the set of sky scores is estimated for each of a plurality of surrounding positions of the set of ground positions. A method of calculating (or estimating) a sky score is described in reference to method <NUM> in <FIG>.

At step <NUM>, ground data (e.g., ground data <NUM>) is captured using one or more ground sensors (e.g., ground sensor(s) <NUM>) of the mobile machine. The one or more machine sensors may include the one or more ground sensors.

At step <NUM>, a set of ground scores are calculated for the set of ground positions. Each of the set of ground scores may be indicative of an accessibility of the corresponding one of the set of ground positions for the mobile machine.

At step <NUM>, a navigation map (e.g., navigation maps <NUM>, <NUM>) consisting of the set of sky scores and the set of ground scores is formed. The navigation map may be defined over a grid (e.g., the set of ground positions may be distributed over a grid) or over some other spatial distribution, such as over a set of evenly or unevenly spaced set of ground positions. In some embodiments, the set of sky scores may be defined over the same set of ground positions as the set of ground scores or over a different set of ground positions. In some embodiments, the navigation map may include one sky score and one ground score for each point (e.g., ground position) in a grid.

At step <NUM>, positioning data (e.g., positioning data <NUM>) is captured using non-satellite positioning sensors (e.g., non-satellite positioning sensor(s) <NUM>). The one or more machine sensors may include the non-satellite positioning sensors. The non-satellite positioning sensors may include cameras, IMUs, or any type of sensor capable of calculating position that do not rely on satellite signals.

At step <NUM>, a navigation of the mobile machine is modified using the set of sky scores. In some embodiments, the navigation of the mobile machine may be modified further based on the navigation map. In some embodiments, the navigation of the mobile machine may be modified further based on the set of ground scores. In some embodiments, the navigation of the mobile machine may be modified further based on the positioning data.

In some embodiments, modifying the navigation of the mobile machine may include performing any modification to control signals (e.g., control signals <NUM>) sent to actuators (e.g., actuators <NUM>) of the mobile machine based on the set of sky scores and/or the navigation map. In some embodiments, modifying the navigation of the mobile machine may include causing the mobile machine to move toward a higher score from the set of sky scores and away from a lower score from the set of sky scores. For example, the mobile machine may be caused to alter a planned path in order to pass through the higher score and avoid the lower score. In some embodiments, modifying the navigation of the mobile machine may include causing the mobile machine to adjust its positioning algorithm to ignore the satellite data and instead use the positioning data captured by non-satellite positioning sensors when the mobile machine is positioned at a ground position with a corresponding low sky score.

<FIG> illustrates an example method <NUM> of calculating a sky score for a ground position, in accordance with some embodiments of the present disclosure. One or more steps of method <NUM> may be omitted during performance of method <NUM>, and steps of method <NUM> need not be performed in the order shown. One or more steps of method <NUM> may be performed by one or more processors. Method <NUM> may be implemented as a computer-readable medium or computer program product comprising instructions which, when the program is executed by one or more computers, cause the one or more computers to carry out the steps of method <NUM>. One or more steps of method <NUM> may be used in conjunction with method <NUM>.

At step <NUM>, one or more satellite signals (e.g., wireless signals <NUM> or satellite data <NUM>) are received from one or more satellites (e.g., GNSS satellites <NUM>) using a GNSS receiver (e.g., GNSS receivers <NUM>, <NUM>) of a mobile machine (e.g., mobile machines <NUM>, <NUM>, <NUM>). Each of the one or more satellite signals may be received from one of the one or more satellites. The one or more satellite signals may be received via a GNSS antenna.

At step <NUM>, an image (e.g., images <NUM>, <NUM>, <NUM>) is captured using an imaging device (e.g., imaging devices <NUM>, <NUM>) of the mobile machine. The imaging device may be at least partially oriented toward the one or more satellites. The image may be an upward-facing image. The imaging device may be a camera, a depth sensor, among other possibilities.

At step <NUM>, the image is segmented into a plurality of regions (e.g., regions <NUM>) based on RF characteristics of objects in the image. Each region of the plurality of regions may be characterized by an extent to which the one or more satellite signals are obstructed by the objects within the region. In one example, the plurality of regions includes a first region having objects that provide little obstruction to satellite signals passing therethrough (e.g., clear sky, clouds), a second region having objects that provide some obstruction to satellite signals passing therethrough (e.g., vegetation, foliage), and a third region having objects that provide significant obstruction to satellite signals passing therethrough (e.g., buildings, mountains).

In some embodiments, the image may be segmented such that each pixel of the image is included in one of the plurality of regions. In some embodiments, certain portions of the image may not be included in any of the plurality of regions. As an example, the process that performs image segmentation may be unable to segment certain portions of the image due to, for example, artifacts in the image, unrecognizable objects in the image, among other possibilities. In some embodiments, the portions of the image that are unable to be segmented directly may be included in the closest region or may be included in a region for unrecognizable objects, among other possibilities.

At step <NUM>, an orientation (e.g., orientation <NUM>) of the image is determined. The orientation of the image may be directly related to (e.g., equal to) the orientation of the imaging device. In some embodiments, the orientation of the imaging device may first be determined and subsequently used to determine the orientation of the image. In some embodiments, the orientation of the image may be determined using satellite data related to the one or more satellite signals. In some embodiments, the orientation of the image may be determined using the image itself. In some embodiments, the orientation of the image may be captured using an orientation sensor (e.g., orientation sensor <NUM>). The orientation sensor may be mounted to the imaging device and/or the mobile machine such that the rotational movement of the orientation sensor is indicative of the rotational movement of the imaging device. The orientation sensor may be an IMU, a gyroscope, a tilt sensor, among other possibilities.

At step <NUM>, the one or more satellites are projected onto the image based on the orientation of the image such that a corresponding region is identified for each of the one or more satellites. In some embodiments, a pixel location within the image is first determined for each of the one or more satellites. The pixel location may be the location within the image at which an orbital position of each of the one or more satellites is aligned or found. The orbital position of each of the one or more satellites may be determined by analyzing satellite data or be obtained through other means (e.g., the orbital positions may be obtained over the internet). In some embodiments, a position of the image may be computed prior to performing step <NUM> so that the pose of the image may be known. Upon determining the pose, the one or more satellites may be projected onto the image based on both the position and orientation of the image.

At step <NUM>, the sky score is calculated for the ground position based on the projected satellites. If the mobile machine is currently positioned at the ground position, the sky score may be calculated by a formulation that, in some examples, sums the quantity of satellites in the image and weights each satellite in accordance with the corresponding region that was identified for the satellite. For example, in one implementation, the sky score may be calculated by summing the quantity of satellites projected onto the image within a first region (and weighting each with a first weight, such as <NUM>), the quantity of satellites projected onto the image within a second region with a second weighting value (and weighting each with a second weight, such as <NUM>), and the quantity of satellites projected onto the image within a third region with a third weighting value (and weighting each with a third weight, such as <NUM>).

If the mobile machine is not currently positioned at the ground position, the sky score is estimated by modeling the environment surrounding the mobile machine and estimating above-described formulation for the ground position. In some instances, the environment may be modeled using multiple images by, for example, estimating the height of objects based on the distance traveled by the mobile machine between the images being captured and the movement of the objects within the images (e.g., number of pixels moved).

<FIG> illustrate an example trilateration technique performed by a GNSS receiver operating within a GNSS to generate a position estimate, in accordance with some embodiments of the present disclosure. <FIG> shows a first scenario in which a GNSS receiver receives GNSS signals from a first satellite <NUM>-<NUM> and generates a distance estimate (e.g., <NUM>,<NUM>) for that satellite. This informs the GNSS receiver that it is located somewhere on the surface of a (first) sphere with a radius of <NUM>,<NUM>, centered on first satellite <NUM>-<NUM>. <FIG> shows a second scenario in which the GNSS receiver receives GNSS signals from a second satellite <NUM>-<NUM> and generates a distance estimate (e.g., <NUM>,<NUM>) for the additional satellite. This informs the GNSS receiver that it is also located somewhere on the surface of a (second) sphere with a radius of <NUM>,<NUM>, centered on second satellite <NUM>-<NUM>. This limits the possible locations to somewhere on the region <NUM> where the first sphere and second sphere intersect.

<FIG> shows a third scenario in which the GNSS receiver receives GNSS signals from a third satellite <NUM>-<NUM> and generates a distance estimate (e.g., <NUM>,<NUM>) for the additional satellite. This informs the GNSS receiver that it is also located somewhere on the surface of a (third) sphere with a radius of <NUM>,<NUM>, centered on third satellite <NUM>-<NUM>. This limits the possible locations to two points <NUM> where the first sphere, the second sphere, and the third sphere intersect. <FIG> shows a fourth scenario in which the GNSS receiver receives GNSS signals from a fourth satellite <NUM>-<NUM>. Fourth satellite <NUM>-<NUM> can be used to resolve which of points <NUM> is a correct point <NUM> (by generating a fourth sphere) and/or to synchronize the receiver's clock with the satellites' time.

<FIG> illustrates a simplified computer system <NUM>, in accordance with some embodiments of the present disclosure. <FIG> provides a schematic illustration of one embodiment of computer system <NUM> that can perform some or all of the steps of the methods provided by various embodiments. It should be noted that <FIG> is meant only to provide a generalized illustration of various components, any or all of which may be utilized as appropriate. <FIG>, therefore, broadly illustrates how individual system elements may be implemented in a relatively separated or more integrated manner.

Computer system <NUM> is shown comprising hardware elements that can be electrically coupled via a bus <NUM>, or may otherwise be in communication, as appropriate. The hardware elements may include one or more processors <NUM>, including without limitation one or more general-purpose processors and/or one or more special-purpose processors such as digital signal processing chips, graphics acceleration processors, and/or the like; one or more input devices <NUM>, which can include, without limitation a mouse, a keyboard, a camera, and/or the like; and one or more output devices <NUM>, which can include, without limitation a display device, a printer, and/or the like.

Computer system <NUM> may further include and/or be in communication with one or more non-transitory storage devices <NUM>, which can comprise, without limitation, local and/or network accessible storage, and/or can include, without limitation, a disk drive, a drive array, an optical storage device, a solid-state storage device, such as a random access memory ("RAM"), and/or a read-only memory ("ROM"), which can be programmable, flash-updateable, and/or the like. Such storage devices may be configured to implement any appropriate data stores, including without limitation, various file systems, database structures, and/or the like.

Computer system <NUM> might also include a communications subsystem <NUM>, which can include, without limitation a modem, a network card (wireless or wired), an infrared communication device, a wireless communication device, and/or a chipset such as a Bluetooth® device, an <NUM> device, a Wi-Fi device, a WiMax device, cellular communication facilities, etc., and/or the like. The communications subsystem <NUM> may include one or more input and/or output communication interfaces to permit data to be exchanged with a network such as the network described below to name one example, to other computer systems, and/or any other devices described herein. Depending on the desired functionality and/or other implementation concerns, a portable electronic device or similar device may communicate image and/or other information via the communications subsystem <NUM>. In other embodiments, a portable electronic device, e.g. the first electronic device, may be incorporated into computer system <NUM>, e.g., an electronic device as an input device <NUM>. In some embodiments, computer system <NUM> will further comprise a working memory <NUM>, which can include a RAM or ROM device, as described above.

Computer system <NUM> also can include software elements, shown as being currently located within the working memory <NUM>, including an operating system <NUM>, device drivers, executable libraries, and/or other code, such as one or more application programs <NUM>, which may comprise computer programs provided by various embodiments, and/or may be designed to implement methods, and/or configure systems, provided by other embodiments, as described herein. Merely by way of example, one or more procedures described with respect to the methods discussed above can be implemented as code and/or instructions executable by a computer and/or a processor within a computer; in an aspect, then, such code and/or instructions can be used to configure and/or adapt a general purpose computer or other device to perform one or more operations in accordance with the described methods.

A set of these instructions and/or code may be stored on a non-transitory computer-readable storage medium, such as the storage device(s) <NUM> described above. In some cases, the storage medium might be incorporated within a computer system, such as computer system <NUM>. In other embodiments, the storage medium might be separate from a computer system e.g., a removable medium, such as a compact disc, and/or provided in an installation package, such that the storage medium can be used to program, configure, and/or adapt a general purpose computer with the instructions/code stored thereon. These instructions might take the form of executable code, which is executable by computer system <NUM> and/or might take the form of source and/or installable code, which, upon compilation and/or installation on computer system <NUM> e.g., using any of a variety of generally available compilers, installation programs, compression/decompression utilities, etc., then takes the form of executable code.

For example, customized hardware might also be used, and/or particular elements might be implemented in hardware or software including portable software, such as applets, etc., or both.

As mentioned above, in one aspect, some embodiments may employ a computer system such as computer system <NUM> to perform methods in accordance with various embodiments of the technology. According to a set of embodiments, some or all of the procedures of such methods are performed by computer system <NUM> in response to processor <NUM> executing one or more sequences of one or more instructions, which might be incorporated into the operating system <NUM> and/or other code, such as an application program <NUM>, contained in the working memory <NUM>. Such instructions may be read into the working memory <NUM> from another computer-readable medium, such as one or more of the storage device(s) <NUM>. Merely by way of example, execution of the sequences of instructions contained in the working memory <NUM> might cause the processor(s) <NUM> to perform one or more procedures of the methods described herein. Additionally or alternatively, portions of the methods described herein may be executed through specialized hardware.

The terms "machine-readable medium" and "computer-readable medium," as used herein, refer to any medium that participates in providing data that causes a machine to operate in a specific fashion. In an embodiment implemented using computer system <NUM>, various computer-readable media might be involved in providing instructions/code to processor(s) <NUM> for execution and/or might be used to store and/or carry such instructions/code. In many implementations, a computer-readable medium is a physical and/or tangible storage medium. Such a medium may take the form of a non-volatile media or volatile media. Non-volatile media include, for example, optical and/or magnetic disks, such as the storage device(s) <NUM>. Volatile media include, without limitation, dynamic memory, such as the working memory <NUM>.

Common forms of physical and/or tangible computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CD-ROM, any other optical medium, punchcards, papertape, any other physical medium with patterns of holes, a RAM, a PROM, EPROM, a FLASH-EPROM, any other memory chip or cartridge, or any other medium from which a computer can read instructions and/or code.

Various forms of computer-readable media may be involved in carrying one or more sequences of one or more instructions to the processor(s) <NUM> for execution. Merely by way of example, the instructions may initially be carried on a magnetic disk and/or optical disc of a remote computer. A remote computer might load the instructions into its dynamic memory and send the instructions as signals over a transmission medium to be received and/or executed by computer system <NUM>.

Specific details are given in the description to provide a thorough understanding of exemplary configurations including implementations. However, configurations may be practiced without these specific details. For example, well-known circuits, processes, algorithms, structures, and techniques have been shown without unnecessary detail in order to avoid obscuring the configurations. This description provides example configurations only, and does not limit the scope, applicability, or configurations of the claims. Rather, the preceding description of the configurations will provide those skilled in the art with an enabling description for implementing described techniques. Various changes may be made in the function and arrangement of elements without departing from the scope of the disclosure.

Claim 1:
A method comprising:
capturing sensor data using one or more machine sensors of a mobile machine, wherein capturing the sensor data includes:
capturing (<NUM>) satellite data from one or more satellites; and
capturing (<NUM>) an image using an imaging device that is at least partially oriented toward the one or more satellites;
segmenting (<NUM>) the image into a plurality of regions based on predicted radio frequency, RF, characteristics of objects in the image;
projecting (<NUM>) the orbital positions of the one or more satellites onto the image;
calculating (<NUM>) a set of sky scores for a set of ground positions surrounding the mobile machine based on the satellite data and the region of the segmented image onto which each of the one or more satellites is projected,
wherein the set of sky scores are estimated by modeling an environment surrounding the mobile machine
wherein each of the set of sky scores is indicative of an accuracy of a satellite-based position at one of the set of ground positions; and
modifying a navigation of the mobile machine using the set of sky scores.