Методы декомпозиции ячеек
В указанном выше первом подходе к планированию пути используется декомпозиция ячеек; иными словами, в этом методе осуществляется разложение свободного пространства на конечное количество непрерывных участков, называемых ячейками. Эти участки обладают тем важным свойством, что задача планирования пути в пределах одного участка может быть решена с помощью простых средств (например, в виде передвижения по прямой линии). Таким образом, задача планирования пути преобразуется в задачу поиска в дискретном графе, во многом аналогичную задачам поиска, представленным в главе 3.
Простейшая декомпозиция ячеек представляет собой сетку с равномерным шагом. На рис. 25.13, а показаны декомпозиция пространства с помощью квадратной сетки и путь решения, оптимальный для сетки с этими размерами. Кроме того, на этом рисунке используются затенение в виде градаций серого цвета для обозначения стоимости каждой ячейки сетки свободного пространства, т.е. стоимости самого короткого пути от этой ячейки к цели. (Эти стоимости можно вычислить с помощью детерминированной формы алгоритма Value-Iteration, приведенного в листинге 17.1.) На рис. 25.13,6 показана соответствующая траектория манипулятора в рабочем пространстве.
Такая декомпозиция имеет преимущество в том, что обеспечивает чрезвычайно простую реализацию, но характеризуется также двумя ограничениями. Во-первых, она может применяться только для пространств конфигураций с малым количеством измерений, поскольку количество ячеек сетки растет экспоненциально в зависимости от d, т.е. от количества измерений. Во-вторых, возникает проблема, обусловленная тем, что некоторые ячейки являются "смешанными", т.е. не принадлежащими полностью ни к свободному, ни к занятому пространству. Путь, найденный в качестве решения, который включает такую ячейку, может не соответствовать действительному решению, в связи с тем что не будет существовать способа пересечения ячейки в желаемом направлении по прямой линии. В результате этого процедуpa планирования пути становится противоречивой. С другой стороны, если мы будем настаивать на том, чтобы использовались только полностью свободные ячейки, то процедура планирования станет неполной, в связи с тем что могут возникать случаи, в которых единственные возможные пути к цели лежат через смешанные ячейки, особенно если размер ячейки сопоставим с размерами проходов и просветов в рассматриваемом пространстве.
Существуют два способа усовершенствования метода декомпозиции ячеек, позволяющие исправить эти недостатки. Первый из них состоит в том, что допускается дальнейшее разделение смешанных ячеек, возможно, с использованием ячеек, вдвое меньших по сравнению с первоначальным размером. Такая операция может продолжаться рекурсивно до тех пор, пока не будет найден путь, полностью проходящий по свободным ячейкам. (Безусловно, этот метод может применяться, только если есть возможность определить, является ли данная конкретная ячейка смешанной, а эта операция является простой, только если границы пространства конфигураций определяются с помощью относительно простых математических описаний.) Такой метод является полным, при условии, что заданы ограничения на величину наименьшего прохода, через который должен пройти искомый путь. Хотя при этом основная часть усилий, связанных с вычислениями, сосредоточивается на наиболее сложных участках в пространстве конфигураций, данный метод все еще не позволяет добиться успешного масштабирования и распространения его на многомерные задачи, поскольку при каждом рекурсивном разбиении ячейки создаются 2d меньших ячеек. Второй способ получения полного алгоритма состоит в том, чтобы неуклонно соблюдалось требование точной декомпозиции ячеек свободного пространства. Этот метод должен допускать, чтобы ячейки принимали неправильную форму в тех местах, где они встречаются с границами свободного пространства, но эти формы все еще должны оставаться "простыми" в том смысле, что при их использовании можно было легко вычислить траекторию прохождения через любую свободную ячейку. Для реализации этого метода требуется использование некоторых весьма сложных геометрических понятий, поэтому данный метод не будет рассматриваться здесь более подробно.
Рассматривая путь решения, показанный на рис. 25.13, я, можно заметить дополнительные сложности, которые необходимо преодолеть. Во-первых, следует отметить, что этот путь содержит произвольно острые углы; робот, движущийся с какой-либо конечной скоростью, не сможет пройти по такому пути. Во-вторых, заслуживает внимания то, что путь проходит очень близко от препятствия. Любой, кто занимается вождением автомобиля, знает, что парковочная площадка, на которой оставлено по одному миллиметру просвета с каждой стороны, в действительности вообще не годится для парковки; по той же причине следует предпочесть такие пути решения, которые не чувствительны к небольшим погрешностям движения.
Желательно максимизировать расстояние от препятствий и вместе с тем минимизировать длину пути. Этой цели можно достичь, введя понятие поля потенциалов. Поле потенциалов — это функция, определенная в пространстве состояний, значение которой растет пропорционально расстоянию до ближайшего препятствия. Такое поле потенциалов показано на рис. 25.14, д, — чем более темным цветом обозначена точка в пространстве конфигураций, тем ближе она к препятствию. При использовании в задаче планирования пути такое поле потенциалов становится дополнительным термом стоимости в уравнении оптимизации. Благодаря этому возникает интересная ситуация поиска компромисса. С одной стороны, робот стремится минимизировать длину пути к цели. С другой стороны, он пытается оставаться в стороне от препятствий, придерживаясь минимальных значений функции потенциалов. Назначив обеим целям соответствующие веса, можно найти примерно такой путь, как показано на рис. 25.14, б. На этом рисунке показана также функция стоимости, выведенная на основании комбинированной функции затрат, которая и в этом случае вычислена с помощью итерации по стоимостям. Очевидно, что полученный в результате путь длиннее, но вместе с тем и безопаснее.