Q-CP: Learning Action Values for Cooperative Planning

Francesco Riccio, Roberto Capobianco, Daniele NardiICRA 2018 · OpenReview

Abstract

Research on multi-robot systems has demonstrated promising results in manifold applications and domains. Still, efficiently learning an effective robot behaviors is very difficult, due to unstructured scenarios, high uncertainties, and large state dimensionality (e.g. hyper-redundant and groups of robot). To alleviate this problem, we present Q-CP a cooperative model-based reinforcement learning algorithm, which exploits action values to both (1) guide the exploration of the state space and (2) generate effective policies. Specifically, we exploit Q-learning to attack the curse-of-dimensionality in the iterations of a Monte-Carlo Tree Search. We implement and evaluate Q-CP on different stochastic cooperative (general-sum) games: (1) a simple cooperative navigation problem among 3 robots, (2) a cooperation scenario between a pair of KUKA YouBots performing hand-overs, and (3) a coordination task between two mobile robots entering a door. The obtained results show the effectiveness of Q-CP in the chosen applications, where action values drive the exploration and reduce the computational demand of the planning process while achieving good performance.

Introduction

Multi-robot coordination faces a significant "curse of dimensionality." As the number of agents increases, the state-action space grows exponentially, making traditional planning and reinforcement learning (RL) computationally prohibitive. Existing approaches often fall into two camps: decision-theoretic planning (like Monte-Carlo Tree Search), which excels at look-ahead but lacks generalization, and RL (like Q-learning), which generalizes well but often requires massive data and struggles with long-term consequences without extensive exploration.

Q-CP (Q-value based Cooperative Planning) bridges this gap for cooperative general-sum stochastic games. By integrating Q-learning into the iterations of a Monte-Carlo Tree Search (MCTS), Q-CP leverages learned value functions to prune the search space, focusing computational resources on the most promising actions.

Methodology

The core of Q-CP is the integration of function approximation into the Upper Confidence Tree (UCT) search process.

Function Approximation via GMMs

Instead of deep neural networks, Q-CP utilizes Gaussian Mixture Models (GMMs) for regression on action values ($Q$-values). GMMs provide a non-parametric way to capture complex value distributions while offering a built-in measure of uncertainty ($\sigma^2$). This uncertainty is critical for balancing exploration and exploitation.

Admissible Action Selection

A key innovation is the "admissibility" criterion. In standard UCT, all possible actions at a node might be explored. Q-CP uses the learned $Q$-function to identify a subset of "admissible" actions—those predicted to be near-optimal or those with high uncertainty. This effectively "crops" the search tree, ignoring obviously suboptimal strategies early in the planning process.

Cooperative hand-over task between two KUKA YouBots.

Experimental Evaluation

The researchers evaluated Q-CP in three simulated environments using the V-REP simulator: a cooperative navigation task with three robots, a coordination task for door passing, and a complex hand-over task involving two KUKA YouBots. The latter, pictured above, involves a continuous state space and requires precise coordination between mobile platforms and 5DOF arms.

Key Results

Q-CP was compared against vanilla-UCT, random-UCT, and TD-search. The results demonstrate that Q-CP achieves high performance with significantly lower computational demand.

Comparison of average cumulative rewards and number of explored states across iterations.
  • Efficiency: In the "Door Passing" scenario, Q-CP reduced the number of explored states by approximately 60% compared to vanilla UCT while maintaining comparable rewards.
  • Generalization: By relating similar states through the GMM, Q-CP plans more effectively in novel but similar parts of the environment, a capability lacking in vanilla MCTS.
  • Scalability: While methods like TD-search struggled as dimensionality increased (e.g., the YouBot arm task), Q-CP remained robust, reaching high reward plateaus faster than baseline methods.

Conclusion and Future Work

Q-CP demonstrates that action values can effectively guide exploration in complex multi-robot tasks. Future work includes moving toward fully online planning to reduce reliance on simulation calls and exploring Deep Neural Networks for even higher-dimensional "hyper-redundant" robotic systems. Additionally, addressing the non-i.i.d. nature of data collected during tree searches remains a priority for improving learning stability.

Summary updated

Abstract

Research on multi-robot systems has demonstrated promising results in manifold applications and domains. Still, efficiently learning an effective robot behaviors is very difficult, due to unstructured scenarios, high uncertainties, and large state dimensionality (e.g. hyper-redundant and groups of robot). To alleviate this problem, we present Q-CP a cooperative model-based reinforcement learning algorithm, which exploits action values to both (1) guide the exploration of the state space and (2) generate effective policies. Specifically, we exploit Q-learning to attack the curse-of-dimensionality in the iterations of a Monte-Carlo Tree Search. We implement and evaluate Q-CP on different stochastic cooperative (general-sum) games: (1) a simple cooperative navigation problem among 3 robots, (2) a cooperation scenario between a pair of KUKA YouBots performing hand-overs, and (3) a coordination task between two mobile robots entering a door. The obtained results show the effectiveness of Q-CP in the chosen applications, where action values drive the exploration and reduce the computational demand of the planning process while achieving good performance.
BibTeX
@inproceedings{riccio2018q,
  author = {Francesco Riccio and Roberto Capobianco and Daniele Nardi},
  title = {{Q-CP: Learning Action Values for Cooperative Planning}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2018},
  url = {https://openreview.net/forum?id=RE8G0tGTRo},
}
Figure