STRIPS

Немає перевірених версій цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

STRIPS (Stanford Research Institute Problem Solver) — це автоматичний планувальник, розроблений Річардом Файксом і Нільсом Нілсоном у 1971 році. Найменування програми — абревіатура від Stanford Research Institute Problem Solver (вирішувач проблем Стенфордского дослідного інституту). Програма призначалася для вирішення проблеми формування плану поведінки робота Шекі (Shakey the Robot), що переміщує предмети через множину приміщень. В подальшому слово STRIPS стало також використовуватися для позначення формальної мови, що описує вхідні дані цього планувальника. Ця мова є основною більшої частини сучасних мов опису задач автоматичного планування. Програма STRIPS зробила дуже великий вплив на наступні розробки в галузі штучного інтелекту, і ті базові методики подання знань, які були в ній використані для формування дій, не втратили своєї актуальності і дотепер.

Визначення

Опис задачі планування на мові STRIPS включає в себе наступні компоненти:

Початковий стан;
Визначення цільових станів — ситуацій, яких планувальник намагається досягнути;
Перелік можливих дій (операторів). Кожна дія включає:
- передумови (preconditions) — попередня умова, яка має бути задоволеною, для того щоб дія могла бути виконаною;
- післяумови (postconditions) — зміни стану, що відбудуться після виконаання дії.

Висловлюючись математично, задача планування в STRIPS-формалізмі — це четвірка $\langle P,O,I,G\rangle$ , компоненти якої мають наступні значення :

$P$ — множина умов (conditions)
$O$ — множина операторів; кожен оператор в свою чергу — це четвірка $\langle \alpha ,\beta ,\gamma ,\delta \rangle$ . Усі елементи четвірки є множинами. По черзі, це умови, які:
1. мають бути задоволені перед виконанням операції
2. мають бути незадоволені (щоб виконання операції мало сенс)
3. такі, що задовольняють дану операцію
4. порушені даною операцією
$I$ — початковий стан — перелік умов, які рахуються вже задоволеними (усі інші умови рахуються незадоволеними);
$G$ — специфікація бажаної цілі; задаєтся парою $\langle N,M\rangle$ , яка визначає, які умови мають бути задоволені і незадоволені, для того, щоб ціль рахувалася досягненою.

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

Принцип представлення даних

Поточний стан навколишнього середовища — приміщень і предметів у них — представляється набором висловів предикат-аргумент, які в сукупності утворюють модель світу. Так, набір формул: W = {at (робот, кімнатаА), at (ящик1, кімнатаБ), at (ящик2, кімнатаВ)} означає, що робот знаходиться в кімнаті А і є два ящики, один з яких знаходиться в кімнаті Б, а другий — в кімнаті В.

Дії, які може виконати робот, приймають форму операторів, які можливо застосувати до поточної моделі світу. Ці оператори дозволяють додати в модель деякі факти (відомості) або вилучити їх з моделі. Наприклад, виконання операції: «Перемістити робота з кімнати А в кімнату Б» в моделі світу призведе до формування нової моделі W. При цьому факт at (робот, кімнатаА) буде вилучено з моделі, а доданий факт at (робот, кімнатаБ). В результаті нова модель світу буде мати вигляд: W = {at (робот, кімнатаБ), at (ящик1, кімнатаБ), at (ящик2, кімнатаВ)}.

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

Таблиці операторів і методика «засіб-аналіз завершення»

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

push (X, Y, Z)
Попередні умови at (робот, Y), at (X, Y)
Список вилучень at (робот, Y), at (X, Y)
Список додатків at (робот, Z), at (X, Z)

Тут вираз push (X, Y, Z) означає, що об'єкт X виштовхується (роботом) з положення Y в положення Z, причому X, Y і Z — змінні в області значень, що охоплює доступну множину об'єктів, у той час як робот, кімнатаА, ящик1, кімнатаБ, ящик2, кімнатаВ — це імена конкретних об'єктів з цієї множини.

З точки зору програміста змінні X, У і Z у визначенні оператора, що заданий елементом таблиці, — це аналоги формальних параметрів у визначенні процедури, яка відповідає такій дії: «Виштовхнути який-небудь об'єкт з будь-якого положення в будь-яке інше положення, якщо мають місце задані попередні умови, потім видалити формули, зазначені в списку видалення, і додати формули, зазначені в списку додавання».

