Ситуаці́йне чи́слення (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.

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

Змінні Змінні — це певні твердження, значення істинності яких можуть змінюватися, та моделюються за допомогою відносних змінних, предикатами, які використовують ситуацію як фінальний аргумент. Також можливі функціональні змінні — функції, які використовують ситуацію як фінальний аргумент і повертають ситуаційно-залежні значення. Змінні можна розуміти як «властивості світу». Наприклад, змінна 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).

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

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

Проблема фрейму Перша проблема отримала назву проблеми фрейму. Природний спосіб зробити опис дії коротким — сконцентруватися на описі змін, що викликаються дією, залишаючи за кадром факти, на які дія не впливає. Нехай, наприклад, ми володіємо описом деякої ситуації (природно частковим описом, тобто безліччю фактів). Назвемо її початковою ситуацією — S0. Нехай в опис ситуації входять такі факти, виражені флюентами (фактами): 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), S0). Будемо позначати її S1. Ця ситуація може бути зовсім не тією ж самою ситуацією, що і S0. Вважати так навіть правильно, тому що ситуація змінилася, і ми тепер знаємо потрібний нам телефонний номер. А це означає, що у нас є пара фактів 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), сенс якої полягає в тому, що дуже складно описати всі ефекти дії. Так, наприклад, переміщення шафи роботом з однієї кімнати в іншу спричинить переміщення і всіх книг всередині шафи, і звільнення місця в кімнаті, і зміна зовнішнього вигляду кімнати, і багато інших змін. Але випливає питання, який спосіб є найбільш адекватним для опису таких змін? Опис всіх ефектів в аксіомах переходу до нової ситуації зажадає дуже великої кількості таких аксіом.

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

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

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

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

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