Область наук:
  • Математика
  • Рік видавництва: 2007
    Журнал: Известия Південного федерального університету. Технічні науки
    Наукова стаття на тему 'Алгоритм навігації адаптивних мобільних роботів по автоматично формується карті в умовах динамічно мінливого зовнішнього середовища'

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

    ?5. Батищев ДМ. Генетичні алгоритми вирішення екстремальних задач: Навчальний посібник. - Воронеж, 1995. - 69 с.

    6. Дуккардт А.Н. Методи генетичного пошуку для мультіхромосомних уявлень / VII всеукраїнська наукова конференція студентів та аспірантів, Технічна кібернетика, радіоелектроніка та системи управління. - Таганрог: Изд-во ТРТУ, 2004. - С. 108 -109.

    7. J. Cong, C. Wu, "Global Clustering-Based Performance-Driven Circuit Partitioning", Proc. ISPD, 2002.

    8. W.E. Donath et al, "Timing Driven Placement Using Complete Path Delays", Proc. ACM / IEEE DAC, 1990..

    9. G. Karypis, R.Aggarwal, V.Kumar, S. Shekhar, "Multilevel Hypergraph Partitioning: Application in VLSI domain", Proc. ACM / IEEE DAC, 1997..

    10. J. Minami, T.Koide, S.Wakabayashi, "An Iterative Improvement Circuit Partitioning Algorithm under Path Delay Constraints", IEICE Trans. Fundamentals, Dec. 2000.

    11. P. Zarkesh-Ha, J.A. Davis, J.D. Meindl, "Prediction of Net-Length Distribution for Global Interconnects in Heterogeneous Systemon-a-Chip", IEEE Trans. VLSI Systems, Dec.2000.

    Ю.В. Чернухін, A.A. приймання

    АЛГОРИТМ НАВІГАЦІЇ АДАПТИВНИХ МОБІЛЬНИХ РОБОТІВ ПО АВТОМАТИЧНО формованого КАРТІ В УМОВАХ динамічно змінюється зовнішнього середовища

    .

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

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

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

    . ,

    , .

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

    одночасним нанесенням на карту координат цих ділянок разом з типами розташованих на них об'єктів. Далі відбувається визначення ділянок, сусідніх з дослідженими, їх вивчення і т.д. Описаний процес повторюється до тих пір, поки в середовищі не залишиться жодного недослідженого ділянки [2]. Після формування карти процес навігації по ній здійснюється згідно біонічному методу управління АМР на основі нейропроцессорних мереж [3]. При цьому, -вання моделі зовнішнього середовища (ПФМВС), що відображає мережу (ОС), мережа аферентного синтезу (САС), мережа прийняття рішень (СПР), підсистему визначення

    () ().

    Нехай мета задана на карті і не потрапляє в зону сприйняття СП робота. Тоді процедуру визначення напрямку руху на кожному кроці виконується в два етапи [3]. На першому етапі карта в масштабі відображається в САС, де визначається напрям глобального переміщення АМР без відпрацювання кроку переміщень-.

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

    АМР на мапі середовища, яка знову зчитується в САС з урахуванням події переміщення. Знову визначається проміжна мета, обчислюється і відпрацьовується наступний напрямок руху і т.д. до виходу АМР в зону цілі [3].

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

    .

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

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

    наступному кроці на підставі порівняння їх поточних положень з тими, які вони займали в попередній момент часу * г-1 [4].

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

    Percept - оператор формування дискретної моделі зовнішнього середовища в ПФМВС; PathPlan - оператор визначення одиничного вектора напрямку до мети; Extr - оператор екстраполяції положення рухливих перешкод на 1

    -E

    квант дискретного часу; y oMt! +1 - дискретні вектора, що визначають екстрапольовані положення рухливих перешкод в наступний момент дискретного часу; U, - одиничний вектор напрямку на ціль; р - модуль швидкості

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

    ди на i-му кроці; Yt - дискретний вектор, який визначає положення цілі на карті

    -до

    (Мета передбачається нерухомою); Y osi - дискретні вектора, що визначають

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

    i-,; Y oMi

    - , -ствий в середовищі, в тій же системі координат, ЩО І YOSi; XRi - вектор, який визначає положення робота в середовищі на i-му кроці; Correct (XR (i + 1)) - оператор локалізації положення АМР на карті за інформацією, повчати з середовища. Тоді, відповідно до біонічних методом управління [3], алгоритм руху до мети по карті може бути сформульовано таким чином:

    1. i = 1.

    2. {Ytі, Yos ,, YoMi} = Percept (Yt, YoSl, YoMl) .

    3. Якщо Yті Ф 0, то перехід до п.11, інакше - наступний крок.

    . - -до -до

    4. Yі, = PathPlan (Yт, Yos,).

    5. Y oMtl + 1 = Extr (YoMt ,, YoMt, _1) .

    6. Ui = PathPlan (Yі ,, Yos ,, Y oMtlA).

    7. AXRi = pUi At.

    8. XrM = Xri + AXr,.

    9. XR (, + 1) = Correct (XR (M)).

    10. i = i + 1, перехід до п.2.

    11. Y oMtl + 1 = Extr (Y oMt,, Y oMtl-1).

    12. U, = PathPlan (Yosi, YEoMtM, Yt,).

    13. AXRl = pU, At.

    14. XR (i + 1) = XRi + AXRi .

    15. Якщо XR (, + j) = YTi, то зупинка, інакше - наступний крок.

    16. i = i + 1, перехід до п.2.

    , .2

    зовнішнього середовища за допомогою оператора Percept. Далі в п.3 відбувається перевірка попадання цілі в область сприйняття СП АМР. Якщо мета знаходиться в його зоні сприйняття, то карта не використовується. Замість цього відбувається перехід до п.11, в якому екстраполюються положення рухливих перешкод в наступний мо. .12 -льон руху до мети з урахуванням екстраполювати плану прохідності середовища.

    .13 -

    ном напрямку, який відпрацьовується в п.14. Далі в п.15 відбувається перевірка досягнення мети. Якщо АМР досяг мета, то робота алгоритму завершується, в іншому випадку описаний процес повторюється. Якщо ж мета знаходиться поза

    , .4

    на проміжну мету по карті середовища оператором PathPlan. Після цього в п.5

    , .6 -

    правління руху до чергової проміжної мети з урахуванням цієї інформації. У п.п.7-8 реалізується крок в певному напрямку. У п.9 відбувається уточнення позиції АМР на карті. Цикл руху до мети за допомогою карти, наведений в рядках 4-9, повторюється до потрапляння мети в зону сприйняття АМР.

    Експериментальні дослідження алгоритмів. Експериментальна перевірка описаних алгоритмів проводилася за допомогою спеціально розробленого програмного моделює кошти, реалізованого в операційній системі Windows. Головне вікно цієї програми наведено на рис.1, а. Даний засіб включає програмну модель нейромережевої системи управління АМР, редактор зовнішнього середовища з можливістю завдання положень робота, і цілі, а також траєкторій руху рухомих перешкод. Крім цього, моделює засіб має в своєму складі підпрограми, що реалізують алгоритми автоматичного формування карти зовнішнього середовища і навігації по ній АМР. При цьому є можливість вмикати або вимикати екстраполяцію положення рухливих перешкод в середовищі при навігації. За допомогою описаного кошти було проведено ряд експериментів. Взаємне розташування АМР, нерухомої перешкоди і цілі перед початком одного з них показано на рис.1, а. На початку експерименту середу задавалася статичної. Експеримент проводився в три етапи. На першому етапі АМР здійснював побудову карти середовища, використовуючи описану вище методику. При цьому початкова позиція робота відзначена на рис.1, а прямокутником. В результаті АМР повністю досліджував зовнішнє середовище і сформував її карту, показану на ріс.1,6. У процесі дослідження середовища зіткнення робота з перешкодою були відсутні.

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

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

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

    Рис.1. Вікна програмного моделює кошти

    Рис.2. результати експериментів

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

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Filliat D., Meyer J.A. Map based navigation in mobile robots. A review of localization strategies. Journal of Cognitive System Research, №4,2003, pp. 243-282.

    2. Чернухін ЮМ., Приймання A.A. Формування та використання карти зовнішнього середовища в завданні навігації адаптивного мобільного робота. Матеріали VIII всеросійської науково-технічної конференції "нейроінформатіке 2006", Збірник наукових праць. Частина 2. - М .: Изд-во МГУЛ. 2006. - С.10-16.

    3. Чернухін ЮМ. Нейропроцессорние мережі. - Таганрог: Изд-во ТРТУ, 1999. - 439 с.

    4. . ., . .

    інтелектуальних мобільних роботів. Збірник доповідей Ювілейної Міжнародної конференції по нейрокібернетиці. - Ростов-на-Дону: Изд-во ТОВ «ЦВВР», 2002 Т2. -З. 147-151.

    Б.К. Лебедєв, С.А. Степаненко

    ГЕНЕТИЧНИЙ АЛГОРИТМ РОЗМІЩЕННЯ, КЕРОВАНИЙ тимчасові обмеження *

    .

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

    .

    .

    . , .

    Існуючі алгоритми розміщення, керованого тимчасовими обмеженнями, можна розділити на 2 категорії: засновані на оцінці шляхів поширення сигналів (path-based) і засновані на оцінці ланцюгів схеми (net-based).

    Path-based алгоритми [1-3] безпосередньо намагаються мінімізувати затримку найдовшого шляху. Популярним підходом є мінімізація суми довжин деякого безлічі критичних шляхів. Цей набір критичних шляхів або попередньо визначається методом статичного часового аналізу, або може динамічно змінюватися від ітерації до ітерації. Більшість алгоритмів цього класу засноване на методах математичного програмування.

    path-based -

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

    Алгоритми net-based [4-7] на відміну від path-based алгоритмів безпосередньо не накладають обмеження на шляху проходження сигналу. Замість цього, тимчасові обмеження або вимоги на шляху перетворюються в обмеження на довжину ланцюгів або ваги ланцюгів. Основна ідея полягає в тому, щоб більш критичним ланцюгах привласнити більшу вагу. Ця інформація потім використовується алгоритмом мінімізації зваженої довжини з'єднань, з метою отримання розміщення з кращого тимчасовою затримкою. Цей отриманий варіант розміщення розглядається статичним аналізатором, після чого виходить новий набір тимчасової інформації, яка використовується на наступній ітерації. Зазвичай цей процес повторюється на кількох ітераціях, до тих пір, поки спостерігається поліпшення або поки не буде виконано задане число ітерацій. Методики, засновані на обчисленні ваг ланцюгів, володіють деякими привабливими властивостями: порівняно низька тимчасова складність, велика гнучкість (можуть бути інтегровані в існуючі алгоритми, які мінімізують довжину про-

    * Робота виконана за фінансової підтримки програми розвитку наукового потенціалу вищої школи РНП.2.1.2.2238


    Завантажити оригінал статті:

    Завантажити