Київський національний університет імені Тараса Шевченка

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                             М.І. ГАЛАГАН

                                                     

Планування рішень в умовах часових обмежень

 Методичний посібник з курсу  “Основи проектування баз знань“

 

 

 

 

 

 

 

 

Київ -2002

 

 

 

 

 

Методичний посібник з курсу “Основи проектування баз знань”/Упорядник Галаган М.І.;

Відп. ред. Анісімов А.В.-К.,2002.

 

Виконуєтся аналіз основних методів планування рішень, що застосовуються в штучному

інтелекті з акцентом на наявність або відсутність слідуючих характеристик: засоби

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

засоби специфікації ресурсних потреб і витрат; оптимізація ресурсних потреб і витрат;

моделювання невизначеності; оптимізація цільової функції; умовні дії, що включають

підтримку виконання певної умови. На основі аналізу процесів планування рішень

пропонуються архітектури для інтеграції цих прроцесів в інтелектуальних системах.

Приводиться класифікація найбільш відомих плануючих систем на рівні їх методологій.

 

 

Для студентів університетів та технічних вузів із спеціальностей  “Прикладна математика”,

“Інформатика ”,“ Інформаційні системи в менеджменті”.

 

 

Відповідальний редактор д-р фіз.-мат. наук, проф. Анісімов А. В.

Рецензент к. фіз.-мат. наук  Заславський Ю.А.

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗМІСТ

 

1. ВСТУП……………………………………………………………………………………………………4

2. С-ПЛАНУВАННЯ…………………………………………………………………………………….. .8

2.1. Прямий пошук в ситуативному просторі…………………………………………..8

2.2. Цілеспрямоване планування………………………………………………………...9

2.3. Система GRAPHPLAN……………………………………………………………..11

2.4. Планування, як вирішення проблеми задовільнюємості (ПЗ-планування)……..14

3. Н-ПЛАНУВАННЯ………………………………………………………………………………………15

4. D-ПЛАНУВАННЯ………………………………………………………………………………………18

4.1. Динамічне програмування………………………………………………………….18

4.2. Марківські вирішуючі процеси (МВП)……………………………………………22

4.3. Частково-спостережуючі МВП (ЧС – МВП)…………………………………..…24

5. Т-ПЛАНУВАННЯ………………………………………………………………………………………26

5.1. Представлення задач планування як задач задовільнення обмежень (ЗЗО)…….26

5.1.1 Вибір стартового часу в ЗЗО………………………………………………………27

5.1.2 Впорядкування задач……………………………………………………………….28

5.2 Розв’язання ЗЗО………………………………………………………………………29

5.2.1 Конструктивний пошук…………………………………………………………….29

5.2.2 Локальний пошук………………………………………………………………….  31

5.3 Інтервальний підхід до Т-планування (ІТ-планування)……………………………32

6. ІНТЕГРАЦІЯ ПРОЦЕСІВ ПЛАНУВАННЯ В ІНТЕЛЕКТУАЛЬНИХ СИСТЕМАХ………………   39

6.1 Планування ресурсних і метричних величин……………………………………….40

6.2 Інтеграція С&Т-планування………………………………………………………….44

6.3 Класифікація систем планування рішень……………………………………………44

7. ВИСНОВКИ……………………………………………………………………………………………….46

СПИСОК ЛІТЕРАТУРИ……………………………………………………………………………………..47

 

 

 

1.         Вступ

Фундаментально, планування є задача синтезу програми дій для досягнення множини цілей. Вона часто включає деяку множину обмежень і оптимізацію цільової функції. Як всяка програма план рішень може включати умовні дії, паралельні дії та цикли. Більшисть робіт по плануванню рішень в області штучного інтелекту (ШІ) попадають до одної з слідуючих парадигм:

·           класичне планування (С-планування);

·           ієрархічне планування в мережі задач (Н-планування);

·           планування на основі теорії рішень (D-планування);

·           планування в умовах часових обмежень (Т-планування).

В роботі виконується аналіз основних методів планування рішень, що застосовуються в ШІ з акцентом на наявність або відсутність слідуючих характеристик:

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

·           засоби спеціфікацій ресурсних потреб і витрат;

·           моделювання невизначеності;

·           оптимізація цільової функції;

·           умовні дії, що включають підтримку виконання певної умови.

Для ілюстрації процесів планування рішень ми будемо використовувати відомий в літературі з ШІ приклад задачі планування рішень гіпотетичного космічного апарату (КА), що тримає курс на віддалену планету. В процесі польоту існують часові інтервали, в яких КА може виконувати функції коммунікації і наукових спостережень (НС). Із великої кількості НС, які може виконувати КА, кожне має деяку оцінку або приорітет. Для кожного НС КА повинен бути спрямований на ціль і повинні бути виконані потрібні вимірювання або фотографування. Спрямування на ціль є досить тривала операція, яка може тривати  до 30 хвилин, в залежності від кута повороту. В результаті вибір експериментів і порядок їх виконання має значний вплив на тривалість поворотів і тому на можливу кількість виконаних експериментів. Все це ускладнюється такими факторами:

·           Оскільки існує перетин серед можливостей інструментів, а різні інструменти націлюють в різних напрямках, то вибір інструменту впливає на напрямок і тривалість повороту.

·           Інструменти перед використанням повинні бути одкалібровані, що потребує повороту на одну з можливих калібровочних цілей. Перекалібровка не потрібна, якщо послідовність спостережень виконується одним і тим же інструментом.

·           На спрямування КА використовується обмежена кількість палива, а НС потребують витрат енергії. Енергія обмежена, але може бути поповнена в кількості, яка залежить від спрямуваності сонячних батарей.

Враховуючи всі ці фактори, необхідно максимізувати кількість НС (наукову віддачу від космічної подорожі). Звичайно, ця задача не зовсім гіпотетична, вона існує для справжніх космічних  зондів,  міжпланетних КА, космічних обсерваторій і навіть для автоматизованих земних обсерваторій. Вона також подібна проблемам планування ремонтних операцій, в яких присутні каскадні множини виборів інструментів і персоналу, що впливають на тривалість і можливе упорядкування різних ремонтних операцій.

Складність цих проблем пов‘язана з тим, що вони є оптимізаційними проблемами, які вимогають безперервного часу, ресурсів, розмірності і суміші операцій вибору дій та їх упорядкування.

На жаль, існує небагато планувальників типу C, D, H, які могли б навіть представити обмеження в наведених вище проблемах. Набагато менше планувальників цих типів можуть виконувати бажаний вивід та оптимізацію.В той час як Т-планувальники краще представляють часові обмеження і ресурси, більшисть з них не має справи з виборами дій. Таким чином, для вирішення реальних проблем потрібні системи, які містять можливості C, D, H і Т-планувальників.

На основі аналізу процесів планування рішень в роботі пропонуються  архітектури для  інтеграції цих процесів в інтелектуальних системах. Виділяються також узагальнені характеристики для класифікації та співставлення різних плануючих систем – методології. Приводиться класифікація найбільш відомих плануючих систем на рівні їх методологій.

2.         С-планування.

В парадигмі С-планування задача виникає в середовищі , де V – множина  об’єктів, R – множина  відношень на V, A – множина дій. Задача визначається парою , де ,  - відповідно, моделі вихідної і цільової ситуацій. Ситуації звичайно визначаються за допомогою пар  і представляються множинами стверджуючих і заперечних літералів обчислення предикатів.

Дії середовища виконують перетворення на множині ситуацій S такі, що , де .

Розв‘язанням даної задачі буде така ситуаційна траєкторія  ,  що . Для представлення дій звичайно використовуються  параметризовані структури відомої плануючої системи STRIPS [1], що називаються S-операторами.

S-оператор включає множину передумов П, які повинні бути істинними перед виконанням дії, і множину змін або ефектів Е цієї дії на середовище. Передумови і ефекти звичайно задаються стверджуючими або заперечними предикатами, що зв’язані по типу кон’юнкції.

Розглянемо наш приклад з КА із вступу.

Використуючи S-оператори ми могли б моделювати спрощений варіант дії по цільовому повороту КА:

ПОВЕРНУТИ (?ціль):

П:  спрямування (?напрямок), ?напрямок  ?ціль,

Е:  спрямування(?напрямок), спрямування(?ціль)

 

Цей оператор має один параметр – цільову орієнтацію для повороту. Передумови потребують, щоб перед поворотом КА був спрямований в деякому напрямку, іншому, ніж цільовий. Якщо це виконується, то після операції повороту КА буде спрямований не в вихідному, а в цільовому напрямку.

Як видно з опису, ефекти оператору специфікують лише ті відношення, які змінюються в результаті виконання оператору. Так само ми можемо моделювати операції по калібровці і зйомці цілі:

КАЛІБРУВАТИ:  (?інструмент):

П:  стан(?інструмент, вкл),  ціль-калібр(?ціль),  спрямування(?ціль)

Е:  стан(?інструмент, вкл),   стан(?інструмент, калібр)

ЗНІМАТИ:  (?ціль, ?інструмент):

П:  стан(?інструмент, калібр),  спрямування(?ціль)

Е:  образ(?ціль)

 

В ряді сучасних плануючих систем використовується розширена версія мови STRIPS (відома як ADL), де дозволяється диз‘юнкція в передумовах і ефектах, умовні ефекти та обмежена універсальна квантифікація. Однак, все ще існує ряд серйозних обмежень з мовами STRIPS і ADL, таких як:

В останній час з‘явились нові розширення ADL-представлення, щоб подолати перечислені вище обмеження [2]. Всі ці розширення потребують розвитку методів С-планування. Розглянемо найбільш значимі з них.

2.1.          Прямий пошук в ситуативному просторі (ППСП).

ППСП визначає напрямок планування від вихідної до цільової ситуацій. Планувальник починає з поточної ситуації , обирає оператор, в якого виконуються всі умови в даній ситуації, і генерує нову ситуацію, додаючи до неї позитивні ефекти оператору і викреслюючи його негативні ефекти. Пошук продовжується доки не знаходиться ситуація, в якій досягаються всі цілі G. На виході формується план P, який перетворює  в G.

Малюнок 1 представляє опис цього алгоритму.

Оскільки число дій , що застосовуються,  в кожній ситуації є дуже великим, алгоритм ППСП працює в пошуковому просторі експоненсійних розмірів (, де d – максимальна довжина рішення).

В нашому прикладі з КА існує багато інструментів, вимикачів і клапанів, які можуть бути активовані в кожний момент часу. В додаток існує нескінченна кількість різних напрямків повороту КА.

Для того, щоб ППСП був ефективним необхідні такі евристики, які б забезпечували дослідження лише невеликої частини пошукового простору. По цій причині більшість плануючих систем використовували багато інших пошукових стратегій.

2.2.          Цілеспрямоване планування (ЦП).

Не так давно більшість робіт по С-плануванню було сфокусовано на генерації планів в зворотньому напрямку від цілей. Основна ідея заключається у виборі дії, яка може досягти одну із цілей і додати цю дію в поточний план. Ціль замінюється підцілями, що відповідають передумовам дії. Весь процес повторюється до тих пір, доки всі підцілі не є підмножиною вихідних умов.

Подібно ППСП цей підхід є відносно простим до тих пір, доки поточний план підтримується повністю упорядкованим. Однак, коли дії залишаються лише частково-упорядкованими, потрібен деякий облік, щоб запобігти взаємодії між неупорядкованими діями.

Алгоритм зворотнього пошуку (ЗВП) представлений на  маллюнку 2.

Алгоритм стартує від множини цілей G з множиною обмежень О  та пустим планом Р, а фінішує коли всі підцілі є підмножиною вихідної ситуації .Пункти, які починаються зі слова ВИБРАТИ, є точками “відступу назад” . Після вибору дії виникає нова множина підцілей G і нова множина обмежень .

Для реалізації обліку можливих взаємодій між неупорядкованими діями були розроблені різні стратегії [3-6].

Найбільш використовуємим є підхід, заснований на понятті причинного зв‘язку [6]. Суть цього підходу полягає в тому, що в процесі генерації плану підтримується множина причинних зв‘язків, що складається з літералів, які повинні зберігатись між відповідними діями в плані. Таким чином, при додаванні в план дії, щоб досягти окремої підцілі, додається також причинний зв‘язок для того, щоб зафіксувати той факт, що підціль зберігається між даною дією та дією, яку згенерували.

Нехай в нашому прикладі з КА наша ціль – це образ окремого астероїду,              ОБРАЗ( Астероїд ), а план вже містить дію ЗНІМАТИ( Астероїд, Камера ).          У зв‘язку з цим ми маємо підціль СПРЯМУВАННЯ( Астероїд ). Для досягнення цієї підцілі планувальник додає дію ПОВЕРНУТИ( Астероїд ). Крім того, планувальник повинен додати причинний зв‘язок щоб зберегти літерал СПРЯМУВАННЯ( Астероїд ) між дією ПОВЕРНУТИ( Астероїд ) і дією ЗНІМАТИ( Астероїд, Камера ).

Причинні зв‘язки повинні періодично перевірятись для виявлення інших дій, які можуть загрожувати їм. В цьому випадку додаються впорядковуючі обмеження на дії для ліквідації цих загроз. Для КА друга дія ПОВЕРНУТИ( в інший напрямок ) могла б загрожувати причинному  зв‘язку для першого напрямку. Тому ця дія повинна виконуватись або перед першою дією ПОВЕРНУТИ, або після дії ЗНІМАТИ.

Планувальники, які використовують цей підхід, називаються частково-упорядкуючими (ЧСУ) планувальниками [ 7-9 ].

Незважаючи на всі зусилля, спрямовані на цілеспрямоване С-планування, ці планувальники не мали великого практичного успіху.

Хоча фактор гілкування при пошуці в зворотньому напрямку значно менший, ніж в прямому, він все ще достатньо великий. Тому докладаються значні зусилля для реалізації обліку можливих взаємодій між невпорядкованими діями. У зв‘язку з цим, успіх цілеспрямованого планування, як і ППСП-планування, сильно залежить від якості евристичного управління. Цікаво, що таке управління важче виразити в парадигмі цілеспрямованого пошуку, а без якісних евристик такі планувальники звичайно обмежені у вирішенні задач, що потребують не більше дюжини дій.

ЧСУ-планування було розширене зовні парадигми С-планування.

Найбільш відомий і широко розповсюджений ЧСУ-планувальник – UСПОР [10] допускає оператори з умовними ефектами та інші виразові можливості мови ADL. Були розроблені ЧСУ-планувальники для роботи з часовими обмеженнями [11,12], метричними величинами [11] і невизначеністю [13-20].

На жаль, ці планувальники звичайно не можуть вирішувати задачі, що включають більше 20 дій.

2.3.           Система GRAPHPLAN.

В 1995 році була розроблена плануюча система GRAPHPLAN [21], яка використовує оригінальний підхід для пошуку планів. Основна ідея – виконати деякий аналіз досяжності щоб вилучити з багатьох комбінацій і послідовностей дій ті, які є несумісними.

Стартуючи з вихідних умов, GRAPHPLAN визначає множину літералів, які можливі після першого кроку, двох кроків, трьох кроків і т.д. Для першого кроку ця множина буде об‘єднанням літералів, досягаємих в ситуаціях за один крок від вихідних умов.

Для нашого прикладу КА після першого кроку міг би відзняти образ в стартовому напрямку, або спрямувати в новому напрямку. Таким чином, кожний з цих літералів належить множині, що досягається після першого кроку.

Після двох кроків в додаток до всіх літералів, що можливі після першого кроку, КА міг би відзняти образ в деякому новому напрямку, або міг би встановити зв‘язок з Землею ( якщо КА на першому кроці був спрямований на Землю ).

Після трьох кроків дані могли бути передані на Землю. Однак, не всі ці літерали є сумісними; навіть коли дозволені паралельні дії, не всі досяжні літерали могли бути досягнуті в один і той же час.

В прикладі з КА ми не можемо знімати образ у вихідному напрямку і одночасно робити поворот, оскільки дія ЗНІМАТИ потребує щоб КА залишався спрямованим у вихідному напрямку. Подібно КА не може одночасно повертати в сторону астероїду та в сторону Землі. GRAPHPLAN використовує поняття несумісності шляхом виводу бінарних взаємо-виключних (мутексних) відношень між несумісними діями та між несумісними літералами.

Правила для взаємовиключення є досить простими:

·           Дві дії є мутексні на даному кроці якщо:

-        вони мають протилежні ефекти;

-        ефект однієї дії є протилежним передумові іншої дії;

-        вони мають мутексні передумови на цьому кроці.

·           Два літерали є мутексні на даному кроці якщо:

-        вони є протилежними літералами;

-        всі дії, які досягають їх є мутексними на попередньому кроці.

 

Використовуючи ці правила, GRAPHPLAN може вивести наступне:

  1. після першого кроку неможливо одночасно бути спрямованим на Землю і на астероїд;
  2. після двох кроків неможливо ні мати образ астероїду і бути спрямованим на Землю, ні мати образ астероїду і встановлений зв‘язок із Землею;
  3. після трьох кроків неможливо мати образ астероїду і встановлений зв‘язок із Землею

Використовуючи цю просту мутексну інформацію, ціль “зняти образ астероїду та передати його на Землю” не може бути досягнута після п‘яти кроків. Вона буде досягнута лише після того, як буде згенеровано шостий рівень літералів.

Ключові особливості перших двох рівнів плануючого графу зображені на    малюнку 3.

 

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

Було показано, що GRAPHPLAN значно перевершує обговорені вище ЧСУ-планувальники на широкому колі задач. Найкращі планувальники, що використовують цю технологію, вирішують задачі, які включають біля 50 дій. Подібно ЧСУ-планувальникам технологія системи GRAPHPLAN була розширена, щоб дозволяти оператори з кванторами і умовними евристиками і інші особливості мови ADL [22-24]. Були також зроблені спроби розширення системи GRAPHPLAN, щоб дозволити планування в умовах невизначеності [25-27], але ці зусилля до сих пір не довели свою практичність. В більш пізніх роботах по системі GRAPHPLAN дозволяється обмеженe використання часу [28] і метричних величин  [29].

2.4.          Планування, як вирішення проблеми задовільнюємості (ПЗ-планування)

Основна ідея цього підходу полягає в допущенні деякої довжини плану і трансляціі проблеми планування  в множину пропозиційних формул (ПФ), а потім у вирішенні проблеми задовільнюємості  (ПЗ) даної ПФ на результуючій множині. Якщо ПФ є незадовільнюєма, довжина плану збільшується і процес повторюється.

