Кіріспе
Ситуациялық есептеу динамикалық салаларды бейнелеу және олар туралы ой жүргізуге арналған логикалық формализм. Оны алғаш рет 1963 жылы Джон Маккарти енгізді. Осы мақалада ұсынылған ситуациялық есептеудің негізгі нұсқасы 1991 жылы Рей Рейтер енгізген нұсқаға негізделген. Содан кейін Маккартидің 1986 жылғы нұсқасы және логикалық бағдарламалау түзілімі туралы бөлімдер келеді.
Элементтер
Ситуациялық калькульдің негізгі элементтері – әрекеттер, ағындар және жағдайлар. Әдетте, әлемді сипаттауға бірнеше объектілер де қатысады. Ситуациялық калькуль үш түрге бөлінген реттелген доменге негізделген: әрекеттер, жағдайлар және объектілер, мұндағы объектілер әрекеттер мен жағдайлар емес, барлық нәрсені қамтиды. Әр түрдегі айнымалыларды қолдануға болады. Әрекеттер, жағдайлар және объектілер доменнің элементтері болса, ағындар предикаттар немесе функциялар түрінде модельделеді.
Іс-шаралар
Іс-әрекеттер белгілі бір доменді құрайды. Іс-әрекет түріндегі айнымалыларды, сондай-ақ нәтижесі іс-әрекет түрінде болатын функцияларды қолдануға болады. Іс-әрекеттерді сандық тұрғыдан бағалауға болады. Мысал ретінде, робот әлемінде роботтың жаңа орынға қозғалуын модельдейтін және роботтың бір объектіні (о) алуын модельдейтін әрекеттер болуы мүмкін. Әрекеттің орындалу мүмкіндігін көрсету үшін арнайы Poss предикаты қолданылады.
Жағдайлар
Ситуациялық есептеуде динамикалық әлем әртүрлі әрекеттердің орындалуы нәтижесінде бірнеше жағдайлар арқылы даму ретінде модельделеді. Ситуация – іс-әрекеттердің оқиғаларының тарихын көрсетеді. Мұнда сипатталған Рейтердің ситуациялық есептеуінің нұсқасында, ситуация терминнің тікелей мағынасына да, Маккарти мен Хейстің бастапқы анықтамасына да қайшы келеді, ситуация күйді білдірмейді. Рейтер осы мәселені былай түйіндейді: ситуация – әрекеттердің шекті тізбегі. Міне, сонымен. Бұл күй емес, сәтте түсірілген сурет емес, бұл тарих. Ешқандай әрекет орындалмастан бұрынғы ситуация әдетте S0 деп белгіленеді және бастапқы ситуация деп аталады. Әрекетті орындау нәтижесінде туындайтын жаңа ситуация do функциясының символымен белгіленеді (кейбір басқа сілтемелерде result қолданылады). Бұл функция символының аргументтері ретінде ситуация мен әрекет, ал нәтижесінде – берілген ситуацияда берілген әрекетті орындаудан туындайтын ситуация болады. Ситуациялар – әрекеттердің тізбегі, ал күйлер емес, және бұл аксиомамен күшпен сақталады: егер және тек қана егер және тең болса. Егер ситуациялар күйлер болса, бұл шарттың мағынасы жоқ, себебі екі түрлі күйде орындалған екі түрлі әрекет бірдей күйге әкелуі мүмкін. Мысалы, робот әлемінде, егер роботтың алғашқы әрекеті орынға жылжу болса, бірінші әрекеті және нәтижесінде пайда болған ситуация, ал егер оның келесі әрекеті допты алу болса, нәтижесінде пайда болған ситуация. Ситуация сияқты терминдер орындалған әрекеттердің тізбегін көрсетеді, ал орындалу нәтижесінде туындаған күйдің сипаттамасын емес.
A situation is a finite sequence of actions. Period. It's not a state, it's not a snapshot, it's a history. The situation before any actions have been performed is typically denoted S 0 and called the initial situation. The new situation resulting from the performance of an action is denoted using the function symbol do (Some other references also use result). This function symbol has a situation and an action as arguments, and a situation as a result, the latter being the situation that results from performing the given action in the given situation. The fact that situations are sequences of actions and not states is enforced by an axiom stating that is equal to if and only if and This condition makes no sense if situations were states, as two different actions executed in two different states can result in the same state. In the example robot world, if the robot's first action is to move to location , the first action is and the resulting situation is If its next action is to pick up the ball, the resulting situation is Situations terms like and denote the sequences of executed actions, and not the description of the state that result from execution.
Ағыстығы
Шындық мәні өзгеруі мүмкін мәлімдемелер реляциялық флюенттермен, жағдайды соңғы аргумент ретінде қабылдайтын предикаттармен модельделеді. Сондай-ақ функционалдық флюенттер де болуы мүмкін, олар жағдайды соңғы аргумент ретінде қабылдайды және жағдайға тәуелді мәнді қайтарады. Флюенттерді "әлемнің қасиеттері" деп қарастыруға болады. Мысалда, флюентті роботтың белгілі бір жағдайда нақты бір затты алып жүргенін көрсету үшін қолдануға болады. Егер робот бастапқыда ештеңе алып жүрмесе, онда ол жалған болады, ал болса, онда шын болады. Роботтың орналасқан жерін функционалдық флюент арқылы модельдеуге болады, ол белгілі бір жағдайда роботтың орналасқан жерін қайтарады.
Формулалар
Динамикалық әлемнің сипаттамасы екінші реттік логикада үш түрлі формула арқылы кодталады: әрекеттерге қатысты формулалар (алғы шарттар мен салдары), әлемнің күйіне қатысты формулалар және негізгі аксиомалар.
Әрекеттің әсері
Бір жағдайда әрекет жасалуы мүмкін болғандықтан, сол әрекеттің жағдайларға (fluents) тигізетін әсерін анықтау қажет. Бұл эффект аксиомалары арқылы іске асырылады. Мысалы, затты көтеріп алу роботтың оны алып жүруіне себеп болатынын былай модельдеуге болады:
Сонымен қатар, ағымдағы жағдайға байланысты болатын шартты әсерлерді де көрсетуге болады. Төмендегі модельдер кейбір заттардың қажалдағыш (fragile) екенін (қажалдағыш предикаты арқылы көрсетіледі) және оларды тастағанда олардың сынғанын (бұзылған fluent арқылы көрсетіледі) көрсетеді:
Бұл формула әрекеттердің әсерін дұрыс сипаттағанымен, логикада әрекетті толыққанды сипаттау үшін жеткіліксіз, себебі кадрлық мәселе бар.
Фрейм мәселесі
Жоғарыда келтірілген формулалар іс-әрекеттердің салдары туралы ой-пікір қалыптастыруға ыңғайлы болғанымен, олардың бір маңызды кемшілігі бар – олар іс-әрекеттердің нәтижесінде болмайтын өзгерістерді анықтауға қолданылмайды. Мысалы, бір затты көтергеннен кейін роботтың орны өзгермейді деген қорытындыға келгенің өзі қиын. Бұл үшін «кадр аксиомасы» деп аталатын формула қажет:
Кадр аксиомаларын көрсету қажеттігі динамикалық әлемдерді аксиомалаудағы мәселе ретінде ұзақтан бері танылып келеді және бұл «кадр проблемасы» деп белгілі. Мұндай аксиомалардың саны көбінесе өте көп болғандықтан, жобалаушыға қажетті кадр аксиомасын жіберіп алуы немесе әлем туралы сипаттама өзгертілгенде барлық қажетті аксиомаларды өзгертуді ұмытуы ықтимал.
Негізгі аксиомалар
Ситуациялық калькульдің негізгі аксиомалары жағдайлардың тарихтар екенін формалдайды. Олар жағдайлар бойынша екінші реттік индукция сияқты басқа да қасиеттерді қамтиды.
Регрессия
Регрессия – жағдай есептеуінде салдарларды дәлелдеу механизмі. Ол жағдайды қамтитын формуланы, әрекет a және жағдай s қамтитын формуламен өрнектеуге негізделген, бірақ бұрынғы жағдайды емес. Осы процедураны қайталап орындау арқылы бастапқы жағдай S0 ғана қамтылған эквивалентті формулаға жетуге болады. Дәлелдеу бұл формуладан бастапқысына қарағанда оңайырақ болуы тиіс.
ГОЛОГ
GOLOG — жағдайлық есептеуге негізделген логикалық бағдарламалау тілі.
Ситуациялық есептеудің бастапқы нұсқасы
Маккарти мен Хейздің бастапқы жағдайлық калькулы мен қазіргі кездегі арасындағы басты айырмашылық жағдайларды түсіндіруде. Қазіргі заманғы жағдайлық есептеуде жағдай – бұл іс-әрекеттер тізбегі. Бастапқыда жағдай «уақыттың бір мезетіндегі ғаламның толық жай-күйі» деп түсіндірілді. Бастапқыда мұндай жағдайларды толық сипаттау мүмкін емес екендігі анық болды; идея жай ғана жағдай туралы кейбір мәлімдемелерді беру және олардан салдарлар шығаруға арналған. Бұл сондай-ақ флуенттік калькулыда қолданылатын тәсілден өзгеше, онда жай-күй белгілі фактілердің жиынтығы болуы мүмкін, яғни ғаламның мүмкін толық емес сипаттамасы. Ситуациялық есептеудің бастапқы нұсқасында флуенттер реификацияланбайды. Басқаша айтқанда, өзгеруі мүмкін жағдайлар функциялар арқылы емес, предикаттар арқылы көрсетіледі. Шын мәнінде, Маккарти мен Хейс флуентті жағдайға байланысты функция ретінде анықтады, бірақ олар үнемі флуенттерді білдіру үшін предикаттарды қолданды. Мысалы, s жағдайында x жерде жаңбыр жауып тұрғаны предикаты арқылы көрсетіледі. Маккартидің 1986 жылғы жағдайлық есептеу нұсқасында функционалдық флуенттер қолданылады. Мысалы, x объектісінің s жағдайындағы орны функциясы арқылы көрсетіледі, мұнда орналасу – функция. Мұндай функциялар туралы мәлімдемелер теңдікті пайдалана отырып берілуі мүмкін: екі жағдайдағы s және объектісінің орналасуы бірдей екенін білдіреді. Іс-әрекеттерді орындау функция арқылы бейнеленеді: s жағдайындағы a әрекетін орындау нәтижесінде жағдайы пайда болады. Іс-әрекеттердің әсерлері s жағдайындағы флуенттер мен жағдайындағы флуенттер арасындағы қатынастарды көрсететін формулалармен білдіріледі. Мысалы, есікті ашу әрекеті есіктің құлыпталмаған болса, ашық болуына әкеледі: Ашық және құлыпталған предикаттары есіктің ашық және құлыпталған болу шарттарын білдіреді. Бұл шарттар өзгеруі мүмкін болғандықтан, олар жағдай аргументімен бірге предикаттармен бейнеленеді. Формула есік бір жағдайда құлыпталмаған болса, есікті ашу әрекетін орындағаннан кейін ашық болатынын көрсетеді, бұл әрекет тұрақты арқылы бейнеленеді. Бұл формулалар ықтимал деп саналатын барлық нәрсені алуға жеткіліксіз. Шын мәнінде, әр түрлі жағдайлардағы флуенттер тек іс-әрекеттердің алғышарттары мен әсерлері болған жағдайда ғана байланысты; егер флуентке іс-әрекет әсер етпесе, оның өзгермегенін анықтауға жол жоқ. Мысалы, жоғарыдағы формуладан екенін күтуге болады (есікті ашу оны құлыптамайды). Инерция сақталуы үшін кадр аксиомалары деп аталатын формулалар қажет. Бұл формулалар іс-әрекеттердің барлық әсерінсіздіктерін көрсетеді: Ситуациялық есептеудің бастапқы формулировкасында бастапқы жағдай, кейіннен S0 арқылы белгіленеді, нақты анықталмаған. Егер жағдайларды әлемнің сипаттамасы деп қарастырсақ, бастапқы жағдайдың қажеті жоқ. Мысалы, есіктің жабылып, бірақ құлыпталмаған сценарийді бейнелеу үшін оны ашу әрекеті бастапқы жағдайды білдіретін тұрақты s алып, ол туралы мәлімдемелер жасау арқылы формальдастырылады (мысалы, ). Өзгерістерден кейін есіктің ашық екендігі формуласымен көрініс табады. Алғашқы жағдай, егер қазіргі заманғы жағдайлық есептеудегідей, жағдай іс-әрекеттердің тарихы деп қарастырылатын болса, қажет, өйткені бастапқы жағдай іс-әрекеттердің бос тізбесін білдіреді. Маккарти 1986 жылы енгізген жағдайлық есептеу нұсқасы бастапқыдан функционалдық флуенттерді пайдаланумен (мысалы, s жағдайында x-тің орнын білдіретін термин) және кадр аксиомаларын ауыстыру үшін шектеуді пайдалану әрекетімен ерекшеленеді.
The execution of actions is represented by the function result: the execution of the action a in the situation s is the situation The effects of actions are expressed by formulae relating fluents in situation s and fluents in situations For example, that the action of opening the door results in the door being open if not locked is represented by:
The predicates locked and open represent the conditions of a door being locked and open, respectively. Since these conditions may vary, they are represented by predicates with a situation argument. The formula says that if the door is not locked in a situation, then the door is open after executing the action of opening, this action being represented by the constant opens. These formulae are not sufficient to derive everything that is considered plausible. Indeed, fluents at different situations are only related if they are preconditions and effects of actions; if a fluent is not affected by an action, there is no way to deduce it did not change. For example, the formula above does not imply that follows from , which is what one would expect (the door is not made locked by opening it). In order for inertia to hold, formulae called frame axioms are needed. These formulae specify all non effects of actions:
In the original formulation of the situation calculus, the initial situation, later denoted by S 0, is not explicitly identified. The initial situation is not needed if situations are taken to be descriptions of the world. For example, to represent the scenario in which the door was closed but not locked and the action of opening it is performed is formalized by taking a constant s to mean the initial situation and making statements about it (e. g., ). That the door is open after the change is reflected by formula being entailed. The initial situation is instead necessary if, like in the modern situation calculus, a situation is taken to be a history of actions, as the initial situation represents the empty sequence of actions. The version of the situation calculus introduced by McCarthy in 1986 differs to the original one by the use of functional fluents (e. g., is a term representing the position of x in the situation s) and for an attempt to use circumscription to replace the frame axioms.
Логикалық бағдарлама ретінде жағдайды есептеу
Сондай-ақ, жағдайды есептеуді логикалық бағдарлама ретінде жазу мүмкін (мысалы, Ковальски 1979, Апт және Безем 1990, Шанахан 1997). Мұнда Holds – метапредикат, ал f айнымалысы флуенттер жиымы бойынша өзгереді. Poss, Initiates және Terminates предикаттары сәйкесінше Poss, және предикаттарына сәйкес келеді. Сол жақтағы жебе ← – эквиваленттіктің ↔ жартысы. Екінші жартысы бағдарламаны толықтыру арқылы түсіндіріледі, онда жоққа шығару сәтсіздік ретінде қарастырылады. Индукциялық аксиомалар да жасырын, олар тек бағдарламаның қасиеттерін дәлелдеу үшін ғана қажет. Логикалық бағдарламаларды орындаудың әдеттегі механизмі – SLD шешімі сияқты кері қорыту, регрессияны автоматты түрде іске асырады.
Here Holds is a meta predicate and the variable f ranges over fluents. The predicates Poss, Initiates and Terminates correspond to the predicates Poss, , and respectively. The left arrow ← is half of the equivalence ↔. The other half is implicit in the completion of the program, in which negation is interpreted as negation as failure. Induction axioms are also implicit, and are needed only to prove program properties. Backward reasoning as in SLD resolution, which is the usual mechanism used to execute logic programs, implements regression implicitly.