Декомпозиція клітин!!!

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

Метод декомпозиції клітин можна поділити на наступні підгрупи:

• Точна декомпозиція клітин.

• Приблизна декомпозиція клітин.

• Імовірнісна декомпозиція клітин.

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

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

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

Фодерато використовував комбінацію декомпозиції клітин та з'єднуючого дерева для створення оптимального рішення для віртуального агента в грі під назвою Ms. Pac-Man. Сеада порівняв декомпозицію клітин з дорожньою картою в 8-мірному та загальному плануванні руху. Недоліки, такі як комбінаторний вибух, обмежена деталізація і генерування нездійснюваних рішень пропонуються декомпозицією клітин від компанії Seda. Seda стверджує, що метод дорожної карти усуває недоліки методу декомпозиції клітин. Аналогічно, Лінгельбах вказав на те, що декомпозиція клітин у своєму процесі викликає проблему складності. Крім того, процес визначення того, чи є клітина вільною, дуже складний.

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

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