До цього часу було розроблено декілька різних кодуючих схем [30-32], але основна ідея цих схем полягає в визначенні пропозійної змінної для:

·           кожної можливої дії на кожному кроці;

·           кожної можливої пропозиції (літералу) на кожному кроці.

Кожна дійова змінна вказує на присутність або відсутність дії на даному кроці в плані. Кожна пропозиційна змінна вказує істинна чи фальшива ця пропозіція на даному кроці. ПЗ-диз’юнкти (диз’юнкції літералів) генеруються для слідуючих обмежень:

 ВИХІДНІ УМОВИ:           пропозиції в вихідних умовах є істинні на кроці 0.

 ЦІЛІ:                                цілі є істинні на останньому кроці.

 ДІЇ:                                   кожна дія, що виконується на кроці к означає, що всі ії передумови є істинні на кроці к, і всі ії ефекти є істинні на кроці к+1.

 ПРИЧИННІСТЬ:               якщо пропозиція є фальш (істина) на кроці к і істина (фальш) на кроці к+1, то принаймні одна із дій, яка причиняє істинність (фальшивість) пропозіції, повинна виконуватися на кроці к.

ВИКЛЮЧЕННЯ:               дві несумісні дії не можуть виконуватися на одному і тому ж кроці.

Після трансляції застосовуються швидкі алгоритми для спрощення формул. Для пошуку рішень можуть використовуватись систематичні і стохастичні методи.

Найкращі ПЗ-планувальники і GRAPHPLAN-планувальники мають дуже подібні результати. Вони значно перевищують ЧСУ-планувальники на більшості проблем. Подібно ЧСУ- і GRAPHPLAN-планувальникам ПЗ-планувальники можуть бути розширені, щоб дозволяти оператори з квантифікаторами і умовними ефектами. Фактично це розширення впливає лише на процес трансляції, а не на процес вирішення. Метричні величини, подібні паливу, представляють більш серьозні труднощі. В [33] для роботи з метричними величинами використовуються методи лінійного програмування в координації з методами ПЗ-планування.

Найбільш серйозні недоліки ПЗ-планування є такі:

РОЗМІР КОДУВАННЯ.            Число змінних і диз’юнктів може бути дуже    великим, тому що всі можливі дії і пропозиції представляються точно, для кожної часової точки. В результаті ПЗ-планувальники потребують великих об’ємів пам’яті (гегобайти) навіть для проблем середніх розмірів.

БЕЗПЕРЕРВНИЙ ЧАС.           Описане вище кодування обмежується дискретним часом і тому не може мати справу з діями, що мають різні протяжності  або включають часові обмеження. Як альтернатива, може використовуватися причинне кодування [32], але воно ще не показало своєї практичності і ефективності.

3.         Н-планування

Переважно всі плануючі  системи, які було розроблено для практичних застосувань, використовують методи планування в ієрархічних мережах задач [34-35].

Основна різниця між Н-плануванням і С-плануванням полягає в тому, що Н-планування зводить задачі високого рівня до примітивних задач, в той час, як       С-планування виконує складання (синтез) дій, щоб досягти цілей. Наприклад, ціль ОБРАЗ(Астероїд)  могла б бути специфікована як високорівнева задача ЗНІМАТИ(Астероїд). Н-планування виконується шляхом рекурсивного розширення високорівневих задач в мережі задач більш низького рівня, які вирішують високорівневу задачу. Дозволені розширення описуються трансформаційними правилами, що називаються методами. В основному метод – це відображення задачі в частково упорядковану мережу задач, разом з множиною обмежень. Можливий метод для розширення задач ОТРИМАТИОБРАЗ в прикладі з КА показаний на  малюнку 4

Згідно з цим методом, задача ОТРИМАТИОБРАЗ(?ціль, ?інструмент) може бути замінена за допомогою частково-упорядкованої мережі з трьох задач: ПОВЕРНУТИ(?ціль), КАЛІБРУВАТИ(?інструмент), ЗНІМАТИ(?ціль, ?інструмент) і додатковим обмеженням, щоб пропозиція СПРЯМУВАВ(?ціль) підтримувалась між повернути і знімати образ. Після кожного розширення            Н-планувальник виконує пошук конфліктів серед задач мережі. Вирішення конфліктів виконується за допомогою програм, що називаються критиками, які вводять додаткові обмеження упорядкування і комбінують або вилучають водночас неможливі дії. Планування завершується, коли результуюча мережа містить лише примітивні задачі і множина обмежень сумісна.

На малюнку 5 представлений псевдокод алгоритму Н-планування.

ВИБРАТИ  вказує на точку “відступу назад”.

Час і метричні величини не представляють труднощів для Н-планувальників. Ці обмеження можуть бути специфіковані всередині програм-методів і можуть перевірятись на сумісність разом з обмеженнями упорядкування і захисту. Існує декілька Н-планувальників, які забезпечують роботу з часовими і метричними обмеженнями [34]. Відносно легко інтегрувати Н-планувальник з системою складання розкладів (Т-планувальником) – коли мережа задач зведена до примітивних задач, Т-планувальник може використовуватись для того, щоб оптимізувати порядок результуючої мережі.

Найбільшою силою Н-планування є те, що пошук може бути щільно контрольованим за рахунок ретельної розробки методів.

В С-плануванні передумови і ефекти дії специфікують при яких умовах дія може використовуватись і чого вона може досягти. В Н-плануванні методи точно специфікують які комбінації дій повинні використовуватись для окремих цілей.

Інакше кажучи, Н-планувальнику говорять (підказують) як використовувати дії, в той час як С-планувальник повинен це визначати із опису дії.

Існує два принципові недоліки Н-планування:

4.         Д-планування.

На протязі багаьох років дослідники в області теорії прийняття рішень і дослідження операцій моделювали процеси прийняття послідовностей рішень, використовуючи математичні моделі динамічного програмування, Марківських вирішуючих процесів і частково-спостережуємих Марківських вирішуючих процесів.

Оскільки останнім часом зросла зацікавленість у використанні цих моделей для планування рішень в інтелектуальних системах, розглянемо їх більш детально.

4.1.          Динамічне програмування (ДП).

ДП – це метод дослідження операцій, в яких процес прийняття рішень може бути розбитий на окремі кроки. Такі операції називаються багатокроковими.

Початок розвитку ДП відноситься до 50-х років минулого століття і пов‘язаний з ім‘ям американського математика Белмана.

Розглянемо загальну постановку задачі ДП.

Припустимо, що управління деякою системою (об‘єкт управління) можна розбити на n кроків, які переводять систему з вихідної ситуації S0 в цільову ситуацію  Sg. Рішення приймаються послідовно на кожному кроці, а управління, що переводить систему із S0  в Sg, представляє собою сукупність n покрокових управлінь (рішень).

Позначимо через Pk рішення на k-тому кроці (k = 1,2,3,.....,n).

Змінні Pk задовольняють деяким обмеженням і в даному сенсі називаються допустимими.

Нехай P( P1, P2,…….., Pn ) – план рішень, що переводить систему із ситуації S0 в ситуацію Sg.

Ситуація Sk – ситуація після k-того рішення.

Отримуємо послідовність ситуацій: .

Цільова функція (показник ефективності) багатокрокової операції, що розглядається, залежить від вихідної ситуації і плану рішень P:

                                                  Z= F(S0, P)                                                            (4.1)

Зробимо ще декілька припущень:

1.      Ситуація  Sk після k-того кроку залежить тільки від попередньої ситуації і рішення Pk на k-тому кроці, і не залежить від попередніх ситуацій і рішень:

                                               Sk= jk( Sk-1, Pk ), k = 1,2,….,n                                 (4.2) 

                 Рівняння  (4.2) називаються ситуативними рівняннями.

2.      Цільова функція (4.1) є аддитивною від показника ефективності на кож-

      ному кроці:                     

                                               Zk=fk(Sk-1,Pk),k = 1,2,……n                                    (4.3)

      тоді                                                                     (4.4)

З урахуванням зроблених припущень задача динамічного програмування (покрокової оптимізації) може бути сформульована наступним чином: необхідно визначити такий допустимий план рішень P, що переводить систему із ситуації S0 в ситуацію Sg, при якому цільова функція приймає найбільше (або найменше) значення.

Особливістю моделі ДП є багатокроковість процесу оптимізації плану рішень. При цьому необхідно дотримуватись наступного принципу оптимальності Белмана:

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

Згідно з принципом оптимальності, рішення на  n-ному кроці потрібно обирати таким чином, щоб для будь-яких ситуацій Sn-1 отримати на цьому кроці максимум цільової функції.

Позначимо через максимум цільової функції на n–ному кроці при умові, що до початку останнього кроку система була в довільній ситуації Sn-1, а на останньому кроці рішення було оптимальним.

 називається умовним максимумом цільової функції на n–ному кроці. Очевидно, що:

                                                                            (4.5)

Максимізація ведеться по всім допустимим рішенням Pn. Рішення Pn, при якому досягається  також залежить від Sn-1, позначається через Pn(Sn-1) і називається умовно-оптимальним рішенням на n–ному кроці.

Нехай - умовний максимум цільової функції при оптимальному управлінні на  (n – k +1) кроках, починаючи з k-того кроку і до кінця при умові, що до початку k-того кроку система знаходиться в ситуації Sк-1. Фактично цю функцію можна задати наступним чином:

                         , тоді

                         .

 

