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

Липатов, Алексей Андреевич

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

кандидата технических наук: Липатов, Алексей Андреевич
город: Москва
год: 2006
специальность ВАК РФ: 05.13.11

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

Автореферат диссертации по теме "Методы и программные средства интеллектуализации пользовательского интерфейса систем недоопределенных вычислений"

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

Липатов Алексей Андреевич

МЕТОДЫ И ПРОГРАММНЫЕ СРЕДСТВА ИНТЕЛЛЕКТУАЛИЗАЦИИ ПОЛЬЗОВАТЕЛЬСКОГО ИНТЕРФЕЙСА СИСТЕМ НЕДООПРЕДЕЛЁННЫХ ВЫЧИСЛЕНИЙ

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

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

Москва - 2006

Работа выполнена в Московском инженерно-физическом институте (государственном университете)

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

Рыбина Галина Валентиновна

Официальные оппоненты: доктор технических наук, профессор

Еремеев Александр Павлович

кандидат технических наук, доцент Тарасов Валерий Борисович

Ведущая организация: Государственное учреждение

Российский научно-исследовательский институт информационных технологий и систем автоматизированного проектирования (ГУ РосНИИИТАП)

Защита состоится « 4 » октября 2006 г. в 15 час. 00 мин. на заседании диссертационного совета Д 212.130.03 в МИФИ по адресу: 115409, г. Москва, Каширское шоссе, дом 31.

С диссертацией можно ознакомиться в библиотеке МИФИ. Автореферат разослан «¿»августа 2006 г.

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

Учёный секретарь / Д ^^ 1 я» Шумилов Ю.Ю.

диссертационного совета

2JDOG£

Л6АО'I

Общая характеристика работы

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

Диссертационная работа посвящена решению проблемы интеллектуализации пользовательских интерфейсов в контексте одного из ведущих в последние годы направлений в искусственном интеллекте (ИИ) - методов и систем программирования в ограничениях (Constraint Programming). Сегодня методы программирования в ограничениях широко применяются для решения задач проектирования, планирования, поддержки разработок пользовательских интерфейсов, в электронных таблицах и системах, подобных им, в различных задачах искусственного интеллекта, в качестве расширений универсальных языков программирования и во многих других областях. Программирование в ограничениях является по своей сути максимально декларативным, поскольку основано на описании модели задачи, а не алгоритма ее решения, благодаря чему, методы программирования в ограничениях широко используются для задач с недооп-ределёнными данными. К числу методов программирования в ограничениях, наиболее часто применяемых для решения задач с недоопределёнными данными, относятся метод недоопределённых вычислений, метод толерантного распространения ограничений, метод распространения значений и др.

Значительный вклад в исследование и решение данных проблем внесли отечественные учёные Д.А. Поспелов, Э.В. Попов, А.Н. Мелихов, Э.Х. Тыугу, Г.С. Осипов, А.С. Нариньяни, Г.В. Рыбина, А.П. Еремеев, В.Б. Тарасов, И.Б. Фоминых, А.Н. Аверкин, Н.Г. Ярушкина, В.М. Курейчик, а также целый ряд зарубежных учёных JI. Заде (L. Zadeh), Д. Дюбуа (D. Dubois), А. Прад (А. Prade), Д. Уолц (D. Waltz), А. Макверс (A. Mackworth), У. Монтанари (U. Моп-tanari), Е. Фредер (Е. Freuder), Е. Хивонен (Е. Hyvonen) и др.

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

• недоопределённость значений переменных;

• наличие в модели большого числа переменных и ограничений;

• необходимость вносить изменения в модель в процессе решения задачи, воздействуя таким образом, на её область решения;

• наличие сложной внутренней структуры у моделируемых фрагментов действительности (экономика страны, региона, технический объект, календарный план проекта).

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

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.-Петербург

ОЭ 200 ¿Гкт

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

• обеспечение визуального представления недоопределённых значений переменных модели;

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

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

• обеспечение графического отображения процесса решения задач и управления им.

В современных коммерческих системах программирования в ограничениях таких как, UniCalc, "Интегра", Time-Ex (Российский НИИ искусственного интеллекта), ILOG CP, ILOG OPL Development Studio (ILOG, Франция-США), Koalog Constraint Solver, Koalog Configurator (Koalog SARL, Франция), MINERVA (IF Computer Japan Ltd., Япония) и др., эти проблемы решены не полностью.

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

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

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

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

2. Разработка методов интерактивного графического представления массивов числовых переменных и функциональных зависимостей, заданных в недоопределённых моделях.

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

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

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

6. Разработка архитектуры графической подсистемы для систем недоопреде-лённых вычислений.

7. Разработка и программная реализация графической подсистемы для систем недоопределённых вычислений

8. Интеграция графической подсистемы в состав оболочки интеллектуального решателя 1МСа1с.

9. Использование графической подсистемы для решения задач в рамках решателя ишСак.

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

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

Научная новизна. В диссертации получены следующие новые результаты.

1. Предложен новый метод интерактивного графического отображения одномерных массивов недоопределённых числовых переменных.

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

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

4. Предложен способ расширения области применения кластерного подхода для недоопределённых моделей.

5. Предложен новый метод частичной автоматизации внесения изменений в структурные недоопределённые модели в процессе решения задачи на основе их интеграции с элементами императивного управления.

6. Разработаны оригинальные алгоритмы интерактивного графического представления массивов недоопределённых числовых переменных и функциональных зависимостей, заданных в недоопределённых моделях.

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

