Реконфигурирование распределённых систем методами ресурсозависимой логики

Ю.С. Легович,

с.н.с., к.т.н, legov@ipu.ru,

Д.Ю. Максимов,
н.с., jhanjaa@ipu.ru
ИПУ РАН, г. Москва

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

The possibility of collective intellect explanation by a structure in the set of systems tasks is discussed. The lattice of tasks a system is able to decide is associated with a distributed or organizational system. An external product operation on the lattice elements is defined. Correspondently linear logic operations also are defined. Implication is used in system reconfiguring choice i.e. in choice of resource to new task execution. Demonstrated, that this choice may be determined by tasks lattice structure and product operation definition in many respects. The reconfiguring method use is showed at the example of robots street cleaners operation.

Введение

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

Все виды функционирования системы, как в [1-3], представляются в виде решетки с образующими из списка системных задач/целей. Объединения этих образующих будут соответствовать вариантам функционирования системы с разным набором решаемых задач, причем, чем больше задач решается в этом варианте, тем выше в решетке задач лежит соответствующее объединение. Пересечение образующих - подзадачи, действия, которые входят в разные задачи. Например, у группы роботов подзадачи движения и захвата будут входить в разные задачи системы. Наименьший элемент решетки (0) соответствует бездействию, а наибольший (true) – параллельному решению всех задач. С точки зрения ценности выполнения вышележащие элементы на диаграмме решетки оказываются более ценными, как имеющие большую степень истинности, что соответствует большей ценности более активного поведения системы, когда она решает больше задач. В работе [1] выбор исполнителя вновь возникающей задачи осуществлялся с помощью операции импликации (относительного псевдодополнения), которая определялась на решетке исходя только из ее структуры, если она была дистрибутивной (точнее брауэровой). Но не всегда решетка задач является дистрибутивной. Кроме того, хотелось бы большей гибкости в выборе решения.

В этой работе на решетке определяется умножение элементов, что позволяет определить дополнительно операции линейной логики. Эта логика ресурсозависима, т.е. ресурс (посылка) может использоваться в выводе только один раз, в отличие от классической логики [4]. Таким образом, импликация трактуется как потребление ресурса (посылки) и получение результата (заключения), что можно представить как переключение с задачи-посылки на задачу-заключение. Эта импликация является также элементом решетки и имеет некоторую степень истинности, т.е. ценности, что позволяет оценивать ценность переключения разных задач на выполнение новой задачи.

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

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

1. Метод выбора ресурса

1.1. Элементы линейной логики

Мы не будем рассматривать линейную логику в общем виде, а представим только требуемые в дальнейшем элементы ее модели в фазовом пространстве. Эта семантика линейной логики представлена в [4]. Фазовым пространством называется пара (М, ┴), где М – мультипликативный моноид и решетка, а - произвольное подмножество этого моноида. Для произвольных определено умножение и определена линейная импликация . Для определен его дуал как . Фактами называются такие , что или, эквивалентно, для некоторого . Например: , T = М = Ø^┴, 0 = T^┴ = М^┴ = Ø^┴┴. Здесь T - наибольший элемент решетки М, 0 - ее наименьший элемент, 1 - моноидальная единица, I – нейтральный элемент мультипликативной конъюнкции (см. ниже).

Легко получить следующие свойства:

, , , , .

Отсюда видно, что значением и консеквентом импликации может быть только факт.

На фактах определены решеточные дуальные друг другу операции аддитивной конъюнкции & - это решеточное пересечение: и аддитивной дизъюнкции + - это, практически, решеточное объединение: , а также мультипликативные операции – мультипликативная конъюнкция × и мультипликативная дизъюнкция, которую мы здесь обозначим ∂. Последние операции выражаются через моноидальное умножение с использованием дуальности: и . Нейтральный элемент & - T, дуальный ему нейтральный элемент + – 0. Нейтральный элемент ∂ - ┴, а дуальный ему нейтральный элемент × - I.

