Московський Державний інститут радіотехніки, електроніки та автоматики

(Технічний університет)

кафедра: ІТС

Факультет: Кібернетики < p> Курсова робота по курсу: Інтелектуальні системи управління тема: Повна паралельна підтримка для систем планування, заснованих на випадках

студент: Частухін Віталій група: АІ-1-93 керівник: Захаров

МОСКВА 1996

Повна паралельна підтримка для систем планування, заснованих на випадках

Опис

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

Система планування, заснована на випадках відрізняється від систем генерування планів, таких як Нонлін (від англ. "Nonlinear" - нелінійний), які будують погано підібраний план шляхом пошуку відповідного фрагменту плану, розширення цього фрагмента шляхом додавання в нього дій і потім перевірки розширеного фрагменту плану на "шкідливість" і "корисність" взаємодій між впровадженими діями. Це дорогий процес.

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

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

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

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

а) Організація бази знань

База знань організується як семантична мережа, що містить поданняепізодичних і концептуальних знань. Концепція включає об'єкти, якіможуть мати фізичні властивості, дії, які можуть задаватисяправилами, початкові умови і слідства. Концепція організуєтьсявідносинами is-a (приналежності), part/whole (часткового порядку) ііншими. Представлення (концепція) може також містити включення абоіндивідуальні імена типів, які представляють частину об'єктів.

Епізодичні знання описуються накопиченим досвідом системи (або дослідами,які були їй повідомлені заздалегідь). Кожному епізоду ставиться у відповідністьпевні дата, час, місце та інші властивості.

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

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

У Капер вузли семантичної мережі представляють концепції, імена типів іепізоди.

Пам'ять Капер здійснена з використанням повної паралельної, заснованоїна фреймах, системи подання знань, названої Парку.

Капер використовує Структурний Конструктор для вибірки епізодів з пам'яті.
Структурний Конструктор розглядає базу знань як граф з вершинами,що представляють собою фрейми і гранями, що представляють собою слоти
(які пов'язують собою два фрейму).

б) Підбір плану

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

Автори і назва оригіналу перекладеної статті:
"Massively Parallel Support for Case-Based Planning",
Brian P. Kettler, James A. Hendler, William A. Anderson, and Matthew P.
Evett