М.І. Галаган планування рішень в умовах часових обмежень Методичний посібник з курсу “Основи проектування баз знань“



Скачати 455.91 Kb.
Сторінка1/10
Дата конвертації11.03.2016
Розмір455.91 Kb.
  1   2   3   4   5   6   7   8   9   10
Київський національний університет імені Тараса Шевченка

М.І. ГАЛАГАН

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

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

Київ -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 і Т-планувальників.

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


  1   2   3   4   5   6   7   8   9   10


База даних захищена авторським правом ©refs.in.ua 2016
звернутися до адміністрації

    Головна сторінка