1. Определение проблемы фреймов 9
1.1. История вопроса 9
1.2. Постановка проблемы 14
2. Проблема ветвления 24
2.1. Минимизация изменений 24
2.2. Причинные связи 31
3. Проблема квалификации 38
3.1. Семантика возможных миров 38
3.2. Состояния по умолчанию: нормы предположений 61
ЗАКЛЮЧЕНИЕ 67
Список литературы 69
Актуальность темы исследования.
Тема данной работы находится в области одной из самых молодых и динамично развивающихся наук — Искусственного Интеллекта (ИИ). И хотя еще в 70-е гг., после знаменитого отчета Джеймса Лайтхилла, появились пессимистические настроения относительно будущего этой молодой и еще не окрепшей науки, она продолжает развиваться. Можно даже сказать, что только в последнее время она вышла на траекторию размеренного поступательного движения. До начала 90-х годов история этой науки представляла череду взлетов и падений, окрыляющих побед, и унизительных поражений. И только после этого началась настоящая работа, без сверх ожиданий, но и без сверх разочарований.
Однако, даже без сильных потрясений, динамичность развития ИИ, как и в целом Computer Science, никогда не вызывала сомнения. Постоянно ставятся все новые проблемы, находятся новые решения и подходы. Однако некоторые проблемы прочно заняли пьедестал классических, и остаются там по сей день. Одна из таких проблем — так называемая «проблема фреймов». Эта проблема была поставлена еще в 1969 г ., на заре развития компьютерных технологий и непосредственно связанного с ними ИИ, однако удовлетворительного решения не нашла до сих пор. И тому видят несколько причин . Это и особенности публикаций по данной тематике — они направлены на решение «игрушечных проблем» (обвинение в стиле сэра Д. Лайтхилла); и в целом особенность исследований в компьютерных науках — оно направлено не на решение общей проблемы, а на то, чтобы программа заработала, поэтому часто страдает излишней конкретикой и решениями ad hoc. Но главной причиной (приобретающей особую значимость на фоне ранее приведенных) является то, что это одна из ключевых проблем темпорального размышления. Она шире, чем кажется, и поиски её решения становятся вынужденным шагом при любой попытке размышлять о времени, изменениях и действиях. По крайней мере в рамках логицистского подхода к ИИ .
Это действительно философская проблема (поставленная с точки зрения искусственного интеллекта). В явной форме здесь выражаются древние философские проблемы, связанные с понятием причинности и познания. Проблема фреймов ставит вопрос о том, как описать изменяющийся под влиянием действий мир так, чтобы не упустить никаких причинных связей, но и не считать все в мире ежесекундно меняющимся (старый спор Парменида с Гераклитом). В связи с попытками объяснить наш мир непонятливому компьютеру, эти философские проблемы выступают в четкой и ясной форме, и во многом становятся яснее нам самим.
Поэтому решение данной проблемы является весьма актуальной задачей, которую ставят перед собой многие исследователи, но зачастую не достигают желаемого результата. Хотя справедливости ради стоит отметить, что «неудачные попытки» решения проблемы фреймов — это не безнадежные провалы. Это по-своему удачные подходы, в которых, однако находят изъяны, зачастую — за счет переформулировки самой проблемы (подробнее о толкованиях проблемы фреймов в гл. 1). Так, например, Джон МакКарти (сформулировавший проблему) дал одно из решений проблемы, которое не удовлетворило научное сообщество, казалось несостоятельным и неосуществимым. Однако ряд специалистов, сотрудничавших с ним в этом проекте, затем использовали идеи МакКарти в создании программы RCS Advisor — программы, проверяющей способность шаттла к маневрированию в случае неполадок . Поэтому вполне логично ожидать и возможность практического применения от решения проблемы фреймов, даже неудачного.
Тот нормативный подход, который предлагается в данной работе, кажется актуальным данной проблеме, в первых, по причине того, что основывается на семантике возможных миров, которая очень хорошо подходит для рассуждений в условиях неполной информации, а также потому, что соответствует интуициям относительно того, как с подобными проблемами справляются люди.
Степень разработанности проблемы.
Литературы, посвященной проблеме фреймов в том или ином аспекте настолько много, что упомянуть в этой работе все представляется невозможным. Поэтому мы обратим внимание только на ключевые работы, представляющие глубоко проработанные и зарекомендовавшие себя подходы. Однако стоит отметить, что упомянутая литература в основном существует в виде статей в периодических изданиях и материалах конференций, в больших монографических исследованиях на эту тему наблюдается определенный недостаток.
Начинается история проблемы фреймов с уже упомянутой работы МакКарти [35]. Им же были предложены варианты решения проблемы на основе немонотонной логики, например в [33] и [32] Суть данного подхода заключается в возможности признания исключений и возможности последующего пересмотра выводов при признании чего-то «аномалией». Критика предложенного автором решения была представлена в знаменитой работе [21], где предлагается сценарий «Йельской стрельбы». Этот сценарий не поддается немонотонной логике, как и конкурентные действия.
Для преодоления этого затруднения были предложены так называемые хронологические подходы, которые вводят строгий временной порядок, и тем самым избегают затруднений, возникающих в Йельском сценарии. Это, например, [25], [28], [48].
Другим решением стали подходы, основанные на понятии причинности: [26], [23],[13]. Но такие подходы, опять же, не позволяют конкурентных и неизвестных действий
Не использующий немонотонные рассуждения, но остающийся в рамках близкого к ситуационному исчислению формализма подход представлен в [16], где проводится категоризация функций на устойчивые и текучие, действия рассматриваются как элементарные, но порождающие цепи непрямых эффектов при определенных обстоятельствах. Похожий подход был независимо предложен в [47].
Однако объясняющих аксиом осталось все равно довольно много, около 2F (где F - количество функций). Модификация данного подхода в [43] привела к снижению количества аксиом до F+A, где A - это количество действий. В этой системе также возможно рассмотрение конкурентных действий, однако с весьма ограниченными характеристиками.
Процедурный подход, предложенный в [19], широко известный STRIPS, является по своей сути в первую очередь системой для планирования (поиска решения в графе состояний). В отношении проблемы фреймов там принимается посылка, что если действие не известно явным образом как меняющее значение какой-либо функции, то оно этого и не делает. Этот подход очень имеет очевидные преимущества: он интуитивно понятен и эффективен с вычислительной стороны, однако он не может моделировать условные действия, что отмечено в [39], [40]. Также он с трудом воспринимает конкурентные действия и в целом все, что не отражено явным образом — в соответствии со своим базовым принципом.
Если говорить о более общем взгляде на проблему фреймов как проблему темпорального рассуждения, то можно упомянуть здесь работы логиков, направленные на выявление адекватного описания временной структуры: [31], [41], [42], [44], [45]. Данные подходы относятся к тематике модальных логик, и потому в особенности стоят упоминания в данной работе, где подход также по своей сути является модальным. Однако здесь разговор идет только о времени.
Есть ряд работ, посвященных построению модальных логик действия: [1], [14], [22]. Однако здесь сосредоточенность на действии делает его главным объектом исследования, и потому главный вопрос проблемы фреймов — описание среды, которое мы должны вывести из описания состояния её в другое время и описания действия — не поднимается.
Модальных подходов к самой проблеме фреймов нами не было обнаружено, поэтому та узкая область, в которой развивается наша работа, остается не разработанной в литературе.
Объект исследования:
формальные системы, моделирующие изменяющуюся среду и действия в ней.
Предмет исследования:
Способы преодоления некоторых затруднений, встречающихся в такого рода системах, общее название которых — проблема фреймов.
Цель и задачи исследования.
Конечной целью данного исследования является демонстрация возможностей модально-логического подхода к решению проблемы фреймов, конкретно с точки зрения логики деонтических (нормативных) модальностей. Достижение поставленной цели осуществляется решением следующих задач:
1. Дать четкое рабочее определение проблемы фреймов для базового формализма, описывающего действие;
2. Рассмотреть способы решения в нем проблемы ветвления, как под-проблемы проблемы фреймов;
3. Рассмотреть применение семантики возможных миров как удобной модели для рассмотрения действий в условиях неполной информации;
4. Наметить способ построения на базе такой семантики нормативно-модальных правил вывода.
Теоретико-методологическая основа исследования.
Основная методология данного исследования — это логический анализ темпоральных рассуждений.
Структура и объем работы.
Магистерская диссертация состоит из введения, трех глав, содержащих 6 подразделов, и заключения. В первой главе проводится историческое рассмотрение проблемы фреймов, дается строгое её определение для введенного базового формализма (как двух взаимосвязанных проблем — проблемы ветвлений и проблемы квалификации). Во второй главе рассматривается проблема ветвлений, дается вариант её решения за чет расширения базового формализма (добавляются понятия ограничений состояний, информации о влияниях, и, самое главное, законов причинных связей). В третьей главе рассматривается проблема квалификации, базовый формализм расширяется посредством введения для него семантики возможных миров, рассматриваются свойства этой модели и предлагается вариант решения проблемы квалификации за счет оценки литералов по степени ожидаемости, и вводящихся на этой основе модальных нормативных операторов. Список литературы включает 51 наименование. Общий объем работы - 72 страницы.
Проблема фреймов, центральная тема данной работы, вынужденно была объяснена только в рамках самой работы. Это связано с тем широким толкованием, которое она приобрела в научных кругах. Нам необходимо выделить тот фрагмент, который мы сделаем предметом своего исследования. Для наших целей мы ввели формализм, отдаленно напоминающий ситуационное исчисление, и выразили проблему в нем. Проблема в таком виде заключалась в следующем: для спецификации того, что в мире меняется, а что остается неизменным после того, как было произведено какое-либо действие, требуется очень большое количество аксиом. Это мы назвали проблемой ветвлений — проблемой устранения ветвления ситуаций, если быть более точными. То есть нас занимал вопрос о том, как определить однозначно и в соответствии с интуицией результат действия в сложном домене, где имеют место различного рода причинные связи между элементами. И при этом сохранить разумным количество требуемых аксиом. Решение мы нашли во введении причинных связей. Мы описали действия как влияющие на очень маленький фрагмент реальности, но могущие вызвать тем самым цепь причинных связей как своих непрямых действий. Это позволило нам получить формализм, хорошо справляющийся с ветвящимися доменами.
Следующим шагом стало включение в рассмотрение таких ситуаций, где нам не доступна полная информация о состоянии среды. Поэтому наши выводы стали лишь гипотетическими (не из-за неудачности формализма, а из-за отсутствия фактических данных). Научиться работать с такой неопределенностью — это и было нашей задачей в случае проблемы квалификации, второй проблемы, которую мы для себя определили.
Эта проблема была основной для нас. Именно в ней мы предложили свой подход, основывающийся на семантике возможных миров. Мы подробно рассмотрели следствия принятия этой семантики, и в конце обозначили общую идею рассмотрения предположений как принимаемых в согласии с некоторой нормой. Эта идея основана на том, что человек, его обыденный разум, по нашему мнению, ожидает от мира некоторого «нормального поведения». Полная информация о мире нам не доступна, но постепенно мы начинаем привыкать к этому. И в этом заключается «рациональность» - мы вырабатываем себе некоторые нормы взаимодействия с миром, и перестаем тяготиться отсутствием полной информации о нем.
В данной работе рассмотрен только простейший вариант ситуаций с неполной информацией: когда нам доступна вся общая информация о мире (законы причинных связей, законы действий), не доступны только какие-то фактические данные, значения конкретных литералов. Также в данной работе мы не рассматривали вопросов, возникающих с разрешением конкурентных действий и случайных изменений в среде. Мы обозначили общий путь их описания, но не углублялись в проблему.
Рассмотрение этих вопросов может стать продолжением данного исследования, вместе с попытками применения логики предпочтения к выведению норм предположения, и попытками расширения данного подхода до ситуаций, где нам не известны общие данные о мире, его законы.
Научная новизна исследования заключается в попытке применить сначала семантику возможных миров, а затем построенных на этой основе модальных операторов, нормативных по своей природе, определяющих то, как мы должны рассуждать о действиях и их результатах в мире с неполной информацией.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