З точки зору логіки елемент push таблиці операторів може бути прочитаний у вигляді формули, яка стверджує:

«За будь-яких X, Y і Z об'єкт X виштовхується з Y в Z, якщо робот і об'єкт X в Y, а потім стан зміняться заміною Y на Z».

Цільовий стан також представляється формулою, наприклад: а1 (ящик1, кімнатаА), а2 (ящик2, кімнатаБ).

Програма STRIPS включає множину процедур, які виконують різні функції, зокрема:

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

Щоб уявити собі, як на практиці використовувати подібну структуру уявлень, розглянемо просту задачу: як готуватися до ланчу з потенційним клієнтом. Для цього, по-перше, потрібно мати у своєму розпорядженні певну суму готівкових грошей, щоб розплатитися, по-друге, потрібно зголодніти, оскільки мова йде про прийом їжі. Сформульовані умови можна розглядати як попередні для досягнення мети «ланч». Ця мета може бути представлена оператором. Після завершення ланчу гроші будуть витрачені, а у вас зникне почуття голоду. Ці прості факти знайшли відображення в списках видалень і додавань для оператора have lunch. Однак володіння певною сумою готівкових грошей не можна розглядати як природний стан клієнта. Спочатку потрібно отримати їх в банкоматі, що, в свою чергу, вимагає пересування. Отже, потрібно додати в таблицю операторів ще два елементи — at cash mashine (пересування до банкомата) і have money (одержання готівки).

Цей простий приклад має досить цікаві властивості. Зазначимо, що формули для моделі світу в початковому стані: at (work), have (transport) залишаються в недоторканності до тих пір, поки ми явно не видалимо їх. Таким чином, у вас залишається можливість пересуватися по місту протягом усього часу реалізації плану, оскільки формально відсутні будь-які ознаки, що ця можливість може бути втрачена (наприклад, автомобіль буде викрадений, або ви потрапите в дорожню аварію, або по дорозі до банкомату скінчиться бензин). Точно так само може щось статися і з банкоматом — він може «зажувати» картку, або ви можете забути витягнути її, або може раптом з'явитися механічна рука і ножицями розрізати її. Але передбачається, що послідовність дій, представлена в створеному машиною плані, не повинна передбачати такі виняткові ситуації, хоча в реальній обстановці це може мати місце.

Така стратегія «зворотних» міркувань, тобто від цілей до підцілей, надзвичайно поширена в програмах штучного інтелекту та експертних системах, наприклад Mycin. Але навіть на такій обмеженій множині операторів, як у нашому прикладі, може існувати кілька варіантів виконання дій. У цьому разі необхідно буде організувати якийсь механізм пошуку найкращої послідовності операторів, що призводять до досягнення сформульованої мети.

По суті, в системі STRIPS при виборі операторів виконується пошук в просторі станів. У результаті формується план, тобто послідовність операторів, що приводить до досягнення мети, причому за основу береться стратегія «зворотного» простежування. Основна відмінність STRIPS від інших аналогічних програм полягає в тому, що замість методики «генерація-перевірка» для пересування в просторі станів використовується інший метод, відомий як «засіб — аналіз завершення» (means-ends analisys).

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

Основна ідея, яка лежить в основі методу «засіб — аналіз завершення», полягає в тому, щоб з кожною новою операцією відмінність між поточним станом та цільовим зменшувалася, тобто кожна чергова операція повинна наближати нас до мети. Але це передбачає включення в розгляд деякої міри для оцінки «відстані» в просторі станів. Такий захід дуже схожий на оціночну функцію. Якщо наступна мета сформульована у вигляді at (ящик1, кімнатаА),а ящик знаходиться в кімнаті Б, то переміщення робота з кімнати А в кімнату У ніяк не «наблизить» поточний стан до цільового. А ось переміщення робота з кімнати А в кімнату Б зменшить відстань між поточним і цільовим станом, оскільки робот тепер зможе на черговому кроці виштовхнути ящик з кімнати Б в кімнату А. У цьому сенсі поведінка робота «мотивується» від цільового стану до підцілей, які можуть привести до досягнення сформульованої мети.

Насправді програма STRIPS зчитує список цілей на зразок такого:at (ящик1, кімнатаА), at (ящик2, кімнатаБ), а потім зіставляє ці цілі і список додавання в описі кожного оператора. Так, мета at (ящик1, кімнатаА) буде відповідати елементу at (X, Z) в списку додатків оператора push (X, Y, Z).