Основные научные результаты, выносимые на защиту.

1. Новый метод интерактивного графического отображения одномерных массивов недоопределённых числовых переменных.

2. Новые методы интерактивного графического отображения двухмерных и трёхмерных массивов недоопределённых числовых переменных.

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

4. Способ расширения области применения кластерного подхода для недоопределённых моделей.

5. Новый метод частичной автоматизации внесения изменений в структурные недоопределённые модели в процессе решения задачи на основе их интеграции с элементами императивного управления.

6. Оригинальные алгоритмы интерактивного графического представления массивов недоопределённых числовых переменных и функциональных зависимостей, заданных в недоопределённых моделях.

7. Новая архитектура графической подсистемы для систем недоопределённых вычислений.

8. Программная реализация графической подсистемы для систем недоопределённых вычислений.

Практическая значимость.

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

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

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

полученных результатов с результатами, приведёнными в научной литературе, а также актом о внедрении.

Реализация результатов. Разработанная графическая подсистема интегрирована в состав недоопределённого решателя UniCalc.

Результаты работы использованы в НИР, выполненных в РосНИИ искусственного интеллекта в рамках следующих проектов:

• международный проект «Распределённое императивное программирование в ограничениях» в сотрудничестве с Centre for Mathematics and Computer Science (CWI) (Центр исследований в информатике), финансировавшийся NWO (Нидерландская организация по научным исследованиям);

• проект «Разработка аппарата решения сложных вычислительных задач в условиях неточной и недоопределённой информации на основе методов программирования в ограничениях», поддержанный РФФИ (грант № 03-01-00750).

Результаты работы также применялись в рамках проектов Министерства обороны РФ по Государственному оборонному заказу 2000-2004 гг.:

• «Комплексные исследования по созданию интегрированной системы информационно-аналитического обеспечения военно-экономического анализа и экспертиз мероприятий строительства, развития и содержания Вооружённых сил Российской Федерации» (шифр «Интегра»);

• «Разработка методического аппарата военно-экономического анализа в системе бюджетного планирования Министерства обороны Российской Федерации» (шифр «Барракуда»);

• «Разработка научно-методических основ проведения военно-экономических исследований с использованием математических методов ситуационного анализа, оптимизации и принятия решений» (шифр «Сатисфакция»),

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

• Time-EX, система ресурсно-календарного планирования на основе недооп-ределённых моделей и развитой временной логики;

• "Интегра", технология электронных таблиц на основе недоопределённых вычислений;

• "Экономика", технология разработки недоопределённой модели макроэкономики на основе технологии "Интегра";

• "Региономика", специализация технологии "Экономика" для разработки со-цио-экономических моделей регионов РФ.

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

Апробация результатов. Основные положения и результаты диссертации докладывались и обсуждались на III международной конференции «Проблемы управления и моделирования в сложных системах», (г. Самара, 2001 г.), на 9-й национальной конференции по искусственному интеллекту с международным

участием - КИИ'2004 (г. Тверь, 2004 г.), на «Научных сессиях МИФИ» (г. Москва, 1999 - 2006 гг.). Доклады, представленные на «Научных сессиях МИФИ» в 2002, 2004 и 2005 гг., были отмечены дипломами «Научной сессии МИФИ».

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

Структура и объём работы. Диссертация состоит из введения, четырёх разделов, заключения, списка использованной литературы (69 наименований) и приложений. Основная часть диссертации содержит 150 страниц машинописного текста, включая 33 рисунка, 7 таблиц.

Содержание работы

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

В первом разделе рассматриваются проблемы взаимодействия пользователя с системами недоопределённых вычислений (Н-вычислений). Значение и сложность проблемы взаимодействия человека с ЭВМ возрастают как по мере вовлечения в процесс непосредственного взаимодействия с ЭВМ большого числа конечных пользователей, работающих в диалоговом режиме, так и в связи с разработкой систем, осуществляющих представление и обработку недоопределённых данных и знаний. Недоопределённость - свойство данных и знаний, определяемое как частичное знание о сущности х, ограниченное информацией о том, что х принадлежит к некоторому конкретному множеству X. Уточнение знаний или данных, описывающих х, приводит к сокращению множества X, стягивающемуся в потенциале до одного элемента, отражающего полную информацию о х. В диссертации рассматриваются вопросы, связанные только с недоопределёнными числовыми значениями, причём, множество X задаётся числовым интервалом, например: х = [1.7, 5.9]. Этот вид недоопределённости к настоящему времени наиболее проработан в теоретическом плане, а средства представления и обработки недоопределённых числовых значений реализованы в ряде программных продуктов.

Для решения задач с недоопределёнными данными широко используются методы программирования в ограничениях, основанные на описании модели объекта, с которым связана решаемая задача, как набора ограничений R =" {Rb R2, ..., Rk} над переменными хь х2, ..., х„ с областями значений соответственно Aj, А2,..., Ап. Ограничения могут иметь вид уравнений, неравенств, логических выражений и т. п. Методы программирования в ограничениях обеспечивают автоматическое нахождение наборов значений (аь а2, ..., an), а,еА„ i =1,2, ..., п, одновременно удовлетворяющих всем ограничениям из множества R.

На рис. 1 показаны некоторые системы программирования в ограничениях, решающие задачи с недоопределёнными данными, и области их применения.

"Интегра"

Финансовое планирование Расчет бюджета

РосНИИ

ис|усствеиного интеллекта

Time-Ex

Ре сур ш^халщирше планировали на основе неполных данных

РосНИИ

иыусственного интеллекта

