Efficiency of a sequential process

Question

I'm not sure if this is more of a programming question or a mathematical one. Please let me know the proper forum to ask this in, if this isn't the one.

I have a sequential process as follows:

1. There are $n$ coins scattered in a square grid of $100 \times 100$ points.
2. There are $m$ agents at a central location, i.e., the point $(50,50)$.
3. These agents can do a random walk on the grid, moving one gridpoint in one step. In one time step, all the agents move one step from their current position.
4. The agents are supposed to find the coins. Once an agent finds a coin, the time step is noted. Then, the agent proceeds to move to the central location along the shortest path from the point where the coin was found. Again, in one time step, the agent can move only one gridpoint, while other agents might still be searching for other coins.
5. Once the agent with the coin reaches the central location, the coin is left and the agent starts searching for other coins again.
6. The process stops when a specified number of time steps are over, irrespective of whether all the coins have been found.

In the general process, I have control over the distribution of coins, whether all the agents leave at once or at certain time steps, and whether they can interact with each other to reduce exploring the same area again. In the end, I want to find how quickly are the coins found by the agents. I'm looking for a way to quantify this efficiency of finding coins in the generalized case of $n$ coins and $m$ agents. This means, if I want to compare 10 agents finding 100 coins with 5 agents finding 50 coins, this quantity should be able to tell me in which case the agents were more efficient in finding the coins. I can plot the percentage of coins found over time, and this is usually an S-curve, but as my parameters increase, I think it'd be better if I had single values to compare rather than plot-lines.

In my opinion, I think the three parameters that would play a role in determining this efficiency are the distance of a coin from the centre, the time steps taken by an agent to find the coin starting from the centre, and the total number of agents in the area searching for coins. But I'm not sure what would be a good way of relating them together.

Answer 1

Partial Answer

We have a lattice graph $G$ with an identified node as the central node, $c$.

Let $$N=V \space \text{\\} \space \{c\},$$ i.e., $N$ is the set of nodes of $G$ excluding $c$.

Let $$S = \{ p_n | p_n \text{is the shortest path between } c, n \in N \}$$

If we constrain the problem by saying the number of agents $k$ that will be deployed is determined at $t = 0$ and remains constant throughout the simulation, we can choose $$k = |S|$$

This assigns one agent to each shortest path $p_n$ and we can affirm that there are no contentions between agents that we have to model.

Let $d_{n,0}, d_{n,1}, \dots, d_{n,j}$ be the sorted distances of the coins from $c$ for path $p_n$ i.e., $d_{n,j} < d_{n,j+1}$.

Consider the paths $(c,x)$ and $(c,y)$. We could have two agents on these paths and they could have collected the coins at $x, y$ respectively. Who gets priority while returning back to $c$? The answer is, it does not matter as they are both equidistant from $c$.

Therefore, we will assume the convention without loss of generality that the agent on the shorter path will have priority. This helps us simplify our calculation.

Let $m_n$ be the number of coins on the path $p_n$. Let $c_n$ be the number of coins collected on the path $p_n$.

$c_n$ is constrained by

$$\sum_{k=1}^{m_n} 2d_{n, k} \le t$$

The total number of coins collected is given by

$$C = \sum_{i=1}^{n} c_i$$

Let $M$ be the number of agents. Then the average productivity of the agent is given by

$$C \over M$$

Let $C_{total}$ be the total number of coins. Efficiency $(\eta)$ of the deployment in terms of coins collected would be

$$\eta = {C \over C_{total} } \times 100 \text{%}$$

Prologue: This becomes very complicated if you allow more agents than the number of shortest paths to coins because you would then need to model when those agents can enter the field, how many can enter the field and how they coordinate with the primary agent on the shortest path without causing contention.

In theory, once a shortest path is cleared of all coins (this will occur if $c_k < t$ for any $k$), all paths that are connected to it by an edge can make use of it to line up agents-in-waiting. As soon as one of those agents sees a coin at a distance $x$ from it lying on a connected shortest path $p_m$ and the coin is at a distance of $d_{n,r}$ and there is no other coin between that coin and $c$ and the primary agent is moving towards $c$, the agent-in-waiting can move to collect that coin.

In the figure above, $r$ is an agent moving towards $c$ with a collected coin. The light blue nodes are agents-in-waiting. The agent $a$ can move to collect coin $j$ and follow $r$.

This will help improving the efficiency. We could use the shortest path from an agent-in-waiting to a coin and dispatch the agent to that coin. However, this gets complex very quickly and I am not sure of a simple way to compute the number of coins collected.