коллектив роботов. Коллективное поведение роботов. Желаемое и действительное

• Название: Коллективное поведение роботов. Желаемое и действительное
• Дата: 05.10.2022
• Размер: 1.49 Mb.
• Имя файла: коллектив роботов.pdf
• Тип: Статья; #716569
• страница: 2 из 5

3.1. Формальные модели коллективного поведения
Автоматные модели. В 60-е гг. 20 века сформировалась школа, изучающая различные модели поведения на основе конечных автоматов. Основным тезисом являлось: любое достаточно сложное поведение слагается из совокупности простых поведенческих актов [Цетлин, 1969]. Яркими представителями этого направления являются ее основоположник М.Л. Цетлин, В.И. Варшавский, В.Л. Стефанюк, Д.А. Поспелов и др.
7

Характерно, что первая работа, в которой был впервые предложен и использован термин "коллективное поведение автоматов", была опубликована еще в 1963 году.
Исследуя разнообразные формы поведения, начиная от условно-рефлекторного, и заканчивая моделями коллективного поведения, был создан теоретический фундамент для описания коллективного взаимодействия объектов самой разной природы.
В рамках коллективного поведения автоматов рассматривались задачи распределения ресурсов между участниками, особенности организации однородных коллективов, поведение неоднородных структур (вводился ранг рефлексии участников) и т.п. Решались также задачи синхронизации взаимодействия членов коллектива (автоматов). Именно на базе подобных моделей был создан фундамент сотовой связи (задача о коллективе радиостанций, которым надо "договариваться" между собой о мощности своих сигналов) [Стефанюк, 2004],
[Стефанюк и др., 1967]. Именно эти модели и методы (см., например,
[Варшавский и др., 1984], [Гаазе-Раппопорт и др., 1987]) стали основой для построения многих децентрализованных коллективных систем, моделей индивидуального и коллективного поведения.
Заметим, что некоторые разработанные подходы и методы до сих пор недоценены особенно применительно к задаче коллективного поведения роботов. В качестве первого примера можно рассмотреть задачу регулировки мощности радиостанций. Современные стандарты сотовой связи подразумевают наличие т.н. базовых станций, которые берут на себя функции централизованного управления, в т.ч. – и регулировку мощности сигналов.
Однако предложенная в [Стефанюк, 2004], [Стефанюк и др., 1967] схема взаимодействия радиостанция является принципиально децентрализованной, самоорганизующейся. А это является принципиальным моментом для организации той же самой пресловутой «умной» пыли или интеллектуальных сенсорных сетей. Дело в том, что для этих систем наиболее актуальной проблемой является сбалансированность энергоресурса. Именно минимизация энергозатрат, гарантированность времени функционирования системы в целом – это самое слабое место сенсорных сетей. И здесь как никогда важна способность элементов сети
«договориться» между собой.
Вторым примером является множество работ по подражательному, стайному поведению. Самое удивительное, что в качестве иллюстрирующих примеров чаще всего используется схема, в которой роботы, способные к выполнению одного из двух действий, согласуют свои действия, выбирая такое, которое выполняет большинство его соседей.
Однако та же классическая задача о поливе участков гораздо более глубока и интересна. В этой задаче согласованность действий агентов – автоматов – достигается на основе наличия в коллективе игроков, обладающих ненулевым рангом рефлексии (способность рассуждать за другого).
Скважина
6 5
…
4 1
3 2
Дана скважина и кольцевой коллектор.
Необходимо экономить электроэнергию.
Решение:
•
Кольцо из N автоматов. Каждый из них может находиться в одном из двух состояний – 0 и 1.
•
Плохо, когда: 1) не экономится электроэнергия; 2) все засыхает.
Автомату с первым РР лучше сохранить свое текущее состояние.
Автомату с первым РР необходимо знать не только соседей, но и соседей соседей.
Автомату со вторым РР – аналогично.
Чем выше РР, тем о большем количестве соседей необходимо иметь информацию.
Состояние
Левый сосед
Собственное Правый сосед
Вероятность наказания
0 0
0 1
0 0
1 0.5 0
1 0
0 0
1 1
0.5 1
0 0
0.5 1
0 1
0 1
1 0
0.5 1
1 1
1
Левые соседи
Основной автомат Правые соседи
…
1 0
1
1 0
…
Рис.3. Иллюстрация к задаче о поливе участков
8