"Экономика"

Прогнозир оваше макроэкономически! процессов на уровне страны, региона, отрясли, корпорации

РосНИИ исфсствонного интеллекта

ILOG OPL Development 8tudio

Календарное планирование Маршрупцацни_

ILOG (Франц»я-США)

SemP-T

Разработка

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

РосНИИ иыусствонного интеллекта

СИСТЕМЫ I

ПРОГРАММИРОВАНИЯ В

ОГРАНИЧЕНИЯХ, РЕШАЮЩИЕ ЗАДАЧИ С Г НЕДООПРЕДЕЛЁННЫМИ ДАННЫМИ

ILOG Solver

Календарное плашфование Составление расшсаннй Днспетчершация Распределение ресур сов

ILOG (Франция-США)

UrriCalc

Инженерные расчёты Геометрическое проектирование Решете задач в области

РосНИИ искусственного интеллекта

Nemo+

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

РосНИИ

ис!усственного интеллекта

ЕСЪ*Р8в система логического программирования

Интервальная библиотека I

Решение нелинейных систем ограничений

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

Рис. 1. Системы программирования в ограничениях, решающие задачи с недоопределёнными данными, и области их применения.

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

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

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

Рис. 2. Общая схема решения задачи с помощью системы Н-вычислений.

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

• недоопределённость значений переменных;

• наличие в Н-модели большого числа переменных и ограничений;

• необходимость вносить изменения в Н-модель в процессе решения задачи, воздействуя, таким образом, на её область решения;

• наличие сложной внутренней структуры у моделируемых фрагментов действительности (экономика страны, региона, технический объект, календарный план проекта).

Проведённый анализ наиболее развитых современных систем Н-вычислений, таких, как решатель UniCalc, система недоопределённых электронных таблиц "Интегра", система решения макроэкономических задач "Экономика", система ресурно-календарного планирования Time-Ex, показал, что одним из перспективным путей решения указанных проблем является развитие пользовательского интерфейса систем Н-вычислений за счёт создания

средств визуализации различных элементов Н-моделей, а также разработки средств структурного представления Н-моделей.

Существующие средства графического отображения Н-моделей современных систем Н-вычислений имеют ряд недостатков, наиболее существенными из которых являются следующие.

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

2. Визуализация только одномерных массивов переменных.

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

4. Невозможность визуализации функций более чем от одного аргумента.

5. Не решены проблемы визуализации массивов с большим числом переменных.

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

1. Структурирование набора переменных при не структурированном наборе ограничений (система "Интегра").

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

3. Отсутствие структурирования Н-моделей на уровне вычислительного ядра системы (системы "Интегра" и Time-Ex).

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

• обеспечение взаимодействия пользователя с системой в наглядной и компактной форме, в частности, прямого воздействия пользователя на область решения Н-модели;

• развитие метода Н-вычислений за счёт повышения уровня языка описания задачи и введения дополнительных возможностей управления процессом решения.

Сформулирована цель и поставлены задачи диссертационного исследования.

Во втором разделе излагаются формальные основы аппарата Н-моделей, и метода Н-вычислений. Модель определяется множеством переменных X и множеством отношений на этих переменных R. Каждой из переменных хеХ сопоставлена область значений, являющаяся подобластью универсума U. Декартово произведение областей значений всех переменных произвольной сово-

