Реферат: Мова опису задач SITPLAN-2

Реферат на тему:

Мова опису задач SITPLAN-2

1. Вступ

В останнi роки у нас в країнi та за кордоном з'явився новий клас програмних систем, спроможних вирiшувати задачи не за заданими алгоритмами, а за їх формулюваннями, якi складаються з описiв вихiдних та цiльових ситуацiй. Такого роду системи названi в [1] i нтелектуальними вир i шуючими системами (І ВС ). Важливою особливiстю цих систем є те, що разом з обробкою даних в них виконується обробка знань про проблемну область (ПО ). Для работи в слабоформалiзованих ПО створюються І ВС , вiдомi пiд назвою експертн i системи (MYSIN, PROSPECTOR, R1 [2] та iн.). Поряд з експертними системами в слабоструктурованих ПО використується ще один рiзновид І ВС - розрахунково-логiчнi системи (ПРИЗ, МАВР, СПОРА [2] та iн.).

Для опису формулювань задач i знань про ПО в І ВС використуються не мови програмування, а мови опису задач, в яких декларативний компонент значно бiльш розвинений, нiж процедурний (останнього може взагалi не бути).

У даному посiбнику розглядається мова опису задач SITPLAN-2 , яка є подальшим розвитком мови SITPLAN , орiєнтованої на задачi перетворювання ситуацiй в змiшанiй, декларативно-процедурнiй формi подання [3].

Мова SITPLAN має ряд переваг порiвняно з iншими мовами опису задач. Це докладно аналiзуєтся в [4]. Однiєю з найбiльш важливих переваг мови SITPLAN , що зберiгається в SITPLAN-2 , єїї неприв'язанiсть до конкретних стратегiй планування рiшень. На вiдмiну вiд мови SITPLAN запропонована мова мiстить ряд засобiв, якi розширюють можливостi формалiзацiї та формулювань задач планування дiй в проблемних областях, що включають складнi багатокомпонентнi об'єкти, а також задач в умовах невизначеностi та часових обмежень.

Для опису знань про проблемну область у мовiSITPLAN-2 використуються такi конструкцiї:

· базовi поняття та вiдношення;

· складовi поняття та вiдношення, що подаються конструкцiями типу фреймiв;

· в'язки продукцiйних правил, що називаються операторами i демонами.

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

Мова SITPLAN-2 є вхiдною мовою системи керування базою знань (СКБЗ ), архiтектура якої приведена на мал. 1 .

Формулювання задачи i опис знань про проблемну область обробляється лiнгвiстичним процесором i перетворюється у внутрiшнє подання в пам'ятi даних та знань у виглядi пирамiдальних мереж [5]. СКБЗ орiєнтована на вирiшення практичних задач з великими обсягами бази знань у таких ПО як технологiя програмування, САПР , АСК , науковi дослiдження, робототехнiка i таке iнше. Бази знань у цих ПО мiстять десятки тисяч продукцiйних правил i тому СКБЗ повинна бути вiртуальною. Оскiльки СКБЗ орiєнтован на супер-, мiнi- та персональнi комп'ютери, одним з основних принципiв його реалiзацiїє принцип мобiльностi. В зв'язку з цим реалiзацiя СКБЗ здiйснюється на мовiС І в операцiйних системах UNIX , MS-DOS , WINDOWS та iн.

1. Формалiзм синтаксичного опису

Синтаксичнi структури мови беруться у хвилястi дужки { } .

Застосування квадратних дужок [ ] означає, що замкнена в них конструкцiя або набiр альтернатив може бути вiдсутньою. Альтернативнi визначення записуються окремими рядками або роздiляються вертикальними рисочками i беруться в дужки ( { } чи [ ] ).

Три крапки пiсля символу або конструкцiї означають його (або її) повторення не менш одного разу.

