В.В. Семко, канд. техн. наук

Інститут телекомунікацій і глобального інформаційного простору НАН України, м. Київ, Україна

ЛОГІКО-МАТЕМАТИЧНА МОДЕЛЬ ОПИСУ ПРОСТОРУ РІШЕНЬ

В.В. Семко, канд. техн. наук

Институт телекоммуникаций и глобального информационного пространства НАН Украины, г. Киев, Украина

ЛОГИКО-МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОПИСАНИЯ
ПРОСТРАНСТВА РЕШЕНИЙ

V.V. Semko, Candidate of Technical Sciences

Institute of Telecommunications and Global Information Space in the system of the National Academy of Sciences of Ukraine, Kyiv, Ukraine

LOGICAL-MATHEMATICAL MODEL OF THE DESCRIPTION
OF DECISIONS SPACE

Розглянуто питання розрахунку підпростору рішень простору спостережень при синтезі гарантованих управлінь у топологічному просторі пошуку. Запропоновано логіко-математичну модель опису підпростору рішень для пошукової системи.

Ключові слова: простір спостережень, простір рішень, пошукова система, об’єкт пошуку, топологічний простір.

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

Ключевые слова: пространство наблюдений, пространство решений, объект поиска, топологическое пространство.

The paper presents questions of calculation of decision of space of supervisions subspace are in-process considered at the synthesis of the assured managements in topological space of search. The logical-mathematical model of the description of decision space is offered for the searching system.

Key words: space of supervision, space of decisions, object of search, topological space.

Постановка проблеми. Принциповою відмінністю задач пошуку є те, що при їх вирішенні використовується поточна інформація. Якщо така інформація надходить у дискретні моменти часу з великими інтервалами, синтез алгоритмів пошуку та переслідування зазвичай здійснюється з використанням методів теорії пошуку.

У разі використання методів теорії пошуку традиційно застосовуються ігрові методи. Використання теоретико-автоматних методів під час створення систем синтезу та прийняття рішень дозволяє створити новітні алгоритми пошуку та переслідування.

При цьому великий інтерес є під час застосування теоретико-автоматних методів у разі створення систем синтезу та прийняття рішень.

Під час створення сучасних автоматизованих засобів і систем управління виходять з положень теорії перетворення інформації (загальної теорії алгоритмів, абстрактної теорії автоматів) та теорії побудови різного роду перетворювачів інформації (елементи математичної логіки, абстрактна та структурна теорія автоматів).

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

Під час вирішення задач пошуку і переслідування у просторі спостережень та просторі станів застосуємо цифровий автомат як пристрій або програмний засіб перетворення інформації.

Аналіз досліджень і публікацій. На відміну від ігрових методів вирішення задач пошуку та переслідування [1; 2] Д.О. Поспєловим та його послідовниками була запропонована теорія ситуаційного управління складними об’єктами [3; 4].

Для здійснення мети управління об’єктом, який є спроможним до автономної роботи та на тактичному рівні об’єднує об’єкт та суб’єкт управління (ергамат), необхідно здійснити формальний опис інформаційної множини гарантованих управлінь ергаматом під час синтезу рішень щодо управління його переміщенням у просторі пошуку (спостереження) [5; 6]. Тобто синтезовані рішення щодо управління ергаматом мають обиратись тільки у множині його гарантованих управлінь за деяким принципом оптимальності та правилом останову процедури перебору.

Отже, задача синтезу гарантованих управлінь ергаматом в умовах невизначеності є актуальною і має не тільки теоретичне, але і велике прикладне значення для вирішення задач конфлікту взаємодії об’єктів та суб’єктів у фізичному та віртуальному просторі.

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

Мета статті. Головною метою цієї роботи є розроблення моделі синтезу ситуаційного управління ергаматом в умовах невизначеності.

Виклад основного матеріалу. Постановка та вирішення задачі пошуку істотно залежить від того, яку інформацію має пошукова система (ПС) та об’єкт пошуку (ОП) [5].

Для моделі ПС [6]

(1)

де – базис; – співвідношення, яке враховує кінематичні співвідношення щодо руху ПС; – граматика та правила утворення співвідношень при взаємодії ПС та ОП.

, (2)

