CHiPS: composing hierarchical Pareto solutions for scalable planning in multi-objective MDPs

Conference item

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.

Authors: Hentges, C; Budd, M; Platt, A; Lacerda, B; Parker, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: IEEE
• Host title: 2025 European Conference on Mobile Robots (ECMR)
• Pages: 1-6
• Publication date: 2025-09-18
• Event title: 12th European Conference on Mobile Robots (ECMR 2025)
• Event location: Padua, Italy
• Event website: https://ecmr2025.dei.unipd.it/
• Event start date: 2025-09-02
• Event end date: 2025-09-05
• DOI: 10.1109/ecmr65884.2025.11163228
• EISSN: 2767-8733
• ISSN: 2639-7919
• EISBN: 9798331527051
• ISBN: 9798331527068
• Language: English
• Keywords: uncertainty; navigation; scalability; Markov decision processes; Europe; planning; mobile robots