580 lines
34 KiB
TeX
580 lines
34 KiB
TeX
\documentclass[a4paper, final]{article}
|
||
%\usepackage{literat} % Нормальные шрифты
|
||
\usepackage[14pt]{extsizes} % для того чтобы задать нестандартный 14-ый размер шрифта
|
||
\usepackage{tabularx}
|
||
\usepackage[T2A]{fontenc}
|
||
\usepackage[utf8]{inputenc}
|
||
\usepackage[russian]{babel}
|
||
\usepackage{amsmath}
|
||
\usepackage[left=25mm, top=20mm, right=20mm, bottom=20mm, footskip=10mm]{geometry}
|
||
\usepackage{ragged2e} %для растягивания по ширине
|
||
\usepackage{setspace} %для межстрочно го интервала
|
||
\usepackage{moreverb} %для работы с листингами
|
||
\usepackage{indentfirst} % для абзацного отступа
|
||
\usepackage{moreverb} %для печати в листинге исходного кода программ
|
||
\usepackage{pdfpages} %для вставки других pdf файлов
|
||
\usepackage{tikz}
|
||
\usepackage{graphicx}
|
||
\usepackage{afterpage}
|
||
\usepackage{longtable}
|
||
\usepackage{float}
|
||
|
||
|
||
|
||
% \usepackage[paper=A4,DIV=12]{typearea}
|
||
\usepackage{pdflscape}
|
||
% \usepackage{lscape}
|
||
|
||
\usepackage{array}
|
||
\usepackage{multirow}
|
||
|
||
\renewcommand\verbatimtabsize{4\relax}
|
||
\renewcommand\listingoffset{0.2em} %отступ от номеров строк в листинге
|
||
\renewcommand{\arraystretch}{1.4} % изменяю высоту строки в таблице
|
||
\usepackage[font=small, singlelinecheck=false, justification=centering, format=plain, labelsep=period]{caption} %для настройки заголовка таблицы
|
||
\usepackage{listings} %листинги
|
||
\usepackage{xcolor} % цвета
|
||
\usepackage{hyperref}% для гиперссылок
|
||
\usepackage{enumitem} %для перечислений
|
||
|
||
\newcommand{\specialcell}[2][l]{\begin{tabular}[#1]{@{}l@{}}#2\end{tabular}}
|
||
|
||
|
||
\setlist[enumerate,itemize]{leftmargin=1.2cm} %отступ в перечислениях
|
||
|
||
\hypersetup{colorlinks,
|
||
allcolors=[RGB]{010 090 200}} %красивые гиперссылки (не красные)
|
||
|
||
% подгружаемые языки — подробнее в документации listings (это всё для листингов)
|
||
\lstloadlanguages{ SQL}
|
||
% включаем кириллицу и добавляем кое−какие опции
|
||
\lstset{tabsize=2,
|
||
breaklines,
|
||
basicstyle=\footnotesize,
|
||
columns=fullflexible,
|
||
flexiblecolumns,
|
||
numbers=left,
|
||
numberstyle={\footnotesize},
|
||
keywordstyle=\color{blue},
|
||
inputencoding=cp1251,
|
||
extendedchars=true
|
||
}
|
||
\lstdefinelanguage{MyC}{
|
||
language=SQL,
|
||
% ndkeywordstyle=\color{darkgray}\bfseries,
|
||
% identifierstyle=\color{black},
|
||
% morecomment=[n]{/**}{*/},
|
||
% commentstyle=\color{blue}\ttfamily,
|
||
% stringstyle=\color{red}\ttfamily,
|
||
% morestring=[b]",
|
||
% showstringspaces=false,
|
||
% morecomment=[l][\color{gray}]{//},
|
||
keepspaces=true,
|
||
escapechar=\%,
|
||
texcl=true
|
||
}
|
||
|
||
\textheight=24cm % высота текста
|
||
\textwidth=16cm % ширина текста
|
||
\oddsidemargin=0pt % отступ от левого края
|
||
\topmargin=-1.5cm % отступ от верхнего края
|
||
\parindent=24pt % абзацный отступ
|
||
\parskip=5pt % интервал между абзацами
|
||
\tolerance=2000 % терпимость к "жидким" строкам
|
||
\flushbottom % выравнивание высоты страниц
|
||
|
||
|
||
% Настройка листингов
|
||
\lstset{
|
||
language=python,
|
||
extendedchars=\true,
|
||
inputencoding=utf8,
|
||
keepspaces=true,
|
||
% captionpos=b, % подписи листингов снизу
|
||
}
|
||
|
||
\begin{document} % начало документа
|
||
|
||
|
||
|
||
% НАЧАЛО ТИТУЛЬНОГО ЛИСТА
|
||
\begin{center}
|
||
\hfill \break
|
||
\hfill \break
|
||
\normalsize{МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ\\
|
||
федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский политехнический университет Петра Великого»\\[10pt]}
|
||
\normalsize{Институт компьютерных наук и кибербезопасности}\\[10pt]
|
||
\normalsize{Высшая школа технологий искусственного интеллекта}\\[10pt]
|
||
\normalsize{Направление: 02.03.01 <<Математика и компьютерные науки>>}\\
|
||
|
||
\hfill \break
|
||
\hfill \break
|
||
\hfill \break
|
||
\hfill \break
|
||
\large{Реферат по дисциплине}\\
|
||
\large{<<Генетические алгоритмы>>}\\
|
||
\large{<<Планирование пути робота>>}\\
|
||
|
||
\hfill \break
|
||
\hfill \break
|
||
\end{center}
|
||
|
||
\small{
|
||
\begin{tabular}{lrrl}
|
||
\!\!\!Студент, & \hspace{2cm} & & \\
|
||
\!\!\!группы 5130201/20102 & \hspace{2cm} & \underline{\hspace{3cm}} &Тищенко А. А. \\\\
|
||
\!\!\!Преподаватель & \hspace{2cm} & \underline{\hspace{3cm}} & Большаков А. А. \\\\
|
||
&&\hspace{4cm}
|
||
\end{tabular}
|
||
\begin{flushright}
|
||
<<\underline{\hspace{1cm}}>>\underline{\hspace{2.5cm}} 2025г.
|
||
\end{flushright}
|
||
}
|
||
|
||
\hfill \break
|
||
% \hfill \break
|
||
\begin{center} \small{Санкт-Петербург, 2025} \end{center}
|
||
\thispagestyle{empty} % выключаем отображение номера для этой страницы
|
||
|
||
% КОНЕЦ ТИТУЛЬНОГО ЛИСТА
|
||
\newpage
|
||
|
||
\tableofcontents
|
||
|
||
|
||
\newpage
|
||
|
||
\section*{Введение}
|
||
\addcontentsline{toc}{section}{Введение}
|
||
Планирование пути мобильного робота — это задача построения коллизие-свободной траектории из начальной точки в целевую в присутствии препятствий и ограничений среды. Актуальность задачи обусловлена широким спектром приложений: от автономной логистики и сельского хозяйства до роботизированной инспекции и сервисной робототехники. Традиционные графовые методы (Дейкстра, A*) обеспечивают точный поиск на известных картах, однако их эффективность снижается при росте размерности, наличии динамики и сложных ограничений. Эволюционные подходы, в частности генетические алгоритмы (ГА), предоставляют гибкую эвристическую альтернативу, позволяя естественно учитывать несколько критериев качества и штрафы за нарушения ограничений.
|
||
|
||
Цель работы — исследовать применение ГА для планирования пути на дискретном представлении среды (grid) и в параметризации траекторий через направления движения (угловое кодирование), а также сравнить различные способы кодирования хромосом и их влияние на качество маршрутов и вычислительные затраты.
|
||
|
||
В работе:
|
||
\begin{itemize}
|
||
\item кратко рассмотрена классификация алгоритмов планирования пути по характеру среды (статическая/динамическая), принципу (глобальные/локальные) и полноте (точные/эвристические);
|
||
\item формализована фитнесс-функция с учётом длины пути и штрафов за пересечение препятствий, а для углового кодирования — с дополнительными слагаемыми за число поворотов;
|
||
\item изучены три варианта grid-кодирования узлов пути (двоичное, десятичное, упорядоченное) и угловое кодирование с 4 и 8 направлениями движения;
|
||
\item проведены эксперименты в статических сценах и сценарии с поэтапным появлением новых препятствий (offline/online-перепланирование);
|
||
\item сопоставлены метрики: длина маршрута, число поколений и время решения.
|
||
\end{itemize}
|
||
|
||
Полученные результаты демонстрируют применимость ГА к задачам планирования как в статических, так и в динамически меняющихся средах, а также выявляют влияние выбора представления пути на качество и стоимость поиска.
|
||
|
||
|
||
\newpage
|
||
\section{Постановка задачи}
|
||
Планирование пути робота -- вычисление пути, свободного от столкновений, от начальной позиции до конечной
|
||
среди множества препятствий
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.8\linewidth]{img/task.png}
|
||
\caption{Задача планирования пути}
|
||
\label{fig:task}
|
||
\end{figure}
|
||
|
||
\newpage
|
||
\section{Классификация алгоритмов планирования пути}
|
||
На схеме \ref{fig:classification} показана классификация алгоритмов планирования пути.
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=1\linewidth]{img/classification.png}
|
||
\caption{Классификация алгоритмов планирования пути}
|
||
\label{fig:classification}
|
||
\end{figure}
|
||
|
||
Алгоритмы планирования пути можно классифицировать по трём главным признакам:
|
||
|
||
\begin{itemize}
|
||
|
||
\item По характеру среды (based on environment)
|
||
|
||
\begin{itemize}
|
||
|
||
\item \textbf{Статические (Static)}
|
||
Используются, когда карта среды известна заранее и не меняется. Все препятствия заранее заданы, и алгоритм строит маршрут до старта движения.
|
||
Пример: классические алгоритмы поиска пути на графе (A*, Дейкстра).
|
||
|
||
\item \textbf{Динамические (Dynamic)}
|
||
Применяются в условиях, где препятствия могут появляться или перемещаться во время движения робота. Алгоритм должен уметь перестраивать путь «на лету» (онлайн-планирование).
|
||
Пример: D* Lite, Anytime Repairing A*, алгоритмы на основе предсказаний и реактивного управления.
|
||
\end{itemize}
|
||
|
||
|
||
\item По принципу алгоритма (based on algorithm)
|
||
|
||
\begin{itemize}
|
||
\item \textbf{Глобальные (Global)}
|
||
Предполагают знание полной карты окружающей среды. Алгоритм ищет оптимальный путь целиком от старта до цели.
|
||
Пример: A*, Дейкстра, волновой алгоритм (Wavefront).
|
||
|
||
\item \textbf{Локальные (Local)}
|
||
Робот строит путь только на основе данных с датчиков «здесь и сейчас». Такие методы хорошо работают в неизвестных или частично известных средах.
|
||
Пример: Bug Algorithms, Potential Fields, Dynamic Window Approach.
|
||
|
||
\end{itemize}
|
||
|
||
\item По полноте поиска (based on completeness)
|
||
|
||
\begin{itemize}
|
||
\item \textbf{Точные (Exact)}
|
||
Гарантируют нахождение решения (если оно существует), а также могут обеспечить оптимальность. Но часто требуют много вычислительных ресурсов.
|
||
Пример: алгоритм Дейкстры, точный A*.
|
||
|
||
\item \textbf{Эвристические (Heuristic)}
|
||
Используют приближённые методы и эвристики для ускорения поиска. Решение находится быстрее, но не всегда оптимальное.
|
||
Пример: эвристический A*, эволюционные методы (генетические алгоритмы, рой частиц, муравьиные алгоритмы).
|
||
|
||
\end{itemize}
|
||
|
||
\end{itemize}
|
||
|
||
|
||
|
||
\newpage
|
||
\section{Генетические алгоритмы для построения пути}
|
||
Для решения произвольной задачи с помощью ГА необходимо определить:
|
||
|
||
\begin{itemize}
|
||
\item особь и популяцию;
|
||
\item генетические операторы;
|
||
\item фитнесс функцию;
|
||
\item параметры ГА.
|
||
\end{itemize}
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.5\linewidth]{img/genalg.png}
|
||
\caption{Составляющие ГА}
|
||
\label{fig:genalg}
|
||
\end{figure}
|
||
|
||
\subsection{Grid-кодирование пути}
|
||
|
||
\subsubsection*{Кодирование хромосом}
|
||
Рассмотрим часто используемое на практике представление окружения робота в виде «решетки» -- сетки
|
||
(grid).
|
||
Для представления окружения используется:
|
||
\begin{itemize}
|
||
\item двоичное;
|
||
\item десятичное;
|
||
\item упорядоченное кодирование;
|
||
\end{itemize}
|
||
показанное на рисунке \ref{fig:grid} (белые клетки--свободное пространство, серые -- препятствия).
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.5\linewidth]{img/grid.png}
|
||
\caption{Grid-кодирование пути}
|
||
\label{fig:grid}
|
||
\end{figure}
|
||
|
||
Тогда хромосома (особь популяции) представляет потенциальное решение -
|
||
Путь от начальной точки S (левый верхний угол) до конечной точки- цели T (правый нижний угол)
|
||
Хромосома (путь робота) содержит начальную и конечную вершины графа, представляющего решетку, а
|
||
также вершины, пересекаемые роботом
|
||
Эти вершины (или шаги) называются генами хромосомы.
|
||
Различные методы кодирования используются для хромосомы, в зависимости от формы представления
|
||
окружения:
|
||
|
||
\newpage
|
||
\begin{enumerate}
|
||
\item Двоичное кодирование – содержит двоичные коды номеров строк и столбцов (координаты x,y)
|
||
«узловых» вершин пути.
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.5\linewidth]{img/binary.png}
|
||
\caption{Двоичное кодирование}
|
||
\label{fig:binary}
|
||
\end{figure}
|
||
\item Десятичное кодирование – содержит десятичные номера строк и столбцов (координаты x,y)
|
||
«узловых» вершин пути.
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.45\linewidth]{img/decimal.png}
|
||
\caption{Десятичное кодирование}
|
||
\label{fig:decimal}
|
||
\end{figure}
|
||
\item Упорядоченное кодирование - содержит номера(в общем порядке ячеек - вершин) проходимых
|
||
«узловых» вершин пути.
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.4\linewidth]{img/ordered.png}
|
||
\caption{Упорядоченное кодирование}
|
||
\label{fig:ordered}
|
||
\end{figure}
|
||
\end{enumerate}
|
||
|
||
|
||
\subsubsection*{Инициализация популяции}
|
||
Выполняется случайно
|
||
При этом некоторые построенные хромосомы соответствуют нереализуемым путям, которые пересекают
|
||
препятствия
|
||
В таблице представлены экспериментальные данные по генерации начальной популяции
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.5\linewidth]{img/table.png}
|
||
\caption{Таблица экспериментальных данных}
|
||
\label{fig:table}
|
||
\end{figure}
|
||
|
||
Далее находятся оптимальные или близкие к оптимальным решения (пути роботов), даже если начальная
|
||
популяция содержит нереализуемые решения
|
||
|
||
\subsubsection*{Фитнесс функция}
|
||
Целью планирования пути является построение пути робота между начальной и конечной точками.
|
||
Оптимальный путь должен иметь минимальную длину, время и минимальные энергозатраты.
|
||
Прежде всего, минимизируется длина пути.
|
||
Поэтому все эволюционные методы построения пути включают в фитнесс-функцию длину пути робота,
|
||
которая может быть определена следующим образом.
|
||
|
||
Здесь $P_i$
|
||
- i-й ген хромосомы $P$ , $d$ - расстояние между 2-мя узлами.
|
||
Фитнесс-функция для реализуемых путей определяется как сумма расстояний между узлами пути.
|
||
Заметим, что для нереализуемых путей (имеющих пересечения с препятствия) фитнесс-функция имеет
|
||
дополнительную штрафную функцию. Если между узлами встречается препятствие, то в фитнессфункцию добавляется штраф.
|
||
Для поиска пути робота используется классический ГА.
|
||
На последнем шаге итерации (поколения) в соответствии с вычисленными значениями фитнесс-функции
|
||
отбираются хромосомы для производства потомков с помощью генетических операторов кроссинговера
|
||
и мутации.
|
||
Для выбора родителей применяется ранговый отбор
|
||
|
||
\begin{equation}
|
||
f =
|
||
\begin{cases}
|
||
\displaystyle \sum_{i=1}^{n-1} d(p_i, p_{i+1}), & \text{для допустимых путей (без столкновений)}, \\[1.5ex]
|
||
\displaystyle \sum_{i=1}^{n-1} d(p_i, p_{i+1}) + \text{штраф}, & \text{для недопустимых путей}.
|
||
\end{cases}
|
||
\end{equation}
|
||
|
||
\begin{equation}
|
||
d(p_i, p_{i+1}) = \sqrt{(x_{(i+1)} - x_i)^2 + (y_{(i+1)} - y_i)^2},
|
||
\end{equation}
|
||
где $p_i = (x_i, y_i)$ — координаты $i$-й вершины пути.
|
||
|
||
|
||
\subsubsection*{Генетические операторы}
|
||
Для генерации потомков используется обычный 1-точечный кроссинговер с заданной вероятностью $P_c$.
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.7\linewidth]{img/crossover.png}
|
||
\caption{Одноточечный кроссинговер}
|
||
\label{fig:crossover}
|
||
\end{figure}
|
||
|
||
Пример на Рис.~\ref{fig:crossover} показывает кроссинговер для упорядоченного кодирования хромосом.
|
||
|
||
Далее к потомкам (каждому гену) с малой вероятностью $P_m$ применяется оператор мутации, который вносит
|
||
небольшое изменение в ген в зависимости от способа кодирования.
|
||
Мутация расширяет пространство поиска и препятствует преждевременной сходимости в локальном
|
||
экстремуме
|
||
|
||
\subsubsection*{Эксперименты}
|
||
|
||
\textbf{Эксперимент 1.} Построение пути проводилось в следующем окружении (сетка 16х16) с 8
|
||
препятствиями с использованием указанных выше методов кодирования хромосом.
|
||
|
||
Параметры ГА:
|
||
\begin{itemize}
|
||
\item Мощность популяции $N=60$;
|
||
\item Вероятности: кроссинговера $P_c=1.0$, мутации $P_m=0.1$
|
||
\end{itemize}
|
||
После 10 запусков ГА для каждого метода получены средние значения расстояния, число поколений и
|
||
время решения, которые представлены на
|
||
Рис.~\ref{fig:table1}.
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.45\linewidth]{img/experiment1.png}
|
||
\caption{Эксперимент 1}
|
||
\label{fig:experiment1}
|
||
\end{figure}
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.8\linewidth]{img/table1.png}
|
||
\caption{Таблица эксперимента 1}
|
||
\label{fig:table1}
|
||
\end{figure}
|
||
|
||
\newpage
|
||
\textbf{Эксперимент 2.} Эксперимент 2 для окружения с 7 препятствиями. Параметры ГА те же.
|
||
|
||
Данные для различных методов кодирования представлены на рисунке \ref{fig:table3}. Видно, что десятичное и упорядоченное кодирование показывают лучшие результаты.
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.45\linewidth]{img/experiment2.png}
|
||
\caption{Эксперимент 2}
|
||
\label{fig:experiment2}
|
||
\end{figure}
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.8\linewidth]{img/table2.png}
|
||
\caption{Таблица эксперимента 2}
|
||
\label{fig:table2}
|
||
\end{figure}
|
||
|
||
|
||
|
||
|
||
\subsection{Угловое кодирование пути}
|
||
|
||
\subsubsection*{Кодирование хромосом}
|
||
|
||
Для кодирования пути робота эволюционные методы используют различные методы.
|
||
Альтернативным рассмотренному ранее кодированию (узлов) вершин проходимого пути,
|
||
является кодирование на основе углов направлений движения робота.
|
||
Это можно сделать по-разному (с различной точностью).
|
||
На Рис.~\ref{fig:angle} представлены 2 варианта кодирования направлений движения:
|
||
|
||
а) 4 направления - робот может передвигаться по горизонталям и вертикалям.
|
||
|
||
б) 8 направлений- робот может передвигаться также по диагоналям.
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.7\linewidth]{img/angle.png}
|
||
\caption{Для кодирования направлений используются целые числа:\\ а) (0,1,2,3), либо
|
||
б) (0,1,2,3,4,5,6,7)}
|
||
\label{fig:angle}
|
||
\end{figure}
|
||
|
||
|
||
Тогда каждый ген в хромосоме представляет направление движения робота на следующем
|
||
шаге.
|
||
|
||
В этом случае хромосома (см. Рис.~\ref{fig:angle_chromosome}) представляет «коллекцию» направлений движения робота в каждой
|
||
точке, начиная от старта, и кончая финалом.
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.9\linewidth]{img/angle_chromosome.png}
|
||
\caption{Хромосома с угловым кодированием пути. D – целое число, определяющее направление движения на следующем шаге.}
|
||
\label{fig:angle_chromosome}
|
||
\end{figure}
|
||
|
||
\subsubsection*{Фитнесс-функция}
|
||
|
||
Фитнесс-функция в задаче планирования пути робота определяется следующим образом:
|
||
|
||
\begin{equation}
|
||
\text{Cost}(P) = w_1 D + w_2 O + w_3 C,
|
||
\end{equation}
|
||
|
||
где:
|
||
\begin{itemize}
|
||
\item $w_1, w_2, w_3$ -- коэффициенты (константы), задающие вклад каждой компоненты;
|
||
\item $D$ -- расстояние (длина) пути;
|
||
\item $O$ -- число пересекаемых ячеек препятствий;
|
||
\item $C$ -- число изменений направлений движения.
|
||
\end{itemize}
|
||
|
||
Особь (маршрут) с минимальным значением фитнесс-функции соответствует оптимальному пути.
|
||
Очевидно, что увеличение числа изменений направления приводит к увеличению времени движения,
|
||
а каждое пересечение препятствия сопровождается значительным штрафом.
|
||
|
||
|
||
\subsubsection*{Эксперименты}
|
||
|
||
\textbf{Эксперимент 1}. Метод апробирован на различного типа препятствиях с разным числом направлений движений (4 или 8).
|
||
Начальная точка -- (0,0). Конечная точка -- (15, 9).
|
||
В 1-м эксперименте использовались только статические препятствия.
|
||
|
||
На Рис.~\ref{fig:angle_experiment1}-\ref{fig:angle_experiment2} представлены результаты для 2- вариантов направлений движений(4 или 8), которые показывают способность ГА решать данную проблему.
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.7\linewidth]{img/angle_experiment1.png}
|
||
\caption{Загроможденные препятствия. \\ (a) 4 направления, (b) 8 направлений}
|
||
\label{fig:angle_experiment1}
|
||
\end{figure}
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.7\linewidth]{img/angle_experiment2.png}
|
||
\caption{Региональные препятствия. \\ (c) 4 направления, (d) 8 направлений}
|
||
\label{fig:angle_experiment2}
|
||
\end{figure}
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.7\linewidth]{img/angle_experiment3.png}
|
||
\caption{Препятствия окружают конечную точку. \\ (e) 4 направления, (f) 8 направлений}
|
||
\label{fig:angle_experiment3}
|
||
\end{figure}
|
||
|
||
|
||
\newpage
|
||
\textbf{Эксперимент 2.} Динамическую систему поиска пути можно разделить на две компоненты.
|
||
|
||
\begin{itemize}
|
||
\item Ищем маршрут по заранее заданной карте ещё до запуска робота (offline компонента).
|
||
\item Если робот встретил новые препятствия, которых не было в исходной карте, то запускается новый алгоритм поиска с актуальной точки (online компонента).
|
||
\end{itemize}
|
||
|
||
Сначал генетический алгоритм был запущен для статической среды (см.~Рис.~\ref{fig:static}).
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.7\linewidth]{img/static.png}
|
||
\caption{Запуск для статической среды (offline компонента)}
|
||
\label{fig:static}
|
||
\end{figure}
|
||
|
||
\newpage
|
||
И далее добавлялись (случайно) 1 препятствие (см. Рис.~\ref{fig:obstacle1}).
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.7\linewidth]{img/obstacle1.png}
|
||
\caption{Обновлённый путь после добавления ещё одного препятствия.}
|
||
\label{fig:obstacle1}
|
||
\end{figure}
|
||
|
||
И ещё одно препятствие (см. Рис.~\ref{fig:obstacle2}).
|
||
|
||
\begin{figure}[h!]
|
||
\centering
|
||
\includegraphics[width=0.7\linewidth]{img/obstacle2.png}
|
||
\caption{Обновлённый путь после добавления второго препятствия.}
|
||
\label{fig:obstacle2}
|
||
\end{figure}
|
||
|
||
|
||
|
||
\newpage
|
||
% ---------- ЗАКЛЮЧЕНИЕ ----------
|
||
\section*{Заключение}
|
||
\addcontentsline{toc}{section}{Заключение}
|
||
|
||
В работе рассмотрено применение генетических алгоритмов к задаче планирования пути робота на дискретной карте и в форме углового (направленного) кодирования. Показано, что:
|
||
\begin{enumerate}
|
||
\item Для grid-представления десятичное и упорядоченное кодирование обеспечивают в среднем более короткие пути и/или меньшее время поиска по сравнению с двоичным кодированием при сопоставимых параметрах ГА (\(N=60\), \(P_c=1.0\), \(P_m=0.1\)).
|
||
\item Угловое кодирование с 8 направлениями, как правило, даёт более гибкие и короткие траектории, чем с 4 направлениями, однако требует контроля числа поворотов (штраф \(C\)) для предотвращения «ломаных» маршрутов.
|
||
\item В динамическом сценарии поэтапное появление препятствий эффективно обрабатывается за счёт online-перепланирования: повторный запуск ГА из текущего положения восстанавливает коллизие-свободный путь без полной переразметки карты.
|
||
\end{enumerate}
|
||
|
||
Ограничения подхода включают чувствительность к настройкам операторов и вероятностей, риск преждевременной сходимости и вычислительные затраты при частых проверках коллизий.
|
||
|
||
ГА представляют собой практичный и переносимый инструмент планирования пути в условиях неопределённости и динамики, при этом выбор кодирования и архитектуры фитнесс-функции критически влияет на компромисс между качеством траектории и затратами вычислений.
|
||
|
||
|
||
|
||
\newpage
|
||
\section*{Список литературы}
|
||
\addcontentsline{toc}{section}{Список литературы}
|
||
|
||
\vspace{-1.5cm}
|
||
\begin{thebibliography}{0}
|
||
\bibitem{skobtsov} М.В. Прохоров, Ю.А. Скобцов. Многокритериальный генетический алгоритм построения пути робота в сложной среде. — Санкт-Петербург: СПбПУ, 2016. — 36с.
|
||
|
||
\bibitem{matveeva} Матвеева А.В. Оптимизация построения маршрута с помощью генетического алгоритма // Финансовый университет при Правительстве Российской Федерации, 2022. — С. 10–12.
|
||
\end{thebibliography}
|
||
|
||
\end{document} |