Русский English
V международная конференция
«РАЗВИТИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ В РОССИИ, СТРАНАХ БЫВШЕГО СССР И СЭВ»
Россия, Москва, НИУ ВШЭ, 6–8 октября 2020 года
Предоставление докладов на английском языке
Интерактивная компьютерная графика в приложениях недоопределённых моделей

Интерактивная компьютерная графика в приложениях недоопределённых моделей

Аннотация

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

Ключевые слова – интеллектуальная система, недоопределённая модель, интерактивная компьютерная графика, пользовательский интерфейс.

I. Введение

Одним из ведущих центров исследований и прикладных разработок в области искусственного интеллекта в СССР и России с 1970-х гг. является Вычислительный центр Сибирского отделения Академии наук СССР, ныне Институт систем информатики им. А.П. Ершова Сибирского отделения РАН. В 1977 г. там была создана лаборатория искусственного интеллекта под руководством известного советского и российского учёногоАлександра Семёновича Нариньяни, внесшего значительный вклад в становление и развитие этого научного направления. А.С. Нариньяни – действительный член РАЕН, один из основателей и активных участников Советской, а затем Российской ассоциации искусственного интеллекта, член Научного Совета по методологии искусственного интеллекта РАН. Им были получены значительные научные результаты в таких областях, как проблема взаимодействия человека с ЭВМ на естественном языке, создание инструментальных средств разработки интеллектуальных систем, представление и обработка знаний, включая постановку и исследование проблемы НЕ-факторов знаний и создание математического аппарата для их представления и обработки.

Сформулированное им понятие НЕ-факторов [1, 2] и разработанная концепция недоопределённости [1, 3, 4] заложили основу нового направления в области создания теоретических моделей представления и обработки знаний и их практической реализации.

Весьма плодотворной оказалась идея А.С. Нариньяни о том, что формальная модель объекта, представляющая собой совокупность переменных и связывающих их отношений, может рассматриваться как основа перспективных информационных технологий. Ранее такой основой общепризнанно считался алгоритм. Эта идея была высказана А.С. Нариньяни в работе «Модель или алгоритм: новая парадигма информационной технологии» [5]. В работе было проведено сопоставление модели и традиционного (императивного) алгоритма, выделяющее пять их существенных различий, приведённых в Табл. 1.

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

В свою очередь, объединение концепций модели и недоопределённости позволило А.С. Нариньяни создать математический аппарат недоопределённых моделей (Н-моделей). Развитие, реализация и практическое применение Н-моделей стали одним из основных направлений работы лаборатории искусственного интеллекта ИСИ им. А.П. Ершова СО РАН, Российского НИИ искусственного интеллекта и ЗАО «ИнтеллиТек».

Таблица 1

Основные свойства модели и алгоритма [5]

Модель

Алгоритм

а. Принципиально декларативна

а. В определенном смысле, антидекларативен

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

b. Разделяет параметры на входные и выходные, явным образом определяя вторые через первые

c. В неявной форме определяет решение всех задач, связанных с объектом моделирования

c. Определяет в явной форме решение только одной задачи, отношение которой к реальному объекту не всегда очевидно (см. ниже)

d. Может быть недоопределённой

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

е. В общем случае определяет все пространство решений

е. Традиционный (неинтервальный) алгоритм позволяет получать только отдельные – часто далеко не лучшие – точечные решения

Эти работы во многом основывались на научно-техническом заделе, созданном лабораторией Искусственного интеллекта ВЦ СО АН СССР при выполнении в 1985-1988 гг. проекта создания ЭВМ нового поколения СТАРТ [6]. Среди результатов этого проекта следует отметить ряд инструментальных программных средств:

  • ГАММА-СЕТЛ – система программирования сверхвысокого уровня;

  • ТИГРИС – инструментарий пользовательских интерфейсов;

  • ИНФО-ТЕК – настраиваемая на пользователя информационная система;

  • ЛИНГВА. Ф – фабрика интерфейсов на естественных языках;

  • UNICALC – решатель алгебраических проблем на основе Н-моделей.