Схема зіставлення полягає у підстановці значень змінних Х/ящик1, Z / кімнатаА та призводить до рівності виразів at (ящик1, кімнатаА) та at (X, Z).

Програма формує підцілі, вибираючи як оператор:

Підстановкою {Х/ящик1, Z / кімнатаА} означити попередню умову, що є похідним від відповідності at (ящик1, кімнатаА) та at (X, Z), і отримати таким чином at (po6от, Y), at (ящик1, Y).
Знайти в моделі світу формулу, яка представляла б поточне положення ящика а1 (ящик1, кімнатаБ), порівняти її з at (ящик1, Y) і в результаті цього порівняння сформулювати підстановку {Y / кімнатаБ}, яку потім застосувати до вже частково визначеної попередньої умови. В результаті буде сформульована чергова підціль: at (робот, кімнатаБ), at (ящик1, кімнатаБ).

Тепер перша попередня умова дасть бажане (цільове) становище робота, а другу попередню умову вже виконано.

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

Підцілі формулюються на основі аналізу попередніх умов, заданих для операторів, означуючи їх підстановкою змінних з формули моделі світу. Як тільки вибрано потрібний оператор, його попередні умови перетворюються і додаються в список підцілей. Якщо в поточному стані можна застосувати не один оператор, то для вибору між «кандидатами» потрібно застосувати будь-яку евристику. Наприклад, можна вибрати той з операторів, який обіцяє найбільше скорочення «відстані» між поточним станом та цільовим. Інший можливий варіант — оператори в таблиці заздалегідь впорядковані і потрібно застосовувати той з них, який стоїть у списку раніше.

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

Аналіз методу подання і управління

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

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

Припустимо тепер, що в множину цілей потрібно включити, наприклад, і таку: «перенести будь-які три ящика в кімнату А», тобто мета задає не єдиний стан світу, а безліч станів, що задовольняють сформульованим умовам. При такій постановці проблеми набір процедур, орієнтованих на табличне подання, доведеться переглянути докорінно. Подання на базі конструкцій предикат-аргумент дозволяє висловити цільовий стан, ввівши у вираз змінні at (X, кімнатаА), at (Y, кімнатаА), at (Z, кімнатаА).

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

Пошук рішення проблеми передбачає використання евристик, оскільки, як правило, існує безліч варіантів, серед яких доводиться вибирати.
При одноманітному поданні простіше знаходити ті оператори, які можна застосувати в конкретній ситуації, і переглянути, який ефект дасть їх застосування. Однакове уявлення також значно спрощує програмну реалізацію процесу пошуку.
Часто вдається досягти заданої мети, застосовуючи методику зниження рівня складності проблеми (problem reduction). При цьому проводиться зворотна трасування проблеми — «відштовхуючись» від мети, з'ясовуємо, які попередні умови потрібно задовольнити для її досягнення, і формулюємо на основі таких міркувань простіші підцілі. Цей процес рекурсивно продовжується до тих пір, поки не будуть сформульовані тривіальні підцілі, досяжні за допомогою найпростіших операцій.

Мова представлення, подібна до тієї, що використовується в STRIPS, з точки зору програмної реалізації є мовою, яка інтерпретується, тобто трансляція з цієї мови виконується інтерпретатором, програмою, яка здатна розпізнавати в операторах мови формули, подібні push (ящик1, кімнатаБ, кімнатаА), і висловити закладений в формулах сенс у термінах виконуваних процедур. Так, сенс наведеної вище формули інтерпретується як необхідність досягти попередніх умов at (робот, кімнатаБ), at (ящик1, кімнатаБ), а потім реалізувати дії, передбачені списками додавань і винятків, тобто, додати в модель світу стан at (робот, кімнатаА), at (ящик1, кімнатаА) і виключити з моделі світу стан at (робот, кімнатаБ), at (ящик1, кімнатаБ).

Такий підхід до інтерпретації отримав найменування процедуральної семантики (procedural semantics), оскільки все, що відомо програмі про сенс формули, — які дії їй потрібно виконати для того, щоб формула отримала значення істина. Однак, це не дуже широке тлумачення сенсу, і такий підхід навряд чи просуне нас далеко у розвитку машинного «розуміння». Але, тим не менш, процедуральних семантика дозволяє нам принаймні побудувати зв'язок між думкою і дією.