Методы и средства программирования в ограничениях для систем автоматизации проектирования

Метод удовлетворения (распространения) ограничений является одним из активно развивающихся подходов для решения нестандартных и сложных задач. Он относится к той области искусственного интеллекта, которая занимается решением комбинаторных задач, а также работой с неточными и неполными данными. Задача удовлетворения ограничений (constraint satisfaction problem, CSP) неформально описывается следующим образом:

— Решаемая задача состоит из набора переменных и набора ограничений.

— С каждой переменной связана собственная область определения (множество допустимых значений), которая может изменяться в процессе решения CSP.

— Ограничения связывают переменные и ограничивают множества их значений.

— Решением CSP является такой набор значений переменных, для которого удовлетворяются все ограничения.

— Целью решения CSP может быть как поиск одного решения (возможно, с заданными свойствами), так и поиск всех решений.

Впервые задача удовлетворения ограничений была сформулирована Хаффманом (Huffman) [20] и Маквортом (Mackworth) [28] в 70х годах.

Примерно до середины 90х годов задача удовлетворения ограничений рассматривалась только для дискретных данных (finite domain CSPCSP FD) [6, 14, 30, 43]. Классическим примером CSP FD является задача о расстановки ферзей: на шахматном поле размером NxN требуется расположить N ферзей так, чтобы они не били друг друга. Описание задачи состоит из N переменных, соответствующих ферзям и набора ограничений, реализующих условия «2 ферзя не могут стоять на одной вертикали», «2 ферзя не могут стоять на одной горизонтали», «2 ферзя не могут стоять на одной диагонали». Пример описания данной задачи в системе NemoNext приведён ниже в Главе 2.

Задачи удовлетворения ограничений для непрерывных областей данных обычно называются численными задачами удовлетворения ограничений {numerical CSPNCSP) [12, 18, 21, 25]. NCSP очень часто встречаются в реальных приложениях, например, при моделировании физических явлений, при описании химических процессов, в системах моделирования и проектирования. Как правило, эти задачи представляют собой совокупность уравнений и неравенств, связывающих переменные с непрерывной областью определения, хотя иногда ограничения могут задаваться в виде таблиц, а также включать целочисленные переменные. Очень часто реальные системы являются недоопределёнными или переопределёнными. Поэтому применение классических вычислительных методов или методов компьютерной алгебры для решения таких задач оказывается неудачным и приходится прибегать к упрощению исходной системы.

Примером NCSP может быть решение уравнения <

Таким образом, для решения CSP выделяют два класса методов — методы решения CSP FD и методы решения NCSP. Для каждого из этих классов разработан свой набор эффективных алгоритмов и построены соответствующие прикладные системы [4, 23, 43, 45]. Причём в настоящее время методы распространения ограничений все чаще объединяются с другими подходами. Например, методы распространения ограничений над конечными областями (CSP FD) используется в комбинации с методами исследования операций и методами линейного программирования, а методы распространения ограничений над непрерывными областями (NCSP) используют методы интервальной математики.

В начале 80х годов А. С. Нариньяни был предложен метод недоопределённых вычислений [57, 59]. Неформально, метод может быть описан следующим образом:

— Модель (описание задачи) состоит из конечного набора объектов и конечного набора ограничений.

— С каждым объектом модели связываются: недоопределённое значение (множество допустимых значений), функция присваивания и функция проверки корректности.

— Ограничения связывают объекты и вычисляют новые (недоопределённые) значения для своих аргументов.

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

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

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

— Семейство математических решателей 11шСа1с [2, 3, 24], ориентированных на решение численных задач.

— Мультиагентные системы ТАО [67, 68] позволяют использовать понятие «время» в постановке задачи и моделировать поведение динамических систем.

— Экспертные системы для работы с неточными данными [51, 52].

— Семейство систем НеМо (Немо-Тек — [63]- НеМо+ [37, 46, 49]), характерной чертой которых является расширяемость (возможность настроить систему на конкретную предметную область путём создания новых типов данных и ограничений).

