Рух у випадковому напрямку

Вступ

Під час розв’язування більшості прикладних задач регулювання,

інформацію, потрібну для побудови і реалізації системи керування,

можна поділити на дві частини:

– числову (кількісну), що отримується з вимірювальних датчиків;

– лінгвістичну (якісну), що надходить від експерта.

Значна частина нечітких систем регулювання використовує другий

вид знань, що частіше за все подають у формі бази нечітких правил.

У випадку, коли виникає потреба спроектувати нечітку систему,

але наявні лише числові дані, ми стикаємося з серйозними проблема-

ми. Один із способів їх розв’язання – це застосування так званих ней-

ро-нечітких (neuro-fuzzy) систем. Вони мають багато переваг, але їх

база правил повільно наповнюється знаннями в процесі ітеративного

навчання.

8.2. Нечіткі нейронні мережі

Основна перевага систем з нечіткою логікою – це здатність вико-

ристовувати умови і методи розв’язування задач, описані мовою, близь-

кою до природної. Однак класичні системи з нечіткою логікою, не-

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

вил, вид і параметри функцій належності, що описують вхідні і вихід-

ні змінні системи, а також вид алгоритму нечіткого висновку, виби-

раються суб’єктивно експертом-людиною, і вони не завжди відпові-

дають дійсності.

Для усунення вказаного недоліку був запропонований апарат не-

чітких нейронних мереж (fuzzy neural networks). Ці системи відомі та-

кож як адаптивні нейро-нечіткі системи висновку (Adaptive Neuro-Fuzzy Inference System, ANFIS).

Нечітка нейронна мережа – це багатошарова нейронна мережа, в якій шари виконують функції елементів системи нечіткого висновку. Нейрони такої мережі характеризуються набором параметрів, настроювання яких виконують під час навчання, як у звичайних ШНМ. На рис. 8.1 зображена нечітка ШНМ на базі алгоритму Сугено нульового порядку, за якого значення вихідної змінної обчислюють за фор-мулою

де α_r – значення функцій належності передумов кожного окремого правила r за конкретних значень вхідних сигналів.

Шар 1 здійснює зведення до нечіткості.Нелінійні функціїµ_ri (x_i ),де r – номер продукційного правила, а i – номер компоненти вхідного вектора, відповідають функціям належності передумов правил. Настроювані параметри цього шару – параметри використовуваних функцій належності.

Шар 2 обчислює вислідні функції належності передумов нечіткихправил. У цьому випадку шар не має настроюваних параметрів.

Шар 3 (складається з двох нейронів)і виконує додавання і зважене додавання вихідних сигналів шару 2. Параметрами цього шару є вагові коефіцієнти w_r .

Шар 4 реалізує операція ділення y = f₁ f₂.Він не містить настро-юваних параметрів.

Якщо в такій мережі використовувати функції належності гаус-сового типу, а для обчислення вислідних функцій належності переду-

мов правил (шар 2) – операцію множення замість операції «мінімум», то отримаємо досить поширену нечітку мережу Ванга–Менделя.

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

Рис. 8.1. Нечітка нейронна мережа на основі алгоритму Сугено

8.3. Синтез нечітких правил на основі числових даних

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

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

куване (еталонне) значення вихідного сигналу.

Задача полягає у формуванні нечітких правил, щоб побудований на їх основі модуль керування під час отримання вхідних сигналів генерував коректні (що мають мінімальну похибку) вихідні сигнали.

Крок 1. Поділ простору вхідних і вихідних сигналів на інтервали

Припустимо, що нам відоме мінімальне і максимальне значення кожного сигналу. За ними можна визначити інтервали, в яких мітяться припустимі значення. Наприклад, для вхідного сигналу x₁ такий інтервал позначимо [x₁⁻ , x₁⁺ ] . Якщо значення x₁⁻ і x₁⁺ невідомі, то можна скористатися навчаючими даними і вибрати з них відповідно

мінімальне і максимальне значення:

x₁⁻=min(x₁), x₁⁺=max(x₁).

Аналогічно для сигналу x₂ визначимо інтервал [x₂⁻ , x₂⁺ ] , а для бажаного вихідного сигналу d – інтервал [d ⁻, d ⁺ ] .

Кожен визначений у такий спосіб інтервал поділимо на 2n + 1 (непарне число) інтервалів (відрізків), причому значення n для кожно-

го сигналу підбирається індивідуально, а відрізки можуть мати однакову або різну довжину. Окремі інтервали позначимо так: S_n (малий n), ... , S_n (малий1), M (середній), B₁(великий1), ... , B_n (великий n).

На рис. 8.2 подано приклад такого поділу, де область визначення сигналу x₁ розбита на п’ять інтервалів (n = 2), сигналу x₂ – на сім ін-тервалів (n = 3), а область визначення вихідного сигналу y – на п’ять інтервалів (n = 2).

Рис. 8.2. Поділ простору сигналів на інтервали

Кожна функція належності в даному прикладі має трикутну форму. Одна з вершин розміщена у центрі відрізка і їй відповідає значення функції, що дорівнює 1. Дві інших вершини лежать в центрах сусідніх відрізків. Їм відповідають значення функції належності, що дорівнюють 0. Зазначимо, що можна запропонувати багато інших способів поділу вхідного і вихідного простору на окремі відрізки і використовувати інші форми функцій належності.

Крок 2. Побудова нечітких правил на основі даних для навчання

Визначимо ступені належності даних для навчання кожного відрізка, виділеного на кроці 1.

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

