4: Планування шляху

Last updated
Save as PDF

Page ID: 32001

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Планування шляху є важливим примітивом для автономних мобільних роботів, який дозволяє роботам знаходити найкоротший - або в іншому випадку оптимальний - шлях між двома точками. Оптимальними шляхами можуть бути шляхи, які мінімізують кількість поворотів, кількість гальмування або те, що вимагає конкретне застосування. Алгоритми пошуку найкоротшого шляху важливі не тільки в робототехніці, але і в мережевій маршрутизації, відеоіграх і розумінні згортання білка.

Планування шляху вимагає карти навколишнього середовища і робота, щоб бути в курсі його розташування по відношенню до карти. Будемо вважати поки що робот здатний локалізуватися, оснащений картою і здатний обходити тимчасові перешкоди на своєму шляху. Як створити карту, як локалізувати робота, і як боротися з невизначеною інформацією про положення, будуть основними осередками нагадування про цю книгу. Цілі цієї глави полягають у тому, щоб

представити відповідні зображення карти,
пояснити основні алгоритми планування шляху, починаючи від Дейкстри, до A*, D* і RRT,
ввести варіації проблеми планування шляху, такі як планування траєкторії покриття.