Исследование особых ситуаций для задачи выбора пути в условиях неопределенности

( The Singular Situations Investigation for Path Finding Problem in Uncertainty
Preprint, Inst. Appl. Math., the Russian Academy of Science)

Бакиров А.К., Кирильченко А.А.
(A.K.Bakirov, A.A.Kiril’chenko)

ИПМ им. М.В.Келдыша РАН

Москва, 2001
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты №№ 96-01-01003, 99-07-90187, 99-01-00981)

Аннотация

В работе исследуются особые ситуации для задачи выбора пути мобильным роботом в условиях неопределенности. Эти ситуации могут возникать при вариации координат исходной и целевой точки, а также радиуса действия измерительной системы робота. При этом происходит резкое изменение двигательного поведения мобильного робота.

Abstract

The paper deals with singular situations investigation for path finding problem of mobile robot in uncertainty. Such situations can appear by variations of start point, goal point and information system radius. In this case the mobile robot motion behavior abrupt modification is happened.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.. 2

1.   АЛГОРИТМ ВЫБОРА ПУТИ.. 5

2.   ОСОБЕННОСТИ ПОСТАНОВКИ ПОДЦЕЛЕЙ.. 5

3.   ОСОБЫЕ СИТУАЦИИ.. 7

4.   ПРИМЕР ВЫДЕЛЕНИЯ ОСОБЫХ СИТУАЦИЙ НА ОСНОВЕ ИЗМЕНЕНИЯ РАДИУСА ДЕЙСТВИЯ ИС МР.. 10

5.   КЛАССИФИКАЦИОННАЯ СХЕМА ХАРАКТЕРИСТИК СЛОЖНОСТИ ЗАДАЧИ ВЫБОРА ПУТИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ.. 12

ЗАКЛЮЧЕНИЕ.. 15

ЛИТЕРАТУРА.. 16

ВВЕДЕНИЕ

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

Хорошо известно, что локальная оптимизация с глобальной точки зрения может быть неэффективной. В связи с этим, в условиях неопределенности (возникающей из-за затенения одних препятствий другими) увеличение радиуса действия измерительной системы (ИС) не всегда приводит к уменьшению длины построенного мобильным роботом (МР) пути [3].

Это объясняется, в частности, тем, что при возрастании радиуса действия ИС в поле зрения МР могут попасть более привлекательные (с точки зрения локальной оптимизации) альтернативы движения, которые могут завести в тупик (МР с меньшим радиусом их просто не заметит).

Поясним сказанное примером. На рис.1 изображена ситуация «Немонотонность по обходу». При небольшом радиусе действия ИС МР обходит препятствие справа. При увеличении радиуса действия ИС МР обнаруживает ближайший конец стены слева и предпочитает обход слева. При дальнейшем увеличении радиуса действия, он обнаруживает удаленную стену слева и возвращается к первоначальному решению. На рис.2 изображен график изменения длины построенного пути в зависимости от радиуса действия ИС МР.

 

Рис. 1а

Рис. 1б

Рис. 1в

 

Рис.2

 

Исследования показали, что существует четыре типа ситуаций, вызывающих указанный эффект:

1.           Немонотонность по обходу. К этому типу относятся ситуация, указанная выше.

2.           Немонотонность в малом [4]. Разброс значений порождается особенностями моделирования информационно-двигательных действий нижнего уровня.

3.           Неустойчивость по тупикам. Основной причиной данной неустойчивости является наличие тупиков (мнимых или реальных) – точек, в которых осмотр дальнего плана не дает новых опорных подцелей движения в секторе обзора.

4.           «Резонансная» немонотонность. Сюда относятся все ситуации немонотонности с числом пучков путей большим или равным трех и не попадающих в предыдущие классы [5].

Среда, в рамках которой действует МР, представляет собой толерантное метрическое пространство (основным отношением толерантности является отношение видимости). Такая структура ниже называется террайном. Двигательное поведение МР на террайне определяется алгоритмом функционирования, состоящем из набора информационно-двигательных действий (ИДД).

