автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и средства программирования в ограничениях для систем автоматизации проектирования

На правах рукописи

УДК 519 688, 519 682 3

СИДОРОВ Владимир Анатольевич

МЕТОДЫ И СРЕДСТВА ПРОГРАММИРОВАНИЯ В ОГРАНИЧЕНИЯХ ДЛЯ СИСТЕМ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ

05 13 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискании ученой степени кандидата физико-математических наук

ООЗ1БОВ4Э

Новосибирск 2007

003160649

Работа выполнена в Институте систем информатики имени А П Ершова СО РАН

Научный руководитель:

Телерман Виталий Васильевич, кандидат технических наук

Официальные оппоненты: Лаврентьев Михаил Михайлович,

доктор физико-математических наук

Семенов Александр Леонидович, кандидат физико-математических наук

Ведущая организация

Институт вычислительной математики и математической геофизики СО РАН

Защита состоится 8 ноября 2007 г в 15 ч 30 мин на заседай диссертационного совета К003 032 01 в Институте систем информатики имени А П Ершова Сибирского отделения РАН по адресу 630090, г Новосибирск, пр Академика Лаврентьева, 6

С диссертацией можно ознакомиться в читальном зале ИСИ СО РАН (г Новосибирск, пр Академика Лаврентьева, 6)

Автореферат разослан «28» сентября 2007 г

Ученый секретарь

диссертационного совета КООЗ 032 01,

к ф -м н

Мурзин Ф А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

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

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

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

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

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

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

Задача удовлетворения ограничений была сформулирована в 1970-ых годах Хаффманом (Huffman) и Маквортом (Mackworth)

В начале 1980-ых годов АС Нариньяни был предложен метод недоопределенных вычислений Данный метод может быть описан следующим образом

- Модель (задача удовлетворения ограничений) состоит из конечного набора объектов и конечного набора ограничений

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

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

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

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

Развитие метода недоопределенных вычислений в 1990-ых годах привело к созданию целого ряда разнообразных систем, таких как

- семейство математических решателей UniCalc, ориентированных на решение численных задач,

- мультиагентные системы ТАО, позволяющих использовать понятие «время» в постановке задачи и моделировать поведение динамических систем,

- экспертные системы для работы с неточными данными,

- семейство систем НеМо (Немо-Тек, НеМо+), характерной чертой которых является расширяемость (возможность настроить систему на конкретную предметную область путем создания новых типов данных и ограничений)

В конце 1990-ых годов фирма Dassault Systèmes - ведущий производитель инженерных систем автоматизации проектирования (САПР) верхнего уровня, в рамках развития своего флагманского продукта CATIA V5, столкнулась с потребностью в универсальном решателе задач удовлетворения ограничений В этот момент основным направлением развития системы являлось повышение ее интеллектуальности Под понятием «интеллектуальность» подразумевался набор инструментов, повышающих уровень автоматизации процесса проектирования, в частности контроль корректности модели изделия при ее модификации, автоматическое построение различных конфигураций изделия по

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

- способность решать произвольные системы уравнений и неравенств,

- легкая интеграция в систему CATIA V5,

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

Фирма Dassault Systèmes выбрала в качестве базового вычислителя для решения CSP систему НеМо+ На основе НеМо+ была разработана и реализована система NemoNext, которая в отличие от НеМо+ удовлетворяла всем требованиям Dassault Systèmes по технологичности, настраиваемости, расширяемости и другим требованиям, предъявляемым к промышленным программным продуктам В процессе интеграции системы NemoNext в CATIA V5 возник целый ряд задач, потребовавших разработки специализированных методов и алгоритмов

Цель работы

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

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

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

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

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

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

процессе решения задачи удовлетворения ограничений

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

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

7 Осуществлена интеграция системы NemoNext в САПР CATIA V5

Методы исследованиях

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

Научная новизна

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

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

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

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

Практическая ценность

Предложенные алгоритмы и методы реализованы в системе программирования в ограничениях NemoNext Система NemoNext используется в составе нескольких коммерческих компонентов системы автоматизации проектирования CATIA V5, которые поставляются клиентам Dassault Systèmes

Апробация работы

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