де – характеристичний вектор стану ПС; – множина описів усіх ОП у просторі спостереження Q, яка вміщує дані про згладжені ОП, похідних від координат відповідно до припущень , яке враховує прогноз і динаміку переміщення всіх ОП.

Співвідношення

(3)

вміщує згладжені координати ПС у просторі спостереження QЄ вироджені в точку початку координат, зв’язаної з ПС системи координат, – згладжені значення вектора швидкості (першої похідної) ПС у просторі спостереження Q, – припустиме значення дистанції зближення ПС з ОП у просторі спостереження Q.

Слід зауважити, що значення визначається вимогами безпеки взаємодії об’єктів у просторі спостереження Q та невизначеністю переміщення ОП.

Введемо для i-го ОП співвідношення, яке описує його властивості

(4)

де – згладжені координати i-го ОП у просторі спостереження Q, – згладжені значення вектора швидкості (першої похідної) i-го ОП у просторі спостереження Q, – припустиме значення дистанції зближення ОУ з i-м ОП у просторі спостереження Q.

У такому разі маємо формальну мову опису управлінь ПС, яка є безліччю ланцюжків у деякому кінцевому алфавіті. За моделлю (1) кінцевим алфавітом для ПС є співвідношення (3).

Наявність граматики вказує на кінцевий механізм завдання мови, яка описує ланцюжки управління ПС. У загальному випадку ланцюжки управління є нескінченною множиною. Слід зауважити, що нескінченні об’єкти важко задати, наприклад, простим перерахуванням елементів.

Формальна мова є безліччю ланцюжків у деякому кінцевому алфавіті. За моделлю (1) кінцевим алфавітом є співвідношення (3).

ПС є керованою ергатичною системою в просторі спостереження Q.

Визначимо регулярну граматику пошукової системи

, (5)

де – множина нетермінальних позицій, – множина термінальних (кінцевих) позицій, – кінцева множина правил (продукцій), яка вміщує хоча б одну нетермінальну позицію, – початкова нетермінальна позиція ПС.

Тоді для переміщення ПС у базисі, визначеному співвідношенням (2), можна задати n ланцюжків , які характеризуються переміщенням відображаючої точки ПС у просторі та обраними значеннями характеристик переміщення , які визначаються динамічними та фізичними обмеженнями щодо можливих управлінь ПС.

Тобто

(6)

Тим самим стратегія переміщення ПС є конкатенацією ланцюжків, кількість яких обумовлена динамічними характеристиками ОУ, обмеженнями простору спостереження, динамічними характеристиками спостережуваних ОП, обмеженнями політики безпеки для інформаційних об’єктів та суб’єктів, а також іншими вимогами, які є обов’язковими для всіх об’єктів у просторі спостережень.

Формально граматика є породжуючою і використовується для побудови "правильних" ланцюжків. Послідовність правил у процесі породження ланцюжка є його синтезом

. (7)

Критерій відбору під час розрахунку і конкатенації ланцюжків може входити до правил ПС.

При наявності формального опису інформаційної множини гарантованих управлінь ПС при синтезі рішень (ланцюжків) перебірна процедура синтезу рішень перетворюється в мінімально перебірну задачу динамічного програмування за критерієм мінімізації втрат ресурсів.

Нехай базис має вигляд

, (8)

де - l-та підмножина алфавіту, яка не є пустою.

Позначимо ланцюжок

, (9)

де операція конкатенації символів (базової складової мови).

Тоді множина є формальною мовою, яка визначена на алфавіті .

Мову засновано на системі обмежень, які накладаються на систему напіввідношень (продукції) Туе, а граматика визначена як механізм породження ланцюжків .

Визначення формальної граматики вимагає наявності ще одного алфавіту

. (10)

Під час вирішення практичних задач для технічних або ергатичних систем управління алфавітний спосіб завдання інформації при синтезі рішень з урахуванням системи напіввідношень є достатньо зручним та універсальним, а ПС виконує функції перетворення інформації.

Припустимо, що є деяке явище з деякого класу явищ , яке приводить до появи деякого визначеного явища з класу явищ . У такому разі маємо перетворення інформації

. (11)

Тобто здійснюється відображення явища в явище певним об’єктом (ПС), який є перетворювачем інформації.