В целях проверки эффективности работы алгоритма выбора пути для задачи достижения целевой точки на террайне в условиях неопределенности было проведено его тестирование на примере представленного на рисунке фрагмента Кносского дворца [8].

Районы, ограниченные препятствиями, называются комнатами.

 

Рис. 3. Террайн, использовавшийся в численных экспериментах при тестировании алгоритма. (На рисунке представлен один из путей, построенных из фиксированной начальной к фиксированной целевой точке).

 

При численных экспериментах варьировались следующие параметры алгоритма:

·        Координаты целевой точки

·        Радиус действия информационной системы (ИС) мобильного робота (МР).

·        Расстояние неразличимости положения МР и координат текущей подцели (и целевой точки).

В качестве основного критерия эффективности действия алгоритма использовался эквивалент длины пройденного пути – количество элементарных смещений (вращательных и поступательных) МР при перемещении из начальной в целевую точку. (Размеры тестового террайна соответствуют размерам дисплея в пикселях при разрешении 640x480. При этом поворот на 15° предполагался равным смещению на 1 пиксель).

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

1.    АЛГОРИТМ ВЫБОРА ПУТИ

Опишем в общих чертах алгоритм выбора пути, используемый информационной системой (ИС) мобильного робота для решения задачи о достижении целевой точки. Он представляет собой модификацию алгоритмов, основанных на методе подцелей и изложенных ранее [1,2,4,9].

1.    МР проводит осмотр дальнего плана с выделением текущих альтернатив движения в виде набора подцелей. Если подцелей не обнаружено, то 7.

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

3.    Из набора выделенных подцелей по некоторому критерию выбирается оптимальная.

4.    МР перемещается к выбранной подцели.

5.    Если достигнутая подцель есть в списке резервных, то ей присваивается характеристика "пройдена". Подцели, пройденной в двух направлениях присваивается характеристика "тупик". Если достигнутая подцель тупиковая то 7.

6.    Повторение шагов 1-5 до достижения целевой точки.

7.    Из набора резервных подцелей по некоторому критерию выбирается оптимальная. Если резервных подцелей нет, то аварийная остановка алгоритма. Иначе 4.

Таким образом, представленный алгоритм является аналогом алгоритма поиска вглубь по априорно известному графу для террайна в условиях неопределенности. Главное различие заключается в том, что в нашей задаче исследуемый граф строится непосредственно в ходе решения поставленной перед МР задачей. Следовательно, ряд особых ситуаций может быть связан именно с особенностями постановки подцелей.

2.    ОСОБЕННОСТИ ПОСТАНОВКИ ПОДЦЕЛЕЙ

Предполагается, что робот измеряет дальности до препятствий в некотором секторе обзора, который в работе был принят равным 180°. Полученный набор дальностей подвергается логической фильтрации с целью выделения скачков дальности вблизи вершин препятствий, свободной зоны в направлении целевой точки и участков на границе видимости.

Таким образом, алгоритм выбора пути для мобильного робота выставляет 3 типа подцелей [9]:

·      "к цели";

·      "у угла";

·      "у стены".

Они зависят от взаимного расположения положения МР в момент проведения сеанса измерения и препятствий террайна, а подцель типа "к цели" также зависит и от положения целевой точки. В качестве критериев надежности подцелей выделим:

·              устойчивость постановки (будет ли подцель поставлена вообще);

·              устойчивость координат (будет ли подцель смещаться при смещении точки обзора).

Проанализируем каждый тип подцели по данным критериям.

Подцель типа "к цели" достаточно устойчиво ставится вдали от препятствий и теряет устойчивость в их непосредственной близости. Приведенный ниже рисунок иллюстрирует этот факт.

 

Рис. 4а. МР поставил две подце­ли: "у угла" и "к цели". Подцель "у угла" имеет привязку к координа­там угла.

Рис. 4б. Малое смещение МР привело к исчезновению подцели типа "к цели".

 

