Skip to content

README-RU.md

Latest commit

 

History

History
119 lines (94 loc) · 28.3 KB

README-RU.md

File metadata and controls

119 lines (94 loc) · 28.3 KB

CBS--PrioritizedPlanning--MP

В данном проекте приводятся реализации различных алгоритмов решающих задачи планирования траекторий для группы агентов. Рассматриваются алгоритмы Conflict based search и Enhanced conflict based search, а также некоторые их модификации. Для всех алгоритмов используется модель передвижения агентов, известная как motion primitives.

Сборка и запуск

Для сборки проекта можно использовать cmake с помощью файла CMakeLists.txt, размещенного в репозитории. Также файлы проекта могут быть открыты и скомпилированы в Qt Creator с конфигурациями, заданными в файле PathPlanning.pro.

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

Формат входных данных

Основной файл содержит разделы map, algorithm и options:

Раздел map - задание карты. Содержит следующие тэги:

  • grid - содержит атрибуты width и height, задающие ширину и высота карты (в клетках). В теле тега описывается сама карта, 0 означает свободную клетку, а 1 - препятствие. Ряды обособляются тэгом row, количество рядов должно быть равно height, а количество символов в каждом ряду должно быть равно width.

Раздел algorithm - выбор параметров алгоритма. Содержит следующие тэги:

  • planner - используемый алгоритм. Может принимать следующие значения:

    1. cbs - Conflict based search. Может использоваться только с поиском нижнего уровня astar или sipp
    2. ecbs - Enhanced conflict based search. В алгоритме на верхнем уровне используется вторичная эвристика h3 из статьи. Поиск нижнего уровня зависит от параметра low_level.

  • low_level - алгоритм, используемый в поиске нижнего уровня в алгоритмах CBS, ECBS и Prioritized planning. Может принимать следующие значения:

    1. astar - алгоритм A*
    2. sipp - алгоритм SIPP (дискретная версия для четырехсвязной сетки)
    3. focal_search - Алгритм Focal search как в оригинальной статье про ECBS. В алгоритме используется вторичная эвристика, равная количеству вершинных конфликтов на уже построенном участке траектории до текущей вершины
    4. scipp - алгоритм SCIPP Для алгоритма CBS могут использоваться только алгоритмы A* и SIPP, если выбрано другое значение low_level, оно будет проигнорированно и будет использоваться алгоритм A*.

  • with_perfect_h - будет ли производиться предпосчет кратчайших путей от всех вершин до конечных позиций агентов для вычисления оптимальной эвристики в A* (true или false). Если при перемещении агента присутствуют повороты, продолжительность начального и конечного поворотов не учитывается при подсчете эвристики (то есть эвристика не учитывает начальную и конечную ориентацию). Опциональный параметр, значение по умолчанию равно false

  • with_card_conf - будут ли учитываться кардинальные конфликты (описываются здесь). Кардинальные конфликты рассматриваются в порядке убывания минимального увеличения стоимости решения, необходимого для устранения конфликта. При совпадении данных значений, конфликты упорядочиваются в порядке увеличения времени их возникновения. Полукардинальные и некардинальные конфликты как обычно рассматриваются после кардинальных и упорядочиваются по времени возникновения. Принимает значения true или false. Опциональный параметр, значение по умолчанию равно false

  • with_bypassing - будет ли производиться обход конфликтов (conflict bypassing). Описывается здесь, принимает значения true или false. Опциональный параметр, значение по умолчанию равно false

  • with_ct_tree_h - будет ли вычисляться эвристика на вершинах дерева обхода CBS, основанная на максимальном паросочетаннии в графе кардинальных конфликтов. Описывается здесь как ICBS-h1 (с тем отличием, что в данном случае рассматривается взвешенный граф, где веса ребер совпадают с минимальным увеличением стоимости при устранении конфликта). Для поиска паросочетания используется жадный алгоритм. Принимает значения true или false. При использовании этой опции, опция with_card_conf фиксируется равной true. Опциональный параметр, значение по умолчанию равно false

  • mp_type - тип используемых примитивов движения. Может принимать следующие значения:

    1. 2k_neigh - передвижение агентов происходит по 2k связной сетке (где значение k задается параметром neigh_degree) с постоянной скоростью, время прохождения ребра совпадает с его длиной. Примитивы поворота не используются, все развороты агентов происходят мгновенно
    2. custom - примитивы задаются в файле, название которого передается через параметр mp_file

  • neigh_degree - степень связности для 2k-связной сетки (то есть параметр k). Целое число больше либо равное 2. Опциональный параметр, значение по умолчанию равно 2

  • mp_file - назвение параметра с описанием примитивов в формате описываемом в разделе "Формат описания примитивов". Обезательный параметр при mp_type = custom

  • scale - нечетное целое число. Когда scale > 1, каждая клетка разбивается на scale*scale клеток меньшего размера, и агент помещается в центральную клетку. Опциональный параметр, значение по умолчанию равно 1

  • agent_size - радиус агента. Действительное число, не больше чем 0.5 / scale (для больших значений некорректно определяется набор клеток, задеваемых при движении). Опциональный параметр, значение по умолчанию равно 0.5

  • time_resolution - параметр, используемый для переведения времени выполнения примитивов в целое количество тактов времени. Время прохождения ребра получается умножением его длины на time_resolution с последующим округлением вниз. Например, если time_resolution = 1000, переход по прямой в соседнюю ячейку по горизонтали занимает 1000 тактов, а по диагонали 1414 такта. Опциональный параметр, значение по умолчанию равно 1000

  • focal_w - вес, который используется на верхнем уровне в алгоритме ECBS и на нижнем уровне в алгоритмах Focal search и SCIPP при построении списка FOCAL. Во всех случаях гарантируется, что стоимость полученного решения будет отличаться от оптимальной не более чем в focal_w раз. Опциональный параметр, значение по умолчанию равно 1.0

