Поведение стаи

[kishkin]

Добрый день!

Возникла задача, и думаю здесь кто-нибудь подскажет.

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

Например, Ракета П-700 «Гранит». Стая таких ракет, каким-то образом определяет себе главного, распределяет цели, при уничтожении одной из них, кто-то занимает ее место. Конечно, было бы интересно посмотреть на конкретную реализацию этого комплекса, но ясно, что это не возможно.

Однако подобные задачи решались, не так ли? Подскажите, куда смотреть?

Best retards,
Mike

[worm2]

Ну вот, например, такой вариант:
Каждому агенту присвоен уникальный номер, у кого в стае номер больше --- тот и главный.

[Igor Borovikov]

Как ни забавно но такая задача часто встречается в программировании компьютерных игр. Например, несколько врагов, управляемых игрой, нападают на противника - как координировать действия отдельных агентов? Именно такую задачу я решал на одном из игровых проектов. Конкретное решение в Вашем случае может быть другим, но вот тут есть некторые ссылки и соображения которые вероятно помогут: http://3dmatics.com/compsci/osm/slides/index.htm

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

Решение, которое предлагает worm2, требует взаимодействия сложности NxN - чтоб агенты могли договорится у кого номер больше. Если N велико и если есть вероятность ошибок в обмене сообщениями, то ситуация может оказаться неоднозначной. Например в случае ошибок стая может распасться или главный в стае будет переназначаться слишком часто.

Вообще задача в Вашей постановке очень интересна. Если что то найдете полезное, не сочтите за труд запостить!

[zbl]

Igor Borovikov писал(а):

Решение, которое предлагает worm2, требует взаимодействия сложности NxN - чтоб агенты могли договорится у кого номер больше.

Не факт.
Если взаимодействовать только с ближайшими соседями, то будет порядка N сеансов связи, но можно передавать не только свою информацию, но и в купе передать полученное от своих соседей.
Отсюда не факт, что не хватит порядка N сеансов для алгоритма поиска максимального номера.
Но факт, что результат зависит от порядка, в котором устанавливались сеансы связи между парами ближайших соседей.
Плюс.
Не факт, что нельзя организовать широковещательную или многоадресную передачу.
Тогда за один сеанс информацию смогут получить сразу несколько агентов.

Igor Borovikov писал(а):

Вообще задача в Вашей постановке очень интересна. Если что то найдете полезное, не сочтите за труд запостить!

Присоединяюсь.

[Shed]

простой и изящный критерий(не знаю как применительно к вашей задаче):
При уничтожении "главного", его место занимает агент, наиболее
приближённый к нему (по расстоянию).Для Комп. игры, думаю, -самое ТО.

[kishkin]

Всем привет!

Господа, спасибо за помощь.

worm2 писал(а):

Ну вот, например, такой вариант:
Каждому агенту присвоен уникальный номер, у кого в стае номер больше --- тот и главный.

Ага. Такая мысль уменя тоже была, но все таки решил покопаться.

Igor Borovikov писал(а):

Как ни забавно но такая задача часто встречается в программировании компьютерных игр.

Было нагуглено в первый же день. Плюс в трэде про искусственный интеллект нашел много интересных ссылок по этой теме.

По поводу сложности алгоритма определения. Тут, как мне кажется от конкретной реализации будет зависеть. Например в статье A Distributed Algorithm for Minimum-Weight Spanning Trees Галлагер и другие предлагают интересный распределенный алгоритм, который потребует не более 5N log2N + 2E пересланных сообщений. Ну, это я не точно цитирую. Там от графа зависит.

Shed писал(а):

простой и изящный критерий(не знаю как применительно к вашей задаче):
При уничтожении "главного", его место занимает агент, наиболее
приближённый к нему (по расстоянию).Для Комп. игры, думаю, -самое ТО.

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

В общем, я все еще пытаюсь разобраться в различных методах и сравнить их. А темы такие: flock behaviour, swarm intelligence и теория графов (есть замечательная книжка Н. Кристофидеса "Теория графов. Алгоритмический подход", в которой решена подобная задача).

Будут результаты, первое, что сделаю - зашлю их сюда.

[PAV]

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

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

Однако с другой стороны возможно все-таки выделение некоторых содержательных критериев. Например:

- вожаком назначается ракета, летящая впереди других, потому что она видит обстановку самой первой и соответственно у нее чуть больше времени на принятие решений;

- вожаком назначается ракета, летящая максимально в середине группы, потому что у нее самая устойчивая связь со всеми членами группы;

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

[незваный гость]

Ещё пара вариантов:

— вожаком назначают ракету в хвосте, потому, что сбивать будут первые (у них наименьшее время подлёта);

— идёт вероятностное назначение и переназначение вожака, поскольку если противник знает/угадает стратегию, он будет целиться в вожака.

Об угадывании есть забавный пассаж у Орсона Скота Карда в «Игре Эндера». Так что, маскировка коммандира — сверхкритична.

В любом случае, мы имеем дело с emerging behaviour: поаедением стаи (роя), не следующим непосредственно из поведения отдельных объектов. Хотя задачи о баранах / волках по меньшей мере звучат менее кровожадно, чем задачи о ракетах.

