Лучшая эвристика A *: несколько целей и агентов

Question

У меня проблема с квадратным лабиринтом со стенами, целями и агентами.Агенты могут двигаться только горизонтально / вертикально.На каждом шаге каждый агент перемещается с 1 квадрата.

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

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

Эвристика, которую я пытаюсь экспериментировать, следующая:

Для каждой цели я беру ближайшее расстояние Манатана от агента и суммирую результат.

В этом случае, если осталось две цели и три агента, в сумме берут только двух агентов.и самый дальний агент не рассматривается, сумма будет меньше, чем в случае с тремя агентами и тремя оставшимися целями.

В соответствии с определением допустимой эвристики, я сомневаюсь, что мое допустимо.

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

У кого-нибудь есть советы или интересный подход для рассмотрения?

Answer 1

A * работает только с одним агентом.Вам нужно будет запустить отдельный экземпляр поиска для каждого агента.

Если имеется много агентов и всего несколько целей, а ваш график не ориентирован, вы можете вместо этого выполнять поиск от целей к агентам (при условии, что вам нужен только ближайший агент) и затем сторнируйте результаты.

Если вам нужно найти пути с лотами и лотами агентов, вам следует использовать другойалгоритм.Есть много вариантов;ключевые слова, чтобы искать здесь, "поиск роя роя", "поток толпы" и "boids".Обычно вы создаете векторное поле для всей карты и соединяете его с каким-то алгоритмом уклонения.