В конце 90х годов фирма Dassault Systemes, ведущий производитель инженерных САПР верхнего уровня1, в рамках развития своего флагманского продукта CATIA V5 [10], столкнулась с потребностью в универсальном решателе задач удовлетворения ограничений. В этот момент основным перспективным направлением развития системы являлось повышение интеллектуальности системы. Под понятием «интеллектуальность» подразумевался набор инструментов, повышающих уровень автоматизации процесса проектирования, в частности: контроль корректности модели изделия при её модификации, автоматическое построение различных конфигураций изделия по внешним параметрам, автоматическая корректировка модели при изменении пользователем её параметров, нахождение оптимальных конфигураций и т. д. Основными требованиями, предъявляемыми к такому универсальному вычислителю, были:

— Способность решать произвольные системы уравнений и неравенств.

— Лёгкая интеграция в систему С ATI A V5.

— Возможность настраивать вычислитель для решения специализированных задач CATIAV5.

Фирма Dassault Systemes выбрала в качестве базового вычислителя для решения CSP систему НеМо+. На основе НеМо+ была разработана и реализована система NemoNext, которая в отличие от НеМо+ удовлетворяла всем требованиям Dassault Systemes по технологичности, настраиваемости, расширяемости и другим требованиям, предъявляемым к промышленным.

1 Системы автоматизации проектирования (САПР) разделяются на три класса систем, в зависимости от набора предоставляемых возможностей, цены одного рабочего места и рыночного позиционирования: системы нижнего уровня, системы среднего уровня, системы верхнего уровня. программным продуктам. Тем не менее, в процессе интеграции системы №то№х1 в САПА У5 возник целый ряд задач, потребовавших разработки специализированных методов и алгоритмов.

Автор принимал непосредственное участие в проектировании и реализации системы №тоКех1 с самого первого дня разработки. Ему принадлежит авторство разработки алгоритмов подключения внешних модулей к №то№х1, разработка алгоритмов нахождения точных решений с заданной точностью, алгоритмов поиска решения, ближайшего к заданному, алгоритма поиска всех решений и ряд других методов.

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

Цель работы — разработка методов и алгоритмов для решения задач, возникающих при взаимодействии системы программирования в ограничениях с промышленной САПР. Можно выделить два основных класса таких задач: нахождение точного решения СБР с указанными свойствами (в частности, поиск решения с заданной точностью, поиск решения, ближайшего к заданному, поиск нескольких или всех различающихся решений) и интеграция специфических понятий САПР (объектов и отношений) в задачи, решаемые системой программирования в ограничениях.

Для достижения поставленной цели в диссертации последовательно решены следующие задачи исследования:

1. Формально описана семантика типов данных и основных видов ограничений, используемых в задаче удовлетворения ограничений.

2. Разработан декларативный объектно-ориентированный язык описания задачи удовлетворения ограничений.

3. Разработаны методы поиска решений, расширяющих класс задач, решаемых системой удовлетворения ограничений.

4. Создана концепция использования внешних вычислительных модулей, реализующих различные специализированные функции и отношения (В1аскВох), в процессе решения задачи удовлетворения ограничений.

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

6. Разработана архитектура системы программирования в ограничениях №то№х!-.

7. Осуществлена интеграция системы №то№х1 в САПР САТ1АУ5.

Методы исследования. В диссертационной работе были использованы модели и методы искусственного интеллекта, теории множеств, методы функционального анализа, методы объектно-ориентированного проектирования и программирования.

Основными теоретическими результатами работы, выносимыми на защиту и определяющими научную новизну работы, являются:

— Декларативный объектно-ориентированный язык описания модели для задачи удовлетворения ограничений.

— Концепция использования внешних вычислительных модулей, реализующих различные специализированные функции или отношения (В1аскВох), в процессе решения задачи удовлетворения ограничений.

— Метод поиска решений задачи удовлетворения ограничений с указанной точностью и отбрасыванием близких решений.

— Формальное описание различных видов недоопределённости и семантики типов данных и ограничений задачи удовлетворения ограничений. Содержание работы.

