7.4.3. Система МЕСНО и решение задач механики на языке Пролог

Система МЕСНО решает с помощью исчисления предикатов задачи механики, включающие материальные точки, наклонные плоскости, нити, блоки. Задачи формулируются на обычном языке. МЕСНО способна контролировать свои правила вывода и ведущийся ею поиск решения. Для этого она использует метаинформацию, содержащуюся также в форме правил. Система была разработана А. Банди и др. (A. Bundy et al., 1979) в Университете Эдинбурга.

Первая задача этой программы состоит в том, чтобы понимать высказывания, сделанные на естественном языке, в случае, когда из-за обширности области это невозможно сделать просто по ключевым словам (Bobrow, 1975; Charniak, 1978; Gelb, 1965). Здесь даже для простой постановки проблемы требуется глубокое погружение в мир физических явлений.

Вторая задача — обучение тому, чему, как правило, не обучают в курсах механики: как именно происходит решение уравнений, как конструируются модели, как организуется изучение задачи. Необходимо четко выяснить, в чем именно состоит отличие эксперта от новичка: оба знают примерно одни и те же основные факты и формулы, но первый Всегда способен найти им эффективное употребление. Их отличает также степень знания общей модели и структуры контроля. Коллектив ученых Эдинбургского университета имел для глубокого анализа этих отличий два важных отправных пункта. Первый — книга Марпля (D. Marple), в которой исследуются протоколы того, как инженеры из Кембриджа составляют уравнения. Это исследование проведено достаточно хорошо, чтобы можно было определять предложения, готовые к непосредственному кодированию в виде программы. Второй отправной пункт подготовил сам Банди. Анализируя методы решения человеком линейных и квадратных уравнений, он выявил совокупность стратегий, таких, как “перегруппировка”, “изолирование”, “привлечение”, которые могут быть выражены на языке Пролог. Оставалось изложить и привести в систему остальное, в частности найти хорошие правила вывода, способные строить длинные дедуктивные цепи, начиная от формулировки задачи на естественном языке до ее полного решения.

Пример

Две частицы с массами и с связаны тонкой нитью, перекинутой через блок. Найти ускорение частицы массой

Синтаксический и семантический анализ этого предложения (относительно простой) начинается с глаголов и опирается на

законы механики. В данном случае анализ приводит к появлению 22 единиц, необходимых для формулировки предложений:

(см. скан)

По методу Марпля отыскивается уравнение, которое выражает искомую величину в зависимости от данных и Гравитационную постоянную программа МЕСНО добавляет к условию cajvia. На первом этапе составляются уравнения для сил, действующих на частицы. Например, для частицы имеем

Введение новой неизвестной “натяжение-1” требуется используемыми правилами. Программа что эта величина имеет смысл натяжения и ей не хватает еще одного уравнения для решения задачи. Тогда она использует тот факт, что натяжение на другом конце нити должно быть тем же самым и составляет уравнение для сил, действующих на частицу Исключая переменную “натяжение-1”, программа получает результат. Испытания программы проводились и на других, более сложных примерах.

Описание системы

База физических знаний

Система имеет упрощенное представление о мире, подчиняющемся законам ньютоновской механики. Она может работать только с объектами 0, 1 или 2 измерений. Точка — нульмерный объект, и ее роль может играть частица с массой или простая отметка на плоскости. Линия представляет собой одномерный объект и имеет два не совмещенных друг с другом конца. Эти простые понятия используются при описании многих других объектов. Например, блок, человек, груз могут быть описаны как точки, а такие объекты, как шнур, нить, брус, планка, хотя и обладают различными физическими свойствами, могут быть представлены в виде линий.

Связь между объектами описывается с помощью предикатов. Имя предиката определяет вид связи, а аргументы служат для уточнения находящихся в связи объектов, их порядка, условий объединения, направлений и знаков. Конкретная ситуация определяется значениями аргументов при вызове. Пример связи приведен на рис. 7.96. “АС” определяет вызов процедуры типа “создать”, которая выполняется с помощью модуля поиска названных величин.

Рис. 7.96. Пример связи между объектами.

Очевидно, здесь могут потребоваться глубоко рекурсивные структуры базы знаний, поскольку, например, такое понятие, как “суммарные силы”, принадлежит области данных другой формулы.

Логика управления

