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

Міністерство освіти і науки, молоді та спорту України КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ БУДІВНИЦТВА І АРХІТЕКТУРИ

05.01.01 - прикладна геометрія, інженерна графіка

УДК 514.18

Автореферат

дисертації на здобуття наукового

ступеня кандидата технічних наук

Геометричне моделювання траєкторії переміщення фігури на площині серед перешкод

з використанням R-ФУНКЦій

Морозова Галина Вікторівна

Київ 2011

Дисертацією є рукопис.

Робота виконана в Національному університеті цивільного захисту України Міністерства надзвичайних ситуацій України.

Науковий керівник: - доктор технічних наук, професор Куценко Леонід Миколайович, професор кафедри інженерної та аварійно-рятувальної техніки, Національний університет цивільного захисту України (м. Харків)

Офіційні опоненти:

- доктор технічних наук, професор Шоман Ольга Вікторівна, завідувач кафедри геометричного моделювання та комп'ютерної графіки, Національний технічний університет «Харківський політехнічний інститут» (м. Харків)

- кандидат технічних наук, доцент Мацулевич Олександр Євгенійович, доцент кафедри прикладної геометрії і інформаційних технологій проектування, Таврійський державний агротехнологічний університет (м. Мелітополь)

Захист відбудеться " 19 " жовтня 2011 р. о 13⁰⁰ годині на засіданні спеціалізованої вченої ради Д 26.056.06 у Київському національному університеті будівництва і архітектури за адресою: 03680, Київ-680, Повітрофлотський проспект, 31, ауд. 466.

З дисертацією можна ознайомитися в бібліотеці Київського національного університету будівництва і архітектури за адресою:03680, м. Київ, Повітрофлотський проспект, 31.

Автореферат розісланий " 14 " вересня 2011 р.

Вчений секретар спеціалізованої вченої ради О.А. Бондар

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

траєкторія прямокутний площина

Актуальність теми. Проблеми сучасної прикладної геометрії пов'язані з дослідженнями широкого класу кривих ліній і поверхонь, що зводяться до необхідності їх опису в рамках конкретно заданих умов. При цьому ефективність опису залежить не тільки від алгоритму розв'язання завдання і його програмної реалізації, але й від вибору теоретичної моделі. Для опису ліній і поверхонь широко використовують способи Безьє, Кунса, сплайнів, R-функцій тощо. Ці способи ефективні переважно у випадках детермінованого задання вхідних даних. Але існує клас задач, коли криві лінії і поверхні задані в описовій формі, яка важко формалізується. Прикладом є визначення кривої лінії, що сполучає на площині дві задані точки, за умови її проходження між фігурами цієї площини, що не перетинаються. Науковою темою є розробка способу опису зазначеної лінії залежно від розташування та геометричної форми фігур-перешкод. Для цього необхідно запропонувати інструмент дослідження, який полягає у застосуванні спеціально побудованої поверхні, подібної графіку віртуальної потенціальної функції. Ця поверхня має бути залежною від розташування фігур-перешкод та кінцевої точки руху. Тому актуальності набуває дослідження властивостей побудованої поверхні з метою розрахунку на практиці траєкторії переміщення по площині мобільного робота з урахуванням кола, яке обмежує його габарити (далі ? габаритного кола), і перешкод у вигляді фігур, що належать цій площині.

Зв'язок роботи з науковими програмами, планами, темами. Роботу виконано на кафедрі інженерної та аварійно-рятувальної техніки Національного університету цивільного захисту України в рамках науково-дослідної теми «Підвищення ефективності застосування засобів малої механізації в підрозділах МНС» (№ державної реєстрації 0109U003061).

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

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

Для досягнення мети у дисертації поставлено такі основні задачі:

виконати огляд робіт з розрахунку шляху робота серед перешкод та способів ідентифікації об'єкта (контейнера) на складській площадці;

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

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

розробити спосіб побудови та опису віртуальних потенціальних функцій і знаходження проміжних точок ітерації в алгоритмі визначення траєкторії переміщення «точкового» робота;

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

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

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

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

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

