Loading AI tools
З Вікіпедії, вільної енциклопедії
STRIPS (Stanford Research Institute Problem Solver) — це автоматичний планувальник, розроблений Річардом Файксом і Нільсом Нілсоном у 1971 році. Найменування програми — абревіатура від Stanford Research Institute Problem Solver (вирішувач проблем Стенфордского дослідного інституту). Програма призначалася для вирішення проблеми формування плану поведінки робота Шекі (Shakey the Robot), що переміщує предмети через множину приміщень. В подальшому слово STRIPS стало також використовуватися для позначення формальної мови, що описує вхідні дані цього планувальника. Ця мова є основною більшої частини сучасних мов опису задач автоматичного планування. Програма STRIPS зробила дуже великий вплив на наступні розробки в галузі штучного інтелекту, і ті базові методики подання знань, які були в ній використані для формування дій, не втратили своєї актуальності і дотепер.
Опис задачі планування на мові STRIPS включає в себе наступні компоненти:
Висловлюючись математично, задача планування в STRIPS-формалізмі — це четвірка , компоненти якої мають наступні значення :
Планом (рішенням) такої задачі планування є послідовність дій (операторів), котра може бути виконаною, починаючи зі стану , і приведе до якогось із цільових станів .
Поточний стан навколишнього середовища — приміщень і предметів у них — представляється набором висловів предикат-аргумент, які в сукупності утворюють модель світу. Так, набір формул: 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).
Програма формує підцілі, вибираючи як оператор:
Тепер перша попередня умова дасть бажане (цільове) становище робота, а другу попередню умову вже виконано.
Так як таблиця операторів, модель світу і цілі представлені за допомогою одного і того ж синтаксису у вигляді конструкцій предикат-аргумент, то, застосовуючи описану вище схему зіставлення, програма досить просто знаходить, які саме операції потрібно виконати для досягнення поставленої мети. Все, що потрібно для цього зробити, — переглянути списки додавань в описі операторів і знайти в них елемент, відповідний до заданої мети.
Підцілі формулюються на основі аналізу попередніх умов, заданих для операторів, означуючи їх підстановкою змінних з формули моделі світу. Як тільки вибрано потрібний оператор, його попередні умови перетворюються і додаються в список підцілей. Якщо в поточному стані можна застосувати не один оператор, то для вибору між «кандидатами» потрібно застосувати будь-яку евристику. Наприклад, можна вибрати той з операторів, який обіцяє найбільше скорочення «відстані» між поточним станом та цільовим. Інший можливий варіант — оператори в таблиці заздалегідь впорядковані і потрібно застосовувати той з них, який стоїть у списку раніше.
Весь процес вирішення проблеми за такою методикою має яскраво виражений рекурсивний характер. Підцілі можуть, в свою чергу, спричинити формулювання підпід-цілей і т. д. На самому нижньому рівні виявляться підцілі, які реалізуються операторами, або не мають попередніх умов, або мають такі попередні умови, які задовольняються тривіально.
Для того щоб краще уявити собі переваги методу подання, використаного в системі STRIPS, розглянемо альтернативний метод. Припустимо, що поточний стан навколишнього світу представлено у вигляді двовимірного масиву з елементами різного розміру (в такому масиві елементи верхнього рівня — комірки — представляють різні приміщення, а елементи другого рівня — об'єкти в цих приміщеннях). Такий варіант подання компактніше описового, але він не дозволяє виконувати операції зіставлення. Можна, звичайно, придумати який-небудь спосіб опису цілей та операцій на мові, орієнтованій на роботі з масивами, але тоді буде втрачено деякі з головних переваг розглянутої методики.
Припустимо тепер, що в множину цілей потрібно включити, наприклад, і таку: «перенести будь-які три ящика в кімнату А», тобто мета задає не єдиний стан світу, а безліч станів, що задовольняють сформульованим умовам. При такій постановці проблеми набір процедур, орієнтованих на табличне подання, доведеться переглянути докорінно. Подання на базі конструкцій предикат-аргумент дозволяє висловити цільовий стан, ввівши у вираз змінні at (X, кімнатаА), at (Y, кімнатаА), at (Z, кімнатаА).
Після цього можна використовувати колишню методику пошуку рішення.
Мова представлення, подібна до тієї, що використовується в STRIPS, з точки зору програмної реалізації є мовою, яка інтерпретується, тобто трансляція з цієї мови виконується інтерпретатором, програмою, яка здатна розпізнавати в операторах мови формули, подібні push (ящик1, кімнатаБ, кімнатаА), і висловити закладений в формулах сенс у термінах виконуваних процедур. Так, сенс наведеної вище формули інтерпретується як необхідність досягти попередніх умов at (робот, кімнатаБ), at (ящик1, кімнатаБ), а потім реалізувати дії, передбачені списками додавань і винятків, тобто, додати в модель світу стан at (робот, кімнатаА), at (ящик1, кімнатаА) і виключити з моделі світу стан at (робот, кімнатаБ), at (ящик1, кімнатаБ).
Такий підхід до інтерпретації отримав найменування процедуральної семантики (procedural semantics), оскільки все, що відомо програмі про сенс формули, — які дії їй потрібно виконати для того, щоб формула отримала значення істина. Однак, це не дуже широке тлумачення сенсу, і такий підхід навряд чи просуне нас далеко у розвитку машинного «розуміння». Але, тим не менш, процедуральних семантика дозволяє нам принаймні побудувати зв'язок між думкою і дією.
![]() |
Це незавершена стаття зі штучного інтелекту. Ви можете допомогти проєкту, виправивши або дописавши її. |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.