Ситуаційне числення

Ситуаці́йне чи́слення (Situational Calculus) — логічний формалізм (логіка першого порядку) розроблений для представлення і обґрунтування динамічно змінних світів, областей і систем. Вперше поняття було введене Джоном Маккарті в 1963 році. Основна версія ситуаційного числення базується на представленні, введеному Реєм Рейтером у 1991 році. Ситуаційне числення завойовує нову популярність у наші дні. Однією із причин такого є те, що його виразність виявилась значно багатшою, ніж було заплановано. Іншою причиною є властивість чітко охарактеризувати сильні і слабкі сторони різних загальних теорій про дії, виражені в цьому формалізмі. Основними елементами ситуаційного числення є:

Ситуації — терм першого порядку, що визначає ймовірнісну історію світу.

Послідовність представлена за допомогою бінарного функціонального символу do :do(a, s) визначає історію, що є результатом додавання нової дії в історію s. Тут також визначається стан світу.

Дія — це діяння, що може бути заподієне у світі, визначається функціональним символом.

Дії є термами першого порядку: Put(x, y): може визначати дію при якій об'єкт x покласти на об'єкт y. Do(put(A,B), s): визначає стан, що є результатом того, що A поклали на B, коли світ перебуває в стані(ситуації) s.

Змінні — це змінні величини, що описують стан світу. Змінна являє собою відношення або функцію, значення якої можуть змінюватися, залежно від ситуації.

Змінні визначені або за допомогою предикатів, або функціональних символів, що приймають терм ситуації як аргумент. closeTo(x, y, s) : x близький до y в ситуації s. Pos(x, s) : визначає позицію x в ситуації s.

Основні елементи ситуаційного числення ред.

Основними елементами ситуаційного числення є дії, ситуації і змінні. Спочатку, як правило, визначають кількість об'єктів, що беруть участь в описанні світу. Ситуаційне числення засновується на відсортованих просторах трьох різних типів: простір дій, простір ситуацій і простір об'єктів; об'єкти включають в себе все, що не належить до дій або ситуацій. Змінні кожного типу можуть бути використані, в той час як дії, ситуації чи об'єкти — це елементи простору і моделюються як предикати чи функції.

Дії ред.

Дії формують собою своєрідний простір. Змінні певного типу дій можуть бути використані в ситуаційному аналізі. Кількість дій ми можемо визначити. Спеціальний предикат Poss використовується для позначення чи є виконуваною дія в певній ситуації, чи ні. Розглянемо приклад : у світі роботів, термом дії, що є можливим до виконання, буде дія move(x, y), котрий моделює пересування в нове місце з координатами (x, y), і дія pickup(o), що моделює підняття роботом об'єкту o.

Ситуації ред.

У ситуаційному аналізі динамічний світ змодельований через пересування по серії ситуацій, котрі є результатами різних дій, виконаних в межах світу. Ситуація зображає історію певних подій. За версією Рейтера, ситуація не зображує стан, всупереч точному значенню. Цей пункт було реалізовано Рейтером наступним чином : Ситуація — завершена послідовність дій в певний період. Це не стан, і не знімок світу в певний момент, це історія. Ситуація, в якій не відбулося жодної дії, зазвичай позначається S₀ і називається початковою ситуацією. Нова ситуація, що результує виконану послідовність дій, позначається з використанням функціонального символу do. Цей функціональний символ використовує як аргументи ситуацію і дію, і в результаті повертає нову ситуацію, котра встановиться після виконання даного діяння в попередній (початковій) ситуації. Той факт, що ситуація — це послідовність дій і не є станом, посилюється за допомогою аксіоми, котра констатує: do(a, s) еквівалентно do(a’,s’) . Умова була б не коректною, якщо б ситуації були станами, оскільки дві різні дії, виконані в двох різних станах можуть дати в результаті той самий стан. Розглянемо приклад : у світі роботів, якщо перша дія робота — пересунутись на ділянку (2,3), то першою дією буде move(2,3) , а результуючою ситуацією — do(move(2,3),S₀). Якщо наступною буде дія «підняти м'ячик», то результуючою буде ситуація do(pickup(Ball), do(move(2,3),S₀)). Ситуаційні терми do(move(2,3),S₀) і do(pickup(Ball), do(move(2,3),S₀)) — визначають послідовність виконаних дій, і це не опис стану, що є результатом виконаної дії.

Змінні ред.

Змінні — це певні твердження, значення істинності яких можуть змінюватися, та моделюються за допомогою відносних змінних, предикатами, які використовують ситуацію як фінальний аргумент. Також можливі функціональні змінні — функції, які використовують ситуацію як фінальний аргумент і повертають ситуаційно-залежні значення. Змінні можна розуміти як «властивості світу». Наприклад, змінна is_carrying (o; S) може бути використана для індикації чи тримає робот конкретний об'єкт o в конкретній ситуації S. Робот спочатку нічого не тримає, is_carrying (Ball; S) є хибністю (FALSE) , у той час як is_carrying (Ball; do (pickup (Ball); S)) є істиною (TRUE). Місце знаходження робота може бути змодельоване за допомогою функціональної змінної location(S), яка повертає місцезнаходження (x; y) робота в конкретної ситуації S.

