Дослідження методів пошуку траєкторії руху для транспортної системи з урахуванням динамічної зміни навколишнього середовища

Размещено на http://www.allbest.ru/

РЕФЕРАТ

Об`єкт дослідження - транспортна система постачання промислового цеху.

Предмет дослідження - методи пошуку траєкторії руху для транспортної системи промислового цеху.

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

Методи дослідження - аналіз критеріїв оптимальності, моделювання алгоритмів і порівняння результатів моделювання.

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

Отримані алгоритми рекомендується до застосування в ТС промислових об`єктів з не великою кількістю об`єктів ПЦ і складною системою руху в межах приміщення.

Прогнозні припущення щодо розвитку об'єкта дослідження - модернізація алгоритмів для роботи в складних системах.

ПОШУК ОПТИМАЛЬНОГО ШЛЯХУ, ДИНАМІЧНА ЗМІНА СЕРЕДОВИЩА, АЛГОРИТМИ ТРАНСПОРТНОЇ СИСТЕМИ, ТЕОРІЯ ГРАФІВ, КРИТЕРІЇ ОПТИМАЛЬНОСТІ.

РЕФЕРАТ

Объект исследования - транспортная система поставки промышленного цеха.

Предмет исследования - методы поиска траектории движения для транспортной системы промышленного цеха.

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

Метод исследования - анализ критериев оптимальности, моделирования алгоритмов и сравнения результатов моделирования.

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

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

Прогнозные предположения о развитии объекта исследования - модернизация алгоритмов для работы в сложных системах.

ПОИСК ОПТИМАЛЬНОГО ПУТИ, ДИНАМИЧЕСКОЕ ИЗМЕНЕНИЕ СРЕДЫ, АЛГОРИТМЫ ТРАНСПОРТНОЙ СИСТЕМЫ, ТЕОРИЯ ГРАФОВ, КРИТЕРИИ ОПТИМАЛЬНОСТИ.

ABSTRACT

Explanatory note: 89 p., 23 fig., 6 tables., 3 applications, 48 sources.

Object of study - transport system of industrial supply shop.

The subject of research - methods of finding the trajectory of the transport system for industrial plant.

Purpose - to create and study methods of finding the optimal route based industrial robot dynamic environmental change.

Method of study - an analysis of optimality criteria, simulation algorithms and comparing simulation results.

Today is the actual problem of control of industrial robots in dynamic changes in environmental parameters. This paper provides a number of algorithms search for destination using different parameters, as optimality criteria. The modeling algorithms for various environmental conditions of the industrial plant. A comparative analysis of algorithms and are strengths and weaknesses of each.

The findings are recommended for use in industrial facilities with TS are not many objects of PC and its complex system of movement within the room.

Forecast assumptions about the object of research - modernization of algorithms to work in complex systems.

SEARCH OF OPTIMAL WAYS, DYNAMIC CHANGES ENVIRONMENT, TRANSPORT SYSTEM ALGORITHMS, GRAPH THEORY, OPTIMALITY CRITERION.

ЗМІСТ

• Перелік умовних позначень, символів, одиниць, скорочень і термінів
• Вступ
• 1 Аналіз задачі пошуку траєкторії руху
• 1.1 Аналіз основних теоретичних застав реалізації систем пошуку траєкторії руху
• 1.2 Основні поняття теорії графів
• 1.3 Основні поняття теорії дерев рішень
• 1.4 Основні поняття теорії керування
• 1.5 Основні поняття теорії оптимізації
• 2 Розробка методу вибору шляху прямування
• 2.1 Аналіз функціональних вимог методу вибору шляху прямування
• 2.2 Обґрунтування можливих критеріїв пошуку траєкторії руху
• 3 Розробка алгоритмічного і програмного забезпечення методу пошуку шляху прямування
• 3.1 Основні вимоги до розробки алгоритмів
• 3.2 Розробка алгоритму пошуку всіх можливих глобальних маршрутів з точки початку маршруту до точки його закінчення
• 4 Дослідження методів пошуку з урахуванням критеріїв оптимальності
• 4.1 Дослідження методу пошуку оптимального шляху прямування за кількістю контрольних точок маршруту
• 4.2 Дослідження методу пошуку оптимального шляху прямування за одним параметром
• 4.3 Дослідження методу пошуку оптимального шляху прямування за всіма параметрами
• 5 Експериментальне дослідження процесу керування роботою транспортної системи з урахуванням динамічної зміни навколишнього середовища
• 6 Охорона праці та безпека в надзвичайних ситуаціях
• 6.1 Аналіз умов праці у виробничому приміщенні
• 6.2 Промислова безпека у виробничому приміщенні
• 6.3 Виробнича санітарія у приміщенні
• 6.4 Пожежна безпека виробничого приміщення
• 6.5 Безпека у надзвичайних ситуаціях
• Висновки
• Перелік літературних посилань
• Додаток А - Алгоритми, використані в роботі
• Додаток Б - Програмні коди
• Додаток В - Роздатковий матеріал
• ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ, СИМВОЛІВ, ОДИНИЦЬ, СКОРОЧЕНЬ І ТЕРМІНІВ
• ГМ - глобальний маршрут;
• ЗСУ - зовнішнє середовище керування;
• КТ - контрольна точка;
• ЛМ - локальний маршрут;
• ЛМС система «людина-машина-середовище»;
• МЗТ - матриця зв'язування точок;
• НС - надзвичайна ситуація;
• ПК - персональний комп`ютер;
• ПП - предмет праці;
• ПЦ - промисловий цех;
• ТС - транспортна система.
• ВСТУП
• Значний прогрес в області обчислювальної техніки, програмного забезпечення і телекомунікації, розвиток інформаційних технологій, підвищення міри автоматизації і перерозподіл функцій між людиною і апаратурою привів до створення високоефективних і високонадійних роботизованих систем транспортних систем.
• Сучасний рівень обчислювальних пристроїв дозволяє практично без обмежень реалізовувати різні алгоритми керування рухливими об'єктами. У даній магістерській роботі будуть розроблені принципи інтелектуальної системи ухвалення рішень для вибору шляху руху роботизованої системи з одного пункту в іншій і утримування системи на обраній траєкторії[46].
• На сьогоднішній день є актуальною проблема керування промисловими роботами в умовах динамічної зміни параметрів навколишнього середовища тому було прийняте рішення про виконання даної роботи.
• Об`єкт дослідження - транспортна система постачання промислового цеху.
• Предмет дослідження - методи пошуку траєкторії руху для транспортної системи промислового цеху.
• Система пошуку траєкторії руху для автоматизованих виробничих транспортних систем призначена для динамічного керування всіма ланками процесу транспортування на виробництві як на конвеєрних лініях, так і керування переміщенням роботизованих платформ по території в залежності від поставлених цілей [41].
• Основними складностями при виборі траєкторії руху для транспортної системи є:

- динамічність навколишнього середовища тобто зміна основних факторів навколишнього середовища на траєкторії руху підчас руху об`єкту транспортної системи таких, як наприклад поява перешкоди на шляху прямування;

