В указанном выше первом подходе к планированию пути используется декомпозиция ячеек; иными словами, в этом методе осуществляется разложение свободного пространства на конечное количество непрерывных участков, называемых ячейками. Эти участки обладают тем важным свойством, что задача планирования пути в пределах одного участка может быть решена с помощью простых средств (например, в виде передвижения по прямой линии). Таким образом, задача планирования пути преобразуется в задачу поиска в дискретном графе, во многом аналогичную задачам поиска, представленным в главе 3.

Рис. 25.12. Три конфигурации робота, показанные в рабочем пространстве и пространстве конфигураций

Простейшая декомпозиция ячеек представляет собой сетку с равномерным шагом. На рис. 25.13, а показаны декомпозиция пространства с помощью квадратной сетки и путь решения, оптимальный для сетки с этими размерами. Кроме того, на этом рисунке используются затенение в виде градаций серого цвета для обозначения стоимости каждой ячейки сетки свободного пространства, т.е. стоимости самого короткого пути от этой ячейки к цели. (Эти стоимости можно вычислить с помощью детерминированной формы алгоритма Value-Iteration, приведенного в листинге 17.1.) На рис. 25.13,6 показана соответствующая траектория манипулятора в рабочем пространстве.