I am researching into coding a solver for a variant of the Sokoban game with multiple agents, restrictions (eg. colors of stones, goals) and relaxations (push AND pull possible etc.)

By researching online I have found classic papers in the field, like the Rolling Stone paper (by Andreas Junghanns and Jonathan Schaeffer) and Sokoban: Enhancing general single-agent search methods using domain knowledge from the same authors.

These solutions seem to be outdated and I am currently structuring my solver per the notes of the two most performant solvers: YASS and Sokolution.

From the research I've done these two seem to be my best bet.

It is apparent that they are not enough by themselves to solve a multi-agent environment. Those solvers are made for a single agent. So far, I have failed to find useful multi-agent proposals.

In this context, my question is: What can be considered state-of-the-art in order to (1) coordinate multiple agents with different goals and (2) plug a solver's solution in and validate/edit it? What are some search terms I can use to research this further?

Thank you very much

  • $\begingroup$ Can you expand a bit on what you mean by "coordinate multiple agents with different goals"? Are you interested in, say, two agents with red and blue stones, and different red and blue goal zones on the same map? $\endgroup$ Commented May 24, 2019 at 11:17
  • $\begingroup$ Yes, this is exactly what I'm going for! I'll start with at max 10 agents, 10 diff colors and 50x50 grids. $\endgroup$ Commented May 24, 2019 at 11:20
  • $\begingroup$ Multi-agent Planning in Sokoban and A multi-agent planning approach integrated with learning mechanism may be useful, but I think the literature is meager on that topic. $\endgroup$ Commented May 24, 2019 at 11:40
  • $\begingroup$ Thanks a lot. I've read the first paper and it doesn't seem to provide enough information to direct to a practical solution. Would you happen to know good or state of the art multi-agent planning literature even in other domains? $\endgroup$ Commented May 24, 2019 at 11:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.