- постійна зміна цілей транспортної системи - алгоритми пошуку повинні бути гнучкими до динамічної зміни цілей руху системи;

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

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

Основними задачами, поставленими в даній магістерській роботі, є:

- дослідження основних алгоритмів пошуку траєкторії руху для транспортної системи;

- аналіз сучасних методів формування траєкторії для транспортних систем;

- аналіз основних методів автоматизованого керування транспортною системою з урахуванням динамічної зміни навколишнього середовища;

- виділення рекомендацій щодо покращення методів пошуку траєкторії руху для транспортної системи, а також виділення критичних моментів при проектуванні даних систем.

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

Повторне заземлення нульового провідника в мережі 380/220В розраховується для приміщення з параметрами: довжина - 10м, ширина - 8м, висота - 3м. Кількість робочих місць в приміщенні дорівнює 8.

1 АНАЛІЗ ЗАДАЧІ ПОШУКУ ТРАЄКТОРІЇ РУХУ

1.1 Аналіз основних теоретичних застав реалізації систем пошуку траєкторії руху

На даний момент існує досить багато теорій і реалізованих алгоритмів пошуку траєкторії руху для різноманітних систем як промислового спрямування, так і цивільного, військового та інших областей використання. Більшість з розроблених алгоритмів проектувалися для виконання певного вузько направленого завдання в деякій області техніки, наприклад в медицині, в військових цілях, в надзвичайних ситуаціях, в промисловості та ін.[41].