В 1990-2000-х гг. в Российском НИИ искусственного интеллекта и ЗАО «ИнтеллиТек» под руководством А.С. Нариньяни был создан целый ряд прикладных систем, использующих метод Н-моделей [1]. Для применения данных систем в таких областях, как планирование и управление, финансы, инженерные расчёты и др. [7-9] потребовались развитые средства пользовательского интерфейса и, в частности, средства интерактивной компьютерной графики (ИКГ), обеспечивающие работу пользователей с Н-моделями. Специфические требования к таким средствам ИКГ были обусловлены принципиальными особенностями метода Н-моделей.

Целью статьи является краткий обзор истории развития программных средств ИКГ для систем Н-моделей, разработанных под руководством и на основе идей А.С. Нариньяни.

II. Процесс решения задачи с помощью Н-модели

Н-модель представляет собой описание некоторого объекта в виде системы алгебраических уравнений, неравенств, а также логических выражений, накладывающих ограничения на значения его параметров. Задача моделирования заключается в том, чтобы найти области значений параметров или их точные значения, удовлетворяющие заданной системе ограничений [7-10]. Следует отметить, что задачи в такой общей постановке решаются методами программирования в ограничениях или constraint programming – направления прикладной математики, активно развивающегося в мире [11, 12]. В рамках этого направлении разработаны многочисленные алгоритмы удовлетворения ограничений. Однако аппарат Н-моделей обладает рядом уникальных особенностей, выделяющих его среди аналогов. Среди таких особенностей можно отметить следующие [13].

  1. В Н-модели оценки значений переменных представлены в виде множеств, содержащих их истинные значения.

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

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

  4. Система ограничений может содержать одновременно линейные и нелинейные ограничения, а также логические условия.

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

Возможность решения задачи в такой постановке обеспечивается алгоритмом недоопределённых вычислений [1]. Алгоритм обеспечивает нахождение многомерного параллелепипеда, в котором гарантированно лежат все решения системы ограничений. Если заданная система не имеет действительных решений, то выдаётся сообщение о её несовместности.

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

Материалы конференции SoRuCom-2020. Рис. 1. Общая схема решения задачи с помощью Н-модели Рис. 1. Общая схема решения задачи с помощью Н-модели

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

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

  • изменение ограничений модели в процессе поиска решения;

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

Таким образом, средства ИКГ в системах, использующих Н-модели, должны выполнять не только иллюстративную, но и когнитивную функцию [14], то есть помогать находить путь решения задачи и предоставлять возможности корректировки Н-модели. Кроме того, задачиИКГ осложняются недоопределённостью данных, представляемых в большинстве приложений числовыми интервалами, и большой размерностью прикладных проблем.

III. Графические средства в системах, основанных на Н-моделях

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

  • «UniCalc» – интеллектуальный решатель алгебро-дифференциальных задач;

  • «Nemo+» – решатель логико-алгебраических задач;

  • «Time-EX» – система гибкого календарного планирования и управления проектами на основе Н-моделей и временной логики;

  • «FinPlan» – специализированная программная технология, обеспечивающая решение широкого класса финансовых и экономических в условиях неполноты и неточности исходных данных;

  • «Экономика» – специализированная версия «FinPlan» для разработки макроэкономических моделей уровня и бюджета страны, региона;

  • «INTEGRA.NM» – развитие технологии «FinPlan» на базе обновлённого решателя «UniCalc»;

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

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

В первом варианте решатель «UniCalc» версии 3, применявшейся наиболее широко [15, 16], включал в себя графическую подсистему, обеспечивающую отображение графиков функций от одной переменной, заданных пользователем в Н-модели. Подсистема предоставляла следующие основные возможности:

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

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

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

В ходе работы над созданием последующих версий системы «UniCalc» были разработаны несколько экспериментальных графических подсистем, к числу которых относятся графическая подсистема «iG» [10, 17], графическая подсистема на базе активных графических объектов (АГО) [18] и графический модуль, реализующий корректную визуализацию области решений Н-модели[19].

Подсистема «iG» реализует следующие основные функции [10, 17]:

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

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

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

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

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

Кроме того, можно отметить следующие особенности подсистемы:

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

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

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

Материалы конференции SoRuCom-2020. Рис. 2. Одномерный массив недоопределённых переменных со значениями, полученными на трёх шагах решения задачи Рис. 2. Одномерный массив недоопределённых переменных со значениями, полученными на трёх шагах решения задачи

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