АП Ершова «Перспективы систем информатики» в 1996, 1999 и 2003 гг, национальных конференциях с международным участием "Искусственный интеллект" в 1996 и 1998 гг, на третьем сибирском конгрессе по прикладной и индустриальной математике, посвященном памяти CJI Соболева в 1998 г, на международной конференции «Interval Methods and Computer Aided Proofs in Science and Engineering» (INTERVAL'96) в 1996 г

Автором по теме диссертации опубликовано 13 печатных работ Структура и объем работы

Диссертационная работа состоит из введения, четырех глав и списка литературы Общий объем работы 152 страницы Список литературы содержит 72 наименования Работа включает 12 таблиц, 13 рисунков и графиков

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы исследований и формулируются задачи диссертационной работы

В первой главе работы приведено формальное описание метода недоопределенных вычислений, используемого для решения задачи удовлетворения ограничений На основе введенных понятий выполняется уточнение и конкретизация способов представления множества значений переменных, дано краткое описание их основных свойств, а также выполняется формальное описание семантики основных типов данных и видов ограничений Одним из основных понятий метода недоопределенных вычислений является вид недоопределенности Вид недоопределенности SDk{D) - это способ представления множества значений переменной, обладающий следующими свойствами

1 SDk{D)c 2°

2 0 е SD, (/>), De SDk (d) , V* s D, SDt (d)

3 x,,x2 e SDk (£>)=> x, c\x7 e SDk(d)

Существует достаточно много различных видов недоопределенности

- одиночное значений: = {0.О,{х}\хеО\;

- интервал: 1п1егуа1(й)= {0,[1оы,ирр1,\;

ограниченное перечисление: Епит„ (/)) = {0.Д X \ .V с р\х\ < Л'}; ограниченный мультиинтервал ШШтег»а1н{р)~Щ\ Х = е 1ше^и1{о\ I < .V};

- структура: Я/шсф).

В работе представлен новый вид нед определенности: Шxedli{D), объединяющий достоинства интервала и перечисления.

Вид недоопределейности связан с типом данных переменной. БибJ[иoтeки

системы NemoNext содержат следующие типы данных.

Тип данных Вид н едоо! тред елен н о стя Описание

interval int Interval Целое число, представленное в виде интервала.

enum int EnumK , Mixed v Целое число, представленное (в зависимости от версии библиотеки) либо в виде перечисления, либо в виде комбинации интервала и перечисления.

en urn scale Ettutfl . Целое число, представленное в виде перечисления, область значений которого задастся пользователем.

single real Single Одиночное вещественное число.

interval real Interval Число, представленное в виде интервала.

enum real Mixed N Число, представленное в виде комбинации интервала и перечисления.

multi interval real MulliJnter\al„ Вещественное число, представленное в виде множества непересекающихся интервалов.

interval positive Interial Положительное вещественное число.

interval angle Interval Вещественное число, значения которого определены в интервале [- 2л, 2л].

single bool Single Логическое значение.

single string Single Строка символов произвольной длины, ограниченных "Щ.

enum string Enum, Перечисление строк.

record Struct Запись, состоящая из недоопред елейных именованных слотов.

array Struct Статический массив недоопределенных

объектов

single set Single Множество

interval set Interval Недоопределенное множество

pointer Struct Ссылка на объект

Таблица 1 Типы данных системы ШтоЫех1

В Таблице 1 перечислены основные типы данных, указан связанный с ними вид недоопределенности и даны краткие пояснения В первой главе работы дано подробное формальное описание перечисленных типов данных

Другим базовым понятием задачи программирования в ограничениях является собственно ограничение В системе 1Чето№х1 реализован достаточно большой набор различных видов ограничений (примерно 1000), семантика некоторых из них описана в конце первой главы Полный список типов данных и ограничений системы ЫетоИех! приводится в Приложении 1

Во второй главе рассматривается строение системы ИетоЫех! как с точки зрения архитектуры и внутреннего строения системы, так и с позиции пользователя и языка описания модели

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

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

• расширяемость системы новыми типами данных и ограничениями,

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

• использование концепции «недоопределенность» для работы с неточными и не полностью определенными данными

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

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

Транслятор описания модели на языке NemoNext

Интеграционный модуль системы САЛА

Библиотеки типов данных и ограничений | АЬзЬ^айТурез |

•

Numbers - —| PaitialConstraints j

1-* 4—1

j MultnntervalReals j—Enumlntegers j-— —j RootLocation J

t

j Arrays |— —| BinaryTables |

| Strings j— —| BlackBoxes (

| Sets |—'

АР1

Рис 1 Архитектура системы №етоЪ1ех1

На Рис 1 представлены четыре уровня архитектуры системы ЫетоЫех! Самый нижний уровень составляют библиотеки типов данных и ограничений,

10

которые загружаются динамически при построении конкретной модели

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

Уровень API представляет собой описание и реализацию внешнего программного интерфейса системы

Внешний (сервисный) уровень содержит набор утилит для тестирования и отладки системы, трансляторы с языка описания модели NemoNext, модули для интеграции с другими системами и тд

Наиболее удобным средством для описания возможностей системы, является язык описания модели NemoNext, который обладает следующими свойствами

- Язык поддерживает все возможности системы

- Язык является декларативным и используется для формулировки решаемой задачи, а не алгоритма решения

- Язык является объектно-ориентированным, что позволяет создавать новые типы данных (классы) с помощью механизма наследования, инкапсулировать характерные ограничения внутрь классов и переопределять методы классов

- Язык поддерживает механизм обобщенных типов данных и отношений Существуют группы типов данных, отличающиеся друг от друга одним или несколькими параметрами Такие типы данных можно создавать с помощью отдельной сущности «обобщенный тип данных» и набора параметров Характерными примером такой конструкции является массив, где параметрами являются тип элемента массива и число, задающее размер массива

- Язык содержит развитый препроцессор, используемый для упрощения создания больших моделей

- Язык поддерживает все параметры вычислителя, влияющие на процесс

вычислений

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

Ключевыми проблемами, возникающими при интеграции системы NemoNext в систему CATIA V5, являются следующие

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

2 Организация поиска различных видов решений с помощью специализированных ограничений, в том числе

• поиск решения с указанной точностью,

• поиск решения, ближайшего к заданному значению,

• поиск нескольких (или всех) раздельных решений

3 Использование внешних функций и параметров САПР CATIA V5 в модели, решаемой системой NemoNext, которые не могут быть реализованы в рамках последней Для решения данной проблемы разработана специальная технология — механизм В1аскВох-ограничений

Вторая часть главы посвящена методам поиска точечного решения Со стороны САПР от системы программирования в ограничениях требуется найти несколько видов точечных решений

- решение с заданной точностью,

- решение, ближайшее к заданному значению переменных,

- несколько (или все) различные решения,

- частичное решение

Для решения соответствующих задач система NemoNext предоставляет следующие средства

- Различные варианты метода хронологического перебора с откатами

- Методы решения задачи оптимизации

- Методы иерархического удовлетворения ограничений

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

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

Рис 2 Взаимодействие ограничения с В1аскВох-процедурой

На Рис 2 представлена общая схема работы В1аскВох-ограничения Основную проблему, возникающую при работе В1аскВох-ограничения, можно сформулировать следующим образом

Требуется найти интервальную оценку значений аргументов В1аскВох-ограничения с учетом заданных начальных значений этих аргументов

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

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

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

Для решения этих подзадач выделяется отдельная сущность - Эвристика Очевидно, что для различных типов В1аскВох мы должны использовать различные Эвристики

ira^^lBHgrHKii Тип В1аскВох-отношений: ^^.^Ще^б^&у^ые метбды . |

Simple Интервальное отношение

InputOutput Интервальная функция Интервальная бисекция

Grid Произвольное отношение Линейная интерполяция в узлах решетки

ID Gold Одномерная функция Метод «золотого сечения» Метод хорд

ID Gradient Одномерная функция Метод градиентного спуска Метод хорд

1D Quadratic Одномерная функция Метод квадратичной интерполяции Метод хорд

ID Spline Одномерная функция Интерполяция сплайном

Simplex Многомерная функция Метод деформируемого многогранника

Gradient Многомерная функция Метод градиентного спуска Метод координатного спуска

Bilinear Многомерная функция Интерполяция билинейной функцией

Таблица 2 Эвристики

В Таблице 2 перечислены реализованные Эвристики, указан вид В1аскВох-отношения, для которого данные Эвристики применяются и перечислены используемые численные методы

Для решения поставленной задачи используются хорошо известные численные методы для решения одно- и многомерных задач оптимизации Но, в нашем случае, существует ряд специфических факторов, которые приводят к значительной модификации применяемых методов

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

- Природа В1аскВох в общем случае не известна Поэтому не гарантируется ни дифференцируемость, ни непрерывность В1аскВох-функции

- Область определения В1аскВох-функции не известна Поэтому каждый из указанных методов должен корректно обрабатывать выход из области определения функции

- Алгоритмы поиска работают в ограниченной области, задаваемой начальными интервальными значениями аргументов В1аскВох-ограничения

- В процессе решения задачи ищется не интервальное, а точечное решение

- Система программирования в ограничениях ищет решение, ближайшее к заданной точке

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

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

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

5 Выполнена интеграция системы КешоЫех! в САПР САПА У5 Сформулированы возникающие при этом проблемы

ЛИЧНЫЙ ВКЛАД АВТОРА

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

- Разработка языка описания модели №тоЫех1 и реализация его транслятора

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

- Разработка механизма В1аскВох-ограничений и соответствующих "алгоритмов подключения внешних модулей Реализация библиотеки В1аскВох-ограничений для системы КешоИех!

- Формализация числовых типов данных и ограничений и реализация библиотек числовых типов данных для системы КетоИех!

Кроме того, автор внес большой вклад в разработку ядра системы КетоИех^ библиотеки поиска точных решений, библиотеки абстрактных типов данных, библиотеки строковых типов данных, модуля интеграции с системой САПА У5

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Телерман В.В., Сидоров В.А., Ушаков Д.М Интервальные и мультиинтервальные расширения в недоопределенных моделях // Вычислительные технологии, № 1 — Т 2 — 1997 — С 62-70

2 Загорулько Г.Б., Сидоров В.А., Телерман В.В, и др. НеМо+ Объектно-ориентированная среда программирования в ограничениях на основе недоопределенных моделей // КИИ'98 Шестая национальная конференция с международным участием Сборник научных трудов в трех томах Том I —Пущино, 1998 —С 524-530

3 Загорулько Г.Б., Сидоров В А , Телерман В.В. и др. Обстановка для программирования в ограничениях на основе недоопределенных моделей NeMo+ (язык, архитектура, интерфейс) // Научно-техн отчет N 7 / Российский НИИ искусственного интеллекта, Институт систем информатики им А П Ершова СО РАН — Москва, Новосибирск, 1998— 107 с

4 Загорулько Г.Б., Сидоров В А., Тарасевич В.В. Решение задач потокораспределения в сетях средствами системы НеМо+ // КИИ'98 Шестая национальная конференция с международным участием Сборник научных трудов в трех томах Том I —Пущино, 1998 —С 312-318

5 Кузнецов A.A., Сидоров В.А., Телерман В В , Ушаков Д.М., Технология решения задач в объектно-ориентированной среде НеМо+ // V Национальная конференция с международным участием "Искусственный интеллект - 96" (сборник трудов), Казань, 1996 —ТЗ —С 408—414

6 Сидоров В.А. Программирование в ограничениях с черными ящиками — Новосибирск, 2003 — 39 с — (Препр / ЗАО Ледас, N2)

7 Lipski S., Sidorov V., Telerman V., Ushakov D. Database Processing m Constraint Programming Paradigm Based on Subdefimte Models // Joint Bulletin of NCC&IIS, 12 (1999), NCC Pubhher Novosibirsk, 1999

8 Lipski S., Sidorov V, Telerman V, Ushakov D. Merging Constraint Programming Paradigm with Database Processing Третий сибирский

конгресс по прикладной и индустриальной математике, посвященный памяти С JI Соболева (1908-1989) Тез докл , часть V — Новосибирск Институт математики СО РАН, 1998 —С 54

9 Sidorov V., Telerman V. Industrial Application of External Black-Box Functions in Constraint Programming Solver // Perspectives of System Informatics Proc / Ed by M Broy, A Zamulin — Berlin а о Springer-Verlag, 2003 — P 415-422 — (Lect Notes Comput Sci, 2890)

10 Sidorov V., Telerman V., Ushakov D. Constraint Programming Techniques for Solving Problem on Graph // Perspectives of System Informatics Proc / Ed by D Bj0rner, M Broy, A Zamulm — Berlin а о Spnnger-Verlag, 1999 — P 420-429 — (Lect Notes Comput Sci, 1755)

11 Telerman V., Sidorov V., Ushakov D. Problem Solving in the Object-Oriented Technological Environment NeMo+, // Perspectives of System Informatics Proc, Lecture Notes m Computer Science 1181 — Berlin а о Sprmger-Verlag, 1996 — P 91-100

12 Telerman V.V., Sidorov V.A., Ushakov D.M. Interval and Multnnterval Extensions in Subdefmite Models // In International Conf on Interval Methods and Computer Aided Proofs m Science and Engineering (INTERVAL'96), Wurzburg, Germany, Sept 30-0ct 2, 1996 — P 131-132

13 Telerman V., Ushakov D., Sidorov V. Object-Oriented Constraint Programming Environment NeMo+ and its Applications // ICTAI'97, Newport Beach, CA, USA, 1997

Сидоров В A

Сидоров В А

МЕТОДЫ И СРЕДСТВА ПРОГРАММИРОВАНИЯ В ОГРАНИЧЕНИЯХ ДЛЯ СИСТЕМ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ

Автореферат

Подписано в печать 28 09 2007г Формат бумаги 60x90 1/16

Отпечатано на ризографе " AL Group" 630090, г Новосибирск, пр акад Лаврентьева, 6 Заказ № 748

Объем 1,0 уч -изд л _Тираж 100 экз

Введение.

Глава 1. Система NemoNext. Формальное описание.

Методы достижения совместности.

Базовые понятия.

Модель NemoNext.

Алгоритм удовлетворения ограничений системы NemoNext.

Виды педоопределённости.

Одиночное значение (Single).

Интервал (Interval).

Перечисление (Enum).

Ограниченное перечисление (EnumN).

Мультиинтервал (Multilnterval).

Ограниченный мультиинтервал (MultilntervalN).

Смешанный вид недоопределённости (MixedN).

Структурный вид недоопределённости (Struct).

Особые случаи.

Логический тип данных.

Применение вида недоопределённости Single.

Применение мультиинтервалов.

Типы данных.

Целые числа.

Вещественные числа.

Логический тип данных.

Строки.

Структуры.

Запись.

Массив.

Множество.

Ссылка.

Ограничения.

Ограничения для типа данных interval int.

Ограничения для типа данных interval real.

Ограничения для типа данных single bool.

Ограничения для типа данных enum string.

Ограничения для типа данных array.

Ограничения для типа данных interval set.

Глава 2. Система программирования в ограничениях NemoNext.

Архитектура системы NemoNext. Инструментальный уровень.

Библиотеки типов данных и ограничений.

Вычислитель.

Сервисный уровень.

Архитектура системы NemoNext. Пользовательский уровень.

Декларативное представление модели.

Модульность.

Виды недоопределённости.

Типы данных.

Отношения.

Объектно-ориентированная парадигма описания модели.

Механизм обобщённых классов и отношений.

Классы решаемых задач.

Глава 3. Интеграция системы программирования в ограничениях NemoNext в САПР.

Параметрическое проектирование.

Реализация параметрического проектирования в системе CATIA V5.

Виды инженерных отношений.;.

Параметрическая оптимизация.

Интеграция NemoNext в систему CATIA V5.

Методы поиска точного решения в системе NemoNext.

Поиск точного решения.

Оценка точности найденного решения.

Нахождение точного решения, ближайшего к заданному.

Задача оптимизации.

Иерархическое удовлетворение ограничений.

Выбор ближайшего решения с помощью эвристик метода полного перебора.

Нахождение нескольких точечных решений.

Ползущие решения.

Поиск частичного решения.

Реализация.

Глава 4. В1аскВох-ограничение.

Формулировка задачи.

Взаимодействие внешней процедуры с В1аскВох-ограничением.

Эвристики.

Многомерные эвристики.

Алгоритм «Бисекция».

Градиентный метод.

Метод координатного спуска.

Дополнительные задачи.

Локальность.

Поиск условного экстремума.

Несовместные точки.

Поиск точного решения.

Поиск решения, близкого к заданной точке.

Одномерные Эвристики.

Квадратичная интерполяция.

Локальность.

Другие эвристики.

Алгоритм «Interval Bisection».

Реализация.

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

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

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

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

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

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

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

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

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

Примером NCSP может быть решение уравнения <<sin(x*cos(y))-cos(y*sin(x)) = 0». Задача состоит из двух переменных («х» и «у») и одного ограничения. В общем случае любая система уравнений и неравенств может рассматриваться как задача 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 Systèmes, ведущий производитель инженерных САПР верхнего уровня1, в рамках развития своего флагманского продукта CATIA V5 [10], столкнулась с потребностью в универсальном решателе задач удовлетворения ограничений. В этот момент основным перспективным направлением развития системы являлось повышение интеллектуальности системы. Под понятием «интеллектуальность» подразумевался набор инструментов, повышающих уровень автоматизации процесса проектирования, в частности: контроль корректности модели изделия при её модификации, автоматическое построение различных конфигураций изделия по внешним параметрам, автоматическая корректировка модели при изменении пользователем её параметров, нахождение оптимальных конфигураций и т.д. Основными требованиями, предъявляемыми к такому универсальному вычислителю, были:

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

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

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

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

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 Systèmes, то система с самого начала проектировалась для использования в качестве универсального решателя в системах автоматизации проектирования (САПР). Соответственно, одной из важнейших задач, которую необходимо было решить, была проблема интеграции системы в состав САПР С 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 Systèmes, что характеризует практическую значимость данной работы.

Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и четырёх приложений. Объем диссертации: полный - 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 Systèmes, начиная с проектирования системы программирования в ограничениях и заканчивая созданием специальной техники для работы со специфическими сущностями САПР.

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

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

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

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

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

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

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

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

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

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

1.V., Hopcroft J.E., Ullman J.D. Data structures and algorithms. — Reading: Addison-Wesley, 1983.

2. Babichev A., Kadyrova O., Kashevarova Т., Semenov A. UniCalc as a tool for solving problems with inaccurate and subdefmite data // Proc. Conf. Interval'92. — Interval Computations. — 1992. — Vol. 3(5). — P. 13-16.

3. Benhamou F., McAllester D., Van Hentenryck P. CLP(Intervals) Revisited, // Proc. 1994 Intern. Logic Progr. Simp. — MIT Press, 1994. — P. 124-138.

4. Besiere C. Arc-consistency and Arc-consistency again. // Artificial Intelligence.1994. —N65. —P. 179-190

5. Besiere C., Freuder E.C., Region J.C. Using inference to reduce arcconsistency computation. // Proc. 14th IJCAI. — 1996. — Vol. 1. — P. 592-598.

6. Borning A., Freeman-Benson В., Wilson M. Constraint Hierarchies. // Constraint Programming: Proc. 1993 NATO ASI Parnu, Estonia. — SpringerVerlag, 1994. —P. 80-122.

7. CAA С++ Source Checker: http://www.3ds.com/index.php?id=847&type=222&nocache=l&cHash=e6a36 cc62b&3dsplmproductsdomain.=19&3dsplmproducts[product]=273&filename =doc/

8. CATIA V5R17 Fact Sheet to review the new features of the Solution: http://www.3ds.com/fileadminAA 5R17/c517factsheet.pdf

9. CATIA V5R17 PLM solution for digital product definition and simulation: http://www.3ds.com/products-solutions/plm-solutions/catia/overview/

10. Cleary J. G. Logical Arithmetic. // Future Gener. Сотр. Systems. — 1987. —1. Vol 2(2). —P. 125-149.

11. Collavizza H., Delobel F., Rueher M. A note on partial consistencies over continuous domains // Proc. CP98, Pisa, Italy, October 26-30, 1998. — Berlin a. o.: Springer Verlag, 1998. —P. 147-161.

12. Davis E. Constraint Propagation with Interval Labels. // Artificial Intelligence.1987.—N32. —P. 281-331.

13. Deville Y., Van Hetenryck P. An Efficient Arc Consistency Algorithm for a Class of CSPProblems. //Proc. IJCAI. — 1991, —P. 325-330.

14. Gaschning J.A General Backtracking Algorithm That Eliminates Most Redundant Tests. // Proceeding IJCAI-77. — 1997. — P. 457.

15. Ginsberg M.L. Dynamic BackTracking. // J. Artificial Intelligence Research. — 1993.—N1.—P. 25-46.

16. Golomb S.W. , Baumert L.D. Backtrack programming // J. of the ACM. — 1965. —Vol 12,N.4. —P. 516-524.

17. Hansen E.A., Sengupta S. Bounding solutions of systems of equations using interval analysis // BIT. — 1981. — Vol. 21. — P. 203-211.

18. Haralick R.M., Elliot G.L. Increasing Tree Search Efficiency For Constraint Satisfaction Problems. // Artificial Intelligence. — 1980. — N 14. — P. 263313.

19. Huffman D.A. Impossible objects as nonsence sentences // Machine Intelligence. — 1971. — Vol. 6. — P. 295-323.

20. Hyvonen E. Constraint Resoning Based on Interval Arithmetic. // Proc. IJCAI.1989. —P. 193-199.

21. Nelder J.A., Mead R. A simplex method for function minimization. Computer Journal, P. 308-313,1965.

22. Kumar V. Algorithms for Constraint Satisfaction Problems: A Survey. // AI Magazine. — 1992. —Vol.l3(l). —P. 32-44.

23. Lhomme O. Consistency techniques for numeric CSP's // Proc. of the 13th IJCAI / Ed. by R. Bajcsy. — IEEE Computer Society Press, 1993. — P. 232238.

24. Lipski S., Sidorov V., Telerman V., Ushakov D. Database Processing in Constraint Programming Paradigm Based on Subdefinite Models // Joint Bulletin ofNCC&IIS,. 12 (1999), NCC Publiher. Novosibirsk, 1999.

25. Mackworth А.К. Consistency in Networks of Relations. // Artificial Intelligence. — 1977. — N 8. — P. 99-118.

26. Minton S., Johnston M.D., Philips A.B., Laird P. Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method. // Proc. of AAAI90. — 1990. — P. 17-24.

27. Mohr R., Henderson T. Arc-consistency and path-consistency revisited. // Artificial Intelligence. — 1986. — N 28. — P. 225-233.

28. Narin'yani A.S. NE-factors: Different Pragmatics of an Interval in Knowledge Representation // Conf. on Numerical Analisys with Automatic Result Verification, Lafayette, Louisiana, February 25-March 1, 1993.

29. Nilsson N.J. Principles of artificial intelligence. — Palo Alto: Tioga, 1980. 66. Numerical Computation Guide. — Mountain View, USA, November, 1995.

30. Lewis R.M., Torczon V., and Trosset M.W. Direct search methods: Then and now. Journal of Computational and Applied Mathematics, 124, 2000.

31. Jacoby S.L.S., Kowalik J.S., and Pizzo J.T. Iterative Methods for Nonlinear Optimization Problems. Prentice-Hall, Englewood Cliffs, N.J., 1972.

32. Telerman V., Sidorov V., Ushakov D. Problem Solving in the Object-Oriented Technological Environment NeMo+, // Perspectives of System Informatics: Proc., Lecture Notes in Computer Science 1181. — Berlin a.o.: Springer-Verlag, 1996. —P. 91-100.

33. Telerman V., Ushakov D. Data Types in Subdifinite Models. // Artificial Intellegence and Symbolic Mathematical Computation: Proc., Lecture Notes in Computer Science 1138. — Springer-Varlag, 1996. — P. 305-319.

34. Telerman V., Ushakov D. Subdififnite Models as a Variety of Constraint Programming. // Proc. 8th Intern. Conf. on Tools with Artificial Intelligence. ICTAI'96. —IEEE Computer Soc., 1996, —P. 157-163.

35. Telerman V.V. Propagation of numerical constraints in sub-definite models // International Congress on Computer Systems and Applied Mathematics (CSAM'93), St.Petersburg, July 19-23, Abstracts. — St.Petersburg, 1993. — P. 101-102.

36. Tsang E. Foundation of Constraint Satisfaction. — London: Academic Press Ltd., 1993.

37. Ushakov D. Some Formal Aspects of Subdifinite Models. — Novosibirsk, 1998. — 23 p. — (Preprint/A. P. Ershov Institute of Informatics Systems,

38. Siberian Division of Russian Academy of Sciences; N 49).

39. Van Hentenryck P., Michel L., Deville Y. Numérica: a modeling language for global optimization. — Cambridge: MIT Press, 1997.

40. Telerman V., Ushakov D., Sidorov V. Object-Oriented Constraint Programming Environment NeMo+ and its Applications // ICTAI'97, Newport Beach, CA, USA, 1997.

41. Гурии JI.C., Дымарский Я.С., Меркулов А.Д. Задачи и методы оптимального распределения ресурсов. Москва: Советское радио, 1968 -463 с.

42. Загорулько Ю.А., Попов И.Г. Представление знаний в интегрированной технологической среде SemP-TAO. // Проблемы представления и обработки не полностью определенных знаний / под ред. И. Е. Швецова. — Москва,

43. Новосибирск, 1996. — С. 59-74.

44. Загорулько Ю.А. Технология конструирования развитых системобработки знаний на основе семантических сетей и систем продукций.-Новосибирск, 1995. — 65 с. (Препр./ РАН. Сиб. отд-ние. ИСИ; N 27).

45. Летова Т.А., Пантелеев A.B. Экстремум функций в примерах и задачах. Москва: МАИ, 1998. — 376 с.

46. Лоенко М .Ю. Алгоритм коррекции решения // Тр. конф. молодых ученых, посвященная 10-летию ИВТ СО РАН. — Новосибирск, 2001. — Т. 1. — С. 49-53.

47. Нариньяни A.C. недоопределённость в системах представления и обработки знаний. // Изв. АН СССР. Сер. "Техн. кибернетика." — 1986. — N5. —С. 3-28.

48. Нариньяни A.C. недоопределённые множества новый тип данных для представления знаний. — Новосибирск, 1980. — 33 с. — (Переп. / АН СССР. Сиб. отд-ние. ВЦ; N 232).

49. Нариньяни А.С, Телерман В.В., Ушаков Д.И., Швецов И.Е. Программирование в ограничениях и недоопределённые модели // Информационные технологии. — М.: Машиностроение, 1998. — № 7. — С. 13-22.

50. Нариньяни A.C. недоопределённые модели и операции с недоопределёнными значениями. — Новосибирск, 1982. — 33с. — (Препр. / АН СССР. Сиб. отд-ние. ИЦ; N 400).

51. Сидоров В.А. Программирование в ограничениях с чёрными ящиками. —

52. Новосибирск, 2003. — 39 с. — (Препр. / ЗАО Ледас; N2).

53. Телерман В.В. Использование мультиинтервалов в недоопределённыхмоделях. // Тез. докл. X всесоюз. семинара " Параллельное программирование и высокопроизводительные системы: Методы представления знаний в информационных технологиях". — Киев, 1990.

54. Телерман В.В., Дмитриев В.Е. Технология программирования на основе недоопределённых моделей. — Новосибирск, 1995. — 38 с. — (Препр. / РАН. Сиб. отд-ние. ИСИ. N 25).

55. Телерман В.В., Сидоров В.А., Ушаков Д.М. Интервальные и мультиинтервальные расширения в недоопределённых моделях // Вычислительные технологии №1. — Т. 2, — 1997. — С. 62-70.

56. Телерман В.В., Ушаков Д.М. Недоопределенные модели: формализация подхода и перспективы развития // Проблемы представления и обработки не полностью определенных знаний / Под ред. И.Е. Швецова. — Москва-Новосибирск: РосНИИ ИИ, 1996. — С. 7-30.

57. Тыугу Э.Х. Концептуальное программирование. — М.: Наука, 1984. 255 с.

58. Швецов И.Е. Основные положения технологии активных объектов. — Новосибирск, 1995. — 26 с. — (Препр. / РосНИИ ИИ).

59. Швецов И.Е., Нестеренко Т.В., Старовит С.А., Титова М.В. Технология активных объектов: от концепции к реализации. //Проблемы представления и обработки не полностью определенных знаний / под. ред. И. Е. Швецова.

60. Москва, Новосибирск, 1996. — С. 88-100.

61. Швецов И.Е., Телерман В.В. Интервалы и мультиинтервалы внедоопределённых вычислительных моделях // Тр. Междунар. конф. по интервальным и стохастическим методам в науке и технике "ИНТЕРВАЛ92", 1992. —Т. 1, —С. 201-203.

62. Загорулько Ю.А., Попов И.Г., Костов Ю.В., Сергеев И.П. Общая концепция агентов в системе моделирования SEMP-A. // Труды международной научно-практической конференции KDS-2001 "Знание

63. Диалог- Решение". — Т. 1. — Санкт-Петербург, 2001. — С.259-267.

64. Яковлев А.Г. Машинная арифметика мультиинтервалов. // Вопросы кибернетики. Проблемно-ориентированные вычислительные системы. — 1987. —С. 66-81.