От координат МР зависит также, будет ли поставлена подцель типа "у угла", т.к. она выбирается вблизи скачка функции удаления от препятствий (в зависимости от азимутального угла) ri(yi), превышающего определенное пороговое значение. Если расстояние от МР до угла и радиус действия ИС МР различается незначительно, то необходимого скачка не будет и подцель окажется незафиксированной.

 

Рис. 5. Подцель типа "у угла" ставится вблизи скачков функции расстояния до препятствия.

Рис. 6. Подцель типа "у стены" смещается при смещении точки осмотра МР

 

В этом случае будет поставлена подцель типа "у стены". Этот тип подцели является самым устойчивым по постановке и введен для повышения надежности работы ИС МР.

 

Рассмотрим теперь координатную устойчивость подцелей.

Координаты подцелей типа "к цели" и "у стены" являются "плавающими": при малом изменении положения МР происходит малое смещение подцелей. По этой причине они не могут характеризовать террайн и не сохраняются в качестве резервных подцелей.

Координаты подцели типа "у угла" более устойчивы по отношению к вариациям положения МР. Подцель "привязана" собственно к угловой точке террайна и может являться его характеристикой.

3.    ОСОБЫЕ СИТУАЦИИ

Исходя из приведенной схемы алгоритма выбора пути и особенностей постановки подцелей можно ожидать возникновения особых ситуаций следующих типов:

 

1.    Отсутствуют резервные подцели ("пустой резерв").

2.    Подцель с характеристикой "тупик" закрывает реальные альтернативы ("ложный тупик").

3.    Резервная подцель не выводит из тупика (ситуация "ложная альтернатива").

4.    МР неоднократно проходит подцель в одном направлении ("петля").

 

Рассмотрим каждую из выделенных особых ситуаций подробнее.

Как было показано выше, в качестве резервных подцелей могут быть взяты только подцели типа "у угла". Если путь МР, приводящий его в тупик, проходит через все обнаруженные подцели типа "у угла", то резервных подцелей у него не остается (рис. 7).

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

Возникновение особой ситуации типа "ложный тупик" (рис. 8) возможно вследствие ограниченности ИС МР как по расстоянию, так и по углу обзора. В результате МР может упустить возможность поставить альтернативную подцель "у угла", т.е. "не заметить" возможные ответвления коридора, вследствие чего задача достижения целевой точки может оказаться нерешенной.

Предполагаемые пути выхода из ситуаций типа "ложный тупик" заключаются в увеличении информационных возможностей МР, увеличении числа сеансов осмотр-фильтрация, а также включение в программу МР таких сеансов при движении из тупика.

 

Рис. 7. Отсутствуют резервные подцели. МР больше не имеет альтерна­тивных путей. Задача достижения целевой точки не решена.

Рис. 8. "Ложный тупик": вблизи точки 13 заметно ответвление лабиринта. Тем не менее, подцели 9 и 10 имеют характеристику "тупик".

 

Особая ситуация типа "ложная альтернатива" (рис. 9) приводит к тому, что МР повторно исследует уже пройденный коридор до тех пор, пока вновь не обнаружит тупик (или не попадет в подцель с меткой "тупик"). Данная особая ситуация сама по себе не является фатальной, но приводит к неоправданному увеличению длины пути.

"Ложная альтернатива" возникает при следующих условиях:

1)    в результате фильтрации полученной при осмотре дальнего плана информации ИС МР выделяет близкорасположенные (по углу) подцели типа "у угла" и "к цели";

2)    оптимальной является подцель типа "к цели";

3)    МР находится у однозначного поворота коридора.

Первое и третье условия определяют собственно "ложность" подцели. Второе – ее наличие в качестве резервной (резервной может быть подцель только типа "у угла"). Необходимость третьего условия проиллюстрирована на рисунке 9б: из точки 2 не может быть поставлена подцель типа "к цели", зато из резервной подцели, исходящей из точки 1 – может.

