Disclosed are techniques for navigating a mobile machine, such as an autonomous robot, in an environment that includes objects that may block, reflect, or distort satellite signals to be used for positioning. Satellite data may be captured from one or more satellites. An image may be captured using an imaging device that is at least partially oriented toward the one or more satellites. A set of sky scores may be calculated for a set of ground positions surrounding the mobile machine based on the satellite data and the image. Each of the set of sky scores may be indicative of an accuracy of a satellite-based position at one of the set of ground positions. The mobile machine's navigation may be modified using the set of sky scores.