Abstract. We present a hierarchical planning methodology for approximating Pareto-optimal policies in Multi-Objective Markov Decision Process (MOMDP) models. These models describe missions in which a mobile robot must navigate an environment and perform actions at specific locations. Our approach relies on clustering the state space of the full MOMDP into hierarchical subproblem MOMDPs. We then build the set of Pareto-optimal policies for these sub-problem MOMDPs, and treat them as macro-actions in a high-level MOMDP which selects the policy to use for each of the sub-problems, as well as the order in which to address them. Our bottom-up approach synthesises approximations of Pareto-optimal policies for large problems while providing precise performance guarantees. We empirically evaluate our method, showing it achieves substantial scalability gains over a non-hierarchical approach while preserving high-quality solutions.