Множество фактов разбивается на два дуальных друг другу класса – открытых Op и замкнутых Cl фактов. Множество Op замкнуто по операциям + и ×. Ее наибольшим элементом по включению является I, а наименьшим – 0. Множество Cl замкнуто, соответственно, по & и ∂, его наибольшим элементом является T, а наименьшим - ┴.

1.2. Принципы определения умножения

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

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

Вместе с определением ┴ следует определить дуальный ему I и взаимно дуальные множества открытых и замкнутых фактов, учитывая, что &^┴ = +. И в дальнейшем, при выборе вариантов определения умножения, следует все время проверять замкнутость множества открытых фактов Op относительно операции ×. При выборе дуальных к не-фактам, следует использовать свойство .

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

1.

2.

3.

4. .

Последнее условие означает, что один и тот же факт может быть дуалом как факта, так и не-факта.

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

5. .

Это предположение естественно, поскольку мы оцениваем ценность перехода той или иной задачи-посылки импликации в задачу-заключение по значению импликации. Тогда ценность перехода в состояние полного бездействия (0) будет иметь нулевую ценность. Дополнительное условие в 5) следует из того, что 0 может быть дуалом не-факта и тогда это условие может не выполняться, что, вообще говоря, противоречит определению нейтрального элемента умножения.

Однако, моноид, который используется в линейной логике, в общем случае может содержать делители 0, т.е. произведение ненулевых элементов может быть нулевым. И действительно, как будет видно в §2, условие 5) не всегда может быть обеспечено. В таком случае, предлагается просто вычислять импликацию, используя информацию, полученную из других условий.

Рассмотрение предложенной методики на конкретном примере в §2 позволит определить еще дополнительные эвристические правила исходя из разумности предполагаемого поведения системы.

2. Управление группой роботов-дворников

Рассмотрим группу роботов-дворников, которые могут выполнять следующие задачи: x₁ – обследование территории, поиск мусора; e – вынос мусора; x₃ – распиливание выносимого предмета на части, в случае, если он слишком тяжелый. У этих задач есть подзадачи, которые не являются самостоятельными: d₁ – движение и d₃ – захват. На рис.1 представлена решетка задач такой группы роботов с образующими x₁ - x₃ и e. Как и в [1-3] объединение образующих представляет возможное параллельное выполнение задач или, в духе линейной логики [4], - возможное выполнение одной из объединяемых.

рис. 1 Решетка задач группы роботов-дворников

На этом рисунке представлено также паразитное состояние системы x₂: это ступор, в который впадает робот при невозможности выполнить распил (например, бетонного столба), или ступор при невозможности поднять предмет (невозможность выполнить вынос e). В принципе, и задачи x₁ и x₃ тоже можно представить как объединение подзадач: например, поиск мусора – это движение вместе с наблюдением d₄. В таком случае могут появиться и другие паразитные состояния. Но, во-первых, это усложнило бы решетку, а во-вторых, логично представлять задачи системы как образующие решетки.

В соответствии с принципами определения умножения (§1.2), состояние системы x₂ –является не-фактом. В качестве взаимно дуальных множеств открытых и замкнутых фактов можно выбрать, соответственно, Cl = {T, U₁₃, U_23e, C_3e, U₂₃, x₃ = ┴} и Op = {0, d₃, d₁, e, x₁, C_1e = I}. Дуалы к не-фактам следующие: x₂^┴ = x₁, C_2e^┴ = d₁, U₁₂^┴ = 0.

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

Имеем :

:

:

:

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

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

В простейшем случае не предполагается, что этот мусор потребует распила, поэтому логично предположить, что эту новую цель добавит в список своих целей кто-то из выполняющих задачу e (вынос мусора). Действительно, , а C_3e включает возможность выполнения задачи x₃, которую выполнять не предполагается. Для определения того, кто из выполняющих задачу e включит новую e в список своих целей можно воспользоваться методом, предложенным в [2,3].