Логика управления системы МЕСНО написана на языке Пролог, но запрещает нормальную для Пролога стратегию решения: все действия МЕСНО последовательно разлагаются в подцели с помощью одного из 150 правил вывода из базы знаний. Каждой выделившейся подцели присваивается обозначение D для “непосредственный”, АС для “с созданием” или SC для “без создания”. Эти обозначения используются на рис. 7.10 для пояснения стратегии решения.

Нормализация. Если возможно, каждая подцель сначала уточняется в соответствии с законами механики (если отыскивается ускорение, то обычно по отношению к земле) или выражается с помощью предикатов, более удобных для системы.

Вывод. МЕСНО ищет правило, правый член которого соответствует поставленной цели. Посылки этого правила определяют новые подцели. Поиск ведется в глубину сначала с неизменным порядком правил. Правила МЕСНО управляют созданием новых объектов, необходимых для решения задачи.

Рис. 7.10. (см. скан) Логика подцелей в системе МЕСНО.

Классы подобий. Работа системы МЕСНО основана на свойствах используемых в ней предикатов, которые могут быть транзитивными, симметричными или рефлексивными. Они сгруппированы в классы подобия, которые изоморфны деревьям, образованным множеством предложений Пролога.

Корень дерева является единственным представителем класса и может быть унифицирован, как и другие правила. Например, правилу равенства соответствует следующая аксиоматика:

(см. скан)

которая позволяет упорядочить в дереве все равные элементы. Кроме равенства в системе имеются еще три предиката: “та же позиция”, “единица.измерения” и “период времени”, которые

относятся к точечным объектам, занимающим в данный момент одинаковую позицию, величинам одинаковой природы, выраженным в различных единицах, отрезкам времени.

Выполнение

Первый шаг. Сначала система МЕСНО не рассматривает уравнения или соотношения, которые вводили бы новый объект (вызов подцелей только вида D или SC). Это ограничение впоследствии отбрасывается.

Прогнозирование. Система МЕСНО использует семантическую информацию о физическом мире для того, чтобы решить, является ли промежуточная цель приемлемой или для прогнозирования свойств решения: длина должна быть положительным числом, угол по отношению к плоскости меньше 180°. Даже такая форма знания влияет на выполнение правил равенства и принятие решения.

Метод Марпля. Для нахождения неизвестной величины х система МЕСНО последовательно выполняет следующие действия: а) описывает неизвестную, т. е. уточняет ее физическую природу (например, что это — масса), и определяет связанные с ней понятия (ускорение, направление движения, время); б) ищет соотношения, т. е. составляет список возможных формул; в) находит подходящее уравнение, т. е. отбирает из предыдущего списка наилучшую подходящую к данной ситуации формулу, ориентируясь на смысл известных параметров, г) проверяет, является ли найденная формула действительно независимой от уже известных уравнений, чтобы из нее можно было определить другие неизвестные.

Формальные алгебраические вычисления. Кроме классических методов, основанных на правилах переписи, применимость которых определяется самим Прологом, вычислительный модуль использует фактическую информацию в процессе решения для исключения физически невозможных ситуаций типа неустойчивого равновесия (в частности, в задачах движения по траекториям типа русских гор) (Borning, 1981).

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

Результаты

Система реализована на ЭВМ DEC-10 с памятью слов и с длиной слова 36 бит. Блок естественного языка содержит 900 предложений, модуль вычитания — 600 предложений,

алгебраические вычисления — 200. Интерпретатор Пролог занимает 20К памяти.

Испытания системы проводились главным образом по трем направлениям: механические блоки, движение частиц при постоянном ускорении, движение частиц по сложным траекториям. Только часть задач может быть сформулирована на естественном (английском) языке, остальные задачи необходимо формулировать в терминах предикатов. Разрабатываются также основы решения задач, включающие рычаги, сооружения, снаряды, моменты инерции, относительные скорости, гидростатику. Приведем пример формулировки задачи: Частица, находившаяся в состоянии покоя, начинает движение из точки Р. При заданном радиусе найти наименьшую величину при которой частица совершит полный оборот по окружности (Окружности являются касательными друг к другу в точке (рис. 7.11).)

Рис. 7.11. Задача на движение частицы.

Чтобы сформулировать эту задачу в логике первого порядка, окружности разрезают на три связанные друг с другом части с помощью позиционных отношений. Условия можно описать с помощью 20 единичных предложений, которые играют для системы ту же роль, что для нас рисунок.

В литературе описывается полное решение с помощью системы МЕСНО некоторых сложных задач, условия которых (записанные на обычном языке) занимают более одной страницы текста.