TL;DR
This paper introduces PSMBDP, a novel planning algorithm for decentralized partially observable Markov decision processes (Dec-POMDPs). PSMBDP improves upon existing methods by using a heuristic distribution over agent beliefs to select policy trees, leading to higher quality solutions and better scalability for complex problems.
What Problem Does This Paper Address?
Coordinating multiple intelligent agents in uncertain environments is a significant challenge. Dec-POMDPs provide a powerful framework for modeling such scenarios, but finding optimal policies is computationally intractable due to the exponential growth of state and observation spaces. Existing approaches like Memory Bounded Dynamic Programming (MBDP) and Point Based Incremental Pruning (PBIP) attempt to mitigate this by bounding the number of policies considered. However, these methods often rely on heuristics that don't fully leverage the probabilistic nature of agent beliefs, potentially leading to suboptimal solutions or limitations in handling problems with many observations. This paper addresses the need for a more effective way to select policies in Dec-POMDPs that better accounts for the distribution of agent beliefs, aiming for improved solution quality and scalability.
Methods
The core contribution of this paper is the PSMBDP (Policy Search Memory Bounded Dynamic Programming) algorithm. PSMBDP builds upon existing memory-bounded dynamic programming techniques but introduces a novel optimization criterion. Instead of selecting policies based on individual belief points (as in MBDP), PSMBDP considers a heuristic probability distribution over beliefs at each planning step. This distribution is approximated using Monte-Carlo sampling.
The algorithm's key innovation lies in how it selects a bounded set of policy trees. It formulates this selection as a combinatorial optimization problem that aims to maximize the expected reward across the sampled belief distribution. This is achieved through a two-phase dynamic programming operator:
- Exhaustive Backup: This phase generates all possible policy trees, similar to standard DP.
- Pruning with Incremental Greedy Optimization: This is where PSMBDP differs significantly. It uses the heuristic belief distribution to guide the selection of the best policy trees. The paper proposes a greedy approach where it first selects a joint policy that maximizes the expected reward over the belief distribution. Then, it iteratively adds local policy trees for individual agents, optimizing a criterion that considers the impact of each local tree on the overall expected reward. This greedy selection is implemented using a branch-and-bound search, which implicitly enumerates policy trees rather than exhaustively generating them, improving scalability.
Datasets
The paper evaluates PSMBDP on several benchmark problems:
- Dec-Tiger: A standard benchmark for decentralized POMDPs.
- Firefighters: A problem involving multiple agents coordinating to extinguish fires.
- Modified Firefighters: An extension of the Firefighters problem with a higher number of observations.
- Cooperative Box Pushing: A problem designed to test algorithms' ability to handle a large number of observations.
The authors do not introduce new datasets but use existing, well-established benchmarks in the field.
Key Insights and Ideas
- Belief Distribution is Key: The paper argues that considering the distribution of agent beliefs, rather than just individual points, is crucial for selecting high-quality policies in Dec-POMDPs. This allows the algorithm to make more informed decisions that perform well across a range of likely future states.
- Combinatorial Optimization for Policy Selection: Framing the selection of a bounded set of policy trees as a combinatorial optimization problem, guided by the belief distribution, is a powerful way to improve solution quality.
- Greedy Incremental Approach: The proposed greedy strategy for selecting local policy trees, optimized using branch-and-bound, offers a practical way to solve the complex optimization problem and improve scalability.
- Scalability with Observations: By focusing on belief distributions and using branch-and-bound for policy selection, PSMBDP shows promise in handling problems with a higher number of observations, a common bottleneck in existing methods.
Key Results
PSMBDP consistently outperforms existing state-of-the-art algorithms like MBDP and PBIP in terms of solution quality (higher Average Expected Value - AEV) across several benchmark problems.
- Dec-Tiger: PSMBDP achieved significantly higher AEV (166.27) compared to MBDP (91.59) and PBIP (88.33) with a comparable number of policy trees.
- Firefighting: PSMBDP found solutions of better quality than MBDP.
- Modified Firefighting: PSMBDP achieved better results than PBIP, especially in a scenario with more observations.
- Cooperative Box Pushing: PSMBDP found slightly better solutions than PBIP, even when PBIP times out on longer horizons.
While PSMBDP can be computationally more intensive than simpler heuristics, its improved solution quality often justifies the increased computation time, especially for more complex problems.
Limitations and Future Work
- Heuristic Dependency: The performance of PSMBDP relies on the quality of the heuristic policy used to generate the belief distribution. The paper notes that using a POMDP belief prior as a heuristic did not yield good results, highlighting the importance of problem-specific heuristics.
- Greedy Optimization: The current implementation uses a greedy approach for policy selection. The authors suggest that using better optimization methods for the combinatorial problem could lead to even better solutions.
- Scalability with Observations: While PSMBDP shows improvement, the underlying exhaustive backup phase can still be exponential with the number of observations. The branch-and-bound search helps mitigate this in practice, but theoretical guarantees for very large observation spaces are not fully established.
- Future Work: The authors suggest exploring better optimization methods for the policy selection criterion and investigating more sophisticated ways to handle decentralized beliefs across multiple agents.
Summary updated