Для решения задачи удовлетворения ограничений, системой №то№х1 используется метод недоопределёниых вычислений, описанный в работах [39, 44, 59, 62]. Формальное доказательство сходимости метода было представлено в работе [44], но скорость сходимости метода, в силу его универсальности, сильно зависит от способа реализации конкретных ограничений и выбранного представления данных: различные (но при этом корректные с точки зрения метода недоопределёниых вычислений) реализации могут приводить к различным результатам и могут иметь принципиально разную скорость сходимости. В первой главе работы приведено краткое формальное описание метода недоопределёниых вычислений. На основе введённых понятий выполняется уточнение и конкретизация способов представления множества значений (видов недоопределённости) переменных, и дано краткое описание их основных свойств. Далее приводится формальное описание основных типов данных и семантики некоторых видов ограничений.

Вторая глава посвящена описанию архитектуры системы программирования в ограничениях №то№х<:. При её разработке учитывались следующие базовые принципы:

Универсальность системы означает способность формулировать и решать с её помощью максимально широкий диапазон задач. Сюда можно отнести следующие свойства:

— Расширяемость системы дополнительными типами данных и ограничений.

— Единый универсальный алгоритм решения задачи.

— Использование концепции «недоопределённость» для работы с неточными и не полностью определёнными данными. Тем самым существенно расширяется диапазон решаемых задач и они точнее соответствуют реальным задачам пользователя.

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

Технологичность и простота интеграции в сторонние системы определяется модульным строением системы и наличием развитого API (внешнего программного интерфейса). Модульность системы поддерживается объектно-ориентированным подходом, что повышает уровень описания задачи и упрощает их формулировку. Другим важным свойством, упрощающим процесс формулировки задачи является декларативность языка представления модели. Декларативность позволяет пользователю сконцентрироваться не на том, каким образом решать задачу, а на том, какую именно задачу решать и каким образом её лучше сформулировать.

Описание реализации вышеуказанных принципов системы программирования в ограничениях приводится с двух точек зрения:

— С точки зрения архитектуры и внутреннего строения системы.

— С точки зрения пользователя и языка описания модели.

В третьей главе описываются проблемы интеграции системы NemoNext в промышленные программные продукты. Так как основным заказчиком работ по системе NemoNext выступает фирма Dassault Systemes, то система с самого начала проектировалась для использования в качестве универсального решателя в системах автоматизации проектирования (САПР). Соответственно, одной из важнейших задач, которую необходимо было решить, была проблема интеграции системы в состав САПР С ATI A V5. В третьей главе описываются модули САПР CATIA V5, которые взаимодействуют с системой NemoNext. Показывается роль, которую выполняет система программирования в ограничениях в составе CATIA V5 и описываются задачи, которые NemoNext решает по запросу внешней системы. Эти задачи заметно отличаются от задач, обычно решаемых системой программирования в ограничениях. В частности, САПР может потребоваться найти:

— Решение с заданной точностью.

— Решение, ближайшее к текущему значению аргументов.

— Несколько или все различные решения.

— Частичное решение.

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

В четвёртой главе описывается концепция использования внешних вычислительных модулей в задаче удовлетворения ограничений. Такой вычислительный модуль мы будем далее называть ШаскВох-процедурой, а отношение, которое данный модуль реализует — чёрным ящиком или ВШскВох. Соответствующее ограничение системы программирования в ограничениях будем называть В1аскВох-ограничением.

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

— Нахождение минимума и максимума В1аскВох (чтобы построить интервальное значение аргумента В1аскВох-ограничения, соответствующего результату В1аскВох).

— Нахождение минимума и максимума всех обратных функций к В1аскВох (чтобы построить интервальные значения аргументов В1аскВох-ограничения, соответствующих входным аргументам В1аскВох).

Также можно выделить ряд дополнительных факторов, серьёзно влияющих на решение указанной задачи:

— Большое время вычисления одного вызова В1аскВох-процедуры.

— Неизвестная природа В1аскВох отношения.

