Efficacité d'un processus séquentiel

Question

Je ne sais pas s'il s'agit plus d'une question de programmation ou d'une question mathématique. S'il vous plaît laissez-moi savoir le forum approprié pour poser cette question, si ce n'est pas celui-là.

J'ai un processus séquentiel comme suit:

1. Il y a $n$ pièces dispersées dans une grille carrée de $100 \times 100$ points.
2. Il y a $m$ agents à un emplacement central, c'est-à-dire au point $(50,50)$.
3. Ces agents peuvent effectuer une marche aléatoire sur la grille, en déplaçant un point de grille en une seule étape. En une seule étape, tous les agents se déplacent d'une étape par rapport à leur position actuelle.
4. Les agents sont censés trouver les pièces. Une fois qu'un agent trouve une pièce, le pas de temps est noté. Ensuite, l'agent se déplace vers l'emplacement central le long du chemin le plus court à partir du point où la pièce a été trouvée. Encore une fois, en une seule étape, l'agent ne peut déplacer qu'un seul point de grille, tandis que d'autres agents peuvent toujours rechercher d'autres pièces.
5. Une fois que l'agent avec la pièce atteint l'emplacement central, la pièce est laissée et l'agent recommence à chercher d'autres pièces.
6. Le processus s'arrête lorsqu'un nombre spécifié d'étapes de temps est écoulé, que toutes les pièces aient été ou non trouvées.

Dans le processus général, j'ai le contrôle sur la distribution des pièces, si tous les agents partent en même temps ou à certaines étapes de temps, et s'ils peuvent interagir les uns avec les autres pour réduire à nouveau l'exploration de la même zone. En fin de compte, je veux savoir à quelle vitesse les pièces sont trouvées par les agents. Je cherche un moyen de quantifier cette efficacité de recherche de pièces dans le cas généralisé de$n$ pièces et $m$agents. Cela signifie que si je veux comparer 10 agents trouvant 100 pièces avec 5 agents trouvant 50 pièces, cette quantité devrait être en mesure de me dire dans quel cas les agents ont été plus efficaces pour trouver les pièces. Je peux tracer le pourcentage de pièces trouvées au fil du temps, et il s'agit généralement d'une courbe en S, mais à mesure que mes paramètres augmentent, je pense que ce serait mieux si j'avais des valeurs uniques à comparer plutôt que des lignes de tracé.

À mon avis, je pense que les trois paramètres qui joueraient un rôle dans la détermination de cette efficacité sont la distance entre une pièce et le centre, le temps que prend un agent pour trouver la pièce à partir du centre et le nombre total d'agents. dans la zone à la recherche de pièces. Mais je ne sais pas quelle serait une bonne façon de les relier.

Answer 1

Réponse partielle

Nous avons un graphique en treillis $G$ avec un nœud identifié comme nœud central, $c$.

Laisser $$N=V \space \text{\\} \space \{c\},$$ c'est à dire, $N$ est l'ensemble des nœuds de $G$ à l'exclusion $c$.

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

Si on contraint le problème en disant le nombre d'agents $k$ qui sera déployé est déterminé à $t = 0$ et reste constant tout au long de la simulation, on peut choisir $$k = |S|$$

Cela affecte un agent à chaque chemin le plus court $p_n$ et nous pouvons affirmer qu'il n'y a pas de conflits entre agents que nous devons modéliser.

Laisser $d_{n,0}, d_{n,1}, \dots, d_{n,j}$ être les distances triées des pièces de $c$ pour chemin $p_n$ c'est à dire, $d_{n,j} < d_{n,j+1}$.

Considérez les chemins $(c,x)$ et $(c,y)$. Nous pourrions avoir deux agents sur ces chemins et ils auraient pu collecter les pièces à$x, y$respectivement. Qui a la priorité lors du retour à$c$? La réponse est que cela n'a pas d'importance car ils sont tous les deux équidistants de$c$.

Par conséquent, nous supposerons la convention sans perte de généralité selon laquelle l'agent sur le chemin le plus court aura la priorité. Cela nous aide à simplifier notre calcul.

Laisser $m_n$ être le nombre de pièces sur le chemin $p_n$. Laisser$c_n$ être le nombre de pièces collectées sur le chemin $p_n$.

$c_n$ est contraint par

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

Le nombre total de pièces collectées est donné par

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

Laisser $M$être le nombre d'agents. Ensuite, la productivité moyenne de l'agent est donnée par

$$C \over M$$

Laisser $C_{total}$être le nombre total de pièces. Efficacité$(\eta)$ du déploiement en termes de pièces collectées serait

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

Prologue: Cela devient très compliqué si vous autorisez plus d'agents que le nombre de chemins les plus courts vers les pièces, car vous auriez alors besoin de modéliser quand ces agents peuvent entrer dans le champ, combien peuvent entrer dans le champ et comment ils se coordonnent avec l'agent principal sur le chemin le plus court sans provoquer de conflit.

En théorie, une fois que le chemin le plus court est dégagé de toutes les pièces (cela se produira si $c_k < t$ pour toute $k$), tous les chemins qui lui sont connectés par une périphérie peuvent l'utiliser pour aligner les agents en attente. Dès que l'un de ces agents voit une pièce à distance$x$ à partir de là couché sur un chemin le plus court connecté $p_m$ et la pièce est à une distance de $d_{n,r}$ et il n'y a pas d'autre pièce entre cette pièce et $c$ et l'agent principal se dirige vers $c$, l'agent en attente peut se déplacer pour récupérer cette pièce.

Dans la figure ci-dessus, $r$ est un agent qui se dirige vers $c$avec une pièce collectée. Les nœuds bleu clair sont des agents en attente. L'agent$a$ peut se déplacer pour collecter des pièces $j$ et suivre $r$.

Cela aidera à améliorer l'efficacité. Nous pourrions utiliser le chemin le plus court entre un agent en attente et une pièce et envoyer l'agent vers cette pièce. Cependant, cela se complexifie très rapidement et je ne suis pas sûr d'un moyen simple de calculer le nombre de pièces collectées.