Система пошуку траєкторії руху, орієнтована на керування промисловими роботами транспортної системи підприємства, має задовольняти таким основним критеріям:

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

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

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

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

Більшість сучасних систем пошуку траєкторії руху побудовані на двох теоріях: теорія графів і теорія дерева рішень.

1.2 Основні поняття теорії графів

траєкторія рух транспортний

Теорія графів - це область дискретної математики, особливістю якої є геометричний підхід до вивчення об'єктів. Теорія графів знаходиться зараз в самому розквіті. Зазвичай її відносять до топології (тому що у багатьох випадках розглядаються лише топологічні властивості графів), проте вона перетинається з багатьма розділами теорії безлічі, комбінаторної математики, алгебри, геометрії, теорії матриць, теорії ігор, математичної логіки і багатьох інших математичних дисциплін. Основний об'єкт теорії графів - граф і його узагальнення[35].

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

Існує ще один вигляд завдань, пов'язаних з подорожами уздовж графів. Йдеться про завданнях, в яких потрібно відшукати дорогу, що проходить через всі вершини, причому не більше одного разу через кожну. Цикл, що проходить через кожну вершину один і лише один раз, носить назву гамільтонової лінії (на честь Уїльяма Роуена Гамільтона, знаменитого ірландського математика минулого століття, яке першим почало вивчати такі лінії). На жаль, поки що не знайдений загальний критерій, за допомогою якого можна було б вирішити, чи є даний граф гамільтоновим, і якщо так, то знайти на нім всі гамільтонови лінії.

Граф G(V,E) - комбінаторний об'єкт, що складається з двох кінцевої безлічі: V - званого безліччю вершин і безлічі пар елементів з V, тобто Е VxV, званого безліччю ребер, якщо пари неврегульовані, і безліччю дуг, якщо пари впорядковані. У першому випадку граф G(V,Е) називається неорієнтованим, в другому орієнтованим. Якщо е = (v1,v2)

eЕ,

то говорять, що ребро е з'єднує вершини v1, v2, якщо v1 = v2, то ребро е називається петлею. Дві вершини v1, v2 називаються суміжними, якщо існує з'єднуюче їх ребро. Аналогічно, два різних ребра суміжні, якщо вони мають спільну вершину.

Ступенем вершини v називається число ребер d (v), інцидентних їй, при цьому петля враховується двічі. У разі орієнтованого графа розрізняють ступінь d0 (v) по вихідних дугах і d1 (v) - по вхідних.

Шлях - це послідовність ребер e1, е2, ... , еm, така, що ei, ei +1 мають спільну вершину. Число ребер називається довжиною шляху. Якщо жодна з вершин не з'являється більше одного разу, то шлях називається простим. Ясно, що в простому шляху жодне ребро не використовується двічі.

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

У разі орієнтованого графа, якщо шлях проходить в напрямку дуг, він називається орієнтованим. Аналогічно визначається орієнтований цикл[36].

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

Дводольні графи - це графи, у яких безліч вершин можна розбити на дві безлічі V1, і V2, і так що кожне ребро графа з'єднує лише деяку вершину з V1 з деякою вершиною з V2.

Граф одиничного n-мірного куба Вn. Вершини графа - n-мірні двійкові набори. Ребра з'єднують вершини, що відрізняються однією координатою.

Нехай G - зв'язний граф, u, v - довільні вершини. Визначимо d (u, v) - відстань між u і v як довжину найкоротшого шляху з u в v. При цьому вважаємо d (u, v) = 0 при u = v.

Ясно, що введене таким чином відстань задовольняє аксіомам метрики:

d(u,v)0;

d(u, v) = 0u = v; (1.1)

d(u,v) = d(v,u);

d(u, v)+d(v, w) d(u, w) (нерівність трикутника).

Для зв'язного графа G діаметр d (G) визначається як:

d(G) = max d(u,v).

Графи G1 (V1, E1) і G2 (V2, E2) називаються ізоморфними, якщо існує Бієкція f: V1 V2, така, що виконується