Символ “: ” використовується замiсть “дорiвнює по визначенню”, “_ ” означає “пропуск”. У текстах на мовiSITPLAN-2 можуть зустрiчатися коментарi - будь-якi послiдовностi символiв, замкненi в косi дужки з зiрочками /* ... */ . Коментарi у процесi розбору текстiв пропускаються без будь-якої обробки. Службовi слова набираються великими видiленими лiтерами.

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

2. Елементарнi конструкцi мови

Синтаксис

слово: { лiтера } ...

службове слово: { велика видiлена лiтера } ...

iдентифiкатор: слово лiтера

цифра

змiнна: Х { цифра } ...

Семантика

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

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

Змiнна - це найменування, що дано окремому текстовому значенню. Значення змiнних та їх типи визначаються порiвненням виразiв.

3. Енки (n -ки)

Синтаксис

первинний рядок: слово

iдентифiкатор

число

змiнна

n -ка: первинний рядок _ первинний рядок

n -ка_[ первинний рядок ] ...

Семантика

Енки використовуються для видiлення кортежiв вiдношень, iмена яких вiдсутнi у фразах природної мови i припускаються за умовчанням. Енка - це складове iм'я, яке є неподiльною лексичною одиницею. Енка з числом компонент, що дорiвнює двум, називається парою. Енка, що мiстить хоча б одну змiнну, вважається змiнною.

Приклади

Енки: ІВАНОВ_МИКОЛА_ІВАНОВИЧ;

ПОВЕРХНЯ_А_ОБ'ЄКТА_В;

ГОСТ_24_42_56;

ТОЧКА_Х1_Х2_Х3.

Пари: СТІЛ_А; ЯЩИК_Х5; ВЕЛИКИЙ_КОНТЕЙНЕР.

Енка змiнна: Х1_МИКОЛА_ІВАНОВИЧ.

4. Вирази

Синтаксис

операцiя: { арифметична | логiчна | тригонометрична |

вiдношення | присвоювання }

префiкс заперечення: НІ

NOT

описовий вираз: первинний рядок

n -ка

первинний рядок ( описовий вираз )

( описовий вираз )

префiкс заперечення, описовий вираз

описовий вираз, описовий вираз

операцiйний вираз: операцiя

операцiя, первинний рядок

первинний рядок, описовий вираз

( описовий вираз )

описовий вираз, описовий вираз

декларативний вираз: описовий вираз

операцiйний вираз

процедурний вираз: ! описовий вираз

! операцiйний вираз

простий вираз: декларативний вираз

процедурний вираз

квантор: УВЕСЬ | Є

обмежувач: ЦИКЛ | СТАРТ | ТРИВ | СИТ | ДОС | МАХ | МIN

iменувальна частина виразу:

описовий вираз ...

квантор описовий вираз ...

обмежувач описовий вираз ...

складовий вираз: iменувальна частина виразу: простий вираз: ... складовий вираз

( простий вираз: ) ...

вираз: простий вираз

складовий вираз

список виразiв: { вираз; } ...

( список виразiв )

{ список виразiв }

список виразiв

[ список виразiв ]

Семантика

Вираз є основною семантичною одиницею при опису задач. В мовiSITPLAN-2 використується два типи виразiв: описовi та операцiйнi. В кожному з них видiляються два рiзновида виразiв: декларативнi та процедурнi (останнi починаються з символу ! ). Крiм того вирази можуть бути простими i складовими.

4.1. Описовi вирази

Декларативнi описовi вирази служать для опису властивостей, станiв та зв'язкiв об'єктiв середовища без вказiвки, як їх використовувати. Семантика цих виразiв залежить вiд класу задач i типу конструкцiї. Як описовi вирази можуть бути використанi фрази природної мови, а також послiдовностi, складенi з пар, n -ок, первинних рядкiв, ком та пропускiв.

Приклади

СТОЛ; ТОЧКА Х1_Х2_Х3;

ПОРЯД ( ОБ_1, СТОЛ) ;

( ПОВ_1_ОБ_2 НА ПОВ_3_ОБ_4) ;

ОБ_1, ОБ_2, ОБ_3 НА ПІДЛОЗІ.