Тепер співставимо дані для навчання (x₁ (i), x₂ (i), d (i)) з областями значень, в яких вони мають максимальні ступені належності. Наприклад, для випадку, показаного на рис. 8.2, x₁ (1) має найбільший ступінь належності до інтервалу M, а x₂ (1) – до інтервалу S₁. Остаточно для кожної пари даних для навчання можна записати правило:

{x₁ (1), x₂ (1);d (1)}⇒

{x₁ (1)[max = 0.8 in M], x₂ (1)[max = 0.6 in S₁ ];d (1)[max = 0.8 in M]}⇒

R(1): if x₁ is M and x₂ is S₁ then y is M.

(8.1)

{x₁ (2), x₂ (2);d (2)}⇒

{x₁ (2)[max = 0.8 in B₁ ], x₂ (2)[max =1 in M];d (2)[max = 0.8 in B₁ ]}⇒

R(2): if x₁ is B₁ and x₂ is M then y is B₁.

Крок 3. Приписування кожному правилу ступеня істинності

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

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

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

R: if x₁ is A₁ and x₂ is A₂ then y is B

ступінь істинності, що позначається як SP(R), визначається як

SP(R) =µ _A1 ( x₁ ) µ _{A 2} ( x₂ ) µ_B ( y) .

Наприклад, правило R(1) з (8.3) матиме ступінь істинності

SP(R ₁ ) =µ _M ( x₁ ) µ _{S 1} ( x₂ ) µ _M ( y) = 0,8 ⋅ 0,6 ⋅ 0,8 = 0,384 .

Крок 4. Створення бази даних нечітких правил

Спосіб побудови бази нечітких правил подано на рис. 8.3.

Рис. 8.3. Форма бази нечітких правил

Ця база зображена у вигляді таблиці, яку заповнюють нечіткими правилами таким чином: якщо правило має вигляд як, наприклад, правило R(1) у (8.1), то на перетині рядка S₁ і стовпця M вписують назву нечіткої множини, отриманої в результаті, тобто М (відповідної вихідному сигналові y). Якщо є декілька нечітких правил з одним і тим же посиланням, то з них вибирають те, яке має найвищий ступінь істинності.

Крок 5. Зведення до чіткості

Наша задача зазвичай полягає у визначенні за допомогою бази правил відображення f : (x₁, x₂) → y , де y – вихідна величина нечіткої системи. Під час визначення кількісного значення керуючого впливу y для даних вхідних сигналів потрібно виконувати операцію зведеннядо чіткості.

Спочатку для вхідних сигналів (x₁, х₂) з використанням операції добутку об’єднаємо посилання (умови) k-го нечіткого правила. Так визначають ступінь активності k-го правила. Його значення знаходять за формулою

Для розрахунку вихідного значення y скористаємось способом зведення до чіткості за середнім центром:

.

Розглянутий метод можна легко узагальнити для нечіткої системи з будь-якою кількістю входів і виходів.

8.4. Нечітка одноелементна модель

Ефективність застосування апарату нечіткої логіки ґрунтується на теоремах, аналогічних теоремам про повноту для нейронних мереж, суть яких полягає в тому, що система на основі алгоритму нечіткого виводу під час виконання визначених, але не дуже жорстких умов – це універсальний апроксиматор.

Найбільш простою системою апроксимації функцій є нечітка одноелементна модель (singleton fuzzy model), що ґрунтується на системі Сугено нульового порядку:

До довільної функціональної залежності y = f(x) може бути застосована процедура кусково-лінійної апроксимації, як показано на рис. 8.4.

Рис. 8.4. Кусково-лінійна апроксимація і синтез множин

Вузли кусково-лінійної апроксимуючої функції відповідатимуть значенням коефіцієнта функції наслідку w_i в моделі (8.2). Висновок і зведення до чіткості здійснюються за формулою

.

– добре прогнозовані апроксимаційні властивості;

– просте отримання параметрів.

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

9. АЛГОРИТМИ ЗНАХОЖДЕННЯ ОПТИМАЛЬНИХ ТРАЄКТОРІЙ

9.1. Загальні положення

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

покиціль не досягнутавибрати напрям руху до цілі

якщошлях вільний,

торухатись

інакшевибрати інший напрям відповідно

до вибраного алгоритму обходу перешкоди

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

9.2. Найпростіші алгоритми обходу перешкод

Найбільш прості алгоритми обходу перешкод – це метод руху у випадковому напрямку і метод відслідковування меж перешкод.

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

Тут і далі сірим кружечком позначено рухомий об’єкт, білим – ціль руху, а чорними квадратами – перешкоди.

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

Метод відслідковування меж перешкод

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

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

a б

Рис. 9.3. Метод відслідковування обрисів перешкод

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

9.3. Метод «пошуку в ширину»

Найбільш простим алгоритмом серед методів обходу зв’язних графів – це метод «пошуку в ширину» (breadth-first search). Принцип його роботи такий: починаючи з першого вузла (положення), цей ал-

горитм перевіряє спочатку всі вузли, що межують з ним, потім всі вузли в двох кроках від нього, потім у трьох кроках, і так далі доти, доки цільового вузла (положення) не буде знайдено. Зазвичай всі необстежені сусідні вузли вміщуються у список «відкритих» вузлів, який є стеком типу «першим зайшов, першим вийшов» (FIFO, first-in-first-out).Алгоритм цього методу такий:

functionBreadthFirstSearch : Boolean;var

n, n', s : node; Open : queue;