We consider the problem of planning paths on graphs with some edges whose traversability is uncertain; for each uncertain edge, we are given a probability of being traversable (e.g., by a learned classifier). We categorize different interpretations of the problem that are meaningful for mobile robots navigating partially-known environments, each of which yields a different formalization; we then focus on the case in which the true traversability of an edge is revealed only when the agent visits one of its endpoints (Canadian Traveller Problem). In this context, we design a large simulation campaign on synthetic and real-world maps to study the impact of two different factors: the planning strategy, and the amount of uncertainty (which could depend on the quality of the classifier producing traversability estimates).