Репозиторий проекта по курсу "МЕТОДЫ ЭВРИСТИЧЕСКОГО ПЛАНИРОВАНИЯ"
Проект основан на статье Hernandez Ulloa, C., Yeoh, W., Baier, J. A., Zhang, H., Suazo, L., & Koenig, S. (2020). A Simple and Fast Bi-Objective Search Algorithm и содержит реализацию алгоритмов бикритериального поиска BOA* и NAMOA*.
Проект реализован на Python 3.6 в виде тетрадки Jupyter Notebook и зависит от следующих библиотек:
- NetworkX, версия 2.5
- Numpy, версия 1.19.2
- Pandas, версия 1.0.5
- Matplotlib, версия 3.2.2
- tqdm, версия 4.47.0
Производительность реализаций алгоритмов сравнивалась на 100 случайно выбранных парах вершин из графа дорожной сети New York City соревнования 9th DIMACS Implementation Challenge - Shortest Paths
Продемонстрировано применение реализации BOA* к задаче поиска оптимальных путей на примере 8-связной карты duskwood от Moving AI Lab с двумя критериями: минимизация длины пути и максимизация безопасности пути. Безопасность проходимой клетки определяется как расстояние до ближайшей непроходимой клетки. Безопасность маршрута принимается равной сумме значений метрики безопосности для каждой клетки маршрута.