Раздел options - выбор параметров тестирования. Содержит следующие тэги:

  • agents_file - общий префикс названий входных файлов с описанием агентов
  • tasks_count - количество входных файлов с описанием агентов: рассматриваются файлы с названиями вида agents_file-n.xml, где n принимает значения от 1 до tasks_count. Опциональный параметр, значение по умолчанию равно 1
  • agents_range - в атрибутах min и max данного тега указывается минимальное и максимальное количество агентов для тестирования. При single_execution=false, количество агентов увеличивается от min до max с шагом равным agents_step, и алгоритм запускается на соотвествующем подмножестве агентов. Тестирование прекращается, если алгоритм работает дольше заданного лимита по времени или не находит решения. Опциональный параметр, по умолчанию минимальное количество агентов равно 1, а максимальное совпадает с количеством агентов во входном файле
  • agents_step - шаг увеличения числа агентов при тестировании. Опциональный параметр, значение по умолчанию равно 1
  • maxtime - максимальное время работы алгоритма в миллисекундах. Опциональный параметр, значение по умолчанию равно 1000
  • single_execution - true или false, если выбрано значение true, алгоритм будет запущен только один раз для первого файла с агентами, с количеством агентов равным значению атрибута max в agents_range. При этом будет отличаться формат выходного файла (см. раздел "Формат выходных данных"). Опциональный параметр, значение по умолчанию равно false
  • pointwise_output - требуется ли добавлять промежуточные точки в примитивах при записи путей в выходной файл (используется для визуализации). Может принимать значения true и false, учитывается при single_execution = true. Опциональный параметр, значение по умолчанию равно false
  • time_step - интервал времени между двумя промежуточными точками при pointwise_output = true. Задается как целое количество тактов времени, длительность которых зависит от параметра time_resolution. Например, если time_resolution = 1000 и time_step = 10, на каждую секунду выполнения примитива будет приходиться 100 промежуточных точек. Опциональный параметр, значение по умолчанию равно 1, учитывается при single_execution = true и pointwise_output = true
  • aggregated_results - сохранять ли в лог отдельные результаты тестирования для каждого файла с агентами или усредененные результаты по всем файлам. Опциональный параметр, значение по умолчанию равно true
  • logpath - каталог, в который будет сохранен отчет. Опциональный параметр, по умолчанию, отчет сохраняется в тот же каталог, в котором находится входной файл)
  • logfilename - название файла с отчетом. Опциональный параметр, по умолчанию, название файла с отчетом получается из названия входного файла дописыванием строки "_log")

Файлы с агентами

Каждому агенту соответствует собственный тег agent со следующими атрибутами:

  • id - идентификатор агента
  • start_i, start_j - координаты стартовой позиции агента (клетки нумеруются с 0, клетка (0, 0) это верхний левый угол карты, первая координата соответствует номеру строки, а вторая номеру столбца)
  • goal_i, goal_j - координаты конечной позиции агента
  • start_angle_id - идентификатор начальной ориентации агента. Значение 0 соответствует ориентации на север, остальные ориетации нумеруются по часовой стрелке. Опциональный параметр, значение по умолчанию равно 0
  • goal_angle_id - идентификатор конечной ориентации агента. Если значение не указано или равно -1, агент завершит движение с той же ориентацией, с которой он пришел в конечную позицию

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

Формат описания примитивов

