Мережа підцілей!!!

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

Походження

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

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

Сфера використання

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

Виконала Федорова Ольга

Developed by Інститут Програмних Систем