Префiкс заперечення (НІ, NOT) в складi описового виразу означає вiдсутнiсть властивостi, стану чи зв'язки, що подається даним описовим виразом.

Приклади

НІ Х1 У ЯЩИКУ_2;

НІ РОБОТ ПОРЯД СТОЛ_Х2.

Процедурнi описовi вирази використовуються в таких випадках:

· Для опису звернення до вбудованої процедури. Наприклад, ! ПЕРЕСТАВИТИ МОЖНА ( Х1, Х2, Х3) . Пiд час виклика цiєї процедури перевiряється можливiсть переставлення об'єкта Х1 з об'єкту Х2 на Х3.

· Для означення iмперативiв (конструкцiй), що забезпечують участь користувача в процесi рiшення задачi, а також пошук, вилучення, ввiд та модифiкацiю певних конструкцiй у базi знань, наприклад, ! ВИКОНАТИ: { OP1 } ... { OPn } . Цей iмператив означає виконання послiдовностi операторiв { OP1 } ... { OPn } : СИТ ! ВИЛУЧИТИ { вир. 1, вир. 2, ... вир } . Пiд час його виконання з опису ситуацiї будуть вилученi вирази, що взятi у дужки.

4.2. Операцiйнi вирвзи

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

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

Процедурнi операцiйнi вирази означають запуск однiєї або кiлькох вбудованих процедур, що реалiзують указанi в виразах операцiї.

Процедурнi операцiйнi вирази, що забранi в дужки, обчислюються, починаючи з дужок найбiльшої вкладеностi.

Приклади

(1)

(2) (3)

(4)

Вирази (1), (2) є декларативними. Вони не задають якоїсь послiдовностi виконання операцiй. До них можуть бути застосованi правила виводу i тотожнiх перетворень. Наприклад, вираз (1) за допомогою правила замiни iмплiкацiї диз'юнкцiєю можна привести до вигляду Вираз (2) можна привести до вигляду

Вирази (3), (4) є процедурними. Вони задають певну послiдовнiсть виконання операцiй. Послiдовнiсть виконання операцiй виразу (3) є такою:

1) виконується операцiя складення i;

2) пiдноситься до квадрату ;

3) результат кроку 2 вiднiмається вiд результату кроку 1;

4) змiннiй присвоюється результат операцiї вiднiмання.

Пiд час обробки виразу (4) спочатку виконується операцiя над змiнними i, потiм операцiя над , , i нарештi операцiя над значеннями “iстина” або “хибнiсть”, що отриманi в результатi операцiй (1), (2). Результатом (4) також є значення “iстина” або “хибнiсть”.

4.3. Квантори i обмежувачi

В мовiSITPLAN-2 з метою розширення виразових можливостей запроваджуються додатковi засоби типу кванторiв i обмежувачiв, якi служать для указання мiри, наскiльки значення змiнних повинно бути iстиним, щоб висловлювання вцiлому стало iстиним.

Приклади виразiв з кванторами

УВЕСЬ Х1 Є Х2: ЦВЯХ Х1 З МАТЕРІАЛУ Х2 ТЕРМОСТІЙКИЙ.

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

До складу запроваджуваних обмежучив входить обмежувач циклу, позначений службовим словом ЦИКЛ . Вiн використовується пiд час опису ситуацiй i операторiв з великою кiлькiстю об'єктiв, якi знаходяться в одному i тому ж вiдношеннi.

Приклад

ЦИКЛ 100 Х1: ЦВЯХ Х1 У ЯЩИКУ.

Цей вираз може бути iнтерпретован таким чином: “У ящику знаходиться сто цвяхiв”. Як видно з приведеного прикладу в виразах з циклом може бути явно вказано кiлькiсть повторiв циклу, якщо ж вона не вказана, то семантика обмежувача циклу спiвпадає з семантикою квантора спiльностi, тобто вираз

ЦИКЛ Х1: ЦВЯХ У ЯШИКУ

є еквiвалентний виразу

УВЕСЬ Х1: ЦВЯХ У ЯШИКУ.

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

