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