Для выхода из особой ситуации типа "ложная альтернатива" может потребоваться усовершенствование способности МР определять повторяющиеся маршруты.

 

Рис. 9а. Особая ситуация "ложная альтернатива": открытая подцель достигается из точки 10 и ведет в уже пройденный коридор. Таким образом, она не позволяет МР выйти из тупика.

Рис. 9б. В отличие от "ложной альтернативы", исходящей из точки 10, открытые подцели, исходящие из точек 13, 7 и 1 являются реальными альтернативами.

 

На рисунке 10 представлена особая ситуация типа "стягиваемая петля".

 

Рис. 10. "Стягиваемая петля": блуждание МР в двух комнатах. Размеры комнаты позволили в точке 19 поставить подцель 20 типа "у стены" (в коридоре был бы зафиксирован тупик). Таким образом, МР стал двигаться вдоль стены по подцелям типа "у стены", как в алгоритме контурного обхода. Сразу выйти из комнаты роботу помешало наличие более приоритетных подцелей типа "к цели" (14, 15, 29). Подцели типа "у угла" (28, 38) пройдены только в одном направлении (возможно, несколько раз) и не сигнализируют о наличии тупика.

 

Кроме "стягиваемых петель", появляющихся в комнатах, возможно образование подобных "петель" вокруг препятствий не связанных с главной стеной террайна – "нестягиваемых петель". Они также строятся на подцелях типа "у стены", а устойчивость им придают подцели типа "у угла". Соответственно, выйти из подобной "петли" позволяет наличие подцелей типа "к цели".

В качестве выхода из особых ситуаций типа "петля" можно предложить усовершенствование системы маркирования пройденных подцелей с фиксацией количества проходов в каждом направлении.

4.    ПРИМЕР ВЫДЕЛЕНИЯ ОСОБЫХ СИТУАЦИЙ НА ОСНОВЕ ИЗМЕНЕНИЯ РАДИУСА ДЕЙСТВИЯ ИС МР

На представленных ниже рисунках изображены графики зависимости длины построенного пути от радиуса действия ИС МР для двух разных целевых точек (исходная точка одна и та же). Рисунки 12, 14, 15 соответствуют задаче, изображенной на рисунке 3.

 

 

Рис. 11. Крупный масштаб

Рис. 12. Крупный масштаб

 

На основании полученных графиков можно сделать предварительный вывод об отсутствии детерминированной зависимости между этими величинами. Тем не менее, анализируя полученные графики можно сделать вывод о наличии особых ситуаций связанных с особенностями террайна, на котором решается поставленная задача.

 

Рис. 13. Мелкий масштаб. У графика сравнительно гладкая структура.

Рис. 14. Мелкий масштаб. На графике явно заметны пики, показывающие на особые ситуации.

 

Так, для первого из представленных графиков колебания длины построенного пути составляют порядка 45% от длины максимального пути, а для второго – порядка 90% (при 30% без учета точек с особыми ситуациями). На основании приведенных данных можно с определенностью говорить о наличии особых ситуаций для второй задачи.

Пути, построенные для второй задачи представлены на рисунке 15.

 

Рис. 15а. Простейший путь

Рис. 15б. МР четырежды возвращался к резервным подцелям. Особая ситуация "ложная альтернатива"

Рис. 15в. Зарегистрировано два тупика. Имеет место ситуация "ложный тупик"

Рис. 15г. Особая ситуация "Пустой резерв". Задача не решена

 

5.    КЛАССИФИКАЦИОННАЯ СХЕМА ХАРАКТЕРИСТИК СЛОЖНОСТИ ЗАДАЧИ ВЫБОРА ПУТИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

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

Для исследования задачи выбора эффективного алгоритма маршрутизации о априорно известному графу использовались следующие десять характеристик сложности задачи [1]:

1.                Время построения пути.

2.                Длина построенного пути.

3.                Число ребер пути.

4.                Число отброшенных ребер вдоль пути.

5.                Размер фронта волны поиска (массива открытых вершин) на заключительной итерации.

