STRIPS (Stanford Research Institute Problem Solver) — це автоматичний планувальник, розроблений Річардом Файксом і Нільсом Нілсоном у 1971 році. Найменування програми — абревіатура від Stanford Research Institute Problem Solver (вирішувач проблем Стенфордского дослідного інституту). Програма призначалася для вирішення проблеми формування плану поведінки робота Шекі (Shakey the Robot), що переміщує предмети через множину приміщень. В подальшому слово STRIPS стало також використовуватися для позначення формальної мови, що описує вхідні дані цього планувальника. Ця мова є основною більшої частини сучасних мов опису задач автоматичного планування. Програма STRIPS зробила дуже великий вплив на наступні розробки в галузі штучного інтелекту, і ті базові методики подання знань, які були в ній використані для формування дій, не втратили своєї актуальності і дотепер.
Визначення
Опис задачі планування на мові STRIPS включає в себе наступні компоненти:
Початковий стан; Визначення цільових станів — ситуацій, яких планувальник намагається досягнути; Перелік можливих дій (операторів). Кожна дія включає: передумови (preconditions) — попередня умова, яка має бути задоволеною, для того щоб дія могла бути виконаною; післяумови (postconditions) — зміни стану, що відбудуться після виконаання дії.
Висловлюючись математично, задача планування в STRIPS-формалізмі — це четвірка , компоненти якої мають наступні значення :
— множина умов (conditions) — множина операторів; кожен оператор в свою чергу — це четвірка . Усі елементи четвірки є множинами. По черзі, це умови, які: мають бути задоволені перед виконанням операції мають бути незадоволені (щоб виконання операції мало сенс) такі, що задовольняють дану операцію порушені даною операцією — початковий стан — перелік умов, які рахуються вже задоволеними (усі інші умови рахуються незадоволеними); — специфікація бажаної цілі; задаєтся парою , яка визначає, які умови мають бути задоволені і незадоволені, для того, щоб ціль рахувалася досягненою.
Планом (рішенням) такої задачі планування є послідовність дій (операторів), котра може бути виконаною, починаючи зі стану , і приведе до якогось із цільових станів .
Принцип представлення даних Поточний стан навколишнього середовища — приміщень і предметів у них — представляється набором висловів предикат-аргумент, які в сукупності утворюють модель світу. Так, набір формул: 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, кімнатаБ).
Тепер перша попередня умова дасть бажане (цільове) становище робота, а другу попередню умову вже виконано.
Так як таблиця операторів, модель світу і цілі представлені за допомогою одного і того ж синтаксису у вигляді конструкцій предикат-аргумент, то, застосовуючи описану вище схему зіставлення, програма досить просто знаходить, які саме операції потрібно виконати для досягнення поставленої мети. Все, що потрібно для цього зробити, — переглянути списки додавань в описі операторів і знайти в них елемент, відповідний до заданої мети.
Підцілі формулюються на основі аналізу попередніх умов, заданих для операторів, означуючи їх підстановкою змінних з формули моделі світу. Як тільки вибрано потрібний оператор, його попередні умови перетворюються і додаються в список підцілей. Якщо в поточному стані можна застосувати не один оператор, то для вибору між «кандидатами» потрібно застосувати будь-яку евристику. Наприклад, можна вибрати той з операторів, який обіцяє найбільше скорочення «відстані» між поточним станом та цільовим. Інший можливий варіант — оператори в таблиці заздалегідь впорядковані і потрібно застосовувати той з них, який стоїть у списку раніше.
Весь процес вирішення проблеми за такою методикою має яскраво виражений рекурсивний характер. Підцілі можуть, в свою чергу, спричинити формулювання підпід-цілей і т. д. На самому нижньому рівні виявляться підцілі, які реалізуються операторами, або не мають попередніх умов, або мають такі попередні умови, які задовольняються тривіально.
Аналіз методу подання і управління