Таким образом, получили еще эвристический принцип выбора возможного варианта решения:

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

Более сложный вариант мы получаем, если возможно потребуется распил.

a. В этом случае на вынос e переключается x₁, скорее всего тот, кто этот предмет нашел (т.к. он ближе всех других, выполняющих задачу x₁). В случае, если предмет поднять не удалось (из составляющих вынос e остался только захват d₃), то робот впадает в ступор – в состояние x₂ и возникает необходимость распила x₃.

Из всех состояний, x₂ с наибольшей степенью истинности переходит в d₃ - , поэтому будем считать, что этот переход происходит всегда. Далее, из всех задач именно d₃ с наибольшей степенью истинности переключается на x₃ - . Поэтому все тот же робот будет пробовать распилить предмет, который не поддается выносу. Если распил удался, то робот переходит в состояние d₃ (от задачи x₃ остается только захват), а потом переключается на вынос или продолжает пилить дальше, поскольку , и мы оказываемся в варианте a.

b. Если распил не удался, то робот впадает в ступор – в состояние x₂, из которого переходит в d₃. В этом случае возникает задача выноса e не одним исполнителем при невозможности выполнения распила x₃. Мы попадаем в вариант a, к которому добавляется исходное состояние d₃ – робот захватил предмет и держит его. В этом случае и d₃, и e имеют одинаковую степень истинности переключения на вынос – C_1e. Поэтому к роботу в состоянии d₃ подключится кто-то из выносящих мусор (e) и так до тех пор, пока не наберется достаточное для выноса число роботов.

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

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

Заключение

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

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

Таким образом, в зависимости от различных исходных предположений, можно выбирать вариант функционирования системы, что может быть полезным в анализе среды функционирования сложных систем [5, 6] и при согласовании иерархических решений [7, 8].

Литература

1. Легович Ю.С., Максимов Д.Ю. Логические модели выбора решения в самоорганизующихся системах // Проблемы управления. 2013. № 3. - С. 18-26.

2. Легович Ю.С., Максимов Д.Ю. Принятие решений в группе интеллектуальных агентов / Труды международной научно-практической конференции "Теория активных систем (ТАС-2014)". Москва-Санкт-Петербург: ИПУ РАН, 2014. - С. 206-209.

3. Легович Ю.С., Максимов Д.Ю. Решеточный подход к принятию решений в группе беспилотных летательных аппаратов / Труды 14-й Международной конференции "Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта (CAD/CAM/PDM-2014). М.: ООО "Аналитик", 2014. - С. 81-82.

4. Girard J.-Y. Linear Logic: Its syntax and semantics. // Theoretical Computer Science, 50, 1987. – P. 1-102.

5. Рожнов А. В., Кривоножко В. Е., Лычёв А. В. Построение гибридных интеллектуальных информационных сред и компонентов экспертных систем на основе обобщённой модели анализа среды функционирования // Нейрокомпьютеры: разработка, применение. 2013. №6. С. 3-12.

6. Белавкин П.А., Федосеев С.А., Рожнов А.В., Лобанов И.А. Исследование стратегической мобильности проблемно-ориентированных систем управления и их позиционирование в условиях развития информационного пространства // Известия ЮФУ. Технические науки. 2013. Тематический выпуск "Перспективные системы и задачи управления", № 3. С. 211-217.

7. Барышев П.Ф., Рожнов А.В., Губин А.Н., Лобанов И.А. Обоснование информационно-аналитической системы в развитии методов и моделей согласования иерархических решений // Динамика сложных систем — XXI век. 2014. № 3. С. 43-52.

8. Рожнов А.В., Антиох Г.М., Селиверстов Д.Е., Кублик Е.И. Системная интеграция направлений научной деятельности в условиях формирования предынтеллектуальной инфраструктуры // Информационно-измерительные и управляющие системы. 2014. № 11. С. 59-64 http://www.radiotec.ru/catalog.php?cat=jr9.