6.                Размер тела волны поиска (массив закрытых вершин) на заключительной итерации.

7.                Число итераций.

8.                Число элементов в волне на момент завершения поиска (сумма пятой и шестой характеристик).

9.                Целенаправленность (число ребер в пути, деленное на восьмую характеристику, не считая начальной вершины).

10.           Максимальная длина фронта волны поиска (массива открытых вершин).

Для характеристики сложности всего графа могут использоваться гистограммы указанных выше характеристик для выбранного тестового набора задач (в которые могут входить и все возможные задачи на данном графе). Численные эксперименты показали [1], что для алгоритмов выбора пути по априорно известному графу выполняется свойство несравнимости любых двух алгоритмов даже в пределах достаточно узкого множества возможных задач. Это означает, что если рассматриваются 2 алгоритма А и В, то существует задача, где алгоритм А эффективнее алгоритма В, и существует задача, где алгоритм В эффективнее алгоритма А.

 

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

 

Второй способ заключается в построении характеристик структуры террайна.

 

Поскольку террайн представляет собой граф с континуумом вершин и ребер, построенных на основе отношений видимости, то на нем могут быть аналогично определены следующие две основные структурные характеристики графа: диаметр и число доминирования.

Целочисленная метрика k(x,y), задаваемая на точках носителя террайна определяется как минимальное число ребер в допустимом пути (ломаной) из x в y и наоборот. Максимум этой функции по точкам x, y и определяет диаметр террайна. Таким образом, диаметр террайна равен минимально необходимому числу сеансов измерений для передвижения между любыми двумя выбранными точками (в случае, если нет ограничений на радиус действия измерительной системы). Ниже эта характеристика будет обозначаться как γ(V).

Аналогом числа доминирования для террайна является навигационное число [2]. Пусть А – множество точек на террайне, а V – носитель террайна. Если V(A)=V (это означает, что множество видимых из А вершин совпадает со всем террайном), то А называется навигационным множеством. Навигационное множество называется навигационным базисом, если при удалении из А любого элемента оставшееся подмножество точек уже не является навигационным.

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

Навигационное множество называется навигационным множеством k-го порядка, если для любой точки x |A(x)|≥k

Для страндартного террайна множество вершин Р является навигационным множеством по крайней мере четвертого порядка. Пусть nmin(V) и nmax(V) соответствуют минимальной и максимальной возможным размерностям (числу элементов) для навигационного базиса. Очевидно, что эти два числа могут быть различны (см. рис.1).

 

X1 *

Y2 о

 

Y1 о

 

о Y3

 

Y4 о

*X2

Рис.16. Навигационный базис {Xk} c nmin(V)=2 и навигационный базис {Yk} c nmax(V)=4

Указанные числа называются минимальным и максимальным навигационными числами террайна.

ПРИНЦИП ОГРАНИЧЕННОГО РАЗНООБРАЗИЯ

Принцип ограниченного разнообразия террайна заключается в общем случае в выполнении условия γ(V) « nmin(V), при этом вводится коэффициент ограниченного разнообразия а как отношение а= nmin(V)/γ(V).

Например, транспортная сеть отдельного города, граф ассоциативной связи между словами языка удовлетворяют указанному принципу.

 

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

Магистральное множество играет основополагающую роль в системе выбора пути. Множество вершин препятствий является примером магистрального множества. Если μ – минимальное число элементов в магистральном множестве, то справедлива оценка:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.17. nmin(V)=2, γ(V)=3, μ(V)=3, т.е. для данной структуры приведенная формула принимает вид μ=b-1

 

 

Рисунок 17 иллюстрирует тот факт, что существуют террайны, для которых достигается μ=b-1, т.е. приведенная выше оценка сверху может быть улучшена максимум на 1.

 

Следующие 4 характеристики также позволяют оценивать структурную сложность террайна. К ним относятся [5]:

1.           Число образующих – отрезков для препятствий

2.           Число образующих – блоков с единичной длиной для построения препятствий (число клеточек)