Наприклад, вираз

MAX Х1: ІНСТУЛЬТ Х2 З ЙМОВІРНІСТЮ Х1

буде iстиним при максимальних значеннях змiнної Х1.

Обмежувач старту (СТАРТ ) служить для завдання iнтервалу часу, в продовж якого досягається iстиннiсть охоплених ним виразiв.

Часовiiнтервали обозначемо парами , де - нижня, а - верхня межа часового iнтервалу.

Щоб подати рiзнi часовiiнтервали, використують виразиє семантика яких приведена в табл. 1 .

Таблиця 1

Обмежувач тривалостi (ТРИВ ) служить для указання тривалостi дiй або подiй. Вираз обмежувача задається змiнною, константою або функцiєю:

СТАРТ В 7_0_0 ТРИВ 10 с: ДЗВОНИТЬ БУДИЛЬНИК.

ТРИВ Х1 с: ПЕРЕДАЧА ДАНИХ НА ЗЕМЛЮ.

ТРИВ К-Y/2: ПЕРЕМОТКА СТРІЧКИ.

Обмежувач достовiрностi (ДОСТ ) служить для указання ступеню iстинностi наступного за ним виразу. Ступiнь iстинностi виразiв задається числовими значеннями у iнтервалi вiд 0 до 1:

ДОСТ 0.7: ІНСУЛЬТ ІШЕМІЧНИЙ ПАЦІЄНТА ІВАНОВА В.В.

4.4. Складовi вирази

Для бiльшої наочностii компактностi в мовiSITPLAN-2 використовуються конструкцiї типу фреймiв. Це складовий вираз, що мiстить iменувальну частину виразу, яка iдентифiкує описове поняття, i набiр виразiв, якi вiдображують властивостi, вiдношення та складовi частини, котрi безпосередньо входять до структури об'єкта, що описується.

Приклади

1. Складовий вираз, що використовується для опису складових об'єктiв:

КОМНАТА К1: ДОВЖИНА 8 М;

ШИРИНА 10 М;

ДВЕРІ А З'ЄДНУЮТЬ КІМНАТУ_К1 З КІМНАТОЮ_К2;

СТІЛ 1 ПОРЯД З СТОЛОМ 2.

2. Складовий вираз, що використовується для завдання параметрiв стратегiї планування:

ПАРАМЕТРИ: СТРАТЕГІЯ Х1;

КОЕФІЦІЄНТ ЦР Х3;

ЛІМІТИ ЧАСУ Х3;

ПРЯМЕ РОЗГАЛУЖЕННЯ Х4;

ЗВОРОТНЄ РОЗГАЛУЖЕННЯ Х3.

В мовiSITPLAN-2 прийнятi такi узгодження вiдносно описiв упорядкованих i неупорядкованих спискiв виразiв:

· упорядкованi списки виразiв, в яких мається на увазi зв'язка типу & , беруться в круглi дужки ( ) ;

· неупорядкованi списки виразiв, в яких мається на увазi зв'язка типу & , беруться в хвилястi дужки { } ;

· упорядкованi списки виразiв, в яких мається на увазi зв'язка типу , беруться в кутовi дужки ;

· неупорядкованi списки виразiв, в яких мається на увазi зв'язка типу , беруться в квадратнi дужки [ ] .

Якщо списки виразiв не взятi в дужки, мається на увазi зв'язка типу & .

5. Опис знань про проблемну область

Опис знань про проблемну область мiстить такi компоненти: опис понять, що визначають об'єкти проблемної областi, та вiдношень мiж об'єктами, а також опис операторiв та демонiв, що моделюють дiї, подiї та правила логiчного виводу.

Базовi поняття i вiдношення служать для узгоджування виразiв вихiдної ситуацiїi цiльової умови з виразами опису операторiв.

Список базових понять складається з найменувань класiв об'єктiв. Для цього можуть бути використанi слова природної мови:

БПОН СТІЛ, СТІЛЕЦЬ, ШАФА, ...