купности Х'сХ называется областью значений совокупности переменных X'. Каждое т-арное (т = 1,2,...) отношение геЯ, связывающее переменные Х'={хь х2,...,хт}, есть подмножество области значений X'. Отношение г(Х') можно рассматривать и как подмножество области значений X, включающее все значения X, проекция которых на область значений X' принадлежит г. Это позволяет все отношения модели рассматривать как отношения, определённые на всей области значений X.

Пусть хеХ имеет область значений А. Обозначим *А множество всех подмножеств А без пустого. Переменной х взаимно однозначно сопоставляется недоопределённая переменная (Н-переменная) *х с областью значений на *А. Значения *ае*А, которые включают лишь один элемент из А, называются точными, а остальные - недоопределёнными (Н-значение). Значение *а равное А называется полной неопределённостью и обозначается а .

Недоопределённым расширением (Н-расширением) алгебры О = (А, Б) на классе объектов А, замкнутом относительно множества Б унарных, бинарных и т. д. операций, называется алгебра = (*А, *Р). Операции алгебры получаются расширением операций множества Б на класс *А по следующей формуле: *^*а1,...,*ат) = {а = ДЪ)| Ь ех™,*а,}. Расширенные операции замкнуты на *А и сохраняют коммутативность и ассоциативность в тех случаях, когда эти свойства имели место у исходных операций. Однако, в сохраняются не все свойства операций алгебры р. На основе Н-расширения операций могут быть построены Н-расширения функций, а функции, в свою очередь, могут использоваться для интерпретации отношений модели, содержащей Н-переменные. Для одного и того же множества А можно построить различные Н-расширения. Будем рассматривать интервальное Н-расширение: А1п'с™' = { [а^5, аир] | а1'0, аир е А }. Здесь а1"0 обозначает нижнюю, а аир - верхнюю границу интервала. Пустому множеству соответствует любой интервал, где аЬс>аир. К Н-значениям такого вида могут применяться операции интервальной арифметики.

С использованием описанных выше понятий Н-модель определяется как четвёрка (X, Л, С), где: X - множество Н-переменных, Я - множество функционально интерпретируемых ограничений на значениях переменных из X, -множество функций присваивания, С - множество функций проверки корректности. Каждой переменной хеХ сопоставлены область значений Ах, начальное значение ахеАх, функция присваивания вида = где

%оЫ - текущее Н-значение х, а - Н-значение, полученное в ходе вычислений, и функция проверки корректности, проверяющая, не является ли новое Н-значение переменной пустым. Н-модель может быть представлена как функциональная сеть, на которой выполняется процесс Н-вычислений. Н-модель обладает следующими свойствами:

• процесс Н-вычислений завершается за конечное число шагов;

• достижение процессом неудачи (значение одной из Н-переменных стало пустым) или успеха (вычисление ни одной из функций интерпретации не при-

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

• в случае успеха процесса, при одних и тех же входных Н-значениях переменных Н-модели их выходные Н-значения не зависят от конкретной стратегии выбора очередного ограничения для интерпретации;

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

Далее рассматриваются разработанные в диссертации методы интерактивного графического представления заданных в Н-моделях одномерных, двухмерных и трёхмерных массивов числовых Н-переменных, а также пользовательских функций от одной и двух переменных и методы структурного представления Н-моделей. В Н-моделях могут быть определены массивы Н-переменных, имеющие одно и более измерений. С помощью массивов могут быть представлены такие математические объекты, как матрицы коэффициентов СЛАУ, векторы переменных систем уравнений, множества значений функций на заданных областях значений аргументов и т.д.

Предложенный метод интерактивного графического отображения одномерных массивов Н-переменных предусматривает сопоставление каждому элементу х, массива Х=(Х1,Х2,...,хп) строки изображения, в которой визуализируется Н-значение а, данного элемента (рис. 3). Высота строки может настраиваться путём выбора одного из трёх масштабов изображения:

• основного - информация об элементе массива отображается в графической и текстовой форме, обеспечивается возможность ввода дополнительных ограничений вида x¡ < (>) С путём изменения графического отображения элемента массива;

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

• графического - графическое отображение выполняет только иллюстративную функцию.

Для любого масштаба автоматически определяется высота строки, обеспечивающая отображение наибольшего количества элементов массива при заданных ограничениях. Так, например, в основном масштабе высота строки И определяется по формуле Ь = шах(Ьт1П, тт(Ц-ипс(—), Ь )), где Ьтш - минимальная

N

высота строки, обусловленная необходимостью отображения текста, Ьтах - максимальная высота строки, Н - высота доступной области экрана, N - число элементов в массиве, Штс - функция выделения целой части действительного числа. Масштаб шкалы значений переменных также может настраиваться. При этом цена деления линейной шкалы имеет вид п-10т, где п е {1, 2, 5},

тт1П < т < ттах, шт1П - порядок наименьшего, а ттах - наибольшего представи-мого в системе числа.

Й Не« РпкуИг |Ь \АА1 ..РЖУПО^МИИУщкдюПи усЛ«|4..1М ИИР,

Рис. 3. Одномерный массив показан с использованием линейной шкалы.

Для отображения массивов с большим разбросом значений элементов используется специальная шкала, значения которой вычисляются по формуле а' = 51§п(а) • 1я(|а| + 1). Возможность сравнения результатов, полученных на разных шагах вычисления Н-модели, обеспечивается хранением в памяти системы для каждого массива х набора его состояний = (зХ|,яХ2,..-,зхт). Значения переменной х„ соответствующие разным состояниям, отображаются разными оттенками цвета (рис. 3). На фоне данных, скорректированных на двух предыдущих шагах вычислений, видны дополнительные ограничения, приведшие к сужению области решения.

Разработанный в диссертации метод интерактивного графического отображения двухмерных массивов Н-переменных основан на том, что каждому элементу хч, I = 1,2,..., п,3 = 1,2,..., т массива Н-переменных хп х2, ... хп1

Х=х12 х22 ■•■ Хл2 х1т х2т ••• хпт

соответствует фрагмент изображения, цвет которого отображает интервальное Н-значение элемента хч (рис. 4). Цвет может показывать среднее значение ин-

хир -хь°

тервала х = —-— или его ширину 1„ = хиир-хиЬс. Шкала цветов, применяе-

} 2

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

Ж Ми1ИГ.*1П|Ам1 и ни ИИ О

ШМ** 'ШШ^ЗШШШ !

Рис. 4. Отображение двухмерного массива Н-переменных с настраиваемой

шкалой цветов.

В диссертации разработан метод интерактивного графического отображения трехмерных массивов Н-переменных, основанный на представлении проекций массива на плоскости, параллельные плоскостям, в которых один из индексов массива неизменен. Проекциями трёхмерного массива X = (Х|,Х2,...,ХП), где Х„ ¡=1,2,...,п - двухмерный массив размерностью шхк элементов, являются двухмерные массивы размерностью пхт, тхк, пхк элементов. Элемент такого массива соответствует вектору массива X. Цвет элемента может отображать одну из следующих характеристик соответствующего вектора: наименьшее и наибольшее среднее значение интервального значения в данном векторе, наименьшее и наибольшее значение недоопределённости в данном векторе.

Цвет, соответствующий отображаемому числовому значению, определяется аналогично тому, как это делается в методе графического отображения двухмерных массивов Н-переменных. Трехмерный массив также может быть представлен в виде набора его сечений по заданным пользователем плоскостям, которые визуализируются как двухмерные массивы.

В Н-модели могут присутствовать явно описанные функциональные зависимости. Значения таких функций могут быть недоопределёнными. Предложенный в диссертации метод интерактивного графического отображения функции от одного аргумента заключается в том, что значения функции f(x) на заданном пользователем интервале значений аргументов [xmm, xmax] отображаются в виде кривых, представляющих верхнюю и нижнюю границы Н-значений функции. Кривые строятся на основе одномерного массива Н-значений функции, определяемых по следующей формуле: у; = f(x0 ——-i).

п-1

i = 0,1,..., п — 1, где хо= xmin, xn_ 1 = х1ГШХ, п - число элементов массива значений, по которым строится отображение функции. Метод характеризуется следующими основными возможностями.

1. Масштабирование изображения по двум координатным осям.

2. Применение специальных шкал, аналогичных применяемым при визуализации одномерных массивов.

3. Возможность ввода ограничений на значение функции вида f(x) < (>) С, где xefxmm, Xmax], С - некоторая константа.