Методи дослідження: елементи аналітичної та прикладної геометрії, обчислювальної математики, інформатики та комп'ютерної графіки, теорії R-функцій, комп'ютерного моделювання в середовищі Maple.

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

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

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

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

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

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

Вірогідність та обґрунтованість результатів підтверджується доведенням тверджень, аналітичними перетвореннями за допомогою пакета Мaple, а також побудованими за допомогою комп'ютера зображеннями результатів трасування для тестових прикладів і розрахунками у процесі впровадження.

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

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

Апробація результатів дисертації. Основні положення дисертаційної роботи доповідалися та обговорювались на: міській секції графіки ХДУХТ під керівництвом д.т.н., проф. Ю.М. Тормосова (м. Харків, 2010 р); науково-практичних конференціях «Геометричне і комп'ютерне моделювання: енергозбереження, екологія, дизайн» (м. Сімферополь, 2009 р.); науково-практичній конференції «Сучасні проблеми геометричного моделювання» (м. Харків, 2009 р.); науково-практичній конференції «Сучасні проблеми геометричного моделювання» (м. Одеса, 2010 р.); науково-практичній конференції «Сучасні проблеми геометричного моделювання» (м. Мелітополь, 2009, 2010 рр.); науковому семінарі кафедри інженерної та аварійно-рятувальної техніки НУЦЗУ під керівництвом д.т.н., проф. О.М. Ларіна (м. Харків, 2007, 2010 рр.); науковому семінарі кафедри нарисної геометрії та графіки НТУ «ХПІ» під керівництвом д.т.н., доц. О.В. Шоман (м. Харків, 2009, 2010 рр.); науковому семінарі аспірантів при КНУБА під керівництвом д.т.н., проф. О.Л. Підгорного і д.т.н., проф. С.М. Ковальова

(м. Київ, 2010 р.); науковому семінарі кафедри прикладної математики та інформаційних технологій проектування ТДАТУ під керівництвом д.т.н., проф. А.В. Найдиша (м. Мелітополь, 2010, 2011 рр.).

Публікації. За результатами досліджень опубліковано 7 робіт, 7 - у виданнях, які рекомендовано ВАК України; з них всі - одноосібно, та одержано позитивне рішення про видачу деклараційного патенту на корисну модель (реєстраційний номер заявки u 2011 01775).

Структура і обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел зі 127 найменувань та додатків. Робота містить 184 сторінки тексту та 128 рисунки.

Основний ЗМІСТ РОБОТИ

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

У першому розділі наведено огляд алгоритмів розрахунку траєкторії мобільних роботів серед перешкод. В роботах Е. Селіфонова, А. Тихомирова зазначено, що серед таких алгоритмів популярними є хвильовий алгоритм, алгоритми із елементами евристики, а також алгоритм пошуку шляхів з умовною назвою «Алгоритм A*». Хвильовий алгоритм базується на ідеї формування уявної хвилі зі стартової точки, що поступово заповнює площину, у підсумку доходячи до точки цілі. До переваг хвильового алгоритму відносять простоту реалізації, хоча така перевага досягається не раціонально, адже пошук, замість того, щоб бути спрямованим до цілі, здійснюється рівномірно у всіх напрямах. Модифікацією хвильового алгоритму є двохвильовий алгоритм, коли «запускаються» дві хвилі: зі стартової й цільової точок. Алгоритм працює до моменту зустрічі двох хвильових фронтів. На базі цього було створено алгоритм Best-First Search з метою виправити основний недолік попередніх алгоритмів, а саме: ігнорування пріоритетного напряму до цілі та використання евристичного пошуку. До недоліків відносять визначення шляхів траси, які вигинаються навколо перешкоди (а не відрізки прямих) і які необхідно інтерпретувати системою керування робота.

Найбільш застосовним алгоритмом пошуку оптимальних шляхів вважається «Алгоритм A*», який поєднує у собі переваги попередніх алгоритмів і використовує евристики (B-F Search). До його недоліків відносять, по суті, суб'єктивний фактор - робота алгоритму залежить від якості евристичного наближення, яке формулює фахівець: якщо наближення невдале, то спостерігається погіршення роботи алгоритму.