[kishkin]

PAV писал(а):

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

Мудрое замечание, ничего не скажешь. Надо подумать.

Добавлено спустя 3 минуты 9 секунд:

незваный гость писал(а):

:evil:

Об угадывании есть забавный пассаж у Орсона Скота Карда в «Игре Эндера». Так что, маскировка коммандира — сверхкритична.

Поделиться можете?

незваный гость писал(а):

Хотя задачи о баранах / волках по меньшей мере звучат менее кровожадно, чем задачи о ракетах.

Ну, это смотря, куда ракеты летят.

[незваный гость]

Игра Эндера:

- Покажите мне, как вы разбили жукеров, Мэйзер.

Лицо учителя окаменело.

- Вы показывали мне все остальные сражения раз десять. Думаю, я наметил пару-другую маневров, которые можно противопоставить прежней тактике жукеров. Но вы не показывали, как на самом деле разбили их.

- Эта запись - один из самых больших наших секретов, Эндер.

- Знаю. Я отчасти восстановил картину по кусочкам. У вас была небольшая группа истребителей, резерв, у них - армада, десятки кораблей-маток и сотни истребителей. Вы атакуете вражеский корабль. Огонь! Взрыв! И тут сцена всегда обрывается. Дальше идут только кадры с морскими пехотинцами, проникающими на корабли жукеров, чтобы найти одни трупы.

Мэйзер улыбнулся.

…
- Но ведь вы выиграли сражение?

- Я тоже думаю, что это придает вес моим суждениям, но ты же знаешь, как это бывает. Ксенобиологи и ксенопсихологи не могут вынести мысли о том, что офицер флота опередил их, опираясь на чистые догадки. Думаю, что они вдобавок здорово возненавидели меня за то, что, осмотрев эту пленку, провели остаток жизни здесь, на Эросе. Требования безопасности. Нельзя сказать, чтобы они были счастливы.

- Рассказывайте.

- Жукеры не разговаривают. Они обмениваются мыслями; это процесс единовременный, как филотический эффект. Как действие анзибля. Но большинство людей считает, что это именно мыслеобмен, двусторонняя связь, как при использовании языка: я посылаю тебе мысль, а ты мне отвечаешь. Только я в это не верю. Жукеры реагируют на любое изменение ситуации все вместе и слишком быстро. Ты видел наши записи. Жукеры не совещаются, не выбирают наилучший вариант. Каждый корабль действует как часть единого организма. Так ведет себя в бою человеческое тело: различные его органы мгновенно и бездумно исполняют, что им положено. Там нет мысленного диалога между существами - носителями разных мыслительных процессов. Все их мысли появляются вместе и сразу.

- Единая личность? Отдельный жукер просто часть тела, как рука или нога?

…

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

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

- Ты это видишь. Я это вижу. Только двое из тех, кто за эти годы успел посмотреть фильм. Но ведь мы правы, не так ли?

- Они сделали так, чтобы корабль ничем не отличался от других.

- Знают, где их слабое место.

- Вы правы. Это действительно королева. Но тогда они должны были сосредоточить всю огневую мощь на вас. Они могли бы смести вас с дороги к чертовой матери.

- Знаю. Но не могу постичь. Не то чтобы они не пытались остановить меня - стреляли, и еще как. Но словно не могли поверить до последней минуты, пока не стало слишком поздно, что я и в самом деле убью королеву. Может, в их мире королев не убивают - только захватывают, снимают с доски. Я сделал то, чего они не ожидали даже от врага.

[kishkin]

Почитал. Спасибо.

[Gafield]

Раз упоминались конкретные ракеты, то тут такой вопрос. Сколько их реально применяется, насколько велика стая? Если порядка $10^1$, то при современных вычислительных средствах связь всех со всеми вроде не должна быть проблемой, и всякие асимптотические оценки с логарифмами здесь, вроде, ни к чему. А вот если их порядка $10^2$, то тогда уже интересней.

Или это дипломная работа, типа, пусть число ракет равно N...

[kishkin]

На самом деле, ракеты были просто примером. Количество агентов растет от 1 до $10^4$

Добавлено спустя 2 минуты 34 секунды:

Gafield писал(а):

Или это дипломная работа, типа, пусть число ракет равно N...

Точно. Дипломная работа. Но все таки не про ракеты.

[Igor Borovikov]

Цитата:

Но все таки не про ракеты.

В этом случае задачу хотелось бы поставить задачу поточнее, а то раззадорили... а это и не про ракеты вовсе! Если это компьютерная игра, то мне кажется, что я знаю ответ (см ссылку выше. Опять же, насчет нагугливания - это конечно, хорошо и правильно, но вот личный опыт - это совсем другое ).

А если это моделирование реальных боевых взаимодействий, то это, конечно, еще более другое дело...

[В.О.]

Моделирование стаи
http://www.red3d.com/cwr/boids/
www.iamm.ac.donetsk.ua/journals/transac ... 26_136.pdf

У животных лидером становится самый крупный, самый активный, самый агрессивный... иногда самый умный.