Agents meeting in a directed connected graph

Question

We have a directed connected graph, where nodes are places one can go to and edges are the "roads" between places. We have K agents whose goal is to meet in one node. Agents start in different nodes. Note that more than one agent can be at one node at the same time and that all agents move by one node at every turn(they move synchronously).

We have to variants of this task:

1. in each turn every agent must move

2. an agent may pass on moving.

For a chosen variant, I have to find an algorithm to complete this task, but it cannot be the state-space search algorithm.

I've been sitting on this for a while, but I cannot think of anything.

I've been thinking if agents could know each other positions in order to choose where to go, but it's a state-space search. I also thought that if agents meet, they could continue together. But I'm looking for an alternative to state-space search algorithms.

Answer 1

It's not possible to solve version 1) of the problem in general. To see why, consider a graph with 2 cities, and 2 agents, where the agents start in opposite nodes. Since both agents need to move every turn, they will never meet in the same city.

For version 2), I'm going to make some assumptions that aren't completely clear from your text:

• Agents have only local information. They can't see the global structure of the graph, and just all agree to meet at city X, because they don't know that X exists. They also can't see where other agents are initially.
• Cities are labelled, or otherwise identifiable to the agents. That is, an agent can tell whether they've visited a city before or not.
• Agents can tell how many agents are in their current city, and in all adjacent cities.
• There are a finite number of cities, and it's always possible to get from city A to city B, for any pair of cities (A,B).
• Agents have no way to communicate with each other, except by being present in the same space or not.

In this setup, the following heuristic will always work:

• If you've never seen another agent, move to a random adjacent city, or stay in place, with a uniform probability of taking each possible action.

• If you've never seen another agent before, but you see one or more agents now, then switch permanently to the following strategy:

  1. If you can see an adjacent city with more agents than your city, move there now. If you can see several such cities, move to the largest one. Pick randomly in case of a tie.
  2. If an adjacent city has the same number of agents as yours, flip a coin to decide whether to go or stay. Eventually, one city ends up with more than the other, and then step 1 causes all agents to end up in the same city.
  3. Otherwise, if you can see other adjacent cities with fewer agents, just stay put. They'll come to you.
  4. If all adjacent agents are empty and there's a total of $n$ agents you can see in your city right now, then remember $n$.
  5. As long as you still can't see more than $n$ agents in total, stay put with probability $(n-1)/n$ and move to a random adjacent city with probability $1/n$.
  6. If you stayed put per step 5, and you still can only see n agents, and all but one of them is in your current city, move to the city with the single agent who moved. Otherwise, if 0 or more than 1 agent moved, stay put. The agents who moved come back, and we go to step 5.
  7. After successfully moving, go to step 1 again.

You can see that once agents meet up in a group, that group never shrinks. Further, groups of agents are always trying to move around together. You can prove that a group moves an average of about $\frac{1}{2e}$ every step. It may take a while, but eventually every group will bump into every other group, resulting in all the agents being in the same city.