Рис. 1. Трасування шляху робота методом віртуальних потенціалів

Кращий з алгоритмів трасування мобільних роботів базується на методі віртуальних потенціальних полів. Цей метод досліджено у роботах А.К. Платонова, А.А. Кирильченка, М.А. Колганова та інших. Тут для навігації використовується мнемонічний прийом віртуальної електростатики, згідно з яким навколишні об'єкти ніби притягують або відштовхують мобільного робота у процесі його руху. При цьому вважається, що точка цілі має деякий заряд «плюс»; фігури-перешкоди і рухома точка-робот мають заряди «мінус»; місця розташування точки цілі й перешкод є фіксованими (рис. 1). Тоді, під дією віртуальних електростатичних сил, рухома точка буде відштовхуватися від перешкод і притягуватися до цілі і, за певних умов, має її досягти.

Полями рівних потенціалів можна вважати геометричні об'єкти, наведені в роботах О.В. Шоман. Еквідистантні множини точок за допомогою поверхонь однакового нахилу досліджувалися в роботах С.Ф. Пилипаки, Д.Г. Войтюк, Д.Ф. Кучкарової, М.С. Водянського, І.Ю. Хименка.

Недоліки методу віртуальних потенціальних полів:

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

- у процесі визначення траси приховано геометричну суть розрахунків;

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

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

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

Сучасною технологією автоматичної ідентифікації контейнерів на складській площадці є радіочастотна ідентифікація (RFID). RFID-системи застосовуються в різноманітних випадках, коли є потреба в оперативному і точному контролі, відстеженні й обліку численних переміщень контейнерів. У роботах М.Ю. Васильєва, П.А. Аркіна, І.Ю. Крилова наведено варіант оптимізації роботи контейнерного терміналу за допомогою наявності на площадці мобільного терміналу збору даних, одержуваних RFID-системою. Мобільний термінал, будучи підключеним до локальної мережі компанії через зв'язок Wi-Fi, дозволяє відобразити інформацію на екрані комп'ютера оператора.

Недоліки ідентифікації контейнерів на складі за RFID-технологією:

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

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

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

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

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

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

Рис. 2. Система активованих датчиків, що визначають прямокутник

Оберемо на площадці складу прямокутну систему координат Oxy. Тоді положення кожного датчика на площадці визначатиметься двома цілими числами - його номерами по осі Ох і по осі Оу. В результаті на екрані комп'ютера оператора стануть відомими координати опорних точок (відповідно ті, де «спрацюють» геркони), в околі яких проходитиме певна сторона прямокутника.

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

а) ліву:

x1 = 3: y1 = 6:

x2 = 3: y2 = 7:

x3 = 4: y3 = 8:

x4 = 4: y4 = 9:

x5 = 5: y5 = 10:

x6 = 5: y6 = 11:

x7 = 5: y7 = 12:

x8 = 6: y8 = 13:

x9 = 6: y9 = 14:

x10 = 6: y10 = 15:

б) праву:

x1 = 9: y1 = 3:

x2 = 9: y2 = 4:

x3 = 10: y3 = 4:

x4 = 10: y4 = 5:

x5 = 10: y5 = 6:

x6 = 11: y6 = 7:

x7 = 11: y7 = 8:

x8 = 12: y8 = 10:

x9 = 12: y9 = 11:

x10 = 13: y10 = 13:

в) верхню:

x1 = 7.: y1 = 15.:

x2 = 8.: y2 = 15.:

x3 = 9.: y3 = 14.:

x4 = 10.: y4 = 14.

x5 = 11.: y5 = 14.:

x6 = 11.: y6 = 13.:

x7 = 12.: y7 = 13.:

x8 = 13.: y8 = 13.:

г) нижню:

x1 = 3.: y1 = 6.:

x2 = 3.: y2 = 5.:

x3 = 4.: y3 = 5.:

x4 = 5.: y4 = 5.:

x5 = 6.: y5 = 4.:

x6 = 7.: y6 = 4.:

x7 = 8.: y7 = 3.:

x8 = 9.: y8 = 3.:

В роботі наведено спосіб складання рівняння прямокутника (в основі контейнера) за інформацією про його сторони, одержаною з датчиків. Для складання рівнянь сторін прямокутника застосовано метод Хафа, різновид якого запропоновано А.В. Найдишем (метод віднесення до простору параметрів). Суть методу полягає у відображенні точок площини Oxy на площину Opq параметрів p i q. Точку А(x, y) площини Oxy можна відобразити у синусоїду на площині Opq за допомогою нормального рівняння прямої

x cos p + y sin p - q = 0. (1)

Рівняння (1) задає відображення всієї площини Oxy на смугу 0 p < 2 уявної площини Opq. Коли декілька точок розташовані на одній прямій, то їх образи - синусоїди повинні перетнутися в одній точці. Тобто коли точки (x₁, y₁), (x₂, y₂), ... (x_m, y_m) лежать на одній прямій, то на площині Opq знайдеться така точка (p₀, q₀), що в ній при k = 1...m перетнуться синусоїди

x_k cos p + y_k sin p - q = 0. (2)

Ступінь «купчастості» розташування точок попарних перетинів синусоїд можна обрати в якості критерію «віддаленості» обраної множини точок від шуканої прямої. Отже, за критерій «наближеної» належності сім'ї точок (x, y) прямій x cos p₀ + y sin p₀ - q₀ = 0 можна обрати радіус -околу точки (p₀, q₀) на площині Opq. Згідно методу віднесення до простору параметрів для точок тесту побудуємо на площині Opq синусоїди і визначимо координати точок, в околі яких перетинається їх максимальне число. На рис. 3 зображено синусоїди для точок в околі всіх чотирьох сторін прямокутника, де колами позначено околи максимальної кількості перетинів синусоїд.

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

Рис. 3. Синусоїди для точок в околах всіх сторін прямокутника

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

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

А саме, коли апріорі відомо, що аналізується розташування прямокутника, то повинні бути однаковими координати p центрів кіл 1 і 2, а також кіл 3 і 4. Крім того, однаковими мають бути кути нахилу прямих, проведені через центри кіл 1 і 3, а також кіл 2 і 4 (рис. 3). За великих розбіжностей зазначених величин їх доцільно осереднити.

В результаті виконання програми (складеної для середовища пакета Maple) одержано координати точок (p, q) для опису сторін прямокутника:

а) лівої: p = 2.72; q = 0; б) правої: p = 2.75; q = -7.3;

в) верхньої: p = 1.2; q = 16.7; г) нижньої: p = 1.1; q = 6.48.

Отже, рівняння сторін прямокутника одержуємо у вигляді

x cos 2,72 + y sin 2,72 = 0;

x cos 2,75 + y sin 2,75 =-7,3; (3)

x cos 1,2 + y sin 1,2 = 16,7;

x cos 1,1 + y sin 1,1 = 6,48.

На рис. 4 сумісно зображено сторони чотирикутника, описані рівняннями (3). Тут терміном «прямокутник» навмисно замінено термін «чотирикутник», щоб підкреслити результат наближення. За формулами аналітичної геометрії обчислюємо точку перетину діагоналей чотирикутника x₀=7,9 i y₀=9,4, а також величини його сторін - довжину a = 9,9 та ширину b = 7 умовних одиниць. Перенесемо точку (х₀, у₀) в початок координат і повернемо чотирикутник на кут w = 1,16 радіан. В результаті одержуємо «стандартне» положення чотирикутника (рис. 5). Непаралельність сторін чотирикутника ілюструє наявність похибок, внесених внаслідок дискретного розташування датчиків, які, втім, для розглянутого впровадження не суттєві (осереднення значень тут не проводилося для демонстрації можливостей способу у «чистому» вигляді).

Рис. 4. Сумісне зображення сторін чотирикутника

Рис. 5. Стандартне положення чотирикутника

Зазначені перенос і поворот здійснюються за допомогою формул перетворення координат (тут збережено синтаксис мови Maple): w = 1.16;

X = x*cos(w) - y*sin(w) + x0;

Y = x*sin(w) + y*cos(w) + y0;

f1 = X*cos(2.72) + Y*sin(2.72) = 0; (4)