4. Возможность сравнения значений, полученных на разных шагах вычислений Н-модели.

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

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

• интервальная недоопределённость значений переменных Н-модели;

• возможность уточнения Н-модели путём наложения ограничений на значения её переменных;

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

По сравнению с графическими средствами таких коммерческих систем Н-вычислений, как UniCalc, "Интегра" (РосНИИ искусственного интеллекта), ILOG CP, ILOG OPL Development Studio (ILOG, Франция-США), Koalog Constraint Solver, Koalog Configurator (Koalog SARL, Франция), MINERVA (IF Computer Japan Ltd., Япония) и др., новыми являются следующие возможности:

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

• визуализация двухмерных и трёхмерных массивов Н-переменных;

• интерактивное отображение функций от одного аргумента и отображение функций от двух аргументов.

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

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

Новизна данного подхода заключается в том, что впервые предложен метод структурирования Н-моделей для широкого круга предметных областей. Метод структурирования, реализованный в настоящее время в системе календарного планирования Time-Ex, ориентирован исключительно на эту проблемную область. КСМ позволяют обеспечить возможность представления структуры объектов моделирования, повысить наглядность представления Н-моделей с большим количеством ограничений и переменных. Благодаря кластерной

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

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

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

Алгоритм определения оттенка цвета, отображающего некоторое числовое значение, (рис. 5) является одним из основных при визуализации двухмерных массивов. Алгоритм имеет следующие входные данные: Утт - наименьшее отображаемое значение; Утах - наибольшее отображаемое значение; 1тш - нижняя граница числового интервала, отображаемого с повышенной контрастностью; 1тах - верхняя граница числового интервала, отображаемого с повышенной контрастностью; х - значение, для которого нужно определить цвет; С -число градаций цвета, доступных для отображения значений в положительной или отрицательной области. Выходными данными алгоритма являются значение градации цвета ЬиАе[0, С], соответствующей х, и значения составляющих цвета в ЛОВ-представлении. В зависимости от значений входных данных, возможны восемь вариантов вычисления составляющих цвета.

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

Также в данном разделе приводится описание структур данных, предназначенных для хранения в памяти системы информации об отображаемых элементах Н-моделей. Разработанные структуры данных обеспечивают следующие основные возможности:

• представление в памяти системы одномерных и двухмерных массивов Н-переменных, в том числе массивов значений отображаемых функций;

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

• хранение в памяти системы всех ограничений на значения элементов массивов и значения отображаемых функций, введённых путём взаимодействия с графическим отображением;

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

Рис. 5. Общий алгоритм преобразования числового значения в цвет. В четвёртом разделе рассматривается проектирование, программная реализация и внедрение графической подсистемы ¡в для систем Н-вычислений. Данная графическая подсистема, разработанная автором с использованием описанных выше методов и алгоритмов, обеспечивает реализацию следующих основных функций:

• графическое отображение одномерных массивов Н-переменных;

• графическое отображение двухмерных массивов Н-переменных;

• возможность введения и изменения дополнительных ограничений на значения элементов массивов путём взаимодействия с их графическим отображением;

• возможность сравнения значений элементов одномерных массивов, полученных в результате выполнения последовательности шагов вычисления Н-модели;

• графическое отображение функций с недоопределёнными значениями от одной переменной;

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

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

Подсистема включает в себя три основные части (рис. 6): ядро визуализации, программный интерфейс и пользовательский интерфейс. Основной частью графической подсистемы является ядро визуализации, которое выполняет следующие функции:

• представление отображаемых элементов Н-модели в структурах данных подсистемы;

• формирование графического отображения элементов Н-модели;

• обработка команд пользователя по управлению графическим отображением;

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

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

Графическая подсистема ¡в включена в состав интеллектуального решателя ишСа1с, разработанного в РосНИИ искусственного интеллекта (рис. 7).

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

• получение информации об именах и текущих значениях всех переменных Н-модели, связанной с некоторым вычислителем;

• задание начальных приближений для значений переменных Н-модели, связанной с некоторым вычислителем.

Система Н-вычислений

Оболочка

1

Вычислительное ядро

I

СОМ-интерфейс ■ Профаммный интерфейс

Ядро визуализации

Менеджер визуализации

1 I 1

I

Хранилище одномерных массивов

I

Блок визуализации одномерных массивов

Блок визуализации функций от одной переменной

Хранилище двухмерных массивов

Блок визуализации двухмерных массивов

Пользовательский интерфейс

Графическая подсистема Ю

Рис. 6. Структура графической подсистемы Ю.