Пожалуй, теория коллективного поведения автоматов до сих пор является одной из очень немногих строгих, формальных моделей подобного рода систем.
Тем не менее, где в явном виде применялась теория коллективного поведения автоматов для реализации коллективного поведения роботов автору, к сожалению, неизвестно. Сослаться можно, пожалуй, на [Карпов и др., 2005]. В этой работе рассматривалась задача поведения двух роботов (роботы серии «АМУР»), которые могли обмениваться друг с другом накопленным опытом. Опыт приобретался при функционировании роботов в различных средах, а механизмом, реализующим обучение на базе условно-рефлекторного поведения, были конечные стохастические автоматы.
p
11
p
12
… p
1n p
21
p
22
… p
2n p
i1
p i2
… p in
… p
m1
p m2
… p mn d
1
= D(P
1
) p
11
p
12
… p
1n p
21
p
22
… p
2n p
i1
p i2
… p in
… p
m1
p m2
… p mn d
2
= D(P
2
)
P
i
2
A
2
P
i
1
A
1






⊕
<
≥
<
≥
=
иначе
P
P
R
d
,
R
d
,
P
R
d
,
R
d
,
P
P
2
i
1
i
1
2
2
i
2
1
1
i
i
R – порог (СКО,
δ
и т.п.)
Рис.4. Роботы серии «АМУР». Объединение матриц вероятностей действия
Клеточные автоматы. Иногда встречаются утверждения, что теоретическим и методологическим базисом коллективного поведения роботов может служить теория клеточных автоматов. Более того, сама теория клеточных автоматов родилась в каком-то смысле из робототехники. В свое время фон Нейман пытался решить задачу о роботе, собирающего другого робота (т.н. кинематическая модель). Однако в дальнейшем, осознав сложность создания подобного самовоспроизводящегося робота, фон Нейман разработал более абстрактную и удобную математическую модель – первую теорию клеточных автоматов. Сейчас, являясь примером классической однородной структуры [Аладьев, 2009], теория клеточных автоматов в явном виде для решения задачи коллективного поведения роботов практически не используется.
Оптимизационный подход. Здесь под этим термином понимается построение формальных моделей коллективов и групп роботов, причем эти модели допускают применение различного рода методов оптимизации управления.
При этом подходе состояния системы "робот среда" задаются парами вида
)
(
),
(
)
(
t
E
t
R
t
S
∈
,
где R(t) и S(t) – соответственно состояния робота и среды в момент времени t. Далее задаются начальные условия
)
(
),
(
0 0
0 0
t
E
E
t
R
R
=
=
Общая же постановка задачи определяется следующим образом [Каляев и др., 2009]:
Задача управления роботом R состоит в том, чтобы определить такую последовательность действий (вектор-функцию действий) A(t) на интервале времени [t
0
, t f
], выполнение которых при заданных связях, начальных условиях и ограничениях обеспечивало бы экстремум функционала
∫
+
Φ
=
f
t
t
f
f
f
dt
t
t
g
t
E
t
R
t
A
F
t
E
R
Y
0
)
),
(
),
(
),
(
),
(
(
)
,
,
(

9

Здесь g(t) – действия прочих сил, существующих в среде. Разумеется, вводятся ограничения на возможные состояния системы "робот-среда" и возможные действия робота.
}
{
)}
(
{
)
(
S
t
S
t
S
p
⊂
∈
}
{
)}
(
{
)
(
A
t
A
t
A
p
⊂
∈
В рамках такого "оптимизационного" подхода рассматриваются процедуры оптимизации коллективных действий в группе роботов, определяются условия устойчивости и сходимости, решаются задачи распределения целей между участниками коллектива, улучшения плана и проч.
Оптимизационный подход позволяет решать целый ряд задач, среди которых есть очень и эффектные. Например, есть такая красивая задача, как распределение целей между роботами группы, да еще в условиях заранее неизвестных противодействий противника (см. упомянутую выше артиллерийскую систему NLOS-LS или [Каляев и др., 2009]).
Если имеется M целей T
1
, T
2
, …, T
M
и N "роботов" R
1
,…,R
N
и известно, что ущерб, наносимый противнику при поражении i-й цели, определяется как Y
i
=F
i
(P
i
,n i
), где P
i
– приоритет цели, а n i
– количество роботов, поразивших i-ю цель, то целевым функционалом управления группой роботов будет Y
c
=
∑
Y
i
. А далее цели распределяются между роботами так, чтобы, естественно, максимизировать Y
c
Рис.5. Распределение целей T
i между «роботами» R
i
Эта задача (по крайней мере – на модельном уровне) решается достаточно хорошо.
Однако следует отметить, что подобный подход слишком абстрагируется от робота, как сложного технического объекта. «Умную пыль», «умные снаряды» и им подобные распределенные системы вряд ли можно отнести к объектам исследования именно коллективного поведения роботов. Дело даже не в том, что зачастую происходит выхолащивание самого понятия робота (и роботом называют буквально все, что движется и не движется – от тележки до лифта). Дело в том, что составная часть коллектива – робот – не может быть примитивной, простой. Особь – это сложное устройство. Только тогда возможна самоорганизация. Только тогда возникают предпосылки для коллективного поведения.
3.2. Многоагентные системы
Теория многоагентных систем (МАС) естественным образом претендует на то, чтобы стать основой для реализации коллективного поведения роботов. Действительно, понимая под агентом некую "разумную" сущность, способную к рациональному поведению, и в качестве которой может выступать робот, можно поставить знак равенства между МАС и задачей согласованного коллективного поведения технических устройств.
Наиболее близкими к теории МАС можно считать задачи организации командной работы. При этом следует различать командную работу роботов от иных видов
10

скоординированного поведения типа альянсов и коалиций. Командная работа – это такое поведение, которое целиком подчинено достижению общей командной цели.
Речь идет о том, что в команде ее участники (роботы, агенты) берут на себя обязательство стремиться к достижению командной цели, а сама цель системы декомпозируется (в пространстве и времени) на множество взаимосвязанных подцелей, достижение которых возлагается на различных агентов команды. Разумеется, распределение подцелей между членами команды, а также координация их поведения должны выполняться средствами самой команды, без какого-либо внешнего вмешательства.
Агент, как сущность, помимо прочего характеризуется такими свойствами, как наличие общих и индивидуальных обязательств и намерений, способностью к планированию, коммуникации, согласованию и т.д. Поэтому в МАС активно применяются такие теории, как теория общих намерений, теория общих планов, теория игр и т.п.
Теория игр. Многие ситуации, возникающие в МАС, имеют аналоги в теории игр.
Речь идет прежде всего о кооперативных играх, о формировании различных стратегий переговоров, игры в размещения и др.
Теория общих намерений. Основными понятиями теории общих намерений
[Cohen a.o., 1991] являются:
- события – связаны с конкретным агентом или объектом внешнего мира;
- убеждения – утверждения, в истинности которых агент убежден в текущий момент времени;
- цели – некоторые состояния агента, которые он стремится достичь;
- взаимные убеждения – складываются из убеждений группы агентов.
Для описания поведения команды агентов используются как индивидуальные, так и общие обязательства и соглашения.
Соглашения – это условия, при которых агент должен придерживаться своих обязательств, выраженных в терминах долговременной цели.
В свою очередь общие (коллективные) обязательства и соглашения определяются так, чтобы они описывали действия группы агентов, как одного агента. Поэтому эти обязательства и соглашения определяются через понятие "конечной цели" агента.
Разумеется, для коллективной работы между общими и индивидуальными намерениями агента должна существовать тесная связь.
Слабость теории общих намерений заключается в том, что она не конкретизирует алгоритмические средства планирования командной работы и не определяет средства для динамического пересмотра плана и обновления его оставшейся части. Теория предлагает только общие принципы организации командной работы, что позволяет лишь построить протокол взаимодействия членов команды – т.н. протоколом общих намерений
Теория общих планов, напротив, ориентирована прежде всего на построение конкретных планов, а не на формирование команды и общей дисциплины взаимодействия агентов. Теория использует понятие общих и индивидуальных обязательств и соглашений.
Базовые понятия теории: групповой план и индивидуальные ментальные понятия агентов. Согласование же индивидуальных действий и планов групп агентов выходит за рамки теории.
Итак, недостатком теории общих планов является отсутствие конкретизации способа построения общего плана.
Комбинированные модели. Разумеется, имеются попытки создания различного рода комбинированных моделей командной работы агентов, которые объединяли бы достоинства теории общих планов и теории соглашений.
Например, комбинированная модель [Tambe, 97] на верхнем уровне использует понятия общих обязательств и общих намерений команды агентов, взятые из теории общих намерений. При этом понятие общих намерений используется в этой теории для описания поведения команды агентов в терминах конкретных операторов, что характерно для теории общих планов.
11

Однако и эта модель не предоставляет возможности динамического изменения плана и коллективной обработки непредвиденных ситуаций.
Основные проблемы и ограниченность применения подобного рода теорий хорошо иллюстрируется следующими вполне конкретными и реальными ситуациями
[Городецкий и др., 2011]:
- Агент не в состоянии выполнить назначенное действие (исчерпан ресурс, действие не может быть выполнено в новых условиях изменившейся среды и др.), но переназначение действия другому агенту в теории общих планов не предусмотрено.
- Требуемое действие может оказаться невыполнимым для агентов, и тогда нужно выбирать новый план достижения цели (в теории общих намерений такая ситуация приведет состоянию "цель недостижима").
- Возникновение непредвиденной ситуации при исполнении действия (например, агент сообщил, что он начал исполнение действия, однако в ожидаемый момент не появилось свидетельств, что действие закончено).
Коллективная обработка непредвиденных ситуаций и возможность изменения сценариев вообще не рассматривается в известных работах. Более того, известные методы не рассчитаны на специфику командной работы агентов в условиях противодействия.
Языковые проблемы. Основные трудности создания коллективных систем, согласованно решающих общие задачи, носят прежде всего языковый характер.
Существует целый ряд формальных языков для описания взаимосвязанных потоков действий (работ). Это сети Петри, цепи процессов, управляемых событиями (Event-Driven
Process Chain), сети потоков работ (Workflow Net) и т.д. Общие недостатки существующих формальных языков связаны с тем, что ни один из них не обладает выразительными возможностями, необходимыми для спецификации планов командного поведения агентов. В той или иной степени для этих языков характерно:
- отсутствие явного представления данных, которые используются и порождаются потоками действий;
- ограничения на возможности обмена сообщениями и ряд других;
- слабые возможности по описанию временных аспектов, в частности, временной синхронизации процессов и игнорирование продолжительности процессов во времени;
- отсутствие возможности выбора альтернативного сценария поведения в реальном времени, если такая необходимость возникла.
Поэтому очевидно, что в теории МАС именно разработке новых языков посвящено большое количество работ. Например, в [Городецкий, 2010] предлагается следующая модель описания и планирования командной работы агентов.
Как и в теории общих намерений, для формирования команд агентов используется протокол общих намерений, определяющий обязательства и соглашения агентов команды.
Как и в теории общих планов, используются понятия группового плана и индивидуального планов, а также понятие действия. Все множество возможных планов представляется в т.н. сценарной базе знаний. При этом разные агенты могут иметь разные базы, что может отражать различие их способностей решать те или иные задачи.
Исполнение сценария командной работы есть пошаговый процесс исполнения частично упорядоченной во времени последовательности действий.
Для описания сценарных баз знаний разработан специальный язык описания процессов, который построен на основе существующих языков описания сложных процессов
("потоков работ"), разработанных для описания бизнес-процессов. При этом каждое сложное действие представляется синтаксической структурой сценарной базы знаний. На рис.6, а приведен простой пример синтаксической модели сценарной базы знаний. Здесь определено множество возможных вариантов для достижения цели X
4
из начального состояния X
1
: (A
1
A
3
A
4
), (A
2
A
3
A
4
), (A
3
A
2
A
4
), (A
3
A
1
A
4
) и (A
3
A
5
).
12