f2 = X*cos(2.75) + Y*sin(2.75) = -7.3;

f3 = X*cos(1.2) + Y*sin(1.2) = 16.7;

f4 = X*cos(1.1) + Y*sin(1.1) = 6.48.

Для стандартного положення чотирикутника в роботі запропоновано опис сім'ї його еквідистант у вигляді:

. (5)

На рис. 6 наведено лінії рівня функції (5) як еквідистанти побудованого прямокутника (a = 9,9; b = 7). За допомогою формул перетворення координат

;

(6)

у початкове положення «повертаємо» прямокутник із «прикріпленими» до нього елементами сім'ї еквідистант (рис. 7).

У роботі наведено описи еквідистант для інших багатокутників.

Рис. 6. Лінії рівня функції (5)

Рис. 7. Еквідистанти прямокутника

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

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

Віртуальну потенціальну функцію для перешкоди у вигляді багатокутника з рівнянням f(x,y) = 0 пропонується описувати у вигляді:

, (7)

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

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

Оберемо на площині прямокутну систему координат Оху, в якій заздалегідь побудовано цифрову модель положень контейнера з відомими координатами кутів прямокутника {[a;b][c;d]}. Сім'ю зовнішніх еквідистант прямокутника за допомогою R-функцій задамо рівнянням:

, (8)

де описи R-кон'юнкції та R-диз'юнкції обрано у вигляді:

=; (9)

=. (10)

Для розрахунку шляху переміщення точки між перешкодами множину N прямокутників {[a_k; b_k][c_k; d_k]} (k=1..N)) опишемо рівнянням:

. (11)

Тоді f(х,у) = const буде описом сім'ї еквідистант об'єднання прямокутників. На рис. 8 наведено приклад еквідистант множини прямокутників, побудованих за координатами їх вершин, які, повертаючись до методу віртуальних потенціальних функцій, умовно можна вважати лініями рівних віртуальних потенціалів.

а)

б

Рис. 8. Прямокутники, побудовані за координатами вершин (а); еквідистанти множини прямокутників (б)

Нехай N прямокутників описано рівняннями f_i(x, y) = 0 вигляду (8). Віртуальну потенціальну функцію, що досягає глобального мінімуму в точці з координатами C(x_C, y_C) і має «пагорби» над відповідними N прямокутниками, слід описувати так:

. (12)

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

Було складено програму побудови траєкторії руху важкої кульки в полі «вертикального» тяжіння по поверхні графіка віртуальної потенціальної функції залежно від положення обраної стартової точки. Особливістю алгоритму є те, що при старті заздалегідь відомою є кінцева точка екстремуму - точка цілі C(x_C, y_C), і на етапах кожної ітерації початкові напрями обираються саме до неї. Задача алгоритму полягає лише у слідкуванні за неперетином траєкторії з «пагорбами» перешкод. У критичних випадках слід здійснювати їх обхід. На відміну від методу градієнтного спуску, при цьому вдалося обійтися без визначення похідних функції. На рис. 10 подано приклади траєкторій як ортогональних проекцій на площину траєкторії кульки залежно від положення стартової точки.

а)

б)

Рис. 9. П'ять прямокутників (а); графік віртуальної потенціальної функції (б)

Рис. 10. Приклади траєкторій залежно від положення стартової точки

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

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

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

При цьому квадрат зі стороною 2R і з «заокругленими» кутами пропонується описати параметричними рівняннями

; (13)

За допомогою формул (8) і (13) можна визначати відстань між прямокутником (контейнером) і «квадратом» (наприклад, профілем будівельної колони).

Якщо вирази для x і y з формули (13) обрати аргументами функції (8), то утвориться функція , мінімум якої дорівнюватиме відстані між прямокутником і «квадратом».

Наприклад, для визначення відстані між кутовими точками графік функції z(t) матиме єдину точку мінімуму (рис. 11). При t = 0 одержуємо значення відстані z₀ = 2, 1967432. А для варіанта визначення відстані між гранями графік функції z(t) матиме не єдину точку мінімуму (рис. 12). При -0,2 < t < 2,54 одержуємо значення відстані z₀ = 1,5.

