Реализация обратного прослеживания в системе VT
Программа VT (название программы — аббревиатура от Vertical Transportation, транспортировка по вертикали) была использована фирмой Westinghouse Elevator для разработки лифтовых систем индивидуального исполнения. Исходные данные для программы VT представляют собой набор основных параметров проектируемой системы — скорость, грузоподъемность, размеры лифтовых шахт. На основе этих данных программа формирует список подходящего оборудования и компоновку всех шахт с учетом требований безопасности и производительности системы.
В процессе проектирования программа сначала формирует примерную компоновку, а затем уточняет ее на основе анализа оговоренных ограничений. На первом этапе используется прямая цепочка правил логического вывода. Программа выбирает в качестве исходных данных либо введенные параметры, либо значения, вычисленные другими процедурами. Типичное правило (в системе VT они почему-то названы PROCEDURE — процедура) представлено ниже.
ЕСЛИ: доступны значения параметров
DOOR-OPENING, PLATFORM-WIDTH и OPENING-WIDTH
и DOOR-OPENING=CENTER,
ТО: CAR-JAMBETURN=(PLATFORM-WIDTH - OPENING-WIDTH)/2.
На этом этапе весь процесс направляется данными. Допустима любая операция проектирования, если только для этого имеется достаточно исходной информации. Но поскольку на этом этапе некоторые из задач оказываются недоопределенными, то вполне возможна и такая ситуация, когда при отсутствии полностью определенных задач в списке актуальных очередное предложение будет сформировано такой недоопределенной задачей. В результате в дальнейшем будет развиваться частичная конфигурация проекта, созданная на базе неполной информации. Иными словами, в системе VT не всегда соблюдаются условия соответствия, сформулированные в предыдущей главе, но, тем не менее, процесс проектирования продолжается, поскольку предполагается, что в дальнейшем удастся скорректировать возможное нарушение ограничений.
По мере развития проекта система VT отслеживает на каждом шаге, от каких исходных или промежуточных данных зависят сформированные на этом шаге данные.
В процессе отслеживания формируется сеть зависимостей (dependency network). Структура сети зависимостей будет детально рассмотрена в главе 19, а пока считайте, что такая сеть представляет собой один из видов ориентированного графа без петель. Узлы графа представляют вычисленные значения важных параметров проектируемой системы, например CAR_JUMB_RETURN (пространство для маневрирования автомобилей при загрузке в лифт), а ребра — применяемые для их определения правила. Узлы и ребра графа формируются по мере активизации тех или иных правил в процессе развития проекта. В результате программа после завершения проектирования получит возможность выяснить, каким образом в процессе рассуждений было определено значение того или иного параметра, и найти, какое из принятых в процессе проектирования решений привело к нарушению ограничений. Найденное решение и послужит отправной точкой для пересмотра проекта.
Нарушение ограничений выявляется с помощью демонов (см. главу 6). Если имеется достаточно информации для того, чтобы определить, как связано значение некоторой величины со значениями ограничений, выполняется сравнение. Возможные способы устранения несоответствия ранжированы и активизируются в заданном порядке. Пример правила устранения несоответствия приведен ниже.
ЕСЛИ: нарушено ограничение MAXIMUM-MACHINE-GROOVE-PRESSURE,
ТО: попробовать понизить значение MACHINE-GROOVE-MODEL (1),
увеличить значение HOST-CABLE_QUANTITY (4).
После применения правила устранения несоответствия программа, пользуясь сформированной ранее сетью зависимостей, корректирует и остальные параметры проекта, зависящие от тех, которые были изменены в результате применения правила.
Приведенное выше правило устранения предлагает два варианта, причем указанный в скобках уровень приоритета означает, что предпочтение следует отдать первому варианту. Если же его реализовать по каким-либо причинам не удастся, следует попробовать второй вариант.
Говорят, что два ограничения являются антагонистическими, если удовлетворение одного из них приводит к нарушению другого.
Если вернуться к рассмотренному выше примеру с посещением кинотеатра, то можно интерпретировать антагонистические ограничения следующим образом. Два человека хотят вместе пойти в кино, но один не желает видеть ничего, кроме фильмов ужасов, а другой не выносит вида крови. Если удовлетворить вкусы одного, то желание другого будет проигнорировано.
Проблема пересмотра ранее принятых решений усложняется тем фактом, что коррекция параметров, необходимая для устранения одних ограничений, влияет на другие параметры, которые, в свою очередь, связаны с другими ограничениями. В правиле, приведенном выше, одна из рекомендаций предполагает изменение количества тросов подъемника, что приведет к изменению множества других параметров всей конструкции. Вполне возможно, что после этого придется заменить и модель лифта. База знаний программы VT включает 37 цепочек устранения несоответствия ограничениям, причем три из них имеют дело с антагонистическими ограничениями. Антагонистическими, например, являются ограничения MAXIMUM-MACHINE-GROOVE-PRESSURE (максимальная нагрузка на трос подъемника) и MAXIMUM-TRACTION_RATIO (максимальное отношение сцепления). Понижение нагрузки приведет к увеличению отношения сцепления и наоборот.
Если одновременно нарушаются оба антагонистических ограничения, то складывается ситуация, когда, скорректировав параметры, необходимые для устранения одного несоответствия, мы еще более усугубим другое. В системе VT проблема устранения антагонистических ограничений выделена в отдельный случай и решается следующим образом. Когда демон фрейма обнаруживает такую ситуацию, каждому параметру, имеющему отношение к выявленному нарушению ограничений, присваивается то значение, которое он имел до нарушения любого ограничения. Таким образом отменяются все предпринятые ранее меры по ликвидации нарушения всех ограничений. После этого программа предпринимает попытку выполнить какую-либо из корректирующих операций, весь набор которых разделен на три группы очередности:
(1) операции, которые помогают устранить нарушение обоих антагонистических ограничений;
(2) операции, которые помогают устранить нарушение одного из антагонистических ограничений и не усугубляют нарушение другого;
(3) операции, которые помогают устранить нарушение одного из антагонистических ограничений, но усугубляют нарушение другого.
Если дело доходит до выполнения операций третьей группы, то сначала программа пытается устранить нарушение наиболее существенного ограничения. Таким образом, одно из важнейших отличий программы VT от MOLGEN состоит в том, что хотя в обеих системах используется стратегия предложение и пересмотр, в программе VT гораздо большее внимание уделено фазе пересмотра ранее принятых решений, а программа MOLGEN концентрируется на реализации принципа наименьшего принуждения.
Программа VT реализована с помощью языка OPS5. База знаний этой программы насчитывает около 3000 правил. В литературе приводятся сведения о производительности системы. Для выполнения задания средней сложности программа активизирует от 2 500 до 11 500 правил, на что затрачивается от 7 до 20 минут машинного времени компьютера VAX 11/780, оснащенного оперативной памятью объемом 20 Мбайт. Интересно отметить, что около 2000 правил системы VT сформировано с помощью системы автоматизированного приобретения знаний SALT, а другие (их около 1000) отвечают за организацию ввода/вывода, управление порядком применения правил и формирование объяснений, помогающих пользователю уяснить, почему программа в процессе проектирования приняла определенные решения.
