Эффективность последовательного процесса

Question

Я не уверен, что это скорее вопрос программирования или математический. Пожалуйста, дайте мне знать, на каком форуме можно задать этот вопрос, если это не тот.

У меня есть следующий последовательный процесс:

1. Есть $n$ монеты, разбросанные в квадратной сетке $100 \times 100$ точки.
2. Есть $m$ агентов в центральном месте, т. е. в точке $(50,50)$.
3. Эти агенты могут совершать случайное блуждание по сетке, перемещая одну точку сетки за один шаг. За один временной шаг все агенты перемещаются на один шаг от своего текущего положения.
4. Агенты должны найти монеты. Как только агент находит монету, отмечается временной шаг. Затем агент переходит к центральному местоположению по кратчайшему пути от точки, где была найдена монета. Опять же, за один временной шаг агент может переместить только одну точку сетки, в то время как другие агенты могут все еще искать другие монеты.
5. Как только агент с монетой достигает центрального местоположения, монета остается, и агент снова начинает поиск других монет.
6. Процесс останавливается по истечении заданного количества временных шагов независимо от того, все ли монеты были найдены.

В общем процессе я контролирую распределение монет, все ли агенты уходят сразу или в определенные временные интервалы, а также могут ли они взаимодействовать друг с другом, чтобы снова сократить исследование одной и той же области. В конце концов, я хочу узнать, насколько быстро агенты находят монеты. Я ищу способ количественно оценить эффективность поиска монет в обобщенном случае$n$ монеты и $m$агенты. Это означает, что если я хочу сравнить 10 агентов, нашедших 100 монет, с 5 агентами, нашедшими 50 монет, это количество должно быть в состоянии сказать мне, в каком случае агенты были более эффективны в поиске монет. Я могу построить процент монет, найденных с течением времени, и это обычно S-образная кривая, но по мере увеличения моих параметров я думаю, что было бы лучше, если бы у меня были отдельные значения для сравнения, а не линии графика.

На мой взгляд, три параметра, которые будут играть роль в определении этой эффективности, - это расстояние монеты от центра, временные шаги, предпринятые агентом, чтобы найти монету, начиная с центра, и общее количество агентов. в области поиска монет. Но я не уверен, что было бы хорошим способом связать их вместе.

Answer 1

Частичный ответ

У нас есть решетчатый граф $G$ с идентифицированным узлом в качестве центрального узла, $c$.

Позволять $$N=V \space \text{\\} \space \{c\},$$ т.е. $N$ это набор узлов $G$ без учета $c$.

Позволять $$S = \{ p_n | p_n \text{is the shortest path between } c, n \in N \}$$

Если мы ограничим проблему, указав количество агентов $k$ который будет развернут, определяется в $t = 0$ и остается неизменным на протяжении всего моделирования, мы можем выбрать $$k = |S|$$

Это назначает одного агента каждому кратчайшему пути $p_n$ и мы можем утверждать, что между агентами нет конфликтов, которые мы должны моделировать.

Позволять $d_{n,0}, d_{n,1}, \dots, d_{n,j}$ быть отсортированными расстояниями монет от $c$ для пути $p_n$ т.е. $d_{n,j} < d_{n,j+1}$.

Рассмотрим пути $(c,x)$ и $(c,y)$. У нас могло быть два агента на этих путях, и они могли собирать монеты в$x, y$соответственно. Кто получает приоритет при возвращении в$c$? Ответ: это не имеет значения, поскольку они оба равноудалены от$c$.

Поэтому без ограничения общности мы примем соглашение, что агент на более коротком пути будет иметь приоритет. Это помогает нам упростить расчет.

Позволять $m_n$ быть количеством монет на пути $p_n$. Позволять$c_n$ быть количеством монет, собранных на пути $p_n$.

$c_n$ сдерживается

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

Общее количество собранных монет выражается как

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

Позволять $M$быть количеством агентов. Тогда средняя производительность агента определяется выражением

$$C \over M$$

Позволять $C_{total}$быть общим количеством монет. Эффективность$(\eta)$ развертывания с точки зрения собранных монет будет

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

Пролог: это становится очень сложным, если вы разрешаете больше агентов, чем количество кратчайших путей к монетам, потому что тогда вам нужно будет смоделировать, когда эти агенты могут войти в поле, сколько из них могут войти в поле и как они координируются с основным агентом на кратчайший путь, не вызывающий споров.

Теоретически, как только кратчайший путь будет очищен от всех монет (это произойдет, если $c_k < t$ для любой $k$), все пути, которые связаны с ним ребром, могут использовать его для выстраивания ожидающих агентов. Как только один из этих агентов увидит монету на расстоянии$x$ от него, лежащего на соединенном кратчайшем пути $p_m$ и монета находится на расстоянии $d_{n,r}$ и нет никакой другой монеты между этой монетой и $c$ и основной агент движется к $c$, ожидающий агент может перейти, чтобы забрать эту монету.

На рисунке выше $r$ агент движется к $c$с собранной монетой. Голубые узлы - это ожидающие агенты. Агент$a$ может двигаться, чтобы собирать монету $j$ и следовать $r$.

Это поможет повысить эффективность. Мы могли бы использовать кратчайший путь от ожидающего агента до монеты и отправить агента к этой монете. Однако это очень быстро усложняется, и я не уверен в простом способе подсчета количества собранных монет.