Поиск оптимального пути в 3D

1. Поиск оптимального пути в пространстве

Лицей-интернат для одарённых
детей Ставропольского края
Поиск оптимального
пути в пространстве
Дидур А.С.
Руководитель: ст. преподаватель кафедры защиты информации
СевКавГТУ Подопригора Н.Б.

2. Введение

Поиск пути (англ. Pathfinding) — термин в
информатике и искусственном интеллекте,
который означает определение компьютерной
программой наилучшего, оптимального
маршрута между двумя точками. Сегодня,
поиск оптимального пути в пространстве
является одной из ключевых задач
современных систем ИИ и многих других
областей науки и техники.
1

3.

На данный момент реализованы следующие функции:
Поиск кратчайшего пути
в одно-, дву-, трехмерных пространствах.
Искусственный интеллект
обхода препятствий.
Визуализация поиска на плоскости.
2

4.

Пространство и способы и его представления:
Для поиска в пространствах с различной размерностью я
разработал различные варианты их представления при
помощи графов. Связи между вершинами являются
вариантами передвижения из одной координаты в соседнюю.
Модель одномерного
пространства представляет
собой совокупность вершин
имеющих по две связи
(см. рис 1.1)
рис 1.1
3

5.

Пространство и способы и его представления:
Модель двумерного
пространства представляет
собой систему вершин,
имеющих по шесть связей
(см. рис 1.2).
Таким образом вершины
образовывают матрицу
координат в которых будет
происходить поиск.
рис 1.2
4

6.

Пространство и способы и его представления:
Модель трёхмерного
представляет собой
совокупность элементов
имеющих по десять
связей(см. рис 1.3).
Т.е. к каждой вершине
пространства в отличие
от двумерного добавляются
ещё и связи по высоте.
рис 1.3
5

7.

Чем программа реализующая поиск в трёхмерном
пространстве лучше других систем?
Возможность решать более широкий спектр задач.
Возможность при необходимости приспособить
решение задачи для любой размерности пространства.
Универсальность метода.
6

8.

Элементы интерфейса:
Пункт 1.) Сначала
пользователь выбирает
нужную ему размерность
пространства(см. рис 2.1).
по умолчанию выбрано 3D.
Пункт 2.) На данном этапе
пользователь ограничивает
пространство заданной
размерности в нужных ему
диапазонах(так же см. рис. 2.1).
рис 2.1
7

9.

Элементы интерфейса:
Пункты 3-4)Пользователь
определяет в пространстве
точки начала и пункта
назначения(см. рис 2.2).
Затем по желанию
располагаются
препятствия(они могут
располагаться случайно
или по усмотрению)
(см. рис 2.3).
рис 2.2
рис 2.3
8

10.

Элементы интерфейса:
Далее, по нажатии кнопки
“рассчитать” программа
определяет оптимальный
путь(см. рис 2.4) (если он
существует), и выводит
пользователю длину
оптимального пути. В
случае недосягаемости
точки назначения
программа выводит
соответствующее
сообщение(см. рис 2.5).
рис 2.4
рис 2.5
9

11.

Алгоритм:
В основу работы данной
программы вложен
алгоритм Ли. Данный
алгоритм построен на
трассировке пространства
лучами или волнами.
Препятствия являются
источниками вторичных
волн, что позволяет
отсканировать всё
пространство.
Элемент в который
пришла волна сам
становится фронтом
волны и т.д.(см. рис 3.1).
рис 3.1
10

12.

Алгоритм:
Если волна прошла все
доступные вершины, но
так и не достигла пункт
назначения, значит, путь
от старта до финиша
проложить
невозможно.(см рис.
3.2).После достижения
волной финиша, от
финиша прокладывается
путь до старта и
сохраняется в массиве.
рис 3.2
11

13.

Алгоритм:
К отрицательным чертам данного
метода следует отнести его низкую
производительность и большой объем
памяти требуемый для хранения
информации. Но был осуществлён выбор
именно этого метода так как в отличие от
других методов, он в процессе своей
работы находит кратчайший путь от
начальной вершины до каждой. Это очень
полезно в тех случаях когда точка
назначения может динамически
меняться, тогда нам потребуется только
одиножды просчитать пространство.
12

14.

Сфера применения:
Сфера применения алгоритмов трассировки
обширна, одна из них – автоматизированная
трассировка печатных плат(см. рис. 4.1).
рис 4.1
13

15.

Сфера применения:
Другая сфера применения – нахождение
кратчайшего пути на оцифрованных картах
местности(см. рис. 4.2-4.4.5).
рис 4.2
рис 4.4
рис 4.3
рис 4.5
14

16.

Как видим у алгоритмов достаточно широкое
применение и роль которую они начинают играть на
рынке увеличивается с каждым годом. Существуют
целые компании которые ведут свои исследования в
данном направлении. В данном контексте стоит
упомянуть фирмы Autodesk (U.S.A.) и Kynogon (Fr.).
Их главные направления разработки в этой области:
* Иерархический поиск пути в трёхмерном пространстве
* Алгоритмы координации командного взаимодействия
* Динамический анализ трёхмерной топологии и др.
15

17.

В программе планируются следующие
дополнения:
Исправление некоторых неполадок.
Улучшение графического интерфейса.
Введение наглядной системы трёхмерного рендеринга.
Считывание заданий из файла.
16

18.

Системные требования:
Процессор: 233 MHz
Оперативная память: 64 Мб RAM
Видеоадаптер и монитор: VGA (640 x 480)
Свободное место на HDD: 10 мб
Устройства взаимодействия с пользователем:
клавиатура,мышь
17

19.

Спасибо за внимание!!!