Skip to content

README-RU.md

Latest commit

 

History

History
104 lines (84 loc) · 23.3 KB

README-RU.md

File metadata and controls

104 lines (84 loc) · 23.3 KB

Push-and-Rotate--CBS--PrioritizedPlanning

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

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

Для сборки проекта можно использовать 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
    2. ecbs - Enhanced conflict based search. В алгоритме на верхнем уровне используется вторичная эвристика h3 из статьи. Поиск нижнего уровня зависит от параметра low_level.
    3. anytime_cbs - CBS с фокальным поиском на верхнем уровне и оптимальным алгоритмом на верхнем уровне (astar или sipp), как описано в статье
    4. anytime_ecbs - ECBS с фокальным поиском на верхнем уровне и нижнем уровне. Для обновления focal_w на нижнем уровне списки OPEN, CLOSE и FOCAL, полученные в поисках нижнего уровня сохраняются.
    5. push_and_rotate - Push and rotate
    6. prioritized_planning - Prioritized planning

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

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

    Для алгоритма CBS могут использоваться только алгоритмы A* и SIPP, если выбрано другое значение low_level, оно будет проигнорированно и будет использоваться алгоритм A*.

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

  • with_cat - будет ли использоваться Conflict avodance table (true или false, учитывается если выбран алгоритм CBS или ECBS). Опциональный параметр, значение по умолчанию равно false

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

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

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

  • with_disjoint_splitting - будет ли производиться disjoint splitting. Описывается здесь, принимает значения true или false, учитывается если выбран алгоритм CBS или ECBS. При использовании этой опции, опция with_card_conf фиксируется равной true. Опциональный параметр, значение по умолчанию равно false

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

  • gen_subopt_from_opt - могут ли оптимальные вершины генерировать субоптимальных потомков в алгоритме zero_scipp. Принимает значения true или false, учитывается если low_level = zero_scipp. Опциональный параметр, значение по умолчанию равно false

  • use_cat_at_root - нужно ли учитывать траектории предыдущих других агентов, при планировании начального решения в корневой вершине. Принимает значения true или false, при значении false индивидуальные траектории агентов в корневой вершине строятся полностью независимо, иначе алгоритм пытается избежать конфликтов, насколько это позволяет фактор субоптимальности. Опциональный параметр, значение по умолчанию равно true. Не используется для anytime-алгоритмов

  • pp_order - задает правило, согласно которому выбираются приоритеты агентов в prioritized_planning. Может принимать следующие значения:

    • 0 - агенты обрабатываются в том же порядке, в котором они указаны в файле
    • 1 - агенты обрабатываются в порядке увеличения манхэттенского расстояния от стартовой позиции до конечной
    • 2 - агенты обрабатываются в порядке уменьшения манхэттенского расстояния от стартовой позиции до конечной

    Опциональный параметр, значение по умолчанию равно 0

  • parallelize_paths_1 - требуется ли применять процедуру параллеллезации путей, построенных Push and rotate (без этой опции в каждый момент времени двигается только один агент). Принимает значения true или false, учитывается только для алгоритма Push and rotate. . Опциональный параметр, значение по умолчанию равно false

  • parallelize_paths_2 - требуется ли дополнительно параллелизовать пути, построенные Push and rotate (увеличивает коэффициент сжатия, но замедляет работу алгоритма). Принимает значения true или false, учитывается только для алгоритма Push and rotate. При использовании этой опции, опция parallelize_paths_1 фиксируется равной true. Опциональный параметр, значение по умолчанию равно false

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

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

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

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

  • id - идентификатор агента
  • start_i, start_j - координаты стартовой позиции агента (клетки нумеруются с 0, клетка (0, 0) это верхний левый угол карты, первая координата соответствует номеру строки, а вторая номеру столбца)
  • goal_i, goal_j - координаты конечной позиции агента

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

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

Выходной файл так же содержит разделы 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. Каждый такой тег соответствует одному действию агента и содержит следующие теги:

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

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