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$ – Marcus Ritt May 24 '19 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$ – Panos Filianos May 24 '19 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$ – Marcus Ritt May 24 '19 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$ – Panos Filianos May 24 '19 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.