juliapomdp/factoredvaluemcts.jl

Scalable MCTS for team scenarios

FactoredValueMCTS

This package implements the Monte Carlo Tree Search (MCTS) planning algorithm for Multi-Agent MDPs. The algorithm factorizes the true action value function, based on the locality of interactions between agents that is encoded with a Coordination Graph. We implement two schemes for coordinating the actions for the team of agents during the MCTS computations. The first is the iterative message-passing MaxPlus, while the second is the exact Variable Elimination. We thus get two different Factored Value MCTS algorithms, FV-MCTS-MaxPlus and FV-MCTS-VarEl respectively.

The full FV-MCTS-MaxPlus algorithm is described in our AAMAS 2021 paper Scalable Anytime Planning for Multi-Agent MDPs (Arxiv). The FV-MCTS-Varel is based on the Factored Statistics algorithm from the AAAI 2015 paper Scalable Planning and Learning from Multi-Agent POMDPs (Extended Version) applied to Multi-Agent MDPs rather than POMDPs. We use the latter as a baseline and show how the former outperforms it on two distinct simulated domains.

To use our solver, the domain must implement the interface from MultiAgentPOMDPs.jl. For examples, please see MultiAgentSysAdmin and MultiUAVDelivery, which are the two domains from our AAMAS 2021 paper. Experiments from the paper are available at https://github.com/rejuvyesh/FVMCTS_experiments.

Installation

using Pkg
Pkg.add("FactoredValueMCTS")

Citation

@inproceedings{choudhury2021scalable,
    title={Scalable Anytime Planning for Multi-Agent {MDP}s},
    author={Shushman Choudhury and Jayesh K Gupta and Peter Morales and Mykel J Kochenderfer},
    booktitle={International Conference on Autonomous Agents and MultiAgent Systems},
    year={2021}
}

factoredvaluemcts.jl's Issues

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

Use LightGraphs.jl API to check whether undirected graph edge in the graph rather than collected edgelist

FactoredValueMCTS.jl/src/fvmcts/action_coordination/maxplus.jl

Lines 191 to 207 in 26f7aa6

	nbrs = neighbors(tree.coordination_stats.adjmatgraph, i)
	edgelist = collect(edges(adjgraphmat))
	if tree.coordination_stats.use_agent_utils
	@views q_values[i, :] = state_stats.agent_action_q[i, :]/n_agents
	end
	for n in nbrs
	if Edge(i,n) in edgelist # use backward message
	q_values[i,:] += bwd_messages[findfirst(isequal(Edge(i,n)), edgelist), :]
	elseif Edge(n,i) in edgelist
	q_values[i,:] += fwd_messages[findfirst(isequal(Edge(n,i)), edgelist), :]
	else
	@warn "Neither edge found!"
	end
	end
	end

Thanks @freemin7 for bringing this to our attention on slack.