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

Недоопределенные модели Нариньяни: становление, применение, проблемы и перспективы

Аннотация

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

I. Введение

Недоопределенные модели (Н-модели), а затем и метод недоопределенных вычислений (МНВ) были предложены А.С. Нариньчни в начале 80-x годов для представления и обработки не полностью определенных знаний [1–3]. Рассматриваемый вначале как оригинальный подход в области искусственного интеллекта, МНВ трансформировался постепенно в прикладную технологию, которую принято относить к направлению «программирование в ограничениях» (constraint programming), активно развиваемому в мире как одно из наиболее перспективных направлений в области информационных технологий. Практика показала, что технология Н-моделей выделяется среди других подходов вычислительной мощностью, универсальностью и эффективностью. Фактически она является единственной технологией, которая позволяет решать задачу удовлетворения ограничений в самой общей постановке [4]. 

Под руководством А.С. Нариньяни на базе Н-моделей была создана многоуровневая технология программирования, позволяющая решать качественно новые классы задач в таких областях как экономика и финансы, инженерные расчеты, календарное планирование, вычислительная математика, САПР, ГИС и др. На основе аппарата Н-моделей были реализованы такие прикладные системы и инструментальные комплексы как UniCalc [5–7], NeMo+[8], Time-Ex [9], ФинПлан [10], и др., которые широко использовались для решения практических задач. 

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

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

II. О методе недоопределенных вычислений

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

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

Рис. 1. Схема метода недоопределенных вычислений. SoRuCom-2020

Рис. 1. Схема метода недоопределенных вычислений

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

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

III. Решатель UniCalc и программный комплекс NeMo +

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

Первая макетная реализация решателя была выполнена в 1987 году в операционной среде Unix, а в 1991 году появилась версия решателя UniCalc для MS DOS, что сделало возможным его использование на массовых персональных компьютерах IBM PC и совместимых с ними. Хотя эта версия решателя имела ограничения на размер обрабатываемой модели (из-за ограниченного размера оперативной памяти), но, тем не менее, решатель привлек внимание пользователей своей простотой и эффективностью и был приобретен рядом промышленных предприятий и конструкторских бюро для выполнения проектных работ и инженерных расчетов.

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

В 1995 г. версия UniCalc/DOS прошла тестирование в фирме SAIC (США) и было высоко оценена специалистами.  

В 1996 году появились версии UniCalc для популярных операционных систем Windows 95 и Windows NT, что предопределило возможность его широкого использования.  

В этом же году UniCalc экспонировался на крупнейшей международной компьютерной выставке CeBIT в Германии и ряде российских выставок. 

Следует озаметить, что UniCalc нашел применение во многих научных, учебных, промышленных и конструкторских организациях и предприятиях в России и за рубежом. Среди них такие известные предприятия, как АвтоВАЗ, Новосибирский завод химконцентратов, авиазавод им. Бериева (г. Таганрог), ОАО «Камов» (Россия), Dassault Aviation и Dassault Systemes (Франция).  

Развитием решателя UniCalc стала объектно-ориентированная среда NeMo+ [3],предназначенная для моделирования предметных областей и решения задач с произвольными недоопределёнными типами данных. Она обеспечивает максимальное использование возможностей аппарата недоопределённых моделей: если UniCalc позволяет решать задачи только с числовыми параметрами, то в NeMo+ реализуются широкий набор различных типов данных (множества, символьные и логические параметры и др.) и развитые механизмы управления, позволяющие решать сложные комбинаторные задачи.

Во второй половине 1990-х годов системы UniCalc и NeMo+ были приобретены французской компанией Dassault Systèmes. На основе технологического комплекса NeMo+ по заказу Dassault Systèmes был реализован решатель задач программирования в ограничениях NemoNext, который успешно использовался в модуле управлениями знаниями САПР CATIA V5 и CATIA V6.  

IV. Применение Н-моделей для решения финансово-экономических задач

А.С. Нариньяни уделял большое внимание применению разработанных при его непосредственном участии Н-технологий для решения практических задач. Если вначале в качестве таких задач выступали задачи из области проектирования технических систем, то потом фокус постепенно сместился на финансово-экономические задачи. Первое время такие задачи решались с помощью универсального решателя UniCalc, а затем была разработана специализированная система ФинПлан – система электронных таблиц, поддерживающая работу с интервальными значениями, своего рода Excel со встроенным в него UniCalc’ом. Позже ФинПлан перерос в технологию INTEGRA.NM[11]. 

