Incremental Policy Generation for Finite-Horizon DEC-POMDPs

By Chris Amato, Jilles Steeve Dibangoye, Shlomo Zilberstein. 2009

81 citations recorded by the source corpus.

Solving multiagent planning problems modeled as DEC-POMDPs is an important challenge. These models are often solved by using dynamic programming, but the high resource usage of current approaches results in limited scalability. To improve the efficiency of dynamic programming algorithms, we propose a new backup algorithm that is based on a reachability analysis of the state space. This method, which we call incremental policy generation, can be used to produce an optimal solution for any possible initial state or further scalability can be achieved by making use of a known start state. When incorporated into the optimal dynamic programming algorithm, our experiments show that planning horizon can be increased due to a marked reduction in resource consumption. This approach also fits nicely with approximate dynamic programming algorithms. To demonstrate this, we incorporate it into the state-of-the-art PBIP algorithm and show significant performance gains. The results suggest that the performance of other dynamic programming algorithms for DEC-POMDPs could be similarly improved by integrating the incremental policy generation approach.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability (2017, methodology): “Performance is evaluated on both multi-agent single-target (MAST) and multi-agent multi-target (MAMT) capture domains, variations of the existing meeting-in-a-grid Dec-POMDP benchmark (Amato et al., 2009).”
Multi-agent reinforcement learning as a rehearsal for decentralized planning (2016, neutral): “Other scalable approximate methods for Dec-POMDP solution exist (e.g. PBIP-IPG [1]); however, we find Dec-RSPI to be a more appropriate target for comparison because it, like RLaR, does not assume full a priori knowledge of the model.”
Decentralized Likelihood Quantile Networks for Improving Performance in Deep Multi-Agent Reinforcement Learning (2018, methodology): “We use a partially observable meeting-in-a-grid domain (Amato et al., 2009) to be consistent with previous work (Omidshaﬁei et al., 2017).”
Likelihood Quantile Networks for Coordinating Multi-Agent Reinforcement Learning (2018, methodology): “We first conduct experiments on a standard partially observable meeting-in-a-grid domain [1] to be consistent with previous work [26].”
Rollout Sampling Policy Iteration for Decentralized POMDPs (2010, methodology): “[1], which has 81 states, 5 actions and 9 observations per robot.”
Decentralized POMDPs (2012, methodology): “To reduce the burden of this complexity, many papers have proposed new methods for performing this point-based backup operation (Seuken and Zilberstein, 2007a; Carlin and Zilberstein, 2008; Dibangoye et al, 2009; Amato et al, 2009; Wu et al, 2010a).”
Planning with macro-actions in decentralized POMDPs (2014, background): “Value Time (s) h = 100 h = 200 h = 100 h = 200 O-MBDP(3) 94.4 194.4 133 517 MBDP(3) 92.1 193.4 3084 13875 TBDP 92.8 192.1 427 1372 Table 1: Times and values for larger horizons on the meeting in a grid benchmark. generation (MBDP-IPG) [2], rollout sampling policy iteration (DecRSPI) [33] and trial-b”
Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion (2011, methodology): “The method proposed in [2] effectively focuses on state space reachability in problem structure.”