We consider planning problems where a robot must visit a large set of locations to complete a task at each one. Our focus is problems where the difficulty of each task, and thus its duration, can be predicted, but not fully known in advance. We propose a general Markov decision process (MDP) model for difficulty-aware problems, and propose variants on this model which allow adaptation to different robotics domains. Due to the intractability of the general problem, we propose simplifications to allow planning in large domains, the key being constraining navigation using a solution to the travelling salesperson problem (TSP). We build a set of variant models for two domains with different characteristics: UV disinfection, and cleaning, evaluating them on maps generated from real-world environments. We evaluate the effect of model variants and simplifications on performance, and show that our models outperform a rule-based baseline.