Рис. 11. Визначення відстані між кутовими точками

Рис. 12. Визначення відстані між гранями

Нехай N прямокутників описані рівняннями вигляду (8). Розглянемо функцію , одержану в результаті підстановки x і y із (13) в кожну функцію . Тоді найменша відстань від «квадрата» до N прямокутників дорівнюватиме мінімуму R-кон'юнкції .

На рис. 13 наведено приклади визначення відповідної відстані.

а б в

Рис. 13. Приклад розташування колони і контейнерів (а); графіки функцій f_і(x,y) (б); графік R-кон'юнкції (в)

Нехай задано два прямокутники, для яких за допомогою R-функцій складено рівняння f₁ (x,y) = 0 та f₂ (x,y) = 0. Тоді відстань між прямокутниками дорівнюватиме подвоєному мінімальному значенню R-кон'юнкції f₁₁f₂.

Рис. 14. Прямокутники з гістограмами відстаней

Таким чином, в околі обраного прямокутника можна побудувати в точках, де досягаються екстремуми R-кон'юнкції, гістограми відповідних відстаней між сусідніми прямокутниками (рис. 14).

В роботі запропоновано новий спосіб трасування робота з габаритним колом радіуса R між множиною прямокутників.

Нехай N прямокутників описано рівняннями f_i(x, y) = 0 вигляду (5). Тоді трасу робота з габаритним колом радіуса R можна визначати з ліній рівня R-диз'юнкції , де критерієм можливості проходження робота по трасі є виконання нерівності F(x, y) < R .

Приклад. Для прямокутників на рис. 9, 10 є графіки їх сукупності (рис. 15, а), а також графік R-диз'юнкції (рис. 15, б).

а б

Рис. 15. Графік сукупності прямокутників з рис. 9, 10 (а); графік R-диз'юнкції для цих прямокутників (б)

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

Рис. 16. Припустимі шляхи руху робота, залежно від габаритного кола радіуса R

Далі розглянемо віртуальну потенціальну функцію для визначення смуги переміщення робота. Для цього поєднаємо спосіб трасування точки по графіку віртуальної потенціальної функції (рис. 9, 10), а також трасування габаритного кола по площині (рис. 15, 16). В результаті одержимо графік потенціальної функції з виділеними на ньому смугами (рис. 17).

Рис. 17. Графік потенціальної функції з циліндричними ортогональними поверхнями, що спираються на контури смуг на площині

Зазначені смуги одержують за допомогою циліндричних ортогональних поверхонь із напрямними - контурами смуг на площині (рис. 16). Тобто на графіку потенціальної функції смуги відповідають певним відстаням від прямокутників і окреслені циліндричними поверхнями, що спираються на відповідні «колірні» смуги площини (рис. 18).

а б

Рис. 18. Проекції смуг на графік потенціальної функції для габаритного радіуса: малого (а); великого (б)

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

Траєкторію робота з початком в точці S(x_S,y_S) доцільно визначати за допомогою складеного алгоритму, головними моментами якого є наступні.

1. За допомогою наведеного в роботі способу побудувати віртуальну потенціальну функцію z = z(x,y) і визначити необхідну кількість її ліній рівня.

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

3. За обраним напрямом визначити точку К на «нижчій» лінії рівня потенціальної функції, а також обрати дві допоміжні точки К₁ і К₂, розташовані на перпендикулярі до прямої SK по різні боки від точки К (рис. 19).

Рис. 19. Вибір допоміжних точок К₁ і К₂

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

4. Залежно від різниці значень функції z(x,y) в допоміжних точках К₁ і К₂ зробити висновок про необхідність або напрям обходу перешкоди.

5. З урахуванням прийнятого рішення перейти до пункту 2.

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

1. З використанням методу Хафа описати рівняннями у неявному вигляді множину прямокутників за координатами вузлових точок, розташованими на площині в околах їх сторін.

2. За допомогою R-функцій описати сім'ю еквідистант відносно множини прямокутників для визначення відстаней між ними.

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

4. Знайти проміжні точки ітерації в процесі визначення траєкторії цільового переміщення «точкового» робота по графіку віртуальної потенціальної функції.

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

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

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