BCON CMT, PLATE, GLASS, ...

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

БВ І ДН Х1 НА Х2;

Х1 ПОРЯД З Х2;

ВИСОТА Х1 Х3.

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

Опис складеного поняття являє собою складовий вираз, iменувальна частина якого є найменуванням поняття, а слiдуючий за нею список простих виразiв - визначенням цього поняття в термiнах його компонентiв, тобто понять i вiдношень бiльш низького рiвня, аж до базових, наприклад:

СПОН МЕБЛІ: { СТІЛ, СТІЛЕЦЬ, ... ШАФА } ;

МОЛ -Х1: ТИП Х2;

КІЛЬКІСТЬ АТОМІВ Х3;

КІЛЬКІСТЬ КІЛЕЦЬ Х4;

ВКЛЮЧАЄ Х5.

Іменувальна частина виразу в описi складового вiдношення є вiдношенням, що визначається, а слiдуючий за нею список простих виразiв - його визначенням в термiнах вiдношень бiльш низького рiвня, аж до базових, наприклад:

СВ І ДН ПЕРЕНЕСТИ Х1 З Х2 НА Х3:

/ПІДІЙТИ ДО Х2, ВЗЯТИ Х1, ПІДІЙТИ ДО Х3,

ПОСТАВИТИ Х1 НА Х3/.

5.1. Опис операторiв та демонiв

Синтаксис

опис оператора: { тип оператора } { iменувальна частина }:

{ список продукцiйних правил }:

[ ДЕ список значень змiнних ]

опис демона: { тип демона } { iменувальна частина }

{ список продукцiйних правил }

[ ДЕ список значень змiнних ]

тип оператора: ОЛ | OL | ОД | OA

тип демона: ДЛ | DL | ДП | DE

список продукцiйних правил:

{ опис основного правила }

[ опис корекцiйного правила ] ...

опис основного правила:

ЯКЩО [ список виразiв ] [ / список виразiв / ]

ТО [ список виразiв ]

опис корекцiйного правила:

' ЯКЩО [ список виразiв ] [ / список виразiв / ]

' ТО [ список виразiв ]

список значень змiнних:

{ змiнна первинний рядок , ... } ; ...

пара

Семантика

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

Використання демонiв дозволяє моделювати процеси випадкового пошуку. Розлiчають такi типи операторiв i демонiв:

· оператор типу дiї (ОД або OA );

· оператор типу правила логiчного виводу (ОЛ або OL );

· демон типу подiї (ДП або DE );

· демон типу правила логiчного виводу (ДЛ або DL ).

Продукцiйнi правила, що входять до операторiв i демонiв, роздiляються на основнi та корекцiйнi.

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

Кожне продукцiйне правило складається з лiвоїi правої частини. Лiва частина продукцiйного правила є сукупнiсть елементарних умов (вхiдних виразiв), необхiдних при виконаннi цього правила.

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

Рiзнi варианти пiдстановки значень змiнних вiдповiдають рiзним вариантам застосування продукцiйного правила.

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

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

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

Наведемо приклад запису продукцiйних правил оператора типу дiї, вiдповiдного перемiщенню робота з кiмнати Х1 у смiжну з нею кiмнату Х3.

ОД ДОСТ 0,5 СТАРТ ПІСЛЯ 5: ПЕРЕЙТИ З КІМ_Х1 У КІМ_Х3

ЯКЩО

ПРИМІЩЕННЯ: МІСТИТЬ ДВЕРІ_Х2, КОМ_Х1, КОМ_Х3

ДВЕРІ_Х2: З'ЄДНУЄ КОМ_Х1 З КОМ_Х3, СТАН ВІДЧИНЕНА.

/ КОМ_Х1 МІСТИТЬ РОБОТ /

РОБОТ ПОРЯД З ДВЕРЯМИ_Х2,

ТО

КОМ_Х3 МІСТИТЬ РОБОТ,

' ЯКЩО

УВЕСЬ Х4: КОМ_Х1 МІСТИТЬ Х4;