Модель задачи, решаемой средствами INTEGRA.NM, ее параметры и связывающие их ограничения, хранятся в ячейках таблицы. Однако, в отличие от известных электронных таблиц (например, Excel), в ячейках таблицы INTEGRA.NM может содержаться не только точная, но и частично известная информация, заданная в виде интервалов допустимых значений соответствующих параметров (рис. 2). В результате вычислений или при поступлении дополнительной информации извне эти интервалы автоматически сужаются.

Рис.2. Табличный интерфейс INTEGRA.NM. SoRuCom-2020

Рис.2. Табличный интерфейс INTEGRA.NM

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

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

Средства графического представления технологии INTEGRA.NM адаптированы для работы с интервальными данными. Пользователь имеет возможность создавать так называемые активные экраны (АЭ). АЭ состоит из фрагмента таблицы, содержащего наиболее важные анализируемые параметры, и диаграмм, на которых эти параметры представлены более наглядно и с учетом динамики их изменения. Каждый экран снабжается полем с комментариями. В процессе решения задачи лицо, принимающее решения (ЛПР) может вносить данные в таблицу, пересчитывать значения параметров. Благодаря «горячей» связи между таблицей и диаграммами, все изменения автоматически отображаются на диаграммах (рис. 3).

Рис.3. Активный экран. SoRuCom-2020

Рис.3. Активный экран

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

На базе технологии INTEGRA решалось множество финансово-экономических задач. В частности, эта технология была успешно опробована в рамках нескольких проектов Минобороны РФ, при разработке моделей промышленности Москвы, Томской и Ивановской областей, а также экспериментальных моделей экономики Республик Казахстан и Болгария.

V. Проблемы широкого применения Н-моделей и пути их решения

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

Даже несмотря на успешное применение системы ФинПлан в самых разных областях, оно все же было не таким широким, какого эта система заслуживала. Основная причина – это объективная и субъективная неготовность пользователя использовать новые технологии. Александр Семенович, наверное, не зря категорически отказывался широко и бесконтрольно продавать ФинПлан как оболочку, дабы не дискредитировать идею, предпочитая создавать готовые системы (модели конкретных предметных областей) и именно их передавать пользователю. Он неоднократно говорил, что мы – «высококлассное ателье», а не «магазин готового платья». Человек без специальной подготовки не сможет составить модель так, чтобы она хорошо и эффективно считалась. А субъективную неготовность пользователей породили, как это ни парадоксально, простота и наглядность получаемых системой результатов. Руководители среднего звена одного предприятия, на котором предполагалось внедрить эту систему, после получения первых результатов стали откровенно саботировать внедрение – уж слишком прозрачно выглядели эти результаты.

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

Рис. 4. Представление метода недоопределенных вычислений в ИАИР ППР. SoRuCom-2020

Рис. 4. Представление метода недоопределенных вычислений в ИАИР ППР

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

В ИСИ СО РАН разработаны средства комплексной поддержки создания интеллектуальных СППР – построены онтология области знаний «Поддержка принятия решений» (ППР), базирующийся на этой онтологии информационно-аналитический ресурс (ИАИР) и репозиторий методов ППР. Онтология ППР включает фрагмент, описывающий метод Н-вычислений и связанные с ним понятия (рис. 1). Сам метод и реализующие его программные средства, встроены в репозиторий методов ППР. А ИАИР ППР [12]предоставляет широкий свободный доступ к онтологии, к конкретным объектам, связанным с методом Н-вычислений, к программным реализациям этого метода и программным системам, базирующимся на нем. 

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

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

В последнее время снова вырос интерес к Н-моделям. Они применяются не только в системах поддержки принятия решений [13], но и в робототехнике [14], в частности при решении задачи рекогносцировки мобильных роботов [15], для распознавания сцен [16] и групп подвижных объектов [17]. 

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

Источник финансирования. Благодарности

