2
$\begingroup$

Say we had two agents and we want them both to traverse a map concurrently.

Their goal is to collectively visit a collection of certain points on the map. If there was just one agent, it would be simple enough to just implement BFS or A* and get a good solution.

But considering there are two, how can we divide the points to be visited among the two agents in such a way that no steps (or minimal steps) are wasted in visiting all the points?

Edit/Clarification:

-The points do not need to be visited in a particular order. -If there was only one agent, I could get a possible solution with a BFS or A* where the goal state is all the points having been visited.

Edit 2: Pictures

An example of the problem might be as seen below. Agents start at the top left of the maze and the goal is a state space where all the red dots have been visited.

A possible path that might be returned by BFS with a single agent: enter image description here

What I would like to achieve with multiple agents: enter image description here

$\endgroup$
  • $\begingroup$ Can you specify the problem more? Do the points need to be visited in a particular order, or can they be visited in any order? If any order is OK, then how do you plan to solve it with only one agent? There can be $n!$ possible orderings. $\endgroup$ – D.W. May 13 '17 at 8:38
  • 1
    $\begingroup$ If your plan for a single agent is to just do A* with the state space being essentially the set of unvisited points, why can't you do exactly the same thing with two agents? Note, by the way, that this will take exponentially long even in the single-agent case, since you're essentially solving hamilonian path, depending on what your notion of "good solution" is. $\endgroup$ – David Richerby May 13 '17 at 13:59
  • $\begingroup$ By the way, you seem to have ended up with two separate accounts. If you use the "contact us" link at the bottom of the page, you can get the site admins to merge them. Then you'll be able to edit your own posts and respond to comments under them. $\endgroup$ – David Richerby May 13 '17 at 14:03
  • $\begingroup$ Thanks for the merge advice, all fixed up. I added some pictures to help explain how I am thinking about it. Open to the idea that I may be way off about how I am approaching/thinking about the problem. $\endgroup$ – Paul May 13 '17 at 16:24

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.