# Decoupled Monte Carlo Tree Search for Cooperative Multi-Agent Planning
## 1 Introduction  
Cooperative multi-agent planning involves coordinating the actions of multiple agents with a common objective and a willingness to work together towards a shared goal. While this type of planning can be less complex than non-cooperative planning, where agents may have conflicting goals or limited communication, it still requires careful coordination and consideration of the actions and capabilities of each agent. The number of possible combinations of actions that each agent can take can still grow exponentially with the number of agents. In addition, the environment in which the agents are operating may be dynamic and subject to change, requiring the plan to be flexible and adaptable. All these challenges of cooperative multi-agent planning render the problem intractable for most interesting problems, such as warehouse commissioning. In a warehouse setting, there may be multiple agents with different capabilities and resources, working in a dynamic environment with constantly changing demands and constraints. Coordinating the actions of these agents to efficiently complete tasks can be a complex and computationally intensive task. Traditional optimization methods may not scale well to these types of problems, and even with advanced algorithms, finding an optimal solution may be impractical, due to the time and computational resources required. As a result, finding effective approaches to cooperative multi-agent planning in warehouse commissioning, and other similar problems, is an active area of research. In this paper, we aimed to improve the scalability of cooperative multi-agent planning using online planning. Online planning involves making decisions and taking actions in real-time, as new information becomes available, rather than solving the problem in advance. This can be particularly useful in dynamic environments, where the problem may change rapidly, or in problems with large state spaces, where the computational cost of solving the problem in advance may be prohibitive. Monte Carlo Tree Search (MCTS) is one of the well-known online planning algorithms for complex problems. MCTS does not require a full model of the process. Instead, a black-box simulator, the definition of state, and action space is enough for MCTS. The MCTS algorithm plans over the joint actions of agents. The joint action set is constructed as the Cartesian product of the actions of agents. The planning algorithm calculates a single joint action for the given state. Agents execute the assigned actions independently. Although this approach works well, it creates an exponential increase in the state and action space of the problem. To reduce this exponential increase, we propose using decoupled planning. When the MCTS algorithm is used as a planning algorithm, we call it decoupled MCTS. In decoupled MCTS, every agent plans independently, but the same joint reward of the simulation is used. This approach results in a linear increase in state and action space but suffers from local optimum results [1]. In our experiments, we showed that this approach achieved reasonable performance, compared to the baseline methods such as MCTS over joint actions. When decoupled MCTS uses deterministic action selection policy in cooperative problems, the action synchronization problem occurs. This is due to the propagation of the same reward value for each agent. Although decoupled MCTS is widely used in regard to general game-playing problems [2; 3; 4; 5; 6; 7], they do not report such a problem, even for cooperative games. In cooperative problems, each decoupled agent chooses an individual action, then, these actions are combined and executed for the problem and, finally, a reward is taken. This reward updates all agents' actions, but these updated actions constitute only one of the combinations of all agents' actions. This combination has the same statistics. If a deterministic action selection policy is used, the actions of that combination are chosen together since they have the same statistics.