Х4 ДВЕРІ_Х2

/ РОБОТ ПОРЯД З Х4. /

Пiсля виконання основного продукцiйного правила опис пiдсумковiї ситуацiї записується вираз “КОМ_Х3 МІСТИТЬ РОБОТ” з конкретизованим значенням змiнної Х3, яке набулося пiд час розпiзнавання застосування цього правила в вiдповiдностi з описом його лiвої частини. З опису вхiдної ситуацiї буде вилучено вираз “КОМ_Х1 МІСТИТЬ РОБОТ”.

До складу цього оператора входить також корекцiйне правило без правої частини. Внаслiдок виконання цiєї продукцiї з опису вхiдної ситуацiї вилучаються вирази, що затверджують факти находження робота зо всiма об'єктами Х4. Проте, слiд замiтити, що умови находження робота поряд з об'єктами Х4 не є умовами застосування оператора.

Операторам, якi мають в описах продукцiй цикли, можуть вiдповiдати послiдовностi дiй, що циклiчно повторюються.

Наведемо приклад iменувальної частини оператора, що задає циклом дiю по перестановцi п'яти об'єктiв з столу Х2 на стiл Х3:

ОД ЦИКЛ 5 СТАРТ ПЕРЕД 12.00 ТРИВ 30 С:

( ПІДІЙТИ ДО С ТОЛУ Х2; ВЗЯТИ Х1;

ПІДІЙТИ ДО С ТОЛУ Х3; ПОСТАВИТИ Х1 НА СТІЛ Х3 ) .

Для задання часу початку i тривалостi виконання оператора в описiiменувальної частини використанi обмежувачи старта i тривалостi.

Рiшення по вибору вариантiв механiчної обробки деталей приведени в табл. 2 .

Таблиця 2

Опис оператора, що моделює таблицю рiшень, мiстить значення змiнних, якi йдуть поза службовим словом ДЕ , i має вигляд:

ОД ВАР Х1:

ЯКЩО

КПД Х2;

ВДД Х3;

НЗД Х4;

ДД Х5;

ДЦО Х6;

МАТЕРІАЛ Х7;

ВЗ Х8;

ТО

ВАР Х1;

ДЕ:

Х1 1, 2, 3, 4, 5;

Х2 1, 2, 1, 2, 3, 4, 5, 3, 4, 5, 4, 5;

Х3 0, 1, 2, 3, 1, 2, 3, 0, 1;

Х4 О_И, О_И , О_А, О_А , З_А;

Х5 0_Ж, 0_Ж, 0_6, 0_Б, 7_Д;

Х6 _ , _ , 0_5, 1_5, 0_5;

Х7 _ , _ , 0_6, 0_6, 0_6;

Х8 _ , _ , 5, 6, 8, 9, 0, 6, 8, 9, 5, 6, 8, 9.

Демон типу подiя, що моделює дзвiнок будильнику пiд час Х1 тривалiстю Х2, подається таким чином:

ДС

СТАРТ В Х1 ТРИВ Х2:

ЯКЩО

БУДИЛЬНИК УСТАНОВЛЕНО НА Х1;

ТО

СТАРТ В Х1 ТРИВ Х2: БУДИЛЬНИК ДЗВОНИТЬ.

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

Установочнi поверхнi об'єктiв i вiльних мiсць апроксимуємо квадратами i класiфiкуємо за розмiрами цих квадратiв так, що при установцi на поверхню А класу i об'єкта з установочною поверхнею класу i-1 (див. мал.2 , мiсце Х4 зайняте, мiсця Х6, Х7, Х8 - вiльнi). Пiсля вилучення об'єкта з поверхнiА на нiй з'являються чотири вiльних мiсця класу i-1, якi за допомогою демона логiчного виводу перетворюються в одне вiльне мiсце класу i (на мал. 2 з вiльних мшсць Х4, Х6, Х7, Х8 утворюється вiльне мiсце Х1).

Опис такого демона виглядає так:

ДЛ ВІЛЬНЕ МІСЦЕ_Х1 КЛАСУ_Х2:

ЯКЩО / ОБ_Х3: ВІЛЬНЕ МІСЦЕ_Х4 КЛАСУ_Х5;

ВІЛЬНЕ МІСЦЕ_Х6 КЛАСУ_Х5;

ВІЛЬНЕ МІСЦЕ_Х7 КЛАСУ_Х5;

ВІЛЬНЕ МІСЦЕ_Х8 КЛАСУ_Х5. /

ТО Х1:=NAMER, X2:=X5+1;

ОБ'ЄКТ_Х3: ВІЛЬНЕ МІСЦЕ_Х1 КЛАСУ_Х2.

6. Опис формулювань задач

Синтаксис

опис ситуацiї: список виразiв.

опис змiн: ! ДОПИСАТИ список виразiв

! ADD

! ВИЛУЧИТИ

! DEL

опис вихiдної ситуацiї: СИТ опис ситуацiй

SIT опис змiн

опис цiльової ситуацiї: Ц І ЛЬ опис ситуацiї

GOAL

опис формулювання задачi: { опис вихiдної ситуацiї} { опис цiльової ситуацiї}

Семантика

Опис формулювання задачi складається з описiв вихiдноїi цiльової ситуацiй.

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

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

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

Хай S - множина ситуацiй для деякого класу задач перетворення ситуацiй, - базова ситуацiя. Позначимо через множину виразiв, що подає ситуацiю .

Тодi множину виразiв назовемо записувальним фрагментом по вiдношенню до , а множину виразiв - вилучальним фрагментом по вiдношенню до . Звiдси випливає, що .

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

Наведемо приклад опису вихiдної ситуацiї:

СИТ ПРИМІЩЕННЯ_ЦЕХ_125:

ДОВЖИНА 100 М;

ШИРИНА 50 М;

ВИСОТА 5 М;

ВКЛЮЧАЄ ВІДДІЛОК_1, ВІДДІЛОК_2;

ВІДДІЛОК_1:

ДОВЖИНА 20 М;

ШИРИНА 10 М;

ВИСОТА 5 М;

ТИП ТЕХНІЧНИЙ;

ВКЛЮЧАЄ ВЕРСТАТ_1, ВЕРСТАТ_2,

ВЕРСТАТ_3, ВЕРСТАТ_4,

ВЕРСТАТ_5;

ПОРЯД З ВІДДІЛКОМ_2;

ВІДДІЛОК_2:

ДОВЖИНА 30 М;

ШИРИНА 15 М;

ВИСОТА 5 М;

ТИП СКЛАДАЛЬНИЙ;

ВКЛЮЧАЄ ВЕРСТАТ_1, ВЕРСТАТ_2,

ВЕРСТАТ_3, ВЕРСТАТ_4,

ВЕРСТАТ_5, ВЕРСТАТ_6;

Опис цiльової ситуацiї може бути заданий:

· повним описом цiльової ситуацiї, тобто усiх об'єктiв, що указанi в опису вихiдної ситуацiї;

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

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

Цiльова ситуацiя вважається досягнутою, якщо iснує такий вариант пiдстановки змiнних, при якому усiiї описи приймають значення “iстина”.

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

Приклади

1. Ц І ЛЬ СТАРТ ПІСЛЯ 15.00

НІ Х1 ЗНАХОДИТЬСЯ НА ОБ'ЄКТІ_41.

2. Ц І ЛЬ СТАРТ МІЖ 10 11

/ ОСЦИЛОГРАФ НА СТОЛІ А,

ТРИВ 30 ХВИЛ.,

ТУМБЛЕР ЖИВЛЕННЯ ОСЦИЛОГРАФУ УВІМКНУТО / .

3. Ц І ЛЬ СТАРТ ПЕРЕД 12.00

А НА В; С НА D.

4. Ц І ЛЬ УВЕСЬ Х1:

ВОЛЬТМЕТР Х1 У ШАФІ_1.

5. Ц І ЛЬ Є Х1:

ДЕТАЛЬ Х1 У ЯЩИКУ_3.

6. Ц І ЛЬ ЦИКЛ 5 Х1:

ВОЛЬТМЕТР_Х1 НА СТОЛІ_2.

Опис першої цiльової ситуацiї включає обмежувач старту (СТАРТ ) подiї. Інтерпретацiя його така: “На об'єктi_41 в певний перiод часу (пiсля 15.00) не повинно бути жодного об'єкта”.

У прикладi 2 використується обмежувачи старту i тривалостi. Перший з них показує на момент старту подiї (мiж 10.00 i 11.00), другий визначає тривалiсть процесу (30 хвилин). Двi подiї “осцилограф на столi А” i “тумблер живлення осцилографу увiмкуто” повиннi початися в один i той самий промiжок часу, але не водночас. Друга подiя повинна початися пiсля першоїi тривати 30 хвилин. Приклад 3 iлюструє використання пiд час опису цiльової ситуацiї обмежувача старту з обов'язковим одночасним початком (до 12.00) двох рiзних подiй (А на В) i (С на D). Приклад 4 мiстить квантор загалу “УВЕСЬ ” iiнтерпретується таким чином: “Цiльова ситуацiя вважається досягнутою, якщо всi вольтметри знаходяться у шафi_1”. Інтерпретацiя приклада 5, що мiстить квантор iснування, є така: “В ящику_3 знаходиться хоча б одна деталь_Х1”. Приклад 6 мiстить квантор циклу, у вiдповiдностi з яким п'ять вольтметрiв повиннi бути на столi.

7. Пiдсумки

Таким чином, з опису мови SITPLAN-2 виходить, що розширення можливостей формалiзацiїi формулювань задач у порiвняннi з мовою SITPLAN досягається за рахунок:

1) введення конструкцiй типу фреймiв для опису складних складових об'єктiв i параметрiв стратегiй;

2) введення конструкцiй для подання невизначеностей i часових обмежень в описах продукцiйних правил;

3) введення змiнних, кванторiв загалу та iснування; обмежувачив максимуму, мiнiмуму i циклу, визначених на множинах описових виразiв i дозволяючих формування моделей складних складових об'єктiв;

4) введення конструкцiй для подання об'єктiв, що описуються частково-упорядкованими множинами, якi дозволяють задавати мета-значення (елементи стратегiї планування рiшень);

5) видiлення наборiв продукцiйних правил, що вiдповiдають операторам (дiїi логiчного виводу) i демонам (процесiв i логiчного виводу), якi дозволяють моделювати як процеси цiльоспрямованого, так i випадкового пошуку рiшення;

6) введення конструкцiй типу iмперативiв, дозволяючих використовачу, з одного боку, виконувати пiдказки в процесi рiшення задачi, моделювати процес перетворення ситуацiї певної послiдовностi дiй, с другого - поповняти i вилучати певнi конструкцiї з бази знань в процесi формулювань задач i опису проблемних областей;

7) введення конструкцiй для компактного подання у виглядi продукцiйних правил таблиць рiшень великого обсягу, що мiстять конкретнi значення чи iнтервали значень змiнних;

8) введення конструкцiй, що реалiзують механiзми пояснювання процесiв рiшення i знань.

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

1. Галаган Н.И., Рабинович З.Л. Интеллектуальные решающие системы // Кибернеика. - 1986. - № 3. - с. 18-26.

2. Представление знаний в человеко-машинных робототехнических системах. Том С. Прикладные человеко-машинные системы, ориентированные на знания. - М.: ВЦ АН СССР, ВИНИТИ. 1984. - 291 с.

3. Галаган Н.И. Язык описания задач SITPLAN // Кибернетика. - 1979. - № 2. - с. 89-97.

4. Галаган Н.И. SITPLAN - язык описания задач преобразования ситуаций. - Киев: Изд-во АН УССР, 1979. - 45 с.

5. Гладун В.П. Эвристический поиск в сложных средах. - Киев: Наук. думка, 1077. - 165 с.