Материалы конференции SoRuCom-2020.  Рис. 3. Отображение двухмерного массива Н-переменных с настраиваемой шкалой цветов. Рис. 3. Отображение двухмерного массива Н-переменных с настраиваемой шкалой цветов.

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

Материалы конференции SoRuCom-2020.  Рис. 4. График функции от одной переменной с Н-значениями при различных дополнительных ограничениях. Рис. 4. График функции от одной переменной с Н-значениями при различных дополнительных ограничениях.

Была осуществлена интеграция подсистемы «iG» с решателем «UniCalc®» версии 3 и проведён ряд экспериментов по её применению.

Новым направлением в развитии графических средств для систем, использующих Н-модели, стало использование технологии активных объектов (ТАО) [20]. На этой основе был разработан подход, в соответствии с которым графическое отображение данных строится системой взаимодействующих активных объектов специального вида – активных графических объектов (АГО) [18]. При этом различные классы АГО соответствует различным элементам отображаемой информации (например, переменной, заданию календарного плана, координатному пространству и т.п.). АГО характеризуется следующими основными свойствами:

  • имеет набор слотов (параметров), значения которых в некоторый момент времени называются его состоянием;

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

  • может взаимодействовать с другими АГО, программами, пользователем.

Концепция АГО реализована в экспериментальной графической подсистеме для решателя «UniCalc», обеспечивающей визуализацию недоопределённых функций от одной и двух переменных в виде двухмерных и трёхмерных интерактивных графических образов функций.

Другой важной проблемой, связанной с графическими средствами систем, использующих Н-модели, является корректная визуализация области решений [19]. Задача корректной визуализации возникает в связи с тем, что область решений Н-модели может представлять собой тело сложной формы в многомерном пространстве. Однако в существующих системах результат вычислений представляется в виде многомерного параллелепипеда, содержащего как область решений, так и точки, не являющиеся решениями. Таким образом, корректная визуализация должна обеспечить приближение графического отображения области решений к её реальной форме.

Данная задача решается в работе [19] с помощью так называемых покрытий области решений. Покрытие строится путём последовательного нахождения фрагментов области решений Н-модели, соответствующих ограниченным интервалам значений переменных. Чем уже интервалы, тем с большей точностью построенное множество многомерных параллелепипедов приближается к истинной форме области решений.

В работе [19] предложены алгоритмы построения покрытий и визуализации двухмерных и трёхмерных областей решений. Данные алгоритмы были реализованы в графическом модуле для решателя «UniCalc».

Особенность средств ИКГ для проблемно-ориентированных систем, заключается в том, что используемые графические образы должны соответствовать объектам конкретной проблемной области и отображать их недоопределённость и поведение. Рассмотрим подходы к решению этих задач на примере систем «FinPlan», «INTEGRA.NM» и «Time-EX».

Система электронных таблиц «INTEGRA.NM» (до начала 2000-х гг. выпускалась под названием «FinPlan») [8] с успехом применялась для решения задач финансово-экономического анализа, планирования, аудита инвестиционных проектов и др. Система имеет развитые средства визуализации недоопределённых данных, которые представлены комплексом объёмных и плоских линейчатых и столбчатых диаграмм.

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

Система календарно-ресурсного планирования и управления проектами «Time-EX» [9] предназначена для построения и мониторинга выполнения календарных планов проектов с учётом ресурсных ограничений. Задания проекта могут иметь недоопределённые даты начала и окончания и недоопределённую длительность.

В системе «Time-EX» реализован комплекс интерактивных графических и табличных представлений, обеспечивающих создание и редактирование основных элементов плана проекта – подпланов, заданий, видов ресурсов, а также отображение построенного плана. В частности, для представления плана проекта используются следующие виды графических отображений:

  • сетевая диаграмма проекта;

  • диаграмма Гантта;

  • гистограмма загрузки ресурсов проекта.

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

