Библиографический список

1. Н.Д. Нильсон. Искусственный интеллект. Методы поиска решений.- М.: Мир, 1973.

2. S.M. LaValle, “Planning Algorithms”, 1999-2006. Available: http:// msl.es.uiuc.edu/ planning

3.6.4. Алгоритм фронта волны

Рассмотрим алгоритм фронта волны [1], который является частным случаем метода искусственных потенциалов [2].

Суть метода искусственных потенциалов состоит в том, что робот рассматривается как заряженная частица, движущаяся в потенциальном поле. Предварительно определив над пространством (непрерывным или дискретным), в котором оперирует робот, некоторую особым образом сконструированную функцию (навигационную функцию или искусственный потенциал), мы затем можем руководствоваться ею для перевода робота из стартовой конфигурации в целевую.

Работу алгоритма рассмотрим на примере двумерного дискретного пространства конфигураций X. Каждая точка q этого пространства представляет собой некоторую конфигурацию робота. Некоторые точки пространства являются запрещенными, их количество и расположение известно заранее и не изменяется в процессе движения робота. Робот при движении не может выходить за пределы прямоугольника, левая и нижняя границы которого заданы конфигурацией q^L, а правая и верхняя – конфигурацией q^H. Заданы также стартовая конфигурация q⁰ и целевая конфигурация q^T. Данные начальные условия изображены на рис. 3.10.

Необходимо спланировать путь из q⁰ в q^T, т.е. определить последовательность конфигураций {q₁, q₂, …, q_n}, такую, что q₁ = q⁰, q_n = q^T, все точки последовательности являются разрешенными, и для любого i = 1, 2, …, n–1 точки q_i и q_i+1 будут соседними в пространстве X.

Построение функции искусственного потенциала

Каждой разрешенной конфигурации q из пространства X необходимо поставить в соответствие некоторое числовое значение v_p(q) — значение потенциала. Основное требование к функции потенциала v_p состоит в том, чтобы она имела единственный минимум в целевой конфигурации q^T. Алгоритм фронта волны заключается в следующем:

1. В список WF (фронт волны) помещается целевая конфигурация q^T, которой присваивается значение потенциала v_p(q^T) = 0. Список NWF (новый фронт волны) пуст. Переменной v (текущее значение потенциала) присваивается значение 1.

2. Для каждой конфигурации q из списка WF формируется список N конфигураций, соседних с ней.

3. Каждой конфигурации n из списка N, если она является разрешенной, и для нее еще не установлено значение потенциала, присваивается значение потенциала v_p(n) = v, после чего конфигурация n заносится в список NWF.

4. После того, как рассмотрены все конфигурации из списка N, происходит переход к следующей конфигурации q на шаге 2.

5. После того, как рассмотрены все конфигурации из списка WF, если список NWF пуст, то алгоритм заканчивает свою работу. В противном случае список WF очищается, содержимое списка NWF копируется в список WF, список NWF очищается, значение переменной v увеличивается на 1, и алгоритм продолжает свою работу с шага 2.

Построенная таким образом функция потенциала будет иметь единственный минимум в точке q^T. Кроме того, поскольку функция потенциала никак не зависит от стартовой конфигурации, то при неизменном количестве и расположении запрещенных точек, однажды рассчитанной функцией потенциала можно пользоваться для планирования траектории из любой разрешенной начальной точки в точку q^T.

Результаты работы алгоритма фронта волны (вычисленная функция потенциала) приведены на рис. 3.11.

Планирование пути

После вычисления функции потенциала планирование пути движения не представляет трудностей. Начав со стартовой конфигурации q⁰, следует для каждой точки планируемого пути рассмотреть все соседние с ней разрешенные точки и перейти в ту из них, которая имеет наименьшее значение потенциала. Если таких точек несколько, следует выбрать одну из них произвольным образом (в соответствии с некоторым алгоритмом или случайно), данный выбор никак не изменит общую длину пути (в шагах).

Путь, спланированный с использованием данного алгоритма, приведен на рис. 3.12.

Можно видеть, что полученный путь отвечает всем предъявленным требованиям: исходит из точки q⁰, приходит в q^T, не налегает на препятствия, не содержит разрывов и не выходит за границы рабочего пространства.

Порядок просмотра соседних точек

При построении искусственного потенциала с помощью алгоритма фронта волны и при последующем планировании пути для каждой текущей конфигурации q следует рассмотреть все соседние с ней конфигурации. В текущей реализации каждая конфигурация q в двумерном пространстве может иметь не более 8 соседних конфигураций (соседними считаются те конфигурации, каждая координата которых отличается от соответствующей координаты конфигурации q не более чем на один шаг дискретизации). Схема порождения соседних конфигураций показана на рис. 3.13.

Рис. 3.11

Рис. 3.12

Рис. 3.13

Рис. 3.14

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

Возможны и другие схемы порождения соседних конфигураций (см. рис. 3.14). В программной реализации метода искусственных потенциалов выбор той или иной схемы задается директивой препроцессора языка при компиляции программы.

Алгоритм применим для n-мерного пространства состояний. Время его работы принимает значительные размеры с ростом размерности пространства состояний.