Цільова функція на (n-k) останніх кроках при довільному рішенні Pk на k-тому кроці і оптимальному управлінні на послідуючих (n-k) кроках дорівнює   .

Згідно принципу оптимальності, рішення Pk обирається з умови максимуму цієї суми

       , k=n-1,n-2,..2,1.         (4.6)

Рішення Pk на k-тому кроці, при якому досягається максимум в (4.6), позначається  і називається умовно-оптимальним рішенням  на k-тому кроці ( в праву частину рівняння (4.6) потрібно замість Sk підставити вираз   із ситуаційних рівнянь.

Рівняння (4.6) називають рівняннями Белмана. Вони дозволяють знайти попереднє значення функції, знаючи послідуючі.

Якщо з рівняння (4.5) знайти , то при k = n-1 з рівняння (4.6) можна визначити вирази для  і відповідні їм , розв‘язавши задачу максимізації для всіх можливих значень Sn-2.  Далі, знаючи  і використовуючи рівняння (4.6) та (4.2), знаходимо ситуаційні рівняння.

Процес розв‘язання рівнянь (4.5) та (4.6) називається умовною оптимізацією.

В результаті умовної оптимізації отримаємо дві послідовності:

                     , ,......, ,    та

                     , ,......,,  .

Використовуючи ці послідовності, можна знайти розв‘язок задачі ДП при даних     n та S0 .

По визначенню, умовний максимум цільової функції за n кроків, при умові, що до початку 1-го кроку система була в ситуації S0 , Zmax = .

При фіксованому S0 отримаємо . Далі з рівняння (4.2) знаходимо  і підставляємо цей вираз у послідовність умовно-послідовних рішень:  і так далі по ланцюгу:

               

Отримаємо оптимальний розв‘язок задачі ДП :

                   

стрілка ® означає використання ситуаційних рівнянь, а стрілка Þ - послідовність умовно-оптимальних рішень.

4.2.           Марківські вирішуючі процеси (МВП).

МВП відрізняються від процесів детерміністичного С-планування по-перше тим, що включають ймовірнісні дії, а по-друге тим, що припускають повну спостерігаємість ефектів дій.

Таким чином, при визначенні МВП, задаються:

·        Ситуативний простір S;

·        Дії A(s) Í A, що застосовуються в кожній sÎS;

·        Перехідні ймовірності Pa(S’ êS) для sÎS та  aÎA(s);

·        Вартості застосування дій C(a,s)>0

·        Множина цільових ситуацій G Í S.

Ситуації, які виникають в результаті застосування дії , не є передбачуваними, але є спостережними і забезпечують зворотній зв‘язок для вибору наступної дії . Розглянемо наступний приклад. Припустимо, що знімаюча камера в КА має липку заслонку, яка іноді не відкривається. Таким чином, коли КА робить спробу знімати образ в окремому напрямку, цей образ може бути отриманий або ні. Частини МВП для цього сценарію показані на малюнку 6.

Розв‘язання МВП є не послідовність дій, а функція , яка відображує ситуації s в дії aÎA(s). Така функція називається політикою. Політика  встановлює ймовірність кожній ситуативній траєкторії s0, s1, s2,…., яка стартує в ситуації s0 і задається добутком ймовірностей переходу  з .

 

Припускається, що дії в цільовій ситуації не мають вартості  і  не виконують змін.  ( тобто, C(a,s) = 0  і  Pa(s ês) = 1, якщо  sÎG ).

Очікувана вартість, асоційована з політикою , яка починається в стані s є середньою ймовірністю таких траєкторій, помножених на їх вартість    .

Оптимальним рішенням буде політика , яка мінімізує очікувану вартість для всіх станів sÎS.

МВП традіційно вирішуються потужними методами, які називаються ітерація оцінки вартості і ітерація політики [35]. Ці методи знаходять оптимальні політики для МВП, що представлені в умовних планах. Умовні плани специфікують, яку дію треба вибирати в кожній можливій ситуації МВП.

Принциповою перешкодою щодо використання МВП для планування є великий розмір пошукового простору. Якщо КА має 50 перемикачів, кожен з яких може бути включеним або виключеним, то існує  можливих ситуацій тільки для самих перемикачів. Тому багато робіт по застосуванню МВП для планування в інтелектуальних системах зконцентровано на обмеженні розмірів ситуаційного простору.

Моделі МВП  успішно застосовувались для планування в деяких ретельно описаних галузях. Зокрема вони довели свою корисність у навігаційних задачах для роботів, де є невизначеність у локалізації і орієнтації робота після переміщення [36].

Крім великих розмірів ситуаційного простору існують деякі інші перешкоди щодо використання МВП:

Крім того, оптимальні політики часто важко зрозуміти. Для людини краще мати більш компактний план, який покриває лише найбільш критичні або найбільш ймовірні випадки.

4.3.          Частково-спостережувані Марківські вирішуючі процеси (ЧС-МВП).

ЧС-МВП узагальнюють МВП, дозволяючи ситуаціям частково-спостережуємими [37].

Інформація про ситуацію надходить від спостережень o, ймовірності яких Pa(о|s) залежать від виконаної дії a і результуючої ситуації s.

Додатково, апріорний ймовірнісний розподіл над ситуаціями кодує апріорну довіру про вихідну ситуацію, яка більше не припускається спостережуваною або відомою.

Таким   чином,  ЧС-МВП  характеризується  елементами  МВП,   інформацією  про невизначеність вихідної ситуації та сенсорною моделлю у формі:

·        вихідна довірча ситуація b0;

·        множина О спостережень о з ймовырностями Pa(o|s).

Ймовірності Pa(o|s) виражають ймовірність виконання спостереження о в ситуації s після виконання дії а. Ці ймовірності повинні визначатись для кожної ситуації s і дії aÎA(s), а в сумі повинні дорівнювати одиниці, тобто:

                                        .

Оскільки зворотній зв‘язок від середовища в ЧС-МВП  є частковий, ситуація, в якій знаходиться система, звичайно невідома, а тому політики, які відображують ситуації, в дії не застосовуються.

Вирішення ЧС-МВП приймає  форму функції, яка відображає довірчі ситуації в дії, причому довірчі ситуації є ймовірністними розподілами над реальними ситуаціями середовища.

Ефекти дій на довірчих ситуаціях є повністю передбачуваними. Довірча ситуація ba, яка є результатом виконання дії  а в довірчій ситуації b, може бути отримана наступним чином:

                                                                                  (4.7)

При відсутності спостережень, ЧС-МВП  зводиться до детерміністичної проблеми в довірчому просторі, де задача полягає у знаходженні послідовності дій, яка відображує вихідну довірчу ситуацію b0 в заключну довірчу ситуацію bf  з діями a, які відображують одну довіру b в довіру-спадкоємця ba згідно (4.7).

Ми беремо заключні довірчі ситуації як довіри, що роблять ціль визначеною, тобто довіри, для яких bf (s) = 0 для всіх  sÏG, або простіше bf (G) = 1.

Можуть використовуватись і інші множини заключних ситуацій, наприклад, довіри bf, які роблять ціль дуже подібною ( bf (G) ³ 0.9 ) і так далі.

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

Ймовірність отримання о, ba(о), визначається за формулою:

                                                                             (4.8)

Подібно (4.8),  ймовірність того, що ситуація належить s після виконання дії а в довірчій ситуації b при спостереженні о:

 

                                                                       (4.9)

Ці вирази витікають з моделей дій та сенсорів, а також з правила Байєса.

Таким чином, при наявності спостережень, дії мають ймовірністні ефекти на довірчих ситуаціях; ЧС-МВП зі спостереженнями вже є не детерміністичною проблемою в довірчому просторі, а МВП на довірчому просторі [37- 38].

Розв‘язання ЧС-МВП зводиться до розв‘язання  довірчої МВП: політика, яка відображує такі довірчі ситуації в дії така, що очікувана вартість переходу від вихідної ситуації b0 до заключної ситуації bf мінімальна.

Проблема планування зі спостереженнями [39] може бути сформульована як      ЧС-МВП, вирішенням якої є політики, що відображують довірчі ситуації в дії. В літературі по ШІ такі політики представляються умовними планами, тобто послідовними планами, розширеними за допомогою тестів та гілкувань [21, 27, 39].

5.         Т-планування.

Процес Т-планування в ШІ має такі особливості:

·        Виводи про час і ресурси є коренем Т-планування;

·        Задачі Т-планування майже завжди включають оптимізаційні підзадачі;

·        Задачі Т-планування включають невелику фіксовану множину операцій вибору дій і вимагають значних зусиль з приводу їх впорядкування.

Найбільш загальний підхід для розв’язання задач  Т-планування полягає в  їх представленні у вигляді задач задоволення обмежень (ЗЗО) із застосуванням загальних методів їх розв’язання.

5.1.          Представлення задач Т-планування як ЗЗО.

ЗЗО формально описуються множиною рішень і множиною обмежень на комбінації рішень.

Рішення описуються в термінах змінних, кожній з яких може бути присвоєне значення з області її значень. Обмеження описуються в термінах відношень, що встановлюють які з комбінацій значень змінних є істинними.

Існує два підходи для представлення задач Т-планування у вигляді ЗЗО:

·        Встановлення стартового часу для кожної задачі таким чином, щоб виконувались всі часові та ресурсні обмеження;

·        Встановлення обмежень впорядкування на задачі таким чином, щоб виконувались всі часові та ресурсні обмеження.

5.1.1.      Вибір стартового часу в ЗЗО.

Перший підхід представлення задачі Т-планування у вигляді ЗЗО полягає у наступному:

·        встановлення змінної, що представляє стартовий час кожної задачі в дискретному інтервалі – плануючому горизонті;

·        специфікація обмежень задачі шляхом упорядкування задачі (наприклад, якщо задача А повинна приходити перед задачею В, то старт задачі В повинен бути не раніше, ніж старт плюс протяжність задачі А);

·        специфікація обмежень для кожної часової точки і кожного ресурсу таким чином, щоб загальне використання ресурсу всіма активними в цій точці задачами не превищувало потужності цього ресурсу.

Тоді рішення приймають форму встановлення стартового часу для кожної задачі.

Для багатьох складних ресурсних проблем, в яких потужність і використання ресурсу змінюються з часом, цей підхід є фаворитним представленням. Також він дає можливість точно визначити залишок ресурсу для кожної часової точки.

Однак, існують також обмеження через необхідність фіксації точного часу для кожної задачі та залежності множини виборів від числа часових кроків.

Множина можливих виборів є суттєво великою не через реальне число виборів, а через велику кількість можливих встановлень задач в часових точках.

Цей підхід потребує визначення атомних часових кроків перед розв’язанням задачі, і розмір представлення залежить від дискретизації часу.

5.1.2.      Впорядкування задач.

В основі другого підходу  представлення задачі Т-планування у вигляді ЗЗО лежить ідея, яка полягає в тому, що дві впорядковані задачі не конкурують на одному й тому ж ресурсі.

Визначивши впорядковуючі змінні для пар задач, отримаємо представлення наступних обмежень:

·        булеву змінну для кожної впорядкованої пари задач, яка показує, що перша приходить перед другою;

·        обмеження на впорядковуючі змінні, які кодують як попередньо існуючі обмеження, так і відповідний порядок задач, на основі встановлення значень цих змінних;

·        обмеження на визначення можливих стартових часів (МСЧ) для кожної задачі, основані на впорядкуванні;

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

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

Підтримка сліду МСЧ для кожної задачі служить двом цілям. По-перше, може бути визначене впорядкування, яке порушує заданий часовий інтервал.Це можливо тоді, коли множина МСЧ для задачі стає пустою. По-друге, підтримка МСЧ дає можливість визначити чи існує загроза для ресурсів, які були виділені, і , якщо немає, гарантувати істиність фінального плану.

Підтримка МСЧ є відносно простою. Фактично, в більшості підходів використовується алгоритм Форда [40], або інші методи дослідження операцій, які визначають множину МСЧ для кожної задачі в заданій множині частково-впорядкованих задач.

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

Майже для будь-якої задачі Т-планування, результуючий пошуковий простір є значно меншим, ніж при першому підході.

Представлення на основі впорядкування задач не залежить також від часової дискретизації. При цьому представленні, впорядкування задач виконується до тих пір, поки система може гарантувати, що ресурси не перевикористані. Однак, коли ресурсні величини стають складнішими, верифікація ресурсів стає теж складнішою.

5.2.          Розв’язання ЗЗО.

Існує дві категорії алгоритмів розв’язання ЗЗО:

·        конструктивний пошук;

·        локальний пошук.

При конструктивному пошуці циклічно виконується вибір і встановлення значення змінної; перевірка обмежень; відступ назад при порушенні обмежень.

При локальному пошуці спочатку виконується встановлення значень всіх змінних, а потім робиться спроба “відремонтувати” порушені обмеженні шляхом зміни значення змінної в одному з обмежень.

5.2.1.      Конструктивний пошук.

На малюнку 7 представлений простий алгоритм конструктивного пошуку для розв’язання ЗЗО.

На кожному рівні алгоритму виконується вибір та встановлення значення змінної і рекурсивний виклик самого себе на конкретизованій версії ЗЗО.

Якщо вибране значення змінної несумісне, то процедура зазнає невдачі і виконується хронологічний відступ назад. Пунктами відступу назад є оператори Вибрати.

Цей алгоритм складається з декількох компонентів:

·        впорядкування змінних;

·        впорядкування значень змінних;

·        стратегія розповсюдження обмежень;

·        стратегія відступу назад.

У впорядкуванні змінних найбільш відомою евристикою є мінімум залишившихся значень (МЗЗ), яка обирає змінну з найменшим числом залившившихся значень. На жаль, для Т-планування, де змінними є впорядковані рішення, МЗЗ допомагає мало.

Більш ефективними для цих задач є евристики, приведені в [41], які впорядковують змінні у відповідності з шириною стартового вікна задачі та перетином між часовими інтервалами.

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

Механізм розповсюдження обмежень виводить нові обмеження в результаті встановлення значення змінної. В діапозон стратегій розповсюдження обмежень входять як прості стратегії швидкої перевірки сумісності, подібні “перевірці вперед”, так і потужні, але вартісні стратегії К-сумісності, які можуть виводити нові К-містні обмеження серед залишившихся змінних.

Алгоритм конструктивного пошуку, приведений на малюнку 6, виконуё хронологічний відступ назад, коли поточне встановлення змінної приводить до невдачі.

Існує багато інших алгоритмів конструктивного пошуку для ЗЗО [42-45], які ідентифікують змінні, відповідні за невдачу і відступають назад на відповідний рівень.  

5.2.2.       Локальний пошук.

Локальний пошук звичайно починається з повного встановлення значень змінних, навіть незважаючи на те, що деякі обмеження можуть бути порушені. Поступово, модифікуючи встановлення шляхом зміни деяких, або всіх значень змінних досягається розв’язання ЗЗО.

В процесі пошуку генерується “сусідство” нових встановлень, виконується їх ранжування і вибір найкращої. Кожна з цих дій називається рухом.

Оскільки ефективність цього підходу сильно залежить від вихідного встановлення, після відповідного числа рухів і невдачі знайти розв’язок, генерується нове вихідне встановлення і т.д.

Кожний цикл, який включає генерацію вихідного встановлення і виконання ряду рухів, називається спробою.

Після достатньої кількості невдачних спроб процес завершується з визнанням загальної невдачі.

Алгоритм локального пошуку зображено на малюнку 8.

Малюнок 8 описує сімейство алгоритмів локального пошуку.

Для того, щоб конкретизувати алгоритм, необхідно специфікувати процедури генерувати сусідів, ранжувати сусідів, відібрати сусіда. Ефективність алгоритму ЛП залежить від цих процедур.

5.3.          Інтервальний підхід до задач Т-планування.

Розглянуте раніше STRIPS-представлення задачі С-планування використовує дискретну модель часу, в якій всі дії припускаються миттєвими, або, в крайньому разі, з однаковою протяжністю. Однак, як вже говорилось, ЧСУ-планування не залежить від даного припущення, і дії можуть бути довільної протяжності.

Система DEVISOR [11] була першим ЧСУ-планувальником, в якому дії та цілі могли бути обмежені довільними часовими інтервалами.

Окрім системи DEVISOR  відомі ще декілька ЧСУ-планувальників [12,46-48], які використовують інтервальне представлення для дій і фактів, а також методи задовільнення обмежень для управління цими інтервалами.

Будемо посилатися на цей підхід як на ІТ-планування.

Ідея використання інтервалів для представлення часу в ШІ була вперше введена Алленом [49], який описує середовище стверджуючими пропозиціями на деякому часовому інтервалі. Так само, дії та події мають місце на часових інтервалах.

Обмеження між інтервалами описують відношення між діями (подіями) і пропозиціями, які повинні мати місце перед і після. Наприклад, будемо говорити, що КА виконує поворот на астероїд А37 на деякому інтервалі І, і позначати як ПОВОРОТ(А37)І. Подібно, будемо говорити, що КА спрямований на астероїд А37 на часовому інтервалі J, і позначати як СПРЯМУВ(А37)J.

Дотримуючись [50], будемо використовувати термін часово-кваліфіковане твердження (ЧКТ), посилаючись на пропозицію, дію або подію, що має місце на інтервалі.

Аллен ввів 7 інтервальних відношень ( та їх інверсії ), які використовуються для того, щоб описати відношення між інтервалами. Вони приведені на малюнку 9.

Використовуючи дані інтервальні відношення, можемо описати яким чином дії (події) впливають на середовище. Наприклад, інтервали і обмеження, імпліковані оператором ЗНІМАТИ в прикладі з КА, могли б бути:

$Р { стан(?інструм, калібр)Р^ містить(Р,А)}

ЗНІМАТИ(?ціль, ?інструмент)А®& $Q { спрям(?ціль)Q^ містить(Q,A)}

                                                       &$R { образ(?ціль)R^ зустрічає (R,A)}

Ця аксіома проілюстрована на малюнку 10 й стверджує:

Якщо існує дія ЗНІМАТИ(?ціль,?інструмент) на інтервалі А, то стан(?інструм, калібр) і спрям(?ціль) повинні мати місце на інтервалах P і Q, які містять дію ЗНІМАТИ, а образ(?ціль) буде мати місце на деякому інтервалі R, що настуапає безпосередньо після дії.

Інтервальне представлення дає більшу гнучкість та точність в специфікації часових відношень, ніж STRIPS-оператори. Наприклад, можемо специфікувати, що передумова потрібна лише для першої частини дії, або для всієї дії. Можемо також специфікувати, що дві дії повинні виконуватись одночасно, щоб досягти деякої умови, або що є певні часові обмеження на цілі, дії, або події.

Хоча квантифіковані логічні вирази, що приведені вище, є дуже загальними, вони дещо громіздкі та не зовсім зрозумілі. А тому, в [48] була розроблена скорочена форма для специфікації аксіом, в якій інтервали існують не прямо, а побічно. Наприклад, аксіома КАЛІБРУВАТИ (?інструмент) може бути специфікована в скороченій формі таким чином:

КАЛІБРУВАТИ (?інструмент)    зустрінутий     стан(?інструм, вкл)

                                                            вміщений          калібрціль (?ціль)

                                                            вміщений          спрямув (?ціль)     

                                                            зустрічає           стан(?інструм, калібр)

Ця аксіома означає:

коли існує інтервал, в якому виконується дія КАЛІБРУВАТИ(?інструм), то існують також і інші інтервали, в яких містяться стан(?інструм,вкл), калібрціль(?ціль), спрямув(?ціль) і стан(?інструм, калібр); ці інтервали мають вказані відношення з інтервалом для дії КАЛІБРУВАТИ.

ІТ-планування виконується дуже подібно до ЧСУ-планування, що було розглянуте раніше. ІТ-планувальник працює в зворотньому напрямку від цілей, додаючи нову ЧКТ-дію в план, в який, в свою чергу, додається нова ЧКТ-підціль з інтервальними обмеженнями. 

В процесі ІТ-планування можуть виникати додаткові обмеження впорядкування між ЧКТ для того, щоб ліквідувати конфлікти.

Якщо в плані немає недосягнутих підцілей і конфліктів, то план є повним. Відступи назад виконуються в тому випадку, коли неможливо досягти окремої підцілі, або задовольнити обмеження.

Недетерміністичний алгоритм ІТ-планування зображено на малюнку 11.

Розглянемо роботу алгоритму ІТП на прикладі з КА, де ціллю є  отримати образ астероїду А37. Спочатку модель включає інтервали для кожної з вихідних та цільових умов. Це зображено на малюнку 12.      

Однак початкова модель ще не має обмежень на кінець інтервалів для вихідних умов і на початок цільової умови. Оскільки немає причинного зв’язку для цілі Образ А37, ЧКТ для цієї цілі обирається алгоритмом. В нашому прикладі існує лише один спосіб досягти ЧКТ – додати дію ЗНІМАТИ. Відповідно з обмеженнями, дія ЗНІМАТИ повинна бути вміщена інтервалом, в якому КА спрямований на цільовий астероїд, а також інтервалом, в якому інструмент (ще не конкретизований) був би калібрований. Ці два інтервали додаються в план разом з відповідними обмеженнями.

На цій стадії роботи алгоритму можемо також вивести, що інтервал для спрямув(А37) повинен бути після інтервалу спрямув(Земля) зустрічає минуле, тому що КА не може бути спрямований більше, ніж в одному напрямку одночасно. Результуючий частковий план зображено на малюнку 13.

Тепер маємо два ЧКТ без причинних зв’язків. Для того, щоб досягти спрямув(А37), повинен бути введений крок ПОВЕРНУТИ, а щоб досягти стан(?інстр,калібр), необхідно ввести крок КАЛІБРУВАТИ. Обмеження, пов’язані з цими кроками, спричиняють введення деяких додаткових ЧКТ, як показано на малюнку 14.

 

 

 

 

 

На цій стадії ще неможливо нічого вивести про часові відношення між спрямув(?калібрціль) та іншими трьома ЧКТ-спрямуваннями, оскільки ще не визначено які з цілей (А37, Земля, ?напрямок) є можливо каліброваними.

Однак можемо вибрати декілька пар інтервалів для зв’язування на цій стадії. Зокрема, можемо зв’язати інтервали калібрціль(?калібрціль) та стан(?інстр,вкл) з інтервалами вихідних умов, а також спрямув(калібрціль) та спрямув(?напрям). результуючий частковий план вказаний на малюнку 15.

Тепер лише спрямув(Т17) залишається без причинного зв’язку і може бути досягнуте лише введенням іншого кроку ПОВЕРНУТИ. Після додавання цього кроку та інтервалів, потрібних для задовільнення обмежень для дії ПОВЕРНУТИ, єдиний недосягнутий інтервал може бути зв’язаний з вихідними умовами щоб видати заключний план, показаний на малюнку 16.

ІТ-планувальники можуть розглядатись як динамічні машини для задовільнення обмежень. Вони циклічно додають в мережу нові ЧКТ і обмеження, а після цього використовують методи задовільнення обмежень для розповсюдження ефектів цих обмежень і перевірки сумісностей.

На сьогодні ІТ-планування ще широко не вивчене і серйозно не порівняне з іншими методами планування.

 

На основі інтервального підходу було розроблено декілька плануючих систем. Найбільш практичними є IxTeT [47] і HSTS/RA [48], які застосовувались для розв’язання реальних космічних проблем та генерували складні плани, які включали повороти, спостереження, навігацію, комунікації та інші аспекти космічних операцій, враховуючи обмежені ресурси, протяжність задач і часові обмеження.

6.         Інтеграція процесів планування в інтелектуальних системах.

В  попередніх розділах розглядались різні методи планування, а також було продемонстровано їх застосування в прикладі з КА. Цей приклад потребує застосування як методів С-планування з їх потужними механізмами вибору дій, так і методів Т-планування для впорядкування дій.

Подібно задачам Т-планування, приклад з КА включає часові обмеження, дії з різною протяжністю, ресурси, числові величини і оптимізацію. Однак цей приклад вимагає також і вибору дій – вибір окремого спостереження призводить до вибору інструменту для його реалізації, а вибір інструменту в свою чергу призводить до вибору каліброваної цілі.

Більшість методів С-планування не взмозі працювати з ресурсними та числовими змінними або з неперервним часом. Багато методів ігнорують оптимізацію.

Як вже зазначалося раніше, останнім часом були зроблені спроби розширити методи С-планування для того, щоб мати справу з ресурсними змінними [51], метричними величинами [12, 29, 33], і дозволити оптимізаційний критерій [33].

Відомі також спроби розширити С-планування для того, щоб мати справу з неперервним часом і часовими обмеженнями [11, 12, 28, 47, 48].

У цьому розділі розглянемо деякі методи інтеграції процесів планування в інтелектуальних системах.

6.1.          Планування ресурсних і метричних величин.

Термін ресурс використовується в ШІ для того, щоб посилатись на ряд різних речей від дискретно-розділяємих засобів ( група ідентичних машин на заводі ) до неперервних числових величин, які бувають витратними та оновлюємими ( подібно паливу).

В Т-плануванні ресурси часто класифікують як одномісні та багатомісні. Одномісні ресурси не викликають ніяких спеціальних труднощів для більшості формалізмів планування. Якщо дві дії потребують одного й того ж ресурсу, вони конфліктують і не можуть перетинатись. В рамках ЧСУ-планування це реалізується додаванням впорядкуючих обмежень між діями, які можуть перетинатись.

В GRAPHPLAN будь-які дії з ресурсними конфліктами можуть розглядатись як взаємовиключні, або мутексні, і цього достатньо для того, щоб запобігти їх паралельному виконанню.

В ПЗ-плануванні можуть бути додані взаємовиключні аксіоми для кожної пари дій з ресурсними конфліктами в кожній часовій точці.

Планування багатомісних ресурсів більш складне , зважаючи на дві причини:

·        важче ідентифікувати групи дій з потенціальними ресурсними конфліктами;

·        кількість способів для вирішення конфліктів зростає експоненційно з числом конфліктуючих дій.

Ці ж питання виникають і при Т-плануванні.

Система О-ПЛАН використовує оптимістичні і песимістичні методи [51] для того, щоб ідентифікувати і вирішити багатомісні ресурсні конфлікти.

Планувальник IxTeT [47] використовує пошук на графах для ідентифікації багатомісних конфліктів. Після ідентифікації додається диз’юнкція впорядкуючих обмежень для вирішення конфліктів.

Метричними величинами в прикладі з КА є напрямок спрямування КА і кількість палива, що залишилось.

Труднощі з метричними величинами полягають в тому, що коли виконується дія, то зміна однієї метричної кількості є функцією від зміни іншої. Наприклад, в операції ПОВЕРНУТИ кількість палива, що витрачається на поворот КА є функцією вуглової відстані між поточною та цільовою орієнтацією КА.

Існує доволі простий підхід – розширити передумови та ефекти дій обмеженнями рівності та нерівності, які вимагають арифметичні та функціональні вирази.   Згідно з [29], можемо описати операцію ПОВЕРНУТИ наступним чином:

 

ПОВЕРНУТИ(?ціль):

         П: СПРЯМУВ(?напр), ?напр ¹?ціль,

              паливо ³ вугол(?напр,?ціль) / ВИБРАТИ;

        Е: ù СПРЯМУВ(?напр), СПРЯМУВ(?ціль),

             Паливо -= вугол(?напр,?ціль) / ВИБРАТИ.

 

Нерівність в передумовах специфікує, щоб поточний запас палива був достатнім для повороту КА на бажаний вугол. Рівність в ефектах специфікує, щоб результуючий запас палива буде зменшений на величину, яка потрібна для повороту КА. Зауважимо, що в даному представленні не було специфіковано яким чином змінюється кількість палива в процесі повороту, а лише специфіковувалось скільки повинно бути палива до та після повороту.

Для багатьох цілей таке представлення достатнє. Але якщо двом діям дозволити використовувати одну метричну величину одночасно, необхідно описати яким чином вона змінюється в процесі дії.

Більшість планувальників використовують просте дискретне представлення метричних величин і не дозволяють паралельних дій, що впливає на одну й ту саму метричну величину [29,33,34]. Але існує декілька планувальників, подібних  ZENO [52], які використовують більш детальне представлення змін метричних величин відносно часу.

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

Найпростіший підхід – ігнорувати метричні обмеження до тих пір, поки значення змінних не будуть точно відомі. В цей час робиться перевірка обмежень на задовільнюємість. Якщо обмеження не задовільняються, то робиться відступ назад. Наприклад, для дії ПОВЕРНУТИ, перед тим як перевіряється її передумова, повинні бути відомі поточна і цільова орієнтації КА, запас палива і його витрати. Такий пасивний підхід реалізується в  [11].

Деякі планувальники [12,33] роблять спробу перевірити сумісність метричних нерівностей, навіть перед тим, як відомі всі значення змінних. Вони типово обмежують свій аналіз на підмножині лінійних метричних нерівностей, використовуючи методи лінійного програмування (ЛП).

Один з таких планувальників – ZENO – є ЧСУ-планувальником, який неперервно перевіряє метричні обмеження, використовуючи комбінацію Гаусового виключення для рівнянь і Симплекс-алгоритм для нерівностей.

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

Останні зусилля по плануванню з метричними нерівностями призвели до створення планувальника LPSAT [33].

LPSAT використовує методи ЛП в інтеграції з ПЗ-плануванням. Проблема планування представляється як проблема задовільнюємості (ПЗ), за виключенням того, що метричні передумови та ефекти замінюються тригерними змінними в ПЗ-кодуванні.

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

Ще один підхід до планування з метричними величинами представляє проблему планування як суміш числового і лінійного програмування (ЧЛП).

В ЧЛП-представленні в основному використовується та ж форма, що і в ПЗ-представленні, тобто змінні визначаються для:

·           кожної можливої дії на кожному дискретному часовому кроці;

·           кожної прпозиції на кожному дискретному часовому кроці.

Замість значень істина/фальш змінні приймають значення 0/1 ( 1 означає, що пропозиція є істинна, або дія має місце ).

В цьому представленні обмеження між діями і пропозиціями мають форму лінійних нерівностей, які можуть формуватись прямо з диз’юнктів ПЗ-представлення. Напрмиклад, дія А, що має ефект Е та задається в ПЗ-представленні диз’юнктом ù Аt Ú Et+1  може бути трансльована в ЧЛП-форму у вигляді нерівності:

                                      (1-At) + Et+1  ³ 1.

Як і в ПЗ-плануванні, подібні нерівності потрібні для передумов дій, аксіом і взаємовиключень. Дії, що включають метричні обмеження, можуть транслюватись таким же чином, як і в системі LPSAT.

Після трансляції, для розв’язання результуючої системи нерівностей використовується стандартний ЧЛП-вирішувач.

Принциповою перевагою ЧЛП-підходу є єдиний механізм обробки аксіом і метричних обмежень, а також більш природня специфікація і виконання оптимізаційного критерію.

Недоліками ЧЛП-підходу залишаються ті ж самі, що і при ПЗ-підході – великий розмір кодування і тільки дискретний час.

6.2.          Інтеграція С&T планування.

На основі аналізу процесів С-  і  Т-планування в 2-му та 5-му розділах можна виділити наступні типи систем для інтеграції цих процесів:

·        Пошарові С&T-системи.

В цих системах процеси С-  і  Т-планування розділяються. При розв’язанні задач, що включають альтернативні дії, спочатку запускається підсистема    С-планування для вибору дій, а потім підсистема Т-планування для впорядкування цих дій з урахуванням часових обмежень.

·        Прошаровані С&T-системи.

В цих системах спостерігається прошарування процесів вибору дій та їх впорядкування. Зазвичай, спочатку обирається дія, а потім вирішуються конфлікти з іншими діями шляхом визначення обмежень впорядкування дій та їх часових інтервалів.

Прикладом прошарованих С&T-систем є системи IxTeT  та  HSTS/RA, які вже згадувались раніше.

Прошаровані С&T-системи можуть, в свою чергу, інтегруватись з системами лінійного програмування для роботи з метричними обмеженнями і неперервним часом. Прикладом такої інтеграції є система ZENO, яка розглядалась в розділі 6.1.

 

6.1.    Класифікація систем планування рішень.

 

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

В цілях класифікації та співставлення різних плануючих систем будемо називати ці сукупності методів методологіями.

Далі приводиться класифікація найбільш відомих плануючих систем на рівні їх узагальнених характеристик – методологій. Методології згруповані в окремі типи і називаються іменем тієї системи, в якій вони були вперше реалізовані.

 

 

№

Назва типу

методології
6.2.1.1.1.1                    Склад методології

Приклади систем, що реалізують методологію

1

2

3

4

1

6.2.1.1.1.1.1.1  STRIPS

Цілеспрямоване планування.

 

STRIPS, WARPLAN [61], INTERPLAN [62],      ADEX [69 ], CODEX [70 ]

2

NOAH

Частково-впорядкуюче планування.

Цілеспрямоване планування.

NOAH [58], NONLIN [59], TWEAK [4], UCPOP [10], UWL [14], CNLP [13]

3

GRAPHPLAN

Плануючий граф.

Частково-впорядкуюче планування.

Цілеспрямоване планування.

GRAPHPLAN, IPP [67],   BLACKROX [66],        STAN [68], SENSORY GRAPHPLAN [26]

4

O – PLAN

Ієрархічне планування задовільнення обмежень.

O–PLAN [54],      PLANERS-1 [55],

OPTIMUM.AIV  [56],   GARI [57], SIPE [60]

 

1

2

3

4

5

DEVISER

Частково-впорядкуюче планування.

Часові інтервали.

 

DEVISER [11], IxTeT [47],        TRAINS [46], HSTS/RA [48],     DESKARTE [50]

6

ZENO

Частково-впорядкуюче планування.

Часові інтервали.

Лінійне програмування.

ZENO [52]

7

LPSAT

ПЗ-планування.

Лінійне програмування.

 

LPSAT [33],          SATPLAN [53],      MAXPLAN [63],    ZANDER [63]

8

C-BURIDAN

Марківські вирішуючі процеси.

Динамічне програмування.

 

C-BURIDAN [64]

9

PGRAPHPLAN

Марківські вирішуючі процеси.

Динамічне програмування.

Плануючий граф.

 

PGRAPHPLAN [27], TGRAPHPLAN [27],      SPI [65]

 

          

 

7.          Висновки.

 

Розглянувши різні моделі процесів планування рішень, було визначено, що деякі моделі можуть взаємодоповнювати одна одну.

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

Приклад планування дій космічного апарату показує, що існують задачні середовища, які включають як процеси вибору дій так і їх впорядкування. Для розв’язання таких задач можна використовувати інтегровані пошарові і прошаровані С&T-системи.

Пошарові системи осбливо корисні для багатоагентних розподілених середовищ, де можлива взаємодія між агентами при розв’язанні однієї задачі.

Прошаровані С&T-системи більш корисні для одноагентних середовищ.

В тому випадку, коли маємо справу з неперервним часом або метричними величинами, доцільно інтегрувати пошарові і прошаровані С&T-системи з підсистемами лінійного програмування.

Системи для розгалуженого планування зазвичай використовують Марківські вирішуючі процеси та інтегруються з підсистемами динамічного програмування.

Узагальненими характеристиками для класифікації та співставлення різних плануючих систем є їх методології.

 

 

Cписок літератури

 

  1. Fikes R. and Nillsson N.  STRIPS: A new approach to the application of theorem proving to problem solving.  J.Artificial Intelligence – 1971, V2, p.189-208
  2. М.І.Галаган  Мова опису задач SITPLAN-2. Методичний посібник з курсу “Основи проектування баз знань”, Вид. Київ. Університету, 1999
  3. Tate A. Generating Project Networks.  In Proc. 5th Int. Joint Conf. on AI, 1977, 888-893
  4. Chapman D.  Planning for conjunctive goals.  Artificial Intelligence, 1987, 32(3), 333-377
  5. McAllester D. and Rosenblitt D.  Systematic Nonleaner Planning.  In Proc. 9th National Conf. on AI, 1991, 634-639
  6. Kambhampati S., Knoblock C. and Yang Q.  Planning as refinement search:a unifed framework for evalution design tradeoffs in partial order planning.  Artificial Intelligence, 1995, 76, 167-238
  7. Weld D.  An introduction to least commitment planning.  In AI Magazine, 1994, 15(4), 27-61
  8. Russel S. and Norvig P. Artificial Intelligence: A Modern Approach. 1995, Prentice Hall
  9. Dean T. and Kambhampati S.  Planning and Scheduling.  In CRC Handbook of Computer Sciance and Engineering, 1996
  10. Penberthy J. and Weld D. UCPOP: A sound, complete, partial order planner for ADL. In Proc. 3th Int. Conf. on Principles of Knowledge Representation and Reasoning.  1992, 103-114
  11. Vere S.  Planning in time: windows and durations foe activities and goals.  Pattern Analysis and Machine Intelligence, 1983, 5, 246-267
  12. Penberthy J. and Weld D.  Temporal planning with continuous change.  In Proc. 12th National Conf. on AI, 1994, 1010-1015
  13. Peot M. and Smith D.  Conditional Nonlinear Planning.  In Proc. 1st Int. Conf. on AI Planning Systems, 1992, 189-197
  14. Etzioni O., Hanks S., Weld D., Draper D., Lesh N. and Williamson M.  An approach to planning with incomplete information.  In Proc. 3th Int. Conf. on Principles of Knowledge Representation and Reasoning.  1992, 115-125
  15. Pryor L. and Collins G.  Planning for contingencies: a decision-based approach. JAIR 4, 1996, 287-339
  16. Golden R. and Boddy M. Conditional linear planning.  In Proc. 2nd  Int. Conf. on AI Planning Systems, 1994, 80-85
  17. Kushmeric N., Hanks S. and Weld D.  An algorithm for probabilistic planning. Artificial Intelligence, 1995, 76, 239-286
  18. Draper D., Hanks S. nad Weld D.  Probabilistic planning with information gathering and contingent execution.  In Proc. 2nd  Int. Conf. on AI Planning Systems, 1994, 31-36
  19. Golden K. and Weld D.  Representing sensing actions: the middle ground revisited. In Proc. 5th  Int. Conf. on Principles of Knowledge Representation and Reasoning.  1996, 174-185
  20. Golden K.  Leap before you look: information gathering in the PUCCINI planner.  In Proc. 4th   Int. Conf. on AI Planning Systems, 1998
  21. Blum A. and Furst M.  Fast planning through planning graphanalysis.  Artificial Intelligence, 1997, 90, 281-300
  22. Gazen B. and Knoblock C.  Combinning the expressivity of UCPOP with the efficiency of Graphplan.  In Proc. 4th European Conf. on Planning, 1997, 223-235
  23. Koehler J., Nebel B., Hoffmann J. and Domopoulos Y. Extending planning graphs to an ADL subsrt.  In Proc. 4th European Conf. on Planning, 1997, 275-287
  24. Anderson, C.,Smith, D.and Weld, D. Coditional effects in Graphplan. In Proc. 4th Int. Conf.AI Planning System,1998
  25. Smith D. and Weld D. Conformant Graphplan  In Proc. 15th National Conf. on AI, 1998
  26. Weld D., Anderson C. and Smith D.  Extending Graphplan to handle uncertainty & sensing actions.  In Proc. 15th National Conf. on AI, 1998
  27. Blum A. and Langeford J.  Probabilistic planning in the Graphplan framework.  In AIPS-98 Workshop on Planning as Combinatorial Search, 1998, 8-12
  28. Smith D. and Weld D. Temporal planning with mutual exclusion reasoning.  In 16th Int. Joint Conf. on AI, 1998
  29. Koehler  J.  Planning under Resource Constraints. In Proc. 15th European Conf. on AI, 1998
  30. Kautz H. and Selman B.  Pushin the envelope: planning, propositional logic, and stochastic search.  In Proc. 13th National Conf. on AI, 1996
  31. Ernst M., Millstein T., and Weld D. Automatic SAT-compilation of the planning problems.  In 15th Int. Joint Conf. on AI, 1997
  32. Kautz H., McAllester D., and Selman B.  Encoding plans in propositional logic. In Proc. 5th  Int. Conf. on Principles of Knowledge Representation and Reasoning.  1996
  33. Wolfman S. and Weld D.  Combining Linear  Programming and Satisfiability Solving for Resource Planning.  Knowledge Engineering  Review, 1999
  34. Wilkins D.  Can AI planners solver practical problems?  Computational Intelligence, 1990, 6(4), 232-246
  35.    Puterman M.  Markov Decision Processes: Discrete Stochastic Dynamic Programming.  John Wiley & Sons, 1994
  36. Dean T., Kaelbling L., Kirman J., and Nicholson A.  Planning under time constraints  in stochastic domains.  AI 1995, 76, 35-74
  37. Geneserreth M. and Nillson N.  Logical Foundations of AI.  Morgan Kaufman, 1987
  38. Allen,J., and Hendler,J., and Tate,A. Reading in Planning. Morgan Kaufman,1990  
  39. Drummond M., Bresina J., and Swanson K.  Just-In-Case Scheduling.  In Proc. 12th National Conf. on AI, 1994
  40. Ford Jr.L. Network Flow Theory.  Technical Report, Rand Corporation, 1956
  41. Smith S. and Cheng C.  Slack-based heuristics for constraint saticfaction scheduling. In Proc. 11th National Conf. on AI, 1993
  42. Mackworth A.  Consistency in networks in relations.  Artificial Intelligence, 1977, 8, 99-118
  43. Nadel B.  Constraint satisfaction algorithms.  Computational Intelligence, 1989, 5, 188-224
  44. Ginsberg M. Approximate planning.  Artificial Intelligence, 1995, 76, 89-123
  45. Bayardo R.  A complexity analysis of space bounded learning algorithms for the constraint satisfaction problem.  In Proc. 13th National Conf. on AI, 1996, 298-303
  46. Ferguson,G.,Allen,J.,and Miller,B.TRAINS-95:Towards a mixed-initiative planning assistant.In Proc.3rd Int.Conf. on AI Planning Systems,1996  
  47. Ghallab M. and Laryelle H.  Representation and Control in IxTiT, a Temporal Planner.  In Proc.2nd Int. Conf. on AI Planning Systems, 1994, 61-67
  48. Zweben M. and Fox M.  Intelligence Schedulling.  1994, Morgan Kaufman
  49. Allen,J. Towards a general theory of action and time.Artificial Intelligence 23(2),123-154, 1984    
  50. Joslin D.  Passivate and activate decision postponement in plan generation. Ph.D. dissertation, Intelligence Systems Program, U.Pittsburgh, 1996
  51. Drabble B. and Tate A.  The use of optimistic and pessimistic resource profiles to inform search in an activity based planner. In 2nd Int. Conf. on AI Planning Systems, 1994, 243-248
  52. Penberthy J.  Planning with continuos change.  Ph.D. dissertation 93-12-01, Dept. of Computer Science and Engineering, U. Washington, 1993
  53. Weld D.   Recent advances in AI planning.  In IA Magazine, 1999, 20(2), 93-123
  54. Bell,C.and Tate,A.Using temporal constrains to restrict search in planner.In Proc. Of the Third Alveys IKBS SIG Workshop,Oxfordshire,1985
  55. Fuchs J.J., Gasquet A., Olalainty B. and Currie V.W.  Plan- ERS.1: An expert planning system for generation spacecraft mission plans.  In 1st Int. Conf. on Expert Planning Systems, Brighton, 1999
  56. Aarup M.  OPTIMUM-AIV: A knowledge-based planning and scheduling system for spacecraft AIV.  In Fox M. and Zweden M. editors, Knowledge Based Scheduling, Morgan Kaufman, San Mateo, California, 1994
  57. Descotte Y. and Latombe J.C.  Making compromises among constraints in a planner.  Artificial Intellegence, 1985, 27, 183-217
  58. Sacerdoti E.D.  The nonlinear nature of plans.  In Proc. Of IJCAI-1975, p.208-214, Tbillisi, Georgia, IJCAI
  59. Tate A.  Generating project networks.  .  In Proc. Of IJCAI-1977, p.888-893, Cambridge, Massachusetts, IJCAI
  60. Wilkins D.E.  Practical Planning: Extending the AI Planning Paradigm. Morgan Kaufman, San Mateo, California, 1988
  61. WARPLAN: a system for generating plans.  Departament of Computational logic, MEMO 76, University of Edinburg, Edinburg, Scotland, 1974
  62. Tate A.  Iteracting goals and their use.  In Proc. Of IJCAI-1975, p.215-218, Tbillisi, Georgia, IJCAI
  63. Majercik S.M. and Littman M.L. MAXPLAN: a new approach to probabilistic planning.  In AIPS, 1998, p.86-93
  64. Majercik S.M. and Littman M.L.  Contingent planning under  umertaninty via stochastic satisfability.  In AAAI,  1999
  65. Boutilier, et.al.  Exploiting structure in policy construction.  In IJCAI-95, Monreal, 1995, p.1104-1111
  66. Kautz H and Selman B.  BLACKBOX: A New Approach to the Application of Theorem Proving to Problem Solving
  67. Koehler J.  Solving Complex Planning Tasks Through Extraction of Subproblems.   In AIPS-98, p.62-69
  68. Long D. and Fox M.  Efficient Implementation of the Plan Graph in STAN.  In JAIR, 1998, V10, p.87-115
  69. Галаган Н.И., Тесанюк Ю.Н.  Адаптивная экспертная система АДЭКС-2.0.  Тр Всесоюзного научно-технического семинара “Программное обеспечение новых информационных технологий”, Тверь, 1991
  70. Ващенко Н.Д., Гладун В.П., Дрючин Ю.Л.  Инструментальный комплекс для построения экспертных систем КОДЭКС.  Всесоюзная конференция по искусственному интеллекту, М: ВИНИТИ, 1988
  71. Питер Джексон, Введение в экспертные системы. – Изд. дом “Вильямс”, Москва – Санкт-Петербург – Киев, 2001.