Файл содержит один или несколько разделов section. Каждая секция соответствует одной из возможных ориентаций агента и содержит притивы, в начале выполнения которых агент должен находиться в данной ориентации. Каждый тег section содержит теги coeff и time_finish с описанием притивывов движения и поворота соответственно. Тег coeff содержит следующие атрибуты:

  • id - идентификатор примитива
  • Tf - время выполнения маневра
  • xf, yf - конечная позиция агента относительно начальной (смещение после выполнения примитива)
  • a1, a2, a3, a4, b1, b2, b3, b4 - коэффициенты, задающие траекторию движения агента. А именно, координаты агента относительно его начальной позиции вычисляются как x(t) = a4t3+a3t2+a2t+a1, y(t) = b4t3+b3t2+b2t+b1, а угол ориентации агента вычисляется как arctg(y'(t)/x'(t)) = arctg((3b3t2+2b2t+b2) / (3a3t2+2a2t+a2)
  • v0, v1 - начальная и конечная скорость агента
  • phi0, phif - начальная и конечная ориентация агента (в градусах)

Следует заметитить, что реальные скорость и ориентация агента зависят только от коэффициентов ai и bi, в то время как значения v0, v1, phi0 и phif используются только для проверки корректности перехода между состояниями (агент может начать выполнение примитива только если его текущая ориентация и скорость совпадают с phi0 и v0 этого примитива, развороты возможны только если скорость агента равна 0). Теги time_finish описывает примитивы разворота, не предполагающие перемещения, поэтому они содержит только атрибуты id, Tf, phi0 и phif. Чтобы добиться поведения, схожего с примитивами 2k_neigh (скорость не учитывается, повороты производятся мгновенно) следует оставить в файле только теги coeff, поместить все примитивы в одну секцию и сделать все значения v0, v1, phi0, phif равными 0.

На изображении ниже можно видеть примера набора примитивов движения:

В директории Examples приводится примеры описания данного набора примитивов с поворотами и без.

Формат выходных данных

Выходной файл так же содержит разделы map и options, содержание которых совпадает со входным файлом, а также раздел log, в котором содержится сам отчет. Он содержит тэг mapfilename с названием основного входного файла, и ряд других тегов в зависимости от значений параметров single_execution и aggregated_results.

В случае, если single_execution=false, aggregated_results = false, создается один или несколько тегов results с результатами тестирования. Каждому входному файлу с агентами соответствует отдельный тег results, который содержит по одному тегу result для каждого количества агентов. В атрибутах каждого такого тега содержатся результаты тестирования алгоритма с данным количеством агентов из данного входного файла. А именно, тег содержит следующие атрибуты:

  1. agents_count - количество агентов
  2. success_count - количество тестов (среди tasks_count тестовых файлов) для которых алгоритм построил корректное решение в заданное время
  3. makespan - количество итераций до того как последний из агентов закончит движение
  4. flowtime - суммарное количество действий, совершенных агентами с учетом остановок
  5. time - время работы алгоритма
  6. HL_expansions - количество раскрытых вершин верхнего уровня в алгоритмах CBS и ECBS (размер списка CLOSE окончании поиска).
  7. HL_nodes - количество созданных вершин верхнего уровня в алгоритмах CBS и ECBS (сумма размеров списков OPEN, CLOSE и FOCAL по окончании поиска).
  8. LL_avg_expansions - среднее количество раскрытых вершин нижнего уровня в алгоритмах CBS и ECBS, усредненное по всем запускам поиска нижнего уровня.
  9. LL_avg_nodes - среднее количество созданных вершин нижнего уровня в алгоритмах CBS и ECBS, усредненное по всем запускам поиска нижнего уровня.

Пример выходного файла для данного режима.

В случае, если single_execution=false, aggregated_results = true, создается единственный тег results с усредненными результатами тестирования. Так же как и в предыдущем случае, он содержит по одному тегу result с теми же атрибутами для каждого количества агентов. При этом в атрибутах тега указываются значения, усредненные по всем файлам с агентами, для которых алгоритм был способен найти решение с данным количеством агентов. Пример выходного файла для данного режима.

В случае, если single_execution=true создаются следующие теги (тег aggregated_results в данном случае не учитывается):

  • taskfilename - название дополнительного входного файла с агентами
  • summary - информация о построенном решении. Содержит атрибуты agents_count, makespan, flowtime, time, HL_expansions, HL_nodes, LL_avg_expansions, LL_avg_nodes, которые определяются так же, как указано выше
  • для каждого агента указывается отдельный тег agent со следующими атрибутами:
  • id - идентификатор агента
  • start.x, start.y - координаты стартовой позиции агента
  • goal.x, goal.y - координаты конечной позиции агента

При этом координата x соотвествует координате j, а координата y координате i. Также в этот тег вкладывается тег path с атрибутом pathfound, принимающим значения true или false в зависимости от того, было ли найдено решение, в который в свою очередь вкладывается несколько тегов section. Каждый такой тег соответствует одному перемещению агента. Если pointwise_output = false одним перемещением считается весь примитив, иначе добавляются перемещения между промежуточными точками. Тег содержит следующие атрибуты:

  • id - идентификатор секции
  • start.x, start.y - позиция агента перед совершением действия
  • goal.x, goal.y - позиция агента после совершения действия (эта позиция либо совпадает со стартовой либо является соседней с ней)
  • start.heading, goal.heading - ориентация агента до и после совершения действия (в градусах)
  • duration - продолжительность действия (всегда равна 1)

Пример выходного файла для данного режима с pointwise_output = false. Пример выходного файла для данного режима с pointwise_output = true.