— Неизвестная область определения В1аскВох.

— Требование решать задачи, указанные в Главе 3 (поиск решения с заданной точностьюпоиск решения, ближайшего к текущему значению аргументовпоиск нескольких решений).

В результате, были разработаны несколько специализированных методов и алгоритмов, которые позволили решить все указанные выше задачи [35].

Предложенные алгоритмы и методы реализованы в системе NemoNext, входят в состав нескольких продуктов (компонентов) САПР CATIA V5 и поставляются клиентам Dassault Systemes, что характеризует практическую значимость данной работы.

Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и четырёх приложений. Объем диссертации: полный — 152 страницбез приложений — 128 страниц.

Список литературы

содержит 72 наименований. Работа включает 16 рисунка и 12 таблиц.

Результаты работы докладывались на международных конференциях.

Личный вклад автора.

В рамках разработки системы автор диссертации выполнил следующие работы:

— Исследование видов недоопределённости MultiintervalN и MixedN, структурных недоопределённых типов данных.

— Формализация числовых типов данных и ограничений. Реализация соответствующих библиотек системы NemoNext.

— Разработка объектно-ориентированного декларативного языка описания модели и реализация его транслятора.

— Разработка и реализация метода поиска точных решений с указанной точностью и отбрасыванием близких решений.

— Разработка концепции использования внешних вычислительных модулей (BlackBox) в задаче удовлетворения ограничений. Рзаработка специализированных алгоритмов и методов для работы с BlackBox. Реализация библиотеки BlackBox системы NemoNext.

Кроме того автор внёс большой вклад в разработку ядра системы, модуля поиска точных решений, модуля интеграции с системой С ATI A V5, модуля абстрактных типов данных, модуля строковых типов данных.

Дальнейшие работы по развитию системы NemoNext можно разбить на несколько групп:

— Создание дополнительных продуктов в рамках САПР С ATI A V5, таких как: система контроля максимальных допусков изделия (Tolerancing), интервальный вычислитель (Interval Solver), система совместной разработки изделия (Collaborative Design). Возможно, данные продукты потребуют от системы NemoNext решения новых задач.

— Создание и реализация дополнительных алгоритмов решения задач, таких как: нахождение ЗВ-совместности, быстрое решение подсистем линейных уравнений, использование производных при поиске точного решения, более эффективные эвристики работы с BlackBox.

— Разработка следующей версии решателя, с упором на скорость работы и компактность вместо универсальности.

Заключение

.

Одним из способов повышения функциональности систем автоматизации проектирования является использование в их составе систем программирования в ограничениях для решения различных задач. При такой интеграции, зачастую, возникает ряд научных проблем, требующих специальных исследований. В данной работе рассматривается полный спектр задач, возникающих при организации взаимодействия между системой программирования в ограничениях NemoNext и машиностроительной САПР CATIA V5 фирмы Dassault Systemes, начиная с проектирования системы программирования в ограничениях и заканчивая созданием специальной техники для работы со специфическими сущностями САПР.

Основными результатами работы являются следующие:

1. Разработан объектно-ориентированный язык, декларативно описывающий задачу удовлетворения ограничений, и реализован транслятор языка.

2. Разработана концепция использования внешних вычислительных модулей (механизм В1аскВох-ограничений) в задаче удовлетворения ограничений.

3. Разработаны методы поиска решений для задачи удовлетворения ограничений. В том числе, поиск решений с заданной точностью, поиск решения, ближайшего к заданному, поиск нескольких или всех различных решений, поиск частичного решения.

4. Разработана архитектура и выполнена реализация системы программирования в ограничениях NemoNext.

5. Выполнена интеграция системы NemoNext в САПР CATIA V5.

Кроме того получены менее значимые результаты:

Выполнено формальное описание различных способов представления множества допустимых значений (виды недоопределённости) и семантики типов данных и ограничений.

Разработаны оригинальные виды недоопределённости, типы данных и ограничения.

Сформулированы проблемы, возникающие при интеграции системы программирования в ограничениях в САПР.