ВИСНОВКИ

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

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

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

При цьому отримано результати, що мають науково-практичну цінність:

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

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

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

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

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

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

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

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНО У ТАКИХ РОБОТАХ

1. Морозова Г.В. Автоматичний вибір шляху руху робота за допомогою різновидів методу потенціалів / Морозова Г.В. // Прикладна геометрія та інженерна графіка. - Київ: КНУБА, 2009.- Вип. 82. - С.283-289.

2. Морозова Г.В. Геометрична інтерпретація методу потенціалів для трасування шляху мобільного робота / Морозова Г.В. // Прикладна геометрія та інженерна графіка. - Київ: КНУБА, 2010.- Вип. 85. - С.65-70.

3. Морозова Г.В. Вибір шляху робота між точками площини за умови обходу прямокутних перешкод / Морозова Г.В. // Геометричне та комп'ютерне моделювання. - Харків: ХДУХТ, 2010. - Вип.27. - С. 93-98.

4. Морозова Г.В. Мінімізація потенціальної функції двох змінних методом Хука-Дживса / Морозова Г.В. // Праці Таврійського державного агротехнологічного університету. - Мелітополь: ТДАТУ, 2010. - Вип.4. -Т.47. - С.130-136.

5. Морозова Г.В. Порівняння методів мінімізації потенціальної функції двох змінних / Морозова Г.В. // Праці Таврійського державного агротехнологічного університету. - Мелітополь: ТДАТУ, 2010. - Вип.4. - Т.48. - С.117-123.

6. Морозова Г.В. Метод визначення траєкторії переміщення мобільного робота на площині серед перешкод / Морозова Г.В. // Автомобильный транспорт. - Харьков: ХНАДУ, 2010. - Вып.27. - С.121-126.

7. Морозова Г.В. Опис положення контейнера для алгоритму трасування шляху мобільного робота / Морозова Г.В. // Інформаційно-керуючі системи на залізничному транспорті. - Харків: УкрДАЗТ, 2011. - Вип.1. - С.3-11.

АНОТАЦІЯ

Морозова Г.В. Геометричне моделювання траєкторії переміщення фігури на площині серед перешкод з використанням R-функцій. - Рукопис.

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

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

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

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

АННОТАЦИЯ

Морозова Г.В. Геометрическое моделирование траектории перемещения фигуры на плоскости среди препятствий с использованием R-функций. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.01.01 - Прикладная геометрия, инженерная графика. - Киевский национальный университет строительства и архитектуры, г. Киев, Украина, 2011.

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

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

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

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

Ключевые слова: мобильный робот, траектория движения робота, габаритный круг робота, виртуальная потенциальная функция, R-функция.

ANNOTATION

Morozova G.V. Geometric modeling of movement trajectory of shape on a plane among obstacles using R-functions. - Manuscript.

Dissertation for seeking the scientific degree of candidate of technical sciences on the specialty 05.01.01 - Applied geometry, engineering graphics. - Kyiv National University of Engineering and Architecture, Kiev, Ukraine, 2011.

Dissertation is devoted to development of the calculation method of curve shape on the plane, which is the shor path connecting two given points of the plane and passes between the obstacles - rectangles, described by equations in implicit form for the coordinates of nodal points; method is based on the potential use of virtual functions and R-functions. The aim of study is the development of an algorithm for calculating the movement trajectories on the plane among obstacles for the mobile robot accounting its overall dimensions circle.

It is developed the ways of construing the potential virtual functions and search of passing points of iteration in the process of focus point movement till minimum, and defining the lanes between obstacles gone by the mobile robot with the given overall circle. The method based on this is elaborated for construing the potential virtual function which allows to define the lanes between obstacles gone by the mobile robot accounting its overall circle.

Results of research are presented for introduction at Prilutsk factory of fire and special engineering when designing robotic systems trace in emergency and in the system of computer-aided placement of containers in the company "Feodosia sea trade port", in teaching process of the National University of Civil Defense of Ukraine.

Keywords: mobile robot, the trajectory of the robot movement, the overall circle of robot, virtual potential function, R-function.

Размещено на Allbest.ru

...