Skip to content

Latest commit

 

History

History
92 lines (73 loc) · 5.76 KB

README.md

File metadata and controls

92 lines (73 loc) · 5.76 KB

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

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

Пример:

Alt Text

Контакты

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

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