(v1, v2)E(f(v1), f(v2)E2

При цьому f називається ізоморфізмом графів G1 і G2. Ізоморфізм графа G на себе називається автоморфізмом.

Наступні графи мають тільки тотожні авто морфи



Рисунок 1.1 - Графи тотожних аморфів

Широко відома так звана проблема ізоморфізму графів, в якій для будь-яких двох графів потрібно встановити, ізоморфні вони чи ні [36].

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

Нехай G1 + (V1, E1), G2 = (V2, E2) - два графа.

Об'єднання графів G1 і G2 є граф, у якого V = V1 V2,

Е = E1 Е2.

З'єднання графів G1 + G2 є граф, у якого

V = V1 V2, Е = E1 Е2 {(v1, v2)} для всіх v1 V1, v2 V2

Прямий добуток графів є граф, у якого V = V1V2,

((c1,v2),(v1,v2))E(v1,v1)E и (v2,v2)E2

Для дводольного графа необхідно і достатньо, щоб він не містив циклів непарної довжини.

Нехай G = (V, Е) - двочастковий граф, С - один з його циклів довжини k. Фіксуємо вершину v1 С і проходимо цикл, починаючи з v1. Нехай це вершини v1, v2, ..., vk. Оскільки кінці кожного ребра лежать в різних частках, то k - парне число.

Нехай G = (V, Е) - зв'язний і всі його цикли парної довжини. Визначимо розбиття V = V1 V2 наступним чином: Фіксуємо довільну вершину v1 V і включаємо її в V1. Тепер включаємо u V1 d (u, v1) - парне число. Решта вершини включаємо в V2.

Покажемо, що граф G двочастковий. Нехай, навпаки, існує ребро (v ', v "), де v', v" V1. Отже, d (v1, v '), d (v1, v ") - парних. Ребро (v', v") дає цикл непарної довжини, що містить шлях від v1 до v ', ребро (v', v "), шлях від v "до v1. Аналогічно показуємо, що немає ребер (v ', v "), v', v" V2.

Також в теорії графів існую можливість використання різних алгоритмів пошуку наступної ланки.

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

Ейлеров цикл в графі існує тоді і тільки тоді, коли граф зв'язний і усі його вершини мають парні ступеня.

Алгоритм у вигляді дерева - алгоритм передбачає побудову дерева рішень і рух по його вітках.

Похибка такого алгоритму рівна 1.

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

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

Приведені методи не дають повністю точних і не у всіх задачах їх можна використовувати.

1.3 Основні поняття теорії дерев рішень

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

Дерева рішень - один з таких методів автоматичного аналізу даних. На сьогоднішній день існує значна кількість алгоритмів, що реалізують дерева рішень CART, C4.5, NewId, ITrule, CHAID, CN2 і т.д.[34].

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

- головну мету або вершину дерева цілей (для промисловості це може бути, наприклад, випуск продукції);

- підпорядковані їй другорядні цілі першого, другого і наступних рівнів (гілки дерева).

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

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

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

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

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

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

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

У найбільш простому вигляді дерево рішень - це спосіб представлення правил в ієрархічній, послідовної структурі. Основа такої структури - відповіді "Так" або "Ні" на ряд питань[37].

Інтуїтивність дерев рішень. Класифікаційна модель, представлена ??у вигляді дерева рішень, є інтуїтивною і спрощує розуміння розв'язуваної задачі. Результат роботи алгоритмів конструювання дерев рішень, на відміну, наприклад, від нейронних мереж, що представляють собою "чорні ящики", легко інтерпретується користувачем. Це властивість дерев рішень не тільки важливо при віднесенні до певного класу нового об'єкта, але і корисно при інтерпретації моделі класифікації в цілому. Дерево рішень дозволяє зрозуміти і пояснити, чому конкретний об'єкт відноситься до того чи іншого класу.

Дерева рішень дають можливість видобувати правила з бази даних на природній мові. Приклад правила: Якщо Вік> 35 і Доход> 200, то видати кредит.

Дерева рішень дозволяють створювати класифікаційні моделі в тих областях, де аналітику досить складно формалізувати знання.

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

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

Розроблено ряд масштабованих алгоритмів, які можуть бути використані для побудови дерев рішення на надвеликих базах даних; масштабованість тут означає, що зі зростанням числа прикладів або записів бази даних час, що витрачається на розрахунок, тобто побудова дерев рішень, зростає лінійно. Приклади таких алгоритмів: SLIQ, SPRINT.

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

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

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

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

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

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

Друга стратегія полягає у використанні набору процедур, що визначають "відповідний розмір" дерева, вони розроблені Бріманом, Куілендом та ін. в 1984 році. Однак, як відзначають автори, не можна сказати, що ці процедури доступні початкуючому користувачеві.

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

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

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

Зупинка - такий момент в процесі побудови дерева, коли слід припинити подальші розгалуження.

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

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

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

Існує ще ряд правил, але слід зазначити, що жодне з них не має великої практичної цінності, а деякі застосовні лише в окремих випадках.

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

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

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

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

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

Жоден алгоритм побудови дерева не можна апріорі вважати найкращим або досконалим, підтвердження доцільності використання конкретного алгоритму має бути перевірено і підтверджено експериментом.

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

1.4 Основні поняття теорії керування

Під керуванням розуміється процес такого впливу на деяку систему або об`єкт (об`єкт керування), при якому стан системи або об`єкта змінюється «в потрібну сторону»[5].

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

Об'єкт керування розглядається в контексті як завгодно складної системи, що перетворює вхідні управляючі впливу U(t) у вихідні сигнали (траєкторії) V (t), що характеризують стан об'єкта керування в момент часу t. Очевидно, що реальний об'єкт керування може мати безліч входів і виходів, що визначають його функціональне взаємодія з зовнішнім середовищем. Всі ці канали зв'язку з середовищем на рис. 1.2 не показані. зображені лише ті входи і виходи, які є істотними для формулювання завдання керування.

Рисунок 1.2 - Система керування

Об'єкт керування та пристрій керування, який впливає на нього, утворюють систему керування. Передбачається, що на об'єкт керування діють також обурення Е(t), що змінюють, як правило, в непередбачуваному напрямку, основні характеристики об'єкта керування.

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

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

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

Завдання стабілізації полягає в підтримці деяких вихідних (керованих) характеристик об'єкта керування на заданих рівнях незважаючи на постійно діючі обурення Е(t):

Завдання виконання програми, або завдання програмного керування, виникає, коли необхідно забезпечити наперед задані траєкторії V (t). Інакше кажучи, необхідно «примусити» об'єкт керування змінювати свої керовані характеристики в часі за заданим законом, за певною програмою V * (t).

У завданнях стеження основна проблема зводиться до формування такої вихідний траєкторії V (t) керованого об'єкта, яка як можна більш точно апроксимувати б іншу, заздалегідь не відому траєкторію V * (t).

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

Коли говориться про завдання оптимізації в теорії керування, то мається на увазі завдання реалізації деяких оптимальних (по заданому критерію) вихідних траєкторій керованої системи.

В теорії керування виділяють декілька основних принципів керування:

- принцип жорсткого (розімкнутого) керування передбачає відсутність зворотного зв'язку в загальній схемі керування. Такі системи керування без зворотного зв'язку називаються розімкнутими. найчастіше вони застосовуються для цілей програмного керування. Принцип жорсткого керування проілюстрований на рис. 1.3, де представлена система жорсткого керування, вирішальна завдання програмного керування (завдання виконання заданої програми). Тут мета керування V*(t) задає бажану програму зміни стану об'єкта в часі. Ця програма передається керуючому пристрою для побудови необхідного керування U (t), В результаті такого керування стан об'єкта повинно змінюватися за законом V {t). Система керування прагне забезпечити рівність

для будь-якого моменту часу.

Рисунок 1.3 - Система жорсткого програмного керування

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

Рисунок 1.4 - Замкнута система програмного керування

У пристрої керування порівнюється бажане V*(t) і дійсне значення функції V(t). Це дозволяє визначити, наскільки стан об'єкта відрізняється від запланованого (задається програмою V*(t)).

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

1.5 Основні поняття теорії оптимізації

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

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

Керовані змінні - це такі параметри задачі, значення яких можна змінювати.

Цільова функція - це функція, що пов'язує керовані змінні та критерії таким чином, що дозволяє обчислити значення критерію при довільних значеннях керованих змінних[48].

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

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

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

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

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

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

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

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

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

Знайти max (min) f (x) за умови, що змінна х (точка х) пробігає деякий заданий безліч Х:

f(x) = max(min),хIХ. (1.1)

Рішення завдання досягається застосуванням певної математичної процедури, яка полягає в послідовному наближенні раціональних варіантів, відповідних вибраній комбінації чинників, до єдиного оптимального плану[25].

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

2 РОЗРОБКА МЕТОДУ ВИБОРУ ШЛЯХУ ПРЯМУВАННЯ

2.1 Аналіз функціональних вимог до методу вибору шляху прямування

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

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

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

- точки завантаження або розвантаження промислового робота;

- точки поворотів на траєкторії руху;

- точки очікування команди.

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

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

- розрахунок усіх можливих напрямків прямування робота з точки відправлення до точки призначення.

- вибір найбільш коректного шляху прямування з урахуванням параметрів прямування.

До основних параметрів прямування можна віднести:

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

- обмеження швидкості робота на певних ділянках ПЦ;

- обмеження габаритних розмірів робота з вантажем або без нього;

- наявність перешкод на траєкторії прямування;

- відстань та напрямок руху робота до наступної точки;

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

Список параметрів може бути розширений в залежності від завдань.

2.2 Обґрунтування можливих критеріїв пошуку траєкторії руху

Більшість сучасних систем побудовані з використанням одного з методів пошуку: теорії графів або теорії дерева рішень.

Рисунок 2.1 - Схема промислового цеху

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

– кружечками позначені контрольні точки для роботизовано системи постачання;

- прямокутником з написом «Станок №…» позначені промислові потужності цеху (станки);

- прямокутником з стрілочкою вверх та вниз позначені місця завантаження заготівок на станок або відвантаження оброблених деталей;

- прямокутником з стрілочкою вниз позначені точки очікування команд.

Таким чином можна розрахувати найкоротший шлях прямування між двома точками напряму.

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

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

Точки 1, 3, 7, 11 і 10 є точками завантаження/відвантаження для складу, станка №1, станка №2, станка №3 і станка №4 відповідно, але ці точки також можуть виконувати роль точок повороту траєкторії руху.

На рисунку 2.2 вказані основні можливі маршрути прямування між сусідніми контрольними точками, де кружечками позначені контрольні точки для роботизовано системи постачання з порядковими номерами; стрілочками позначені локальні маршрути.

Кожен локальний (маршрут лише між двома сусідніми точками по прямій лінії) далі позначається як Мл(пл)(кл), де п - точка відправлення, к - точка прибуття.



Рисунок 2.2 - Основні можливі маршрути прямування між сусідніми контрольними точками

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

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

Наприклад щоб доставити обладнання зі складу (точка №1) до станку№1(точка №3) глобальний маршрут матиме вигляд:

Мг(1)(3)= Мл(1)(4) ->Мл(4)(3).

Роботу буде потрібно пройти два локальних маршрути: Мл(1)(4) і Мл(4)(3).

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

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

- можливість обмеження певних параметрів робота на певних локальних маршрутах таких, як максимальна швидкість руху робота на локальному маршруті та інших;

- здатність ще на етапі прорахунку глобального маршруту руху виключити ті локальні маршрути, які не задовольняють певним параметрам робота: невідповідність максимальних габаритів на маршруті даним габаритам робота (вантаж може біти негабаритним і змінювати загальні габарити робота підчас руху) та інші;

- вибір глобального маршруту у відповідності до пріоритетності виконання завдання і завантаження на маршрутах (наприклад роботу поставлене завдання доставити певний вантаж з точки А в точку Б, існує два можливих глобальних маршрути виконання - перший скоріше, але на маршруті частіше виникають перешкоди, другий більш повільний, але на ньому перешкоди бувають рідше, ніж на першому; якщо пріоритет завдання вказаний, як мінімальний, то робот буде орієнтуватись не на мінімальний час виконання і мінімальні затрати, а на більш надійний маршрут);

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

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

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

Коренем дерева буде точка №1, завчасно будується дерево можливих рішень руху робота по цеху. Для нашого цеху дерево рішень має вигляд (рис.2.3).

Рисунок 2.3 - Дерево рішень

На рисунку 2.3 овалом позначені контрольні точки з порядковим номером кожної контрольної точки; стрілочками позначені локальні маршрути між сусідніми контрольними точками.

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

До основних критеріїв відносяться: час проходження локального маршруту на максимальній швидкості в секундах t, довжина маршруту l в метрах, мінімальна ширина на маршруті в метрах w, мінімальна висота на маршруті в метрах h, завантаженість маршруту p (мінімум, середня, максимум, заблокований), максимальна швидкість на маршруті в кілометрах за годину v.

Таблиця 2.1 - Основні критерії дерева рішень

Маршрут/ точка	t, c	l, м	w, м	h, м	p	v, км/год
Мл(1)(2)	14	70	12	3	мінімальна	5
Мл(1)(4)	5	25	13	2,7	мінімальна	5
Мл(2)(8)	5	25	15	2,7	мінімальна	5
Мл(8)(7)	3	15	15	2,8	мінімальна	5
Мл(4)(3)	6	30	14	3	мінімальна	4
Мл(4)(5)	4	20	15	3	мінімальна	5
Мл(5)(6)	3	15	-	3	максимум	3
Мл(5)(9)	3	15	-	2,6	максимум	4
Мл(7)(6)	4	20	15	2,5	мінімальна	4
Мл(6)(10)	3	15	-	3	середня	5
Мл(9)(10)	3	15	-	3	середня	6
Мл(9)(11)	2	10	-	3	середня	6
Мл(11)(о)	3	15	-	2,9	середня	6
Мл(10)(о)	2	10	-	2,9	середня	6

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

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

Таблиця 2.2 - Основні часові параметри при поворотах

Кут повороту, о	Наявність навантаження, tпов, с
	Наявне	Не наявне
90	2,5	1,5
180	5	3
270	7,5	4,5
360	10	6

Якщо в контрольній точці робот не виконує поворотів tпов=0.

Для підвищення точності розрахунків треба врахувати час розгону робота до максимальної для даної ділянки швидкості

tроз=0,5с.

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

; (2.1)

де: tзаг - загальний час;

tі - основний час проходження локального маршруту;

tпов - час повороту;

tроз - час розгону.

Розрахувати довжину глобального маршруту можна за формулою:

;(2.2)

де - загальна довжина глобального маршруту;

- довжина і-того локального маршруту.

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

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

3 РОЗРОБКА АЛГОРИТМІЧНОГО ТА ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ МЕТОДУ ПОШУКУ ШЛЯХУ ПРЯМУВАННЯ

3.1 Основні вимоги до розробки алгоритмів

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

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

- кількість контрольних точок, які потрібно пройти роботу для досягнення поставленої перед ним мети - транспортування об'єктів з точки А в точку Б;

- значення певних параметрів глобального маршруту (ГМ), які розраховані з урахуванням параметрів локальних маршрутів (ЛМ), які включені в даний ГМ, за певним законом;

- оціночні значення кожного ГМ, які визначені після аналізу всіх параметрів, заданих для кожного ЛМ, який входить в даний ГМ.

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

3.2 Розробка алгоритму пошуку всіх можливих глобальних маршрутів з точки початку маршруту до точки його закінчення

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

Даний алгоритм зображений на рисунку А.1. Вхідними даними для алгоритму є лише точки початку ГМ та точка його кінця.

Метод, на основі якого побудований алгоритм, використовує теорію графів для пошуку шляхів прямування. Під контрольною точкою в даному методі розуміється певна вершина. Дві вершини (контрольні точки) є суміжними, якщо існує з'єднуюче їх ребро. Під ребром в даному методі розуміється деякий локальний маршрут промислового цеху (рисунок 2.2). Глобальний маршрут - це певний шлях, послідовність ребер e1, е2, ... , еm, така, що ei, ei +1 мають спільну вершину. Для нашого завдання логічно використовувати такий підхід, при якому жодна з вершин не з'являється більше одного разу, отже шлях, пошуком котрого займається алгоритм, є простим.

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