Planning for large-scale multiagent problems via hierarchical decomposition with applications to UAV health management

Yu Fan Chen, N. Kemal Ure, Girish Chowdhary, Jonathan P. How, John Vian

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

14 Citations (Scopus)


This paper introduces a novel hierarchical decomposition approach for solving Multiagent Markov Decision Processes (MMDPs) by exploiting coupling relationships in the reward function. MMDP is a natural framework for solving stochastic multi-stage multiagent decision-making problems, such as optimizing mission performance of Unmanned Aerial Vehicles (UAVs) with stochastic health dynamics. However, computing the optimal solutions is often intractable because the state-action spaces scale exponentially with the number of agents. Approximate solution techniques do exist, but they typically rely on extensive domain knowledge. This paper presents the Hierarchically Decomposed MMDP (HD-MMDP) algorithm, which autonomously identifies different degrees of coupling in the reward function and decomposes the MMDP into a hierarchy of smaller MDPs that can be solved separately. Solutions to the smaller MDPs are embedded in an autonomously constructed tree structure to generate an approximate solution to the original problem. Simulation results show HD-MMDP obtains more cumulative reward than that of the existing algorithm for a ten-agent Persistent Search and Track (PST) mission, which is a cooperative multi-UAV mission with more than 1019 states, stochastic fuel consumption model, and health progression model.

Original languageEnglish
Title of host publication2014 American Control Conference, ACC 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages7
ISBN (Print)9781479932726
Publication statusPublished - 2014
Externally publishedYes
Event2014 American Control Conference, ACC 2014 - Portland, OR, United States
Duration: 4 Jun 20146 Jun 2014

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619


Conference2014 American Control Conference, ACC 2014
Country/TerritoryUnited States
CityPortland, OR


  • Fault-tolerant systems
  • Markov processes
  • Stochastic systems


Dive into the research topics of 'Planning for large-scale multiagent problems via hierarchical decomposition with applications to UAV health management'. Together they form a unique fingerprint.

Cite this