Аксіоматизація ред.

Опис динамічного світу закодовано в логіці другого порядку, використовуючи три види аксіоматизації:

Аксіоматизация дій ;
Аксіоматизация станів світу;
Фундаментальні аксіоми.

Передумови дій ред.

Деякі дії можуть бути нездійсненними в даних ситуаціях. Наприклад, неможливо покласти об'єкт, якщо його не тримаєш в цей момент. Саме через це дії мають передпосилання: достатні умови яких повинні відповідати стану світу перш ніж дії будуть виконані в цих станах. Обмеження на вчинення дій змодельовані за допомогою літералів форми Poss(a; S), де a — дія, S — ситуація і Poss — спеціальний бінарний предикат, що позначає можливість виконання дії в заданій ситуації. Наприклад, умова того, що можна кинути об'єкт, тільки в тому випадку, якщо ти його тримаєш, моделюється таким чином: Poss (drop (o); S) — is_carrying (o; S).

Проблеми ситуаційного числення ред.

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

Проблема фрейму ред.

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

Has (person1, phoneBook, s0);
AtHome (person2, s0);

І нехай є наступні аксіоми:

("P1, p2, s) [Has (p1, phoneBook, s) -> KnowNumber (p1, p2, result (p1, seekNumber (p2, phoneBook), s))];
(„P1, p2, s) [KnowNumber (p1, p2, s) & AtHome (p2, s) -> Talking (p1, p2, result (p1, call (p2), s));

Перші дві флюенти говорять про те, що в початковій ситуації у деякої особи person1 є телефонна книга, і якась особа person2 перебуває вдома. Аксіома a1 стверджує, що якщо у деякого особи є телефонна книга, то вона може знайти телефонний номер будь-якої іншої особи (дія seekNumber). Аксіома a2 стверджує, що якщо у деякої особи є телефонний номер іншої особи, і ця інша особа перебуває вдома, то можна з нею поговорити, виконавши дзвінок (дія call). Покладаючись на здоровий глузд, ми можемо зробити наступний висновок. Якщо в початковій ситуації від імені person1 виконати послідовність дій [seekNumber (person2, phoneBook), call (person2)], то ми досягнемо ситуації, в якій відбувається розмова між двома персонами (Talking (person1, person2, sx)). Однак ситуаційне обчислення ставить перешкоду в досягненні цього простого висновку.

Виконавши першу дію, перебуваючи в початковій ситуації, ми опинимося у новій ситуації — result (person1, seekNumber (person2, phoneBook), S₀). Будемо позначати її S₁. Ця ситуація може бути зовсім не тією ж самою ситуацією, що і S₀. Вважати так навіть правильно, тому що ситуація змінилася, і ми тепер знаємо потрібний нам телефонний номер. А це означає, що у нас є пара фактів KnowNumber (person1, person2, s1) і AtHome (person2, s0), але вони не є посиланням для аксіоми a2, так як в них мова йде про різні ситуації. Значить того, що ми описали, недостатньо. Щоб послідовність дій спрацювала, необхідно переписати першу аксіому наступним чином:

(«P1, p2, s) [Has (p1, phoneBook, s) & AtHome (p2, s) ->AtHome (p2, result (p1, seekNumber (p2, phoneBook), s)) & KnowNumber (p1, p2, result (p1, seekNumber (p2, phoneBook), s))].

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

Зазвичай проблему фрейму формулюють таким чином: як визначити, які пропозиційні флюенти, що використовуються при описі фактів про ситуацію, залишаються незмінними після виконання дії? Або, іншими словами, які флюенти у новій ситуації (після виконання дії) будуть мати ті ж значення, що і до виконання дії.

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

Проблема непрямих ефектів ред.

Друга проблема ситуаційного числення називається проблемою непрямих ефектів (ramification problem), сенс якої полягає в тому, що дуже складно описати всі ефекти дії. Так, наприклад, переміщення шафи роботом з однієї кімнати в іншу спричинить переміщення і всіх книг всередині шафи, і звільнення місця в кімнаті, і зміна зовнішнього вигляду кімнати, і багато інших змін. Але випливає питання, який спосіб є найбільш адекватним для опису таких змін? Опис всіх ефектів в аксіомах переходу до нової ситуації зажадає дуже великої кількості таких аксіом.

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

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

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

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

Обмежувальні умови ред.

Третя проблема носить назви проблеми обмежувальних умов (qualification problem). Суть її полягає в тому, що дуже важко перерахувати всі умови, які можуть перешкоджати виконанню дії. Наприклад, нехай робот повинен виконати дію — перемістити шафу з північного кута кімнати в південний. Виконанню такого завдання може перешкоджати безліч речей:

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

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

Наслідки проблем ред.

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

Вклад вчених в розвиток ситуаційного числення ред.

Найвагоміший вклад в розвиток ситуаційного числення внесли:

Рей Рейтер,
Джон Маккарті,
Вчені Міллер та Шенехен.

Рей Рейтер ред.

Рейтером в запропонованому ситуаційному численні для завдання кінцевої послідовності примітивних дій був введений бінарний конструктор do(a, s), що дозволяє будувати послідовність дій шляхом додавання в цю послідовність дії »a“, що виконується в ситуації «s». Ситуаційне числення лежить в основі створеного ним логічного підходу до створення динамічних систем, що володіють функціями планування, управління, моделювання, оновлення баз даних, діагностики, а також застосовується для розробки програмного забезпечення агентів і роботів.

Джон Маккарті ред.

У своїй роботі Маккарті дає таке визначення логічного підходу до моделювання поведінки складних об'єктів у штучному інтелекті: «Логічний підхід — це створення комп'ютерних програм, в яких подаються знання про світ взагалі, знання про ситуації в ньому, а також знання про цілі в вигляді виразів на деякій логічній мові. Далі, необхідно описати дії для досягнення цілей». Маккарті зауважує, що наприкінці 1980 р. немонотонний вивід, обраний як один з найперспективніших для використання в цих цілях, а також, що ситуації, багаті об'єктами, які неможливо описати повністю і можливо говорити тільки про деякі їх аспекти. Він припускає, що на основі фактів, що описують ситуацію, і загальних законів, які задають виконання дій і виникнення подій, можливо описати деякі ситуації, які з'являться в майбутньому. Для формалізації дій в ситуаційному численні, Маккарті вводить поняття: передісторія, планування і передбачення. Передісторія Маккарті розглядає як одне з найпростіших понять, оскільки вона описує те, що вже сталося. Він пропонує ставити її як допомогу опису ситуацій і подій, які є частково впорядкованими в часі. Для цього Маккарті вводить набір ситуацій, що описуються подіями і відносинами між ними. В ситуаційному численні Маккарті оригінально введена і використана конструкція: s' = result (e, s) для позначення подій або дій, які здійснюють перехід з однієї ситуації до іншої. Маккарті зауважує, що в передісторії ситуації описуються логічними формулами, які містять попередні ситуації та події (дії), що описують переходи між ними. Він зазначає, що передісторії можуть бути суперечливими. Наприклад, якщо записано, що хтось прилетів до Москви, і в такій ситуації додано, що він знаходиться в Пекіні, то це приклад суперечливої передісторії. Для того щоб цього не відбувалося, Маккарті вводить поняття коректної передісторії і зауважує, що ще поки не ясно як її відстежувати. Також для моделювання поведінки складних об'єктів, їм розробляється апарат немонотонних міркувань з передісторією. Дж. Маккарті планує розробити інтерпретатор, що дозволяє будувати з незв'язаних ситуацій і подій різні передісторії.

Міллер та Шенехен ред.

Ще одним внеском у науково-практичний напрямок, що займається проблемами моделювання динамічної поведінки об'єктів, є числення подій, створене Р. Міллером та M. Шенехеном. Вони розробили кілька аксіоматизацій для числення подій в рамках класичної логіки 1-го порядку, які є формальним апаратом для опису міркувань про дії та їх зміни.

Термін «Числення подій» був вперше введений Ковальським і Серготом в 1986 р., як логічна програма для подання дій (або подій) та їх результатів, а також для міркувань про них, яка розроблялася в основному для додатків до баз даних. Слід зазначити, що в даний час на основі числення подій розроблений ряд додатків, в яких описується аксіоматизація числення подій. Р. Міллер і M. Шенехен відзначають, що навіть якщо обмежитися формалізмами класичної логіки для опису числення подій, існує ряд різних аксіоматизацій.

Р. Міллер і M. Шенехен вперше представили шість аксіом, які є проблемно-незалежними, і проілюстрували їх використання в ряді додатків. Вчені відзначили, що центральною особливістю числення подій є те, що воно на передісторії, тобто передбачається тимчасова структура, яка є проблемно-незалежною для будь-якого виконання дій. Твердження про те, коли різні дії сталися в цій структурі, включаються до її опису. Тимчасова структура зазвичай передбачається лінійною — зазвичай набір додатних дійсних чи цілих чисел, хоча вона може бути і розгалуженою. Час представляється додатним дійсними числами, і аксіоми для опису часової структури включаються в розроблене ними числення. Основна ідея числення подій — установка значень істиності змінних величин, якими є властивості, в задані відліки часу. Змінні величини мають значення «істина», якщо вони ініціюються за допомогою виконання інших дій в заданому тимчасовому відліку. Аналогічно, змінна величина приймає значення «хибність» в заданому тимчасовому відліку, якщо вона була завершена або не ініційована в заданому тимчасовому відліку. Зазначимо, що аксіоми, розроблені Р. Міллером та M. Шенехеном, можуть бути використані для опису ініціювання та завершення змінних величин за допомогою виконання дій, на які вони посилаються як на події або дії типу подій.

Посилання ред.

STRIPS-формализм в обзоре по языкам планирования (Проект „„Интеллектуальное планирование““)
^{[недоступне посилання з липня 2019} СИТУАЦИОННЫЕ ИСЧИСЛЕНИЯ ]