Conflict Based Search

Реализация алгоритма многоагентного поиска пути на базе Conflict Based Search

Требования

Linux

• Git 2.7.4 или выше
• CMake 3.2 или выше;
• GCC 4.9 или выше

Mac

• Git 2.23.0 или выше
• CMake 3.2 или выше;
• Apple LLVM version 10.0.0 (clang-1000.11.45.5) или выше;

Windows

• Git 2.23.0 или выше
• CMake 3.2 или выше;

Начало работы

Cоздайте ответвление (fork) этого репозитория в свой GitHub аккаунт. Загрузите содержимое полученного репозитория, либо клонируйте его в нужную вам директорию.

git https://github.com/dpaleyev/PathPlanningProject.git

или (с помощью ssh)

git@github.com:dpaleyev/PathPlanningProject.git

или просто скачать архив с файлами

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

Сборку проекта возможно осуществить используя CMake.

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

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

Примеры входных и выходных файлов можно посмотреть в папке Examples

Входной файл содержится в теге root, в котором расположены следующие теги:

• map — обязательный тег, содержащий основную информацию о задаче

  • width, height — размеры карты
  • cellsize — размер одной клетки
  • startx, starty — координаты начальной клетки для каждого агента по очереди в тегах agent
  • finishx, finishy — координаты конечной клетки для каждого агента по очереди в тегах agent
  • grid — содержит поле: height тегов row, в каждом из которых width нулей или единиц через пробел, причем нули означают свободную клетку, а единицы — занятую

• algorithm

  • searchtype — алгоритм поиска: astar
  • metrictype — эвристика для оценки расстояния (x, y — расстояние до цели по горизонтали и вертикали соответственно)
    • euclidean — sqrt(x * x + y * y)
    • manhattan — abs(x) + abs(y)
    • chebyshev — max(abs(x), abs(y))
    • diagonal — min(x, y) * (sqrt(2) - 1) + max(x, y)
  • hweight — вес эвристики при подсчете f вершины
  • allowdiagonal — разрешено ли ходить по диагонали: true или false
  • cutcorners — разрешено ли ходить по диагонали, если с одной стороны стена: true или false
  • allowsqueeze — разрешено ли ходить по диагонали, если с обеих сторон стены: true или false
  • prioratizeconflicts — включено ли использование улучшения приоритезации конфликов в CBS: true или false
  • bypass — включено ли использование улучшения приоритезации конфликов в CBS: true или false
  • corridorsymmetry — включено ли использование улучшения распознавания конфликов в коридорах в CBS: true или false
  • targetsymmetry — включено ли использование улучшения распознавания конфликтов в конечных точках в CBS: true или false

• options

  • loglevel — уровень логирования, каждый следующий включает всю информацию предыдущего
    • 0 — ничего
    • 0.5 — только тег summary (подробнее в формате выходного файла)
    • 1 — путь на поле и в форматах hplevel и lplevel
    • 1.5 — тег lowlevel, в который записываются списки OPEN и CLOSED в конце работы алгоритма
    • 2 — в тег lowlevel списки OPEN и CLOSED записываются на каждом шаге алгоритма
  • logpath
  • logfilename

Визуализация

Визуализация происходит с помощью Python скрипта visualizer.py

После запуска передается путь до лог файла и автоматические начинается визуализация

Пример:

Контакты

Яковлев Константин Сергеевич

• kyakovlev@hse.ru
• Сайт НИУ ВШЭ
• Telegram: @KonstantinYakovlev

Дергачев Степан

• sadergachev@edu.hse.ru
• Telegram: @haiot4105