В связи с этим, в диссертации разработан следующий способ организации взаимодействия подсистемы ¡С с системой 11тСа1с. С каждым экземпляром вычислителя может быть связан свой собственный экземпляр графической подсистемы, который создаётся по команде пользователя, переданной с помощью оболочки системы. Подсистема Ю предоставляет оболочке решателя 11шСа1с СОМ-интерфейс. С помощью метода этого интерфейса оболочка передаёт подсистеме СОМ-интерфейс соответствующего вычислителя и сообщает об успешном завершении вычислений. Используя методы интерфейса вычислителя, подсистема получает информацию об отображаемых массивах Н-переменных и передаёт вычислителю ограничения на значения переменных в виде начальных приближений для их значений.

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

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

Ядро визуализации

h

Графическая подсистема IG

Программный интерфейс

Пользовательский интерфейс

СОМ-интерфейс

Блок построения функциональной сети I

Блок символьных преобразований

Блок автоматического дифференцирования

Вычислитель

Библиотека недоопределённых I типов данных I

Математическая библиотека функций

Блок Н-вычислений

1

Блок обжатия и поиска корней b

Функциональная сеть

Вычислительное ядро решателя UniCalc

Рис. 7. Обобщённая архитектура решателя UniCalc.

Подсистема iG была реализована в инструментальной среде Borland Delphi-7 (Borland Software Corporation). Объём исходного кода составляет 380 Кб. Подсистема реализована в двух вариантах: визуальный компонент Borland Delphi и динамическая библиотека с СОМ-интерфейсом. Объём библиотеки составляет 750 Кб. Подсистема может работать под управлением операционных систем MicroSoft Windows версий 95, 98, Millenium Edition, 2000, ХР.

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

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

Сравнение графических средств различных систем Н-вычислений (UniCalc с подсистемой iG, UniCalc-3, "Интегра", "Экономика") показывает, что графическая подсистема iG предоставляет ряд принципиально новых функциональных возможностей, к числу которых относятся:

• интерактивное графическое отображение двухмерных массивов Н-переменных;

• наглядное отображение массивов Н-переменных, содержащих большое число элементов;

• возможность визуального сравнения Н-значений, имеющих разброс до нескольких порядков.

Кроме того, хотя в системах "Интегра" и "Экономика" было реализовано внесение изменений в Н-модель путём взаимодействия с графическим отображением Н-переменных и сравнение решений, полученных на разных шагах вычислений Н-модели, эти возможности были реализованы применительно к ограниченным наборам задач в узких предметных областях. Подсистема iG ориентирована на применение в составе универсальных систем Н-вычислений и предоставляет такие возможности для решения задач из широкого круга предметных областей.

Рассматривается опыт практического применения методов и алгоритмов визуализации массивов числовых переменных и функциональных зависимостей, заданных в Н-моделях, а также графической подсистемы iG, реализующей эти методы и алгоритмы, для решения практических задач. Графическая подсистема iG с 2001 г. используется в исследованиях и разработках РосНИИ искусственного интеллекта, связанных с развитием метода Н-вычислений и интеллектуального решателя алгебраических задач UniCalc, а также при создании прикладных Н-моделей. Решатель UniCalc и подсистема iG успешно применяются для решения следующих задач:

• экспериментальное исследование метода Н-вычислений и тестирование вычислительного ядра решателя UniCalc;

• задачи в области экономики;

• технические и экономические задачи при проектировании летательных аппаратов.

Подсистема iG в составе решателя UniCalc использовались для решения практических задач в ряде предприятий, в том числе АО «АвтоВАЗ» (Россия), Dassault Systèmes (Франция) и др. Применение решателя UniCalc и подсистемы iG позволило сократить время решения некоторых задач проектирования в 2,5 раза. Кроме того, в ряде случаев решены задачи, которые не решаются другими методами. Результаты диссертации использованы в НИР, выполненных в рамках следующих проектов.

1. Международный проект «Распределённое императивное программирование в ограничениях» в сотрудничестве с Centre for Mathematics and Computer

Science (CWI) (Центр исследований в информатике), финансировавшийся NWO (Нидерландская организация по научным исследованиям). 2. В проекте «Разработка аппарата решения сложных вычислительных задач в условиях неточной и недоопределённой информации на основе методов программирования в ограничениях», поддержанном РФФИ (грант № 03-01-00750).

Также результаты диссертации были использованы в трёх проектах Министерства обороны РФ по Государственному оборонному заказу 2000-2004 гг. В настоящее время предложенные в диссертации методы визуализации и структурирования Н-моделей используются при разработке следующей версии решателя UniCalc и ряда проблемно-ориентированных систем на его основе.

С 2001г. результаты работы использовались в учебном процессе в Московском инженерно-физическом институте на лабораторных работах для поддержки курса «Проектирование систем, основанных на знаниях». Представлены общие выводы по диссертации. В приложения вынесены:

• акт о внедрении результатов диссертационного исследования;

• алгоритмы преобразования числового значения в цвет;

• UML-диаграммы проектирования графической подсистемы iG;

• пример решения задачи с использованием графической подсистемы iG.

Основные результаты работы

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

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

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

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

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

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

7. На основе разработанных методов, алгоритмов и архитектуры программных средств выполнена программная реализация графической подсистемы iG для систем недоопределённых вычислений.

8. Осуществлена интеграция графической подсистемы iG в состав оболочки интеллектуального решателя UniCalc.

9. Результаты работы внедрены в РосНИИ искусственного интеллекта, что подтверждено актом о внедрении, и используются в учебном процессе в Московском инженерно-физическом институте.

Основные публикации по теме диссертации