Работа выполнена при финансовой поддержке РФФИ (грант № 19-07-00762).

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

  1. Нариньяни А.С. Недоопределенные множества – новый тип данных для представления знаний. Препринт 232. Проект ВОСТОК. Вып.4. – Новосибирск: ВЦ СО РАН, 1980. 

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

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

  4. Нариньяни А. С. Введение в недоопределенность // Информационные технологии; прил. 4. – М: Новыетехнологии, 2007. – 32 с. 

  5. Babichev A.B., Kadyrova O.B., Kashevarova T.P., Leshchenko A.S. and Semenov A.L. UniCalc, A Novel Approach to Solving Systems of Algebraic Equations // Interval Computations, N2, 1993, pp. 29–47. 

  6. A.S. Narin'yani, A.L. Semenov, A.B. Babichev, T.P. Kashevarova and A.S. Leshchenko. A New Approach to Solving Algebraic Systems by Means of Sub-Definite Models // Proceedings of the 16-th IFIP Conference on System Modelling and Optimization. Compiegne, France. July, 1993. J.Henry and J.-P. Yvon (Eds.), Lecture Notes in Control and Information Sciences. v. 197, Springer Verlag, 1994. 

  7. Костов Ю.В., Липовой Д.А., Мамонтов П.Г., Петров Е.С. Новый UNICALC: версия 5 – возможности и перспективы // Труды 9-й национальной конференции по искусственному интеллекту – КИИ-2004. Тверь, 2004. – с. 915–922. 

  8. Загорулько Г. Б., Сидоров В. А., Телерман В. В., Ушаков Д. М. NeMo+: Объектно-ориентированная система программирования в ограничениях на основе недоопределенных моделей // Труды 6-й национальной конференции по искусственному интеллекту – КИИ’98. Пущино, 1998. – с.524–530. 

  9. Нариньяни А.С., Гофман И.Д., Инишев Д.А., Банасюкевич Д.В. Развитие интеллектуальной технологии недоопределенного планирования и управления проектами Time-EX // Труды 7-й национальной конференции по искусственному интеллекту КИИ-2000 (23-26 октября 2000 г.), Переславль-Залесский, – с.617–624. 

  10. Нариньяни А.С., Корниенко В.В., Прейс С.В., Швецов И.Е. ФинПлан: новая технология финансово-экономического планирования в условиях неполноты информации // Информационные технологии. № 11, М.: Издательство «Машиностроение»,1998. – с. 10–16. 

  11. Нариньяни А.С., Загорулько Г.Б. Интеллектуальные таблицы: новые возможности в решении сложных задач // Материалы Международной научно-практической конференции "Информационные технологии, информационные измерительные системы и приборы в исследовании сельскохозяйственных процессов". Ч.1. – РАСХН Сиб. отд-ние. – Новосибирск, 2003. – с. 240–242. 

  12. Загорулько Ю.А., Загорулько Г.Б., Шестаков В.К. Подход к разработке информационно-аналитического интернет-ресурса по поддержке принятия решений//ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И СИСТЕМЫ: труды Шестой Международной научной конференции. Научное электронное издание, 2017. – с. 113–116. 

  13. Загорулько Г.Б., Массель Л.В. Разработка интеллектуальной СППР по предотвращению угроз энергетической безопасности// Вестник СибГУТИ, 2019. № 3. – c. 70–79. 

  14. Карпов В.Э. О некоторых особенностях применения недоопределенных моделей в робототехнике. //V-я Международная научно-практическая конференция "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (28-30 мая 2009). Сб. научных трудов в 2-х т., М: Физматлит, 2009. Т.1. – с.520–532 

  15. Ольшанский Д.Л. О применимости недопределенных моделей к задаче рекогносцировки мобильных роботов // VI-я Международная научно-практическая конференция "Интегрированные модели и мягкие вычисления в искусственном интеллекте", Коломна, 16-19 мая 2011 г. 

  16. Московский А.Д. Метод распознавания сцен на основе недоопределенных моделей // Шестнадцатая Национальная конференция по искусственному интеллекту с международным участием (КИИ-2018). Труды конференции: в 2-х томах. 2018. Т.2. – с. 27–34. 

  17. Липатов А.А., Ушаков В.Н. Методы формального представления и обработки неопределенных количественных и качественных данных для выявления групп объектов //Мягкие измерения и вычисления, 2018. № 3 (4). – с. 16–24.

Об авторе: Институт систем информатики им. А.П. Ершова СО РАН, Новосибирск, Россия;
zagor@iis.nsk.sugal@iis.nsk.su

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