Перетворення є детермінованим та однозначним. У цьому разі вихідна інформація повністю визначає похідну. При цьому еквівалентність перетворення не є обов’язковою, тобто

. (12)

У такому разі синтез ланцюжків є перетворенням похідної інформації з використанням двійкового кодування, а синтез ланцюжків є результатом функціонування детермінованого кінцевого автомата, який у загальному вигляді є п’ятіркою

, (13)

де – базис, в якому формально описано стан ПС (алфавіт), – алфавіт стану автомата, – функція переходів для ОУ, – початковий стан автомату, – множина кінцевих станів автомата.

Функція переходів є множиною кінцевих точок станів кінцевого автомату, яким є ОУ при його переміщенні у просторі .

Під час вирішення задачі пошуку було сформовано простір , в якому ОУ має ознаку приналежності .

Визначимо алфавіт у вигляді

, (14)

де – час, – кількість ОП, – припустимі для ПС напрямки переміщення у просторі спостереження .

Фактично є автоматним відображенням підмножини станів i-го ОП на множину . Тобто є множиною автоматного відображення, яке задовольняє умови повноти для ПС.

Множина визначає просторове автоматне відображення у множину , включаючи пусті відображення .

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

Під час врахування ланцюжки визначаються за будь-яким методом пошуку (евристичним або з використанням нейронних мереж) за певним критерієм відбору та правилом зупинки.

Тим самим задача синтезу ланцюжків перестає бути ігровою, пошук відображення похідного алфавіту стає мінімально переборною процедурою в просторі рішень для ПС.

Надалі будемо мати на увазі, що використовується пов’язана система координат, центр якої розміщено в точковому об’єкті, а вісь ординат збігається з будівельною віссю ПС. ОП у подальшому також є точковим об’єктом.

Пошук має місце щодо об’єктів, множина положень (станів) яких утворює деяку кінцеву або нескінчену область на площині або в просторі пошуку.

Для спрощення розглянемо алгоритм розрахунку інформаційного образу рішень при синтезі ланцюжків за алфавітом згідно з виразом (14) для двомірного простору спостереження .

Розглянемо спосіб побудови (розрахунку) простору рішень для комбінованого керування (ПРКК) ПС за напрямком та швидкістю.

При розрахунку ПРКК здійснимо декомпозицію, задачу на два рівні: обчислення множин (діапазонів) припустимих швидкостей при обраному (заданому) напрямку переміщення ПС у просторі , об’єднання множин припустимих швидкостей на множині обраних (припустимих) напрямків переміщення ПС.

Під час здійснення розрахунків введемо значення часу затримки . Значення враховує час виконання обчислювальних процедур, прийняття рішення щодо обраного напрямку руху та швидкості в діапазоні припустимих швидкостей ПС [ , ]. Координати i-го ОП визначені у пов’язаній з ПС системі декартових координат для випадку відносного руху (рис.). Визначимо координати вектора істинної швидкості i-го ОП у режимі істинного руху.

Формально ПРКК можна визначити

, (15)

де – ПРКК, – множина напрямків переміщення, – множина припустимих швидкостей переміщення для i-го ОП за напрямком з множини , – кількість ОП на час спостереження.

Згідно з (15) ПРКК буде являти собою множину, утворену як перетин множин припустимих швидкостей переміщення ПС стосовно i-го ОП за напрямками припустимого переміщення ПС.

Тим самим ПРКК буде являти собою об’єднання за напрямками переміщення окремих діапазонів (множин) припустимих швидкостей ПС відносно всіх ОП (лінійка швидкостей) на поточний момент часу.

З геометричної інтерпретації способу визначення ПРКК отримаємо евристичне вирішуване правило у вигляді предикативної структури.

Рис. Геометрична інтерпретація способу розрахунку лінійки швидкостей

Побудуємо в ортогональному базисі з початку координат, як із центра, коло радіуса , який дорівнює припустимій дистанції зближення ПС з i-м ОП. Відобразимо точкою згладжені координати i-го ОП. Проведемо з точки дотичні та до побудованого кола, які за своїм геометричним змістом є гранично припустимими лініями відносного руху (переміщення) ЛВР1 та ЛВР2 відповідно і забезпечують розходження з i-м ОП на відстані, яка не є меншою від .

