April 3rd, 2009

cartoon

Декларативное планирование revisited: темпоральная логика

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

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

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

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

Один нюанс - мы формулируем условие не в терминах системы натурального вывода, как это принято в LTL, а фактически в терминах логики предикатов. То есть, наше условие - это практически всегда условие на группе артефактов. Например - каждый модуль системы находится в репозитории, проходит юнит тест, и покрытие теста по метрике строки кода не менее 80%.

Однако, раз уж у нас стало все так формально, и условия - это предикаты, то надо точно определить то множество объектов, на котором они у нас формулируются. Множество это состоит из функций (фич), и компонентов (классов/модулей/итд). Мы воспользуемся CRC-картами, которые связывают модули и фичи. Что такое CRC-карты?

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

Class = { Function } + { Attribute }

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

Attribute = Class | простой тип или структура данных

А каждая функция/фича определяется простым текстовым описанием, и списком классов, с которыми мы должны взаимодействовать для выполнения функции

Function = Description + { Collaborator }

Collaborator = Class

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

Теперь, покажем, как мы обходимся без активностей-задач. Эта проблема решается констрейнтами, уважаемые коллеги. Временными ограничениями, висящими на "стрелках". Мы пишем на стрелке "2-3 недели" - и она означает, что "событие Б не может произойти раньше, чем через 2 недели после события А, но не позже, чем через 3 недели.

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

Ок, а что насчет назначения ресурсов? :) Видите-ли, логические условия на стрелке могут быть не только временными, но и учитывать доступность ресурсов. Любых. Достаточно сложным образом, скажем, мы можем формулировать условия на некоторые свойства ресурсов.

Что мы получили? Концептуально простую модель, не содержащую активностей, и вообще - ничего, кроме событий и логических связей между ними. Имеющую строгий математический бэкграунд. Можно в ее терминах ней думать, описывать процессы, и составлять планы. А можно применить ее в движке планирования или шедулера - открываются весьма интересные свойства. Прям дух захватывает от появляющихся возможностей.