1. A method executed by a processor of a computing device, the method comprising: receiving a computer-implemented graph that comprises nodes and edges, the computer-implemented graph representative of a region over which a machine is able to travel, the nodes representative of respective locations in the region, the edges representative of travel segments between locations, wherein each edge in the edges connects a respective pair of nodes in the nodes, each node in the nodes connected to at least one other node by a respective edge in the edges, the edges have respective distributions over costs assigned thereto, and the respective costs have a statistical relationship therebetween; receiving data from a sensor, the data being about a travel segment in the travel segments; responsive to receiving the data, updating the respective distributions over the costs of the edges in the computer-implemented graph based upon the data and the statistical relationship; identifying a particular travel segment in the travel segments over which the machine is to travel, the identifying based upon the updating of the respective distributions over the costs of the edges and a destination location of the machine; and responsive to identifying the particular travel segment, directing the machine to travel along the particular travel segment in the travel segments, wherein directing the machine to travel along the particular travel segment comprises outputting a signal that causes the machine to travel along the particular travel segment in the travel segments.