З початку координат будуємо вектор істинної швидкості ПС.

З точки будуємо вектор власної швидкості i-го ОП. Через точку проводимо лінію, яка є паралельною до вектора . У точці будуємо трикутник швидкості для отримання вектора відносної швидкості, спрямованого по ЛВР1 та ЛВР2, змінивши величину, а при необхідності і напрямок вектора на протилежний. Таким чином, отримуємо значення множників при векторі , які задовольняють умови

, (16)

де та – коефіцієнти, які визначають зміну величини вектора для побудови вектора відносної швидкості та , які відповідно забезпечують переміщення вздовж ліній ЛВР1 та ЛВР2. Тобто

. (17)

З виразу (16) знайдемо співвідношення для обчислення та .

. (18)

Аналіз практичних можливостей отримання вектора відносної швидкості переміщення i-го ОП вздовж ліній ЛВР1 та ЛВР2 дозволяє зробити висновок про те, що в окремих випадках співпадання векторів та з векторами та може бути по два вектори та відповідно для кожної лінії відносного руху, що є характерним для випадків зближення та переслідування. Тобто маємо дві множини

. (19)

Відповідно до значень величин у співвідношеннях

, (20)

, (21)

і значенням найбільшої можливої швидкості та співвідношеннями між знаками множин і визначено евристичне вирішаюче правило формування інтервалів безпечних швидкостей для ПС.

Евристичне вирішуюче правило формування інтервалів безпечних швидкостей для ПС визначається набором предикатів, кожен з яких надає однозначну відповідь про припустимі швидкості [0 ,].

(22)

(23)

(24)

(25)

(26)

(27)

()
{ (28)

(
{ (29)

(
{ (30)

(
(](
((}{ (31)

{(
({ (32)

([
(({ (33)

([
(({∅ (34)

[(
({ (35)

([
([{ (36)

([
([{ (37)

( [(
[ (>{ (38)

([
([ (>{ (39)

([ (40)

(41)

(42)

(43)

(44)

Вирішуюче правило (22-44) описує всі можливі співвідношення для задач пошуку і є прийнятним як для динамічних, так і інформаційних об’єктів.

Слід зазначити, що вирішуюче правило (22-44) одночасно враховує розв’язання задач пошуку і переслідування. Це досягається завдяки врахуванню можливості зближення ПС з ОП під час пересікання границі кола з радіусом для i-го ОП (рис.). При вході в межі та виході за межі кола при його перетині лінією відносного руху точка входу визначає розв’язання для задачі пошуку, а точка виходу визначає розв’язання для задачі переслідування.

Висновки. Для розв’язання задачі пошуку, оцінювання ситуації та синтезу стратегії ціледосягнення у просторі пошуку синтезовано предикативну структуру (22-44), яка є вирішуючим правилом граматики , що являє собою детермінований опис алгоритму розрахунку інформаційного образу рішень при синтезі ланцюжків за алфавітом згідно з виразом (14). Тобто розв’язується задача перетворення вхідної інформації у вихідну для автоматизованої чи автоматичної системи синтезу та прийняття рішень. Тим самим на виході системи формується інформаційний клас (образ), який є похідним щодо параметрів та ознак образів, які розпізнаються й аналізуються ПС.

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

Список використаних джерел

1. Айзекс Р. Дифференциальные игры / Р. Айзекс. – М. : Мир, 1967. – 480 с.

2. Кривонос Ю. Г. Динамические игры с разрывными траекториями / Ю. Г. Кривонос, И. И. Матичин, А. А. Чикрий. – К. : Наукова думка, 2005. – 220 с.

3. Поспелов Д. И. Ситуационное управление: теория и практика / Д. И. Поспелов. – М. : Наука, 1986. – 288 с.

4. Ющенко А. С. К теории деятельности эргатических мехатронных систем / А. С. Ющенко // Мехатроника, автоматизация, управление. – 2000. – № 3. – С. 2-11.

5. Ким Д. П. Методы поиска и преследования подвижных объектов / Д. П. Ким. – М. : Наука, 1989. – 336 с.

6. Семко В. В. Модель конфлікту взаємодії об’єктів кібернетичного простору / В. В. Семко // Проблеми управління та інформатизації. – 2012. – Вип. № 2 (38). – С. 88-92.