---
title: 【軟體】經典導航算法
tags: TTennis Pickup Robot
disqus: hackmd
---

<h1 style="text-align: center; color: orange;">
🛠️ 【軟體】經典導航算法 🛠️
</h1>

<h2 style="text-align: center; color: skyblue;"> 前言 </h2>

<center>

機器導航是在一地圖上進行的連續控制行為, 地圖和目的地都可能是未知的.
導航算法的目標, 是讓機器既快又優雅地走到目標.

關於地圖, 高精度的 dense map 可能會採用隨機灑點的算法策略.
精度較低的場景, 可以直接將地圖切分為一定精度的 grid map.

總之不同 scenario 下有其適應的導航算法, 也有很多可優化的面向.

</center>

</br>

<h2 style="text-align: center; color: skyblue;"> Dijkstra's vs. Best-First-Search</h2>

<center>

場景：網格地圖、地圖已知、目的地已知

Dijkstra's 其實就是導航場景下的廣度優先搜尋(BFS).
速度慢但一定是最佳路徑解.

Best-First-Search 顧名思義就是先走當下代價 $g(v)$ 最低的路徑, 是種貪心策略.
它不會去回頭考慮沒走到的路徑, 是否會比當前有更高的期望值.
此算法求解速度快, 但經常不是最佳解.

所謂代價, 可以是移動到該點的路徑長, 或是該點與目標的距離等.

所謂 greedy policy, 意指貪心地只考慮當下最優解的算法.
但會忽略先苦後甘且整體代價更小的路徑解.

另個名詞是 heuristic(啟發式的): 意指有使用經驗法則的演算法.

任意導航算法中如果有考慮**節點與目標點的距離函數**,
是歐式距離、曼哈頓距離還是其他啟發函數 $h(v)$ 才是最有效率的,
取決於場景跑圖經驗, 沒有標準答案, 我們會稱作是 heuristic 的.

Dijkstra's 就是一套制式標準的走法, 並不是 heuristic 的.

</center>

<h2 style="text-align: center; color: skyblue;"> A* algorithm</h2>

<center>

A* algorithm = Dijkstra's + Best-First-Search

A* 每次迭代, 會像 BFS 展開當前節點能行走到的點,
並考慮 spanning tree 中所有末節點的 $h(v)$+$g(v)$ 最低的走.

**在啟發函數定合適下, A* 會盡可能快地找到最優路徑.**

也就是說, A* 每走下步都會回頭考慮所有路徑可能性,
並搭配啟發函數合理地往正確方向移動或止損.
不會像 greedy policy 一定要撞牆才反悔, 但又不像 BFS 那樣純暴力展開.

</center>