In the aerial supply delivery problem, an un-manned aircraft needs to deliver supplies as close as possible to the desired goal location. This involves choosing and landing at a landing site that is closest to or most accessible from the desired goal location. The problem is complicated by the fact that the status of candidate landing sites is unknown before the mission begins, and instead the aircraft needs to compute a sequence according to which it flies and senses the candidate landing sites in order to land as quickly as possible. The problem of computing this sequence corresponds to planning under uncertainty about environment. In this paper, we show how it can be solved efficiently via a recently developed probabilistic planning framework, called Probabilistic Planning with Clear Preferences (PPCP). We show that the problem satisfies the Clear Preferences assumption required by PPCP,and therefore all the theoretical guarantees continue to hold. The experimental results in simulation show that our approachcan solve large-scale problems in real-time while experiments on a physical quad-rotor provide proof of concept.