3.           Максимальный размер граничной рамки, куда вписывается структура препятствий, называемый уровнем разнообразия террайна

4.           Число препятствий

 

Третий подход заключается в том, что фиксируется эталонный алгоритм выбора пути, характеристики действия которого для данной задачи берутся в качестве характеристик сложности задачи. Этот подход был предложен в 80-е годы сотрудником ИПМ им. М.В. Келдыша Е.И. Кугушевым.

ЗАКЛЮЧЕНИЕ

При тестировании алгоритма выбора пути на основе метода подцелей выделено и проанализировано четыре типа особых ситуаций:

1.          Отсутствуют резервные подцели ("пустой резерв").

2.          Подцель с характеристикой "тупик" закрывает реальные альтер­нативы ("ложный тупик").

3.          Резервная подцель не выводит из тупика (ситуация "ложная альтернатива").

4.          МР неоднократно проходит подцель в одном направлении ("петля").

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

Исследования также показали, что существует четыре типа ситуаций, вызывающих эффект немонотонной зависимости эффективности работы алгоритма от радиуса действия измерительной системы МР:

1.          Немонотонность по обходу. К этому типу относятся ситуация, указанная во введении.

2.          Немонотонность в малом [4]. Разброс значений порождается особенностями моделирования информационно-двигательных действий нижнего уровня.

3.          Неустойчивость по тупикам. Основной причиной данной неустойчивости является наличие тупиков (мнимых или реальных) – точек, в которых осмотр дальнего плана не дает новых опорных подцелей движения в секторе обзора.

4.          «Резонансная» немонотонность. Сюда относятся все ситуации немонотонности с числом пучков путей большим или равным трех и не попадающих в предыдущие классы. (А.Кир.?)

По данным имитационного моделирования колебания в немонотонной области длины построенного пути составили 63% для (1), 23% для (2), 67% для (3) и 15% для (4) от максимальной длины построенного пути.

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

ЛИТЕРАТУРА

1. Бакиров А.К., Кирильченко А.А. Проблемы управления распределенными мобильными системами // М.: Препринт Ин-та прикл.матем. им. М.В. Келдыша РАН, 2000, N 64. 23 с.

2. Кирильченко А.А. Обоснование алгоритмов выбора пути в условиях неопределенности. // Препринт Ин-та прикл. матем. им. М.В. Келдыша АН СССР, 1991, N 108, 25 с.

3. Бакиров А.К., Кирильченко А.А. Исследование эффекта немонотонной зависимости длины пути от радиуса действия измерительной системы в условиях неопределенности. // Материалы 6-ой Межд. научно-технич. конф. "Современные методы и средства океанологических исследований", М., 2000, ч.2, с. 50-51.

4. Бакиров А.К. Особенности имитационного моделирования распределенных мобильных систем. // Материалы 6-ой Межд. научно-технич. конф. "Современные методы и средства океанологических исследований", М., 2000, ч.2, с.

5. Кирильченко А.А. Об исследовании эффективности алгоритмов выбора пути в условиях неопределенности. 2. Атлас особых ситуаций и атлас "неустойчивого доминирования" //М.:Препринт Ин-та прикл.матем. им. М.В. Келдыша РАН, 1997, N 44.-27с.

6. Барбашова Т.Ф., Кирильченко А.А., Павловский В.Е. Исследование и выбор эффективных алгоритмов маршрутизации. // Препринт Института прикладной математики им. М.В. Келдыша АН СССР,1987, # 4, 32 с.

7. Петров А.А., Активное формирование моделей проблемной среды очувственными роботами. // М.: ИППИ РАН, 1997, 229 с.

8. Кнооооооооооооский двоооооорееееееееееееееец.

9. Кирильченко А.А., Карпов И.И., Платонов А.К. Метод подцелей в задаче выбора трассы мобильного робота в условиях неопределенности // Препринт Ин. прикл. матем. им. М.В. Келдыша АН СССР, 1983, N 16, 28 с.