1. Липатов A.A., Полторацкий A.B. Отображение данных в системах интервальных вычислений // Проблемы управления и моделирования в сложных системах. Труды III Международной конференции. - Самара: Самарский научный центр РАН, 2001. С. 509-514.

2. Нариньяни A.C., Липатов A.A. Визуализация данных в технологиях интервальных расчетов // Информационные технологии. - 2001, № 8. С. 11-16.

3. Lipatov A.A., Poltaratskii A.V. Representation of interval models and interval data in the constraint programming system // Joint Bulletin of the Novosibirsk Computing Center and A.P. Ershov Institute of Informatics Systems. Series: Computer Science, Issue: 16 (2001). - Novosibirsk: NCC Publisher, 2001. P. 129-139.

4. Липатов A.A. Повышение уровня представления недоопределённых моделей в решателе UniCalc // Научная сессия МИФИ-2003. Сб. науч. тр. В 14 томах. Т.З. -М.: МИФИ, 2003. С. 160-161.

5. Липатов A.A. Структурные динамические модели - расширение аппарата Н-моделей // Научная сессия МИФИ-2004. Сб. науч. тр. В 15 томах. Т.З. - М.: МИФИ, 2004. С. 130-131.

6. Липатов A.A., Плавеичук Е. А. Структурирование Н-моделей в проекции на многотабличную версию системы Финплан // 9-я Национальная конференция по искусственному интеллекту с международным участием - КИИ-2004. Труды конференции. В 3-х томах. Т. 3. - М.: Физматлит, 2004. С. 928-936.

Принято к исполнению 03/08/2006 Исполнено 03/08/2006

Заказ № 528 Тираж: 100 экз.

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Варшавское т., 36 (495) 975-78-56 (495) 747-64-70 www.autoreferat.ru

loo G в

ИМ 01 Що\

»

Оглавление автор диссертации — кандидата технических наук Липатов, Алексей Андреевич

ВВЕДЕНИЕ.

1. ПРОБЛЕМЫ ВЗАИМОДЕЙСТВИЯ ПОЛЬЗОВАТЕЛЕЙ С СИСТЕМАМИ НЕДООПРЕДЕЛЁННЫХ ВЫЧИСЛЕНИЙ.

1.1. Анализ современного состояния исследований в области представления и обработки не полностью определённых данных и знаний.

1.2. Недоопределённые модели и метод недоопределённых вычислений.

1.2.1. Программирование в ограничениях.

1.2.2. Недоопределённые модели.

1.3. Области применения метода недоопределённых вычислений.

1.3.1. Существующие системы недоопределённых вычислений и области их применения.

1.3.2. Взаимодействие пользователя с системой недоопределённых вычислений при решении задачи - основные этапы.

1.3.3. Проблемы применения метода недоопределённых вычислений.

1.4. Существующие подходы к решению поставленных проблем.

1.4.1. Визуализация числовых данных.

1.4.2. Графическое отображение недоопределённых моделей в современных системах недоопределённых вычислений.

1.5. Структурное представление недоопределённых моделей в современных системах недоопределённых вычислений.

1.6. Постановка задачи диссертационного исследования.

Выводы.;.

2. МЕТОДЫ ВИЗУАЛИЗАЦИИ И СТРУКТУРНОГО ПРЕДСТАВЛЕНИЯ НЕДООПРЕДЕЛЁННЫХ МОДЕЛЕЙ.

2.1. Теоретические основы недоопределённых моделей и метода недоопределённых вычислений

2.1.1. Модель и ее недоопределённое описание.

2.1.2. Операции над недоопределёнными значениями и функции от недоопределённых переменных.

2.1.3. Недоопределённые расширения.

2.1.4. Модели с недоопределёнными переменными и метод недоопределённых вычислений.

2.2. Методы интерактивного графического представления некоторых элементов недоопределённых моделей.

2.2.1. Требования к графическому отображению элементов недоопределённых моделей в системах недоопределённых вычислений.

2.2.2. Метод визуализации одномерных массивов недоопределённых переменных.

2.2.3. Метод визуализации двухмерных массивов недоопределённых переменных.

2.2.4. Метод визуализации трёхмерных массивов недоопределённых переменных.

2.2.5. Методы визуализации недоопределённых функций.

2.2.6. Особенности предложенных методов.

2.3. Структурные недоопределённые модели.

2.3.1. Кластерные структурные модели.

2.3.2. Пример описания недоопределённой модели в кластерном виде.

2.3.3. Метод частичной автоматизации внесения изменений в кластерные структурные модели в процессе решения задачи.

2.3.4. Особенности предложенного метода.

Выводы.

3. АЛГОРИТМИЧЕСКИЕ ОСНОВЫ ВИЗУАЛИЗАЦИИ НЕДООПРЕДЕЛЁННЫХ ЧИСЛОВЫХ ПЕРЕМЕННЫХ И ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ.

3.1. Алгоритмы визуализации элементов недоопределённой модели.

3.1.1. Работа системы недоопределённых вычислений и её графической подсистемы в режиме диалога с пользователем.

3.1.2. Работа графической подсистемы в режиме интерактивного отображения массива недоопределённых переменных.

3.1.3. Работа графической подсистемы в режиме интерактивного отображения недоопределённой функции.

3.1.4. Визуализация одномерных массивов недоопределённых переменных.

3.1.4.1. Алгоритм построения линейной шкалы значений недоопределённых переменных.

3.1.4.2. Алгоритм масштабирования шкалы значений элементов массива по значению элемента массива.

3.1.5. Визуализация двухмерных массивов недоопределённых переменных.