IV. Выводы и заключение

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

  • Министерство обороны РФ;

  • Счётная палата РФ;

  • Росинформтехнологии;

  • ФГУП ЦНИИ Атоминформ;

  • АО «АвтоВАЗ»;

  • Dassault Systemes (Франция);

  • высшие учебные заведения (МГТУ им. Н.Э. Баумана, МИФИ, Новосибирский государственный университет и др.).

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

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

  1. Нариньяни А.С. Недоопределенность в системах представления и обработки знаний // Изв. АН СССР. Техн. кибернетика, 1986. № 5. – С. 3 – 28.

  2. Нариньяни А.С. НЕ-факторы и инженерия знаний: от наивной формализации к естественной прагматике // Труды IV Национальной конференции «Искусственный Интеллект'94».v.1, Рыбинск 1994.

  3. Нариньяни А.С. Недоопределенные множества – новый тип данных для представления Знаний. // Препр. ВЦ СОАН СССР № 232, 1980.

  4. Нариньяни А.С. Недоопределенные модели и операции с недоопределенными значениями. – Препринт ВЦ СО АН СССР, N 400, 1982.

  5. Нариньяни А.С. Модель или алгоритм: новая парадигма информационной технологии. // Информационные технологии, № 4, М., 1997. С. 11 – 16.

  6. Загорулько Ю.А., Кононенко И.С., Котов В.Е., Левин Д.Я., Телерман В.В., Черемных Н.А. Александр Семенович Нариньяни. Виртуальный компьютерный музей. 2010. Электронный ресурс.https://computer-museum.ru/galglory/nariniani.htm#endnote4 Дата обращения 10.07.2020

  7. Кашеварова Т.П. Использование системы UniCalc для решения задач математического моделирования. – Новосибирск, 1999. – 34 с. – (Препр. / РАН. ИСИ; № 64).

  8. Напреенко В.Г. Применение технологии Н-моделей к задачам экономики и финансов / Информационные технологии. – 2008, № 6. Приложение.

  9. Нариньяни А.С., Гофман И.Д., Липатов А.А., Инишев Д.А. Интеллектуальная технология недоопределённого календарно-ресурсного планирования и управления проектами Time-Ex® / Информационные технологии. 2010, № 2. Приложение. 32 с.

  10. Липатов А.А. Методы и программные средства интеллектуализации пользовательского интерфейса в приложении к системам недоопределённых вычислений // Искусственный интеллект и принятие решений. – 2008, №3. С. 16-27.

  11. Handbook of Constraint Programming. Edited by F. Rossi, P. van Beek and T. Walsh. 2006. Elsevier.

  12. Щербина О.А. Удовлетворение ограничений и программирование в ограничениях. Препринт. 2012. Электронный ресурс.http://soa7.socionet.ru/files/shcherbina_csp_review.pdfДата обращения 10.07.2020

  13. Нариньяни А.С. Введение в недоопределенность // Приложение к журналу «Информационные технологии». 2007, №4.

  14. Зенкин А.А. Когнитивная компьютерная графика / Под ред. Д.А. Поспелова – М.: Наука, 1991. – 192 с

  15. Babichev A.B., Kadyrova O.B., Kashevarova T.P., Leshchenko A.S., Semenov A.L. UniCalc, A Novel Approach to Solving Systems of Algebraic Equations // Numerical Analysis with Automatic Result Verifications: Proc. / Intern. Conf., Lafayette, Louisiana, USA, February-March, 1993. – Interval Computations. – 1993. – No. 2. – P. 29-47.

  16. Semenov A.L., Leshchenko A.S. Interval and Symbolic Computations in the UniCalc Solver // Inter. Conf. on Interval and Computer-Algebraic Methods in Science and Engineering (INTERVAL-94): Abstracts. St-Petersburg, Russia, 1994. – P. 206 – 208.

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

  18. Шурбаков А.В., Липатов А.А. Активные графические объекты – новый подход к созданию систем визуализации моделей // Научная сессия МИФИ-2005. Сб. науч. тр. В 15 томах. Т.3. – М.: МИФИ, 2005. С. 174-175.

  19. Ботоева Е.Ю. Двух- и трехмерная визуализации множества решений в системе UniCalc // Молодая информатика. Вып. 2. Сб. тр. аспирантов и молодых ученых. Под ред. к.ф.-м.н. И. С. Ануреева. Институт систем информатики имени А. П. Ершова СО РАН, 2006 С. 48-59.Электронный ресурс.https://www.iis.nsk.su/files/articles/young_informatics_2.pdfДата обращения 10.07.2020

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

Об авторе: Алексей Андреевич Липатов АО «Концерн «Вега», Москва, Россия, alexey.lipatov75@mail.ru

Материалы международной конференции Sorucom 2020
автора 22.02.2022