НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИІНСТИТУТ ПРОБЛЕМ МАШИНОБУДУВАННЯ ІМ. А.М. ПІДГОРНОГОЦИКЛ РОБІТ “МАТЕМАТИЧНІ МЕТОДИ ОПТИМІЗАЦІЇ ТА ІНТЕЛЕКТУАЛЬНІ КОМП’ЮТЕРІ ТЕХНОЛОГІЇ МОДЕЛЮВАННЯ СКЛАДНИХ ПРОЦЕСІВ І СИСТЕМ З УРАХУВАННЯМ ПРОСТОРОВИХ ФОРМ ОБ’ЄКТІВ”РЕФЕРАТ ГРИЦИК Володимир Володимирович – член-кореспондент НАН України, Заслужений діяч науки i техніки України, доктор технічних наук, професор, завідувач відділу Державного науково-дослідного інституту інформаційної інфраструктури НАН та Державного департаменту з питань зв’язку та інформатизації України ^ ШЕВЧЕНКОАнатолій Іванович – член-кореспондент НАН України, Заслужений діяч науки i техніки України, доктор технічних наук, професор, ректор Державного університету інформатики і штучного інтелекту МОН України ^ КIСЕЛЬОВАОлена Михайлівна – Заслужений діяч науки і техніки України, доктор фізико-математичних наук, професор, декан Дніпропетровського національного університету імені Олеся Гончара МОН України ^ ЯКОВЛЕВСергій Всеволодович – Заслужений діяч науки i техніки України, доктор фізико-математичних наук, професор, завідувач кафедри Харківського інституту управління ^ БІДЮКПетро Іванович – доктор технічних наук, професор, професор кафедри Інституту прикладного системного аналізу Національного технічного університету України "Київський політехнічний інститут" МОН України і НАН України ^ ГІЛЬМикола Іванович – доктор технічних наук, старший науковий співробітник, провідний науковий співробітник Інституту проблем машинобудування імені А.М. Підгорного НАН України ^ КРАКЮрій Васильович – доктор фізико-математичних наук, професор, професор кафедри Київського національного університету імені Тараса Шевченка ^ КУЛЯСАнатолій Іванович – кандидат технічних наук, старший науковий співробітник, учений секретар Інституту кібернетики імені В.М.Глушкова НАН України ^ РОМАНОВАТетяна Євгеніївна – доктор технічних наук, професор, старший науковий співробітник Інституту проблем машинобудування імені А.М. Підгорного НАН України ^ СТЕЦЮКПетро Іванович – кандидат фізико-математичних, в.о. завідувача відділу Інституту кібернетики імені В.М.Глушкова НАН України Цикл робіт охоплює період досліджень за останні 40 років та об'єднує 27 монографій і 250 наукових статей (з них 110 статей у міжнародних журналах, що містяться в базі даних SCOPUS з індексом h=3 їх цитування) в області обчислювальної математики, інформатики, штучного інтелекту, теорії управління та автоматизованого проектування, які виконані в Інституті проблем машинобудування імені А. М. Підгорного НАН України, Інституті кібернетики імені В. М. Глушкова НАН України, Державному науково-дослідному інституті інформаційної інфраструктури (м. Львів), Київському національному університеті імені Тараса Шевченка, Національному технічному університеті України “Київський політехнічний інститут”, Харківському інституті управління, Державному університеті інформатики і штучного інтелекту (м. Донецьк), Дніпропетровському національному університеті імені Олеся Гончара. Мета дослідження полягає у розробці потужного інструментарію комп’ютерного та математичного моделювання, конструктивних методів оптимізації, створенні та впровадженні високоінтелектуальних інформаційних технологій дослідження складних процесів і систем різноманітної природи з урахуванням просторової форми об'єктів. У результаті спільної творчої та взаємодоповнюючої діяльності сформувався колектив вчених, що представляє, як географічно так і за напрямками фундаментальних досліджень, потужні наукові центри України, які відомі своїми результатами світового рівня. Кожний з авторів творчого колективу є засновником або входить до числа найбільш відомих представників наукових шкіл Львова, Дніпропетровська, Донецька, Києва, Харкова, що проводять дослідження в напрямку математичного моделювання, теорії оптимізації, комп’ютерних інформаційних технологій та штучного інтелекту. Оригінальні фундаментальні наукові досягнення склали суттєвий внесок у розв’язання найважливіших прикладних проблем створення нових засобів обчислювальної техніки та програмного забезпечення приладів і систем різного призначення, маніпуляційних систем та робототехніки, систем керування об’єктами просторових конструкцій, геометричного проектування, розпізнавання образів, аналізу й синтезу аудіо і відео інформації, паралельної обробки інформації в режимі реального часу, інформаційних систем моделювання інтелектуальної діяльності людини та інтелектуальних робототехнічних систем на базі телекомунікаційних і інформаційно-вимірювальних засобів. Цикл робіт об’єднаний єдиною методологією дослідження, включаючи моделювання реальних просторових об’єктів, формалізацію їх взаємовідношень, дослідження класів базових задач розміщення, покриття і розбиття, оптимізації структури та параметрів складних процесів і систем з об'єктами довільної просторової форми, створення новітніх високоінтелектуальних інформаційних технологій їх моделювання та практичне впровадження розроблених систем. В силу охоплення різних тематичних областей досліджень, основні результати, що описані в циклі наукових праць, згруповані за відповідним напрямками та розподілені по трьох розділах. Перший розділ “Математичне та комп'ютерне моделювання процесів розміщення, покриття та розбиття об'єктів довільної просторової форми та конструктивні методи оптимізації“ присвячений розробці конструктивних засобів математичного і комп’ютерного моделювання складних систем з об’єктами, що мають довільну просторову форму, метричні характеристики та відповідне взаємне розташування з урахуванням технологічних обмежень. Розроблена методологія побудови адекватних математичних моделей реальних об’єктів та їх відношень в дво-, три- та n-вимірних евклідових просторах. Побудовані математичні моделі оптимізаційних задач пакування, розкрою, компоновки, покриття та розбиття в складних системах з об'єктами довільної просторової форми та досліджено їх властивості. З метою урахування похибок вихідних даних набув подальшого розвитку новий напрям теорії інтервального аналізу – інтервальна геометрія. Розроблені нові та набули подальшого розвитку класичні методи оптимізації складних процесів та систем, в тому числі методи дискретної та комбінаторної оптимізації, глобальної статистичної оптимізації багатоекстремальних функцій, некласичні методи нескінченновимірного математичного програмування з булєвими змінними, чисельні методи оптимізації негладких функцій. Отримані наступні фундаментальні результати. Формалізовано класи базових та складених дво-, три- та n-вимірних об'єктів евклідових просторів, що є адекватними математичними моделями матеріальних об’єктів. Побудовано n-вимірний інтервальний простір, нові класи відображень та введені інтервальні об'єкти як математичні моделі заданих з похибками довільних об'єктів. Введені спеціальні класи функцій, на базі яких розроблені методи формалізації відношень об'єктів довільної просторової форми в евклідових та інтервальних просторах. Створено методологію математичного моделювання та визначено класи задач оптимізації розміщення (пакування, компоновки та розкрою), покриття і розбиття у складних системах з об'єктами довільної просторової форми. Побудовані математичні моделі та розроблені конструктивні методи розв'язання основних оптимізаційних задач розміщення з урахуванням технологічних обмежень (зон заборони, заданих відстаней між об’єктами, можливості їх обертання та похибок вихідних даних), у тому числі задач розміщення неорієнтованих складених об’єктів та задач оптимізації розміщення n-паралелепіпедів та n-політопів. Створено методологію математичного та комп'ютерного моделювання задач покриття заданої області об'єктами довільної просторової форми. Формалізовано критерії покриття та доведені теореми про розбиття простору параметрів розміщення покриваючих об’єктів. Побудовано математичну модель задачі трансляційного включення для області покриття зі змінними параметрами розміщення та метричними характеристиками. Запропоновано структурно-декомпозиційний підхід, який дозволяє звести задачу покриття до розв’язання послідовності певних класів задач математичного програмування. Важливий здобуток виконаних досліджень – це якісно новий рівень теоретичного обґрунтування і практичної реалізації математичних моделей та оптимізаційних методів розв’язання задач геометричного проектування. Досліджені нові комбінаторні моделі задач синтезу дискретних структур. На основі відображення комбінаторних множин у евклідовий простір розроблено теоретичні засади побудови нового класу задач дискретної оптимізації – задач евклідової комбінаторної оптимізації. Досліджено властивості евклідових комбінаторних множин. Побудована загальна теорія опуклого продовження функцій, заданих на евклідових комбінаторних множинах. Доведені теореми про існування опуклих, сильно опуклих та диференційованих функцій на комбінаторних багатогранниках. Запропоновані конструктивні методи побудови опуклих продовжень. Досліджено екстремальні властивості функцій на евклідових комбінаторних множинах. Доведено теореми про оцінку мінімумів функцій для різних класів евклідових комбінаторних множин. Запропоновано та теоретично обґрунтовано методи евклідової комбінаторної оптимізації. Досліджено задачу квадратичної оптимізації на евклідовій множині переставлень та наведений точний метод її розв’язання. Досліджено класи нових математичних моделей неперервних задач оптимального розбиття множин n-вимірного евклідового простору. Розглянуті детерміновані, стохастичні, лінійні та нелінійні багатопродуктові задачі оптимального розбиття множин. Виділено клас динамічних задач розбиття з критерієм оптимальності, який залежить від фазових траєкторій і управління заданої керованої системи. Розроблено єдиний підхід, в основі якого лежить зведення нескінченновимірних задач оптимізації до скінченновимірних негладких задач максимізації або негладких максимінних задач. Запропоновано метод урахування впливу невизначеності на значення критерію оптимальності у випадку, якщо вихідна інформація носить ймовірнісний характер. Встановлений взаємозв`язок задач оптимального розбиття множин та задач про кульове покриття. Для функціональних класів, заданих квазіметриками, запропоновано новий чисельний метод пошуку вузлів та коефіцієнтів оптимальних квадратурних формул, оснований на властивостях задачі оптимального розбиття множин . Отримані фундаментальні результати в напрямку теорії глобальної оптимізації. Реалізована ідея розбиття множини визначення багатоекстремальної функції на області притягання локальних екстремумів, що дозволило, завдяки розробленій теорії оптимального розбиття множин, знайти не тільки області притягання, але і центри цих областей, яким відповідають всі локальні екстремуми. Розроблені ймовірнісні моделі детермінованих задач. Побудована група методів послідовної статистичної оптимізації (метод околів, що звужуються, метод асимптотичного перебору локальних екстремумів), які базуються на статистичних властивостях функцій у просторах великої розмірності. Доведені теореми про збіжність методів, отримані умови теоретичної ефективності у порівнянні з класичними методами випадкового пошуку. Розвинуто класичну теорію оптимізації негладких опуклих функцій, методи якої базуються на зовнішній апроксимації множини екстремумів еліпсоїдами з монотонним зменшенням їх об'єму. Побудовано нові сімейства субградієнтних методів з перетворенням простору для знаходження точки мінімуму опуклої функції при апріорному знанні оптимального значення функції, які мають прискорену збіжність при розв'язуванні задач з яружними особливостями. Методи базуються на використанні нових класів лінійних неортогональних операторів перетворення n-вимірного евклідового простору для апроксимації еліпсоїдами опуклих тіл, отриманих у результаті перетину кулі та напівпросторів. Методи адаптовано для знаходження допустимої точки системи опуклих нерівностей. Розроблено математичні моделі, алгоритми та програмне забезпечення для задач знаходження пропускних здатностей дуг надійної орієнтованої мережі з передачею потоків як довільними шляхами, так і по заданій множині припустимих шляхів. Розроблено нові методи негладкої оптимізації для знаходження лагранжевих двоїстих оцінок в квадратичних неопуклих задачах. Побудовано нові моделі для задачі мінімізації поліноміальних функцій, задачі про максимальний розріз графу та задачі про максимально незалежну множину вершин графу. Обгрунтовано нові властивості оцінок Шора для зваженого числа внутрішньої стійкості графу. Побудовано нові сімейства графів, для яких зважене число стійкості знаходиться за поліноміальний час. Другий розділ “Фундаментальні методи моделювання, аналізу, синтезу та оптимізації складних просторових конструкцій“ присвячений розробці математичних і технічних засобів дослідження складних просторових об’єктів нелінійної природи та оптимізації їх параметрів. Створена методологія побудови математичних моделей процесів та систем, що спрямована на оптимізацію проектування, моделювання, формування рівнянь руху, керування, оцінювання параметрів і станів об’єктів з урахуванням експериментальних і статистичних даних. Розроблена теорія математичного моделювання, оптимальної фільтрації та оптимального керування елементами великих космічних конструкцій з нелінійними характеристиками. Розроблені нові підходи і методи моделювання систем з елементами штучного інтелекту. Отримані наступні фундаментальні результати. Побудовано нові математичні моделі просторових конструкцій з нелінійностями у просторі станів, запропоновані оригінальні алгоритми оптимального оцінювання станів. Розроблені і доведені до інженерного рівня методи оптимального керування просторовою орієнтацією конструкцій та їх коливаннями. Запропоновано ряд методів структурної і параметричної ідентифікації просторових конструкцій та створено відповідні обчислювальні процедури, призначені для використання в режимі реального часу. Розроблено методи моделювання нестаціонарних нелінійних процесів довільної природи із невизначеностями структурного, статистичного і параметричного характеру. Розроблено нові оптимізаційні методи розв’язання задач планування станів та проектування просторових кінематичних схем маніпуляційних роботів, в тому числі методи проектування оптимальних структур маніпуляційних роботів для виконання завдань з певного класу. Запропоновано нові чисельні методи і алгоритми автоматичної побудови оптимальних динамічних моделей маніпуляційних роботів за критерієм мінімізації обчислювальної складності. Розроблено новий числово-аналітичний підхід для формування рівнянь динаміки у вигляді з явно виділеними складовими сил, що діють на систему. Доведено, що за такого підходу кожна кінематична схема маніпуляційної системи буде мати власну мінімальну обчислювальну складність. Досліджено проблеми проектування і аналізу множини кінематичних схем, які можуть бути практично реалізовані, а також досліджено вплив кожної складової частини рівнянь динаміки на обчислювальну складність всієї системи. Для вирішення проблеми керування рухом маніпуляційних роботів розроблено координаційний підхід, який полягає у виділенні самих суттєвих елементів рівнянь динаміки з метою їх використання для синтезу і аналізу систем керування. Розроблені алгоритми геометричної, кінематичної та динамічної координації, адаптації і побудови законів руху. Розроблено новий метод планування просторових рухів маніпуляційних роботів у середовищі з обмеженнями, як аналог процедур навчання та прийняття рішень для виконання маніпуляцій і локомоцій вищих організмів. Подано комплексний підхід до розпізнавання та ідентифікації складних ситуацій, який базується на аналогії з методами колективного прийняття рішень, що ефективно використовуються у багатьох прикладних задачах. Розроблено методи теорії редукції, спрямовані на встановлення такого співвідношення складності відновлюваної функції й обсягу емпіричних даних, що забезпечують необхідні якість і надійність розв’язку задачі. Розроблено методи моделювання нестаціонарних нелінійних процесів довільної природи із невизначеностями структурного, статистичного і параметричного характеру. Запропоновано методи встановлення коректності класів нелінійності стаціонарних моделей різних типів для оптимального проектування механічних систем. Запропоновані нові підходи і методи для моделювання мислення в системах зі штучним інтелектом. Створена віртуальна штучна особистість - робот «VITROM» як комплекс програм, що дозволяє імітувати діяльність функціональних систем мозку людини на основі поглибленого вивчення структурно-функціональної організації нервової системи людини. Проведені експериментально-теоретичні дослідження інтелектуально-творчих процесів при формуванні нових знань і рішень. Третій розділ “Прикладні інтелектуальні комп’ютерні технології дослідження складних процесів і систем“ присвячений розробці нових перспективних інформаційних технологій обробки, аналізу, діагностики даних і візуалізації інформації для створення оригінальних і удосконалення існуючих засобів обчислювальної техніки та програмного забезпечення приладів і систем дослідження технічних, фізичних, біологічних та інтелектуальних процесів. Створені нові інтелектуальні інформаційні технології базуються на розроблених авторським колективом фундаментальних математичних методах оптимізації, моделювання, аналізу і синтезу складних процесів і систем різноманітної природи з урахуванням просторових форм об'єктів. Отримані наступні фундаментальні результати. Розроблено прикладні засоби побудови єдиного математичного інформаційного інструментарію для всебічного і повного дослідження фізичних процесів і природних явищ, який включає низку методів відбору, розпізнавання, класифікації, розпаралелювання для швидкої обробки інформації, побудови архітектури технічних засобів і математичних моделей для створення на цій основі високоефективних спеціалізованих і проблемно-орієнтованих інформаційно-аналітичних систем реального часу. Створено теоретичні основи синтезу високопродуктивних проблемно-орієнтованих і спеціалізованих систем обробки інформації, які відображають принципи ієрархічності, рекурсивності, глибокого розпаралелювання алгоритмів на заданому рівні з метою обробки інформації в темпі її надходження. Отримано загальні термальні подання моделей і алгоритмів, що відображають ієрархічність складних задач на різних рівнях та дозволяють ефективно описати ланцюгові та гіллясті фізичні процеси, що характеризують стан складних технічних систем, об’єктів, довкілля тощо. Розроблено основи теорії алгоритмів і систем обробки інформації, які мають паралельну структуру, а також одержано конструктивні підходи для побудови таких алгоритмів і систем з врахуванням їх фізичної і обчислювальної реалізації. Визначено класи алгоритмів, які допускають автоматичну реалізацію в системах реального часу. Розроблено концепцію, створено новітні інформаційні технології та ефективні методи моделювання і експериментального дослідження нейроподібних спеціалізованих обчислювальних сіток і середовищ високої живучості для цифрової обробки та аналізу сигналів, обробки складних зображень. Розроблено і виготовлено високопродуктивні спеціалізовані процесори і проблемно-орієнтовані системи на базі системних середовищ, які застосовуються для постановки обчислювальних експериментів при обробці складних зображень в режимі реального часу, а також вирішення важливих народногосподарських задач і екологічних досліджень. Запропоновано формальний підхід до проектування штучних імунних систем, який реалізований при розв'язанні задач прогнозування часових рядів значень контрольованих параметрів і змінних. У рамках створеної інформаційно-аналітичної системи технічного діагностування така штучна імунна система використовується при розв'язанні задачі прогнозування технічного стану об'єкта діагностування і задачі опису відсутніх спостережень у вузлах байєсової мережі. На основі виконання полігонних і стендових випробувань розроблених методів та відповідного програмно-алгоритмічного забезпечення сформульовано рекомендації стосовно вибору методу збудження конструктивних елементів великих космічних конструкцій з метою отримання інформативних експериментальних даних, необхідних для розв’язання задач структурної і параметричної ідентифікації. Збудження конструкції досягається за рахунок прикладання до неї імпульсу сили, вибір того чи іншого способу збудження визначається складністю досліджуваної конструкції та вимогами до точності очікуваних результатів. Створено загальну концепцію побудови прикладних систем штучного інтелекту і можливості побудови обчислювальних систем з ймовірнісними алгоритмами перетворення інформації з використанням сучасного математичного апарату систем масового обслуговування. Для обробки експериментальних і статистичних даних, створення адекватних математичних моделей та оцінювання прогнозів в умовах наявності невизначеностей структурного, статистичного і параметричного характеру розроблено нові нейронечіткі методи і моделі на основі спеціальних поліномів та методів оцінювання параметрів. Розроблено науково-методологічні засади дослідження і створення інтелектуальних робототехнічних систем нового покоління з підвищеними розумовими та руховими функціями, що реалізовані в серії мобільних маневрених інтелектуально-механічних крокуючих роботів широкого призначення. Здійснено дослідження науково-теоретичних засад керування крокуючими електронно-механічними роботами на базі інтелектуальних інформаційно-вимірювальних систем і сучасних засобів телекомунікацій, розроблено електроприводи, системи керування та балансування ваги крокуючого робота, яка забезпечує його рух довільною поверхнею. У дослідженнях науково-теоретичних проблем створення системи бінаурального слуху для роботів розроблена і випробувана модель пеленгації джерела звуку та система обробки звукових хвиль від масивів сенсорів на основі розроблених оригінальних методів. Створені проблемно-орієнтовані системи для розв’язання задач геометричного проектування складних систем з урахуванням просторових форм дво-, три- та n-вимірних об'єктів. Реалізовано перехід до візуального процесу геометричного проектування, коли адекватна математична модель формується водночас із графічним відображенням постановки задачі. Такий інтелектуальний інструментарій візуально-графічного розв’язку оптимізаційних задач дає змогу накопичувати зразки моделювання у базі прецедентів для подальшої реалізації механізму виведення за аналогією та дозволяє отримувати високий рівень якості результату, суттєво зменшуючи час їх розв’язання. У дослідженнях з комп’ютерної обробки зображень вдосконалено наукові засади автоматичного комп’ютерного розпізнавання образів, технологію формування структурного опису зображень та методи їх обробки, що дозволило вирішувати широке коло задач інтелектуального аналізу візуальної інформації. Запропоновано нові методи моделювання і розпізнавання обличчя людини, дослідження мімічних проявів та емоційних станів на обличчі людини. Вперше запропонована математична модель та цілісна інформаційна технологія для автоматичного визначення довільного емоційного стану конкретної людини, як опуклої комбінації деяких базових станів. Для задач розпізнавання побудовані функціональні перетворювачі над деякою підмножиною контрольних точок. Розроблено нові методи створення інтелектуальних комп’ютерних систем розпізнавання мовно-зорових образів з елементами семантичного сприйняття інформаційних текстів. У розробках по розпізнаванню мовних образів розвинуто концепцію пофонемного розпізнавання послідовності окремо вимовлених слів, що дозволило спростити процедуру навчання та покращити загальні покажчики системи. Розроблено нові методи аналізу і синтезу голосової мовної інформації. Для вирішення задачі комп’ютерного синтезу розроблено сегментно-конкатенативний метод. Створена інформаційна комп’ютерна технологія озвучення довільних текстів українською мовою та розроблена автоматизована комп’ютерна система перетворення вхідної голосової мовної інформації у текстову. Вперше в Україні розроблена унікальна інформаційна технологія для моделювання та вивчення української жестової мови. Технологія включає перетворення текстів українською мовою в їх аналоги на мові жестів, аналіз і синтез міміки і артикуляції губ, просторове моделювання рухів жестової мови і дактильної абетки тривимірної моделі людини, відображення процесу промовляння. Розробка має велике соціальне значення, оскільки дає можливість впроваджувати вивчення та використання української жестової мови в установах України. За результатами досліджень авторами опубліковано понад 100 монографій, підручників, навчальних посібників та понад 1200 наукових статей. Результати доповідались на більш ніж 100 міжнародних наукових конференціях, симпозіумах, семінарах. За безпосередньою участю авторів захищено понад 50 докторських та кандидатських дисертацій. Теоретичні засади моделювання складних процесів і систем покладені в основу вирішення фундаментальних прикладних проблем, що досліджувались в рамках державних науково-технічних програм на замовлення міністерств і відомств України, а також отримали матеріально-технічну і фінансову підтримку закордонних установ Європейського Союзу та США у вигляді понад 20 грантів на наукові дослідження. Практична значимість отриманих результатів підтверджується понад 70 патентами, авторськими свідоцтвами, актами впровадження, свідоцтвами про реєстрацію авторських прав на твір, створенням сучасних інформаційних технологій світового рівня для дослідження складних процесів і систем з урахуванням просторових форм об’єктів.