3.1.6. Получение графической подсистемой информации об отображаемых элементах -недоопределённой модели.

3.2. Структуры данных для визуализации элементов недоопределённых моделей.

3.2.1. Структуры данных для представления одномерных массивов недоопределённых переменных.

3.2.2. Структуры данных для представления двухмерных массивов недоопределённых переменных

3.2.3. Структуры данных для представления недоопределённых функций от одного аргумента.

Выводы.

4. ПРОЕКТИРОВАНИЕ, ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ВНЕДРЕНИЕ ГРАФИЧЕСКОЙ ПОДСИСТЕМЫ ДЛЯ СИСТЕМ НЕДООПРЕДЕЛЁННЫХ ВЫЧИСЛЕНИЙ.

4.1. Графическая подсистема iG.

4.1.1. Функции и архитектура графической подсистемы iG.

4.1.2. Менеджер визуализации.

4.1.3. Хранилище одномерных массивов.И

4.1.4. Хранилище двухмерных массивов.

4.1.5. Блок визуализации одномерных массивов.

4.1.6. Блок визуализации двухмерных массивов.

4.1.7. Блок визуализации функций от одной переменной.

4.1.8. Пользовательский интерфейс графической подсистемы.

4.1.9. Программный интерфейс графической подсистемы iG.

4.2. Графическая подсистема iG в составе интеллектуального решателя UniCalc.

4.3. Примеры использования графической подсистемы iG.

4.3.1. Нахождение глобального минимума функции от двух переменных.

4.3.2. Использование подсистемы iG при решении недоопределённой системы ограничений.

4.4. Сравнение графической подсистемы iG с существующими графическими средствами систем недоопределённых вычислений.

4.5. Тестирование графической подсистемы iG.

4.6. Внедрение и использование результатов диссертации.

4.6.1. Области применения графической подсистемы iG.

4.6.2. Применение графической подсистемы iG для экспериментального исследования метода Н-вычислений и тестирования вычислительного ядра решателя UniCalc.

4.6.3. Применение графической подсистемы iG при решении задач в области экономики.

4.6.4. Применение графической подсистемы iG для решения технических и экономических задач при проектировании летательных аппаратов.

4.6.5. Использование разработанных методов и алгоритмов.

Выводы.

ВЫВОДЫ.

Введение 2006 год, диссертация по информатике, вычислительной технике и управлению, Липатов, Алексей Андреевич

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

Диссертационная работа посвящена решению проблемы интеллектуализации пользовательских интерфейсов в контексте одного из ведущих в последние годы направлений в искусственном интеллекте (ИИ) - методов и систем программирования в ограничениях (Constraint Programming). Сегодня методы программирования в ограничениях широко применяются для решения задач проектирования, планирования, поддержки разработок пользовательских интерфейсов, в электронных таблицах и системах, подобных им, в различных задачах искусственного интеллекта, в качестве расширений универсальных языков программирования и во многих других областях. Программирование в ограничениях является по своей сути максимально декларативным, поскольку основано на описании модели задачи, а не алгоритма ее решения, благодаря чему, методы программирования в ограничениях широко используются для задач с недооп-ределёнными данными. К числу методов программирования в ограничениях, наиболее часто применяемых для решения задач с недоопределёнными данными, относятся метод недоопределённых вычислений, метод толерантного распространения ограничений, метод распространения значений и др.

Значительный вклад в исследование и решение данных проблем внесли отечественные учёные Д.А. Поспелов, Э.В. Попов, А.Н. Мелихов, Э.Х. Тыугу, Г.С. Осипов, А.С. Нариньяни, Г.В. Рыбина, А.П. Еремеев, В.Б. Тарасов, И.Б. Фоминых, А.Н. Аверкин, Н.Г. Ярушкина, В.М. Курейчик, а также целый ряд зарубежных учёных J1. Заде (L. Zadeh), Д. Дюбуа (D. Dubois), А. Прад (А.

Prade), Д. Уолц (D. Waltz), А. Макверс (A. Mackworth), У. Монтанари (U. Mon-tanari), E. Фредер (E. Freuder), E. Хивонен (E. Hyvonen) и др.

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

• недоопределённость значений переменных;

• наличие в модели большого числа переменных и ограничений;

• необходимость вносить изменения в модель в процессе решения задачи, воздействуя таким образом, на её область решения;

• наличие сложной внутренней структуры у моделируемых фрагментов действительности (экономика страны, региона, технический объект, календарный план проекта).

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

• обеспечение визуального представления недоопределённых значений переменных модели;

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

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

• обеспечение графического отображения процесса решения задач и управления им.

В современных коммерческих системах программирования в ограничениях таких как, UniCalc, "Интегра", Time-Ex (Российский НИИ искусственного интеллекта), ILOG CP, ILOG OPL Development Studio (ILOG, Франция-США), Koalog Constraint Solver, Koalog Configurator (Koalog SARL, Франция), MINERVA (IF Computer Japan Ltd., Япония) и др., эти проблемы решены не полностью.

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

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

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

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

2. Разработка методов интерактивного графического представления массивов числовых переменных и функциональных зависимостей, заданных в недоопределённых моделях.

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

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

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

6. Разработка архитектуры графической подсистемы для систем недоопреде-лённых вычислений.

7. Разработка и программная реализация графической подсистемы для систем недоопределённых вычислений

8. Интеграция графической подсистемы в состав оболочки интеллектуального решателя UniCalc.

9. Использование графической подсистемы для решения задач в рамках решателя UniCalc.